c语言链表是怎么存储数据结构,数据结构(C语言)用单链表存储一元多项式,并实现... 数据结构一元多项式计算(急求)...
时间: 2023-08-05 15:46:03 浏览: 114
数据结构(C语言)用单链表存储一元多项式-并实现两个多项式的相加运算.doc
5星 · 资源好评率100%
C语言链表是由节点构成,每个节点包含两个部分:数据域和指针域。数据域用来存储具体的数据,指针域则指向下一个节点的位置,最后一个节点的指针域指向NULL。链表的头指针指向第一个节点。
用单链表存储一元多项式需要将每个节点的数据域分别存储多项式的系数和指数,指针域指向下一个节点。具体实现可以定义一个结构体来表示每个节点,如下所示:
```
typedef struct PolyNode* PtrToPolyNode;
struct PolyNode {
int coef; //系数
int expo; //指数
PtrToPolyNode next; //指向下一个节点的指针
};
typedef PtrToPolyNode Polynomial; //多项式类型定义为指向PolyNode的指针
```
然后可以按照如下方式构建链表:
```
Polynomial CreatePolyNode() {
Polynomial P, Rear, Tmp;
int c, e, N;
scanf("%d", &N);
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->next = NULL;
Rear = P;
while (N--) {
scanf("%d %d", &c, &e);
Tmp = (Polynomial)malloc(sizeof(struct PolyNode));
Tmp->coef = c;
Tmp->expo = e;
Tmp->next = NULL;
Rear->next = Tmp;
Rear = Tmp;
}
Tmp = P;
P = P->next;
free(Tmp);
return P;
}
```
这个函数可以从标准输入中读入一元多项式的系数和指数,然后依次创建每个节点并将其添加到链表中,最后返回链表头指针。
实现一元多项式计算的具体方法可以参考如下代码:
```
Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
Polynomial front, rear, temp;
int sum;
rear = (Polynomial)malloc(sizeof(struct PolyNode));
front = rear;
while (P1 && P2) {
if (P1->expo > P2->expo) {
Attach(P1->coef, P1->expo, &rear);
P1 = P1->next;
} else if (P1->expo < P2->expo) {
Attach(P2->coef, P2->expo, &rear);
P2 = P2->next;
} else {
sum = P1->coef + P2->coef;
if (sum) Attach(sum, P1->expo, &rear);
P1 = P1->next;
P2 = P2->next;
}
}
for (; P1; P1 = P1->next) Attach(P1->coef, P1->expo, &rear);
for (; P2; P2 = P2->next) Attach(P2->coef, P2->expo, &rear);
rear->next = NULL;
temp = front;
front = front->next;
free(temp);
return front;
}
void Attach(int c, int e, Polynomial *prear) {
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c;
P->expo = e;
P->next = NULL;
(*prear)->next = P;
*prear = P;
}
```
这个函数实现了两个一元多项式相加的功能,具体过程是比较两个多项式当前节点的指数大小,按照从大到小的顺序将结果依次添加到新的链表中。如果两个节点的指数相同,则将它们的系数相加,如果和不为0,则将结果添加到新的链表中。最后将新的链表头指针返回即可。
注意,在使用完链表后需要及时释放内存,以免造成内存泄漏。
阅读全文