数据结构之顺序表的实现
程序员文章站
2022-06-22 08:41:11
数据结构之顺序表的实现 一、原理 1.定义 顺序表是在计算机中以数组形式保存的。 2.特点 在计算机中占用连续的一段内存 一旦声明,空间大小一般不变 二、初始化相关操作 包括: 1. 结构体的定义 2. 顺序表的创建 3. 顺序表清空 4. 判断顺序表是否为空 1.结构体定义 即定一个满足顺序表定义 ......
数据结构之顺序表的实现
一、原理
1.定义
顺序表是在计算机中以数组形式保存的。
2.特点
-
在计算机中占用连续的一段内存
-
一旦声明,空间大小一般不变
二、初始化相关操作
包括:
- 结构体的定义
- 顺序表的创建
- 顺序表清空
- 判断顺序表是否为空
1.结构体定义
即定一个满足顺序表定义的结构体,其中包含 数组、存储长度、总长度。
typedef int elemtype; //将int抽象为elemtype,表明顺序表也可以存储其他类型(如将int改为char) struct list { elemtype *list; //声明数组用于给顺序表存储数据,等价于以下声明方式 //elemtype[] list; int length; //用于记录顺序表存储的数据长度 int maxsize; //用于记录顺序表最大长度(即最多存储数据) }
2.初始化
对顺序表进行初始化,包括分配自定义长度的数组空间,设定存储长度为0,存储长度为规定值
//初始化,传入需要初始化的顺序表和初始化长度 void initlist(struct list *l,int maxsize){ //初始化长度合法性判断 if(maxsize<0){ printf("初始化长度非法!\n"); exit(1); //退出程序 } //对顺序表长度进行赋值 l->maxsize = maxsize; //根据初始化长度和存储数据类型来动态分配数组 l->list = malloc(sizeof(maxsize*sizeof(elemtype))); //分配成功判定 if(!l->list){ printf("动态分配存储失败\n"); exit(1); } //初始化存储数据为0个 l->length = 0; }
3.清空
将顺序表内容清空,用于某些题目要求或节省空间
//清空,传入需要清空的顺序表 void clearlist(struct list *l){ //判断顺序表是否已经为空 if(l->list!=null){ free(l->list); //释放顺序表中数组内存 l->list = 0; l->length = 0; l->maxsize = 0; } }
4. 判断是否为空
判断顺序表是否为空,在某些操作之前,先要判断顺序表是否为空,防止出错
int isempty(struct list *l){ return l->length==0?1:0; //顺序表最大长度为0则为空返回1,否则返回0 }
三、增加相关操作
包括:
- 向表头插入元素x
- 向表尾插入元素x
- 向第n个位置插入元素x
- 向递增的线性表中插入元素x,之后仍然保持有序
进行操作之前,还需要一个方法,当插入元素超过数组长度时,将数组容量扩大,即重新申请空间
tip:将顺序表扩大一倍空间
void remalloc(struct list *l){ elemtype *p = realloc(l->list,2*l->maxsize*sizeof(elemtype)); if(!p){ printf("空间分配失败\n"); exit(1); } l->list = p; //使list重新指向新生成的空间 l->maxsize = 2*l->maxsize; printf("存储空间已经扩大为2倍\n"); }
1.向表头插入元素x
void insertelemtohead(struct list *l,elemtype x){ int i; //判断存储空间是否已满 if(l->length==l->maxsize){ printf("存储空间已满,重新分配中..."); remalloc(l); } //所有元素后移 for(i=l->length;i>0;i--){ l->list[i+1]=l->list[i]; } l->list[i]=x; l->length++; }
2.向表尾插入元素x
void insertelemtotail(struct list *l,elemtype x){ //判断存储空间是否已满 if(l->length==l->maxsize){ printf("存储空间已满,重新分配中..."); remalloc(l); } l->list[l->length++]=x; }
3.向线性表l的第n个位置插入元素x
void insertelemsomewhere(struct list *l,elemtype x,int n){ //判断存储空间是否已满 if(l->length==l->maxsize){ printf("存储空间已满,重新分配中..."); remalloc(l); } int i; for(i=l->length;i>=n;i--){ l->list[i] = l->list[i-1]; } l->list[i] = x; l->length--; }
四、删除相关操作
包括:
-
删除表头元素并返回被删除的值
-
删除第n个元素并返回被删除元素
-
从线性表l中删除值为x的第一个元素
1.删除表头元素并返回被删除的值
删除表头第一个元素,长度减少1,返回被删除的值
elemtype delheadelem(struct list *l){ elemtype x = l->list[0]; //合法性判断 if(l->length==0){ printf("线性表为空,不能删除\n"); exit(1); } for(int i=0;i<l->length;i++){ l->list[i] = l->list[i+1]; } l->length--; return x; }
2.删除第n个元素并返回被删除元素
elemtype delsomeelem(struct list *l,int n){ if(n<l->length){ printf("n位置越界,不能删除"); exit(1); } elemtype x = l->list[n-1]; for(int i=n;i<l->length;i++){ l->list[i]=l->list[i+1]; } l->length--; retur x; }
3.从线性表l中删除值为x的第一个元素
从线性表l中删除值为x的第一个元素,若删除成功则返回1,否则返回0
int delelemknown(struct list *l,elemtype x){ int i,j; //先找出值为x的下标 for(i=0;i<l->length;i++){ if(l->list[i]==x){ break; } } for(j=i;i<l->length;j++){ l->list[j]=l->list[j+1]; } l->length--; return 1; }
五、修改相关操作
包括:
- 把线性表中第n个元素修改为x
1.把线性表中第n个元素修改为x
把线性表中第n个元素修改为x,若成功则返回1,失败返回0
int updateelemknown(struct list *l,elemtype x,int n){ if(n>l->length||n<1){ return 0; } l->list[n]=x; return 1; }
六、查找相关操作
包括:
-
查找第n个位置的值
-
顺序遍历输出所有值
-
返回值等于x的下标
1.查找第n个位置的值
输入要查找的坐标,若合法则范围对应的值,若非法则提示并推出
int getelem(struct list *l,int n){ if(n<0||n>l->maxsize){ printf("查找位置超出长度!\n"); exit(1); } return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数,而数组是从0开始计数 }
2.顺序遍历输出所有值
输出顺序表中的所有值
void getall(struct list *l){ int i = 0; while(i<l->length){ printf(l->list[i]+"\t"); i++; } printf("\n"); }
3.查找值为x的节点并返回其坐标
输入要查找的值x,若存在则范围首次出现的下标,否则返回0
void findelem(struct list *l,elemtype x){ int i; for(i=0;i<l->length;i++){ if(l->list[i]==x){ return i; } } }
七、总结
1.优点
- 查找方便
- 空间利用率高
2.缺点
- 删除和增加操作效率低
- 空间固定,不易扩展
八、完整代码
#include "stdio.h" #include <stdlib.h> /** * =======顺序表的定义========= */ typedef int elemtype; //结构体定义 struct list{ elemtype *list;//存储数据 int length;//存储长度 int maxsize;//最大长度 }; //初始化 void initlist(struct list *l,int maxsize){ //初始化长度合法性判断 if(maxsize<0){ printf("初始化长度非法!\n"); exit(1); //退出程序 } l->maxsize = maxsize; l->list = malloc(sizeof(maxsize* sizeof(elemtype))); //判断分配空间是否成功 if(!l->list){ printf("空间分配失败"); exit(1); } l->length=0; } //清空 void clearlist(struct list *l){ if(l->list!=null){ free(l->list); l->list=0; l->maxsize=0; l->length=0; } } //判空 int isempty(struct list *l){ return l->length==0?1:0; } /** * =======增加操作========= */ //空间再分配 void remalloc(struct list *l){ elemtype *p = realloc(l->list,2*l->maxsize* sizeof(elemtype)); if(!p){ printf("空间分配失败"); exit(1); } l->list = p; l->maxsize = 2*l->maxsize; printf("空间已扩大两倍"); } //向表头插入元素 void insertelemtohead(struct list *l,elemtype x){ if(l->length==l->maxsize){ remalloc(l); printf("空间已满,重新分配中"); } for(int i=l->length;i>0;i++){ l->list[i-1] = l->list[i]; } l->list[0] = x; l->length++; } //向表尾插入元素 void insertelemtotail(struct list *l,elemtype x){ if(l->length==l->maxsize){ remalloc(l); printf("空间已满,重新分配中"); } l->list[l->length++] = x; } //向线性表l的第n个位置插入元素x void insertelemsomewhere(struct list *l,elemtype x,int n){ int i; if(l->length==l->maxsize){ remalloc(l); printf("空间已满,重新分配中"); } for(i=l->length;i>=n;i--){ l->list[i]=l->list[i-1]; } l->list[i]=x; l->length++; } /** * =======删除操作========= */ //删除表头元素并返回被删除的值 void delheadelem(struct list *l){ elemtype x = l->list[0]; if(l->length==0){ printf("顺序表为空,删除失败!"); exit(1); } for(int i=1;i<l->length;i++){ l->list[i-1] = l->list[i]; } l->length--; } //删除第n个元素并返回被删除元素 elemtype delsomeelem(struct list *l,int n){ elemtype x = l->list[n-1]; if(n>l->length){ printf("n位置越界,不能删除"); exit(1); } for(int i=n;i<l->length;i++){ l->list[i-1] = l->list[i]; } l->length--; return x; } //从线性表l中删除值为x的第一个元素 int delelemknown(struct list *l,elemtype x){ int i,j; for(i=0;i<l->length;i++){ if(l->list[i]==x){ break; } } for(j=i;j<l->length;j++){ l->list[j]=l->list[j+1]; } l->length--; return 1; } /** * =======修改操作========= */ //把线性表中第n个元素修改为x int updateelemknown(struct list *l,elemtype x,int n){ if(n>l->length||n<1){ return 0; } l->list[n]=x; return 1; } /** * =======查找操作========= */ //查找第n个位置的值 int getelem(struct list *l,int n){ if(n<0||n>l->maxsize){ printf("查找位置超出长度!\n"); exit(1); } return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数,而数组是从0开始计数 } //顺序遍历输出所有值 void getall(struct list *l){ int i = 0; while(i<l->length){ printf("%d\t",l->list[i]); i++; } printf("\n"); } //查找值为x的节点并返回其坐标 int findelem(struct list *l,elemtype x){ int i; for(i=0;i<l->length;i++){ if(l->list[i]==x){ return i; } } } //主函数 int main() { //初始化操作测试 struct list l; initlist(&l,20); //插入操作测试 insertelemtohead(&l,2); insertelemsomewhere(&l,4,2); insertelemtotail(&l,5); printf("%d\n",l.list[0]); printf("%d\n",l.list[1]); //删除操作测试 delelemknown(&l,2); printf("%d\n",l.list[0]); //修改操作测试 updateelemknown(&l,8,1); //查找操作测试 printf("%d\n",getelem(&l,2)); printf("%d\n",findelem(&l,8)); printf("%d\n",l.list[0]); getall(&l); }