《數(shù)據(jù)結(jié)構(gòu)線性表PPTPPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)線性表PPTPPT課件.ppt（109頁珍藏版）》請在匯文網(wǎng)上搜索。

1、第2章 線性表 2.1 線性表的基本概念 2.2 線性表的順序存儲2.3 線性表的鏈?zhǔn)酱鎯?.4 線性表的應(yīng)用 本章小結(jié) 2.5 有序表 12.1 線性表的基本概念 2.1.1 線性表的定義2.1.2 線性表的運(yùn)算22.1.1 線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。該序列中所含元素的個數(shù)叫做線性表的長度,用n表示,n0。當(dāng)n=0時,表示線性表是一個空表,即表中不包含任何元素。設(shè)序列中第i(i表示位序)個元素為ai(1in)。線性表的一般表示為:(a1,a2,ai,ai+1,an)3 其中a1為第一個元素,又稱做表頭元素,a2為第二個元素,an為最后一個元素,又稱做表尾元素

2、。例如,在線性表 (1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。42.1.2 線性表的運(yùn)算 線性表的基本運(yùn)算如下:(1)初始化線性表InitList(&L):構(gòu)造一個空的線性表L。(2)銷毀線性表DestroyList(&L):釋放線性表L占用的內(nèi)存空間。5 (3)判線性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。(4)求線性表的長度ListLength(L):返回L中元素個數(shù)。(5)輸出線性表DispList(L):當(dāng)線性表L不為空時,順序顯示L中各結(jié)點的值域。(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e):用e返回L中第

3、i(1iListLength(L)個元素的值。6 (7)定位查找LocateElem(L,e):返回L中第1個值域與e相等的位序。若這樣的元素不存在,則返回值為0。(8)插入數(shù)據(jù)元素ListInsert(&L,i,e):在L的第i(1iListLength(L)+1)個元素之前插入新的元素e,L的長度增1。(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):刪除L的第i(1iListLength(L)個元素,并用e返回其值,L的長度減1。7 例2.1 假設(shè)有兩個集合 A 和 B 分別用兩個線性表 LA 和 LB 表示,即線性表中的數(shù)據(jù)元素即為集合中的成員。編寫一個算法求一個新的集合C=A

4、B,即將兩個集合的并集放在線性表LC中。解:本算法思想是:先初始化線性表LC,將LA的所有元素復(fù)制到LC中,然后掃描線性表LB,若LB的當(dāng)前元素不在線性表LA中,則將其插入到LC中。算法如下:8void unionList(List LA,List LB,List&LC)int lena,lenc,i;ElemType e;InitList(LC);for(i=1;i=ListLength(LA);i+)/*將LA的所有元素插入到Lc中*/GetElem(LA,i,e);ListInsert(LC,i,e);lena=ListLength(LA);/*求線性表的長度*/lenB=ListLen

5、gth(LB);9for(i=1;i=lenb;i+)GetElem(LB,i,e);/*取LB中第i個數(shù)據(jù)元素賦給e*/if (!LocateElem(LA,e)ListInsert(LC,+lenc,e);/*LA中不存在和e相同者,則插入到LC中*/10 由于LocateElem(LA,e)運(yùn)算的時間復(fù)雜度為O(ListLength(LA),所以本算法的時間復(fù)雜度為:O(ListLength(LA)*ListLength(LB)。112.2 線性表的順序存儲2.2.1 線性表的順序存儲順序表2.2.2 順序表基本運(yùn)算的實現(xiàn)122.2.1 線性表的順序存儲順序表 線性表的順序存儲結(jié)構(gòu)就是:

6、把線性表中的所有元素按照其邏輯順序依次存儲到從計算機(jī)存儲器中指定存儲位置開始的一塊連續(xù)的存儲空間中。這樣,線性表中第一個元素的存儲位置就是指定的存儲位置,第i+1個元素(1in-1)的存儲位置緊接在第i個元素的存儲位置的后面。線性表 邏輯結(jié)構(gòu)順序表 存儲結(jié)構(gòu)13 假定線性表的元素類型為ElemType,則每個元素所占用存儲空間大小(即字節(jié)數(shù))為sizeof(ElemType),整個線性表所占用存儲空間的大小為:n*sizeof(ElemType)其中,n表示線性表的長度。14順序表示意圖15 在定義一個線性表的順序存儲類型時,需要定義一個數(shù)組來存儲線線表中的所有元素和定義一個整型變量來存儲線性

7、表的長度。假定數(shù)組用dataMaxSize表示,長度整型變量用length表示,并采用結(jié)構(gòu)體類型表示,則元素類型為通用類型標(biāo)識符ElemType的線性表的順序存儲類型可描述如下:16 typedef struct ElemType dataMaxSize;int length;SqList;/*順序表類型*/其中,data成員存放元素,length成員存放線性表的實際長度。說明：由于C/C+中數(shù)組的下標(biāo)從0開始，線性表的第i個元素ai存放順序表的第i-1位置上。為了清楚，將ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。172.2.2 順序表基本運(yùn)算的實現(xiàn) 一旦采用順序表存儲

8、結(jié)構(gòu),我們就可以用C/C+語言實現(xiàn)線性表的各種基本運(yùn)算。為了方便,假設(shè)ElemType為char類型,使用如下自定義類型語句:typedef char ElemType;181.建立順序表其方法是將給定的含有n個元素的數(shù)組的每個元素依次放入到順序表中，并將n賦給順序表的長度成員。算法如下：void CreateList(SqList*&L,ElemType a,int n)/*建立順序表*/int i;L=(SqList*)malloc(sizeof(SqList);for(i=0;idatai=ai;L-length=n;192.順序表基本運(yùn)算算法(1)初始化線性表InitList(L)該運(yùn)

9、算的結(jié)果是構(gòu)造一個空的線性表L。實際上只需將length成員設(shè)置為0即可。void InitList(SqList*&L)/引用型指針 L=(SqList*)malloc(sizeof(SqList);/*分配存放線性表的空間*/L-length=0;本算法的時間復(fù)雜度為O(1)。順序表L20 (2)銷毀線性表DestroyList(L)該運(yùn)算的結(jié)果是釋放線性表L占用的內(nèi)存空間。void DestroyList(SqList*&L)free(L);本算法的時間復(fù)雜度為O(1)。21 (3)判定是否為空表ListEmpty(L)該運(yùn)算返回一個值表示L是否為空表。若L為空表,則返回1,否則返回0。

10、int ListEmpty(SqList*L)return(L-length=0);本算法的時間復(fù)雜度為O(1)。22 (4)求線性表的長度ListLength(L)該運(yùn)算返回順序表L的長度。實際上只需返回length成員的值即可。int ListLength(SqList*L)return(L-length);本算法的時間復(fù)雜度為O(1)。23 (5)輸出線性表DispList(L)該運(yùn)算當(dāng)線性表L不為空時,順序顯示L中各元素的值。void DispList(SqList*L)int i;if(ListEmpty(L)return;for(i=0;ilength;i+)printf(%c,L

11、-datai);printf(n);24 本算法中基本運(yùn)算為for循環(huán)中的printf語句,故時間復(fù)雜度為:O(L-length)或O(n)25 (6)求某個數(shù)據(jù)元素值GetElem(L,i,e)該運(yùn)算返回L中第 i(1iListLength(L)個元素的值,存放在e中。int GetElem(SqList*L,int i,ElemType&e)if(iL-length)return 0;e=L-datai-1;return 1;本算法的時間復(fù)雜度為O(1)。26 (7)按元素值查找LocateElem(L,e)該運(yùn)算順序查找第1個值域與e相等的元素的位序。若這樣的元素不存在,則返回值為0。i

12、nt LocateElem(SqList*L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;else return i+1;27 本算法中基本運(yùn)算為while循環(huán)中的i+語句,故時間復(fù)雜度為:O(L-length)或O(n)28 (8)插入數(shù)據(jù)元素ListInsert(L,i,e)該 運(yùn) 算 在 順 序 表 L的 第 i個 位 置(1iListLength(L)+1)上插入新的元素e。思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將順序表原來第i個元素及以后元素均后移一個位置,騰出一個空位置插入新元素

13、,順序表長度增1。29 int ListInsert(SqList*&L,int i,ElemType e)int j;if(iL-length+1)return 0;i-;/*將順序表邏輯位序轉(zhuǎn)化為elem下標(biāo)即物理位序*/for(j=L-length;ji;j-)L-dataj=L-dataj-1;/*將datai及后面元素后移一個位置*/L-datai=e;L-length+;/*順序表長度增1*/return 1;a0ai-1aian-1邏輯位序1 i i+1 n MaxSize 30 對于本算法來說,元素移動的次數(shù)不僅與表長L.length=n有關(guān),而且與插入位置i有關(guān):當(dāng)i=n+1

14、時,移動次數(shù)為0；當(dāng)i=1時,移動次數(shù)為n,達(dá)到最大值。在線性表sq中共有n+1個可以插入元素的地方。假設(shè)pi(=)是在第i個位置上插入一個元素的概率,則在長度為n的線性表中插入一個元素時所需移動元素的平均次數(shù)為:因此插入算法的平均時間復(fù)雜度為O(n)。31 (9)刪除數(shù)據(jù)元素ListDelete(L,i,e)刪除順序表L中的第i(1iListLength(L)個元素。思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將線性表第i個元素以后元素均向前移動一個位置,這樣覆蓋了原來的第i個元素,達(dá)到刪除該元素的目的,最后順序表長度減1。32int ListDelete(SqList*&L,int i,

15、ElemType&e)int j;if(iL-length)return 0;i-;/*將順序表邏輯位序轉(zhuǎn)化為elem下標(biāo)即物理位序*/e=L-datai;for(j=i;jlength-1;j+)L-dataj=L-dataj+1;/*將datai之后的元素后前移一個位置*/L-length-;/*順序表長度減1*/return 1;a0ai-1aian-1邏輯位序1 i i+1 n MaxSize 33 對于本算法來說,元素移動的次數(shù)也與表長n和刪除元素的位置i有關(guān):當(dāng)i=n時,移動次數(shù)為0；當(dāng)i=1時,移動次數(shù)為n-1。在線性表sq中共有n個元素可以被刪除。假設(shè)pi(pi=)是刪除第i個

16、位置上元素的概率,則在長度為n的線性表中刪除一個元素時所需移動元素的平均次數(shù)為:=因此刪除算法的平均時間復(fù)雜度為O(n)。34 例2.2 設(shè)計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu)即順序表)的適當(dāng)位置上,并保持線性表的有序性。解:先通過比較在順序表L中找到存放x的位置i,然后將x插入到L.datai中,最后將順序表的長度增1。35 void Insert(SqList*&L,ElemType x)int i=0,j;while(ilength&L-datailength-1;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;查

17、找插入位置元素后移一個位置a0ai-1aian-1邏輯位序1 i i+1 n MaxSize 36 例2.3 設(shè)計一個算法,將兩個元素有序(從小到大)的順序表合并成一個有序順序表。求解思路:將兩個順序表進(jìn)行二路歸并。37歸并到順序表r中 k記錄r中元素個數(shù) 1(i=0)2(j=0)將1(i=1)插入r(k=1)3(i=1)2(j=0)將2(j=1)插入r(k=2)3(i=1)4(j=1)將3(i=2)插入r(k=3)5(i=2)4(j=1)將4(j=2)插入r(k=4)5(i=2)10(j=2)將5(j=3)插入r(k=5)將q中余下元素插入r中。順序表p：135i順序表q：241020j順序

18、表r：1k38SqList*merge(SqList *p,SqList *q)SqList*r;int i=0,j=0,k=0;r=(SqList*)malloc(sizeof(SqList);while(ilength&jlength)if(p-datai dataj)r-datak=p-datai;i+;k+;else r-datak=q-dataj;j+;k+;39while(ilength)r-datak=p-datai;i+;k+;while(jlength)r-datak=q-dataj;j+;k+;r-length=k;/*或p-length+q-length*/return(

19、r);40 例2.4 已知長度為n的線性表A采用順序存儲結(jié)構(gòu),編寫一個時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。解:用k記錄順序表A中等于item的元素個數(shù),邊掃描A邊統(tǒng)計k,并將不為item的元素前移k個位置,最后修改A的長度。對應(yīng)的算法如下:41void delnode1(SqList&A,ElemType item)int k=0,i;/*k記錄值不等于item的元素個數(shù)*/for (i=0;iA.length;i+)if(A.datai!=item)A.datak=A.datai;k+;/*不等于item的元素增1*/A.lengt

20、h=k;/*順序表A的長度等于k*/算法1：類似于建順序表42void delnode2(SqList&A,ElemType item)int k=0,i=0;/*k記錄值等于item的元素個數(shù)*/while(inext=NULL;for(i=0;idata=ai;s-next=L-next;/*將*s插在原開始結(jié)點之前,頭結(jié)點之后*/L-next=s;56adc bi=0i=1i=2i=3 head采用頭插法建立單鏈表的過程heada headda headcda headbcda 第1步:建頭結(jié)點第2步:i0,新建a結(jié)點,插入到頭結(jié)點之后第3步:i1,新建d結(jié)點,插入到頭結(jié)點之后第4步:i

21、2,新建c結(jié)點,插入到頭結(jié)點之后第5步:i3,新建b結(jié)點,插入到頭結(jié)點之后57 (2)尾插法建表 頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點插到當(dāng)前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點。采用尾插法建表的算法如下:58 void CreateListR(LinkList*&L,ElemType a,int n)LinkList*s,*r;int i;L=(LinkList*)malloc(sizeof(LinkList);/*創(chuàng)建頭結(jié)點*/r=L;/*r始終指向終端結(jié)點,開始時

22、指向頭結(jié)點*/for(i=0;idata=ai;r-next=s;/*將*s插入*r之后*/r=s;r-next=NULL;/*終 端 結(jié) 點 next域 置 為NULL*/59bcdai=0i=1i=2i=3head頭結(jié)點adcb b采用尾插法建立單鏈表的過程602.插入結(jié)點運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點插入到單鏈表的第i個結(jié)點的位置上。先在單鏈表中找到第i-1個結(jié)點,再在其后插入新結(jié)點。單鏈表插入結(jié)點的過程如下圖所示。61插入結(jié)點示意圖62 3.刪除結(jié)點運(yùn)算 刪除運(yùn)算是將單鏈表的第i個結(jié)點刪去。先在單鏈表中找到第i-1個結(jié)點,再刪除其后的結(jié)點。刪除單鏈表結(jié)點的過程如下圖所示。63刪除結(jié)點

23、示意圖64 4.線性表基本運(yùn)算實現(xiàn) (1)初始化線性表InitList(L)該運(yùn)算建立一個空的單鏈表,即創(chuàng)建一個頭結(jié)點。void InitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/*創(chuàng)建頭結(jié)點*/L-next=NULL;65 (2)銷毀線性表DestroyList(L)釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點的空間。void DestroyList(LinkList*&L)LinkList*p=L,*q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);66 (3)判線性

24、表是否為空表ListEmpty(L)若單鏈表L沒有數(shù)據(jù)結(jié)點,則返回真,否則返回假。int ListEmpty(LinkList*L)return(L-next=NULL);67 (4)求線性表的長度ListLength(L)返回單鏈表L中數(shù)據(jù)結(jié)點的個數(shù)。int ListLength(LinkList*L)LinkList*p=L;int i=0;while(p-next!=NULL)i+;p=p-next;return(i);68 (5)輸出線性表DispList(L)逐一掃描單鏈表L的每個數(shù)據(jù)結(jié)點,并顯示各結(jié)點的data域值。void DispList(LinkList*L)LinkList

25、*p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);69 (6)求 線 性 表 L中 指 定 位 置 的 某 個 數(shù) 據(jù) 元 素GetElem(L,i,&e)思路：在單鏈表L中從頭開始找到第 i個結(jié)點,若存在第i個數(shù)據(jù)結(jié)點,則將其data域值賦給變量e。70 int GetElem(LinkList*L,int i,ElemType&e)int j=0;LinkList*p=L;while(jnext;if(p=NULL)return 0;/*不存在第i個數(shù)據(jù)結(jié)點*/else /*存在第i個數(shù)據(jù)結(jié)點*/e=p-data;re

26、turn 1;71 (7)按元素值查找LocateElem(L,e)思路：在單鏈表L中從頭開始找第1個值域與e相等的結(jié)點,若存在這樣的結(jié)點,則返回位置,否則返回0。int LocateElem(LinkList*L,ElemType e)LinkList*p=L-next;int n=1;while(p!=NULL&p-data!=e)p=p-next;n+;if(p=NULL)return(0);else return(n);72 (8)插入數(shù)據(jù)元素ListInsert(&L,i,e)思路：先在單鏈表L中找到第i-1個結(jié)點*p,若存在這樣的結(jié)點,將值為e的結(jié)點*s插入到其后。int List

27、Insert(LinkList*&L,int i,ElemType e)int j=0;LinkList*p=L,*s;while(jnext;73if(p=NULL)return 0;/*未找到位序為i-1的結(jié)點*/else/*找到位序為i-1的結(jié)點*p*/s=(LinkList*)malloc(sizeof(LinkList);/*創(chuàng)建新結(jié)點*s*/s-data=e;s-next=p-next;/*將*s插入到*p之后*/p-next=s;return 1;74 (9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)思路：先在單鏈表L中找到第i-1個結(jié)點*p,若存在這樣的結(jié)點,且也存在后

28、繼結(jié)點,則刪除該后繼結(jié)點。int ListDelete(LinkList*&L,int i,ElemType&e)int j=0;LinkList*p=L,*q;while(jnext;75if(p=NULL)return 0;/*未找到位序為i-1的結(jié)點*/else/*找到位序為i-1的結(jié)點*p*/q=p-next;/*q指向要刪除的結(jié)點*/if(q=NULL)return 0;/*若不存在第i個結(jié)點,返回0*/p-next=q-next;/*從單鏈表中刪除*q結(jié)點*/free(q);/*釋放*q結(jié)點*/return 1;76 例2.5 設(shè)C=a1,b1,a2,b2,an,bn為一線性表,采

29、用帶頭結(jié)點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得:A=a1,a2,an,B=b1,b2,bn 77 解:設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放。先建立兩個頭結(jié)點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾,用p指針掃描單鏈表hc,將當(dāng)前結(jié)點*p鏈到ha未尾,p沿next域下移一個結(jié)點,若不為空,則當(dāng)前結(jié)點*p鏈到hb未尾,p沿next域下移一個結(jié)點,如此這樣,直到p為空。最后將兩個尾結(jié)點的next域置空。對應(yīng)算法如下:78 void fun(LinkList*hc,LinkList*&ha,LinkList*&hb)LinkL

30、ist*p=hc-next,*ra,*rb;ha=hc;/*ha的頭結(jié)點利用hc的頭結(jié)點*/ra=ha;/*ra始終指向ha的末尾結(jié)點*/hb=(LinkList*)malloc(sizeof(LinkList);/*創(chuàng)建hb頭結(jié)點*/rb=hb;/*rb始終指向hb的末尾結(jié)點*/79 while(p!=NULL)ra-next=p;ra=p;/*將*p鏈到ha單鏈表未尾*/p=p-next;if(p!=NULL)rb-next=p;rb=p;/*將*p鏈到hb單鏈表未尾*/p=p-next;ra-next=rb-next=NULL;/*兩個尾結(jié)點的next域置空*/80 本算法實際上是采用尾

31、插法建立兩個新表。所以,尾插法建表算法是很多類似習(xí)題的基礎(chǔ)！81 例2.6 有一個帶頭結(jié)點的單鏈表head,其ElemType類型為char,設(shè)計一個算法使其元素遞增有序。解:若原單鏈表中有一個或以上的數(shù)據(jù)結(jié)點,先構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表(只含一個數(shù)據(jù)結(jié)點的單鏈表一定是有序表)。掃描原單鏈表余下的結(jié)點*p(直到p=NULL為止),在有序表中通過比較找插入*p的前驅(qū)結(jié)點*q,然后將*p插入到*q之后(這里實際上采用的是直接插入排序方法)。82 void Sort(LinkList*&head)LinkList*p=head-next,*q,*r;if(p!=NULL)/*head有一個或以上

32、的數(shù)據(jù)結(jié)點*/r=p-next;/*r保存*p結(jié)點后繼結(jié)點的指針*/p-next=NULL;/*構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表*/p=r;while(p!=NULL)r=p-next;/*r保存*p結(jié)點后繼結(jié)點的指針*/83 q=head;while(q-next!=NULL&q-next-datadata)q=q-next;/*在有序表中找插入*p的前驅(qū)結(jié)點*q*/p-next=q-next;/*將*p插入到*q之后*/q-next=p;p=r;/*掃描原單鏈表余下的結(jié)點*/842.3.3 雙鏈表 對于雙鏈表,采用類似于單鏈表的類型定義,其DLinkList類型的定義如下:typedef st

33、ruct DNode /*定義雙鏈表結(jié)點類型*/ElemType data;struct DNode*prior;/*指向前驅(qū)結(jié)點*/struct DNode*next;/*指向后繼結(jié)點*/DLinkList;85 在雙鏈表中,有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進(jìn)行結(jié)點插入和刪除時涉及到前后結(jié)點的一個指針域的變化。而在雙鏈表中,結(jié)點的插入和刪除操作涉及到前后結(jié)點的兩個指針域的變化。86雙鏈表中插入結(jié)點示意圖87 歸納起來,在雙鏈表中p所指的結(jié)點之后插入一個*s結(jié)點。其操作語句描述為:s-next=p-next;/*將*s插入到*p之后*/p-next-prior=s;s-prior=p;p-next=s;88刪除結(jié)點示意圖 在 雙 鏈 表中刪除一個結(jié)點的過程如右圖所示:89 歸納起來,刪除雙鏈表L中*p結(jié)點的后續(xù)結(jié)點。其操