一元多项式采用带表头结点的单链表存放,用类C语言设计算法求一元多项式的值。
时间: 2023-05-27 20:02:44 浏览: 106
假设表头结点指针为L,表中每个结点类型为Node,包含两个域:项系数coef和项指数exp。
算法思路如下:
1. 初始化多项式值sum为0。
2. 从头结点开始遍历链表,对于每个结点:
- 将当前结点的项系数coef和项指数exp分别保存到变量c和x中。
- 计算当前结点的项值itemValue = c * pow(value, x),其中value为给定的x的值。
- 将itemValue累加到多项式值sum中。
3. 返回多项式值sum。
算法实现如下:
```c
float polyValue(Node* L, float value) {
float sum = 0;
Node* p = L->next;
while (p != NULL) {
float c = p->coef;
int x = p->exp;
float itemValue = c * pow(value, x);
sum += itemValue;
p = p->next;
}
return sum;
}
```
相关问题
利用所学的数据结构的基本知识,设计一个一元稀疏多项式简单计算器。 输入:输入并建立多项式; 输出:输出多项式,输出形式为整数序列要求:1)多项式相加/相减;2)计算多项式在x处的值;可以用带表头结点的单链表存储多项式,多项式的项数存放在头结点中。用C语言数据结构
下面是一个基于带头结点的单链表实现的一元稀疏多项式简单计算器的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义多项式项的结构体
typedef struct PolyNode {
int coef; // 系数
int expon; // 指数
struct PolyNode *next; // 指向下一项的指针
} PolyNode, *Polynomial;
// 创建一个空的多项式(只有头结点)
Polynomial createPoly() {
Polynomial poly = (Polynomial) malloc(sizeof(PolyNode));
poly->next = NULL;
return poly;
}
// 从标准输入读入多项式
Polynomial readPoly() {
Polynomial poly = createPoly();
int n; // 项数
scanf("%d", &n);
while (n--) {
int coef, expon;
scanf("%d%d", &coef, &expon);
if (coef != 0) { // 忽略系数为0的项
Polynomial p = (Polynomial) malloc(sizeof(PolyNode));
p->coef = coef;
p->expon = expon;
p->next = NULL;
// 将新项插入到多项式中
Polynomial q = poly;
while (q->next && q->next->expon > expon) {
q = q->next;
}
if (q->next && q->next->expon == expon) { // 合并同类项
q->next->coef += coef;
if (q->next->coef == 0) { // 合并后系数为0,删除该项
Polynomial t = q->next;
q->next = t->next;
free(t);
}
} else { // 插入新项
p->next = q->next;
q->next = p;
}
}
}
return poly;
}
// 将多项式输出到标准输出
void printPoly(Polynomial poly) {
if (!poly->next) {
printf("0\n");
} else {
printf("%d ", count(poly)); // 输出项数
Polynomial p = poly->next;
while (p) {
printf("%d %d ", p->coef, p->expon);
p = p->next;
}
printf("\n");
}
}
// 返回多项式的项数
int count(Polynomial poly) {
int count = 0;
Polynomial p = poly->next;
while (p) {
count++;
p = p->next;
}
return count;
}
// 多项式相加
Polynomial addPoly(Polynomial poly1, Polynomial poly2) {
Polynomial poly = createPoly();
Polynomial p = poly1->next, q = poly2->next;
while (p && q) {
if (p->expon > q->expon) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *p;
t->next = NULL;
p = p->next;
insertPoly(poly, t);
} else if (p->expon < q->expon) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *q;
t->next = NULL;
q = q->next;
insertPoly(poly, t);
} else {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
t->coef = p->coef + q->coef;
t->expon = p->expon;
t->next = NULL;
p = p->next;
q = q->next;
if (t->coef != 0) {
insertPoly(poly, t);
} else {
free(t);
}
}
}
while (p) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *p;
t->next = NULL;
p = p->next;
insertPoly(poly, t);
}
while (q) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *q;
t->next = NULL;
q = q->next;
insertPoly(poly, t);
}
return poly;
}
// 在多项式中插入一个项,按指数降序排列
void insertPoly(Polynomial poly, Polynomial node) {
Polynomial p = poly;
while (p->next && p->next->expon > node->expon) {
p = p->next;
}
if (p->next && p->next->expon == node->expon) { // 合并同类项
p->next->coef += node->coef;
if (p->next->coef == 0) { // 合并后系数为0,删除该项
Polynomial t = p->next;
p->next = t->next;
free(t);
} else {
free(node);
}
} else {
node->next = p->next;
p->next = node;
}
}
// 多项式相减
Polynomial subPoly(Polynomial poly1, Polynomial poly2) {
Polynomial poly = createPoly();
Polynomial p = poly1->next, q = poly2->next;
while (p && q) {
if (p->expon > q->expon) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *p;
t->next = NULL;
p = p->next;
insertPoly(poly, t);
} else if (p->expon < q->expon) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *q;
t->coef = -t->coef;
t->next = NULL;
q = q->next;
insertPoly(poly, t);
} else {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
t->coef = p->coef - q->coef;
t->expon = p->expon;
t->next = NULL;
p = p->next;
q = q->next;
if (t->coef != 0) {
insertPoly(poly, t);
} else {
free(t);
}
}
}
while (p) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *p;
t->next = NULL;
p = p->next;
insertPoly(poly, t);
}
while (q) {
Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
*t = *q;
t->coef = -t->coef;
t->next = NULL;
q = q->next;
insertPoly(poly, t);
}
return poly;
}
// 计算多项式在x处的值
int calcPoly(Polynomial poly, int x) {
int sum = 0;
Polynomial p = poly->next;
while (p) {
sum += p->coef * pow(x, p->expon);
p = p->next;
}
return sum;
}
int main() {
// 读入第一个多项式
Polynomial poly1 = readPoly();
// 读入第二个多项式
Polynomial poly2 = readPoly();
// 输出第一个多项式
printf("Poly1: ");
printPoly(poly1);
// 输出第二个多项式
printf("Poly2: ");
printPoly(poly2);
// 计算第一个多项式在x=2处的值
int x = 2;
int result = calcPoly(poly1, x);
printf("Poly1(%d) = %d\n", x, result);
// 计算第二个多项式在x=3处的值
x = 3;
result = calcPoly(poly2, x);
printf("Poly2(%d) = %d\n", x, result);
// 计算两个多项式相加的结果
Polynomial sum = addPoly(poly1, poly2);
printf("Poly1 + Poly2: ");
printPoly(sum);
// 计算两个多项式相减的结果
Polynomial diff = subPoly(poly1, poly2);
printf("Poly1 - Poly2: ");
printPoly(diff);
return 0;
}
```
这个计算器支持读入两个多项式,计算多项式在某个点的值,以及将两个多项式相加和相减。其中,多项式以带头结点的单链表形式存储,每个节点表示一个项,包含系数和指数两个成员变量。
是使用带表头结点的单链表储存多项式并实现一元稀疏多项式简单计算器的 C 语言代码
在C语言中,我们可以使用单链表结构存储多项式的系数及其对应的变量次幂。每个节点可以包含一个整数表示系数,另一个整数表示变量的指数。这里是一个简单的例子,展示了如何创建一个带表头结点的链表结构以及如何实现一元稀疏多项式的基本加法操作:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int coefficient;
int exponent;
struct Node* next;
} PolynomialNode;
// 创建新节点
PolynomialNode* createNode(int coeff, int exp) {
PolynomialNode* newNode = (PolynomialNode*)malloc(sizeof(PolynomialNode));
newNode->coefficient = coeff;
newNode->exponent = exp;
newNode->next = NULL;
return newNode;
}
// 添加项到链表
void addTerm(PolynomialNode** head, int coeff, int exp) {
PolynomialNode* newNode = createNode(coeff, exp);
if (*head == NULL) {
*head = newNode;
} else {
PolynomialNode* current = *head;
while (current->next != NULL && current->exponent > exp) {
current = current->next;
}
if (current->exponent > exp) {
newNode->next = current->next;
current->next = newNode;
} else {
newNode->next = NULL;
}
}
}
// 打印多项式
void printPolynomial(PolynomialNode* head) {
PolynomialNode* current = head;
while (current != NULL) {
printf("%d*x^%d + ", current->coefficient, current->exponent);
current = current->next;
}
printf("0\n");
}
// 简单的多项式加法
PolynomialNode* addPolynomials(PolynomialNode* head1, PolynomialNode* head2) {
PolynomialNode* resultHead = NULL;
// 遍历两个多项式
while (head1 != NULL || head2 != NULL) {
int coeff1 = (head1 != NULL) ? head1->coefficient : 0;
int exp1 = (head1 != NULL) ? head1->exponent : 0;
int coeff2 = (head2 != NULL) ? head2->coefficient : 0;
int exp2 = (head2 != NULL) ? head2->exponent : 0;
// 计算和的系数和次幂
int newCoeff = coeff1 + coeff2;
int newExp = exp1 >= exp2 ? exp1 : exp2;
// 如果结果存在,则更新;如果不存在,创建新节点
PolynomialNode* newNode = createNode(newCoeff, newExp);
if (resultHead == NULL) {
resultHead = newNode;
} else {
PolynomialNode* current = resultHead;
while (current->next != NULL && current->exponent > newExp) {
current = current->next;
}
if (current->exponent > newExp) {
newNode->next = current->next;
current->next = newNode;
} else {
newNode->next = NULL;
}
}
// 移动指针
if (head1 != NULL) {
head1 = head1->next;
}
if (head2 != NULL) {
head2 = head2->next;
}
}
return resultHead;
}
int main() {
PolynomialNode* head1 = NULL;
PolynomialNode* head2 = NULL;
// 添加一些项到第一个多项式
addTerm(&head1, 2, 1); // 2x^1
addTerm(&head1, -1, 2); // -1x^2
// 添加一些项到第二个多项式
addTerm(&head2, 3, 0); // 3x^0
addTerm(&head2, 4, 2); // 4x^2
// 计算并打印结果
PolynomialNode* result = addPolynomials(head1, head2);
printPolynomial(result);
return 0;
}
```
这个示例实现了两个一元多项式的简单加法。注意,这只是一个基本版本,实际应用可能需要处理更复杂的情况,如合并同次幂项、移除零次幂项等。
阅读全文