数据结构课设

来源：乌哈旅游

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

报告(论文)题目：交通咨询系统设计一元高次多项式的加、减、乘运算十进制四则运算计算器作者所在系部：计算机科学工程系作者所在专业：计算机科学与技术作者所在班级： B10512 作者学号： 20104051217 作者姓名：易伟皎指导教师姓名：斯琴巴拉完成时间： 2011/12/19

北华航天工业学院教务处制

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

课题名称《数据结构》课程设计讲师完成时间班级 2011.12.19 B10512 指导教师斯庆巴拉职称学生姓名易伟皎总体设计要求总体设计要求：课程设计内容共给定7个题目，从中按要求选3个题目。每个题目都按课程设计详细要求，在规定的两周时间内完成。选题要求：4和7、2和6、1和5不能一起选。题目： 1、迷宫问题 2、哈夫曼编码/译码实现 3、交通咨询系统设计 4、排序算法的比较 5、求一元高次多项式的加、减、乘运算 6、十进制四则运算计算器 7、航班信息查询系统设计工作内容及时间进度安排第一周、周１：设计动员，分组，布置课程设计任务。第一周、周2：查阅资料，制定方案，进行程序总体设计。第一周、周3~第二周2：详细设计, 系统调试。第二周、周3：整理，撰写设计报告。第二周、周3~周5：验收，提交设计报告，评定成绩。毕业设计成果 1、课程设计报告书一份 2、源程序清单一份

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

第1章问题描述 ................................................................................................................. 1

1.1题目内容 ................................................................................................................ 1

1.1.1交通咨询系统设计 .................................................................................... 1 1.1.2一元高次多项式的加、减、乘运算 ........................................................ 1 1.1.3十进制四则运算计算器 .............................................................................. 1 1.2基本要求 ................................................................................................................ 1

1.2.1交通咨询系统设计 .................................................................................... 1 1.2.2一元高次多项式的加、减、乘运算 ........................................................ 1 1.2.3 十进制四则运算计算器 ....................................................................... 2

第2章需求分析 ................................................................................................................. 3

2.1功能说明 ................................................................................................................ 3

2.1.1交通咨询系统设计 ...................................................................................... 3 2.1.2一元高次多项式的加、减、乘运算 ........................................................ 4 2.1.3十进制四则运算计算器 ............................................................................ 5 2.2输入说明 ................................................................................................................ 5

2.2.1交通咨询系统设计 .................................................................................... 5 2.2.2一元高次多项式的加、减、乘运算 ........................................................ 5 2.2.3十进制四则运算计算器 ............................................................................ 5 2.3输出说明 ................................................................................................................ 6

2.3.1交通咨询系统设计 .................................................................................... 6 2.3.2一元高次多项式的加、减、乘运算 ........................................................ 6 2.3.3十进制四则运算计算器 ............................................................................ 6 2.4测试数据 ................................................................................................................ 6

2.4.1交通咨询系统设计 .................................................................................... 6 2.4.2一元高次多项式的加、减、乘运算 ........................................................ 6 2.4.3十进制四则运算计算器 ............................................................................ 6

第3章概要设计 ................................................................................................................. 7

3.1程序模块结构 ........................................................................................................ 7

3.1.1交通咨询系统设计 .................................................................................... 7 3.1.2一元高次多项式的加、减、乘运算 ........................................................ 7 3.1.3十进制四则运算计算器 ............................................................................ 8

第4章详细设计 ................................................................................................................. 9

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

4.1定义的数据类型 .................................................................................................... 9

4.1.1交通咨询系统设计 .................................................................................... 9 4.1.2一元高次多项式的加、减、乘运算 ...................................................... 10 4.1.3十进制四则运算计算器 .......................................................................... 11 4.2函数间的调用关系 .............................................................................................. 13

4.2.1交通咨询系统设计 .................................................................................. 13 4.2.2一元高次多项式的加、减、乘运算 ...................................................... 27 4.2.3十进制四则运算计算 .............................................................................. 32

第5章调试分析 ............................................................................................................... 47

5.1调试过程分析 ...................................................................................................... 47

5.1.1交通咨询系统设计 .................................................................................. 47 5.1.2一元高次多项式 ...................................................................................... 47 5.1.3十进制四则运算计算器 .......................................................................... 47 5.2算法的时空分析 .................................................................................................. 47

5.2.1交通咨询系统设计 .................................................................................. 47 5.2.2一元高次多项式 ...................................................................................... 47 5.2.3十进制四则运算计算器 .......................................................................... 48

第6章使用说明 ............................................................................................................... 49

6.1交通咨询系统设计 .............................................................................................. 49 6.2一元高次多项式 .................................................................................................. 49 6.3十进制四则运算计算器 ...................................................................................... 49 第7章测试结果 ............................................................................................................... 50

7.1交通咨询系统设计 .............................................................................................. 50 7.2一元高次多项式 .................................................................................................. 52 7.3十进制四则运算计算器 ...................................................................................... 53 总结 ................................................................................................................................. 54 参考文献 ............................................................................................................................. 55

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

第1章问题描述

1.1题目内容

1.1.1交通咨询系统设计

1.1.2一元高次多项式的加、减、乘运算

1.1.3十进制四则运算计算器

1.2基本要求

1.2.1交通咨询系统设计

设计一个交通咨询系统，能让旅客咨询从任一城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。

1．创建图的存储结构使用邻接矩阵。

2．查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径（要求使用迪杰斯特拉算法），显示出所有路径，按升序排列。第二类是任意两个城市间的最短路径（要求使用弗洛伊德算法），显示最短路径。

3．按给定交通地图完成以上功能。

1.2.2一元高次多项式的加、减、乘运算

系统总体说明：

用链表表示一元高次多项式，实现两个多项式的加、减、乘运算。完成功能的详细说明：

1．描述多项式时，将每个子项看成是由系数和指数两部分组成。 2．输入并创建一元多项式，以链表作为存储结构。 3．实现两个多项式的相加、相减和相乘运算。 4．显示多项式，查看运算结果。 5．用户界面包括以下功能：创建,加法,减法,乘法,显示,退出.

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

1.2.3 十进制四则运算计算器

系统总体说明：

将算术表达式用二叉树表示，并对其进行遍历，求出后缀表达式后，计算后缀表达的值。

完成功能的详细说明：

1．表达式以中缀字符串形式给出，以‘#’作为结束符。 2．二叉树以二叉链表形式存储。

3．给出二叉树先序、中序和后序三种遍历的结点序列，所有遍历用非递归算法实现。

4．求后缀表达式的值用栈实现。

5．算术表达式中包含的运算有加、减、乘、除。

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

第2章需求分析

2.1功能说明

2.1.1交通咨询系统设计

系统总体说明：

完成功能的详细说明：

1．创建图的存储结构使用邻接矩阵。

3．按给定交通地图完成以上功能。

8 242 305 20 1892 1145 22 216 11 676 842 3 1100 967 639 10 14 7 409 902 672 12 25 367 675 6 140 17

2 16 9 668 695 21 511 24 349 1 137 704 18 397 4 674 23 651 15 825 13 622 5 534 19 607 255 3

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

图1 表示交通网的例图

注：图中顶点给定的是每个城市的代号，边上的权值代表里程。各城市间通行时的花费和时间如表1所示。

城市名称和代号对照：

1：北京 2：长春 3：成都 4：大连 5：福州 6：广州 7：贵阳 8：哈尔滨 9：呼和浩特

10：昆明 11：兰州 12：柳州 13：南昌 14：南宁 15：上海 16：沈阳 17：深圳

18：天津 19：武汉 20：乌鲁木齐 21：西安 22：西宁 23：徐州 24：郑州 25：株州

表1 各城市间通行时的花费和时间表

起点终点花费间 20 11 1 18 16 21 7 12 11 9 24 23 2 3 12 25 450 370 250 220 90 270 210 230 32 24 13 5 3 15 10 11 22 9 24 18 2 3 12 19 11 1 23 16 8 10 14 24 70 230 95 240 72 380 74 185 时起点终点花费间 2 12 3 13 2 23 2 4 11 21 1 16 3 7 7 19 21 24 18 4 7 10 25 25 210 190 55 160 330 225 310 145 时起点终点花费间 5 11 1 7 21 11 20 3 时23 6 15 25

232 225 12 11 13 5 15 13 260 215 14 10 13 6 25 17 105 265 4 14 2.1.2一元高次多项式的加、减、乘运算

实现两个一元高次多项式的加减乘除运算。并输出结果！系统总体说明：

用链表表示一元高次多项式，实现两个多项式的加、减、乘运算。完成功能的详细说明：

描述多项式时，将每个子项看成是由系数和指数两部分组成。

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

输入并创建一元多项式，以链表作为存储结构。实现两个多项式的相加、相减和相乘运算。显示多项式，查看运算结果。用户界面包括以下功能：

创建，加法，减法，乘法，显示，退出

2.1.3十进制四则运算计算器

输入一个十进制算数表达式，实现它的运算，并求出他的前，中，后缀表达式并显示出来。

系统总体说明：

将算术表达式用二叉树表示，并对其进行遍历，求出后缀表达式后，计算后缀表达的值。

完成功能的详细说明：

表达式以中缀字符串形式给出，以‘#’作为结束符。二叉树以二叉链表形式存储。

给出二叉树先序、中序和后序三种遍历的结点序列，所有遍历用非递归算法实现。求后缀表达式的值用栈实现。

算术表达式中包含的运算有加、减、乘、除。

2.2输入说明

2.2.1交通咨询系统设计

程序运行后显现提示信息，由用户输入选项。程序将自动为用户查询；

2.2.2一元高次多项式的加、减、乘运算

用户输入两个一元高次多项式，然后根据指令实现两个多项式的加减显示运算

2.2.3十进制四则运算计算器

用户输入一个十进制的数学表达式，通过指令来进行运算，并实现他的前，中，后缀表达式。

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

2.3输出说明

2.3.1交通咨询系统设计

用户输入数据完毕，程序将输出查询结果

2.3.2一元高次多项式的加、减、乘运算

用户输入完毕，程序根据指令输出相应的结果。

2.3.3十进制四则运算计算器

用户输入完毕，程序根据指令输出相应的结果。

2.4测试数据

2.4.1交通咨询系统设计

用户输入测试指令。

2.4.2一元高次多项式的加、减、乘运算

输入一个一元高次多项式，最好不要太复杂，方便检验。

2.4.3十进制四则运算计算器

输入一个简单易算，但是包含各种运算符的表达式以方便检验。

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

第3章概要设计

3.1程序模块结构

3.1.1交通咨询系统设计

本程序包含主程序、Dihkstra算法，Floyd,算法！

图3-1 模块间的调用关系

3.1.2一元高次多项式的加、减、乘运算

本程序包括主函数，插入函数，建立多项式函数，销毁多项式函数，输出函数，加法运算函数，减法运算函数，乘法运算函数。

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

图3-1-2模块间的调用关系

3.1.3十进制四则运算计算器

本程序包括主程序，栈的定义，初始化，出入栈，创建树，先中后序遍历，输入表达式利用后缀表达式求值，输入函数。显示函数。

图3-1-3十进制四则运算间的模块调用关系

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

第4章详细设计

4.1定义的数据类型

4.1.1交通咨询系统设计

1．结点类型 typedef struct {int rode;

int money; int time;

}type; 2．图的类型 typedef struct

{ int vexs[MAXSIZE];

type edges[MAXSIZE][MAXSIZE];

3．交通图G的定义

利用MGragh定义变量G，然后利用CreateMGragh(MGragh *G)函数对其进行初始化。 4．主函数的伪码算法 void main() {定义各个变量； ……

CreateMGragh(&G);

int v,e;

}MGragh;

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

……. { …… Switch() {

………….掉哟部分各个函数。 } } }

while(qq==1)

4.1.2一元高次多项式的加、减、乘运算

1．结点类型 //定义节点

typedef struct Polynomial{

float coef; //系数 int expn; //指数 struct Polynomial *next;

}*Polyn,Polynomial; //Polyn为结点指针类型 2．链表的定义

利用Polynomial定义一个变量。利用Polyn CreatePolyn(Polyn head,int m){建立一个头指针为head、项数为m的一元多项式

3．主函数的伪码算法 int main(){ ……

pa=CreatePolyn(pa,m);//建立多项式a pb=CreatePolyn(pb,m);//建立多项式a …… for（） { If（）

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

{PrintPolyn(pb); PrintPolyn(pa);} …… if() {…} …}

DestroyPolyn(pa); DestroyPolyn(pb); return 0; }

4.1.3十进制四则运算计算器

1．结点类型 typedef struct { int isNum;//0是操作符1代表数字！ union { double num; char oper;

};

} Info;

typedef struct BiTNode { Info *data;

struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree; 2. 栈的类型 typedef struct { Info *data[STACK_SIZE];

int top;

} ExpStack;// 定义表达式栈

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

// 为后序非递归二叉树而建的栈 typedef struct { BiTree link; int flag;

} StackType;

// 为创建二叉树而建的栈 typedef struct { BiTree link[STACK_SIZE];

int top; } TreeStack; 3.树，栈的定义

使用对应的节点类型创建变量。 4.主函数的伪码算法 void main() { …… While() { Intput(); …… Switch() { case 1: cout<<\"输入表达式\"; ComputeExpression(info,tempExp,result,bt);

break; case 2: cout<<\"结果为：\"<case 3:

ShowExpression(info,tempExp,bt);

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

break;

case 4: 结束.

} } }

4.2函数间的调用关系

4.2.1交通咨询系统设计

void CreateMGragh(MGragh *G) //构造路程图，返回首地址G { int i,j;

G->v=25;G->e=30; //顶点数和边数 for(i=1;i<=G->v;i++)

{ G->vexs[i]=i; //顶点信息

}

for(i=1;i<=G->v;i++) for(j=1;j<=G->v;j++) if(i==j) { G->edges[i][j].money=0; G->edges[i][j].rode=0; G->edges[i][j].time=0;

} else { G->edges[i][j].money=MAXEDGE; G->edges[i][j].rode=MAXEDGE;

G->edges[i][j].time=MAXEDGE; 13

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

}

G->edges[1][9].rode=G->edges[9][1].rode=668; G->edges[1][18].rode=G->edges[24][1].rode=695; G->edges[2][8].rode=G->edges[8][2].rode=242; G->edges[2][16].rode=G->edges[16][2].rode=305; G->edges[3][7].rode=G->edges[7][3].rode=967; G->edges[3][10].rode=G->edges[10][3].rode=1100; G->edges[3][21].rode=G->edges[21][3].rode=842; G->edges[4][16].rode=G->edges[16][4].rode=397; G->edges[5][13].rode=G->edges[13][5].rode=622; G->edges[6][17].rode=G->edges[17][6].rode=140; G->edges[6][25].rode=G->edges[25][6].rode=675; G->edges[7][10].rode=G->edges[10][7].rode=639; G->edges[7][12].rode=G->edges[12][7].rode=607; G->edges[7][25].rode=G->edges[25][7].rode=902; G->edges[9][11].rode=G->edges[11][9].rode=1145; G->edges[11][20].rode=G->edges[20][11].rode=1892; G->edges[11][21].rode=G->edges[21][11].rode=676; G->edges[11][22].rode=G->edges[22][11].rode=216; G->edges[12][14].rode=G->edges[14][12].rode=255; G->edges[12][25].rode=G->edges[25][12].rode=672; G->edges[13][15].rode=G->edges[15][13].rode=825; G->edges[13][25].rode=G->edges[25][13].rode=367; G->edges[15][23].rode=G->edges[23][15].rode=651; G->edges[16][18].rode=G->edges[18][16].rode=704; G->edges[18][23].rode=G->edges[23][18].rode=674; G->edges[19][24].rode=G->edges[24][19].rode=534; G->edges[19][25].rode=G->edges[25][19].rode=409; G->edges[21][24].rode=G->edges[24][21].rode=511; G->edges[23][24].rode=G->edges[24][23].rode=349;

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

G->edges[1][9].money=G->edges[9][1].money=230; G->edges[1][18].money=G->edges[18][1].money=55; G->edges[1][24].money=G->edges[24][1].money=250; G->edges[2][8].money=G->edges[8][2].money=72; G->edges[2][16].money=G->edges[16][2].money=90; G->edges[3][7].money=G->edges[7][3].money=330; G->edges[3][10].money=G->edges[10][3].money=380; G->edges[3][21].money=G->edges[21][3].money=270; G->edges[4][16].money=G->edges[16][4].money=160; G->edges[5][13].money=G->edges[13][5].money=215; G->edges[6][17].money=G->edges[17][6].money=260; G->edges[6][25].money=G->edges[25][6].money=225; G->edges[7][10].money=G->edges[10][7].money=225; G->edges[7][12].money=G->edges[12][7].money=210; G->edges[7][25].money=G->edges[25][7].money=310; G->edges[9][11].money=G->edges[11][9].money=370; G->edges[11][20].money=G->edges[20][11].money=450; G->edges[11][21].money=G->edges[21][11].money=210; G->edges[11][22].money=G->edges[22][11].money=70; G->edges[12][14].money=G->edges[14][12].money=74; G->edges[12][25].money=G->edges[25][12].money=230; G->edges[13][15].money=G->edges[15][13].money=260; G->edges[13][25].money=G->edges[25][13].money=105; G->edges[15][23].money=G->edges[23][15].money=232; G->edges[16][18].money=G->edges[18][16].money=240; G->edges[18][23].money=G->edges[23][18].money=220; G->edges[19][24].money=G->edges[24][19].money=185; G->edges[19][25].money=G->edges[25][19].money=145; G->edges[21][24].money=G->edges[24][21].money=190; G->edges[23][24].money=G->edges[24][21].money=95;

G->edges[1][9].time=G->edges[9][1].time=12;

G->edges[1][18].time=G->edges[18][1].time=1;

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

G->edges[1][24].time=G->edges[24][1].time=13; G->edges[2][8].time=G->edges[8][2].time=2; G->edges[2][16].time=G->edges[16][2].time=3; G->edges[3][7].time=G->edges[7][3].time=21; G->edges[3][10].time=G->edges[10][3].time=23; G->edges[3][21].time=G->edges[21][3].time=15; G->edges[4][16].time=G->edges[16][4].time=7; G->edges[5][13].time=G->edges[13][5].time=10; G->edges[6][17].time=G->edges[17][6].time=14; G->edges[6][25].time=G->edges[25][6].time=11; G->edges[7][10].time=G->edges[10][7].time=11; G->edges[7][12].time=G->edges[12][7].time=10; G->edges[7][25].time=G->edges[25][7].time=20; G->edges[9][11].time=G->edges[11][9].time=24; G->edges[11][20].time=G->edges[20][11].time=32; G->edges[11][21].time=G->edges[21][11].time=5; G->edges[11][22].time=G->edges[22][11].time=2; G->edges[12][14].time=G->edges[14][12].time=2; G->edges[12][25].time=G->edges[25][12].time=11; G->edges[13][15].time=G->edges[15][13].time=14; G->edges[13][25].time=G->edges[25][13].time=4; G->edges[15][23].time=G->edges[23][15].time=12; G->edges[16][18].time=G->edges[18][16].time=13; G->edges[18][23].time=G->edges[23][18].time=5; G->edges[19][24].time=G->edges[24][19].time=4; G->edges[19][25].time=G->edges[25][19].time=3; G->edges[21][24].time=G->edges[24][21].time=11; G->edges[23][24].time=G->edges[24][23].time=3;

}

void rodeshort1(MGragh *G, int vv)

{ int v, w, i, pre[26],min,p;

int P[26];

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

int D[26]; int final[26]; for(v=1; v<=G->v; v++) { final[v]=0;

D[v]=G->edges[vv][v].rode; //将边上权值付给数组D[]; P[vv]=-1;

if(D[v]P[v]=vv;

if(D[v]==MAXEDGE)

P[v]=-2;

} D[vv]=0;

将vv顶点加入S集 for(i=1;i<=G->v;i++) { min=MAXEDGE; // 当前所知离vv顶点的最近距离 for(w=1;w<=G->v;w++) if(!final[w]) // w顶点在V-S中 if(D[w]min=D[w];

} // w顶点离vv顶点更近

final[v]=1; // 离vv顶点最近的v加入S集 for(w=1;w<=G->v;w++) // 更新当前最短路径及距离 if(!final[w]&&(min+G->edges[v][w].rodeedges[v][w].rode; P[w]=v;

}

for(i=1;i<=G->v;i++) {

if(P[i]==-2)

final[vv]=1; //

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

cout<<\"max\"<else {

cout<while(pre[o]!=-1) { p=P[pre[o]]; o++; pre[o]=p;

}

while(o>1) { cout<<\" -> \"<o--;

} if(vv!=i)

{cout<<\" -> \"<}

}

void rodeshort2(MGragh *G,int a,int b) { int u, v, w;

int P[26][26]; int D[26][26]; for(v=1;v<=G->v;v++) for(w=1;w<=G->v;w++) { D[v][w]=G->edges[v][w].rode;

if( D[v][w]18

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

}

P[v][w]=v;

else

if(v!=w)

P[v][w]=-2;

else

P[v][w]=-1;

for(u=1;u<=G->v;u++) for(v=1;v<=G->v;v++) for(w=1;w<=G->v;w++)

if(D[v][u]+D[u][w]{

D[v][w]=D[v][u]+D[u][w]; P[v][w]=u;

}

for(int i=1;i<=25;i++)

for(int j=1;j<=25;j++)

{ if(i==a&&j==b)

{

if(D[i][j]==MAXEDGE) { if(i!=j) } else {

cout<<\"最小值：\"<cout<<\"从\"<径：\"; }

}

cout< \";

Ppath2(P,i,j);

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

void moneyshort1(MGragh *G, int vv)

{ int v, w, i, pre[26],min,p; int P[26]; int D[26]; int final[26]; for(v=1; v<=G->v; v++) { final[v]=0;

D[v]=G->edges[vv][v].money; //将边上权值付给数组D[]; P[vv]=-1;

if(D[v]P[v]=vv;

if(D[v]==MAXEDGE)

P[v]=-2;

}

D[vv]=0;

final[vv]=1; // 将vv顶点加入S集 for(i=1;i<=G->v;i++) { min=MAXEDGE; // 当前所知离vv顶点的最近距离 for(w=1;w<=G->v;w++) if(!final[w]) // w顶点在V-S中 if(D[w]min=D[w];

} // w顶点离vv顶点更近

final[v]=1; // 离vv顶点最近的v加入S集 for(w=1;w<=G->v;w++) // 更新当前最短路径及距离 if(!final[w]&&(min+G->edges[v][w].moneyedges[v][w].money; P[w]=v;

}

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

}

for(i=1;i<=G->v;i++) { if(P[i]==-2)

cout<<\"max\"<else { cout<pre[0]=P[i]; int o=0;

while(pre[o]!=-1) { p=P[pre[o]]; o++; pre[o]=p;

}

while(o>1) { cout<<\" -> \"<o--;

} if(vv!=i)

{cout<<\" -> \"<}

}

void moneyshort2(MGragh *G,int a,int b) //法求任意两个顶点间的最短路径 {

用弗洛伊德算21

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

int u, v, w;

int P[26][26]; int D[26][26]; for(v=1;v<=G->v;v++)

for(w=1;w<=G->v;w++) { }

D[v][w]=G->edges[v][w].money;

if( D[v][w]P[v][w]=v;

else

if(v!=w)

P[v][w]=-2;

else

P[v][w]=-1;

for(u=1;u<=G->v;u++) for(v=1;v<=G->v;v++) for(w=1;w<=G->v;w++)

if(D[v][u]+D[u][w]{

D[v][w]=D[v][u]+D[u][w]; P[v][w]=u;

}

for(int i=1;i<=25;i++)

for(int j=1;j<=25;j++)

{ if(i==a&&j==b)

{

if(D[i][j]==MAXEDGE) { if(i!=j) } else {

cout<<\"最小值：\"<cout<<\"从\"<径：\";

cout< \";

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

}

void timeshort1(MGragh *G, int vv) //迪杰斯特拉算法求某一点到其他点的最短路径

{ //vv代表起点，P[]表示到下一个节点的前驱节点的代码，final[v]=1，且v在已经遍历过的顶点中，当且仅当求的最短路径

}

Ppath2(P,i,j);

cout<int v, w, i, pre[26],min,p; // int P[26]; int D[26]; int final[26]; for(v=1; v<=G->v; v++) { } D[vv]=0;

final[v]=0;

D[v]=G->edges[vv][v].time; //将边上权值付给数组D[]; P[vv]=-1;

if(D[v]P[v]=vv;

if(D[v]==MAXEDGE)

P[v]=-2;

final[vv]=1; // 将vv顶点加入S集

for(i=1;i<=G->v;i++) {

min=MAXEDGE; // 当前所知离vv顶点的最近距离 for(w=1;w<=G->v;w++)

if(!final[w]) // w顶点在V-S中

if(D[w]23

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

{ v=w;

min=D[w];

} // w顶点离vv顶点更近

final[v]=1; // 离vv顶点最近的v加入S集 for(w=1;w<=G->v;w++) // 更新当前最短路径及距离 if(!final[w]&&(min+G->edges[v][w].timeedges[v][w].time; P[w]=v;

}

for(i=1;i<=G->v;i++) { if(P[i]==-2)

cout<<\"max\"<else {

cout<pre[0]=P[i]; int o=0;

while(pre[o]!=-1) { p=P[pre[o]]; o++; pre[o]=p;

}

while(o>1) { cout<<\" -> \"<o--;

}

if(vv!=i)

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

{cout<<\" -> \"<}

}

void timeshort2(MGragh *G,int a,int b) //求任意两个顶点间的最短路径 { int u, v, w;

int P[26][26]; int D[26][26]; for(v=1;v<=G->v;v++) for(w=1;w<=G->v;w++) { D[v][w]=G->edges[v][w].time;

if( D[v][w]P[v][w]=v;

else if(v!=w)

P[v][w]=-2;

else

P[v][w]=-1;

}

for(u=1;u<=G->v;u++) for(v=1;v<=G->v;v++) for(w=1;w<=G->v;w++)

if(D[v][u]+D[u][w]P[v][w]=u;

} for(int i=1;i<=25;i++)

for(int j=1;j<=25;j++)

用弗洛伊德算法25

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

{ if(i==a&&j==b)

{ if(D[i][j]==MAXEDGE) { if(i!=j) } else

cout<<\"从\"<径：\";

}

函数间的调用关系如图4-2-1所示。

{

}

cout<<\"最小值：\"< \";

Ppath2(P,i,j);

cout<路26

\"<<\"

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

图4-2-1函数间的调用关系

4.2.2一元高次多项式的加、减、乘运算

void Insert(Polyn p,Polyn h){

if(p->coef==0) delete p; //系数为0的话释放结点 else{ Polyn q1,q2; q1=h;q2=h->next;

while(q2&&p->expnexpn){ //查找插入位置 q1=q2; q2=q2->next; }

if(q2&&p->expn==q2->expn){ //将指数相同相合并 q2->coef+=p->coef; delete p;

if(!q2->coef){ //系数为0的话释放结点 q1->next=q2->next; delete q2; } }

else{ //指数为新时将结点插入 p->next=q2; q1->next=p; }

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

} }

Polyn CreatePolyn(Polyn head,int m){//建立一个头指针为head、项数为m的一元多项式 int i; Polyn p;

p=head=new Polynomial; head->next=NULL; for(i=0;ip=new Polynomial;//建立新结点以接收数据 cout<<\"请输入第\"<>p->coef>>p->expn;

Insert(p,head); //调用Insert函数插入结点 }

return head; }

void DestroyPolyn(Polyn p){//销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next){ delete q1; q1=q2;//指针后移 q2=q2->next; } }

void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q) { //若多项式为空，输出0 cout<<'0'; cout<28

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

if(q->coef>0&&flag!=1) cout<<'+'; //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况 cout<coef; if(q->expn==1) cout<<'X';

else if(q->expn) cout<<\"X^\"<expn; } else{

if(q->coef==1){ if(!q->expn) cout<<'1'; else if(q->expn==1) cout<<'X'; else cout<<\"X^\"<expn; }

if(q->coef==-1){

if(!q->expn) cout<<\"-1\"; else if(q->expn==1) cout<<\"-X\"; else cout<<\"-X^\"<expn; } }

q=q->next; flag++; }//while cout<int compare(Polyn a,Polyn b){ if(a&&b){

if(!b||a->expn>b->expn) return 1; else if(!a||a->expnexpn) return -1; else return 0; }

else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 }//compare

Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next; Polyn qb=pb->next;

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

Polyn headc,hc,qc;

hc=new Polynomial;//建立头结点 hc->next=NULL; headc=hc; while(qa||qb){ qc=new Polynomial; switch(compare(qa,qb)){ case 1: {

qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: {

qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: {

qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } }//switch if(qc->coef!=0){ qc->next=hc->next; hc->next=qc; hc=qc; }

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

else delete qc;//当相加系数为0时，释放该结点 }//while return headc; }

Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a-b，返回其头指针 Polyn h=pb; Polyn p=pb->next; Polyn pd;

while(p){ //将pb的系数取反 p->coef*=-1; p=p->next; }

pd=AddPolyn(pa,h);

for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1; return pd; }

Polyn Mulresult(Polyn D1,Polyn D2) /*多项式相乘*/ { Polyn D; Polyn p,q; int x,z;

D=new Polynomial; D->next=NULL; p=D1->next; q=D2->next; while(q) { while(p) { x=p->coef*q->coef; /*系数相乘，指数相加*/

z=p->expn+q->expn;

Polyn t;

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

t=new Polynomial;//建立新结点以接收数据

t->coef=x; }

} return D;

}

p=D1->next; q=q->next;

t->expn=z;

Insert(t,D); p=p->next;

函数间的调用关系如图4-2-2所示。

图4-2-2函数间的调用关系

4.2.3十进制四则运算计算

Precedence GetPrecedence(int ch) {

switch(ch) {

case '+' : return plus; case '*' : return times; case '-' : return minus; case '/' : return divide; case '(' : return lparen;

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

case ')' : return rparent; default : return mod;

}

typedef struct { Info *data[STACK_SIZE];

int top; } ExpStack;// 定义表达式栈

ExpStack *Init_ExpStack() { ExpStack *e; e = new ExpStack; if(!e) { cout<<\"分配储存空间失败！\"<else {

e->top = -1; return e;

}

int Empty_ExpStack(ExpStack *e) { return e->top==-1 ? 1 : 0;

}

void Push_ExpStack(ExpStack *e,Info *info) { if(e->top == STACK_SIZE-1) { cout<<\"栈满！结束程序！\"<else { e->top++;

e->data[e->top] = info;

}

void Pop_ExpStack(ExpStack *e,Info *&info)

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

{ if(e->top == -1) { cout<<\"栈为空！结束程序！\"<else

info = e->data[e->top--];

}

typedef struct BiTNode { Info *data;

struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;

typedef struct { BiTree link;

int flag;

} StackType;

typedef struct { BiTree link[STACK_SIZE];

int top;

} TreeStack;

int CreatBiTree(BiTree &bt,Info *info[]) { if(info[1]->oper == '=') {

bt = NULL; return 1;

}

TreeStack *numTS = new TreeStack; TreeStack *operTS = new TreeStack; numTS->top = -1; operTS->top = -1; int i;

for(i = 0;info[i]->oper != '=';i++)

{

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

数字栈

//运

operTS->link[operTS->top]->lchild = numTS->link[numTS->top--];// 数据出

if(info[i]->isNum) //数字元素入栈 { } else {

if(info[i]->oper == '(')//作括号如站 { }

else if(info[i]->oper == ')')//一直初战一直到预见括号的另一半 {

while(operTS->link[operTS->top]->data->oper != '(') {

operTS->link[operTS->top]->rchild = numTS->link[numTS->top--];// 数据出operTS->link[++operTS->top] = new BiTNode; operTS->link[operTS->top]->data = info[i]; numTS->link[++numTS->top] = new BiTNode; numTS->link[numTS->top]->data = info[i];

numTS->link[numTS->top]->lchild = numTS->link[numTS->top]->rchild = NULL;

算副作为根节点两个数字作为自节点

numTS->link[++numTS->top] = operTS->link[operTS->top--];//运算符出操作

符栈，把地址并入数字栈

} else

if(GetPrecedence(info[i]->oper)

}

delete operTS->link[operTS->top--];// '('出操作符栈 if(operTS->top==-1 && info[i+1]->oper!='=') { }

cout<<\"表达式缺少左括号！请重新输入！\"<GetPrecedence(operTS->link[operTS->top]->data->oper))

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

{

operTS->link[++operTS->top] = new BiTNode; operTS->link[operTS->top]->data = info[i];

}//操作符优先级高于栈顶运算符入栈 else {

while(GetPrecedence(info[i]->oper)

GetPrecedence(operTS->link[operTS->top]->data->oper))

数字栈

numTS->link[++numTS->top] = operTS->link[operTS->top--];//运算符出操作

operTS->link[operTS->top]->lchild = numTS->link[numTS->top--];// 数据出

{

operTS->link[operTS->top]->rchild = numTS->link[numTS->top--];// 数据出

符栈，并入数字栈

}

void Visited(BiTree p) {

}

operTS->link[++operTS->top] = new BiTNode;//把这个运算符入栈 operTS->link[operTS->top]->data = info[i];

if(operTS->top==-1 && numTS->top==0) { } else { }

cout<<\"表达式缺少右括号！请重新输入！\"<bt = numTS->link[numTS->top]; return 1;

if(p->data->isNum)

cout<data->num<<\" \";

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

else

cout<data->oper<<\" \";

}

void NRPreOrder(BiTree bt) { BiTree stack[STACK_SIZE]; BiTree p = bt; int top = -1; if(bt == NULL) {

cout<<\"The bintree is empty!\"<while(p!=NULL || top!=-1) { while(p) { Visited(p);

if(top >= STACK_SIZE -1) {

cout<<\"The stack is full!\"<}

stack[++top] = p; // push stack p = p->lchild;

}

p = stack[top--]; // pop stack p = p->rchild;

}

void NRInOrder(BiTree bt) { BiTree stack[STACK_SIZE]; BiTree p = bt; int top = -1;

if(bt == NULL)

}

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

{ cout<<\"The bintree is empty!\"<while(p!=NULL || top!=-1) { while(p) {

if(top >= STACK_SIZE -1) {

cout<<\"The stack is full!\"<}

stack[++top] = p; p = p->lchild; // push stack

}

p = stack[top--]; // pop stack Visited(p); p = p->rchild;

}

void NRPostOrder(Info *postExpression[],BiTree bt,int &countpostExpression,int isRecord) { StackType stack[STACK_SIZE]; BiTree p = bt; int sign,top = -1; if(bt == NULL) {

cout<<\"The bintree is empty!\"<}

while(p!=NULL || top!=-1) { if(p) { top++;

stack[top].link = p; stack[top].flag = 1; p = p->lchild;

}

else

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

{ p = stack[top].link; sign = stack[top].flag; top--; if(sign == 1) { top++;

stack[top].link = p; stack[top].flag = 2; p = p->rchild;

} else { if(isRecord) postExpression[++countpostExpression] = p->data; else

Visited(p);

p = NULL;

}

int IsNum(char ch)

{ if((ch>='0'&&ch<='9') ) return 1;

else

return 0; }

void CreateOperInfo(Info *&info,char ch,int &countInfo) { info = new Info;

info->isNum = 0;

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

info->oper = ch; countInfo++;

}

void CreateNumInfo(Info *&info,double n,int &countInfo) { info = new Info; info->isNum = 1; info->num = n; countInfo++;

}

bool GetExpression(Info *info[],char tempExp[]) { cout<<\"请输入一个表达式\\n（输入等号结束）: \"; int i = 1; tempExp[0] = '('; do { cin>>tempExp[i];

i++;

} while(tempExp[i-1] != '=');

cin.ignore(256,'\\n'); // 忽略'='后的字符 cout<if(tempExp[1]=='+' || tempExp[1]=='*' || tempExp[1]=='/') { cout<<\"输入错误开头不可以为‘+’‘*’‘/’！请重新输入！\"<}

// 开始转化为可用的结构 int countInfo = 0; i = 0;

while(tempExp[i] != '=') { if(IsNum(tempExp[i])) {

int middle = i,begin = i;

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

int m = 0,n = 0;

while(IsNum(tempExp[i])) { }

double tempDouble = 0; if(begin != 0)

for(m = begin;m < middle;m++)

tempDouble

i++; middle = i;

(tempExp[m]-'0')*pow((double)10,(double)(middle-m-1));

} else {

if(tempExp[i] == ')') { }

else if(tempExp[i] == '(') { }

else if(tempExp[i]=='+' || tempExp[i]=='-' || tempExp[i]=='*' || tempExp[i]=='/' ) {

if((countInfo!=0) && (info[countInfo-1]->isNum || info[countInfo-1]->oper==')') )

CreateOperInfo(info[countInfo],'*',countInfo);

CreateOperInfo(info[countInfo],tempExp[i],countInfo); if(info[countInfo-1]->oper == ')')

CreateOperInfo(info[countInfo],'*',countInfo);

CreateNumInfo(info[countInfo],tempDouble,countInfo);

CreateOperInfo(info[countInfo],tempExp[i],countInfo);

if(tempExp[i+1] == '=') {

cout<<\"警告！等号前不能为操作符！请重新输入！\"<41

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

}

// 利用后缀表达式求值

double ComputePostExpression(Info *info[],BiTree bt) {

}

i++; }

} else { }

}

return 0;

if(tempExp[i]=='-' && info[countInfo-1]->oper=='(') { }

else if(!(info[countInfo-1]->isNum || info[countInfo-1]->oper==')')) { } else

CreateOperInfo(info[countInfo],tempExp[i],countInfo);

cout<<\"警告！不能连续出现两个以上的运算符！请重新输入！\"<CreateNumInfo(info[countInfo],0,countInfo);

CreateOperInfo(info[countInfo],tempExp[i],countInfo);

cout<<\"有字符不是运算符！请重新输入！\"<CreateOperInfo(info[countInfo],')',countInfo); CreateOperInfo(info[countInfo],'=',countInfo); return 1;

Info *postExpression[EXPRESSION_SIZE]; int countPostExp = -1; // 获取后缀表达式

NRPostOrder(postExpression,bt,countPostExp,1);

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

postExpression[++countPostExp] = new Info; postExpression[countPostExp]->isNum = 0; postExpression[countPostExp]->oper = '='; // 计算后缀表达式

ExpStack *postS = Init_ExpStack(); Info *num1,*num2; Info *tempNum;

for(int i = 0;postExpression[i]->oper != '=';i++) {

if(postExpression[i]->isNum) else {

Pop_ExpStack(postS,num2); Pop_ExpStack(postS,num1); tempNum = new Info;

switch(postExpression[i]->oper) {

case '*' : tempNum->num = num1->num * num2->num;

Push_ExpStack(postS,tempNum); break;

Push_ExpStack(postS,postExpression[i]);

case '/' : if(num2->num == 0)

{

cout<<\"运算过程中‘0’不能作除数！结果不正确！

\"<}

return num1->num / num2->num;

tempNum->num = num1->num / num2->num; Push_ExpStack(postS,tempNum); break;

case '+' : tempNum->num = num1->num + num2->num;

Push_ExpStack(postS,tempNum); break;

case '-' : tempNum->num = num1->num - num2->num;

Push_ExpStack(postS,tempNum);

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

break;

}

return postS->data[postS->top]->num;

}

void input_n(int &n) {

cout<<\"****************************************\"<>n; while(n>4 || n<1) {

cout<<\"\\n您的输入有误，请重新输入:\";

}

cout<}

void input_showExpression(int &t) { cout<<\"*********************************\"<cout<<\"* 1.前缀表达式 *\"<cout<<\"*********************************\"<>t; while(t>3 || t<1)

cout<<\"\\n您的输入有误，请重新输入：\";

}

void ComputeExpression(Info *info[],char tempExp[],double &result,BiTree &bt) { while(!GetExpression(info,tempExp));

while(!CreatBiTree(bt,info))

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

while(!GetExpression(info,tempExp));

}

void ShowExpression(Info *info[],char tempExp[],BiTree &bt) { int t,i;

input_showExpression(t); switch(t) {

case 1: cout<<\"\\n前缀表达式：\"; NRPreOrder(bt); cout<break;

case 2: cout<<\"\\n中缀表达式：\"; NRInOrder(bt); cout<cout<<\"\\n原表达式为：\"; for(i=1;tempExp[i] != '=';i++)

cout<cout<break;

case 3: cout<<\"\\n后缀表达式：\"; NRPostOrder(info,bt,t,0);//t Info 无意义参数 cout<break;

}

函数间的调用关系如图4-2-3所示。

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

图4-2-3函数间的调用关系

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

第5章调试分析

5.1调试过程分析

5.1.1交通咨询系统设计

程序将各个操作集成在函数中，在调试直至需要输入相对的指令就可以。有错误的话，可以很方便的在对应的函数中找到错误。

5.1.2一元高次多项式

定义各个函数将操作封装进入以方便操作与调试

5.1.3十进制四则运算计算器

定义各个函数将操作封装进入以方便操作与调试

5.2算法的时空分析

5.2.1交通咨询系统设计

（1）对于一个城市到各个城市的最短路径，由于各个城市都要储存，共有25个。所以空间复杂度为S(1).

（2）对于时间来说Floyd算法的时间复杂度为O(n^3)，对于dijkstra算法的时间复杂度O（n^2);

5.2.2一元高次多项式

（1）存储多项式空间复杂度为S（N）。

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

(2)创建时间复杂度为O（n），显示时时间复杂度都是为O（n），计算加减法时时间复杂度为o（n），计算乘法时时间复杂度为O（n^2+2n）

5.2.3十进制四则运算计算器

(1)对于表达式储存空间复杂度为S（n），计算临时空间复杂度为O(n)。

（2）创建表达式时间复杂度为O（n），主函数时间复杂度为O（n）其他都为O（1）。

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

第6章使用说明

6.1交通咨询系统设计

程序会给用户提示，根据提示完成查询操作。

6.2一元高次多项式

程序提示用户分别输入两个多项式的项数。并且输入各项的系数，指数。然后程序给出提示对这两个多项式进行操作。并且输出结果。

6.3十进制四则运算计算器

程序给出提示，根据提示输入一个数学表达式，再根据提示完成对表达式的运算，输出等操作。

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

第7章测试结果

7.1交通咨询系统设计

输入两个命令完成测试。第一个命令

输入1出现查询各个城市的查询然后输入1作为起点开始查询运行结果如图7-1-1

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

图7-1-1

第二个命令

输入4实现两个城时间最短路径的查询分别输入2 ，3查询这两个城市的对端路径结果如图7-1-2

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

图7-1-2

7.2一元高次多项式

输入相应操作完成测试测试结果如图7-2-1

北华航天工业学院课程报告图7-2-1

7.3十进制四则运算计算器

输入一个表达式进行运算显示进行测试测试结果如图7-3-1 图7-3-1

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

总结

本设计使用本学期学习的数据结构和C++的知识

通过课程设计不仅学习了VC++，而且技术素质和实践能力有了进一步的提高，对提出问题、思考问题与解决问题有了进一步的深刻认识。同时对软件开发也有了更为全面的了解，通过自己的努力思考、学习研究与指导老师的认真指导，使自己的能力得到了进一步锻炼与提高。

对于数据结构这门课程有了新的认识，意识到代码不过是表象，其灵魂是算法，而数据结构，就是研究这一项的

本系统通过调试运行，结果表明系统具有可行性与可扩充性，但系统还有待于进一步完善。

学习了数据结构，掌握了很多算法，并通过了本次课程设计对此熟悉了。通过本次课程设计了解到了自己的很多不足，比如选发的选择，运用，并且了解到思路的重要性，写程序前一定要有一个明确的思路，否则不仅写得慢，易出错，写完后自己也不满意，充满了种种漏洞，写出的程序一定要人性化，即界面一定简单易懂，要以用户的位置思考问题。

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

参考文献

［1］刘国钧，郑如斯．中国书的故事．北京：中国青年出版社，1979：115．

［2］姚伯元．课程设计(论文)规范化管理与培养学生综合素质．中国高等教育网教学研究，

2005-2-2．

［3］刘振鹏，张小莉，郑艳娟。数据结构（第二版）。中国铁道出版社2007.4 ［4］谭浩强。C++面向对象程序设计。清华大学出版社2006年1月。［5］谭浩强。C程序设计（第三版）。北京：清华大学出版社。2005

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

评语指导教师评语及设计成绩课程设计成绩：指导教师：日期：年月日 56

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

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

数据结构课设