从多项式相加看线性结构

前言

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

干货

给出两个多项式:

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

相关文章

来自专栏我是攻城师

理解算法的复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度...

772
来自专栏我的博客

算法复杂度

算法复杂度 分为时间复杂度和空间复杂度。即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。 时间复杂度 在计算机科学中,算法的时间复杂...

3106
来自专栏网络和编程

float类型加法精度损失问题(C++)

奇怪的就是:a依然是406682816,并没有加一。网上查了一些资料,这里分享一下原因。

45715
来自专栏闻道于事

算法学习(一)

不论学习有多忙,也要抽空读点书。 算法 什么是算法? 有一个很著名的公式  “程序=数据结构+算法”。 曾经跟朋友吃饭的时候我问他什么是算法,他说算法嘛,就是一...

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

洛谷P3382 【模板】三分法(三分)

970
来自专栏desperate633

LintCode 矩阵的之字型遍历题目分析代码

给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。

581
来自专栏ACM算法日常

水果Fruit(母函数) - HDU 2152

转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

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

BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)

Description 由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。 由乃认为玉米田不美,所以她决定出...

3198
来自专栏nnngu

数据结构01 算法的时间复杂度和空间复杂度

1、算法的概念: 算法 (Algorithm),是对特定问题求解步骤的一种描述。 解决一个问题往往有不止一种方法,算法也是如此。那么解决特定问题的多个算法之间如...

3003
来自专栏AI派

Numpy 修炼之道 (4)—— 基本运算操作

需要注意的是,乘法运算符*的运算在NumPy数组中也是元素级别的(这与许多矩阵语言不同)。如果想要执行矩阵乘积,可以使用dot函数:

3557

扫码关注云+社区