程序员经验分享-hwhale

链表作业 3：多项式加法

2023-11-17

题目描述：
实现两个一元n次多项式的加法。例如P(A)=x+3x2-5x5+7，P(B)=2x2+6x3+x5-4x6，求P(A)+P(B)。

输入：每行是两个用空格隔开的整数m,n，分别代表多项式的系数和指数，以输入0 0作为结尾

输出：每次完成一个多项式的输入后，先输出该多项式；当第二个多项式输出完成后，下一行输出两个多项式输出的结果

（多项式打印的要求:  如果是第一项，不要打+号
            //如果不是第一项，且系数为正数，要打加号

            //如果系数为负数，系数自身带有符号

            //如果系数为1，不用打系数
            //系数为-1打印负号                           

            //如果系数不为1或-1，打印系数
            //如果指数为0，直接打系数不用打x^和指数
            //如果系数是-1或1，需要打1出来，不能只打符号

            //指数不为0
            //打印x
            //如果指数为1，不打指数，否则打指数）

思路：我们需要（1） 通过输入来构建链表，数据域存储系数和指数，按指数由大到小排序

（2) 以多项式的形式来打印链表

（3）将两个链表合并，指数由大到小排序

（4）清空链表

（本文章中部分代码参考了 懒猫老师《数据结构》本题的模板！有错误欢迎指正哦！）

（测试用例可以在懒猫老师的这篇文章中找到懒猫老师-C语言-链表作业3：多项式加法(代码模板) - 知乎）

目录

一，结点 

二，主函数

三，工具函数 

四，完整代码

一，结点 

typedef struct polynomial {
	int coefficient;//系数
	int exp;//指数
	struct polynomial *next;
} *Link, Node;

二，主函数

int main() {
	Link headA, headB; //两个多项式的头指针
	Link headAB;//合并后的多项式的头指针

	/*链表的初始化*/
	headA = (Link)malloc(sizeof(Node));
	headA->next = NULL;
	headB = (Link)malloc(sizeof(Node));
	headB->next = NULL;
	headAB = (Link)malloc(sizeof(Node));
	headAB->next = NULL;

	printf("请输入第一个多项式的系数和指数，以(0 0)结束：\n");
	inputPoly(headA);
	printf("第一个");
	print(headA);
	printf("请输入第二个多项式的系数和指数，以(0 0)结束：\n");
	inputPoly(headB);
	printf("第二个");
	print(headB);

	combin2List(headA, headB, headAB);
	printf("合并后");
	print(headAB);
	clearLink(headA);
	clearLink(headB);
	clearLink(headAB);
	return 0;
}

三，工具函数 

（1）创建链表的函数

这里包括两个函数，一个用来输入，一个用来创建链表，输入的函数-->再调用创建链表的函数

输入的函数：

void inputPoly(Link head) {
	int coefficient, exp; //系数和指数
	printf("请输入系数和指数(如：\"2 3\"表示2x^3)：");
	scanf("%d %d", &coefficient, &exp);
	while (coefficient != 0 || exp != 0) { //连续输入多个系数和指数
		insert(head, coefficient, exp); //调函数输入多项式
		printf("请输入系数和指数：");
		scanf("%d %d", &coefficient, &exp);
	}
}

 处理成链表的函数：(注意，每次新建链表都要记得指针域->next=NULL)

bool insert(Link head, int coefficient, int exp) {
	Link p, q, newNode;
	p = head->next;
	q = head;
	newNode = (Link)malloc(sizeof(Node));
	newNode->coefficient = coefficient;
	newNode->exp = exp;
	newNode->next = NULL;//太重要了这一行代码
	while (p != NULL) {
		//次数相等
		if (exp == p->exp) {
			p->coefficient += coefficient;
			return true;
		}
		//大于当前次数
		else if (exp > p->exp) {
			q->next = newNode;
			newNode->next = p;
			return true;
		} else {
			q = p;
			p = p->next;
		}
	}
	if (p == NULL) {
		q->next = newNode;
		newNode->next = NULL;
		return true;
	}
	return false;
}

 (2)  打印链表的函数

这里对需要用到的函数进行说明：

（1）数字转换为字符串函数itoa

 （2）字符串连接函数strcat

以两个字符串作为参数，把第2个字符串备份附加在第1个字符串末尾，并把拼接后形成的新的字符串作为第一个字符串，第二个字符串不变。

函数返回值 第一个字符串的地址

（3）字符串清空函数memset

memset(item,0,20);清空长20的字符串item

  函数：

（易错：对所有系数为0的情况，若是第一项系数为0，判断应该仍保持true,并且continue。

所以我这里添加了flag的判断，只要进入过系数非0的情况，flag=1,判断就为false了) 

void print(Link head) {
	Link p; //指向链表要输出的结点
	printf("多项式如下：\n");
	p = head->next;

	if (p == NULL) {
		printf("多项式为空\n");
		return;
	}
	// 不是空表
	char item[20] = ""; //要打印的当前多项式的一项
	char number[7] = ""; //暂时存放系数转换成的字符串
	bool isFirstItem = true;//标志是否为第一个节点
	int flag = 0;
	//打印节点
	while (p != NULL) {
		memset(item, 0, 20); //清空字符串item
		itoa(p->coefficient, number, 10);
		if (p->coefficient == 0) {//当为0时的判断非常容易出错
			if (flag == 0) {
				isFirstItem = true;	//如果第一项系数为0，移动指针，判断仍为true
				p = p->next;
				continue;
			} else if (flag == 1) {
				p = p->next;
				continue;
			}
		} else {
			if (isFirstItem != true && p->coefficient > 0) {
				strcat(item, "+");
			}
			if (p->coefficient == 1) {}
			else if (p->coefficient == -1) {
				strcat(item, "-");
			} else if (p->coefficient != 0) {
				strcat(item, number);
			}
			if (p->exp == 1) {
				strcat(item, "x");
			} else if (p->exp == 0) {
				if (p->coefficient == 1 || p->coefficient == -1)
					strcat(item, "1");
			} else {
				strcat(item, "x^");
				strcat(item, itoa(p->exp, number, 10));
			}
			flag = 1;
		}
		printf("%s", item); //打印当前节点代表的项
		p = p->next;//指向下个结点
		isFirstItem = false; //标志不是第一项了
	}
	printf("\n");
	return;
}

(3)合并链表函数
判断的关键条件：
如果指数a>指数b，a节点插入ab链表，a指针后移
如果指数a<指数b，b节点插入ab链表，b指针后移
如果指数a==指数b，a、b系数相加，插入ab链表，a、b指针后移
如果a、b链表还有尾巴，将它加到ab链表后面

void combin2List(Link heada, Link headb, Link headab) {
	Link pa, pb; //指向a，b链表和ab的指针
	pa = heada->next;
	pb = headb->next;
	while (pa != NULL && pb != NULL) { //a,b链表都没有没有访问完毕
		if (pa->exp > pb->exp) {
			insert(headab, pa->coefficient, pa->exp);
			pa = pa->next;
		} else if (pa->exp < pb->exp) {
			insert(headab, pb->coefficient, pb->exp);
			pb = pb->next;
		} else if (pa->exp == pb->exp) {
			int coefficient;
			coefficient = pa->coefficient + pb->coefficient;
			insert(headab, coefficient, pa->exp);
			pa = pa->next;
			pb = pb->next;
		}
		//如果指数a>指数b，a节点插入ab链表，a指针后移
		//如果指数a<指数b，b节点插入ab链表，b指针后移
		//如果指数a==指数b，a、b系数相加，插入ab链表，a、b指针后移
	}
	//如果a、b链表还有尾巴，将它加到ab链表后面
	while (pa != NULL) {
		insert(headab, pa->coefficient, pa->exp);
		pa = pa->next;
	}
	while (pb != NULL) {
		insert(headab, pb->coefficient, pb->exp);
		pb = pb->next;
	}
	return;

}

（4）清空链表函数

（注意这里要先单独的把头指针一释放，再p,q移动释放后面的）

void clearLink(Link head) {
	Link p, q;
	if (head == NULL)
		return;
	q = head->next;
	free(head);
	while (q != NULL) {
		p = q;
		q = q->next;
		free(p);
	}

}

四，完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct polynomial {
	int coefficient;//系数
	int exp;//指数
	struct polynomial *next;
} *Link, Node;

void inputPoly(Link head);//用于从控制台读入链表的函数
void print(Link head);//打印链表用的函数
bool insert(Link head, int coefficient, int exp); //向链表插入一个元素的函数
void combin2List(Link heada, Link headb, Link headab); //合并两个链表
void clearLink(Link head);

int main() {
	Link headA, headB; //两个多项式的头指针
	Link headAB;//合并后的多项式的头指针

	/*链表的初始化*/
	headA = (Link)malloc(sizeof(Node));
	headA->next = NULL;
	headB = (Link)malloc(sizeof(Node));
	headB->next = NULL;
	headAB = (Link)malloc(sizeof(Node));
	headAB->next = NULL;

	printf("请输入第一个多项式的系数和指数，以(0 0)结束：\n");
	inputPoly(headA);
	printf("第一个");
	print(headA);
	printf("请输入第二个多项式的系数和指数，以(0 0)结束：\n");
	inputPoly(headB);
	printf("第二个");
	print(headB);

	combin2List(headA, headB, headAB);
	printf("合并后");
	print(headAB);
	clearLink(headA);
	clearLink(headB);
	clearLink(headAB);
	return 0;
}

/**输入二项式数据的函数*/
/*这个函数用来输入二项式，给用户合适的提示，读入用户输入的系数和指数。
调用函数insert，将用户输入的二项式的一项插入到链表中去。*/
void inputPoly(Link head) {
	int coefficient, exp; //系数和指数
	printf("请输入系数和指数(如：\"2 3\"表示2x^3)：");
	scanf("%d %d", &coefficient, &exp);
	while (coefficient != 0 || exp != 0) { //连续输入多个系数和指数
		insert(head, coefficient, exp); //调函数输入多项式
		printf("请输入系数和指数：");
		scanf("%d %d", &coefficient, &exp);
	}
}

/**向多项式链表中插入元素的函数
int coefficient 一个多项式项的系数
int exp 一个多项式项的幂
*/
bool insert(Link head, int coefficient, int exp) {
	Link p, q, newNode;
	p = head->next;
	q = head;
	newNode = (Link)malloc(sizeof(Node));
	newNode->coefficient = coefficient;
	newNode->exp = exp;
	newNode->next = NULL;//太重要了这一行代码
	while (p != NULL) {
		//次数相等
		if (exp == p->exp) {
			p->coefficient += coefficient;
			return true;
		}
		//大于当前次数
		else if (exp > p->exp) {
			q->next = newNode;
			newNode->next = p;
			return true;
		} else {
			q = p;
			p = p->next;
		}
	}
	if (p == NULL) {
		q->next = newNode;
		newNode->next = NULL;
		return true;
	}
	return false;
}

/**
打印多项式链表的函数
*/
/*
①　通过指针访问链表
②　多重条件语句嵌套
③　数字转换为字符串函数itoa
④　标志是否为第一个节点的flag的设置
⑤　字符串连接函数strcat
⑥　字符串清空函数memset。memset(item,0,20);清空长20的字符串item
请补充代码实现。
*/
/*char *itoa( int value, char *string,int radix);

value：欲转换的数据；string：目标字符串的地址；radix：转换后的进制数，可以是10进制、16进制等。*/
void print(Link head) {
	Link p; //指向链表要输出的结点
	printf("多项式如下：\n");
	p = head->next;

	if (p == NULL) {
		printf("多项式为空\n");
		return;
	}
	// 不是空表
	char item[20] = ""; //要打印的当前多项式的一项
	char number[7] = ""; //暂时存放系数转换成的字符串
	bool isFirstItem = true;//标志是否为第一个节点的flag
	int flag = 0;
	//打印节点
	while (p != NULL) {
		memset(item, 0, 20); //清空字符串item
		itoa(p->coefficient, number, 10);
		if (p->coefficient == 0) {//当为0时的判断非常容易出错
			if (flag == 0) {
				isFirstItem = true;	//如果第一项系数为0，移动指针，判断仍为true
				p = p->next;
				continue;
			} else if (flag == 1) {
				p = p->next;
				continue;
			}
		} else {
			if (isFirstItem != true && p->coefficient > 0) {
				strcat(item, "+");
			}
			if (p->coefficient == 1) {}
			else if (p->coefficient == -1) {
				strcat(item, "-");
			} else if (p->coefficient != 0) {
				strcat(item, number);
			}
			if (p->exp == 1) {
				strcat(item, "x");
			} else if (p->exp == 0) {
				if (p->coefficient == 1 || p->coefficient == -1)
					strcat(item, "1");
			} else {
				strcat(item, "x^");
				strcat(item, itoa(p->exp, number, 10));
			}
			flag = 1;
		}
		printf("%s", item); //打印当前节点代表的项
		p = p->next;//指向下个结点
		isFirstItem = false; //flag标志不是第一项了
	}
	printf("\n");
	return;
}

/**
合并两个有序链表a，b到链表ab
heada.headb,headab分别为链表a,b,ab的头指针
*/
void combin2List(Link heada, Link headb, Link headab) {
	Link pa, pb; //指向a，b链表和ab的指针
	pa = heada->next;
	pb = headb->next;
	while (pa != NULL && pb != NULL) { //a,b链表都没有没有访问完毕
		if (pa->exp > pb->exp) {
			insert(headab, pa->coefficient, pa->exp);
			pa = pa->next;
		} else if (pa->exp < pb->exp) {
			insert(headab, pb->coefficient, pb->exp);
			pb = pb->next;
		} else if (pa->exp == pb->exp) {
			int coefficient;
			coefficient = pa->coefficient + pb->coefficient;
			insert(headab, coefficient, pa->exp);
			pa = pa->next;
			pb = pb->next;
		}
		//如果指数a>指数b，a节点插入ab链表，a指针后移
		//如果指数a<指数b，b节点插入ab链表，b指针后移
		//如果指数a==指数b，a、b系数相加，插入ab链表，a、b指针后移
	}
	//如果a、b链表还有尾巴，将它加到ab链表后面
	while (pa != NULL) {
		insert(headab, pa->coefficient, pa->exp);
		pa = pa->next;
	}
	while (pb != NULL) {
		insert(headab, pb->coefficient, pb->exp);
		pb = pb->next;
	}
	return;

}

void clearLink(Link head) {
	Link p, q;
	if (head == NULL)
		return;
	q = head->next;
	free(head);
	while (q != NULL) {
		p = q;
		q = q->next;
		free(p);
	}

}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构初步

链表

数据结构

算法

链表作业 3：多项式加法 的相关文章

随机推荐

  • 【嵌入式】用STM32F103c8t6芯片完成对SD卡的数据读写

    目录 一 SD卡协议 1 SD卡的体系架构 2 SD卡寄存器列表 3 SD卡初始化 SPI模式 4 SD卡读写 SPI模式 二 STM32CubeMX 三 Keil代码修改 四 电路连接 五 烧录运行结果 六 心得体会 七 参考链接 一 S

  • Linux tcpdump抓包命令

    1 tcpdump抓包命令 c 指定抓取包的数量 即最后显示的数量 i 指定tcpdump监听的端口 未指定 选择系统中最小的以配置端口 i any 监听所有网络端口 i lo 监听lookback接口 nn 对监听地址以数字方式呈现 且对

  • 新版TCGA的突变数据SNP下载和整理

    关于TCGAbiolinks包的学习前面一共介绍了5篇推文 今天继续学习如何使用TCGAbiolinks下载和整理MAF格式的突变数据 之前的TCGA的MAF文件是可以下载的 每个癌症包含4种软件得到的突变文件 后来就改版了 不让你随便下载

  • 网络篇 OSPF的路由器类型-42

    OSPF路由器类型 在OSPF初篇的时候 就说到了OSPF是一种比EIGRP协议更加复杂的大型网络配置协议 它的路由器类型也分为了好几种 现在我们通过下图来了解一个OSPF路由器类型 1 内部路由器 所有的接口都接入到同一个区域中的路由器

  • 自定义类型——结构体、枚举、联合

    一 结构体 我们知道 数组是将相同类型的元素放在一起 类似于数组 结构体是将相同或不同的元素放在一起 eg struct example example是结构体名 可以省略 但不建议省略 内部的是结构体成员 int a char c flo

  • 冲量在线创始人刘尧：以信创软硬件结合场景为突破口“占山为王”

    数据大爆炸的时代 发展信创 保证数据的安全与流通便成为刻不容缓的议题 专注于数据智能互联解决方案的科技创新企业冲量在线 致力于促进数据生产要素在社会间的互联互通 构建可信 安全 隐私 公平 高效的 数据互链网 作为隐私计算结合信创的先行者

  • php简单密码验证txt,php用户名和密码的简单验证

    5 php页面提交form表单 username password 5 1 php页面接收form表单 并进行处理 设置用户名和密码 arr user array user pwd arr pwd array user gt 1111 pw

  • React 生命周期

    React 类组件的生命周期 就是组件从创建到消耗的过程 只有类组件才有生命周期 分为 挂载阶段 更新阶段 卸载阶段 挂载阶段 钩子函数 constructor 创建组件时 最先执行 作用 初始化 state 创建 Ref 使用 bind

  • 单机版kubernetes

    Kubernetes 集群的搭建是有一定难度的 官方安装推荐了MiniKube作为单机调试 学习 1 centos安装 1 1 先决条件 安装VirtualBox KVM Note Minikube 也支持 vm driver none 选

  • 【leecode】小练习(简单8题)

    def twoSum nums target 给定 nums 2 7 11 15 target 9 因为 nums 0 nums 1 2 7 9 所以返回 0 1 type nums List int type target int rty

  • nfs漏洞的处理：目标主机showmount -e信息泄露(CVE-1999-0554)

    文章目录 前言 一 漏洞内容 二 配置现状 1 nfs server节点 etc exports文件的配置 2 client节点执行showmount e 测试 三 nfs server节点增加访问控制的配置 1 etc hosts all

  • Node.js中Redirect拼接参数方法，带参数重定向

    一 在Node js里req redirect 里拼接URL是这样的 client1 req query client client1是你获取到的需要拼接的变量 res redirect allNode client client1 注意冒

  • openstack实战之使用sysprep工具封装windows7镜像

    openstack实战之使用sysprep工具封装windows7镜像 在openstack云平台环境下 使用sysprep封装windows7系统主要目的是清理虚拟机的SID 避免使用同一windows7镜像克隆出的虚拟机出现相同的SID

  • hive数据表去重方法

    1 hive 0 8 0数据表去重方法 问题描述 hive的外部表test中 在若干字段上存在重复现象 现在需要将若干字段上值相同的多条记录 只保其中留一条 舍弃其余的 解决思路 1 group by的方法 首先新建与test表完全相同的新

  • 单点登录的解析和代码实现

    单点登录 系统简介 Http协议 web应用采用browser server架构 http作为通信协议 http是无状态协议 浏览器的每一次请求 服务器会独立处理 不与之前或之后的请求产生关联 这个过程用下图说明 三次请求 响应对之间没有任

  • 生成图片验证码的两种实现方式

    最近工作中 需求让新加一个图片验证码功能 其实这个功能之前自己写过 想必跟大家现在心里想到的实现方式一样 要么是通过servlet实现请求操作 要么是通过get请求实现操作 然后在后台通过session存储图片上的字符串 和之后前台请求过来

  • 什么是测试开发工程师？

    什么是测试开发工程师 测试开发工程师 Software Development Engineer in Test 简称SDET 是指那些既可以称作是开发人员 同时也负责软件开发阶段和测试周期的测试工作的技术人员 一个专业的SDET更关注软件

  • Matlab模拟仿真模糊PID(Fuzzy)

    研究项目 模糊PID Fuzzy 的仿真测试 研究内容 本篇文章主要研究如何通过matlab软件实现模糊PID Fuzzy 的仿真测试 研究材料 matlab 2017a软件 基本概念和定义 模糊量 如E EC 论域 上下限 240 240

  • Numpy中的argsort函数详解

    Numpy中的argsort函数返回的是每个元素的排序序号 但是不是很容易理解 gt gt gt dd mat 4 5 1 gt gt gt dd argsort matrix 2 0 1 一开始的时候想不明白为什么是2 0 1而不是1 2

  • 链表作业 3：多项式加法

    题目描述 实现两个一元n次多项式的加法 例如P A x 3x2 5x5 7 P B 2x2 6x3 x5 4x6 求P A P B 输入 每行是两个用空格隔开的整数m n 分别代表多项式的系数和指数 以输入0 0作为结尾 输出 每次完成一个

热门标签