線性表是一種最簡單的線性結構

1、1,線性表是一種最簡單的線性結構,第二章 線性表,2,線性結構的基本特征:,1．集合中必存在唯一的一個“第一元素”；,2．集合中必存在唯一的一個 “最后元素”;,3．除最后元素在外，均有 唯一的后繼；,4．除第一元素之外，均有 唯一的前驅。,線性結構 是 一個數據元素的有序（次序）集,3,2.1 線性表的類型定義,2.3 線性表類型的實現 ? 鏈式映象,2.4 一

2、元多項式的表示,2.2 線性表類型的實現 ? 順序映象,4,2.1 線性表的類型定義,5,抽象數據類型線性表的定義如下：,ADT List {,數據對象：,D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } //稱 n 為線性表的表長; //稱 n=0 時的線性表為空表。,數據關系：,R1

3、＝{ |ai-1 ,ai∈D, i=2,...,n },//設線性表為 (a1，a2, . . . ，ai，. . . ，an), //稱 i 為 ai 在線性表中的位序。,6,基本操作：,結構初始化操作,結構銷毀操作,引用型操作,更改型操作,,} ADT List,7,InitList( &L ),操作結果：,構造一個空的線性表L。,初始化操作,,8,結構銷毀操作,DestroyList( &am

4、p;L ),初始條件：操作結果：,線性表 L 已存在。,銷毀線性表 L。,,9,ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ),NextElem( L, cur_e, &next_e ),GetElem( L, i, &e ),LocateElem( L, e, compare( ) ),ListTraverse(L, visit( )

5、),,引用型操作:,10,ListEmpty( L ),初始條件：操作結果：,線性表L已存在。,若L為空表，則返回TRUE，否則FALSE。,,（線性表判空）,11,ListLength( L ),初始條件：操作結果：,線性表L已存在。,返回L中元素個數。,,（求線性表的長度）,12,PriorElem( L, cur_e, &pre_e ),初始條件：操作結果：,線性表L已存在。,若cur_e是L的元素，但不是第

6、一個，則用pre_e 返回它的前驅，否則操作失敗，pre_e無定義。,,（求數據元素的前驅）,13,NextElem( L, cur_e, &next_e ),初始條件：操作結果：,線性表L已存在。,若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。,,（求數據元素的后繼）,14,GetElem( L, i, &e ),初始條件： 操作結果：,線性表L已存在

7、，且 1≤i≤LengthList(L),用 e 返回L中第 i 個元素的值。,,（求線性表中某個數據元素）,15,LocateElem( L, e, compare( ) ),初始條件：操作結果：,線性表L已存在，e為給定值， compare( )是元素判定函數。,返回L中第1個與e滿足關系compare( )的元素的位序。若這樣的元素不存在，則返回值為0。,,（定位函數）,16,ListTraverse(L, vis

8、it( )),初始條件：操作結果：,線性表L已存在。Visit() 為某個訪問函數。,依次對L的每個元素調用函數visit( )。一旦visit( )失敗，則操作失敗。,,（遍歷線性表）,17,更改型操作,ClearList( &L ),PutElem( L, i, &e ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),,18,ClearLis

9、t( &L ),初始條件：操作結果：,線性表L已存在。,將L重置為空表。,,（線性表置空）,19,PutElem( L, i, &e ),初始條件：操作結果：,線性表L已存在，且 1≤i≤LengthList(L),把e值賦到L中第i個元素。,,（改變數據元素的值）,20,ListInsert( &L, i, e ),初始條件：操作結果：,線性表L已存在，且 1≤i≤LengthList(L)

10、+1,在L的第i個元素之前插入新的元素e，L的長度增1。,,（插入數據元素）,21,ListDelete(&L, i, &e),初始條件：操作結果：,線性表L已存在且非空，且1≤i≤LengthList(L),刪除L的第i個元素，并用e返回其值，L的長度減1。,,（刪除數據元素）,22,利用上述定義的線性表基本操作 可以實現其它更復雜的操作,23,假設:有兩個集合A和B分別用兩個線性表LA和LB表示(即：線

11、性表中的數據元素即為集合中的成員） 現要求求一個新的集合A＝A∪B。,例 2-1,24,要求對線性表作如下操作：擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數據元素插入到線性表LA中去。,上述問題可演繹為：,25,1．從線性表LB中依次察看每個數據元素;,2．依值在線性表LA中進行查訪;,3．若不存在，則插入之。,GetElem(LB, i, &e)→e,LocateElem(LA, e, equal(

12、 )),ListInsert(LA, n+1, e),操作步驟：,26,GetElem(Lb, i, &e); // 取Lb中第i個數據元素賦給e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的數據元素，則插入之,void union(List &La, List Lb)

13、{ La_len = ListLength(La); Lb_len = ListLength(Lb); // 求線性表的長度,for (i = 1; i <= Lb_len; i++) {,},} // union,27,已知一個非純集合 B，試構造一個純集合 A，使 A中只包含 B 中所有值各不相 同的數據元素。,課堂練習：,仍選用線性表表示集合,28,GetElem(Lb, i, &e); // 取

14、Lb中第i個數據元素賦給e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的數據元素，則插入之,for (i = 1; i <= Lb_len; i++) {,},void union(List &La, List Lb) { La_len=ListLen

15、gth(La); Lb_len=ListLength(Lb);,} // union,InitList(La);,29,例2-2 歸并兩個“其數據元素按值非遞減有序排列”的線性表 LA 和 LB，求得線性表 LC 也具有同樣特性。,設 La = (a1, …, ai, …, an) Lb = (b1, …, bj, …, bm) Lc = (c1, …, ck, …, cm+n),則

16、 k = 1, 2, …, m+n,30,1．初始化 LC 為空表；2．分別從 LA和LB中取得當前元素 ai 和 bj；3．若 ai≤bj，則將 ai 插入到 LC 中，否則將 bj 插入到 LC 中；4．重復 2 和 3 兩步，直至 LA 或 LB 中元素

17、 被取完為止；5．將 LA 表或 LB 表中剩余元素復制插入到 LC 表中。,基本操作：,31,void MergeList(List La, List Lb, List &Lc) { InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i

18、<= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, &ai); GetElem(Lb, j, &bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListI

19、nsert(Lc, ++k, bj); ++j; } },32,while (i <= La_len) { GetElem(La, i++, &ai); ListInsert(Lc, ++k, ai); } // 插入 La 表中剩余元素 while (j <= Lb_len) { GetElem(Lb, j++, &

20、bj); ListInsert(Lc, ++k, bj); } // 插入 Lb 表中剩余元素} // merge_list,33,預習題,線性表的順序存儲結構有何特點？“隨機存取”的含義是什么？復習C語言中有關數組類型的使用方法。查閱相關資料，掌握函數malloc（）與realloc（）。,34,表示 的最簡單的一種順序映象方法是： 令 y 的存儲位置和 x 的存儲位置相鄰。,2.2 線性表

21、類型的實現 ----順序映象,35,用一組地址連續(xù)的存儲單元 依次存放線性表中的數據元素,a1 a2 … ai-1 ai … an,線性表的起始地址，稱作線性表的基地址,,,,,,,,,,,,,36,以“存儲位置相鄰”表示有序對 即：LOC(ai) = LOC(ai-1) + C 一個數據元素所占存儲量↑ 所有

22、數據元素的存儲位置均取決于第一個數據元素的存儲位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址,37,順序映像的C語言描述#define LIST_INIT_SIZE 100 // 線性表存儲空間的初始分配量#define LISTINCREMENT 10

23、 // 線性表存儲空間的分配增量typedef struct { ElemType *elem; // 存儲空間基址 int length; // 當前長度 int listsize; // 當前分配的存儲容量 //(以sizeof(ElemType)為單位)} SqList; // 俗稱 順序表,38,線性表的初始化

24、操作,Status InitList_Sq( SqList& L ) { // 構造一個空的線性表 L.elem = (ElemType*)malloc(LIST_ INIT_SIZE?sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE re

25、turn OK;} // InitList_Sq,算法時間復雜度：,O(1),39,線性表操作 LocateElem(L, e, compare( )) 的實現：,40,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { i = 1; // i的初值為第

26、1元素的位序 p = L.elem; // p的初值為第1元素的存儲位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; } // LocateElem_Sq,O( L

27、istLength(L) ),算法的時間復雜度為：,41,線性表操作 ListInsert(&L, i, e)的實現。,問：,插入元素時，線性表的邏輯結構發(fā)生什么變化？,42,(a1, …, ai-1, ai, …, an) 改變?yōu)?(a1, …, ai-1, e, ai, …, an),a1 a2 … ai-1 ai … an,

28、,,,,,,a1 a2 … ai-1,,,,,,,,,,,,ai,,…,,,an,,,,,,e,,,,,,, ,,,表的長度增加,,43,Status ListInsert_Sq(SqList &L, int pos, ElemType e) { if (pos L.length+1) return ERROR; // 插入位置不合法 if (L.length >= L.list

29、size) { // 當前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) exit(

30、OVERFLOW); // 存儲分配失敗 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存儲容量 } q = &(L.elem[pos-1]); // q指示插入位置 for (p = &(L.elem[L

31、.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L.length; // 表長增1 return OK; } // ListInsert_Sq,,,44,if (pos L.length+1) return ERROR;

32、 // 插入位置不合法if (L.length >= L.listsize) { // 當前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTIN

33、CREMENT)*sizeof (ElemType)); if (!newbase) exit(OVERFLOW); // 存儲分配失敗 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存儲容量},,45,考慮平均的情況:,假設在第 i 個元素之前插入的概

34、率為 則在長度為n的線性表中插入一個元素所需移動元素次數的期望值為：,若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：,46,線性表操作 ListDelete(&L, i, &e)的實現：,問：,刪除元素時，線性表的邏輯結構發(fā)生什么變化？,47,(a1, …, ai-1, ai, ai+1, …, an) 改變?yōu)?

35、 (a1, …, ai-1, ai+1, …, an),a1 a2 … ai-1 ai ai+1 … an,,,,,,,a1 a2 … ai-1,,,,,,,,,,,,ai+1,,…,,,an,,,,,,,,,,, ,,,,,表的長度減少,,48,Status ListDelete_Sq (SqList &L, int pos, ElemType &e) {

36、 if ((pos L.length)) return ERROR; // 刪除位置不合法 p = &(L.elem[pos-1]); // p為被刪除元素的位置 e = *p; // 被刪除元素的值賦給e q = L.elem+L.length-1; // 表尾元素的位置 for (++p

37、; p <= q; ++p) *(p-1) = *p; // 被刪除元素之后的元素左移 --L.length; // 表長減1 return OK; } // ListDelete_Sq,此算法的時間復雜度為:,O( ListLength(L)

38、),49,考慮平均的情況:,,假設刪除第 i 個元素的概率為 , 則在長度為n的線性表中刪除一個元素所需移動元素次數的期望值為：,若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：,50,算法 ListInsert_Sq 和 ListDelete_Sq 的 時間復雜度為:,O( n ),51,順序表的合并（算法2.7）,可從算法2.2直接寫出形式上及其相似的算法，如教材P26的算法2.7。

39、 請參看算法演示。 算法時間復雜度： O（La.length＋Lb.length）,52,void MergeList(SqList La,SqList Lb,SqList *Lc) // 算法2.7 { // 已知順序線性表La和Lb的元素按值非遞減排列。//歸并La和Lb得到新的順序線性表Lc,Lc的元素也按值非遞減排列 pa=La.elem

40、; pb=Lb.elem; (*Lc).listsize=(*Lc).length=La.length+Lb.length pc=(*Lc).elem =(ElemType*)malloc((*Lc).listsize*sizeof(ElemType)); if(!(*Lc).elem) exit(OVERFLOW);// 存儲分配失敗 pa_last=La.elem+La.l

41、ength-1; pb_last=Lb.elem+Lb.length-1; while(pa<=pa_last&&pb<=pb_last) { // 表La和表Lb均非空 if (*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while(pa<=pa_last) *p

42、c++=*pa++; // 插入La的剩余元素 while(pb<=pb_last) *pc++=*pb++; // 插入Lb的剩余元素 },53,預習題,鏈表的存儲結構有何特點？在進行鏈表的插入與刪除元素操作時應該特別注意什么操作？什么是頭結點？它有什么作用？循環(huán)鏈表的結構特點是什么？雙向鏈表的結構特點是什么？鏈表和順序表各基本操作各有什么特點？一元多項式應該采用線性表的哪種映象方法來存儲較適宜？,5

43、4,2.3 線性表類型的實現----鏈式映象,55,用一組地址任意的存儲單元存放線性表中的數據元素。,a1 a2 … ... an ^,,,,,,,,,,,,,,,,,,,,,,,,,,,,以線性表中第一個數據元素 的存儲地址作為線性表的地址，稱作線性表的頭指針,一、單鏈表,以元素(數據元素的映象) + 指針(指示后繼元素存儲位置的) = 結點(表示數據元素 或 數

44、據元素的映象),以“結點的序列”表示線性表??稱作鏈表,頭結點,56,Typedef struct LNode { ElemType data; // 數據域 struct Lnode *next; // 指針域 } LNode, *LinkList;,二、結點和單鏈表的C語言描述,LinkList L； // L 為單鏈表的頭指針,57,線性表的操作 GetElem(L, i,

45、&e)在鏈表中的實現:,三、單鏈表操作的實現,基本操作為: 使指針 p 始終指向 線性表中第 j 個數據元素,58,Status GetElem_L(LinkList L, int pos, ElemType &e) { p = L->next; j = 1; // p 指向第一個結點，j 為計數器 while (p && jnext; ++j; }

46、 // 順指針向后查找，直到 p 指向第 pos 個元素或 p 為空 if ( !p || j>pos ) return ERROR; // 第pos個元素不存在 e = p->data; // 取第pos個元素 return OK;} // GetElem_L,算法的時間復雜度為:,O(ListLength(L)),5

47、9,線性表的操作 ListInsert(&L, i, e) 在鏈表中的實現:,有序對 改變?yōu)?和,基本操作為:找到線性表中第i-1 個結點，修改其指向后繼的指針,60,Status ListInsert_L(LinkList L, int pos, ElemType e) { p = L; j = 0; while (p && j next; ++

48、j; } // 尋找第pos-1個結點 if (!p || j > pos-1) return ERROR; // pos小于1或者大于表長 s = (LinkList) malloc ( sizeof (LNode)); // 生成新結點 s->data = e; s->next = p->next; // 插入L中

49、 p->next = s; return OK; } // LinstInsert_L,算法的時間復雜度為:,O(ListLength(L)),61,線性表的操作ListDelete (&L, i, &e)在鏈表中的實現:,有序對 和 改變?yōu)?,基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針。,62,Status ListDelete_L(LinkList L, in

50、t pos, ElemType &e) { p = L; j = 0; while (p->next && j next; ++j; } // 尋找第pos個結點，并令p指向其前趨 if (!(p->next) || j > pos-1) return ERROR; /

51、/ 刪除位置不合理 q = p->next; p->next = q->next; e = q->data; free(q); // 刪除并釋放結點 return OK; } // ListDelete_L,算法的時間復雜度為:,O(ListLength(L)),63,操作 ClearList(&L) 在鏈表中的實現:,void ClearList(&L) {

52、 // 將單鏈表重新置為一個空表 while (L->next) { p=L->next; L->next=p->next; }} // ClearList,free(p);,算法時間復雜度：,O(ListLength(L)),64,如何從線性表得到單鏈表？,鏈表是一個動態(tài)的結構，因此生成鏈表的過程是一個結點“逐個插入” 的過程。,65,例如：逆位序輸入

53、 n 個數據元素的值，建立帶頭結點的單鏈表。,操作步驟：,一、建立一個“空表”；,二、輸入數據元素an， 建立結點并插入；,三、輸入數據元素an-1， 建立結點并插入；,,,,,,,,,,,,,,,,an,,,,,,,,,,an,,an-1,,,,,,四、依次類推，直至輸入a1為止。,66,void CreateList_L(LinkList &L, int n) {} // Creat

54、eList_L,算法的時間復雜度為:,O(Listlength(L)),L = (LinkList) malloc (sizeof (LNode));L->next = NULL; // 先建立一個帶頭結點的單鏈表,for (i = n; i > 0; --i) { p = (LinkList) malloc (sizeof (LNode)); scanf(&p->data); /

55、/ 輸入元素值 p->next = L->next; L->next = p; //插入},67,用上述定義的單鏈表實現線性表的操作時，存在的問題：,改進鏈表的設置：,1．單鏈表的表長是一個隱含的值；,1．增加“表長”、“表尾指針” 和 “當前位置的 指針” 三個數據域；,2．在單鏈表的最后一個元素之后插入元素時， 需遍歷整個鏈表；,3．在鏈表中，元素的“位序”概念淡化，結點的

56、 “位置”概念加強。,2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。,68,四、一個帶頭結點的線性鏈表類型,typedef struct LNode { // 結點類型 ElemType data; struct LNode *next;} *Link, *Position;,Status MakeNode( Link &p, ElemType e ); // 分配由p指向的值

57、為e的結點，并返回OK； // 若分配失敗，則返回ERROR,void FreeNode( Link &p ); // 釋放p所指結點,69,typedef struct { // 鏈表類型 Link head, tail; // 分別指向頭結點和 // 最后一個結點的指針 int l

58、en; // 指示鏈表長度 Link current; // 指向當前被訪問的結點 //的指針，初始位置指向頭結點} LinkList;如果不特別聲明的話，那么以后各節(jié)中討論的單鏈表都指的是這種帶頭結點的鏈表。,70,鏈表的基本操作:,{結構初始化和銷毀結構},Status InitList( LinkList &L );

59、// 構造一個空的線性鏈表 L，其頭指針、 // 尾指針和當前指針均指向頭結點， // 表長為零。,Status DestroyList( LinkList &L ); // 銷毀線性鏈表 L，L不再存在。,O(1),O(n),71,{引用型操作},Status ListEmpty ( LinkList L );//判表空,int ListLength( LinkList L ); // 求表長,Statu

60、s Prior( LinkList L ); // 改變當前指針指向其前驅,Status Next ( LinkList L ); // 改變當前指針指向其后繼,ElemType GetCurElem ( LinkList L ); // 返回當前指針所指數據元素,O(1),O(1),O(n),O(

61、1),O(1),72,Status LocatePos( LinkList L, int i ); // 改變當前指針指向第i個結點,Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)); // 若存在與e 滿足函數compare( )判定關系的元 // 素，則移

62、動當前指針指向第1個滿足條件的 // 元素的前驅，并返回OK; 否則返回ERROR,Status ListTraverse(LinkList L, Status(*visit)() ); // 依次對L的每個元素調用函數visit(),O(n),O(n),O(n),73,{更改型操作},Status ClearList ( LinkList &L ); // 重置 L 為空表,Sta

63、tus SetCurElem(LinkList &L, ElemType e ); // 更新當前指針所指數據元素,Status Append ( LinkList &L, Link s ); // 在表尾元素之后鏈接一串結點,Status InsAfter ( LinkList &L, Elemtype e );

64、 // 將元素 e 插入在當前指針之后,Status DelAfter ( LinkList &L, ElemType& e ); // 刪除當前指針之后的結點,O(1),O(n),O(n),O(1),O(1),74,Status InsAfter( LinkList& L, ElemType e ) { // 若當前指針在鏈表中，則將數據元素e插入在線性鏈

65、 // 表L中當前指針所指結點之后,并返回OK; // 否則返回ERROR。 } // InsAfter,if ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s->next = L.current->next; L.current->next = s; if (L.tail = L.c

66、urrent) L.tail = s; L.current = s; return OK;,75,Status DelAfter( LinkList& L, ElemType& e ) { // 若當前指針及其后繼在鏈表中，則刪除線性鏈表L中當前 // 指針所指結點之后的結點，并返回OK; 否則返回ERROR。 if ( !(L.current && L.current->

67、;next ) ) return ERROR; q = L.current->next; L.current->next = q->next; if (L.tail = q) L.tail = L.current; e=q->data; FreeNode(q); return OK;} //DelAfter,76,最后一個結點的指針域的指針又指回第一個結

68、點的鏈表,a1 a2 … ... an ^,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1. 循環(huán)鏈表,五、其它形式的鏈表,77,2. 雙向鏈表,typedef struct DuLNode { ElemType data; // 數據域 struct DuLNode *prior;

69、 // 指向前驅的指針域 struct DuLNode *next; // 指向后繼的指針域} DuLNode, *DuLinkList;,,,,,,,,,,,,,,78,雙向循環(huán)鏈表,空表,非空表,a1 a2 … ... an ^,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

70、,,,,,,,,,,,79,課堂練習,1.將一個單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1,a2,...an，則逆序鏈接后變?yōu)閍n,an-1,...a1。,80,【思路分析】,讀入當前結點，并將當前結點插入到表頭，這樣最先插入的結點成為表尾，最后插入的結點成為表頭。,81,【解答】,Status Contray ( LinkList &head ) { // 將單鏈表中所有結點逆置，成功則返回OK p =