2012年宁夏回族自治区数据总结摘要

2012年宁夏回族自治区数据总结摘要

1、4、 void LinkList_reverse(Linklist &L)

//链表的就地逆置;为简化算法,假设表长大于2

{

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

{

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头

}

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

2、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。

void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\n”,v); num=0;}//if

p=g[v].firstarc;

while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。

{static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。

{num=0; visited[1..n]=0; dfs(i); }

}// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。