數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記

No.No.PAGE100/100數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記一、緒論數(shù)據(jù)結(jié)構(gòu)的符號(hào)的總稱。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)：數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。對(duì)數(shù)據(jù)的運(yùn)算。（數(shù)據(jù)元素都不是孤立存在的）。抽象數(shù)據(jù)類型（ADT）：特性，用一個(gè)三元組表示（D,S,P）。數(shù)據(jù)類型：是程序設(shè)計(jì)語言中的一個(gè)概念，它是一個(gè)值的集合和操作的集合。邏輯結(jié)構(gòu)分為四類結(jié)構(gòu)：集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。存儲(chǔ)結(jié)構(gòu)系的表示，通常由四種基本的存儲(chǔ)方法實(shí)現(xiàn)：的邏輯關(guān)系，存儲(chǔ)密度大。有些操作（如插入、刪除）效率較差。鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），且不能折半查找。表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)）。散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間鍵字隨機(jī)存取，不能順序存取，也不能折半存取。算法算法的基本概念作。算法的特性：有窮性、確定性、可行性、輸入、輸出。算法的設(shè)計(jì)目標(biāo)：正確性，可讀性，健壯性，高效率與低存儲(chǔ)量需求。算法和程序十分相似，但又有區(qū)別。程序不一定具有有窮性，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對(duì)問題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語言來描述，則它就是一個(gè)程序。算法的時(shí)間復(fù)雜度如何計(jì)算：找到一個(gè)基本操作（最深層循環(huán))分析該基本操作的執(zhí)行次數(shù)x與問題規(guī)模n的關(guān)系x的數(shù)量級(jí)就是算法時(shí)間復(fù)雜度：常用技巧：加法規(guī)則：乘法規(guī)則：“常對(duì)冪指階”三種復(fù)雜度：最壞時(shí)間復(fù)雜度：考慮輸入數(shù)據(jù)“最壞”的情況。平均時(shí)間復(fù)雜度：考慮所有輸入數(shù)據(jù)都等概率出現(xiàn)的情況。最好時(shí)間復(fù)雜度：考慮輸入數(shù)據(jù)“最好”的情況。算法的性能問題只有在n很大時(shí)才會(huì)暴露出來算法的空間復(fù)雜度普通程序：找到所占空間大小與問題規(guī)模相關(guān)的變量xn的關(guān)系x的數(shù)量級(jí)就是算法空間復(fù)雜度遞歸程序：找到遞歸調(diào)用的深度x與問題規(guī)模n的關(guān)系x的數(shù)量級(jí)就是算法空間復(fù)雜度二、線性表線性表的定義和操作線性表的基本概念線性表：是具有相同n個(gè)數(shù)據(jù)元素的有限序列。特點(diǎn)：存在唯一的第一個(gè)元素。除第一個(gè)元素之外，每個(gè)元素均只有一個(gè)直接前驅(qū)。線性表的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈表線性表的基本操作InitList(&L)L，并分配內(nèi)存空間。DestroyList(&L)L占用的內(nèi)存空間。ListInsert(&L,i,&e)Lie。ListDelete(&L,i,&e)Lie值。LocateElem(L,e)L中查找具有給定元素值的元素。GetElem(L,i)Li個(gè)位置的元素的值。Length(L)L的長(zhǎng)度，即表中元素的個(gè)數(shù)。PrintList(L)L的所有元素值。Empty(L)Ltruefalse。操作數(shù)據(jù)結(jié)構(gòu)的思路：創(chuàng)銷、增刪改查順序表順序表的基本概念順序表：用順序存儲(chǔ)上。特點(diǎn)：隨機(jī)訪問，即可以在 時(shí)間內(nèi)找到第i個(gè)元素。存儲(chǔ)密度高，每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素。拓展容量不方便（要把數(shù)據(jù)復(fù)制到新的區(qū)域）。插入刪除操作不方便，需移動(dòng)大量元素：順序表的實(shí)現(xiàn)靜態(tài)實(shí)現(xiàn)：1#defineMaxSize10//定義最大長(zhǎng)度23typedefstruct{4intdata[MaxSize];//使用靜態(tài)的數(shù)組存放數(shù)據(jù)元素5intlength;//順序表的當(dāng)前長(zhǎng)度6 7//初始化順序表voidInitList(SqList&L){L.length=0;//順序表初始長(zhǎng)度為11 }12intmain(){SqListL//聲明一個(gè)順序表InitList(L//初始化順序表return17 }動(dòng)態(tài)實(shí)現(xiàn)：1 #defineInitSize10//順序表的初始長(zhǎng)度2typedefstruct{int*data//聲明動(dòng)態(tài)分配數(shù)組的指針intMaxSize//順序表的最大容量intlength//順序表的當(dāng)前長(zhǎng)度8//初始化順序表voidInitList(SeqList&L){//用malloc函數(shù)申請(qǐng)一片連續(xù)的存儲(chǔ)空間L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=15 }16//增加動(dòng)態(tài)數(shù)組的長(zhǎng)度voidIncreaseSize(SeqList&L,intlen){int*p=L.data;L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));for(inti=0;i<L.length;i++)L.data[ip[i//將數(shù)據(jù)復(fù)制到新區(qū)域L.MaxSizeL.MaxSizelen//順序表最大長(zhǎng)度增加lenfree(p//釋放原來的內(nèi)存空間25 }26intmain(){SeqListL//聲明一個(gè)順序表InitList(L//初始化順序表30 ...IncreaseSize(L,len);return33 }malloc()針。順序表的基本操作插入：1#defineMaxSize10//定義最大長(zhǎng)度23typedefstruct{4intdata[MaxSize];//用靜態(tài)的數(shù)組存放數(shù)據(jù)元素5intlength;//順序表的當(dāng)前長(zhǎng)度6 7//在順序表i位置插入eboolListInsert(SqList&L,inti,inte){if(i1||iL.length+1//判斷i的范圍是否有效returnfalse;if(L.lengthMaxSize//判斷存儲(chǔ)空間是否已滿returnfalse;for(intjL.lengthjij--//將第i個(gè)元素之后的元素后移L.data[j]=L.data[j-1];L.data[i-1e//在位置i處放入eL.length++//長(zhǎng)度+1return19 }20intmain(){SqListL;InitList(L);242526

ListInsert(L,3,3);return0;時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：刪除：1#defineMaxSize1023typedefstruct{4intdata[MaxSize];5intlength;6 }7//刪除順序表i位置的數(shù)據(jù)并存入eboolListDelete(SqList&L,inti,int&e){if(i1||iL.length//判斷i的范圍是否有效returnfalse;eL.data[i-1//將被刪除的元素賦值給efor(intjijL.lengthj++//將第i個(gè)位置后的元素前移L.data[j-1]=L.data[j];L.length--;return17 }18intmain(){SqListL;InitList(L);inte=-1;if(ListDelete(L,3,e))printf("已刪除第3個(gè)元素，刪除元素值為%d\n"e);25else26printf("位序i不合法，刪除失敗\n");27return0;28}時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：按位查找：//靜態(tài)分配的按位查找#defineMaxSize3typedefstruct{ElemTypedata[MaxSize];intlength;89 ElemTypeGetElem(SqListL,inti){10 returnL.data[i-1];11 }1//動(dòng)態(tài)分配的按位查找2#defineInitSize1034typedefstruct{5ElemType*data;6intMaxSize;7intlength;8}SeqList;910ElemTypeGetElem(SeqListL,inti){11returnL.data[i-1];12}時(shí)間復(fù)雜度：按值查找：1 #defineInitSize2typedefstruct{ElemType*data;intMaxSize;intlength;8//查找第一個(gè)元素值為e的元素，并返回其位序intLocateElem(SqListL,ElemTypee){for(inti=0;i<L.length;i++){if(L.data[i]==e)returni+1;//數(shù)組下標(biāo)為i的元素值等于e，返回其位序14 }15 return0//沒有查找到16 }在《數(shù)據(jù)結(jié)構(gòu)》考研初試中，手寫代碼可以直接用“==”ElemType時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：鏈表單鏈表的基本概念單鏈表：用鏈?zhǔn)酱鎯?chǔ)針表示。特點(diǎn)：優(yōu)點(diǎn)：不要求大片連續(xù)空間，改變?nèi)萘糠奖?。缺點(diǎn)：不可隨機(jī)存取，要耗費(fèi)一定空間存放指針。兩種實(shí)現(xiàn)方式：帶頭結(jié)點(diǎn)，寫代碼更方便。頭結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，頭結(jié)點(diǎn)指向的下一個(gè)結(jié)點(diǎn)才存放實(shí)際數(shù)據(jù)。表和非空表的處理需要用不同的代碼邏輯。單鏈表的實(shí)現(xiàn)不帶頭結(jié)點(diǎn)的單鏈表：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//初始化一個(gè)空的單鏈表boolInitList(LinkList&L){LNULL//空表，暫時(shí)還沒有任何結(jié)點(diǎn)return10 }11voidtest(){LinkListL; //聲明一個(gè)指向單鏈表的頭指針//初始化一個(gè)空表InitList(L);16 ...17 }18//判斷單鏈表是否為空boolEmpty(LinkListL){return22 }帶頭結(jié)點(diǎn)的單鏈表：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//初始化一個(gè)單鏈表（帶頭結(jié)點(diǎn)）boolInitList(LinkList&L){L(LNode*)malloc(sizeof(LNode)); //分配一個(gè)頭結(jié)點(diǎn)if(LNULL) //內(nèi)存不足，分配失敗returnfalse;L->nextNULL; //頭結(jié)點(diǎn)之后暫時(shí)還沒有結(jié)點(diǎn)return13 }14voidtest(){LinkListL; //聲明一個(gè)指向單鏈表的頭指針//初始化一個(gè)空表InitList(L);19 ...20 }21//判斷單鏈表是否為空boolEmpty(LinkListL){if(L->next==NULL)returntrue;elsereturn28 }單鏈表的插入按位序插入（帶頭結(jié)點(diǎn)）：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在第i個(gè)位置插入元素eboolListInsert(LinkList&L,inti,ElemType8 if(i<1)9 returnFalse;LNode*p; //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)intj=0; //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)pL; //循環(huán)找到第i-1個(gè)結(jié)點(diǎn)while(p!=NULL&&j<i-1){ //如果i>lenghp最后會(huì)等于NULLp=p->next;15 j++;16 }//p值為NULL說明i值不合法if(p==NULL)returnfalse;//在第i-1個(gè)結(jié)點(diǎn)后插入新結(jié)點(diǎn)LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//將結(jié)點(diǎn)s連到p后return27 }時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：按位序插入（不帶頭結(jié)點(diǎn)）：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在第i個(gè)位置插入元素eboolListInsert(LinkList&L,inti,ElemTypee){//判斷i的合法性9 if(i<1)returnfalse;//需要判斷插入的位置是否是第1個(gè)12if(i==1){13LNode*s=(LNode*)malloc(sizeof(LNode));14s->data=e;15s->next=L;16L=s; //頭指針指向新結(jié)點(diǎn)17returntrue;18}19//i>1的情況與帶頭結(jié)點(diǎn)一樣，唯一區(qū)別是j的初始值為120LNode*p; //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)21intj=1; //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)22p=L;23//循環(huán)找到第i-1個(gè)結(jié)點(diǎn)24while(p!=NULL&&j<i-1){ //如果i>lenghp最后會(huì)等于NULL25p=p->next;26j++;27}28//p值為NULL說明i值不合法29if(p==NULL)30returnfalse;31//在第i-1個(gè)結(jié)點(diǎn)后插入新結(jié)點(diǎn)32LNode*s=(LNode*)malloc(sizeof(LNode));33s->data=e;34s->next=p->next;35p->next=s;36returntrue;37}時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：除非特別聲明，否則之后的代碼都默認(rèn)為帶頭結(jié)點(diǎn)！指定結(jié)點(diǎn)的后插操作：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在結(jié)點(diǎn)p后插入元素eboolInsertNextNode(LNode*p,ElemTypee){if(p==NULL){return10 }LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)returnfalse;s->data=e;s->next=p->next;p->next=s;return18 }19//按位序插入的函數(shù)中可以直接調(diào)用后插操作boolListInsert(LinkList&L,inti,ElemType22 if(i<1)returnFalse;LNode*p;25//指針p指向當(dāng)前掃描到的結(jié)點(diǎn)26intj=0;27//當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)28p=L;29//循環(huán)找到第i-1個(gè)結(jié)點(diǎn)30while(p!=NULL&&j<i-1){31//如果i>lengh,p最后會(huì)等于NULL32p=p->next;33j++;34}35returnInsertNextNode(p,e)36}時(shí)間復(fù)雜度：指定結(jié)點(diǎn)的前插操作：如果傳入頭指針，就可以循環(huán)整個(gè)鏈表找到指定結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)q，再對(duì)q進(jìn)行后插操作；如果不傳入頭指針，可以在指定結(jié)點(diǎn)p后插入一個(gè)結(jié)點(diǎn)s，并交換兩個(gè)結(jié)點(diǎn)所保存的數(shù)據(jù)，從而變相實(shí)現(xiàn)指定結(jié)點(diǎn)的前插操作。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在結(jié)點(diǎn)p前插入元素eboolInsertPriorNode(LNode*p,ElemTypee){returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));//內(nèi)存不足分配失敗returnfalse;//將s插入結(jié)點(diǎn)p之后s->next=p->next;p->next=s;//交換兩個(gè)結(jié)點(diǎn)中的數(shù)據(jù)s->data=p->data;p->data=e;return21 }時(shí)間復(fù)雜度：?jiǎn)捂湵淼膭h除按位序刪除：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,4//刪除第i個(gè)結(jié)點(diǎn)并將其所保存的數(shù)據(jù)存入eboolListDelete(LinkList&L,inti,ElemType&e){7 if(i<1)returnfalse;LNode*p; //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)intj=0; //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)p=L;12//循環(huán)找到第i-1個(gè)結(jié)點(diǎn)13while(p!=NULL&&j<i-1){14//如果i>lengh，p和p的后繼結(jié)點(diǎn)會(huì)等于NULL15p=p->next;16j++;17}18if(p==NULL)19returnfalse;20if(p->next==NULL)21returnfalse;22//令q暫時(shí)保存被刪除的結(jié)點(diǎn)23LNode*q=p->next;24e=q->data;25p->next=q->next;26free(q)27returntrue;28}時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：刪除指定結(jié)點(diǎn)：如果傳入頭指針，就可以循環(huán)整個(gè)鏈表找到指定結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)q，再對(duì)p進(jìn)行刪除操作；如果不傳入頭指針，可以把指定結(jié)點(diǎn)p的后繼結(jié)點(diǎn)q刪除，并使結(jié)點(diǎn)p保存結(jié)點(diǎn)q存儲(chǔ)的數(shù)據(jù)，從而變相實(shí)現(xiàn)刪除指定結(jié)點(diǎn)的操作。但是如果指定結(jié)點(diǎn)p沒有后繼結(jié)點(diǎn)，這么做會(huì)報(bào)錯(cuò)。//刪除指定結(jié)點(diǎn)pboolDeleteNode(LNode*p){if(p==NULL)returnfalse;LNode*qp->next//令q指向p的后繼結(jié)點(diǎn)//如果p是最后一個(gè)結(jié)點(diǎn)，則q指向NULL，繼續(xù)執(zhí)行就會(huì)報(bào)錯(cuò)p->data=q->data;p->next=q->next;free(q);return11 }時(shí)間復(fù)雜度：?jiǎn)捂湵淼牟檎野次徊檎遥?typedefstructLNode{2ElemTypedata;3structLNode*next;4}LNode,*LinkList;56//查找指定位序i的結(jié)點(diǎn)并返回7LNode*GetElem(LinkListL,inti){8if(i<0)9returnNULL;10LNode*p;11intj=0;12131415161718 19

p=L;while(p!=NULL&&j<i){p=p->next;j++;}returnp;//封裝后的插入操作，在第i個(gè)位置插入元素e，可以調(diào)用查詢操作和后插操作boolListInsert(LinkList&L,inti,ElemType22 if(i<1)returnFalse;//找到第i-1個(gè)元素LNode*p=GetElem(L,i-1);//在p結(jié)點(diǎn)后插入元素ereturnInsertNextNode(p,28 }時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：按值查找：//查找數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)指針，否則返回NULLLNode*LocateElem(LinkListL,ElemTypee){LNode*P=L->next;//從第一個(gè)結(jié)點(diǎn)開始查找數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)while(p!=NULL&&p->data!=e){p=7 }8 return9 }時(shí)間復(fù)雜度：最好時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：計(jì)算單鏈表長(zhǎng)度：//計(jì)算單鏈表的長(zhǎng)度intLength(LinkListL){intlen=0; //統(tǒng)計(jì)表長(zhǎng)LNode*p=L;while(p->next!=NULL){p=p->next;len++;8 }9 return10 }時(shí)間復(fù)雜度：?jiǎn)捂湵淼慕⑽膊宸ń捂湵恚?/使用尾插法建立單鏈表LLinkListList_TailInsert(LinkList&L){intx; //設(shè)ElemType為整型intL(LinkList)malloc(sizeof(LNode)); //建立頭結(jié)點(diǎn)(初始化空表)LNode*s,*rL; //r為表尾指針scanf("%d"&x); //輸入要插入的結(jié)點(diǎn)的值7 while(x!=9999){ //輸入9999表示結(jié)束s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;rs; //r指針指向新的表尾結(jié)點(diǎn)12 scanf("%d",&x);13}1413}14r->next=NULL;15returnL;16}時(shí)間復(fù)雜度：頭插法建立單鏈表：1LinkListList_HeadInsert(LinkList&L){//逆向建立單鏈表2LNode*s;3intx;4L=(LinkList)malloc(sizeof(LNode));//建立頭結(jié)點(diǎn)5L->next=NULL;6scanf("%d",&x);//輸入要插入的結(jié)點(diǎn)的值7while(x!=9999){//輸入9999表結(jié)束8s=(LNode*)malloc(sizeof(LNode));9s->data=x;10s->next=L->next;11L->next=s;12//將新結(jié)點(diǎn)插入表中，L為頭指針13scanf("%d",&x);14}15returnL;16}頭插法實(shí)現(xiàn)鏈表的逆置：//將鏈表L中的數(shù)據(jù)逆置并返回LNode*Inverse(LNode*L){LNode*p,*q;pL->next; //p指針指向第一個(gè)結(jié)點(diǎn)L->nextNULL; //頭結(jié)點(diǎn)置空//依次判斷p結(jié)點(diǎn)中的數(shù)據(jù)并采用頭插法插到L鏈表中while(p!=8 q=p;p=p->next;q->next=L->next;L->next=12 }13 return14 }具體解釋詳見\h【數(shù)據(jù)結(jié)構(gòu)】單鏈表逆置：頭插法圖解雙鏈表雙鏈表的定義：點(diǎn)和后繼結(jié)點(diǎn)。雙鏈表的實(shí)現(xiàn)：typedefstructDNode{ //定義雙鏈表結(jié)點(diǎn)類型ElemTypedata; //數(shù)據(jù)域structDNode*prior*next; //前驅(qū)和后繼指針}DNode,*DLinklist;(帶頭結(jié)點(diǎn))：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//初始化雙鏈表boolInitDLinkList(Dlinklist&L){L=(DNode*)malloc(sizeof(DNode));if(L==NULL)returnfalse;L->priorNULL; //頭結(jié)點(diǎn)的prior指針永遠(yuǎn)指向NULLL->nextNULL; //頭結(jié)點(diǎn)之后暫時(shí)還沒有結(jié)點(diǎn)，置空return14 }15voidtestDLinkList(){DLinklistL;InitDLinkList(L);19 ...20 }21//判斷雙鏈表是否為空boolEmpty(DLinklistL){if(L->next==NULL)returntrue;elsereturn28 }雙鏈表的后插操作：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后boolInsertNextDNode(DNode*p,DNode*s){if(p==NULL||s==NULL)returnfalse;s->next=p->next;//判斷結(jié)點(diǎn)p之后是否有后繼結(jié)點(diǎn)if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return17 }雙鏈表的前插操作、按位序插入操作都可以轉(zhuǎn)換成后插操作雙鏈表的刪除操作：//刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)boolDeletNextDNode(DNode*p){returnfalse;//找到p的后繼結(jié)點(diǎn)qDNode*q=p->next;returnfalse;p->next=q->next;if(q->next!=NULL)q->next->prior=p;free(q);return14 }15//銷毀一個(gè)雙鏈表boolDestoryList(DLinklist&L){//循環(huán)釋放各個(gè)數(shù)據(jù)結(jié)點(diǎn)while(L->next!=NULL){DeletNextDNode(L);free(L);//頭指針置空24 }25 }雙鏈表的遍歷：//向后遍歷while(p!=NULL){//對(duì)結(jié)點(diǎn)p做相應(yīng)處理p=5 }6//向前遍歷while(p!=NULL){//對(duì)結(jié)點(diǎn)p做相應(yīng)處理p=11 }12//跳過頭結(jié)點(diǎn)的遍歷while(p->prior!=NULL){151617

//對(duì)結(jié)點(diǎn)p做相應(yīng)處理p=p->prior;雙鏈表不可隨機(jī)存取，按位查找、按值查找操作都只能用遍歷的方式實(shí)現(xiàn)。循環(huán)鏈表循環(huán)鏈表的定義：指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。循環(huán)單鏈表的實(shí)現(xiàn)：typedefstructLNode{ElemTypedata;structLNode*next;}DNode,5//初始化循環(huán)單鏈表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));if(L==NULL)returnfalse;//最后一個(gè)結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)L->next=L;return14 }15//判斷循環(huán)單鏈表是否為空boolEmpty(LinkListL){if(L->next==L)returntrue;else2122 23

returnfalse;//判斷結(jié)點(diǎn)p是否為循環(huán)單鏈表的表尾結(jié)點(diǎn)boolisTail(LinkListL,LNode*p){if(p->next==L)returntrue;elsereturn30 }循環(huán)雙鏈表的實(shí)現(xiàn)：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//初始循環(huán)雙鏈表boolInitDLinkList(DLinklist&L){L=(DNode*)malloc(sizeof(DNode));if(L==NULL)returnfalse;//頭結(jié)點(diǎn)的prior指針指向最后一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)L->prior=L;L->next=14 }15//判斷循環(huán)雙鏈表是否為空boolEmpty(DLinklistL){if(L->next==L)returntrue;elsereturn22 }23//判斷結(jié)點(diǎn)p是否為循環(huán)雙鏈表的表尾結(jié)點(diǎn)boolisTail(DLinklistL,DNode*p){if(p->next==L)returntrue;elsereturn30 }循環(huán)雙鏈表的插入和刪除操作：//將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后boolInsertNextDNode(DNode*p,DNode*s){s->next=p->next;//循環(huán)雙鏈表不用擔(dān)心p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為空p->next->prior=s;s->prior=p;p->next=8 }9//刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)boolDeletNextDNode(DNode*p){//找到p的后繼結(jié)點(diǎn)qDNode*q=p->next;//循環(huán)雙鏈表不用擔(dān)心q結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為空p->next=q->next;q->next->prior=p;171819

free(q);returntrue;靜態(tài)鏈表靜態(tài)鏈表的定義個(gè)結(jié)點(diǎn)包括了數(shù)據(jù)元素和下一個(gè)結(jié)點(diǎn)的數(shù)組下標(biāo)。特點(diǎn)：優(yōu)點(diǎn)：增、刪操作不需要大量移動(dòng)元素。缺點(diǎn)：不能隨機(jī)存取，只能從頭結(jié)點(diǎn)開始依次往后查找，容量固定不變！靜態(tài)鏈表的定義：#defineMaxSize10 //靜態(tài)鏈表的最大長(zhǎng)度structNode{ //靜態(tài)鏈表結(jié)構(gòu)類型的定義ElemTypedata; //存儲(chǔ)數(shù)據(jù)元素intnext; //下一個(gè)元素的數(shù)組下標(biāo)5 };6//用數(shù)組定義多個(gè)連續(xù)存放的結(jié)點(diǎn)voidtestSLinkList(){structNodea[MaxSize]; //數(shù)組a作為靜態(tài)鏈表每一個(gè)數(shù)組元素的類型都是structNode10 ...11 }也可以這么定義：#defineMaxSize10 //靜態(tài)鏈表的最大長(zhǎng)度typedefstruct{ //靜態(tài)鏈表結(jié)構(gòu)類型的定義ELemTypedata; //存儲(chǔ)數(shù)據(jù)元素intnext; //下一個(gè)元素的數(shù)組下標(biāo)6voidtestSLinkList(){SLinkList9 }第一種是我們更加熟悉的寫法，第二種寫法則更加側(cè)重于強(qiáng)調(diào)a是一個(gè)靜態(tài)鏈表而非數(shù)組。靜態(tài)鏈表的注意點(diǎn)：初始化靜態(tài)鏈表時(shí)，需要把a(bǔ)[0]的next設(shè)為-1，并將空閑結(jié)點(diǎn)的next設(shè)置為某個(gè)特殊值，比如-2。按位序查找結(jié)點(diǎn)時(shí)，從頭結(jié)點(diǎn)出發(fā)挨個(gè)往后遍歷結(jié)點(diǎn)，時(shí)間復(fù)雜度 。1的結(jié)點(diǎn)；③修改新結(jié)點(diǎn)的next-1i-1號(hào)結(jié)點(diǎn)的next為新結(jié)點(diǎn)的下標(biāo)；順序表和鏈表的比較邏輯結(jié)構(gòu)：順序表和鏈表都屬于線性表，都是線性結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：順序表：順序存儲(chǔ)優(yōu)點(diǎn)：支持隨機(jī)存取，存儲(chǔ)密度高。缺點(diǎn)：大片連續(xù)空間分配不方便，改變?nèi)萘坎环奖?。鏈表：鏈?zhǔn)酱鎯?chǔ)優(yōu)點(diǎn)：離散的小空間分配方便，改變?nèi)萘糠奖?。缺點(diǎn)：不可隨機(jī)存取，存儲(chǔ)密度低。-創(chuàng)建：順序表：需要預(yù)分配大片連續(xù)空間。若分配空間過小，則之后不方便拓展容量；若分配空間過大，則浪費(fèi)內(nèi)存資源。靜態(tài)分配：靜態(tài)數(shù)組，容量不可改變。動(dòng)態(tài)分配：動(dòng)態(tài)數(shù)組，容量可以改變，但是需要移動(dòng)大量元素，時(shí)間代價(jià)高（使用malloc()、free()）。鏈表：只需要分配一個(gè)頭結(jié)點(diǎn)或者只聲明一個(gè)頭指針。-銷毀：Length=0靜態(tài)分配：靜態(tài)數(shù)組——系統(tǒng)自動(dòng)回收空間。動(dòng)態(tài)分配：動(dòng)態(tài)數(shù)組——需要手動(dòng)free()。鏈表：依次刪除各個(gè)結(jié)點(diǎn)free()。-增/刪：順序表：插入/刪除元素要將后續(xù)元素后移/前移；時(shí)間復(fù)雜度：，時(shí)間開銷主要來自于移動(dòng)元素。鏈表：插入/刪除元素只需要修改指針；時(shí)間復(fù)雜度：，時(shí)間開銷主要來自查找目標(biāo)元素。-查找：順序表按位查找：按值查找： ，若表內(nèi)元素有序，可在時(shí)間內(nèi)找到（二分法）鏈表：按位查找：按值查找：三、棧與隊(duì)列棧棧的基本概念棧是特殊的線性表：只允許在一端進(jìn)行插入或刪除操作，其邏輯結(jié)構(gòu)與普通線性表相同。（最上面的為頂元素）。（最下面的為空棧：不含任何元素的空表。

底元素）。特點(diǎn)：后進(jìn)先出（后進(jìn)棧的元素先出棧）——LIFO（LastInFirstOut）。缺點(diǎn)：棧的大小不可變，解決方法：共享?xiàng)?。棧的基本操作InitStack(&S)S，分配內(nèi)存空間。DestroyStack(&S)S所占用的內(nèi)存空間。Push(&S,x)Sx加入使其成為新的棧頂元素。Pop(&S,&x)S非空，則彈出（刪除）x返回。GetTop(S,&x)Sx返回棧頂元素。StackEmpty(S)SStruefalse。棧的順序存儲(chǔ)實(shí)現(xiàn)順序棧的定義：#defineMaxSize10 //定義棧中元素的最大個(gè)數(shù)typedefstruct{ElemTypedata[MaxSize]; //靜態(tài)數(shù)組存放棧中元素inttop; //棧頂元素6voidtestStack(){SqStackS; //聲明一個(gè)順序棧(分配空間9 }順序棧的初始化：#defineMaxSize10typedefstruct{ElemTypedata[MaxSize];inttop;6//初始化棧voidInitStack(SqStack&S){910 11

S.top1; //初始化棧頂指針//判斷棧是否為空boolStackEmpty(SqStack14 if(S.top==-1)returntrue;elsereturn18 }入棧出棧：1//新元素進(jìn)棧2boolPush(SqStack&S,ElemTypex){//判斷棧是否已滿3if(S.top==MaxSize-1)4returnfalse;5S.data[++S.top]=x;6returntrue;7}89//出棧10boolPop(SqStack&x,ElemType&x){//判斷棧是否為空11if(S.top==-1)12returnfalse;13x=S.data[S.top--];14returntrue;15}讀取棧頂元素：//讀棧頂元素boolGetTop(SqStackS,ElemType3 if(S.top==-1)returnfalse;x=S.data[S.top];return7 }共享?xiàng)＃▋蓚€(gè)棧共享同一片空間）：12#defineMaxSize10 //定義棧中元素的最大個(gè)數(shù)typedefstruct{3ElemTypedata[MaxSize];//靜態(tài)數(shù)組存放棧中元素4inttop0;//0號(hào)棧棧頂指針5inttop1;//1號(hào)棧棧頂指針6}ShStack;78//初始化棧9voidInitSqStack(ShStack&S){10S.top0=-1;11S.top1=MaxSize;12}棧的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)鏈棧的定義：1typedefstructLinknode{2ElemTypedata;//數(shù)據(jù)域3Linknode*next;//指針域4}Linknode,*LiStack;56voidtestStack(){LiStackL; //聲明一個(gè)鏈棧8 }鏈棧的初始化：typedefstructLinknode{ElemTypedata;Linknode*next;}Linknode,5//初始化棧boolInitStack(LiStack&L){L=(Linknode*)malloc(sizeof(Linknode));if(L==NULL)returnfalse;L->next=NULL;return13 }14//判斷棧是否為空boolisEmpty(LiStack&L){if(L->next==NULL)returntrue;elsereturn21 }入棧出棧：//新元素入棧boolpushStack(LiStack&L,ElemTypex){Linknode*s=(Linknode*)malloc(sizeof(Linknode));if(s==NULL)returnfalse;s->data=x;//頭插法s->next=L->next;L->next=s;return11 }12//出棧boolpopStack(LiStack&L,int&x){//棧空不能出棧if(L->next==NULL)returnfalse;Linknode*s=L->next;x=s->data;L->next=s->next;free(s);return23 }隊(duì)列隊(duì)列的基本概念隊(duì)列是操作受限的線性表：(入隊(duì))(出隊(duì))。隊(duì)頭：允許刪除的一端。隊(duì)尾：允許插入的一端。空隊(duì)列：不含任何元素的空表。特點(diǎn)：先進(jìn)先出（先入隊(duì)的元素先出隊(duì)）——FIFO（FirstInFirstOut）。隊(duì)列的基本操作InitQueue(&Q)Q。DestroyQueue(&Q)Q所占用的內(nèi)存空間。EnQueue(&Q,x)Qx加入，使之成為新的隊(duì)尾。DeQueue(&Q,&x)Qx返回。GetHead(Q,&x)Qx。QueueEmpty(Q)Qtrue。隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)順序隊(duì)列的定義：1 #defineMaxSize10; //定義隊(duì)列中元素的最大個(gè)數(shù)2typedefstruct{ElemTypedata[MaxSize]; //用靜態(tài)數(shù)組存放隊(duì)列元素5intfront,rear;//隊(duì)頭指針和隊(duì)尾指針6}SqQueue;78voidtest{9SqQueueQ;//聲明一個(gè)隊(duì)列10}順序隊(duì)列的初始化：1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;7//初始化隊(duì)列voidInitQueue(SqQueue&Q){//初始化時(shí)，隊(duì)頭、隊(duì)尾指針指向0//隊(duì)尾指針指向的是即將插入數(shù)據(jù)的數(shù)組下標(biāo)//隊(duì)頭指針指向的是隊(duì)頭元素的數(shù)組下標(biāo)Q.front=Q.rear=14 }15//判斷隊(duì)列是否為空boolQueueEmpty(SqQueueQ){if(Q.front==Q.rear)returntrue;elsereturn22 }入隊(duì)出隊(duì)（循環(huán)隊(duì)列）：//新元素入隊(duì)boolEnQueue(SqQueue&Q,ElemTypex){//如果隊(duì)列已滿直接返回if((Q.rear+1)%MaxSizeQ.front) //犧牲一個(gè)單元區(qū)分隊(duì)空和隊(duì)滿returnfalse;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return9 }10//出隊(duì)boolDeQueue(SqQueue&Q,ElemType&x){//如果隊(duì)列為空直接返回if(Q.rear==Q.front)returnfalse;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return19 }獲得隊(duì)頭元素：//獲取隊(duì)頭元素并存入xboolGetHead(SqQueue&Q,ElemType&x){if(Q.rear==Q.front)returnfalse;x=Q.data[Q.front];return7 }注意：

環(huán)隊(duì)列不能使用Q.rear==Q.front作為判空的條件，因?yàn)楫?dāng)隊(duì)列已滿時(shí)也符合該條件，會(huì)與判空發(fā)生沖突！解決方法一：犧牲一個(gè)單元來區(qū)分隊(duì)空和隊(duì)滿，即將(Q.rear+1)%MaxSize==Q.front作為判斷隊(duì)列是否已滿的條件。（主流方法）解決方法二：設(shè)置size變量記錄隊(duì)列長(zhǎng)度。1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;6intsize;7}SqQueue;89//初始化隊(duì)列10voidInitQueue(SqQueue&Q){11Q.rear=Q.front=0;12Q.size=0;13}1415//判斷隊(duì)列是否為空16boolQueueEmpty(SqQueue0){17if(Q.size==0)18returntrue;19else20returnfalse;21}2223//新元素入隊(duì)24boolEnQueue(SqQueue&Q,ElemTypex){25if(Q.size==MaxSize)26returnfalse;27Q.size++;28Q.data[Q.rear]=x;29Q.rear=(Q.rear+1)%MaxSize;30returntrue;31}3233//出隊(duì)34boolDeQueue(SqQueue&Q,ElemType&x){35if(Q.size==0)36returnfalse;37Q.size--;38x=Q.data[Q.front];39Q.front=(Q.front+1)%MaxSize;40returntrue;41}解決方法三tag變量記錄隊(duì)列最近的操作。（tag=0：最近進(jìn)行的是刪除操作；tag=1近進(jìn)行的是插入操作）1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;inttag;8//初始化隊(duì)列voidInitQueue(SqQueue&Q){Q.rear=Q.front=0;Q.tag=13 }14//判斷隊(duì)列是否為空boolQueueEmpty(SqQueue0){if(Q.front==Q.rear&&Q.tag==0)returntrue;elsereturn21 }22//新元素入隊(duì)boolEnQueue(SqQueue&Q,ElemTypex){if(Q.rear==Q.front&&tag==1)returnfalse;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1;return31 }32//出隊(duì)boolDeQueue(SqQueue&Q,ElemType&x){if(Q.rear==Q.front&&tag==0)returnfalse;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.tag=0;return41 }隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)鏈隊(duì)列的定義：//鏈?zhǔn)疥?duì)列結(jié)點(diǎn)typedefstructLinkNode{ElemTypedata;structLinkNode*next;6//鏈?zhǔn)疥?duì)列typedefstruct{//頭指針和尾指針LinkNode*front,*rear;}*LinkQueue;鏈隊(duì)列的初始化（帶頭結(jié)點(diǎn)）：typedefstructLinkNode{ElemTypedata;structLinkNode*next;5typedefstruct{LinkNode*front,*rear;9//初始化隊(duì)列voidInitQueue(LinkQueue&Q){//初始化時(shí)，front、rear都指向頭結(jié)點(diǎn)Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=15 }16//判斷隊(duì)列是否為空boolIsEmpty(LinkQueueQ){if(Q.front==Q.rear)returntrue;elsereturn23 }入隊(duì)出隊(duì)：//新元素入隊(duì)voidEnQueue(LinkQueue&Q,ElemTypex){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=8 }9//隊(duì)頭元素出隊(duì)boolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==Q.rear)returnfalse;LinkNode*p=Q.front->next;x=p->data;Q.front->next=p->next;//如果p是最后一個(gè)結(jié)點(diǎn)，則將隊(duì)頭指針也指向NULLif(Q.rear==p)Q.rear=Q.front;free(p);return22 }以上是帶頭結(jié)點(diǎn)的鏈隊(duì)列，下面是不帶頭結(jié)點(diǎn)的操作：typedefstructLinkNode{ElemTypedata;structLinkNode*next;5typedefstruct{LinkNode*front,*rear;9//初始化隊(duì)列voidInitQueue(LinkQueue&Q){12//不帶頭結(jié)點(diǎn)的鏈隊(duì)列初始化，頭指針和尾指針都指向NULL13Q.front=NULL;14Q.rear=NULL;15}16//判斷隊(duì)列是否為空boolIsEmpty(LinkQueueQ){if(Q.front==NULL)returntrue;elsereturn23 }24//新元素入隊(duì)voidEnQueue(LinkQueue&Q,ElemTypex){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;//第一個(gè)元素入隊(duì)時(shí)需要特別處理if(Q.front==NULL){Q.front=s;Q.rear=s;}else{Q.rear->next=s;Q.rear=37 }38 }39//隊(duì)頭元素出隊(duì)boolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==NULL)returnfalse;LinkNode*s=Q.front;x=s->data;if(Q.front==Q.rear){Q.front=Q.rear=NULL;}else{Q.front=Q.front->next;50 }free(s);return53 }雙端隊(duì)列定義：雙端隊(duì)列是允許從兩端插入、兩端刪除的線性表。如果只使用其中一端的插入、刪除操作，則等同于棧。兩端插入，一端刪除一端插入，兩端刪除兩端插入，一端刪除一端插入，兩端刪除輸出受限的雙端隊(duì)列：允許考點(diǎn)：判斷輸出序列的合法化

的線性表。的線性表。例：數(shù)據(jù)元素輸入序列為1，2，3，4，判斷4!=24個(gè)輸出序列的合法性棧中合法的序列，雙端隊(duì)列中一定也合法棧輸入受限的雙端隊(duì)列輸出受限的雙端隊(duì)列14個(gè)合法() 42134231不合法只有4132和4231不合法棧與隊(duì)列的應(yīng)用棧在括號(hào)匹配中的應(yīng)用用棧實(shí)現(xiàn)括號(hào)匹配：（棧的特性——LIFO）。遇到左括號(hào)就入棧。遇到右括號(hào)，就“消耗”一個(gè)左括號(hào)（出棧）。匹配失敗情況：掃描到右括號(hào)且?？?，則該右括號(hào)單身。掃描完所有括號(hào)后，棧非空，則該左括號(hào)單身。左右括號(hào)不匹配。開始開始no?？?？yesno還有未處理的括號(hào)？yesa是左括號(hào)？yesnoyes?？眨縩ob與a匹配？yesno結(jié)束匹配失敗匹配成功彈出棧頂元素b掃描下一個(gè)括號(hào)aa壓入棧頂#defineMaxSize10typedefstruct{chardata[MaxSize];inttop;6voidInitStack(SqStack&S);boolStackEmpty(SqStack&S);boolPush(SqStack&S,charx);boolPop(SqStack&S,char11//判斷長(zhǎng)度為length的字符串str中的括號(hào)是否匹配boolbracketCheck(charstr[],intlength){SqStackS;InitStack(S);//遍歷strfor(inti=0;i<length;i++){//掃描到左括號(hào)，入棧19 if(str[i]=='('||str[i]=='['||str[i]=='{'){Push(S,str[i]);}else{//掃描到右括號(hào)且?？罩苯臃祷豬f(StackEmpty(S))returnfalse;chartopElem;//用topElem接收棧頂元素Pop(S,topElem);//括號(hào)不匹配29 if(str[i]==')'&&topElem!='(')30 returnfalse;31 if(str[i]==']'&&topElem!='[')32 returnfalse;33 if(str[i]=='}'&&topElem!='{')34 returnfalse; }35}36//掃描完畢若?？談t說明字符串str中括號(hào)匹配37returnStackEmpty(S);38}棧在表達(dá)式求值中的應(yīng)用轉(zhuǎn)換為前綴或后綴表達(dá)式，然后再進(jìn)行求值。前綴表達(dá)式（波蘭表達(dá)式）：前綴表達(dá)式的運(yùn)算符位于兩個(gè)操作數(shù)之前。后綴表達(dá)式（逆波蘭表達(dá)式）：后綴表達(dá)式的運(yùn)算符位于兩個(gè)操作數(shù)之后。中綴轉(zhuǎn)后綴的手算方法：確定中綴表達(dá)式中各個(gè)運(yùn)算符的運(yùn)算順序。選擇下一個(gè)運(yùn)算符，按照的方式組合成一個(gè)新的操作數(shù)。如果還有運(yùn)算符沒被處理，就繼續(xù)執(zhí)行。例：將 轉(zhuǎn)換為后綴表達(dá)式？答：中綴轉(zhuǎn)后綴要遵循“左優(yōu)先”原則：只要左邊的運(yùn)算符能先計(jì)算，就優(yōu)先計(jì)算左邊的。后綴表達(dá)式的手算方法：例：計(jì)算 ?答：后綴表達(dá)式的機(jī)算方法：從左往右掃描下一個(gè)元素，直到處理完所有元素。若掃描到操作數(shù)則壓入棧，并回到第一步；否則執(zhí)行第三步。若掃描到運(yùn)算符，則彈出兩個(gè)棧頂元素，執(zhí)行相應(yīng)運(yùn)算，運(yùn)算結(jié)果壓回棧頂，回到第一步。彈出棧頂元素時(shí)，先出棧的是“右操作數(shù)”。開始開始結(jié)束no還有未處理的元素？yesa是操作數(shù)？yesa壓入棧頂no彈出兩個(gè)棧頂元素并執(zhí)行相應(yīng)的計(jì)算，得到結(jié)果bb壓入棧頂掃描下一個(gè)元素a中綴轉(zhuǎn)前綴的手算方法：確定中綴表達(dá)式中各個(gè)運(yùn)算符的運(yùn)算順序。選擇下一個(gè)運(yùn)算符，按照的方式組合成一個(gè)新的操作數(shù)。如果還有運(yùn)算符沒被處理，就繼續(xù)執(zhí)行第二步。例：將 轉(zhuǎn)為前綴表達(dá)式？答： 中綴轉(zhuǎn)前綴遵循“右優(yōu)先”原則：只要右邊的運(yùn)算符能先計(jì)算，就優(yōu)先算右邊的。前綴表達(dá)式的計(jì)算方法：從右往左掃描下一個(gè)元素，直到處理完所有元素。若掃描到操作數(shù)則壓入棧，并回到第一步；否則執(zhí)行第三步。若掃描到運(yùn)算符，則彈出兩個(gè)棧頂元素，執(zhí)行相應(yīng)運(yùn)算，運(yùn)算結(jié)果壓回棧頂，回到第一步。中綴轉(zhuǎn)后綴的機(jī)算方法：理各個(gè)元素，直到末尾?？赡苡龅饺N情況：遇到操作數(shù)：直接加入后綴表達(dá)式。遇到界限符：遇到“(”直接入棧；遇到“)”則依次彈出棧內(nèi)運(yùn)算符并加入后綴表達(dá)式，直到彈出“(”為止。注意：“(”不加入后綴表達(dá)式。遇到運(yùn)算符：依次彈出棧中優(yōu)先級(jí)“(”或?？談t停止。之后再把當(dāng)前運(yùn)算符入棧。1#defineMaxSize402typedefstruct{3chardata[MaxSize];4inttop;5}SqStack;67typedefstruct{8chardata[MaxSize];9intfront,rear;10}SqQueue;1112voidInitStack(SqStack&S);13boolStackEmpty(SqStackS);14boolPush(SqStack&S,charx);15boolPop(SqStack&S,char&x);16voidInitQueue(SqQueue&Q);17boolEnQueue(LQueue&Q,charx);18boolDeQueue(LQueue&Q,char&x);19boolQueueEmpty(SqQueueQ);2021//判斷元素ch是否入棧22intJudgeEnStack(SqStack&S,charch){23chartp=S.data[S->top];24//如果ch是a~z則返回-125if(ch>='a'&&ch<='z')26return-1;27//如果ch是+、-、*、/且棧頂元素優(yōu)先級(jí)大于等于ch則返回028elseif(ch=='+'&&(tp=='+'||tp=='-'||tp=='*'||tp=='/'))29return0;30elseif(ch=='-'&&(tp=='+'||tp=='-'||tp=='*'||tp=='/'))31return0;32elseif(ch=='*'&&(tp=='*'||tp=='/'))33return0;34elseif(ch=='/'&&(tp=='*'||tp=='/'))35return0;36//如果ch是右括號(hào)則返回237elseif(ch==')')38return2;39//其他情況ch入棧，返回140elsereturn1;41}42//中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式intmain(intargc,charconst*argv[]){SqStackS;SqQueueQ;InitStack(S);InitQueue(Q);charch;printf("請(qǐng)輸入表達(dá)式，以“#”結(jié)束：");scanf("%c",&ch);52 while(ch!='#'){//當(dāng)棧為空時(shí)if(StackEmpty(&S)){//如果輸入的是數(shù)即a~z56 if(ch>='a'&&ch<='z')EnQueue(Q,ch);//如果輸入的是運(yùn)算符，直接入棧elsePuch(S,ch);}else{//當(dāng)棧非空時(shí)，判斷ch是否需要入棧intn=JudgeEnStack(S,ch);//當(dāng)輸入是數(shù)字時(shí)直接入隊(duì)65 if(n==-1){EnQueue(Q,ch);}elseif(n==0){//當(dāng)輸入是運(yùn)算符且運(yùn)算符優(yōu)先級(jí)不高于棧頂元素時(shí)while(1){//取棧頂元素入隊(duì)chartp;Pop(S,tp);EnQueue(Q,tp);//再次判斷是否需要入棧n=JudgeEnStack(S,ch); //當(dāng)棧頭優(yōu)先級(jí)低于輸入運(yùn)算符或者棧頭為‘)’時(shí)，入棧并跳出循環(huán)77 if(n!=0){EnStack(S,ch);break;80 }81 }}elseif(n==2){//當(dāng)出現(xiàn)‘)’時(shí)將()中間的運(yùn)算符全部出棧入隊(duì)while(1){chartp;Pop(S,tp);87 if(tp=='(')break;elseEnQueue(Q,tp);91 }}else{//當(dāng)運(yùn)算符優(yōu)先級(jí)高于棧頂元素或出現(xiàn)‘(’時(shí)直接入棧Push(S,ch);95 }96 }97 scanf("%c",98 }//將最后棧中剩余的運(yùn)算符出棧入隊(duì)while(!StackEmpty(S)){chartp;102Pop(S,tp);103EnQueue(Q,tp);104}105//輸出隊(duì)中元素106while(!QueueEmpety(Q)){107printf("%c",DeQueue(Q));108}109return0;110}中綴表達(dá)式的機(jī)算方法：+后綴表達(dá)式的求值（兩個(gè)算法的結(jié)合）初始化兩個(gè)棧，（操作數(shù)棧和運(yùn)算符棧），若掃描到操作數(shù)，壓入操作數(shù)棧；若掃描到運(yùn)算符或界限符，則按照“中綴轉(zhuǎn)后綴”相同的邏輯壓入運(yùn)算符棧（期間也會(huì)彈出運(yùn)算符，每當(dāng)彈出一個(gè)運(yùn)算符時(shí)，就需要再?gòu)棾鰞蓚€(gè)操作數(shù)棧的棧頂元素并執(zhí)行相應(yīng)運(yùn)算，運(yùn)算結(jié)果再壓回操作數(shù)棧）。棧在遞歸中的應(yīng)用函數(shù)調(diào)用的特點(diǎn)：最后被調(diào)用的函數(shù)最先執(zhí)行結(jié)束（LIFO）。函數(shù)調(diào)用時(shí)，需要用一個(gè)“函數(shù)調(diào)用?！贝鎯?chǔ)：調(diào)用返回地址實(shí)參局部變量遞歸調(diào)用時(shí)，函數(shù)調(diào)用?？煞Q為“遞歸工作?！表敚幻客顺鲆粚舆f歸，就從棧頂彈出相應(yīng)信息。缺點(diǎn)：效率低，太多層遞歸可能會(huì)導(dǎo)致棧溢出；可能包含很多重復(fù)計(jì)算。可以自定義棧將遞歸算法改造成非遞歸算法。隊(duì)列的應(yīng)用樹的層次遍歷圖的廣度優(yōu)先遍歷操作系統(tǒng)中多個(gè)進(jìn)程爭(zhēng)搶著使用有限的系統(tǒng)資源時(shí)，先來先服務(wù)算法（FirstComeFirstService）是一種常用策略。特殊矩陣的壓縮存儲(chǔ)除非題目特別說明，否則數(shù)組下標(biāo)默認(rèn)從0開始。一維數(shù)組的存儲(chǔ)：LOC=LOC+i*sizeof(ElemType)(0≤i<10)二維數(shù)組的存儲(chǔ)：M行N列的二維數(shù)組 中，設(shè)起始地址為L(zhǎng)OC，若按行優(yōu)先存儲(chǔ)，則 的存地址=LOC+(i*N+j)*sizeof(ElemType)M行N列的二維數(shù)組 中，設(shè)起始地址為L(zhǎng)OC，若按列優(yōu)先存儲(chǔ)，則 的存地址=LOC+(j*M+i)*sizeof(ElemType)對(duì)稱矩陣的壓縮存儲(chǔ)：若n階矩陣中任意一個(gè)元素 都有 則該矩陣為對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，只需存儲(chǔ)主對(duì)角線+下三角區(qū)。若按照行優(yōu)先原則將各元素存入一維數(shù)組中，即 存到數(shù)組 中，那么有 ，又 故有：若按照列優(yōu)先存儲(chǔ)，有： 三角矩陣的壓縮存儲(chǔ)：下三角矩陣：除了主對(duì)角線和下三角區(qū)，其余的元素都相同。上三角矩陣：除了主對(duì)角線和上三角區(qū)，其余的元素都相同。壓縮存儲(chǔ)策略：按行優(yōu)先原則將主對(duì)角線+下三角區(qū)存入一維數(shù)組中，并在最后一個(gè)位置存常量。即 存入到數(shù)組 中，那么數(shù)組 共有 個(gè)元素。對(duì)于k，有：三對(duì)角矩陣的壓縮存儲(chǔ)：三對(duì)角矩陣，又稱帶狀矩陣：當(dāng) 時(shí)，有中，那么。對(duì)于三對(duì)角矩陣，按行優(yōu)先原則，只存儲(chǔ)帶狀部分，即 存入到數(shù)組中，那么。若已知數(shù)組下標(biāo)k，則 。稀疏矩陣的壓縮存儲(chǔ)：稀疏矩陣的非零元素遠(yuǎn)遠(yuǎn)少于矩陣元素的個(gè)數(shù)。壓縮存儲(chǔ)策略：<行，列，值>鏈?zhǔn)酱鎯?chǔ)：十字鏈表法四、串串的基本概念串：即字符串（String）是由零個(gè)或多個(gè)字符組成的有限序列。串的長(zhǎng)度：中字符的個(gè)數(shù)n， 時(shí)的串稱為空串。子串：串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串。字符在主串中的位置：字符在串中的序號(hào)。串的基本操作StrAssign(&T,chars)Tchars。StrCopy(&T,S)ST。StrEmpty(S)STRUE。StrLength(S)S中元素的個(gè)數(shù)。ClearString(&S)S清為空串。DestroyString(&S)S銷毀（回收存儲(chǔ)空間）。Concat(&T,S1,S2)TS1S2SubString(&Sub,S,pos,len)SubSposlen的子串。Index(S,T)STS0。StrCompare(S,T)S>T，則返回值>0S=T，則返回值=0S<T值<0。串的存儲(chǔ)實(shí)現(xiàn)串的順序存儲(chǔ)（靜態(tài)數(shù)組）：//ch[0]廢棄不用，聲明int型變量length來存放串的長(zhǎng)度#defineMAXLEN3typedefstruct{charch[MAXLEN];intlength;8//串的初始化boolInitString(SString&S){S.length=0;return13 }14//求串的長(zhǎng)度intStrLength(SStringS){return18 }19//求主串由位序pos開始len長(zhǎng)度的子串存入到串Sub中boolSubString(SString&Sub,SStringS,intpos,intlen){if(pos+len-1>S.length)returnfalse;for(inti=pos;i<pos+len;i++)Sub.ch[i-pos+1]=S.ch[i];Sub.length=len;return28 }29//比較S與T的大小。若S>T，則返回值大于0S=T，則返回值等于0S<T，則返回值小于0intStrCompare(SStringS,SStringT){for(inti=1;i<=S.length&&i<=T.length;i++){if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i]35 }//掃描過的所有字符都相同，則長(zhǎng)度長(zhǎng)的串更大returnS.length-T.length;38 }39//定位串T在串S中的位置，若無法定位則返回0intIndex(SStringS,SStringT){inti=1,n=StrLength(S),m=StrLength(T);SStringsub; //用于暫存數(shù)據(jù)while(i<=n-m+1){SubString(sub,S,i,m);46if(StrCompare(sub,T)!=0)47++i;48else49returni;50}51return0;52}535455565758voidtest{SStringS;InitString(S);...}串的順序存儲(chǔ)（動(dòng)態(tài)數(shù)組）：1 #defineMAXLEN2typedefstruct{char*ch;intlength;7boolInitString(HString&S){S.ch=(char*)malloc(MAXLEN*sizeof(char));if(S.ch==NULL)returnfalse;S.length=0;return14 }15voidtest{HStringS;InitString(S);19 ...20 }串的鏈?zhǔn)酱鎯?chǔ)：typedefstructStringNode{charch; //每個(gè)結(jié)點(diǎn)存1個(gè)字符structStringNode*next;}StringNode,*String;上述方式存儲(chǔ)密度很低，可以使每個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符。每個(gè)結(jié)點(diǎn)被稱為塊，整個(gè)鏈表被稱為塊鏈結(jié)構(gòu)。typedefstructStringNode{charch[4]; //每個(gè)結(jié)點(diǎn)存多個(gè)字符structStringNode*next;}StringNode,*String;串的樸素模式匹配串的模式匹配：在主串中找到與模式串相同的子串，并返回其所在主串中的位置。模式串某個(gè)對(duì)應(yīng)字符不匹配時(shí)，就立即放棄當(dāng)前子串，轉(zhuǎn)而檢索下一個(gè)子串。串的樸素模式匹配算法代碼實(shí)現(xiàn)：//在主串S中找到與模式串T相同的子串并返回其位序，否則返回0intIndex(SStringS,SStringT){intk=1;4inti=k,j=1;5while(i<=S.length&&j<=T.length){6if(S.ch[i]==T.ch[j]){7++i;++j;8}else{9k++;i=k;j=1;10}11}12if(j>T.length)13returnk;14else15return0;16}時(shí)間復(fù)雜度：設(shè)模式串長(zhǎng)度為m，主串長(zhǎng)度為n最壞時(shí)間復(fù)雜度：KPM算法i間開銷增加。最壞時(shí)間復(fù)雜度。串的前綴：包含第一個(gè)字符，且不包含最后一個(gè)字符的子串。串的后綴：包含最后一個(gè)字符，且不包含第一個(gè)字符的子串。nextj個(gè)字符匹配失敗時(shí)，將前（1~j-1）個(gè)字符組成的串記為S，則：next[j]=S的最長(zhǎng)相等前后綴長(zhǎng)度+1。特別地，next[1]=0。例：求模式串“abcabd”的next數(shù)組。序號(hào)j123456模式串a(chǎn)bcabdnext[j]011123KPM算法：當(dāng)子串和模式串不匹配時(shí)，ij=next[j]。KMP算法的平均時(shí)間復(fù)雜度為：。KPM算法代碼實(shí)現(xiàn)：//獲取模式串T的next[]數(shù)組voidgetNext(SStringT,int3 inti=1,j=0;4 next[1]=0;5 while(i<T.length){6 if(j==0||T.ch[1]==T.ch[j]){7 ++i;++j;next[i]=j;}elsej=next[j];11 }12 }13//KPM算法，求主串S中模式串T的位序，沒有則返回0intIndex_KPM(SStringS,SString16 inti=1,j=1;intnext[T.length+1];getNext(T,next);while(i<=S.length&&j<=T.length){20if(j==0||S.ch[i]==T.ch[j]){21++i;++j;22}else23j=next[j];24}25if(j>T.length)26returni-T.length;27else28return0;29}3031intmain(){32SStringS={"ababcabcd",9};33SStringT={"bcd",3};34printf("%d",Index_KPM(S,T));//輸出935}KPMnext數(shù)組：1212voidgetNextval(SStringT,intnextvalinti=1,j=0;3nextval[1]=0;4while(i<T.length){5if(j==0||T.ch[i]==T.ch[j]){6++i;++j;7if(T.ch[i]!=T.ch[j])8nextval[i]=j;9else10nextval[i]=nextval[j];11}else12j=nextval[j];13}14}五、樹樹的概念樹的定義和基本術(shù)語樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，n0時(shí)，稱為空樹?？諛渲袘?yīng)滿足：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集合T1，T2，…，Tm合本身又是一棵樹，并且稱為根結(jié)點(diǎn)的子樹。度：樹中一個(gè)結(jié)點(diǎn)的孩子個(gè)數(shù)稱為該結(jié)點(diǎn)的度。所有結(jié)點(diǎn)的度的最大值