数据结构实现两个多项式的相加和相减

数据结构实现两个多项式的相加和相减 本文将讨论使用单链表存储多项式，并实现两个多项式的相加和相减操作。 多项式的存储和表示 在本文中，我们使用单链表来存储多项式。每个结点代表一个多项式项，包含系数和指数两个成员变量。我们使用结构体 PolyNode 来定义单链表结点类型，其中 coef 成员变量存储系数，exp 成员变量存储指数。 ```c typedef struct pnode { int coef; // 系数 int exp; // 指数 struct pnode *next; } PolyNode, *Polylist; ``` 多项式的输入和排序 我们使用函数 polycreate() 来创建一个多项式，并将其存储在单链表中。该函数将读取用户输入的系数和指数，对应的多项式项，并将其添加到单链表中。我们使用函数 PolySort() 将单链表中的多项式项按指数从大到小排序。 ```c Polylist polycreate() { // ... while (c != 0) { s = (PolyNode *)malloc(sizeof(PolyNode)); s->coef = c; s->exp = e; s->next = rear->next; rear->next = s; rear = s; scanf("%d %d", &c, &e); } s->next = NULL; return head; } void PolySort(PolyNode *&head) { PolyNode *p = head->next, *q, *r; if (p != NULL) { r = p->next; p->next = NULL; p = r; while (p != NULL) { r = p->next; q = head; while (q->next != NULL && q->next->exp > p->exp) q = q->next; p->next = q->next; q->next = p; p = r; } } } ``` 多项式的相加和相减 我们使用函数 PolyAdd() 来实现两个多项式的相加操作。该函数将两个多项式的结点逐个比较，如果指数相同，则将系数相加，否则，将结点添加到结果多项式中。 ```c void PolyAdd(PolyNode *ha, PolyNode *hb, PolyNode *&hc) { PolyNode *pa = ha->next, *pb = hb->next, *s, *pre; int sum; hc = (PolyNode *)malloc(sizeof(PolyNode)); pre = hc; while (pa != NULL && pb != NULL) { if (pa->exp > pb->exp) { s = (PolyNode *)malloc(sizeof(PolyNode)); s->exp = pa->exp; s->coef = pa->coef; pre->next = s; pre = s; pa = pa->next; } else if (pa->exp < pb->exp) { s = (PolyNode *)malloc(sizeof(PolyNode)); s->exp = pb->exp; s->coef = pb->coef; pre->next = s; pre = s; pb = pb->next; } else { sum = pa->coef + pb->coef; if (sum != 0) { s = (PolyNode *)malloc(sizeof(PolyNode)); s->exp = pa->exp; s->coef = sum; pre->next = s; pre = s; } pa = pa->next; pb = pb->next; } } if (pb != NULL) pa = pb; while (pa != NULL) { s = (PolyNode *)malloc(sizeof(PolyNode)); s->exp = pa->exp; s->coef = pa->coef; pre->next = s; pre = s; pa = pa->next; } pre->next = NULL; } ``` 本文讨论了使用单链表存储多项式，并实现了两个多项式的相加和相减操作。该算法可以应用于多项式的计算和处理中。