大二下-数据结构习题

1、编写递归算法，根据树的双亲表示法及其根节点创建树的孩子—兄弟链表 结构。要求写算法以前写出这两种 结构的类型说明。/*

树的双亲表 表示

*/#define

MAX_TREE_SIZE

100typedef

struct

{

//结点结构emType

data;int

parent; /*

双亲位置域*/}

PTNode;typedef

struct{

//树结构

PTNode

nodes[MAX_TREE_SIZE];int

r,n;/*

根的位置和结点数*/}

PTree;双亲表示采用数组1、编写递归算法，根据树的双亲表示法及其根节点创建树的孩子—兄弟链表 结构。要求写算法以前写出这两种 结构的类型说明。孩子-兄弟表示采用链表表示//c6-5.h

树的二叉链表(孩子－兄弟)typedef

struct

CSNode{emType

data;CSNode

*

child,*nextsibling;}CSNode,*CSTree;1、编写递归算法，根据树的双亲表示法及其根节点创建树的孩子—兄弟链表 结构。要求写算法以前写出这两种 结构的类型说明。分析：结构。1、编写递归算法，根据树的双亲表示法及其根节点创建树的孩子—兄弟链表要求写算法以前写出这两种 结构的类型说明。结构。1、编写递归算法，根据树的双亲表示法及其根节点创建树的孩子—兄弟链表要求写算法以前写出这两种 结构的类型说明。2、以二叉链表为 结构的二叉树，其数据域为整型。试设计算法，计算每层中结点数据域大于50的结点个数，并输出这些结点数据域的值和序号。2、以二叉链表为 结构的二叉树，其数据域为整型。试设计算法，计算每层中结点数据域大于50的结点个数，并输出这些结点数据域的值和序号。2、以二叉链表为 结构的二叉树，其数据域为整型。试设计算法，计算每层中结点数据域大于50的结点个数，并输出这些结点数据域的值和序号。//根节点入队3、假设以双亲表示法做树的 结构，写出双亲表示的类型说明，并编写求给定的树的深度算法。（注：已知树中的结点数）【分析】由于以双亲表示法作树的 结构，找结点的双亲容易。因此 可求出每一结点的层次，取其最大层次就是树的深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为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、由题知，该有向图无环，否则“若从顶点i至顶点j有一条弧，则应使i<j”无法成立。2、利用拓扑排序，在排序过程中将每一顶点的数据域赋予整型序号。Status

Topological

Sort(ALGraph

G){//有向图G采用邻接表 结构。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号顶点并将其数据域赋值整型序号for(p=G.vertices[i]. arc；p；

p=p—>nextarc)

{k=p—>adivex；//对i号顶点的每个邻接点的入度减1if(！(--indegree[k]))Push(S，k)；//若入度减为0，则入}//for}//while}//TopologicalSort3、试编写把一个无向图的邻接矩阵 结构转换为邻节表 结构的算法。分析：先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中 相应的边表结点。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;

//邻接表头结点初始化for(i=0;i<A.vexnum;i++)

//在邻接矩阵上查找值不为零的元素，相应的边表结点找到后在邻接表的对应单链表中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、试编写图的深度优先遍历的非递归算法。分析：深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程，设计一个栈来模拟递归实现中系统设置的工作栈，算法的伪代码描述为：4、试编写图的深度优先遍历的非递归算法。假设图采用邻接矩阵作为 结构，具体算法如下：void

DFSTraverse(ALGraph*

G,int

k){Stack

s;

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

G!=NULL) push(k);//若图不为空，则将节点标号压入while(!StackEmpty(s))

//栈不为空说明还有节点未被{i

=getTop(s); //取栈顶节点标号，但是不要将其出栈for(j=0;j<vertexNum;j++)

//遍历该元素的相邻节点是否有未被标记。若有，则 ，并标记为已 ，然后压入栈。{if(arc[k][j]==1

&&

visited[j]==0){visited[j]=1;s[++top]=j;}if(j==vertexNum)top--;//若无，则当前节点退栈}}}5、假设以邻接矩阵为图的

结构，编写算法判别在给定的有向图中是否存在一个有向回路。若存在，则以顶点序列的方式输出该回路（找到一条即可，图中不存在顶点到自己的弧）5、假设以邻接矩阵为图的

结构，编写算法判别在给定的有向图中是否存在一个有向回路。若存在，则以顶点序列的方式输出该回路（找到一条即可，图中不存在顶点到自己的弧）main

{

find_cycle（）;}回