课程设计说明书 NO.1
用链表实现一元多项式计算器 1 课程设计的目的 1.本次课程设计的主要目的是设计一个一元多项式简单计算器，熟悉掌握一元多项式在链式存储结构上的实现，能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入并体会两种存储结构各自的优缺点和适用性； 2.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技 4.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5.加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。 2 设计方案论证 2.1 课程设计方案 2.1.1问题描述:设计一个一元多项式简单计算器 基本要求:一元多项式简单计算器的基本功能是: （1）输入并建立多项式 （2）输出多项式的类数学表达式，如x^15-8x^7-14（序列按指数降序排列） （3）计算多项式在x处的值 （4）求多项式a的导函数a’ （5）多项式a和b相加，建立多项式a+b； （6）多项式a和b相减，建立多项式a-b； 2.1.2设计思路 设计中用带头结点的单链表存储一元多项式，多项式的项数存放在头结点；演示程序 用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”后，由用户在键盘上输入多项式
沈 阳 大 学 课程设计说明书 NO.2
的项数及各项的系数和指数，然后进行相加，相减运算，运算根据一元多项式相加相减的运算规则进行； 对于两个一元多项式中所有指数相同的项，对应指数相加减，若其结果不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去，复抄时应比较相应的指数值的大小，保证多项式序列的升序排列。 程序中一共定义了两种形式的数据结构，均为顺序存储结构，用带表头结点的单链表存储多项式，多项式的项数存放在头结点中 ： （1）多项式的各项定义如下 { int coef,exp; struct node *next; }JD *p; p 为 JD 结构体类型，含有三个部分，指向多项式系数的p->coef ，指向多项式指数的p->exp ,还有指向下一个多项式的指针p->next,用单链表的形式存储; （2）头结点定义如下 typedef struct hhead { int num; struct node *head; }HD *h; h 为 HD 结构体类型,含有两个部分,用于存储多项式项数的h->head ,指向多项式第一项的指针h->head typedef struct node 2.1.3 设计方法 本程序的特点是主要运用指针数组、结构体和链表等算法完成程序。其中在建立链表的时候用数组指针，然后又通过指针数组完成多项式的创建。
沈 阳 大 学 课程设计说明书 NO.3
（1）指针数组 一个数组，若其元素均为指针类型数据，称为指针数组，也就是说，指针数组的每一个元素都相当于一个指针变量。 一维指针数组的定义形式为：类型名*数组名[数组长度]； 因为指针数组比较适合用来指向若干个字符串，使字符串处理更加方便更加灵活。因此可以分别定义一些字符串，然后用指针数组中的元素分别指向各字符串。如果想对字符串排序，不必改动字符串的位置，只需改动指针数组中各元素的指向（即改变各元素的值，这些值都是各字符串的首地址）。这样，各字符串的长度可以不同，而且移动指针变量的值（地址）要比移动字符串所花的时间要少得多。 （2）结构体 当许多项都与某一项相关联时（如本程序：多项式的项数，项的系数和指数都与某多项式的名称有关联），如果将项数，系数，指数分别定义为互相独立的简单变量，则难以反映他们之间的关系，于是便利用数据结构中的结构体把他们组织成一个组合项，这种方法相当于高级语言的“记录”。 其中，声明一个结构体类型的一般形式为： Struct 结构体名 {成员表列}； 花括号内是该结构体中的各个成员，由他们组成一个结构体。其中，对各个成员都应进行类型声明，即： 类型名 成员名； （3）线性链表 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这存储单元可以是连续的，也可以是不连续的）。用线性链表表示线性表的时候，数据元素之间的逻辑关系是由结点中的指针指示的。也就是说，指针为数据元素中间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求相邻。由此，这种存储结构为非顺序映像或链式映像。
沈 阳 大 学 课程设计说明书 NO.4
2.1.4 模块功能说明 Void main() //主函数 { //首先需要根据需要进入相应的功能函数 1-------函数求值 { HD *typeinput() //首先调用“输入”函数，定义头结点指针h，多项式指针p，输入多项式有关的信息，存储到两个指针中，返回指向多项式的头结点h HD *arrange(HD *h) //调用排序函数，定义形参h，从上一个函数中得到h的有关信息，将信息传给p，通过对指数的大小进行比较，从而对多项式按指数从小到大排序，返回头指针h void output(HD *h) //输出函数，得到上一个函数中的实参h，将排序后的多项式输出，无返回值 void valueoutput(HD *h) //求值函数，形参h，得到实参后，输入x的值，对多项式求值，然后输出，无返回值 HD *daoshu(HD *h) //求导函数，形参h，得到实参h后，把信息传给指针p，调出多项式的信息后对系数和指数进行修改，达到求导的目的，返回头结点指针 void output(HD *h) //再次调用输出函数，将求导后的多项式输出 } 2--------多项式相加 { void PP() //相加调用函数，定义多个指向多项式的指针*ha,*hb,*ha1,*hb1，还需要调用三个函数，HD *typeinput() HD *arrange(HD *h) void output(HD *h) 达到输入两
沈 阳 大 学 课程设计说明书 NO.5
个多项式的信息后排序，输出，把头指针分别给ha，hb { void plus(HD *ha,HD *hb) //相加函数，调用此函数，接受上一个函数传递的指针，进行相加运算，把相加的结果再传给ha，然后回到void PP() 函数中去 void output(HD *h) //将相加的结果输出 } } 3--------多项式相减 { void SS() //相减调用函数，同上面的相加函数一样，输入，排序输出后 ，将第二个多项式的所有项的系数变成他的相反数，然后进行相加运算 { void substract(HD *ha,HD *hb) //相减函数 （这部分与上面的运行顺序一样，省去。。。。。。。） } } } 程序运行时只能在一个功能中进行，若想运行其他功能，需要重新启动程序后在运行 2.1.5程序设计的功能框图 （1）程序的基本功能： ①建立多项式 ②对多项式求值
沈 阳 大 学