第二章 線性表.ppt

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

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; /圖書編號(hào) char *name; /圖書名稱 char *auther; /作者名稱 .; ,2.1.2 線性表的基本操作 線性表初始化：Init_List(L) 求線性表的長(zhǎng)度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_

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

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

5、eqList( ) SeqList *L; L=malloc(sizeof(SeqList); L-last=-1; return L; ,2.在線性表L中第i個(gè)數(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(位置錯(cuò));return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dat

6、aj; /* 結(jié)點(diǎn)移動(dòng) */ 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個(gè)元素); return(0); for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向上移動(dòng)*/ 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; /*返回的是存儲(chǔ)位置*/ ,插入算法的分析 假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：,刪除算法的分析 在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： 分析結(jié)論 順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其

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

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

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

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

12、ext; j+ /* p所指的是第 j 個(gè)結(jié)點(diǎn)*/ return j; ,3. 查找操作 (1) 按序號(hào)查找 Get_Linklist(L,i) Lnode * Get_LinkList(LinkList L, Int i); /*在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，找到返回其指針，否則返回空*/ 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é)點(diǎn)，找到后返回其指針，否

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

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

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

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

17、next-prior=p-prior; free(p);,x,x,P,2.4 線性表的應(yīng)用舉例,例22 有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也是從小到大的升序排列。 算法思路：依次掃描通過(guò)A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表相加的長(zhǎng)度。,算法如下： 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; 算法的時(shí)間復(fù)雜度是O(m+n)，其中m是A的表長(zhǎng)，n是B的表長(zhǎng)。,2.4 應(yīng)用舉例 例2.4 已知單鏈表H，寫一算法將其倒置。即實(shí)現(xiàn)如圖2.22的操作。(a)為