1、 课程设计报告课程设计报告 一元多项式计算一元多项式计算 VSVS 迷宫求解迷宫求解 系系 别：别： 专业年级：专业年级： 学生姓名：学生姓名： 学学 号：号： 任课老师：任课老师： 二二 一一 二二 年年 三三 月月 一、题目内容描述一、题目内容描述 （一） 、（一） 、实验二实验二 一元多项式计算一元多项式计算* 1、任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式 的相加、相减、相乘，并将结果输出； 2、在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以 使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提 出算法的改进方法； （二） 、（二
2、） 、实验四实验四 迷宫求解迷宫求解 1、任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走 出迷宫的路径，并将路径输出； 2、要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程 图） 、源程序、 测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。 二、解题分析二、解题分析 （一） 、一元多项式计算分析：（一） 、一元多项式计算分析： 1 1、一元稀疏多项式简单计算器的功能是：、一元稀疏多项式简单计算器的功能是： 1.1 输入并建立多项式； 1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,cn,en, 其中 n 是多项式的项数，ci 和
3、ei 分别是第 i 项的系数和指数，序列按 指数降序排列； 1.3 求多项式 a、b 的导函数； 1.4 计算多项式在 x 处的值； 1.5 多项式 a 和 b 相加，建立多项式 a+b； 1.6 多项式 a 和 b 相减，建立多项式 a-b。 2 2、设计思路、设计思路: : 2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3 利用链表实现队列的构造。 每次输入一项的系数和指数， 可以输出构 造的一元多项式 2.4 演示程序以用户和计算机的对话方式执行，即在计算机终站上显示 “提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令； 最后根
4、据相应的输入数据（滤去输入中的非法字符）建立的多项式以及 多项式相加的运行结果在屏幕上显示。多项式显示的格式为： c1xe1+c2xe2+cnxen 3 3、设计思路分析设计思路分析： 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式， 在这里采用链表的方式存储链表，所以我将结点结构体定义为： 序数 coef 指数 expn 指针域 next 运用尾插法建立两条单链表，以单链表 polyn p 和 polyn h 分别表示两个一 元多项式 a 和 b，a+b 的求和运算等同于单链表的插入问题（将单链表 polyn p 中的结点插入到单链表 polyn h 中），因此“和多项式”中的
5、结点无须另 生成。 为了实现处理，设 p、q 分别指向单链表 polya 和 polyb 的当前项，比 较 p、q 结点的指数项，由此得到下列运算规则： 若 p-expnexpn， 则结点 p 所指的结点应是“和多项式”中的一 项，令指针 p 后移。 若 p-expn=q-expn，则将两个结点中的系数相加，当和不为 0 时修 改结点 p 的系数。 若 p-expnq-expn， 则结点 q 所指的结点应是“和多项式”中的一 项，将结点 q 插入在结点 p 之前，且令指针 q 在原来的链表上后移。 （二） 、迷宫求解分析：（二） 、迷宫求解分析： 1、 迷宫形状由 0 表示可通过，用 1 表示
6、是障碍。为方便用 0,1 输入。并把 迷宫图形保存在二维数组 grid 中。而打印出的图形中 0表示能过1表示 障碍。 2、 对探索过的位置加以标记，输入起点终点后可由相应函数来完成搜索。 到目的点就可退出该调用程序。把每步路径保存到二维数组中，通过反向进行退 步可把完整的路径保存在相应结构体数组内， 通过标记的路径可将串作相应的改 变就能输出的带路径的图。 3、根据二维字符数组和加标记的位置坐标，输出迷宫的图形。 4、 该程序在获取迷宫图结构后， 可对迷宫任意入口到出口的路线进行搜索， 主要由广度优先搜索完成该操作。它可以是 30 以内大小的迷宫，有自行提供的 迷宫图，本课程设计是以二维数组作为迷宫的存储结构。 而广度优先搜索用的队 列一步一步完成的，从而找到的是最短路径，并能输出打印。 三、所用数据结构的描述（用伪代码）三、所用数据结构的描述（用伪代码） （一） 、一元多项式计算：（一） 、一元多项式计算： 1 1、元素类型、结点类型和指针类型：、元素类型、结点类型和指针
