數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題課(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡(jiǎn)介】 )。 // 調(diào)用順序表插入函數(shù)}// InsertDecreaseList1寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。解：求單鏈表長(zhǎng)只能用遍歷的方法了，從頭數(shù)到尾。算法如下：int ListLength( LinkList L ){ int len=0。 ListNode *p。p=L。 //設(shè)該表有頭結(jié)點(diǎn)while (pnext) {p=pnext。len++。 }return len。}// ListLength1已知L1和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且已知其長(zhǎng)度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，請(qǐng)分析你的算法的時(shí)間復(fù)雜度。解：算法如下:LinkList Link( LinkList L1 , LinkList L2 ){//將兩個(gè)單鏈表連接在一起ListNode *p, *q。p=L1。 q=L2。while ( pnext ) p=pnext。 //查找終端結(jié)點(diǎn)pnext = qnext 。 //將L2的開始結(jié)點(diǎn)鏈接在L1之后return L1 。}// LinkList Link分析：本算法的主要操作時(shí)間花費(fèi)在查找L1的終端結(jié)點(diǎn)上，與L2的長(zhǎng)度無關(guān)，所以本算的法時(shí)間復(fù)雜度為：m+1=O(m)刪除帶頭結(jié)點(diǎn)單鏈表L中的元素x。解：算法如下:Void delete(LinkList amp。L,ElemType x){ p=Lnext。 pre=L。 while(p) { if(pdata=x) { prenext=pnext。 free(p)。 p=prenext。 } else { pre=p。 p=pnext。 } }}//delete2已知：A=(a1,a2,……,an1,an) B=(b1,b2,……,bn1,bn)均為順序表，試編寫一個(gè)比較A、B大小的算法。解：算法目標(biāo)是分析兩表的大小，所以不應(yīng)破壞原表。表的大小指的是“詞典順序”，而非表的長(zhǎng)度。基本操作為：同步比較兩個(gè)表中相應(yīng)的數(shù)據(jù)元素。假設(shè)：int pare(SqList La,SqList Lb)循環(huán)條件：(i=)amp。amp。( i=)主要操作為：if ([i]==[i]) i++。 else if ([i][i]) return 1。 else return 1。循環(huán)結(jié)束時(shí)可能有三種情況：l (i )amp。amp。( i) return 0。l (i=)amp。amp。(i) return 1。l (i)amp。amp。(i=) return 1。2刪除有序表中所有其值大于minval且小于maxval的數(shù)據(jù)元素。解：while(pamp。amp。pdata=minval) { pre=p。 p=pnext。 }if (p) { while (pamp。amp。pdatamaxval) p=pnext。 q=prenext。 prenext=p。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1