數(shù)據(jù)結構第二章線性表

1、第二章 線性表n2.1 線性表的類型定義n2.2 線性表的順序表示和實現(xiàn)n2.3 線性表的鏈式表示和實現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表n2.4 一元多項式的表示及相加線性結構：是一個數(shù)據(jù)元素的有序集例如（A，B，C，D，E，Z） （32，25，76，28，96）注：1、一個數(shù)據(jù)元素的集合 2、這些數(shù)據(jù)元素是有序的線性結構的特征：1、唯一的“第一個元素”2、唯一的“最后一個元素”3、除最后一個元素外，所有元素都有唯一的后繼4、除第一個元素外，所有元素都有唯一的前驅2.1 線性表的類型定義一、線性表(Linear List) ：由n(n)個數(shù)據(jù)元素(結點)a1，

2、a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 例1、26個英文字母組成的字母表 （A，B，C、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）二、抽象數(shù)據(jù)類型的線性表的定義ADT List數(shù)據(jù)對象： D=ai|aiElem Set ，i=1，2，3n，n=0數(shù)據(jù)關系： R1=| ai-1，ai D，i=，2，3，n基本操作n基本操作：1、結構初始化InitList（&L）結果：構造一個空的線性表L2、銷毀結構DestroyList

3、（&L）初始條件：線性表L已經(jīng)存在結果：銷毀線性表L3、引用型操作ListEmpty（L）；ListLength（L）PriorElem（L.cur_e, &pre_e）；NextElem（ L.cur_e, &next_e ）；GetElem（L，e，&e）；LocateElem(L，e，compare（）);ListTraverse（L，visit（）4、加工型操作ClearList（&L）PutElem（L，i，&e）ListInsert(&L，i，e)ListDelete (&L，i，&e ）注：1、InitLis

4、t（ &L ）和ClearList（ &L ）的區(qū)別2、除了初始化操作外，每一個操作都有一個初始條件和操作結果3、任何一種抽象數(shù)據(jù)類型，都包含有初始化操作和銷毀操作例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。算法：1、從線性表LB中依次取得每個數(shù)據(jù)元素 GetElem（LB，i）e 2、依值在線性表LA中進行查訪 LocateElem（LA，e，equal（） 3、若不存在，則插入到LA中 ListInsert（LA，n+1，e） void union(List &La，List Lb) La-len=Listlength(La

5、); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e); if(!LocateElem(la，e，equal() Listinsert(la，+la-len，e) 例2-2 已知一個非純集合B，試構造一個純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素算法1： void purge (List &La，List Lb) InitList (La); La-len=Listlength(La); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e);

6、if(!LocateElem(la，e，equal() +la-len; Listinsert(la，la-len，e) 算法2： 1、先對原表進行排序 2、然后插入 void purge(List &La，List Lb) InitList(La); La-len=Listlength(La); Lb-len=Listlength(Lb); for(I=1;I=Lb-len;I+) GetElem(lb，I，e); if（ListEmpty（La）|！Equal（en，e） Listinsert(la，+la-len，e)； en=e； 例2-3 巳知線性表LA和線性表LB中的數(shù)據(jù)元

7、素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。 此問題的算法如下：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=la-len)&(j=lb-len) GetElem(la，I，ai); GetElem(lb，j，bj);void mergelist(list la，list l b，list &lc) InitList(lc

8、); i=j=1;k=0; la-len=ListLength(la); l b-len=ListLength(lb); while(i=la-len)&(j=lb-len) GetElem(la，i，ai); GetElem(lb，j，bj);if(ai=bj) ListInsert(lc，+k，ai);+i; else ListInsert(lc，+k，bj);+j; while(I=la-len) GetElem(la，i+，ai); ListInsert(lc，+k，ai); while(j=l b-len) GetElem(l b，j+，bj); ListInsert(lc，

9、+k，bi); 2.2 線性表的順序存儲結構一、線性表的順序映像1、線性表的順序映像:把線性表的結點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 假設線性表的每個元素需占用c個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a I )之間滿足下列關系： LOC(a i+1)=LOC(a i)+c 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC (ai)=LOC(a1)+(i-1)*c a1 a2 a3 ai-1 ai an結論：所有數(shù)據(jù)元素的存儲位

10、置均取決于第一個數(shù)據(jù)元素的存儲位置。2、順序映像的c語言描述 # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; Sqlist;注：1、由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應該用一個變量來表示線性表的長度屬性，所以我們用結構類型來定義順序表類型。 2、線性表的長度是可以變化的，但是在設計的時候先給定一個值，相應的存儲空間的大小是這個值的倍數(shù)二

11、、 順序表上實現(xiàn)的基本操作1、線性表的初始化操作 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: return OK; 2、LocateElem（L，e，compare()） Int LocateElem_sq(SqList L,ElemType e, Status (*compare)(ElemType , Elem

12、Type) i=1; p=L.elem; while(i=L.length & !(*compare)(*p+ , e) +i; if (i next ;j=1; while(p& jnext; j+; if (!p | jpos) return error; e=p-data; return ok; （2）按值查找Status GetElem(linklist L, int key，ElemType &e) p=Lnext; while( p & pdata!=key) p=pnext; if (!p) return error; else return p;

13、 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關，其平均時間復雜度的分析類似于按序號查找，也為O(n)。2、ListInsert（&L, i, e） P29基本操作：找到線性表中第i-1 個結點，修改其指向后繼的指針，并且插入新結點3、ListDelete（ &L, i, &e ）P30基本操作：找到線性表中第i-1 個結點，修改其指向后繼的指針，并釋放刪除的結點4、CreatList（LinkList &L）（1）尾插法建表 該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表尾上，直到讀入結束標志

14、為止。Void Create_L(LinkList &L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=null; p=L; for (i=1;idata); pnext=q; p=q; p-next=null; return (L); （2）頭插入法該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。 void CreatList_L(LinkList &L, int n) L=(LinkList)malloc(sizeof (LNode

15、); L-next=Null; for (i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); p-next=L-next; L-next=p; 5、用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：（1）單鏈表的表長是一個隱含的值（2）在單鏈表的最后，一個元素最后插入元素時，需要遍歷整個鏈表（3）在鏈表中，元素的“位序”概念淡化，結點的“位置”概念強化。改進鏈表的設置：增加“表長”，“表尾指針”，“當前位置的指針”三個數(shù)據(jù)域三、一個帶頭結點的線性表類型1、結點結構：Typedef struct LNode ElemT

16、ype data; struct LNode *next; *Link, *Position;2、鏈表類型：Typedef struct Link head,tail; Int len; Link current; LinkList;3、基本操作：(1) InitList（LinkList & L）(2) DestroyList(LinkList &L)(3) Prior (LinkList L) ; Next(LinkList L); GetCurElem(LinkList L); LocatePos(LinkList L , int i); LocateElem(LinkL

17、ist L,ElemType e, compare(); ListTraverse(LinkList L, Status (*visit)();(4)ClearList(LinkList &l); SetCurElem(LinkList &L,ElemType e); Append(LinkList &L, Link s) InsAfter( LinkList &L ,ElemType e); DelAfter(LinkList &L ,ElemType *e)Status InsAfter (LinkList &L, ElemType e) i

18、f (!L.current) return Error; if (!MakeNode(s,e) return Error; s-next=L.current-next; L.current-next=s; return ok;四、循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。最后一個結點的指針指向第一個結點的鏈表。單循環(huán)鏈表：在單鏈表中，將終端結點的指針域NULL改為指向表頭結點的或開始結點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。 為了使空表和非空表的處理一致，循環(huán)鏈表中也可設置一個頭結點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結點表示。如下圖所示： a1 an .head 非空表 空表例

19、、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個線性表的運算。 linklist connect(linklist taila，linklist tailb) linklist p=tailanext; tailanext=(tailbnext)next free(tailbnext); tailbnext=p; return(tailb); 五、雙鏈表1、雙向鏈表(Double linked list):在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為： typedef struct DulNode ElemType data; struct DulNode *prior，*next; DulNode,*DulNode; 設指針p指向某一結點， (pprior)next=p=(pnext)prior即結點*