線性表的16種算法

1、#include<stdio.h>#include<stdlib.h>typedefintelemType;/*/*以下是關(guān)于線性表順序存儲操作的16種算法 */*/structList elemType*list; intsize; intmaxSize;voidagainMalloc(structList*L) /*空間擴展為原來的2倍，并由p指針?biāo)赶?，原?nèi)容被自動拷貝到p所指向的存儲空間*/ elemType*p=realloc(L->list,2*L->maxSize*sizeof(elemType); if(!p)/*分配失敗則退出運行*/ pr

2、intf("存儲空間分配失??！ "); exit(1); L->list=p;/*使list指向新線性表空間*/ L->maxSize=2*L->maxSize;/*把線性表空間大小修改為新的長度*/*1.初始化線性表L，即進行動態(tài)存儲空間分配并置L為一個空表*/voidinitList(structList*L,intms) /*檢查ms是否有效，若無效的則退出運行*/ if(ms<=0) printf("MaxSize非法！ "); exit(1);/*執(zhí)行此函數(shù)中止程序運行，此函數(shù)在stdlib.h中有定義*/ L->

3、maxSize=ms;/*設(shè)置線性表空間大小為ms*/ L->size=0; L->list=malloc(ms*sizeof(elemType); if(!L->list) printf("空間分配失??！ "); exit(1); return;/*2.清除線性表L中的所有元素，釋放存儲空間，使之成為一個空表*/voidclearList(structList*L) if(L->list!=NULL) free(L->list); L->list=0; L->size=L->maxSize=0; return;/*3.返回線

4、性表L當(dāng)前的長度，若L為空則返回*/intsizeList(structList*L) returnL->size;/*4.判斷線性表L是否為空，若為空則返回1,否則返回0*/intemptyList(structList*L) if(L->size=0) return1; else return0; /*5.返回線性表L中第pos個元素的值，若pos超出范圍，則停止程序運行*/elemTypegetElem(structList*L,intpos) if(pos<1|pos>L->size)/*若pos越界則退出運行*/ printf("元素序號越界！

5、 "); exit(1); returnL->listpos-1;/*返回線性表中序號為pos值的元素值*/*6.順序掃描（即遍歷）輸出線性表L中的每個元素*/voidtraverseList(structList*L) inti; for(i=0;i<L->size;i+) printf("%d",L->listi); printf(" "); return;/*7.從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1*/intfindList(structList*L,elemTypex) inti

6、; for(i=0;i<L->size;i+) if(L->listi=x) returni; return-1;/*8.把線性表L中第pos個元素的值修改為x的值，若修改成功返回1，否則返回0*/intupdatePosList(structList*L,intpos,elemTypex) if(pos<1|pos>L->size)/*若pos越界則修改失敗*/ return0; L->listpos-1=x; return1;/*9.向線性表L的表頭插入元素x*/voidinserFirstList(structList*L,elemTypex)

7、inti; if(L->size=L->maxSize) againMalloc(L); for(i=L->size-1;i>=0;i-) L->listi+1=L->listi; L->list0=x; L->size+; return;/*10.向線性表L的表尾插入元素x*/voidinsertLastList(structList*L,elemTypex) if(L->size=L->maxSize)/*重新分配更大的存儲空間*/ againMalloc(L); L->listL->size=x;/*把x插入到表尾*

8、/ L->size+;/*線性表的長度增加*/ return;/*11.向線性表L中第pos個元素位置插入元素x，若插入成功返回，否則返回*/intinsertPosList(structList*L,intpos,elemTypex) inti; if(pos<1|pos>L->size+1)/*若pos越界則插入失敗*/ return0; if(L->size=L->maxSize)/*重新分配更大的存儲空間*/ againMalloc(L); for(i=L->size-1;i>=pos-1;i-) L->listi+1=L->

9、listi; L->listpos-1=x; L->size+; return1;/*12.向有序線性表L中插入元素x,使得插入后仍然有序*/voidinsertOrderList(structList*L,elemTypex) inti,j; /*若數(shù)組空間用完則重新分配更大的存儲空間*/ if(L->size=L->maxSize) againMalloc(L); /*順序查找出x的插入位置*/ for(i=0;i<L->size;i+) if(x<L->listi) break; /*從表尾到下標(biāo)i元素依次后移一個位置，把i的位置空出來*/

10、 for(j=L->size-1;j>=i;j-) L->listj+1=L->listj; /*把x值賦給下標(biāo)為i的元素*/ L->listi=x; /*線性表長度增加1*/ L->size+; return;/*13.從線性表L中刪除表頭元素并返回它，若刪除失敗則停止程序運行*/elemTypedeleteFirstList(structList*L) elemTypetemp; inti; if(L->size=0) printf("線性表為空，不能進行刪除操作！ "); exit(1); temp=L->list0;

11、for(i=1;i<L->size;i+) L->listi-1=L->listi; L->size-; returntemp;/*14.從線性表L中刪除表尾元素并返回它，若刪除失敗則停止程序運行*/elemTypedeleteLastList(structList*L) if(L->size=0) printf("線性表為空，不能進行刪除操作！ "); exit(1); L->size-; returnL->listL->size;/*返回原來表尾元素的值*/*15.從線性表L中刪除第pos個元素并返回它，若刪除失敗則

12、停止程序運行*/elemTypedeletePosList(structList*L,intpos) elemTypetemp; inti; if(pos<1|pos>L->size)/*pos越界則刪除失敗*/ printf("pos值越界，不能進行刪除操作！ "); exit(1); temp=L->listpos-1; for(i=pos;i<L->size;i+) L->listi-1=L->listi; L->size-; returntemp;/*16.從線性表L中刪除值為x的第一個元素，若成功返回1，失敗返

13、回0*/intdeleteValueList(structList*L,elemTypex) inti,j; /*從線性表中順序查找出值為x的第一個元素*/ for(i=0;i<L->size;i+) if(L->listi=x) break; /*若查找失敗，表明不存在值為x的元素，返回0*/ if(i=L->size) return0; /*刪除值為x的元素L->listi*/ for(j=i+1;j<L->size;j+) L->listj-1=L->listj; L->size-; return1;/*/voidmain()

14、inta10=2,4,6,8,10,12,14,16,18,20; inti; structListL; initList(&L,5); for(i=0;i<10;i+) insertLastList(&L,ai); insertPosList(&L,11,48);insertPosList(&L,1,64); printf("%d ",getElem(&L,1); traverseList(&L); printf("%d ",findList(&L,10); updatePosList(&a

15、mp;L,3,20); printf("%d ",getElem(&L,3); traverseList(&L); deleteFirstList(&L);deleteFirstList(&L); deleteLastList(&L);deleteLastList(&L); deletePosList(&L,5);deletePosList(&L,7); printf("%d ",sizeList(&L); printf("%d ",emptyList(&

16、L); traverseList(&L); clearList(&L); return0;#include<stdio.h>#include<stdlib.h>#defineNN12#defineMM20typedefintelemType;/*/*以下是關(guān)于線性表鏈接存儲（單鏈表）操作的16種算法*/*/structsNode/*定義單鏈表結(jié)點類型*/ elemTypedata; structsNode*next;/*1.初始化線性表，即置單鏈表的表頭指針為空*/voidinitList(structsNode*hl) *hl=NULL; return

17、;/*2.清除線性表L中的所有元素，即釋放單鏈表L中所有的結(jié)點，使之成為一個空表*/voidclearList(structsNode*hl) /*cp和np分別作為指向兩個相鄰結(jié)點的指針*/ structsNode*cp,*np; cp=*hl; /*遍歷單鏈表，依次釋放每個結(jié)點*/ while(cp!=NULL) np=cp->next;/*保存下一個結(jié)點的指針*/ free(cp); cp=np; *hl=NULL;/*置單鏈表的表頭指針為空*/ return;/*3.返回單鏈表的長度*/intsizeList(structsNode*hl) intcount=0;/*用于統(tǒng)計結(jié)點

18、的個數(shù)*/ while(hl!=NULL) count+; hl=hl->next; returncount;/*4.檢查單鏈表是否為空，若為空則返回，否則返回*/intemptyList(structsNode*hl) if(hl=NULL) return1; else return0; /*5.返回單鏈表中第pos個結(jié)點中的元素，若pos超出范圍，則停止程序運行*/elemTypegetElem(structsNode*hl,intpos) inti=0;/*統(tǒng)計已遍歷的結(jié)點個數(shù)*/ if(pos<1) printf("pos值非法，退出運行！ "); ex

19、it(1); while(hl!=NULL) i+; if(i=pos) break; hl=hl->next; if(hl!=NULL) returnhl->data; else printf("pos值非法，退出運行！ "); exit(1); /*6.遍歷一個單鏈表*/voidtraverseList(structsNode*hl) while(hl!=NULL) printf("%5d",hl->data); hl=hl->next; printf(" "); return;/*7.從單鏈表中查找具有給

20、定值x的第一個元素，若查找成功則返回該結(jié)點data域的存儲地址，否則返回NULL*/elemType*findList(structsNode*hl,elemTypex) while(hl!=NULL) if(hl->data=x) return&hl->data; else hl=hl->next; returnNULL;/*8.把單鏈表中第pos個結(jié)點的值修改為x的值，若修改成功返回，否則返回*/intupdatePosList(structsNode*hl,intpos,elemTypex) inti=0; structsNode*p=hl; while(p!=

21、NULL)/*查找第pos個結(jié)點*/ i+; if(pos=i) break; else p=p->next; if(pos=i) p->data=x; return1; else return0; /*9.向單鏈表的表頭插入一個元素*/voidinsertFirstList(structsNode*hl,elemTypex) structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("內(nèi)存分配失敗，退出運行！ "); exit(1); newP->data=x;/*把x

22、的值賦給新結(jié)點的data域*/ /*把新結(jié)點作為新的表頭結(jié)點插入*/ newP->next=*hl; *hl=newP; return;/*10.向單鏈表的末尾添加一個元素*/voidinsertLastList(structsNode*hl,elemTypex) structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("內(nèi)在分配失敗，退出運行！ "); exit(1); /*把x的值賦給新結(jié)點的data域，把空值賦給新結(jié)點的next域*/ newP->data=x; new

23、P->next=NULL; /*若原表為空，則作為表頭結(jié)點插入*/ if(*hl=NULL) *hl=newP; /*查找到表尾結(jié)點并完成插入*/ else structsNode*p=NULL; while(p->next!=NULL) p=p->next; p->next=newP; return;/*11.向單鏈表中第pos個結(jié)點位置插入元素為x的結(jié)點，若插入成功返回，否則返回*/intinsetPosList(structsNode*hl,intpos,elemTypex) inti=0; structsNode*newP; structsNode*cp=*hl

24、,*ap=NULL; /*對pos值小于等于的情況進行處理*/ if(pos<=0) printf("pos值非法，返回表示插入失敗！ "); return0; /*查找第pos個結(jié)點*/ while(cp!=NULL) i+; if(pos=i) break; else ap=cp; cp=cp->next; /*產(chǎn)生新結(jié)點，若分配失敗，則停止插入*/ newP=malloc(sizeof(structsNode); if(newP=NULL) printf("內(nèi)存分配失敗，無法進行插入操作！ "); return0; /*把x的值賦給新結(jié)

25、點的data域*/ newP->data=x; /*把新結(jié)點插入到表頭*/ if(ap=NULL) newP->next=cp;/*或改為newP->next=*hl;*/ *hl=newP; /*把新結(jié)點插入到ap和cp之間*/ else newP->next=cp; ap->next=newP; return1;/*插入成功返回1*/*12.向有序單鏈表中插入元素x結(jié)點，使得插入后仍然有序*/voidinsertOrderList(structsNode*hl,elemTypex) /*把單鏈表的表頭指針賦給cp，把ap置空*/ structsNode*cp=

26、*hl,*ap=NULL; /*建立新結(jié)點*/ structsNode*newP; newP=malloc(sizeof(structsNode); if(newP=NULL) printf("內(nèi)在分配失敗，退出運行！ "); exit(1); newP->data=x;/*把x的值賦給新結(jié)點的data域*/ /*把新結(jié)點插入到表頭*/ if(cp=NULL)|(x<cp->data) newP->next=cp; *hl=newP; return; /*順序查找出x結(jié)點的插入位置*/ while(cp!=NULL) if(x<cp->d

27、ata) break; else ap=cp; cp=cp->next; /*把x結(jié)點插入到ap和cp之間*/ newP->next=cp; ap->next=newP; return;/*13.從單鏈表中刪除表頭結(jié)點，并把該結(jié)點的值返回，若刪除失敗則停止程序運行*/elemTypedeleteFirstList(structsNode*hl) elemTypetemp; structsNode*p=*hl;/*暫存表頭結(jié)點指針，以便回收*/ if(*hl=NULL) printf("單鏈表為空，無表頭可進行刪除，退出運行！ "); exit(1); *h

28、l=(*hl)->next;/*使表頭指針指向第二個結(jié)點*/ temp=p->data;/*暫存原表頭元素，以便返回*/ free(p);/*回收被刪除的表頭結(jié)點*/ returntemp;/*返回第一個結(jié)點的值*/*14.從單鏈表中刪除表尾結(jié)點并返回它的值，若刪除失敗則停止程序運行*/elemTypedeleteLastList(structsNode*hl) elemTypetemp; /*初始化cp和ap指針，使cp指向表頭結(jié)點，使ap為空*/ structsNode*cp=*hl; structsNode*ap=NULL; /*單鏈表為空則停止運行*/ if(cp=NULL

29、) printf("單鏈表為空，無表頭進行刪除，退出運行！ "); exit(1); /*從單鏈表中查找表尾結(jié)點，循環(huán)結(jié)束時cp指向表尾結(jié)點，ap指向其前驅(qū)結(jié)點*/ while(cp->next!=NULL) ap=cp; cp=cp->next; /*若單鏈表中只有一個結(jié)點，則需要修改表頭指針*/ if(ap=NULL) *hl=(*hl)->next;/*或改為*hl=NULL;*/ /*刪除表尾結(jié)點*/ else ap->next=NULL; /*暫存表尾元素，以便返回*/ temp=cp->data; free(cp);/*回收被刪除的

30、表尾結(jié)點*/ returntemp;/*返回表尾結(jié)點的值*/*15.從單鏈表中刪除第pos個結(jié)點并返回它的值，若刪除失敗則停止程序運行*/elemTypedeletePosList(structsNode*hl,intpos) inti=0; elemTypetemp; /*初始化cp和ap指針，使cp指向表頭結(jié)點，使ap為空*/ structsNode*cp=*hl; structsNode*ap=NULL; /*單鏈表為空或pos值非法則停止運行 （編程入門）*/ if(cp=NULL)|(pos<=0) printf("單鏈表為空或pos值不正確，退出運行！ "

31、); exit(1); /*從單鏈表中查找第pos個結(jié)點，找到后由cp指向該結(jié)點，由ap指向其前驅(qū)結(jié)點*/ while(cp!=NULL) i+; if(i=pos) break; ap=cp; cp=cp->next; /*單鏈表中沒有第pos個結(jié)點*/ if(cp=NULL) printf("pos值不正確，退出運行！ "); exit(1); /*若pos等于1，則需要刪除表頭結(jié)點*/ if(pos=1) *hl=(*hl)->next;/*或改為*hl=cp->next;*/ /*否則刪除非表頭結(jié)點，此時cp指向該結(jié)點，ap指向前驅(qū)結(jié)點*/ else ap->next=cp->next; /*暫存第pos個結(jié)點的值，以便返回*/ temp=cp->data; free(cp);/*回收被刪除的第pos個結(jié)點*/ returntemp;/*返回在temp中暫存的第pos個結(jié)點的值*/*16.從單鏈表中刪除值為x的第一個結(jié)點，若刪除成功則返回1,否則返回0*/intdeleteValueList(structsNode*hl,elemTypex) /*初始化cp和ap指針，使cp指向表頭結(jié)點，使ap為空*/ structsN