數(shù)據(jù)結(jié)構(gòu)實(shí)用教程習(xí)題答案

1、1 緒論回答下列概念：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，算法數(shù)據(jù)結(jié)構(gòu) : 按照某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，用一定的存儲(chǔ)方式存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義一個(gè)運(yùn)算的集合，就稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu): 數(shù)據(jù)元素之間的邏輯關(guān)系，是根據(jù)實(shí)際問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu): 是指數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映射。算法 : 是指對(duì)數(shù)據(jù)元素進(jìn)行加工和處理數(shù)據(jù)結(jié)構(gòu)研究的三方面內(nèi)容是什么？它們之間有什么聯(lián)系和區(qū)別？三方面內(nèi)容 : 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算的集合。聯(lián)系和區(qū)別：數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)學(xué)模型，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指邏輯結(jié)構(gòu)到存儲(chǔ)區(qū)域的映射，運(yùn)算是定義在

2、邏輯結(jié)構(gòu)上，實(shí)現(xiàn)在存儲(chǔ)結(jié)構(gòu)上。簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)中討論的三種經(jīng)典結(jié)構(gòu)及其邏輯特征。三種經(jīng)典結(jié)構(gòu)：線性表、樹(shù)和圖。線性表：有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著一對(duì)一的相互關(guān)系。樹(shù)： 有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)， 可有若干個(gè)終端結(jié)點(diǎn)， 其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)，可以有若干個(gè)后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著一對(duì)多的層次關(guān)系。圖：可有若干個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)可以有若干個(gè)前趨結(jié)點(diǎn)和若干個(gè)后繼結(jié)點(diǎn)，數(shù)據(jù)元素間存在著多對(duì)多的網(wǎng)狀關(guān)系。實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的常用存儲(chǔ)方法有哪幾種？簡(jiǎn)述各種方法的基本思想。常用存儲(chǔ)方法有四種：順序存儲(chǔ)、鏈接

3、存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。各種方法的基本思想：順序存儲(chǔ)：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里。鏈接存儲(chǔ)：通過(guò)附加指針域表示數(shù)據(jù)元素之間的關(guān)系。索引存儲(chǔ)：除了存儲(chǔ)數(shù)據(jù)元素，還要建立附加索引表來(lái)標(biāo)識(shí)數(shù)據(jù)元素的地址。散列存儲(chǔ)：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，稱為關(guān)鍵字地址轉(zhuǎn)換法。算法的特性是什么？如何定性的評(píng)價(jià)一個(gè)算法的優(yōu)劣？算法的特性：有窮性、確定性、可行性、輸入、輸出。算法的定性評(píng)價(jià)標(biāo)準(zhǔn)有：正確性、可讀性、健壯性、簡(jiǎn)單性。算法的定量評(píng)價(jià)標(biāo)準(zhǔn)是什么？算法的定量評(píng)價(jià)標(biāo)準(zhǔn)有：時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度：是一個(gè)算法運(yùn)行時(shí)所耗費(fèi)的系統(tǒng)時(shí)間，也就是算法的時(shí)間效率?？?/p>

4、間復(fù)雜度：是一個(gè)算法運(yùn)行時(shí)所耗費(fèi)的存儲(chǔ)空間，也就是算法的空間效率。寫出下列程序段中帶標(biāo)號(hào)語(yǔ)句的頻度，并給出執(zhí)行各程序段的時(shí)間復(fù)雜度（ n 為整數(shù)） 。i=1;while ( in ) do【 1】 i+;s=0;for(i=l;i=i;j-)【 1 】 s=s+i+j;5) i=1 ；while ( in ) do( 2) s=1;for(i=1;i=n;i+)【 1】 s=s*i;( 4) i=1;while(i*i=n)【 1 】 i+;x=1;y=100;do1 i=i*2;答：(1) n-1, O(n)(4)而O()而2線性表【1】While(x0)個(gè)數(shù)據(jù)元素的有限序列。順序表：順序表

5、(Sequential List)是采用順序存儲(chǔ)結(jié)構(gòu)的線性表。單鏈表：每個(gè)結(jié)點(diǎn)只附加一個(gè)指向后繼的指針域，這樣的鏈表稱為單鏈表(Single Linked List )靜態(tài)鏈表：用數(shù)組實(shí)現(xiàn)的鏈表，指針就變換為數(shù)組的下標(biāo)，結(jié)點(diǎn)即為數(shù)組中的下標(biāo)變量，由于 需要預(yù)先分配一個(gè)較大的數(shù)組空間，因此這種鏈表稱之為靜態(tài)鏈表。比較順序表和鏈表這兩種線性表不同存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。.邏輯關(guān)系的表示：順序表隱含表示關(guān)系，鏈表顯示表示關(guān)系。.存儲(chǔ)密度：順序表的存儲(chǔ)密度大，而鏈表的存儲(chǔ)密度小。.存儲(chǔ)分配方式：順序表的存儲(chǔ)空間是預(yù)先靜態(tài)分配的一塊連續(xù)存儲(chǔ)空間，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模。鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，

6、動(dòng)態(tài)分配和釋放存 儲(chǔ)空間，存儲(chǔ)空間可連續(xù)也可不連續(xù)。.存取方法：順序表可以隨機(jī)存取，鏈表必須順序存取。.插入、刪除操作：在順序表中做插入、刪除時(shí)平均移動(dòng)表中一半的元素；在鏈表中作插入、 刪除時(shí)，只要修改指針域，而不需要移動(dòng)元素。所以順序表的插入、刪除 效率低，鏈表的插入、刪除效率高。.實(shí)現(xiàn)語(yǔ)言：順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類型。而鏈表的操作是基于指針的， 對(duì)于沒(méi)有提供指針類型的高級(jí)語(yǔ)言，必須采用靜態(tài)鏈表?？傊?，兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇那一種由實(shí)際問(wèn)題中的主要因素決定。通?！拜^穩(wěn)定”的 線性表選擇順序存儲(chǔ)，而頻繁做插入、刪除的線性表，即動(dòng)態(tài)性較強(qiáng)的線性表宜選擇鏈接存儲(chǔ)。.3 已知長(zhǎng)度

7、為n的線性表A中的元素是整數(shù)，寫算法求線性表中值大于item的元素個(gè)數(shù)。分兩種情況編寫函數(shù)：(1)線性表采用順序存儲(chǔ)；(2)線性表采用單鏈表存儲(chǔ)。(1)線性表采用順序存儲(chǔ)#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item) int i,j=0;for(i=0;ilast ;i+)if( L-datai item )j+;return j;( 2 )線性表采用單鏈表存儲(chǔ)typedef int

8、DataType;typedef struct Node DataType data;struct Node *next;LinkList;LinkList *locateElem(LinkList *L, DataType item ) LinkList *p=L-next;int i=0;while ( p )if( p-data item) i+; p=p-next; return i ;.4 已知長(zhǎng)度為 n 的線性表 A 中的元素是整數(shù)，寫算法刪除線性表中所有值為 item 的數(shù)據(jù)元素。 分兩種情況編寫函數(shù)： ( 1 )線性表采用順序存儲(chǔ)；( 2 )線性表采用單鏈表存儲(chǔ)。( 1 )線性

9、表采用順序存儲(chǔ)#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item) int i=0;While(ilast)if( L-datai =item )for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last -; Else i+;( 2 )線性表采用單鏈表存儲(chǔ)typedef int DataType;typedef struct NodeDataType dat

10、a;struct Node *next;LinkList;int deleteDupNode(LinkList *L, DataType item)LinkList *p,*q,*r;q= L; p=L-next;while (p)if (p-data=item) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; 設(shè)長(zhǎng)度為Max 的順序表L 中包含 n 個(gè)整數(shù)且遞增有序。試寫一算法，將x 插入到順序表的適當(dāng)位置上，以保持表的有序性，并且分析算法的時(shí)間復(fù)雜度。#define MAX 1024typedef int DataType; ty

11、pedef struct DataType dataMAX; int last; SeqList; int inserts(SeqList *L, DataType x) int i;if (L-last = Max-1) printf( full); return 0; i= L-last;while(i=0& L-datai x)L-data i+1= L-data i-;/ “相當(dāng)于 L-data i+1= L-data i ; i-;“L-data i+1=x; L-last +; return 1; 設(shè)帶頭結(jié)點(diǎn)的單鏈表L中的數(shù)據(jù)元素是整型數(shù)且遞增有序。試寫一算法，將 x插入到單鏈表的

12、適當(dāng)位置上，以保持表的有序性，并且分析算法的時(shí)間復(fù)雜度。typedef int DataType;typedef struct Node DataType data;struct Node *next;LinkList;void InsertList(LinkList *L,datetype x)LinkList *p,*s;s=(LinkList *)malloc(sizeof(Linklist);s-data=x;p=L;while(p-next)&(p-next-datanext;s-next=p-next; p-next=s; 試寫一算法實(shí)現(xiàn)對(duì)不帶頭結(jié)點(diǎn)的單鏈表H進(jìn)行就地逆置。type

13、def int DataType;typedef struct Node DataType data;struct Node *next;LinkList;LinkList * Reverse(LinkList * H) LinkList *p,*q;if (!H) return;p=H-next; q=H-next; H-next=NULL;While(q)q=q-next; p-next= H; H =p;p=q;return H;若帶頭結(jié)點(diǎn)的單鏈表L 中的數(shù)據(jù)元素是整型數(shù)，編寫算法對(duì)單鏈表L 進(jìn)行排序。typedef int DataType;typedef struct Node Da

14、taType data;struct Node *next;LinkList;void InsertList(LinkList *L)LinkList *p,*q,*s;if (!L-next | ！ L-next-next) return;q= L-next-next; L-next-next= NULL;while(q)s=q; q=q-next;p=L;while(p-next)&(p-next-datadata ) p=p-next;s-next=p-next; p-next=s;設(shè)單鏈表X和單鏈表Y分別存儲(chǔ)了兩個(gè)字符串，設(shè)計(jì)算法找出X中第一個(gè)不在 Y中出現(xiàn)的字符。typedef ch

15、ar DataType;typedef struct Node DataType data;struct Node *next;LinkList;linklist *search(linklist *x, linklist *y)linklist *p,*q;p=x; q=y;while(p&q)if(p-data!=q-data) q=q-next; else p=p-next; q=y; return p; 已知遞增有序的兩個(gè)單鏈表A 和 B 各存儲(chǔ)了一個(gè)集合。設(shè)計(jì)算法實(shí)現(xiàn)求兩個(gè)集合的交集運(yùn)算C=AO Botypedef int DataType;typedef struct NodeDa

16、taType data;struct Node *next;LinkList;LinkList *union(LinkList *A,LinkList *B)LinkList *C, *p,*q,*s*r;p=A-next;q=B-next;C=A; r=C;while (p&q) if (p-data=q-data) r-next=p; r=p;p=p-next; q=q-next;else if (p-datadata) p=p-next;else q=q-next;r-next= NULL ; free(B); return C;已知遞增有序的兩個(gè)單鏈表A和B,編寫算法將 A、B歸并成一

17、個(gè)遞增有序的單鏈表C。typedef int DataType;typedef struct NodeDataType data;struct Node *next;LinkList;LinkList *union(LinkList *A,LinkList *B)LinkList *C, *p,*q,*s*r;p=A-next;q=B-next;C=A; r=C;while (p&q) if (p-datadata) s=p; p=p-next; else s=q; q=q-next; r-next=s;r=s;if (!q) r-next=q;else r-next=p;free(B); r

18、eturn C;3 棧和隊(duì)列回答下列概念：棧，隊(duì)列，順序棧，鏈隊(duì)列棧： 棧( Stack )是運(yùn)算受限的線性表，限制它的插入和刪除操作僅在表的一端進(jìn)行。隊(duì)列： 只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，將這種線性表稱為隊(duì)或隊(duì)列( Queue) 。順序棧： 采用順序方式存儲(chǔ)的棧稱為順序棧(Sequential Stack) 。鏈隊(duì)列： 采用鏈接方法存儲(chǔ)的隊(duì)列稱為鏈隊(duì)列( Linked Queue ) 。棧和隊(duì)列各有什么特點(diǎn)？簡(jiǎn)述棧、隊(duì)列和線性表的差別。棧(Stack)是運(yùn)算受限的線性表，限制它的插入和刪除操作僅在表的一端進(jìn)行，又稱為后進(jìn)先出的線性表( Last In First Out

19、) ，簡(jiǎn)稱 LIFO 表。只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，將這種線性表稱為隊(duì)或隊(duì)列(Queue) ，又叫先進(jìn)先出的線性表，簡(jiǎn)稱為 FIFO (First In First Out ) 表。這三種結(jié)構(gòu)有很多的相似之處，其差別主要體現(xiàn)在運(yùn)算上，具有不同的運(yùn)算特點(diǎn)。同線性表的運(yùn)算相比，棧和隊(duì)列在操做上受到限制。線性表可以在元素序列的任何位置上進(jìn)行插入、刪除操作，查找運(yùn)算往往是線性表上使用頻率最高的操作。查找、插入、刪除的時(shí)間復(fù)雜度一般為 O （ n ） 。棧和隊(duì)列的插入和刪除運(yùn)算都限制在線性表的表端完成，在棧和隊(duì)列上不需要查找運(yùn)算。棧和隊(duì)列的插入及刪除運(yùn)算時(shí)間復(fù)雜度都可以為 O （

20、 1）。設(shè)有編號(hào)為 1， 2， 3， 4 的四輛車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫出這四輛車開(kāi)出車站的所有可能的順序。 TOC o 1-5 h z 1234213412432143132423141342234114322431若數(shù)列1、2、3、4、5、6順序進(jìn)棧，假設(shè) P表示入棧操作，S表示出棧操作，例如：操作序列PSPSPSPSPSPST得到出棧序列為：123456。依此類推，請(qǐng)回答:（ 1）能否得到出棧序列325641？若能，請(qǐng)寫出對(duì)應(yīng)的操作序列。（ 2）能否得到出棧序列154623？若能，請(qǐng)寫出對(duì)應(yīng)的操作序列。（3）對(duì)應(yīng)操作序歹U:PPSSPPSPSPSS導(dǎo)至IJ的出棧序歹U是什么?

21、（4）對(duì)應(yīng)操作序歹U:PPPPSPSSPSSS導(dǎo)至IJ的出棧序歹U是什么?（ 5）從上面的結(jié)果中你能總結(jié)出什么結(jié)論？（ 1）能得到325641。在123 依次進(jìn)棧后， 3 和 2 出棧，得部分輸出序列 32 ；然后 4 ， 5 入棧， 5出棧，得部分出棧序列325； 6 入棧并出棧，得部分輸出序列3256 ；最后退棧，直到?？铡５幂敵鲂虼鮑 325641。其操作序歹U為 PPPSSPPSPSSS（2）不能得到輸出順序?yàn)?54623的序列。部分合法操作序列為ADAAAADDAD導(dǎo)到部分輸出序列 1546 后，棧中元素為 23， 3 在棧頂，故不可能2 先出棧，得不到輸出序列 154623 。21

22、4563453621（5）借助棧由輸入序列12n得到輸出序列pip2pn,則在輸出序列中不可能存在這樣的情形： 存在著 ijk 使 pj pkfront=sq-rear判斷隊(duì)滿的條件是：（ sq-rear+1 ） % MAXSIZE= = sq-front求隊(duì)列長(zhǎng)度的公式為： m = （sq-rear - sq-front+ MAXSIZE ） % MAXSIZE;通常稱正讀和反讀都相同的字符序列為回文，例如，abcdeedcba、abcdcba”是回文。若字符序列存儲(chǔ)在一個(gè)單鏈表中， 編寫算法判斷此字符序列是否為回文。 （提示： 將一半字符先依次進(jìn)棧）#define maxsize 100t

23、ypedef char datatype1;typedef structdatatype1 datamaxsize; int top; seqstack;typedef int datatype;typedef struct node datatype data;struct node *next; Linklist;Duichen(Linklist *head)int i=1;Linklist *p;seqstack *s;s=initSeqStack();p= head-next;n=0;while(p)n+; p=p-next;p=head-next;while(idata); i+;

24、if (n%2!=0) p=p-next;while(p&p-data=pop(s) p=p-next;if (p) return 0 else return 1;兩個(gè)棧共享數(shù)組 am 空間，棧底分別設(shè)在兩端，此時(shí)?？?、棧滿的條件是什么？試寫出兩個(gè)棧公用的算法： Top(i), Push(i,x) 和 Pop(i) ，其中 i 為棧的序號(hào)0 或 1 。#define m 100typedef char datatype;typedef struct nodedatatype am;int top0 , top1; seqstack;Seqstack ss,*s=&ss;int push(int

25、 i, datatype x) if (s-top1 = s-top0+1) printf( “full ”); return 0;if(i=0)s-top0+;s-as-top0=x;else s-top1-;s-as-top1=x;return 1;datatype pop(int i)if(i=0) if (s-top0= -1) printf( “empty ”); return 0;s-top0-; return s-as-top0+1;else if (s-top1= m) printf( “empty”); return 0;s-top1+; return s-as-top1-1

26、;datatype top(int i)if(i=0) if (s-top0= -1) printf( “empty ”); return 0; return s-as-top0;else if (s-top1=m) printf( “empty”); return 0; return s-as-top1;假設(shè)以數(shù)組 am 存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量rear 和 length 分別作為隊(duì)尾指針和隊(duì)中元素個(gè)數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)入隊(duì)和出隊(duì)的算法(在出隊(duì)的算法中要返回隊(duì)頭元素) 。#define m 100int enqueue(int a, int rear, int

27、 length, int x) if(length = m)printf( “queue is full ”); return 0;rear=(rear+1)% m;arear=x;length +;return length;int dequeue(int a, int rear, int length, int *x) if(length =0)printf( “queueempty”); return 0;*x= a (rear- length +m)%m;length -;return length;4 多維數(shù)組及廣義表回答下列概念：三元組表、廣義表、十字鏈表三元組表：稀疏矩陣中的非零

28、元素三元組組成的線性表。廣義表：也稱為列表(Lists)是n (nn。個(gè)元素a1，現(xiàn) ，a,，an的有限序列，元素ai 可以是原子或者是子表(子表亦是廣義表)。十字鏈表：稀疏矩陣(即三元組表)的一種鏈接存儲(chǔ)結(jié)構(gòu)。稀疏矩陣中每個(gè)非零元素都用一個(gè)包含五個(gè)域的結(jié)點(diǎn)來(lái)表示，存儲(chǔ)非零元素所在行的行號(hào)域i ，存儲(chǔ)非零元素所在列的列號(hào)域j ，存儲(chǔ)非零元素值的值域v ，以及行指針域 right 和列指針域down ，分別指向同一行中的下一個(gè)非零元素結(jié)點(diǎn)和同一列中的下一個(gè)非零元素 結(jié)點(diǎn)。二維數(shù)組在采用順序存儲(chǔ)時(shí)，元素的排列方式有哪兩種？行優(yōu)先和列優(yōu)先。矩陣壓縮存儲(chǔ)的目的是什么？請(qǐng)寫出對(duì)稱陣壓縮存儲(chǔ)四種方式的地址

29、公式。壓縮存儲(chǔ)的目的：節(jié)省矩陣的存儲(chǔ)空間。將對(duì)稱矩陣的下(上)三角存儲(chǔ)在數(shù)組長(zhǎng)度為n (n+1) /2的數(shù)組sa中，設(shè)矩陣中的某一個(gè)元素aj在數(shù)組中的下標(biāo)為k,則對(duì)稱陣壓縮存儲(chǔ)四種方式下k的計(jì)算公式如下：(1)行優(yōu)先順序存儲(chǔ)下三角i(i+1)/2+j i 河(下三角)k= ，右I j(j+1)/2+i ivj (上三角)(2)列優(yōu)先順序存儲(chǔ)下三角,1(2n-j+1 ) /2+i-j i 河(下三角) k=4J (2n-i+1 ) /2+j-i i vj (上三角)(3)行優(yōu)先順序存儲(chǔ)上三角ji (2n-i+1) /2+j-i i j (下三角)(4)列優(yōu)先順序存儲(chǔ)上三角k= fj (j+1)

30、/2+i iwj (上三角)1i (i+1) /2+j i j (下三角)在特殊矩陣和稀疏矩陣中，哪一種經(jīng)過(guò)壓縮存儲(chǔ)后會(huì)失去隨機(jī)存取的特性？稀疏矩陣。設(shè)有一個(gè)10階的對(duì)稱矩陣 A,以行優(yōu)先順序存儲(chǔ)下三角元素，其中a00為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)字節(jié)，則a85的地址為多少？若aii為第一元素，那么a85的地址又會(huì)是多少？若aoo為第一元素，則 a85的地址為：41若aii為第一元素，則 a85的地址為：32請(qǐng)給出圖4.10中稀疏矩陣A6的三元組順序表和十字鏈表存儲(chǔ)結(jié)構(gòu)圖示。矩陣A6X7的三元組順序表：01234133462164311-3765矩陣A6X7及十字鏈表表示:H1H2

31、H3H4H5H6H7廣義表分幾類？它們之間有什么關(guān)系？廣義表分為：線性表、純表、再入表和遞歸表四種。它們之間的關(guān)系滿足：遞歸表 再入表 純表 線性表。分別求出下列廣義表的表頭、表尾及表長(zhǎng)、表深。A= (a)表頭：a表尾：()表長(zhǎng)：1表深：1B= (a,b) , (c,d)表頭：(a,b)表尾：(c,d)表長(zhǎng)：2表深：2C= (a, (b,c) ,d,e)表頭：a表尾：(b,c),d,e)表長(zhǎng)：4表深：2D= (a,b, (c,d) , (e, (f,g)表頭：a表尾：(b, (c,d) , (e, (f,g)表長(zhǎng)：4表深：4請(qǐng)畫出下列廣義表的圖形表示。A= (a,b,c)B= (A,d)C=

32、(x ,A , B)ABC回答下列概念：樹(shù)、二叉樹(shù)、滿二叉樹(shù)、完全二叉樹(shù)、哈夫曼樹(shù)樹(shù)：可以用二元組或遞歸兩種方法定義樹(shù)。樹(shù)的二元組定義如下：設(shè)tree= (D, S),其中D是數(shù)據(jù)元素的集合，S是D中數(shù)據(jù)元素之間關(guān)系的集合。設(shè) 關(guān)系rCS,相對(duì)r,滿足下列條件：(1) D中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)，該結(jié)點(diǎn)被稱為樹(shù)的根(Root);(2)除樹(shù)根結(jié)點(diǎn)外，D中其余的結(jié)點(diǎn)有且僅有一個(gè)前趨結(jié)點(diǎn)；(3)從根到其余結(jié)點(diǎn)都有路徑。則稱tree是相對(duì)r的樹(shù)形結(jié)構(gòu)。二叉樹(shù)：二叉樹(shù)(Binary Tree)是n (n0個(gè)結(jié)點(diǎn)的有限集合，滿足：(1)當(dāng)n=0時(shí)，為空二叉樹(shù)。(2)當(dāng)n0時(shí)，是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分

33、別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。滿二叉樹(shù)：每層結(jié)點(diǎn)數(shù)都達(dá)到最大值的二叉樹(shù)。完全二叉樹(shù)：除最下面一層外其余各層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下一層上的結(jié)點(diǎn)都集中在最左邊的若干位置上的二叉樹(shù)。哈夫曼樹(shù)：又稱最優(yōu)二叉樹(shù)，是在含有n個(gè)葉子結(jié)點(diǎn)，權(quán)值分別為 W1, W2, , Wn的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度 WPL最小的二叉樹(shù)。對(duì)于圖5.37給出的樹(shù)，回答下列問(wèn)題：(1)寫出它的二元組表示；(2)根結(jié)點(diǎn)、葉結(jié)點(diǎn)和分支結(jié)點(diǎn)分別都為哪些；(3)結(jié)點(diǎn)F的度數(shù)和層數(shù)分別為多少；(4)結(jié)點(diǎn)B的兄弟和孩子分別為哪些？(5)從結(jié)點(diǎn)B到結(jié)點(diǎn)N是否存在路徑？若存在請(qǐng)寫出具體路徑。(6)從結(jié)點(diǎn)C到結(jié)點(diǎn)L是否存在路

34、徑？若存在請(qǐng)寫出具體路徑。圖 5.37(1)該樹(shù)采用二元組表示如下:設(shè) tree = ( D, D = A , R = AI,rC SC,AG,J,E,AG, H, I, J, K, L, , , , , , , N5.3包含三個(gè)結(jié)點(diǎn)的二叉樹(shù):5.4判斷下列說(shuō)法是否正確：(1)二叉樹(shù)是度為 2的有序樹(shù)。(2)二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2。(3)完全二叉樹(shù)一定存在度為 1的結(jié)點(diǎn)。(X)(X)(X)畫出包含三個(gè)結(jié)點(diǎn)的樹(shù)和二叉樹(shù)的所有不同形態(tài)，說(shuō)明樹(shù)和二叉樹(shù)之間的區(qū)別與聯(lián)系。包含三個(gè)結(jié)點(diǎn)的樹(shù):5.5少？設(shè)樹(shù)T的度為4,其中度為1, 2, 3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4, 2, 1, 1則T中的葉子數(shù)為多

35、葉子數(shù)為8。5.6結(jié)點(diǎn)數(shù)為n的二叉樹(shù)，高度最大是多少？最小是多少？將其擴(kuò)充成完全二叉樹(shù)時(shí)最多需要附加 多少個(gè)虛點(diǎn)？結(jié)點(diǎn)數(shù)為n的二叉樹(shù)，高度最大是 n,最小是log；1或log2n 1) 。將其擴(kuò)充成完全二叉樹(shù)時(shí)最多需要附加的虛點(diǎn)個(gè)數(shù):2n-1-n。5.7分別畫出圖5.38中的二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和二叉鏈表存儲(chǔ)結(jié)構(gòu)的圖示。1 I C口5.8分別寫出圖 前序遍歷序列： 中序遍歷序列： 后序遍歷序列：圖 5.38順序存儲(chǔ)結(jié)構(gòu)的圖示：012345678 9101112131415 27 2829ABCDE#F#G#H#IJ二叉鏈表存儲(chǔ)結(jié)構(gòu)的圖示:root/ B中二叉樹(shù)的前序、中序和后序遍歷序列。ABD

36、EGCFHIJDBGEACIHJFDGEBIJHFCA出滿足下面條件的二叉樹(shù)：(1)前序遍歷與中序遍歷結(jié)果相同(2)前序遍歷和后序遍歷結(jié)果相同(3)中序遍歷和后序遍歷結(jié)果相同(1)只有右分支的單分支樹(shù)。(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)。(3)只有左分支的單分支樹(shù)。以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫出前序遍歷的非遞歸算法。#define MAXSIZE 100typedef char DataType;typedef struct Node/* 二叉鏈表存儲(chǔ)結(jié)構(gòu) */ DataType data;struct Node *lchild,*rchild;BiTree;typedef BiTree* SElem

37、Type ; /*棧中數(shù)據(jù)元素類型，棧中保存結(jié)點(diǎn)指針*/typedef struct SElemType dataMAXSIZE;int top;SeqStack;/*棧的類型定義，順序棧 */*棧的基本操作的實(shí)現(xiàn)*/*初始化棧*/*首先建立棧空間，然后初始化棧頂指針*/SeqStack *initSeqStack() SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top= -1;return s; intpush (SeqStack *s, SElemType x)if (s-top=MAXSIZE-1)/* 棧滿不能入棧 */ pri

38、ntf(overflow);s-top+;s-datas-top=x;return 1;void pop (SeqStack *s) s-top-;int empty (SeqStack *s) if (s-top= -1)return 1;else return 0;SElemType top (SeqStack *s) return (s-datas-top );return 0;/* 出棧，假設(shè)棧不空*/* 設(shè)棧不空 */void PreOrderFei(BiTree *p)/* 前序遍歷二叉樹(shù)的非遞歸算法 */ SeqStack *s;s=initSeqStack();while(1)

39、 while(p) printf(%c, p-data); push(s,p); p=p-lchild; /*先訪問(wèn)結(jié)點(diǎn)，后壓棧*/if (empty(s) break;p=top(s); pop(s); p=p-rchild;引入線索二叉樹(shù)的目的是什么？ n 個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有多少條線索？有效利用空指針域，提高遍歷運(yùn)算的效率，簡(jiǎn)化遍歷算法。n 個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有n+1 條線索。設(shè)一棵二叉樹(shù)的中序、 后序遍歷序列分別為： G L D H B E I A C J F K 和 L G H D I E B J K F C A ，請(qǐng)回答：( 1)畫出二叉樹(shù)邏輯結(jié)構(gòu)的圖示。( 2)畫出上題中

40、二叉樹(shù)的中序線索二叉樹(shù)。( 3)畫出中序線索二叉鏈表存儲(chǔ)結(jié)構(gòu)圖示并給出C 語(yǔ)言描述。( 4)給出利用中序線索求結(jié)點(diǎn)中序后繼的算法。typedef char DataType;typedef struct Node DataType data;struct Node *lchild,*rchild;int ltag,rtag;BiThrTree;BiThrTree * InOrderNext(BiThrTree *p)/* 求中序后繼 */ if(p-rtag=1) p=p-rchild;/*分兩種情況查找結(jié)點(diǎn)后繼*/elsep=p-rchild;while(p-ltag=0) p=p-lchi

41、ld; return p;以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)求二叉樹(shù)高度的算法。typedef char DataType;typedef struct Node/* 二叉鏈表存儲(chǔ)結(jié)構(gòu)*/ DataType data;struct Node *lchild,*rchild;BiTree;int height（BiTree *T）/* 求樹(shù)高 */ int i,j;if（!T） return 0; TOC o 1-5 h z i=height（T-lchild）; /* 求左子樹(shù)的高度*/j=height（T-rchild）; /* 求右子樹(shù)的高度*/return ij?i+1:j+1;/*二叉樹(shù)的

42、高度為左右子樹(shù)中較高的高度加1*/試設(shè)計(jì)一個(gè)算法，根據(jù)二叉樹(shù)的前序序列和中序序列創(chuàng)建一棵二叉樹(shù)。算法思想：確定二叉樹(shù)的根節(jié)點(diǎn)。樹(shù)根是二叉樹(shù)前序遍歷的第一個(gè)元素。求解二叉樹(shù)的左右子樹(shù)。找出根結(jié)點(diǎn)在中序遍歷中的位置， 根左邊的所有元素是左子樹(shù)，根右邊的所有元素是右子樹(shù)。若根結(jié)點(diǎn)左邊或右邊為空，則該方向子樹(shù)為空；若根結(jié)點(diǎn) 左邊和右邊都為空，則此結(jié)點(diǎn)為葉子節(jié)點(diǎn)。遞歸求解樹(shù)。將左子樹(shù)和右子樹(shù)分別看成一棵二叉樹(shù)，重復(fù)（ 1 ）（ 2 ）（ 3 ）步，直到 所有的結(jié)點(diǎn)完成定位。typedef char DataType;typedef struct Node/* 二叉鏈表存儲(chǔ)結(jié)構(gòu)*/ DataType da

43、ta;struct Node *lchild,*rchild;BiTree;char pre50 = ABDHLEKCFG;/全局變量-前序序列char mid50 = HLDBEKAFCG; / 中序序列int position(char c)/* 求解字符在中序遍歷序列中的位置*/return strchr(mid,c)-mid;/* strchr()#include 功能：查找字符串s中首次出現(xiàn)字符c的位置(指針)，如果s中不存在c則返回NULL*/void preMidCreateTree(BiTree *p, int i, int j, int len) /* i: 子樹(shù)的前序序列的

44、首字符在pre 中的下標(biāo)j: 子樹(shù)的中序序列的首字符在mid 中的下標(biāo)len: 子樹(shù)的遍歷序列長(zhǎng)度，即子樹(shù)中的字符數(shù)*/int m;if(len data = prei;m = position(prei);preMidCreateTree(p-left, i+1, j, m-j);/m-j 為左子樹(shù)字符數(shù)preMidCreateTree(p-right, i+(m-j)+1, m+1, len-1-(m-j); /len-1-(m-j)為右子樹(shù)字符數(shù) void main()BiTree *root = NULL;preMidCreateTree(root, 0, 0, strlen(mid)

45、;BCFD請(qǐng)畫出5.37中的樹(shù)對(duì)應(yīng)的二叉樹(shù)。請(qǐng)畫出5.39中的各二叉樹(shù)對(duì)應(yīng)的森林。(a)(b)圖 5.39(a)(b)(c)(d)設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為 B,它有m個(gè)結(jié)點(diǎn)，B的根為p, p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是多少？m-n。假設(shè)用于通信的電文由字符集a, b, c, d, e, f, g, h中的字母構(gòu)成，這 8個(gè)字母在電文中出現(xiàn)的概率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。(1)為這8個(gè)字母設(shè)計(jì) Huffman編碼。(2)求出哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL。(3)若用三位二進(jìn)制數(shù)對(duì)這8個(gè)字母進(jìn)行等長(zhǎng)編碼，

46、則Huffman編碼的平均碼長(zhǎng)是等長(zhǎng)編碼的百分之幾？(1)哈夫曼樹(shù):對(duì)應(yīng)的哈夫曼編碼:字符編碼a1010b00c10000d1001e11f10001g01h1011(2)帶權(quán)路徑長(zhǎng)度為:nWPLWili =0.07 4+0.19 2+0.02 5+0.06 4+0.32 2+0.03 5+0.21 2+0.10 4=2.61i 1(3) 2.61/3*100%=87%6圖回答下列概念：完全圖、子圖、連通分量、網(wǎng)絡(luò)、最小生成樹(shù)、拓?fù)湫蛄型耆珗D：任意兩個(gè)頂點(diǎn)之間都有邊的圖。子 圖：設(shè)有圖G=(V,E),若V是V的子集(V V) , E是E的子集(E E),且E中的邊 所鄰接的點(diǎn)均在 V中出現(xiàn)，則

47、G=(V,E)也是一個(gè)圖，并且稱之為G的子圖。連通分量：無(wú)向圖 G的極大連通子圖。網(wǎng) 絡(luò)：邊上帶權(quán)的圖。最小生成樹(shù)：連通網(wǎng)絡(luò)的所有生成樹(shù)中邊上權(quán)值之和最小的生成樹(shù)。拓?fù)湫蛄校河邢驘o(wú)環(huán)圖中所有頂點(diǎn)按照拓?fù)渑判虻乃枷肱懦傻囊粋€(gè)線性序列。n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，如何求邊的條數(shù)？如何求某個(gè)頂點(diǎn)的度？如 果該圖為有向圖呢？無(wú)向圖的鄰接矩陣是對(duì)稱的，“1的個(gè)數(shù)則是圖中邊的條數(shù)的2倍，第i行或第i列上“1的個(gè)數(shù)都是序號(hào)為i的頂點(diǎn)的度。有向圖中，“1的個(gè)數(shù)則是圖中邊的條數(shù)，第i行“1的個(gè)數(shù)是序號(hào)為i的頂點(diǎn)的出度，第i列上“1的個(gè)數(shù)是序號(hào)為i的頂點(diǎn)的入度。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖

48、，若采用鄰接表為存儲(chǔ)結(jié)構(gòu)，所有邊表中的結(jié)點(diǎn)總數(shù) 為多少？ 如何求某個(gè)頂點(diǎn)的度？當(dāng)該圖為有向圖時(shí)，所有邊表中的結(jié)點(diǎn)總數(shù)為多少？如何求某 個(gè)頂點(diǎn)的入度和出度？(1)無(wú)向圖的邊表中的結(jié)點(diǎn)總數(shù)為：2*e;某個(gè)頂點(diǎn)的度：該頂點(diǎn)的邊表中的結(jié)點(diǎn)個(gè)數(shù)。(2)若該圖為有向圖，且采用鄰接表(通常稱為出邊表)為存儲(chǔ)結(jié)構(gòu)，則所有邊表中的結(jié)點(diǎn)總數(shù)為e;出邊表中，頂點(diǎn) Vi對(duì)應(yīng)的邊表結(jié)點(diǎn)的個(gè)數(shù)即為頂點(diǎn)Vi的出度；求頂點(diǎn)vi的入度，需要遍歷整個(gè)出邊表，求邊表結(jié)點(diǎn)中adjvex域的值為i的結(jié)點(diǎn)個(gè)數(shù)。6.4 設(shè)一個(gè)有向圖為 G=(V,E),其中 V= V 1,V2,V3,V4, E=, 請(qǐng)回答下列各問(wèn)：(1)畫出該有向圖，求出

49、每個(gè)頂點(diǎn)的入度和出度。(2)畫出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)圖示并給出C語(yǔ)言描述。(3)畫出該圖的鄰接表和逆鄰接表的存儲(chǔ)結(jié)構(gòu)圖示并給出C語(yǔ)言描述。(4)寫出從頂點(diǎn) V2出發(fā)的DFS序列和BFS序列。(1)有向圖如下：頂點(diǎn)Vi的入度是2,出度是1;頂點(diǎn)V2的入度是1 ,出度是2;頂點(diǎn)V3的入度是1,出度是0； 頂點(diǎn)V4的入度是1,出度是2。01234V1V2V3V4數(shù)組 TOC o 1-5 h z 00011010A1=0000C語(yǔ)言描述：#define N 4/*圖的頂點(diǎn)數(shù)*/typedef char VexType; /* 頂點(diǎn)類型 */typedef int AdjType; /* 權(quán)值類型 *

50、/ typedef struct VexType vertexN+1; /* 頂點(diǎn)數(shù)組 */ AdjType edgeN+1N+1;/* 鄰接矩陣 */AdjMatrix;C語(yǔ)言描述:typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct VexType vertex;EdgeNode *link;VexNode;#define N 10/*鄰接點(diǎn)域*/*指針域*/*定義邊表結(jié)點(diǎn)*/*頂點(diǎn)域*/*指針域*/*定義頂點(diǎn)表結(jié)點(diǎn)*/VexNode adjlistN+1;鄰接表圖示：逆鄰接表圖示:DFS 序歹U：

51、V2, V1,V4,V3BFS 序列：V2, V1,V3,V46.5對(duì)圖6.50所示的無(wú)向圖，依次輸入各邊：（V1,V2）、（V1,V4）、（V2,V3）、（V3,V4）、（V3,V5）,請(qǐng)回答下列各問(wèn)：（1）寫出該無(wú)向圖的二元組表示。（2）畫出該圖的鄰接矩陣和鄰接表（頭插法建表）存儲(chǔ)結(jié)構(gòu)圖示。（3）對(duì)（2）中的鄰接矩陣，給出從頂點(diǎn)V1出發(fā)的DFS序列和DFS生成樹(shù)。（4）對(duì)（2）中的鄰接表，給出從頂點(diǎn)Vi出發(fā)的BFS序列和BFS生成樹(shù)。（1）無(wú)向圖G的二元組表示：設(shè)G=（V, E） , V為頂點(diǎn)集，E為邊集，則V= V1, V2, V3, V4, V5E=（V1,V2）、（V1,V4）、（V

52、2,V3）、（V3,V4）、（V3,V5）（2）鄰接矩陣圖示：門 012345經(jīng)V1V2V3V4V5 TOC o 1-5 h z 0101010100A1= 0101110100鄰接表圖示:_ 00100（3）對(duì)（2）中的鄰接矩陣，從頂點(diǎn)V1出發(fā)的DFS序列是V1,V2,V3,V4,V5DFS生成樹(shù)是：(4)對(duì)(2)中的鄰接表，從頂點(diǎn) V1出發(fā)的BFS序列是:V1,V4,V2,V3,V5BFS生成樹(shù)：畫出圖6.51的所有可能的最小生成樹(shù)。圖 6.50圖 6.51求出圖6.52從頂點(diǎn)V1到其他各頂點(diǎn)之間的最短路徑。然占S八、路徑長(zhǎng)度路徑V10V1 V1V220V1 V2V35V1 7 V3V41

53、9V1 -V3V6V4V525V1 V3-V6V5V615V1 V3V66.8給出圖6.53所有可能的拓?fù)湫虼鮑。圖 6.53圖 6.52V2, V1, V3, V5, V4, V7, V8, V6 或 V5, V2, V1, V3, V4, V7, V8, V6 或 V7, V2, V1 , V3, V5, V4, V8, V66.9設(shè)計(jì)一個(gè)算法將一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接鏈表。鄰接矩陣的C語(yǔ)言描述#define N 5typedef char VexType;typedef int AdjType; typedef struct VexType vertexN+1;AdjType ed

54、geN+1N+1;AdjMatrix;鄰接表的C語(yǔ)言描述 typedef struct node int adjvex;struct node *next;EdgeNode; typedef struct VexType vertex;EdgeNode *link;VexNode;VexNode adjlistN+1;void creatAdjList(AdjMatrix *adj) int i,j;EdgeNode *s;for(i=1;ivertexi;adjlisti.link =NULL;/* 邊表指針初始為空*/for(i=1;i=1;j-) if(adj-edgeij=1) s=(

55、EdgeNode*)malloc(sizeof(EdgeNode); /* 生成邊表結(jié)點(diǎn) */ s-adjvex=j;s-next=adjlisti.link;/* 插入到頂點(diǎn) vi 的邊表頭部*/adjlisti.link=s; /* creatAdjList */6.10 以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，試寫出圖的非遞歸的深度優(yōu)先搜索算法。/ 鄰接矩陣的 C 語(yǔ)言描述#define N 5/* 圖的頂點(diǎn)數(shù) */#define MAXSIZE 10typedef char VexType;/* 頂點(diǎn)類型*/typedef int AdjType;/* 權(quán)值類型*/typedef struct V

56、exType vertexN+1; /* 頂點(diǎn)數(shù)組 */ AdjType edgeN+1N+1;/* 鄰接矩陣 */AdjMatrix;int visitedN+1; /* 全局標(biāo)志數(shù)組，標(biāo)注頂點(diǎn)是否被訪問(wèn) */typedef int SElemType ; /* 棧中數(shù)據(jù)元素類型，棧中保存頂點(diǎn)序號(hào) */ typedef struct SElemType dataMAXSIZE;int top;SeqStack;/* 棧的類型定義，順序棧*/void DFS(AdjMatrix *adj,int i) /* 從頂點(diǎn) i 出發(fā)進(jìn)行深度優(yōu)先搜索，用鄰接矩陣adj 存儲(chǔ)圖 */ SeqStack *

57、s;int v=i;s=initSeqStack();push(s,v);while(!empty(s) v= top(s);if(!visitedv) visitedv=1;/* 標(biāo)記 v 已經(jīng)訪問(wèn)過(guò) */printf ( 輸出序號(hào)為 %d 的頂點(diǎn) : %cn,v,adj-vertexv); /* 訪問(wèn)頂點(diǎn) v*/for (j=1;jedgevj)&(!visitedj) push(s,j);break; if(jN) pop(s);6.11 修改 Prim 算法，使之能在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求圖的最小生成樹(shù)，并分析其時(shí)間復(fù)雜度。由于圖上的邊都帶有權(quán)值， 因此鄰接表結(jié)構(gòu)中的邊表結(jié)點(diǎn)除了保存鄰

58、接點(diǎn)的序號(hào)外， 還要保存邊的權(quán)值。最小生成樹(shù)的存儲(chǔ)結(jié)構(gòu)采用邊集數(shù)組。/鄰接表存儲(chǔ)結(jié)構(gòu)#define N 5#define MAX 10000 typedef int AdjType; typedef struct node int adjvex;AdjType weight; struct node *next;EdgeNode;typedef struct VexType vertex;EdgeNode *link;VexNode;VexNode adjlistN+1;/最小生成樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef struct edge int fromvex;int endvex;int weig

59、ht;EdgeSetArray; EdgeSetArray TN;/鄰接表存儲(chǔ)結(jié)構(gòu)上的Prim 算法void prim() int i,j,w,min,minest;EdgeNode *p=null; EdgeSetArray edtemp; for (i=1;i adjvex;Tj.weight=p- weight; p=p-next;/* 依次搜索頂點(diǎn) 1 的鄰接點(diǎn) */* 鄰接點(diǎn)的序號(hào) */* 求當(dāng)前最短邊，下標(biāo)為minest */for (i=1;i=N-1;i+) min=MAX;for(j=i;j=N-1;j+)if (Tj.weightmin)/* 求生成樹(shù)中的第i 條邊 */

60、min=Tj.weight; minest=j;/* Tminest 是當(dāng)前最短的邊*/if (i!=minest)/* 將當(dāng)前最短的邊保存到 Ti ，如果不是則交換*/ edtemp=Tminest;Tminest=Ti;Ti=edtemp;/* 調(diào)整邊集數(shù)組 */ k= Ti.endvex;for(j=i+1;j adjvex= Tj.endvex & p-weightweight;Tj.formvex=k;break; /*for-j*/ /*for-i*/* prim */6.12 以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，試寫出從源點(diǎn)到其他各頂點(diǎn)的最短路徑的Dijkstra 算法。/ 鄰接表存儲(chǔ)結(jié)構(gòu)