數(shù)據(jù)結(jié)構(gòu)第二章線性表課件

1、數(shù)據(jù)結(jié)構(gòu)第二章線性表1數(shù)據(jù)結(jié)構(gòu) 第二章 線性表重慶一中 葛靜數(shù)據(jù)結(jié)構(gòu)第二章線性表2數(shù)據(jù)元素之間滿足線性關系的表稱為線性表，是一種最基本、最簡單的數(shù)據(jù)結(jié)構(gòu)類型。本章討論線性表的邏輯和存儲結(jié)構(gòu)、相關算法的實現(xiàn)以及線線性表的邏輯和存儲結(jié)構(gòu)、相關算法的實現(xiàn)以及線性表應用舉例。性表應用舉例。2.1線性表的定義及基本操作線性表的定義及基本操作2.1.1 定義：定義：線性表(Linear List)是若干數(shù)據(jù)元素的一個線性序列，記為：L=(a1,ai-1aiai+1an)其中：L為表名，ai(1in)為數(shù)據(jù)元素；n為表長，n0 時，L為非空表，否則為空表。2.1.2 線性表的邏輯結(jié)構(gòu)和特征線性表的邏輯結(jié)構(gòu)和

2、特征 線性表L可用二元組形式描述： L= (D,R)數(shù)據(jù)元素集合: D=ai | aidatatype ,i=1,2, n ,n0關系集合: R= | ai , ai+1D, 1in-1表長n=0時，L為空表；關系符在這里稱為有序?qū)?，表示任意相鄰的兩個元素之間的一種先后次序關系，稱ai是ai+1的直接前驅(qū), ai+1是ai的直接后繼，當表長n1時，關系集R為空集。數(shù)據(jù)結(jié)構(gòu)第二章線性表3例2-1 線性表的例子 L1=(A,B,Z) 元素為字符； L2=(6,7, ,105) 元素為整數(shù)；學生記錄表： 線性表的特征：對非空表線性表的特征：對非空表,a1是表頭是表頭,無前驅(qū)；無前驅(qū)；an是表尾是表尾

3、,無后繼；其它的每個元無后繼；其它的每個元素素ai有且僅有一個直接前驅(qū)有且僅有一個直接前驅(qū)(ai-1)和一個直接后繼和一個直接后繼(ai+1)。2.1.3 線性表的抽象數(shù)據(jù)類型表示線性表的抽象數(shù)據(jù)類型表示 設線性表 L=(a1,a2, ,an)，對 L的抽象數(shù)據(jù)類型表示： 學 號 姓 名性 別 年 齡班 級 -J99001丁蘭女19計99-J99002王林男20計99-J99032馬紅女18計99-a1a2.a32數(shù)據(jù)結(jié)構(gòu)第二章線性表4線性表的抽象數(shù)據(jù)類型表示ADT List 數(shù)據(jù)元素集：D=ai|aidatatype,i=1,2, n,n0數(shù)據(jù)關系集：R=|ai,ai+1D,1in-1 基本

4、操作集：P(置表空、求表長、插入、刪除、查找一個元素等) 數(shù)據(jù)結(jié)構(gòu)第二章線性表52.2.1 順序表若將線性表L=(a0,a1, ,an-1)中的各元素依次存儲于計算機一片連續(xù)的存儲空間，如圖2.2所示。這種機內(nèi)表示為線性表的順序存儲結(jié)構(gòu)(順序表)。 地址： b: 占d個單元 b+d: 設Loc(ai)為ai的地址，Loc(a1)= b，則： Loc(a2)=b+1*d b+（i-1）*d: . Loc(ai)=b+（i-1）*d b+（n-1)*d: 圖圖2.2順序表的特點順序表的特點：(1)邏輯上相鄰的元素 ai, ai+1，存儲位置也是相鄰的；(2)對ai的存取為隨機存取或按地址存取。(3

5、)存儲密度高。存儲密度D=(數(shù)據(jù)結(jié)構(gòu)中元素所占存儲空間)/(整個數(shù)據(jù)結(jié)構(gòu)所占空間)。順序表的不足順序表的不足：對表的插入和刪除等運算的時間復雜度較差。 a1 a2 aian數(shù)據(jù)結(jié)構(gòu)第二章線性表6線性表的順序存儲Type list=record vec:array1.m0 of elemtype; len:integer;End;Var L:list;1、setnull(L) L.len:=0; 操作結(jié)果：構(gòu)造一個空的線性表L。2、length(L) return(L.Len);初始條件：線性表L存在。操作結(jié)果：返回L中的元素個數(shù)。3、向線性表的第i個元素插入一個元素步驟： （1）檢查存儲空間是

6、否已經(jīng)滿，若滿，則“溢出”。 （2）檢查i是否超范圍1=i=n+1,若是，則“超出范圍” （3）將線性表中第i個元素和后面所有元素均后移一位。 （4）將新元素寫在第i個位置上。 （5）線性表長度加1. a1 ai an數(shù)據(jù)結(jié)構(gòu)第二章線性表7線性表的抽象數(shù)據(jù)類型表示3、向線性表的第i個元素插入一個元素的算法描述Insert(L,i,x);Begin if L.len=m0 then writeln(overflow); if (iL.len+1) then writeln(out of range); for j:=L.len downto i do L.vecj+1:=L.vecj; L.ve

7、ci=x; L.len:=L.len+1;End;算法復雜度分析：算法第1、2步根據(jù)情況可省略。時間復雜度主要取決于第3步，即for循環(huán)的次數(shù)，也就是向后移動的元素個數(shù)。當i=n+1時，最好情況,元素不移動,當i=1時，最壞情況，移動n次。假定在線性表的任何位置上插入元素的概率相同，為pi=1/(n+1),1=i=n+1,則元素平均移動的次數(shù)為：Pi(n+n-1+n-2+0)=pi (n(n+1)/2)=n/2故最壞和平均O(n)數(shù)據(jù)結(jié)構(gòu)第二章線性表8線性表的抽象數(shù)據(jù)類型表示4、刪除線性表的第i個元素算法步驟： （1）檢查1=i=n,若不是，則“超出范圍” （2）若刪除的元素有用，則把第i個元

8、素賦值給變參帶回。 （3）把第i個元素后面所有的元素前移一位。 （4）線性表長度減1。算法描述：Delete(L,i,x);Begin if(in) then writeln(out of range); x:=L.vexi; for j:=i+1 to L.len do L.vecj-1:=L.vecj; L.len:=L.len-1;End; 時間復雜度分析：最壞，i=n時，不移動元素，i=1時，移動n-1個元素。刪除任意元素等概率情況下1/n，1/n(0+1+2+n-1)=1/n(n(n-1)/2)=(n-1)/2故最壞和平均O(n)數(shù)據(jù)結(jié)構(gòu)第二章線性表9線性表的抽象數(shù)據(jù)類型表示5、刪除

9、給定值等于x的第一個元素。算法步驟： （1）從線性表的起始元素開始，根X 比較，直到X等于某個元素值（查找成功），或者查完所有元素仍找不到（查找失?。?。 （2）若查找失敗，則“沒有找到”錯誤處理。 （3）刪除其值等于x的元素。 （4）線性表長度減1；算法描述：Delete(L,x);Begin i:=1; while (i=n)and(L.vecix) do inc(i); if in then writeln(not find) else for j:=i+1 to L.len do L.vecj-1:=L.vecj; dec(L.len);End;O(n)數(shù)據(jù)結(jié)構(gòu)第二章線性表10線性表的操

10、作以上運算是對線性表L施加的一些基本運算，對線性表L的運算還有： 合并、拆分、復制、排序合并、拆分、復制、排序等等。例例2-2 設線性表La=(a1a2, ,am), Lb= (b1b2, ,bn)，求LaLb =La，如圖2.1所示。算法思路算法思路：依次取Lb中的bi(i=1,2,n)，若bi不在La中，則將其插入。算法描述算法描述： procedure Union(La, Lb:list);begin var i,x:integer; k:boolean; for i:=1 to Lb.len do begin x:=Lb.veci; k:=locateLa,x;判斷x是否在La中，自定

11、義函數(shù) if not k then insert(La,x); end;類似可寫出求LaLb , LaLb等運算的算法。 1 3 5 7La 5 7 9 11 Lb數(shù)據(jù)結(jié)構(gòu)第二章線性表11線性表的操作例例2-3 設計清除線性表L=(a1,a2,-,ai,-,an)中重復元素的算法。算法思路算法思路：對當前表L中的每個ai（1in-1），依次與aj(i+1jn) 比較，若與ai相等，則刪除之。算法描述算法描述：procedure Purge(var L:list) begin for i:=1 to L.len-1 do for j:=i+1 to L.len do if L.veci=L.ve

12、cj then delete(L,j)；delete函數(shù)表示從L中刪除第j位上的元素 end;初始：L=（1，3，1，5，3，5，7） i j結(jié)果：L=（1，3，5，7）數(shù)據(jù)結(jié)構(gòu)第二章線性表12 2.3 線性表的鏈式存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)有存儲密度高及能夠隨機存取等優(yōu)點，但存在以下幾點不足：(1)插入、刪除等運算耗時，且存在元素在存儲器中成片移動的現(xiàn)象；(2)要求系統(tǒng)提供一片較大的連續(xù)存儲空間。下面討論線性表的鏈式存儲結(jié)構(gòu)，即鏈表。是第二章的重點。2.3.1單鏈表單鏈表將線性表L=(a1,a2,an)中各元素分布在存儲器的不同存儲塊，稱為節(jié)點，通過地址或指針建立它們之間的聯(lián)系，所得到的存

13、儲結(jié)構(gòu)為鏈表結(jié)構(gòu)。表中元素ai的節(jié)點形式如圖2.4所示。 圖圖2.4其中，data域存放數(shù)據(jù)元素ai，而next域是一個指針，指向ai的直接后繼ai+1所在的節(jié)點。于是，線性表L=( a1,a2,an)的結(jié)構(gòu)如圖2.5所示: data next a1 a2 an L .數(shù)據(jù)結(jié)構(gòu)第二章線性表13單鏈表例例2-4 設線性表L=(趙，錢，孫，李，周，吳，鄭，王)，各元素在存儲器中的分布如圖2.6所示。 地址地址dataNext100李李142106錢錢112112孫孫100118王王NULL124吳吳136130趙趙106136鄭鄭118142周周124 圖圖2.6帶頭節(jié)點的單鏈表：帶頭節(jié)點的單鏈表

14、： a1 an L L趙趙錢錢孫孫吳吳鄭鄭王王周周李李數(shù)據(jù)結(jié)構(gòu)第二章線性表14單鏈表節(jié)點描述：type link=node; node=record data:elemtype; next:link; end; 若說明var A:node; p:link; 則結(jié)構(gòu)變量A為所描述的節(jié)點，而指針變量p為指向此類型節(jié)點的指針（或p的值為節(jié)點的地址），如圖2.8所示: 設p指向鏈表中節(jié)點ai，如圖2.9所示:獲取ai，寫作：p.data；而取ai+1,寫作：p.next.data。 另外，若指針p的值為NULL，則它不指向任何節(jié)點, 此時取p.data或p.next是錯誤的。 data next P

15、A： aiai+1 P數(shù)據(jù)結(jié)構(gòu)第二章線性表152.3.2單鏈表的基本操作可調(diào)用pascal中new(p)函數(shù)向編譯系統(tǒng)申請節(jié)點的存儲空間，若說明：Var var p:link; new(p); 則獲得了一個類型為node的節(jié)點，且該節(jié)點的地址已存入指針變量P中：1建立單鏈表建立單鏈表算法思路算法思路：依次讀入L=(a1,.,an)中每一ai(設為整型)，若i=n，則將ai形成一節(jié)點，鏈入表尾，最后返回鏈表的頭節(jié)點指針H。算法描述算法描述：procedure create; var p,q,h:link; I,j:integer; begin i:=1;readln(x);new(p);p.da

16、ta:=x;p.next:=nil; q:=p;h:=p;inc(i); while i=n do begin readln(x); new(p); p.data:=x; p.next:=nil; q.next:=p; q:=p; end; end; data next P 數(shù)據(jù)結(jié)構(gòu)第二章線性表16設L=(2，4，8)，則建表過程如下：設表長為n，顯然此算法的時間復雜度為T(n)=O(n)。從此算法可以看到，鏈表的結(jié)構(gòu)是動態(tài)形成的，即算法運行前，表結(jié)構(gòu)是不存在的，而通過算法的運行，得到一個如圖所示的單鏈表。2鏈表查找鏈表查找 在單鏈表中查找即實現(xiàn)GetElem(L,k)。算法思路算法思路：從表

17、頭第一個結(jié)點起，依次使每個結(jié)點的關鍵字同給定的的值K進行比較，直到某個結(jié)點的關鍵字等于給定值K(查找成功)，或查找的表尾（查找失敗）為止。算法描述算法描述：function locate(H,k):boolean; begin p:=h; while pnil do if p.datak then p:=p.next else begin locate:=true;q:=p;break;end;q返回被查找元素的地址 end; 建立單鏈表H248數(shù)據(jù)結(jié)構(gòu)第二章線性表173前插前插 即實現(xiàn)ListInsert(L, i, e)。討論將x插入表中節(jié)點ai之前的情況。算法思路算法思路：調(diào)用算法Get

18、Elem(H,i-1)，獲取節(jié)點ai-1的指針p(ai 之前驅(qū))，然后申請一個q節(jié)點，存入e，并將其插入p節(jié)點之后。插入時的指針變化如圖2.14所示。 圖圖2.14算法描述算法描述：q.next:=p.next; p.next:=q;此算法的時間主要花費在函數(shù)Getlist(H,i-1)上，故T(n)=O(n)，但插入時未引起元素的移動，這一點優(yōu)于順序結(jié)構(gòu)的插入。Ha1ai anai-1Pe q數(shù)據(jù)結(jié)構(gòu)第二章線性表18單鏈表刪除4刪除刪除 即實現(xiàn)ListDel(L,i)。圖圖2.15 算法思路算法思路：同插入法，先調(diào)用函數(shù)GetElem(H,i-1),找到節(jié)點ai的前驅(qū)，然后如圖2.15所示，

19、將節(jié)點ai刪除之。算法描述算法描述：p.next:=q.next; dispose(q)同插入法，此算法的T(n)=O(n)。Ha0ai ai-1Pai+1q數(shù)據(jù)結(jié)構(gòu)第二章線性表19線性表的存儲結(jié)構(gòu)n順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用數(shù)組類型： list: array 1.max of elemtp ;n動態(tài)鏈式存儲結(jié)構(gòu)動態(tài)鏈式存儲結(jié)構(gòu) 用指針類型： point = p_list ; p_list = record data : elemtp ; next: point ; end;n靜態(tài)鏈式存儲結(jié)構(gòu)靜態(tài)鏈式存儲結(jié)構(gòu)type statinode=record data:elemtype; next:

20、integer; end; var a:array1.maxof statinode;abcdeacaebd54013bcde數(shù)據(jù)結(jié)構(gòu)第二章線性表20比較一下方案邏輯結(jié)構(gòu)物理結(jié)構(gòu)特點無序數(shù)組無序線性表數(shù)組差無序鏈表鏈表插入快有序數(shù)組有序線性表數(shù)組查找快有序鏈表鏈表比較平衡數(shù)據(jù)結(jié)構(gòu)第二章線性表21線性表的典型實例線性表的典型實例n約瑟夫問題約瑟夫問題nM個人圍成一圈，從第一個人開始報數(shù)，數(shù)到個人圍成一圈，從第一個人開始報數(shù)，數(shù)到N的人的人出圈；再由下一個人開始報數(shù)，數(shù)到出圈；再由下一個人開始報數(shù)，數(shù)到N(N1)的人出的人出圈；圈；.。輸出依次出圈的人的編號。輸出依次出圈的人的編號。M的值預先的值預先選定，選定，N由鍵盤輸入。由鍵盤輸入。n分析：要解決這道問題，首先需要構(gòu)造一個環(huán)表，構(gòu)分析：要解決這道問題，首先需要構(gòu)造一個環(huán)表，構(gòu)造環(huán)的方法很簡單，只要存儲每個人的下一個即可，造環(huán)的方法很簡單，只要存儲每個人的下一個即可，當然，最后一個人的下一個就是第一個人，這樣就構(gòu)當然，最后一個人的下一個就是第一個人，這樣就構(gòu)成了一個環(huán)，構(gòu)造環(huán)以后，就可進行刪除操作，直到成了一個環(huán)，構(gòu)造環(huán)以后，就可進行刪除操作，直到環(huán)剩下一個人為止。環(huán)剩下一個人為止。數(shù)據(jù)結(jié)構(gòu)第二章線性表22約瑟夫問題(采用鏈表)write(m & n:); readln(m,n);