C語言經典(C語言必看文檔)數據結構C語言實現系列［1］一一線性表#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是關于線性表順序存儲操作的16種算法*//*****************************************************************"structList{elemType*list;intsize;intmaxSize;）；voidagainMalloc(structList*L)(/*空間擴展為原來的2倍，并由p指針所指向，原內容被自動拷貝到p所指向的存儲空間*/elemType*p=realloc(L->listr2*L->maxSize*sizeof(elemType));if(!p){ /*分配失敗則退出運行*/printf("存儲空間分配失敗！")；exit(1);1L->list=p;/*使list指向新線性表空間*/L->maxSize=2*L->maxSize;/*把線性表空間大小修改為新的長度*/)/*1.初始化線性表L,即進行動態存儲空間分配并置L為一個空表*/voidinitList(structList*LZintms)(/*檢查ms是否有效，若無效的則退出運行*/if(ms<=0){printf("MaxSize非法！H;exit(l);/*執行此函數中止程序運行，此函數在stdlib.h中有定義*/)L->maxSize=ms;/★設置線性表空間大小為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.返回線性表L當前的長度，若L為空則返回0*/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<1pos>L->size){ /★若pos越界則退出運行*/printf("元素序號越界！");exit(1);}returnL->list[pos-1]; /*返回線性表中序號為pos值的元素值*/}/*6.順序掃描(即遍歷)輸出線性表L中的每個元素*/voidtraverseList(structList*L)

inti;for(i=0;i<L->size;i++){printf(*'%d”,L->list[i]);}printf(MM);return;}/*7.從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1*/intfindList(structList★L,elemTypex)(inti;for(i=0;i<L->size;i++){if(L->list[i]==x){returni;)}return-1;)/*8.把線性表L中第pos個元素的值修改為x的值，若修改成功返回1,否則返回0*/intupdatePosList(structList*LZintpos,elemTypex)(if(pos<1pos>L->size){ /*若pos越界則修改失敗*/return0;}L->list[pos-1]=x;return1;}/*9.向線性表L的表頭插入元素x*/voidinserFirstList(structList*L,elemTypex)(inti;if(L->size==L->maxSize){againMalloc(L);}for(i=L->size-1;i>=0;i--){L->list[i+1]=L->list[i];}L->list[0]=x;L->size++;return;

/*10.向線性表L的表尾插入元素x*/voidinsertLastList(structList*L,elemTypex)(if(L->size==L->maxSize){ /*重新分配更大的存儲空間*/againMalloc(L);}L->list[L->size]=x;/*把x插入到表尾*/L->size++;/*線性表的長度增加1*/return;)/★11.向線性表L中第pos個元素位置插入元素x,若插入成功返回1,否則返回0*/intinsertPosList(structList*LZintpos,elemTypex)(inti;if(pos<1pos>L->size+1){ /*若pos越界則插入失敗*/return0;)if(L->size==L->maxSize){ /*重新分配更大的存儲空間*/againMalloc(L);)for(i=L->size-1;i>=pos-1;i——){L->list[i+1]=L->list[i];}L->list[pos-1]=x;L->size++;return1;)/*12.向有序線性表L中插入元素x,使得插入后仍然有序*/voidinsertOrderList(structList*LZelemTypex)(intizj;/*若數組空間用完則重新分配更大的存儲空間*/if(L->size==L->maxSize){againMalloc(L);}/*順序查找出X的插入位置*/for(i=0;i<L->size;i++){if(x<L->list[i]){break;)}/*從表尾到下標i元素依次后移一個位置，把i的位置空出來*/for(j=L->size-1;j>=i;j——)

L->list[j+1]=L->list[j]；/*把x值賦給下標為i的元素*/L->list[i]=x;/*線性表長度增加1*/L->size++;return;}/*13.從線性表L中刪除表頭元素并返回它，若刪除失敗則停止程序運行*/elemTypedeleteFirstList(structList*L)(elemTypetemp;inti;if(L->size==0){printf("線性表為空，不能進行刪除操作！");exit(1);}temp=L->list[0];for(i=1;i<L->size;i++)L->list[i-l]=L->list[i];L->size--;returntemp;)/*14.從線性表L中刪除表尾元素并返回它，若刪除失敗則停止程序運行*/elemTypedeleteLastList(structList*L)(if(L->size==0){printf(”線性表為空，不能進行刪除操作！exit(1);}L->size--;returnL->list[L->size]; /*返回原來表尾元素的值*/}/*15.從線性表L中刪除第pos個元素并返回它，若刪除失敗則停止程序運行*/elemTypedeletePosList(structList*LZintpos)(elemTypetemp;inti;if(pos<1pos>L->size){ /*pos越界則刪除失敗*/printf("pos值越界，不能進行刪除操作！n);exit(1);}temp=L->list[pos-1];

for(i=pos;i<L->size;i++)L->list[i-1]=L->list[i];L->size——;returntemp;}/*16.從線性表L中刪除值為x的第一個元素，若成功返回1,失敗返回0*/intdeleteValueList(structList*LZelemTypex)(int1,j;/★從線性表中順序查找出值為x的第一個元素*/for(i=0;i<L->size;i++){if(L->list[i]==x){break;))/*若查找失敗，表明不存在值為x的元素，返回0*/if(i==L->size){return0;}/*刪除值為x的元素[i]*/for(j=i+1;j<L->size;j++){L->list[j-1]=L->list[j];}L->size—;return1;}voidmain()(inta[10]=[2,4,6,8,10,12,14,16,18,20);inti;structListL;initList(&L,5);for(i=0;i<10;i++){insertLastList(&Lra[i]);}insertPosList(&LZ11r48); insertPosList(&LZ1,64);printf(n%d”，getElem(&L,1));traverseList(&L);printf(n%d”,findList(&LZ10));updatePosList(&LZ3,20);printf(n%d”,getElem(&Lf3));traverseList(&L);deleteFirstList(&L); deleteFirstList(&L);

deleteLastList(&L);;deleteLastList(&L);;deletePosList(&LZ7);deletePosList(&LZ5);printf(H%d”,sizeList(&L));printf(H%d",emptyList(&L));traverseList(&L);clearList(&L);return0;#include<stdio.h>#include<stdlib.h>#defineNN12#defineMM20typedefintelemType;/★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Hr*************************************//* 以下是關于線性表鏈接存儲(單鏈表)操作的16種算法 */structsNode{ /*定義單鏈表結點類型*/elemTypedata;structsNode*next;}；/★1.初始化線性表，即置單鏈表的表頭指針為空*/voidinitList(structsNode**hl)(*hl=NULL;return;}/*2.清除線性表L中的所有元素，即釋放單鏈表L中所有的結點，使之成為一個空表*/voidclearList(structsNode**hl)(/*cp和np分別作為指向兩個相鄰結點的指針*/structsNode*cpz*np;cp=*hl;/*遍歷單鏈表，依次釋放每個結點*/while(cp!=NULL){np=cp->next;/*保存下?個結點的指針*/free(cp);cp=np;}*hl=NULL; /*置單鏈表的表頭指針為空*/return;/*3.返回單鏈表的長度*/intsizeList(structsNode*hl)(intcount=0; /*用于統計結點的個數*/while(hl!=NULL){count++;hl=hl->next;}returncount;)/*4.檢查單鏈表是否為空，若為空則返回1,否則返回0*/intemptyList(structsNode*hl)(if(hl==NULL){return1;}else{return0;))/*5.返回單鏈表中第pos個結點中的元素，若pos超出范圍，則停止程序運行*/elemTypegetElem(structsNode*hlfintpos)(inti=0; /*統計已遍歷的結點個數*/if(pos<1){printf("pos值非法，退出運行！”)；exit(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(n%5dH,hl->data);hl=hl->next;)printf(Hn);return;)/*7.從單鏈表中查找具有給定值x的第一個元素，若查找成功則返回該結點data域的存儲地址，否則返回NULL*/elemType*findList(structsNode*hl,elemTypex)(while(hl!=NULL){if(hl->data==x){return&hl->data;}else{hl=hl->next;))returnNULL;)/*8.把單鏈表中第pos個結點的值修改為x的值，若修改成功返回1,否則返回0*/intupdatePosList(structsNode★hl,intpos,elemTypex)(inti=0;structsNode*p=hl;while(p!=NULL){ /*查找第pos個結點*/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)；exit(1);}newP->data=x; /*把x的值賦給新結點的data域*//*把新結點作為新的表頭結點插入*/newP->next=*hl;*hl=newP;return;}/★10.向單鏈表的末尾添加一個元素*/voidinsertLastList(structsNode**hlrelemTypex)(structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf(”內在分配失敗，退出運行！");exit(1);}/*把X的值賦給新結點的data域，把空值賦給新結點的next域*/newP->data=x;newP->next=NULL;/★若原表為空，則作為表頭結點插入*/if(*hl==NULL){*hl=newP;}/*查找到表尾結點并完成插入*/else(structsNode*p=NULL;while(p->next!=NULL){p=p->next;)p->next=newP;}return;

/*11.向單鏈表中第pos個結點位置插入元素為X的結點，若插入成功返回1,否則返回0*/intinsetPosList(structsNode**hl,intpos,elemTypex){inti=0;structsNode*newP;structsNode*cp=*hl,*ap=NULL;/*對pos值小于等于0的情況進行處理*/if(pos<=0){printf("pos值非法，返回0表示插入失敗！”)；return0;}/*查找第pos個結點*/while(cp!=NULL){i++；if(pos==i){break;}else{ap=cp;cp=cp->next;))/*產生新結點，若分配失敗，則停止插入*/newP=malloc(sizeof(structsNode));if(newP==NULL){printf(”內存分配失敗，無法進行插入操作！”)；return0;)/*把x的值賦給新結點的data域*/newP->data=x;/*把新結點插入到表頭★/if(ap==NULL){newP->next=cp; /*或改為newP->next=*hl;*/*hl=newP;}/*把新結點插入到ap和cp之間*/else(newP->next=cp;ap->next=newP;}return1; /*插入成功返回1*/}/*12.向有序單鏈表中插入元素x結點，使得插入后仍然有序*/voidinsertOrderList(structsNode**hlzelemTypex)

/*把單鏈表的表頭指針賦給CP，把ap置空*/structsNode*cp=*hl,*ap=NULL;/*建立新結點*/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("內在分配失敗，退出運行！")；exit(1);}newP->data=x; /*把x的值賦給新結點的data域*//*把新結點插入到表頭*/if((cp==NULL)(x<cp->data)){/*這個地方要注意呀*/newP->next=cp;*hl=newP;return;}/*順序查找出x結點的插入位置*/while(cp!=NULL){if(x<cp->data){break;}else(ap=cp;cp=cp->next;}}/*把x結點插入到ap和cp之間*/newP->next=cp;ap->next=newP;return;)/*13.從單鏈表中刪除表頭結點，并把該結點的值返回，若刪除失敗則停止程序運行*/elemTypedeleteFirstList(structsNode**hl)(elemTypetemp;structsNode*p=*hl; /*暫存表頭結點指針，以便回收*/if(*hl==NULL){printf("單鏈表為空，無表頭可進行刪除，退出運行！”)；exit(1);}*hl=(*hl)->next; /*使表頭指針指向第二個結點*/temp=p->data; /*暫存原表頭元素，以便返回★/

free(p);returntemp;/*free(p);returntemp;/*返回第?個結點的值*//*14.從單鏈表中刪除表尾結點并返回它的值，若刪除失敗則停止程序運行*/elemTypedeleteLastList(structsNode**hl)(elemTypetemp;/*初始化cp和ap指針，使cp指向表頭結點，使ap為空*/structsNode*cp=*hl;structsNode*ap=NULL;/★單鏈表為空則停止運行*/if(cp==NULL){printf(”單鏈表為空，無表頭進行刪除，退出運行！?,);exit(1);}/*從單鏈表中查找表尾結點，循環結束時cp指向表尾結點，ap指向其前驅結點*/while(cp->next!=NULL){ap=cp;cp=cp->next;)/*若單鏈表中只有一個結點，則需要修改表頭指針*/if(ap==NULL){*hl=(*hl)->next; /*或改為=NULL;*/}/*刪除表尾結點*/else(ap->next=NULL;}/*暫存表尾元素，以便返回*/temp=cp->data;free(cp); /★回收被刪除的表尾結點★/returntemp; /★返回表尾結點的值★/}/*15.從單鏈表中刪除第pos個結點并返回它的值，若刪除失敗則停止程序運行*/elemTypedeletePosList(structsNode**hlzintpos)(inti=0;elemTypetemp;/★初始化cp和ap指針，使cp指向表頭結點，使ap為空*/structsNode*cp=*hl;structsNode*ap=NULL;/*單鏈表為空或pos值非法則停止運行*/

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

ap=cp;cp=cp->next;}/*若查找失敗，即該單鏈表中不存在值為x的結點，則返回0*/if(cp==NULL){return0;)/*假如刪除的是表頭或非表頭結點則分別進行處理*/if(ap==NULL){*hl=(*hl)->next; /*或改為*hl=cp->next*/}else{ap->next=cp->next;}free(cp); /*回收被刪除的結點*/return1; /*返回1表示刪除成功*/intmain(intargc,char*argv[])(inta[NN];inti;structsNode*p,*h,*s;srand(time(NULL));initList(&p);for(i=0;i<NN;i++){a[i]=rand()&MM;)printf("隨機數序列：”)；for(i=0;i<NN;i++){printf(H%5dnza[i]);}printf(Mn);printf(“隨機數逆序：“);for(i=0;i<NN;i++){insertFirstList(&pza[i]);}traverseList(p);printf("單鏈表長度：%5d”，sizeList(p));for(h=p;h!NULL;h=h->next){while(deleteValueList(&(h->next),h->data)){

}printf("去除重復數：“);traverseList(p);printf("單鏈表長度：%5d",sizeList(p));h=NULL;for(s=p;s!=NULL;s=s->next){insertOrderList(&h,s->data);)printf("有序表序列：，')；traverseList(h);clearList(&p);system(npausen);return0;數據結構C語言實現系列［2］一棧#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是關于棧順序存儲操作的6種算法 */structstack{elemType*stack; /*存儲棧元素的數組指針*/inttop; /*存儲棧頂元素的下標位置★/intmaxSize; /*存儲stack數組的長度*/}；voidagainMalloc(structstack*s)(/*空間擴展為原來的2倍，原內容被自動拷貝到p所指向的存儲空間中★/elemType*p;p=realloc(s->stackr2*s->maxSize*sizeof(elemType));if(!p){printf(”內在分配失敗！”);exit(1);}/*把棧空間的大小修改新的長度*/s->stack=p; /*使stack/*把棧空間的大小修改新的長度*/s->maxSize=2*s->maxSize;return;

/*1.初始化棧S為空*/voidinitStack(structstack★s,intms)(if(ms<=0){printf(nms的值非法！H);exit(1);)s->maxSize=ms;s->stack=malloc(ms*(sizeof(elemType)));if(!s->stack){printf(”內在分配失敗！");exit(1);)s->top=-1; /*初始置棧為空*/return;)/*2.新元素進棧，即把它插入到棧頂*/voidpush(structstack*s,elemTypex)(/*若棧空間用盡則重新分配更大的存儲空間*/if(s->top==s->maxSize-1){againMalloc(s);)s->top++; /★棧頂指針后移一個位置*/s->stack[s->top]=x; /*將新元索插入到棧頂*/return;)/*3.刪除(彈出)棧頂元素并返回其值*/elemTypepop(structstack*s)(/*若棧空則退出運行*/if(s->top==-1){printf("棧空，無元素出棧！”)；exit(1);)s->top—； /*棧頂指針減1表示出棧*/returns->stack[s->top+l]; /*返回原棧頂元素的值*//*4.讀取棧頂元素的值*/

elemTypepeek(structstack*s)/*若棧空則退出運行*/if(s->top==-1){printf("棧空，無元素可讀取！”)；exit(1);)returns->stack[s->top]; /★返回原棧頂元素的值*/}/*5.判斷s是否為空，若是則返回1表示其，否則返回0表示假*/intemptyStack(structstack*s)(if(s->top==-1){return1;}else(return0;/*6.清除棧s中的所有元素，釋放動態存儲空間*/voidclearStack(structstack*s)(if(s->stack){free(s->stack);s->stack=NULL;s->top=-1;s->maxSize=0;}return;intmain()(structstacks;inta[8]={3,8,5,17,9,30,15,22);inti;initStack(&s,5);for(i=0;i<8;i++){push(&s,a[i]);)printf(H%d”,pop(&s));printf(n%d”，pop(&s));

push(&s,68);printf(M%d”，peek(&s));printf(M%d”，pop(&s));while(!emptyStack(&s)){printf(M%d”，pop(&s));)printf("n);clearStack(&s);system('*pausen);return0;/* 以下是關于棧鏈接存儲操作的6種算法structsNode{elemTypedata;structsNode*next;)；/*1,初始化鏈棧為空*/voidinitStack(structsNode**hs)(*hs=NULL;return;)/*2.向鏈中插入一個元素(入棧)*/voidpush(structsNode**hszelemTypex)(structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("內在空間分配失敗！”)；exit(1);)newP->data=x; /*給新分配的結點賦值*//*向棧頂插入新結點*/newP->next=*hs;*hs=newP;return;}/*3.從鏈棧中刪除一個元素并返回它(出棧)elemTypepop(structsNode**hs)

structsNode*p;elemTypetemp;if(*hs==NULL){printf("棧空無法刪除！");exit(1);)/*暫存棧頂結點指針，并使棧頂指針指向下一個結點*/p=*hs;*hs=p->next;/*暫存原棧頂元素以便返回，同時回收原棧頂結點*/temp=p->data;free(p);returntemp; /*返【可原棧頂元素*/}/*4.讀取棧頂元素*/elemTypepeek(structsNode**hs)(/*對于空棧則退出運行★/if(*hs==NULL){printf("棧空，無棧頂元素！");exit(1);)return(*hs)->data; /*返回棧頂結點的值*/}/*5.判斷鏈棧是否為空，為空返回1,否則返回0*/intemptyStack(structsNode**hs)(if(*hs==NULL){return1;}else{return0;))/*6.清除鏈棧為空*/voidclearStack(structsNode**hs)(structsNode*cp,*np;cp=*hs; /*使cp指向棧頂結點*//*從棧底依次刪除每個結點*/while(cp!=NULL){

np=cp->next;free(cp);cp=np;}*hs=NULL; /*置鏈棧為空*/return;數據結構C語言實現系列[3]—關于棧的一些習題#include<stdio.h>#include<stdlib.h>typedefintelemType;#includenLinkAccess.cH/*對由fname所指字符串為文件名的程序文件進行括號配對檢查*/intbracketsCheck(char*fname)(structsNode*a; /*申明一個鏈棧*/charch;FILE*fp;fp=fopen(fname,"rn);if(!fp){printf("File,%s*nofound!",fname);exit(1);}initStack(&a);ch=fgetc(fp); /★從文件中讀取第一個字符到ch★/while(ch!=EOF){printf(M%cnrch);switch(ch){case'{':case1[1:case'push(&a,ch);break;case*},:if(peek(&a)==1{*){pop(&a);}else{return0;break;case*]*:

if(peek(&a)==1[*){pop(&a);}else{return0;)break;case*)1:if(peek(&a)==1(*){pop(&a);}else{return0;}break;)ch=fgetc(fp);}if(emptyStack(&a)){return1;}else{return0;intmain()(if(bracketsCheck(nABCD.cn)){printf("Match!n);}else{printf(nMissmatch!");)system(Mpause°);return0;)#include<stdio.h>#include<stdlib.h>typedefdoubleelemType;#includenLinkA/*計算由str所指向字符串的后綴表達式(逆波蘭式)的值*/doublecompute(char*str)(structsNode*s;/*用s棧存儲操作數和中間計算結果，元素類型為double*/doublex,y; /★x,y用于保存浮點數*/inti=0; /*i用于掃描后綴表達式*/

typedefdoubleelemType;initStack(&s);/*掃描后綴表達式中的每個字符，并進行相應處理★/while(str[i])(if(str[i]==*1){ /*掃描到空格字符不做任何處理*/i++；continue;)switch(str[i])(case'+':x=pop(&s)+pop(&s);i++；break;case'-：x=pop(&s)； /*彈出減數*/x=pop(&s)-X；i++;break;case'*'：x=pop(&s)*pop(&s);i++；break;case*/*:x=pop(&s); /★彈出除數*/if(x!=0.0)(x=pop(&s)/X；}else(printf(“除數為0!");exit(1);}i++；break;default:/*掃描到的是浮點數字符串，生成對應的浮點數*/x=0; /*x保存掃描到的整數部分的值*/while(str[i]>=48&&str[i]<=57)(x=x*10+str[i]-48;i++;

if(str[i]doublej=10.0;/*j作為相應小數位的權值*/i++；y=0;while(str[i]>=48&&str[i]<=57)(y=y+(str[i]-48)/j;i++;j*=10;1x+=y;/*把小數部分合并到整數部分x中*/))/*把掃描轉換后或進行相應運算后得到的浮點數壓入棧s中*/push(&s,x);}/*若計算結束后棧為空則中止運算*/if(emptyStack(&s))(printf("后綴表達式錯誤！");exit(1);)/*若棧中只有一個元素，則它就是該后綴表達式的值，否則出錯*/X=pop(&S);if(emptyStack(&s)){returnx;)else(printf("后綴表達式錯誤！M);exit(1);})/*返回運算符。p所對應的優先級數值*/intprecedence(charop)(switch(op){case1+1:casereturn1;case***:case1/1:return2;case'(':case101;default:return0;數據結構c語言實現系列［4］一隊列#include<stdio.h>#include<stdlib.h>typedefintelemType;/★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★if★/* 以下是關于隊列鏈接存儲操作的6種算法 */structsNode{/★值域*//*/★值域*//*鏈接指針*//*隊首指針*//*隊尾指針*/structsNode*next;}；structqueueLK{structsNode*front;structsNode*rear;)；/*1.初始化鏈隊*/voidinitQueue(structqueueLK*hq)(hq->front=hq->rear=NULL; /*把隊首和隊尾指針置空*/return;}/*2.向鏈隊中插入一個元素x*/voidenQueue(structqueueLK*hq,elemTypex)(/★得到一個由newP指針所指向的新結點*/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("內存空間分配失敗！");

exit(1);}/*把X的值賦給新結點的值域，把新結點的指針域置空*/newP->data=x;newP->next=NULL;/★若鏈隊為空，則新結點即是隊首結點又是隊尾結點*/if(hq->rear==NULL){hq->front=hq->rear=newP;}else{/*若鏈隊非空，則依次修改隊尾結點的指針域和隊尾指針，使之指向新的隊尾結點*/hq->rear=hq->rear->next=newP; /★注重賦值順序哦*/)return;)/*3.從隊列中刪除一個元素*/elemTypeoutQueue(structqueueLK*hq)(structsNode*p;elemTypetemp;/*若鏈隊為空則停止運行*/if(hq->front==NULL){printf(”隊歹ij為空，無法刪除！n);exit(1);}temp=hq->front->data; /*暫存隊尾元素以便返回*/p=hq->front; /*暫存隊尾指針以便回收隊尾結點★/hq->front=p->next; /*使隊首指針指向下一個結點*//★若刪除后鏈隊為空，則需同時使隊尾指針為空★/if(hq->front==NULL){hq->rear=NULL;}free(p); /*回收原隊首結點*/returntemp;/*返回被刪除的隊首元素值*/}/*4.讀取隊首元素*/elemTypepeekQueue(structqueueLK*hq)(/★若鏈隊為空則停止運行★/if(hq->front==NULL){printf("隊列為空，無法刪除！");exit(1);

returnhq->front->data;/*returnhq->front->data;/*返回隊首元素*//*5.檢查鏈隊是否為空，若為空則返回1,否則返回0*/intemptyQueue(structqueueLK*hq)(/*判定隊首或隊尾任一個指針是否為空即可*/if(hq->front==NULL){return1;}else{return0;))/*6.清除鏈隊中的所有元素*/voidclearQueue(structqueueLK*hq)(structsNode*p=hq->front; /*隊首指針賦給p*//★依次刪除隊列中的每一個結點，最后使隊首指針為空★/while(p!=NULL){hq->front=hq->front->next;free(p);p=hq->front;} /*循環結束后隊首指針已經為空*/hq->rear=NULL; /*置隊尾指針為空*/return;intmain(intargcrchar*argv[])(structqueueLKq;inta[8]={3,8,5,11,9,30,15,22);inti;initQueue(&q);for(i=0;i<8;i++){enQueue(&q,a[i]);)printf(n%d”,outQueue(&q));printf(M%d”,outQueue(&q));enQueue(&qz68);printf(n%d”，peekQueue(&q));printf(M%d”，outQueue(&q));while(!emptyQueue(&q)){printf(n%d”，outQueue(&q));

printf(nn);clearQueue(&q);system(Hpausen);#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是關于隊列鏈接存儲操作的typedefintelemType;/* 以下是關于隊列鏈接存儲操作的6種算法 *//*值域*//*鏈接指針*//*隊首指針*//*值域*//*鏈接指針*//*隊首指針*//*隊尾指針*/)；structqueueLK{structsNode*frent;structsNode*rear;)；/*1.初始化鏈隊*/voidinitQueue(structqueueLK*hq)(hq->front=hq->rear=NULL; /*把隊首和隊尾指針置空*/return;}/*2.向鏈隊中插入一個元素x*/voidenQueue(structqueueLK*hq,elemTypex)(/★得到一個由newP指針所指向的新結點★/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf(“內存空間分配失敗！”);exit(1);)/*把X的值賦給新結點的值域，把新結點的指針域置空*/newP->data=x;newP->next=NULL;/*若鏈隊為空，則新結點即是隊首結點又是隊尾結點★/if(hq->rear==NULL){hq->front=hq->rear=newP;}else{/*若鏈隊非空，則依次修改隊尾結點的指針域和隊尾指針，使之指向新的隊尾結點*/

hq->rear=hq->rear->next=newP;/*注重賦值順序哦*//*注重賦值順序哦*//*3.從隊列中刪除一個元素*/elemTypeoutQueue(structqueueLK*hq)(structsNode*p;elemTypetemp;/*若鏈隊為空則停止運行*/if(hq->front==NULL){printf("隊列為空，無法刪除！”)；exit(1);)temp=hq->front->data; /*暫存隊尾元素以便返回*/p=hq->front; /*暫存隊尾指針以便回收隊尾結點*/hq->front=p->next; /*使隊首指針指向下一個結點*//*若刪除后鏈隊為空，則需同時使隊尾指針為空*/if(hq->front==NULL){hq->rear=NULL;)free(p); /*回收原隊首結點*/returntemp; /*返回被刪除的隊首元素值*/}/*4.讀取隊首元素*/elemTypepeekQueue(structqueueLK*hq)(/*若鏈隊為空則停止運行*/if(hq->front==NULL){printf("隊列為空，無法刪除！exit(1);)returnhq->front->data; /★返回隊首元素*/)/*5.檢查鏈隊是否為空，若為空則返回1,否則返回0*/intemptyQueue(structqueueLK*hq)(/*判定隊首或隊尾任一個指針是否為空即可*/if(hq->front==NULL){return1;}else{return0;

/*6.清除鏈隊中的所有元素*/voidclearQueue(structqueueLK*hq)structsNode*p=hq->front; /*隊首指針賦給p*//*依次刪除隊列中的每一個結點，最后使隊首指針為空*/while(p!=NULL){hq->front=hq->front->next;free(p);p=hq->front;} /*循環結束后隊首指針已經為空*/hq->rear=NULL; /*置隊尾指針為空*/return;intmain(intargc,char*argv[])(structqueueLKq;inta[8]={3,8,5,17,9,30,15,22};inti;initQueue(&q);for(i=0;i<8;i++){enQueue(&q,a[i]);)printf(n%d”,outQueue(&q));printf(M%d”,outQueue(&q));enQueue(&qz68);printf(n%d”,peekQueue(&q));printf(n%d”,outQueue(&q));while(!emptyQueue(&q)){printf(H%d”,outQueue(&q));)printf(nn);clearQueue(&q);system(HpauseH);數據結構c語言實現系列［5］一串串的簡單模式匹配

#include<stdio.h>#include<stdlib.h>/*定義單鏈表結構體★/structnode(charch;structnode*next;)；/*初始化單鏈表*/voidinit(structnode**h)(*h=(structnode*)malloc(sizeof(structnode));(*h)->next=NULL;return;)/*將x結點插入到鏈表后*/voidappend(structnode*p,intx)(structnode*s;s=(structnode*)malloc(sizeof(structnode));s->ch=x;s->next=NULL;/*移動到表尾*/while(p->next!=NULL)(p=p->next;}p->next=s;return;}voiddisplay(structnode*p)(printf(nYoutypedstringis:n);while(p->next!=NULL)printf(n%cMzp->next->ch);

p=p->next;)printf(Mn);return;)intmain(intargc,char*argv[])(structnode*tz*s; /*s為主串，t為模式串*/structnode*sNextz*p,*q;inti,x=0;init(&s);printf("Pleasetypemainstring:n);while(x!=1,){x=getchar();if(x!=*1)(append(s,x); /*添加到表尾*/})display(s);init(&t);printf(HPleasetypesubstring:n);x=0;while(x!='1)(x=getchar();if(x!=1')(append(t,x); /*添力口到表尾*/)}display(t);/*初始化*/sNext=s->next;p=sNext;q=t->next;i=1；/*從開始字符進行比較*/

while((p->next!=NULL)&&(q->next!=NULL))/*進行匹配檢驗★/if(p->ch==q->ch)(p=p->next;q=q->next;)else(sNext=sNext->next;p=sNext; /*指向主串中的下一個*/q=t->next;/*指針后退重新開始匹配★/i++; /*記錄位置*/})/*輸出結果★/if((q->next)==NULL&&(t->next->ch==s->next->ch))(printf(Mmatchposition:為d”，i);)else{printf(nNotmatch!n);)printf(MM;return0;}數據結構C語言實現系列［6］一堆#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是關于堆順序存儲操作的5種算法 *//★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★it//★定義堆的順序存儲類型★/structheap{elemType*heap; /*定義指向動態數組空間的指針*/intlen; /*定義保存堆長度的變量*/intmaxSize;/*用于保存初始化時所給的動態數組空間的大小*//*1.初始化堆★/voidinitHeap(structheap*hbt,intms)(/*檢查ms的值是否有效*/if(ms<=0){printf("數組長度參數非法！")；exit(1);}/*動態分配存儲的數組空間*/hbt->heap=malloc(ms*sizeof(elemType));if(hbt->heap==NULL){printf("空間分配失敗！");exit(1);}/*設置maxSize域和len域的值*/hbt->maxSize=ms;hbt->len=0;return;}/*2.清除堆*/voidclearHeap(structheap*hbt)(if(hbt->heap!=NULL){free(hbt->heap);hbt->heap=NULL;hbt->len=0;hbt->maxSize=0;)return;}/*3.檢查一個堆是否為空*/intemptyHeap(structheap*hbt)

if(0==hbt->len){return1;)else{return0;/*4.向堆中插入一個元素*/voidinsertHeap(structheap*hbt,elemTypex)(inti;/*堆滿時數組空間擴展為原來的2倍，原內容被自動拷貝到P所指向的存儲空間中*/if(hbt->len==hbt->maxSize){elemType*p;p=realloc(hbt->heapz2*hbt->maxSize*sizeof(elemType));if(p==NULL){printf("存儲空間分配失敗！”)；exit(1);}hbt->heap=p; /*堆數組空間指向新空間*/hbt->maxSize=2*hbt->maxSize; /*修改數組空間的大小*/)/*向堆尾添加新元素*/hbt->heap[hbt->len]=x;hbt->len++;/*用i指向待調整元素的位置，初始指向新元素所在的堆尾位置*/i=hbt->len-1;/*尋找新元素的最終位置，每次使雙親元素下移一層*/while(0!=i){intj=(i-1)/2; /*j指向下標為i的元素的雙親*//*比較調整結束退出循環*/if(x>=hbt->heap[j]){break;)hbt->heap[i]=hbt->heap[j]; /*雙親元素下移*/i=j；}hbt->heap[i}hbt->heap[i]/*把新元素調整到最終位置*/return;/*5.從堆中刪除元素*/elemTypedeleteHeap(structheap*hbt)(elemTypetemp,x;inti,j;/*若為空堆，則顯示出錯信息并退出運行*/if(0==hbt->len){prints(”堆已空，退出運行！”)；exit(1);}/*將堆頂元素暫存在temp中以便返回*/temp=hbt->heap[0];hbt->len——;/*若刪除操作后變為空堆則返回★/if(0==hbt->len){returntemp;)/*將待調整的堆尾元素暫存在X中，以便放入最終位置*/x=hbt->heap[hbt->len];/*用i指向待調整元素的位置，初始指向堆頂位置*/i=0;/*用j指向i的左孩子位置，初始指向下標1的位置*/j=2*i+1;/*尋找待調整元素的最終位置，每次使孩子元素上移一層*/while(j<=hbt->len-1){ /*調整到孩子為空時止*//*若右孩子存在并且較小，應使j指向右孩子*/if((j<hbt->len-1)&&(hbt->heap[j]>hbt->heap[j+1])){j++；}/*若條件成立則調整結束，退出循環*/if(x<=hbt->heap[j]){break;}/*孩子元素上移到雙親位置*/hbt->heap[i]=hbt->heap[j];/*使i和j分別指向下一層結點*/i=j；

2*i+1;)/*把待調整元素放到最終位置*/hbt->heap[i]=x;returntemp;intmain(void)(intI,x;inta[8]={23,56,40,62,38,55,10,16);structheapb;initHeap(&br5);/*向堆b中依次插入數組a中的每一個元素*/for(i=0;i<8;i++){insertHeap(&b,a[i]);)while(!emptyHeap(&b)){x=deleteHeap(&b);printf(n%dH,x);if(!emptyHeap(&b)){printf(“，")；}}printf("n);clearHeap(&b);return0;}數據結構C語言實現系列[7]一二叉樹#include<stdio.h>#include<stdlib.h>#defineSTACK_MAX_SIZE30#defineQUEUE_MAX_SIZE30#ifndefelemType

typedefcharelemType;#endif/* 以下是關于二叉樹操作的11個簡單算法strUCtBTreeNode{elemTypedata;structBTreeNode*left;structBTreeNode*right;)；/*1.初始化二叉樹*/voidinitBTree(structBTreeNode**bt)(*bt=NULL;return;}/*2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立)*/voidcreateBTree(structBTreeNode**btzchar*a)(structBTreeNode*p;structBTreeNode*s[STACK_MAX_SIZE];/*定義s數組為存儲根結點指針的棧使用*/inttop=-1;/*定義top作為s棧的棧頂指針，初值為-1,表示空棧*/intk;/*用k作為處理結點的左子樹和右子樹，k=1處理左子樹，k=2處理右子樹*/inti=0;/*用i掃描數組a中存儲的二叉樹廣義表字符串，初值為0*/*bt=NULL;/*把樹根指針置為空，即從空樹開始建立二叉樹*//*每循環一次處理一個字符，直到掃描到字符串結束符\0為止*/while(a[i]!='\0'){switch(a[i]){case11:break;/*對空格不作任何處理*/case'(1：if(top==STACK_MAX_SIZE-1){printf("棧空間太小！\nH);exit(1);}top++;s[top]=p;k=1;break;case*),:if(top==-1){printf("二叉樹廣義表字符串錯誤！\n”);exit(1);)top--;break;

casek=2;break;default:p=malloc(sizeof(structBTreeNode));p->data=a[i];p->left=p->right=NULL;if(*bt==NULL){*bt=p;}else{if(k==1){s[top]->left=p;}else{s[top]->right=p;}}}i++;/*為掃描下一個字符修改i值*/)return;)/*3.檢查二叉樹是否為空，為空則返回1,否則返回0*/intemptyBTree(structBTreeNode*bt)(if(bt==NULL){return1;}else{return0;}}/*4.求二叉樹深度★/intBTreeDepth(structBTreeNode*bt)(if(bt==NULL){return0;/*對于空樹，返回。結束遞歸*/}else{intdepl=BTreeDepth(bt->left);/*計算左子樹的深度*/intdep2=BTreeDepth(bt->right);/*計算右子樹的深度*/if(depl>dep2){returndepl+1;}else{returndep2+1;}/*5.從二叉樹中查找值為x的結點，若存在則返回元素存儲位置，否則返回空值*/

elemType*findBTree(structBTreeNodeelemTypex)if(bt==NULL){returnNULL;}else{if(bt->data==x){return&(bt->data);}else{/*分別向左右子樹遞歸查找*/elemType*p;if(p=findBTree(bt->left,x)){returnp;}if(p=findBTree(bt->right,x)){returnp;)returnNULL;})}/*6.輸出二叉樹(前序遍歷)*/voidprintBTree(structBTreeNode*bt)(/*樹為空時結束遞歸，否則執行如下操作*/if(bt!=NULL){printfbt->data);/*輸出根結點的值*/if(bt->left!=NULLbt->right!=NULL){printf(“(”)；printBTree(bt->left);if(bt->right!=NULL){printf(11,n);)printBTree(bt->right);printf(M)0);})return;}/*7.清除二叉樹，使之變為一棵空樹*/voidclearBTree(structBTreeNode**bt)(if(*bt!=NULL){clearBTree(&((*bt)->left));clearBTree(&((*bt)->right));free(*bt);*bt=NULL;

}return;)/*8.前序遍歷*/voidpreOrder(structBTreeNode*bt)(if(bt!=NULL){printf(H%c”，bt->data);/*訪問根結點*/preOrder(bt->left); /*前序遍歷左子樹*/preOrder(bt->right); /*前序遍歷右子樹*/)return;}/*9.前序遍歷*/voidinOrder(structBTreeNode*bt)(if(bt!=NULL){inOrder(bt->left); /*中序遍歷左子樹*/printf(n%c”，bt->data);/★訪問根結點*/inOrder(bt->right); /★中序遍歷右子樹*/}return;}/*10.后序遍歷*/voidpostOrder(structBTreeNode*bt)(if(bt!=NULL){postOrder(bt->left); /*后序遍歷左子樹★/postOrder(bt->right); /*后序遍歷右子樹*/printf(n%c”，bt->data); /*訪問根結點*/}return;}/*11*按層遍歷*/voidlevelOrder(structBTreeNode*bt)(structBTreeNode