数据结构用c语言和链表实现多项式相加
时间: 2023-05-28 12:05:02 浏览: 79
以下是一个简单的C语言程序,使用链表实现多项式相加:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义多项式的节点
typedef struct Node {
int coef; // 系数
int exp; // 指数
struct Node *next; // 下一个节点
} Node;
// 创建一个新节点
Node *createNode(int coef, int exp) {
Node *node = (Node *) malloc(sizeof(Node));
node->coef = coef;
node->exp = exp;
node->next = NULL;
return node;
}
// 插入节点到多项式中
void insert(Node **head, int coef, int exp) {
Node *node = createNode(coef, exp);
if (*head == NULL) {
*head = node;
} else {
Node *curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = node;
}
}
// 打印多项式
void print(Node *head) {
Node *curr = head;
while (curr != NULL) {
printf("%dx^%d", curr->coef, curr->exp);
curr = curr->next;
if (curr != NULL) {
printf(" + ");
}
}
printf("\n");
}
// 多项式相加
Node *add(Node *p1, Node *p2) {
Node *head = NULL;
while (p1 != NULL || p2 != NULL) {
if (p1 == NULL) {
insert(&head, p2->coef, p2->exp);
p2 = p2->next;
} else if (p2 == NULL) {
insert(&head, p1->coef, p1->exp);
p1 = p1->next;
} else if (p1->exp > p2->exp) {
insert(&head, p1->coef, p1->exp);
p1 = p1->next;
} else if (p1->exp < p2->exp) {
insert(&head, p2->coef, p2->exp);
p2 = p2->next;
} else {
insert(&head, p1->coef + p2->coef, p1->exp);
p1 = p1->next;
p2 = p2->next;
}
}
return head;
}
int main() {
// 创建多项式1: 2x^3 + 4x^2 + 3x^1 + 1x^0
Node *p1 = NULL;
insert(&p1, 2, 3);
insert(&p1, 4, 2);
insert(&p1, 3, 1);
insert(&p1, 1, 0);
printf("p1 = ");
print(p1);
// 创建多项式2: 3x^3 + 2x^2 + 1x^1 + 5x^0
Node *p2 = NULL;
insert(&p2, 3, 3);
insert(&p2, 2, 2);
insert(&p2, 1, 1);
insert(&p2, 5, 0);
printf("p2 = ");
print(p2);
// 计算多项式相加
Node *p3 = add(p1, p2);
printf("p3 = ");
print(p3);
return 0;
}
```
输出结果为:
```
p1 = 2x^3 + 4x^2 + 3x^1 + 1x^0
p2 = 3x^3 + 2x^2 + 1x^1 + 5x^0
p3 = 5x^3 + 6x^2 + 4x^1 + 6x^0
```
该程序使用了链表来存储多项式,其中每个节点包含了系数和指数。`createNode()` 函数用于创建一个新节点,`insert()` 函数用于将节点插入到多项式中,`print()` 函数用于打印多项式,`add()` 函数用于计算多项式相加。在 `add()` 函数中,我们通过比较指数的大小来决定将哪个节点的系数插入到结果多项式中。最后,我们调用 `add()` 函数来计算多项式相加,并打印结果。