順序表的建立與操作算法C語(yǔ)言實(shí)現(xiàn)

1、順序表的建立與常用操作的算法(C語(yǔ)言實(shí)現(xiàn))#defineLIST_INIT_SIZE10/*線(xiàn)性表存儲(chǔ)空間的初始分配量*/*c2-1.h線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)*/#defineLISTINCREMENT2/*線(xiàn)性表存儲(chǔ)空間的分配增量*/typedefstructElemType*elem;/*存儲(chǔ)空間基址*/intlength;/*當(dāng)前長(zhǎng)度*/intlistsize;/*當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)*/SqList;StatusInitList(SqList*L)/*操作結(jié)果：構(gòu)造一個(gè)空的順序線(xiàn)性表*/(*L).elem=(ElemType*)mallo

2、c(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/(*L).length=0;/*空表長(zhǎng)度為0*/(*L).listsize=LIST_INIT_SIZE;/*初始存儲(chǔ)容量*/returnOK;StatusDestroyList(SqList*L)/*初始條件：順序線(xiàn)性表L已存在。操作結(jié)果：銷(xiāo)毀順序線(xiàn)性表L*/free(*L).elem);(*L).elem=NULL;(*L).length=0;(*L).listsize=0;/*bo2-1.c順序表(存儲(chǔ)結(jié)構(gòu)由c2-1.h定義)的基本操作(12個(gè)

3、)returnOK;StatusClearList(SqList*L)/*初始條件：順序線(xiàn)性表L已存在。操作結(jié)果：將L重置為空表*/(*L).length=0;returnOK;*/StatusListEmpty(SqListL)/*初始條件：順序線(xiàn)性表L已存在。操作結(jié)果：若L為空表，則返回TRUE否則返回FALSE*/if(L.length=0)returnTRUE;elsereturnFALSE;intListLength(SqListL)/*初始條件：順序線(xiàn)性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)*/returnL.length;StatusGetElem(SqListL,inti,

4、ElemType*e)/*初始條件：順序線(xiàn)性表L已存在，1wiwListLength(L)*/*操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值*/if(i<1|i>L.length)exit(ERROR);*e=*(L.elem+i-1);returnOK;intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/*初始條件：順序線(xiàn)性表L已存在，compare。是數(shù)據(jù)元素判定函數(shù)(滿(mǎn)足為1,否則為0)*/*操作結(jié)果：返回L中第1個(gè)與e滿(mǎn)足關(guān)系compare()的數(shù)據(jù)元素的位序。*/*若這樣的數(shù)據(jù)元素不存在，則返

5、回值為0。算法2.6*/ElemType*p;inti=1;/*i的初值為第1個(gè)元素的位序*/p=L.elem;/*p的初值為第1個(gè)元素的存儲(chǔ)位置*/while(i<=L.length&&!compare(*p+,e)+i;if(i<=L.length)returni;elsereturn0;StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)/*初始條件：順序線(xiàn)性表L已存在*/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/*否則操作失敗，pre_e無(wú)定義*/inti=2;

6、ElemType*p=L.elem+1;while(i<=L.length&&*p!=cur_e)p+;i+;if(i>L.length)returnINFEASIBLE;else*pre_e=*-p;returnOK;StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e)/*初始條件：順序線(xiàn)性表L已存在*/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，*/*否則操作失敗，next_e無(wú)定義*/inti=1;ElemType*p=L.elem;while(i<L.len

7、gth&&*p!=cur_e)i+;p+;Jif(i=L.length)returnINFEASIBLE;else*next_e=*+p;returnOK;StatusListInsert(SqList*L,inti,ElemTypee)/*初始條件：順序線(xiàn)性表L已存在，1WiWListLength(L)+1*/*操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1*/ElemType*newbase,*q,*p;if(i<1|i>(*L).length+1)/*i值不合法*/returnERROR;if(*L).length>=(*L).lists

8、ize)/*當(dāng)前存儲(chǔ)空間已滿(mǎn)，增加分配*/newbase=(ElemType*)realloc(*L).elem,(*L).listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/*存儲(chǔ)分配失敗*/(*L).elem=newbase;/*新基址*/(*L).listsize+=LISTINCREMENT;/*增加存儲(chǔ)容量*/q=(*L).elem+i-1;/*q為插入位置*/for(p=(*L).elem+(*L).length-1;p>=q;-p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=

9、e;/*插入e*/+(*L).length;/*表長(zhǎng)增1*/returnOK;StatusListDelete(SqList*L,inti,ElemType*e)/*初始條件：順序線(xiàn)性表L已存在，1wiwListLength(L)*/*操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長(zhǎng)度減1*/ElemType*p,*q;if(i<1|i>(*L).length)/*i值不合法*/returnERROR;p=(*L).elem+i-1;/*p為被刪除元素的位置*/*e=*p;/*被刪除元素的值賦給e*/q=(*L).elem+(*L).length-1;/*表尾元素的位置*/

10、for(+p;p<=q;+p)/*被刪除元素之后的元素左移*/*(p-1)=*p;(*L).length-;/*表長(zhǎng)減1*/returnOK;StatusListTraverse(SqListL,void(*vi)(ElemType*)/*初始條件：順序線(xiàn)性表L已存在*/*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗，則操作失敗*/*vi()的形參加'&',表明可通過(guò)調(diào)用vi()改變?cè)氐闹?/ElemType*p;inti;p=L.elem;for(i=1;i<=L.length;i+)vi(p+);printf("n&qu

11、ot;);returnOK;/*main2-1.c檢驗(yàn)bo2-1.c的主程序*/#include"c1.h"typedefintElemType;#include"c2-1.h”#include"bo2-1.c”Statuscomp(ElemTypec1,ElemTypec2)/*數(shù)據(jù)兀素/Ute函數(shù)(平方關(guān)系)*/if(c1=c2*c2)returnTRUE;elsereturnFALSE;voidvisit(ElemType*c)/*ListTraverse()調(diào)用的函數(shù)(類(lèi)型要,致)*/printf("%d",*c);voidd

12、bl(ElemType*c)/*ListTraverse()調(diào)用的另函數(shù)(兀素值加倍)*/*c*=2;voidmain()SqListL;ElemTypee,e0;Statusi;intj,k;i=InitList(&L);printf("初始化L后：L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);for(j=1;j<=5;j+)i=ListInsert(&L,1,j);printf("在L的表頭依次插入15后：*L.elem=");for(j=1;j&

13、lt;=5;j+)printf("%d",*(L.elem+j-1);printf("n");printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);i=ListEmpty(L);printf("L是否空：i=%d(1:是0:否)n",i);i=ClearList(&L);printf("清空L后：L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,

14、L.listsize);i=ListEmpty(L);printf("L是否空：i=%d(1:是0:否)n",i);for(j=1;j<=10;j+)ListInsert(&L,j,j);printf("在L的表尾依次插入110后：*L.elem=");for(j=1;j<=10;j+)printf("%d",*(L.elem+j-1);printf("n");printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.lengt

15、h,L.listsize);ListInsert(&L,1,0);printf("在L的表頭插入0后：*L.elem=");for(j=1;j<=ListLength(L);j+)/*ListLength(L)為元素個(gè)數(shù)*/printf("%d",*(L.elem+j-1);printf("n");printf("L.elem=%u(有可能改變)L.length=%d(改變)L.listsize=%d(改變)n",L.elem,L.length,L.listsize);GetElem(L,5,&

16、;e);printf("第5個(gè)元素的值為：%dn",e);for(j=3;j<=4;j+)k=LocateElem(L,j,comp);if(k)printf("第個(gè)元素的值為%d的平方n",k,j);elseprintf("沒(méi)有值為%d的平方的元素n",j);for(j=1;j<=2;j+)/*測(cè)試頭兩個(gè)數(shù)據(jù)*/GetElem(L,j,&e0);/*把第j個(gè)數(shù)據(jù)賦給e0*/i=PriorElem(L,e0,&e);/*求e0的前驅(qū)*/if(i=INFEASIBLE)printf("元素d無(wú)前驅(qū)n

17、",e0);elseprintf("元素d的前驅(qū)為：%dn",e0,e);for(j=ListLength(L)-1;j<=ListLength(L);j+)/*最后兩個(gè)數(shù)據(jù)*/GetElem(L,j,&e0);/*把第j個(gè)數(shù)據(jù)賦給e0*/i=NextElem(L,e0,&e);/*求e0的后繼*/if(i=INFEASIBLE)printf("元素d無(wú)后繼n",e0);elseprintf("元素d的后繼為：%dn",e0,e);k=ListLength(L);/*k為表長(zhǎng)*/for(j=k+1;j>=k;j-)i=ListDelete(&L,j,&e);/*刪除第j個(gè)數(shù)據(jù)*/if(i=ERROR)printf("刪除第外數(shù)據(jù)失敗n",j);elseprintf("刪除的元素值為：dn",e);)printf("