數(shù)據(jù)結(jié)構(gòu)課件(c語(yǔ)言)(2)-資料下載頁(yè)
2024-10-19 19:48本頁(yè)面
【正文】 ? /*建立一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表 */ ?{ ?L=( double_linklist *)malloc(sizeof(double_ linklist))。 ?L–prior=NULL。 ?L–next=NULL。 ?return(L)。 ?} 第 2章 線性表 28 (2) 在雙向鏈表中插入數(shù)據(jù)元素 InsDouItem(*L, item, i): a i1 a iitem第 i 1 個(gè)結(jié)點(diǎn) 第 i 個(gè)結(jié)點(diǎn)t第 2章 線性表 29 (3) 在雙向鏈表中刪除數(shù)據(jù)元素 DeleDouItem(*L, item, i): 第 i 個(gè)結(jié)點(diǎn)第 i 1 個(gè)結(jié)點(diǎn)a ia i1 a i+1第 i + 1 個(gè)結(jié)點(diǎn)... ...p q第 2章 線性表 30 循環(huán)鏈表 循環(huán)鏈表是一種首尾相接的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 在這種存儲(chǔ)結(jié)構(gòu)中 ，每一個(gè)結(jié)點(diǎn)的指針域都記錄著它的下一個(gè)結(jié)點(diǎn)的地址 ， 最后一個(gè)結(jié)點(diǎn)的指針域記錄頭結(jié)點(diǎn)的地址 ， 使鏈表鏈接呈環(huán)狀 ，這樣的鏈表就稱之為單循環(huán)鏈表 ， 如圖 ；與單循環(huán)鏈表類似 ， 將雙向鏈表中尾結(jié)點(diǎn)的后繼指針域記錄鏈表的頭結(jié)點(diǎn)的地址 ， 頭結(jié)點(diǎn)的前驅(qū)指針域記錄尾結(jié)點(diǎn)的地址 ， 即構(gòu)造了雙向循環(huán)鏈表 ， 如圖 。 在循環(huán)鏈表中 ， 從任意一個(gè)結(jié)點(diǎn)出發(fā)均可訪問(wèn)到表中其他結(jié)點(diǎn) 。 第 2章 線性表 31 ...a 2heada 1 a nhead(a)空表 ( b )非空表... a na 2a 1headhead(a)空表 ( b )非空 表第 2章 線性表 32 例 ：已知 L1和 L2分別為兩個(gè)單循環(huán)鏈表的頭指針 。 試遍寫一算法將鏈表 L2連接在鏈表 L1的后面 ， 連接后形成的單循環(huán)鏈表頭指針為 L1。 ? linklist *Combination(linklist *L1, linklist *L2) ? { ? linklist *p, *q。 ? p=L1–next。 ? q=L2–next。 ? while(p–next!=L1) ? p=p–next。 ? while(q–next!=L2) ? q=q–next。 ? p=L2–next。 ? q–next=L1。 ? free(L2)。 ? return(L1)。 ? } ( a )單循環(huán)鏈表 L1a na 1L1a 2 ... b nb 1L2b 2 ......b 2b 1 b na na 1L1a 2 ...( b )單循環(huán)鏈表 L 2( c )鏈表 L2 連接到鏈表 L1 后p q第 2章 線性表 33 ? 靜態(tài)鏈表 ? 以上我們提到的線性表的各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都是根據(jù)需要?jiǎng)討B(tài)分配及釋放其結(jié)點(diǎn)所占的內(nèi)存空間，這種鏈表稱為動(dòng)態(tài)鏈表。還有一種鏈表叫作靜態(tài)鏈表，與動(dòng)態(tài)鏈表的區(qū)別在于靜態(tài)鏈表需要預(yù)先分配一個(gè)較大的空間，以備以后需求。因此，靜態(tài)鏈表可用一維數(shù)組來(lái)實(shí)現(xiàn)，其基本結(jié)構(gòu)為 : ? define MAXSIZE maxlen ? typedef int elemtype。 /*定義新類型，類型名為 elemtype*/ ? typedef struct SeqLinkList ? { ? elemtype data。 /*數(shù)據(jù)域 */ ? int next。 /*下標(biāo)指針域 */ ? }SLList[MAXSIZE]。 第 2章 線性表 34 例 （ A,B,C,D,E,F） 的靜態(tài)鏈表存儲(chǔ)示意圖如下 ，請(qǐng)?jiān)诘?4個(gè)數(shù)據(jù)元素之前插入一新的數(shù)據(jù)元素 G。 第 2章 線性表 35 線性表的存儲(chǔ)方式小結(jié) 線性表的存儲(chǔ)方式主要分兩大類，一類是順序存儲(chǔ)，一類是鏈?zhǔn)酱鎯?chǔ)，其中鏈?zhǔn)酱鎯?chǔ)又包括單鏈表、雙向鏈表、循環(huán)鏈表及靜態(tài)鏈表等多種存儲(chǔ)結(jié)構(gòu)。不同的存儲(chǔ)結(jié)構(gòu)各有其優(yōu)缺點(diǎn)。 順序存儲(chǔ)結(jié)構(gòu)是處理線性表時(shí)較常用的一種存儲(chǔ)方式，它利用數(shù)組來(lái)實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)，數(shù)據(jù)元素的物理存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系相對(duì)應(yīng)，可以方便的實(shí)現(xiàn)對(duì)數(shù)據(jù)的隨機(jī)存取，是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，如對(duì)一個(gè)線性表的主要操作是查詢，則可采用這種存儲(chǔ)方式。 第 2章 線性表 36 但正因?yàn)樗抢脭?shù)組來(lái)實(shí)現(xiàn)存儲(chǔ)，就限定了它需要預(yù)先設(shè)定好線性表中數(shù)據(jù)元素可能達(dá)到的最大個(gè)數(shù)，如果對(duì)線性表操作過(guò)程中，表長(zhǎng)變化較大，則設(shè)定最大表長(zhǎng)就比較困難，也可能造成部分內(nèi)存空間的浪費(fèi)。另外，為了保持順序表中數(shù)據(jù)元素有序性，在插入或刪除數(shù)據(jù)元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)，這樣對(duì)需要頻繁進(jìn)行插入刪除操作的線性表來(lái)說(shuō)，效率太低。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)恰與順序存儲(chǔ)結(jié)構(gòu)互補(bǔ)。組成鏈表的每個(gè)結(jié)點(diǎn)所占空間是動(dòng)態(tài)申請(qǐng)及釋放的，存儲(chǔ)空間的使用更靈活，當(dāng)線性表表長(zhǎng)不確定時(shí)，可采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯順序是由結(jié)點(diǎn)的指針域來(lái)控制的，這樣在插入或刪除數(shù)據(jù)元素時(shí)，只要修改指針域的值即可，不需要移動(dòng)大量數(shù)據(jù)。但當(dāng)每個(gè)結(jié)點(diǎn)數(shù)據(jù)域所占空間不是很大時(shí)，指針域所占空間就會(huì)顯得很大，因此，具體使用哪種存儲(chǔ)結(jié)構(gòu)，還視實(shí)際問(wèn)題而定。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1