【正文】 。j=i+1。countk。a,int i,int k){ //本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素 if(i1||k0||i+k) return INFEASIBLE。 指出以下算法中的錯誤和低效之處，并將它改寫為一個既正確又高效的算法。 }解：(1) 如果L的長度不小于2，將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。 } void AA(LNode *pa, LNode *pb) { //pa和pb分別指向單循環(huán)鏈表中的兩個結(jié)點(diǎn) BB(pa,pb)。 while(pnext!=q) p=pnext。 } return OK。 Pnext=Q。 P=L。 Lnext) { Q=L。(1) Status A(LinkedList L) { //L是無表頭結(jié)點(diǎn)的單鏈表 if(L amp。(18) free(Q)。(16) Q=Ppriou。(14) Pnextpriou=Ppriou。(12) Pnextpriou=S。(10) Ppriounext=P。(8) Spriou=Ppriou。(6) Spriou=P。(4) Ppriou=S。(2) Ppriou=Pprioupriou。e. 刪除P結(jié)點(diǎn)的語句序列是_______________________。c. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是_______________________。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是_______________________。(14) free(Q)。(12) P=L。(10) Q=P。(8) while(Pnextnext!=Q) P=Pnext。 Q=Qnext。(5) while(P!=NULL) P=Pnext。(3) Pnext=Pnextnext。(1) P=Pnext。 d. 刪除首元結(jié)點(diǎn)的語句序列是____________________。 b. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是____________________。解：a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6) 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。(12) L=S。(10) P=Q。(8) while(Pnext!=Q) P=Pnext。(6) Snext=NULL。(4) Snext=Pnext。(2) Pnext=Pnextnext。d. 在表尾插入S結(jié)點(diǎn)的語句序列是__________________。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是__________________。解： 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。i=3。i) Ins_LinkList(L,i+1,i*2)。 for(i=4。 Pdata=i*21。i++){ Pnext=(LinkList)malloc(sizeof(LNode))。 for(i=1。 L=(LinkList)malloc(sizeof(LNode))。 對以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時不用進(jìn)行特殊處理。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。解：(1) 在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與元素在表中的位置有關(guān)。它可以對空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。首元結(jié)點(diǎn)是指鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點(diǎn)。第1章 線性表 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個元素結(jié)點(diǎn)）。解：頭指針是指向鏈表中第一個結(jié)點(diǎn)的指針。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對鏈表的操作。 填空題。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。解： 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。 P=L。i=4。 P=Pnext。 } Pnext=NULL。i=1。 for(i=1。i++) Del_LinkList(L,i)。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是__________________。c. 在表首插入S結(jié)點(diǎn)的語句序列是__________________。(1) Pnext=S。(3) Pnext=Snext。(5) Snext=L。(7) Q=P。(9) while(Pnext!=NULL) P=Pnext。(11) P=L。(13) L=P。 a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是____________________。 c. 刪除P結(jié)點(diǎn)的語句序列是____________________。 e. 刪除尾元結(jié)點(diǎn)的語句序列是____________________。(2) Pnext=P。(4) P=Pnextnext。(6) while(Qnext!=NULL) { P=Q。 }(7) while(Pnext!=Q) P=Pnext。(9) while(Pnextnext!=NULL) P=Pnext。(11) Q=Pnext。(13) L=Lnext。解：a. (11) (3) (14) b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是_______________________。d. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_______________________。(1) Pnext=Pnextnext。(3) Pnext=S。(5) Snext=P。(7) Snext=Pnext。(9) Ppriounext=Pnext。(11) Pnextpriou=P。(13) Ppriounext=S。(15) Q=Pnext。(17) free(P)。解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 簡述以下算法的功能。amp。 L=Lnext。 while(Pnext) P=Pnext。 Qnext=NULL。 }(2) void BB(LNode *s, LNode *q) { p=s。 pnext =s。 BB(pb,pa)。 (2) 將單循環(huán)鏈表拆成兩個單循環(huán)鏈表。Status DeleteK(SqList amp。//參數(shù)不合法 else {for(count=1。count++){ //刪除第一個元素 for(j=。j) [ji]=[j]。 } return OK。a,int i,int k){ //從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素 //注意i的編號從0開始 int j。 for(j=0。j++) [j+i]=[j+i+k]。 return OK。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。va,ElemType x){ //在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i。 for(i=。i) [i]=[i1]。 ++。} 設(shè)和均為順序表，和分別為和中除去最大共同前綴后的子表。試寫一個比較，大小的算法。A,SqList amp。 k=?:。ik。 if([i][i]) j=1。 if(k) j=1。 return j。解：int LocateElem_L(LinkList amp。 LinkList p=L。amp。 i++。 else return i。解：//返回單鏈表的長度int ListLength_L(LinkList amp。 LinkList p=L。 while(p){ p=pnext。 } return i。試寫一算法將這兩個鏈表連接在一起，假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時間完成連接運(yùn)算。解：void MergeList_L(LinkList amp。hb,LinkList amp。 pa=ha。 while(panextamp。pbnext){ pa=panext。 } if(!panext){ hc=hb。 pbnext=hanext。 while(panext) pa=panext。 }} 已知指針la和lb分別指向兩個無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。試問此算法是否正確？若有錯，請改正之。 p=la。 while(ki){ p=pnext。 } q=p。 k++。 k=1。 k++。 qnext=snext。}解：Status DeleteAndInsertSub(LinkList amp。lb,int i,int j,int len){ LinkList p,q,s,prev=NULL。 if(i0||j0||len0) return INFEASIBLE。