【文章內(nèi)容簡(jiǎn)介】 的長(zhǎng)度:。cinn。 cout輸入n個(gè)元素的值:\n。 for(i=1。i=n。i++) { cine。 InsertList_L(L,i,e)。 }}2．單鏈表的綜合演示主程序void main_L(){ LinkList L。 ElemType e。 int i,num。 Create_L(L)。 TraverseList_L(L)。 while(1) { cout1提取第i個(gè)結(jié)點(diǎn)的值，2修改第i個(gè)結(jié)點(diǎn)的值，3插入第i個(gè)結(jié)點(diǎn)\n。 cout4刪除第i個(gè)結(jié)點(diǎn)，5查找第一個(gè)數(shù)據(jù)為e的結(jié)點(diǎn)，6顯示當(dāng)前鏈表的內(nèi)容\n。 cout7退出演示程序\n。 cinnum。 switch(num) { case 1: cout輸入位置i:。 cini。 if(GetElem_L(L,i,e)) cout第i個(gè)元素的值為eendl。 else cout輸入的位置不合理\n。 break。 case 2: cout輸入修改位置i和值e:。 cinie。 if(!SetElem_L(L,i,e)) cout輸入的位置不合理,修改不成功\n。 break。 case 3: cout輸入插入位置i和值e:。 cinie。 if(!InsertList_L(L,i,e)) cout插入的位置不合理,操作不成功\n。 break。 case 4: cout輸入刪除位置i:。 cini。 if(!DeleteList_L(L,i,e)) cout刪除位置不合理,操作失敗\n。 else cout第i個(gè)結(jié)點(diǎn)被刪除，其值為：e\n。 break。 case 5: cout輸入要查找的值e:。 cine。 if(!LocateElem_L(L,e)) cout查找不成功\n。 else cout數(shù)據(jù)為e的結(jié)點(diǎn)在鏈表中\(zhòng)n。 break。 case 6: TraverseList_L(L)。 break。 case 7: cout歡迎使用順序表演示程序\n。 return。 default: cout選擇不合理重新選擇\n。 }//end_switch }//end_while }//end_main_L()（運(yùn)行結(jié)果略）1．時(shí)間效率分析順序表中的元素存儲(chǔ)在一個(gè)連續(xù)的地址空間中，可以對(duì)表中的元素進(jìn)行隨機(jī)訪問(wèn)。由于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，不能隨機(jī)訪問(wèn)鏈表中的每一個(gè)結(jié)點(diǎn)，只能從鏈表的頭指針開(kāi)始逐個(gè)向后訪問(wèn)。若鏈表的長(zhǎng)度為n，則對(duì)鏈表結(jié)點(diǎn)的訪問(wèn)、插入、刪除、輸出等基本操作都要執(zhí)行一個(gè)關(guān)于指針的循環(huán)程序，其操作的時(shí)間復(fù)雜度均為T(mén)(n)=O(n)。但是，相對(duì)于順序表而言雖然插入和刪除操作的時(shí)間復(fù)雜度相同，由于其基本操作中，鏈表僅僅是簡(jiǎn)單的指針賦值運(yùn)算而順序表要移動(dòng)整個(gè)記錄，所以順序表實(shí)際花費(fèi)的時(shí)間較多。另一方面，當(dāng)順序表的實(shí)際長(zhǎng)度達(dá)到其最大長(zhǎng)度時(shí)，如果再執(zhí)行插入操作時(shí)就要整體分配更大的連續(xù)內(nèi)存空間并移動(dòng)全部記錄，此時(shí)將花費(fèi)更多的時(shí)間。2．空間效率分析相對(duì)于順序存儲(chǔ)而言，鏈表中的一個(gè)結(jié)點(diǎn)比順序表中的一個(gè)記錄要多一個(gè)指針存儲(chǔ)空間，所以通常情況下，鏈表的存儲(chǔ)密度（即線性表中的數(shù)據(jù)所占字節(jié)數(shù)/線性表所占字節(jié)數(shù)）比順序表的存儲(chǔ)密度低。但是，如果順序表的最大長(zhǎng)度遠(yuǎn)大于實(shí)際的記錄數(shù)時(shí)其存儲(chǔ)密度將會(huì)大大降低。另一方面，順序表要求較大的連續(xù)存儲(chǔ)空間，而鏈表中的結(jié)點(diǎn)在內(nèi)存中不要求連續(xù)存放。就此而言，鏈表對(duì)系統(tǒng)中內(nèi)存資源的利用率較高。在通常情況下，如果很少進(jìn)行插入和刪除操作，并且記錄總數(shù)的變化范圍可以確定時(shí)，選用順序存儲(chǔ)結(jié)構(gòu)；如果頻繁地執(zhí)行插入和刪除操作或記錄總數(shù)的變化范圍不能確定時(shí)，選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比較合理。線性表的指針是單方向的，從任意一個(gè)結(jié)點(diǎn)出發(fā)查找其后繼結(jié)點(diǎn)都比較容易，但是要找一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)必須從頭指針開(kāi)始逐個(gè)向后訪問(wèn)。本節(jié)給出的循環(huán)鏈表可以部分彌補(bǔ)以上缺陷。環(huán)鏈表的結(jié)構(gòu)是將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使整個(gè)鏈表構(gòu)成一個(gè)單向環(huán)形。這種鏈表的特點(diǎn)是從任意一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問(wèn)到表中的所有結(jié)點(diǎn)。在有些應(yīng)用問(wèn)題中，使用循環(huán)鏈表可以簡(jiǎn)化操作（比如在鏈表的末尾插入一個(gè)結(jié)點(diǎn)的運(yùn)算）。在循環(huán)鏈表中同樣設(shè)有一個(gè)頭結(jié)點(diǎn)，空循環(huán)鏈表只有一個(gè)頭結(jié)點(diǎn)組成并且自成循環(huán)。循環(huán)鏈表的許多基本操作與單鏈表一致，此處不再重復(fù)。只需注意的是：（1）在單鏈表中空表的條件是hnext==NULL，而在循環(huán)鏈表中空表的條件為hnext==h。（2）指向鏈尾結(jié)點(diǎn)的指針p在單鏈表中滿足的條件是pnext==NULL,而在循環(huán)鏈表中滿足的條件是pnext==h.在有n個(gè)結(jié)點(diǎn)的單鏈表或單向循環(huán)鏈表中，求一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，而求它的直接前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。其原因是在結(jié)點(diǎn)中只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針，而不含指向直接前驅(qū)結(jié)點(diǎn)的指針信息。為此給出以下雙向鏈表的概念。1．雙向鏈表雙向鏈表中，結(jié)點(diǎn)的結(jié)構(gòu)在單鏈表結(jié)點(diǎn)結(jié)構(gòu)(data,next)的基礎(chǔ)上再增加一個(gè)指向直接前驅(qū)結(jié)點(diǎn)的指針域prior。在C++語(yǔ)言中用以下結(jié)構(gòu)類(lèi)型來(lái)表示雙向鏈表中一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型：typedef struct DNode{ElemType data。DNode *next,*prior。}*DLinkList。其中，DNode為雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)類(lèi)型，DLinkList為指向該結(jié)點(diǎn)的指針類(lèi)型。2．雙向循環(huán)鏈表與單向循環(huán)鏈表類(lèi)似，在雙向鏈表中，使頭結(jié)點(diǎn)的prior指針指向尾結(jié)點(diǎn)且使尾結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)，這樣就構(gòu)成一個(gè)雙向循環(huán)鏈表。雙向鏈表的特點(diǎn)是可以直接求得鏈表中任意一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。但是由于增加了一個(gè)指針域，相對(duì)于單向鏈表而言，其存儲(chǔ)密度有所降低。1．靜態(tài)鏈表的概念在有些計(jì)算機(jī)高級(jí)語(yǔ)言中沒(méi)有設(shè)置指針類(lèi)型，所以不能直接使用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在這樣的語(yǔ)言環(huán)境中可借用一維數(shù)組來(lái)描述線性鏈表的存儲(chǔ)結(jié)構(gòu)，即靜態(tài)鏈表存儲(chǔ)方式。在C++語(yǔ)言中靜態(tài)鏈表的結(jié)構(gòu)類(lèi)型定義如下：const int MAXSIZE=1000。 //鏈表的最大長(zhǎng)度typedef struct SNode{ ElemType data。int cur。}SLinkList[MAXSIZE]。其中，SNode為靜態(tài)鏈表的結(jié)點(diǎn)類(lèi)型（相當(dāng)于鏈表的結(jié)點(diǎn)類(lèi)型），數(shù)據(jù)域data中存放元素的數(shù)據(jù)，下標(biāo)（游標(biāo)）域cur中存放下一個(gè)元素（直接后繼）的下標(biāo)；SLinkList為靜態(tài)鏈表存儲(chǔ)空間Space的定義類(lèi)型（相當(dāng)于鏈表中堆空間的類(lèi)型）。2．靜態(tài)鏈表的存儲(chǔ)域（1）靜態(tài)存儲(chǔ)空間Space的初始化InitSpace_S(amp。Space) 該操作將靜態(tài)鏈表的存儲(chǔ)域Space設(shè)置成一個(gè)帶頭結(jié)點(diǎn)的空閑“單循環(huán)鏈表”。其中以第一個(gè)元素a0作為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的cur=1,a1的cur=2,…,an1 的cur=0(n為最大存儲(chǔ)長(zhǎng)度）。（a）所示。存儲(chǔ)空間初始化算法如下：void InitSpace_S(SLinkList amp。Space){ int n=MAXSIZE,i。 for(i=0。in1。i++)Space[i].cur=i+1。 Space[n1].cur=0。}（2）從Space中取一個(gè)結(jié)點(diǎn)的操作NewSNode(amp。Space)該操作相當(dāng)于堆分配命令語(yǔ)句new,其作用是將Space中的空閑鏈表上第一個(gè)結(jié)點(diǎn)摘取下來(lái)并返回該結(jié)點(diǎn)的下標(biāo)。操作不成功時(shí)返回0。 （a）（b）所示。算法設(shè)計(jì)代碼如下：int NewSNode(SLinkList amp。Space){ int p。 if(p=Space[0].cur) Space[0].cur=Space[p].cur。 return p。} （3）歸還Space一個(gè)結(jié)點(diǎn)的操作DeleteSNode(amp。Space,p) 該操作相當(dāng)于釋放堆空間的語(yǔ)句delete,其作用是將一個(gè)結(jié)點(diǎn)p插入到Space中空閑鏈表上第一個(gè)結(jié)點(diǎn)的位置。(a)、(b)的前提下，歸還一個(gè)結(jié)點(diǎn)（設(shè)下標(biāo)為2）(c)所示。算法設(shè)計(jì)代碼如下：void DeleteSNode(SLinkList amp。Space,int p){ Space[p].cur=Space[0].cur。 Space[0].cur=p。}3．靜態(tài)鏈表基本操作在此給出有關(guān)靜態(tài)鏈表的初始化、插入、刪除、顯示等基本操作的實(shí)現(xiàn)過(guò)程。（1）靜態(tài)鏈表p的初始化InitList_S(amp。Space,amp。p)初始化操作是從其存儲(chǔ)空間Space的空閑鏈表中摘取一個(gè)結(jié)點(diǎn)，其下標(biāo)保存到p作為該鏈表的頭結(jié)點(diǎn)的指針。并將其cur域的值置0值。如果操作成功返回1，否則返回0。算法設(shè)計(jì)代碼如下：int InitList_S(SLinkList amp。Space,int amp。p){ if(p=NewSNode(Space)) { Space[p].cur=0。 return 1。 } return 0。} （2）靜態(tài)鏈表p的插入操作InsertList_S(amp。Space,amp。p,i,e)該操作從Space中摘取一個(gè)結(jié)點(diǎn)將data域的值置為e并將其插入到p中第i個(gè)位置。如果操作成功返回1，否則返回0。算法設(shè)計(jì)代碼如下：int InsertList_S(SLinkList amp。Space,int amp。p,int i,ElemType e){ int h=p,q,k=1。 while(Space[h].curamp。amp。ki) {//求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn) h=Space[h].cur。k++。 } if(i1||ki)return 0。 if(!(q=NewSNode(Space)))//獲取一個(gè)結(jié)點(diǎn) return 0。 Space[q].data=e。 Space[q].cur=Space[h].cur。 Space[h].cur=q。 return 1。}（3）靜態(tài)鏈表p的刪除操作DeleteList_S(amp。Space,amp。p,i,amp。e)該操作刪除p中第i個(gè)結(jié)點(diǎn)將data值賦值給e,并將資源歸還給Space。如果操作成功返回1，否則返回0。算法設(shè)計(jì)代碼如下：int DeleteList_S(SLinkList amp。Space,int amp。p,int i,ElemType amp。e){ int h=p,q,k=1。 while(Space[h].curamp。amp。ki) { h=Space[h].cur。k++。 } if(i1||!Space[h].cur)return 0。 q=Space[h].cur。 Space[h].cur=Space[q].cur。 e=Space[q].data。 DeleteSNode(Space,q)。 return 1。}（4）靜態(tài)鏈表p的遍歷操作TraverseList_S(Space,p)該操作按序顯示鏈表p中每一個(gè)結(jié)點(diǎn)的值。算法設(shè)計(jì)代碼如下：void TraverseList_S(SLinkList Space,int p){ int i=Space[p].cur。 while(i) { coutSpace[i].data 。 i=Space[i].cur。 } coutendl。}4．靜態(tài)鏈表的綜合演示程序void main_S(){ SLinkList SS。 int p,i,num,n,k。 ElemType e。 InitSpace_S(SS)。 if(!InitList_S(SS,p)) { cout初始化不成功！\n。 return。 } cout建立一個(gè)靜態(tài)鏈表，輸入長(zhǎng)度:。 cinn。 cout輸入n個(gè)結(jié)點(diǎn)的值:。 for(i=0。in。i++) { cine。 if(!InsertList_S(SS,p,i+1,e)) { cout空間已滿!\n。 break。 } } cout鏈表的初始內(nèi)容為:\n。 TraverseList_S(SS,p)。 cout1在第i個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn),2刪除第i個(gè)結(jié)點(diǎn)\n。 cout3顯示當(dāng)前鏈表的內(nèi)容,4顯示可用空間長(zhǎng)度\n。 cout5退出演示程序. 。 while(1) { cout“輸入選擇:”。 cinnum。 switch(num) { case 1: cout輸入插入位置i和值e:。 cinie。 if(!InsertList_S(SS,p,i,e)) cout插入的位置不合理,或空間已滿。\n。 break。 case 2: cout輸入刪除位置i:。 cini。 if(!DeleteList_S(SS,p,i,e)) cout刪除位置不合理,或鏈表已空\(chéng)n。 else cout第i個(gè)結(jié)點(diǎn)被刪除，其值為：e\n。 break。 case 3: TraverseList_S(SS,p)。 break。 case 4: for(i=0,k=0。) { if(!(i=SS[i].cur))break。