數(shù)據(jù)結構 (2)ppt課件

1、第2章 線性表 第二章第二章 線性表線性表2.1 線性表的類型定義線性表的類型定義 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) 2 1第2章 線性表 線性構造是一個數(shù)據(jù)元素的有序次序集線性構造是一個數(shù)據(jù)元素的有序次序集 線性構造的根本特征線性構造的根本特征:1集合中必存在獨一的一個集合中必存在獨一的一個“第一元素；第一元素；2集合中必存在獨一的一個集合中必存在獨一的一個“最后元素；最后元素；3除最后元素在外，均有獨一的后繼；除最后元素在外，均有獨一的后繼；4除第一元素之外，均有獨一的前驅(qū)。除第一元素之外，均有獨一的前驅(qū)。2第2章

2、線性表 2.1 線性表的類型定義線性表的類型定義線性表linear_list是最常用且最簡單的一種數(shù)據(jù)構造。簡言之，一個線性表是n個數(shù)據(jù)元素的有限序列。例如： A,B,C,D,Z 6,17,28,50,92,188在線性表中，一個數(shù)據(jù)元素可以由假設干數(shù)據(jù)項item組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄record，含有大量記錄的線性表又稱文件file。3第2章 線性表 籠統(tǒng)數(shù)據(jù)類型線性表的定義如下：ADT List 數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 /稱n為線性表的表長; 稱n=0時的線性表為空表。數(shù)據(jù)關系：R1 |ai-1 ,aiD, i=2,.,

3、n /設線性表為 (a1，a2,.，an), 稱i為ai在線性表中的位序。根本操作：InitList( &L )構造初始化操作結果：構造一個空的線性表L。DestroyList( &L )銷毀構造 初始條件：線性表L已存在。操作結果：銷毀線性表L。4第2章 線性表 ListEmpty( L )初始條件：線性表L已存在。操作結果：假設L為空表，那么前往TRUE，否那么FALSE。ListLength( L )初始條件：線性表L已存在。操作結果：前往L中元素個數(shù)。PriorElem( L, cur_e, &pre_e )初始條件：線性表L已存在。操作結果：假設cur_e是L的元素，但不是第一個，那

4、么用pre_e 前往它的前驅(qū)，否那么操作失敗，pre_e無定義。5第2章 線性表 NextElem( L, cur_e, &next_e )初始條件：線性表L已存在。操作結果：假設cur_e是L的元素，但不是最后一個，那么用next_e前往它的后繼，否那么操作失敗，next_e無定義。GetElem( L, cur_e, &next_e )初始條件：線性表L已存在， 1iLengthList(L)操作結果：用e前往L中第i個元素的值。LocateElem( L, e, compare( ) )初始條件：線性表L已存在，compare( )是元素斷定函數(shù)。操作結果：前往L中第1個與e滿足關系co

5、mpare( )的元素的位序。假設這樣的元素不存在，那么前往值為0。6第2章 線性表 ListTraverse(L, visit( )初始條件：線性表L已存在。操作結果：依次對L的每個元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，那么操作失敗。ClearList( &L )初始條件：線性表L已存在。操作結果：將L重置為空表。PutElem( L, i, &e )初始條件：線性表L已存在，1iLengthList(L)操作結果：L中第i個元素賦值同e的值。ListInsert( &L, i, e )初始條件：線性表L已存在，1iLengthList(L)+1操作結果：在L的第i個元素之

6、前插入新的元素e，L的長度增1。7第2章 線性表 ListDelete(&L, i, &e)初始條件：線性表L已存在且非空，1iLengthList(L)操作結果：刪除L的第i個元素，并用e前往其值，L的長度減1。 ADT List8第2章 線性表 例例2-1 假設有兩個集合假設有兩個集合A和和B分別用兩個線性表分別用兩個線性表LA和和LB表示即：線性表中的數(shù)據(jù)元素即為集表示即：線性表中的數(shù)據(jù)元素即為集合中的成員，現(xiàn)要求一個新的集合合中的成員，現(xiàn)要求一個新的集合AAB。上述問題可演繹為，要求對線性表作如下操作：擴展線性表上述問題可演繹為，要求對線性表作如下操作：擴展線性表LA，將存在于線性表，

7、將存在于線性表LB中而不存中而不存在于線性表在于線性表LA中的數(shù)據(jù)元素插入到線性表中的數(shù)據(jù)元素插入到線性表LA中去。中去。1從線性表從線性表LB中依次獲得每個數(shù)據(jù)元素中依次獲得每個數(shù)據(jù)元素; GetElem(LB, i)e2依值在線性表依值在線性表LA中進展查訪中進展查訪; LocateElem(LA, e, equal( )3假設不存在，那么插入之。假設不存在，那么插入之。 ListInsert(LA, n+1, e)9第2章 線性表 void union(List &La, List Lb) / 將一切在線性表將一切在線性表Lb中但不在中但不在La中的數(shù)據(jù)元素插入到中的數(shù)據(jù)元素插入到La中

8、中La_len = ListLength(La);Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e);/ 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給eif(!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e);/ La中不存在和中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之一樣的數(shù)據(jù)元素，那么插入之 / union10第2章 線性表 2.2 線性表類型的實現(xiàn)線性表類型的實現(xiàn) -順序映象順序映象用一組地址延續(xù)的存儲單元依次

9、存放線性表中的數(shù)據(jù)元素線性表的起始地址，稱作線性表的基地址以“存儲位置相鄰表示有序?qū)?即：一切數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置11第2章 線性表 順序映像的順序映像的C C言語描畫言語描畫/- /- 線性表的動態(tài)分配順序存儲構造線性表的動態(tài)分配順序存儲構造 - -#define LIST_INIT_SIZE 80 / #define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量線性表存儲空間的初始分配量#define LISTINCREMENT 10 / #define LISTINCREMENT 10 / 線性表存儲空間的分配增量線性表存儲空間的分配增

10、量typedef struct typedef struct ElemType ElemType * *elem; / elem; / 存儲空間基址存儲空間基址 int length; / int length; / 當前長度當前長度 int listsize; / int listsize; / 當前分配的存儲容量當前分配的存儲容量( (以以sizeof(ElemType)sizeof(ElemType)為單位為單位) ) SqList; / SqList; / 俗稱俗稱 順序表順序表12第2章 線性表 線性表的初始化在順序映像中的實現(xiàn)線性表的初始化在順序映像中的實現(xiàn)Status InitL

11、ist_Sq(SqList &L) / 構造一個空的線性表構造一個空的線性表L。L.elem =(ElemType )malloc(LISTINCREMENT*sizeof(ElemType);if (!L.elem) exit(OVERFLOW); / 存儲分配失敗存儲分配失敗L.length = 0; / 長度為長度為0L.listsize = LISTINCREMENT; / 初始存儲容量初始存儲容量return OK; / InitList_Sq13第2章 線性表 線性表操作ListInsert(&L, i, e)的實現(xiàn)：問：插入元素時，線性表的邏輯構造發(fā)生什么變化？ (a1, , a

12、i-1, ai, , an) 改動為 (a1, , ai-1, e, ai, , an)14第2章 線性表 Status ListInsert_Sq(SqList &L, int pos, ElemType e) / 在順序線性表在順序線性表L的第的第pos個元素之前插入新的元素個元素之前插入新的元素e，/ pos的合法值為的合法值為1posListlength_Sq(L)+1if (pos L.length+1) return ERROR; / 插入位置不合法插入位置不合法if (L.length = L.listsize) / 當前存儲空間已滿，添加分配當前存儲空間已滿，添加分配newba

13、se = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存儲分配失敗存儲分配失敗L.elem = newbase; / 新基址新基址L.listsize += LISTINCREMENT; / 添加存儲容量添加存儲容量q = &(L.elempos-1); / q指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移插入位置及之后的

14、元素右移*q = e; / 插入插入e+L.length; / 表長增表長增1return OK; / ListInsert_Sq15第2章 線性表 線性表操作ListDelete(&L, i, &e)的實現(xiàn)：問：刪除元素時，線性表的邏輯構造發(fā)生什么變化？(a1, , ai-1, ai, ai+1, , an) 改動為 (a1, , ai-1, ai+1, , an)16第2章 線性表 Status ListDelete_Sq(SqList &L, int pos, ElemType &e) / 在順序線性表在順序線性表L中刪除第中刪除第pos個元素，并用個元素，并用e前往其值。前往其值。/

15、pos的合法值為的合法值為1posListLength_Sq(L)if (pos L.length) return ERROR; / 刪除位置不合法刪除位置不合法p = &(L.elempos-1); / p為被刪除元素的位置為被刪除元素的位置e = *p; / 被刪除元素的值賦給被刪除元素的值賦給eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置for (+p; p Next=p-Next;q-Next=p-Next;和和p-Next=q;p-Next=q;，即修正兩個結點的指針域的值就可以了，如下，即修正兩個結點的指針域的值就可以了，如下圖。圖。24第2章 線

16、性表 單鏈表的插入 (a) 插入前；(b) 插入后xqPq-Nextp-Next；p-Nextq；xpq(a)(b)25第2章 線性表 線性表的操作ListInsert(&L, i, e)在鏈表中的實現(xiàn):根本操作為:找到線性表中第i-1個結點，修正其指向后繼的指針有序?qū)?改動為 和 Status ListInsert_L(LinkList L, int pos, ElemType e) / 在帶頭結點的單鏈表L中第pos個數(shù)據(jù)元素之前插入數(shù)據(jù)元素ep = L; j = 0;while (p & j next; +j; / 尋覓第pos-1個結點if (!p | j pos-1) return

17、ERROR; / pos小于1或者大于表長s = (LinkList) malloc ( sizeof (LNode); / 生成新結點s-data = e; s-next = p-next; / 插入L中p-next = s;return OK; / LinstInsert_L26第2章 線性表 刪除操作如下圖。刪除刪除操作如下圖。刪除p p所指示的結點時，只需修正一個指針：所指示的結點時，只需修正一個指針：q-Next=p-Nextq-Next=p-Next，但，但還需運用還需運用free(p)free(p)語句回收結點占用的空間。這里，結點語句回收結點占用的空間。這里，結點* *q q是

18、結點是結點* *p p的前驅(qū)結點的前驅(qū)結點(predecessor)(predecessor)。由此可見，在單鏈表中，為了刪除一個結點，我們必需知道它的前驅(qū)結點。由此可見，在單鏈表中，為了刪除一個結點，我們必需知道它的前驅(qū)結點。27第2章 線性表 單鏈表的刪除 (a) 刪除前；(b) 刪除后qq-Nextp-Next；pqp(a)(b)28第2章 線性表 Status ListDelete_L(LinkList L, int pos, ElemType &e) / 在帶頭結點的單鏈表在帶頭結點的單鏈表L中，刪除第中，刪除第pos個元素，并由個元素，并由e前往其值前往其值p = L; j = 0

19、;while (p-next & j next; +j;if (!(p-next) | j pos-1) return ERROR; / 刪除位置不合理刪除位置不合理q = p-next; p-next = q-next; / 刪除并釋放結點刪除并釋放結點e = q-data; free(q);return OK; / ListDelete_L算法的時間復雜度為算法的時間復雜度為:O(ListLength(L)29第2章 線性表 五、循環(huán)鏈表五、循環(huán)鏈表 另一種方式的鏈式存儲構造。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈另一種方式的鏈式存儲構造。它的特點是表中最后一個結點的指針域指

20、向頭結點，整個鏈表構成一個環(huán)。由此，從表中任一結點出發(fā)均可找到表中其他結點，如圖為單鏈表的循環(huán)鏈表表構成一個環(huán)。由此，從表中任一結點出發(fā)均可找到表中其他結點，如圖為單鏈表的循環(huán)鏈表和帶頭結點的循環(huán)鏈表。和帶頭結點的循環(huán)鏈表。最后一個結點的指針域的指針又指回第一個結點的鏈表最后一個結點的指針域的指針又指回第一個結點的鏈表30第2章 線性表 單循環(huán)鏈表(a) 空表；(b) 非空表(a)(b)Heada0a1an1Head31第2章 線性表 帶表頭結點的單循環(huán)鏈表(a) 空表；(b) 非空表(a)(b)Heada0a1an1Head32第2章 線性表 六、雙向鏈表六、雙向鏈表 我們曾經(jīng)看到，在各種單

21、鏈表中插入一個新結點時，需知道新結點插入位置的前驅(qū)結點，我們曾經(jīng)看到，在各種單鏈表中插入一個新結點時，需知道新結點插入位置的前驅(qū)結點，而當刪除一個結點時也需知道該結點的前驅(qū)結點。經(jīng)常為了得到前驅(qū)結點的地址，必需從頭開而當刪除一個結點時也需知道該結點的前驅(qū)結點。經(jīng)常為了得到前驅(qū)結點的地址，必需從頭開場查找，這一過程是費時的。此外，在實踐運用中，有時需求逆向訪問表中元素，這對單鏈表場查找，這一過程是費時的。此外，在實踐運用中，有時需求逆向訪問表中元素，這對單鏈表構造來說顯然是困難的。為處理這類問題，可將鏈表設計成雙向鏈表構造來說顯然是困難的。為處理這類問題，可將鏈表設計成雙向鏈表(doubly l

22、inked list)(doubly linked list)。33第2章 線性表 雙向鏈表的每個結點包含三個域：Element、Prior和Next。其中，Element為元素域，Next域為指向后繼結點的指針，新增的Prior域用以指向前驅(qū)結點。 雙向鏈表也可以帶表頭結點，并且也可構成雙向循環(huán)鏈表。此時，表頭結點的Next和Prior分別指向雙向循環(huán)鏈表的頭結點(或表頭結點)和尾結點。帶表頭結點的雙向循環(huán)鏈表的構造表示圖如下圖。34第2章 線性表 帶表頭結點的雙向循環(huán)鏈表(a) 空表；(b) 非空表(a)(b)HeadHeada0an135第2章 線性表 /- 線性表的雙向鏈表存儲構造 -

23、typedef struct DuLNode ElemType data; / 數(shù)據(jù)域struct DuLNode *prior;/ 指向前驅(qū)的指針域struct DuLNode *next; / 指向后繼的指針域 DuLNode, *DuLinkList;36第2章 線性表 線性表順序存儲構造的優(yōu)缺陷：線性表順序存儲構造的優(yōu)缺陷：1 1、優(yōu)點、優(yōu)點1 1構造簡單構造簡單2 2可直接定位到表中任一元素，并可隨機存取元素；延續(xù)存儲速度快可直接定位到表中任一元素，并可隨機存取元素；延續(xù)存儲速度快2 2、缺陷、缺陷1 1存儲空間難于準確靜態(tài)分配，大了浪費，小了不夠存儲空間難于準確靜態(tài)分配，大了浪費，

24、小了不夠2 2插入、刪除操作大不方便，需挪動大量數(shù)據(jù)元素，效率低插入、刪除操作大不方便，需挪動大量數(shù)據(jù)元素，效率低37第2章 線性表 線性表鏈式存儲構造的優(yōu)缺陷：線性表鏈式存儲構造的優(yōu)缺陷：1 1、優(yōu)點、優(yōu)點1 1存儲空間動態(tài)分配，可以按需運用存儲空間動態(tài)分配，可以按需運用2 2插入、刪除結點操作時通常只需修正指針，不用挪動數(shù)據(jù)元素插入、刪除結點操作時通常只需修正指針，不用挪動數(shù)據(jù)元素2 2、缺陷、缺陷1 1每一結點附加指針域每一結點附加指針域2 2非隨機存取構造，查找定位操作需從頭指針出發(fā)順著鏈表掃描非隨機存取構造，查找定位操作需從頭指針出發(fā)順著鏈表掃描38第2章 線性表 習習 題題 2 21 定義一個構造類型，它包括年、月、日。用該構造類型定義一個構造變量。 22 設計一個算法，用來復制一個單鏈表 23 設有長度為n的一維整型數(shù)組A，設計一個算法，將原數(shù)組中的元素以逆