交通系统系统设计及一元高次多项式的加减乘运算_课程设计报告(编辑修改稿)

交通系统系统设计及一元高次多项式的加减乘运算_课程设计报告(编辑修改稿)内容摘要：

83。 34 北华航天工业学院课程报告 4 第 1 章 问题描述 题目内容 交通咨询系统设计 设计一个交通咨询系统，能让旅客咨询从任一城市顶点到另一城市顶点之间的最短路径（里程）或最低 花费或最少时间等问题。 对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。 一元高次多项式的加、减、乘运算 用链表表示一元高次多项式，实现两个多项式的加、减、乘运算。 基本要求 交通咨询系统设计 1．创建图的存储结构使用邻接矩阵。 2．查询分为两类。 一类是能让旅客咨询从一个城市 到另外所有城市的 最短路径（要求使用迪杰斯特拉算法），显示出所有路径，按升序排列。 第二类是任意两个城市间的最短路径（要求使用弗洛伊德算法），显示最短路径。 3．按给定交通地图完成以上功能。 一元高次多项式的加、减、乘运算 ，将每个子项看成是由系数和指数两部分组成。 ，以链表作为存储结构。 、相减和相乘运算。 ，查看运算结果。 ： 创建 加法 减法 乘法 显示 退出 北华航天工业学院课程报告 5 测试数据 交通咨询系统设计 任意输入 所需要查找的一个 或两个城市，然后查找最短距离、最少花费和最短时间。 一元高次多项式的加、减、乘运算 2X^4+3X^4=5X^4 6X^3+3X^5=6X^3+3X^5 7X^9*4X^5=28X^45 北华航天工业学院课程报告 6 第 2 章 需求分析 功能说明 交通咨询系统设计 查询分为两类。 一类是能让旅客咨询从一个城市 到另外所有城市的 最短路径，显示出所有路径，按升序排列。 第二类是任意两个城市间的最短路径，显示最短路径。 一元高次多项式的加、减、乘运算 描述多项式时，将每个子项看成是由系数和指数两部分组成。 输入并创建一元多项式，以链表作为存储结构。 实现两个多项式的相加、相减和相乘运算。 显示多项式，查看运算结果。 输入说明 交通咨询 系统设计 用户根据自己所需要的利用交通系统查询的功能自己进行查询。 一元高次多项式的加、减、乘运算 程序运行后显现提示信息，由用户输入两个多项式，由用户自行选择加减乘功能进行运算。 输出说明 交通咨询系统设计 根据用户不同的选择功能输出不同。 北华航天工业学院课程报告 7 一元高次多项式的加、减、乘运算 用户输入数据完毕，程序将输出运算结果。 测试数据 交通咨询系统设计 用户自行选择功能，可进行按序号查找和按名称查找。 一元高次多项式的加、减、乘运算 测试数据应 为两组整数，正负都没有关系。 北华航天工业学院课程报告 8 第 3 章 概要设计 抽象数据类型定义 交通咨询系统设计 为实现上程序功能，应 创建图的存储结构并使用邻接矩阵 表示集合。 1． 建图的存储结构 typedef struct { int vexs[max]。 string name[max]。 int cost[max][max]。 int distance[max][max]。 int time[max][max]。 int vnm,enm。 }mgraph。 2． 邻接矩阵 void create(mgraph amp。 g,int n,int e) { int i,j。 =n。 =e。 for(i=1。 i=。 i++) [i]=i。 //对应数组下标即为城市代号 for(i=1。 i=。 i++) {//初始化 for(j=1。 j=。 j++) { 北华航天工业学院课程报告 9 if(i==j) { [i][j]=0。 [i][j]=0。 [i][j]=0。 } else { [i][j]=MAX。 [i][j]=MAX。 [i][j]=MAX。 } } } 一元高次多项式的加、减、乘运算 链表和数组的使用，下面是链表的定义 ： typedef struct{ double xishu。 double zhishu。 }LNode,*LinkList。 数组的定义： LNode a[2],b[3]。 程序模块结构 交通咨询系统设计 本程序包含 主程序、 最少花费、最短距离、最少时间模块和迪杰斯特拉算法、弗洛伊德算法 模块等 三个模块。 最少花费、最短距离、最少时间模 块实现 判断两城市之间信息。 迪杰斯特拉算法、弗洛伊德算法 模块实现 两城市之间的各种信息的具体计算。 三个模块间的调用关系如图 31 所示。 北华航天工业学院课程报告 10 图 31 模块间的调用关系 图 一元高次多项式的加、减、乘运算 本程序包含主程序、加减乘运算函数模块 显示模块三个模块。 加减乘模块 是用来计算一元高次多项式的加减乘的核心模块。 显示模块是用来显示计算结果的模块。 三个模块间的调用关系如图 32 所示。 图 32 模块间的调用关系图 北华航天工业学院课程报告 11 第 4 章 详细设计 定义的数据类型 交通咨询系统设计 1．元素类型、结点类型和指针类型 typedef struct { int vexs[max]。 string name[max]。 int cost[max][max]。 int distance[max][max]。 int time[max][max]。 int vnm,enm。 }mgraph。 st。 2． 图和邻接矩阵的定义 //图的有关信息 typedef struct { int sign。 int len。 int hour。 int spend。 }save。 //存放城市代号和距离 void create(mgraph amp。 g,int n,int e) { int i,j。 =n。 =e。 北华航天工业学院课程报告 12 for(i=1。 i=。 i++) [i]=i。 //对应数组下标即为 城市代号 for(i=1。 i=。 i++) {//初始化 for(j=1。 j=。 j++) { if(i==j) { [i][j]=0。 [i][j]=0。 [i][j]=0。 } else { [i][j]=MAX。 [i][j]=MAX。 [i][j]=MAX。 } } } 3． 迪杰斯特拉算法 和弗洛伊德算法 利用 迪杰斯特拉算法和弗洛伊德算法计算最少花费、最短距离、最少时间。 其 基本操作的伪码算法如下： 迪杰斯特拉一城至诸城最少花费 void shortestcost(mgraph g,int v0) { int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。 v=。 v++) 北华航天工业学院课程报告 13 { final[v]=0。 d[v].spend=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].spendMAXamp。 amp。 v!=v0) p[v]=v0。 if(d[v].spend==MAX) p[v]=2。 } d[v0].spend=0。 final[v0]=1。 for(i=2。 i=。 i++) { min=MAX。 for(w=1。 w=。 w++) if(!final[w]) if(d[w].spendmin) { v=w。 min=d[w].spend。 } final[v]=1。 for(w=1。 w=。 w++) {//修改 d 中存放的最短距离和前驱结点 if(!final[w]amp。 amp。 (min+[v][w]d[w].spend)) { d[w].spend=min+[v][w]。 d[w].sign=w。 p[w]=v。 } } } //选择排序法 for(i=1。 i。 i++) 北华航天工业学院课程报告 14 { k=i。 for(j=i+1。 j=。 j++) if(d[j].spendd[k].spend) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].spend。 d[k].spend=d[i].spend。 d[i].spend=m。 } } for(i=1。 i=。 i++) { if(d[i].sign!=v0) { cout 从 setw(2)v0到 setw(2)d[i].sign城市最少花费：setw(4)d[i].spend。 cout 所经过的路径：。 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } coutendl。 } } //迪杰斯特拉一城至诸城最短时间 void shortesttime(mgraph g,int v0) { 北华航天工业学院课程报告 15 int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。 v=。 v++) { final[v]=0。 d[v].hour=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].hourMAXamp。 amp。 v!=v0) p[v]=v0。 if(d[v].hour==MAX) p[v]=2。 } d[v0].hour=0。 final[v0]=1。 for(i=2。 i=。 i++) { min=MAX。 for(w=1。 w=。 w++) if(!final[w]) if(d[w].hourmin) { v=w。 min=d[w].hour。 } final[v]=1。 for(w=1。 w=。 w++) {//修改 d 中存放的最短距离和前驱结点 if(!final[w]amp。 amp。 (min+[v][w]d[w].hour)) { d[w].hour=min+[v][w]。 d[w].sign=w。 北华航天工业学院课程报告 16 p[w]=v。 } } } //选择排序法 for(i=1。 i。 i++) { k=i。 for(j=i+1。 j=。 j++) if(d[j].hourd[k].hour) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].hour。 d[k].hour=d[i].hour。 d[i].hour=m。 } } for(i=1。 i=。 i++) { if(d[i].sign!=v0) { cout 从 setw(2)v0到 setw(2)d[i].sign城市最短时 间：setw(2)d[i].hour。 cout 所经过的路径：。 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } 北华航天工业学院课程报告 17 coutendl。 } } } //迪杰斯特拉算法 void shortestdistance(mgraph g,int v0) { int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。 v=。 v++) { final[v]=0。 d[v].len=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].lenMAXamp。 amp。 v!=v0) p[v]=v0。 if(d[v].len==MAX) p[v]=2。 } d[v0].len=0。 final[v0]=1。 for(i=2。 i=。 i++) { min=MAX。 for(w=1。 w=。 w++) if(!final[w]) if(d[w].lenmin) { v=w。 min=d[w].len。 } 北华航天工业学院课程报告 18 final[v]=1。 for(w=1。 w=。 w++) {//修改 d 中存放的最短距离和前驱结点 if(!final[w]amp。 amp。 (min+[v][w]d[w].len)) { d[w].len=min+[v][w]。 d[w].sign=w。 p[w]=v。 } } } //选择排序法 for(i=1。 i。 i++) { k=i。 for(j=i+1。 j=。 j++) if(d[j].lend[k].len) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].len。 d[k].len=d[i].len。 d[i].len=m。 } } for(i=1。 i=。 i++) { if(d[i].sign!=v0) { cout 从 setw(2)v0到 setw(2)d[i].sign城市最短路径：setw(4)d[i].len。 cout 所经过的路径：。 北华航天工业学院课程报告 19 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } coutendl。 } } } 4．主函数的伪码算法 void main() { mgraph 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：南昌endl。 cout 14：南宁 15：上海 16：沈阳 17：深圳 18：天津 19：武汉endl。 cout 20：乌鲁木齐 21：西安 22：西宁 23：徐州 24：郑州 25：株州endl。 cout ++。