实习报告
题目：设计一个一元稀疏多项式计算器
班级: 姓名 学号_________完成日期：__
一、课程题目
一元稀疏多项式计算器
二、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1 输入并建立多项式；
1.2 输出多项式，输出形式为整数序列：n ，c1,e1,c2,e2, „„„cn,en,
其中n 是多项式的项数，ci 和ei 分别是第i 项的系数和指数，序列按指
数降序排列；
1.3 求多项式a 、b 的导函数；
1.4 计算多项式在x 处的值；
1.5多项式a 和b 相加，建立多项式a+b；
1.6 多项式a 和b 相减，建立多项式a-b 。
2、设计思路:
2.1 定义线性表的动态分配顺序存储结构；
2.2 建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构
造的一元多项式
3、测试数据：
（1）、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);
（2）、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15
)=(-7.8x^15-1.2x^9+12x^-3-x);
（3）、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);
（4）、(x+x^3)+(-x-x^3)=0;
（5）、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);
（6）、(x+x^2+x^3)+0=x+x^2+x^3.
三、概要设计
1. 有序表的抽象数据类型定义为：
ADT List{
数据对象：D={ai | ai ∈R,i=1,2,…,n,n ≧0}
数据关系：R1={| ai-1, a i ∈D, ai-1,
基本操作：
InitList()
操作结果：构造一个空的有序表L 。
DestroyList(L)
初始条件：有序表L 已存在。
操作结果：销毁有序表L 。
ListLength(L)
初始条件：有序表L 已存在。
操作结果：返回有序表L 的长度。
ClearList( L )
初始条件：有序表L 已存在。
操作结果：清空链表内容。
Ins_before ( N,N )
初始条件：有序表L 已存在。
操作结果：插入节点到链表。
} ADT OrderedList
2. 多项式的抽象数据类型定义为：
ADT Poly {
数据对象：D={ai |ai 为实数，i=1，2，…，n }
数据关系：R1={}
基本操作：
CreatePoly( L,N )
初始条件：N 为节点，L 为有序表。
操作结果：将N 插入多项式的适当位置。
GetPoly( L )
操作结果：将用户输入转换为节点。
PrintPoly( L )
初始条件：多项式L 已存在。
操作结果：显示多项式。
AddPoly( L_1,L_2,L_add )
初始条件：多项式L_1,L_2,L_add已存在。
操作结果：生成L_1,L_2之和的多项式L_add
DiffPoly( L ,L_diff)
初始条件：多项式L ,L_diff已存在。
操作结果：生成L 的导数多项式L_add。
AlterPoly( L )
初始条件：多项式L 已存在。
操作结果：将L 多项式取相反数。
}ADT Poly、
三、详细设计
1、Constant.h
#ifndef __constant__
#define __constant__
#include
#include
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#endif
2、Polynt.h
#include"constant.h"
typedef struct elemType{
float coef;//系数
int expn;//指数
}ElemType;
typedef struct node{
ElemType data; //指向结点元素的值
struct node *next; //后继
}Node,*Polyn; //结点类型，指针类型
typedef struct{
Node *head;
Node *tail;
}List;
Status MakeNode(Polyn &p,ElemType e); //分配由p 指向的数据
元素为e 、后继为“空”的结点
Status InitList(List &L); //构造链表
Status DestroyList(List &L); //销毁线性表
void Insert(List &L,Polyn s); //将s 指向的结点插
入L 的最后一个结点
void Insbefore(Polyn p,Polyn q);
Status CreatPolyn(List &polynomial,int m); //创建一
个一元多项式polynomial ，并输入m 项的指数和系数
void PrintPolyn(List L); //打印输出一元多
项式
void AlterPoly(List L); //减法
void AddPolyn(List L1,List L2,List &L3); //
多项式加法
3、Polyn.cpp
#include"Polynt.h"
Status MakeNode(Polyn &p,ElemType e)
{//分配由p 指向的数据元素为e 、后继为“空”的结点
p=(Polyn)malloc(sizeof(Node));
p->data.coef=e.coef;
p->data.expn=e.expn;
p->next=NULL;
return OK;
}
Status InitList(List &L)
{//初始化链表
ElemType e;
Polyn p;
e.coef = ' ';
e.expn = ' ';
MakeNode(p,e);
L.head = p;
L.tail=p;
return OK;
}
Status DestroyList(List &L)
{//销毁链表
Polyn p,q;
if(L.head==L.tail) {free(L.head);L.head=L.tail=NULL;return OK;}
p=L.head->next;
while(!p){
q=p->next;
free(p);
p=q;}
L.head=L.tail=NULL;
return OK;
}
void Insert(List &L,Polyn s)
{
if(L.head->next ==NULL)
{
L.head->next =s;
s->next =NULL;
L.tail = s;
}
else{
if(L.head->next!=NULL && s->data.expn>L.head->next->data.expn)
{s->next=L.head->next;L.head->next=s; return;}
if(L.tail->data.expn>s->data.expn)
{L.tail->next=s; L.tail=s;return;}
for (Polyn p = L.head->next; p!=NULL;p = p->next )
{
if (s->data.expn== p->data.expn)
{
p->data.coef+=s->data.coef;
free(s);
return;
}
else if ( p->data.expn>s->data.expn &&
p->next->data.expndata.expn)
{
s->next=p->next;p->next=s;
return;
}
}
}
}
Status CreatPolyn(List &polynomial,int m)
{//创建一个一元多项式polynomial ，并输入m 项的指数和系数
ElemType e;
Polyn p;
for(int i=0;i
{
scanf("%g,%d",&e.coef,&e.expn);
MakeNode(p,e);
Insert(polynomial,p);}
polynomial.tail=p;
return OK;
}
void PrintPolyn(List L)
{
Polyn p;
if(L.head==L.tail)
printf("0");
else
{
p=L.head->next;
while(p!=NULL)
{
if(p==L.head->next)
{
if(p->data.coef>0)
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else if(p->data.coef
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else
{printf(" ");}
p=p->next;
}
else if(p!=L.head->next && p!=NULL)
{
if(p->data.coef>0)
{
if(p->data.expn!=0)
{printf("+%gx^%d",p->data.coef,p->data.expn);}
else{printf("+%g",p->data.coef);}
}
else if(p->data.coef
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else
{printf(" ");}
p=p->next;
}
else
return;
}
}
}
void AlterPoly(List L)
{
for(Polyn p=L.head->next;p!=NULL;p=p->next)
p->data.coef*=-1;
}
void AddPolyn(List L1,List L2,List &L3)
{
Polyn p1,p2,p3;
p1=L1.head->next;
p2=L2.head->next;
while(p1!=NULL && p2!=NULL)
{
if(p1->data.expn>p2->data.expn)
{
MakeNode(p3,p1->data);
Insert(L3,p3);
p1=p1->next;
}
else if(p1->data.expndata.expn)
{
MakeNode(p3,p2->data);
Insert(L3,p3);
p2=p2->next;
}
else if(p1->data.expn==p2->data.expn)
{
MakeNode(p3,p2->data);
p3->data.coef=p1->data.coef+p2->data.coef;
p3->data.expn=p1->data.expn;
Insert(L3,p3);
p1=p1->next;p2=p2->next;
}
}
if(p1==NULL && p2!=NULL)
{
while(p2!=NULL){
MakeNode(p3,p2->data);
Insert(L3,p3);
p2=p2->next;
}
}
else if(p2==NULL && p1!=NULL)
{
while(p1!=NULL){
MakeNode(p3,p1->data);
Insert(L3,p3);
p1=p1->next;
}
}
}
4、main.cpp
#include"Polynt.h"
#include
#include
void main()
{
system("cls");
printf("*********************************************************
***\n");
printf(" 欢迎使用一元稀疏多项式计算 \n");
printf("*********************************************************
***\n");
printf("1、创建多项式A 2、创建多项式B 3、相加 4、相减 5、退出
\n");
List polynomialA,polynomialB,polynomialC;
InitList(polynomialA); InitList(polynomialB); InitList(polynomialC);
char poly;
int m;int n=1;
for(;;)
{
printf("请输入指令:");
poly=getchar();
switch(poly)
{
case'1': //创建多项式A printf("请输入多项式A 的项数：");
scanf("%d",&m);
printf("\n请 输 入 多 项 式 A：");
CreatPolyn(polynomialA,m);
printf("\n多项式A 是：");
PrintPolyn(polynomialA);
printf("\n");
break;
case'2': //创建多项式B printf("请输入多项式B 的项数：");
scanf("%d",&m);
printf("\n请 输 入 多 项 式 B：");
CreatPolyn(polynomialB,m);
printf("\n多项式B 是：");
PrintPolyn(polynomialB);
printf("\n");
break;
case'3': //加法
printf("结果是:");
AddPolyn(polynomialA,polynomialB,polynomialC);
PrintPolyn(polynomialC);
printf("\n");
break;
case'4': //减法
printf("结果是:");
AlterPoly(polynomialB);
DestroyList(polynomialC);
InitList(polynomialC);
AddPolyn(polynomialA,polynomialB,polynomialC);
PrintPolyn(polynomialC);
} } printf("\n"); break; case'5': DestroyList(polynomialA); //退出 DestroyList(polynomialB); DestroyList(polynomialC); return; } poly=getchar(); if(poly==5) break;
实习报告
题目：设计一个一元稀疏多项式计算器
班级: 姓名 学号_________完成日期：__
一、课程题目
一元稀疏多项式计算器
二、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1 输入并建立多项式；
1.2 输出多项式，输出形式为整数序列：n ，c1,e1,c2,e2, „„„cn,en,
其中n 是多项式的项数，ci 和ei 分别是第i 项的系数和指数，序列按指
数降序排列；
1.3 求多项式a 、b 的导函数；
1.4 计算多项式在x 处的值；
1.5多项式a 和b 相加，建立多项式a+b；
1.6 多项式a 和b 相减，建立多项式a-b 。
2、设计思路:
2.1 定义线性表的动态分配顺序存储结构；
2.2 建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构
造的一元多项式
3、测试数据：
（1）、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);
（2）、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15
)=(-7.8x^15-1.2x^9+12x^-3-x);
（3）、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);
（4）、(x+x^3)+(-x-x^3)=0;
（5）、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);
（6）、(x+x^2+x^3)+0=x+x^2+x^3.
三、概要设计
1. 有序表的抽象数据类型定义为：
ADT List{
数据对象：D={ai | ai ∈R,i=1,2,…,n,n ≧0}
数据关系：R1={| ai-1, a i ∈D, ai-1,
基本操作：
InitList()
操作结果：构造一个空的有序表L 。
DestroyList(L)
初始条件：有序表L 已存在。
操作结果：销毁有序表L 。
ListLength(L)
初始条件：有序表L 已存在。
操作结果：返回有序表L 的长度。
ClearList( L )
初始条件：有序表L 已存在。
操作结果：清空链表内容。
Ins_before ( N,N )
初始条件：有序表L 已存在。
操作结果：插入节点到链表。
} ADT OrderedList
2. 多项式的抽象数据类型定义为：
ADT Poly {
数据对象：D={ai |ai 为实数，i=1，2，…，n }
数据关系：R1={}
基本操作：
CreatePoly( L,N )
初始条件：N 为节点，L 为有序表。
操作结果：将N 插入多项式的适当位置。
GetPoly( L )
操作结果：将用户输入转换为节点。
PrintPoly( L )
初始条件：多项式L 已存在。
操作结果：显示多项式。
AddPoly( L_1,L_2,L_add )
初始条件：多项式L_1,L_2,L_add已存在。
操作结果：生成L_1,L_2之和的多项式L_add
DiffPoly( L ,L_diff)
初始条件：多项式L ,L_diff已存在。
操作结果：生成L 的导数多项式L_add。
AlterPoly( L )
初始条件：多项式L 已存在。
操作结果：将L 多项式取相反数。
}ADT Poly、
三、详细设计
1、Constant.h
#ifndef __constant__
#define __constant__
#include
#include
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#endif
2、Polynt.h
#include"constant.h"
typedef struct elemType{
float coef;//系数
int expn;//指数
}ElemType;
typedef struct node{
ElemType data; //指向结点元素的值
struct node *next; //后继
}Node,*Polyn; //结点类型，指针类型
typedef struct{
Node *head;
Node *tail;
}List;
Status MakeNode(Polyn &p,ElemType e); //分配由p 指向的数据
元素为e 、后继为“空”的结点
Status InitList(List &L); //构造链表
Status DestroyList(List &L); //销毁线性表
void Insert(List &L,Polyn s); //将s 指向的结点插
入L 的最后一个结点
void Insbefore(Polyn p,Polyn q);
Status CreatPolyn(List &polynomial,int m); //创建一
个一元多项式polynomial ，并输入m 项的指数和系数
void PrintPolyn(List L); //打印输出一元多
项式
void AlterPoly(List L); //减法
void AddPolyn(List L1,List L2,List &L3); //
多项式加法
3、Polyn.cpp
#include"Polynt.h"
Status MakeNode(Polyn &p,ElemType e)
{//分配由p 指向的数据元素为e 、后继为“空”的结点
p=(Polyn)malloc(sizeof(Node));
p->data.coef=e.coef;
p->data.expn=e.expn;
p->next=NULL;
return OK;
}
Status InitList(List &L)
{//初始化链表
ElemType e;
Polyn p;
e.coef = ' ';
e.expn = ' ';
MakeNode(p,e);
L.head = p;
L.tail=p;
return OK;
}
Status DestroyList(List &L)
{//销毁链表
Polyn p,q;
if(L.head==L.tail) {free(L.head);L.head=L.tail=NULL;return OK;}
p=L.head->next;
while(!p){
q=p->next;
free(p);
p=q;}
L.head=L.tail=NULL;
return OK;
}
void Insert(List &L,Polyn s)
{
if(L.head->next ==NULL)
{
L.head->next =s;
s->next =NULL;
L.tail = s;
}
else{
if(L.head->next!=NULL && s->data.expn>L.head->next->data.expn)
{s->next=L.head->next;L.head->next=s; return;}
if(L.tail->data.expn>s->data.expn)
{L.tail->next=s; L.tail=s;return;}
for (Polyn p = L.head->next; p!=NULL;p = p->next )
{
if (s->data.expn== p->data.expn)
{
p->data.coef+=s->data.coef;
free(s);
return;
}
else if ( p->data.expn>s->data.expn &&
p->next->data.expndata.expn)
{
s->next=p->next;p->next=s;
return;
}
}
}
}
Status CreatPolyn(List &polynomial,int m)
{//创建一个一元多项式polynomial ，并输入m 项的指数和系数
ElemType e;
Polyn p;
for(int i=0;i
{
scanf("%g,%d",&e.coef,&e.expn);
MakeNode(p,e);
Insert(polynomial,p);}
polynomial.tail=p;
return OK;
}
void PrintPolyn(List L)
{
Polyn p;
if(L.head==L.tail)
printf("0");
else
{
p=L.head->next;
while(p!=NULL)
{
if(p==L.head->next)
{
if(p->data.coef>0)
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else if(p->data.coef
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else
{printf(" ");}
p=p->next;
}
else if(p!=L.head->next && p!=NULL)
{
if(p->data.coef>0)
{
if(p->data.expn!=0)
{printf("+%gx^%d",p->data.coef,p->data.expn);}
else{printf("+%g",p->data.coef);}
}
else if(p->data.coef
{
if(p->data.expn!=0)
{printf("%gx^%d",p->data.coef,p->data.expn);}
else{printf("%g",p->data.coef);}
}
else
{printf(" ");}
p=p->next;
}
else
return;
}
}
}
void AlterPoly(List L)
{
for(Polyn p=L.head->next;p!=NULL;p=p->next)
p->data.coef*=-1;
}
void AddPolyn(List L1,List L2,List &L3)
{
Polyn p1,p2,p3;
p1=L1.head->next;
p2=L2.head->next;
while(p1!=NULL && p2!=NULL)
{
if(p1->data.expn>p2->data.expn)
{
MakeNode(p3,p1->data);
Insert(L3,p3);
p1=p1->next;
}
else if(p1->data.expndata.expn)
{
MakeNode(p3,p2->data);
Insert(L3,p3);
p2=p2->next;
}
else if(p1->data.expn==p2->data.expn)
{
MakeNode(p3,p2->data);
p3->data.coef=p1->data.coef+p2->data.coef;
p3->data.expn=p1->data.expn;
Insert(L3,p3);
p1=p1->next;p2=p2->next;
}
}
if(p1==NULL && p2!=NULL)
{
while(p2!=NULL){
MakeNode(p3,p2->data);
Insert(L3,p3);
p2=p2->next;
}
}
else if(p2==NULL && p1!=NULL)
{
while(p1!=NULL){
MakeNode(p3,p1->data);
Insert(L3,p3);
p1=p1->next;
}
}
}
4、main.cpp
#include"Polynt.h"
#include
#include
void main()
{
system("cls");
printf("*********************************************************
***\n");
printf(" 欢迎使用一元稀疏多项式计算 \n");
printf("*********************************************************
***\n");
printf("1、创建多项式A 2、创建多项式B 3、相加 4、相减 5、退出
\n");
List polynomialA,polynomialB,polynomialC;
InitList(polynomialA); InitList(polynomialB); InitList(polynomialC);
char poly;
int m;int n=1;
for(;;)
{
printf("请输入指令:");
poly=getchar();
switch(poly)
{
case'1': //创建多项式A printf("请输入多项式A 的项数：");
scanf("%d",&m);
printf("\n请 输 入 多 项 式 A：");
CreatPolyn(polynomialA,m);
printf("\n多项式A 是：");
PrintPolyn(polynomialA);
printf("\n");
break;
case'2': //创建多项式B printf("请输入多项式B 的项数：");
scanf("%d",&m);
printf("\n请 输 入 多 项 式 B：");
CreatPolyn(polynomialB,m);
printf("\n多项式B 是：");
PrintPolyn(polynomialB);
printf("\n");
break;
case'3': //加法
printf("结果是:");
AddPolyn(polynomialA,polynomialB,polynomialC);
PrintPolyn(polynomialC);
printf("\n");
break;
case'4': //减法
printf("结果是:");
AlterPoly(polynomialB);
DestroyList(polynomialC);
InitList(polynomialC);
AddPolyn(polynomialA,polynomialB,polynomialC);
PrintPolyn(polynomialC);
} } printf("\n"); break; case'5': DestroyList(polynomialA); //退出 DestroyList(polynomialB); DestroyList(polynomialC); return; } poly=getchar(); if(poly==5) break;