构造两个按指数递增的有序链表,实现两个一元多项式相加,c代码
时间: 2024-10-15 16:19:53 浏览: 5
在C语言中,你可以使用结构体表示多项式的系数和项数,然后构造两个链表分别存储两个多项式。这里首先假设你已经有了一个链表节点的数据结构,包含系数(coeff)和指数(exponent)。为了实现两个多项式相加,你需要遍历每个链表,并对相应的项进行加法运算,若结果超过某个阈值则创建新节点并插入到新的链表中。
以下是简单的C代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Term {
double coeff;
int exponent;
struct Term* next;
} Term;
Term* create_term(double coeff, int exponent) {
Term* node = (Term*)malloc(sizeof(Term));
node->coeff = coeff;
node->exponent = exponent;
node->next = NULL;
return node;
}
Term* add_terms(Term* term1, Term* term2) {
if (!term1 || !term2)
return term1 ? term1 : term2;
if (term1->exponent > term2->exponent) {
term1->next = add_terms(term1->next, term2);
return term1;
} else if (term1->exponent < term2->exponent) {
term2->next = add_terms(term1, term2->next);
return term2;
} else { // same exponent, add coefficients
term1->coeff += term2->coeff;
if (term1->coeff != 0) {
term2->next = add_terms(NULL, term2); // move to next term in chain
}
return term1;
}
}
// 创建按指数递增的有序链表函数
Term* build_sorted_list(double* values, int length) {
Term* head = NULL;
for (int i = 0; i < length; i++) {
Term* new_term = create_term(values[i], i);
if (!head)
head = new_term;
else {
Term* current = head;
while (current->next && current->exponent < new_term->exponent)
current = current->next;
if (current->exponent == new_term->exponent)
current->next = new_term;
else
current->next = new_term;
}
}
return head;
}
void print_linked_list(Term* list) {
while (list) {
printf("%.2f*x^%d -> ", list->coeff, list->exponent);
list = list->next;
}
printf("\n");
}
int main() {
double poly1[] = {1, 2, 3}; // [1x^0 + 2x^1 + 3x^2]
double poly2[] = {4, 5, 6}; // [4x^0 + 5x^1 + 6x^2]
Term* list1 = build_sorted_list(poly1, sizeof(poly1)/sizeof(double));
Term* list2 = build_sorted_list(poly2, sizeof(poly2)/sizeof(double));
Term* result = add_terms(list1, list2);
printf("Poly 1: ");
print_linked_list(list1);
printf("Poly 2: ");
print_linked_list(list2);
printf("Sum: ");
print_linked_list(result);
return 0;
}
```
这个程序首先将给定的一元多项式数组构建为按指数递增排序的链表,然后合并两个链表得到相加后的链表。注意这只是一个基本示例,实际应用中可能需要处理更复杂的场景,如合并过程中可能会有溢出、零除等问题。