線性表及其結(jié)構(gòu)特點

1、線性表及其結(jié)構(gòu)特點 在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序次序線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序次序集集 線性結(jié)構(gòu)特點：n2.1 線性表的類型定義：n定義： 一個線性表是n個數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表A,B,C,.Z)是一個線性表例學(xué)號姓名年齡001張三18002李四19數(shù)據(jù)元素特征：n元素個數(shù)n表長度，n=0空表n1in時nai的直接前驅(qū)是ai-1，a1無直接前驅(qū)nai的直接后繼是ai+1

2、，an無直接后繼n元素同構(gòu)，且不能出現(xiàn)缺項n線性表是一種典型的線性結(jié)構(gòu)。抽象數(shù)據(jù)類型線性表線性表的定義如下：ADT List 數(shù)據(jù)對象數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 稱n為線性表的表長表長; 稱n=0時的線性表為空空表表。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2,.，ai，.，an), 稱i為ai在線性表中的位序位序。 根本操作：根本操作：結(jié)構(gòu)初始化結(jié)構(gòu)初始化InitList( &L )操作結(jié)果：構(gòu)造一個空的線性表L。銷毀結(jié)構(gòu)銷毀結(jié)構(gòu)DestroyList( &L )初始條件：線性表L已

3、存在。操作結(jié)果：銷毀線性表L。 引用型操作引用型操作ListEmpty( L )初始條件：線性表L已存在。操作結(jié)果：假設(shè)L為空表，那么返回TRUE，否那么FALSE。ListLength( L )初始條件：線性表L已存在。操作結(jié)果：返回L中元素個數(shù)。PriorElem( L, cur_e, &pre_e )初始條件：線性表L已存在。操作結(jié)果：假設(shè)cur_e是L的元素，但不是第一個，那么用pre_e 返回它的前驅(qū)，否那么操作失敗，pre_e無定義。NextElem( L, cur_e, &next_e )初始條件：線性表L已存在。操作結(jié)果：假設(shè)cur_e是L的元素，但不是最后一個

4、，那么用next_e返回它的后繼，否那么操作失敗，next_e無定義。 GetElem( L, cur_e, &next_e )初始條件：線性表L已存在， 1iLengthList(L)操作結(jié)果：用e返回L中第i個元素的值。LocateElem( L, e, compare( ) )初始條件：線性表L已存在，compare( )是元素判定函數(shù)。操作結(jié)果：返回L中第1個與e滿足關(guān)系compare( )的元素的位序。假設(shè)這樣的元素不存在，那么返回值為0。ListTraverse(L, visit( )初始條件：線性表L已存在。操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit( )。一旦vis

5、it( )失敗，那么操作失敗。 加工型操作加工型操作 ClearList( &L )初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。PutElem( L, i, &e )初始條件：線性表L已存在，1iLengthList(L)操作結(jié)果：L中第i個元素賦值同e的值。 ListInsert( &L, i, e )初始條件：線性表L已存在，1iLengthList(L)+1操作結(jié)果：在L的第i個元素之前插入新的元素e，L的長度增1。ListDelete(&L, i, &e)初始條件：線性表L已存在且非空，1iLengthList(L)操作結(jié)果：刪除L的第i

6、個元素，并用e返回其值，L的長度減1。 ADT List 利用上述定義的線性表可以完成其它更利用上述定義的線性表可以完成其它更復(fù)雜的操作復(fù)雜的操作 n例例2-1 假設(shè)有兩個集合假設(shè)有兩個集合A和和B分別用兩個分別用兩個線性表線性表LA和和LB表示即：線性表中的數(shù)表示即：線性表中的數(shù)據(jù)元素即為集合中的成員，現(xiàn)要求一據(jù)元素即為集合中的成員，現(xiàn)要求一個新的集合個新的集合AAB。n上述問題可演繹為，要求對線性表作如上述問題可演繹為，要求對線性表作如下操作：擴大線性表下操作：擴大線性表LA，將存在于線性，將存在于線性表表LB中而不存在于線性表中而不存在于線性表LA中的數(shù)據(jù)元中的數(shù)據(jù)元素插入到線性表素插入

7、到線性表LA中去。中去。思路：1從線性表LB中依次取得每個數(shù)據(jù)元素; GetElem(LB, i)e2依次在線性表LA中進行查訪; LocateElem(LA, e, equal( )3假設(shè)不存在，那么插入之。 ListInsert(LA, n+1, e) void union(List &La, List Lb) / 將所有在線性表將所有在線性表Lb中但不在中但不在La中的數(shù)據(jù)元素插入中的數(shù)據(jù)元素插入到到La中中La_len = ListLength(La);Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度for (i = 1; i = Lb_len;

8、 i+) GetElem(Lb, i, e);/ 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給eif(!LocateElem(La, e, equal( ) ListInsert(La, +La_len1, e);/ La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，那么插入之相同的數(shù)據(jù)元素，那么插入之 / union例例2-2 一個非純集合一個非純集合B，試構(gòu)造一個純集，試構(gòu)造一個純集合合A，使，使A中只包含中只包含B中所有值各不相同中所有值各不相同的數(shù)據(jù)元素。的數(shù)據(jù)元素。void purge(List &La, List Lb) / 線性表線性表Lb中的數(shù)據(jù)元素依值非遞減有中的數(shù)據(jù)元

9、素依值非遞減有序排列序排列(Lb是有序表是有序表)，/ 構(gòu)造線性表構(gòu)造線性表La，使其只包含，使其只包含Lb中所有中所有值不相同的數(shù)據(jù)元素值不相同的數(shù)據(jù)元素InitList(LA);La_len = ListLength(La);Lb_len =ListLength(Lb); / 求線性表的長度for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i個數(shù)據(jù)元素賦給eif(!equal (en, e) /en初始化為LB中沒有的值ListInsert(La, +La_len, e);en = e; / La中不存在和 e 相同的數(shù)據(jù)元素，那么

10、插入之 / purge例例2-3 歸并兩個歸并兩個“其數(shù)據(jù)元素按值非遞減其數(shù)據(jù)元素按值非遞減有序排列的線性表有序排列的線性表LA和和LB，求得線性，求得線性表表LC也具有同樣特性也具有同樣特性設(shè)設(shè) La = (a1, , ai, , an) Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)那么那么 Ck = k = 1, 2, , m+n 思路：1分別從LA和LB中取得當(dāng)前元素ai和bj；2假設(shè)aibj，那么將ai插入到LC中，否那么將bj插入到LC中。void MergeList(List La, List Lb, List &Lc) / 線

11、性表線性表La和和Lb中的元素按值非遞減排中的元素按值非遞減排列。列。/ 歸并歸并La和和Lb得到新的線性表得到新的線性表Lc，/ Lc的元素也按值非遞減排列。的元素也按值非遞減排列。InitList(Lc); i = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);while (i = La_len) & (j = Lb_len) / La和Lb均非空GetElem(La, i, ai); GetElem(Lb, j, bj);if (ai = bj) ListInsert(Lc, +k, ai); +i; e

12、lse ListInsert(Lc, +k, bj); +j; while (i = La_len) GetElem(La, i+, ai);ListInsert(Lc, +k, ai);while (j = Lb_len) GetElem(Lb, j+, bj);ListInsert(Lc, +k, bj); / merge_list 2.2 線性表的順序存儲結(jié)構(gòu)順序表： 定義：用一組地址連續(xù)的存儲單元存放一個線性表叫元素地址計算方法：nLOC(ai)=LOC(a1)+(i-1)*LnLOC(ai+1)=LOC(ai)+Ln其中：nL一個元素占用的存儲單元個數(shù)nLOC(ai)線性表第i個元素

13、的地址順序表：n特點：n實現(xiàn)邏輯上相鄰物理地址相鄰n實現(xiàn)隨機存取n實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標元素序號M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組動態(tài)申請和釋放內(nèi)存DATATYPE *pData = (DATA

14、TYPE *)malloc(M*sizeof(DATATYPE);free(pData); 順序映像的C語言描述 /- 線性表的動態(tài)分配順序存儲結(jié)構(gòu) -#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量typedef struct ElemType *elem; / 存儲空間基址int length; / 當(dāng)前長度int listsize; / 當(dāng)前分配的存儲容量(以sizeof(ElemType)為單位) SqList; / 俗稱 順序表順序表線性表的初始化在順序映像中的實現(xiàn)Stat

15、us InitList_Sq(SqList &L) / 構(gòu)造一個空的線性表L。L.elem = (ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType);if (!L.elem) exit(OVERFLOW); / 存儲分配失敗L.length = 0; / 長度為0L.listsize = LIST_INIT_SIZE; / 初始存儲容量return OK; / InitList_Sq線性表操作LocateElem(L, e, compare( )的實現(xiàn)： int LocateElem_Sq(SqList L, ElemType e,St

16、atus (*compare)(ElemType, ElemType) / 在順序線性表在順序線性表L中查找第中查找第1個值與個值與e滿足滿足compare()的元素的位序。的元素的位序。/ 假設(shè)找到，那么返回其在假設(shè)找到，那么返回其在L中的位序，中的位序，否那么返回否那么返回0。i = 1; / i的初值為第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此算法的

17、時間復(fù)雜度為: O( ListLength(L) )線性表操作ListInsert(&L, i, e)的實現(xiàn)： n問：插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ n(a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an) 內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1an-1x思路：1、合法性檢查2、存儲空間的處理判斷、申請3、元素的移動：從n號到pos號往后移動。4、把e插入pos號位置，長度增1Status L

18、istInsert_Sq(SqList &L, int pos, ElemType e) / 在順序線性表L的第pos個元素之前插入新的元素e，pos為位序/ pos的合法值為1posListlength_Sq(L)+1if (pos L.length+1) return ERROR; / 插入位置不合法if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit

19、(OVERFLOW); / 存儲分配失敗L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存儲容量q = &(L.elempos-1); / q指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK; / ListInsert_Sqn算法時間復(fù)雜度T(n)n設(shè)Pi是在第i個元素之前插入一個元素的概率，那么在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認為線性表操作ListDelete(&L, i, &e)的實現(xiàn)： n問：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？n(a1, , ai-1, ai, ai+