2015年湖南省数据库入门基础(3)

2015年湖南省数据库入门基础

// Knap←Knap(s,n-1)

7、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。
{printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
}//Print
void dfs(int v)
{visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle

8、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
9、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：
（1）．建立有向图G的邻接表存储结构；
（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

10、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：
（1）．建立有向图G的邻接表存储结构；
（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

11、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x， 这情况下向j 小的方向继续查找；二是A[i,j]<x，下步应向i大的方向查找；三是A[i,j]=x，查找成功。否则，若下标已超出范围，则查找失败。
void search(datatype A[ ][ ], int a,b,c,d, datatype x)
//n*m矩阵A,行下标从a到b,列下标从c到
d,本算法查找x是否在矩阵A中.
{i=a; j=d; flag=0; //flag是成功查到x的标志
while(i<=b && j>=c)
if(A[i][j]==x) {flag=1;break;}
else if (A[i][j]>x)