64653administrator(已修改)
2024-10-16 09:46 本頁(yè)面
【正文】 線性表 本講主要內(nèi)容 ?順序表 ?鏈表 順序存儲(chǔ)結(jié)構(gòu) ? 將表中元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲(chǔ)單元中，這種存儲(chǔ)結(jié)構(gòu)是順序結(jié)構(gòu)。 ? 采用順序存儲(chǔ)結(jié)構(gòu)的線性表簡(jiǎn)稱為“順序表”。順序表的存儲(chǔ)特點(diǎn)是：只要確定了起始位置，表中任一元素的地址都通過(guò)下列公式得到： LOC（ ai） =LOC（ a1） +（ i1） *L 1?i ?n 其中， L是元素占用存儲(chǔ)單元的長(zhǎng)度。 存儲(chǔ)示意圖 a1 a2 …. ai …. 元素序號(hào) 內(nèi)存狀態(tài) 存儲(chǔ)地址 1 2 …. i …. LOC(a1) LOC(a1)+1 …. LOC(a1)+(i1) …. 結(jié)構(gòu)的 VC++實(shí)現(xiàn) define MAXLENGTH 100 class SeqList{ int list[MAXLENGTH]。 int last。 }。 見例子 :unit_03中的類 SeqList 算法 11 插入算法 算法步驟 : step1 將第 n至第 i個(gè)元素后移一個(gè)存儲(chǔ)位置 。 step2 將 x插入到 ai1之后 。 step3 表的長(zhǎng)度 +1。 見例子 :unit_03中的類 SeqList::insert 算法 12 刪除算法 算法步驟 : step1 判別指定的位置是否合法； step2 若合法，則將位置 i+1至 n上的元素前 移一個(gè)存儲(chǔ)位置 。 step3 表的長(zhǎng)度 1。 見例子 :unit_03中的類 SeqList::insert 順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn) ? 數(shù)據(jù)連續(xù)存放、隨機(jī)存取 ? 邏輯上相鄰，物理上也相鄰 ? 存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單、易實(shí)現(xiàn) ? 插入、刪除操作不便 ? 存儲(chǔ)密度大，空間利用率高 結(jié)論 ： 順序存儲(chǔ)結(jié)構(gòu)適合于表中元素變動(dòng)較少的情況。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 線性表的順序存儲(chǔ)結(jié)構(gòu)容易實(shí)現(xiàn)，可以隨機(jī)存取表中的任意元素。 ? 順序 表 缺點(diǎn)是： –難于插入、刪除操作； –需要預(yù)先分配空間，不管這些空間能否最大限度地利用。 ? 鏈表存儲(chǔ)結(jié)構(gòu) 在這兩個(gè)方面恰好是優(yōu)點(diǎn)： –容易插入、刪除操作 –不需要預(yù)分空間。 鏈表有關(guān)基本概念 結(jié)點(diǎn)（ NODE） 表中元素的存儲(chǔ)單元。 鏈表存儲(chǔ)結(jié)構(gòu)形式為： 鏈表結(jié)構(gòu)的 C語(yǔ)言描述為： struct node { int data 。 struct node *next 。 }。 typedef struct node NODE； data next 數(shù)據(jù)域 指針域 鏈表（ Link） 由結(jié)點(diǎn)組成的表。 頭指針（ head） 指向鏈表中第 1個(gè)結(jié)點(diǎn)的指針。 頭結(jié)點(diǎn) 為方便操作，在頭指針和頭結(jié)點(diǎn)之間設(shè)置 的結(jié)點(diǎn)。 首元結(jié)點(diǎn) 第一個(gè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1