北邮数据结构上机 一元多项式

数据结构实验报告

实验名称： 实验1——线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期：

1．实验要求

实验目的： 熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作实现方法

培养使用线性表解决实际问题的能力

实验内容：

利用线性表实现一个一元多项式Polynomial; f(x)=a0+a1x+a2x2+a3x3+…+anxn 提示：Polynomial的结点结构如下： struct term {

float coef;\\\\系数 int expn;\\\\指数 }；

可以使用链表实现，也可以使用顺序表实现 具体要求如下：

能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减

能够计算一元多项式在x处的值 能够计算一元多项式的导数（选作） 能够进行一元多项式相乘（选作） 编写main ()函数测试算法的正确性

2. 程序分析

由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，

第1页

北京邮电大学信息与通信工程学院

那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。 本程序完成的主要功能：

1、输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。 2、多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。

3、多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。

4、多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。

5、多项式的乘法：根据输入信息八两多项式计算，并输出一个新的多项式。

2.1 存储结构

本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下： next …… coef1 exp1 next Coef2 exp2 next coefn expn next front 2.2 关键算法分析

1、多项式的输入：

自然语言描述：

1. 设置多项式的项数n；

2. 按照多项式的项数申请动态结构数组element *e=new element[n]存储多项式

的系数和指数；

3. 按照指数递增的次序输入各项的系数以及指数，分别存入coef和exp； 4. 再将输入的系数以及指数赋给每一个结点的coef和exp域； 5. 利用头插法将每个结点加入链表。 ·伪代码：

1. 输入项数n； 2. element *e=new element[n]; 3. 运用for循环，循环n次

3.1 element *e=new element[n];

3.2 cin>>e[i].exp; 3.3 cin>>e[i].coef; 3.4 return e;

4. 运用头插法将结点插入链表。 2、多项式的输出

·自然语言描述：

第2页

北京邮电大学信息与通信工程学院

1. 获取头结点；

2. 循环n-1次（n为多项式的项数）

2.1将指针的指向后移；

2.2依照多项式的各种情况，设置输出方式

2.2.1 系数为1且指数不为1和0，输出Xexpn+； 2.2.2 系数不为0且指数为0，输出（coef）+； 2.2.3 系数不为0且指数为1，输出（coef）X+；

2.2.4 系数不为0和1，指数不为0和1，输出(coef)X(expn)+；

3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。 源代码如下：

Node *p= GetFirst()->next; if(p==NULL) { cout<<0; } while(p) { if(p->data.exp==0) { cout<data.coef; } else { cout<data.coef<<\"X\"<data.exp; } p=p->next; if((p!=0)&&(p->data.coef>0)) { cout<<\"+\"; } }

3、多项式的相加相减

·自然语言描述：

1. 指针p和q分别指向a和b两个多项式的头结点的下一个节点； 2. 将结果多项式的项数置为0； 3. 只有p或q非空，进行以下循环：

3.1 申请一个term* 型的指针d，将其next域赋为NULL；进行判断：

1.3.1 如果p和q均非空

3.3.3.1 如果p和q的指数相等

将d的系数赋为p、q系数之和，指数不变，将p、q指向后移；

3.3.3.2 如果p->expn>q->expn

复制q到结果多项式（减法系数为q->coef的相反数）

3.3.3.3 如果p->expnexpn

第3页

北京邮电大学信息与通信工程学院

复制p到结果多项式

3.3.3.4 判断后将项数++，插入新节点d；

1.3.2 如果q为空，p仍存在，逐项将p复制到结果多项式。每进行一次，

项数++，p后移。

1.3.3 如果p为空，q仍存在，逐项将q复制到结果多项式（减法将系数

变为原来的相反数）。每进行一次，项数++，q后移。

3.2 返回结果多项式的项数

·代码描述：

1. 工作指针p、q初始化： Node *p_prior= GetFirst(); Node *p=p_prior->next;

Node *q=B.GetFirst()->next; 2、while(p&&q) { if(p->data.expdata.exp) { p_prior=p; p=p->next; } else if(p->data.exp>q->data.exp) { p_prior->next=q; p_prior=q; q=q->next; p_prior->next=p; } else{ p->data.coef+=q->data.coef; if(fabs(p->data.coef)<1e-7) { p_prior->next=p->next; delete p; p=p_prior->next; } else { p_prior=p; p=p_prior->next; } Node * temp=q; q=q->next; delete temp; } } if(q)

第4页

北京邮电大学信息与通信工程学院

p_prior->next=q;

B.GetFirst()->next=NULL; }

时间复杂度：O(n) 空间复杂度：O(2)

对于减法的实现在coef的前面乘以-1，在用加法的算法就行了。 while(q) { int i=-1; q->data.coef=i*q->data.coef; q=q->next; } q=B.GetFirst()->next; 4、计算在x处的值：

·自然语言描述：

1. 将工作指针指向多项式的第一项； 2. 将结果sum置为0；

3. 指针不为空，即进行循环：

3.1sum+=p->data.coef*pow(x,p->data.exp); 3.2 p=p->next;

4．返回sum；

· 伪代码描述：

1. Node *p= GetFirst()->next; 2. double sum=0; 3. while(p) sum+=p->data.coef*pow(x,p->data.exp); p=p->next;

4. cout<<\"在\"<时间复杂度：O(n) 空间复杂度：S(1) 5、求导数

1. 将指针指到多项式的第一项的结点：Node *p_prior= GetFirst(); 2. 循环n次

2.1 每项求导的系数为：p->data.coef*=p->data.exp;;指数为：p->data.exp-=1; 2.2 将新结点插入新链表； 2.3 指针p后移。

代码如下，注意常数项：

Node *p_prior= GetFirst(); Node *p=p_prior->next;

第5页

北京邮电大学信息与通信工程学院

int m=GetMax();

if(p->data.exp==0) //常数求导 {

p_prior->next=p->next; Node *temp=p; p=p->next; delete temp; }

while (p) {

p->data.coef*=p->data.exp; p->data.exp-=1; if(p->next==NULL) {

m=p->data.exp; }

p=p->next; }

时间复杂度：O(n) 空间复杂度：S(1)

6、两多项式的乘积：

1、建立三个动态结构数组存贮相乘两个多项式以及乘以后所得多项式的参数。 double * d1=new double[m+B.GetMax()+1]; double * d2=new double[m+B.GetMax()+1]; double * d3=new double[m+B.GetMax()+1]; 2、初始化后依次赋值 d1[i]=0;d2[i]=0;

for (int i=0;i<=m+B.GetMax();i++)

if (i==p->data.exp) //有这一指数项则在i的位置存储此项系数 d1[i]=p->data.coef; p=p->next; 3、赋给第三个

for (int i=0;i<=m+B.GetMax();i++) d3[i]=0; for (int j=0;j<=i;j++) //算法柯西乘法原理 d3[i]+=d1[j]*d2[i-j]; if (d3[i]!=0) //不为的就自增一项 n++; 4、导出

element *e3=new element[n]; for (int i=0,j=0;i<=m+B.GetMax();i++) //构造每一项

第6页

北京邮电大学信息与通信工程学院

{ if (d3[i]!=0) { e3[j].coef=d3[i]; e3[j].exp=i; j++; } }

时间复杂度：O(n) 空间复杂度：S(2)

2.3 其他

1.

3. 测试主函数流程：

开始 设置多项式 A的项数 进行A-B 的运算 按照A的项数动态申请 输出相减 的结果 结束 输出A 进行对A 求导数的运算 设置多项式 B的项数 输出求导 的结果 结束 按照B的项数动态申请 输入x的取值 输出B 计算A在x处的取值并输出 进行A+B 的运算 结束 输出相加 的结果add 第7页 求积输出结果 结束 结束 北京邮电大学信息与通信工程学院

测试条件：问题规模n的数量级为1

A多项式每项的系数和指数分别为：<1,1> <2,2>

B多项式每项的系数和指数分别为：<1,1> <2,2> <3,3> X的值为：2

运行出来的结果是：

第8页

北京邮电大学信息与通信工程学院

测试结论：通过测试，本程序具有的功能有：多项式的建立、多项式的输入与输出、多项式的相加及相减，多项式求导，多项式求值以及多项式求积。

4. 总结

1. 调试时出现的问题及解决的方法

① 输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的

结果。

② 相加相减操作：在刚开始的时候，只考虑了p、q指针均非空的情况，计算的结果

就出现了问题，但逐项的运算后，会出现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。 ③ 在插入结点的时候出现了一些问题，经查看是尾插法运用地并不熟练，后运用头插

法将结点插入链表中，编完程序后，又仔细学习了尾插法的操作。

2. 心得体会

通过本次实验，我熟悉了链表的相关操作，包括链表的建立、头插法；同时由于多项式的运算中会出现许多种不同的情况，在这方面也锻炼了我的思维严密性。在编写程序的过程中，编译的时候出现了一些错误，但都经过自己的钻研以及与同学探讨成功解决。

3. 下一步的改进

① 、输出窗口不够完美，加一个循环即可解决问题。 ② 、时间复杂度较大，程序运行慢。

源代码：

文件一 LinkList.h #include

第9页

北京邮电大学信息与通信工程学院

using namespace std;

template struct Node {

T data; //数据域 struct Node * next; //指针域 };

template class LinkList {

public:

LinkList(){front = new Node ; front->next = NULL;} //无参构造函数

LinkList(T a [], int n); //有参构造函数 ~LinkList(); //析构函数

Node * GetFirst(); //获取头结点地址 void PrintList(); //遍历线性表元素 int GetLength() ; //获取线性表的长度

Node * Get(int i); //获取线性表第i个位置上的元素结点地址 int Locate (T x); //查找线性表中值为x的元素，找到后返回其位置

void Insert (int i, T x); //在线性表的第i个位置上插入值为x的新元素

T Delete(int i); //删除线性表第i个元素，并将该元素返回 private:

Node * front; //头指针 };

template

LinkList::LinkList(T a [], int n) {

front = new Node ; front->next = NULL; for(int i=n-1;i>=0;i--) {

Node * s = new Node ; s->data = a[i];

s->next = front->next; front->next = s; }

第10页

北京邮电大学信息与通信工程学院

}

template

LinkList::~LinkList() //析构函数 {

Node * p = front; while (p) {

front = p; p = p->next; delete front; } }

template

Node * LinkList::GetFirst() {

return front; }

template

void LinkList:: PrintList() {

Node * p = front->next; while (p) {

cout<data<<\" \"; p = p->next; }

cout<template

int LinkList::GetLength() {

Node * p = front; int i=0; while(p) {

i++;

p=p->next; }

return i-1; }

template

Node * LinkList::Get(int i) {

第11页

北京邮电大学信息与通信工程学院

Node * p = front->next; int j = 1;

while ( p && j != i ) {

p = p->next; j++; }

return p; }

template

int LinkList::Locate (T x) { Node * p = front->next; int j=1; while (p) {

if (p->data == x) return j; p = p->next; j++; }

return -1; //若找不到，返回错误标识-1 }

template

void LinkList::Insert (int i, T x) {

Node * p = front; if(i!=1)

p=Get(i-1); if(p) {

Node * s=new Node ; s->data=x;

s->next=p->next; p->next=s; }

else throw\"插入位置错误\"; }

template

T LinkList::Delete(int i) {

Node * p = front;

if (i != 1) p = Get(i-1); //若不是在第一个位置插入，得到第i-1个元素的地址

Node * q = p->next;

第12页

北京邮电大学信息与通信工程学院

p->next = q->next; T x = q->data; delete q;

return x; }

文件二。。测试.cpp

// 一元多项式计算.cpp : 定义控制台应用程序的入口点。

#include \"stdafx.h\"

#include

#include \"LinkList.h\"

struct element {

double coef; int exp;

element(double c=0,int e=0):coef(c),exp(e){} };

class PoloyList:public LinkList {

public:

PoloyList(element data[],int n):LinkList(data,n){} int GetMax(); //获取最大项指数 void PrintList(); //多项式的输出 void Add(PoloyList & B); //求和 void Sub(PoloyList & B); //相减

void Cal(double x); //计算在x处的值 void Der(); //求导 PoloyList * Mul(PoloyList & B); //相乘 };

//获取最大项指数

int PoloyList:: GetMax() {

Node *p_prior= GetFirst(); Node *p=p_prior->next; if(p==NULL)

第13页

//构造函数 北京邮电大学信息与通信工程学院

return 0; else

while(p->next) {

p=p->next; }

return p->data.exp; }

//多项式的输出

void PoloyList::PrintList() {

Node *p= GetFirst()->next; if(p==NULL) {

cout<<0; }

while(p) {

if(p->data.exp==0) {

cout<data.coef; } else {

cout<data.coef<<\"X\"<data.exp; }

p=p->next;

if((p!=0)&&(p->data.coef>0)) {

cout<<\"+\"; } } }

//求和

void PoloyList::Add(PoloyList &B) {

Node *p_prior= GetFirst(); Node *p=p_prior->next;

Node *q=B.GetFirst()->next; while(p&&q) {

if(p->data.expdata.exp) {

p_prior=p;

第14页

北京邮电大学信息与通信工程学院

p=p->next; }

else if(p->data.exp>q->data.exp) {

p_prior->next=q; p_prior=q; q=q->next;

p_prior->next=p; } else{

p->data.coef+=q->data.coef; if(fabs(p->data.coef)<1e-7) {

p_prior->next=p->next; delete p;

p=p_prior->next; } else {

p_prior=p;

p=p_prior->next; }

Node * temp=q; q=q->next; delete temp; } } if(q)

p_prior->next=q;

B.GetFirst()->next=NULL; }

//相减

void PoloyList::Sub(PoloyList &B) {

Node *p_prior= GetFirst(); Node *p=p_prior->next;

Node *q=B.GetFirst()->next; while(q) {

int i=-1;

q->data.coef=i*q->data.coef; q=q->next; }

q=B.GetFirst()->next;

第15页

北京邮电大学信息与通信工程学院

while(p&&q) {

if(p->data.expdata.exp) {

p_prior=p; p=p->next; }

else if(p->data.exp>q->data.exp) {

p_prior->next=q; p_prior=q; q=q->next;

p_prior->next=p; } else{

p->data.coef+=q->data.coef; if(fabs(p->data.coef)<1e-7) {

p_prior->next=p->next; delete p;

p=p_prior->next; } else {

p_prior=p;

p=p_prior->next; }

Node * temp=q; q=q->next; delete temp; } } if(q)

p_prior->next=q;

B.GetFirst()->next=NULL; }

//计算在x处的值

void PoloyList::Cal(double x) {

Node *p= GetFirst()->next; double sum=0; while(p) {

sum+=p->data.coef*pow(x,p->data.exp);

第16页

北京邮电大学信息与通信工程学院

p=p->next; }

cout<<\"在\"<//求导

void PoloyList::Der() {

Node *p_prior= GetFirst(); Node *p=p_prior->next; int m=GetMax();

if(p->data.exp==0) //常数求导 {

p_prior->next=p->next; Node *temp=p; p=p->next; delete temp; }

while (p) {

p->data.coef*=p->data.exp; p->data.exp-=1; if(p->next==NULL) {

m=p->data.exp; }

p=p->next; } }

//相乘

PoloyList * PoloyList::Mul(PoloyList & B) {

Node *p_prior= GetFirst(); Node *p=p_prior->next;

Node *q=B.GetFirst()->next; int m=GetMax();

double * d1=new double[m+B.GetMax()+1]; double * d2=new double[m+B.GetMax()+1]; double * d3=new double[m+B.GetMax()+1]; for (int i=0;i<=m+B.GetMax();i++) {

d1[i]=0; d2[i]=0;

第17页

北京邮电大学信息与通信工程学院

}

for (int i=0;i<=m+B.GetMax();i++) {

if (i==p->data.exp) //有这一指数项则在i的位置存储此项系数

{

d1[i]=p->data.coef; p=p->next;

if (p==NULL) //一旦p为空就跳出循环,p所指的一项后面的项系数在前面已经设为 {

break; } } }

for (int i=0;i<=m+B.GetMax();i++) {

if (i==q->data.exp) {

d2[i]=q->data.coef; q=q->next; if (q==NULL) {

break; } } }

int n=0; //记录新二项式的项数 for (int i=0;i<=m+B.GetMax();i++) {

d3[i]=0;

for (int j=0;j<=i;j++) //算法柯西乘法原理 {

d3[i]+=d1[j]*d2[i-j]; }

if (d3[i]!=0) //不为的就自增一项 {

n++; } }

element *e3=new element[n];

for (int i=0,j=0;i<=m+B.GetMax();i++) //构造每一项 {

if (d3[i]!=0)

第18页

北京邮电大学信息与通信工程学院

{

e3[j].coef=d3[i]; e3[j].exp=i; j++; } }

PoloyList *C=new PoloyList(e3,n); //构造二项式对象 //释放动态空间 delete []d1; delete []d2; delete []d3; return C; }

element * Build(int &n,char *t) //多项式参数的输入 {

cout<<\"请输入第\"<>n;

cout<<\"请按升幂的次序输入\"<cout<<\"请输入第\"<>e[i].exp;

while(i!=0&&e[i].exp<=e[i-1].exp) {

cout<<\"请输入指数大于前一项的指数:\"; cin>>e[i].exp; }

cout<<\"第\"<>e[i].coef; while(e[i].coef==0) {

cout<<\"请输入非零系数: \"; cin>>e[i].coef; }

}

cout<第19页

北京邮电大学信息与通信工程学院

void main() {

int p,q;

element *e1=Build(p,\"1\"); element *e2=Build(q,\"2\"); PoloyList A(e1,p); PoloyList B(e2,q); cout<<\"f1(X)=\"; A.PrintList(); cout<cout<<\"f2(X)=\"; B.PrintList(); delete e1; e1=NULL; delete e2; e2=NULL;

cout<>n; switch(n) {

case 1: {

cout<<\"f1(X)+f2(X)=\"; A.Add(B);

A.PrintList(); break; } case 2: {

cout<<\"f1(X)-f2(X)=\"; A.Sub(B);

A.PrintList(); break; } case 3: {

double x;

cout<<\"输入x的值\"; cin>>x;

cout<<\"在\"<第20页

北京邮电大学信息与通信工程学院

}

cout<<\"f1(\"<A.Der();cout<<\"f`1(x)=\";A.PrintList();cout<cout<<\"f1(X)*f2(X) = \"; PoloyList *T=A.Mul(B); T->PrintList(); delete T;T=NULL; break; }

cout<cout<第21页

北京邮电大学信息与通信工程学院

第22页