1、整理課件第二章第二章線性表線性表整理課件線性結構的線性結構的基本特征基本特征為為: :1集合中必存在唯一的一個集合中必存在唯一的一個“第一元第一元素素”；2集合中必存在唯一的一個集合中必存在唯一的一個 “最后元最后元素素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后繼唯一的后繼；4除第一元素之外，均有除第一元素之外，均有 唯一的前驅唯一的前驅。 線性結構線性結構是一個數據元素的是一個數據元素的有序有序( (次序次序) )集集線性表線性表是一種最簡單的線性結構線性結構整理課件2.1 線性表的類型定義線性表的類型定義2.3 線性表的鏈式表示和實現線性表的鏈式表示和實現2.4 一元多項式

2、的表示一元多項式的表示2.2 線性表的順序表示和實現線性表的順序表示和實現整理課件2.1 線性表的類型定義線性表的類型定義一、線性表的邏輯結構一、線性表的邏輯結構 線性表是線性表是n個數據元素個數據元素a1,a2,an的有限序列，的有限序列，記為記為 (a1,a2,ai,an)其中，其中，ai可以是一個數、一個字母、一串字符、一可以是一個數、一個字母、一串字符、一頁書，甚至更復雜的信息頁書，甚至更復雜的信息例如：英文字母表（例如：英文字母表（A,B,C,Z） 在校生人數變化情況表在校生人數變化情況表 （800，1500，2400，4100，20000） 整理課件在稍復雜的線性表中，一個數據元素

3、可以由若干個數據在稍復雜的線性表中，一個數據元素可以由若干個數據項組成，如職工花名冊表項組成，如職工花名冊表編號姓名性別年齡月收入1王小林男5122002陳紅女4718003孫麗麗女3517604趙京男271650在這種情況下，通常把數據元素稱為記錄，把含有大量在這種情況下，通常把數據元素稱為記錄，把含有大量記錄的線性表稱為文件。記錄的線性表稱為文件。 綜上所述：綜上所述：線性表中的數據元素可以是各種各樣的，線性表中的數據元素可以是各種各樣的，但同一線性表中的元素必定具有相同的特性但同一線性表中的元素必定具有相同的特性,即屬同一數即屬同一數據對象，相鄰數據元素之間存在著序偶關系。據對象，相鄰數

4、據元素之間存在著序偶關系。整理課件若將線性表記為若將線性表記為 （a1,ai-1,ai,ai+1,an），則），則 ai-1是是ai的的直接前趨元素直接前趨元素； ai+1是是ai的的直接后繼元素直接后繼元素； 當當i=1,2,n-1時，時，ai有且僅有一個直接后繼；有且僅有一個直接后繼； 當當i=2,3，,n時，時，ai有且僅有一個直接前趨；有且僅有一個直接前趨；即：第一個元素無前趨；最后一個元素無后繼；即：第一個元素無前趨；最后一個元素無后繼； 其它元素僅有一個直接前趨和一個直接后繼。其它元素僅有一個直接前趨和一個直接后繼。 線性表中元素的個數線性表中元素的個數n（n0）定義為線性表的）定

5、義為線性表的長度長度； n=0時，稱為時，稱為空表空表； 在非空表中的每個數據元素在非空表中的每個數據元素ai都有一個確定的位置，都有一個確定的位置，稱稱i為數據元素在線性表中的為數據元素在線性表中的位序位序。整理課件二、抽象數據類型線性表的定義二、抽象數據類型線性表的定義ADT List 數據對象數據對象：D ai | ai ElemSet, i=1,2,.,n, n0 數據關系：數據關系：R1 | ai-1,aiD, i=2,.,n 整理課件 基本操作：基本操作： 結構初始化操作結構初始化操作結構銷毀操作結構銷毀操作 引用型操作引用型操作 加工型操作加工型操作 ADT List整理課件 I

6、nitList( &L )操作結果：操作結果：構造一個空的線性表L。初始化操作初始化操作整理課件 結構銷毀操作結構銷毀操作DestroyList( &L )初始條件：初始條件：操作結果：操作結果：線性表 L 已存在。銷毀線性表 L。整理課件ListEmpty( L )ListLength( L )引用型操作引用型操作: :PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraver

7、se(L, visit( )整理課件 ListEmpty( L )初始條件：初始條件：操作結果：操作結果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）整理課件ListLength( L )初始條件：初始條件：操作結果：操作結果：線性表L已存在。返回L中元素個數。（求線性表的長度）整理課件 PriorElem( L, cur_e, &pre_e )初始條件：初始條件：操作結果：操作結果：線性表L已存在。若cur_e是L的元素，但不是第一個，則用pre_e 返回它的前驅，否則操作失敗，pre_e無定義。（求數據元素的前驅）整理課件NextElem( L, cu

8、r_e, &next_e )初始條件：初始條件：操作結果：操作結果：線性表L已存在。若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數據元素的后繼）整理課件GetElem( L, i, &e ) 初始條件：初始條件： 操作結果：操作結果：線性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 個元素的值。（求線性表中某個數據元素）整理課件LocateElem( L, e, compare( ) )初始條件：初始條件：操作結果：操作結果：線性表L已存在，e為給定值， compare( )是元素判定函數

9、。返回L中第中第1個個與e滿足滿足關系compare( )的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數）整理課件 ListTraverse(L, visit( )初始條件：初始條件：操作結果：操作結果：線性表L已存在，Visit() 為某個訪問函數。依次依次對L的每個元素調用函數visit( )。一旦visit( )失敗，則操作失敗。（遍歷線性表）整理課件加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e)

10、整理課件ClearList( &L )初始條件：初始條件：操作結果：操作結果：線性表L已存在。將L重置為空表。（線性表置空）整理課件PutElem( &L, i, &e )初始條件：初始條件：操作結果：操作結果：線性表L已存在，且 1iLengthList(L) 。L中第i個元素賦值同e的值。（改變數據元素的值）整理課件 ListInsert( &L, i, e )初始條件初始條件：操作結果：操作結果：線性表L已存在， 且 1iLengthList(L)+1 。在L的第i個元素之前插入插入新的元素e，L的長度增1。（插入數據元素）整理課件ListDelete(&

11、amp;L, i, &e )初始條件：初始條件：操作結果：操作結果：線性表L已存在且非空， 1iLengthList(L) 。刪除L的第i個元素，并用e返回其值，L的長度減1。（刪除數據元素）整理課件 對上述定義的抽象數據類型線性表，還可以進對上述定義的抽象數據類型線性表，還可以進行一些更復雜的運算，如：行一些更復雜的運算，如： 將兩個或兩個以上的線性表合并成一個線性表；將兩個或兩個以上的線性表合并成一個線性表； 把一個線性表拆成兩個或兩個以上的線性表；把一個線性表拆成兩個或兩個以上的線性表； 重新復制一個線性表；重新復制一個線性表； 對線性表中的數據元素按某個數據項遞增或遞減的順對線

12、性表中的數據元素按某個數據項遞增或遞減的順 序進行重新排列，從而得到有序表。序進行重新排列，從而得到有序表。這些運算均可利用上述基本運算來實現。這些運算均可利用上述基本運算來實現。整理課件 線性表是一個相當靈活的數據結構，它的長線性表是一個相當靈活的數據結構，它的長度可依據需要進行增減，對數據元素不僅可以訪度可依據需要進行增減，對數據元素不僅可以訪問，還可以進行插入和刪除等操作。運算的具體問，還可以進行插入和刪除等操作。運算的具體實現一般依賴所采用的存儲結構，所以，這里給實現一般依賴所采用的存儲結構，所以，這里給出的只是定義在邏輯結構上的抽象運算，即只關出的只是定義在邏輯結構上的抽象運算，即只

13、關心這些運算是心這些運算是“做什么做什么”的，至于的，至于“怎樣實現怎樣實現”則依賴于所選定的存儲結構。則依賴于所選定的存儲結構。整理課件利用上述定義的線性表線性表 可以實現其它更復雜的操作例例 2-2例例 2-3例例 2-1整理課件 假設:有兩個集合集合 A 和和 B 分別用兩個線線性表性表 LA 和和 LB 表示，即：線性表中的數據元素即為集合中的成員。 現要求一個新的集合現要求一個新的集合AAB。例例 2-1 整理課件要求對線性表作如下操作： 擴大線性表 LA，將存在于線性表存在于線性表LB 中中而不存在于線性表不存在于線性表 LA 中中的數據元素插插入到線性表入到線性表 LA 中中去。

14、上述問題可演繹為：上述問題可演繹為： LA： (c,p,t,a,q,d) LB: (a,d,b,e,p,r) 結果結果LA: (c,p,t,a,q,d,b,e,r)整理課件1.從線性表LB中依次察看每個數據元素;2.依值在線性表LA中進行查訪; 3.若不存在，則插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步驟：操作步驟：整理課件 GetElem(Lb, i, e); / 取取Lb中第中第i個數據元素賦給個數據元素賦給e if (!LocateElem(La, e, equal( ) ) ListI

15、nsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數據元素，則插入之相同的數據元素，則插入之void union(List &La, List Lb) La_len = ListLength(La); Lb_len = ListLength(Lb); / 求線性表的長度求線性表的長度for (i = 1; i = Lb_len; i+) / union整理課件 已知已知一個非純集合非純集合 B，試構造構造一個純純集合集合 A，使使 A中只包含中只包含 B 中所有值各不中所有值各不相相 同的數據元素同的數據元素。仍選用線性表線性表表示集合。例例 2-2

16、2-2整理課件集合集合 B集合集合 A從集合 B 取出物件放入集合 A要求集合A中同樣物件不能有兩件以上同樣物件不能有兩件以上因此，算法的策略應該和例算法的策略應該和例2-1相同相同整理課件void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / union GetElem(Lb, i, e); / 取取Lb中第中第 i 個數據元素賦給個數據元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不

17、存在和中不存在和 e 相同的數據元素，則插入之相同的數據元素，則插入之for (i = 1; i = Lb_len; i+) InitList(La); / 構造構造(空的空的)線性表線性表LA整理課件 若線性表中的數據元素相互之間可以比較比較，并且數據元素在線性表中依值非遞減或非遞增有依值非遞減或非遞增有序序排列，即 aiai-1 或 aiai-1(i = 2,3, n) 則稱該線性表為有序表有序表(Ordered List)(Ordered List)。試改變結構，以有序表有序表表示集合。整理課件例如例如：（2，3，3，5，6，6，6，8，12）對集合 B 而言， 值相同的數據元素必定相鄰

18、；值相同的數據元素必定相鄰；對集合 A 而言， 數據元素依值從小至大的順序插入。數據元素依值從小至大的順序插入。因此，數據結構改變了數據結構改變了 -解決問題的策略也相應要改變。解決問題的策略也相應要改變。整理課件void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i個數據元素賦給個數據元素賦

19、給 eif (ListEmpty(La) | !equal (en, e) / en為表為表La中當前最后一個元素中當前最后一個元素 ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的數據元素，則插入之相同的數據元素，則插入之整理課件 已知線性表已知線性表LA和和LB中的數據元素按值非遞減有序排中的數據元素按值非遞減有序排列，現要求將列，現要求將LA和和LB歸并為一個新的線性表歸并為一個新的線性表LC，且，且LC中的數據元素仍按值非遞減有序排列。中的數據元素仍按值非遞減有序排列。例如，設例如，設 LA=(3,5,8,11) i LB

20、=(2,6,8,9,11,15,20) j 則則 LC=(2, 3, 5,6,8,8,9,11,11,15,20) k 例例 2-3 整理課件Void MergeList (List La , List Lb, List &Lc) INITIATE(Lc); i=j=1; k=0; /初始化初始化 La_len= LENGTH (La) ; Lb_len= LENGTH (Lb) ; while (i=La_len)& (j=Lb_len) /La和和Lb均非空均非空 GetElem(La,i,ai); GetElem (Lb,j,bj); if (ai=bj) ListIns

21、ert(LC, +k,ai); + i; else ListInsert(LC,+k,bj); + j; while (i=La_len) / 插入插入 La 表中剩余元素表中剩余元素 GetElem(La, i+,ai); ListInsert(LC,+k,ai); while (j=Lb_len) / 插入插入 Lb 表中剩余元素表中剩余元素 GetElem(Lb, j+,bj); ListInsert(LC,+k,bj); / MergeList整理課件2.2 線性表的順序表示和實現線性表的順序表示和實現一、線性表的順序存儲結構一、線性表的順序存儲結構順序映象順序映象二、順序存儲結構的特

22、點二、順序存儲結構的特點三、線性表的順序存貯結構示意圖及描述三、線性表的順序存貯結構示意圖及描述四、線性表的基本操作在順序表中的實現四、線性表的基本操作在順序表中的實現五、順序存儲結構的優缺點五、順序存儲結構的優缺點整理課件一、線性表的順序存儲結構一、線性表的順序存儲結構 順序映象順序映象 最簡單的一種順序映象方法是：最簡單的一種順序映象方法是： 令令y y的存儲位置和的存儲位置和x x的存儲位置相鄰的存儲位置相鄰。 以以 x 的存儲位置和的存儲位置和 y 的存儲位置之間的存儲位置之間某種關系表示邏輯關系某種關系表示邏輯關系。整理課件順序存儲結構：順序存儲結構： 用一組地址連續地址連續的存儲單

23、元依次存放依次存放線性表中的數據元素。 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的基地址基地址整理課件 假設線性表的每個數據元素要占假設線性表的每個數據元素要占c個存儲單個存儲單元，則元，則 LOC(ai+1)=LOC(ai)+c 所有數據元素的存儲位置均取決于第一個所有數據元素的存儲位置均取決于第一個數據元素的存儲位置，即數據元素的存儲位置，即 LOC(ai)=LOC(a1)+(i-1)*c 起始地址（基地址）起始地址（基地址）以“存儲位置相鄰存儲位置相鄰”表示有序對整理課件二、順序存儲結構的特點二、順序存儲結構的特點 表中相鄰的兩個元素其物理存儲位置也相鄰

24、。表中相鄰的兩個元素其物理存儲位置也相鄰。即以元素在計算機內物理位置上的相鄰來表示線性即以元素在計算機內物理位置上的相鄰來表示線性表中數據元素之間相鄰的邏輯關系。每個數據元素表中數據元素之間相鄰的邏輯關系。每個數據元素的存儲位置和線性表的起始位置相差一個和數據元的存儲位置和線性表的起始位置相差一個和數據元素在線性表中的序號成正比的常數；只要確定了起素在線性表中的序號成正比的常數；只要確定了起始位置，線性表中任一數據元素都可隨機存取。始位置，線性表中任一數據元素都可隨機存取。順順序存儲結構是一種隨機存取的存儲結構。序存儲結構是一種隨機存取的存儲結構。 整理課件三、線性表的順序存貯結構示意圖及描述

25、三、線性表的順序存貯結構示意圖及描述aia2a1內存狀態內存狀態序號序號存儲地址存儲地址Loc(a1)Loc(a1) + CLoc(a1) + C * (i-1)12iannLoc(a1) + C * (n-1)空閑空閑Loc(a1) + (maxlen-1)*c整理課件順序映像的順序映像的 C C 語言描述語言描述typedef struct SqList; /俗稱順序表俗稱順序表#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量線性表存儲空間的分配增量El

26、emType *elem; / 存儲空間基址存儲空間基址int length; / 當前長度當前長度int listsize; / 當前分配的存儲容量當前分配的存儲容量 / ( (以以sizeof(ElemType)sizeof(ElemType)為單位為單位) )整理課件四、線性表的基本操作在順序表中的實現四、線性表的基本操作在順序表中的實現InitList(&L) / 結構初始化結構初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 刪除元素刪除

27、元素整理課件Status InitList_Sq( SqList& L ) / 構造一個空的線性表構造一個空的線性表 / InitList_Sq算法時間復雜度時間復雜度： O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit (OVERFLOW); / 存儲分配失敗存儲分配失敗L.length = 0; / 空表長度為零空表長度為零L.listsize = LIST_INIT_SIZE / 初始存儲容量初始存儲容量return OK;整理課件例如：查找順序表例如：查找順序

28、表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可見，基本操作是：將順序表中的元素逐個和給定值e相比較。整理課件 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) /在順序表中查詢第一個滿足判定條件的數據元素，在順序表中查詢第一個滿足判定條件的數據元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 0 / LocateElem_Sq O( ListLength(L)

29、)算法的算法的時間復雜度時間復雜度為：為：i = 1; / i i 的初值為第的初值為第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值為第的初值為第 1 1 元素的存儲位置元素的存儲位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i; else return 0;整理課件線性表操作 ListInsert(&L, i, e)的實現：首先分析首先分析:插入元素時，線性表的邏輯結構邏輯結構發生什么變化發生什么變化？整理課件 (a1, , ai-1, ai, , a

30、n) 改變為 (a1, , ai-1, e, ai , , an)a1 a2 ai-1 ai an a1 a2 ai-1 ai ean, 表的長度增加整理課件 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法算法時間復雜度時間復雜度為為: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.l

31、ength-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表長增表長增1return OK;整理課件if (L.length = L.listsize) / 當前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem = newbase; / 新基址 L

32、.listsize += LISTINCREMENT; / 增加存儲容量if (i L.length+1) return ERROR; / 插入位置不合法整理課件 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法算法時間復雜度時間復雜度為為: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL

33、.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表長增表長增1return OK;整理課件考慮移動元素的平均情況考慮移動元素的平均情況: : 假設在第 i 個元素之前插入的概率為 ， 則在長度為n 的線性表中插入一個元素所需移插入一個元素所需移動元素次數的期望值動元素次數的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個位置上進行插入的插入的概率概率都是相等相等的，則移動元素的期望值移動元素的期望值為：

34、整理課件21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p整理課件線性表操作線性表操作 ListDelete(&L, i, &e)的實現：的實現：首先分析：首先分析：刪除元素時，刪除元素時，線性表的邏輯結構發生什么變化？線性表的邏輯結構發生什么變化？整理課件 (a1, , ai-1, ai,

35、 ai+1, , an) 改變為 (a1, , ai-1, ai+1, , an)ai+1an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 整理課件Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移被刪除元素之后的元素左移-L.length; / 表長減表長減1 1return OK;算法時間復雜度算法時間復雜度為為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置為被刪除元素的位置e = *p; / 被刪除元素的值賦給被