多项式的简单运算数据结构课程设计.docVIP

PAGE PAGE 10 一、课程设计目的 《数据结构》是计算机专业的专业基础课，是一门实践性很强的课程，学生通过理论学习，并在完成每章后面的一些小程序后，理解了数据结构的基本概念，掌握了一些基本的编程技术，但仅有这一方面的训练还是很不够的。全面、严格的训练，是学好该课程的一个不可缺少的组成部分。课程设计对于提高学生用学到的书本知识解决实际问题，培养实际工作所需要的动手能力，对于提高以科学理论和工程上的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用。通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计要求 《数据结构课程设计》则要培养、训练学生选用合适的数据结构并运用程序设计语言（C/C++）编写质量高的应用程序。并建立初步评价算法程序的能力。为编译技术、操作系统、数据库及算法设计与分析等后继课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础 重点和难点： 　　1. 针对具体问题如何选择或设计合适的数据结构； 　　2. 如何根据一定的存储策略实现数据的存储表示； 　　3. 基于上述数据结构设计并实现完成具体要求的算法； 　　4. 对算法的时间性能进行分析。 针对每一个设计题目写出 1. 问题分析和任务定义： 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2. 逻辑设计： 对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图； 3. 详细设计： 定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； 4. 程序编码： 把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5. 程序调试与测试： 采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 三、题目是“用C语言实现一元多项式的相加相减和相乘” 1. 问题分析和任务定义： 用单链表的结构来存储多项式的信息是合适的。首先，一元多项式是必须在运行时动态决定创建的，单链表的动态分配内存空间能够很好的解决这个问题，从而避免了空间上浪费。其次，对于多项式的运算是以其每个节点为单位进行的，其排列可以根据多项式各个项式的指数的不同，由高到低排列，其中对于指数相同的项进行系数的归并，是加减法的运算基础。 2.逻辑设计： 一元多项式的每个项都有2个重要数据域,一是 系数 二是 指数 ,由于考虑到用链表的存储结构故而还要设计下一个节点的指针域 ,从而节点的结构体就这样形成了。 在创建链表时,为了便于对新开辟的节点进行赋值,所以在内存中开辟float 系数，int 指数 的暂存单元，它们连续从终端接受数据，并且覆盖上一次的数据，从而保证了输入的连续性。 链表在创建过程中以什么作为结束链表的创建的标志？这很重要，考虑到系数为0 ，该节点就没有意义，故而链表结束创建的标志 是 0 0，这样的节点会在插入的过程中自动删除。 3.详细设计： 定义节点 typedef struct node //定义节点类型 { float coef; int expn; struct node * next; }PLOY; 创建链表 void insert(PLOY *head,PLOY *inpt)； PLOY *creat(char ch)； //char ch 中的ch 则是多项式的字符标志，如f,g等，传入字符后，接下来就为其函数内的暂存单元赋数值，接着将创建的节点，调用insert 函数，将节点插入链表，继而返回链表的头指针 输出链表 void print(PLOY *fun) //此函数是根据实际的输出格式，对链表的信息进行加工后输出，由于考虑到如果系数为正，直接输出就会缺少‘+’号，而如果该系数为正且系链表的第一项就省略，另外就是，如果系数的绝对值为 1，就可以省略系数 1 ,直接输出符号 链表的加操作 PLOY *addPLOY(PLOY *head,PLOY *p