大二下-數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點(diǎn)創(chuàng)建樹的孩子—兄弟鏈表 結(jié)構(gòu)。要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說(shuō)明。/*

樹的雙親表 表示

*/#define

MAX_TREE_SIZE

100typedef

struct

{

//結(jié)點(diǎn)結(jié)構(gòu)emType

data;int

parent; /*

雙親位置域*/}

PTNode;typedef

struct{

//樹結(jié)構(gòu)

PTNode

nodes[MAX_TREE_SIZE];int

r,n;/*

根的位置和結(jié)點(diǎn)數(shù)*/}

PTree;雙親表示采用數(shù)組1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點(diǎn)創(chuàng)建樹的孩子—兄弟鏈表 結(jié)構(gòu)。要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說(shuō)明。孩子-兄弟表示采用鏈表表示//c6-5.h

樹的二叉鏈表(孩子－兄弟)typedef

struct

CSNode{emType

data;CSNode

*

child,*nextsibling;}CSNode,*CSTree;1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點(diǎn)創(chuàng)建樹的孩子—兄弟鏈表 結(jié)構(gòu)。要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說(shuō)明。分析：結(jié)構(gòu)。1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點(diǎn)創(chuàng)建樹的孩子—兄弟鏈表要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說(shuō)明。結(jié)構(gòu)。1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點(diǎn)創(chuàng)建樹的孩子—兄弟鏈表要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說(shuō)明。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域?yàn)檎?。試設(shè)計(jì)算法，計(jì)算每層中結(jié)點(diǎn)數(shù)據(jù)域大于50的結(jié)點(diǎn)個(gè)數(shù)，并輸出這些結(jié)點(diǎn)數(shù)據(jù)域的值和序號(hào)。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域?yàn)檎?。試設(shè)計(jì)算法，計(jì)算每層中結(jié)點(diǎn)數(shù)據(jù)域大于50的結(jié)點(diǎn)個(gè)數(shù)，并輸出這些結(jié)點(diǎn)數(shù)據(jù)域的值和序號(hào)。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域?yàn)檎?。試設(shè)計(jì)算法，計(jì)算每層中結(jié)點(diǎn)數(shù)據(jù)域大于50的結(jié)點(diǎn)個(gè)數(shù)，并輸出這些結(jié)點(diǎn)數(shù)據(jù)域的值和序號(hào)。//根節(jié)點(diǎn)入隊(duì)3、假設(shè)以雙親表示法做樹的 結(jié)構(gòu)，寫出雙親表示的類型說(shuō)明，并編寫求給定的樹的深度算法。（注：已知樹中的結(jié)點(diǎn)數(shù)）【分析】由于以雙親表示法作樹的 結(jié)構(gòu)，找結(jié)點(diǎn)的雙親容易。因此 可求出每一結(jié)點(diǎn)的層次，取其最大層次就是樹的深度。對(duì)每一結(jié)點(diǎn)，找其雙親，雙親的雙親，直至（根）結(jié)點(diǎn)雙親為0為止。int

Depth(PTree

t){int

maxdepth=0;

/*樹的深度*/int

f,temp;for(i=1;i<=t.n;i++){temp=0;

f=i;while(f>0)

{temp++;

f=t.nodes[f].parent;

} /*

深度加1，并取新的雙親*/if(temp>maxdepth) maxdepth=temp;

}

/*最大深度更新*/}return(maxdepth);/*返回樹的深度*/4、5、分析：2、令G=<V,E>為一個(gè)有向圖，編寫一個(gè)給圖G中每一個(gè)頂點(diǎn)賦以一個(gè)整型序號(hào)的算法，并滿足以下條件：若從頂點(diǎn)i至頂點(diǎn)j有一條弧，則應(yīng)使i<j。分析：1、由題知，該有向圖無(wú)環(huán)，否則“若從頂點(diǎn)i至頂點(diǎn)j有一條弧，則應(yīng)使i<j”無(wú)法成立。2、利用拓?fù)渑判颍谂判蜻^(guò)程中將每一頂點(diǎn)的數(shù)據(jù)域賦予整型序號(hào)。Status

Topological

Sort(ALGraph

G){//有向圖G采用鄰接表 結(jié)構(gòu)。FindInDegree(G，indegree)；//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]InitStack(S)；

for(i=0；i<G.vexnum；

++i)if(!indegree[i])Push(S，i)//建零入度頂點(diǎn)棧,s入度為0者進(jìn)棧count=1；//整型序號(hào)初始化

while(!StackEmpty(S)){Pop(S，i)；G.vertices[i].d ount；++count；//輸出i號(hào)頂點(diǎn)并將其數(shù)據(jù)域賦值整型序號(hào)for(p=G.vertices[i]. arc；p；

p=p—>nextarc)

{k=p—>adivex；//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(！(--indegree[k]))Push(S，k)；//若入度減為0，則入}//for}//while}//TopologicalSort3、試編寫把一個(gè)無(wú)向圖的鄰接矩陣 結(jié)構(gòu)轉(zhuǎn)換為鄰節(jié)表 結(jié)構(gòu)的算法。分析：先設(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中 相應(yīng)的邊表結(jié)點(diǎn)。void

MatToList(AdMatrix

&A,

AdjList

&B){B.vexnum=A.vexnum;structum;

//鄰接表初始化

ode

p;for(i=0;i<A.vexnum;i++)B.AdjList[i].

arc=NULL;

//鄰接表頭結(jié)點(diǎn)初始化for(i=0;i<A.vexnum;i++)

//在鄰接矩陣上查找值不為零的元素，相應(yīng)的邊表結(jié)點(diǎn)找到后在鄰接表的對(duì)應(yīng)單鏈表中for(j=0;j<I;j++)if(A.arcs[i][j]!=0){p->adjvex=j;p->nextarc=B.adjlist[i].

arc;B.adjlist[i].

arc=p;}}4、試編寫圖的深度優(yōu)先遍歷的非遞歸算法。分析：深度優(yōu)先遍歷算法的非遞歸實(shí)現(xiàn)需要了解深度優(yōu)先遍歷的執(zhí)行過(guò)程，設(shè)計(jì)一個(gè)棧來(lái)模擬遞歸實(shí)現(xiàn)中系統(tǒng)設(shè)置的工作棧，算法的偽代碼描述為：4、試編寫圖的深度優(yōu)先遍歷的非遞歸算法。假設(shè)圖采用鄰接矩陣作為 結(jié)構(gòu)，具體算法如下：void

DFSTraverse(ALGraph*

G,int

k){Stack

s;

InitStack(s);//棧初始化if(!visited[G->vertex[k]]&&

G!=NULL) push(k);//若圖不為空，則將節(jié)點(diǎn)標(biāo)號(hào)壓入while(!StackEmpty(s))

//棧不為空說(shuō)明還有節(jié)點(diǎn)未被{i

=getTop(s); //取棧頂節(jié)點(diǎn)標(biāo)號(hào)，但是不要將其出棧for(j=0;j<vertexNum;j++)

//遍歷該元素的相鄰節(jié)點(diǎn)是否有未被標(biāo)記。若有，則 ，并標(biāo)記為已 ，然后壓入棧。{if(arc[k][j]==1

&&

visited[j]==0){visited[j]=1;s[++top]=j;}if(j==vertexNum)top--;//若無(wú)，則當(dāng)前節(jié)點(diǎn)退棧}}}5、假設(shè)以鄰接矩陣為圖的

結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)有向回路。若存在，則以頂點(diǎn)序列的方式輸出該回路（找到一條即可，圖中不存在頂點(diǎn)到自己的?。?、假設(shè)以鄰接矩陣為圖的

結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)有向回路。若存在，則以頂點(diǎn)序列的方式輸出該回路（找到一條即可，圖中不存在頂點(diǎn)到自己的?。﹎ain

{

find_cycle（）;}回