[ppt模板]數(shù)據(jù)結構線性表試題(編輯修改稿)
2025-02-11 06:15 本頁面
【文章內(nèi)容簡介】 pnext。 /*p和q指向相鄰的兩個元素*/ while(pnext) { if(pdata!=qdata) /*若相鄰兩元素不相等時，p和q都向后推一步*/ { p=pnext。 q=pnext。 } else { while(qdata==pdata) /*當相鄰元素相等時刪除多余元素*/ { r=q。 q=qnext。 free(r)。 } pnext=q。p=q。q=pnext。 }/*else*/ }/*while*/}/*Delete_Equal */7．試設計一個算法，對帶頭結點的單鏈表實現(xiàn)就地逆置。 【算法分析】 1）空表或長度為1的表，不做任何處理； 2）表長大于2時，做如下處理： ①首先將整個鏈表一分為二，即從鏈表的第一元素結點處斷開； ②逐個地把剩余鏈表的當前元素q插入到鏈表的頭部。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return。 p=Lnext。 q=pnext。 s=qnext。 pnext=NULL。 /*從鏈表的第一元素結點處斷開*/ while(snext) {qnext=p。p=q。 q=s。s=snext。 /*把L的元素逐個插入新表表頭*/ } qnext=p?！ next=q。Lnext=s。}/*LinkList_reverse*/8．設線性表A=（a1，a2，…，am） 和 B=（b1，b2，…，bn），試設計一個按下列規(guī)則合并A，B為線性表C的算法，即使得 C=（a1，b1，…，am，bm，bm+1 ，…，bn ）當 m≤n時； 或者 C=（a1，b1，…，an，bn，an+1 ，…，am ）當m＞n時。 線性表A，B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。 【算法分析】 1）初始化指針p指向鏈表A的當前元素，指針q指向鏈表B的當前元素； 2）當鏈表A和B均為結束時，做如下處理： ①將B的元素插入 ②若A非空，將A的元素插入 ③指針p和q同時后移 【算法源代碼】 void merge1(LinkList A,LinkList B,LinkList *C) { p=Anext?！ =Bnext?！ ?C=A。 while(pamp。amp。q) { s=pnext?！next=q。 /*將B的元素插入*/ if (s) { t=qnext。 qnext=s。 /*若A非空，將A的元素插入*/ } p=s?！ =t。 /*指針p和q同時后移*/ }/*while*/}/*merge1 */9．假設有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結構，請設計一個算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即 A表和B表）的結點空間構造C表。 【算法分析】按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素。 【算法源代碼】 void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre。 pa=Anext。pb=Bnext。 /*pa和pb分別指向A和B的當前元素*/ pre=NULL。 while(pa||pb) { if(padatapbdata||!pb) /*將A的元素插入新表*/ { pc=pa。q=panext。panext=pre。pa=q。 } else /*將B的元素插入新表*/ { pc=pb。q=pbnext。pbnext=pre。pb=q。 } pre=pc。 } *C=A。 Anext=pc。 /*構造新表頭*/}/*reverse_merge*/10．已知A，B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。 【算法分析】先從B和C中找出共有元素，記為same，再在A中從當前位置開始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳過，到大于same時就再找下一個same。 【算法源代碼】 void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) { i=0。 j=0。 k=0。 m=0。 /*i指示A中元素原來的位置，m為移動后的位置*/ while(i(*A).lengthamp。amp。jamp。amp。 k) { if ([j][k]) j++。 else if([j][k]) k++。 else{ same=[j]。 /*找到了相同元素same*/
試題試卷相關推薦
鄂ICP備17016276號-1