subject_67298.htm

vc

<p>
序号：67298 发表者：麻仓叶 发表日期：2003-12-30 18:13:45
<br>主题：这几个题目的代码都不会写。。。。有没有明白人指点一下的。。。。谢谢啦。。。
<br>内容：1。以单链表为存储结构实现简单排序的算法<BR><BR>2。假设二叉排序树以后继线索链表作存储结构，编写在二叉排序树中插入一个关键字的算法<BR><BR>3。编写利用深度优先遍历有向图实现求关键路径的算法<BR><BR>4。以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法<BR><BR>5。写一个求有向图G中所有简单回路的算法<BR><BR><BR>告诉怎么写也可以，告诉哪里有这方面的东西也可以，谢谢。。。。
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：麻仓叶 回复日期：2003-12-31 14:11:05
<br>内容：都弄好啦，不用帮我写着几个啦。。。。<BR><BR>呼呼~~~深呼吸。。。。。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：麻仓叶 回复日期：2003-12-31 14:14:56
<br>内容：顺便附上最后一个算法的代码^(OO)^<BR><BR><BR>7.30 <BR>int visited[MAXSIZE];<BR>int path[MAXSIZE]; //暂存当前路径<BR>int cycles[MAXSIZE][MAXSIZE]; //储存发现的回路所包含的结点<BR>int thiscycle[MAXSIZE]; //储存当前发现的一个回路<BR>int cycount=0; //已发现的回路个数 <BR>void GetAllCycle(ALGraph G)//求有向图中所有的简单回路<BR>{<BR>for(v=0;v&lt;G.vexnum;v++) visited[v]=0;<BR>for(v=0;v&lt;G.vexnum;v++)<BR>if(!visited[v]) DFS(G,v,0); //深度优先遍历<BR>}//DFSTraverse <BR>void DFS(ALGraph G,int v,int k)//k表示当前结点在路径上的序号<BR>{<BR>visited[v]=1;<BR>path[k]=v; //记录当前路径<BR>for(p=G.vertices[v].firstarc;p;p=p-&gt;nextarc)<BR>{<BR>w=p-&gt;adjvex;<BR>if(!visited[w]) DFS(G,w,k+1);<BR>else //发现了一条回路<BR>{<BR>for(i=0;path[i]!=w;i++); //找到回路的起点<BR>for(j=0;path[i+j];j++) thiscycle[j]=path[i+j];//把回路复制下来<BR>if(!exist_cycle())<BR>{<BR>for(i=0;i&lt;=j;i++)<BR>cycles[cycount][i]=thiscycle[i];//如果该回路尚未被记录过,就添加到记录中<BR>cycount++;<BR>}<BR>for(i=0;i&lt;G.vexnum;i++) thiscycle[i]=0; //清空目前回路数组<BR>}//else<BR>}//for<BR>path[k]=0;<BR>visited[k]=0; //注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前结点visited为真,即表示发现了一条回路<BR>}//DFS <BR>int exist_cycle()//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在<BR>{<BR>int temp[MAXSIZE];<BR>for(i=0;i&lt;cycount;i++) //判断已有的回路与thiscycle是否相同<BR>{ //也就是,所有结点和它们的顺序都相同<BR>j=0;c=thiscycle[ 0 ]; //例如,142857和857142是相同的回路<BR>for(k=0;cycles[i][k]!=c&amp;&amp;cycles[i][k]!=0;k++);//在cycles的一个行向量中寻找等于thiscycle第一个结点的元素<BR>if(cycles[i][k]) //有与之相同的一个元素<BR>{<BR>for(m=0;cycles[i][k+m];m++)<BR>temp[m]=cycles[i][k+m];<BR>for(n=0;n&lt;k;n++,m++)<BR>temp[m]=cycles[i][n]; //调整cycles中的当前记录的循环相位并放入temp数组中<BR>if(!StrCompare(temp,thiscycle)) //与thiscycle比较<BR>return 1; //完全相等<BR>for(m=0;m&lt;G.vexnum;m++) temp[m]=0; //清空这个数组<BR>}<BR>}//for<BR>return 0; //所有现存回路都不与thiscycle完全相等<BR>}//exist_cycle<BR>分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路;扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,142857)存入thiscycle中;由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法. <BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>