交通運(yùn)輸學(xué)院課程設(shè)計(jì)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：14 大?。?82.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁(yè)，還剩13頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　目錄　　第1章引言2　　1.1目的：2　　1.2 內(nèi)容：2　　1.3主要任務(wù)：2

2、;　　第2章設(shè)計(jì)過(guò)程3　　2.1設(shè)計(jì)思路3　　2.1.1Floyd算法3　　2.1.2鄰接矩陣3　　2.1.3圖形用戶界面4　　2.2設(shè)計(jì)內(nèi)容及分析4&

3、lt;p>　　2.2.1 算法部分4　　2.2.2圖形界面處理部分：9　　第3章總結(jié)13　　附錄14　　參考文獻(xiàn)17

4、;　　第1章引言　　1.1目的：　　發(fā)現(xiàn)課程學(xué)習(xí)中的不足和薄弱環(huán)節(jié)，予以補(bǔ)充和加強(qiáng)。綜合運(yùn)用在課程學(xué)習(xí)過(guò)程中所學(xué)知識(shí)，同時(shí)為了實(shí)現(xiàn)課程設(shè)計(jì)的規(guī)定成果進(jìn)行更深入的理論學(xué)習(xí)和實(shí)踐拓展。培養(yǎng)獨(dú)立思考和解決問(wèn)題的能力，探索和創(chuàng)新的能力。具體如下：　?、艔?fù)習(xí)、

5、鞏固Java語(yǔ)言的基礎(chǔ)知識(shí)，進(jìn)一步加深對(duì)Java語(yǔ)言的理解和掌握；　　⑵課程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，鍛煉學(xué)生的分析解決實(shí)際問(wèn)題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力；　?、峭ㄟ^(guò)課程設(shè)計(jì)實(shí)踐，訓(xùn)練并提高學(xué)生在查閱設(shè)計(jì)資料、運(yùn)用標(biāo)準(zhǔn)與規(guī)范和應(yīng)用計(jì)算機(jī)等方面的能力。&l

6、t;p>　　1.2 內(nèi)容：　　求解最短路問(wèn)題（Floyd算法）；　　功能要求：實(shí)現(xiàn)Floyd算法，求解最短路問(wèn)題，用GUI界面實(shí)現(xiàn)。　　1.3主要任務(wù)：　　在java開發(fā)環(huán)境下，運(yùn)用GUI用

7、戶界面技術(shù)，通過(guò)Floyd算法，實(shí)驗(yàn)對(duì)最短路問(wèn)題的求解。要求通過(guò)對(duì)Floyd算法的學(xué)習(xí)，掌握其原理，運(yùn)用Java語(yǔ)言來(lái)實(shí)現(xiàn)該算法流程，取得最短路方案。通過(guò)GUI界面顯示該最短路問(wèn)題的網(wǎng)絡(luò)圖，并標(biāo)記顯示出最短路的路徑。　　第2章設(shè)計(jì)過(guò)程　　2.1設(shè)計(jì)思路

8、　　2.1.1Floyd算法　　首先：對(duì)最短路問(wèn)題中的Floyd算法有個(gè)較為深入的了解。其基本思想可簡(jiǎn)歸納如下：floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問(wèn)題，floyd算法為這個(gè)目標(biāo)重新做一個(gè)詮釋。假設(shè)Ak(i,j)表示從i到j(luò)中途不經(jīng)過(guò)索引比k大的點(diǎn)的最短路徑。它將最短路徑的概念做了限制，使得該限制有機(jī)會(huì)滿足迭代關(guān)

9、系，這個(gè)迭代關(guān)系就在于研究：假設(shè)Ak(i,j)已知，是否可以借此推導(dǎo)出Ak-1(i,j)。經(jīng)過(guò)分析，可得到最短路的關(guān)鍵式子： Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )，這是由Java實(shí)現(xiàn)Floyd算法的基本依據(jù)。簡(jiǎn)單說(shuō)，依次掃描每一點(diǎn)(k)，并以該點(diǎn)作為中介點(diǎn)，計(jì)算出通過(guò)k點(diǎn)的其他任意兩點(diǎn)(i,j)的最短距離，這就是floyd算法的精髓。&

10、lt;/p>　　具體做法：利用一個(gè)三重循環(huán)產(chǎn)生一個(gè)存儲(chǔ)每個(gè)結(jié)點(diǎn)最短距離的矩陣.弗洛伊德算法仍然使用圖的鄰接矩陣arcs[n+1][n+1]來(lái)存儲(chǔ)帶權(quán)有向圖。算法的基本思想是:設(shè)置一個(gè)n x n的矩陣A(k)，其中除對(duì)角線的元素都等于0外，其它元素a(k)[i][j]表示頂點(diǎn)i到頂點(diǎn)j的路徑長(zhǎng)度，K表示運(yùn)算步驟。開始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作為路徑長(zhǎng)度，沒(méi)有有向邊時(shí)，路徑長(zhǎng)度為∞，當(dāng)K=0時(shí), A

11、(0)[i][j]=arcs[i][j]，以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來(lái)的路徑長(zhǎng)度減少了，則以此新路徑代替原路徑，修改矩陣元素。簡(jiǎn)單概括為： 　　第一步，讓所有邊上加入中間頂點(diǎn)1，取A[i][j]與A[i][1]+A[1][j]中較小的值作A[i][j]的值，完成后得到A(1)，

12、;　　第二步，讓所有邊上加入中間頂點(diǎn)2，取A[i][j]與A[i][2]+A[2][j]中較小的值，完成后得到A(2)…，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果,A(n)[i][j]表示頂點(diǎn)i到頂點(diǎn)j的最短距離。　　2.1.2鄰接矩陣　　在設(shè)計(jì)過(guò)程中，還會(huì)涉及一個(gè)重要概念：鄰接矩陣。在圖

13、的鄰接矩陣表示法中： 　　① 用鄰接矩陣表示頂點(diǎn)間的相鄰關(guān)系 　?、?用一個(gè)順序表來(lái)存儲(chǔ)頂點(diǎn)信息　　若G是網(wǎng)絡(luò)，則鄰接矩陣可定義為： 　　其中： 　　w ij 表示邊上的權(quán)值; </p&

14、gt;　　∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。　　【例】下面帶權(quán)圖的兩種鄰接矩陣分別為A 3 和A 4 。 　　2.1.3圖形用戶界面　　為了達(dá)到最終目的，又對(duì)Java中的圖形用戶界面做了簡(jiǎn)單的學(xué)習(xí)，認(rèn)識(shí)到Java 不僅僅用于網(wǎng)絡(luò)開發(fā)，也可以開發(fā)應(yīng)用程序。這就體現(xiàn)的GUI的作用所在

15、。在學(xué)習(xí)了窗口的應(yīng)用后，又對(duì)Graphics類，做了較多的學(xué)習(xí)。用于繪制圖形和簡(jiǎn)單的圖像處理，比如后面用到的畫直線，畫圓等.　　最后，經(jīng)過(guò)多次調(diào)試，將Floyd算法與GUI界面結(jié)合起來(lái)，達(dá)到最終目的，即通過(guò)運(yùn)用Java實(shí)現(xiàn)由圖形用戶界面顯示Floyd算法。　　2.2設(shè)計(jì)內(nèi)容及分析　　2.2.1 算法部分</

16、p>　　聲明部分：　　public class Floyd {　　int[][] length ;// 任意兩點(diǎn)之間路徑長(zhǎng)度 　　int[][][] path ;// 任意兩點(diǎn)之間的路徑　　public F

17、loyd(int[][] G) { 　　int MAX = 100; 　　int row = G.length;// 圖G的行數(shù) 　　int[][] spot = new int[row][row];// 定義任意兩點(diǎn)之間經(jīng)過(guò)的點(diǎn) 　　int[] onePath = ne

18、w int[row];// 記錄一條路徑 　　length = new int[row][row]; 　　path = new int[row][row][]; 　　對(duì)路徑的處理部分：　　for (int i = 0; i <

19、row; i++) // 處理圖兩點(diǎn)之間的路徑 　　for (int j = 0; j < row; j++) { 　　if (G[i][j] == 0) 　　G[i][j] = MAX;// 沒(méi)有路徑的兩個(gè)點(diǎn)之間的路徑為默認(rèn)最大 　　if (i == j) <

20、;/p>　　G[i][j] = 0;// 本身的路徑長(zhǎng)度為0 　　} 　　for (int i = 0; i < row; i++) // 初始化為任意兩點(diǎn)之間沒(méi)有路徑 　　for (int j = 0; j < row; j++) &

21、lt;/p>　　spot[i][j] = -1; 　　for (int i = 0; i < row; i++) // 假設(shè)任意兩點(diǎn)之間的沒(méi)有路徑 　　onePath[i] = -1; 　　找最短路的過(guò)程部分：　　for (int v

22、= 0; v < row; ++v) 　　for (int w = 0; w < row; ++w) 　　length[v][w] = G[v][w]; 　　for (int u = 0; u < row; ++u) 　　for (int v = 0;

23、v < row; ++v) 　　for (int w = 0; w < row; ++w) 　　if (length[v][w] > length[v][u] + length[u][w]) { 　　length[v][w] = length[v][u] + length[u][w];// 如果

24、存在更短路徑則取更短路徑 　　spot[v][w] = u;// 把經(jīng)過(guò)的點(diǎn)加入 　　} 　　for (int i = 0; i < row; i++) { // 求出所有的路徑 　　int[] point = new int

25、[1]; 　　for (int j = 0; j < row; j++) { 　　point[0] = 0; 　　onePath[point[0]++] = i; 　　outputPath(spot, i, j, onePath, point);

26、;　　path[i][j] = new int[point[0]]; 　　for (int s = 0; s < point[0]; s++) 　　path[i][j][s] = onePath[s]; 　　} <p&

27、gt;　　記錄最短路部分：　　void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {　　// 輸出i到j(luò) 的路徑的實(shí)際代碼,point[]記錄一條路徑的長(zhǎng)度 　　if (i == j)

28、 　　return; 　　if (spot[i][j] == -1) 　　onePath[point[0]++] = j; 　　else {

29、;　　outputPath(spot, i, spot[i][j], onePath, point); 　　outputPath(spot, spot[i][j], j, onePath, point); 　　} 　　} </p&g

30、t;　　主函數(shù)部分：　　public static void main(String[] args) {　　System.out.println("請(qǐng)輸入所求問(wèn)題的中間節(jié)點(diǎn)數(shù)：");　　int row;</b&

31、gt;　　Scanner shuru=new Scanner(System.in);　　row=shuru.nextInt();　　System.out.println("請(qǐng)依次輸入兩節(jié)點(diǎn)間的距離：");　　int n,m;</

32、b>　　int data[][]=new int[row][row];　　for(m=0;m<row;m++){　　for(n=0;n<row;n++){　　data[m][n]=shuru.nextInt();

33、　　}　　}　　System.out.println("原矩陣為：");　　for(int i=0;i<row;i++){　　for(int j=0;j<row;j

34、++){　　System.out.printf("%4d",data[i][j]);　　}　　System.out.println();　　}<p

35、>　　對(duì)輸入數(shù)據(jù)進(jìn)行處理：　　for (int i = 0; i < data.length; i++)　　for (int j = i; j < data.length; j++)　　if (data[i][j] != data[j][i]) <

36、b>　　return; 　　}　　Floyd test=new Floyd(data); 　　for (int i = 0; i < data.length; i++) 　　for (int j = i

37、; j < data[i].length; j++) { 　　System.out.println(); 　　System.out.print("從v"+i+"到v"+j+"所經(jīng)過(guò)的點(diǎn)有: "); 　　//輸出經(jīng)過(guò)的路點(diǎn)</

38、b>　　for (int k = 0; k < test.path[i][j].length; k++) 　　System.out.print(test.path[i][j][k] + " "); 　　System.out.println(); <p&

39、gt;　　System.out.println("從v"+i+"到v"+j+"最短路徑長(zhǎng)度是:" 　　+ test.length[i][j]);// 輸出最短路部分　　} 　　}

40、;　　}　　部分截圖如圖1，圖2：　　圖1　　圖2　　2.2.2圖形界面處理部分：<p

41、>　　外層窗體：　　public static void main(String args[]){　　ComputerFrame fr=new ComputerFrame();　　fr.setTitle("Floyd算法求最短路問(wèn)題"); <

42、/p>　　}　　}　　class ComputerFrame extends JFrame implements TextListener　　{ TextArea text1,text2;

43、;　　public ComputerFrame(){　　setLayout(new FlowLayout());　　text1=new TextArea(10,30);//確定文本區(qū)的大小　　text2=new TextArea(10,30);　　a

44、dd(text1);　　add(text2); 　　text2.setEditable(false);　　text1.addTextListener(this);　　setSize(300,400);　　setVisible(tr

45、ue);　　addWindowListener(new WindowAdapter(){　　public void windowClosing(WindowEvent e){　　System.exit(0);　　}

46、;　　});　　validate();　　}　　生成如圖3的一個(gè)兩個(gè)文本框的窗體。上面用來(lái)輸入數(shù)據(jù)，下面用來(lái)顯示路徑圖；　　圖3<

47、/p>　　內(nèi)部畫圖部分：　　public void actionPerformed(ActionEvent e){　　int a=Integer.parseInt(text1.getText());　　int b=Integer.parseInt(

48、text2.getText());　　text3.setText(String.valueOf(shuzu[a-1][b-1]));　　}　　public void paint(Graphics g){ 　　super.paint(g

49、); 　　Graphics2D g1 = (Graphics2D)g;　　//Ellipse2D.Double 　　//public Ellipse2D.Double(double x,double y,double w,double h)　　// 根據(jù)指定坐標(biāo)構(gòu)造和初始

50、化 Ellipse2D 參數(shù)：　　Ellipse2D e1 = new Ellipse2D.Double(40,60 ,20,20); 　　Ellipse2D e2 = new Ellipse2D.Double(200,60,20,20); 　　Ellipse2D e3 = new Ellipse2D.Doubl

51、e(200,200,20,20); 　　Ellipse2D e4 = new Ellipse2D.Double(40,200,20,20); 　　Ellipse2D e5 = new Ellipse2D.Double(320,130,20,20); 　　Ellipse2D e6 = new Ellipse2D.D

52、ouble(400,220,20,20); 　　//x - 窗體矩形左上角的 X 坐標(biāo),y - 窗體矩形左上角的 Y 坐標(biāo),w - 窗體矩形的寬度,h - 窗體矩形的高度　　g1.setPaint(Color.RED); 　　g1.draw(e1); 　　g1.drawS

53、tring("V1", 45, 75);　　g1.draw(e2); 　　g1.drawString("V2", 205,75);　　g1.draw(e3);　　g1.drawString("V3", 45, 2

54、15);　　g1.draw(e4);　　g1.drawString("V4", 205, 215);　　g1.draw(e5); 　　g1.drawString("V5", 325, 145);<p&g

55、t;　　g1.draw(e6); 　　g1.drawString("V6", 400, 180);　　g1.drawLine(60, 70, 200,70);　　g1.drawString("3", 130, 70);　　g1.dr

56、awLine(50, 80, 50, 200);　　g1.drawString("5", 40, 135);　　g1.drawLine(60, 210,200 ,210);　　g1.drawString("2", 130,210);

57、　　g1.drawLine(210, 80, 210,200);　　g1.drawString("4", 200, 135);　　g1.drawLine(55, 75, 203, 203);　　g1.drawString("8", 110, 120);

58、　　g1.drawLine(55, 203, 203, 75);　　g1.drawString("6", 85, 170);　　g1.drawLine(220, 70, 320, 140);　　g1.drawString("11", 280,110);&

59、lt;/p>　　g1.drawLine(220, 210,320, 140);　　g1.drawString("10", 280, 160);　　} 　　}<p

60、>　　第3章總結(jié)　　通過(guò)本次課程設(shè)計(jì)，基本上解決了Floyd算法求解最短路徑問(wèn)題，這使我更加深入的了解了Java語(yǔ)言對(duì)于實(shí)際應(yīng)用的意義。更主要的是，我深深的意識(shí)到，我對(duì)圖形用戶界面有關(guān)方面知識(shí)的嚴(yán)重匱乏，對(duì)它的學(xué)習(xí)有十分的必要性。尤其是在這次課程設(shè)計(jì)中，并沒(méi)有對(duì)圖形用戶界面有很好的應(yīng)用，沒(méi)能對(duì)Floyd算法完全由GUI來(lái)實(shí)現(xiàn)，沒(méi)能完全符合老師的要求

61、，還希望老師能夠見諒。這一點(diǎn)也正是我尚待解決的重要問(wèn)題。　　附錄　　package floyd;　　public class Floyd_0 {　　int[][] length = null;<p&g

62、t;　　int[][][] path = null; 　　public Floyd_0 (int[][] G) { 　　int MAX = 100; 　　int row = G.length; 　　int[][] spot = new int[row][row];int

63、[] onePath = new int[row]; 　　length = new int[row][row]; 　　path = new int[row][row][]; 　　for (int i = 0; i < row; i++) 　　for (int j =

64、 0; j < row; j++) { 　　if (G[i][j] == 0) 　　G[i][j] = MAX;if (i == j) 　　G[i][j] = 0; } 　　for (int i = 0; i < row; i++) </p&g

65、t;　　for (int j = 0; j < row; j++)　　spot[i][j] = -1; 　　for (int i = 0; i < row; i++) 　　onePath[i] = -1; 　　for (int v = 0

66、; v < row; ++v) 　　for (int w = 0; w < row; ++w) 　　length[v][w] = G[v][w]; 　　for (int u = 0; u < row; ++u) 　　for (int v = 0; v &

67、lt; row; ++v) 　　for (int w = 0; w < row; ++w) 　　if (length[v][w] > length[v][u] + length[u][w]) { 　　length[v][w] = length[v][u] + length[u][w];更短路徑 <

68、;/p>　　spot[v][w] = u; 　　} 　　for (int i = 0; i < row; i++) { 　　int[] point = new int[1]; 　　for (int j

69、 = 0; j < row; j++) { 　　point[0] = 0; 　　onePath[point[0]++] = i; 　　outputPath(spot, i, j, onePath, point); 　　path[i][j] = new int[poi

70、nt[0]]; 　　for (int s = 0; s < point[0]; s++) 　　path[i][j][s] = onePath[s]; 　　} 　　}

71、　　} 　　void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point{ 　　if (i == j) 　　return; </p&g

72、t;　　if (spot[i][j] == -1) 　　onePath[point[0]++] = j; 　　else { 　　outputPath(spot, i, spot[i][j], onePath, point); &l

73、t;p>　　outputPath(spot, spot[i][j], j, onePath, point); 　　} 　　} 　　public static void main(String[] args) {

74、　　System.out.println("請(qǐng)輸入所求問(wèn)題的中間節(jié)點(diǎn)數(shù)：");　　int row;　　Scanner shuru=new Scanner(System.in);　　row=shuru.nextInt();</p&g

75、t;　　System.out.println("請(qǐng)依次輸入兩節(jié)點(diǎn)間的距離：");　　int n,m;　　int data[][]=new int[row][row];　　for(m=0;m<row;m++){

76、　　for(n=0;n<row;n++){　　data[m][n]=shuru.nextInt();　　}　　}　　System.out.println("輸

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

交通運(yùn)輸學(xué)院課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

交通運(yùn)輸學(xué)院課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載