1、课程设计说明书 NO.1 一元稀疏多项式简单计数器一元稀疏多项式简单计数器 1.1.课程设计的目的课程设计的目的 (1)通过对数据结构所学知识的综合运用，融会贯通课程中所学的理论知识，初步 掌握排序算法的比较等相关知识； (2)加深对数据结构的基本理论、基本知识和常用技术的理解； (3)提高分析问题的能力和实践能力，培养科学研究的独立工作能力。 2.2.设计方案论证设计方案论证 2.12.1设计思路设计思路 2.1.1 2.1.1 问题描述问题描述 一元稀疏多项式简单计数器 测试数据： （1）(2x+5x8-3.1x11)+(7-5x8+11x9) （2）(6x-3-x+4.4x2-1.2x9
2、)-(-6x-3+5.4x2+7.8x15) （3）(x+x2+x3)+0 （4）(x+x3)-(-x-x-3) 2.1.2 2.1.2 要求要求 （1） 输入并建立多项式 （2） 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2cn，en，其中 n 是 多项式的项数，ci，ei 分别为第 i 项的系数和指数。序列按指数降序排列。 （3） 多项式 a 和 b 相加，建立多项式 a+b，输出相加的多项式。 （4） 多项式 a 和 b 相减，建立多项式 a-b，输出相减的多项式。 用带头结点的单链表存储多项式。 2.1.3 2.1.3 需求分析需求分析 运行环境: Microsoft V
3、isual c+ 6.0 沈 阳 大 学 课程设计说明书 NO2 程序所实现的功能: 可以实现多项式的建立，以及两个多项式的相加、减，并且输出相加、减后所得的 结果。 2.22.2设计方法设计方法 2.2.1 2.2.1 设计分析设计分析 这个课程设计用来解决一元稀疏多项式简单计数器的问题。每个部分都有不同的 算法思想。 （1）建立多项式 一元多项式是由多个项的和组成的，将一元多项式的每快个项用一结点表示，该 结果中应包括该项的系数、该项的指数、指向下一项的指针，可以用线性表来依次输入 各项结点，从而完成多项式链表的建立，为了使原多项式各项顺序不变，故采用尾插法 建表。 （2）降幂输出多项式
4、我们可以先设一个幂指数 i 为可输入的最大幂指数，然后从首元结点开始顺次查询 每一结点的指数和 i，若相等则输出该结点，否则，i-,继续从首元结点开始查询，重 复上述过程，直到 i 为可输入的最小幂指数。这样，就按指数降幂输出了多项式。 多项式的项数统计可以通过头结点的 next 来实现，若非空，count+,直到结点的指针 域为空，这样，count 就统计出了项数。 （3）多项式相加 多项式的相加过程，其实就是相同指数的项的系数相加，不同指数的项复制到和 多项式中，将结果用降幂输出函数输出。 （4）多项式相减 多项式的相减过程，其实就是相同指数的项的系数相减，对于不同指数的项，若 是被减多项式，则将该结点复制输出，若是减多项式，则将该结点的系数变为原系数的 相反数输出，将结果用降幂输出函数输出。 沈 阳 大 学 课程设计说明书 NO.3 2.2.22.2.2 功能模块功能模块图图 图 1 2.2.32.2.3 模块划分模块划分 (1) 带头结点的多项式的
