数据结构课设交通咨询系统设计求一元高次多项式加_减_乘

1、北华航天工业学院课程设计报告课程设计报告报告(论文)题目： 数据结构课程设计 作者所在系部： 计算机科学与工程系 作者所在专业： 计算机科学与技术 作者所在班级： 作 者 学 号： 作 者 姓 名： 指导教师姓名： 完 成 时 间 ： 2010 年12月 北华航天工业学院教务处制目 录第一章 问题描述11.1题目内容11.1.1交通咨询系统设计11.1.2求一元高次多项式加、减、乘11.2基本要求11.2.1交通咨询系统设计11.2.2求一元高次多项式加、减、乘11.3 测试数据21.3.1交通咨询系统设计21.3.2求一元高次多项式加、减、乘2第二章 需求分析32.1功能说明32.1.1交通

2、咨询系统设计32.1.2求一元高次多项式加、减、乘32.2输入说明32.2.1交通咨询系统设计32.2.2求一元高次多项式加、减、乘32.3输出说明32.3.1交通咨询系统设计32.3.2求一元高次多项式加、减、乘42.4测试数据42.4.1交通咨询系统设计42.4.2求一元高次多项式加、减、乘4第三章 概要设计53.1抽象数据类型定义53.1.1交通咨询系统设计53.1.2求一元高次多项式加、减、乘53.2程序模块结构63.2.1交通咨询系统设计63.2.2求一元高次多项式加、减、乘7第四章 详细设计84.1定义的数据类型84.1.1交通咨询系统设计84.1.2求一元高次多项式加、减、乘16

3、4.2函数间的调用关系254.2.1交通咨询系统设计254.2.2求一元高次多项式加、减、乘25第五章 调试分析265.1调试过程分析265.1.1交通咨询系统设计265.1.2求一元高次多项式加、减、乘265.2算法的时空分析265.2.1交通咨询系统设计265.2.2求一元高次多项式加、减、乘27第六章 使用说明286.1交通咨询系统设计286.2求一元高次多项式加、减、乘28第七章 测试结果297.1交通咨询系统设计297.2求一元高次多项式加、减、乘31总 结34参考文献35附 录36第一章 问题描述1.1题目内容1.1.1交通咨询系统设计利用图的邻接矩阵表示已知城市之间的里程、时间、

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

5、，将每个子项看成是由系数和指数两部分组成。2输入并创建一元多项式，以链表作为存储结构。3实现两个多项式的相加、相减和相乘运算。4显示多项式，查看运算结果。1.3 测试数据1.3.1交通咨询系统设计第一组测试数据：1. 测试起始城市到其余所有城市的最短路程（以升序排序输出），以北京为例运行结果：北京 到 天津 总里程 137 天津ß北京 (时间： 1 路费： 55)北京 到 呼和浩特 总里程 668 呼和浩特ß北京 (时间： 12 路费：230)北京 到 郑州 总里程 695 郑州ß北京 (时间：13 路费： 250)北京 到 徐州 总里程 811 徐州ß

6、天津ß北京 (时间：6 路费：275)···北京 到 乌鲁木齐 总里程 3705 乌鲁木齐ß兰州ß呼和浩特ß北京 (时间：68 路费：1050)2. 测试起始城市到任一城市的最少路程，以北京到长春为例运行结果：最少路程 1146 北京à天津à沈阳à长春 第二组测试数据：1. 按第一种查询方式查询，输入不存在的城市代号时，以输入z为例运行结果：输入错误请重新输入：1.3.2求一元高次多项式的加、减、乘运算用户输入数据完毕，程序将输出运算结果，以加法为例。输入A：1，1，1，0，0，0B：1，1，-

7、1，0，0，0。输出：2X。第二章 需求分析2.1功能说明2.1.1交通咨询系统设计本程序用以咨询从一个城市到另外所有城市的最短路径并显示出所有路径（按升序排列）和任意两个城市间的最短路径并显示显示最短路径。2.1.2求一元高次多项式的加、减、乘运算本程序用于计算两个系数、指数为实数（分数除外）的一元高次多项式的加、减、乘运算。多项式的系数、指数由用户输入，程序根据用户输入的数据计算并显示相应的运算结果。2.2输入说明2.2.1交通咨询系统设计程序运行后显现提示信息，由用户输入选择内容。程序会自动将其排序合并同类项。程序将自动处理用户的错误选择。2.2.2求一元高次多项式的加、减、乘运算程序运

8、行后显现提示信息，由用户输入多项式并选择运算。程序将自动处理用户的错误选择。2.3输出说明2.3.1交通咨询系统设计用户输入选择内容后，程序将输出咨询结果。例如：测试起始城市到任一城市的最少花费时，以北京到南昌为例输出结果：最少花费 55 北京à天津 若输入不存在的城市代号时，以输入z为例输出结果：输入错误请重新输入：2.3.2求一元高次多项式的加、减、乘运算用户输入数据完毕，程序将输出运算结果，例如：输入A：1，1，1，0，0，0B：1，1，-1，0，0，0。以加法为例会输出2X。2.4测试数据2.4.1交通咨询系统设计测试数据可为任意类型，范围最好在菜单及对照表中的数据。用户输入

9、数据后，将显示信息与实际交通图对照，查看是否一致。2.4.2求一元高次多项式的加、减、乘运算测试数据应为两组实数，用户自己设计多组数据并计算出相应结果，然后把数据输入设计好的程序中，检验输出加、减、乘运算后的结果和用户自己计算的结果是否一致。第三章 概要设计3.1抽象数据类型定义3.1.1交通咨询系统设计ADT MGraph 数据对象：DvexsMAXVexType, vn|enint数据关系：R(vexsvn, en)|vexsvnVexType, vn|enint 基本操作：CreateMGraph(G)操作结果：完成图的创建。Floyd(G, P,int D)操作结果：找任意两城市将的最

10、短路径。FloydTime(G, P,int D)操作结果：找任意两城市间的最短时间。FloydCost(G, P,int D)操作结果：找任意两城市间的的最少花费。Dijkstra (G,P,D)操作结果：找任意两城市间的最短路径。DijkstraTime(G,P,D)操作结果：找任意城市到其余城市的最短时间。DijkstraCost(G,P,D)操作结果：找任意城市到其余城市的最少花费。 ADT MGraph3.1.2求一元高次多项式的加、减、乘运算为实现上程序功能，应以有序链表表示多项式。为此单链表这个抽象数据类型。1单链表的抽象数据类型定义ADT LinkList 数据对象：D=dat

11、a1| data2DataType 数据关系：R=data1Xdata2|data1, data2DataType 基本操作：CreatLinkList (L) 操作结果：创建了一个二维数组。Sort(L)操作结果：是二维数组按第二维变量升序排列CreatLinkList (L1) 操作结果：创建链表L1。CreatLinkList (L2) 操作结果：创建链表L2。Sort(L1) 操作结果：对链表L1排列。Sort(L2) 操作结果：链表L2排列。put_LinkList(L) 初始条件：多项式L已存在。操作结果：输出多项式L。Add(L, L1, L2); 操作结果：两多项式L1，L2相

12、加并存在L中。Sub(L, L1, L2); 操作结果：两多项式L1，L2相减并存在L中。Mul(L, L1, L2); 操作结果：两多项式L1，L2相乘并存在L中。 ADT LinkList3.2程序模块结构3.2.1交通咨询系统设计本程序包括主函数、图和邻接矩阵的单元模块等三个模块。1）主函数模块：2）图的模块实现图的抽象类型的定义；3）邻接矩阵模块实现边的信息的存储定义。两个模块间的调用关系如图3-1所示。 主函数单元模块图的单元模块邻接矩阵单元模块图3-1 模块间的调用关系图3.2.2求一元高次多项式的加、减、乘运算本程序包括主函数、单链表和结点结构的单元模块等三个模块。1）本程序包含

13、主程序模块：2）单链表元模块实现单链表的抽象数据类型；3）结点结构单元模块定义点链表的结点结构。各模块间的调用关系如图3-2示。主函数单元模块单链表单元模块结点结构单元模块图3-1 模块间的调用关系图第四章 详细设计4.1定义的数据类型4.1.1交通咨询系统设计1元素类型typedef structint num;/城市代号char name8;/城市名VertexType; /顶点的类型typedef int EdgeType; /边的类型2图的类型typedef structVertexType vexsMaxVertexNum;/顶点（包含名字，代码）EdgeType edgesMaxV

14、ertexNumMaxVertexNum;/路程EdgeType costMaxVertexNumMaxVertexNum;/花费EdgeType timeMaxVertexNumMaxVertexNum;/时间int vn,en;/边数 顶点数MGraph; /图的存储类型 部分基本操作实现的伪码算法如下：1求任意城市到到其余城市间的最短里程、时间、花费。本处共三次使用迪杰斯特拉算法，以求里程为例void Dijkstra(MGraph &G,int *P,int *D)char v3;cout<<"请输入您所在城市:(a-y)"cin>>

15、v3;while(v3<'a'|v3>'y') cout<<"输入错误请重新输入："<<endl;cin>>v3; /判断输入是否合理int v0=int(v3-'a')+1;/将char型转换为int型int i,v,pre,w;int min;int finalMaxVertexNum; /记录此顶点对应的路径是否最小值for(v=1;v<=G.vn;v+)finalv=0;Dv=G.edgesv0v;Pv0=-1;if(Dv<INFINITY&&

16、 v!=v0)Pv=v0;if(Dv=INFINITY)Pv=-2; /初始化Dv0=0;finalv0=1;for(i=1;i<=G.vn;i+)min=INFINITY;for(w=1;w<=G.vn;w+)if(!finalw)if(Dw<min) v=w;min=Dw;finalv=1;for(w=1;w<=G.vn;w+)if(!finalw&&(min+G.edgesvw<Dw)Dw=min+G.edgesvw;Pw=v; /记录任意点到其余各点的最短路径EdgeType D1MaxVertexNum; /记录排序前DMAX的权值顺序i

17、nt j,k; int flagMaxVertexNum;/记录排序后D变化的下标for(i=1;i<=G.vn;i+)/先初始化为排序前p,D的下标flagi=i;for(i=1;i<=G.vn;i+) /将排序前D中记录的最小权值存入D1中D1i=Di;for(i=1;i<G.vn;i+) for(j=i+1,k=i;j<=G.vn;j+)if(Dj<Dk)k=j;if(k!=i)D0=Dk;Dk=Di;Di=D0;flag0=flagk;flagk=flagi;flagi=flag0;/选择排序将所有路径进行升序排序for(i=1;i<G.vn+1;i

18、+)j=flagi;if(D1j!=0)cout<<"总路程："cout<<D1j<<setw(10)<<G.;int time=0;int cost=0;pre=Pj;while(pre>0)cout<<""<<G.;time=time+G.timeprej;cost=cost+G.costprej;j=pre;pre=Ppre;cout<<" (时间："<<time<<&qu

19、ot; 花费："<<cost<<" )"<<endl;/输出函数cout<<endl;2求任意两城市间的最短里程、最小时间、最少花费。此处共三次使用弗洛伊德算法，以求时间为例void FloydTime(MGraph &G,int PMaxVertexNumMaxVertexNum,int DMaxVertexNumMaxVertexNum) char v3,v4;cout<<"请输入您所在城市:(a-y)"cin>>v3;while(v3<'a

20、9;|v3>'y') cout<<"输入错误请重新输入："<<endl;cin>>v3;/判断输入信息是否合理int a=int(v3-'a')+1;/将char型转换为int型cout<<"请输入您想查询的城市:(a-y)"cin>>v4;while(v4<'a'|v4>'y') cout<<"输入错误请重新输入："<<endl;cin>>v4;/判断输入信

21、息是否合理int b=int(v4-'a')+1; /将char型转换为int型int u,v,w;for(v=1;v<=G.vn;v+)for(w=1;w<=G.vn;w+)Dvw=G.timevw;if(Dvw<MAXCOST)Pvw=w; / 存放vw最短路径上v的后继结点else if(Dvw=MAXCOST)Pvw=MAXCOST;/初始化for(u=1;u<=G.vn;u+)for(v=1;v<=G.vn;v+)for(w=1;w<=G.vn;w+)if(Dvw>Dvu+Duw)Dvw=Dvu+Duw;Pvw=Pvu; /求

22、出最短路径cout<<endl;u=Pab;if(u=MAXCOST)cout<<G.vexs <<"和"<<G.<<"之间无路径"<<endl;elseint cost=0;int s=0;cout<<"最短时间："cout<<Dab<<" "cout<<G.;while(u!=b)cout<<""<<

23、;G.vexs ;cost=cost+G.costua;s=s+G.edgesua;a=u;u=Pub;s=s+G.edgesba;cost=cost+G.costba;cout<<""<<G.vexs <<" "cout<<" (路程："<<s<<" 花费："<<cost<<" )"<<endl;/输出函数cout<<endl;3主函数的伪码算法mai

24、n()int PMaxVertexNum;int DMaxVertexNum;int P1MaxVertexNumMaxVertexNum;int D1MaxVertexNumMaxVertexNum;MGraph G;CreateMGraph(G);char choice;docout<<"交通咨询系统 *主菜单*"<<endl;cout<<"<<<<<<<<<<<<<<<<<<<<<<<&

25、lt;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"<<endl;cout<<"| |"<<endl;cout<<"| 1=>咨询一个城市到另外所有城市的最短路径 |"<<endl;cout<<"| 2=>咨询任意两个城市间的最短路径 |&qu

26、ot;<<endl;cout<<"| 0=>退出系统 |"<<endl;cout<<"| |"<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

27、;>>>>>>>>>>>>"<<endl;cout<<"n请输入您选择的查找方式:"cin>>choice;cout<<endl;switch(choice)case '1':char choice1;docout<<"交通咨询系统 *一个城市到另外所有城市的最短路径*"<<endl;cout<<"<<<<<<<<&l

28、t;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"<<endl;cout<<"| |"<<endl;cout<<"| 1=>所有城市路程 2=>所有城市时间 3=>

29、;城市所有花费 |"<<endl;cout<<"| 0=>返回主菜单 |"<<endl;cout<<"| |"<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>&g

30、t;>>>>>>>>>>>>>>>"<<endl;cout<<"n请输入您选择的查找方式:"cin>>choice1;switch(choice1)case '1':Dijkstra(G,P,D);break;case '2':DijkstraTime(G,P,D);break;case '3':DijkstraCost(G,P,D);break;case '0':cout&l

31、t;<"n您已返回主菜单.n"<<endl;break;default:cout<<"n没有此选项.请重选:"<<endl;break;while(choice1!='0'); ;break;case '2':char choice2;docout<<"交通咨询系统 *咨询任意两个城市间的最短路径 *"<<endl;cout<<"<<<<<<<<<<<

32、<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"<<endl;cout<<"| |"<<endl;cout<<"| 1=>指定城市路程 2=>指定城市时间 3=>指定城市花费 |&

33、quot;<<endl;cout<<"| 0=>返回主菜单 |"<<endl;cout<<"| |"<<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

34、>>>>>>>>>>"<<endl;cout<<"n请输入您选择的查找方式:"cin>>choice2;switch(choice2)case '1':Floyd(G,P1,D1);break;case '2':FloydTime(G,P1,D1);break;case '3':FloydCost(G,P1,D1);break;case '0':cout<<"n您已返回主菜单.n&qu

35、ot;<<endl;break;default:cout<<"n没有此选项.请重选:"<<endl;break;while(choice2!='0'); ;break;case '0':cout<<"您已安全退出系统."<<endl;break;default:cout<<"n没有此选项.请重选:"<<endl;break;while(choice!='0');cout<<"n *欢

36、迎您下次再使用本系统!*"<<endl;return 0;4.1.2求一元高次多项式的加、减、乘运算1元素类型、结点类型和指针类型typedef double DataType;typedef struct NodeDataType data2;/指数DataType data1;/系数struct Node *next;LNode,*LinkList; 部分基本操作实现的伪码算法如下：1合并同类项int A(LinkList &L,double x,double y)LNode *p;int t=0;p=L;while(p)if(p->data2=y)p-

37、>data1=p->data1+x;t=1;p=p->next;return t;/判断是否有同类项，合并同类项，并返回值用以判断是否合并过void CreatLinkList(LinkList &L)LNode *s,*p;L=new LNode;L->next=NULL;double x,y;p=L;cout<<"请输入 系数 幂 "<<endl;cin>>x>>y;while(x!=Flag|y!=Flag) s=new LNode;s->data1=x;s->data2=y;

38、s->next=NULL;p->next=s;p=s;cout<<"请输入 系数 幂 "<<endl; cin>>x>>y;while(A(L,x,y)=1)&&(x!=Flag|y!=Flag)cout<<"请输入 系数 幂 "<<endl;cin>>x>>y; /创建单链表，以flag为结束命令2按幂排序void Sort(LinkList &L)LNode *s,*r,*p,*q;p=L->next;if(L-&

39、gt;next=NULL)return ;while(p->next) q=p->next ;r=L;s=q;if(s->data2>p->data2)while(s->data2<r->next->data2)r=r->next;p->next=q->next;s->next=r->next;r->next=s;else p=p->next;/按data2降序排序3多项式的加法void Add(LinkList &L,LinkList &L1,LinkList &L2)LN

40、ode *p,*q,*s,*s1;p=L1->next;q=L2->next;L=new LNode; L->next=NULL;s1=L;while(q&&p)if(p->data2>q->data2)s=new LNode;s->data1=p->data1;s->data2=p->data2;s1->next=s;s1=s;p=p->next;else if(p->data2<q->data2)s=new LNode;s->data1=q->data1;s->dat

41、a2=q->data2;s1->next=s;s1=s;q=q->next;/将data2较大的结点插入L中elses=new LNode;s->data1=q->data1+p->data1;s->data2=p->data2;s1->next=s;s1=s;q=q->next;p=p->next;/当data2相同时俩个data1相加然后插入L中if(p=NULL)p=q;/p为空时将p指向qwhile(p)s=new LNode;s->data1=p->data1;s->data2=p->data2

42、;s1->next=s;s1=s;p=p->next;s1->next=NULL;/将剩余的结点插入到L4多项式的减法void Sub(LinkList &L,LinkList &L1,LinkList &L2)LNode *p,*q,*s,*s1;p=L1->next;q=L2->next;L=new LNode; L->next=NULL;s1=L;while(q&&p)if(p->data2>q->data2)s=new LNode;s->data1=p->data1;s->d

43、ata2=p->data2;s1->next=s;s1=s;p=p->next;else if(p->data2<q->data2)s=new LNode;s->data1=-q->data1;s->data2=q->data2;s1->next=s;s1=s;q=q->next;/将data2较大的结点插入L中elses=new LNode;s->data1=-q->data1+p->data1;s->data2=p->data2;s1->next=s;s1=s;q=q->nex

44、t;p=p->next;/当data2相同时俩个data1相加然后插入L中if(p=NULL)p=q; p为空时将p指向qwhile(p)s=new LNode;s->data1=p->data1;s->data2=p->data2;s1->next=s;s1=s;p=p->next;s1->next=NULL;/将剩余的结点插入到L5多项式的乘法void Mul(LinkList &L,LinkList &L1,LinkList &L2)LinkList L3;LNode *p,*q,*s,*s3;L=new LNode

45、; L3=new LNode; L->next=NULL;L3->next=NULL;p=L1->next;q=L2->next;s3=L3;while(p)while(q)s=new LNode;s->data1=p->data1*q->data1;s->data2=p->data2+q->data2;s3->next=s;s3=s;q=q->next;q=L2->next;p=p->next;s3->next=NULL;Add(L,L,L3);./调用Add算法，是每次循环的结果相加L=L+L3L3=

46、new LNode; L3->next=NULL;s3=L3;6输出算法void put_LinkList(LinkList &L)LNode *q;if(L->next=NULL)cout<<"该一元多项式为0n"return ;cout<<"多项式为："<<endl;q=L->next;if(q->data1>0)if(q->data2=0)cout<<q->data1;else if(q->data1=1&&q->data2

47、=1)cout<<"X"else if(q->data1=1&&q->data2!=1)cout<<"X"<<q->data2;else if(q->data1!=1&&q->data2=1)cout<<q->data1<<"X"elsecout<<q->data1<<"X"<<q->data2;if(q->data1<0)if(

48、q->data2=0)cout<<q->data1;else if(q->data1=-1&&q->data2=1)cout<<"-X"else if(q->data1=-1&&q->data2!=1)cout<<"-X"<<q->data2;else if(q->data2=1)cout<<q->data1<<"X"elsecout<<q->data1<

49、<"X"<<q->data2;/多项式首相输出算法q=q->next;while(q)if(q->data1>0)if(q->data2=0)cout<<"+"<<q->data1;else if(q->data1=1&&q->data2=1)cout<<"+X"else if(q->data1=1&&q->data2!=1)cout<<"+X"<<

50、;q->data2;else if(q->data1!=1 && q->data2=1)cout<<"+"<<q->data1<<"X"elsecout<<"+"<<q->data1<<"X"<<q->data2;if(q->data1<0)if(q->data2=0)cout<<q->data1;else if(q->data1=-1&a

51、mp;&q->data2=1)cout<<"-X"else if(q->data1=-1&&q->data2!=1)cout<<"-X"<<q->data2;else if(q->data2=1)cout<<q->data1<<"X"elsecout<<q->data1<<"X"<<q->data2;q=q->next;cout<<

52、endl;2主函数的伪码算法void main()LinkList L,L1,L2;/定义链表L,L1,L2。char choice;docout<<" *多项式主菜单* "<<endl;cout<<"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<&l

53、t;<<<<<<<<<<<<<<"<<endl;cout<<"| |"<<endl;cout<<"| 1=>创建多项式A 2=>创建多项式B 3=>多项式相加 |"<<endl;cout<<"| 4=>多项式相减 5=>多项式相乘 0=>退出系统 |"<<endl;cout<<"| |"<

54、;<endl;cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;cout<<"n请输入您的选择:&q

55、uot;cin>>choice;switch(choice)case '1':CreatLinkList(L1);Sort(L1);put_LinkList(L1);break;case '2':CreatLinkList(L2);Sort(L2);put_LinkList(L2);break;case '3':Add(L,L1,L2);put_LinkList(L);break;case '4':Sub(L,L1,L2);put_LinkList(L);break;case '5':Mul(L,L1,

56、L2);put_LinkList(L);break;case '0':cout<<"n您已退出系统.n"<<endl;break;default:cout<<"n没有此选项.请重选:"<<endl;break;while(choice!='0');4.2函数间的调用关系4.2.1交通咨询系统设计函数间的调用关系如图4-1所示。路程时间主函数 从一个城市到所有城市查询 从起始城市到指定城市查询花费路程时间花费图4-1函数间的调用关系4.2.2求一元高次多项式的加、减、乘运算函数

57、间的调用关系如图4-2所示主函数相乘相减创建相加显示图4-2函数间的调用关系第五章 调试分析5.1调试过程分析5.1.1交通咨询系统设计程序中将城市间数据的操作封装在图的邻接矩阵存储类型中，在城市的类型模块中，只须引用图的邻接矩阵操作实现相应的城市查询即可，因而使城市间查询模块的调试比较方便。用两种方式求最短路径时，在初始化记录最短路径的DMAX，PMAX，DMAXMAX，PMAXMAX时要根据自己设定的下标的起始值来赋值，否则在寻找和输出路径的过程中会出现错误；计算相应最短路径的另外两个值时，每次循环都要把记录值赋为零，否则，会累加；在对最短路径进行排序时，要先用另一个数组记录下DMAX，并

58、用数组记录下排序后的下标，否则，输出时会出现找不到前驱的情况，因为排序后DMAX中存放最短路径的顺序与PMAX不能相互对应。 5.1.2求一元高次多项式的加、减、乘运算程序中将指针的操作封装在链表的类型中，在多项式的类型模块中，只须引用链表的操作实现相应的多项式运算即可，从而使多项式模块的调试比较方便。在多项式进行加、减运算后将结果赋给L时，如果直接把L1或L2中的某一项赋给L，不可把指针直接赋给L，这样会改变L1或L2中的多项式，应该把指针指向的系数和指数分别赋给L；输出函数要考虑输出的多项式的系数为0、1、-1，指数为0、1的情况。总之，每一个小细节都要考虑到，这样才能让程序少出错误。5.2算法的时空分析5.2.1交通咨询系统设计由于各城市间的关系用途的邻接矩阵存储，CreateMGraph操作需要对边进行相应的操作时间复杂度为O（n2），用Dijkstra和Floyd求最短路径的时间复杂度均为O（n3），其中n是城市的个数。5.2.2求一元高次多项式的加、减、乘运算多项式采用带头结点的有序单链表存储，其中n为链表的长度，Add，Sub、Mul等操作时间复杂度均为O（m+n），m，n为两链表的长度，Sort用冒泡排序时间复杂度为O（n2），Print等操作的时间复杂度均为O（n）。第六章 使用说明6