[計算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)課件吳偉民編著(已修改)
2025-10-26 04:12 本頁面
【正文】 第二章 線性表 線性結(jié)構(gòu) 特點 ：在數(shù)據(jù)元素的非空有限集中 ?存在 唯一 的一個被稱作“ 第一個 ”的數(shù)據(jù)元素 ?存在 唯一 的一個被稱作“ 最后一個 ”的數(shù)據(jù)元素 ?除第一個外，集合中的每個數(shù)據(jù)元素均 只有一個前驅(qū) ?除最后一個外，集合中的每個數(shù)據(jù)元素均 只有一個后繼 第二章 線性表 教學(xué)目的 ： （ 1） 了解線性表的邏輯結(jié)構(gòu)特性 ， 以及線性表的兩種存儲實現(xiàn)方式； （ 2） 熟練掌握順序表的定義與實現(xiàn) ， 包括查找 、 插入 、 刪除算法的實現(xiàn)； （ 3） 熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表操作的基本方法 ， 能在實際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu) 。 教學(xué)的 重點和難點 ：鏈表。 ? 線性表的定義及運算 ： 是由 n(n=0)個數(shù)據(jù)元素（結(jié)點）a1,a2,a3, ……a n組成的有限序列。 其中： n為數(shù)據(jù)元素的個數(shù)，也稱為 表的長度 。 當(dāng) n=0 時，稱為 空表 。 非空的線性表 (n0) 記作： （ a1,a2,a3, ……a n） ： （ 1）有且僅有一個開始結(jié)點 a1(無直接前趨）； （ 2）有且僅有一個終端結(jié)點 an(無直接后繼）； （ 3）其余的結(jié)點 ai 都有且僅有一個直接前趨 ai1和一個直接后繼ai+1。 （ 4） ai是屬于某個數(shù)據(jù)對象的元素，它可以是一個數(shù)字、一個字母或一個記錄。 （ 1）線性表中的所有數(shù)據(jù)元素的數(shù)據(jù)類型是一致的。 （ 2）數(shù)據(jù)元素 在線性表中的位置只取決于它的序號。 （ 3）結(jié)點間的邏輯關(guān)系是線性的。 a 1 a 2 …… a n 圖 2 1 線性表邏輯結(jié)構(gòu)示意圖 線性表的形式化定義為： linear_list=(D,R) 其中 D={ai ∣ 1≤i≤n,n≥0,ai∈ elemtype} R={ai,ai+1 ∣ 1≤i≤n1} 例 26個英文字母組成的字母表 （ A， B， C、 … 、 Z） 例 某校從 1978年到 1983年各種型號的計算機(jī)擁有量的變化情況。 （ 6， 17， 28， 50， 92， 188） 例 學(xué)生健康情況登記表如下： 姓 名 學(xué) 號 性 別 年齡 健康情況 王小林 790631 男 18 健康 陳 紅 790632 女 20 一般 劉建平 790633 男 21 健康 張立立 790634 男 17 神經(jīng)衰弱 …….. …….. ……. ……. ……. 抽象數(shù)據(jù)類型的定義為： P19 4. 線性表的運算 數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而具體的實現(xiàn)則在存儲結(jié)構(gòu)上進(jìn)行。 （ 1）存取 （ 2）插入 （ 3）刪除 （ 4）查找 （ 5）合并 （ 6）分解 （ 7）排序 （ 8）求線性表的長度 基本運算 線性表的順序存儲結(jié)構(gòu)（順序表） ： 用一組連續(xù)的存儲單元（地址連續(xù)）依次存放線性表的各個數(shù)據(jù)元素。 即：在順序表中邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位置也是相鄰的 。 若一個數(shù)據(jù)元素占 L個存儲單元，則其存儲方式參見下圖。 a1 a2 …… ai ai+1 …… an 地址 內(nèi)容 元素在表中的位序 1 i 2 n 空閑區(qū) i+1 L b=LOC(a1) b + L b +(i1)L b +(n1)L b +(max1)L 從圖中可以看出 , LOC（ a i+1） =LOC(a i)+l 一般地 ,有 第 i個數(shù)據(jù)元素的存儲位置為： LOC（ a i） =LOC(a 1)+(i1)*l LOC(a 1)稱為 基地址 （第一個數(shù)據(jù)元素的存儲位置）。 顯然，數(shù)據(jù)元素在順序表中位置取決于數(shù)據(jù)元素在線性表中的位置。 順序表的特點 是：邏輯位置相鄰，其物理位置也相鄰。 一個一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個數(shù)組元素用相鄰的 ５個字節(jié) 存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ [０ ]的第一個字節(jié)的地址是 ９８ ，則Ｍ [３ ]的第一個字節(jié)的地址是 113 例 1 因此： LOC( M[3] ) = 98 + 5 (30) =113 解： 地址計算通式為： LOC(ai) = LOC
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1