數(shù)據結構第2章典型例題解析-資料下載頁
2025-03-25 03:01本頁面
【正文】 跳過，繼續(xù)后面的比較?！舅惴ā縇inkNode *inter(LinkList A,B){ LNode *q,*p,*r,*s,*C。 C=new LNode。 r=C。 p=A。 q=B。 while (p amp。amp。 q ) if (pdataqdata) p=pnext。 else if (pdata==qdata){ s=new LNode。 sdata=pdata。 rnext=s。 r=s。 p=pnext。 q=qnext。 } else q=qnext。 rnext=NULL。 r=Cnext。 delete C。 return r。}4．單鏈表L是一個遞減有序表，試編寫一個高效算法，刪除表中值大于min且小于max的結點（若表中有這樣的結點），同時釋放被刪結點的空間，這里min 和max 是兩個給定的參數(shù)。并分析算法的時間復雜度?！痉治觥坑捎趩捂湵鞮是一個遞減有序表，即由大到小有序，故可從表頭開始查找第一個比max小的結點，記住其位置，再接著向后查找第一個不大于min的結點，然后將它們之間的結點刪除。【算法】LinkList delete(LinkList L,int min,int max){ //設L為帶頭結點的循環(huán)鏈表 LNode *p,*q,*s,*k。 if(Lnext){ p=Lnext。 s=L。 while (pdata=max){ s=p。 p=pnext。 } //p指向第一個值小于max的結點,s指向其前驅 while (p!=L amp。amp。 pdatamin) //p繼續(xù)下移 p=pnext。 //p 指向第一個值不大于min的結點 while (snext!=p){ //刪除*s 的后繼至* p的前驅之間的結點 k=snext。 snext=knext。 delete k。 } }}前兩個while循環(huán)和起來最多循環(huán)n次，第三個while循環(huán)最多循環(huán)n次，即刪除n個結點，故算法的時間復雜度為O(n)。編寫一個算法，將一個頭結點指針為a的單鏈表A分解為兩個單鏈表A和B，其頭結點指針分別為a和b，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素（頭結點緊接的下一個元素為第1個元素），而B鏈表中含有原鏈表A中序號為偶數(shù)的元素，且保持原來的相對順序。【分析】此題用一個while循環(huán)來處理，一次循環(huán)處理兩個結點：將前一個仍留在a中，后一個從a中刪除，鏈接到b的尾部，直到整個鏈表處理完畢?！舅惴ā縄nt split(LNode *a,LNode *b)//若成功分解，返回1，否則，返回0//a為指向單鏈表a的指針，b為指向單鏈表B的指針{ LNode *cur_a,cur_b,temp。 cur_a=anext。 cur_b=Init_List()。 if(cur_b==NULL) { Return 0。 } *b=cur_b。 while(cur_a!=NULLamp。amp。(temp=cur_a224。next)!=NULL){ cur_a224。next=temp224。next。 cur_a=cur_a224。next。 cur_b224。next=temp。 cur_b=cur_b224。next。 } cur_b224。next=NULL。 return 1。 }
研究報告相關推薦
鄂ICP備17016276號-1