線性表chap-全文預(yù)覽
【正文】 link。 }DoubleNode, *PDoubleNode。 pclist … a1 a2 an head 最后結(jié)點(diǎn) ： pclisthead 第一個(gè)結(jié)點(diǎn) ： pclistheadlink 循環(huán)條件 ： p = pclisthead 空表判斷 ： phead = NULL 思考問(wèn)題 ： 如何將一個(gè)單循環(huán)鏈表（無(wú)頭結(jié)點(diǎn)，且 pclisthead指向第一個(gè)結(jié)點(diǎn)）倒置？ (a1, a2, …, a n) = (an, an1, …, a 1) 雙向鏈表和雙向循環(huán)鏈表 單鏈表缺點(diǎn)： 找后繼容易 ， 找前驅(qū)必須從頭開(kāi)始查找 。 } 循環(huán)鏈表 無(wú)頭結(jié)點(diǎn)： 循環(huán)條件 ： plink = pclisthead 表空條件 ： pclisthead = NULL 帶頭結(jié)點(diǎn)： 循環(huán)條件 ： plink = pclisthead 表空條件 ： pclistheadlink = NULL pclist … info a1 an head 頭結(jié)點(diǎn) 建立： 將最后一個(gè)結(jié)點(diǎn)的指針項(xiàng)指向第一個(gè)結(jié)點(diǎn)（或頭結(jié)點(diǎn)），構(gòu)成一個(gè)循環(huán)鏈。 while (i amp。 return i。 i++) list[i].cursor = i + 1。 /* 釋放 ‘ k’指向的空間，將其連接到備用鏈中 */ void Free(SLinkList list, int k)。如第 i個(gè)分量表示鏈表的第 k個(gè)結(jié)點(diǎn)，則 s[i].cursor指示第 k+1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。 靜態(tài)鏈表 define MaxSize 1000 /* 供分配空間的大小 */ typedef struct { DataType data。 7. 單鏈表與順序表的選擇 游標(biāo) 代替鏈表中的指針，插入、刪除時(shí)僅需要修改游標(biāo)項(xiàng)完成。 (2) 在單鏈表里進(jìn)行插入、刪除運(yùn)算比在順序表里容易得多；順序表通過(guò)數(shù)據(jù)元素移動(dòng)完成，而鏈表通過(guò)修改指針完成。 (2) 注 : (1),(2)順序不能反 a b x s p (1) (2) a b p c 單鏈表刪除結(jié)點(diǎn)時(shí)的情況 plink = plinklink。 /* 無(wú)頭結(jié)點(diǎn) ： 指向第一個(gè)結(jié)點(diǎn) */ /* 帶頭結(jié)點(diǎn) ： 指向頭結(jié)點(diǎn) */ …… /* 有關(guān)單鏈表的其它信息 */ }LinkList, *PLinkList。 單鏈表 數(shù)據(jù)域存放數(shù)據(jù)元素信息 指針域指向后繼結(jié)點(diǎn) 最后結(jié)點(diǎn)無(wú)后繼，因此其指針域?yàn)榭? 線性鏈表的邏輯狀態(tài) （不帶頭結(jié)點(diǎn)） Li Zhao Qian Sun Zhou Wu Zheng Wang ^ H a1 an ^ a2 ... H 頭結(jié)點(diǎn) 帶頭結(jié)點(diǎn)的線性鏈表 2. 線性鏈表的圖示 （數(shù)據(jù)元素的邏輯順序，不是存儲(chǔ)位置） typedef struct Node /* 單鏈表結(jié)點(diǎn)結(jié)構(gòu) */ { DataType info。 缺點(diǎn) ：插入、刪除數(shù)據(jù)元素需要大量的數(shù)據(jù)元素移動(dòng)，時(shí)間 效率低。 int n。 為此，引進(jìn) SeqList 在實(shí)際應(yīng)用中，為了使用方便，通常定義一個(gè) struct SeqList類型的指針類型和別名： typedef struct SeqList *PSeqList。 線性表的順序表示和實(shí)現(xiàn) 邏輯地址 數(shù)據(jù)元素 存儲(chǔ)地址 數(shù)據(jù)元素 0 k0 Loc(k0) k0 1 k1 Loc(k0)+c k1 … … … … i ki Loc(k0)+i*c ki … … n1 kn1 Loc(k0)+(n1)*c kn1 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 順序表的定義 在 C語(yǔ)言 中可以用以下方式定義一個(gè)順序表： define MAXNUM 最多允許的數(shù)據(jù)元素個(gè)數(shù) DataType element[MAXNUM]。 ? 線性表的表示 ： A=(k0， k1, … ， kn1) k0 是第一個(gè)元素， kn1是最后一個(gè)元素 ki是 K i+1的前驅(qū)， K i+1是 Ki的后繼 k0無(wú)前驅(qū)， kn1無(wú)后繼 線性表的概念 ? 創(chuàng)建空線性表； ? 插入一個(gè)元素； ? 刪除某個(gè)元素； ? 查找某個(gè)特定元素； ? 查找某個(gè)元素的后繼元素； ? 查找某個(gè)元素的前驅(qū)元素； ? 判別一個(gè)線性表是否為空表 。線性結(jié)構(gòu)的特點(diǎn) ： 在數(shù)據(jù)元素的非空有限集中， （ 1） 存在唯一的一個(gè)被稱為“ 第一個(gè) ”的數(shù)據(jù)元素； （ 2）存在唯一的一個(gè)被稱為“ 最后一個(gè) ”的數(shù)據(jù)元素； （ 3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè) “ 直接前驅(qū) ” ； （ 4）除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè) “ 直接后繼 ” ； 常用的線性結(jié)構(gòu)： 線性表、堆棧、
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1