第二章 線性表.ppt

1、第2章 線性表,本章主要介紹下列內(nèi)容 線性表的定義和基本操作 線性表的順序存儲結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的應(yīng)用舉例,退出,2.1 線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序存儲結(jié)構(gòu) 2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.4 線性表的應(yīng)用舉例,2.1 線性表的邏輯結(jié)構(gòu),2.1.1 線性表的定義 線性表是由n（n0）個類型相同的數(shù)據(jù)元素組成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L為線性表名稱，習(xí)慣用大寫書寫； ai為組成該線性表的數(shù)據(jù)元素，習(xí)慣用小寫書寫； 線性表中數(shù)據(jù)元素的個數(shù)被稱為線性表的長度，當(dāng)n=0時，線性表為空，又稱為空線

2、性表。,舉例 La=（34，89，765，12，90，-34，22） 數(shù)據(jù)元素類型為int。 Ls=(Hello,World, China, Welcome) 數(shù)據(jù)元素類型為string。 Lb=(book1,book2,.,book100) 數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型： struct bookinfo int No; /圖書編號 char *name; /圖書名稱 char *auther; /作者名稱 .; ,2.1.2 線性表的基本操作 線性表初始化：Init_List(L) 求線性表的長度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_

3、List(L,x) 插入操作：Insert_List(L,i,x) 刪除操作：Delete_List(L,i),2.2 線性表的順序存儲結(jié)構(gòu),2.2.1 線性表的順序存儲結(jié)構(gòu) 線性表的順序存儲結(jié)構(gòu)是指用一組連續(xù)的存儲單元依次存儲線性表中的每個數(shù)據(jù)元素。如下圖2-1所示：,圖2-1 線性表順序存儲結(jié)構(gòu)示意圖,其中，L為每個數(shù)據(jù)元素所占據(jù)的存儲單元數(shù)目。 相鄰兩個數(shù)據(jù)元素的存儲位置計算公式 LOC(ai+1)=LOC(ai)+L 線性表中任意一個數(shù)據(jù)元素的存儲位置的計算公式為： LOC(ai+1)=LOC(a1)+(i-1)*L 順序存儲結(jié)構(gòu)的特點 （1）利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)

4、元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)（物理結(jié)構(gòu)）一致；,（2）在訪問線性表時，可以利用上述給出的數(shù)學(xué)公式，快速地計算出任何一個數(shù)據(jù)元素的存儲地址。因此，我們可以粗略地認(rèn)為，訪問每個數(shù)據(jù)元素所花費的時間相等。這種存取元素的方法被稱為隨機存取法，使用這種存取方法的存儲結(jié)構(gòu)被稱為隨機存儲結(jié)構(gòu)。 在C語言中，實現(xiàn)線性表的順序存儲結(jié)構(gòu)的類型定義 #define MAXSIZE 100 /線性表的最大長度 typedef struct datatype dataMAXSIZE; int last; SeqList;,2.2.2 典型操作的算法實現(xiàn) 初始化線性表L SeqList *init_S

5、eqList( ) SeqList *L; L=malloc(sizeof(SeqList); L-last=-1; return L; ,2.在線性表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素X int Insert_SeqList(SeqList *L，int i，datatype x) int j; if (L-last=MAXSIZE1) printf(表滿); return(-1); /*表空間已滿，不能插入*/ if (iL-last+2)/*檢查插入位置的正確性*/ printf(位置錯);return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dat

6、aj; /* 結(jié)點移動 */ L-datai-1=x;/*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1);/*插入成功，返回*/ ,3. 刪除操作 int Delete_SeqList(SeqList *L;int i) int j; if(iL-last+1) /*檢查空表及刪除位置的合法性*/ printf (不存在第i個元素); return(0); for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向上移動*/ L-last-; return(1); /*刪除成功*/ ,在線性表L中檢索值為X的數(shù)據(jù)元素 int Loc

7、ation_SeqList(SeqList *L, datatype x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; /*返回的是存儲位置*/ ,插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：,刪除算法的分析 在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 分析結(jié)論 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其

8、做插入或刪除操作時，這一點需要值得考慮。,2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu),線性表順序存儲結(jié)構(gòu)的特點 它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。 暴露的問題 l在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動； l對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用； l線性表的容量難以擴充。,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每

9、個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。假設(shè)有一個線性表（a,b,c,d），可用下圖2-2所示的形式存儲：,圖2-2 線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖,術(shù)語 表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點； 其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）； 表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）。 單鏈表簡化的圖2-3描述形式,圖 2-3 單聯(lián)表結(jié)構(gòu)示意圖,其中，head是頭指針，它指向單鏈表中的第一個結(jié)點，這是單鏈表操作的入口點。由于最后一個結(jié)點沒有直接后繼結(jié)點，所以，它的指針域放入一個特殊的值NULL。NULL值在圖示中常用（）

10、符號表示。 帶頭結(jié)點的單鏈表 為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個結(jié)點之前附加一個結(jié)點，并稱為頭結(jié)點。這樣可以免去對鏈表第一個結(jié)點的特殊處理。如下圖2-4所示：,圖 2-4 帶頭結(jié)點的單鏈表結(jié)構(gòu)示意圖,鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點 （1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致； （2）在對線性表操作時，只能通過頭指針進入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，具有這種特點的存取方式被稱為順序存取方式。,在C語言中，實現(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義 typedef struct node datatype

11、data; struct node *next; LNode，*LinkList； 定義頭指針變量： LinkList H；,2.3.2 典型操作的算法實現(xiàn) (1)在鏈表的頭部插入結(jié)點建立單鏈表 LinkList Creat_LinkList1( ) LinkList L=NULL；/*空表L為表頭*/ Lnode *s; int x; /*設(shè)數(shù)據(jù)元素的類型為int*/ scanf(%d, ,2. 求表長(帶頭結(jié)點的) int Length_LinkList1 (LinkList L) Lnode * p=L; /* p指向頭結(jié)點*/ int j=0; while (p-next) p=p-n

12、ext; j+ /* p所指的是第 j 個結(jié)點*/ return j; ,3. 查找操作 (1) 按序號查找 Get_Linklist(L,i) Lnode * Get_LinkList(LinkList L, Int i); /*在單鏈表L中查找第i個元素結(jié)點，找到返回其指針，否則返回空*/ Lnode * p=L; int j=0; while (p-next !=NULL ,(2)按值查找即定位 Locate_LinkList(L,x) Lnode * Locate_LinkList( LinkList L, datatype x) /*在單鏈表L中查找值為x的結(jié)點，找到后返回其指針，否

13、則返回空*/ Lnode * p=L-next; while ( p!=NULL ,4.插入操作 int Insert_LinkList( LinkList L, int i, datatype x) /*在單鏈表L的第i個位置上插入值為x的元素*/ Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1個結(jié)點*/ if (p=NULL) printf(參數(shù)i錯);return 0; /*第i-1個不存在不能插入*/ else s=malloc(sizeof(LNode); /*申請、填裝結(jié)點*/ s-data=x; s-next=p-next; /*新結(jié)點

14、插入在第i-1個結(jié)點的后面*/ p-next=s return 1; ,5. 刪除操作 int Del_LinkList(LinkList L，int i) /*刪除單鏈表L上的第i個數(shù)據(jù)結(jié)點*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1個結(jié)點*/ if (p=NULL) printf(第i-1個結(jié)點不存在);return -1; else if (p-next=NULL) printf(第i個結(jié)點不存在);return 0; else s=p-next; /*s指向第i個結(jié)點*/ p-next=s-next; /*從鏈表中刪除*/ free(

15、s); /*釋放*s */ return 1; ,2.3.3 循環(huán)鏈表 若將鏈表中最后一個結(jié)點的next域指向 實現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結(jié)束的條件有所不同。下面我們就列舉兩個循環(huán)鏈表操作的算法示例。,圖2-7 帶頭結(jié)點的循環(huán)鏈表示意圖,2.3.4 雙向循環(huán)鏈表 在循環(huán)鏈表中，訪問結(jié)點的特點 訪問后繼結(jié)點，只需要向后走一步，而訪問前驅(qū)結(jié)點，就需要轉(zhuǎn)一圈。 結(jié)論：循環(huán)鏈表并不適用于經(jīng)常訪問前驅(qū)結(jié)點的情況。 解決方法：在需要頻繁地同時訪問前驅(qū)和后繼結(jié)點的時候，使用雙向鏈表。所謂雙向鏈表。 雙向鏈表就是每個結(jié)點有兩個指針域。一個指向后繼結(jié)點，另

16、一個指向前驅(qū)結(jié)點。,圖 2-8,(a),(b),用C語言實現(xiàn)雙向循環(huán)鏈表的類型定義 typedef struct dlnode datatype data; struct dlnode *prior,*next; DLNode,*DLinkList;,（1）在雙向循環(huán)鏈表DL中，第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e 在一個結(jié)點之前插入一個新結(jié)點的過程。 在雙向循環(huán)鏈表中的p結(jié)點之前插入s結(jié)點應(yīng)使用下列語句序列： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;,圖 2-9,雙向鏈表中結(jié)點的刪除 p-prior-next=p-next; p-

17、next-prior=p-prior; free(p);,x,x,P,2.4 線性表的應(yīng)用舉例,例22 有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。 算法思路：依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。,算法如下： void merge(SeqList A, SeqList B, SeqList *C) int i,j,k; i=0;j=0;k=0; while ( idatak+=A.datai+; else C-datak+=B.dataj+; while (idatak+= A.datai+; while (jdatak+=B.dataj+; C-last=k-1; 算法的時間復(fù)雜度是O(m+n)，其中m是A的表長，n是B的表長。,2.4 應(yīng)用舉例 例2.4 已知單鏈表H，寫一算法將其倒置。即實現(xiàn)如圖2.22的操作。(a)為