一元多项式的计算课程设计报告.docVIP

本科课程设计（报告）

数据结构课程设计

一元多项式的计算

1.问题描述：

将多个多项式输入并存储在内存中，然后对多项式进行加，减，数乘等运算。

2.程序结构（程序中的函数调用关系图）

voidMenu(polynomial*L);//菜单

voidInitPolynomial(polynomial*L);//初始化多项式

voidIPolynomial(polynomial*L);//输入多项式函数

voidCPolynomial(polynomial*L);//多项式计算函数

voidLPolynomial(polynomial*L);//显示多项式函数

voidQPolynomial(polynomial*L);//退出

voidsort(node*L);//按指数升幂排列并合并同类项

voidout(headL);//输出一个多项式

intmain()//主函数

主函数

主函数

main

输入多项式函数

IPolynomial

菜单函数

Menu

显示多项式函数

LPolynomial

计算多项式函数

CPolynomial

退出函数

QPolynomial

输出一个多项式函数

out

排序合并同类项函数

sort

排序合并同类项函数

sort

输出一个多项式函数

out

输出一个多项式函数

out

程序中各函数原型和函数功能描述

voidMenu(polynomial*L);//菜单

voidInitPolynomial(polynomial*L);//初始化多项式

voidIPolynomial(polynomial*L);//输入多项式函数

voidCPolynomial(polynomial*L);//多项式计算函数

voidLPolynomial(polynomial*L);//显示多项式函数

voidQPolynomial(polynomial*L);//退出

voidsort(node*L);//按指数升幂排列并合并同类项

voidout(headL);//输出一个多项式

intmain()//主函数

主要算法及数据结构描述（算法可用伪代码或流程图描述）

主要算法描述：

输入多项时的录入算法:

利用cin/cin.ignore()语句进行录入

当输入“f=3,0-7,46,50,-1”时，cin一个char变量name，系统把f赋给name,利用cin.ignore()语句，指针在输入流中前进一位跳过“=”。

开始循环：使用cin语句录入一个double型变量，系统吧3赋值给变量,利用cin.ignore()语句，指针在输入流中前进一位跳过“，”，再次利用cin语句录入一个int变量，系统把0赋给变量。此时创造多项式的其中一项的节点(node类型)，并使用头插法插入到多项式中。

直到输入的一项系数为0指数为-1

最后把得到的多项式用sort函数按升幂排列并合并同类项加入到多项式数组中，多项式数目加一

令多项式升幂排序并合并同类项的算法：

添加一个头节点。把链表分成已排序部分和未排序不分，利用直接插入排序的方法进行排序。若出现有可以合并同类的情况则指数不变系数相加。

多项式的计算

以字符串的方式输入多项式计算表达式。扫描整串字符把算术符号赋给字符变量symbol。按照symbol的不同进行不同的运算。

加法

如输入“h=f+g”

先创建一个新的多项式的链表，获取的多项式函数名“h”分别找到加号前后对应的多项式在多项式数组中的位置，把两多项式的每一项复制并用头插法插入到新的多项式中，然后进行排序和合并同类项。最后加入到多项式数组中，多项式数目加一。

减法

如输入“k=f-g”

先创建一个新的多项式的链表，获取的多项式函数名“k”分别找到减号前后对应的多项式在多项式数组中的位置，把被减数多项式的每一项复制并用头插法插入到新的多项式中，把减数的每一项复制，系数取相反数用头插法插入。然后进行排序和合并同类项。最后加入到多项式数组中，多项式数目加一。

数乘

如输入“j=33*f”或“j=f*33

先创建一个新的多项式的链表，获取的多项式函数名“j”

确认“*”所在的位置

然后通过“*”前面字符的asscii码确认数字在乘号前面还是后面。反复利用

num=10*num+当前数字

把在字符串中的数字转化的整数保存在整型变量num里面。

找到被乘多项式，复制每一项，把每一项的系数乘以num，利用头插法插入到新的多项式中然后进行排序和合并同类项。最后加入到多项式数组中，多项式数目加一。

数据结构描述：

每个多项式用单链表来存储：头节点包含多项式的函数名并指向多项式的第一项

typedefstructhead//头节点3