線性表順序表鏈表順序表與鏈表的比較(已改無錯(cuò)字)
2022-11-29 11:38:33 本頁面
【正文】 ？ q指向下一個(gè)逆置的結(jié)點(diǎn) L2 L1 ? 例 2：清除單鏈表中多余的重復(fù)元素 （ 1）依次處理每一個(gè)結(jié)點(diǎn) p （ 2）掃描 p之后每一個(gè)結(jié)點(diǎn) q 10 8 5 8 11 ? L p q qdata=pdata ? ≠ = q指向下一個(gè)結(jié)點(diǎn) q=qnext。 刪除結(jié)點(diǎn) q 注：要先確定 q的前驅(qū)結(jié)點(diǎn) r rnext=qnext。 free(q)。 設(shè)置 r總是指向 q的前驅(qū) 例 3 在按值有序的單鏈表中插入一個(gè)新元素 x，使其仍有序。 3 6 11 20 ? L X=9 （ 1）確定插入的位置 （ 2）插入新結(jié)點(diǎn) 生成新結(jié)點(diǎn) p p 9 p=malloc()。 pdata=x。 插入 注：關(guān)鍵是確定 p的前驅(qū)結(jié)點(diǎn) r r P插入 r之后 pnext=q。 rnext=p。 q 例 4 兩個(gè)單鏈表連接。 L1 a1 a2 am1 am ? （ 1）確定 L1的最后一個(gè)結(jié)點(diǎn) p。 （ 2）將 L2的第一個(gè)結(jié)點(diǎn)鏈接在 p之后。 pnext== ? p pnext=L2。 ? a1 a2 an1 an L2 例：一元多項(xiàng)式的加法 分析： 每一項(xiàng)是由其指數(shù)和系所決定， 它們可以作為線性表的每一個(gè)元素。 結(jié)點(diǎn)結(jié)構(gòu)： 系數(shù) 指數(shù) 指針 coef exp next 結(jié)點(diǎn)數(shù)據(jù)類型： typedef struct node { float coef。 int exp。 struct node *next。 } polynode。 F(x)= a0 +a1x +a2x2 + +an1xn1 +anxn g(x)= 8x 9x8 + 22x9 f(x)= 7+3x +9x8 +5x17 7 0 3 1 9 8 5 17 ? f 8 1 9 8 22 9 ? g 方法一： 依次將 g中每個(gè)結(jié)點(diǎn) “ 插入 ” 到 f中。 指數(shù)不同，插入。 基本思想： 從 g中取出當(dāng)前處理的結(jié)點(diǎn) p, 與掃描 f當(dāng)前位置的結(jié)點(diǎn) q比較，三種情況如下： pexp?qexp = 插入結(jié)點(diǎn) p (確定 p的前驅(qū) r） 系數(shù)相加 ≠ 0 = 0 改寫 qcoef,刪除 p 刪除 p和 q (確定 q的前驅(qū) r） 指數(shù)相同，系數(shù)相加， 結(jié)果不等于 0，直接寫入， 結(jié)果等于 0，則刪除。 q后移 p q 11 q p q p r f(x)= 7+11x + 22x9 +5x17 若 g有剩余的結(jié)點(diǎn)？ polyadd(polynode *f, polynode *g) //兩個(gè)多項(xiàng)式相加 f(x)=f(x)+g(x) { p=。r=。q=。 while( ) { if (pexpqexp) //q后移 {} else if (pexpqexp) //插入 p {} else { qcoef=qcoef+pcoef。 if (qcoef= =0) // { } } } if (q!=) {} return() } 方法二： 依次 f和 g中的每個(gè)結(jié)點(diǎn) “ 歸并 ” 到新鏈表中。 7 0 3 1 9 8 5 17 ? f 8 1 9 8 22 9 ? g h ? pa pb 設(shè)活動(dòng)指針 pa和 pb分別掃描 f和 g每個(gè)結(jié)點(diǎn)。 paexp?pbexp = 歸并 pb 系數(shù)相加 ≠ 0 = 0 改寫 pacoef,歸并 pa 刪除 pb 刪除 pa和 pb 歸并 pa 7 0 11 1 22 9 5 17 ? pa pb pa pb pa pb pb pa 剩余部分直接鏈接 ? polyadd(polynode *f, polynode *g) //兩個(gè)多項(xiàng)式相加 h(x)=f(x)+g(x) { pa= ?。 pb= ?。 h=f。 hnext=NULL。 free(g)。pc= ?。 while(?) { if (paexp pbexp) //歸并 pa {? } if (paexppbexp) // 歸并 pb {?} else { pacoef=pacoef+pbcoef。 if (pacoef!=0) //系數(shù)和不等于 0 {? } else是 //系數(shù)和等于 0 {? } } } if (pa!=NULL) ? //f剩余結(jié)點(diǎn) else ? //g剩余結(jié)點(diǎn) return(? )。 } 循環(huán)鏈表 (Circular List) ? 循環(huán)鏈表是單鏈表的變形。 ? 循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的 next 指針不 為NULL，而是指向頭結(jié)點(diǎn)。 an L a2 a1 p 循環(huán)鏈表的特點(diǎn)是： 從任一結(jié)點(diǎn)的出發(fā)都可以訪問到鏈表中所有結(jié)點(diǎn)。 L (空表 ) 查找成功 查找失敗 循環(huán)鏈表的查找 L 31 48 15 57 L 31 48 15 57 查找 15 ? ? ? 查找 25 ? ? ? ? p p 關(guān)鍵是活動(dòng)指針 p移動(dòng)的界限 循環(huán)鏈表的查找算法 bool Locate (LinkList *L, ElemType e ,LinkList *amp。p) //在鏈表中從頭搜索其數(shù)據(jù)值為 e的結(jié)點(diǎn) { p = Lnext。 //活動(dòng)指針 p 指向第一個(gè)結(jié)點(diǎn) while ( p!=NULL amp。amp。 pdata != e ) p = pnext。 if (p==NULL) return false。 else return true。 } 帶尾指針的循環(huán)鏈表 rear 31 48 15 57 如果插入與刪除多在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。 在表頭刪除，時(shí)間復(fù)雜性 O(1) 在表頭插入，相當(dāng)于在表尾插入 在表尾刪除，時(shí)間復(fù)雜性 O(n) 在表尾插入，時(shí)間復(fù)雜性 O(1) 66 p pnext=rearnext rearnext=p rear p
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1