數據結構習題集答案(c語言版嚴蔚敏)(編輯修改稿)

　

【文章內容簡介】 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。haLinkList amp。hbLinkList amp。hc){ LinkList papb。 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 laLinkedList lbint iint jint 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。laLinkList amp。lbint iint jint len){ LinkList pqsprev=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。 } else{ s=lb。 k=1。 while(samp。amp。kj1){ s=snext。 k++。 } if(!s)return INFEASIBLE。 qnext=snext。 snext=p。 //完成插入 } return OK。} 試寫一算法在無頭結點的動態單鏈表上實現線性表操作Insert(Lib)并和在帶頭結點的動態單鏈表上實現相同操作的算法進行比較實現線性表操作Delete(Li)并和在帶頭結點的動態單鏈表上實現相同操作的算法進行比較 已知線性表中的元素以值遞增有序排列并以單鏈表作存儲結構試寫一高效的算法刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素）同時釋放被刪結點空間并分析你的算法的時間復雜度（注意mink和maxk是給定的兩個參變量它們的值可以和表中的元素相同也可以不同）　　解：Status ListDelete_L(LinkList amp。LElemType minkElemType maxk){ LinkList pqprev=NULL。 if(minkmaxk)return ERROR。 p=L。 prev=p。 p=pnext。 while(pamp。amp。pdatamaxk){ if(pdata=mink){ prev=p。 p=pnext。 } else{ prevnext=pnext。 q=p。 p=pnext。 free(q)。 } } return OK。} 試寫一高效的算法刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同）同時釋放被刪結點空間并分析你的算法的時間復雜度　　解：void ListDelete_LSameNode(LinkList amp。L){ LinkList pqprev。 p=L。 prev=p。 p=pnext。 while(p){ prev=p。 p=pnext。 if(pamp。amp。pdata==prevdata){ prevnext=pnext。 q=p。 p=pnext。 free(q)。 } }} 試寫一算法實現順序表的就地逆置即利用原表的存儲空間將線性表逆置為　　解：// 順序表的逆置Status ListOppose_Sq(SqList amp。L){ int i。 ElemType x。 for(i=0。i。i++){ x=[i]。 [i]=[]。 []=x。 } return OK。} 試寫一算法對單鏈表實現就地逆置　　解：// 帶頭結點的單鏈表的逆置Status ListOppose_L(LinkList amp。L){ LinkList pq。 p=L。 p=pnext。 Lnext=NULL。 while(p){ q=p。 p=pnext。 qnext=Lnext。 Lnext=q。 } return OK。} 設線性表試寫一個按下列規則合并AB為線性表C的算法即使得 當時； 當時線性表AB和C均以單鏈表作存儲結構且C表利用A表和B表中的結點空間構成注意：單鏈表的長度值m和n均未顯式存儲　　解：// 將合并后的結果放在C表中并刪除B表Status ListMerge_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqb。 pa=Anext。 pb=Bnext。 C=A。 while(paamp。amp。pb){ qa=pa。 qb=pb。 pa=panext。 pb=pbnext。 qbnext=qanext。 qanext=qb。 } if(!pa)qbnext=pb。 pb=B。 free(pb)。 return OK。} 假設有兩個按元素值遞增有序排列的線性表A和B均以單鏈表作存儲結構請編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序允許表中含有值相同的元素）排列的線性表C并要求利用原表（即A表和B表）的結點空間構造C表　　解：// 將合并逆置后的結果放在C表中并刪除B表Status ListMergeOppose_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqb。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅指針 qb=pb。 // 保存pb的前驅指針 pa=panext。 pb=pbnext。 Anext=NULL。 C=A。 while(paamp。amp。pb){ if(padatapbdata){ qa=pa。 pa=panext。 qanext=Anext。 //將當前最小結點插入A表表頭 Anext=qa。 } else{ qb=pb。 pb=pbnext。 qbnext=Anext。 //將當前最小結點插入A表表頭 Anext=qb。 } } while(pa){ qa=pa。 pa=panext。 qanext=Anext。 Anext=qa。 } while(pb){ qb=pb。 pb=pbnext。 qbnext=Anext。 Anext=qb。 } pb=B。 free(pb)。 return OK。} 假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元素值各不相同）現要求另辟空間構成一個線性表C其元素為A和B中元素的交集且表C中的元素有依值遞增有序排列試對順序表編寫求C的算法　　解：// 將A、B求交后的結果放在C表中Status ListCross_Sq(SqList amp。ASqList amp。BSqList amp。C){ int i=0j=0k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ ListInsert_Sq(Ck[i])。 i++。 k++。 } } return OK。} 試對單鏈表編寫求C的算法　　解：// 將A、B求交后的結果放在C表中并刪除B表Status ListCross_L(LinkList amp。ALinkList amp。BLinkList amp。C){ LinkList papbqaqbpt。 pa=A。 pb=B。 qa=pa。 // 保存pa的前驅指針 qb=pb。 // 保存pb的前驅指針 pa=panext。 pb=pbnext。 C=A。 while(paamp。amp。pb){ if(padatapbdata){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } else if(padatapbdata){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } else{ qa=pa。 pa=panext。 } } while(pa){ pt=pa。 pa=panext。 qanext=pa。 free(pt)。 } while(pb){ pt=pb。 pb=pbnext。 qbnext=pb。 free(pt)。 } pb=B。 free(pb)。 return OK。} 對順序表重新編寫求得表C的算法 (1) 假設在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同； (2) 利用A表空間存放表C　　解：(1)// A、B求交然后刪除相同元素將結果放在C表中Status ListCrossDelSame_Sq(SqList amp。ASqList amp。BSqList amp。C){ int i=0j=0k=0。 while(i amp。amp。 j){ if([i][j]) i++。 else if([i][j]) j++。 else{ if(==0){ ListInsert_Sq(Ck[i])。 k++。 } else if([]!=[i]){ ListInsert_Sq(Ck[i])。 k++。 } i++。 } } return OK。}(2)// A、B