多项式加法运算（链表实现）

2024-07-16 01:38:11| 来源: 网络整理| 查看: 265

文章目录创建结点类型打印多项式尾插插入排序多项式相加代码总览 + 结果展示

创建结点类型

我们用链表存储一个多项式，那么该链表的每一个结点就代表多项式的某一项。所以我们的每一个结点必须包含三个信息：多项式的系数、多项式的指数以及指向下一个结点的指针。

typedef int SLTDataType;//指数、系数类型 typedef struct SListNode { SLTDataType coef;//系数 SLTDataType expon;//指数 struct SListNode* next;//用于存放下一个结点的地址 }SListNode; 打印多项式

传入一个指向多项式链表的指针，遍历该链表依次打印链表内容。（一次打印一个结点）

//打印多项式 void SListPrint(SListNode* head) { SListNode* cur = head; if (cur) { printf("%dx^%d", cur->coef, cur->expon);//打印第一项 cur = cur->next; } while (cur) { printf("%+dx^%d", cur->coef, cur->expon); cur = cur->next; } printf("\n"); }

注：需将第一项拿出来单独打印，因为我们不希望第一项系数的正号被打印出来（若第一项系数为正）。

尾插

将一个项尾插到一个多项式的后面。我们需要申请一个新结点，将要求的系数和指数赋值给这个新结点，并将新结点的指针域置空，然后尾插到目标多项式的后面。

//创建一个新结点，返回新结点地址 SListNode* BuySLTNode(SLTDataType coef, SLTDataType expon) { SListNode* node = (SListNode*)malloc(sizeof(SListNode));//向新结点申请空间 if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->coef = coef;//系数赋值 node->expon = expon;//指数赋值 node->next = NULL;//将新结点的指针域置空 return node;//返回新结点地址 } //尾插 void SListPushBack(SListNode** pHead, SLTDataType coef, SLTDataType expon) { SListNode* newnode = BuySLTNode(coef, expon);//申请一个新结点 if (*pHead == NULL)//判断是否为空表 { *pHead = newnode;//头指针直接指向新结点 } else { SListNode* tail = *pHead;//接收头指针 while (tail->next != NULL)//若某结点的指针域为NULL，说明它是最后一个结点 { tail = tail->next;指针指向下一个结点 } tail->next = newnode;//让最后一个结点的指针域指向新结点 } }

注：若原多项式为空，即链表为空，直接让原链表指针指向新申请的结点即可。

插入排序

输入的多项式可能并不是有序的，这时我们需要将多项式按指数降序排列（或按指数升序排列），以简化后续多项式的相加操作，这里我们选用插入排序算法。

//插入排序 SListNode* InsertSortList(SListNode* head) { if (head == NULL || head->next == NULL)//若链表为空或链表只有一个结点，则不需排序 return head; SListNode* sortHead = head;//记录排序后链表的第一个结点 SListNode* cur = head->next;//从待排链表的第二个结点开始排序 sortHead->next = NULL;//默认链表的第一个结点有序，设置其指针域为空 while (cur) { SListNode* next = cur->next;//记录当前正在排序的结点的下一个结点 SListNode* c = sortHead;//记录当前遍历到的有序链表的结点位置 SListNode* p = NULL;//记录c的前一个结点位置 while (c) { if (cur->expon > c->expon)//待插入结点的指数大于当前遍历到的有序链表的结点的指数 { break; } else//待插入结点与有序链表中的下一个结点比较 { p = c; c = c->next; } } if (p == NULL)//将待插入结点插入到有序链表的第一个位置 { cur->next = sortHead; sortHead = cur; } else//将待插入结点插入到p和c之间 { cur->next = c; p->next = cur; } cur = next;//插入下一个待插入结点 } return sortHead;//返回排列好的链表 } 多项式相加

从两个待相加的多项式的表头开始，比较两个结点的指数大小，若相同，则将两个结点的系数相加得到新的系数，申请一个新结点（结点的系数为新得到的系数，指数与这两个结点的指数相同）尾插到新链表的后面即可。若两个结点的指数不相同，则申请一个新结点（新结点的系数和指数与两个结点中指数较大的结点相同）尾插到新链表后面即可。

//比较两个结点的指数大小 int Compare(SLTDataType e1, SLTDataType e2) { if (e1 > e2) return 1; else if (e1 switch (Compare(P1->expon, P2->expon))//比较指数 { case 1: SListPushBack(&front, P1->coef, P1->expon); P1 = P1->next; break; case -1: SListPushBack(&front, P2->coef, P2->expon); P2 = P2->next; break; case 0: SLTDataType sum = P1->coef + P2->coef; if (sum) SListPushBack(&front, sum, P1->expon); P1 = P1->next; P2 = P2->next; break; } } while (P1)//将P1剩余项尾插到链表后面 { SListPushBack(&front, P1->coef, P1->expon); P1 = P1->next; } while (P2)//将P2剩余项尾插到链表后面 { SListPushBack(&front, P2->coef, P2->expon); P2 = P2->next; } return front;//返回新链表 }

可以对照下图进行逻辑分析：在这里插入图片描述注：当两个指数相同的结点的系数相加为0时，不必申请新结点插入新链表。

代码总览 + 结果展示 #include #include #include typedef int SLTDataType;//指数、系数类型 typedef struct SListNode { SLTDataType coef;//系数 SLTDataType expon;//指数 struct SListNode* next;//用于存放下一个结点的地址 }SListNode; //打印多项式 void SListPrint(SListNode* head) { SListNode* cur = head; if (cur) { printf("%dx^%d", cur->coef, cur->expon);//打印第一项 cur = cur->next; } while (cur) { printf("%+dx^%d", cur->coef, cur->expon); cur = cur->next; } printf("\n"); } //创建一个新结点，返回新结点地址 SListNode* BuySLTNode(SLTDataType coef, SLTDataType expon) { SListNode* node = (SListNode*)malloc(sizeof(SListNode));//向新结点申请空间 if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->coef = coef;//系数赋值 node->expon = expon;//指数赋值 node->next = NULL;//将新结点的指针域置空 return node;//返回新结点地址 } //尾插 void SListPushBack(SListNode** pHead, SLTDataType coef, SLTDataType expon) { SListNode* newnode = BuySLTNode(coef, expon);//申请一个新结点 if (*pHead == NULL)//判断是否为空表 { *pHead = newnode;//头指针直接指向新结点 } else { SListNode* tail = *pHead;//接收头指针 while (tail->next != NULL)//若某结点的指针域为NULL，说明它是最后一个结点 { tail = tail->next;指针指向下一个结点 } tail->next = newnode;//让最后一个结点的指针域指向新结点 } } //选择排序 SListNode* InsertSortList(SListNode* head) { if (head == NULL || head->next == NULL)//若链表为空或链表只有一个结点，则不需排序 return head; SListNode* sortHead = head;//记录排序后链表的第一个结点 SListNode* cur = head->next;//从待排链表的第二个结点开始排序 sortHead->next = NULL;//默认链表的第一个结点有序，设置其指针域为空 while (cur) { SListNode* next = cur->next;//记录当前正在排序的结点的下一个结点 SListNode* c = sortHead;//记录当前遍历到的有序链表的结点位置 SListNode* p = NULL;//记录c的前一个结点位置 while (c) { if (cur->expon > c->expon)//待插入结点的指数大于当前遍历到的有序链表的结点的指数 { break; } else//待插入结点与有序链表中的下一个结点比较 { p = c; c = c->next; } } if (p == NULL)//将待插入结点插入到有序链表的第一个位置 { cur->next = sortHead; sortHead = cur; } else//将待插入结点插入到p和c之间 { cur->next = c; p->next = cur; } cur = next;//插入下一个待插入结点 } return sortHead;//返回排列好的链表 } //比较两个结点的指数大小 int Compare(SLTDataType e1, SLTDataType e2) { if (e1 > e2) return 1; else if (e1 switch (Compare(P1->expon, P2->expon))//比较指数 { case 1: SListPushBack(&front, P1->coef, P1->expon); P1 = P1->next; break; case -1: SListPushBack(&front, P2->coef, P2->expon); P2 = P2->next; break; case 0: SLTDataType sum = P1->coef + P2->coef; if (sum) SListPushBack(&front, sum, P1->expon); P1 = P1->next; P2 = P2->next; break; } } while (P1)//将P1剩余项尾插到链表后面 { SListPushBack(&front, P1->coef, P1->expon); P1 = P1->next; } while (P2)//将P2剩余项尾插到链表后面 { SListPushBack(&front, P2->coef, P2->expon); P2 = P2->next; } return front;//返回新链表 } int main() { SListNode* P1 = NULL;//存放第一个表达式数据的链表 SListNode* P2 = NULL;//存放第二个表达式数据的链表 SLTDataType coef, expon; //1.输入两个多项式 int count = 0; printf("请输入第一个多项式的项数:>"); scanf("%d", &count); printf("请输入第一个多项式:>"); int i = 0; for (i = 0; i scanf("%dx^%d", &coef, &expon); SListPushBack(&P2, coef, expon); } //2.分别将两个多项式按指数降序排列 SListNode* SortP1 = InsertSortList(P1);//按指数排序第一个多项式 SListNode* SortP2 = InsertSortList(P2);//按指数排序第二个多项式 printf("第一个多项式按指数降序排列为:>"); SListPrint(SortP1); printf("第二个多项式按指数降序排列为:>"); SListPrint(SortP2); //3.将两个多项式相加 SListNode* PolyAddHead = PolyAdd(SortP1, SortP2);//将两个多项式相加 printf("将两个多项式相加之后的结果为:>"); SListPrint(PolyAddHead); return 0; }

在这里插入图片描述注意：多项式输入时，每一项的输入格式需相同，均为：系数x^指数。

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

多项式加法运算（链表实现）

多项式加法运算（链表实现）

今日新闻

点击排行

推荐新闻

图片新闻

专题文章