数据结构(C语言)用单链表存储一元多项式并实现两个多项式的相加运算
本篇文章主要讲述了使用单链表存储一元多项式,并实现两个多项式的相加运算的算法和实现细节。
一、单链表的声明和实现
在C语言中,单链表是一种常用的数据结构,可以用来存储一元多项式。在本文中,我们定义了一个结构体PolynNode,用于存储每个多项式的系数和指数。该结构体包含三个成员变量:coef(系数)、expn(指数)和next(指向下一个节点的指针)。
typedef struct PolynNode{
int coef; // 系数
int expn; // 指数
struct PolynNode *next;
}PolynNode, *PolynList;
二、创建多项式单链表
为了创建一个多项式单链表,我们定义了一个函数CreatePolyn,该函数用于输入n个元素的值,并建立带表头结构的单链线性表。该函数首先生成头结点,然后依次输入系数和指数,并将其存储在单链表中。
void CreatePolyn(PolynList &L, int n) {
int i;
PolynList p, q;
L = (PolynList)malloc(sizeof(PolynNode)); // 生成头结点
L->next = NULL;
q = L;
printf("成对输入%d 个数据\n", n);
for (i = 1; i <= n; i++) {
p = (PolynList)malloc(sizeof(PolynNode));
scanf("%d%d", &p->coef, &p->expn); //指数和系数成对输入
q->next = p;
q = q->next;
}
p->next = NULL;
}
三、遍历多项式单链表
为了遍历多项式单链表,我们定义了一个函数PolynTraverse,该函数用于依次对单链表的每个数据元素调用函数vi()。在遍历过程中,我们使用了printf函数来输出每个多项式项的系数和指数。
void PolynTraverse(PolynList L, void(*vi)(ElemType, ElemType)) {
PolynList p = L->next;
while (p) {
vi(p->coef, p->expn);
if (p->next) {
printf(" + "); //“+”号的输出,最后一项后面没有“+”
}
p = p->next;
}
printf("\n");
}
四、多项式相加运算
为了实现两个多项式的相加运算,我们定义了一个函数MergeList,该函数用于归并两个已经存在的多项式。该函数首先初始化两个指针pa和pb,分别指向两个多项式的头结点,然后依次比较两个多项式的指数,如果指数不相等,则将指数小的结点连上pc指针,否则将两个多项式的系数相加,并将结果存储在pc指针所指的结点中。
PolynList MergeList(PolynList La, PolynList Lb) {
PolynList pa, pb, pc, Lc;
pa = La->next;
pb = Lb->next;
Lc = pc = La; // 用 La 的头结点作为 Lc 的头结点
while (pa && pb) {
if (pa->expn < pb->expn) {
pc->next = pa; //如果指数不相等,pc 指针连上指数小的结点,
pc = pa;
pa = pa->next; //指向该结点的指针后移
} else if (pa->expn > pb->expn) {
pc->next = pb; //pc 指针连上指数小的结点,
pc = pb;
pb = pb->next; //指向该结点的指针后移
} else { // 如果指数相等,则将系数相加
pc->coef = pa->coef + pb->coef;
pc->expn = pa->expn;
pa = pa->next;
pb = pb->next;
}
}
return Lc;
}
本文主要讲述了使用单链表存储一元多项式,并实现两个多项式的相加运算的算法和实现细节。该算法可以实现在计算机科学和数学领域中的实际应用。
评论2
最新资源