交易机制评价标准与国际比较--上海证券交易所创新实验室报告--学士学位论文.doc

北华航天工业学院课程报告

《数据结构》课程设计报告

报告(论文)题目：交通系统系统设计及一元
高次多项式的加减乘运算
作者所在系部： 计算机系
作者所在专业： 计算机科学与技术

目 录

第1章 问题描述 4
1.1题目内容 4
1.1.1交通咨询系统设计 4
1.1.2一元高次多项式的加、减、乘运算 4
1.2基本要求 5
1.2.1交通咨询系统设计 5
1.2.2一元高次多项式的加、减、乘运算 5
1.3 测试数据 5
1.3.1交通咨询系统设计 5
1.3.2一元高次多项式的加、减、乘运算 5
第2章 需求分析 6
2.1功能说明 6
2.1.1交通咨询系统设计 6
2.1.2一元高次多项式的加、减、乘运算 6
2.2输入说明 6
2.2.1交通咨询系统设计 6
2.2.2一元高次多项式的加、减、乘运算 6
2.3输出说明 6
2.3.1交通咨询系统设计 6
2.3.2一元高次多项式的加、减、乘运算 7
2.4测试数据 7
2.4.1交通咨询系统设计 7
2.4.2一元高次多项式的加、减、乘运算 7
第3章 概要设计 8
3.1抽象数据类型定义 8
3.1.1交通咨询系统设计 8
3.1.2一元高次多项式的加、减、乘运算 9
3.2程序模块结构 9
3.2.1交通咨询系统设计 9
3.2.2一元高次多项式的加、减、乘运算 10
第4章 详细设计 11
4.1定义的数据类型 11
4.1.1交通咨询系统设计 11
1．元素类型、结点类型和指针类型 11
4.1.2一元高次多项式的加、减、乘运算 20
1．元素类型、结点类型和指针类型 20
4.2函数间的调用关系 23
4.2.1交通咨询系统设计 23
4.2.2一元高次多项式的加、减、乘运算 24
第5章 调试分析 25
5.1调试过程分析 25
5.1.1交通咨询系统设计 25
5.1.2一元高次多项式的加、减、乘运算 25
5.2算法的时空分析 25
5.2.1交通咨询系统设计 25
5.2.2一元高次多项式的加、减、乘运算 25
第6章 使用说明 26
6.1交通咨询系统设计 26
6.2一元高次多项式的加、减、乘运算 26
第7章 测试结果 27
7.1交通咨询系统设计 27
7.2一元高次多项式的加、减、乘运算 29
参考文献 33
附 录 34

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

2.输入并创建一元多项式，以链表作为存储结构。
3.实现两个多项式的相加、相减和相乘运算。
4.显示多项式，查看运算结果。
5.用户界面包括以下功能：创建 加法 减法 乘法 显示 退出
1.3 测试数据
1.3.1 交通咨询系统设计
任意输入所需要查找的一个或两个城市，然后查找最短距离、最少花费和最短时间。
1.3.2 一元高次多项式的加、减、乘运算
2X^4+3X^4=5X^4
6X^3+3X^5=6X^3+3X^5
7X^9*4X^5=28X^45
第2章 需求分析
2.1 功能说明
2.1.1 交通咨询系统设计
查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径，显示出所有路径，按升序排列。第二类是任意两个城市间的最短路径，显示最短路径。
2.1.2 一元高次多项式的加、减、乘运算
描述多项式时，将每个子项看成是由系数和指数两部分组成。
输入并创建一元多项式，以链表作为存储结构。
实现两个多项式的相加、相减和相乘运算。
显示多项式，查看运算结果。
2.2 输入说明
2.2.1 交通咨询系统设计
用户根据自己所需要的利用交通系统查询的功能自己进行查询。
2.2.2 一元高次多项式的加、减、乘运算
程序运行后显现提示信息，由用户输入两个多项式，由用户自行选择加减乘功能进行运算。
2.3 输出说明
2.31 交通咨询系统设计
根据用户不同的选择功能输出不同。
2.3.2 一元高次多项式的加、减、乘运算
用户输入数据完毕，程序将输出运算结果。
2.4 测试数据
2.4.1 交通咨询系统设计
用户自行选择功能，可进行按序号查找和按名称查找。
2.4.2 一元高次多项式的加、减、乘运算
测试数据应为两组整数，正负都没有关系。

第3章 概要设计
3.1 抽象数据类型定义
3.1.1 交通咨询系统设计
为实现上程序功能，应创建图的存储结构并使用邻接矩阵表示集合。
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 &g,int n,int e)
{
int i,j;
g.vnm=n;
g.enm=e;
for(i=1;i<=g.vnm;i++)
g.vexs[i]=i;
//对应数组下标即为城市代号
for(i=1;i<=g.vnm;i++)
{//初始化
for(j=1;j<=g.vnm;j++)
{
if(i==j)
{
g.distance[i][j]=0;
g.cost[i][j]=0;
g.time[i][j]=0;
}
else
{
g.distance[i][j]=MAX;
g.cost[i][j]=MAX;
g.time[i][j]=MAX;
}
}
}
3.1.2 一元高次多项式的加、减、乘运算
链表和数组的使用，下面是链表的定义
typedef struct{
double xishu;
double zhishu;
}LNode,*LinkList;

数组的定义：
LNode a[2],b[3];
3.2 程序模块结构
3.2.1 交通咨询系统设计
本程序包含主程序、最少花费、最短距离、最少时间模块和迪杰斯特拉算法、弗洛伊德算法模块等三个模块。
最少花费、最短距离、最少时间模块实现判断两城市之间信息。
迪杰斯特拉算法、弗洛伊德算法模块实现两城市之间的各种信息的具体计算。
三个模块间的调用关系如图3-1所示。

图3-1 模块间的调用关系图
3.2.2 一元高次多项式的加、减、乘运算
本程序包含主程序、加减乘运算函数模块显示模块三个模块。
加减乘模块是用来计算一元高次多项式的加减乘的核心模块。
显示模块是用来显示计算结果的模块。
三个模块间的调用关系如图3-2所示。

图3-2 模块间的调用关系图
第4章 详细设计
4.1 定义的数据类型
4.1.1 交通咨询系统设计
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 &g,int n,int e)
{
int i,j;
g.vnm=n;
g.enm=e;
for(i=1;i<=g.vnm;i++)
g.vexs[i]=i;
//对应数组下标即为城市代号
for(i=1;i<=g.vnm;i++)
{//初始化
for(j=1;j<=g.vnm;j++)
{
if(i==j)
{
g.distance[i][j]=0;
g.cost[i][j]=0;
g.time[i][j]=0;
}
else
{
g.distance[i][j]=MAX;
g.cost[i][j]=MAX;
g.time[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<=g.vnm;v++)
{
final[v]=0;
d[v].spend=g.cost[v0][v];
d[v].sign=v;
p[v0]=-1;
if(d[v].spend
for(w=1;w<=g.vnm;w++)
{//修改d中存放的最短距离和前驱结点
if(!final[w]&&(min+g.cost[v][w] 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<=g.vnm;i++)
{
if(d[i].sign!=v0)
{
cout<<" 从"<[i].spend<<" ";
cout<<" 所经过的路径：";
cout<0)
{
cout<<"<-"<x];
int p[max];
save d[max];
int m,n;
for(v=1;v<=g.vnm;v++)
{
final[v]=0;
d[v].hour=g.time[v0][v];
d[v].sign=v;
p[v0]=-1;
if(d[v].hour
min=MAX;
for(w=1;w<=g.vnm;w++)
if(!final[w])
if(d[w].hourgn=w;
p[w]=v;
}
}
}
//选择排序法
for(i=1;i}
for(i=1;i<=g.vnm;i++)
{
if(d[i].sign!=v0)
{
cout<<" 从"<0)
{
cout<<"<-"<e];
}
cout<
if(d[v].len1;w<=g.vnm;w++)
{//修改d中存放的最短距离和前驱结点
if(!final[w]&&(min+g.distance[v][w] 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<=g.vnm;i++)
{
if(d[i].sign!=v0)
{
cout<<" 从"< cout<<" 所经过的路径：";
cout<0)
{
cout<<"<-"<交通咨询系统------------------------ "<沈阳 17：深圳 18：天津 19：武汉"<>num;
switch(num)
{
case 1: onecity(g); break;
case 2: twocity(g); break;
case 3: cout<<" 退出系统成功！"<];
2.加减乘的运算
下面是加法运算的伪代码：
void jia() //加法
{
if(a[0].zhishu==a[1].zhishu) //如果指数相等，让两系数相加
{
b[0].xishu=a[0].xishu+a[1].xishu; // b[0].xishu是两系数之和
if(a[0].zhishu==0&&a[1].zhishu==0)
{
if(a[0].xishu==0&&a[1].xishu==0)
cout<<"0"<)
cout<xishu!=0)
cout<ishu==0&&a[1].zhishu!=0)
{
if(a[0].xishu==0&&a[1].xishu==0)
cout<<"0"<u<<"+"<l;
if(a[0].xishu!=0&&a[1].xishu!=0)
cout<
if(a[0].xishu!=0&&a[1].xishu==0)
cout<元高次多项式的加、减、乘运算系统★"< ※"< 0→退出 ※"<>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 0:break;
default:cout<<"输入有误，请重新输入："<5.1.1 交通咨询系统设计
程序主要是通过各种程序的调用关系运行，只要按着系统提示进行录入就可以了。
5.1.2 一元高次多项式的加、减、乘运算
程序主要以链表建立一元高次多项式，以数组的形式存储一元高次多项式，只要按着系统提示进行录入就可以了。
5.2 算法的时空分析
5.2.1 交通咨询系统设计
（1）由于有序表采用带头结点的有序单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理，shortestdistance2，shortestcost2，shortesttime2等操作的时间复杂度均为O（n），其中n为链表的长度。
（2）构造有序集算法Create读入n个元素，逐个用for循环输入元素后，在直接初始化各个路径花费和城市名称，所以时间复杂度也是O（n）。
5.2.2 一元高次多项式的加、减、乘运算
（1）由于有序表采用带头结点的有序单链表，并增设a[2],b[3]两个数组链表，并且有一个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 一元高次多项式的加、减、乘运算
图7-6初始化界面
图7-8 创建界面

图7-9 加法
图7-10 减法
图7-11 乘法

图7-12显示加法

图7-12显示乘法

图7-13 显示减法

总 结
本设计使用当今较为流行的可视化编程工具……
通过课程设计不仅学习了VC++，而且技术素质和实践能力有了进一步的提高，对提出问题、思考问题与解决问题有了进一步的深刻认识。同时对软件开发也有了更为全面的了解，通过自己的努力思考、学习研究与指导老师的认真指导，使自己的能力得到了进一步锻炼与提高。
通过课程设计不仅学习了数据结构，而且技术素质和实践能力有了进一步的提高，对提出问题、思考问题与解决问题有了进一步的深刻认识。同时对软件开发也有了更为全面的了解，通过自己的努力思考、学习研究与指导老师的认真指导，使自己的能力得到了进一步锻炼与提高。通过这次课设，对于程序中用到的自己又积累了不少编程的经验。
程序十进制四则运算计算器应用到了二叉链表的存储方式、栈、中缀后缀表达式、遍历等知识点。由于表达式中存在字符和数字，因此采用了字符和数字的共用体来作为数据的存储方式。对于表达式可能输入有误的问题，程序中加入了许多判断，减少了程序执行错误表达式的情况。参考文献
［1］ 王立柱．C/C++与数据结构．北京：清华大学出版社，2002_2．
［2］ 刘振鹏，张小莉，郑艳娟．数据结构（第二版）．北京：中国铁道出版社，2007_4．
［3］ 唐宁九．数据结构与算法分析．成都：四川大学出版社，2006_8．
［4］ 李春葆，金晶．数据结构教程．北京：清华大学出版社，2006_11．
［5］ 周霭如，林伟健．C++程序设计基础．北京：电子工业出版社，2003_8．
［6］ 严蔚敏，吴伟民，米宁．数据结构题集（C语言版）．北京：清华大学出版社，2009.4
[7] 斯庆巴拉. 数据结构（C语言描述）.北京：中国水利水电出版社，2005.

附 录
交通系统源代码：
#include
#include
#include
using namespace std;
const int max=100;
const int MAX=20000;
typedef struct
{
int vexs[max];
string name[max];
int cost[max][max];
int distance[max][max];
int time[max][max];
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.vexs[i]=i;
//对应数组下标即为城市代号
for(i=1;i<=g.vnm;i++)
{//初始化
for(j=1;j<=g.vnm;j++)
{
if(i==j)
{
g.distance[i][j]=0;
g.co