線性表順序表鏈表順序表與鏈表的比較-資料下載頁
2024-10-17 11:38本頁面
【導(dǎo)讀】順序表與鏈表的比較。0）個(gè)數(shù)據(jù)元素的有限。ai是表中數(shù)據(jù)元素，n是表長(zhǎng)度。除第一個(gè)元素外，其他每一個(gè)元素。有一個(gè)且僅有一個(gè)直接前驅(qū)。掃描其后所有元素ajj=i+1,i+2,…集合的并集放在LC中。檢查L(zhǎng)A中是否存在bi，若無，則將bi插入到LC中?？梢越鉀Q更復(fù)雜的問題。基本運(yùn)算的實(shí)現(xiàn)完全取決于存儲(chǔ)結(jié)構(gòu)。可利用一維數(shù)組描述存儲(chǔ)結(jié)構(gòu)
【正文】 rearnext=pnext 將循環(huán)鏈表鏈入單鏈表鏈頭 (磁盤動(dòng)態(tài)管理） rear 15 20 25 30 10 av 60 65 70 55 磁盤可利用空間 刪除磁盤文件釋放空間 p p=rearnext。 rearnext=av。 av=p。 T(n)=O(1) 6 10 1 2 3 4 5 7 8 9 例 :選猴王 .(若間隔 5) list 1 2 3 4 5 6 9 10 p p p到要?jiǎng)h除的結(jié)點(diǎn) p結(jié)點(diǎn) 直到 剩一個(gè)結(jié)點(diǎn) 雙向鏈表 (Doubly Linked List) ? 雙向鏈表是指在前驅(qū)和后繼方向都能游歷 (遍歷 )的線性鏈表。 ? 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)： 前驅(qū)方向 ? ? 后繼方向 prior data next 雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式。 ? 雙向鏈表的特點(diǎn) pprior pnext p prior next 空表 L L a1 an p == ppriornext == pnextprior 雙向循環(huán)鏈表的定義 typedef int ElemType。 typedef struct Dnode { Elemtype data。 //數(shù)據(jù)元素 struct Dnode * prior, * next。 //指針 } DlinkList。 建立空的雙向循環(huán)鏈表 void InitList( *amp。L) { L = ( DlinkList * ) malloc( sizeof ( DlinkList ) )。 Lprior = Lnext = L。 //表頭結(jié)點(diǎn)的鏈指針指向自己 return。 } 雙向循環(huán)鏈表的操作 L 31 48 15 57 L 31 48 15 57 p q p=pnext q=qprior L a1 a2 an1 an 例：判斷循環(huán)雙向鏈表是否按值對(duì)稱。 p q 設(shè)兩個(gè)活動(dòng)指針對(duì)稱掃描每個(gè)結(jié)點(diǎn) = 0 ≠ 0 pdata==qdata ? p和 q移向下一對(duì) “不對(duì)稱”結(jié)束 “對(duì)稱”的條件：？ 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。 //靜態(tài)鏈表大小 typedef struct node //靜態(tài)鏈表結(jié)點(diǎn) { elemtype data。 int next。 } snode。 typedef struct //靜態(tài)鏈表 { snode nodes[MaxSize]。 int list,av。 //當(dāng)前可分配空間首地址 } slinkList。 將鏈表空間初始化 slinklist *InitList ( ) { slinkList SL 。 = 0。 = 1。 //當(dāng)前可分配空間 從 1 開始 for ( i = 1。 i MaxSize。 i++ ) [i].next = i+1。 //構(gòu)成空閑鏈接表 [MaxSize1].next = 0。 //鏈表收尾 return(amp。SL)。 } 基于空間的比較， ? 存儲(chǔ)分配的方式 ? 順序表的存儲(chǔ)空間是 靜態(tài)分配 的 ? 鏈表的存儲(chǔ)空間是 動(dòng)態(tài)分配 的 ? 存儲(chǔ)密度 = 結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量 ? 順序表的存儲(chǔ)密度 = 1 ? 鏈表的存儲(chǔ)密度 1 167。 順序表與鏈表的比較 基于時(shí)間的比較 ? 存取方式 ? 順序表可以 隨機(jī)存取 ，也可以 順序存取 ? 鏈表是 順序存取 的 ? 插入 /刪除時(shí)移動(dòng)元素個(gè)數(shù) ? 順序表需要移動(dòng)元素 ? 鏈表不需要移動(dòng)元素，只需要修改指針 本 章 小 結(jié) 通過指針表示元素之間的邏輯關(guān)系。 線性表 L= （ a 1 a 2 a 3 ? ? ? ? ? ? a n） 邏輯特點(diǎn)： 線性結(jié)構(gòu) 順序表： a 1 a 2 a 3 ? ? ? ? ? ? a n 通過每個(gè)元素存儲(chǔ)的相對(duì)位置來表示邏輯關(guān)系。 時(shí)間效率： Loc(ai)=Loc(a1)+(i1)*c 插入操作后面元素依次（逆序）后移； 刪除操作后面元素依次（正序）前移。 空間效率： 無需另外附加空間表示元素之間的關(guān)系 預(yù)先分配存儲(chǔ)空間（溢出 /浪費(fèi)） 鏈表： 特點(diǎn)： 頭指針唯一確定單鏈表。 雙向鏈表 L a1 an 特點(diǎn)： ppriornext==p==pnextprior 單鏈表 循環(huán)單鏈表 an L a1 特點(diǎn)： 從任一結(jié)點(diǎn)出發(fā)，可以訪問所有結(jié)點(diǎn) an L a1 ? 時(shí)間效率： 插入、刪除操作只需修改指針 隨機(jī)訪問通過掃描鏈表實(shí)現(xiàn) 空間效率： 動(dòng)態(tài)分配空間需要多少分配多少 需要附加指針表示元素之間的關(guān)系
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1