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