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

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

樹的雙親表 表示

*/#define

MAX_TREE_SIZE

100typedef

struct

{

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

data;int

parent; /*

雙親位置域*/}

PTNode;typedef

struct{

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

PTNode

nodes[MAX_TREE_SIZE];int

r,n;/*

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

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

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

struct

CSNode{emType

data;CSNode

*

child,*nextsibling;}CSNode,*CSTree;1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點創(chuàng)建樹的孩子—兄弟鏈表 結(jié)構(gòu)。要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說明。分析：結(jié)構(gòu)。1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點創(chuàng)建樹的孩子—兄弟鏈表要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說明。結(jié)構(gòu)。1、編寫遞歸算法，根據(jù)樹的雙親表示法及其根節(jié)點創(chuàng)建樹的孩子—兄弟鏈表要求寫算法以前寫出這兩種 結(jié)構(gòu)的類型說明。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域為整型。試設計算法，計算每層中結(jié)點數(shù)據(jù)域大于50的結(jié)點個數(shù)，并輸出這些結(jié)點數(shù)據(jù)域的值和序號。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域為整型。試設計算法，計算每層中結(jié)點數(shù)據(jù)域大于50的結(jié)點個數(shù)，并輸出這些結(jié)點數(shù)據(jù)域的值和序號。2、以二叉鏈表為 結(jié)構(gòu)的二叉樹，其數(shù)據(jù)域為整型。試設計算法，計算每層中結(jié)點數(shù)據(jù)域大于50的結(jié)點個數(shù)，并輸出這些結(jié)點數(shù)據(jù)域的值和序號。//根節(jié)點入隊3、假設以雙親表示法做樹的 結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度算法。（注：已知樹中的結(jié)點數(shù)）【分析】由于以雙親表示法作樹的 結(jié)構(gòu)，找結(jié)點的雙親容易。因此 可求出每一結(jié)點的層次，取其最大層次就是樹的深度。對每一結(jié)點，找其雙親，雙親的雙親，直至（根）結(jié)點雙親為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中每一個頂點賦以一個整型序號的算法，并滿足以下條件：若從頂點i至頂點j有一條弧，則應使i<j。分析：1、由題知，該有向圖無環(huán)，否則“若從頂點i至頂點j有一條弧，則應使i<j”無法成立。2、利用拓撲排序，在排序過程中將每一頂點的數(shù)據(jù)域賦予整型序號。Status

Topological

Sort(ALGraph

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

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

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

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

p=p—>nextarc)

{k=p—>adivex；//對i號頂點的每個鄰接點的入度減1if(！(--indegree[k]))Push(S，k)；//若入度減為0，則入}//for}//while}//TopologicalSort3、試編寫把一個無向圖的鄰接矩陣 結(jié)構(gòu)轉(zhuǎn)換為鄰節(jié)表 結(jié)構(gòu)的算法。分析：先設置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應單鏈表中 相應的邊表結(jié)點。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é)點初始化for(i=0;i<A.vexnum;i++)

//在鄰接矩陣上查找值不為零的元素，相應的邊表結(jié)點找到后在鄰接表的對應單鏈表中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)先遍歷算法的非遞歸實現(xiàn)需要了解深度優(yōu)先遍歷的執(zhí)行過程，設計一個棧來模擬遞歸實現(xiàn)中系統(tǒng)設置的工作棧，算法的偽代碼描述為：4、試編寫圖的深度優(yōu)先遍歷的非遞歸算法。假設圖采用鄰接矩陣作為 結(jié)構(gòu)，具體算法如下：void

DFSTraverse(ALGraph*

G,int

k){Stack

s;

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

G!=NULL) push(k);//若圖不為空，則將節(jié)點標號壓入while(!StackEmpty(s))

//棧不為空說明還有節(jié)點未被{i

=getTop(s); //取棧頂節(jié)點標號，但是不要將其出棧for(j=0;j<vertexNum;j++)

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

&&

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

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

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

{

find_cycle（）;}回