交通系统系统设计及一元高次多项式的加减乘运算课程设计报告1

1、北华航天工业学院课程报告数据结构课程设计报告报告(论文)题目：交通系统系统设计及一元 高次多项式的加减乘运算 作者所在系部： 计算机系 作者所在专业： 计算机科学与技术 目 录第1章 问题描述41.1题目内容41.1.1交通咨询系统设计41.1.2一元高次多项式的加、减、乘运算41.2基本要求51.2.1交通咨询系统设计51.2.2一元高次多项式的加、减、乘运算51.3 测试数据51.3.1交通咨询系统设计51.3.2一元高次多项式的加、减、乘运算5第2章 需求分析62.1功能说明62.1.1交通咨询系统设计62.1.2一元高次多项式的加、减、乘运算62.2输入说明62.2.1交通咨询系统设计

2、62.2.2一元高次多项式的加、减、乘运算62.3输出说明62.3.1交通咨询系统设计62.3.2一元高次多项式的加、减、乘运算72.4测试数据72.4.1交通咨询系统设计72.4.2一元高次多项式的加、减、乘运算7第3章 概要设计83.1抽象数据类型定义83.1.1交通咨询系统设计83.1.2一元高次多项式的加、减、乘运算93.2程序模块结构93.2.1交通咨询系统设计93.2.2一元高次多项式的加、减、乘运算10第4章 详细设计114.1定义的数据类型114.1.1交通咨询系统设计111元素类型、结点类型和指针类型114.1.2一元高次多项式的加、减、乘运算201元素类型、结点类型和指针类

3、型204.2函数间的调用关系234.2.1交通咨询系统设计234.2.2一元高次多项式的加、减、乘运算24第5章 调试分析255.1调试过程分析255.1.1交通咨询系统设计255.1.2一元高次多项式的加、减、乘运算255.2算法的时空分析255.2.1交通咨询系统设计255.2.2一元高次多项式的加、减、乘运算25第6章 使用说明266.1交通咨询系统设计266.2一元高次多项式的加、减、乘运算26第7章 测试结果277.1交通咨询系统设计277.2一元高次多项式的加、减、乘运算29参考文献33附 录34第1章 问题描述1.1 题目内容1.1.1 交通咨询系统设计设计一个交通咨询系统，能让

4、旅客咨询从任一城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。1.1.2 一元高次多项式的加、减、乘运算用链表表示一元高次多项式，实现两个多项式的加、减、乘运算。1.2 基本要求1.2.1 交通咨询系统设计1创建图的存储结构使用邻接矩阵。2查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径（要求使用迪杰斯特拉算法），显示出所有路径，按升序排列。第二类是任意两个城市间的最短路径（要求使用弗洛伊德算法），显示最短路径。3按给定交通地图完成以上功能。1.2.2一元高次多项式的加、减、乘运算1.描述多项式

5、时，将每个子项看成是由系数和指数两部分组成。2.输入并创建一元多项式，以链表作为存储结构。3.实现两个多项式的相加、相减和相乘运算。4.显示多项式，查看运算结果。5.用户界面包括以下功能：创建 加法 减法 乘法 显示 退出1.3 测试数据1.3.1 交通咨询系统设计 任意输入所需要查找的一个或两个城市，然后查找最短距离、最少花费和最短时间。1.3.2 一元高次多项式的加、减、乘运算2x4+3x4=5x46x3+3x5=6x3+3x57x9*4x5=28x45 第2章 需求分析2.1 功能说明2.1.1 交通咨询系统设计查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径，显示出所

6、有路径，按升序排列。第二类是任意两个城市间的最短路径，显示最短路径。2.1.2 一元高次多项式的加、减、乘运算描述多项式时，将每个子项看成是由系数和指数两部分组成。输入并创建一元多项式，以链表作为存储结构。实现两个多项式的相加、相减和相乘运算。显示多项式，查看运算结果。2.2 输入说明2.2.1 交通咨询系统设计用户根据自己所需要的利用交通系统查询的功能自己进行查询。2.2.2 一元高次多项式的加、减、乘运算程序运行后显现提示信息，由用户输入两个多项式，由用户自行选择加减乘功能进行运算。2.3 输出说明2.3.1 交通咨询系统设计根据用户不同的选择功能输出不同。2.3.2 一元高次多项式的加、

7、减、乘运算用户输入数据完毕，程序将输出运算结果。2.4 测试数据2.4.1 交通咨询系统设计用户自行选择功能，可进行按序号查找和按名称查找。2.4.2 一元高次多项式的加、减、乘运算测试数据应为两组整数，正负都没有关系。第3章 概要设计3.1 抽象数据类型定义3.1.1 交通咨询系统设计为实现上程序功能，应创建图的存储结构并使用邻接矩阵表示集合。1建图的存储结构typedef structint vexsmax; string namemax; int costmaxmax;int distancemaxmax;int timemaxmax; int vnm,enm; mgraph; 2邻接矩

8、阵void create(mgraph &g,int n,int e) int i,j; g.vnm=n; g.enm=e; for(i=1;i<=g.vnm;i+)g.vexsi=i; /对应数组下标即为城市代号for(i=1;i<=g.vnm;i+) /初始化for(j=1;j<=g.vnm;j+) if(i=j) g.distanceij=0; g.costij=0; g.timeij=0; else g.distanceij=max; g.costij=max;g.timeij=max; 3.1.2 一元高次多项式的加、减、乘运算链表和数组的使用，下面是链表的

9、定义：typedef structdouble xishu;double zhishu;lnode,*linklist;数组的定义：lnode a2,b3;3.2 程序模块结构3.2.1 交通咨询系统设计本程序包含主程序、最少花费、最短距离、最少时间模块和迪杰斯特拉算法、弗洛伊德算法模块等三个模块。最少花费、最短距离、最少时间模块实现判断两城市之间信息。迪杰斯特拉算法、弗洛伊德算法模块实现两城市之间的各种信息的具体计算。三个模块间的调用关系如图3-1所示。图3-1 模块间的调用关系图3.2.2 一元高次多项式的加、减、乘运算本程序包含主程序、加减乘运算函数模块显示模块三个模块。加减乘模块是用来

10、计算一元高次多项式的加减乘的核心模块。显示模块是用来显示计算结果的模块。三个模块间的调用关系如图3-2所示。图3-2 模块间的调用关系图第4章 详细设计4.1 定义的数据类型4.1.1 交通咨询系统设计1元素类型、结点类型和指针类型typedef structint vexsmax; string namemax; int costmaxmax;int distancemaxmax;int timemaxmax; int vnm,enm; mgraph; st;2图和邻接矩阵的定义/图的有关信息typedef struct int sign; int len; int hour;int spe

11、nd;save; /存放城市代号和距离void create(mgraph &g,int n,int e) int i,j; g.vnm=n; g.enm=e; for(i=1;i<=g.vnm;i+)g.vexsi=i; /对应数组下标即为城市代号for(i=1;i<=g.vnm;i+) /初始化for(j=1;j<=g.vnm;j+) if(i=j) g.distanceij=0; g.costij=0; g.timeij=0; else g.distanceij=max; g.costij=max;g.timeij=max; 3迪杰斯特拉算法和弗洛伊德算法利用迪

12、杰斯特拉算法和弗洛伊德算法计算最少花费、最短距离、最少时间。其基本操作的伪码算法如下：迪杰斯特拉一城至诸城最少花费void shortestcost(mgraph g,int v0) int i,v,pre,w,min,k,j; int finalmax; int pmax; save dmax; int m,n; for(v=1;v<=g.vnm;v+) finalv=0;dv.spend=g.costv0v; dv.sign=v; pv0=-1; if(dv.spend<max&&v!=v0) pv=v0; if(dv.spend=max) pv=-2; dv0

13、.spend=0; finalv0=-1; for(i=2;i<=g.vnm;i+) min=max; for(w=1;w<=g.vnm;w+) if(!finalw) if(dw.spend<min) v=w; min=dw.spend; finalv=1; for(w=1;w<=g.vnm;w+) /修改d中存放的最短距离和前驱结点if(!finalw&&(min+g.costvw<dw.spend) dw.spend=min+g.costvw; dw.sign=w; pw=v; /选择排序法for(i=1;i<g.vnm;i+) k=i

14、; for(j=i+1;j<=g.vnm;j+) if(dj.spend<dk.spend) k=j; if(k!=i) n=dk.sign;dk.sign=di.sign;di.sign=n; m=dk.spend;dk.spend=di.spend;di.spend=m; for(i=1;i<=g.vnm;i+) if(di.sign!=v0) cout<<" 从"<<setw(2)<<v0<<"到"<<setw(2)<<di.sign<<"

15、;城市最少花费："<<setw(4)<<di.spend<<" " cout<<" 所经过的路径：" cout<<di.sign; pre=pdi.sign;while(pre>0) cout<<"<-"<<pre; pre=ppre; cout<<endl; /迪杰斯特拉一城至诸城最短时间void shortesttime(mgraph g,int v0) int i,v,pre,w,min,

16、k,j; int finalmax; int pmax; save dmax; int m,n; for(v=1;v<=g.vnm;v+) finalv=0;dv.hour=g.timev0v; dv.sign=v; pv0=-1; if(dv.hour<max&&v!=v0) pv=v0; if(dv.hour=max) pv=-2; dv0.hour=0; finalv0=-1; for(i=2;i<=g.vnm;i+) min=max; for(w=1;w<=g.vnm;w+) if(!finalw) if(dw.hour<min) v=w;

17、 min=dw.hour; finalv=1; for(w=1;w<=g.vnm;w+) /修改d中存放的最短距离和前驱结点if(!finalw&&(min+g.timevw<dw.hour) dw.hour=min+g.timevw; dw.sign=w; pw=v; /选择排序法for(i=1;i<g.vnm;i+) k=i; for(j=i+1;j<=g.vnm;j+) if(dj.hour<dk.hour) k=j; if(k!=i) n=dk.sign;dk.sign=di.sign;di.sign=n; m=dk.hour;dk.hou

18、r=di.hour;di.hour=m; for(i=1;i<=g.vnm;i+) if(di.sign!=v0) cout<<" 从"<<setw(2)<<v0<<"到"<<setw(2)<<di.sign<<"城市最短时间："<<setw(2)<<di.hour<<" " cout<<" 所经过的路径：" cout<<di.sign

19、; pre=pdi.sign;while(pre>0) cout<<"<-"<<pre; pre=ppre; cout<<endl; /迪杰斯特拉算法void shortestdistance(mgraph g,int v0) int i,v,pre,w,min,k,j; int finalmax; int pmax; save dmax; int m,n; for(v=1;v<=g.vnm;v+) finalv=0;dv.len=g.distancev0v; dv.sign=v; pv0=-1; if(dv

20、.len<max&&v!=v0) pv=v0; if(dv.len=max) pv=-2; dv0.len=0; finalv0=-1; for(i=2;i<=g.vnm;i+) min=max; for(w=1;w<=g.vnm;w+) if(!finalw) if(dw.len<min) v=w; min=dw.len; finalv=1; for(w=1;w<=g.vnm;w+) /修改d中存放的最短距离和前驱结点if(!finalw&&(min+g.distancevw<dw.len) dw.len=min+g.dis

21、tancevw; dw.sign=w; pw=v; /选择排序法for(i=1;i<g.vnm;i+) k=i; for(j=i+1;j<=g.vnm;j+) if(dj.len<dk.len) k=j; if(k!=i) n=dk.sign;dk.sign=di.sign;di.sign=n; m=dk.len;dk.len=di.len;di.len=m; for(i=1;i<=g.vnm;i+) if(di.sign!=v0) cout<<" 从"<<setw(2)<<v0<<"到&qu

22、ot;<<setw(2)<<di.sign<<"城市最短路径："<<setw(4)<<di.len<<" " cout<<" 所经过的路径：" cout<<di.sign; pre=pdi.sign;while(pre>0) cout<<"<-"<<pre; pre=ppre; cout<<endl; 4主函数的伪码算法void main() mgr

23、aph g; create(g,25,30); int num; string name; do cout<<" -交通咨询系统- "<<endl; cout<<" +城市名称及代码+ "<<endl; cout<<" 1 ：北京 2 ：长春 3 ：成都 4 ：大连 5 ：福州 6 ：广州 7 ：贵阳"<<endl; cout<<" 8 ：哈尔滨 9 ：呼和浩特 10：昆明 11：兰州 12：柳州 13：南昌"<<end

24、l; cout<<" 14：南宁 15：上海 16：沈阳 17：深圳 18：天津 19：武汉"<<endl; cout<<" 20：乌鲁木齐 21：西安 22：西宁 23：徐州 24：郑州 25：株州"<<endl; cout<<" +"<<endl; cout<<endl; cout<<" * 1一城至诸城 2任意两城 3退出系统*"<<endl; cout<<" 请选择："

25、 cin>>num; switch(num) case 1: onecity(g); break; case 2: twocity(g); break; case 3: cout<<" 退出系统成功！"<<endl;break; default: cout<<" 无此选项！请重新输入："<<endl; break; while(num!=3);return; 4.1.2 一元高次多项式的加、减、乘运算1元素类型、结点类型和指针类型typedef structdouble xishu;double

26、 zhishu;lnode,*linklist;lnode a2,b3;2.加减乘的运算下面是加法运算的伪代码：void jia() /加法if(a0.zhishu=a1.zhishu) /如果指数相等，让两系数相加b0.xishu=a0.xishu+a1.xishu; / b0.xishu是两系数之和if(a0.zhishu=0&&a1.zhishu=0)if(a0.xishu=0&&a1.xishu=0)cout<<"0"<<endl;if(a0.xishu=0&&a1.xishu!=0)cout&

27、lt;<a1.xishu<<endl;if(a0.xishu!=0&&a1.xishu=0)cout<<a0.xishu<<endl;if(a0.xishu!=0&&a1.xishu!=0) cout<<b0.xishu<<endl;if(a0.zhishu!=0&&a1.zhishu!=0)if(a0.xishu=0&&a1.xishu=0)cout<<"0"<<endl;if(a0.xishu=0&&a

28、1.xishu!=0)cout<<a1.xishu<<"x"<<a1.zhishu<<endl;if(a0.xishu!=0&&a1.xishu=0)cout<<a0.xishu<<"x"<<a0.zhishu<<endl;if(a0.xishu!=0&&a1.xishu!=0) cout<<b0.xishu<<"x"<<a0.zhishu<<endl;if(a

29、0.zhishu!=a1.zhishu) /指数不等if(a0.zhishu=0&&a1.zhishu!=0)if(a0.xishu=0&&a1.xishu=0)cout<<"0"<<endl;if(a0.xishu=0&&a1.xishu!=0)cout<<a1.xishu<<"x"<<a1.zhishu<<endl;if(a0.xishu!=0&&a1.xishu=0)cout<<a0.xishu<

30、<endl;if(a0.xishu!=0&&a1.xishu!=0) cout<<a0.xishu<<"+"<<a1.xishu<<"x"<<a1.zhishu<<endl;if(a1.zhishu=0&&a0.zhishu!=0)if(a0.xishu=0&&a1.xishu=0)cout<<"0"<<endl;if(a0.xishu=0&&a1.xishu!=0)co

31、ut<<a1.xishu<<endl;if(a0.xishu!=0&&a1.xishu=0)cout<<a0.xishu<<"x"<<a0.zhishu<<endl;if(a0.xishu!=0&&a1.xishu!=0) cout<<a0.xishu<<"x"<<a0.zhishu<<"+"<<a1.xishu<<endl;if(a0.zhishu!=0&am

32、p;&a1.zhishu!=0)if(a0.xishu=0&&a1.xishu=0)cout<<"0"<<endl;if(a0.xishu=0&&a1.xishu!=0)cout<<a1.xishu<<"x"<<a1.zhishu<<endl;if(a0.xishu!=0&&a1.xishu=0)cout<<a0.xishu<<"x"<<a0.zhishu<<e

33、ndl;if(a0.xishu!=0&&a1.xishu!=0) cout<<a0.xishu<<"x"<<a0.zhishu<<"+"<<a1.xishu<<"x"<<a1.zhishu<<endl;3. 主函数的伪代码：void main()lnode l;int d;cout<<" 欢迎使用一元高次多项式的加、减、乘运算系统"<<endl;cout<<"

34、 请先创建之后进行其他操作："<<endl<<endl;for(d=1;d!=0;) cout<<" "<<endl; cout<<" 1创建 "<<endl; cout<<" 2加法 "<<endl; cout<<" 3减法 "<<endl; cout<<" 4乘法 "<<endl; cout<<" 5显示 "

35、<<endl; cout<<" 0退出 "<<endl; cout<<" "<<endl; cout<<" 请选择您所需要的服务："<<endl<<endl; cin>>d; switch(d) case 1:chuangjian(l);break; case 2:jia();break; case 3:jian();break; case 4:cheng();break;case 5:xianshi();break;case

36、0:break;default:cout<<"输入有误，请重新输入："<<endl; cout<<"谢谢使用！"<<endl;4.2 函数间的调用关系4.2.1 交通咨询系统设计函数间的调用关系如图4-1所示。. 图4-1函数间的调用关系4.2.2 一元高次多项式的加、减、乘运算函数间的调用关系如图4-2所示。图4-1函数间的调用关系第5章 调试分析5.1 调试过程分析5.1.1 交通咨询系统设计程序主要是通过各种程序的调用关系运行，只要按着系统提示进行录入就可以了。5.1.2 一元高次多项式的加、减、乘运

37、算程序主要以链表建立一元高次多项式，以数组的形式存储一元高次多项式，只要按着系统提示进行录入就可以了。5.2 算法的时空分析5.2.1 交通咨询系统设计（1）由于有序表采用带头结点的有序单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理，shortestdistance2，shortestcost2，shortesttime2等操作的时间复杂度均为o（n），其中n为链表的长度。（2）构造有序集算法create读入n个元素，逐个用for循环输入元素后，在直接初始化各个路径花费和城市名称，所以时间复杂度也是o（n）。5.2.2 一元高次多项式的加、减、乘运算（1）由于有序表采

38、用带头结点的有序单链表，并增设a2,b3两个数组链表，并且有一个for循环语句，所以时间复杂度是o(n)。（2）构造时的chuangjian直接由手工录入，没有涉及到任何的循环语句，则时间复杂度是o（0）。第6章 使用说明6.1 交通咨询系统设计程序运行后用户根据提，按照自己所需要的查找方式示输入即可。6.2 一元高次多项式的加、减、乘运算程序运行后用户根据提示输入即可。第7章 测试结果7.1 交通咨询系统设计图7-1 交通系统的初始界面图7-2 一城到诸城的最短路径图7-3一城到诸城的最少花费.图7-4 两城之间的最短路径查询 图7-5 两城之间最少花费查询7.2 一元高次多项式的加、减、乘

39、运算 图7-6初始化界面 图7-8 创建界面 图7-9 加法 图7-10 减法 图7-11 乘法图7-12显示加法图7-12显示乘法图7-13 显示减法总 结本设计使用当今较为流行的可视化编程工具通过课程设计不仅学习了vc+，而且技术素质和实践能力有了进一步的提高，对提出问题、思考问题与解决问题有了进一步的深刻认识。同时对软件开发也有了更为全面的了解，通过自己的努力思考、学习研究与指导老师的认真指导，使自己的能力得到了进一步锻炼与提高。通过课程设计不仅学习了数据结构，而且技术素质和实践能力有了进一步的提高，对提出问题、思考问题与解决问题有了进一步的深刻认识。同时对软件开发也有了更为全面的了解，

40、通过自己的努力思考、学习研究与指导老师的认真指导，使自己的能力得到了进一步锻炼与提高。通过这次课设，对于程序中用到的自己又积累了不少编程的经验。程序十进制四则运算计算器应用到了二叉链表的存储方式、栈、中缀后缀表达式、遍历等知识点。由于表达式中存在字符和数字，因此采用了字符和数字的共用体来作为数据的存储方式。对于表达式可能输入有误的问题，程序中加入了许多判断，减少了程序执行错误表达式的情况。参考文献1 王立柱c/c+与数据结构北京：清华大学出版社，2002_22 刘振鹏，张小莉，郑艳娟数据结构（第二版）北京：中国铁道出版社，2007_43 唐宁九数据结构与算法分析成都：四川大学出版社，2006_

41、84 李春葆，金晶数据结构教程北京：清华大学出版社，2006_115 周霭如，林伟健c+程序设计基础北京：电子工业出版社，2003_86 严蔚敏，吴伟民，米宁数据结构题集（c语言版）北京：清华大学出版社，2009.4 7 斯庆巴拉.数据结构（c语言描述）.北京：中国水利水电出版社，2005.附 录交通系统源代码：#include <iostream> #include <iomanip> #include <string> using namespace std; const int max=100; const int max=20000;typedef

42、structint vexsmax; string namemax; int costmaxmax;int distancemaxmax;int timemaxmax; int vnm,enm; mgraph; /图的有关信息typedef struct int sign; int len; int hour;int spend;save; /存放城市代号和距离void create(mgraph &g,int n,int e) int i,j; g.vnm=n; g.enm=e; for(i=1;i<=g.vnm;i+)g.vexsi=i; /对应数组下标即为城市代号for(i

43、=1;i<=g.vnm;i+) /初始化for(j=1;j<=g.vnm;j+) if(i=j) g.distanceij=0; g.costij=0; g.timeij=0; else g.distanceij=max; g.costij=max;g.timeij=max; /对城市名称赋值1="北京" 2="长春" 3="成都" 4="大连" 5="福州" 6="广州" 7=&

44、quot;贵阳"8="哈尔滨" 9="呼和浩特" 10="昆明" 11="兰州"12="柳州" 13="南昌" 14="南宁" 15="上海"16="沈阳" 17="深圳"18="天津" 19="武汉"g.

45、name20="乌鲁木齐" 21="西安" 22="西宁" 23="徐州"24="郑州" 25="株洲" /花费的赋值g.cost2011=450; g.cost1120=450; g.cost911=370; g.cost119=370; g.cost124=250; g.cost241=250; g.cost1823=220; g.cost2318=220; g.cost162=90; g.cost216=90;

46、 g.cost213=270; g.cost321=270; g.cost712=210; g.cost127=210;g.cost1225=230; g.cost2512=230; g.cost2315=232; g.cost1523=232; g.cost625=225; g.cost256=225; g.cost2211=70; g.cost1122=70; g.cost91=230; g.cost19=230; g.cost2423=95; g.cost2324=95; g.cost1816=240; g.cost1618=240; g.cost82=72; g.cost28=72;

47、g.cost103=380; g.cost310=380;g.cost1412=74; g.cost1214=74; g.cost1924=185; g.cost2419=185; g.cost1315=260; g.cost1513=260; g.cost513=215; g.cost135=215; g.cost1121=210; g.cost2111=210; g.cost2421=190; g.cost2124=190; g.cost1225=230; g.cost2512=230; g.cost2315=232; g.cost1523=232; g.cost625=225; g.co

48、st256=225; g.cost2211=70; g.cost1122=70; g.cost91=230; g.cost19=230; g.cost2423=95; g.cost2324=95; g.cost1816=240; g.cost1618=240; g.cost82=72; g.cost28=72; g.cost103=380; g.cost310=380; g.cost1412=74; g.cost1214=74; g.cost1924=185; g.cost2419=185; g.cost1315=260; g.cost1513=260;g.cost513=215; g.cos

49、t135=215; g.cost1121=210; g.cost2111=210; g.cost2421=190; g.cost2124=190; g.cost118=55; g.cost181=55; g.cost164=160; g.cost416=160; g.cost73=330; g.cost37=330; g.cost710=225; g.cost107=225; g.cost725=310; g.cost257=310; g.cost1925=145; g.cost2519=145; g.cost1325=105; g.cost2513=105; g.cost617=265; g.cost176=265; /时间的赋值g