一元多项式的加法和乘法 c语言_c语言一元多项式的乘法与加法运算

题目
总体结构：

各函数解释：

代码

#include<stdio.h>
#include<stdlib.h>

typedef struct PolyNode *Polynomial;
struct PolyNode{
	int coef;//系数
	int expon;//指数 
	Polynomial link;//链表指针域指向下一地址 
};

Polynomial ReadPoly();//读入多项式
void Attach(int c,int e,Polynomial *pRear);//将每次读入的多项式连接 
Polynomial Add(Polynomial P1,Polynomial P2);//多项式相加 
Polynomial Mult(Polynomial P1,Polynomial P2);//多项式相乘 
int Compare(int a,int b);//比较 
void PrintPoly(Polynomial P);//输出多项式 


int main(void)
{
	Polynomial P1,P2,PS,PP;
	
	P1=ReadPoly();//读入数据
	P2=ReadPoly();
	
	PP=Mult(P1,P2);//多项式相乘 
	PrintPoly(PP);
	
	printf("\n");
	
	PS=Add(P1,P2);//多项式相加 
	PrintPoly(PS);
	
	return 0;
}


Polynomial ReadPoly()//读入数据 
{
	Polynomial P,Rear,t;
	int c,e,N; 
	scanf("%d",&N);
	P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
	P->link =NULL;
	Rear=P;//Rear始终指向链表的尾部
	while(N--)
	{
		
        scanf("%d %d",&c,&e);
        if(c!=0)//对系数为零的项进行判断 
		Attach(c,e,&Rear);
	}
	t=P;//释放表头为空的节点 
	P=P->link ;
	free(t);
	return P;
}


void Attach(int c,int e,Polynomial *pRear)//将数据连接成链表 
{
	Polynomial P;
	P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
	P->coef=c;
	P->expon=e;
	P->link =NULL;
	(*pRear)->link=P;//将P指向的新节点插入到当前结果表达式尾项的后面
	*pRear=P;//最后一项指向P
}

int Compare(int a,int b)//比较 ，a>b return 1，a<b return -1, a==b return 0 
{
	if(a>b)
	return 1;
	else if(a==b)
	return 0;
	else
	return -1;
}

Polynomial Add(Polynomial P1,Polynomial P2)//多项式相加 
{
	Polynomial front,rear,temp;//front为头，Rear为尾
	int sum;
	rear=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
	front=rear;
	while(P1&&P2)
		switch(Compare(P1->expon ,P2->expon))
		{
			case 1://如果P1->expon>P2->expon
				Attach(P1->coef,P1->expon,&rear);
				P1=P1->link ;
				break;
			case -1://如果P1->expon<P2->expon
				Attach(P2->coef,P2->expon,&rear);
				P2=P2->link ;
				break;
			case 0://如果P1->expon=P2->expon
				sum=P1->coef +P2->coef;
				if(sum)//如果指数相等，先判断系数和是否为0 
				Attach(sum,P1->expon,&rear);
				P1=P1->link;
				P2=P2->link ;
				break;
		}
		//将未处理完的多项式中所有节点复制到结果多项式中
		while(P1)
		{
			Attach(P1->coef,P1->expon,&rear);
			P1=P1->link;
		}
		while(P2)
		{
			Attach(P2->coef,P2->expon,&rear);
			P2=P2->link;
		}

		rear->link=NULL;//释放头为空的节点 
		temp=front;
		front=front->link ;
		free(temp);
		return front;
}

void PrintPoly(Polynomial P)//打印 
{
	int flag=0;
	if(!P)
	{
		printf("0 0");
		return ;
	}
	
	while(P)
	{
		if(!flag)
			flag=1;
		else
			printf(" ");
		printf("%d %d",P->coef ,P->expon );
		P=P->link ;
	}
}

Polynomial Mult(Polynomial P1, Polynomial P2)//多项式相乘 
{
    Polynomial P, Rear;
    Polynomial t1, t2, t;
    if (!P1 ||!P2)//判断两个链表是否为空
    {
        return NULL;

    }
    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    Rear = P;
    while (t2)//先让t1的第一项和t2的每一项相乘，构建出一个新链表，用于后来数据的插入
    {
        Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;

    while (t1)
    {
        t2 = P2;
        Rear = P;//Rear每次都从所构建的链表头开始，以便于寻找插入位置 
        while (t2) 
        {
            int c = t1->coef*t2->coef;
            int e = t1->expon + t2->expon;
            while (Rear->link&&Rear->link->expon > e)//Rear每次都从所构建的链表头开始，以便于寻找插入位置 
            {
                Rear = Rear->link;
            }
            if (Rear->link&&Rear->link->expon == e)//相等就不需要申请一个新的节点，只要把系数相加。
            {
                if (Rear->link->coef + c)//系数和不为0，
                {
                    Rear->link->coef += c;
                }
                else//系数和为0，删除节点
                {
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }
            else//如果指数不相等，申请空间将将此项插入
            {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->link = NULL;
                t->coef = c;
                t->expon = 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;
}

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211