【正文】 cpnext。cpnext=npnext。 delete cp。} HL=NULL。 } //O(n)4. 得到單鏈表的長度 int ListSize(LNode* HL) //帶頭結(jié)點 { P=HLnext。 int i=0。 while(P!=NULL) { i++。 P = P next。 } return i。} //O(n)5. 得到單鏈表中第 pos個結(jié)點中的元素 ElemType GetElem(LNode* HL, int pos){ if(pos1) { cerrpos is out range!endl。 exit(1)。 } i=0。 P=HLnext。 while(P!=NULL){ i++。 if(i==pos) break。 P = P next。 } if(P!=NULL) return P data。 else{ cerrpos is out range!endl。 exit(1)。}} //O(n)6. 遍歷一個單鏈表 void TraverseList(LNode* HL){ P=HLnext。 while(P!=NULL) { coutHLdata 。 P = P next。 } coutendl。} O(n)7. 查找具有給定值的第一個元素 bool Find(LNode* HL, ElemTypeamp。 item) { LNode* p=HL。int i=1。 while(p!=NULL) if (pdata==item) { return i。 } else {p=pnext。i++。} return false。} O(n)五、 單 鏈表的操作效率分析（ 1） 查找 ：因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。時間效率分析（ 2） 插入和刪除：因線性鏈表不需要移動元素，只要修改指針，僅就插入或刪除而言，時間復(fù)雜度為 O(1)。但是，如果要在單鏈表中進行在某結(jié)點 前 插或刪除操作，因為要 從頭查找前驅(qū) 結(jié)點，所以一般情況下， 單鏈表插入和刪除操作 的時間復(fù)雜度是 O(n)（ 同順序表）。 1. 雙向鏈表六、其它形式的鏈表typedef struct DuLNode { ElemType data。 // 數(shù)據(jù)域 struct DuLNode *prior。 // 指向前驅(qū)的指針域 struct DuLNode *next。 // 指向后繼的指針域} DuLNode, *DuLinkList。雙向鏈表 ： 鏈表中每個結(jié)點除后繼指針域和數(shù)據(jù)域外還有一個前驅(qū)指針域。 最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表 a1 a2 … ... a n 2. 循環(huán)鏈表 和單鏈表的差別僅在于， 判別 鏈表中最后一個結(jié)點的 條件 不再是 “后繼是否為空 ”，而是 “后繼是否為頭結(jié)點 ”。雙向循環(huán)鏈表空表非空表 a1 a2 … ... a n雙向鏈表的操作特點：“ 查詢 ” 和單鏈表相同。“ 插入 ” 和 “ 刪除 ” 時需要同時修改兩個方向上的指針。ai1 aiesnext = pnext。 pnext = s。snextprior = s。 sprior = p。ps插入ai1刪除ai ai+1pnext = pnextnext。pnextprior = p。p七、 靜態(tài)鏈表靜態(tài)鏈表： 在數(shù)組中增加一個（或兩個）指針域，這些指針域用來存放下一個（或上一個）數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表（或雙鏈表）。靜態(tài)鏈表中的指針又稱仿真指針。 靜態(tài)單鏈表的類型定義如下：靜態(tài)單鏈表的類型定義如下： define MAXSIZE 1000 //預(yù)分配最大的元素個數(shù)（連續(xù)空間typedef struct { DataType data 。 //數(shù)據(jù)域 int next 。 //指示域 }ponent , SLinkList[MAXSIZE] 。 //這是一維結(jié)構(gòu)型數(shù)組例 2：一 線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) ， 用靜態(tài)鏈表如何表示？data1ZHAO 3LI 5QIAN 6WU 0ZHOU 4SUN 2…… ……0123456……1000next 說明 1： 假設(shè) S為 SLinkList型變量，則S[MAXSIZE] 為一個靜態(tài)鏈表；S[0].next則表示第 1個結(jié)點在數(shù)組中的位置。說明 2： 如果數(shù)組的第 i個分量表示鏈表的第 k個結(jié)點，則：S[i].data表示第 k個結(jié)點的數(shù)據(jù)；S[i].next 表示第 k+1個結(jié)點 (即 k的直接后繼 )的位置。i頭結(jié)點頭結(jié)點說明 3： 靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。例如：在線性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) 的QIAN, SUN之間 插入新元素插入新元素 LIU， 可以這樣實現(xiàn)：S[7].next = S[3].next；；Step2:將 QIAN的游標換為新元素 LIU的下標：S[3].next = 7Step1:將 QIAN的游標值存入 next的游標中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi頭結(jié)點頭結(jié)點LIU 677本章小結(jié)1. 線性結(jié)構(gòu) (包括表、棧、隊、數(shù)組）的定義和特點 ：2. 僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和一個直接后繼。2. 線性表邏輯結(jié)構(gòu) ： “ 一對一 ” 或 “1 :1”存儲結(jié)構(gòu)： 順序、鏈式運 算： 修改、插入、刪除 [查找和排序另述 ]特征 ： 邏輯上相鄰，物理上也相鄰；優(yōu)點： 隨機查找修改快 O(1)缺點： 插入、刪除慢 O(n)改進方案： 鏈表存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu)循環(huán)鏈表的特點 ： 從任一結(jié)點出發(fā)均可找到表中其他結(jié)點從任一結(jié)點出發(fā)均可找到表中其他結(jié)點雙向鏈表的特點： 可方便 找到任一結(jié)點的前驅(qū)找到任一結(jié)點的前驅(qū)靜態(tài)鏈表的特點： 不用指針也能實現(xiàn)鏈式存儲和運算特征 ： 邏輯上相鄰，物理上未必相鄰；優(yōu)點： 插入、刪除快 O(1)缺點： 隨機查找修改慢 O(n)：順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？　　 順序存儲時， 邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。　　 鏈式存儲時， 相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。順序表 適宜于做 查找 這樣的靜態(tài)操作； 鏈表 宜于做 插入、刪除 這樣的動態(tài)操作。若 線性表的長度變化不大 ，且其主要操作是查找，則采用順序表；若 線性表的長度變化較大， 且其主要操作是插入、刪除操作，則采用鏈表。作業(yè)：試用 C/C++語言編寫一個算法，將一循環(huán)單鏈表就地逆置。操作前：（ a1, a2, … ai1， ai, ai+1 ， …, a n）操作后：（ an, … ai+1 ， ai, ai1 ， …, a 2, a1 ）q=head。p=headnext。 //有頭 結(jié)點while(p!=head) //循環(huán)單鏈表{ r=pnext。 pnext=q。 //前驅(qū)變后繼 q=p。 p=r。 } //準備處理下一結(jié)點headnext=q。 // 以 an為首q=head。p=headnext。 //有頭 結(jié)點while(p!=head) //循環(huán)單鏈表{ s=q。 q=p。 p=pnext。 qnext=s。} //準備處理下一結(jié)點pnext=q。 // 以 an為首 （要求同學(xué)們根據(jù)下面算法的核心語句，編寫一個完整算法）算法的核心語句 A 或 B