实验一 一元多项式计算器 实验学时：2 实验类型：综合型 一、目的与任务 1．目的：掌握顺序表和单链表的存储特点及插入、删除等算法。 2．任务：灵活运用顺序表和单链表的相关算法实现一元多项式的计算。 二、内容、要求与安排方式 1．实验内容：设有一元多项式Am(x)和Bn(X)，编程实现多项式Am(x)和Bn(x)的加法、减法和乘法运算。其中多项式描述为： Am(x)=A0+A1x1+A2x2+A3x3+….+Amxm； Bn(x)=B0+B1x1+B2x2+B3x3+….+Bnxn。 2．输入和输出： （1）输入： 从键盘输入运算指令（相加、相减、相乘），根据运算指令进行相应运算； 从键盘输入两个多项式的系数和指数； 系数和指数采用int类型，运算结果不超出int取值范围。 （2）输出： 每种运算结果以多项式形式输出，要输出升幂和降幂两种情况。 结果多项式中无重复阶项、无零系数项，输出多项式时请采用如下易读形式（一元多项式，总变元为x）： x^4 - 3 x^2 + 5 3．实验要求： 实现一个简单的交互式界面，包括系统菜单、输入提示等。 多项式运算前首先判定多项式特点，根据多项式是否稀疏来选用合适的存储结构； 根据多项式不同的运算要求选择合适的存储结构； 上机编辑、调试出完整正确的程序，包括相加、相减、相乘运算。 4．实验安排方式： 在实验课前编写出完整程序，在实验课时进行调试； 每组1人，独立完成上机实验。 三、注意事项： 1．本实验内容涉及到链式存储结构，请理解链式存储的特点及指针的用法。 2．注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 3．请在实验报告中说明系统使用的主要数据结构。
【实现思路】
链表存储多项式；提取系数到线性表，用指数作为下标，牺牲空间换取时间完成计算，生成答案线性表，构建答案链表以下是各函数声明与主函数逻辑结构【实现方案】
c++链表线性表 //solve.h #include <bits/stdc++.h> using namespace std; #ifndef SOLVE_H_INCLUDED #define SOLVE_H_INCLUDED /** author:mmciel time:2019-5-14 07:26:19 word: 数据结构相关功能的实现：初始化、插入、删除、清空 */ static int OK = 1; static int NO = 0; //多项式结构 typedef struct{ int num; int expx; }Data; //链表结构 typedef struct LNode{ Data data; struct LNode * next; }LNODE,*List; //初始化链表 int InitList(List & L); //插入一个数据到链表 int InsertList(List & L, Data d); //删除一个节点 int DelList(List & L, Data d); //链表长度 int ListLength(List L); //链表清空 int ClearList(List & L); //链表销毁 int DestoryList(List & L); //链表打印，用于调试 int PrintList(List L); //菜单 void welcome(); //分隔输出 void printLine(); //整数转字符串 string tostring(int n); typedef struct{ int * num;//系数 int length; int listsize; }Line; //初始化顺序表 int InitLine(Line & L,int listlen); //插入顺序表 int InsertLine(Line & L,Data d); //删除顺序表 int DelLine(Line & L,Data d); //清空顺序表 int ClearLine(Line & L); //顺序表长度 int LineLength(Line & L); //顺序表销毁 int destoryLine(Line & L); #endif // SOLVE_H_INCLUDED //main.cpp /** author:mmciel time:2019-5-14 07:49:48 一元多项式计算器 完成三个运算 运算逻辑、数据处理逻辑、输出逻辑 */ #include <bits/stdc++.h> #include "solve.h" using namespace std; int order=-1; bool flag = true; List list1=NULL, list2=NULL;//多项式存储到链表 Line line1,line2;//系数的顺序表 List anslist = NULL,nlist = NULL;//结果临时存放 Line ansline;//结果系数的临时存放 int expx1 = 0,expx2 = 0;//获取list1 list2最高次幂 int status;//调试时使用的状态字 List Add(List list1,List list2); List Sub(List list1,List list2); List Mult(List list1,List list2); void Input(List &list1,List &list2); void PrintPolynomial(List temp);//打印多项式 bool DelPolynomial(List list1,List list2);//清空两个多项式 int getMaxExp(List temp);//获取最高次幂 List daozhi(List temp);//链表倒置、为了输出 int main(){ //1.创建两个多项式 2.打印两个多项式 //3.两个多项式相加 4.两个多项式相减 //5.两个多项式相乘 6.清空两个多项式 while(flag){ welcome(); cin>>order; switch(order){ case 1: Input(list1,list2); expx1 = getMaxExp(list1); expx2 = getMaxExp(list2); if(!expx1) expx1++; if(!expx2) expx2++; InitList(anslist); break; case 2: PrintPolynomial(list1);PrintPolynomial(list2); break; case 3: anslist = Add(list1,list2); PrintPolynomial(anslist); nlist = daozhi(anslist); PrintPolynomial(nlist); status = ClearList(anslist); break; case 4: anslist = Sub(list1,list2); PrintPolynomial(anslist); nlist = daozhi(anslist); PrintPolynomial(nlist); status = ClearList(anslist); break; case 5: anslist = Mult(list1,list2); PrintPolynomial(anslist); nlist = daozhi(anslist); PrintPolynomial(nlist); status = ClearList(anslist); break; case 6: DelPolynomial(list1,list2); break; default: flag = false; cout<<"退出..."<<endl; break; } } return 0; }