内容发布更新时间 : 2024/12/23 7:07:24星期一 下面是文章的全部内容请认真阅读。

5. 已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。

参考答案：

void AllSPdfs(AdjList g,vertype u,vertype v)

{ //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)

int top=0,s[];

s[++top]=u; visited[u]=1; while (top>0 || p) {

p=g[s[top]].firstarc; //第一个邻接点。

while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。 if (p==null) top--; //退栈。 else {

i=p->adjvex; //取邻接点（编号）。

if (i==v) //找到从u到v的一条简单路径，输出。 {

for (k=1;k<=top;k++)

printf( \

else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else

}//while

}// AllSPdfs 6.

已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。已知边类型edgenode，包含next和adjvex（序号）成员。类型adjlist表示顶点数组类型，每个数组元素包含link和vex成员。 参考答案：

int outdegree(adjlist adj,int v) {

int degree=0; edgenode *p; p=adj[v].link; while(p!=NULL) { }

degree++; p=p->next;

return degree; } 7.

编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。（要求写出二叉链表的类型定义）

参考答案：

//二叉树的二叉链表表示 typedef struct BINTREENODE

16

{ ElemType data;

struct BINTREENODE *lchild, rchild; } BinNode,*BinTree //答对给2分 int BsBtr(BinTree t, BinTree pre, int flag) { //判别给定的二叉树是否为二叉排序树

pre =NULL; flag=TRUE; if (t && flag)

{ BSBtr(t->lchild, pre, flag);

if (pre = = NULL) { flag=TRUE；pre=t; } else

if(pre->key < t->key) //比较t 与中序直接前驱pre的大小

{ flag=TRUE; pre=t;} //pre与t有序 else flag=FALSE; //pre与t无序 }//if

BSBtr(t->rchild,pre,flag); }//BSBtr

17