C語言全面講解順序表使用操作

第C語言全面講解順序表使用操作目錄一、順序表的結(jié)構(gòu)定義二、順序表的結(jié)構(gòu)操作1.初始化2.插入操作3.刪除操作4.擴(kuò)容操作5.釋放操作6.輸出三、示例編程環(huán)境為ubuntu18.04。

順序表需要連續(xù)一片存儲空間，存儲任意類型的元素，這里以存儲int類型數(shù)據(jù)為例。

一、順序表的結(jié)構(gòu)定義

size為容量，length為當(dāng)前已知數(shù)據(jù)表元素的個數(shù)

typedefstructVector{

int*data;//該順序表這片連續(xù)空間的首地址

intsize,length;

}Vec;

二、順序表的結(jié)構(gòu)操作

1.初始化

Vec*init(intn){//該順序表具有n個存儲單元

Vec*v=(Vec*)malloc(sizeof(Vec));//在內(nèi)存棧上開辟一個空間malloc在內(nèi)存的堆區(qū)，在函數(shù)外面也能訪問

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)){//擴(kuò)容失敗

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;

}

為什么需要判斷插入的位置是否合法呢？這是因?yàn)轫樞虮硎沁B續(xù)一片存儲空間，所以內(nèi)存是連續(xù)的。

下圖以length=5，size=9為例，我們只能在下標(biāo)為0到4之間的數(shù)中插入數(shù)據(jù)。

插入一個元素示意圖

3.刪除操作

interase(Vec*v,intind){//把下標(biāo)為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;

}

判斷需要刪除元素的下標(biāo)是否合法，與插入元素類似刪除一個元素示意圖

4.擴(kuò)容操作

intexpand(Vec*v){

//順序表的擴(kuò)容

//malloc動態(tài)申請空間，空間不一定干凈calloc動態(tài)申請空間，并且清空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不為空，說明擴(kuò)容成功，這個時(shí)候直接跳出循環(huán)

extr_size=1;//否則就把額外擴(kuò)容的空間除以2，降低要求

if(p==NULL)return0;//判斷跳出循環(huán)究竟是擴(kuò)容成功還是擴(kuò)容失敗，如果擴(kuò)容失敗，那就是p為空地址，找不到符合條件的內(nèi)存區(qū)域

v-size+=extr_size;

v-data=p;

return1;

}

注意擴(kuò)容這里寫的比較巧妙，首先intextr_size=v-size;表示先將需要擴(kuò)容的大小設(shè)置成原本的大小，然后就判斷能不能找到那么大的空間。p=(int*)realloc(v-data,sizeof(int)*(v-size+extr_size));如果在系統(tǒng)中能找到這么大的容量，那么就返回找到的內(nèi)存地址的首地址，然后就可以結(jié)束跳出循環(huán)；要是找不到的話那只能降低要求，把extr_size除以2，看看能不能知道，如果實(shí)在找不到，extr_size為0，就會跳出循環(huán)。然后可以通過判斷p是不是空指針來判斷程序是找到能夠擴(kuò)容的空間退出的還是找不到退出的。

要是對malloc、calloc和realloc不熟悉的，可以看我這篇博文：C語言深入探索動態(tài)內(nèi)存分配的使用

5.釋放操作

voidclear(Vec*v){//釋放空間

if(v==NULL)return;

free(v-data);

free(v);

return;

}

先釋放數(shù)據(jù)，再釋放整個順序表。

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;//該順序表這片連續(xù)空間的首地址

intsize,length;

}Vec;

Vec*init(intn){//該順序表具有n個存儲單元

Vec*v=(Vec*)malloc(sizeof(Vec));//在內(nèi)存棧上開辟一個空間malloc在內(nèi)存的堆區(qū)，在函數(shù)外面也能訪問

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

v-size=n;

v-length=0;

returnv;

intexpand(Vec*v){

//順序表的擴(kuò)容

//malloc動態(tài)申請空間，空間不一定干凈calloc動態(tài)申請空間，并且清空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不為空，說明擴(kuò)容成功，這個時(shí)候直接跳出循環(huán)

extr_size=1;//否則就把額外擴(kuò)容的空間除以2，降低要求

if(p==NULL)return0;//判斷跳出循環(huán)究竟是擴(kuò)容成功還是擴(kuò)容失敗，如果擴(kuò)容失敗，那就是p為空地址，找不到符合條件的內(nèi)存區(qū)域

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){//把下標(biāo)為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));//設(shè)置種子

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之間的數(shù)

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;

}

輸出結(jié)果如下：

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