【正文】 // 以 an為首 （要求同學(xué)們根據(jù)下面算法的核心語(yǔ)句，編寫(xiě)一個(gè)完整算法）算法的核心語(yǔ)句 A 或 B。 qnext=s。 q=p。p=headnext。 } //準(zhǔn)備處理下一結(jié)點(diǎn)headnext=q。 //前驅(qū)變后繼 q=p。 //有頭 結(jié)點(diǎn)while(p!=head) //循環(huán)單鏈表{ r=pnext。操作前：（ a1, a2, … ai1， ai, ai+1 ， …, a n）操作后：（ an, … ai+1 ， ai, ai1 ， …, a 2, a1 ）q=head。若 線性表的長(zhǎng)度變化不大 ，且其主要操作是查找，則采用順序表；若 線性表的長(zhǎng)度變化較大， 且其主要操作是插入、刪除操作，則采用鏈表。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。　　 鏈?zhǔn)酱鎯?chǔ)時(shí)， 相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。2. 線性表邏輯結(jié)構(gòu) ： “ 一對(duì)一 ” 或 “1 :1”存儲(chǔ)結(jié)構(gòu)： 順序、鏈?zhǔn)竭\(yùn) 算： 修改、插入、刪除 [查找和排序另述 ]特征 ： 邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)： 隨機(jī)查找修改快 O(1)缺點(diǎn)： 插入、刪除慢 O(n)改進(jìn)方案： 鏈表存儲(chǔ)結(jié)構(gòu)鏈表存儲(chǔ)結(jié)構(gòu)循環(huán)鏈表的特點(diǎn) ： 從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)雙向鏈表的特點(diǎn)： 可方便 找到任一結(jié)點(diǎn)的前驅(qū)找到任一結(jié)點(diǎn)的前驅(qū)靜態(tài)鏈表的特點(diǎn)： 不用指針也能實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)和運(yùn)算特征 ： 邏輯上相鄰，物理上未必相鄰；優(yōu)點(diǎn)： 插入、刪除快 O(1)缺點(diǎn)： 隨機(jī)查找修改慢 O(n)：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？　　 順序存儲(chǔ)時(shí)， 邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。i頭結(jié)點(diǎn)頭結(jié)點(diǎn)說(shuō)明 3： 靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。 //這是一維結(jié)構(gòu)型數(shù)組例 2：一 線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) ， 用靜態(tài)鏈表如何表示？data1ZHAO 3LI 5QIAN 6WU 0ZHOU 4SUN 2…… ……0123456……1000next 說(shuō)明 1： 假設(shè) S為 SLinkList型變量，則S[MAXSIZE] 為一個(gè)靜態(tài)鏈表；S[0].next則表示第 1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。 //數(shù)據(jù)域 int next 。靜態(tài)鏈表中的指針又稱仿真指針。pnextprior = p。 sprior = p。 pnext = s?！?插入 ” 和 “ 刪除 ” 時(shí)需要同時(shí)修改兩個(gè)方向上的指針。 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表 a1 a2 … ... a n 2. 循環(huán)鏈表 和單鏈表的差別僅在于， 判別 鏈表中最后一個(gè)結(jié)點(diǎn)的 條件 不再是 “后繼是否為空 ”，而是 “后繼是否為頭結(jié)點(diǎn) ”。 // 指向后繼的指針域} DuLNode, *DuLinkList。 // 數(shù)據(jù)域 struct DuLNode *prior。但是，如果要在單鏈表中進(jìn)行在某結(jié)點(diǎn) 前 插或刪除操作，因?yàn)橐?從頭查找前驅(qū) 結(jié)點(diǎn)，所以一般情況下， 單鏈表插入和刪除操作 的時(shí)間復(fù)雜度是 O(n)（ 同順序表）。} O(n)五、 單 鏈表的操作效率分析（ 1） 查找 ：因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。i++。 while(p!=NULL) if (pdata==item) { return i。 item) { LNode* p=HL。 } coutendl。 while(P!=NULL) { coutHLdata 。 exit(1)。 } if(P!=NULL) return P data。 if(i==pos) break。 P=HLnext。 exit(1)。 } return i。 while(P!=NULL) { i++。{ P=HLnext。} HL=NULL。cpnext=npnext。 cp=HL。 } // O(1)3. 刪除單鏈表中結(jié)點(diǎn)，使之成為空表void ClearList(LNode*amp。 HL) { HL=NULL。 // 插入}作業(yè)：用單鏈表結(jié)構(gòu)來(lái)存放 26個(gè)英文字母組成的線性表（ a， b， c， … ， z） ,請(qǐng)寫(xiě)出完整的 C/C++語(yǔ)言程序。 // 輸入元素值 pnext = Lnext。 i) { p = (LinkList) malloc (sizeof (LNode))。 // 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for (i = n。L, int n) { // 逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表} // CreateList_L算法的 時(shí)間復(fù)雜度 為 : O(Listlength(L))L = (LinkList) malloc (sizeof (LNode))。操作步驟：一、建立一個(gè) “空表 ”；二、輸入數(shù)據(jù)元素 an， 建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素 an1， 建立結(jié)點(diǎn)并插入；ananan1四、依次類推，直至輸入 a1為止。} //單鏈表尾結(jié)點(diǎn)的指針域要置空！void CreateList_L(LinkList amp。 p=pnext； //讓指針變量 P指向后一個(gè)結(jié)點(diǎn)cinpdata。 in。 // 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表p=L。先挖 “ 坑 ”, 后種 “ 蘿卜 ” ！新手特別容易忘記！！{L = (LinkList) malloc (sizeof (LNode))。算法 時(shí)間復(fù)雜度 ： O(ListLength(L))如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要預(yù)分配空間，因此 生成鏈表的過(guò)程 是一個(gè)結(jié)點(diǎn) “ 逐個(gè)插入 ” 的過(guò)程。 Lnext=pnext。L) { // 將單鏈表重新置為一個(gè)空表P=L。操作 ClearList(amp。 free(q)。 pnext = qnext。 } // 尋找第 i 個(gè)結(jié)點(diǎn)，并令 p 指向其前趨if (!(pnext) || j i1) return ERROR。 j i1) { p = pnext。while (pnext amp。e) { // 刪除以 L 為頭指針 (帶頭結(jié)點(diǎn) )的單鏈表中第 i 個(gè)結(jié)點(diǎn) } // ListDelete_L算法的 時(shí)間復(fù)雜度 為 : O(ListLength(L))p = L。 free(q)。 pnext = qnext。e)在鏈表中的實(shí)現(xiàn) :有序?qū)?ai1, ai 和 ai, ai+1 改變?yōu)? ai1, ai+1ai1 ai ai+1 在單鏈表中 刪除第 i 個(gè)結(jié)點(diǎn) 的 基本操作 為 :找到線性表中第 i1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。 eai1 aisp線性表 的操作 ListDelete (amp。 pnext = s。 // 生成新結(jié)點(diǎn)sdata = e。 } // 尋找第 i1 個(gè)結(jié)點(diǎn)if (!p || j i1) return ERROR。 j i1) { p = pnext。while (p amp。L, i, e) 在單鏈表中的實(shí)現(xiàn) ： 有序?qū)? ai1, ai 改變?yōu)? ai1, e 和 e, ai eai Status ListInsert_L(LinkList L, int i, ElemType e) { // L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 // 在鏈表中第 i 個(gè)結(jié)點(diǎn)之前插入新的元素 e } // LinstInsert_L算法的 時(shí)間復(fù)雜度 為 : O(ListLength(L))……p = L。 // 取得第 i 個(gè)元素return OK。 } // 順指針向后查找，直到 p 指向第 i 個(gè)元素 // 或 p 為空if