发布时间：2025-06-24 17:02:51  作者：北方职教升学中心  阅读量：284

栈、链表、

2.2分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

• 缺陷：显而易见的，空间一定，给少了不够用，给多了太浪费

2.2.2 动态顺序表

概念：不存储数组，而是存储一个指向一块动态开辟的内存空间的指针

• 优点：按需开辟，可增容

  故我们一般都使用动态顺序表

---

2.3 动态顺序表的实现

2.3.1动态顺序表的初始化和销毁及打印

创建顺序表，并将其中的指针置为NULL，容量和有效数据个数置为0，销毁大致相同，不过如果arr指针非空，不要忘了释放动态申请的空间

SeqList.h(其中方法会一一讲到)

• 定义顺序表结构
• 将存储数据类型重命名(方便之后替换->例如我们要求顺序表内存储char类型数据，只用改一行代码即可)
• 所写的函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintsldatatype;typedefstructSeqlist{sldatatype*arr;sldatatype size;sldatatype capacity;}sl;voidslinit(sl*);//初始化voidsldestroy(sl*);//销毁voidslprint(sl*);//打印voidcheckcapacity(sl*);//判断空间是否足够voidslpushback(sl*,sldatatype);//尾插voidslpushfront(sl*,sldatatype);//头插voidslpopfront(sl*);//头删voidslpopback(sl*);//尾删//在指定位置插入和删除数据voidslinsert(sl*,sldatatype,int);voidslfrase(sl*,int);//查找指定数据intslfind(sl*,sldatatype);

test.c

• 用来测试我们写的函数(函数的调用)
• 这一部分就是自己写的时候用的测试用例，随便什么都行

最好是写一个方法测试一次，不然找错误的时候会很痛苦😜

sl s;//要改变s结构体之中的内容，别忘了传地址#define_CRT_SECURE_NO_WARNINGS1#include"Seqlist.h"voidsltest1(){sl s;slinit(&s);slpushback(&s,1);slpushback(&s,2);slpushback(&s,6);slpushback(&s,5);intm=slfind(&s,7);printf("%dn",m);//slpushfront(&s, 2);//slpushfront(&s, 3);//slinsert(&s, 1, 0);//slinsert(&s, 2, 6);//slinsert(&s, 1,0 );//slfrase(&s, 1);//slfrase(&s, 0);//slfrase(&s, 1);//slpopback(&s);//slpopback(&s);//slpopback(&s);//slpopback(&s);//slpopback(&s);slpushback(NULL, 6);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);//slpopfront(&s);slprint(&s);sldestroy(&s);}intmain(){sltest1();return0;}

SeqList.c

函数方法的实现，重点重点！！！

在每一个方法的第一排都使用assert宏来判断ps是否为空（避免使用时传入空指针，后续解引用都会报错）

voidslinit(sl*ps){assert(ps);ps->arr =NULL;ps->capacity =ps->size =0;}voidsldestroy(sl*ps){assert(ps);if(ps->arr){free(ps->arr);ps->arr =NULL;}ps->capacity =ps->size =0;}

考虑到每次测试方法时调试会很麻烦，于是先写一个打印顺序表的方法

voidslprint(sl*ps){assert(ps);inti =0;for(i =0;i <ps->size;i++){printf("%d ",ps->arr[i]);}}

• 遍历就行了，和打印数组一样的

---

2.3.2动态顺序表的插入

插入数据的时候一定要判断空间是否足够，不足要增容，一般2倍或3倍增容！！！

SeqList.c

养成好习惯，不要用arr直接接收动态开辟空间的地址，否则开辟失败arr变为NULL，连原来的内存块都找不到了，这就造成了内存泄漏！！！

voidslcheckcapacity(sl*ps){assert(ps);if(ps->capacity ==ps->size){//增容//若capacity为0，给个默认值，否则乘以2intnewcapacity =ps->capacity ==0?4:2*ps->capacity;sldatatype*tmp =(sldatatype*)realloc(ps->arr,newcapacity *sizeof(sldatatype));if(tmp ==NULL){perror("realloc fail!");exit(1);}ps->arr =tmp;ps->capacity =newcapacity;}}

动态顺序表的尾插

SeqList.c

voidslpushback(sl*ps,sldatatype x){assert(ps);slcheckcapacity(ps);ps->arr[ps->size++]=x;}

• 插入后size++即可了

动态顺序表的头插

SeqList.c

voidslpushfront(sl*ps,sldatatype x){assert(ps);slcheckcapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i -1];}ps->arr[0]=x;ps->size++;}

• 先让每个数据往后一位，注意一定要从后往前挪，否则数据会被覆盖

• 记得size++

动态顺序表的在指定位置插入数据

SeqList.c

voidslinsert(sl*ps,sldatatype x,intpos){assert(ps);assert(pos >=0&&pos <=ps->size);slcheckcapacity(ps);for(inti =ps->size;i >pos;i--){ps->arr[i]=ps->arr[i -1];}ps->arr[pos]=x;ps->size++;}

• 类似头插，涉及到pos以及之后数据的向后移动，还是从后往前挪动
• size++

---

2.3.3动态顺序表的删除

动态顺序表的尾删

删除数据的时候一定要判断顺序表是否为空，即size不能为0！！！

SeqList.c

voidslpopback(sl*ps){assert(ps &&ps->size);ps->size--;//ps->arr[ps->size] = 0;多余了，没有必要}

• 只要让size–即可，不影响后来的插入(数据会被覆盖)

动态顺序表的头删

SeqList.c

voidslpopfront(sl*ps){assert(ps &&ps->size);for(inti =0;i <ps->size-1;i++){ps->arr[i]=ps->arr[i +1];}ps->size--;}

• 让每一位向前移动一位，从前往后挪，防止数据覆盖
• 记得size–

动态顺序表的在指定位置删除数据

SeqList.c

voidslfrase(sl*ps,intpos){assert(ps);assert(pos >=0&&pos <ps->size);//包含了顺序表不为空的限定条件for(inti =pos;i <ps->size-1;i++){ps->arr[i]=ps->arr[i +1];}ps->size--;}

• 类似头删，让pos以及之后的数据向前一位，从前往后挪
• size–

---

2.3.4动态顺序表查找指定数据

SeqList.c

intslfind(sl*ps,sldatatype x){assert(ps);inti =0;intflag =0;for(i =0;i <ps->size;i++){if(ps->arr[i]==x){flag =1;break;}}if(flag)return1;else{return-1;}}

• 遍历就完事了，相信各位已经熟练掌握了(❁´◡`❁)
• 如果找到返回1，没找到就返回-1（使用bool类型也是可以滴）

---

SeqList.c(完整版)

#include"Seqlist.h"voidslinit(sl*ps){ps->arr =NULL;ps->capacity =ps->size =0;}voidsldestroy(sl*ps){assert(ps);if(ps->arr){free(ps->arr);ps->arr =NULL;}ps->capacity =ps->size =0;}voidslprint(sl*ps){assert(ps);inti =0;for(i =0;i <ps->size;i++){printf("%d ",ps->arr[i]);}}voidslcheckcapacity(sl*ps){assert(ps);if(ps->capacity ==ps->size){//增容//若capacity为0，给个默认值，否者乘以2intnewcapacity =ps->capacity ==0?4:2*ps->capacity;sldatatype*tmp =(sldatatype*)realloc(ps->arr,newcapacity *sizeof(sldatatype));if(tmp ==NULL){perror("realloc fail!");exit(1);}ps->arr =tmp;ps->capacity =newcapacity;}}voidslpushback(sl*ps,sldatatype x){assert(ps);slcheckcapacity(ps);ps->arr[ps->size++]=x;}voidslpushfront(sl*ps,sldatatype x){assert(ps);slcheckcapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i -1];}ps->arr[0]=x;ps->size++;}voidslpopback(sl*ps){assert(ps &&ps->size);ps->size--;//ps->arr[ps->size] = 0;多余了，没有必要}voidslpopfront(sl*ps){assert(ps &&ps->size);for(inti =0;i <ps->size-1;i++){ps->arr[i]=ps->arr[i +1];}ps->size--;}voidslinsert(sl*ps,sldatatype x,intpos){assert(ps);assert(pos >=0&&pos <=ps->size);slcheckcapacity(ps);for(inti =ps->size;i >pos;i--){ps->arr[i]=ps->arr[i -1];}ps->arr[pos]=x;ps->size++;}voidslfrase(sl*ps,intpos){assert(ps);assert(pos >=0&&pos <ps->size);//还有更多的限制如顺序表不能为空for(inti =pos;i <ps->size-1;i++){ps->arr[i]=ps->arr[i +1];}}intslfind(sl*ps,sldatatype x){assert(ps);inti =0;intflag =0;for(i =0;i <ps->size;i++){if(ps->arr[i]==x){flag =1;break;}}if(flag)return1;else{return-1;}}

以上就是顺序表的实现方法啦，各位大佬有什么问题欢饮在评论区指正，您的支持是我创作的最大动力！❤️