基本操作：
InitList()
操作结果：构造一个空的有序表L。
DestroyList(L)
初始条件：有序表L已存在。
操作结果：销毁有序表L。
ListLength(L)
初始条件：有序表L已存在。
操作结果：返回有序表L的长度。
ClearList( L )
初始条件：有序表L已存在。
操作结果：清空链表内容。
Ins_before ( N,N )
初始条件：有序表L已存在。
操作结果：插入节点到链表。
} ADT OrderedList
2.多项式的抽象数据类型定义为：
ADT Poly {
数据对象：D={a i |a i为实数，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<0)
{
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<0)
{
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;
