線性表chap(已修改)
2025-10-07 19:42 本頁面
【正文】 線性結(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)： 線性表、堆棧、隊(duì)列、串 等 第二章 線性表 本章主要內(nèi)容： ? 線性表的概念（邏輯結(jié)構(gòu)） ? 線性表的順序存儲結(jié)構(gòu)（順序表） ? 線性表的鏈接存儲結(jié)構(gòu)（鏈表） ? 單鏈表 ? 靜態(tài)鏈表 ? 循環(huán)鏈表 ? 雙向鏈表 ? 線性表的應(yīng)用（ Josephus問題） ? 線性表 ：簡稱為表，是零個(gè)或多個(gè)元素的有窮序列， 通?？梢员硎境?k0， k1, … ， kn1（ n≥1）。 ? 表長 ： 線性表中所含元素的個(gè)數(shù) n。 ? 空表 ： 長度為零的線性表 (n=0)。 ? 表目 ： 線性表中的元素（可包含多個(gè)數(shù)據(jù)項(xiàng)，記錄）。 ? 線性表的表示 ： A=(k0， k1, … ， kn1) k0 是第一個(gè)元素， kn1是最后一個(gè)元素 ki是 K i+1的前驅(qū)， K i+1是 Ki的后繼 k0無前驅(qū)， kn1無后繼 線性表的概念 ? 創(chuàng)建空線性表； ? 插入一個(gè)元素； ? 刪除某個(gè)元素； ? 查找某個(gè)特定元素； ? 查找某個(gè)元素的后繼元素； ? 查找某個(gè)元素的前驅(qū)元素； ? 判別一個(gè)線性表是否為空表 。 ? 線性表的基本運(yùn)算 ： 線性表特點(diǎn) ：關(guān)系簡單、操作靈活，其長度可以增長、縮短 存儲結(jié)構(gòu) ： 順序、鏈接存儲 定義： 將線性表中的元素一個(gè)接一個(gè)地存儲在一片地址連續(xù)的存儲單元中。 邏輯關(guān)系表達(dá) ：以元素在計(jì)算機(jī)內(nèi)存中的“ 物理位置相鄰 ”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，如下所示： Locate(ai+1) = Locate(ai) + sizeof(DataType) Locate(ai) = Locate(a0) + sizeof(DataType) * i 只要確定了首地址，線性表中任意數(shù)據(jù)元素都可以隨機(jī)存取。因此，順序表為 “隨機(jī)存取的存儲結(jié)構(gòu)”。 線性表的順序表示和實(shí)現(xiàn) 邏輯地址 數(shù)據(jù)元素 存儲地址 數(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 線性表的順序存儲結(jié)構(gòu)示意圖 順序表的定義 在 C語言 中可以用以下方式定義一個(gè)順序表： define MAXNUM 最多允許的數(shù)據(jù)元素個(gè)數(shù) DataType element[MAXNUM]。 int n。 定義的缺陷 ：沒有反映出 element和ｎ的內(nèi)在聯(lián)系，即沒有指出ｎ是順序表 element本身的屬性。在這個(gè)定義中，ｎ和element完全處于獨(dú)立平等的地位，所以程序中完全可以將ｎ作為一個(gè)自由變量來使用。 為此，引進(jìn) SeqList 在實(shí)際應(yīng)用中，為了使用方便，通常定義一個(gè) struct SeqList類型的指針類型和別名： typedef struct SeqList *PSeqList。 typedef struct SeqList SeqList。 例如 ： PSeqList palist。 palistn :順序表中數(shù)據(jù)元素個(gè)數(shù) palistelement[0], palistelement[1],… 剩余空間 ： n到 MAXNUM1 struct SeqList { DataType element[MAXNUM]。 int n。 /* n MAXNUM */ }。 順序表的基本運(yùn)算 順序表基本運(yùn)算的實(shí)現(xiàn) [p21~26] 參看書 P20~23頁，理解插入、刪除運(yùn)算的實(shí)現(xiàn) 插入 ： （ k0, k1, …, k p, kp+1,…, k n1） n （ k0, k1, …, k p, x, kp+1,…, k n1） n+1 刪除： （ k0, k1, …, k p1, kp, kp+1,…, k n1） n （ k0, k1, …, k p1, kp+1,…, k n1） n1 ? 創(chuàng)建 ? 插入 ? 刪除 ? 查找 ? 取值 ? 判空 12 111 22 8888 333 123 56 99 12 111 22 8888 234 333 123 56 99 12 111 8888 234 333 123 56 99 333前插入 234 刪除 22元素 設(shè) pi是在第
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1