Java课程设计报告-地铁换乘

地铁换乘第1章课题概述本次Java课程设计的题目是设计并实现地铁换乘中换乘路线以及最优价格。1.1课题的目的为解决如今交通拥挤的状况，多数城市建设多条地体线路，由于地铁线路的交错以及站点的繁多，通过编写程序对用户所在的起始站以及用户所要到达的目的地两站点进行分析，通过算法的计算，得出最优价格的乘车方案提供给用户，以便用户在挑选乘车方案时提供给用户方便。1.2课题的要求1.2.1输入输出的要求（1）程序运行后向用户显示一个地铁换乘的主窗口，在窗口内显示两个可选择下来菜单，为用户提供选择，而不是让用户进行输入站点。（2）用户对起始站以及目的地选择完毕后，在窗口下端的文本区域将显示提供给用户的最优价格方案。（3）对于输出方案的格式中，线路名称用“-”分开，如果两个线路之间使用联票，则联票之间用“，”连接，并在两端加括号，与普通票价区分。（4）当多个方案有相同的最小花费，输出任意一个方案即可。1.2.2程序实现的功能要求（1）对于测试程序过程中，测试数据与实例数据不同，并能够输出正确方案以及输出的各式正确。（2）当用户选择当前起始站，以及目的地，窗口能够输出方案。第2章概要设计2.1程序的主体结构及主要功能的算法2.1.1窗口主程序主体的程序为用户提供一个可供选择站点的GUI界面，方便了用户的输入。对于程序的主体的流程，如图：图2-1主程序流程图该界面为用户显示两个可选择站点的下拉菜单，而可能导致输出错误的的原因是由于用户会在选择站点的过程中，误点导致起始站与目的站相同。如果出现错误，程序将弹出错误信息的窗口提示用户选择的站点有误，并提示用户重新选择。2.1.2线路寻找算法当用户启动程序并选择起始站与目的站，两个站点名称作为String类型参数传入程序，并分别创建对象，线路查找的算法为从起始站找到相邻的站点，将所查找相邻的站点名称与起始的目的站作为参数，利用递归得到所经过的线路。图2-2从起始站遍历图2-3使用递归遍历起始站作为from，目的站作为to，首先查找from所在的线路，并将所得的所有线路在列表中循环，从第一个线路中，获得该线路包含的所有站点，同时，将当前访问的线路分别存入两个不同的容器中，其中一个作为储存已访问线路的容器，另一个作为所要输出方案的线路。图2-4使用容器储存线路并在之前的循环中再次嵌套一层循环，在内层的循环中，所遍历到的站点作为起始站，目的站保持不变，通过递归的方法再次遍历未遍历的站点，与线路相同，已访问的站点储存在另一个容器中。图2-5储存已访问站点直到from与to相同。如果存在from与to相同，将储存输出结果的容器输出，并删除该容器最后一位元素。储存已访问站点或路线容器中，最后一个元素设为false。2.1.3最优价格最优价格利用数学归纳法，即假设已知从线1到线i-1所要花费的价格，从而推算出从线1到线i所花费的价格。由于存在某些线路之间可以使用联票，这就导致在使用数学归纳法的过程中，可能会出现3种情况。1）线i-1与线i之间没有联票；2）线i-2与线i-1之间没有联票，线i-1与线i之间有联票；3）线i-2与线i-1之间有联票，线i-1与线i之间有联票；图2-6计算最优价格三种情况在寻找线路的算法中，当完成一次线路的查找之后，将储存线路的容器作为参数传入计算价格的方法中，通过上述的算法得出价格并复制给最终作为结果输出价格的变量optimal_price暂时储存，但寻找线路的算法再次完成一次线路的查找，重复上述过程，通过与上一次得出的价格做比较，把较小的赋值给optimal_price，直至没有线路方案传入该方法。2.1.4地铁换乘相关信息储存及提取对于上面描述的两个算法中，涉及到线路名，站点名的查找，为了方便程序的运行，分别对于不同的数据使用不同的容器储存。图2-7线路和站点的储存线路与站点的储存使用Map容器，将线路或站点的名称作为键，所对应的对象作为值与键相对应。除此之外，在储存线路价格通过使用二维数组储存线路之间的价格，所以需要将每个线路添加一一对应的序号，使用两个不同的Map容器分别储存线路名称及其所对应的序号，和站点名称与其所对应的序号。图2-8线路（站点）的序号分配储存线路价格所使用的二维数组的长度和宽度为线路数量大小，在初始化数组下，储存的数值均为0，通过对price.txt的读取，单条线路在二维数组中的数值为该线路价格，如果两条线路之间可以使用联票，则储存为联票的价格，其他为初始值。图2-9二维数组储存价格第3章程序功能的实现3.1主类功能的实现主类功能的运行结果为：图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(){ /*创建新的窗口*/ 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程序主要功能的实现3.2.1判断用户输入是否规范当用户选择站点时，起始站与目的站相同，则程序需提示用户，对程序的输入有误，并重新选择站点。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，即用户输入无误，则作出正确的相应，输出最优方案。Enginee1=newEngine(); e1.initialize(); e1.get_optimal_route(from,to); String_optimal=e1._optimal; int_price=e1._price; _optimal_price.setText("最优价格方案为：\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过程中，内容的格式是固定的，均为线路名（联票线路）+“”+价格，由于有些线路之间可以使用线路联票，则需对线路名称进行分割，获得使用联票的两条线路名，并将相应价格数据存入二维数组中。line_price=read_data.split(""); /*非联票*/ if(line_price[0].indexOf(",")==-1){ i=j=_line_index_mapper.get(line_price[0]); _price_matrix[i][j]=Integer.parseInt(line_price[1]); } /*联票*/ 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获取路线列表根据寻找线路算法，代码为if(from.equals(to)){ /*到达终点站*/ calc_optimal_price(route); }首先判断是否到起始站与目的站相同，如果相同表示到达目的站，则将所得线路列表传入计算价格的算法中，进行最优价格的计算。elseif(route.size()>_subway_lines.size()){ /*错误*/ }当储存线路列表的容量大小超过所有线路的数量，则该线路列表错误，不进行操作。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){ /*已经遍历过的线路不再遍历*/ 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，结束内层循环后，将上一个寻找的线路设为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计算最优价格根据上述计算最优价格算法，计算的过程中，会出现三种情况，分别定义三个Integer类型的对象，并初始化为最大值。Integerprice_1=Integer.MAX_VALUE; Integerprice_2=Integer.MAX_VALUE; Integerprice_3=Integer.MAX_VALUE;根据所得的线路列表分别对三种情况进行判断，并分别对三个Integer对象进行赋值。if(_price_matrix[subway_index_i_1][subway_index_i]!=0){ /*i-1与i有联票*/ if(is_join==false){ /*i-1没有与i-2联票，且i-1与i有联票*/ 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联票，需要判断i-1与i-2联好，还是与i联好*/ 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没有联票，不做操作*/ }由于在判断的过程中，存在三个Integer对象其中一个，或两个没有进行赋值，需将初始化值为最大值，如果初始化为，则在判断三个量之间大小时，只能输出0。if(price_1<price_2&&price_1<price_3){ /*方案1最优*/ optimal_price=price_1; optimal_route.add(subway_line._name); is_join=false; }elseif(price_2<price_1&&price_2<price_3){ /*方案2最优*/ 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最优*/ 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章调试及发现问题的解决1.如何将线路与站点相互结合？创建两个类分别为线路类与站点类，在线路类中，创建String类对象储存线路名称和List<String>储存该线路包含站点。在站点类中，创建String对象储存站点名称，List<String>储存该站点所在线路和boolean变量标志该站点是否为换乘站。通过创建两个类的实例对象，可以从线路获得相关站点信息或从站点获得相关线路信息。2.如何储存线路价格？如果使用一位数组或者Map容器储存线路及其对应的价格，当在计算最优价格时，需逐一遍历线路，当某一线路可以去前者或后者使用联票时，无法方便的获得联票的价格。使用二维数组，长度与宽度均为线路总数量。初始值为0，单一的线路值设为该线路价格，可以使用联票的两条线路之间的值设为联票的价格。3.寻找线路时，可能存在多条线路方案，如何获得所有可行的方案？每一次寻找线路分为两层循环，当一条可行线路方案查找的最后，即起始站与目的站相同时，将该方案经过的线