基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算課件

1、基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1第第2章章 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1 數(shù)據(jù)結(jié)構(gòu)的基本概念2.2 線性表及其順序存儲(chǔ)結(jié)構(gòu)2.3 線性鏈表及其運(yùn)算2.4 樹(shù)與二叉樹(shù)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算22.3 線性鏈表及其運(yùn)算線性鏈表及其運(yùn)算2.3.1 線性鏈表的基本概念2.3.2 線性鏈表的基本運(yùn)算2.3.3 循環(huán)鏈表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算32.3.1 線性鏈表的基本概念線性鏈表的基本概念1.線性鏈表線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算4基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算5基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算6基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算7基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算8依次輸出線性鏈表中的各結(jié)點(diǎn)值輸入：線性鏈表的存儲(chǔ)空間

2、V(1：m)、NEXT(1：m)； 線性鏈表的頭指針HEAD。輸出：依次輸出線性鏈表中各結(jié)點(diǎn)的值。 PROCEDURE PRTLL(HEAD) jHEAD WHILE (j0) DO OUTPUT V(j) ； jNEXT(j) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算9 struct 結(jié)構(gòu)體名 數(shù)據(jù)成員表； struct 結(jié)構(gòu)體名 *指針變量名； 例如 struct node char name10； /*數(shù)據(jù)域*/ char sex； /*數(shù)據(jù)域*/ struct node *next； /*指針域*/ 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算10#include stdlib.h/* malloc 函數(shù)需要包含頭文

3、件stdlib.h*/struct node /*定義結(jié)點(diǎn)類(lèi)型*/ int d； /*數(shù)據(jù)域*/ struct node *next； /*指針域*/main() struct node *p； /*定義該類(lèi)型的指針變量p*/ p=(struct node *)malloc(sizeof(struct node)； /*申請(qǐng)分配結(jié)點(diǎn)存儲(chǔ)空間*/ free(p)； /*釋放結(jié)點(diǎn)存儲(chǔ)空間*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算11#include stdlib.h#include stdio.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ int d； struct node *next； main() int

4、x； struct node *head， *p， *q； headNULL； /*置鏈表空*/ qNULL； scanf(“%d”， &x)； /*輸入一個(gè)正整數(shù)*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算12 while(x0) /*若輸入值大于0*/ p(struct node *)malloc(sizeof(struct node)；/*申請(qǐng)一個(gè)結(jié)點(diǎn)*/ pdx； pnextNULL； /*置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域和指針域*/ if(headNULL) headp；/*若鏈表空，則將頭指針指向當(dāng)前結(jié)點(diǎn)p*/ else qnextp； /*將當(dāng)前結(jié)點(diǎn)鏈接在最后*/ qp； /*置當(dāng)前結(jié)點(diǎn)為鏈表最后一個(gè)結(jié)點(diǎn)

5、*/ scanf(%d， &x)； phead； while(p!NULL) /*從鏈表第一個(gè)結(jié)點(diǎn)開(kāi)始打印各結(jié)點(diǎn)元素值，并刪除*/ printf(%5d， pd)； /*打印當(dāng)前結(jié)點(diǎn)中的數(shù)據(jù)*/ qp；ppnext；free(q)；/*刪除當(dāng)前結(jié)點(diǎn)并釋放該結(jié)點(diǎn)空間*/ printf(n)；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算13雙向鏈表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算142.帶鏈的棧帶鏈的?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算15可利用棧及其運(yùn)算基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算16將結(jié)點(diǎn)送回可利用棧輸入：可利用棧棧頂指針TOP（默認(rèn)）；送回可利用棧的結(jié)點(diǎn)序號(hào)p。輸出：結(jié)點(diǎn)p入棧后的可利用棧棧頂指針TOP（默認(rèn)）。 PROCEDURE DIS

6、POSE(p) NEXT(p)TOP； TOPp RETURN從可利用棧取得一個(gè)結(jié)點(diǎn)輸入：可利用棧的棧頂指針TOP（默認(rèn)）。輸出：退棧后的可利用棧棧頂指針TOP（默認(rèn)）；存放取得結(jié)點(diǎn)序號(hào) 的變量p。 PROCEDURE NEW(p) pTOP； TOPNEXT(TOP) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算17帶鏈棧的入棧運(yùn)算輸入：帶鏈棧的棧頂指針top；入棧的元素值x。輸出：元素x入棧后的帶鏈棧棧頂指針top。 PROCEDURE PUSHLL(top，x) NEW(p) 從可利用棧取得一個(gè)新結(jié)點(diǎn) V(p)x 置新結(jié)點(diǎn)數(shù)據(jù)域 NEXT(p)top 置新結(jié)點(diǎn)指針域 topp 改變棧頂指針 RETU

7、RN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算18#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； /*數(shù)據(jù)元素類(lèi)型*/ struct node *next； ；pushll(top，x)ET x； struct node *top； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnext*top；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/ *topp； /*改變棧頂指針*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算19帶鏈棧的退棧運(yùn)算輸入：帶鏈棧的棧頂指針top。輸出：退棧后的帶鏈棧棧頂指針top；存放

8、退出結(jié)點(diǎn)元素 值的變量y。 PROCEDURE POPLL(top，y) yV(top) 取出棧頂元素值 ptop top=NEXT(p) 改變棧頂指針 DISPOSE(p) 被刪除結(jié)點(diǎn)送回可利用棧 RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算20#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； /*數(shù)據(jù)元素類(lèi)型*/ struct node *next； ；popll(top，y)ET y； struct node *top； struct node *p； y*topd； /*取出棧頂元素值*/ p*top； *toppnext； /*改變棧頂指針*/ free

9、(p)； return； /*釋放被刪除結(jié)點(diǎn)后返回*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算213.帶鏈的隊(duì)列帶鏈的隊(duì)列基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算22帶鏈隊(duì)列的入隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的隊(duì)尾指針rear；入隊(duì)的新元素x。輸出：元素x入隊(duì)后的帶鏈隊(duì)列隊(duì)尾指針rear。 PROCEDURE ADDLL(rear，x) NEW(p) 從可利用棧取得一個(gè)新結(jié)點(diǎn)p V(p)x 置新結(jié)點(diǎn)的數(shù)據(jù)域 NEXT(p)0 置新結(jié)點(diǎn)的指針為空 NEXT(rear)p 最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn) rearp 改變隊(duì)尾指針 RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算23#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET

10、 d； /*數(shù)據(jù)元素類(lèi)型*/ struct node *next； ；addll(rear，x)ET x； struct node *rear； struct node *p； p(struct node *)malloc(sizeof(struct node)； pdx； pnextNULL； /*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/ *rearnextp； /*置最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)*/ *rearp； /*改變隊(duì)尾指針*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算24帶鏈隊(duì)列的退隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的排頭指針front。輸出：退隊(duì)后的帶鏈隊(duì)列排頭指針front；存放退出結(jié)點(diǎn) 值的變量y。 PR

11、OCEDURE DELLL(front，y) y=V(front) 取出排頭元素值 pfront frontNEXT(front) 改變排頭指針 DISPOSE(p) 釋放刪除的結(jié)點(diǎn) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算25#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； /*數(shù)據(jù)元素類(lèi)型*/ struct node *next； ；delll(front，y)ET y； struct node *front； struct node *p； y*frontd； /*取出排頭元素值*/ p*front； *frontpnext； /*改變排頭指針*/ fr

12、ee(p)； /*釋放被刪除結(jié)點(diǎn)*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算262.3.2 線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入 一個(gè)新元素。(2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。(4)將一個(gè)線性鏈表按要求進(jìn)行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復(fù)制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算271.在線性鏈表中查找指定元素在線性鏈表中查找指定元素在非空線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)p輸入：非空線性鏈表頭指針HEAD；被尋找元素x。輸出：非空線性鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)

13、p。PROCEDURE LOOKST(HEAD，x，p)pHEADWHILE (NEXT(p)0)and(V(NEXT(p)x) DO pNEXT(p)RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算28struct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； /*數(shù)據(jù)元素類(lèi)型*/ struct node *next； ；struct node *lookst(head，x)ET x； struct node *head； struct node *p； phead； while(pnext!NULL)&(pnext)d)!x) ppnext； return(p)；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算292.線性鏈表

14、的插入線性鏈表的插入 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中 插入一個(gè)新元素?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算30可利用棧與線性鏈表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算31(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p。 并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲，即V(p)b。(2)在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)q?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算32(3)將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后： 使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)，即 NEXT(p)NEXT(q) 使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p，即 NEXT(q)p基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算33線性鏈表的插入輸入：線性鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié) 點(diǎn)值x；插入的新元素b。輸出：插入后的線性鏈表。PR

15、OCEDURE INSLST(HEAD，x，b)1. NEW(p)2. V(p)b3. IF (HEAD0) THEN HEADp； NEXT(p)0； RETURN 4. IF (V(HEAD)x) THEN NEXT(p)HEAD； HEADp； RETURN 5. LOOKST(HEAD，x，q)6. NEXT(p)NEXT(q)； NEXT(q)p7. RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算34#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； struct node *next； ；inslst(head，x，b)ET x，b；struct node

16、 *head； struct node *p， *q； p(struct node *)malloc(sizeof(struct node)； pdb； /*置結(jié)點(diǎn)的數(shù)據(jù)域*/ if (*headNULL) /*鏈表為空*/ *headp；pnextNULL；return； if (*headd)x) /*在第一個(gè)結(jié)點(diǎn)前插入*/ pnext*head；*headp；return； qlookst(*head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/ pnextqnext；qnextp；/*結(jié)點(diǎn)p插到結(jié)點(diǎn)q之后*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算353.線性鏈表的刪除線性鏈表的刪除 在鏈?zhǔn)?/p>

17、存儲(chǔ)結(jié)構(gòu)下的線性表中 刪除包含指定元素的結(jié)點(diǎn)。基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算36可利用棧與線性鏈表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算37(1)尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。 則包含元素x的結(jié)點(diǎn)序號(hào)pNEXT(q)。(2)將結(jié)點(diǎn)q后的結(jié)點(diǎn)p刪除，即 NEXT(q)NEXT(p)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算38(3)將包含元素x的結(jié)點(diǎn)p送回可利用棧。基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算39線性鏈表的刪除輸入：線性鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的線性鏈表。PROCEDURE DELST(HEAD，x)1. IF (HEAD0) THEN “This is a empty list!”； RETURN 2. IF (V(HEA

18、D)x) THEN pNEXT (HEAD)；DISPOSE(HEAD)；HEADp； RETURN 3. LOOKST(HEAD，x，q)4. IF (NEXT(q)0) THEN “No this node in the list!”；RETURN 5. pNEXT(q)； NEXT(q)NEXT(p)6. DISPOSE(p)7. RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算40#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； struct node *next； ；delst(head，x)ET x；struct node *head； struct no

19、de *p， *q； if (*headNULL) /*鏈表為空*/ printf(This is a empty list!n)；return； if (*headd)x) /*刪除第一個(gè)結(jié)點(diǎn)*/ p*headnext；free(*head) ；*headp；return； qlookst(*head，x) ；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/ if (qnextNULL) /*鏈表中沒(méi)有包含元素x的結(jié)點(diǎn)*/ printf(No this node in the list!n)；return； pqnext ；qnextpnext； /*刪除結(jié)點(diǎn)p*/ free(p) ； /*釋放結(jié)點(diǎn)p*

20、/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算412.3.3 循環(huán)鏈表循環(huán)鏈表(1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)， 其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置， 指針域指向線性表第一個(gè)元素的結(jié)點(diǎn)。 循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。(2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不空， 而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算42(1)在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置， 就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)。(2)空表與非空表的運(yùn)算統(tǒng)一?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算43在頭指針為HEAD的循環(huán)鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；被尋找的元素x。輸出

21、：循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)p。PROCEDURE LOOKCST(HEAD，x，p)pHEADWHILE (NEXT(p)HEAD)and(V(NEXT(p)x) DO pNEXT(p)RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算44#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； struct node *next； ；struct node *lookcst(head，x)ET x； struct node *head； struct node *p； phead； while(pnext!head)&(pnext)d)!x) ppnext；

22、return(p)；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算45在頭指針為HEAD的循環(huán)鏈表中包含元素x的結(jié)點(diǎn)前插入新元素b輸入：循環(huán)鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié) 點(diǎn)值x；插入的新元素b。輸出：插入后的循環(huán)鏈表。PROCEDURE INSCST(HEAD，x，b)NEW(p) 從可利用棧取得一個(gè)新結(jié)點(diǎn)pV(p)b 置新結(jié)點(diǎn)p的數(shù)據(jù)域（插入的元素值b）LOOKCST(HEAD，x，q) 尋找循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)qNEXT(p)NEXT(q)；NEXT(q)p 將新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算46#include stdlib.hstruct node /*定義結(jié)點(diǎn)

23、類(lèi)型*/ ET d； struct node *next； ；inscst(head，x，b)ET x，b；struct node *head； struct node *p， *q； p(struct node *)malloc(sizeof(struct node)； pdb； /*置結(jié)點(diǎn)的數(shù)據(jù)域*/ qlookcst(head，x) ；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/ pnextqnext ；qnextp；/*結(jié)點(diǎn)p插入到結(jié)點(diǎn)q后*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算47在頭指針為HEAD的循環(huán)鏈表中刪除包含元素x的結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的

24、循環(huán)鏈表。PROCEDURE DELCST(HEAD，x)LOOKCST(HEAD，x，q) 尋找包含元素x的前一個(gè)結(jié)點(diǎn)qIF (NEXT(q)HEAD) THEN 循環(huán)鏈表中沒(méi)有該結(jié)點(diǎn) “No this node in the list!”；RETURN pNEXT(q)；NEXT(q)NEXT(p)刪除結(jié)點(diǎn)q后的結(jié)點(diǎn)DISPOSE(p) 將被刪除的結(jié)點(diǎn)p送回可利用棧RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算48#include stdlib.hstruct node /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； struct node *next； ；delcst(head，x)ET x；struct node

25、 *head； struct node *p， *q； qlookcst(head，x) ；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/ if (qnextNULL) /*鏈表中沒(méi)有包含元素x的結(jié)點(diǎn)*/ printf(No this node in the list!n)；return； pqnext ；qnextpnext； /*刪除結(jié)點(diǎn)p*/ free(p) ； /*釋放結(jié)點(diǎn)p*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算492.4 數(shù)數(shù) 組組2.4.1 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2.4.2 規(guī)則矩陣的壓縮2.4.3 一般稀疏矩陣的表示基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算502.4.1 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)1.

26、二維數(shù)組以行為主的順序存儲(chǔ)二維數(shù)組以行為主的順序存儲(chǔ)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算512.二維數(shù)組以列為主的順序存儲(chǔ)二維數(shù)組以列為主的順序存儲(chǔ)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算522.4.2 規(guī)則矩陣的壓縮規(guī)則矩陣的壓縮1.下三角矩陣的壓縮存儲(chǔ)下三角矩陣的壓縮存儲(chǔ)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算53用長(zhǎng)度為n(n1)/2的一維數(shù)組B，一行接一行存放A中下三角部分的元素?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算54用長(zhǎng)度為n(n1)/2的一維數(shù)組B，一列接一列存放A中下三角部分的元素?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算55基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算562.對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算573.三對(duì)角矩陣的壓縮存儲(chǔ)三對(duì)角矩陣的壓縮存儲(chǔ)基本數(shù)據(jù)結(jié)構(gòu)

27、及其運(yùn)算58用一個(gè)長(zhǎng)度為3n2的一維數(shù)組B存放三條對(duì)角線上的元素基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算59基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算602.4.3 一般稀疏矩陣的表示一般稀疏矩陣的表示1. 稀疏矩陣的三列二維數(shù)組表示稀疏矩陣的三列二維數(shù)組表示基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算61(1)非零元素所在的行號(hào)i；(2)非零元素所在的列號(hào)j；(3)非零元素的值V。即每一個(gè)非零元素可以用下列三元組表示： （i，j，V）基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算62（1，3，3）（1，8，1）（3，1，9）（4，5，7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算63（7，8，8）（1，3，3）（1，8，1）（3，1，9）（4，5，

28、7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算64基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算65POS(k)表示稀疏矩陣A中第k行的第一個(gè)非零元素 （如果有的話）在三列二維數(shù)組B中的行號(hào)；NUM(k)表示稀疏矩陣A中第k行中非零元素的個(gè)數(shù)。 POS(1)2 POS(k)POS(k1)NUM(k1) ， 2km基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算66構(gòu)造POS與NUM向量輸入：與稀疏矩陣A對(duì)應(yīng)的三列二維數(shù)組B。輸出：POS與NUM向量。PROCEDURE POSNUM(B，POS，NUM)tB(1，3) 非零元素個(gè)數(shù)mB(1，1) 稀疏矩陣行數(shù)FOR k1 TO m DO NUM(k)0 置NUM向

29、量初值FOR k2 TO t1 DO NUM(B(k,1)NUM(B(k,1)1設(shè)置NUM向量POS(1)2FOR k2 TO m DO POS(k)POS(k1)NUM(k1) 設(shè)置POS向量RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算67struct ab int i；/*稀疏矩陣A的行數(shù)或非零元素所在的行號(hào)*/ int j；/*稀疏矩陣A的列數(shù)或非零元素所在的列號(hào)*/ ET v；/*稀疏矩陣A中非零元素個(gè)數(shù)（用ET類(lèi)型表示的整數(shù)）或非零元素值*/ ；posnum(b，pos，num)struct ab b ；int *pos， *num； int k，m，t； mb0.i； t(int)(b0.v)

30、； for (k0； km； k) numk0； for (k1； kt； k) numbk.inumbk.i1； pos01； for (k1; km； k) poskposk1numk1； return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算682.十字鏈表十字鏈表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算69用十字鏈表表示稀疏矩陣的結(jié)構(gòu)特點(diǎn)(1)稀疏矩陣的每一行與每一列均用帶表頭結(jié)點(diǎn)的循環(huán)鏈 表表示。(2)表頭結(jié)點(diǎn)中的行域與列域的值均置為0 （即row0，col0）。(3)行、列鏈表的表頭結(jié)點(diǎn)合用，且這些表頭結(jié)點(diǎn)通過(guò)值 域（即val）相鏈接，并再增加一個(gè)結(jié)點(diǎn)作為它們的 表頭結(jié)點(diǎn)H，其行、列域值分別存放稀疏矩陣的行數(shù) 與列數(shù)。只

31、要給出頭指針H的值，便可掃描到稀疏矩陣中的任意一個(gè)非零元素?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算70基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算71基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算722.5 樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)2.5.1 樹(shù)的基本概念2.5.2 二叉樹(shù)及其基本性質(zhì)2.5.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2.5.4 二叉樹(shù)的遍歷2.5.5 穿線二叉樹(shù)2.5.6 表達(dá)式的線性化基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算732.5.1 樹(shù)的基本概念樹(shù)的基本概念基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算74基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算75基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算76基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算77(1)表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng) 一個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)。(2)運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn) 算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中

32、的順序?yàn)閺淖?到右）。(3)運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算78a*(bc/d)e*hg*f(s，t，xy)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算79a*(bc/d)e*hg*f(s，t，xy)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算80樹(shù)鏈表中的結(jié)點(diǎn)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算812.5.2 二叉樹(shù)及其基本性質(zhì)二叉樹(shù)及其基本性質(zhì)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算821.什么是二叉樹(shù)什么是二叉樹(shù) (1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； (2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié) 點(diǎn)的左子樹(shù)與右子樹(shù)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算832.二叉樹(shù)的基本性質(zhì)二叉樹(shù)的基本性質(zhì)性質(zhì)性質(zhì)1 1 在二叉樹(shù)的第k層上，最多有2k1(k1)個(gè) 結(jié)點(diǎn)。性質(zhì)性質(zhì)

33、2 2 深度為m的二叉樹(shù)最多有2m1個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)3 3 在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn) （即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)性質(zhì)4 4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為 log2n1 其中l(wèi)og2n表示取log2n的整數(shù)部分?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算843.滿(mǎn)二叉樹(shù)與完全二叉樹(shù)滿(mǎn)二叉樹(shù)與完全二叉樹(shù)(1) 滿(mǎn)二叉樹(shù)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算85(2)完全二叉樹(shù)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算86基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算87性質(zhì)性質(zhì)5 5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n1。性質(zhì)性質(zhì)6 6 設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始， 按層序（每一層從左到右）用自然數(shù)1，2，n 給結(jié)點(diǎn)進(jìn)行編號(hào)，則

34、對(duì)于編號(hào)為k(k1，2，n) 的結(jié)點(diǎn)有以下結(jié)論： (1)若k1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)； 若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。 (2)若2kn，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k； 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。 (3)若2k1n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào) 為2k1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算882.5.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1.二叉鏈表二叉鏈表 #include stdlib.h struct btnode /*定義結(jié)點(diǎn)類(lèi)型*/ ET d； /*數(shù)據(jù)域*/ struct btnode *lchild； /*左指針域*/

35、struct btnode *rchild； /*右指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算89基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算90基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算91基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算922.二叉鏈表的生成二叉鏈表的生成(1)輸入根結(jié)點(diǎn)值；(2)若左子樹(shù)不空，則輸入左子樹(shù)，否則輸入一個(gè)結(jié)束符；(3)若右子樹(shù)不空，則輸入右子樹(shù)，否則輸入一個(gè)結(jié)束符。 例如， FCADBEGHP其中表示結(jié)束符基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算93二叉鏈表的生成輸入：二叉鏈表的頭指針BT為空；根結(jié)點(diǎn)標(biāo)志k0。輸出：二叉鏈表的頭指針BT。PROCEDURE CREATBT(BT，k)INPUT b IF b結(jié)束符 THEN 輸入的不是結(jié)束符 NEW(p) 取

36、一個(gè)新結(jié)點(diǎn) V(p)b； L(p)0； R(p)0 置新結(jié)點(diǎn)的值域?yàn)閎及左右指針域 IF k0 THEN BTp 若是第一個(gè)值，則置二叉鏈表頭指針 IF k1 THEN L(BT)p 鏈接到左子樹(shù) IF k2 THEN R(BT)p 鏈接到右子樹(shù) CREATBT(p，1) 輸入左子結(jié)點(diǎn)值 CREATBT(p，2) 輸入右子結(jié)點(diǎn)值 RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算94#include stdio.h”#include stdlib.h”struct btnode int d； struct btnode *lchild； struct btnode *rchild； ；struct btnode

37、 *creatbt(bt，k)struct btnode *bt；int k； int b； struct btnode *p， *t； printf(input b ：)； scanf(%d，&b)；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算95 if (b!0) /*輸入的不是結(jié)束符*/ p(struct btnode *)malloc(sizeof(struct btnode)； pdb； plchildNULL； prchildNULL； if (k0) tp；/*若是第1個(gè)值，則置二叉鏈表頭指針*/ if (k1) btlchildp； /*鏈接到左子樹(shù)*/ if (k2) btrchildp；

38、/*鏈接到右子樹(shù)*/ creatbt(p，1)； /*輸入左子結(jié)點(diǎn)值*/ creatbt(p，2)； /*輸入右子結(jié)點(diǎn)值*/ return(t)/*返回二叉鏈表頭指針*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算962.5.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷1.前序遍歷前序遍歷(DLR)若二叉樹(shù)為空，則結(jié)束返回。否則：(1)訪問(wèn)根結(jié)點(diǎn)；(2)前序遍歷左子樹(shù)；(3)前序遍歷右子樹(shù)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算97輸入：二叉鏈表的頭指針BT。輸出：以BT為頭指針的二叉鏈表的前序序列。 PROCEDURE PRETRAV(BT) IF BT0 THEN OUTPUT V(BT) PRETRAV(L(BT) PRETRAV(R(BT)

39、RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算98#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；pretrav(bt)struc btnode *bt； if (bt !NULL) printf(%dn，btd)； pretrav(btlchild)； pretrav(btrchild)； return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算992.中序遍歷中序遍歷(LDR)若二叉樹(shù)為空，則結(jié)束返回。否則：(1)中序遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)中序遍歷左子樹(shù)。基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算100輸入：二叉鏈表的頭指

40、針BT。輸出：以BT為頭指針的二叉鏈表的中序序列。 PROCEDURE INTRAV(BT) IF BT0 THEN INTRAV(L(BT) OUTPUT V(BT) INTRAV(R(BT) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算101#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；intrav(bt)struc btnode *bt； if (bt !NULL) intrav(btlchild)； printf(%dn，btd)； intrav(btrchild)； return；基

41、本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1023.后序遍歷后序遍歷(LRD)若二叉樹(shù)為空，則結(jié)束返回。否則：(1)后序遍歷左子樹(shù)；(2)后序遍歷左子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算103輸入：二叉鏈表的頭指針BT。輸出：以BT為頭指針的二叉鏈表的后序序列。 PROCEDURE POSTRAV(BT) IF BT0 THEN POSTRAV(L(BT) POSTRAV(R(BT) OUTPUT V(BT) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算104#include stdio.hstruct btnode int d；struct btnode *lchild；struct btnode *rchild；pos

42、trav(bt)struc btnode *bt； if (bt !NULL) postrav(btlchild)； postrav(btrchild)； printf(%dn，btd)； return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1052.5.5 穿線二叉樹(shù)穿線二叉樹(shù)1.穿線二叉樹(shù)的概念穿線二叉樹(shù)的概念基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1062.穿線二叉樹(shù)的構(gòu)造穿線二叉樹(shù)的構(gòu)造基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算107基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算108 struct btnode ET d； /*數(shù)據(jù)域*/ int lflag； /*左標(biāo)志域*/ int rflag； /*右標(biāo)志域*/ struct btnode *lchild；/*左

43、指針域*/ struct btnode *rchild；/*右指針域*/ 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算109(1)若上次訪問(wèn)到的結(jié)點(diǎn)的右指針為空，則 將當(dāng)前訪問(wèn)到的結(jié)點(diǎn)序號(hào)的負(fù)值填入；(2)若當(dāng)前訪問(wèn)到的結(jié)點(diǎn)的左指針為空，則 將上次訪問(wèn)到的結(jié)點(diǎn)序號(hào)的負(fù)值填入?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算110構(gòu)造中序穿線二叉樹(shù)輸入：二叉鏈表的頭指針BT；h0。輸出：在二叉鏈表中加中序線索。PROCEDURE INTHREAD(BT，h)IF BT0 THEN INTHREAD(L(BT)，h) IF (h0)and(R(h)0) THEN R(h)BT； Rflag(h)1 IF L(BT)0 THEN L(BT)h； Lf

44、lag(BT)1 hBT INTHREAD(R(BT)，h) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算111 struct btnode ET d； /*數(shù)據(jù)域*/ int lflag； /*左標(biāo)志域*/ int rflag； /*右標(biāo)志域*/ struct btnode *lchild； /*左指針域*/ struct btnode *rchild； /*右指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算112 inthread(bt，h) struct btnode *bt， *h； if (bt!NULL) inthread(btlchild，h)； if (btlchildNULL) btlchild*h；

45、 btlflag1； if (*h!NULL)&(*h)rchildNULL) (*h)rchildbt； (*h)rflag1； *hbt； inthread(btrchild，h)； return； 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1133.穿線二叉樹(shù)的遍歷穿線二叉樹(shù)的遍歷從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿左鏈找到葉子結(jié)點(diǎn)，該葉子結(jié)點(diǎn)即為中序序列的第一個(gè)結(jié)點(diǎn)。然后從中序序列的第一個(gè)結(jié)點(diǎn)開(kāi)始掃描，依次找出中序序列中的后件。其規(guī)則如下： 若當(dāng)前結(jié)點(diǎn)的右標(biāo)志值為1，則當(dāng)前結(jié)點(diǎn)的指針值為其后件 的存儲(chǔ)序號(hào)； 若當(dāng)前結(jié)點(diǎn)的右指針值不空，則沿右子樹(shù)的左鏈進(jìn)行搜索， 直到發(fā)現(xiàn)某個(gè)結(jié)點(diǎn)的左標(biāo)志值為1且左指針值不空為止，

46、該 結(jié)點(diǎn)即為當(dāng)前結(jié)點(diǎn)的后件?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算114中序穿線二叉樹(shù)的遍歷輸入：二叉鏈表的頭指針BT。輸出：中序遍歷序列。PROCEDURE INTHTRAV(BT)IF BT0 THEN RETURNhBTWHILE (Lflag(h)0) DO hL(h) 沿左鏈找到第一個(gè)結(jié)點(diǎn)OUTPUT V(h) 輸出第一個(gè)結(jié)點(diǎn)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算115WHILE (R(h)0) DO IF (Rflag(h)1) THEN hR(h) ELSE hR(h) WHILE (Lflag(h)0)and(L(h)0) DO hL(h) OUTPUT V(h) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算116struc

47、t btnode int d； /*數(shù)據(jù)域，假設(shè)為整型*/ int lflag； /*左標(biāo)志域*/ int rflag； /*右標(biāo)志域*/ struct btnode *lchild；/*左指針域*/ struct btnode *rchild；/*右指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算117inthtrav(bt)struct btnode *bt； struct btnode *h； if (btNULL) return； hbt； while (hlflag0) hhlchild； printf(%dn，hd)；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算118 while (hrchild!NULL) if (

48、hrflag1) hhrchild； else hhrchild； while (hlflag0)&(hlchild!NULL) hhlchild； printf(%dn，hd)； return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1192.5.6 表達(dá)式的線性化表達(dá)式的線性化1.有序樹(shù)的二叉樹(shù)表示有序樹(shù)的二叉樹(shù)表示將有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的原則：(1)有序樹(shù)T中的結(jié)點(diǎn)與二叉樹(shù)BT中的結(jié)點(diǎn)一一對(duì)應(yīng)；(2)有序樹(shù)T中某個(gè)結(jié)點(diǎn)N的第一個(gè)子結(jié)點(diǎn)（即最左邊的子 結(jié)點(diǎn)）N1，在二叉樹(shù)BT中為對(duì)應(yīng)結(jié)點(diǎn)N的左子結(jié)點(diǎn)；(3)有序樹(shù)T中某個(gè)結(jié)點(diǎn)N的第一個(gè)子結(jié)點(diǎn)以后的其他子結(jié) 點(diǎn)，在二叉樹(shù)BT中被依次鏈接成一串起始于N1的右

49、子結(jié)點(diǎn)?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算120a*(bc/d)e*hg*f(s，t，xy)基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算121基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1222.表達(dá)式的線性化表達(dá)式的線性化(1)將表達(dá)式用有序樹(shù)表示，即構(gòu)造表達(dá)式樹(shù)。(2)將表達(dá)式樹(shù)化為二叉樹(shù)。(3)對(duì)相應(yīng)的二叉樹(shù)進(jìn)行中序遍歷，其遍歷序列即為表達(dá) 式的波蘭表示式?；緮?shù)據(jù)結(jié)構(gòu)及其運(yùn)算123表達(dá)式 a*(bc/d)e*hg*f(s，t，xy)的波蘭表示式為 a b c d / * e h * g s t x y f * 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1242.6 圖圖2.6.1 圖的基本概念2.6.2 圖的存儲(chǔ)結(jié)構(gòu)2.6.3 圖的遍歷基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1252.6

50、.1 圖的基本概念圖的基本概念基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算126基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1272.6.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)1.關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣長(zhǎng)度為n的一維數(shù)組D(1：n)存放圖中各數(shù)據(jù)結(jié)點(diǎn)的信息。n階的二維數(shù)組R(1：n，1：n)存放圖中各結(jié)點(diǎn)的關(guān)聯(lián)息。其中二維數(shù)組R稱(chēng)為圖的關(guān)聯(lián)矩陣。在關(guān)聯(lián)矩陣R中，每一個(gè)元素R(i，j) (1in，1jn)的定義為基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算128基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算129基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算130基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算131基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1322.求值矩陣求值矩陣基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算133基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1343.鄰接表鄰接表（“順序索引鏈接”存儲(chǔ)結(jié)構(gòu)）基本

51、數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算135基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算136基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算137struct node /*單鏈表中結(jié)點(diǎn)結(jié)構(gòu)*/ int num；/*圖中結(jié)點(diǎn)編號(hào)*/ ET1 val；/*求值函數(shù)*/ struct node *next；/*指針域*/ ；struct gpnode /*順序存儲(chǔ)空間中結(jié)點(diǎn)結(jié)構(gòu)*/ ET data； /*結(jié)點(diǎn)值*/ struct node *link；/*指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算138圖鄰接表的構(gòu)造輸入：圖的結(jié)點(diǎn)數(shù)n；依次存放圖中結(jié)點(diǎn)值的數(shù)組D(1：n)。輸出：鄰接表順序存儲(chǔ)空間的首地址。PROCEDURE CREATGP(D，n)定義DATA(1：n)，L

52、INK(1：n) 建立順序存儲(chǔ)空間FOR k0 TO n DO DATA(k)Dk； LINK(k)0 INPUT m，v /*輸入圖中第k個(gè)結(jié)點(diǎn)的后件信息*/ WHILE (m0) DO /*輸入后件信息未結(jié)束*/ NEW(p) /*分配單鏈表結(jié)點(diǎn)*/ NUM(p)m； VAL(p)v；NEXT(p)LINK(k)；LINK(k)p INPUT m，v /*繼續(xù)輸入后件信息*/ RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1392，63（回車(chē)）3，95（回車(chē)）4，84（回車(chē)）1，1（回車(chē)）（結(jié)點(diǎn)A的后件）1，63（回車(chē)）3，49（回車(chē)）4，44（回車(chē)）5，37（回車(chē)）1，1（回車(chē)） （結(jié)點(diǎn)B的后件）1，

53、95（回車(chē)）2，49（回車(chē)）1，1（回車(chē)）（結(jié)點(diǎn)C的后件）1，84（回車(chē)）2，44（回車(chē)）5，35（回車(chē)）1，1（回車(chē)）（結(jié)點(diǎn)D的后件）2，37（回車(chē)）4，35（回車(chē)）1，1（回車(chē)）（結(jié)點(diǎn)E的后件）基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算140#include stdio.h #include stdlib.hstruct node /*單鏈表中結(jié)點(diǎn)結(jié)構(gòu)*/ int num； /*圖中結(jié)點(diǎn)編號(hào)*/ int val； /*求值函數(shù)*/ struct node *next； /*指針域*/ ；struct gpnode /*順序存儲(chǔ)空間中結(jié)點(diǎn)結(jié)構(gòu)*/ char data； /*結(jié)點(diǎn)值*/ struct node *l

54、ink； /*指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算141struct gpnode *creatgp(d，n)/*該函數(shù)返回順序存儲(chǔ)空間的首地址*/int n；char d； struct gpnode *head； struct node *p； int k，m，v； head(struct gpnode *)malloc(n*sizeof(struct gpnode)； for (k0；kn；k) /*依次對(duì)圖中的每一個(gè)結(jié)點(diǎn)建立鏈接所有后件的單鏈表*/ (headk)datadk； /*置順序存儲(chǔ)空間的結(jié)點(diǎn)值*/ (headk)linkNULL；/*置順序存儲(chǔ)空間結(jié)點(diǎn)指針域?yàn)榭?/ prin

55、tf(input linked list of %c :n，dk)； scanf(“%d%d”，&m，&v)； /*輸入圖中第k個(gè)結(jié)點(diǎn)的后件信息*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算142 while (m0) /*輸入后件信息未結(jié)束*/ p(struct node *)malloc(sizeof(struct node)； pnumm； pvalv；/*后件結(jié)點(diǎn)號(hào)與求值函數(shù)值*/ pnext(headk)link；/*新結(jié)點(diǎn)指針指向頭結(jié)點(diǎn)*/ (headk)linkp； /*將新結(jié)點(diǎn)鏈接到單鏈表鏈頭*/ scanf(%d%d，&m，&v)；/*繼續(xù)輸入后件信息*/ retu

56、rn(head)；/*返回順序存儲(chǔ)空間的首地址*/基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1434.鄰接多重表鄰接多重表基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1442.6.3 圖的遍歷圖的遍歷1.縱向優(yōu)先搜索法縱向優(yōu)先搜索法從圖中某一結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，然后進(jìn)行以下過(guò)程：(1)處理或輸出當(dāng)前結(jié)點(diǎn)，記錄當(dāng)前結(jié)點(diǎn)的查訪標(biāo)志。(2)若當(dāng)前結(jié)點(diǎn)有后件結(jié)點(diǎn)，則取第一個(gè)后件結(jié)點(diǎn)。 若該后件結(jié)點(diǎn)未被查訪過(guò)，則以該后件結(jié)點(diǎn)為當(dāng) 前結(jié)點(diǎn)用縱向優(yōu)先搜索法進(jìn)行查訪。已被訪問(wèn)過(guò)結(jié)點(diǎn)未被訪問(wèn)過(guò)結(jié)點(diǎn)k1k0)k(MARK基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算145縱向優(yōu)先搜索法遍歷圖的遞歸算法輸入：圖中結(jié)點(diǎn)數(shù)n；鄰接表順序存儲(chǔ)空間DATA(1：n) 與LINK(1：n)；單鏈表

57、的存儲(chǔ)空間NUM與NEXT。輸出：遍歷序列。PROCEDURE DFSGP(DATA，LINK，n，NUM，NEXT)定義標(biāo)志數(shù)組MARK(1：n)FOR k1 TO n DO MARK(k)0 標(biāo)志數(shù)組初始化k1FOR k1 TO n DODFS(DATA，LINK，k，MARK) IF MARK(k)0 THEN DFS(DATA，LINK，k，MARK)RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算146PROCEDURE DFS(DATA，LINK，k，MARK，NUM，NEXT) OUTPUT DATA(k) 處理或輸出當(dāng)前結(jié)點(diǎn)值MARK(k)1 記錄當(dāng)前結(jié)點(diǎn)的查訪標(biāo)志pLINK(k) 當(dāng)前結(jié)點(diǎn)的

58、第一個(gè)后件結(jié)點(diǎn)WHILE (p0) DO 存在后件結(jié)點(diǎn) kNUM(p) 后件結(jié)點(diǎn)的結(jié)點(diǎn)編號(hào) IF MARK(k)0 THEN 該后件結(jié)點(diǎn)未被查訪過(guò) DFS(DATA，LINK，k，MARK，NUM，NEXT) pNEXT(p) 下一個(gè)后件結(jié)點(diǎn) RETURN基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算147#include stdlib.h#include “stdio.h”struct node /*單鏈表中結(jié)點(diǎn)結(jié)構(gòu)*/ int num； /*圖中結(jié)點(diǎn)編號(hào)*/ int val； /*求值函數(shù)*/ struct node *next；/*指針域*/ ；struct gpnode /*順序存儲(chǔ)空間中結(jié)點(diǎn)結(jié)構(gòu)*/ char

59、 data； /*結(jié)點(diǎn)值*/ struct node *link； /*指針域*/ ；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算148dfsgp(head，n)struct gpnode *head；int n； int k，*mark； markmalloc(n*sizeof(int)；/*定義標(biāo)志數(shù)組空間*/ for (k0； kn； k) markk0；/*標(biāo)志數(shù)組初始化*/ k1； /* for (k1； kn； k) */ dfs(head，k，mark)； /* if (markk10) dfs(head，k，mark)；*/ printf(n)； free(mark)； /*釋放標(biāo)志數(shù)組空空間*/ r

60、eturn；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算149static dfs(head，k，mark) /*遞歸函數(shù)*/struct gpnode *head；int k，*mark； struct node *p； printf(%c，(headk1)data)；/*輸出當(dāng)前結(jié)點(diǎn)值*/ markk11；/*記錄當(dāng)前結(jié)點(diǎn)的查訪標(biāo)志*/ p(headk1)link； /*當(dāng)前結(jié)點(diǎn)的第一個(gè)后件結(jié)點(diǎn)*/ while (p!NULL) /*還存在后件結(jié)點(diǎn)*/ if (mark(pnum)10) /*該后件結(jié)點(diǎn)未被查訪過(guò)*/ dfs(head，pnum，mark)；/*遞歸調(diào)用*/ ppnext；/*下一個(gè)后件結(jié)點(diǎn)*/ return；基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算150縱向優(yōu)先搜索法遍歷圖的非遞歸算法輸入：圖中的結(jié)點(diǎn)數(shù)n；鄰接表的順序存儲(chǔ)空間DATA(1：n