|
|
Posted on 2007-10-05 20:21 山泉彎延 閱讀(1340) 評論(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
都是代碼撒
|