【ZZULI数据结构实验一】多项式的三则运算

2024-03-26 12:12
文章标签 数据结构 实验 运算 多项式 三则 zzuli

本文主要是介绍【ZZULI数据结构实验一】多项式的三则运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【ZZULI数据结构实验一】多项式的四则运算

  • ♋ 结构设计
  • ♋ 方法声明
  • ♋ 方法实现
    • 🐇 定义一个多项式类型并初始化---CreateDataList
    • 🐇 增加节点---Getnewnode
    • 🐇 打印多项式类型的数据-- PrintPoly
    • 🐇 单链表的尾插--Listpush_back
    • 🐇 多项式相加--PolyAdd
    • 🐇 多项式相减-- PolySub
    • 🐇 多项式相乘--PolyMult
    • 🐇 销毁单链表--Destroy
  • ♋ 测试

📃博客主页： 小镇敲码人
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌏 任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎
❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞

前言：本篇博客旨在个人学习，实现了多项式的加减乘运算，对代码的正确性不作100%的保证。

♋ 结构设计

这里我们使用带头单链表来存储多项式的数据（各项系数及其幂次），也可以用顺序表来存数据，但是这样头插不太方便，而且需要另外创建一个节点类型放一个项的系数和幂次。如果你对单链表还留有疑问，可以看看博主的这篇文章单链表详解
这个和下面的方法声明都放到头文件里。
在这里插入图片描述

typedef struct DataList
{int coe;//系数int power;//幂次struct DataList* next;
}List;

♋ 方法声明

List* CreateDataList();//输入数据并构造数据单链表的函数List* PolyAdd(List* A,List* B);//实现多项式相加List* PolySub(List* A,List* B);//实现多项式相减List* PolyMult(List* A,List* B);//实现多项式相乘List* Getnewnode(int coe_, int power_);//申请一个节点，并初始化void PrintPoly(List* A);//打印多项式void Listpush_back(List* C, int coe_,int power_);//尾插节点void Destroy(List* A);//销毁节点

♋ 方法实现

方法实现放到.c文件里。

在这里插入图片描述

🐇 定义一个多项式类型并初始化—CreateDataList

初始化就是放数据的过程，这里直接走一个循环，然后申请空间就可以了，如果你对申请空间有疑问，请看博主这篇文章C语言动态内存管理，这里我们规定输入数据时，应该先输入幂次大的节点（先输入系数，再输入幂次），然后下一次节点链接我们直接头插就可以保证多项式类型的节点从左到右是按照幂次升序存储的（方便后序的四则运算），单链表的头插比尾插简单（尾插需要找尾）。

这里当然你也可以乱输入，增加一个排序函数就可以（按照幂次排）。小小实验我们并不需要这么麻烦，直接输入让它有序就可以了（dog。

这里我们选择带头的单链表，是为了避免头插时没有数据的判空。

代码实现：

List* CreateDataList()
{int coe_ = 0, power_ = 0;//初始化两个临时变量，用于输入每个节点的数据printf("请依次按照幂次从大到小输入数据，先输入多项式的系数，后输入幂次：\n");//提示信息List* Head = Getnewnode(-1, -1);//设置空的头节点while(scanf("%d%d", &coe_, &power_) != EOF){List* newnode = Getnewnode(coe_, power_);newnode->next = Head->next;Head->next = newnode;printf("请依次按照幂次从大到小输入数据，先输入多项式的系数，后输入幂次：\n");//提示信息,每次输入数据前都打印一次,这里会多打印一次无伤大雅} return Head;//返回头节点
}

🐇 增加节点—Getnewnode

我们在很多地方都需要申请节点，而且要初始化，为了不造成代码冗余，我们把其单独作为一个函数写出来，用的时候直接调用就好了。

代码实现：

List* Getnewnode(int coe_, int power_)
{List* newnode = (List*)malloc(sizeof(List));//在堆上申请空间if (newnode == NULL)//如果申请失败{printf("malloc Failed\n");exit(-1);}//初始化新节点newnode->coe = coe_;newnode->power = power_;newnode->next = NULL;//注意next要置空，否则会造成野指针的问题return newnode;//返回新节点
}

🐇 打印多项式类型的数据-- PrintPoly

这个函数就是单纯的打印，为了方便我们后序打印多项式类型看相加和相乘、以及相减的结果，当然你也可以通过调试查看。

代码实现：

void PrintPoly(List* A)//打印多项式
{assert(A);//防止A为空，我们不能对空解引用，assert函数相当于暴力检查List* cur = A->next;//从头节点的下一个节点开始遍历，因为头节点不存数据if (cur == NULL)//cur为空printf("多项式为空\n");while (cur != NULL)//cur不为空{if (cur->coe > 0 && cur != A->next)printf("+%d*(x^%d)", cur->coe, cur->power);elseprintf("%d*(x^%d)", cur->coe, cur->power);cur = cur->next;}printf("\n");
}

🐇 单链表的尾插–Listpush_back

在多项式相加的函数里面我们会用到单链表的尾插，如果你对其原理不太熟悉，请自行翻阅博主之前的博客。

代码实现：

void Listpush_back(List* C, int coe_, int power_)//尾插数据
{assert(C);//C不为空List* newnode = Getnewnode(coe_, power_);//申请新节点并初始化List* tail = C;while (tail->next)//找尾节点{tail = tail->next;}tail->next = newnode;//把新节点链接到尾节点的后面
}

🐇 多项式相加–PolyAdd

我们的多项式相加的思路类似双指针，O(N)时间复杂度内完成。

下面我们画图来分析一下这个过程：

在这里插入图片描述

  • 注意：这里为什么是尾插到C中呢？因为尾插才能保证C中数据是按幂次升序的，因为A和B中的数据都是按幂次升序排列的，我们为什么不把数据放到A和B中的其中一个呢，因为这样会改变A和B的内容，后面我们可能会对A、B做其它操作。

代码实现：

List* PolyAdd(List* A, List* B)
{assert(A && B);//断言，防止A或者B为空指针List* C = Getnewnode(-1, -1);//创建新的链表C，我们不希望改变链表A和B的值，所以把它们相加的结果存入C中List* curA = A->next;List* curB = B->next;while (curA && curB)//A和B的当前位置都不能为空{if (curA->power == curB->power)//如果当前幂次相等，A和B的系数相加，幂次不变，尾插到C中{int new_coe = curA->coe + curB->coe;if (new_coe != 0)Listpush_back(C, new_coe, curA->power);curA = curA->next;curB = curB->next;}else if (curA->power < curB->power)//如果B大，尾插curA{Listpush_back(C, curA->coe, curA->power);curA = curA->next;}else//否则尾插curB{Listpush_back(C, curB->coe, curB->power);curB = curB->next;}}//如果两个链表还有一个剩余，把剩下的数据尾插到C中while (curA){Listpush_back(C, curA->coe, curA->power);curA = curA->next;}while (curB){Listpush_back(C,curB->coe, curB->power);curB = curB->next;}return C;//返回相加的结果链表的头节点指针
}

🐇 多项式相减-- PolySub

多项式相减的大致思路都和多项式相加是一样的，有一个地方要注意，因为是A-B，当B中式子多时，A中对应项的系数就是0，要给B的系数加上负号。

代码实现：

// 定义PolySub函数，接受两个多项式链表A和B作为参数，返回相减后的多项式链表C  
List* PolySub(List* A, List* B)  
{  // 断言A和B都不为空，确保传入的多项式链表是有效的  assert(A && B);  // 创建一个新的链表C，并初始化其头节点（这里用-1作为占位符，实际使用中可能需要其他方式初始化）  List* C = Getnewnode(-1, -1);  // 初始化两个指向A和B链表中第一个实际节点的指针curA和curB  List* curA = A->next;  List* curB = B->next;  // 当curA和curB都不为空时，循环进行以下操作  while (curA && curB)  {  // 如果curA和curB指向的项的指数相同  if (curA->power == curB->power)  {  // 计算两个相同指数项的系数之差  int new_coe = curA->coe - curB->coe;  // 如果系数之差不为0，则将新的项（系数和指数）添加到C链表中  if (new_coe != 0)  Listpush_back(C, new_coe, curA->power);  // 移动curA和curB到下一个节点  curA = curA->next;  curB = curB->next;  }  // 如果curA指向的项的指数小于curB指向的项的指数  else if (curA->power < curB->power)  {  // 将curA指向的项（系数和指数）添加到C链表中  Listpush_back(C, curA->coe, curA->power);  // 移动curA到下一个节点  curA = curA->next;  }  // 否则（即curA指向的项的指数大于curB指向的项的指数）  else  {  // 将curB指向的项的相反数（系数取反，指数不变）添加到C链表中，实现减法  Listpush_back(C, -curB->coe, curB->power);  // 移动curB到下一个节点  curB = curB->next;  }  }  // 如果curA还有剩余节点（即A的某些项在B中没有对应项）  while (curA)  {  // 将这些项（系数和指数）添加到C链表中  Listpush_back(C, curA->coe, curA->power);  // 移动curA到下一个节点  curA = curA->next;  }  // 如果curB还有剩余节点（即B的某些项在A中没有对应项）  while (curB)  {  // 将这些项的相反数（系数取反，指数不变）添加到C链表中，实现减法  Listpush_back(C, -curB->coe, curB->power);  // 移动curB到下一个节点  curB = curB->next;  }  // 返回相减后的多项式链表C  return C;  
}

🐇 多项式相乘–PolyMult

相乘的思路是复用多项式相加的函数，先让B链表中的第一个项和A中各个项相乘（系数相乘，幂次相加），然后得到链表C，然后移动B继续和A中的各个相相乘，并执行多项式相加，最终得到结果。

代码实现：

// 定义PolyMult函数，接受两个多项式链表A和B作为参数，返回相乘后的多项式链表C  
List* PolyMult(List* A, List* B)  
{  // 断言A和B都不为空，确保传入的多项式链表是有效的  assert(A && B);  // 创建一个新的链表C，并初始化其头节点（这里用-1作为占位符）  List* C = Getnewnode(-1, -1);  // 初始化两个指针curA和curB，分别指向A和B链表中第一个实际节点  List* curA = A->next;  List* curB = B->next;  // 遍历curA指向的A链表中的每个项  while (curA)  {  // 计算当前curA指向的项与B链表中第一个项（curB指向的项）的乘积的系数和指数  int new_coe = (curA->coe) * (curB->coe);  int new_power = curA->power + curB->power;  // 将新的项（系数和指数）添加到C链表中  Listpush_back(C, new_coe, new_power);  // 移动curA到下一个节点  curA = curA->next;  }  // 初始化ans为NULL，用于存储最终的乘法结果  List* ans = NULL;  // 遍历curB指向的B链表中的每个项（从第二个项开始，因为第一个项已经在上面的循环中处理过了）  while (curB->next)  {  // 移动curB到下一个节点  curB = curB->next;  // 创建一个新的链表C1，用于存储当前curB指向的项与A链表中所有项的乘积结果  List* C1 = Getnewnode(-1, -1);  // 初始化curA，重新指向A链表中第一个实际节点  List* curA = A->next;  // 遍历curA指向的A链表中的每个项  while (curA)  {  // 计算当前curA指向的项与当前curB指向的项的乘积的系数和指数  int new_coe = (curA->coe) * (curB->coe);  int new_power = curA->power + curB->power;  // 将新的项（系数和指数）添加到C1链表中  Listpush_back(C1, new_coe, new_power);  // 移动curA到下一个节点  curA = curA->next;  }  // 将C链表和C1链表相加，得到当前curB指向的项与A链表相乘的结果，并更新ans  ans = PolyAdd(C, C1);  // 销毁C1链表，释放其占用的内存  Destroy(C1);  // 销毁C链表，释放其占用的内存（C现在保存的是上一轮的结果，我们不再需要它）  Destroy(C);  // 将ans赋值给C，准备进行下一轮的乘法运算  C = ans;  }  // 返回最终的乘法结果链表C  return C;  
}

这里由于我们的C1、和C链表每一次循环都会变成新的链表，我们要及时把旧的链表空间释放，防止内存泄漏的出现。

🐇 销毁单链表–Destroy

这里在多项式相乘函数里，会出现内存泄漏，我们需要及时回收空间，防止出现这种情况。

代码实现：

void Destroy(List* A)//销毁链表
{assert(A);List* cur = A;while (cur){List* cur_next = cur->next;//保存下一个节点的地址free(cur);//释放当前节点的空间cur = cur_next;//指针指向下一个节点}
}

♋ 测试

测试函数我们放到了main.c函数里，主要测试函数的各种功能是否和我们的预期一样，当然由于测试的数据有限，如有bug，欢迎指出。

#include"polynomial.h"void Test()
{List* A = CreateDataList();List* B = CreateDataList();List* AAddB = PolyAdd(A, B);List* ASubB = PolySub(A, B);List* AMultB = PolyMult(A, B);printf("多项式A: ");PrintPoly(A);printf("多项式B: ");PrintPoly(B);printf("多项式A+B: ");PrintPoly(AAddB);printf("多项式A-B: ");PrintPoly(ASubB);printf("多项式A*B: ");PrintPoly(AMultB);
}
int main()
{Test();return 0;
}

这里我们A输入：3 3 2 2 1 1
B输入： 4 4 3 3 2 2 1 1

运行结果：
在这里插入图片描述

和我们预期的结果一致。

这里我们A输入：1 5 1 3 1 1
B输入: 16 1 4 1 2

运行结果：

在这里插入图片描述
与预期结果一致。

这篇关于【ZZULI数据结构实验一】多项式的三则运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/848480。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
uva 575 Skew Binary（位运算）

uva 575 Skew Binary（位运算）

求第一个以（2^(k+1)-1)为进制的数。 数据不大，可以直接搞。 代码： #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
STM32(十一)：ADC数模转换器实验

STM32(十一)：ADC数模转换器实验

AD单通道： 1.RCC开启GPIO和ADC时钟。配置ADCCLK分频器。 2.配置GPIO，把GPIO配置成模拟输入的模式。 3.配置多路开关，把左面通道接入到右面规则组列表里。 4.配置ADC转换器， 包括AD转换器和AD数据寄存器。单次转换，连续转换；扫描、非扫描；有几个通道，触发源是什么，数据对齐是左对齐还是右对齐。 5.ADC_CMD 开启ADC。 void RCC_AD
阅读更多...
HNU-2023电路与电子学-实验3

HNU-2023电路与电子学-实验3

写在前面： 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能，设计 8 重 3-1 多路复用器。 3.分析模型机的功能，设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理，设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器； 2.用 VERILOG 语言设计模型机的 8 重 2-1 多
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2