从多项式相加看线性结构

前言

周三晚上再更新一波,精力有限,尽可能做到每周两更。今天咱们讲讲算法,同时我在知乎上也开了一个数据结构与算法的专栏,大家可以去看看。算法与数据结构是编程的基石,但是现在由于各种库的存在导致大家对数据结构越来越不重视,反正直接拿来用就可以。这就会导致你的技术无法更进一步,总是被大牛牵着鼻子走,而不是成为大牛,成为金字塔底层的人。

干货

给出两个多项式:

大家都很清楚多项式相加,即为相同指数项对应相加。那我们如何使用程序来描述两个多项式相加呢?大家首先想到的是用数组描述,多项式的指数使用下标来表示,前面的系数为对应数组中的值。f1(x)表示如下:

f2(x)表示如下:

其实只要写个for循环,相同下标的相加即可,非常简单。下面问题来了,如果面对的多项式是类似

这种形式的话,0项太多,上面的这种办法就会很冗余,白白浪费空间。因此需要采取另外的办法来描述。上面的方式问题出在我们使用数组下标用来描述指数,当指数很大的时,就会出现很多系数为0项,我们的想法是不要0项,只将非0项存储起来进行描述。因此我们可以将系数和指数绑定到一起作为一个整体,类似这种方式(系数,指数)。还是上面两个多项式,采用结构体+数组的方式进行描述。f1(x)表示如下:

f2(x)表示如下:

其中指数是按照由大到小的顺序存储。大家可以看到指数很大的时候,也不会浪费存储空间。下面我们用C程序来实现。

#include<stdio.h>
#define F1_LENGTH 3
#define F2_LENGTH 3
struct Node{
	int coef;
	int expon;
};
struct Node f1_nodes[3];
struct Node f2_nodes[3];
void main(){
	f1_nodes[0].coef = 3;
	f1_nodes[0].expon = 4;

	f1_nodes[1].coef = 4;
	f1_nodes[1].expon = 2;

	f1_nodes[2].coef = 1;
	f1_nodes[2].expon = 0;

	f2_nodes[0].coef = 5;
	f2_nodes[0].expon = 3;

	f2_nodes[1].coef = 4;
	f2_nodes[1].expon = 2;

	f2_nodes[2].coef = 8;
	f2_nodes[2].expon = 0;
	size_t i = 0, j = 0;
	for (; i < F1_LENGTH && j < F2_LENGTH;)
	{
		if (f1_nodes[i].expon > f2_nodes[j].expon){

			printf("(%d,%d) ", f1_nodes[i].coef, f1_nodes[i].expon);
			i++;
		
		}else if (f1_nodes[i].expon < f2_nodes[j].expon){
			printf("(%d,%d) ", f2_nodes[j].coef, f2_nodes[j].expon);
			j++;
		}else
		{
			printf("(%d,%d) ", f1_nodes[i].coef+f2_nodes[j].coef, f2_nodes[j].expon);
			i++;
			j++;
		}
	}
	while (i<F1_LENGTH)
	{
		printf("(%d,%d) ", f1_nodes[i].coef, f1_nodes[i].expon);
		i++;
	}
	while (j<F2_LENGTH)
	{
		printf("(%d,%d) ", f2_nodes[j].coef, f2_nodes[j].expon);
		j++;
	}
	getchar();}

通过上面的方式即可完成多项式的计算,但是上面的方式依然不是特别好,因为数组的大小是固定的,没办法动态改变,接下来我们使用链表的方式来存储非零项,定义如下数据类型:

f1和f2链表存储形式为:

C语言实现如下:

#include<stdio.h>
#include <malloc.h>
typedef struct Node *PolyLink;
struct Node{
	int coef;
	int expon;
	PolyLink link;

};
void main(){
	PolyLink p,p1;
	PolyLink head1 = (PolyLink)malloc(sizeof(struct Node));
	p = head1;
	p->coef = 3;
	p->expon = 4;
	p->link = (PolyLink)malloc(sizeof(struct Node));

	p = p->link;
	p->coef = 4;
	p->expon = 2;
	p->link = (PolyLink)malloc(sizeof(struct Node));

	p = p->link;
	p->coef = 1;
	p->expon = 0;
	p->link = NULL;

	PolyLink head2 = (PolyLink)malloc(sizeof(struct Node));
	p = head2;
	p->coef = 5;
	p->expon = 3;
	p->link = (PolyLink)malloc(sizeof(struct Node));

	p = p->link;
	p->coef = 4;
	p->expon = 2;
	p->link = (PolyLink)malloc(sizeof(struct Node));

	p = p->link;
	p->coef = 8;
	p->expon = 0;
	p->link = NULL;

	while(head1 != NULL && head2 != NULL){

		if (head1->expon > head2->expon){
			printf("(%d,%d) ", head1->coef, head1->expon);
			p1 = head1;
			head1 = head1->link;
			free(p1);
		}
		else if (head1->expon < head2->expon){

			printf("(%d,%d) ", head2->coef, head2->expon);
			p1 = head2;
			head2 = head2->link;
			free(p1);
		
		}
		else{
			printf("(%d,%d) ", head1->coef+head2->coef, head2->expon);
			p1 = head1;
			head1 = head1->link;
			free(p1);
			p1 = head2;
			head2 = head2->link;
			free(p1);
		
		}
	
	}
	while (head1 != NULL){
		printf("(%d,%d) ", head1->coef, head1->expon);
		p1 = head1;
		head1 = head1->link;
		free(p1);
	}
	while (head2 != NULL){
		printf("(%d,%d) ", head2->coef, head2->expon);
		p1 = head2;
		head2 = head2->link;
		free(p1);

	}
	getchar();}

总结

今天就说到这,算法和数据结构我会一直更新下去,从传统的算法一直到之后的机器学习和深度学习的内容。代码,大家还是阅读原文吧。

原文发布于微信公众号 - 七夜安全博客(qiye_safe)

原文发表时间:2017-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

Python 再牛,在字符串排序上还是被 Julia 和 R 碾压

在《实例对比 Julia, R, Python,谁是狼语言?》我们简单介绍了 Julia 的背景,以及通过优化一个似然函数的参数 μ 和 σ,来对比 Julia...

1133
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

3109
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

1752
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

1952
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

1974
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

2074
来自专栏机器学习算法与Python学习

Python技巧 101:这17个骚操作你都Ok吗

Python 是一门非常优美的语言,其简洁易用令人不得不感概人生苦短。在本文中,作者 Gautham Santhosh 带我们回顾了 17 个非常有用的 Pyt...

984
来自专栏架构说

折半查找部分有序

部分有序 本周qq群有人咨询 Search in Rotated Sorted Array 来源: https://leetcode.com/proble...

2839
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

3167
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

2299

扫码关注云+社区