線性表順序表鏈表順序表與鏈表的比較(參考版)
2024-10-21 11:38本頁面
【正文】 空間效率： 無需另外附加空間表示元素之間的關(guān)系 預(yù)先分配存儲空間（溢出 /浪費(fèi)） 鏈表： 特點(diǎn)： 頭指針唯一確定單鏈表。 線性表 L= （ a 1 a 2 a 3 ? ? ? ? ? ? a n） 邏輯特點(diǎn)： 線性結(jié)構(gòu) 順序表： a 1 a 2 a 3 ? ? ? ? ? ? a n 通過每個元素存儲的相對位置來表示邏輯關(guān)系。 } 基于空間的比較， ? 存儲分配的方式 ? 順序表的存儲空間是 靜態(tài)分配 的 ? 鏈表的存儲空間是 動態(tài)分配 的 ? 存儲密度 = 結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲總量 ? 順序表的存儲密度 = 1 ? 鏈表的存儲密度 1 167。 //鏈表收尾 return(amp。 i++ ) [i].next = i+1。 //當(dāng)前可分配空間 從 1 開始 for ( i = 1。 = 0。 //當(dāng)前可分配空間首地址 } slinkList。 typedef struct //靜態(tài)鏈表 { snode nodes[MaxSize]。 int next。 p q 設(shè)兩個活動指針對稱掃描每個結(jié)點(diǎn) = 0 ≠ 0 pdata==qdata ? p和 q移向下一對 “不對稱”結(jié)束 “對稱”的條件：？ L 31 48 15 57 雙向鏈表的插入 55 19 p q qnext=pnext qprior=p pnextprior=q pnext=q q插入 p之后 qnext=p qprior=pprior ppriornext=q pprior=q q插入 p之后 q pnext pprior head 31 48 15 57 雙向鏈表的刪除 p pprior pnext ppriornext=pnext pnextprior=pprior free(p) 靜 態(tài) 鏈 表 1 2 3 4 5 6 7 8 9 10 11 12 data next 1 2 3 4 5 6 7 8 9 10 11 12 data next 1 2 3 4 5 6 7 8 9 10 11 12 data next a1 a2 a3 a4 a5 a6 2 3 4 5 6 0 list av 8 9 10 11 12 0 a1 a3 a5 a6 8 6 7 5 12 0 list av 4 3 10 11 2 0 a4 a2 a7 a1 a2 a3 a4 a5 a6 2 3 7 5 6 0 list av 4 9 10 11 12 0 x X插入 a3和 a4之間 8av 0y X插入 a6之后 3 9 av 刪除 2 82av 6多次插入刪除之后 靜態(tài)鏈表定義 const int MaxSize = 100。 //表頭結(jié)點(diǎn)的鏈指針指向自己 return。L) { L = ( DlinkList * ) malloc( sizeof ( DlinkList ) )。 //指針 } DlinkList。 typedef struct Dnode { Elemtype data。 ? 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)： 前驅(qū)方向 ? ? 后繼方向 prior data next 雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式。 av=p。 在表頭刪除，時間復(fù)雜性 O(1) 在表頭插入，相當(dāng)于在表尾插入 在表尾刪除，時間復(fù)雜性 O(n) 在表尾插入，時間復(fù)雜性 O(1) 66 p pnext=rearnext rearnext=p rear p rearnext=pnext 將循環(huán)鏈表鏈入單鏈表鏈頭 (磁盤動態(tài)管理） rear 15 20 25 30 10 av 60 65 70 55 磁盤可利用空間 刪除磁盤文件釋放空間 p p=rearnext。 else return true。 pdata != e ) p = pnext。 //活動指針 p 指向第一個結(jié)點(diǎn) while ( p!=NULL amp。 L (空表 ) 查找成功 查找失敗 循環(huán)鏈表的查找 L 31 48 15 57 L 31 48 15 57 查找 15 ? ? ? 查找 25 ? ? ? ? p p 關(guān)鍵是活動指針 p移動的界限 循環(huán)鏈表的查找算法 bool Locate (LinkList *L, ElemType e ,LinkList *amp。 ? 循環(huán)鏈表最后一個結(jié)點(diǎn)的 next 指針不 為NULL，而是指向頭結(jié)點(diǎn)。 if (pacoef!=0) //系數(shù)和不等于 0 {? } else是 //系數(shù)和等于 0 {? } } } if (pa!=NULL) ? //f剩余結(jié)點(diǎn) else ? //g剩余結(jié)點(diǎn) return(? )。pc= ?。 hnext=NULL。 pb= ?。 7 0 3 1 9 8 5 17 ? f 8 1 9 8 22 9 ? g h ? pa pb 設(shè)活動指針 pa和 pb分別掃描 f和 g每個結(jié)點(diǎn)。 while( ) { if (pexpqexp) //q后移 {} else if (pexpqexp) //插入 p {} else { qcoef=qcoef+pcoef。r=。 基本思想： 從 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，則刪除。 F(x)= a0 +a1x +a2x2 +
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1