代码解释
使用结构体存储多项式的系数和指数以及定义指向结构体的指针便于操作
typedef struct Node {
float coef; // 系数
int expn; // 指数
struct Node *next; // 指针域
} Node, *Polynomial;
多项式的创建
传入结构体指针便于数据的存储,以及多项式的项数。
因为polynomial是结构体指针类型,要实现数据的存储需要传入指针的地址所以这边使用的是二级指针以实现对数据的存储(函数中传值和传地址的操作)
在代码中,Polynomial *p
是一个指向 Polynomial 类型指针的指针,也可以称为二级指针。通过使用二级指针,我们可以修改指针本身所指向的地址中存储的内容,而不仅仅是修改指针指向的变量的内容。
在这段代码中,Polynomial *p
是一个指向多项式链表头节点指针的指针。通过使用二级指针,我们可以在函数中修改指针 p
指向的地址中存储的内容,例如在 createPolynomial
函数中,通过 *p = (Polynomial)malloc(sizeof(Node));
这行代码,我们实际上修改了指针 p
所指向的地址,将新分配的内存空间地址赋值给了 *p
,从而改变了调用函数中指针的值。
其中pre充当前驱结点帮助定位新节点 s
应该插入的位置。通过不断更新 pre
和 q
的位置,最终将新节点 s
插入到正确的位置。
void createPolynomial(Polynomial *p, int n) {
*p = (Polynomial)malloc(sizeof(Node));
(*p)->next = NULL;
for(int i = 1; i <= n; i++) {
Node *s, *pre, *q;
s = (Node*)malloc(sizeof(Node));
printf("请输入系数和指数:");
scanf("%f", &s->coef);
scanf("%d", &s->expn);
pre = *p;
q = (*p)->next;
while(q && q->expn < s->expn) {
pre = q;
q = q->next;
}
s->next = q;
pre->next = s;
}
}
多项式相加
这里传入的是指针之所以没有使用二级指针,是因为函数并不需要修改传入的指针本身,而只需要通过传入的指针访问和修改指针指向的内容。在这种情况下,使用单级指针就足够完成所需的操作,不需要额外引入二级指针。在函数中,通过传入的 pa
和 pb
指针来遍历多项式链表,并对多项式进行相加合并的操作。在这个过程中,并不需要改变 pa
和 pb
指针本身所指向的地址,只需要修改它们指向的节点的内容,因此使用单级指针即可满足需求。
通过比较项数来合并系数,选择一个指针作为合并后的总指针对合并后的系数和项数进行存储连接释放结点空间
p3->next = p1 ? p1 : p2;使用三目运算符判断p1和p2是否有都为空,将不为空的指针后继结点连接的p3后。
void addPolynomial(Polynomial pa, Polynomial pb) {
Polynomial p1 = pa->next;
Polynomial p2 = pb->next;
Polynomial p3 = pa;
while(p1 && p2) {
if(p1->expn == p2->expn) {
float sum = p1->coef + p2->coef;
if(sum != 0) {
p1->coef = sum;
p3->next = p1;
p3 = p1;
p1 = p1->next;
Polynomial r = p2;
p2 = p2->next;
free(r);
} else {
Polynomial r = p1;
p1 = p1->next;
free(r);
r = p2;
p2 = p2->next;
free(r);
}
} else if(p1->expn < p2->expn) {
p3->next = p1;
p3 = p1;
p1 = p1->next;
} else {
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
p3->next = p1 ? p1 : p2;
free(pb);
}
对多项式打印
void displayPolynomial(Polynomial p) {
Node *node = p->next;
while(node) {
printf("%.2fx^%d ", node->coef, node->expn);
node = node->next;
if(node) {
printf("+ ");
}
}
printf("\n");
}
完整代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
float coef; // 系数
int expn; // 指数
struct Node *next; // 指针域
} Node, *Polynomial;
void createPolynomial(Polynomial *p, int n) {
*p = (Polynomial)malloc(sizeof(Node));
(*p)->next = NULL;
for(int i = 1; i <= n; i++) {
Node *s, *pre, *q;
s = (Node*)malloc(sizeof(Node));
printf("请输入系数和指数:");
scanf("%f", &s->coef);
scanf("%d", &s->expn);
pre = *p;
q = (*p)->next;
while(q && q->expn < s->expn) {
pre = q;
q = q->next;
}
s->next = q;
pre->next = s;
}
}
void addPolynomial(Polynomial pa, Polynomial pb) {
Polynomial p1 = pa->next;
Polynomial p2 = pb->next;
Polynomial p3 = pa;
while(p1 && p2) {
if(p1->expn == p2->expn) {
float sum = p1->coef + p2->coef;
if(sum != 0) {
p1->coef = sum;
p3->next = p1;
p3 = p1;
p1 = p1->next;
Polynomial r = p2;
p2 = p2->next;
free(r);
} else {
Polynomial r = p1;
p1 = p1->next;
free(r);
r = p2;
p2 = p2->next;
free(r);
}
} else if(p1->expn < p2->expn) {
p3->next = p1;
p3 = p1;
p1 = p1->next;
} else {
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
p3->next = p1 ? p1 : p2;
free(pb);
}
void displayPolynomial(Polynomial p) {
Node *node = p->next;
while(node) {
printf("%.2fx^%d ", node->coef, node->expn);
node = node->next;
if(node) {
printf("+ ");
}
}
printf("\n");
}
int main() {
Polynomial pa, pb;
int n;
printf("请输入多项式 A 的项数: ");
scanf("%d", &n);
createPolynomial(&pa, n);
printf("请输入多项式 B 的项数: ");
scanf("%d", &n);
createPolynomial(&pb, n);
printf("多项式 A: ");
displayPolynomial(pa);
printf("多项式 B: ");
displayPolynomial(pb);
addPolynomial(pa, pb);
printf("A + B 的结果: ");
displayPolynomial(pa);
return 0;
}