算法学习：pta：02-线性结构2 一元多项式的乘法与加法运算_python attach函数

一共编写五个函数
分别是，读入多项式，输出多项式，相乘，相加，attach（创建新节点）。

一、先编写attach函数

在大部分函数中都需要使用它。
创建一个新节点，

void attach(int c,int e,f*prear)
{
	f p;
	p = (f)malloc(sizeof(struct p));
	p->c = c;
	p->e = e;
	p->link = NULL;
	(*prear)->link = p;
	*prear = p;
}
1
2
3
4
5
6
7
8
9
10

p是指向结构体的指针。

rear是表示当前结果多项式的最后一个指针，
prear是指针的指针，（*prear指向指针指示的变量rear）
在函数中需要改变rear的值，返回到调佣函数，
故使用指针的指针。
1
2
3
4
5
6

①动态建立一个空间，p指向这个空间，为头结点
②对新节点赋值
③使p的末尾（link）指向NULL
④修改prear的值，即链表的最后一个节点位置发生改变，rear也要变化：

(*prear)->link = p;
	*prear = p;
1
2

*prear就是rear，rear所指当前链表的最后一项，
而新节点要插入，使当前链表的最后一项link指向新节点，
再改变rear的指向
1
2
3

（point：需要有一个rear来指示链表的末端，rear是“外来”传入的）

二、读入多项式

f read()
{
	f p, rear, t;
	int c, e, n;
	scanf("%d", &n);
	p = (f)malloc(sizeof(struct p));
	p->link = NULL;
	rear = p;
	while(n--)
	{
		scanf("%d %d", &c, &e);
		attach(c, e, &rear);
	}
	t = p;p = p->link;free(t);
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 n表示题目输入的多项式个数，
 使用while（n--）的循环控制次数
1
2

中心思想：先创建一个头位置的空节点，再用attach函数把多项式连接在后面，最后释放头空节点

①p指向构建的空节点，link连接的是NULL
②还是需要一个rear指针来指示此链表的结尾，便于传递给attach函数
③释放空节点：
用一个指向结构体的指针先指向p头结点，
然后移动p，为下一个节点，最后释放t

（point：attach函数中，形参是指针的指针，故为&rear）

这是一个返回类型是指针的函数，最后返回指针p，指向输入完成的多项式。

三、相加

建立5个指针：
t1，t2：两个多项式
p：指向空节点
rear：结尾标志
t：最后释放头空节点

中心思想：
建立一个结果链表，把两个多项式链表相加结果插入。
设p1，p2分别指向两个多项式的第一个节点，
当指数相同，系数相加，若不为零，都分别指向下一项；
如果p1的指数大于p2，则将p1插入当前结果链表，并使p1指向下一项，p2不动，反之亦然。

大致框架：

当p1、p2长度不同时，有一个链表先为空，
此时退出while（t1&&t2）的循环，则再用while循环将剩下的连接到结果多项式后面。

当t1和t2的指数相同时，系数相加：
if判断系数是否为0：
非：使用attach连接到结果链表，t1和t2指向下一项；
是：t1和t2也要指向下一项；

释放头的空节点。
否则输出时会出现：
-842150451

（point：p1，p2是定义的形参，再设置两个指针t1，t2）

四、相乘

中心思想：先用t1的第一项×t2的每一项，构建初始结果项；
构建两个循环，t1第二项开始的每一项分别乘以t2，再将结果插入初始结果项。

f mult(f p1, f p2)//传入两个多项式
{
	f p, t1, t2, rear, t;
	int c, e;
	if (!p1 || !p2)return NULL;
	t1 = p1;t2 = p2;
	p = (f)malloc(sizeof(struct p));
	p->link = NULL;//构造头空节点
	rear = p;
	while (t2)
	{
		attach(t1->c * t2->c, t1->e + t2->e, &rear);
		t2 = t2->link;//t1的第一项×t2的每一项
	}
	t1 = t1->link;//t1移动到第二项
	while (t1)
	{
		t2 = p2;rear = p;//每次t1移到下一项，t2就移到第一项，rear指到头空节点，再次比较插入
		while (t2)
		{
			c = t1->c * t2->c;
			e = t1->e + t2->e;
			while (rear->link && rear->link->e > e)
				rear = rear->link;//比较指数
			if (rear->link && rear->link->e == e)
			{
				if (rear->link->c + c)//判断系数是否为0
					rear->link->c += c;
				else//为0则删除结点
				{
					t = rear->link;
					rear->link = t->link;//即t的下一项，断截t
					free(t);
				}
			}
			else {//指数不相等，而是介于rear和rear.link中间
				t = (f)malloc(sizeof(struct p));
				t->c = c;t->e = e;
				t->link = rear->link;
				rear->link = t;
				rear = rear->link;
			}
			t2 = t2->link;//结束完一次比较之后，移到下一个t2
		}
		t1 = t1->link;//所有t2乘完，移到下一个t1
	}
	t2 = p;p = p->link;free(t2);//删除空节点
	return p;
}
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

五、输出

输出依据题给格式，系数和指数中间有空格，结尾无空格，则转换思路：除第一项外，输出空格系数空格指数
设立flag判断是否为第一项

void print(f p)
{
	int flag = 0;
	if (!p)
	{
		printf("0 0\n");
		return 0;
	}
	while (p)
	{
		if (!flag)
			flag = 1;
		else
			printf(" ");
		printf("%d %d", p->c, p->e);
		p = p->link;
	}
	printf("\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

完整代码如下：

#include<stdio.h>
typedef struct p* f;
struct p
{
	int c;
	int e;
	f link;
};
//创建attach函数建立新的节点
void attach(int c,int e,f*prear)
{
	f p;
	p = (f)malloc(sizeof(struct p));
	p->c = c;
	p->e = e;
	p->link = NULL;
	(*prear)->link = p;
	*prear = p;
}
//读入链表
f read()
{
	f p, rear, t;
	int c, e, n;
	scanf("%d", &n);
	p = (f)malloc(sizeof(struct p));
	p->link = NULL;
	rear = p;
	while(n--)
	{
		scanf("%d %d", &c, &e);
		attach(c, e, &rear);
	}
	t = p;p = p->link;free(t);
	return p;
}
f add(f p1, f p2)
{
	f t1, t2,p,rear,t;
	t1 = p1;t2 = p2;
	p = (f)malloc(sizeof(struct p));
	p->link = NULL;
	rear = p;//rear指向新链表
	while (t1 && t2)
	{
		if (t1->e == t2->e)
		{
			if (t1->c + t2->c)
			{
				attach(t1->c + t2->c, t1->e, &rear);
				t1 = t1->link;
				t2 = t2->link;
			}
			else
			{
				t1 = t1->link;
				t2 = t2->link;
			}

		}
		else
			if (t1->e > t2->e)
			{
				attach(t1->c, t1->e, &rear);
				t1 = t1->link;
			}
			else
			{
				attach(t2->c, t2->e, &rear);
				t2 = t2->link;
			}
	}
	while (t1)
	{
		attach(t1->c, t1->e, &rear);
		t1 = t1->link;
	};
	while (t2)
	{
		attach(t2->c, t2->e, &rear);
		t2 = t2->link;
	};
	t = p;
	p = p->link;
	free(t);
	return p;
}

f mult(f p1, f p2)
{
	f p, t1, t2, rear, t;
	int c, e;
	if (!p1 || !p2)return NULL;
	t1 = p1;t2 = p2;
	p = (f)malloc(sizeof(struct p));
	p->link = NULL;
	rear = p;
	while (t2)
	{
		attach(t1->c * t2->c, t1->e + t2->e, &rear);
		t2 = t2->link;
	}
	t1 = t1->link;
	while (t1)
	{
		t2 = p2;rear = p;
		while (t2)
		{
			c = t1->c * t2->c;
			e = t1->e + t2->e;
			while (rear->link && rear->link->e > e)
				rear = rear->link;
			if (rear->link && rear->link->e == e)
			{
				if (rear->link->c + c)
					rear->link->c += c;
				else
				{
					t = rear->link;
					rear->link = t->link;
					free(t);
				}
			}
			else {
				t = (f)malloc(sizeof(struct p));
				t->c = c;t->e = e;
				t->link = rear->link;
				rear->link = t;
				rear = rear->link;
			}
			t2 = t2->link;
		}
		t1 = t1->link;
	}
	t2 = p;p = p->link;free(t2);
	return p;
}
void print(f p)
{
	int flag = 0;
	if (!p)
	{
		printf("0 0\n");
		return 0;
	}
	while (p)
	{
		if (!flag)
			flag = 1;
		else
			printf(" ");
		printf("%d %d", p->c, p->e);
		p = p->link;
	}
	printf("\n");
}

int main()
{
	f p1, p2, pp, ps;
	p1 = read();
	p2 = read();
	pp = mult(p1, p2);
	print(pp);
	ps = add(p1, p2);
	print(ps);
	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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

以上，来源于mooc 陈越老师、何钦铭老师的《数据结构》