|
|
Posted on 2007-10-05 20:21 山泉弯延 阅读(1294) 评论(4) 编辑 收藏 引用 所属分类: 数据结构实验集
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<conio.h>
4 //==============================================
5 typedef struct PolyNode
6 {
7 int coef;//多项式项的系数
8 int exp;//多项式项的指数
9 struct PolyNode *next;
10 }PolyNode; //声明了多项式项结构
11 //===============================================
12 int PolyList_Init(PolyNode **head)//初始化表头 (注意参数head的写法)
13 {
14 *head =(PolyNode *)malloc(sizeof(PolyNode));
15 if(NULL==*head)
16 return 0;
17 else{(*head)->next=NULL;
18 return 1;}
19 }
20 //================================================
21 int PolyList_Empty(PolyNode *head)//判断连表示是否为空
22 {
23 if(head==NULL)
24 return 1;//当链表头节点都没有的时候返回 1；
25 if(head->next==NULL)
26 return 2;//当链表只存在头节点的时候返回 2；
27 else return 0; //当链表即存在头节点又存在实节点的时候返回 0；
28 }
29 //=================================================
30 int PolyNode_Insert(PolyNode *head,PolyNode *Insertor)//在多项式链表的适当位置插入链表
31 {
32 if(PolyList_Empty(head)==1)
33 {
34 printf("No PolyList Exist! Can not do Insert \n");
35 return 0;
36 }
37 PolyNode *p_front=head;
38 PolyNode *p=head->next;
39 if(PolyList_Empty(head)==2)
40 {
41 Insertor->next=head->next;
42 head->next=Insertor;
43 return 1;
44 }
45 int sum=0;
46 while(p)
47 {
48 if(p->exp == Insertor->exp)
49 {
50 if(sum=(p->coef+Insertor->coef))
51 {
52 p->coef=sum;
53 free(Insertor);
54 return 1;
55 }
56 else{
57 p_front->next=p->next;
58 free(p);
59 free(Insertor);
60 return 1;
61 }
62 }
63 else if(p->exp > Insertor->exp)
64 {
65 Insertor->next=p;
66 p_front->next=Insertor;
67 return 1;
68 }
69 else {p_front=p;
70 p=p->next;}
71 }
72 if(!p)
73 {
74 p_front->next=Insertor;
75 Insertor->next=NULL;
76 return 1;
77 }
78 }
79 //=========================================
80 void PolyList_Free(PolyNode *head)//释放链表
81 {
82 PolyNode *p,*q;
83 for(p=head;p!=NULL;)
84 {q=p;
85 p=p->next;
86 free(q);
87 }
88
89 }
90 //==========================================
91 PolyNode* PolyList_Create(PolyNode *head)//创建一个多项式链表
92 {
93
94 if(!PolyList_Init(&head))
95 {
96 printf("Init PolyLIst Fail!\n");
97 exit(1);
98 }
99 PolyNode *tmp=NULL;
100 int coef_tmp;
101 do{
102 tmp=(PolyNode*)malloc(sizeof(PolyNode));
103 if(!tmp)
104 { PolyList_Free(head);
105 printf("malloc fail\n");
106 exit(1);
107 }
108 printf("coef=");
109 scanf("%d",&(tmp->coef));
110 coef_tmp=tmp->coef;
111 printf("exp=");
112 scanf("%d",&(tmp->exp));
113 if(0!=tmp->coef)
114 PolyNode_Insert(head,tmp);
115 }while(0!=coef_tmp);
116 free(tmp);
117 return head;
118 }
119 //==========================================================
120 PolyNode *PolyList_Copy(PolyNode *head)// 复制多项式（链表）
121 {
122 if(PolyList_Empty(head)==1)
123 {
124 printf("No PolyList Exist!\n");
125 return NULL;
126 }
127 PolyNode *head_copy=head;
128 if(PolyList_Empty(head)==2)
129 {
130 if(!PolyList_Init(&head_copy))
131 {
132 printf("Init PolyLIst Fail!\n");
133 exit(1);
134 }
135 return head_copy;
136 }
137 if(!PolyList_Init(&head_copy))
138 {
139 printf("Init PolyLIst Fail!\n");
140 exit(1);
141 }
142 PolyNode *p_copy=head_copy->next;
143 PolyNode *p_copy_front=head_copy; //定义一个指在p_copy前面节点的指针，完成复制链表的链接工作；
144 PolyNode *p=head->next;
145 while(p)
146 {
147 {
148 p_copy=(PolyNode*)malloc(sizeof(PolyNode));
149 p_copy_front->next=p_copy;//使p_copy_front->next指向p_copy刚刚申请到的新节点；
150 p_copy_front=p_copy;//指针跟随P_copy向前移动
151 p_copy->coef=p->coef;
152 p_copy->exp=p->exp;
153 }
154 p=p->next;
155 }
156 p_copy->next=NULL;
157 return head_copy;
158 }
159 //=================================================
160 int PolyList_View(PolyNode *head)//版本低的多项式访问
161 {
162 if(PolyList_Empty(head))
163 {printf("No PolyList Exist or Poly Empty! Can not do View\n");
164 return 0;
165 }
166 PolyNode *p;
167 printf("Poly=");
168 int count=0;
169 for(p=head->next;p->next!=NULL;)
170 {
171 count++;
172 printf("(%dx^%d)+",p->coef,p->exp);
173 p=p->next;
174 }
175 count++;
176 printf("(%dx^%d) ##多项式的项数为%d\n",p->coef,p->exp,count);
177
178 return 1;
179 }
180 //===================================================
181 int PolyList_View_2(PolyNode *head)//版本高的多项式访问
182 {
183 if(PolyList_Empty(head)==1)
184 {printf("No PolyList Exist! Can not do View\n");
185 return 0;
186 }
187 if(PolyList_Empty(head)==2)
188 {
189 printf("Poly=0\n");
190 return 1;
191 }
192 PolyNode *p;
193 printf("Poly=");
194 for(p=head->next;p!=NULL;)
195 {
196 if(p->coef<0)
197 if(0==p->exp)
198 printf("%d",p->coef);
199 else{ if(-1==p->coef)
200 printf("-x^%d",p->exp);
201 else
202 printf("%dx^%d",p->coef,p->exp);
203 }
204 if(p->coef>0)
205 if(0==p->exp)
206 {if(p==head->next)
207 printf("%d",p->coef);
208 else
209 printf("+%d",p->coef);
210 }
211 else{ if(1==p->coef)
212 {if(p==head->next)
213 printf("x^%d",p->exp);
214 else
215 printf("+x^%d",p->exp);
216 }
217 else
218 {if(p==head->next)
219 printf("%dx^%d",p->coef,p->exp);
220 else
221 printf("+%dx^%d",p->coef,p->exp);
222 }
223 }
224 p=p->next;
225 }
226 printf("\n");
227 return 1;
228 }
229 //========================================================
230 PolyNode* PolyList_Add(PolyNode *lhead,PolyNode *rhead)//多项式相加，rhead将被清空
231 { if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1)
232 {
233 printf("No PolyNode Exist,can not do Add\n");
234 return lhead;
235 }
236 PolyNode *p1_front=lhead;
237 PolyNode *p1=lhead->next,*p2=rhead->next;
238 free(rhead);
239 int sum;
240 PolyNode *p2_tmp;
241 while(p1&&p2)
242 {
243 if(p2->exp == p1->exp)
244 {
245 if(sum=(p1->coef+p2->coef))
246 {
247
248 p1->coef=sum;
249
250 p2_tmp=p2->next;
251 free(p2);
252 p2=p2_tmp;
253
254 p1_front=p1;
255 p1=p1->next;
256
257 }
258 else{
259 p1_front->next=p1->next;
260 p2_tmp=p2->next;
261 free(p2);
262 p2=p2_tmp;
263 free(p1);
264 p1=p1->next;
265 }
266 }
267 else if(p2->exp < p1->exp )
268 {
269 p1_front->next=p2;
270
271 p2=p2->next;
272 p1_front=p1_front->next;
273 p1_front->next=p1;
274
275
276 }
277 else
278 {
279 p1_front=p1;
280 p1=p1->next;
281 }
282
283 }
284 if(!p1)
285 p1_front->next=p2;
286 return lhead;
287
288 }
289 //======================================================================
290 PolyNode* PolyList_Dec(PolyNode *lhead,PolyNode *rhead)//多项式减法运算 ，rhead将被清空
291 {
292 if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1)
293 {
294 printf("No PolyNode Exist,can not do Dec\n");
295 return lhead;
296 }
297 PolyNode *p1_front=lhead;
298 PolyNode *p1=lhead->next,*p2=rhead->next;
299 free(rhead);//将rhead对应的头节点释放掉
300 int sum;
301 PolyNode *p2_tmp;
302 while(p1&&p2)
303 {
304 if(p2->exp == p1->exp)
305 {
306 if(sum=(p1->coef-p2->coef))
307 {
308
309 p1->coef=sum;
310
311 p2_tmp=p2->next;
312 free(p2);
313 p2=p2_tmp;
314
315 p1_front=p1;
316 p1=p1->next;
317
318 }
319 else{
320 p1_front->next=p1->next;
321 p2_tmp=p2->next;
322 free(p2);
323 p2=p2_tmp;
324 free(p1);
325 p1=p1->next;
326
327 }
328 }
329 else if(p2->exp < p1->exp )
330 {
331 p1_front->next=p2;
332 p2->coef=-p2->coef;
333 p2=p2->next;
334 p1_front=p1_front->next;
335 p1_front->next=p1;
336
337
338 }
339 else
340 {
341 p1_front=p1;
342 p1=p1->next;
343 }
344
345 }
346 if(!p1)
347 p1_front->next=p2;
348 while(p2)
349 {
350 p2->coef=-p2->coef;
351 p2=p2->next;
352 }
353 return lhead;
354 }
355 //===============================================================
356 float Poly_X_Sum(PolyNode *head,float x)//求任意的X对应的多项式所得的值
357 {
358 if( PolyList_Empty(head)){
359 printf("No Poly exist or Poly Empty! Can not do X_Sum\n");
360 getch();
361 return 0;
362 }
363 PolyNode *p=head->next;
364 float sum=0;
365 float xsum=1;
366 int i=0;
367 while(p)
368 {
369 // printf("p->exp=%d\n",p->exp);
370 if(p->exp>0)
371 for( i=0,xsum=1;i!=p->exp;i++)//注意xsum还原为 1！
372 { xsum*=x;
373 // printf("xsum --- %f\n",xsum);
374 }
375 if(p->exp<0)
376 for(i=0,xsum=1;i!=p->exp;i--)
377 xsum/=x;
378 if(p->exp==0)
379 xsum=1.0;
380 sum+=(float)p->coef*xsum;
381 // printf("xsum=%f\n",xsum);
382 // printf("sum=%f\n",sum);
383 p=p->next;
384 }
385 return sum;
386 }
387 //=================================================
388 PolyNode *PolyList_Der(PolyNode * head)//对多项式求一般的一阶导数
389 {
390 if(PolyList_Empty(head)==1){
391 printf("No Poly Exist! Can not do Der\n");
392 getch();
393 return NULL;
394 }
395 if(PolyList_Empty(head)==2){
396
397 return head; //对0求导数还是0，所以返回头节点就可以
398 }
399 PolyNode *p_front=head;
400 PolyNode *p=head->next;
401 while(p)
402 {
403 if(0==p->exp)
404 {
405 p_front->next=p->next;
406 free(p);
407 p=p_front->next;
408 }
409 else{
410 p->coef*=p->exp;
411 p->exp--;
412 p_front=p;
413 p=p->next;
414 }
415 }
416 return head;
417 }
418 //==================================================
419 PolyNode *PolyList_Der_N(PolyNode * head,int N)//对多项式求N阶导数
420 {//这边再写空链表的判断语句是有好处的，以防当链表为空时进入循环消耗时间
421
422 if(PolyList_Empty(head)==1){
423 printf("No Poly Exist!Can not do Der_N\n");
424 getch();
425 return head;
426 }
427 if(PolyList_Empty(head)==2){
428
429 return head; //对0求导数还是0，所以返回头节点就可以
430 }
431 int i;
432 for( i=0;i!=N;i++)
433 head=PolyList_Der(head);
434 return head;
435 }
436 //===============================================================
437 PolyNode *PolyList_Mul(PolyNode *lhead,PolyNode * rhead)//多项式的乘法实现（内部采用复制多项式）
438 {
439 if(PolyList_Empty(lhead)==1||PolyList_Empty(rhead)==1){
440 printf("No Poly Exist! Can not do Mul\n");
441 getch();
442 return lhead;
443 }
444 if(PolyList_Empty(lhead)==2) {//此处让结果返回头节点的意思是若两个节点其中有一个是空的，则相乘后的结果应该为0.
445 PolyList_Free(rhead); //同时还要将其中的一个链表清除，因为这已经是做了乘法运算了。
446 return lhead;
447 }
448 if(PolyList_Empty(rhead)==2){//同上
449 PolyList_Free(lhead);
450 return rhead;
451 }
452 PolyNode *p_copy_from_lhead=PolyList_Copy(lhead);//这里已经把第一个多项式的原型给拷贝到一个新的链表中；
453 PolyNode *p_copy_from_lhead_2=NULL;//等会讲使用这个指针来从上面的指针拷贝链表
454 PolyNode *p_copy_tmp=NULL;
455 PolyNode *p2_front=rhead;
456 PolyNode *p2=rhead->next;
457 PolyNode *p1=lhead->next;
458 free(p2_front); //将rhead的头节点处理掉
459 while(p1)
460 {
461 p1->coef*=p2->coef;
462 p1->exp+=p2->exp;
463 p1=p1->next;
464 }//到此处完成第一个多项式与第二个多项式的第一项的乘法，但是此时的第一个多项式已经被破坏；
465 //PolyList_View(lhead);
466 p2_front=p2;
467 p2=p2->next;
468 free(p2_front);//处理掉rhead的第一个节点
469 while(p2)
470 {
471 p_copy_from_lhead_2=PolyList_Copy(p_copy_from_lhead);
472 p_copy_tmp=p_copy_from_lhead_2->next;
473 while(p_copy_tmp)
474 {
475 p_copy_tmp->coef*=p2->coef;
476 p_copy_tmp->exp+=p2->exp;
477 p_copy_tmp= p_copy_tmp->next;
478 }
479 lhead=PolyList_Add(lhead,p_copy_from_lhead_2);
480 p2_front=p2;
481 p2=p2->next;
482 free(p2_front);//处理掉p2_front所对应的节点，这样当循环完成后rhead的所有节点就被清除完毕
483 // PolyList_View(lhead);
484
485 }
486 PolyList_Free(p_copy_from_lhead);//将拷贝lhead的第一个版本释放掉
487 return lhead;
488 }
489 //=====================================================================
490 int main(void)
491 { printf("输入多项式1：格式：coef表示任意项的系数 exp表示对应coef项的指数（输入ceof=0结束exp任意）\n");
492 PolyNode *head_1=NULL;
493 head_1=PolyList_Create(head_1);
494 PolyList_View_2(head_1);
495 printf("输入多项式2：格式：coef表示任意项的系数 exp表示对应coef项的指数（输入ceof=0结束exp任意）\n");
496 PolyNode *head_2=NULL;
497 head_2=PolyList_Create(head_1);
498 PolyList_View_2(head_2);
499 PolyNode *head_4=PolyList_Copy(head_2);
500 printf("得到两个多项式相加之后的多项式\n");
501 head_1=PolyList_Add(head_1,head_2);
502 PolyList_View_2(head_1);
503 printf("得到两个多项式相减之后的多项式\n");
504
505 head_1=PolyList_Dec(head_1,head_4);
506 PolyList_View_2(head_1);
507 printf("复制产生一个新的完全一样的多项式\n");
508 PolyNode *head_3=PolyList_Copy(head_1);
509 PolyList_View(head_3);
510 printf("两个多项式相乘head_1*head_3:\n");
511 head_1=PolyList_Mul(head_1,head_3);
512 PolyList_View(head_1);
513 printf("对多项式求一次导数\n");
514 head_1=PolyList_Der(head_1);
515 PolyList_View(head_1);
516 printf("再对多项式求两次导数\n");//求几次导就给函数的第二个参数赋多少（例如3就是球三次导数！）
517 head_1=PolyList_Der_N(head_1,2);
518 PolyList_View_2(head_1);
519 printf("令X=9.0，得到多项式的和\n");
520 float sum=0;
521 float x=9.89;
522 printf("按任意键继续\n");
523 getch();
524 sum=Poly_X_Sum(head_1,x);
525 printf("多项式的和为%f\n",sum);
526 PolyList_Free(head_1);
527 printf("按任意键继续\n");
528 getch();
529 return 0;
530 }
531
Feedback
# re: 多项式单向链表实现 回复 更多评论
2007-10-05 21:20 by
加油
# re: 多项式单向链表实现 回复 更多评论
2007-10-06 16:46 by
都是代码撒
|