首先来描述一下我们要解决的问题:现有两个一元多项式A和B,计算A+B的结果。例如:
这两个多项式用链表的表示如下:
链表中,用两个变量分别来存放x的指数和系数,下面来看一下这个链表的数据结构:
//多项式每一项节点 typedef struct s_node { //指数 int exp; //系数 int coe; //下一节点指针 struct s_node *next; } s_node; //表数据结构 typedef struct { //头节点 s_node *header; } s_list;
下面来实现多项式链表的功能函数:
//构建一个顺序线性表 bool init_list(s_list *list) { if (list == null) { return false; } list->header = null; return true; } //销毁表 bool destroy_list(s_list *list) { if (list == null) { return false; } if (list->header == null) { return true; } //从头节点开始释放 s_node *p = list->header; while (p != null) { s_node *t = p; p = p->next; free(t); } list->header = null; return true; } //插入一个新元素 bool list_insert(s_list *list, int e, int c) { if (list == null) { return false; } //申请新节点内存 s_node *p_new = (s_node *) malloc(sizeof(s_node)); p_new->exp = e; p_new->coe = c; p_new->next = null; //如果头节点为空 if (list->header == null) { //设置头节点为插入元素 list->header = p_new; return true; } else { s_node *p = list->header; while (p->next != null) { p = p->next; } p->next = p_new; } return false; } //多项式相加 bool list_add(s_list *list_one, s_list *list_two, s_list *list_out) { if (list_one == null || list_two == null || list_out == null) { return false; } //取得等等相加的多项式头节点 s_node *p1 = list_one->header; s_node *p2 = list_two->header; //循环相加 while (!(p1 == null && p2 == null)) { //如果p1为空,则处理剩余的p2项 if (p1 == null && p2 != null) { list_insert(list_out, p2->exp, p2->coe); p2 = p2->next; } //如果p2为空,则处理剩余的p1项 else if (p1 != null && p2 == null) { list_insert(list_out, p1->exp, p1->coe); p1 = p1->next; } //如果p1的指数小,则处理p1 else if (p1->exp < p2->exp) { list_insert(list_out, p1->exp, p1->coe); p1 = p1->next; } //如果p2的指数小,则处理p2 else if (p1->exp > p2->exp) { list_insert(list_out, p2->exp, p2->coe); p2 = p2->next; } //如果指数相同 else if (p1->exp == p2->exp) { //如果计算系数结果不为0,则处理 if (p1->coe + p2->coe != 0) { list_insert(list_out, p1->exp, p1->coe + p2->coe); } p1 = p1->next; p2 = p2->next; } } return true; } //显示多项式 bool list_display(s_list *list) { if (list == null || list->header == null) { return false; } //顺序访问每一个元素 s_node *p = list->header; while (p != null) { if (p == list->header) { printf("%d", p->coe); } else { printf("%+d", p->coe); } if (p->exp != 0) { if (p->exp == 1) { printf("x", p->exp); } else { printf("x^%d", p->exp); } } p = p->next; } return true; }
最后写一个main函数来测试,多项式的项按指数升序(由低到高)的顺序插入链表,这里不考虑链表排序的问题:
int main(int argc, char **args) { //构建多项式A s_list listA; init_list(&listA); list_insert(&listA, 0, 4); list_insert(&listA, 1, 5); list_insert(&listA, 2, 6); list_insert(&listA, 4, -8); list_insert(&listA, 5, 3); list_insert(&listA, 7, -7); list_display(&listA); printf("\n"); //构建多项式B s_list listB; init_list(&listB); list_insert(&listB, 0, 9); list_insert(&listB, 1, -3); list_insert(&listB, 2, -1); list_insert(&listB, 3, 3); list_insert(&listB, 5, -7); list_insert(&listB, 8, 3); list_display(&listB); printf("\n"); s_list listC; init_list(&listC); list_add(&listA, &listB, &listC); list_display(&listC); //销毁list destroy_list(&listA); destroy_list(&listB); destroy_list(&listC); return 0; }
运行结果:
4+5x+6x^2-8x^4+3x^5-7x^7 9-3x-1x^2+3x^3-7x^5+3x^8 13+2x+5x^2+3x^3-8x^4-4x^5-7x^7+3x^8
本例代码:
code path chapter.01/e.g.1.5/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号