内容发布更新时间 : 2024/5/23 21:09:21星期一 下面是文章的全部内容请认真阅读。
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