close

  上一篇介紹了鏈結串列也實際的操作(新增、刪除、插入、查看)，這次要用鏈結串列來實作多項式的相加。

 

 

什麼是多項式?

 

A = 5x^4+6x^2+3x+6

B = 9x^5+3x^2+4x+5

C = 9x^5 + 5x^4 + 9x^2 + 7x + 11

 

  上面這兩個就是多項式，我們按照次方降冪(高->低)的排列之後相加，就可以得出我們的C，接下來就開始實作了，我會聚焦在兩個多項式的相加，新增跟查看的方法就不贅述了，下面會提供完整的程式碼。

 

 

多項式相加實作

 

1.新增結構

 

1
2
3
4
5
6
 
typedef struct Polynomial
{
	int con;
	int pow;
	Polynomial *next;
}POL;

 

  這次所使用的結構會有三個位置分別儲存常數、次方跟下一個位置。

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
int main()
{
	POL *A,*B,*C;
	
	A = new Polynomial;
	B = new Polynomial;
	C = new Polynomial;

	return 0;
}

 

 

 

2.新增多項式

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
void add_Node(Polynomial *cu, int con, int pow)
{
	while(true)
	{
		if(cu->next == NULL)
		{
			cu->next = new Polynomial;
			cu = cu->next;
			cu->con = con;
			cu->pow = pow;
			cu->next = NULL;
			break;
		}else
		{
			cu= cu->next;
		}
	}
}

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
 
int main()
{
	POL *A,*B,*C;
	
	A = new Polynomial;
	B = new Polynomial;
	C = new Polynomial;

	add_Node(A,  5, 4); 
	add_Node(A,  6, 3);
	add_Node(A,  6, 2);
	
	add_Node(B,  9, 5);
	add_Node(B,  3, 3);
	add_Node(B,  4, 1);
	add_Node(B,  2, 0);

	return 0;
}

 

3.檢查多項式

 

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
void check_Node(Polynomial *cu)
{
	while(true)
	{
		cu = cu->next;
		
		if(cu != NULL)
		{
			std::cout<<cu->con<<"x^"<<cu->pow;
			if(cu->next !=NULL)
				std::cout<<"+";
		}else
		{
			std::cout<<std::endl;
			break;
		}
	}
}

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
int main()
{
	POL *A,*B,*C;
	
	A = new Polynomial;
	B = new Polynomial;
	C = new Polynomial;
	
	A->next = NULL;
	B->next = NULL;
	C->next = NULL;
	
	add_Node(A,  5, 4); 
	add_Node(A,  6, 3);
	add_Node(A,  6, 2);
	
	add_Node(B,  9, 5);
	add_Node(B,  3, 3);
	add_Node(B,  4, 1);
	add_Node(B,  2, 0);
	
	check_Node(A);
	check_Node(B);

	return 0;
}

 

4.多項式相加

 

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
void add_up_Node(Polynomial *one, Polynomial *two, Polynomial *three)
{
	one   = one->next;
	two   = two->next;
	
	while(true)
	{
		if(one == NULL and two == NULL)
		{
			three->next = NULL;
			break;
		}
		
		three->next = new Polynomial;
		three = three->next;
		
		if(one == NULL)
		{
			three->con = two->con;
			three->pow = two->pow;
			two = two->next;
			
		}
		else if(two == NULL)
		{
			three->con = one->con;
			three->pow = one->pow;
			one = one->next;
		}
		else
		{
			if(one->pow > two->pow)
			{
				three->con = one->con;
				three->pow = one->pow;
				one = one->next;
			}
			else if(one->pow == two->pow)
			{
				three->con = (one->con+two->con);
				three->pow = one->pow;
		
				one = one->next;
				two = two->next;
			}
			else if(one->pow < two->pow)
			{
				three->con = two->con;
				three->pow = two->pow;
				two = two->next;
			}
		}

	}
}

 

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
int main()
{
	POL *A,*B,*C;
	
	A = new Polynomial;
	B = new Polynomial;
	C = new Polynomial;
	
	A->next = NULL;
	B->next = NULL;
	C->next = NULL;
	
	add_Node(A,  5, 4); 
	add_Node(A,  6, 3);
	add_Node(A,  6, 2);
	
	add_Node(B,  9, 5);
	add_Node(B,  3, 3);
	add_Node(B,  4, 1);
	add_Node(B,  2, 0);
	
	check_Node(A);
	check_Node(B);
	add_up_Node(A, B, C);
	
	check_Node(C);

	return 0;
}

 

 

 

完整程式碼

 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include<iostream>
#include<cstring>


typedef struct Polynomial
{
	int con;
	int pow;
	Polynomial *next;
}POL;


void add_Node(Polynomial *cu, int con, int pow)
{
	while(true)
	{
		if(cu->next == NULL)
		{
			cu->next = new Polynomial;
			cu = cu->next;
			cu->con = con;
			cu->pow = pow;
			cu->next = NULL;
			break;
		}else
		{
			cu= cu->next;
		}
	}
}

void check_Node(Polynomial *cu)
{
	while(true)
	{
		cu = cu->next;
		
		if(cu != NULL)
		{
			std::cout<<cu->con<<"x^"<<cu->pow;
			if(cu->next !=NULL)
				std::cout<<"+";
		}else
		{
			std::cout<<std::endl;
			break;
		}
	}
}

void add_up_Node(Polynomial *one, Polynomial *two, Polynomial *three)
{
	one   = one->next;
	two   = two->next;
	
	while(true)
	{
		if(one == NULL and two == NULL)
		{
			three->next = NULL;
			break;
		}
		
		three->next = new Polynomial;
		three = three->next;
		
		if(one == NULL)
		{
			three->con = two->con;
			three->pow = two->pow;
			two = two->next;
			
		}
		else if(two == NULL)
		{
			three->con = one->con;
			three->pow = one->pow;
			one = one->next;
		}
		else
		{
			if(one->pow > two->pow)
			{
				three->con = one->con;
				three->pow = one->pow;
				one = one->next;
			}
			else if(one->pow == two->pow)
			{
				three->con = (one->con+two->con);
				three->pow = one->pow;
		
				one = one->next;
				two = two->next;
			}
			else if(one->pow < two->pow)
			{
				three->con = two->con;
				three->pow = two->pow;
				two = two->next;
			}
		}

	}
}

int main()
{
	POL *A,*B,*C;
	
	A = new Polynomial;
	B = new Polynomial;
	C = new Polynomial;
	
	A->next = NULL;
	B->next = NULL;
	C->next = NULL;
	
	add_Node(A,  5, 4); 
	add_Node(A,  6, 3);
	add_Node(A,  6, 2);
	
	add_Node(B,  9, 5);
	add_Node(B,  3, 3);
	add_Node(B,  4, 1);
	add_Node(B,  2, 0);
	
	check_Node(A);
	check_Node(B);
	add_up_Node(A, B, C);
	
	check_Node(C);

	return 0;
}

 

結果:

A = 5x^4+6x^3+6x^2
B = 9x^5+3x^3+4x^1+2x^0
C = 9x^5+5x^4+9x^3+6x^2+4x^1+2x^0

 

 

 

 

arrow
arrow
    文章標籤
    介紹 紀錄 筆記 心得 日記 教學 基本 基礎 程式 程式語言 C++ c++
    全站熱搜
    創作者介紹
    創作者 讀書小天地 的頭像
    讀書小天地

    書籍分享天地

    讀書小天地 發表在 痞客邦 留言(0) 人氣()