数据结构课程设计说明书讲解

1/1数据结构课程设计说明书讲解安徽理工高校

数据结构

课程设计说明书题目:一元多项式计算

院系：计算机科学与工程学院

专业班级：数字媒体13-1班

学号：2023303102

同学姓名：钱福琛

指导老师：梁兴柱

2023年1月9日

安徽理工高校课程设计（论文）任务书计算机科学与工程学院

2023年11月10日安徽理工高校课程设计（论文）成果评定表

名目

1问题描述

2功能描述

2.1课题要求

2.2软件格式规定

3设计2

3.1相关函数介绍说明

3.2主程序的流程基函数调用说明

4程序设计4

4.1多项式存储的实现

4.2加减乘除算法

4.2.1加法运算的实现

4.2.2减法运算的实现

4.2.3乘法运算的实现

4.2.4除法运算的实现

4.3函数调用关系图

5运行测试

1问题描述

1.1首先是确定结构化程序设计的流程图，利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块.

2功能描述

2.1课题要求

A.支持一元多项式的运算器

B.能够正确输入并显示输入多项式的每一项

C.要求将输入的多项式F（X），G(X)可进行加，减，乘，除运算，并显示结果

2.2软件格式规定

A．输入的形式:按程序菜单的数字选择输入，并按提示输入多项式。根据（系数指数）的格式进行输入并以输入（00）作为结束输入的掌握。

B.程序所能达到的功能:能够进行多项式的输入，显示，加，减，乘，除运算。

C.输出的形式:根据多项式的数学表达式的形式输出，形如：

F(x)=X^2+2X^3-2X^4-3X^3-X^1+10

3设计

3.1相关函数介绍说明

（1）程序定义的数据结构类型为线性表的链式存储结构类型变量：

typedefstructlinknode

（2）程序定义的其它函数：

linnode*Sort(linnode*S);

//多项式按指数从大到小排序

linnode*CreateList;

//创建多项式

VoidShowList(linnode*head);

//显示多项式

linnode*Copy(linnode*copy);

//拷贝多项式（由于做减法运算时会破坏原来输入的多项式）linnode*SearchList(linnode*head,intx);

//查找函数

Linnode*Mulr(linnode*s,linnode*p)

//用一个节点去乘与一个多项式（帮助除法运算）

Linnode*AddSame(linnode*head);

//和并多项式的同类项

linnode*Add(linnode*head1,linnode*head2);

//加法

linnode*Mul(linnode*head1,linnode*head2);

//乘法

linnode*Sub(linnode*head1,linnode*head2);

//减法

VoidDiv(linnode*head1,linnode*head2)

//除法

intmain

//主函数

3.2主程序的流程基函数调用说明

（1）主程序的简要流程图

图1主程序流程图

（2）各程序模块之间的层次（调用）关系

①输入模块“CreateList”，首先按提示逐项输入多项式的每一项，当接收到“00”时终止输入，此时调用“Sort”进行按指数降序排列后直接返回多项式的链表头指针。

②加法运算模块“Add”，首先将两个多项式连接成一个多项式，再调用“AddSame”函数进行合并连接后的多项式的同类项并返回头指针。

③减法运算程序模块“Sub()”，首先推断多项式1是否为空，不为空时调用“SearchList”进行查找操作，查找到的结果与多项式1作减法后删除多项式2中查找到的对应项。多项式2中剩余的项取反后连接到多项式1的尾部，再调用“AddSame”进行合并同类项操作并返回头指针。

④乘法运算程序模块“Mul()”，首先推断输入的多项式两个不为空时进行多项式相乘运算，并将结构存储在新创建的多项式中。再调用“AddSame”进行合并同类项后返回头指针。

⑥除法运算模块“Div”，首先推断第一个多项式的最高次数大于或等于其次多项式的最高次数，然后再用第一个多项式的第一项去除于其次个多项式的第一项，所得的商的第一项，然后调用“Mulr”用商的第一项去乘其次个多项式，用第一个多项式减去乘得的多项式，所得的差多项式再与其次个多项式的最高指数项推断。直到其次多项式的最高次数项大于与之推断的多项式时结束运算，并调用“ShowList”输出相应的结果。

⑥显示函数“ShowList”，首先调用“Sort”进行排序，再按格式输出多项式的每一项。

4程序设计

4.1多项式存储的实现

多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。依据所学数据结构，采纳线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为：

4.2加减乘除算法

在多项式运算的程序设计中，每一部分都会调用一些其它函数来帮助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘除运算的程序设计，其它函数的程序设计和详细调用关系请查看程序清单。

4.2.1加法运算的实现

加法计算还是比较简单实现的，将两个传递过来的多项式链表进行复制操作（加法运算会破坏原来两个链表的结构），再将复制出来的两链表进行连接操作，即将第一个多项式链表的尾指针next指向其次个链表的第一个节点，最终进行合并同类项操作。

图2加法运算原理图

对于加法运算我们并不用考虑多项式是否为空的状况，为空时连接后合并同类项处理后仍旧返回空的多项式。

4.2.2减法运算的实现

图3减法运算原理图

4.2.3乘法运算的实现

图4乘法运算原理图

4.2.4除法运算的实现

图5除法运算原理图

在程序设计时应留意:

由于在输入多项式的时候就调用了Sort函数进行降序排序，因此在除法运算时并不需要从新排序。

4.3函数调用关系图

此函数调用关系图主要描述了四则运算的实现、取反及实现各运算所要调用的函数，详情还请看程序清单。图6函数调用关系图

5运行测试

图7主界面效果图

main选择菜单

Add加法运算Sub减法运算Mul乘法运算Copy备份

CreateList创建Sort排序AddSame合并

AddSame合并

SearchList搜寻节点

Copy备份AddSame合并Div除法运算

Mulr

Negate取反

AddSame合并ShowList显示输出

Sort排序