線性表順序表鏈表順序表與鏈表的比較-資料下載頁
2025-10-08 11:38本頁面
【導(dǎo)讀】順序表與鏈表的比較。0）個數(shù)據(jù)元素的有限。ai是表中數(shù)據(jù)元素，n是表長度。除第一個元素外，其他每一個元素。有一個且僅有一個直接前驅(qū)。掃描其后所有元素ajj=i+1,i+2,…集合的并集放在LC中。檢查LA中是否存在bi，若無，則將bi插入到LC中?？梢越鉀Q更復(fù)雜的問題?；具\算的實現(xiàn)完全取決于存儲結(jié)構(gòu)?？衫靡痪S數(shù)組描述存儲結(jié)構(gòu)
【正文】 rearnext=pnext 將循環(huán)鏈表鏈入單鏈表鏈頭 (磁盤動態(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é)點 p結(jié)點 直到 剩一個結(jié)點 雙向鏈表 (Doubly Linked List) ? 雙向鏈表是指在前驅(qū)和后繼方向都能游歷 (遍歷 )的線性鏈表。 ? 雙向鏈表結(jié)點結(jié)構(gòu)： 前驅(qū)方向 ? ? 后繼方向 prior data next 雙向鏈表通常采用帶表頭結(jié)點的循環(huá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é)點的鏈指針指向自己 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)雙向鏈表是否按值對稱。 p q 設(shè)兩個活動指針對稱掃描每個結(jié)點 = 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。 //靜態(tài)鏈表大小 typedef struct node //靜態(tài)鏈表結(jié)點 { 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)。 } 基于空間的比較， ? 存儲分配的方式 ? 順序表的存儲空間是 靜態(tài)分配 的 ? 鏈表的存儲空間是 動態(tài)分配 的 ? 存儲密度 = 結(jié)點數(shù)據(jù)本身所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲總量 ? 順序表的存儲密度 = 1 ? 鏈表的存儲密度 1 167。 順序表與鏈表的比較 基于時間的比較 ? 存取方式 ? 順序表可以 隨機存取 ，也可以 順序存取 ? 鏈表是 順序存取 的 ? 插入 /刪除時移動元素個數(shù) ? 順序表需要移動元素 ? 鏈表不需要移動元素，只需要修改指針 本 章 小 結(jié) 通過指針表示元素之間的邏輯關(guān)系。 線性表 L= （ a 1 a 2 a 3 ? ? ? ? ? ? a n） 邏輯特點： 線性結(jié)構(gòu) 順序表： a 1 a 2 a 3 ? ? ? ? ? ? a n 通過每個元素存儲的相對位置來表示邏輯關(guān)系。 時間效率： Loc(ai)=Loc(a1)+(i1)*c 插入操作后面元素依次（逆序）后移； 刪除操作后面元素依次（正序）前移。 空間效率： 無需另外附加空間表示元素之間的關(guān)系 預(yù)先分配存儲空間（溢出 /浪費） 鏈表： 特點： 頭指針唯一確定單鏈表。 雙向鏈表 L a1 an 特點： ppriornext==p==pnextprior 單鏈表 循環(huán)單鏈表 an L a1 特點： 從任一結(jié)點出發(fā)，可以訪問所有結(jié)點 an L a1 ? 時間效率： 插入、刪除操作只需修改指針 隨機訪問通過掃描鏈表實現(xiàn) 空間效率： 動態(tài)分配空間需要多少分配多少 需要附加指針表示元素之間的關(guān)系
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1