一元多项式的表示与运算——课程设计（无序输入 有序输出）
目录
∙ 主要内容：用线性表表示一元多项式。实现一元多项式的相加、求导、求值、相减等运算
相加算法实现：首先确定表示一元多项式的线性表的存储方式----顺序存储结构，链式存储结构均可；
两种存储方式：顺序存储结构和链式存储结构（本文采用链式存储方式解题）
- 一元多项式的指数很高且相邻的指数相差很大时，宜只存放系数非零项的系数和相应的指数，否则浪费存储,且系数非零项仍按指数升序排列方便运算实现。（存储中根据系数的稀疏性来选择）
- 对于次数低的,方便多项式之间的运算,可采用按项顺序存储的形式。
一.例题：（输入无序，指数升序排列的一元多项式）
【问题描述】读入一元多项式中每一项的系数和指数，建立单链表存放输入的一元多项式，写出遍历单链表输出所存放的一元多项式，一元多项式相加，求一元多项式的值，删除一元多项式中指定项等相关操作
【输入形式】x的值，2个一元多项式各项（顺序随意），要删除相加后多项式的指数项
【样例输入1】
2
-1 0 8 3 10 8 2 20 0 0
1 0 5 3 6 2 2 20 0 0
8
【样例说明1】 输入： 第1行的2是一元多项式x的值 第2行和第3行是两个一元多项式每一项的系数和指数，不要求有序输入，以0 0结束
第4行是删除的相加后多项式的指数项输出 第1、2、3行，参照例子 第4行为删除相加后指数项之后的多项式.
【样例输入2】
2
1 2 3 5 4 3 0 0
2 0 -3 5 3 3 2 1 0 0
3
1. 链表结点定义
/* 链表结点定义 */
typedef struct LNode{
int exp, coef; //coef为指数, exp为系数
struct LNode *next;
}LNode, *LinkList;
2. 创建单链表存放一元多项式(将无序的输入有序存放于链表)
/* 创建单链表存放一元多项式*/
void CreateList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode));
L->next = NULL;
LinkList p;
LinkList pre=L;//
LinkList s=L;// 尾插法的尾指针
L->coef = 0.0;//先初始化一下
L->exp = 0;
//一直输入 检测到 输入0 0 的时候截至
while(true){
p=(LinkList)malloc(sizeof(LNode));
p->next=NULL;
if(p==NULL) return;//是否开辟成功
scanf("%d",&p->coef);
scanf("%d",&p->exp);
if(!p->exp&&!p->coef){
free(p); //如果输入有误 就把多开辟的空间释放掉
return;
}
if(p->exp>=s->exp){//输入正序的话就尾插
s->next = p;
s=p;
}
else{//输入比上一个小 说明输入无序 插入
while(pre->next){
pre=pre->next;//从头向后找 插入的位置
if(pre->next->exp>p->exp && pre->exp <= p->exp){
//找到插入的位置
p->next = pre->next;//插入
pre->next=p;
pre = L;//重置pre的指向位置 以便下一次找位置
break;//插入完成 退出循环
}
}
}
}
}
3. 输出一元多项式
//遍历单链表,格式化输出一元多项式的每一项
void Display(LinkList L)
{
LinkList p = L->next;
int First_Term = 1;
//表示当前处理的项是否是多项式的第一项 第一项前面不需要额外正负号
while (p != NULL) {
if (p->exp) {
if (!First_Term && p->coef > 0) {
//整数加上+号
printf("+");
}
printf("%dx^%d", p->coef, p->exp);
} else {
//指数为零 直接打印
printf("%d", p->coef);
}
First_Term = 0; //修改标签
p = p->next;
}
}
4. 一元多项式求值
/* 一元多项式求值 */
double Value(LinkList L, int x)
{
LinkList p=L->next;
double function_sum=0.0;
while(p!=NULL){
function_sum += p->coef*pow(x,p->exp);
p=p->next;
}
return function_sum;
}/* 一元多项式求值 */
5. 删除一元多项式中的指定项
/*删除一元多项式中的指定项 */
void DeleteElem(LinkList &L, int e)
{
//在这里插入你的代码
LinkList p=L->next;//线性表的第一个数据元素
//p在前面 探路
LinkList q=L;// q指向 p的前驱结点地址
while(p!=NULL){
if(p->exp==e){//发现指定指数项
q->next=p->next;//删除该项
free(p);
return;
}
else{
//未发现该指数项 两指针后移 继续探寻
q=p;
p=p->next;
}
}
}//DeleteElem
6. 实现两个一元多项式相加 ha = ha + hb
//ha = ha + hb
void AddPoly(LinkList ha,LinkList hb)
{
LinkList pa = ha->next;//探路
LinkList pb = hb->next;//探路
LinkList p = ha;// p指向 pa的前继结点
while(pa&&pb){
if(pa->exp<pb->exp){
//情况一：当ha中该项的指数小时 指针p 和 pa 直接向后移动一位
p = pa;//后移
pa=pa->next;//后移
}
else if(pa->exp>pb->exp){
//情况二：当ha中该项的指数大时 需要将hb中该节点 连接进来
//接入： 指针p 的后继指向pb pb的后继指向pa
//后移： p 、pb均向后移动一位
hb->next=pb->next;//ha 拿走该pb指向的这个结点
pb->next=pa;//接入： 指针p 的后继指向pb pb的后继指向pa
p->next=pb;
p=pb;//后移： p 、pb均向后移动一位
pb=hb->next;
}
else{
//情况三：相等的时候 需要求和
pa->coef +=pb->coef;//求和：放入ha中
hb->next=pb->next;//该pb指向的节点直接删 他的系数已经被ha加上了
free(pb);//释放空间
pb=hb->next;//更新pb的指向
if(pa->coef){
//不为零时 正常后移
p = pa;
}
else{//删除相加后 系数为0 的项
//系数为零时
// 节省储存空间
p->next = pa->next;
free(pa);//这个释放的原理 要搞清楚
//更新pa的指向
}
pa=p->next;//更新pa的指向 pa
}
}
p->next = pa?pa:pb;//接入剩余的结点
free(hb);//释放空间
}
二.例题：（有序）指数升序排列输出一元多项式
从键盘读入一元多项式中每一项的系数和指数，请编写算法实现（类C语言算法描述，不是完整程序代码）：
（1）建立带表头结点的单链表存放一元多项式（按照指数升序排列）； void CreatePoly(LinkList &pa)
（2）输出一元多项式的所有数据元素(按照指数升序输出每一系数非0项的系数和指数)； void Display(LinkList pa)
（3）输入自变量的值，计算一元多项式的值； int Evaluation(LinkList pa, int
x)，pa为头结点，x为自变量，返回值为一元多项式的值 （4）输入两个一元多项式，求一元多项式的和多项式（不是求值）。 void
AddPoly(LinkList ha,LinkList hb)，结果放入ha链表
1. 链表结点定义
typedef struct Node{
float coef_num;//系数的值
int expn_num;//指数的值
struct Node *next;
}Term,*LinkList;
//使用链表
2. 创建单链表存放一元多项式（按照指数升序排列）
//（1）建立带表头结点的单链表存放一元多项式（按照指数升序排列）；
//循环截至条件 按个数输入
void CreatePoly(LinkList &pa)
{
int m;
cout<<"请输入 一元多项式的项数"<<endl;
cin>>m;
pa=(LinkList)malloc(sizeof(Node));
pa->next = NULL;
LinkList p;
LinkList s=pa;
pa->coef_num = 0.0;;
pa->expn_num = 0;
// 输入到指定 个数停止
for(int i = 0; i < m; i++){
p=(LinkList)malloc(sizeof(Node));
p->next=NULL;
if(p==NULL) return;
cin>>p->coef_num;
cin>>p->expn_num;
//尾插法
s->next = p;
s=p;
}
}
void CreatePoly1(LinkList &pa)
{
cout<<"请输入 一元多项式的系数(系数不为零) 和 指数(输入0 0时停止)"<<endl;
pa=(LinkList)malloc(sizeof(Node));
pa->next = NULL;
LinkList p;
LinkList s=pa;
pa->coef_num = 0.0;
pa->expn_num = 0;
//一直输入 检测到 输入0 0 的时候截至
while(true){
p=(LinkList)malloc(sizeof(Node));
p->next=NULL;
if(p==NULL) return;
cin>>p->coef_num;
cin>>p->expn_num;
if(!p->expn_num&&!p->coef_num){
free(p);
return;
}
//尾插法
s->next = p;
s=p;
}
}
3. 按升序输出一元多项式
//（2）输出一元多项式的所有数据元素(按照指数升序输出每一系数非0项的系数和指数)；
void Display(LinkList pa) {
LinkList p=pa->next;
while(p!=NULL){
cout<< p->coef_num<<" "<<p->expn_num<<endl;//格式
p=p->next;
}
}
4. 计算一元多项式的值
//输入自变量的值，计算一元多项式的值；
float Evaluation(LinkList pa, int x){
//pa为头结点，x为自变量，返回值为一元多项式的值
LinkList p=pa->next;
float function_sum=0.0;
while(p!=NULL){
function_sum += p->coef_num*pow(x,p->expn_num);
p=p->next;
}
return function_sum;
}
5. 实现两个一元多项式相加 ha = ha + hb
void AddPoly1(LinkList ha, LinkList hb){
LinkList pa = ha->next;//探路
LinkList pb = hb->next;//探路
LinkList p = ha;// pa的前继结点 //
while(pa&&pb)
if(pa->expn_num<pb->expn_num){
//情况一：当ha中该项的指数小时 指针p 和 pa 直接向后移动一位
p=pa;
pa=pa->next;
}
else if(pa->expn_num == pb->expn_num){
//情况二：相等的时候 需要求和
pa->coef_num += pb->coef_num;//求和：放入ha中
hb->next=pb->next;//该pb指向的节点直接删 他的系数已经被ha加上了
free(pb);
pb=hb->next;
if(!pa->coef_num){ //判断加和后系数是否为零
//系数为零的情况 删除pa指向的这个结点
p->next=pa->next;
free(pa);//pa指向的释放了这个地址
pa=p->next;
}
else{
//如果不为零 正常后移
p=pa;
pa=pa->next;
}
}
else{
//情况三：当ha中该项的指数大时 需要将hb中该节点 连接进来
//接入： 指针p 的后继指向pb pb的后继指向pa
//后移： p 、pb均向后移动一位
hb->next=pb->next;//ha 拿走该pb指向的这个结点
pb->next=pa;//接入： 指针p 的后继指向pb pb的后继指向pa
p->next=pb;
p=pb;//后移： p 、pb均向后移动一位
pb=hb->next;
}
if(pb) p->next=pb;//接入剩余的结点
free(hb);
}