从多项式相加看线性结构

前言

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

干货

给出两个多项式:

大家都很清楚多项式相加,即为相同指数项对应相加。那我们如何使用程序来描述两个多项式相加呢?大家首先想到的是用数组描述,多项式的指数使用下标来表示,前面的系数为对应数组中的值。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 条评论
登录 后参与评论

相关文章

来自专栏算法channel

动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

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

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

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

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

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

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

2142
来自专栏计算机视觉与深度学习基础

Leetcode 15 3Sum + 有趣的小BUG

Given an array S of n integers, are there elements a, b, c in S such that a + b...

2306
来自专栏数据结构与算法

T4310 祖玛游戏

题目描述 祖玛是一款曾经风靡全球的游戏,其玩法是:在一条轨道上初始排列着若干 个彩色珠子,其中任意三个相邻的珠子不会完全同色。此后,你可以发射珠子到 轨道上并加...

3838
来自专栏Android知识点总结

1.计算机编程通之字节与数据类型

1607
来自专栏人工智能头条

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

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

1313
来自专栏包子铺里聊IT

How to calculate “hard” runtime complexity?

在技术面试中,准确说出一个解法的runtime complexity(算法时间复杂度)是一个非常重要的点。考虑到对于算法时间复杂度的理解是CS领域的基础,因此这...

2888
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

1313
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

2124

扫码关注云+社区

领取腾讯云代金券