DS02_線性表01.ppt

1、第2章 線性表,本章內(nèi)容,2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 2.3.1 單鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加,線性結(jié)構(gòu)的特點(diǎn),在數(shù)據(jù)元素的非空有限集中， （1）存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素； （2）存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素； （3）除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)； （4）除最后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼。,2.1 線性表的類型定義,最常用最簡單 線性表：是n（n0）個具有相同類型的數(shù)據(jù)元素的有限序列。 每個數(shù)據(jù)元素的類型可以是 字

2、符，如字母表(A,B,C,Z) 數(shù)字，如（6,17,28,50,92,188） 記錄，含有大量記錄的線性表又稱文件,線性表的幾個基本概念,若將線性表記為：L（a1, a2 , , ai-1, ai , ai+1, , an) 前驅(qū)和后繼： 表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系，我們稱ai-1是ai的直接前驅(qū)元素， ai是ai-1的直接后繼元素； a1 無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。 線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)n(n=0)。 空表：長度為零（即n=0）的線性表，記為：L=( )。,線性表的ADT定義,ADT List 數(shù)據(jù)對象：D = ai |

3、 ai屬于Elemset, (i=1,2,n, n0) 數(shù)據(jù)關(guān)系：R1 = ai-1,ai|ai-1,ai屬于D,(i=2,3,n) 基本操作： InitList( 等等 /ADT List,InitList(否則返回FALSE。,線性表ADT的基本操作5-1,ListLength(L) 初始條件: 線性表L已經(jīng)存在。 操作結(jié)果: 求長度。返回線性表L中的數(shù)據(jù)元素個數(shù)。 GetElem(L, i, &e) 初始條件: 線性表L已經(jīng)存在，1=i= ListLength(L)。 操作結(jié)果: 用e返回線性表L中第i個數(shù)據(jù)元素的值。 LocateElem(L, e, compare() 初始條件: 線

4、性表L已經(jīng)存在，compare()是數(shù)據(jù)元素判定函數(shù)。 操作結(jié)果: 返回L中第1個與e滿足compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在則返回值為0。,基本操作5-2,PriorElem(L, cur_e, pre_e無意義。 NextElem(L, cur_e, &next_e) 初始條件: 線性表L已經(jīng)存在。 操作結(jié)果:若cur_e是L的數(shù)據(jù)元素, 且不是第最后一個, 則用next_e返回它的后繼, 否則操作失敗, next_e無意義。,基本操作5-3,ListInsert(&L, i, e) 初始條件: 線性表L已經(jīng)存在，1=i= ListLength(L)+1。 操作結(jié)果:

5、 在L的第i個位置之前插入新的數(shù)據(jù)元素e, L的長度加一。 插入前（長度為n） : （a1,a2, ai-1 , ai,an） 插入后（長度為n+1） : （a1,a2, ai-1,e,ai, ,an）,基本操作5-4,ListDelete(&L, i, &e) 初始條件: 線性表L已經(jīng)存在，1=i= ListLength(L)。 操作結(jié)果: 刪除L的第i個數(shù)據(jù)元素,并用e返回其值, L的長度減一。 刪除前（長度為n ） : （ a1,a2, ai-1, ai, ai+1, ,an） 刪除后（長度為n -1 ） : （a1,a2, ai-1, ai+1, ,an） ListTraverse(L

6、, visited() 初始條件: 線性表L已經(jīng)存在 操作結(jié)果: 依次對L的每個數(shù)據(jù)元素調(diào)用visit()函數(shù),一旦visit()失敗，則操作失敗,基本操作5-5,LB,例2-1 線性表La,Lb的合并：La=LaLb,另一種描述：集合求并。 問題描述：假設(shè)兩個集合A和B分別利用兩個線性表LA和LB表示，現(xiàn)要求一個新的集合AAB，即將所有在線性表LB中但不在LA中的數(shù)據(jù)元素插入到LA中。要求利用線性表的基本操作完成算法。 例：La = (2, 5, 7, 9) Lb = (4, 5, 6, 7) 合并結(jié)果:La = (2, 5, 7, 9, 4, 6),LA,算法思想: 1）取Lb中的每個元素

7、。 2）在La中查找是否存在該元素, 若不存在, 則插入La。 算法實現(xiàn)（類C語言）：,void union(List /union，算法2.1,基本操作為for循環(huán)體內(nèi)的GetElem、LocateElem和ListInsert。 假設(shè)GetElem、ListInsert與表長無關(guān)（插入到表尾）。 而LocateElem與表長成正比O(ListLength(La)。 for循環(huán)的循環(huán)次數(shù)為ListLength(Lb) 綜上，時間復(fù)雜度為O(ListLength(La)ListLength(Lb),時間復(fù)雜度分析,例2-2 非遞減有序線性表La,Lb的合并. Lc=LaLb.( 算法2.2),

8、問題描述： 已知線性表La和Lb的元素按值非遞減有序排列。歸并La和Lb得到新的線性表Lc，且Lc的元素仍按值非遞減有序排列。 要求利用線性表的基本操作完成算法。 例： La = (3,5,8,11) Lb = (2,6,8,9,11,15,20) 合并結(jié)果: Lc = (2,3,5,6,8,8,9,11,11,15,20),設(shè)Lc為空表 設(shè)三個位置變量： 2.1 i和j分別指向La和Lb的第一個元素； 2.2 k指向Lc的第一個位置； 比較La的第i個元素和Lb的第j個元素 3.1 若La的第i個元素較小，將其插入到Lc的第k個位置。i+，k+。 3.2 若Lb的第j個元素較小，將其插入到Lc的第k個位置。j+，k+。 4. 若La或Lb中元素均未插入完畢，轉(zhuǎn)到第3步。否則將La中或Lb中的剩余元素插入到Lc中。,算法偽碼,void MergeList(List La, List Lb, List /