數據結構課后習題答案詳解(c語言版嚴蔚敏)2(已修改)

　

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