Java課程設計報告-地鐵換乘

地鐵換乘第1章課題概述本次Java課程設計的題目是設計并實現(xiàn)地鐵換乘中換乘路線以及最優(yōu)價格。1.1課題的目的為解決如今交通擁擠的狀況，多數(shù)城市建設多條地體線路，由于地鐵線路的交錯以及站點的繁多，通過編寫程序對用戶所在的起始站以及用戶所要到達的目的地兩站點進行分析，通過算法的計算，得出最優(yōu)價格的乘車方案提供給用戶，以便用戶在挑選乘車方案時提供給用戶方便。1.2課題的要求1.2.1輸入輸出的要求（1）程序運行后向用戶顯示一個地鐵換乘的主窗口，在窗口內顯示兩個可選擇下來菜單，為用戶提供選擇，而不是讓用戶進行輸入站點。（2）用戶對起始站以及目的地選擇完畢后，在窗口下端的文本區(qū)域將顯示提供給用戶的最優(yōu)價格方案。（3）對于輸出方案的格式中，線路名稱用“-”分開，如果兩個線路之間使用聯(lián)票，則聯(lián)票之間用“，”連接，并在兩端加括號，與普通票價區(qū)分。（4）當多個方案有相同的最小花費，輸出任意一個方案即可。1.2.2程序實現(xiàn)的功能要求（1）對于測試程序過程中，測試數(shù)據(jù)與實例數(shù)據(jù)不同，并能夠輸出正確方案以及輸出的各式正確。（2）當用戶選擇當前起始站，以及目的地，窗口能夠輸出方案。第2章概要設計2.1程序的主體結構及主要功能的算法2.1.1窗口主程序主體的程序為用戶提供一個可供選擇站點的GUI界面，方便了用戶的輸入。對于程序的主體的流程，如圖：圖2-1主程序流程圖該界面為用戶顯示兩個可選擇站點的下拉菜單，而可能導致輸出錯誤的的原因是由于用戶會在選擇站點的過程中，誤點導致起始站與目的站相同。如果出現(xiàn)錯誤，程序將彈出錯誤信息的窗口提示用戶選擇的站點有誤，并提示用戶重新選擇。2.1.2線路尋找算法當用戶啟動程序并選擇起始站與目的站，兩個站點名稱作為String類型參數(shù)傳入程序，并分別創(chuàng)建對象，線路查找的算法為從起始站找到相鄰的站點，將所查找相鄰的站點名稱與起始的目的站作為參數(shù)，利用遞歸得到所經(jīng)過的線路。圖2-2從起始站遍歷圖2-3使用遞歸遍歷起始站作為from，目的站作為to，首先查找from所在的線路，并將所得的所有線路在列表中循環(huán)，從第一個線路中，獲得該線路包含的所有站點，同時，將當前訪問的線路分別存入兩個不同的容器中，其中一個作為儲存已訪問線路的容器，另一個作為所要輸出方案的線路。圖2-4使用容器儲存線路并在之前的循環(huán)中再次嵌套一層循環(huán)，在內層的循環(huán)中，所遍歷到的站點作為起始站，目的站保持不變，通過遞歸的方法再次遍歷未遍歷的站點，與線路相同，已訪問的站點儲存在另一個容器中。圖2-5儲存已訪問站點直到from與to相同。如果存在from與to相同，將儲存輸出結果的容器輸出，并刪除該容器最后一位元素。儲存已訪問站點或路線容器中，最后一個元素設為false。2.1.3最優(yōu)價格最優(yōu)價格利用數(shù)學歸納法，即假設已知從線1到線i-1所要花費的價格，從而推算出從線1到線i所花費的價格。由于存在某些線路之間可以使用聯(lián)票，這就導致在使用數(shù)學歸納法的過程中，可能會出現(xiàn)3種情況。1）線i-1與線i之間沒有聯(lián)票；2）線i-2與線i-1之間沒有聯(lián)票，線i-1與線i之間有聯(lián)票；3）線i-2與線i-1之間有聯(lián)票，線i-1與線i之間有聯(lián)票；圖2-6計算最優(yōu)價格三種情況在尋找線路的算法中，當完成一次線路的查找之后，將儲存線路的容器作為參數(shù)傳入計算價格的方法中，通過上述的算法得出價格并復制給最終作為結果輸出價格的變量optimal_price暫時儲存，但尋找線路的算法再次完成一次線路的查找，重復上述過程，通過與上一次得出的價格做比較，把較小的賦值給optimal_price，直至沒有線路方案傳入該方法。2.1.4地鐵換乘相關信息儲存及提取對于上面描述的兩個算法中，涉及到線路名，站點名的查找，為了方便程序的運行，分別對于不同的數(shù)據(jù)使用不同的容器儲存。圖2-7線路和站點的儲存線路與站點的儲存使用Map容器，將線路或站點的名稱作為鍵，所對應的對象作為值與鍵相對應。除此之外，在儲存線路價格通過使用二維數(shù)組儲存線路之間的價格，所以需要將每個線路添加一一對應的序號，使用兩個不同的Map容器分別儲存線路名稱及其所對應的序號，和站點名稱與其所對應的序號。圖2-8線路（站點）的序號分配儲存線路價格所使用的二維數(shù)組的長度和寬度為線路數(shù)量大小，在初始化數(shù)組下，儲存的數(shù)值均為0，通過對price.txt的讀取，單條線路在二維數(shù)組中的數(shù)值為該線路價格，如果兩條線路之間可以使用聯(lián)票，則儲存為聯(lián)票的價格，其他為初始值。圖2-9二維數(shù)組儲存價格第3章程序功能的實現(xiàn)3.1主類功能的實現(xiàn)主類功能的運行結果為：圖3-1程序界面主窗口分為上下兩部分（up_panel，down_panel），上面部分為程序輸入信息，下面部分為用戶輸出信息。up_panel分為三部分為別為from_panel，表示起始站相關信息；mid_panel，表示為分隔，是界面顯示更加條理分明；to_panel，表示目的地相關信息。相關代碼為：Choice_stations_menu_from; Choice _stations_menu_to; JTextArea_optimal_price; publicmy_window(Stringname){ super(name); DimensionscreenSize=Toolkit.getDefaultToolkit().getScreenSize(); setSize(300,300); setLocation(screenSize.width/2-300/2,screenSize.height/2-300/2); setResizable(false); this.addWindowListener(newwindow_monitor()); } publicvoidlaunch(){ /*創(chuàng)建新的窗口*/ my_window_window=newmy_window("SubwayChange"); GridLayoutgl=newGridLayout(2,1); /*獲得所有站名*/ Enginee=newEngine(); e.initialize(); Set<String>_stations_set=e._stations.keySet(); FlowLayoutfl=newFlowLayout(); fl.setHgap(20); fl.setVgap(30); Panelup_panel=newPanel(fl); up_panel.setBackground(newColor(245,245,245)); gl.setVgap(10); _window.setLayout(gl); Panelfrom_panel=newPanel(gl); Labelfrom_label=newLabel("起始站"); from_label.setAlignment(Label.CENTER); from_panel.add(from_label); _stations_menu_from=newChoice(); Iterator<String>i_from=_stations_set.iterator(); while(i_from.hasNext()){ _stations_menu_from.add(i_from.next()); } _stations_menu_from.addItemListener(newChoiceMonitor()); from_panel.add(_stations_menu_from); Panelmid_panel=newPanel(gl); Labelmid_label=newLabel("-"); mid_label.setAlignment(Label.CENTER); mid_panel.add(mid_label); mid_panel.add(mid_label); Panelto_panel=newPanel(gl); Labelto_label=newLabel("目的地"); to_label.setAlignment(Label.CENTER); to_panel.add(to_label); _stations_menu_to=newChoice(); Iterator<String>i_to=_stations_set.iterator(); while(i_to.hasNext()){ _stations_menu_to.add(i_to.next()); } _stations_menu_to.addItemListener(newChoiceMonitor()); to_panel.add(_stations_menu_to); up_panel.add(from_panel,BorderLayout.WEST); up_panel.add(mid_panel,BorderLayout.CENTER); up_panel.add(to_panel,BorderLayout.EAST); _optimal_price=newJTextArea(); _optimal_price.setFont(newFont("Default",Font.PLAIN,15)); _window.add(up_panel); _window.add(_optimal_price); _window.setVisible(true);3.2程序主要功能的實現(xiàn)3.2.1判斷用戶輸入是否規(guī)范當用戶選擇站點時，起始站與目的站相同，則程序需提示用戶，對程序的輸入有誤，并重新選擇站點。Stringfrom=_stations_menu_from.getSelectedItem(); Stringto=_stations_menu_to.getSelectedItem(); if(from.equals(to)){ error_windowerror=newerror_window(); error.setVisible(true); }該代碼為用戶選擇某一站點是程序作出的相應，首先對于輸入信息判斷，如果有誤，則向用戶提示錯誤信息。super("Error"); JTextAreaerror_info=newJTextArea(); error_info.setFont(newFont("Default",Font.PLAIN,15)); error_info.setText("你選擇的起始站與目的地相同，請重新選擇"); this.add(error_info); this.pack(); DimensionscreenSize=Toolkit.getDefaultToolkit().getScreenSize(); setLocation(screenSize.width/2-300/2,screenSize.height/2-300/2); setResizable(false); this.addWindowListener(newerror_window_monitor());該代碼為判斷為上述判斷中為true時作出的相應。如果為false，即用戶輸入無誤，則作出正確的相應，輸出最優(yōu)方案。Enginee1=newEngine(); e1.initialize(); e1.get_optimal_route(from,to); String_optimal=e1._optimal; int_price=e1._price; _optimal_price.setText("最優(yōu)價格方案為：\n"+"-"+_optimal+"="+_price);3.2.2獲取線路及價格信息當程序讀取stations.txt內容的過程中，首行一定是線路名稱，當讀取內容為空的時候，則讀取的下一行內容同樣一定是線路名稱，其他情況則為站點名稱。while((temp=br.readLine())!=null){ if(temp.length()==0){ temp=br.readLine(); subway_line=newSubwayLine(temp); _subway_lines.put(temp,subway_line); _line_index_mapper.put(temp,++index); }else{ Stationstation=null; if(_stations.containsKey(temp)){ station=_stations.get(temp); }else{ station=newStation(temp); _stations.put(temp,station); _station_index_mapper.put(temp,station_index++); } subway_line.add_station(station); station.add_subway_line(subway_line); } }讀取price.txt過程中，內容的格式是固定的，均為線路名（聯(lián)票線路）+“”+價格，由于有些線路之間可以使用線路聯(lián)票，則需對線路名稱進行分割，獲得使用聯(lián)票的兩條線路名，并將相應價格數(shù)據(jù)存入二維數(shù)組中。line_price=read_data.split(""); /*非聯(lián)票*/ if(line_price[0].indexOf(",")==-1){ i=j=_line_index_mapper.get(line_price[0]); _price_matrix[i][j]=Integer.parseInt(line_price[1]); } /*聯(lián)票*/ else{ String[]line_cheaper_price=line_price[0].split(","); i=_line_index_mapper.get(line_cheaper_price[0]); j=_line_index_mapper.get(line_cheaper_price[1]); _price_matrix[i][j]=Integer.parseInt(line_price[1]); _price_matrix[j][i]=Integer.parseInt(line_price[1]); }3.2.3獲取路線列表根據(jù)尋找線路算法，代碼為if(from.equals(to)){ /*到達終點站*/ calc_optimal_price(route); }首先判斷是否到起始站與目的站相同，如果相同表示到達目的站，則將所得線路列表傳入計算價格的算法中，進行最優(yōu)價格的計算。elseif(route.size()>_subway_lines.size()){ /*錯誤*/ }當儲存線路列表的容量大小超過所有線路的數(shù)量，則該線路列表錯誤，不進行操作。Stationstation=_stations.get(from); List<SubwayLine>subway_lines=station._subway_lines; for(inti=0;i<subway_lines.size();++i){ SubwayLinesubway_line=subway_lines.get(i); if(_is_visit.get(_line_index_mapper.get(subway_line._name) .intValue())==true){ /*已經(jīng)遍歷過的線路不再遍歷*/ continue; } route.add(subway_line); intline_index=_line_index_mapper.get(subway_line._name).intValue(); _is_visit.set(line_index,true); for(intj=0;j<subway_line._stations.size();++j){ Stationtemp=subway_line._stations.get(j); intstation_index=_station_index_mapper.get(temp._station_name).intValue(); if(_is_station_visit.get(station_index)){ continue; } else{ _is_station_visit.set(_station_index_mapper.get(temp._station_name).intValue(),true); get_route(temp._station_name,to,route);以上代碼為線路尋找的代碼，當完成一次路線的查找，程序將進行一下代碼，首先將上一個尋找的站點設為false，結束內層循環(huán)后，將上一個尋找的線路設為false，由于在兩個站點之間，可能存在多個不同的線路方案，當計算完成一個線路列表之后，應將該中最后一個元素刪除。 _is_station_visit.set(_station_index_mapper.get(temp._station_name).intValue(),false); } } _is_visit.set(line_index,false); route.remove(route.size()-1); }3.2.4計算最優(yōu)價格根據(jù)上述計算最優(yōu)價格算法，計算的過程中，會出現(xiàn)三種情況，分別定義三個Integer類型的對象，并初始化為最大值。Integerprice_1=Integer.MAX_VALUE; Integerprice_2=Integer.MAX_VALUE; Integerprice_3=Integer.MAX_VALUE;根據(jù)所得的線路列表分別對三種情況進行判斷，并分別對三個Integer對象進行賦值。if(_price_matrix[subway_index_i_1][subway_index_i]!=0){ /*i-1與i有聯(lián)票*/ if(is_join==false){ /*i-1沒有與i-2聯(lián)票，且i-1與i有聯(lián)票*/ price_2=optimal_price -_price_matrix[subway_index_i_1][subway_index_i_1] +_price_matrix[subway_index_i_1][subway_index_i]; }elseif(is_join==true){ /*i-1與i-2聯(lián)票，需要判斷i-1與i-2聯(lián)好，還是與i聯(lián)好*/ intsubway_index_i_2=_line_index_mapper.get(route .get(i-2)._name); price_3=optimal_price -_price_matrix[subway_index_i_2][subway_index_i_1] +_price_matrix[subway_index_i_2][subway_index_i_2] +_price_matrix[subway_index_i_1][subway_index_i]; } }else{ /*如果i-1與i沒有聯(lián)票，不做操作*/ }由于在判斷的過程中，存在三個Integer對象其中一個，或兩個沒有進行賦值，需將初始化值為最大值，如果初始化為，則在判斷三個量之間大小時，只能輸出0。if(price_1<price_2&&price_1<price_3){ /*方案1最優(yōu)*/ optimal_price=price_1; optimal_route.add(subway_line._name); is_join=false; }elseif(price_2<price_1&&price_2<price_3){ /*方案2最優(yōu)*/ optimal_price=price_2; optimal_route.remove(optimal_route.size()-1); optimal_route.add("("+route.get(i-1)._name+"," +route.get(i)._name+")"); is_join=true; }elseif(price_3<price_1&&price_3<price_2){ /*方案3最優(yōu)*/ optimal_route.remove(optimal_route.size()-1); optimal_route.add(route.get(i-2)._name); optimal_route.add("("+route.get(i-1)._name+"," +route.get(i)._name+")"); optimal_price=price_3; is_join=true; }由于兩個站點之間，可能存在多個不同的線路方案，則需判斷當前線路方案的花費與上個線路方案的花費進行比較。if(optimal_price<_price){ /*比原來的小*/ _price=optimal_price; _optimal=""; for(inti=0;i<optimal_route.size();++i){ if(i!=optimal_route.size()-1){ _optimal+=(optimal_route.get(i)+"-"); } else{ _optimal+=optimal_route.get(i); } } }第4章調試及發(fā)現(xiàn)問題的解決1.如何將線路與站點相互結合？創(chuàng)建兩個類分別為線路類與站點類，在線路類中，創(chuàng)建String類對象儲存線路名稱和List<String>儲存該線路包含站點。在站點類中，創(chuàng)建String對象儲存站點名稱，List<String>儲存該站點所在線路和boolean變量標志該站點是否為換乘站。通過創(chuàng)建兩個類的實例對象，可以從線路獲得相關站點信息或從站點獲得相關線路信息。2.如何儲存線路價格？如果使用一位數(shù)組或者Map容器儲存線路及其對應的價格，當在計算最優(yōu)價格時，需逐一遍歷線路，當某一線路可以去前者或后者使用聯(lián)票時，無法方便的獲得聯(lián)票的價格。使用二維數(shù)組，長度與寬度均為線路總數(shù)量。初始值為0，單一的線路值設為該線路價格，可以使用聯(lián)票的兩條線路之間的值設為聯(lián)票的價格。3.尋找線路時，可能存在多條線路方案，如何獲得所有可行的方案？每一次尋找線路分為兩層循環(huán)，當一條可行線路方案查找的最后，即起始站與目的站相同時，將該方案經(jīng)過的線