数据结构——顺序表的基本操作
顺序表(详细)
·
目录
10.判断是否为空表(L.length是顺序表的长度,当表长等于0时,空表;不为0时,不空)
在数据结构课程中,顺序表有着很重要的作用,虽然说顺序表和数组类似,所以操作较为简单。
主要依据严蔚敏版数据结构教材。
这个文本,主要是针对线性表中的顺序表而操作的。以下代码为自己作业,如果有问题欢迎大家指点。
内容:
void print()
{
printf("\n\t输入数字来选择功能\n");
printf("\t0.退出\n");
printf("\t1.在L中第i个位置之前插入新的数据元素e,L的长度加1\n");
printf("\t2.删除L的第i个数据元素,并用e返回其值,L的长度减一\n");
printf("\t3.用e返回第i个元素的值\n");
printf("\t4.打印表\n");
printf("\t5.判断表是否为空\n");
printf("\t6.按值查找\n");
printf("\t7.求表的长度\n");
printf("\t8.求第i个元素的直接后继\n");
printf("\t9.求第i个元素的直接前驱\n");
printf("\t10.建表\n");
printf("\t11.摧毁顺序表\n");
printf("\t12.清空这个顺序表\n");
printf("\t13.在清空表的基础上重新输入这个表\n");
}
1.顺序表的定义
我们在这里可以使用结构体类型来定义
typedef struct{
int *elem; //顺序表基地址
int length; //顺序表当前长度
int listsize; //顺序表容量
}*Sqlist;
2.define和typedef
//define区
#define List_Init_Size 100
#define List_Increment 10
#define OK 1
#define OVERFLOW -2
#define ERROR 0
//预处理指令区
#include <stdio.h>
#include<stdlib.h>
#include<malloc.h>
3.以下所有用到函数的声明
//函数区
Status Initlist_Sq(Sqlist L); //建表,为表开放空间
Sqlist Creat(); //建表,并且输入表内的值
Status ListInsert_Sq(Sqlist L,int i,int e); //在L中第i个位置之前查人新的数据元素e,L的长度加1
Status ListDelete_Sq(Sqlist L,int i,int *e); //删除L的第i个数据元素,并用e返回其值,L的长度减一
Status GetElem_Sq(Sqlist L,int i,int *e); //用e返回第i个元素的值
void show(Sqlist L); //打印表
Status ListEmpty(Sqlist L); //查看表是否为空函数
void LocateElem(Sqlist L); //按值查找函数
void NextElem(Sqlist L,int i,int e); //求直接后继
void PriorElem(Sqlist L,int i,int e); //求直接前驱
Status OperateMenu(Sqlist L); //switch选择函数
void Length(Sqlist L); //求表长
void DestoryList(Sqlist L); //摧毁表操作
void ClearList(Sqlist L); //清空这个表
Sqlist InList(Sqlist L); //在清空表以后输入表的内容
void print(); //打印功能表函数
4.建表,为表开放空间
使用malloc函数来动态分配
malloc函数:用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存,且分配的大小就是程序要求的大小。
//建表,为表开放空间
Status Initlist_Sq(Sqlist L){
L->elem=(int*)malloc(List_Init_Size*sizeof(int));
if(!L->elem) exit(OVERFLOW); //存储分配失败
L->length=0; //空表长度为0
L->listsize=List_Init_Size; //初始化存储容量
return OK;
}
5.建表,并且输入表内的值
在我们准备输入的时候,需要先为它开方空间,所以要调用Initlist_Sq(Sqlist L)函数,在其后我们使用while循环进行输入,在末尾用printf打印信息显示已经完成。最后返回。
Sqlist Creat()
{
//输入表
printf("请输入表内元素(每个数字按空格相隔,以输入-1为终止条件):");
Sqlist L;
Initlist_Sq(L);
int e,i=0;
scanf("%d",&e);
while(e!=-1)
{
L->elem[i]=e;
L->length++;
i++;
scanf("%d",&e);
}
printf("表已经输好了\n\n");
return L;
}
6.在L中第i个位置之前查人新的数据元素e,L的长度加1
Status ListInsert_Sq(Sqlist L,int i,int e){
//在L中第i个位置之前查人新的数据元素e,L的长度加1
//i的合法值为1<=i<=L.length_Sq(L)+1
if(i<1||i>L->length)return ERROR; //i不合法
if(L->length>=L->listsize) //当前存储空间已满,增加分配
L->elem=(int*)realloc(L->elem,(L->listsize+List_Increment)*sizeof(int));
if(L->elem==NULL)return ERROR; //
L->listsize+=List_Increment; //增加容量
int *q,*p;
q=&L->elem[i-1];
for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p; //插入位置的以后元素右移
*q=e; //插入e
L->length++; //表长+1
return OK;
}
7.删除L的第i个数据元素,并用e返回其值,L的长度减一
Status ListDelete_Sq(Sqlist L,int i,int *e){
if(i<1||i>L->length)return ERROR; //检验合法性
int *q,*p;
p=&L->elem[i-1]; //p为被删除元素
*e = *p; //把被删除元素的值赋值给e
q=L->elem+L->length-1;
for(++p;p<=q;p++)*(p-1)=*p; //被删除元素以后的左移
L->length--; //表-1
return OK;
}
8.用e返回第i个元素的值(因为i对应着第i-1个位置)
Status GetElem_Sq(Sqlist L,int i,int *e){
if(i<1||i>L->length) printf("输入错误\n");
else {*e=L->elem[i-1]; printf("第%d的元素为%d\n\n",i,*e);
}
}
9.打印表的内容
void show(Sqlist L){
for(int j=0;j<L->length;j++){
printf("%d\t",L->elem[j]);
}
}
10.判断是否为空表(L.length是顺序表的长度,当表长等于0时,空表;不为0时,不空)
Status ListEmpty(Sqlist L)
{
if(L->length == 0){
printf("是空表\n\n");
}
else{
printf("不是空表\n\n");
}
}
11.按值查找函数(顺序查找)
void LocateElem(Sqlist L)
{
int e;
int k = 1;
printf("输入你要查找的元素:");
scanf("%d", &e);
for (int i = 0; i < L->length; i++)
if (L->elem[i] == e)
{
printf("找到了,是第%d个元素\n\n", i + 1);
k = 0;
break;
}
if (k)
printf("找不到元素%d\n\n", e);
}
12.求第i个元素的直接后继
void NextElem(Sqlist L,int i,int e)
{
if(i>L->length-1||i<=0) printf("输入有误\n\n");
else {e=L->elem[i];printf("第%d的元素的直接后继是%d\n\n",i,e);}
}
13.求第i个元素的直接前驱
void PriorElem(Sqlist L,int i,int e)
{
if(i>L->length||i<=0) printf("输入有误");
else {e=L->elem[i-2];printf("第%d的元素的直接前驱是%d\n\n",i,e);}
}
14.switch选择函数
Status OperateMenu(Sqlist L){
int num;
scanf("%d",&num);
while(num)
{
switch(num)
{
case 0://退出
num=0;
break;
case 1://在L中第i个位置之前查人新的数据元素e,L的长度加1
if(L==NULL||L->elem==NULL)
{
printf("在使用1号功能之前需要建表\n\n");
}else{
printf("在L中第i个位置之前插入新的数据元素e,L的长度加1\n");
printf("请输入插入位置和数据元素:");
int a,b;
scanf("%d %d",&a,&b);
ListInsert_Sq(L,a,b);
printf("已经插入完毕\n\n");
}
break;
case 2://删除L的第i个数据元素,并用e返回其值,L的长度减一
if(L==NULL||L->elem==NULL)
{
printf("在使用2号功能之前需要建表\n\n");
}else{
printf("删除L的第i个数据元素,并用e返回其值,L的长度减一\n");
printf("请输入删除位置:");
int c,d;
scanf("%d",&c);
ListDelete_Sq(L,c,&d);
printf("删除元素为%d\n",d);
}
break;
case 3://用e返回第i个元素的值
if(L==NULL||L->elem==NULL)
{
printf("在使用3号功能之前需要建表\n\n");
}else{
printf("用e返回第i个元素的值");
printf("请输入位置 i :");
int f,g;
scanf("%d",&f);
GetElem_Sq(L,f,&g);
}
break;
case 4://打印表
if(L==NULL||L->elem==NULL)
{
printf("在使用4号功能之前需要建表\n\n");
}else if(L->length==0)
{
printf("这个表是已经被清空\n");
}else{
printf("打印表\n");
printf("表为:\n");
show(L);
printf("\n\n");
}
break;
case 5://判断表是否为空
if(L==NULL||L->elem==NULL)
{
printf("在使用5号功能之前需要建表\n\n");
}else{
printf("判断表是否为空\n");
ListEmpty(L);
}
break;
case 6://按值查找
if(L==NULL||L->elem==NULL)
{
printf("在使用6号功能之前需要建表\n\n");
}else{
printf("按值查找\n");
LocateElem(L);
}
break;
case 7://求顺序表表长
if(L==NULL||L->elem==NULL)
{
printf("在使用7号功能之前需要建表\n\n");
}else{
printf("求顺序表表长\n");
Length(L);
printf("\n");
}
break;
case 8:
if(L==NULL||L->elem==NULL)
{
printf("在使用8号功能之前需要建表\n\n");
}else{
printf("求直接后继\n");
printf("请输入i:");
int h,j;
scanf("%d",&h);
NextElem(L,h,j);
}
break;
case 9:
if(L==NULL||L->elem==NULL)
{
printf("在使用9号功能之前需要建表\n\n");
}else{
printf("求直接前驱\n");
printf("请输入i:");
int k,m;
scanf("%d",&k);
if(k<=1||k>L->length)
{
printf("输入错误\n\n");
}else{
PriorElem(L,k,m);
}
}
break;
case 10:
printf("建表\n");
L=Creat();
break;
case 11:
if(L==NULL||L->elem==NULL)
{
printf("在使用11号功能之前需要建表\n\n");
}else{
printf("摧毁这个表\n");
DestoryList(L);
}
break;
case 12:
if(L==NULL||L->elem==NULL)
{
printf("在使用12号功能之前需要建表\n\n");
}else{
printf("清空这个表\n");
ClearList(L);
printf("清空表操作完成\n\n");;
}
break;
case 13:
if(L==NULL||L->elem==NULL)
{
printf("在使用13号功能之前需要建表\n\n");
}else{
if(L->length==0)
{
L=InList(L);
}else{
printf("必须是表清空了才能使用这个函数\n\n");
}
}
break;
default:
printf("输入有错\n\n");
}
printf("再次选择数据功能\n");
scanf("%d",&num);
}
}
15.输出表长
void Length(Sqlist L)//求表长
{
if (L->length == 0)
printf("表长度为0");
else
printf("表长为:%d\n",L->length);
}
16.摧毁表操作
void DestoryList(Sqlist L)
{
free(L->elem);
L->length=0;
L->listsize=0;
L->elem=NULL;;
printf("表已经摧毁,如果需要请重新建表\n\n");
}
17.//清空这个表
void ClearList(Sqlist L)
{
L->length=0;
}
18.在清空表以后输入表的内容
Sqlist InList(Sqlist L)
{
DestoryList(L);
Creat();
}
19.功能函数
void print()
{
printf("\n\t输入数字来选择功能\n");
printf("\t0.退出\n");
printf("\t1.在L中第i个位置之前插入新的数据元素e,L的长度加1\n");
printf("\t2.删除L的第i个数据元素,并用e返回其值,L的长度减一\n");
printf("\t3.用e返回第i个元素的值\n");
printf("\t4.打印表\n");
printf("\t5.判断表是否为空\n");
printf("\t6.按值查找\n");
printf("\t7.求表的长度\n");
printf("\t8.求第i个元素的直接后继\n");
printf("\t9.求第i个元素的直接前驱\n");
printf("\t10.建表\n");
printf("\t11.摧毁顺序表\n");
printf("\t12.清空这个顺序表\n");
printf("\t13.在清空表的基础上重新输入这个表\n");
}
代码全部:
//define区
#define List_Init_Size 100
#define List_Increment 10
#define OK 1
#define OVERFLOW -2
#define ERROR 0
//预处理指令区
#include <stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
//typedef区
typedef int Status;
typedef struct{
int *elem; //顺序表基地址
int length; //顺序表当前长度
int listsize;//顺序表容量
}*Sqlist;
//函数区
Status Initlist_Sq(Sqlist L); //建表,为表开放空间
Sqlist Creat(); //建表,并且输入表内的值
Status ListInsert_Sq(Sqlist L,int i,int e); //在L中第i个位置之前查人新的数据元素e,L的长度加1
Status ListDelete_Sq(Sqlist L,int i,int *e); //删除L的第i个数据元素,并用e返回其值,L的长度减一
Status GetElem_Sq(Sqlist L,int i,int *e); //用e返回第i个元素的值
void show(Sqlist L); //打印表
Status ListEmpty(Sqlist L); //查看表是否为空函数
void LocateElem(Sqlist L); //按值查找函数
void NextElem(Sqlist L,int i,int e); //求直接后继
void PriorElem(Sqlist L,int i,int e); //求直接前驱
Status OperateMenu(Sqlist L); //switch选择函数
void Length(Sqlist L); //求表长
void DestoryList(Sqlist L); //摧毁表操作
void ClearList(Sqlist L); //清空这个表
Sqlist InList(Sqlist L);
void print(); //打印功能表函数
//主函数
int main(){
char i;
print(); //输出功能部分
printf("如果想要开始程序,请输入Y或者y,如果不开始可以输入其他,直接退出\n");
scanf("%c",&i);
if(i=='Y'||i=='y'){
Sqlist L=NULL;
//Initlist_Sq(L); //建表
//Initlist_Sq(K);
//printf("请输入表内元素(每个数字按空格相隔,以输入-1为终止条件):");
/*int e;
for(int i=0;;i++){
scanf("%d",&e);
if(e==-1)break;
L->elem[i]=e;
L->length++;
}*/
print();
OperateMenu(L); //switch case判断语句
printf("程序退出了,下次见\n");
}else{
printf("程序截止\n");
}
}
//建表,为表开放空间
Status Initlist_Sq(Sqlist L){
L->elem=(int*)malloc(List_Init_Size*sizeof(int));
if(!L->elem) exit(OVERFLOW); //存储分配失败
L->length=0; //空表长度为0
L->listsize=List_Init_Size; //初始化存储容量
return OK;
}
Sqlist Creat()
{
//输入表
printf("请输入表内元素(每个数字按空格相隔,以输入-1为终止条件):");
Sqlist L;
Initlist_Sq(L);
int e,i=0;
scanf("%d",&e);
while(e!=-1)
{
L->elem[i]=e;
L->length++;
i++;
scanf("%d",&e);
}
printf("表已经输好了\n\n");
return L;
}
Status ListInsert_Sq(Sqlist L,int i,int e){
//在L中第i个位置之前查人新的数据元素e,L的长度加1
//i的合法值为1<=i<=L.length_Sq(L)+1
if(i<1||i>L->length)return ERROR; //i不合法
if(L->length>=L->listsize) //当前存储空间已满,增加分配
L->elem=(int*)realloc(L->elem,(L->listsize+List_Increment)*sizeof(int));
if(L->elem==NULL)return ERROR; //
L->listsize+=List_Increment; //增加容量
int *q,*p;
q=&L->elem[i-1];
for(p=&L->elem[L->length-1];p>=q;--p)*(p+1)=*p; //插入位置的以后元素右移
*q=e; //插入e
L->length++; //表长+1
return OK;
}
//删除L的第i个数据元素,并用e返回其值,L的长度减一
Status ListDelete_Sq(Sqlist L,int i,int *e){
if(i<1||i>L->length)return ERROR; //检验合法性
int *q,*p;
p=&L->elem[i-1]; //p为被删除元素
*e = *p; //把被删除元素的值赋值给e
q=L->elem+L->length-1;
for(++p;p<=q;p++)*(p-1)=*p; //被删除元素以后的左移
L->length--; //表-1
return OK;
}
//用e返回第i个元素的值
Status GetElem_Sq(Sqlist L,int i,int *e){
if(i<1||i>L->length) printf("输入错误\n");
else {*e=L->elem[i-1]; printf("第%d的元素为%d\n\n",i,*e);
}
}
//打印表
void show(Sqlist L){
for(int j=0;j<L->length;j++){
printf("%d\t",L->elem[j]);
}
}
//判断是否为空表
Status ListEmpty(Sqlist L)
{
if(L->length == 0){
printf("是空表\n\n");
}
else{
printf("不是空表\n\n");
}
}
//按值查找函数
void LocateElem(Sqlist L)
{
int e;
int k = 1;
printf("输入你要查找的元素:");
scanf("%d", &e);
for (int i = 0; i < L->length; i++)
if (L->elem[i] == e)
{
printf("找到了,是第%d个元素\n\n", i + 1);
k = 0;
break;
}
if (k)
printf("找不到元素%d\n\n", e);
}
//求第i个元素的直接后继
void NextElem(Sqlist L,int i,int e)
{
if(i>L->length-1||i<=0) printf("输入有误\n\n");
else {e=L->elem[i];printf("第%d的元素的直接后继是%d\n\n",i,e);}
}
//求第i个元素的直接前驱
void PriorElem(Sqlist L,int i,int e)
{
if(i>L->length||i<=0) printf("输入有误");
else {e=L->elem[i-2];printf("第%d的元素的直接前驱是%d\n\n",i,e);}
}
//switch选择函数
Status OperateMenu(Sqlist L){
int num;
scanf("%d",&num);
while(num)
{
switch(num)
{
case 0://退出
num=0;
break;
case 1://在L中第i个位置之前查人新的数据元素e,L的长度加1
if(L==NULL||L->elem==NULL)
{
printf("在使用1号功能之前需要建表\n\n");
}else{
printf("在L中第i个位置之前插入新的数据元素e,L的长度加1\n");
printf("请输入插入位置和数据元素:");
int a,b;
scanf("%d %d",&a,&b);
ListInsert_Sq(L,a,b);
printf("已经插入完毕\n\n");
}
break;
case 2://删除L的第i个数据元素,并用e返回其值,L的长度减一
if(L==NULL||L->elem==NULL)
{
printf("在使用2号功能之前需要建表\n\n");
}else{
printf("删除L的第i个数据元素,并用e返回其值,L的长度减一\n");
printf("请输入删除位置:");
int c,d;
scanf("%d",&c);
ListDelete_Sq(L,c,&d);
printf("删除元素为%d\n",d);
}
break;
case 3://用e返回第i个元素的值
if(L==NULL||L->elem==NULL)
{
printf("在使用3号功能之前需要建表\n\n");
}else{
printf("用e返回第i个元素的值");
printf("请输入位置 i :");
int f,g;
scanf("%d",&f);
GetElem_Sq(L,f,&g);
}
break;
case 4://打印表
if(L==NULL||L->elem==NULL)
{
printf("在使用4号功能之前需要建表\n\n");
}else if(L->length==0)
{
printf("这个表是已经被清空\n");
}else{
printf("打印表\n");
printf("表为:\n");
show(L);
printf("\n\n");
}
break;
case 5://判断表是否为空
if(L==NULL||L->elem==NULL)
{
printf("在使用5号功能之前需要建表\n\n");
}else{
printf("判断表是否为空\n");
ListEmpty(L);
}
break;
case 6://按值查找
if(L==NULL||L->elem==NULL)
{
printf("在使用6号功能之前需要建表\n\n");
}else{
printf("按值查找\n");
LocateElem(L);
}
break;
case 7://求顺序表表长
if(L==NULL||L->elem==NULL)
{
printf("在使用7号功能之前需要建表\n\n");
}else{
printf("求顺序表表长\n");
Length(L);
printf("\n");
}
break;
case 8:
if(L==NULL||L->elem==NULL)
{
printf("在使用8号功能之前需要建表\n\n");
}else{
printf("求直接后继\n");
printf("请输入i:");
int h,j;
scanf("%d",&h);
NextElem(L,h,j);
}
break;
case 9:
if(L==NULL||L->elem==NULL)
{
printf("在使用9号功能之前需要建表\n\n");
}else{
printf("求直接前驱\n");
printf("请输入i:");
int k,m;
scanf("%d",&k);
if(k<=1||k>L->length)
{
printf("输入错误\n\n");
}else{
PriorElem(L,k,m);
}
}
break;
case 10:
printf("建表\n");
L=Creat();
break;
case 11:
if(L==NULL||L->elem==NULL)
{
printf("在使用11号功能之前需要建表\n\n");
}else{
printf("摧毁这个表\n");
DestoryList(L);
}
break;
case 12:
if(L==NULL||L->elem==NULL)
{
printf("在使用12号功能之前需要建表\n\n");
}else{
printf("清空这个表\n");
ClearList(L);
printf("清空表操作完成\n\n");;
}
break;
case 13:
if(L==NULL||L->elem==NULL)
{
printf("在使用13号功能之前需要建表\n\n");
}else{
if(L->length==0)
{
L=InList(L);
}else{
printf("必须是表清空了才能使用这个函数\n\n");
}
}
break;
default:
printf("输入有错\n\n");
}
printf("再次选择数据功能\n");
scanf("%d",&num);
}
}
//输出表长
void Length(Sqlist L)//求表长
{
if (L->length == 0)
printf("表长度为0");
else
printf("表长为:%d\n",L->length);
}
//摧毁表操作
void DestoryList(Sqlist L)
{
free(L->elem);
L->length=0;
L->listsize=0;
L->elem=NULL;;
printf("表已经摧毁,如果需要请重新建表\n\n");
}
//清空这个表
void ClearList(Sqlist L)
{
L->length=0;
}
//在清空表以后输入表的内容
Sqlist InList(Sqlist L)
{
DestoryList(L);
Creat();
}
//功能函数
void print()
{
printf("\n\t输入数字来选择功能\n");
printf("\t0.退出\n");
printf("\t1.在L中第i个位置之前插入新的数据元素e,L的长度加1\n");
printf("\t2.删除L的第i个数据元素,并用e返回其值,L的长度减一\n");
printf("\t3.用e返回第i个元素的值\n");
printf("\t4.打印表\n");
printf("\t5.判断表是否为空\n");
printf("\t6.按值查找\n");
printf("\t7.求表的长度\n");
printf("\t8.求第i个元素的直接后继\n");
printf("\t9.求第i个元素的直接前驱\n");
printf("\t10.建表\n");
printf("\t11.摧毁顺序表\n");
printf("\t12.清空这个顺序表\n");
printf("\t13.在清空表的基础上重新输入这个表\n");
}
运行结果:
如果不建表输入其他功能:
先建表:
功能一:
功能二:
功能三:
功能四:
功能五:
功能六:
功能七:
功能八:
功能九:
更多推荐
所有评论(0)