C课程报告毕业论文.doc

北华航天工业学院课程报告C+课程报告毕业论文目 录第1章 问题描述11.1题目内容11.1.1交通咨询系统设计11.1.2一元高次多项式的加、减、乘运算11.1.3十进制四则运算计算器11.2基本要求11.2.1交通咨询系统设计11.2.2一元高次多项式的加、减、乘运算11.2.3十进制四则运算计算器21.3 测试数据21.3.1交通咨询系统设计21.3.2一元高次多项式的加、减、乘运算31.3.3十进制四则运算计算器3第2章 需求分析42.1功能说明42.1.1交通咨询系统设计。42.1.2一元高次多项式的加、减、乘运算42.1.3十进制四则运算计算器42.2输入说明42.2.1交通咨询系统设计42.2.2一元高次多项式的加、减、乘运算52.2.3十进制四则运算计算器52.3输出说明52.3.1交通咨询系统设计52.3.2一元高次多项式的加、减、乘运算52.3.3十进制四则运算计算器52.4测试数据52.4.1交通咨询系统设计52.4.2一元高次多项式的加、减、乘运算52.4.3十进制四则运算计算器6第3章 概要设计73.1抽象数据类型定义73.1.1交通咨询系统设计73.1.2一元高次多项式的加、减、乘运算73.1.3十进制四则运算计算器83.2程序模块结构93.2.1交通咨询系统设计93.2.2一元高次多项式的加、减、乘运算93.2.3十进制四则运算计算器10第4章 详细设计114.1定义的数据类型114.1.1交通咨询系统设计114.1.2一元高次多项式的加、减、乘运算264.1.3十进制四则运算计算器354.2函数间的调用关系484.2.1交通咨询系统设计484.2.2一元高次多项式的加、减、乘运算484.2.3十进制四则运算计算器49第5章 调试分析505.1调试过程分析505.1.1交通咨询系统设计505.1.2一元高次多项式的加、减、乘运算505.1.3十进制四则运算计算器505.2算法的时空分析505.2.1交通咨询系统设计505.2.2一元高次多项式的加、减、乘运算515.2.3十进制四则运算计算器51第6章 使用说明526.1交通咨询系统设计526.2一元高次多项式的加、减、乘运算526.3十进制四则运算计算器52第7章 测试结果537.1交通咨询系统设计537.2一元高次多项式的加、减、乘运算577.3十进制四则运算计算器60总 结63参考文献64第1章 问题描述1.1题目内容1.1.1交通咨询系统设计设计一个交通咨询系统，能让旅客咨询从任一城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。1.1.2一元高次多项式的加、减、乘运算用链表表示一元高次多项式，实现两个多项式的加、减、乘运算。1.1.3十进制四则运算计算器将算术表达式用二叉树表示，并对其进行遍历，求出后缀表达式后，计算后缀表达的值。1.2基本要求1.2.1交通咨询系统设计1创建图的存储结构使用邻接矩阵。2查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径（要求使用迪杰斯特拉算法），显示出所有路径，按升序排列。第二类是任意两个城市间的最短路径（要求使用弗洛伊德算法），显示最短路径。1.2.2一元高次多项式的加、减、乘运算1描述多项式时，将每个子项看成是由系数和指数两部分组成。2输入并创建一元多项式，以链表作为存储结构。3实现两个多项式的相加、相减和相乘运算。4显示多项式，查看运算结果。 5用户界面包括以下功能： 加法 加法 减法 乘法 显示 退出1.2.3十进制四则运算计算器1表达式以中缀字符串形式给出，以#作为结束符。2二叉树以二叉链表形式存储。3给出二叉树先序、中序和后序三种遍历的结点序列，所有遍历用非递归算法实现。4求后缀表达式的值用栈实现。5算术表达式中包含的运算有加、减、乘、除。1.3 测试数据1.3.1交通咨询系统设计相关数据为下表所示起点终点花费时间路程起点终点花费时间路程起点终点花费时间路程191045032189221107022161020210567610837024114580230126682023190115110232501369523229533490175511371722220567417152401370415316073971519033051772224226330219672022701584229380231100692251163961121010607111374225562431020902112423011672182318545341824145340922142321265112142601482512241054367524225116754122151062251626514140城市名称和代号对照：0：北京1：长春 2：成都 3：大连 4：福州 5：广州 6：贵阳 7：哈尔滨 8：呼和浩特9：昆明 10：兰州 11：柳州 12：南昌 13：南宁 14：上海 15：沈阳 16：深圳 17：天津 18：武汉 19：乌鲁木齐 20：西安 21：西宁 22：徐州 23：郑州 24：株州运行结果：求从城市代号为2到其他相应城市按路程求的相应路径为：0-23-20-2; 1-15-17-0-23-20-2; 2;3-15-17-0-23-20-2; 4-12-24-6-2; 5-24-6-2; 6-2; 7-1-15-17-0-23-20-2; 8-10-20-2; 9-2; 10-20-2; 11-6-2;12-24-6-2; 13-11-6-2; 14-22-23-20-2; 15-17-0-23-20-2; 16-5-24-6-2; 17-0-23-20-2; 18-23-20-2; 19-10-20-2; 20-2; 21-10-20-2; 22-23-20-2; 23-20-2; 24-6-2; 求按路程从2到23的最短路径为： 23-20-21.3.2一元高次多项式的加、减、乘运算原来两个多项式为：L1=2x3+3x-3+5x4 L2=2x3+3x-3+5x4运算结果：两个多项式相加：L1+L2=4x3+6x-3+10x4两个多项式相减：L1-L2=0两个多项式相乘：L1*L2=4x6+12+20x7+9x-6+30x1+25x81.3.3十进制四则运算计算器表达式为：2+3-（4+3）*7运算结果为：先序遍历为：-+23*+437中序遍历为：2+3-4+3*7后序遍历为：23+43+7*-运算结果为：-44 第2章 需求分析2.1功能说明2.1.1交通咨询系统设计。设计一个交通咨询系统，能让旅客咨询从任一城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。2.1.2一元高次多项式的加、减、乘运算1描述多项式时，将每个子项看成是由系数和指数两部分组成。2输入并创建一元多项式，以链表作为存储结构。3实现两个多项式的相加、相减和相乘运算。4显示多项式，查看运算结果。 5用户界面包括以下功能： 加法 加法 减法 乘法 显示 退出2.1.3十进制四则运算计算器 1表达式以中缀字符串形式给出，以#作为结束符。2二叉树以二叉链表形式存储。3给出二叉树先序、中序和后序三种遍历的结点序列，所有遍历用非递归算法实现。4求后缀表达式的值用栈实现。5算术表达式中包含的运算有加、减、乘、除。2.2输入说明2.2.1交通咨询系统设计程序运行后显现提示信息，由用户选择要实现现功能的代号，创建图时不是由用户输入的而在程序中的一个函数中实现的。2.2.2一元高次多项式的加、减、乘运算程序运行后显现提示信息，由用户输入两个多项式每一项都是先后输入该项的系数、指数和字母，系数和指数是所有的实数，程序会自动合并两个指数相同的项。2.2.3十进制四则运算计算器程序运行后显现提示信息，由用户随便输入一个表达式但每一项的操作数必须在09之间。这个表达式可以有括号。2.3输出说明2.3.1交通咨询系统设计用户输入数据完毕后，程序将输出运算结果。2.3.2一元高次多项式的加、减、乘运算用户输入数据完毕后，程序将输出运算结果。2.3.3十进制四则运算计算器用户输入数据完毕后，程序将输出运算结果。2.4测试数据2.4.1交通咨询系统设计创建的图由程序来实现的，对用户输入的数据没有太多的要求，要想实现什么功能直接输入实现该项功能的代码就行。2.4.2一元高次多项式的加、减、乘运算输入两个多项式每一项的系数和指数可以是所有的实数。2.4.3十进制四则运算计算器用来测试的表达式每一项的操作数必须在09之间。这个表达式可以有括号。第3章 概要设计3.1抽象数据类型定义3.1.1交通咨询系统设计为实现上程序功能，该程序应用图来表示交通的一些信息，图是用邻接矩阵来存储，矩阵中的数据类型是一个结构体，该结构体有三个int数据成员，分别来表示两个城市间的路程、花费和时间。1图的邻接矩阵的抽象数据类型定义typedef structVertexType vexsMaxVertexNum;/用来存储图的顶点信息即城市的代号EdgeType edgesMaxVertexNumMaxVertexNum;/用来存储边的一些信息包括路程时间和花费int n,e;/表示顶点数和和边数MGragh;2矩阵中的抽象数据类型定义typedef structint mil;/路程int cost;/花费int time;/时间EdgeType;3.1.2一元高次多项式的加、减、乘运算为实现上程序功能，用一个链表来表示一元高次多项式，该链表的结点中的data是一个结构体类型，该结构体包括三个数据成员分别是多项式的每一项的系数和指数和字母。1.链表的抽象数据类型定义typedef structint xidata;int zhidata;char ch;DataType;/结点中的data数据类型typedef struct NodeDataType data;struct Node *next;LNode,*LinkList;/结点的定义void Creat_double(LinkList &L)/构造一个链表3.1.3十进制四则运算计算器为实现上程序的功能，应用了两个顺序栈，二叉树用二叉链表来存储，这两个顺序栈一个栈用来存储指向存储运算符的结点的指针，一个栈用来存储指向操作数的结点的指针，用这两个栈来实现把一个表达式转换成一个二叉树。1.二叉树抽象数据类型定义typedef struct BiTNodeDataType1 data;/ typedef char DataType1;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void GreatBiTree(BiTree &T)/用二叉链表创建一个二叉树的函数2.栈的抽象数据类型定义typedef structDataType datamaxsize;/该数据类型为指向一个二叉树的结点的指针int top;SeqStack;/栈的定义void Init_SeqStack(SeqStack &s)/栈的初始化函数int Push_SeqStack(SeqStack &s,DataType x)/进栈函数int Pop_SeqStack(SeqStack &s,DataType &x)/出栈函数void GetTop_SeqStack(SeqStack s,DataType &a)/读取栈顶元素函数int Empty_SeqStack(SeqStack s)/判断栈是否为空的函数3.2程序模块结构3.2.1交通咨询系统设计本程序包含主函数、调用能实现各功能函数的函数和实现各功能的函数等三个模块。调用能实现各功能函数的函数模块是用来调用一些函数这些函数是能实现一些功能的函数。实现各功能的函数模块有分别按路程、时间、花费来分别计算从一个城市到所有城市的最短路径和两个城市的最短路径。三个模块间的调用关系如图3-1所示。主函数调用能实现各功能函数的函数实现各功能的函数图3-1 模块间的调用关系图3.2.2一元高次多项式的加、减、乘运算本程序包含主函数、调用能实现各功能函数的函数和实现各功能的函数等三个模块。调用能实现各功能函数的函数模块是用来调用一些函数这些函数能实现一定的功能。实现各功能的函数模块有创建一个链表来存储一个多项式的函数、有实现两个多项式加减乘的函数。有显示多项式的函数。主函数调用能实现各功能函数的函数实现各功能的函数 图3-2 模块间的调用关系图3.2.3十进制四则运算计算器本程序包含主函数、调用能实现各功能函数的函数和实现各功能的函数等三个模块。调用能实现各功能函数的函数模块是用来调用一些函数这些函数能实现一定的功能。实现各功能的函数模块有把表达式创建成一个二叉树的函数和实现二叉树的先序、中序和后序的非递归遍历的函数和用二叉树的后序遍历来计算表达式值的函数。主函数调用能实现各功能函数的函数实现各功能的函数 图3-3 模块间的调用关系图第4章 详细设计4.1定义的数据类型4.1.1交通咨询系统设计1图存储类型的定义#define MaxVertexNum 30typedef int VertexType;typedef structint mil;int cost;int time;EdgeType;typedef structVertexType vexsMaxVertexNum;EdgeType edgesMaxVertexNumMaxVertexNum;int n,e;MGragh;2创建图的函数的伪码算法在创建图时，一些数据不是用户输入的而是程序中已经给定的。void Create_MGragh(MGragh &G)int i,j;G.n=25;G.e=30;for(i=0;iG.n;i+)G.vexsi=i;for(i=0;iG.n;i+)for(j=0;jG.n;j+)G.=maxnum;G.edgesij.cost=maxnum;G.edgesij.time=maxnum;G.=G.=1892;G.edges1910.cost=G.edges1019.cost=450;G.edges1910.time=G.edges1019.time=32;G.=G.=1145;G.edges108.cost=G.edges810.cost=370;G.edges108.time=G.edges810.time=24;G.=G.=668;G.edges80.cost=G.edges08.cost=230;G.edges80.time=G.edges08.time=12;G.=G.=137;G.edges017.cost=G.edges170.cost=55;G.edges017.time=G.edges170.time=1;G.=G.=704;G.edges1715.cost=G.edges1517.cost=240;G.edges1715.time=G.edges1517.time=13;G.=G.=305;G.edges151.cost=G.=90;G.edges151.time=G.edges115.time=3;G.=G.=397;G.edges153.cost=G.edges315.cost=160;G.edges153.time=G.edges315.time=7;G.=G.=242;G.edges17.cost=G.edges71.cost=72;G.edges17.time=G.edges71.time=2;G.=G.=216;G.edges2110.cost=G.edges1021.cost=70;G.edges2110.time=G.edges1021.time=2;G.=G.=676;G.edges2010.cost=G.edges1020.cost=210;G.edges2010.time=G.edges1020.time=5;G.=G.=511;G.edges2320.cost=G.edges2023.cost=190;G.edges2320.time=G.edges2023.time=11;G.=G.=695;G.edges230.cost=G.edges023.cost=250;G.edges230.time=G.edges023.time=13;G.=G.=349;G.edges2322.cost=G.edges2223.cost=95;G.edges2322.time=G.edges2223.time=3;G.=G.=674;G.edges2217.cost=G.edges1722.cost=220;G.edges2217.time=G.edges1722.time=5;G.=G.=651;G.edges2214.cost=G.edges1422.cost=232;G.edges2214.time=G.edges1422.time=12;G.=G.=534;G.edges2318.cost=G.edges1823.cost=185;G.edges2318.time=G.edges1823.time=4;G.=G.=842;G.edges220.cost=G.edges202.cost=270;G.edges220.time=G.edges202.time=15;G.=G.=1100;G.edges29.cost=G.edges92.cost=380;G.edges29.time=G.edges92.time=23;G.=G.=967;G.edges26.cost=G.edges62.cost=330;G.edges26.time=G.edges62.time=21;G.=G.=409;G.edges1824.cost=G.edges2418.cost=145;G.edges1824.time=G.edges2418.time=3;G.=G.=825;G.edges1412.cost=G.edges1214.cost=260;G.edges1412.time=G.edges1214.time=14;G.=G.=639;G.edges96.cost=G.edges69.cost=225;G.edges96.time=G.edges69.time=11;G.=G.=902;G.edges624.cost=G.edges246.cost=310;G.edges624.time=G.edges246.time=20;G.=G.=367;G.edges2412.cost=G.edges1224.cost=105;G.edges2412.time=G.edges1224.time=4;G.=G.=622;G.edges124.cost=G.edges412.cost=215;G.edges124.time=G.edges412.time=10;G.=G.=607;G.edges611.cost=G.edges116.cost=210;G.edges611.time=G.edges116.time=10;G.=G.=672;G.edges2411.cost=G.edges1124.cost=230;G.edges2411.time=G.edges1124.time=11;G.=G.=675;G.edges245.cost=G.edges524.cost=225;G.edges245.time=G.edges524.time=11;G.=G.=255;G.edges1311.cost=G.edges1113.cost=74;G.edges1311.time=G.edges1113.time=2;G.=G.=17;G.edges516.cost=G.edges165.cost=265;G.edges516.time=G.edges165.time=14;cout创建成功endl;3能实现一定功能的函数的伪码算法void milshortestpath1(MGragh G,int v1)/按路程求从一个城市到另外所有城市的最短路径int i,v,pre,w,pMaxVertexNum,DMaxVertexNum;int min;int finalMaxVertexNum;for(v=0;vG.n;v+)finalv=0;Dv=G.;pv1=-1;if(Dv!=maxnum & v!=v1)pv=v1;if(Dv=maxnum)pv=-2;Dv1=0;finalv1=1;for(i=1;iG.n;i+)min=maxnum;for(w=0;wG.n;w+)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;wG.n;w+)if(!finalw & (min+G.Dw)Dw=min+G.;pw=v;cout输出按路程求从v1到其他相应城市的最短路径endl;for(i=0;iG.n;i+)cout=0)cout-pre;pre=ppre;coutendl;void costshortestpath1(MGragh G,int v1) /按花费求从一个城市到另外所有城市的最短路径int i,v,pre,w,pMaxVertexNum,DMaxVertexNum;int min;int finalMaxVertexNum;for(v=0;vG.n;+v)finalv=0;Dv=G.edgesv1v.cost;pv1=-1;if(Dv!=maxnum & v!=v1)pv=v1;if(Dv=maxnum)pv=-2;Dv1=0;finalv1=1;for(i=1;iG.n;+i)min=maxnum;for(w=0;wG.n;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;wG.n;+w)if(!finalw & (min+G.edgesvw.costDw)Dw=min+G.edgesvw.cost;pw=v;cout输出按花费求从v1到其他相应城市的最短路径endl;for(i=0;iG.n;i+)cout=0)cout-pre;pre=ppre;coutendl;void timeshortestpath1(MGragh G,int v1)/按时间求从一个城市到另外所有城市的最短路径int i,v,pre,w,pMaxVertexNum,DMaxVertexNum;int min;int finalMaxVertexNum;for(v=0;vG.n;v+)finalv=0;Dv=G.edgesv1v.time;pv1=-1;if(Dv!=maxnum & v!=v1)pv=v1;if(Dv=maxnum)pv=-2;Dv1=0;finalv1=1;for(i=1;iG.n;i+)min=maxnum;for(w=0;wG.n;w+)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;wG.n;w+)if(!finalw & (min+G.edgesvw.timeDw)Dw=min+G.edgesvw.time;pw=v;cout输出按时间求从v1到其他相应城市的最短路径endl;for(i=0;iG.n;i+)cout=0)cout-pre;pre=ppre;coutendl;void milshortestpath2(MGragh G,int v,int w)/按路程求任意两个城市间的最短路径int i,j,u,pre;int DMaxVertexNumMaxVertexNum,pMaxVertexNumMaxVertexNum;for(i=0;iG.n;i+)for(j=0;jG.n;j+)Dij=G.;if(Dij2000)pij=i;elseif(i!=j)pij=-2;elsepij=-1;for(u=0;uG.n;u+)for(i=0;iG.n;i+)for(j=0;jG.n;j+)if(Diu+DujDij)Dij=Diu+Duj;pij=u;pre=pvw;cout输出按路程求从v到w的最短路径endl;coutw;while(pre!=v)cout-pre;pre=pvpre;cout-vendl;void costshortestpath2(MGragh G,int v,int w)/按花费求任意两个城市间的最短路径int i,j,u,pre;int DMaxVertexNumMaxVertexNum,pMaxVertexNumMaxVertexNum;for(i=0;iG.n;i+)for(j=0;jG.n;j+)Dij=G.edgesij.cost;if(Dijmaxnum)pij=i;elseif(i!=j)pij=-2;elsepij=-1;for(u=0;uG.n;u+)for(i=0;iG.n;i+)for(j=0;jG.n;j+)if(Diu+DujDij)Dij=Diu+Duj;pij=u;pre=pvw;cout输出花费求从v到w的最短路径endl;coutw;while(pre!=v)cout-pre;pre=pvpre;cout-vendl;void timeshortestpath2(MGragh G,int v,int w)/按时间求任意两个城市间的最短路径int i,j,u,pre;int DMaxVertexNumMaxVertexNum,pMaxVertexNumMaxVertexNum;for(i=0;iG.n;i+)for(j=0;jG.n;j+)Dij=G.edgesij.time;if(Dijmaxnum)pij=i;elseif(i!=j)pij=-2;elsepij=-1;for(u=0;uG.n;u+)for(i=0;iG.n;i+)for(j=0;jG.n;j+)if(Diu+DujDij)Dij=Diu+Duj;pij=u;pre=pvw;cout输出时间求从v到w的最短路径endl;coutw;while(pre!=v)cout-pre;pre=pvpre;cout-vendl;void shortestpath1(MGragh G,int v)int n;cout$endl;cout$ 1.按路程来计算 $endl;cout$ 2.铵花费来计算 $endl;cout$ 3.按时间来计算 $endl;cout$ 4.返回上一级 $endl;cout$endl;cout请输入代码n;if(n=1)milshortestpath1(G,v);if(n=2)costshortestpath1(G,v);if(n=3)timeshortestpath1(G,v);if(n=4)void shortestpath1a(MGragh G)int v;cout$endl;cout$ 0.北京 1.长春 2.成都 3.大连 4.福州 $endl;cout$ 5.广州 6.贵阳 7.哈尔滨 8.呼和浩特 9.昆明 $endl;cout$ 10.兰州 11.柳州 12.南昌 13.南宁 14.上海 $endl;cout$ 15.沈阳 16.深圳 17.天津 18.武汉19.乌鲁木齐 $endl;cout$ 20.西安 21.西宁 22.徐州 23.郑州 24.株州 $endl; cout$ 25.返回最初的界面 $endl;cout$endl;cout请输入所要求的城市的代码：v;if(v=24)shortestpath1(G,v);shortestpath1a(G);elsevoid shortestpath2(MGragh G,int v,int w)int n;cout$endl;cout$ 1.按路程来计算 $endl;cout$ 2.铵花费来计算 $endl;cout$