從多項式相加看線性結構

給出兩個多項式：

大家都很清楚多項式相加，即為相同指數項對應相加。那我們如何使用程式來描述兩個多項式相加呢？大家首先想到的是用數組描述，多項式的指數使用下标來表示，前面的系數為對應數組中的值。f1(x)表示如下：

f2(x)表示如下：

其實隻要寫個for循環，相同下标的相加即可，非常簡單。下面問題來了，如果面對的多項式是類似

這種形式的話，0項太多，上面的這種辦法就會很備援，白白浪費空間。是以需要采取另外的辦法來描述。上面的方式問題出在我們使用數組下标用來描述指數，當指數很大的時，就會出現很多系數為0項，我們的想法是不要0項，隻将非0項存儲起來進行描述。是以我們可以将系數和指數綁定到一起作為一個整體，類似這種方式(系數，指數)。還是上面兩個多項式，采用結構體+數組的方式進行描述。f1(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();
}
      

　　通過上面的方式即可完成多項式的計算，但是上面的方式依然不是特别好，因為數組的大小是固定的，沒辦法動态改變，接下來我們使用連結清單的方式來存儲非零項，定義如下資料類型:

typedef struct Node *PolyLink;
struct Node
{
int coef;
int expon;
PolyLink link;

};
      

　　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();

}
      

今天的分享就到這裡，下一篇繼續分析。如果大家覺得還可以呀，記得推薦呦。

歡迎大家支援我公衆号:

        
  
        

本文章屬于原創作品,歡迎大家轉載分享，禁止修改文章的内容。尊重原創,轉載請注明來自:七夜的故事 http://www.cnblogs.com/qiyeboy/