数据结构之顺序表的实现
⼀、原理
1.定义
顺序表是在计算机中以数组形式保存的。
2.特点
在计算机中占⽤连续的⼀段内存⼀旦声明，空间⼤⼩⼀般不变
⼆、初始化相关操作
包括：
1. 结构体的定义2. 顺序表的创建3. 顺序表清空
4. 判断顺序表是否为空
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}
三、增加相关操作
包括：
1. 向表头插⼊元素x2. 向表尾插⼊元素x
3. 向第n个位置插⼊元素x
4. 向递增的线性表中插⼊元素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--;}
四、删除相关操作
包括：
1. 删除表头元素并返回被删除的值2. 删除第n个元素并返回被删除元素3. 从线性表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--; return x;} 2.删除第n个元素并返回被删除元素 ElemType delSomeElem(struct List *L,int n){ if(n printf(\"n位置越界，不能删除\"); exit(1); } ElemType x = L->list[n-1]; for(int i=n;i 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 for(j=i;i L->length--; return 1;} 五、修改相关操作 包括： 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;} 六、查找相关操作 包括： 1. 查找第n个位置的值2. 顺序遍历输出所有值3. 返回值等于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 printf(\"\\n\");} 3.查找值为x的节点并返回其坐标 输⼊要查找的值x，若存在则范围⾸次出现的下标，否则返回0 void findElem(struct List *L,ElemType x){ int i; for(i=0;i 七、总结 1.优点 查找⽅便空间利⽤率⾼ 2.缺点 删除和增加操作效率低 空间固定，不易扩展 ⼋、完整代码 #include \"stdio.h\"#include * =======顺序表的定义========= */ 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--;} //删除第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--; return x;} //从线性表L中删除值为X的第⼀个元素 int delElemKnown(struct List *L,ElemType x){ int i,j; for(i=0;i for(j=i;j 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 printf(\"%d\\ i++; } printf(\"\\n\"); } //查找值为x的节点并返回其坐标 int findElem(struct List *L,ElemType x){ int i; for(i=0;i //主函数int main(){ //初始化操作测试 struct List L; initList(&L,20); //插⼊操作测试 insertElemToHead(&L,2); insertElemSomewhere(&L,4,2); insertElemToTail(&L,5); printf(\"%d\\n\ printf(\"%d\\n\ //删除操作测试 delElemKnown(&L,2); printf(\"%d\\n\ //修改操作测试 updateElemKnown(&L,8,1); //查找操作测试 printf(\"%d\\n\ printf(\"%d\\n\ printf(\"%d\\n\ getAll(&L);} 因篇幅问题不能全部显示，请点此查看更多更全内容