《數(shù)據(jù)結(jié)構(gòu)線性表》PPT課件.ppt

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

2、尾元素。 例如,在線性表 (1,4,3,2,8,10) 中,1為表頭元素,10為表尾元素,2.1.2 線性表的運(yùn)算 線性表的基本運(yùn)算如下: (1) 初始化線性表InitList(i=lenb;i+) GetElem(LB,i,e); /*取LB中第i個(gè)數(shù)據(jù)元素賦給e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和e相同者,則插入到LC中*/,由于LocateElem(LA,e)運(yùn)算的時(shí)間復(fù)雜度為O(ListLength(LA),所以本算法的時(shí)間復(fù)雜度為: O(ListLength(LA)*ListLength(LB,2.2 線

3、性表的順序存儲(chǔ),2.2.1 線性表的順序存儲(chǔ)順序表,2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn),2.2.1 線性表的順序存儲(chǔ)順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)就是:把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)器中指定存儲(chǔ)位置開(kāi)始的一塊連續(xù)的存儲(chǔ)空間中。 這樣,線性表中第一個(gè)元素的存儲(chǔ)位置就是指定的存儲(chǔ)位置,第i+1個(gè)元素(1in-1)的存儲(chǔ)位置緊接在第i個(gè)元素的存儲(chǔ)位置的后面。 線性表 邏輯結(jié)構(gòu) 順序表 存儲(chǔ)結(jié)構(gòu),假定線性表的元素類(lèi)型為ElemType,則每個(gè)元素所占用存儲(chǔ)空間大小(即字節(jié)數(shù))為sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為: n*sizeof(ElemType

4、) 其中,n表示線性表的長(zhǎng)度,順序表示意圖,在定義一個(gè)線性表的順序存儲(chǔ)類(lèi)型時(shí),需要定義一個(gè)數(shù)組來(lái)存儲(chǔ)線線表中的所有元素和定義一個(gè)整型變量來(lái)存儲(chǔ)線性表的長(zhǎng)度。 假定數(shù)組用dataMaxSize表示,長(zhǎng)度整型變量用length表示,并采用結(jié)構(gòu)體類(lèi)型表示,則元素類(lèi)型為通用類(lèi)型標(biāo)識(shí)符ElemType的線性表的順序存儲(chǔ)類(lèi)型可描述如下,typedef struct ElemType dataMaxSize; int length; SqList; /*順序表類(lèi)型*/ 其中,data成員存放元素,length成員存放線性表的實(shí)際長(zhǎng)度。 說(shuō)明：由于C/C+中數(shù)組的下標(biāo)從0開(kāi)始，線性表的第i個(gè)元素ai存放順序表

5、的第i-1位置上。為了清楚，將ai在邏輯序列中的位置稱(chēng)為邏輯位序，在順序表中的位置稱(chēng)為物理位序,2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn),一旦采用順序表存儲(chǔ)結(jié)構(gòu),我們就可以用C/C+語(yǔ)言實(shí)現(xiàn)線性表的各種基本運(yùn)算。為了方便,假設(shè)ElemType為char類(lèi)型,使用如下自定義類(lèi)型語(yǔ)句: typedef char ElemType,1. 建立順序表 其方法是將給定的含有n個(gè)元素的數(shù)組的每個(gè)元素依次放入到順序表中，并將n賦給順序表的長(zhǎng)度成員。算法如下： void CreateList(SqList *,2. 順序表基本運(yùn)算算法 (1) 初始化線性表InitList(L) 該運(yùn)算的結(jié)果是構(gòu)造一個(gè)空的線性表L。實(shí)

6、際上只需將length成員設(shè)置為0即可。 void InitList(SqList * 本算法的時(shí)間復(fù)雜度為O(1,順序表,L,2) 銷(xiāo)毀線性表DestroyList(L) 該運(yùn)算的結(jié)果是釋放線性表L占用的內(nèi)存空間。 void DestroyList(SqList * 本算法的時(shí)間復(fù)雜度為O(1,3) 判定是否為空表ListEmpty(L) 該運(yùn)算返回一個(gè)值表示L是否為空表。若L為空表,則返回1,否則返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的時(shí)間復(fù)雜度為O(1,4) 求線性表的長(zhǎng)度ListLength(L) 該運(yùn)算返回順序表L的

7、長(zhǎng)度。實(shí)際上只需返回length成員的值即可。 int ListLength(SqList *L) return(L-length); 本算法的時(shí)間復(fù)雜度為O(1,5) 輸出線性表DispList(L) 該運(yùn)算當(dāng)線性表L不為空時(shí),順序顯示L中各元素的值。 void DispList(SqList *L) int i; if (ListEmpty(L) return; for (i=0;ilength;i+) printf(%c,L-datai); printf(n);,本算法中基本運(yùn)算為for循環(huán)中的printf語(yǔ)句,故時(shí)間復(fù)雜度為: O(L-length)或O(n,6) 求某個(gè)數(shù)據(jù)元素值Ge

8、tElem(L,i,e) 該運(yùn)算返回L中第 i(1iListLength(L)個(gè)元素的值,存放在e中。 int GetElem(SqList *L,int i,ElemType 本算法的時(shí)間復(fù)雜度為O(1,7) 按元素值查找LocateElem(L,e) 該運(yùn)算順序查找第1個(gè)值域與e相等的元素的位序。若這樣的元素不存在,則返回值為0。 int LocateElem(SqList *L, ElemType e) int i=0; while (ilength,本算法中基本運(yùn)算為while循環(huán)中的i+語(yǔ)句,故時(shí)間復(fù)雜度為: O(L-length)或O(n,8) 插入數(shù)據(jù)元素ListInsert(L

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

10、中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為: 因此插入算法的平均時(shí)間復(fù)雜度為O(n,9) 刪除數(shù)據(jù)元素ListDelete(L,i,e) 刪除順序表L中的第i(1iListLength(L)個(gè)元素。 思路：如果i值不正確,則顯示相應(yīng)錯(cuò)誤信息；否則將線性表第i個(gè)元素以后元素均向前移動(dòng)一個(gè)位置,這樣覆蓋了原來(lái)的第i個(gè)元素,達(dá)到刪除該元素的目的,最后順序表長(zhǎng)度減1,int ListDelete(SqList *,邏輯位序1 i i+1 n MaxSize,對(duì)于本算法來(lái)說(shuō),元素移動(dòng)的次數(shù)也與表長(zhǎng)n和刪除元素的位置i有關(guān):當(dāng)i=n時(shí),移動(dòng)次數(shù)為0；當(dāng)i=1時(shí),移動(dòng)次數(shù)為n-1。在線性表sq中共有n個(gè)元素可

11、以被刪除。假設(shè)pi(pi= )是刪除第i個(gè)位置上元素的概率,則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為: = 因此刪除算法的平均時(shí)間復(fù)雜度為O(n,例2.2 設(shè)計(jì)一個(gè)算法,將x插入到一個(gè)有序(從小到大排序)的線性表(順序存儲(chǔ)結(jié)構(gòu)即順序表)的適當(dāng)位置上,并保持線性表的有序性。 解:先通過(guò)比較在順序表L中找到存放x的位置i,然后將x插入到L.datai中,最后將順序表的長(zhǎng)度增1,void Insert(SqList *,查找插入位置,元素后移一個(gè)位置,邏輯位序1 i i+1 n MaxSize,例2.3 設(shè)計(jì)一個(gè)算法,將兩個(gè)元素有序(從小到大)的順序表合并成一個(gè)有序順序表。 求解

12、思路:將兩個(gè)順序表進(jìn)行二路歸并,歸并到順序表r中 k記錄r中元素個(gè)數(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,順序表q：241020,j,順序表r：1,k,SqList *merge(SqList *p, SqList *q) SqList *r; int i=0,j=0,k=0; r=(S

13、qList *)malloc(sizeof(SqList); while (ilength,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);,例2.4 已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu),編寫(xiě)一個(gè)時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。 解:用k記錄順序表A中等于item的元素個(gè)數(shù),邊掃描A邊統(tǒng)計(jì)k,并將不為item的元素前移k個(gè)位置,

14、最后修改A的長(zhǎng)度。對(duì)應(yīng)的算法如下,void delnode1(SqList /*順序表A的長(zhǎng)度等于k*/,算法1：類(lèi)似于建順序表,void delnode2(SqList /*順序表A的長(zhǎng)度遞減*/,算法2,上述算法中只有一個(gè)while循環(huán),時(shí)間復(fù)雜度為O(n)。算法中只用了i,k兩個(gè)臨時(shí)變量,空間復(fù)雜度為O(1,2.3 線性表的鏈?zhǔn)酱鎯?chǔ),2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)鏈表,2.3.2 單鏈表基本運(yùn)算的實(shí)現(xiàn),2.3.3 雙鏈表,2.3.4 循環(huán)鏈表,2.3.5 靜態(tài)鏈表,2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)鏈表 在鏈?zhǔn)酱鎯?chǔ)中,每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅包含有所存元素本身的信息(稱(chēng)之為數(shù)據(jù)域),而且包含有元素之間邏

15、輯關(guān)系的信息,即前驅(qū)結(jié)點(diǎn)包含有后繼結(jié)點(diǎn)的地址信息,這稱(chēng)為指針域,這樣可以通過(guò)前驅(qū)結(jié)點(diǎn)的指針域方便地找到后繼結(jié)點(diǎn)的位置,提高數(shù)據(jù)查找速度。 一般地,每個(gè)結(jié)點(diǎn)有一個(gè)或多個(gè)這樣的指針域。若一個(gè)結(jié)點(diǎn)中的某個(gè)指針域不需要任何結(jié)點(diǎn),則僅它的值為空,用常量NULL表示,由于順序表中的每個(gè)元素至多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素,即數(shù)據(jù)元素之間是一對(duì)一的邏輯關(guān)系,所以當(dāng)進(jìn)行鏈?zhǔn)酱鎯?chǔ)時(shí),一種最簡(jiǎn)單也最常用的方法是: 在每個(gè)結(jié)點(diǎn)中除包含有數(shù)據(jù)域外,只設(shè)置一個(gè)指針域,用以指向其后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱(chēng)為線性單向鏈接表,簡(jiǎn)稱(chēng)單鏈表,帶頭結(jié)點(diǎn)單鏈表示意圖,在線性表的鏈?zhǔn)酱鎯?chǔ)中,為了便于插入和刪除算法的實(shí)現(xiàn),每個(gè)鏈表帶

16、有一個(gè)頭結(jié)點(diǎn),并通過(guò)頭結(jié)點(diǎn)的指針惟一標(biāo)識(shí)該鏈表,在單鏈表中,由于每個(gè)結(jié)點(diǎn)只包含有一個(gè)指向后繼結(jié)點(diǎn)的指針,所以當(dāng)訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)后,只能接著訪問(wèn)它的后繼結(jié)點(diǎn),而無(wú)法訪問(wèn)它的前驅(qū)結(jié)點(diǎn),另一種可以采用的方法是:在每個(gè)結(jié)點(diǎn)中除包含有數(shù)值域外,設(shè)置有兩個(gè)指針域,分別用以指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn),這樣構(gòu)成的鏈接表稱(chēng)之為線性雙向鏈接表,簡(jiǎn)稱(chēng)雙鏈表,帶頭結(jié)點(diǎn)的雙鏈表示意圖,在雙鏈表中,由于每個(gè)結(jié)點(diǎn)既包含有一個(gè)指向后繼結(jié)點(diǎn)的指針,又包含有一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針,所以當(dāng)訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)后,既可以依次向后訪問(wèn)每一個(gè)結(jié)點(diǎn),也可以依次向前訪問(wèn)每一個(gè)結(jié)點(diǎn),雙鏈表的特點(diǎn),在單鏈表中,假定每個(gè)結(jié)點(diǎn)類(lèi)型用LinkList表示,它應(yīng)

17、包括存儲(chǔ)元素的數(shù)據(jù)域,這里用data表示,其類(lèi)型用通用類(lèi)型標(biāo)識(shí)符ElemType表示,還包括存儲(chǔ)后繼元素位置的指針域,這里用next表示。 LinkList類(lèi)型的定義如下: typedef struct LNode /*定義單鏈表結(jié)點(diǎn)類(lèi)型*/ ElemType data; struct LNode *next; /*指向后繼結(jié)點(diǎn)*/ LinkList,2.3.2 單鏈表基本運(yùn)算的實(shí)現(xiàn),1. 建立單鏈表 先考慮如何建立單鏈表。假設(shè)我們通過(guò)一個(gè)含有n個(gè)數(shù)據(jù)的數(shù)組來(lái)建立單鏈表。建立單鏈表的常用方法有如下兩種: (1) 頭插法建表 該方法從一個(gè)空表開(kāi)始,讀取字符數(shù)組a中的字符,生成新結(jié)點(diǎn),將讀取的數(shù)據(jù)

18、存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下,void CreateListF(LinkList *,i=0,i=1,i=2,i=3,head,采用頭插法建立單鏈表的過(guò)程,head,head,head,head,第1步:建頭結(jié)點(diǎn),第2步:i0,新建a結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后,第3步:i1,新建d結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后,第4步:i2,新建c結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后,第5步:i3,新建b結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后,2) 尾插法建表 頭插法建立鏈表雖然算法簡(jiǎn)單,但生成的鏈表中結(jié)點(diǎn)的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是

19、將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上,為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。采用尾插法建表的算法如下,void CreateListR(LinkList */*終端結(jié)點(diǎn)next域置為NULL*/,b,c,d,a,i=0,i=1,i=2,i=3,head,頭結(jié)點(diǎn),a,d,c,采用尾插法建立單鏈表的過(guò)程,2. 插入結(jié)點(diǎn)運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)的位置上。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再在其后插入新結(jié)點(diǎn)。 單鏈表插入結(jié)點(diǎn)的過(guò)程如下圖所示,插入結(jié)點(diǎn)示意圖,3. 刪除結(jié)點(diǎn)運(yùn)算 刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn),再刪除其后的結(jié)點(diǎn)。

20、刪除單鏈表結(jié)點(diǎn)的過(guò)程如下圖所示,刪除結(jié)點(diǎn)示意圖,4. 線性表基本運(yùn)算實(shí)現(xiàn) (1) 初始化線性表InitList(L) 該運(yùn)算建立一個(gè)空的單鏈表,即創(chuàng)建一個(gè)頭結(jié)點(diǎn)。 void InitList(LinkList *,2) 銷(xiāo)毀線性表DestroyList(L) 釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。 void DestroyList(LinkList *,3) 判線性表是否為空表ListEmpty(L) 若單鏈表L沒(méi)有數(shù)據(jù)結(jié)點(diǎn),則返回真,否則返回假。 int ListEmpty(LinkList *L) return(L-next=NULL);,4) 求線性表的長(zhǎng)度ListLen

21、gth(L) 返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。 int ListLength(LinkList *L) LinkList *p=L;int i=0; while (p-next!=NULL) i+; p=p-next; return(i);,5) 輸出線性表DispList(L) 逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn),并顯示各結(jié)點(diǎn)的data域值。 void DispList(LinkList *L) LinkList *p=L-next; while (p!=NULL) printf(%c,p-data); p=p-next; printf(n);,6)求線性表L中指定位置的某個(gè)數(shù)據(jù)元素GetElem

22、(L,i,int n=1; while (p!=NULL,8) 插入數(shù)據(jù)元素ListInsert(,if (p=NULL) return 0; /*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else/*找到位序?yàn)閕-1的結(jié)點(diǎn)*p*/ s=(LinkList *)malloc(sizeof(LinkList); /*創(chuàng)建新結(jié)點(diǎn)*s*/ s-data=e; s-next=p-next; /*將*s插入到*p之后*/ p-next=s; return 1;,9) 刪除數(shù)據(jù)元素ListDelete(,if (p=NULL) return 0; /*未找到位序?yàn)閕-1的結(jié)點(diǎn)*/ else/*找到位序?yàn)閕-1的結(jié)點(diǎn)*

23、p*/ q=p-next; /*q指向要?jiǎng)h除的結(jié)點(diǎn)*/ if (q=NULL) return 0; /*若不存在第i個(gè)結(jié)點(diǎn),返回0*/ p-next=q-next; /*從單鏈表中刪除*q結(jié)點(diǎn)*/ free(q); /*釋放*q結(jié)點(diǎn)*/ return 1;,例2.5 設(shè)C=a1,b1,a2,b2,an,bn為一線性表,采用帶頭結(jié)點(diǎn)的hc單鏈表存放,編寫(xiě)一個(gè)算法,將其拆分為兩個(gè)線性表,使得: A=a1,a2,an,B=b1,b2,bn,解: 設(shè)拆分后的兩個(gè)線性表都用帶頭結(jié)點(diǎn)的單鏈表存放。 先建立兩個(gè)頭結(jié)點(diǎn)*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個(gè)單鏈表的表尾,用p

24、指針掃描單鏈表hc,將當(dāng)前結(jié)點(diǎn)*p鏈到ha未尾,p沿next域下移一個(gè)結(jié)點(diǎn),若不為空,則當(dāng)前結(jié)點(diǎn)*p鏈到hb未尾,p沿next域下移一個(gè)結(jié)點(diǎn),如此這樣,直到p為空。最后將兩個(gè)尾結(jié)點(diǎn)的next域置空。 對(duì)應(yīng)算法如下,void fun(LinkList *hc, LinkList * /*rb始終指向hb的末尾結(jié)點(diǎn)*,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; /*兩個(gè)

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

26、ext!=NULL /*掃描原單鏈表余下的結(jié)點(diǎn)*/,2.3.3 雙鏈表 對(duì)于雙鏈表,采用類(lèi)似于單鏈表的類(lèi)型定義,其DLinkList類(lèi)型的定義如下: typedef struct DNode /*定義雙鏈表結(jié)點(diǎn)類(lèi)型*/ ElemType data; struct DNode *prior; /*指向前驅(qū)結(jié)點(diǎn)*/ struct DNode *next; /*指向后繼結(jié)點(diǎn)*/ DLinkList,在雙鏈表中,有些操作如求長(zhǎng)度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的,這里不多討論。但在單鏈表中,進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)涉及到前后結(jié)點(diǎn)的一個(gè)指針域的變化。而在雙鏈表中,結(jié)點(diǎn)的插入和刪除操作涉

27、及到前后結(jié)點(diǎn)的兩個(gè)指針域的變化,雙鏈表中插入結(jié)點(diǎn)示意圖,歸納起來(lái),在雙鏈表中p所指的結(jié)點(diǎn)之后插入一個(gè)*s結(jié)點(diǎn)。其操作語(yǔ)句描述為: s-next=p-next;/*將*s插入到*p之后*/ p-next-prior=s; s-prior=p; p-next=s,刪除結(jié)點(diǎn)示意圖,在雙鏈表中刪除一個(gè)結(jié)點(diǎn)的過(guò)程如右圖所示,歸納起來(lái),刪除雙鏈表L中*p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。其操作語(yǔ)句描述為: p-next=q-next; q-next-prior=p,2.3.4 循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域不再是空,而是指向表頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。由此,從表中任一結(jié)點(diǎn)

28、出發(fā)均可找到鏈表中其他結(jié)點(diǎn),帶頭結(jié)點(diǎn)的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖,例2.7 編寫(xiě)出判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱(chēng)相等的算法。 解:p從左向右掃描L,q從右向左掃描L,若對(duì)應(yīng)數(shù)據(jù)結(jié)點(diǎn)的data域不相等,則退出循環(huán),否則繼續(xù)比較,直到p與q相等或p的下一個(gè)結(jié)點(diǎn)為*q為止。對(duì)應(yīng)算法如下,int Equeal(DLinkList *L) int same=1; DLinkList *p=L-next; /*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ DLinkList *q=L-prior; /*q指向最后數(shù)據(jù)結(jié)點(diǎn)*/ while (same=1) if (p-data!=q-data) same=0; el

29、se if (p=q) break;/*數(shù)據(jù)結(jié)點(diǎn)為奇數(shù)的情況*/ q=q-prior; if (p=q) break;/*數(shù)據(jù)結(jié)點(diǎn)為偶數(shù)的情況*/ p=p-next; return same;,2.3.5 靜態(tài)鏈表 靜態(tài)鏈表借用一維數(shù)組來(lái)描述線性鏈表。數(shù)組中的一個(gè)分量表示一個(gè)結(jié)點(diǎn),同時(shí)使用游標(biāo)(指示器cur即為偽指針)代替指針以指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。數(shù)組中的第0個(gè)分量可以看成頭結(jié)點(diǎn),其指針域指示靜態(tài)鏈表的第一個(gè)結(jié)點(diǎn)。 這種存儲(chǔ)結(jié)構(gòu)仍然需要預(yù)先分配一個(gè)較大空間,但是在進(jìn)行線性表的插入和刪除操作時(shí)不需要移動(dòng)元素,僅需要修改“指針”,因此仍然具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn),下圖給出了一個(gè)靜態(tài)鏈表的

30、示例。圖(a)是一個(gè)修改之前的靜態(tài)鏈表,圖(b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表,圖(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表,圖中用陰影表示修改的游標(biāo),2.4 線性表的應(yīng)用,計(jì)算任意兩個(gè)表的簡(jiǎn)單自然連接過(guò)程討論線性表的應(yīng)用。假設(shè)有兩個(gè)表A和B,分別是m1行、n1列和m2行、n2列,它們簡(jiǎn)單自然連接結(jié)果C=A B,其中i表示表A中列號(hào),j表示表B中的列號(hào),C為A和B的笛卡兒積中滿足指定連接條件的所有記錄組,該連接條件為表A的第i列與表B的第j列相等。例如,i=j,C=A B的計(jì)算結(jié)果如下,3=1,由于每個(gè)表的行數(shù)不確定,為此,用單鏈表作為表的存儲(chǔ)結(jié)構(gòu),每行作為一個(gè)數(shù)據(jù)結(jié)點(diǎn)。另外,每行中的數(shù)據(jù)

31、個(gè)數(shù)也是不確定的,但由于提供隨機(jī)查找行中的數(shù)據(jù),所以每行的數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu),這里用長(zhǎng)度為MaxCol的數(shù)組存儲(chǔ)每行的數(shù)據(jù)。因此,該單鏈表中數(shù)據(jù)結(jié)點(diǎn)類(lèi)型定義如下: #define MaxCol 10/*最大列數(shù)*/ typedef struct Node1/*定義數(shù)據(jù)結(jié)點(diǎn)類(lèi)型*/ ElemType dataMaxCol; struct Node1 *next; /*指向后繼數(shù)據(jù)結(jié)點(diǎn)*/ DList,另外,需要指定每個(gè)表的行數(shù)和列數(shù),為此將單鏈表的頭結(jié)點(diǎn)類(lèi)型定義如下: typedef struct Node2/*定義頭結(jié)點(diǎn)類(lèi)型*/ int Row,Col;/*行數(shù)和列數(shù)*/ DList *next;/*指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/ HList; 采用尾插法建表方法創(chuàng)建單鏈表,用戶先輸入表的行數(shù)和列數(shù),然后輸入各行的數(shù)據(jù),為了簡(jiǎn)便,假設(shè)表中數(shù)據(jù)為int型,因此定義: typedef int ElemType; 對(duì)應(yīng)的建表算法如下,void create(HList *,采用尾插法建表,對(duì)應(yīng)的輸出