《交通系统系统设计及一元高次多项式的加减乘运算课程设计报告》由会员分享,可在线阅读,更多相关《交通系统系统设计及一元高次多项式的加减乘运算课程设计报告(69页珍藏版)》请在金锄头文库上搜索。
1、数据结构课程设计报告报告(论文)题目:交通系统系统设计及一元 高次多项式的加减乘运算 作者所在系部: 计算机系 作者所在专业: 计算机科学与技术 作者所在班级: B12511 作 者 学 号: 20124051117 作 者 姓 名: 王硕 指导教师姓名: 斯庆巴拉 完 成 时 间 : 2013年12月25日 北华航天工业学院教务处制目 录第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一元高次多项
2、式的加、减、乘运算5第2章 需求分析62.1功能说明62.1.1交通咨询系统设计62.1.2一元高次多项式的加、减、乘运算62.2输入说明62.2.1交通咨询系统设计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章 详细设
3、计114.1定义的数据类型114.1.1交通咨询系统设计111元素类型、结点类型和指针类型114.1.2一元高次多项式的加、减、乘运算201元素类型、结点类型和指针类型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交
4、通咨询系统设计277.2一元高次多项式的加、减、乘运算29参考文献33附 录34第1章 问题描述1.1 题目内容1.1.1 交通咨询系统设计设计一个交通咨询系统,能让旅客咨询从任一城市顶点到另一城市顶点之间的最短路径(里程)或最低花费或最少时间等问题。对于不同咨询要求,可输入城市间的路程或所需时间或所需费用。1.1.2 一元高次多项式的加、减、乘运算用链表表示一元高次多项式,实现两个多项式的加、减、乘运算。1.2 基本要求1.2.1 交通咨询系统设计1创建图的存储结构使用邻接矩阵。2查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径(要求使用迪杰斯特拉算法),显示出所有路径,按
5、升序排列。第二类是任意两个城市间的最短路径(要求使用弗洛伊德算法),显示最短路径。3按给定交通地图完成以上功能。1.2.2一元高次多项式的加、减、乘运算1.描述多项式时,将每个子项看成是由系数和指数两部分组成。2.输入并创建一元多项式,以链表作为存储结构。3.实现两个多项式的相加、相减和相乘运算。4.显示多项式,查看运算结果。5.用户界面包括以下功能:创建 加法 减法 乘法 显示 退出1.3 测试数据1.3.1 交通咨询系统设计 任意输入所需要查找的一个或两个城市,然后查找最短距离、最少花费和最短时间。1.3.2 一元高次多项式的加、减、乘运算2X4+3X4=5X46X3+3X5=6X3+3X
6、57X9*4X5=28X45 第2章 需求分析2.1 功能说明2.1.1 交通咨询系统设计查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径,显示出所有路径,按升序排列。第二类是任意两个城市间的最短路径,显示最短路径。2.1.2 一元高次多项式的加、减、乘运算描述多项式时,将每个子项看成是由系数和指数两部分组成。输入并创建一元多项式,以链表作为存储结构。实现两个多项式的相加、相减和相乘运算。显示多项式,查看运算结果。2.2 输入说明2.2.1 交通咨询系统设计用户根据自己所需要的利用交通系统查询的功能自己进行查询。2.2.2 一元高次多项式的加、减、乘运算程序运行后显现提示信息
7、,由用户输入两个多项式,由用户自行选择加减乘功能进行运算。2.3 输出说明2.3.1 交通咨询系统设计根据用户不同的选择功能输出不同。2.3.2 一元高次多项式的加、减、乘运算用户输入数据完毕,程序将输出运算结果。2.4 测试数据2.4.1 交通咨询系统设计用户自行选择功能,可进行按序号查找和按名称查找。2.4.2 一元高次多项式的加、减、乘运算测试数据应为两组整数,正负都没有关系。第3章 概要设计3.1 抽象数据类型定义3.1.1 交通咨询系统设计为实现上程序功能,应创建图的存储结构并使用邻接矩阵表示集合。1建图的存储结构typedef structint vexsmax; string n
8、amemax; int costmaxmax;int distancemaxmax;int timemaxmax; int vnm,enm; mgraph; 2邻接矩阵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=M
9、AX; g.costij=MAX;g.timeij=MAX; 3.1.2 一元高次多项式的加、减、乘运算链表和数组的使用,下面是链表的定义:typedef structdouble xishu;double zhishu;LNode,*LinkList;数组的定义:LNode a2,b3;3.2 程序模块结构3.2.1 交通咨询系统设计本程序包含主程序、最少花费、最短距离、最少时间模块和迪杰斯特拉算法、弗洛伊德算法模块等三个模块。最少花费、最短距离、最少时间模块实现判断两城市之间信息。迪杰斯特拉算法、弗洛伊德算法模块实现两城市之间的各种信息的具体计算。三个模块间的调用关系如图3-1所示。图3-
10、1 模块间的调用关系图3.2.2 一元高次多项式的加、减、乘运算本程序包含主程序、加减乘运算函数模块显示模块三个模块。加减乘模块是用来计算一元高次多项式的加减乘的核心模块。显示模块是用来显示计算结果的模块。三个模块间的调用关系如图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;
11、2图和邻接矩阵的定义/图的有关信息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=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
12、=MAX; g.costij=MAX;g.timeij=MAX; 3迪杰斯特拉算法和弗洛伊德算法利用迪杰斯特拉算法和弗洛伊德算法计算最少花费、最短距离、最少时间。其基本操作的伪码算法如下:迪杰斯特拉一城至诸城最少花费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.spendMAX&v!=v0) pv=v0; if(dv.spend=MAX) pv=-2; dv0.spend=0; finalv0=-1; for(i=2;i=g.vnm;i+) min=MAX; for(w=1;w=g.vnm;w+) if(!finalw) if(dw.spendmin) v=w; min=dw.spend; finalv=1; for(w=1;w=g.vnm;w+)