C语言全面讲解顺序表使用操作

第C语言全面讲解顺序表使用操作目录一、顺序表的结构定义二、顺序表的结构操作1.初始化2.插入操作3.删除操作4.扩容操作5.释放操作6.输出三、示例编程环境为ubuntu18.04。

顺序表需要连续一片存储空间，存储任意类型的元素，这里以存储int类型数据为例。

一、顺序表的结构定义

size为容量，length为当前已知数据表元素的个数

typedefstructVector{

int*data;//该顺序表这片连续空间的首地址

intsize,length;

}Vec;

二、顺序表的结构操作

1.初始化

Vec*init(intn){//该顺序表具有n个存储单元

Vec*v=(Vec*)malloc(sizeof(Vec));//在内存栈上开辟一个空间malloc在内存的堆区，在函数外面也能访问

v-data=(int*)malloc(sizeof(int)*n);

v-size=n;

v-length=0;

returnv;

}

2.插入操作

intinsert(Vec*v,intind,intval){//ind为插入元素的位置,val为插入元素的值

if(v==NULL)return0;

if(ind0||indv-length)return0;//判断要插入的位置是否合法

if(v-length==v-size){

if(!expand(v)){//扩容失败

printf(RED("failtoexpand!\n"));

printf(GREEN("successtoexpand!thesize=%d\n"),v-size);

for(inti=v-length;iind;i--){

v-data[i]=v-data[i-1];

v-data[ind]=val;

v-length+=1;

return1;

}

为什么需要判断插入的位置是否合法呢？这是因为顺序表是连续一片存储空间，所以内存是连续的。

下图以length=5，size=9为例，我们只能在下标为0到4之间的数中插入数据。

插入一个元素示意图

3.删除操作

interase(Vec*v,intind){//把下标为ind的元素删除

if(v==NULL)return0;

if(ind0||ind=v-length)return0;

for(inti=ind+1;iv-length;i++){

v-data[i-1]=v-data[i];

v-length-=1;

return1;

}

判断需要删除元素的下标是否合法，与插入元素类似删除一个元素示意图

4.扩容操作

intexpand(Vec*v){

//顺序表的扩容

//malloc动态申请空间，空间不一定干净calloc动态申请空间，并且清空realloc重新申请空间

intextr_size=v-size;

int*p;

while(extr_size){

p=(int*)realloc(v-data,sizeof(int)*(v-size+extr_size));

if(p!=NULL)break;//p不为空，说明扩容成功，这个时候直接跳出循环

extr_size=1;//否则就把额外扩容的空间除以2，降低要求

if(p==NULL)return0;//判断跳出循环究竟是扩容成功还是扩容失败，如果扩容失败，那就是p为空地址，找不到符合条件的内存区域

v-size+=extr_size;

v-data=p;

return1;

}

注意扩容这里写的比较巧妙，首先intextr_size=v-size;表示先将需要扩容的大小设置成原本的大小，然后就判断能不能找到那么大的空间。p=(int*)realloc(v-data,sizeof(int)*(v-size+extr_size));如果在系统中能找到这么大的容量，那么就返回找到的内存地址的首地址，然后就可以结束跳出循环；要是找不到的话那只能降低要求，把extr_size除以2，看看能不能知道，如果实在找不到，extr_size为0，就会跳出循环。然后可以通过判断p是不是空指针来判断程序是找到能够扩容的空间退出的还是找不到退出的。

要是对malloc、calloc和realloc不熟悉的，可以看我这篇博文：C语言深入探索动态内存分配的使用

5.释放操作

voidclear(Vec*v){//释放空间

if(v==NULL)return;

free(v-data);

free(v);

return;

}

先释放数据，再释放整个顺序表。

6.输出

voidoutput(Vec*v){

if(v==NULL)return;

printf("[");

for(inti=0;iv-length;i++){

iprintf(",");

printf("%d",v-data[i]);

printf("]\n");

return;

}

三、示例

#includestdio.h

#includestdlib.h

#includetime.h

//#includewindows.h

#defineCOLOR(a,b)"\033["#b"m"a"\033[0m"

#defineGREEN(a)COLOR(a,32)

#defineRED(a)COLOR(a,31)

typedefstructVector{

int*data;//该顺序表这片连续空间的首地址

intsize,length;

}Vec;

Vec*init(intn){//该顺序表具有n个存储单元

Vec*v=(Vec*)malloc(sizeof(Vec));//在内存栈上开辟一个空间malloc在内存的堆区，在函数外面也能访问

v-data=(int*)malloc(sizeof(int)*n);

v-size=n;

v-length=0;

returnv;

intexpand(Vec*v){

//顺序表的扩容

//malloc动态申请空间，空间不一定干净calloc动态申请空间，并且清空realloc重新申请空间

intextr_size=v-size;

int*p;

while(extr_size){

p=(int*)realloc(v-data,sizeof(int)*(v-size+extr_size));

if(p!=NULL)break;//p不为空，说明扩容成功，这个时候直接跳出循环

extr_size=1;//否则就把额外扩容的空间除以2，降低要求

if(p==NULL)return0;//判断跳出循环究竟是扩容成功还是扩容失败，如果扩容失败，那就是p为空地址，找不到符合条件的内存区域

v-size+=extr_size;

v-data=p;

return1;

intinsert(Vec*v,intind,intval){//ind为插入元素的位置,val为插入元素的值

if(v==NULL)return0;

if(ind0||indv-length)return0;

if(v-length==v-size){

if(!expand(v)){

printf(RED("failtoexpand!\n"));

printf(GREEN("successtoexpand!thesize=%d\n"),v-size);

for(inti=v-length;iind;i--){

v-data[i]=v-data[i-1];

v-data[ind]=val;

v-length+=1;

return1;

interase(Vec*v,intind){//把下标为ind的元素删除

if(v==NULL)return0;

if(ind0||ind=v-length)return0;

for(inti=ind+1;iv-length;i++){

v-data[i-1]=v-data[i];

v-length-=1;

return1;

voidoutput(Vec*v){

if(v==NULL)return;

printf("[");

for(inti=0;iv-length;i++){

iprintf(",");

printf("%d",v-data[i]);

printf("]\n");

return;

voidclear(Vec*v){//释放空间

if(v==NULL)return;

free(v-data);

free(v);

return;

intmain(){

#defineMAX_N20

Vec*v=init(1);

srand(time(0));//设置种子

for(inti=0;iMAX_N;i++){

intop=rand()%4;

intind=rand()%(v-length+3)-1;//取值范围[-1,v-length+1]

intval=rand()%100;//val为1到99之间的数

switch(op){

case0:

case1:

case2:{

printf("insert%dat%dtotheVector=%d\n",val,ind,insert(v,ind,val));

}break;

case3:{

printf("eraseaitemat%d=%d\n",ind,erase(v,ind));

}break;

output(v);

printf("\n");

#undefMAX_N

clear(v);

return0;

}

输出结果如下：

insert82at0totheVector=1

[82]

insert38at2totheVector=0

[82]

successtoexpand!thesize=2

insert7at1totheVector=1

[82,7]

successtoexpand!thesize=4

insert86at2totheVector=1

[82,7,86]

eraseaitemat4=0

[82,7,86]

eraseaitemat4=0

[82,7,86]

insert48at0totheVector=1

[48,82,7,86]

insert65at5totheVector=0

[48,82,7,86]

successtoexpand!thesize=8

insert92at4totheVector=1

[48,82,7,86,92]

eraseaitemat2=1

[48,82,86,92]

insert81at2totheVector=1

[48,82,81,86,92]

insert9at0totheVector=1