c语言单链表实现一元多项式相加
时间: 2023-06-08 10:04:19 浏览: 313
好的,我可以回答这个问题。单链表可以作为存储一元多项式的一种数据结构。相加两个一元多项式的方法是将两个一元多项式中相同次数的项相加,得到新的一元多项式。
具体步骤如下:
1. 定义一个单链表数据结构来存储一元多项式。
2. 读入两个一元多项式并分别存储到两个单链表中。
3. 遍历两个链表,将相同次数的项相加,将结果存储到一个新的链表中。
4. 如果一个链表遍历完了而另一个链表还有剩余的项,将这些项直接添加到新链表中。
5. 输出新链表中的每一项,即为相加的结果。
代码实现可参考下面示例:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int coeff; //系数
int expn; //指数
struct node *next;
} Node;
Node* CreateList(); //创建链表
Node* InputPoly(); //输入一元多项式
void AddPoly(Node*, Node*, Node*); //相加两个一元多项式
void PrintPoly(Node*); //输出一元多项式
int main()
{
Node *A, *B, *C;
A = InputPoly();
B = InputPoly();
C = CreateList();
AddPoly(A, B, C);
PrintPoly(C);
return 0;
}
Node* CreateList()
{
Node *L = (Node*)malloc(sizeof(Node));
L->next = NULL;
return L;
}
Node* InputPoly()
{
Node *L = CreateList();
Node *r = L;
int n, coeff, expn;
printf("请输入一元多项式的项数:");
scanf("%d", &n);
printf("请按照指数递减的顺序输入各项系数和指数:\n");
while(n--)
{
Node *p = (Node*)malloc(sizeof(Node));
scanf("%d%d", &coeff, &expn);
p->coeff = coeff;
p->expn = expn;
r->next = p;
r = p;
}
r->next = NULL;
return L;
}
void AddPoly(Node *A, Node *B, Node *C)
{
Node *pa = A->next, *pb = B->next;
Node *pc = C;
while(pa && pb)
{
Node *p = (Node*)malloc(sizeof(Node));
if(pa->expn == pb->expn)
{
p->coeff = pa->coeff + pb->coeff;
p->expn = pa->expn;
pa = pa->next;
pb = pb->next;
if(p->coeff == 0) free(p);
else
{
pc->next = p;
pc = p;
}
}
else if(pa->expn > pb->expn)
{
p->coeff = pa->coeff;
p->expn = pa->expn;
pa = pa->next;
if(p->coeff == 0) free(p);
else
{
pc->next = p;
pc = p;
}
}
else
{
p->coeff = pb->coeff;
p->expn = pb->expn;
pb = pb->next;
if(p->coeff == 0) free(p);
else
{
pc->next = p;
pc = p;
}
}
}
pc->next = pa ? pa : pb;
}
void PrintPoly(Node *L)
{
Node *p = L->next;
while(p)
{
printf("%dX^%d", p->coeff, p->expn);
p = p->next;
if(p) printf("+");
}
printf("\n");
}
```
阅读全文