当前位置：首页 > news >正文

练习篇：一元稀疏多项式

news 2026/4/29 20:01:57

实验：一元稀疏多项式

稀疏多项式（Sparse Polynomial）是指其中大部分项的系数为0的多项式。这种多项式通常用于解决存在许多未使用变量的数学问题，可以用更少的存储空间来表示这些多项式。在稀疏多项式中，只有一小部分项具有非零系数，而大多数项的系数为0。
在常规的多项式中，让下标对应指数，可以用数组储存每个单项的系数
p(x)=x+2x^2+4x4+6x^6=1x1+2x^2+0x3+4x^4+0x5+6x^6(*省去)
datatype variable[6]={1,2,0,4,0,6};
但面对譬如p(x)=x^10000+x的式子，若开一个数组，大小为10000，使下标等于指数。则0~9999的系数均为0，下标为0和10000的系数为1。这样做很不珍惜内存空间，运行效率极低。
datatype variable[10000]={1,0,0,0,0,...,0,0,1};//error
进而，得益于线性表链表结构的数据操作方便，不受指数限制的特点来实现一元稀疏多项式计算。

ADT

ADT Polynomial
{数据对象
D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0，TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 }

数据关系
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 }

数据操作
CreatPolyn ( &P, m )
操作结果：输入 m 项的系数和指数，建立一元多项式 P
DestroyPolyn ( &P )
初始条件：一元多项式 P 已存在
操作结果：销毁一元多项式 P
PrintPolyn ( &P )
初始条件：一元多项式 P 已存在
操作结果：打印输出一元多项式 P
PolynLength( P )
初始条件：一元多项式 P 已存在
操作结果：返回一元多项式 P 中的项数
AddPolyn ( &Pa, &Pb )
初始条件：一元多项式 Pa 和 Pb 已存在
操作结果：完成多项式相加运算，即 Pa = Pa＋Pb，并销毁一元多项式 Pb
SubtractPolyn ( &Pa, &Pb )
……
} ADT Polynomial

2.核心函数接口实现讲解

辅助函数

Status InitList(Polynomial &P);  // 在 pre 结点之后插入 e（须保证有序）
Status InsAfter(LinkList pre, ElemType e);// 删除 pre 的后继结点，值存入 e  
Status DelAfter(LinkList pre, ElemType &e);  // 查找链表中与 e 指数相同结点的前驱，cmp1 为比较函数  
LinkList LocatePre(Polynomial P, ElemType e, int   (*cmp)(ElemType, ElemType));  // 比较指数是否相等  
int cmp1(ElemType a, ElemType b) {  return a.expn == b.expn;  
}  // 比较指数大小：a<b → -1; a==b → 0; a>b → 1  
int cmp2(ElemType a, ElemType b) {  if (a.expn < b.expn) return -1;  if (a.expn > b.expn) return 1;  return 0;  
}

结构定义

1.定义多项式中每一项的组成

typedef struct
{float coef;//系数int expn;//指数
}ElemType;

2.线性表链式存储的结点结构定义

typedef struct LNode
{ElemType data;//值域struct LNode *next;//指针域
}LNode,*LinkList;

3.链表头结点（多项式定义）

typedef LinkList polynomial;

创建多项式P，共有m项

思路：
1.初始化链表和子项
2.循环输入，比较指数
3.指数升序排队
4.用到InitList,LocateElem,InsAfter函数。

Status CreatePolynomial(polynomial &P,int m)
{
InitList(P);//InitList为链表初始化函数，实现malloc空间开辟及指向空
ElemType e;
P->data.coef=0.0;
P->data.expn=-1;//头结点的指数设为-1
P->next=NULL;
for(int i=0;i<m;i++)
{scanf("%f%d",&e.coef,&e.expn);if(!LocateElem(P,e,cmp1))//如果指数不相同，就插入(LocateElem用于逐一查找已有子项并进行自定义cmp1操作。cmp1用于指数的比较，如果用户输入不同系数的同幂子项，只取第一项){if(!InsAfter(P,e))//不相同但没有插入，失败(InsAfter作用：使子项按指数降序插入)return ERROR;}
}
return SUCCESS;//相同不插入，不相同插入
}
//cmp1比较指数
int cmp1(ElemType a,ElemType b)
{return a.expn==b.expn;
}

加法

思路：
同时遍历两条链，先摘下尾项
switch：
1.指数相同，系数相加
2.指数不同，相加不为0的接链，为0删除
3.一条链遍历完，另一条剩下的接上
switch比较完后，先放入Pc，再取尾项

    Status AddPolyn(polynomial &Pc, polynomial &Pa, polynomial &Pb){// 初始化和多项式InitList(Pc);ElemType e1, e2;int a, b;// 每次从表头摘下当前最小指数项if(DelAfter(Pa, e1))//DelAfter函数，每次从多项式 Pa 摘下当前最前面一项，拿到它的系数、指数存在e1，如果摘不出来（链表空了），就设 a=MAXE 当作结束标记a = e1.expn;elsea = MAXE;e1.expn=MAXE;if(DelAfter(Pb, e2))b = e2.expn;elseb = MAXE;e2.expn=MAXE;while( !(a == MAXE && b == MAXE) )//对取出的子项指数进行比较{// switch 比较分支switch( cmp2(e1, e2) ){case -1:InsAfter(Pc, e1); // PA 当前指数更小，先存入Pcif(DelAfter(Pa, e1)) // 继续取下一项a = e1.expn;elsea = MAXE;break;case 0:e1.coef = e1.coef + e2.coef;// 指数相等：合并同类项if(e1.coef != 0.0)// 系数非零才插入稀疏多项式{InsAfter(Pc, e1);}// 同时取Pa，Pb的两个下一项if(DelAfter(Pa, e1))a = e1.expn;elsea = MAXE;if(DelAfter(Pb, e2))b = e2.expn;elseb = MAXE;break;case 1:// Pb 当前指数更小，跟Pa相同。放，取。InsAfter(Pc, e2);if(DelAfter(Pb, e2))b = e2.expn;elseb = MAXE;break;}}return SUCCESS;
}

乘法

思路：
1.取 Pa 中每一项 (c1,e1)，Pb 中每一项 (c2,e2)
2.相乘规则：
新系数：c = c1c2
新指数：e = e1+e2
3.每生成一个新项，插入临时链表；
4.指数相同的项系数累加，系数为 0 舍弃；
5.最终得到有序稀疏和多项式 Pc = PaPb

Status MultPolyn(polynomial &Pc, polynomial Pa, polynomial Pb)
{InitList(Pc);if(Pa->next==NULL || Pb->next==NULL)return SUCCESS;  // 有一个为零多项式，乘积为0LNode *p = Pa->next;// 遍历Pa每一项while(p){LNode *q = Pb->next;// 遍历Pb每一项while(q){ElemType term;// 系数相乘，指数相加term.coef = p->data.coef * q->data.coef;term.expn = p->data.expn + q->data.expn;if(term.coef == 0.0)// 系数为0，舍弃{q = q->next;continue;}ElemType old;LinkList pre = LocateElem(Pc, term, cmp1);if (pre) {DelAfter(pre, old);   // 删除 pre 的后继old.coef += term.coef;if (old.coef != 0.0)InsAfter(pre, old);  // 在原位插入}else{InsAfter(Pc, term); // 无同指数：有序插入新项}q = q->next;}p = p->next;}return SUCCESS;
}
'#### 菜单流程
打造一个完整的程序
int main() {Polynomial A = NULL, B = NULL, C = NULL;InitList(&A);           // 创建头结点InitList(&B);InitList(&C);int choice, m;while (1) {printf("\n====== 一元稀疏多项式管理器 ======\n");printf("1. 创建多项式 A\n");printf("2. 创建多项式 B\n");printf("3. 加法：C = A + B\n");printf("4. 乘法：C = A * B\n");printf("5. 显示多项式 A\n");printf("6. 显示多项式 B\n");printf("7. 显示多项式 C\n");printf("0. 退出\n");printf("请输入选项：");scanf("%d", &choice);switch (choice) {case 1:printf("输入多项式 A 的项数：");scanf("%d", &m);DestroyPolynomial(&A);          // 重建前先清理InitList(&A);if (CreatePolynomial(&A, m) == SUCCESS)printf("多项式 A 创建成功。\n");elseprintf("创建失败。\n");break;case 2:printf("输入多项式 B 的项数：");scanf("%d", &m);DestroyPolynomial(&B);InitList(&B);if (CreatePolynomial(&B, m) == SUCCESS)printf("多项式 B 创建成功。\n");elseprintf("创建失败。\n");break;case 3:DestroyPolynomial(&C);InitList(&C);AddPolyn(&C, A, B);printf("加法完成，结果已保存至 C。\n");break;case 4:DestroyPolynomial(&C);InitList(&C);MultPolyn(&C, A, B);printf("乘法完成，结果已保存至 C。\n");break;case 5:printf("A(x) = ");PrintPolynomial(A);break;case 6:printf("B(x) = ");PrintPolynomial(B);break;case 7:printf("C(x) = ");PrintPolynomial(C);break;case 0:DestroyPolynomial(&A);DestroyPolynomial(&B);DestroyPolynomial(&C);printf("程序结束。\n");return 0;default:printf("无效选项，请重新输入。\n");}}
}

时间复杂度

InitList O(1) 仅分配一个头结点
DestroyPolynomial O(k) k 为链表中结点总数（含头结点），释放每个结点
InsAfter O(1) 在给定前驱后插入结点
DelAfter O(1) 删除给定前驱的后继结点
LocatePre O(k) 遍历链表，查找与给定指数相等项的前驱，最多遍历整个链表，k 为当前链表长度
cmp1 / cmp2 O(1) 整数 / 浮点数比较

3.可运行代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define OK 1
#define ERROR 0
#define SUCCESS 1
#define MAXE 32767
#define EPS 1e-6typedef int Status;// 多项式项定义
typedef struct
{float coef;int expn;
} ElemType;// 链表结点
typedef struct LNode
{ElemType data;struct LNode *next;
} LNode, *LinkList;typedef LinkList Polynomial; // 多项式类型（带头结点）// 函数声明
Status InitList(Polynomial *P);
Status InsAfter(LinkList pre, ElemType e);
Status DelAfter(LinkList pre, ElemType *e);
LinkList LocatePre(Polynomial P, ElemType e, int (*cmp)(ElemType, ElemType));
int cmp1(ElemType a, ElemType b);
int cmp2(ElemType a, ElemType b);
void PrintPolynomial(Polynomial P);
Status CreatePolynomial(Polynomial *P, int m);
Status AddPolyn(Polynomial *Pc, Polynomial Pa, Polynomial Pb);
Status MultPolyn(Polynomial *Pc, Polynomial Pa, Polynomial Pb);
void DestroyPolynomial(Polynomial *P);// 主函数
int main()
{system("chcp 65001");Polynomial A = NULL, B = NULL, C = NULL;InitList(&A);InitList(&B);InitList(&C);int choice, m;while (1){printf("\n====== 一元稀疏多项式管理器 ======\n");printf("1. 创建多项式 A\n");printf("2. 创建多项式 B\n");printf("3. 加法：C = A + B\n");printf("4. 乘法：C = A * B\n");printf("5. 显示多项式 A\n");printf("6. 显示多项式 B\n");printf("7. 显示多项式 C\n");printf("0. 退出\n");printf("请输入选项：");scanf("%d", &choice);switch (choice){case 1:printf("输入多项式 A 的项数：");scanf("%d", &m);DestroyPolynomial(&A);InitList(&A);if (CreatePolynomial(&A, m) == SUCCESS)printf("多项式 A 创建成功。\n");elseprintf("创建失败。\n");break;case 2:printf("输入多项式 B 的项数：");scanf("%d", &m);DestroyPolynomial(&B);InitList(&B);if (CreatePolynomial(&B, m) == SUCCESS)printf("多项式 B 创建成功。\n");elseprintf("创建失败。\n");break;case 3:DestroyPolynomial(&C);InitList(&C);AddPolyn(&C, A, B);printf("加法完成，结果已保存至 C。\n");break;case 4:DestroyPolynomial(&C);InitList(&C);MultPolyn(&C, A, B);printf("乘法完成，结果已保存至 C。\n");break;case 5:printf("A(x) = ");PrintPolynomial(A);break;case 6:printf("B(x) = ");PrintPolynomial(B);break;case 7:printf("C(x) = ");PrintPolynomial(C);break;case 0:DestroyPolynomial(&A);DestroyPolynomial(&B);DestroyPolynomial(&C);printf("程序结束。\n");return 0;default:printf("无效选项，请重新输入。\n");}}
}// ---------- 基本操作实现 ----------
Status InitList(Polynomial *P)
{*P = (LinkList)malloc(sizeof(LNode));if (!(*P))return ERROR;(*P)->data.coef = 0.0;(*P)->data.expn = -1;(*P)->next = NULL;return OK;
}void DestroyPolynomial(Polynomial *P)
{if (!P || !(*P))return;LinkList q;while (*P){q = (*P)->next;free(*P);*P = q;}*P = NULL;
}Status InsAfter(LinkList pre, ElemType e)
{LinkList s = (LinkList)malloc(sizeof(LNode));if (!s)return ERROR;s->data = e;s->next = pre->next;pre->next = s;return OK;
}Status DelAfter(LinkList pre, ElemType *e)
{if (!pre || !pre->next)return ERROR;LinkList q = pre->next;*e = q->data;pre->next = q->next;free(q);return OK;
}int cmp1(ElemType a, ElemType b)
{return a.expn == b.expn;
}int cmp2(ElemType a, ElemType b)
{if (a.expn < b.expn)return -1;if (a.expn > b.expn)return 1;return 0;
}LinkList LocatePre(Polynomial P, ElemType e, int (*cmp)(ElemType, ElemType))
{LinkList pre = P;while (pre->next){if (cmp(pre->next->data, e))return pre;if (pre->next->data.expn > e.expn)break;pre = pre->next;}return NULL;
}// 创建多项式（升序）
Status CreatePolynomial(Polynomial *P, int m)
{ElemType e;int i;for (i = 0; i < m; i++){printf("请输入第%d项的系数和指数（空格隔开）: ", i + 1);scanf("%f%d", &e.coef, &e.expn);if (fabs(e.coef) < EPS)continue; // 忽略系数0if (LocatePre(*P, e, cmp1) != NULL){printf("指数 %d 的项已存在，忽略此项。\n", e.expn);continue;}// 找到插入位置前驱LinkList pre = *P;while (pre->next && pre->next->data.expn < e.expn)pre = pre->next;if (!InsAfter(pre, e))return ERROR;}return SUCCESS;
}// 加法
Status AddPolyn(Polynomial *Pc, Polynomial Pa, Polynomial Pb)
{ElemType e1, e2;int a, b;if (DelAfter(Pa, &e1))a = e1.expn;else{a = MAXE;e1.expn = MAXE;}if (DelAfter(Pb, &e2))b = e2.expn;else{b = MAXE;e2.expn = MAXE;}LinkList tail = *Pc; // 尾指针，用于尾插（升序）while (!(a == MAXE && b == MAXE)){switch (cmp2(e1, e2)){case -1: // e1 指数较小InsAfter(tail, e1);tail = tail->next;if (DelAfter(Pa, &e1))a = e1.expn;else{a = MAXE;e1.expn = MAXE;}break;case 0: // 指数相同e1.coef += e2.coef;if (fabs(e1.coef) > EPS){InsAfter(tail, e1);tail = tail->next;}if (DelAfter(Pa, &e1))a = e1.expn;else{a = MAXE;e1.expn = MAXE;}if (DelAfter(Pb, &e2))b = e2.expn;else{b = MAXE;e2.expn = MAXE;}break;case 1: // e2 指数较小InsAfter(tail, e2);tail = tail->next;if (DelAfter(Pb, &e2))b = e2.expn;else{b = MAXE;e2.expn = MAXE;}break;}}return SUCCESS;
}// 乘法（不破坏 Pa、Pb，结果存于 Pc）
Status MultPolyn(Polynomial *Pc, Polynomial Pa, Polynomial Pb)
{if (Pa->next == NULL || Pb->next == NULL)return SUCCESS; // 零多项式，Pc 仍为空LNode *pa = Pa->next;while (pa){LNode *pb = Pb->next;while (pb){ElemType term;term.coef = pa->data.coef * pb->data.coef;term.expn = pa->data.expn + pb->data.expn;if (term.coef == 0.0){pb = pb->next;continue;}LinkList pre = LocatePre(*Pc, term, cmp1);if (pre){ // 存在同指数项，合并ElemType old;DelAfter(pre, &old);old.coef += term.coef;if (old.coef == 0.0){// 重新找到 old 的升序插入位置LinkList insPre = *Pc;while (insPre->next && insPre->next->data.expn < old.expn)insPre = insPre->next;InsAfter(insPre, old);}}else{ // 无同指数项，升序插入LinkList insPre = *Pc;while (insPre->next && insPre->next->data.expn < term.expn)insPre = insPre->next;InsAfter(insPre, term);}pb = pb->next;}pa = pa->next;}return SUCCESS;
}// 打印多项式（降幂美观格式）
void PrintPolynomial(Polynomial P)
{if (!P || !P->next){printf("0\n");return;}LNode *p = P->next;while (p){printf("(%.2f,%d)", p->data.coef, p->data.expn);p = p->next;if (p)printf(" "); // 项之间用空格分隔}printf("\n");
}