Java課程設(shè)計(jì)報(bào)告-地鐵換乘

地鐵換乘第1章課題概述本次Java課程設(shè)計(jì)的題目是設(shè)計(jì)并實(shí)現(xiàn)地鐵換乘中換乘路線以及最優(yōu)價(jià)格。1.1課題的目的為解決如今交通擁擠的狀況，多數(shù)城市建設(shè)多條地體線路，由于地鐵線路的交錯(cuò)以及站點(diǎn)的繁多，通過編寫程序?qū)τ脩羲诘钠鹗颊疽约坝脩羲竭_(dá)的目的地兩站點(diǎn)進(jìn)行分析，通過算法的計(jì)算，得出最優(yōu)價(jià)格的乘車方案提供給用戶，以便用戶在挑選乘車方案時(shí)提供給用戶方便。1.2課題的要求1.2.1輸入輸出的要求（1）程序運(yùn)行后向用戶顯示一個(gè)地鐵換乘的主窗口，在窗口內(nèi)顯示兩個(gè)可選擇下來菜單，為用戶提供選擇，而不是讓用戶進(jìn)行輸入站點(diǎn)。（2）用戶對(duì)起始站以及目的地選擇完畢后，在窗口下端的文本區(qū)域?qū)@示提供給用戶的最優(yōu)價(jià)格方案。（3）對(duì)于輸出方案的格式中，線路名稱用“-”分開，如果兩個(gè)線路之間使用聯(lián)票，則聯(lián)票之間用“，”連接，并在兩端加括號(hào)，與普通票價(jià)區(qū)分。（4）當(dāng)多個(gè)方案有相同的最小花費(fèi)，輸出任意一個(gè)方案即可。1.2.2程序?qū)崿F(xiàn)的功能要求（1）對(duì)于測(cè)試程序過程中，測(cè)試數(shù)據(jù)與實(shí)例數(shù)據(jù)不同，并能夠輸出正確方案以及輸出的各式正確。（2）當(dāng)用戶選擇當(dāng)前起始站，以及目的地，窗口能夠輸出方案。第2章概要設(shè)計(jì)2.1程序的主體結(jié)構(gòu)及主要功能的算法2.1.1窗口主程序主體的程序?yàn)橛脩籼峁┮粋€(gè)可供選擇站點(diǎn)的GUI界面，方便了用戶的輸入。對(duì)于程序的主體的流程，如圖：圖2-1主程序流程圖該界面為用戶顯示兩個(gè)可選擇站點(diǎn)的下拉菜單，而可能導(dǎo)致輸出錯(cuò)誤的的原因是由于用戶會(huì)在選擇站點(diǎn)的過程中，誤點(diǎn)導(dǎo)致起始站與目的站相同。如果出現(xiàn)錯(cuò)誤，程序?qū)棾鲥e(cuò)誤信息的窗口提示用戶選擇的站點(diǎn)有誤，并提示用戶重新選擇。2.1.2線路尋找算法當(dāng)用戶啟動(dòng)程序并選擇起始站與目的站，兩個(gè)站點(diǎn)名稱作為String類型參數(shù)傳入程序，并分別創(chuàng)建對(duì)象，線路查找的算法為從起始站找到相鄰的站點(diǎn)，將所查找相鄰的站點(diǎn)名稱與起始的目的站作為參數(shù)，利用遞歸得到所經(jīng)過的線路。圖2-2從起始站遍歷圖2-3使用遞歸遍歷起始站作為from，目的站作為to，首先查找from所在的線路，并將所得的所有線路在列表中循環(huán)，從第一個(gè)線路中，獲得該線路包含的所有站點(diǎn)，同時(shí)，將當(dāng)前訪問的線路分別存入兩個(gè)不同的容器中，其中一個(gè)作為儲(chǔ)存已訪問線路的容器，另一個(gè)作為所要輸出方案的線路。圖2-4使用容器儲(chǔ)存線路并在之前的循環(huán)中再次嵌套一層循環(huán)，在內(nèi)層的循環(huán)中，所遍歷到的站點(diǎn)作為起始站，目的站保持不變，通過遞歸的方法再次遍歷未遍歷的站點(diǎn)，與線路相同，已訪問的站點(diǎn)儲(chǔ)存在另一個(gè)容器中。圖2-5儲(chǔ)存已訪問站點(diǎn)直到from與to相同。如果存在from與to相同，將儲(chǔ)存輸出結(jié)果的容器輸出，并刪除該容器最后一位元素。儲(chǔ)存已訪問站點(diǎn)或路線容器中，最后一個(gè)元素設(shè)為false。2.1.3最優(yōu)價(jià)格最優(yōu)價(jià)格利用數(shù)學(xué)歸納法，即假設(shè)已知從線1到線i-1所要花費(fèi)的價(jià)格，從而推算出從線1到線i所花費(fèi)的價(jià)格。由于存在某些線路之間可以使用聯(lián)票，這就導(dǎo)致在使用數(shù)學(xué)歸納法的過程中，可能會(huì)出現(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計(jì)算最優(yōu)價(jià)格三種情況在尋找線路的算法中，當(dāng)完成一次線路的查找之后，將儲(chǔ)存線路的容器作為參數(shù)傳入計(jì)算價(jià)格的方法中，通過上述的算法得出價(jià)格并復(fù)制給最終作為結(jié)果輸出價(jià)格的變量optimal_price暫時(shí)儲(chǔ)存，但尋找線路的算法再次完成一次線路的查找，重復(fù)上述過程，通過與上一次得出的價(jià)格做比較，把較小的賦值給optimal_price，直至沒有線路方案?jìng)魅朐摲椒ā?.1.4地鐵換乘相關(guān)信息儲(chǔ)存及提取對(duì)于上面描述的兩個(gè)算法中，涉及到線路名，站點(diǎn)名的查找，為了方便程序的運(yùn)行，分別對(duì)于不同的數(shù)據(jù)使用不同的容器儲(chǔ)存。圖2-7線路和站點(diǎn)的儲(chǔ)存線路與站點(diǎn)的儲(chǔ)存使用Map容器，將線路或站點(diǎn)的名稱作為鍵，所對(duì)應(yīng)的對(duì)象作為值與鍵相對(duì)應(yīng)。除此之外，在儲(chǔ)存線路價(jià)格通過使用二維數(shù)組儲(chǔ)存線路之間的價(jià)格，所以需要將每個(gè)線路添加一一對(duì)應(yīng)的序號(hào)，使用兩個(gè)不同的Map容器分別儲(chǔ)存線路名稱及其所對(duì)應(yīng)的序號(hào)，和站點(diǎn)名稱與其所對(duì)應(yīng)的序號(hào)。圖2-8線路（站點(diǎn)）的序號(hào)分配儲(chǔ)存線路價(jià)格所使用的二維數(shù)組的長(zhǎng)度和寬度為線路數(shù)量大小，在初始化數(shù)組下，儲(chǔ)存的數(shù)值均為0，通過對(duì)price.txt的讀取，單條線路在二維數(shù)組中的數(shù)值為該線路價(jià)格，如果兩條線路之間可以使用聯(lián)票，則儲(chǔ)存為聯(lián)票的價(jià)格，其他為初始值。圖2-9二維數(shù)組儲(chǔ)存價(jià)格第3章程序功能的實(shí)現(xiàn)3.1主類功能的實(shí)現(xiàn)主類功能的運(yùn)行結(jié)果為：圖3-1程序界面主窗口分為上下兩部分（up_panel，down_panel），上面部分為程序輸入信息，下面部分為用戶輸出信息。up_panel分為三部分為別為from_panel，表示起始站相關(guān)信息；mid_panel，表示為分隔，是界面顯示更加條理分明；to_panel，表示目的地相關(guān)信息。相關(guān)代碼為：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程序主要功能的實(shí)現(xiàn)3.2.1判斷用戶輸入是否規(guī)范當(dāng)用戶選擇站點(diǎn)時(shí)，起始站與目的站相同，則程序需提示用戶，對(duì)程序的輸入有誤，并重新選擇站點(diǎn)。Stringfrom=_stations_menu_from.getSelectedItem(); Stringto=_stations_menu_to.getSelectedItem(); if(from.equals(to)){ error_windowerror=newerror_window(); error.setVisible(true); }該代碼為用戶選擇某一站點(diǎn)是程序作出的相應(yīng)，首先對(duì)于輸入信息判斷，如果有誤，則向用戶提示錯(cuò)誤信息。super("Error"); JTextAreaerror_info=newJTextArea(); error_info.setFont(newFont("Default",Font.PLAIN,15)); error_info.setText("你選擇的起始站與目的地相同，請(qǐng)重新選擇"); 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時(shí)作出的相應(yīng)。如果為false，即用戶輸入無誤，則作出正確的相應(yīng)，輸出最優(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)價(jià)格方案為：\n"+"-"+_optimal+"="+_price);3.2.2獲取線路及價(jià)格信息當(dāng)程序讀取stations.txt內(nèi)容的過程中，首行一定是線路名稱，當(dāng)讀取內(nèi)容為空的時(shí)候，則讀取的下一行內(nèi)容同樣一定是線路名稱，其他情況則為站點(diǎn)名稱。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過程中，內(nèi)容的格式是固定的，均為線路名（聯(lián)票線路）+“”+價(jià)格，由于有些線路之間可以使用線路聯(lián)票，則需對(duì)線路名稱進(jìn)行分割，獲得使用聯(lián)票的兩條線路名，并將相應(yīng)價(jià)格數(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)){ /*到達(dá)終點(diǎn)站*/ calc_optimal_price(route); }首先判斷是否到起始站與目的站相同，如果相同表示到達(dá)目的站，則將所得線路列表傳入計(jì)算價(jià)格的算法中，進(jìn)行最優(yōu)價(jià)格的計(jì)算。elseif(route.size()>_subway_lines.size()){ /*錯(cuò)誤*/ }當(dāng)儲(chǔ)存線路列表的容量大小超過所有線路的數(shù)量，則該線路列表錯(cuò)誤，不進(jìn)行操作。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);以上代碼為線路尋找的代碼，當(dāng)完成一次路線的查找，程序?qū)⑦M(jìn)行一下代碼，首先將上一個(gè)尋找的站點(diǎn)設(shè)為false，結(jié)束內(nèi)層循環(huán)后，將上一個(gè)尋找的線路設(shè)為false，由于在兩個(gè)站點(diǎn)之間，可能存在多個(gè)不同的線路方案，當(dāng)計(jì)算完成一個(gè)線路列表之后，應(yīng)將該中最后一個(gè)元素刪除。 _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計(jì)算最優(yōu)價(jià)格根據(jù)上述計(jì)算最優(yōu)價(jià)格算法，計(jì)算的過程中，會(huì)出現(xiàn)三種情況，分別定義三個(gè)Integer類型的對(duì)象，并初始化為最大值。Integerprice_1=Integer.MAX_VALUE; Integerprice_2=Integer.MAX_VALUE; Integerprice_3=Integer.MAX_VALUE;根據(jù)所得的線路列表分別對(duì)三種情況進(jìn)行判斷，并分別對(duì)三個(gè)Integer對(duì)象進(jìn)行賦值。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)票，不做操作*/ }由于在判斷的過程中，存在三個(gè)Integer對(duì)象其中一個(gè)，或兩個(gè)沒有進(jìn)行賦值，需將初始化值為最大值，如果初始化為，則在判斷三個(gè)量之間大小時(shí)，只能輸出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; }由于兩個(gè)站點(diǎn)之間，可能存在多個(gè)不同的線路方案，則需判斷當(dāng)前線路方案的花費(fèi)與上個(gè)線路方案的花費(fèi)進(jìn)行比較。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章調(diào)試及發(fā)現(xiàn)問題的解決1.如何將線路與站點(diǎn)相互結(jié)合？創(chuàng)建兩個(gè)類分別為線路類與站點(diǎn)類，在線路類中，創(chuàng)建String類對(duì)象儲(chǔ)存線路名稱和List<String>儲(chǔ)存該線路包含站點(diǎn)。在站點(diǎn)類中，創(chuàng)建String對(duì)象儲(chǔ)存站點(diǎn)名稱，List<String>儲(chǔ)存該站點(diǎn)所在線路和boolean變量標(biāo)志該站點(diǎn)是否為換乘站。通過創(chuàng)建兩個(gè)類的實(shí)例對(duì)象，可以從線路獲得相關(guān)站點(diǎn)信息或從站點(diǎn)獲得相關(guān)線路信息。2.如何儲(chǔ)存線路價(jià)格？如果使用一位數(shù)組或者M(jìn)ap容器儲(chǔ)存線路及其對(duì)應(yīng)的價(jià)格，當(dāng)在計(jì)算最優(yōu)價(jià)格時(shí)，需逐一遍歷線路，當(dāng)某一線路可以去前者或后者使用聯(lián)票時(shí)，無法方便的獲得聯(lián)票的價(jià)格。使用二維數(shù)組，長(zhǎng)度與寬度均為線路總數(shù)量。初始值為0，單一的線路值設(shè)為該線路價(jià)格，可以使用聯(lián)票的兩條線路之間的值設(shè)為聯(lián)票的價(jià)格。3.尋找線路時(shí)，可能存在多條線路方案，如何獲得所有可行的方案？每一次尋找線路分為兩層循環(huán)，當(dāng)一條可行線路方案查找的最后，即起始站與目的站相同時(shí)，將該方案經(jīng)過的線