<p>
序號(hào)：67298 發(fā)表者：麻倉葉 發(fā)表日期：2003-12-30 18:13:45
<br>主題：這幾個(gè)題目的代碼都不會(huì)寫。。。。有沒有明白人指點(diǎn)一下的。。。。謝謝啦。。。
<br>內(nèi)容：1。以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單排序的算法<BR><BR>2。假設(shè)二叉排序樹以后繼線索鏈表作存儲(chǔ)結(jié)構(gòu)，編寫在二叉排序樹中插入一個(gè)關(guān)鍵字的算法<BR><BR>3。編寫利用深度優(yōu)先遍歷有向圖實(shí)現(xiàn)求關(guān)鍵路徑的算法<BR><BR>4。以鄰接表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)求從源點(diǎn)到其余各頂點(diǎn)的最短路徑的Dijkstra算法<BR><BR>5。寫一個(gè)求有向圖G中所有簡(jiǎn)單回路的算法<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>回復(fù)者：麻倉葉 回復(fù)日期：2003-12-31 14:11:05
<br>內(nèi)容：都弄好啦，不用幫我寫著幾個(gè)啦。。。。<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>
回復(fù)者：麻倉葉 回復(fù)日期：2003-12-31 14:14:56
<br>內(nèi)容：順便附上最后一個(gè)算法的代碼^(OO)^<BR><BR><BR>7.30 <BR>int visited[MAXSIZE];<BR>int path[MAXSIZE]; //暫存當(dāng)前路徑<BR>int cycles[MAXSIZE][MAXSIZE]; //儲(chǔ)存發(fā)現(xiàn)的回路所包含的結(jié)點(diǎn)<BR>int thiscycle[MAXSIZE]; //儲(chǔ)存當(dāng)前發(fā)現(xiàn)的一個(gè)回路<BR>int cycount=0; //已發(fā)現(xiàn)的回路個(gè)數(shù) <BR>void GetAllCycle(ALGraph G)//求有向圖中所有的簡(jiǎn)單回路<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); //深度優(yōu)先遍歷<BR>}//DFSTraverse <BR>void DFS(ALGraph G,int v,int k)//k表示當(dāng)前結(jié)點(diǎn)在路徑上的序號(hào)<BR>{<BR>visited[v]=1;<BR>path[k]=v; //記錄當(dāng)前路徑<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 //發(fā)現(xiàn)了一條回路<BR>{<BR>for(i=0;path[i]!=w;i++); //找到回路的起點(diǎn)<BR>for(j=0;path[i+j];j++) thiscycle[j]=path[i+j];//把回路復(fù)制下來<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; //清空目前回路數(shù)組<BR>}//else<BR>}//for<BR>path[k]=0;<BR>visited[k]=0; //注意只有當(dāng)前路徑上的結(jié)點(diǎn)visited為真.因此一旦遍歷中發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)visited為真,即表示發(fā)現(xiàn)了一條回路<BR>}//DFS <BR>int exist_cycle()//判斷thiscycle數(shù)組中記錄的回路在cycles的記錄中是否已經(jīng)存在<BR>{<BR>int temp[MAXSIZE];<BR>for(i=0;i&lt;cycount;i++) //判斷已有的回路與thiscycle是否相同<BR>{ //也就是,所有結(jié)點(diǎn)和它們的順序都相同<BR>j=0;c=thiscycle[ 0 ]; //例如,142857和857142是相同的回路<BR>for(k=0;cycles[i][k]!=c&amp;&amp;cycles[i][k]!=0;k++);//在cycles的一個(gè)行向量中尋找等于thiscycle第一個(gè)結(jié)點(diǎn)的元素<BR>if(cycles[i][k]) //有與之相同的一個(gè)元素<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]; //調(diào)整cycles中的當(dāng)前記錄的循環(huán)相位并放入temp數(shù)組中<BR>if(!StrCompare(temp,thiscycle)) //與thiscycle比較<BR>return 1; //完全相等<BR>for(m=0;m&lt;G.vexnum;m++) temp[m]=0; //清空這個(gè)數(shù)組<BR>}<BR>}//for<BR>return 0; //所有現(xiàn)存回路都不與thiscycle完全相等<BR>}//exist_cycle<BR>分析:這個(gè)算法的思想是,在遍歷中暫存當(dāng)前路徑,當(dāng)遇到一個(gè)結(jié)點(diǎn)已經(jīng)在路徑之中時(shí)就表明存在一條回路;掃描路徑向量path可以獲得這條回路上的所有結(jié)點(diǎn).把結(jié)點(diǎn)序列(例如,142857)存入thiscycle中;由于這種算法中,一條回路會(huì)被發(fā)現(xiàn)好幾次,所以必須先判斷該回路是否已經(jīng)在cycles中被記錄過,如果沒有才能存入cycles的一個(gè)行向量中.把cycles的每一個(gè)行向量取出來與之比較.由于一條回路可能有多種存儲(chǔ)順序,比如142857等同于285714和571428,所以還要調(diào)整行向量的次序,并存入temp數(shù)組,例如,thiscycle為142857第一個(gè)結(jié)點(diǎn)為1,cycles的當(dāng)前向量為857142,則找到后者中的1,把1后部分提到1前部分前面,最終在temp中得到142857,與thiscycle比較,發(fā)現(xiàn)相同,因此142857和857142是同一條回路,不予存儲(chǔ).這個(gè)算法太復(fù)雜,很難保證細(xì)節(jié)的準(zhǔn)確性,大家理解思路便可.希望有人給出更加簡(jiǎn)捷的算法. <BR>
<br>
<a href="javascript:history.go(-1)">返回上頁</a><br><a href=http://www.copathway.com/cndevforum/>訪問論壇</a></p></blockquote>