数据结构一元多项式

1、 数据结构 课程设计报告系 别：计算机与电子系 专业班级：电子0802班 学生姓名：胡锦奎（）指导教师：程海英 （课程设计时间：20 10 年 12月 27日20 11 年1月7日）华中科技大学武昌分校目 录1课程设计目的3页2课程设计题目描述和要求 3页3课程设计报告内容5页3.1 一元多项式运算的实现 5页3.2 迷宫问题实现 9页3.3 校园导游咨询13页3.4 跳舞搭配问题15页3.5 利用栈实现表达式求值18页4总结 20页参考文献 21页（要求：目录题头用三号黑体字居中书写，隔行书写目录内容。目录中各级题序及标题用小四号黑体）一课程设计目的： 数据结构课程设计是在学完数据结构课程之

2、后的实践教学环节.该实践教学是软件设计的综合训练,包括问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力,培养科学的软件工作方法.学生通过数据结构课程设计在各方面得到锻炼 二课程设计题目描述和要求：1一元多项式加法、减法、乘法运算的实现1）设计内容：完成两个一元多项式作加法、减法、乘法，给出明确的等式形式。完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；函数功能要划分好，总体设计应画流程图，程序一定要经得起测试2）设计要求（1）用C语言编程实现上述实验内容中的结构定义和算法。（2）要有main()函数，并且在main()函数中使用检测数

3、据调用上述算法。（3）用switch语句设计如下选择式菜单。 *数据结构综合性实验* *一、多项式的加法、减法、乘法运算* * 1.多项式创建 * * 2.多项式相加 * * 3.多项式相减 * 4.多项式相乘 * 5.清空多项式 * 0.退出系统 * 请选择（05） *请选择（0-5）:。2迷宫求解1）设计内容：以一个m*n的长方形矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2)设计要求（1）用C语言编程实现上述实验内容中的结构定义和算法；（2）要有main()函数，并且在main()函数中使用检测数据调用

4、上述算法；3、校园导游咨询1）设计内容：设计一个校园导游程序，为来访的客人提供各种信息咨询服务，包括：（1）设计所在的学校的校园平面图，所含景点不少于5个。以图中顶点表示校内各景点，存放景点的名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的咨询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径2）设计要求：（1）用C语言编程实现上述实验内容中的结构定义和算法；（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法；（3）用switch语句设计如下选择式菜单4、跳舞配对问题设计内容

5、与要求：一共有m个女生，有n个男生（且mn），现要开一个舞会，男女分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男和女中各出一个人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。设计一系统模拟动态地显示出上述过程，要求如下：1）输出每曲配对情况；2）计算出任何一个男（编号为X）和任意一个女（编号为Y），在第K曲配对跳舞的情况，至少求出K的两个值。5、实现表达式求解设计内容：输入一个表达式，按如下要求完成其求值运算：1）表达式中允许有两种括号：（、）、，请验证其匹配成对的合法性；2）运算符限定于加、减、乘、除四种运算，请验证表达式是否书写合法，如3+2-*5就不是一个合法表达式；3）使用栈的

6、原理实现表达式求值；4）尽量考虑参与运算的数是非1位数，如234+32*12。三课程设计报告内容1 一元多项式加法，减法，乘法运算的实现 1.1数据结构设计根据下面给出的存储结构定义：#define MAXSIZE 20 /定义线性表最大容量 /定义多项式项数据类型typedef struct float coef; /系数 int expn; /指数 term,elemType;typedef struct term termsMAXSIZE; /线性表中数组元素 int last; /指向线性表中最后一个元素位置 SeqList;typedef SeqList polynomial;1.2

7、基本操作函数说明 polynomial*Init_Polynomial();/初始化空的多项式int PloynStatus(polynomial*p)/判断多项式的状态 int Location_Element(polynomial*p,term x)在多项式p中查找与x项指数相同的项是否存在int Insert_ElementByOrder(polynomial*p,term x)/在多项式p中插入一个指数项xint CreatePolyn(polynomial*P,int m)/输入m项系数和指数，建立表示一元多项式的有序表pchar compare(term term1,term te

8、rm2)/比较指数项term1和指数项term2polynomial*addPloyn(polynomial*p1,polynomial*p2)/将多项式p1和多项式p2相加，生成一个新的多项式polynomial*subStractPloyn(polynomial*p1,polynomial*p2)/多项式p1和多项式p2相减，生成一个新的多项式polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/多项式p1和多项式p2相乘，生成一个新的多项式void printPloyn(polynomial*p)/输出在顺序存储结构的多项式p1.3设计思路

9、及算法设计 （1）一元多项式的建立：输入多项式采用头插法的方式，输入多项式中一个项的系数和指数（2）显示输入的数字：显示你输入的各项式的指数和系数。（3）.一元多项式加减法和乘法运算进行加减法和乘法的运算后得到的简化的一元多项式可以用一个核心函数addPloyn来实现多项式的加法，它把p1所指向的多项式加p2所指向的多项式，结果为p3所指的多项式。相加时，首先设两个指针变量p1和p2分别从多项式中的首项开始扫描，比较p1和p2所指结点指数域的值，可能出现下面三种情况之一：A，p1-terms【i】大于p2-terms【j】，则p1继续向后扫描。B，p1-terms【i】等于p2-terms【j

10、】，则将其系数相加。若结果不为零，将结果放入p3-terms【k】中，否则同时删除p1和p2所指结点。然后p1和p2继续向后扫描C，p1-terms【i】小于p2-terms【j】，则将p3所指结点插入p2所指结点之前，然后p1，p2继续向后扫描减法的算法实现和加法类似，乘法的算法实现是让系数想乘，指数部分相加 （4）.一元多项式输出和整理以降幂的形式输出1.4功能模块图主函数建立链表排列和组件相加减或相乘入输组成多项式1.5 源代码分析见电子档1.6测试与结果 2.迷宫问题实现 2.1数据结构设计根据以上问题给出存储结构定义： typedef struct /定义坐标int x;int y;

11、item; /定义坐标和方向typedef structint x;int y;int d;dataType; /定义顺序栈的类型定义typedef structdataType dataMAXLEN;int top;SeqStack;item move8; /8邻域试探方向数组int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1

12、,1,1,1,1,1,1,1,; /定义迷宫数组，0表示有路径，1表示不存在路径 2.2基本操作函数说明void print_Path(SeqStack*s);/输出迷宫路线SeqStack*InitSeqStack()/该函数初始化一个空栈，并返回指向该栈的存储单元首地址int Push(SeqStack*s,dataType x)/将元素x入栈s,若入栈成功返回结果1；否则返回0int StackEmpty(SeqStack*s)/该函数判断栈是否为空，若栈空返回结果1；否则返回0int Pop(SeqStack*s,dataType*x)/将栈顶元素出栈，放入x所指向的存储单元中，若出栈

13、返回结果1；否则返回0void init_move(item move8)/初始化8邻域方向int find_Path(int mazeM+2N+2,item move8)/在迷宫maze二维数组中按move的8邻域方向探测迷宫路线，存在返回1，否则返回0void print_Path(SeqStack*s)/输出栈s中所有迷宫路径2.3程序设计内容与思路 迷宫求解的第一步是确定存储表示。最直接的表示无疑是数组，我们用二维数组maze表示迷宫，闯迷宫的物体的位置可以用数组的行row，列col表示，即maze【row】【col】。用X表示迷宫中的一点，下一步可试探的方向共有8个，如果参照指南针的

14、指向，这8个方向分别为东，南，西，北，东北，东南，西北，西南。有一点需要注意，迷宫中的位置并不都有8个领域，如在迷宫的靠墙位置其领域数小于8，为了方便处理，在迷宫周围加上一圈，可省去边界检查。这样m*n的迷宫需要(m+2)*(n+2)大小的数组，入口点改为maze【1】【1】，出口点改为maze【m】【n】 为了程序实现进一步简化，可以再定义一个数组move表示移动的方向.下一步的移动方向可用下列式子表示 nextRow=row+movedir.x nextcol=col+movedir.y 在迷宫中搜索，某一时刻有多种选择，究竟哪个方向最好，当时并无定论，所以只有先把当前位置保存起来，然后任

15、选一个方向。如果随后的搜索碰到死路，可以回到当前保存起来的位置，然后尝试另一个尚未搜索的方向 2.4程序流程图 2.5 源代码分析 见电子档 2.6测试与结果 3.校园导游咨询 3.1 数据结构设计 #define INT_MAX 10000 #define n 10 /定义全局变量 int costnn; /边的值 int shortestnn; /两点间的最短距离 int pathnn; /经过的景点 3.2 基本操作函数说明 void introduce(); /景点介绍 int shortestdistance(); /要查找的两景点的最短距离 void floyed(); /用flo

16、yed算法求两个景点的最短路径 void display(int i,int j); /打印两个景点的路径及最短距离3.3 程序设计内容与思路（1）用链接矩阵表示法创建一个图，并设计一个交互式界面（2）设计景点介绍界面，用switch语句（3）设计查找最短路径的算法，可用floyd算法（4）打印出两个景点之间的最短路径在该程序的设计中，先设计出main（）主函数，在屏幕上显示所要操作的界面，在main（）主函数中调用另外两个函数：void introduce（）和void shortestdistance（）。接下来再设计这两个函数，当然，在主函数调用前，要事先声明这两个函数3.4 源代码分析

17、见电子档3.5 测试与结果4.跳舞搭配问题 4.1 数据结构设计 Typedef struct QNode /定义链队结点类型 int num; struct QNode*next; QNode,*QueuePtr; Typedef stuuct /定义链队头指针类型 QueuePtr front； /队头指针 QueuePtr rear； /队尾指针 LinkQueue； 42基本操作函数说明 void sleep(clock-t wait); /延迟函数 void InitQ(LinkQueue &Q); /建立空队列 void EnQueue(LinkQueue &Q,int num);

18、 /入队列 void DeQueue(LinkQueue &Q,int &num); /出队列 void DestoryQueue(LinkQueue &Q); /删除队列 void PrintF(LinkQueue &F,int i); /打印第i首曲子是女队的情况 void PrintM(LinkQueue &M,int i); /打印第i首曲子是男队的情况 void check（int n）； /判断输入n是否合法4.3 设计思路和算法设计在算法中假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组中的各元素，并根据性别判断是进男队还是进女队。当这两队构造完成之后，依次将两队

19、的对头元素出对来配对舞伴，直到某队队列为空为止。此时，若某队仍有等待配对者，算法输出此队等待中的人数和队头的等待着的名字，它将是下一轮舞曲开始时第一个获得舞伴的人数据模型（逻辑结构）: 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。存储结构: 循环链表核心算法: 循环队列的入队，出队，判队满，判队空。输入数据: 男生人数、女生人数，歌曲数量输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号即可） 当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。 循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针f

20、ront和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1） 要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。（2） 将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3） 利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4） 循环队列的长度分别设为男女生的个数即可。（5） 在计算机终端输出的结果是：根据要求输出男生女生搭配情况。4.4程序流程图4.5源代码分析见电子档4.6

21、 测试与结果 5.利用栈实现表达式求值 5.1数据结构设计 typedef struct /运算符栈char *base;char *top;int stacksize;SqStackcha;typedef struct /运算数栈double *base;double *top;int stacksize;SqStackdou; 5.2 基本操作函数说明char gettop(sqstackcha &s); /取操作符栈顶元素double gettop(sqstackdou &s); /取操作数栈顶元素int precede(sqstackcha &s,char c); /比较字符c与操作符

22、栈顶元素的优先级void initstak(sqstackcha &s); /初始化操作符栈void initstak(sqstackdou &s); /初始化操作数栈double opterate(double a,char theta,double b); /对操作数a和b用操作符运行其结果void push(sqstackcha &s,char e); /操作符入栈char pop(sqstackcha &s,char e); /操作符出栈double pop(sqstackdou &s,double e);操作符出栈void initstack(sqstackcha &s)/初始化字符

23、型栈5.3设计内容与思路（1）设计主函数，包含界面设计和后缀表达式的算法设计。在此问题中，如果是单位操作数，处理会比较方便，对于多位的操作数，可以采用这样的处理思路：把包含后缀表达式的一个字符串由一个字符指针参数所指向，每次从该字符串中读入一个字符，若它是空格则不做任何处理，若它是运算符，则表明它的两个操作数已经在栈中，其中栈顶元素为运算符的后一个操作数，栈顶元素的前一个元素为运算符的前一个操作数，把它们弹出后进行相应的运算并保存在一个变量中。（2）设计函数，实现把输入的中缀表达式转化为后缀表达式5.4源代码分析见电子档5.5测试与结果四总结通过两周的学习和实践，解决实际问题，让我对数据结构有

24、了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C语言描绘出关键算法。以前我对数据结构（C语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这两周的学习让我对数据结构（C语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这

25、次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用C语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得