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

1、第2章 線性表,2.1 線性表的基本概念,2.2 線性表的順序存儲,2.3 線性表的鏈式存儲,2.4 線性表的應(yīng)用,本章小結(jié),2.5 有序表,1,PPT學習交流,2.1 線性表的基本概念,2.1.1 線性表的定義,2.1.2 線性表的運算,2,PPT學習交流,2.1.1 線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。該序列中所含元素的個數(shù)叫做線性表的長度,用n表示,n0。 當n=0時,表示線性表是一個空表,即表中不包含任何元素。設(shè)序列中第i(i表示位序)個元素為ai(1in)。 線性表的一般表示為: (a1,a2,ai,ai+1,an),3,PPT學習交流,其中a1為第一個元素,

2、又稱做表頭元素,a2為第二個元素,an為最后一個元素,又稱做表尾元素。 例如,在線性表 (1,4,3,2,8,10) 中,1為表頭元素,10為表尾元素。,4,PPT學習交流,2.1.2 線性表的運算 線性表的基本運算如下: (1) 初始化線性表InitList(i=lenb;i+) GetElem(LB,i,e); /*取LB中第i個數(shù)據(jù)元素賦給e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和e相同者,則插入到LC中*/ ,10,PPT學習交流,由于LocateElem(LA,e)運算的時間復(fù)雜度為O(ListLength(

3、LA),所以本算法的時間復(fù)雜度為: O(ListLength(LA)*ListLength(LB)。,11,PPT學習交流,2.2 線性表的順序存儲,2.2.1 線性表的順序存儲順序表,2.2.2 順序表基本運算的實現(xiàn),12,PPT學習交流,2.2.1 線性表的順序存儲順序表 線性表的順序存儲結(jié)構(gòu)就是:把線性表中的所有元素按照其邏輯順序依次存儲到從計算機存儲器中指定存儲位置開始的一塊連續(xù)的存儲空間中。 這樣,線性表中第一個元素的存儲位置就是指定的存儲位置,第i+1個元素(1in-1)的存儲位置緊接在第i個元素的存儲位置的后面。 線性表 邏輯結(jié)構(gòu) 順序表 存儲結(jié)構(gòu),13,PPT學習交流,假定線性

4、表的元素類型為ElemType,則每個元素所占用存儲空間大小(即字節(jié)數(shù))為sizeof(ElemType),整個線性表所占用存儲空間的大小為: n*sizeof(ElemType) 其中,n表示線性表的長度。,14,PPT學習交流,順序表示意圖,15,PPT學習交流,在定義一個線性表的順序存儲類型時,需要定義一個數(shù)組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度。 假定數(shù)組用dataMaxSize表示,長度整型變量用length表示,并采用結(jié)構(gòu)體類型表示,則元素類型為通用類型標識符ElemType的線性表的順序存儲類型可描述如下:,16,PPT學習交流,typedef struc

5、t ElemType dataMaxSize; int length; SqList; /*順序表類型*/ 其中,data成員存放元素,length成員存放線性表的實際長度。 說明：由于C/C+中數(shù)組的下標從0開始，線性表的第i個元素ai存放順序表的第i-1位置上。為了清楚，將ai在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。,17,PPT學習交流,2.2.2 順序表基本運算的實現(xiàn),一旦采用順序表存儲結(jié)構(gòu),我們就可以用C/C+語言實現(xiàn)線性表的各種基本運算。為了方便,假設(shè)ElemType為char類型,使用如下自定義類型語句: typedef char ElemType;,18,

6、PPT學習交流,1. 建立順序表 其方法是將給定的含有n個元素的數(shù)組的每個元素依次放入到順序表中，并將n賦給順序表的長度成員。算法如下： void CreateList(SqList * ,19,PPT學習交流,2. 順序表基本運算算法 (1) 初始化線性表InitList(L) 該運算的結(jié)果是構(gòu)造一個空的線性表L。實際上只需將length成員設(shè)置為0即可。 void InitList(SqList * 本算法的時間復(fù)雜度為O(1)。,順序表,L,20,PPT學習交流,(2) 銷毀線性表DestroyList(L) 該運算的結(jié)果是釋放線性表L占用的內(nèi)存空間。 void DestroyList(

7、SqList * 本算法的時間復(fù)雜度為O(1)。,21,PPT學習交流,(3) 判定是否為空表ListEmpty(L) 該運算返回一個值表示L是否為空表。若L為空表,則返回1,否則返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的時間復(fù)雜度為O(1)。,22,PPT學習交流,(4) 求線性表的長度ListLength(L) 該運算返回順序表L的長度。實際上只需返回length成員的值即可。 int ListLength(SqList *L) return(L-length); 本算法的時間復(fù)雜度為O(1)。,23,PPT學習交流,(5)

8、 輸出線性表DispList(L) 該運算當線性表L不為空時,順序顯示L中各元素的值。 void DispList(SqList *L) int i; if (ListEmpty(L) return; for (i=0;ilength;i+) printf(%c,L-datai); printf(n); ,24,PPT學習交流,本算法中基本運算為for循環(huán)中的printf語句,故時間復(fù)雜度為: O(L-length)或O(n),25,PPT學習交流,(6) 求某個數(shù)據(jù)元素值GetElem(L,i,e) 該運算返回L中第 i(1iListLength(L)個元素的值,存放在e中。 int Get

9、Elem(SqList *L,int i,ElemType 本算法的時間復(fù)雜度為O(1)。,26,PPT學習交流,(7) 按元素值查找LocateElem(L,e) 該運算順序查找第1個值域與e相等的元素的位序。若這樣的元素不存在,則返回值為0。 int LocateElem(SqList *L, ElemType e) int i=0; while (ilength ,27,PPT學習交流,本算法中基本運算為while循環(huán)中的i+語句,故時間復(fù)雜度為: O(L-length)或O(n),28,PPT學習交流,(8) 插入數(shù)據(jù)元素ListInsert(L,i,e) 該運算在順序表L的第i個位置

10、(1iListLength(L)+1)上插入新的元素e。 思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將順序表原來第i個元素及以后元素均后移一個位置,騰出一個空位置插入新元素,順序表長度增1。,29,PPT學習交流,int ListInsert(SqList * ,邏輯位序1 i i+1 n MaxSize,30,PPT學習交流,對于本算法來說,元素移動的次數(shù)不僅與表長L.length=n有關(guān),而且與插入位置i有關(guān):當i=n+1時,移動次數(shù)為0；當i=1時,移動次數(shù)為n,達到最大值。在線性表sq中共有n+1個可以插入元素的地方。假設(shè)pi(= )是在第i個位置上插入一個元素的概率,則在長度為n

11、的線性表中插入一個元素時所需移動元素的平均次數(shù)為: 因此插入算法的平均時間復(fù)雜度為O(n)。,31,PPT學習交流,(9) 刪除數(shù)據(jù)元素ListDelete(L,i,e) 刪除順序表L中的第i(1iListLength(L)個元素。 思路：如果i值不正確,則顯示相應(yīng)錯誤信息；否則將線性表第i個元素以后元素均向前移動一個位置,這樣覆蓋了原來的第i個元素,達到刪除該元素的目的,最后順序表長度減1。,32,PPT學習交流,int ListDelete(SqList * ,邏輯位序1 i i+1 n MaxSize,33,PPT學習交流,對于本算法來說,元素移動的次數(shù)也與表長n和刪除元素的位置i有關(guān):

12、當i=n時,移動次數(shù)為0；當i=1時,移動次數(shù)為n-1。在線性表sq中共有n個元素可以被刪除。假設(shè)pi(pi= )是刪除第i個位置上元素的概率,則在長度為n的線性表中刪除一個元素時所需移動元素的平均次數(shù)為: = 因此刪除算法的平均時間復(fù)雜度為O(n)。,34,PPT學習交流,例2.2 設(shè)計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu)即順序表)的適當位置上,并保持線性表的有序性。 解:先通過比較在順序表L中找到存放x的位置i,然后將x插入到L.datai中,最后將順序表的長度增1。,35,PPT學習交流,void Insert(SqList * ,查找插入位置,元素后移一個

13、位置,邏輯位序1 i i+1 n MaxSize,36,PPT學習交流,例2.3 設(shè)計一個算法,將兩個元素有序(從小到大)的順序表合并成一個有序順序表。 求解思路:將兩個順序表進行二路歸并。,37,PPT學習交流,歸并到順序表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：135,i

14、,順序表q：241020,j,順序表r：1,k,38,PPT學習交流,SqList *merge(SqList *p, SqList *q) SqList *r; int i=0,j=0,k=0; r=(SqList *)malloc(sizeof(SqList); while (ilength ,39,PPT學習交流,while (ilength) r-datak=p-datai; i+;k+; while (jlength) r-datak=q-dataj; j+;k+; r-length=k; /*或p-length+q-length*/ return(r); ,40,PPT學習交流,例

15、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)的算法如下:,41,PPT學習交流,void delnode1(SqList /*順序表A的長度等于k*/ ,算法1：類似于建順序表,42,PPT學習交流,void delnode2(SqList /*順序表A的長度遞減*/ ,算法2,43,PPT學習交流,上述算法中只有一個while循環(huán),時間復(fù)雜度為O(n)。算法中只用

16、了i,k兩個臨時變量,空間復(fù)雜度為O(1)。,44,PPT學習交流,2.3 線性表的鏈式存儲,2.3.1 線性表的鏈式存儲鏈表,2.3.2 單鏈表基本運算的實現(xiàn),2.3.3 雙鏈表,2.3.4 循環(huán)鏈表,2.3.5 靜態(tài)鏈表,45,PPT學習交流,2.3.1 線性表的鏈式存儲鏈表 在鏈式存儲中,每個存儲結(jié)點不僅包含有所存元素本身的信息(稱之為數(shù)據(jù)域),而且包含有元素之間邏輯關(guān)系的信息,即前驅(qū)結(jié)點包含有后繼結(jié)點的地址信息,這稱為指針域,這樣可以通過前驅(qū)結(jié)點的指針域方便地找到后繼結(jié)點的位置,提高數(shù)據(jù)查找速度。 一般地,每個結(jié)點有一個或多個這樣的指針域。若一個結(jié)點中的某個指針域不需要任何結(jié)點,則僅它

17、的值為空,用常量NULL表示。,46,PPT學習交流,由于順序表中的每個元素至多只有一個前驅(qū)元素和一個后繼元素,即數(shù)據(jù)元素之間是一對一的邏輯關(guān)系,所以當進行鏈式存儲時,一種最簡單也最常用的方法是: 在每個結(jié)點中除包含有數(shù)據(jù)域外,只設(shè)置一個指針域,用以指向其后繼結(jié)點,這樣構(gòu)成的鏈接表稱為線性單向鏈接表,簡稱單鏈表；,47,PPT學習交流,帶頭結(jié)點單鏈表示意圖,在線性表的鏈式存儲中,為了便于插入和刪除算法的實現(xiàn),每個鏈表帶有一個頭結(jié)點,并通過頭結(jié)點的指針惟一標識該鏈表。,48,PPT學習交流,在單鏈表中,由于每個結(jié)點只包含有一個指向后繼結(jié)點的指針,所以當訪問過一個結(jié)點后,只能接著訪問它的后繼結(jié)點,

18、而無法訪問它的前驅(qū)結(jié)點。,49,PPT學習交流,另一種可以采用的方法是:在每個結(jié)點中除包含有數(shù)值域外,設(shè)置有兩個指針域,分別用以指向其前驅(qū)結(jié)點和后繼結(jié)點,這樣構(gòu)成的鏈接表稱之為線性雙向鏈接表,簡稱雙鏈表。,50,PPT學習交流,帶頭結(jié)點的雙鏈表示意圖,51,PPT學習交流,在雙鏈表中,由于每個結(jié)點既包含有一個指向后繼結(jié)點的指針,又包含有一個指向前驅(qū)結(jié)點的指針,所以當訪問過一個結(jié)點后,既可以依次向后訪問每一個結(jié)點,也可以依次向前訪問每一個結(jié)點。,雙鏈表的特點,52,PPT學習交流,在單鏈表中,假定每個結(jié)點類型用LinkList表示,它應(yīng)包括存儲元素的數(shù)據(jù)域,這里用data表示,其類型用通用類型標

19、識符ElemType表示,還包括存儲后繼元素位置的指針域,這里用next表示。 LinkList類型的定義如下: typedef struct LNode /*定義單鏈表結(jié)點類型*/ ElemType data; struct LNode *next; /*指向后繼結(jié)點*/ LinkList;,53,PPT學習交流,2.3.2 單鏈表基本運算的實現(xiàn),1. 建立單鏈表 先考慮如何建立單鏈表。假設(shè)我們通過一個含有n個數(shù)據(jù)的數(shù)組來建立單鏈表。建立單鏈表的常用方法有如下兩種: (1) 頭插法建表 該方法從一個空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點,將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點

20、插入到當前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:,54,PPT學習交流,void CreateListF(LinkList * ,55,PPT學習交流,i=0,i=1,i=2,i=3,head,采用頭插法建立單鏈表的過程,head,head,head,head,第1步:建頭結(jié)點,第2步:i0,新建a結(jié)點,插入到頭結(jié)點之后,第3步:i1,新建d結(jié)點,插入到頭結(jié)點之后,第4步:i2,新建c結(jié)點,插入到頭結(jié)點之后,第5步:i3,新建b結(jié)點,插入到頭結(jié)點之后,56,PPT學習交流,(2) 尾插法建表 頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反。若希望兩者

21、次序一致,可采用尾插法建立。該方法是將新結(jié)點插到當前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當前鏈表的尾結(jié)點。采用尾插法建表的算法如下:,57,PPT學習交流,void CreateListR(LinkList */*終端結(jié)點next域置為NULL*/ ,58,PPT學習交流,b,c,d,a,i=0,i=1,i=2,i=3,head,頭結(jié)點,a,d,c,采用尾插法建立單鏈表的過程,59,PPT學習交流,2. 插入結(jié)點運算 插入運算是將值為x的新結(jié)點插入到單鏈表的第i個結(jié)點的位置上。先在單鏈表中找到第i-1個結(jié)點,再在其后插入新結(jié)點。 單鏈表插入結(jié)點的過程如下圖所示。,60,PPT學

22、習交流,插入結(jié)點示意圖,61,PPT學習交流,3. 刪除結(jié)點運算 刪除運算是將單鏈表的第i個結(jié)點刪去。先在單鏈表中找到第i-1個結(jié)點,再刪除其后的結(jié)點。刪除單鏈表結(jié)點的過程如下圖所示。,62,PPT學習交流,刪除結(jié)點示意圖,63,PPT學習交流,4. 線性表基本運算實現(xiàn) (1) 初始化線性表InitList(L) 該運算建立一個空的單鏈表,即創(chuàng)建一個頭結(jié)點。 void InitList(LinkList * ,64,PPT學習交流,(2) 銷毀線性表DestroyList(L) 釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點的空間。 void DestroyList(LinkList * ,6

23、5,PPT學習交流,(3) 判線性表是否為空表ListEmpty(L) 若單鏈表L沒有數(shù)據(jù)結(jié)點,則返回真,否則返回假。 int ListEmpty(LinkList *L) return(L-next=NULL); ,66,PPT學習交流,(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); ,67,PPT學習交流,(5) 輸出線性表DispList(L) 逐一掃描單鏈表L的

24、每個數(shù)據(jù)結(jié)點,并顯示各結(jié)點的data域值。 void DispList(LinkList *L) LinkList *p=L-next; while (p!=NULL) printf(%c,p-data); p=p-next; printf(n); ,68,PPT學習交流,(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,int n=1; while (p!=NULL ,71,PPT學習交流,(8) 插入數(shù)據(jù)元素ListInsert( ,72,PPT學習交流,if (p=NULL) return 0; /*未找到位序為i-1的結(jié)點*/ else/*找到位序為i-1的結(jié)點*p*/

25、s=(LinkList *)malloc(sizeof(LinkList); /*創(chuàng)建新結(jié)點*s*/ s-data=e; s-next=p-next; /*將*s插入到*p之后*/ p-next=s; return 1; ,73,PPT學習交流,(9) 刪除數(shù)據(jù)元素ListDelete( ,74,PPT學習交流,if (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; /*從

26、單鏈表中刪除*q結(jié)點*/ free(q); /*釋放*q結(jié)點*/ return 1; ,75,PPT學習交流,例2.5 設(shè)C=a1,b1,a2,b2,an,bn為一線性表,采用帶頭結(jié)點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得: A=a1,a2,an,B=b1,b2,bn,76,PPT學習交流,解: 設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放。 先建立兩個頭結(jié)點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾,用p指針掃描單鏈表hc,將當前結(jié)點*p鏈到ha未尾,p沿next域下移一個結(jié)點,若不為空,則當前結(jié)點*p鏈到hb未尾,p沿next

27、域下移一個結(jié)點,如此這樣,直到p為空。最后將兩個尾結(jié)點的next域置空。 對應(yīng)算法如下:,77,PPT學習交流,void fun(LinkList *hc, LinkList * /*rb始終指向hb的末尾結(jié)點*/,78,PPT學習交流,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域置空*/ ,79,PPT學習交流,本算法實際上是采用尾插法建

28、立兩個新表。所以,尾插法建表算法是很多類似習題的基礎(chǔ)！,80,PPT學習交流,例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之后(這里實際上采用的是直接插入排序方法)。,81,PPT學習交流,void Sort(LinkList * /*r保存*p結(jié)點后繼結(jié)點的指針*/,82,PPT學習交流,q=head;

29、while (q-next!=NULL /*掃描原單鏈表余下的結(jié)點*/ ,83,PPT學習交流,2.3.3 雙鏈表 對于雙鏈表,采用類似于單鏈表的類型定義,其DLinkList類型的定義如下: typedef struct DNode /*定義雙鏈表結(jié)點類型*/ ElemType data; struct DNode *prior; /*指向前驅(qū)結(jié)點*/ struct DNode *next; /*指向后繼結(jié)點*/ DLinkList;,84,PPT學習交流,在雙鏈表中,有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進行結(jié)點插入和刪除時涉

30、及到前后結(jié)點的一個指針域的變化。而在雙鏈表中,結(jié)點的插入和刪除操作涉及到前后結(jié)點的兩個指針域的變化。,85,PPT學習交流,雙鏈表中插入結(jié)點示意圖,86,PPT學習交流,歸納起來,在雙鏈表中p所指的結(jié)點之后插入一個*s結(jié)點。其操作語句描述為: s-next=p-next;/*將*s插入到*p之后*/ p-next-prior=s; s-prior=p; p-next=s;,87,PPT學習交流,刪除結(jié)點示意圖,在雙鏈表中刪除一個結(jié)點的過程如右圖所示:,88,PPT學習交流,歸納起來,刪除雙鏈表L中*p結(jié)點的后續(xù)結(jié)點。其操作語句描述為: p-next=q-next; q-next-prior=p

31、;,89,PPT學習交流,2.3.4 循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域不再是空,而是指向表頭結(jié)點,整個鏈表形成一個環(huán)。由此,從表中任一結(jié)點出發(fā)均可找到鏈表中其他結(jié)點。,90,PPT學習交流,帶頭結(jié)點的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖,91,PPT學習交流,例2.7 編寫出判斷帶頭結(jié)點的雙向循環(huán)鏈表L是否對稱相等的算法。 解:p從左向右掃描L,q從右向左掃描L,若對應(yīng)數(shù)據(jù)結(jié)點的data域不相等,則退出循環(huán),否則繼續(xù)比較,直到p與q相等或p的下一個結(jié)點為*q為止。對應(yīng)算法如下:,92,PPT學習交流,int Equeal(DLinkList *L) i

32、nt same=1; DLinkList *p=L-next; /*p指向第一個數(shù)據(jù)結(jié)點*/ DLinkList *q=L-prior; /*q指向最后數(shù)據(jù)結(jié)點*/ while (same=1) if (p-data!=q-data) same=0; else if (p=q) break;/*數(shù)據(jù)結(jié)點為奇數(shù)的情況*/ q=q-prior; if (p=q) break;/*數(shù)據(jù)結(jié)點為偶數(shù)的情況*/ p=p-next; return same; ,93,PPT學習交流,2.3.5 靜態(tài)鏈表 靜態(tài)鏈表借用一維數(shù)組來描述線性鏈表。數(shù)組中的一個分量表示一個結(jié)點,同時使用游標(指示器cur即為偽指針)

33、代替指針以指示結(jié)點在數(shù)組中的相對位置。數(shù)組中的第0個分量可以看成頭結(jié)點,其指針域指示靜態(tài)鏈表的第一個結(jié)點。 這種存儲結(jié)構(gòu)仍然需要預(yù)先分配一個較大空間,但是在進行線性表的插入和刪除操作時不需要移動元素,僅需要修改“指針”,因此仍然具有鏈式存儲結(jié)構(gòu)的主要優(yōu)點。,94,PPT學習交流,下圖給出了一個靜態(tài)鏈表的示例。圖(a)是一個修改之前的靜態(tài)鏈表,圖(b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表,圖(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表,圖中用陰影表示修改的游標。,95,PPT學習交流,2.4 線性表的應(yīng)用,計算任意兩個表的簡單自然連接過程討論線性表的應(yīng)用。假設(shè)有兩個表A和B,分別是m1行、n1列和m

34、2行、n2列,它們簡單自然連接結(jié)果C=A B,其中i表示表A中列號,j表示表B中的列號,C為A和B的笛卡兒積中滿足指定連接條件的所有記錄組,該連接條件為表A的第i列與表B的第j列相等。例如:,i=j,96,PPT學習交流,C=A B的計算結(jié)果如下:,3=1,97,PPT學習交流,由于每個表的行數(shù)不確定,為此,用單鏈表作為表的存儲結(jié)構(gòu),每行作為一個數(shù)據(jù)結(jié)點。另外,每行中的數(shù)據(jù)個數(shù)也是不確定的,但由于提供隨機查找行中的數(shù)據(jù),所以每行的數(shù)據(jù)采用順序存儲結(jié)構(gòu),這里用長度為MaxCol的數(shù)組存儲每行的數(shù)據(jù)。因此,該單鏈表中數(shù)據(jù)結(jié)點類型定義如下: #define MaxCol 10/*最大列數(shù)*/ typ

35、edef struct Node1/*定義數(shù)據(jù)結(jié)點類型*/ ElemType dataMaxCol; struct Node1 *next; /*指向后繼數(shù)據(jù)結(jié)點*/ DList;,98,PPT學習交流,另外,需要指定每個表的行數(shù)和列數(shù),為此將單鏈表的頭結(jié)點類型定義如下: typedef struct Node2/*定義頭結(jié)點類型*/ int Row,Col;/*行數(shù)和列數(shù)*/ DList *next;/*指向第一個數(shù)據(jù)結(jié)點*/ HList; 采用尾插法建表方法創(chuàng)建單鏈表,用戶先輸入表的行數(shù)和列數(shù),然后輸入各行的數(shù)據(jù),為了簡便,假設(shè)表中數(shù)據(jù)為int型,因此定義: typedef int ElemType; 對應(yīng)的建表算法如下:,99,PPT學習交流,void create(HList