1、實驗報告課程名稱 數(shù)據(jù)結構上機實驗實驗項目線性表的應用實驗儀器PC機系另寸電子信息與通信學院專 業(yè) _班級/學號學生姓名實驗日期成 績指導教師實驗一.線性表的應用1. 實驗目的：掌握線性鏈表的存儲、運算及應用。利用鏈表實現(xiàn)一元多項式計算。2. 實驗內容：1）編寫函數(shù)，實現(xiàn)用鏈表結構建立多項式；2）編寫函數(shù)，實現(xiàn)多項式的加法運算；3）編寫函數(shù)，實現(xiàn)多項式的顯示；4）測試：編寫主函數(shù)，它定義并建立兩個多項式，顯示兩個多項式，然后將它們相加并顯示結果。變換測試 用的多項式，檢查程序的執(zhí)行結果。選做內容：修改程序，選擇實現(xiàn)以下功能：5）多項式求值：編寫一個函數(shù)，根據(jù)給定的x值計算并 返回多項式f（x）

2、的值。測試該函數(shù)（從終端輸入一個x的值，調用該函數(shù)并顯示返回結果）。6）多項式相減：編寫一個函數(shù)，求兩個多項式相減的多 項式。7）多項式相乘：編寫一個函數(shù)，求兩個多項式的乘積多 項式。3. 算法說明：1）多項式的建立、顯示和相加算法見講義。 可修改顯示 函數(shù)，使輸出的多項式更符合表達規(guī)范。2) 多項式減法：同次項的系數(shù)相減(缺項的系數(shù)是0)。例如 a(x)=-5x 2+2x+3，b(x)= -4x 3+3x，貝U a(x)-b(x) =4x3-5x 2-x+3。提示：a(x)-b(x) = a(x)+(-b(x)。3) 多項式乘法：兩個多項式的相乘是 “系數(shù)相乘，指數(shù) 相加”。算法思想是用一個

3、多項式中的各項分別與另 一個多項式相乘，形成多個多項式，再將它們累加在23一起。例如， a(x)=-5x +2x+3 , b(x)=-4x +3x，則a(x)*b(x) = (-4x 3)*(-5x 2+2x+3)+(3x)*(-5x 2+2x+3)= (20x 5-8x 4-12x 3)+(- 15x 3+6x2+9x)=20x5-8x 4-27x 3+6x2+9x。4. 實驗步驟:根據(jù)實驗報告的要求，我對文件夾里的 C文件進行了豐富和修改，步驟如下：鏈表結構建立多項式：typedef struct polynode float coef; /系數(shù)int exp; /指數(shù)struct pol

4、ynode *next; /下一結點指針 PNode;編寫函數(shù)，實現(xiàn)多項式的加法運算；實現(xiàn)加法功PNode * PolyAdd (PNode *f1, PNode *f2) / /實現(xiàn)兩多項式(頭指針分別為 fl和f2和多項式f3=f1+f2。PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;int exp;float coef;f3=(PNode *)malloc(sizeof(PNode); /f3->exp=-1; / 對頭指針初始化f3->next=f3;pc=f3; / 將pc指向頭指針while (pa->exp!=

5、-1 | pb->exp!=-1) /時，跳出循環(huán)if (pa->exp>pb->exp)exp=pa->exp;coef=pa->coef;pa=pa->n ext;else if (pa->expvpb->exp)相加，返回建立頭指針返回頭指針exp=pb->exp; coef=pb->coef;pb=pb->n ext;elseexp=pa->exp; coef=pa->coef+pb->coef; pa=pa->n ext;pb=pb->n ext;if (coef!=0)q=(PNo

6、de *)malloc(sizeof(PNode); /建立新的q指針存放負指數(shù)的指針q->exp=exp;q->coef=coef; / 將q插入鏈表中q->next=pc->next;pc->n ext=q;pc=q;return f3; /返回實現(xiàn)多項式的顯示；void ShowPloy(PNode *h)/用if語句判斷，當指數(shù)為0是，只輸出系數(shù)；當指數(shù)為1時，輸出系數(shù)和 X;當系數(shù)為1時，輸出X 和指數(shù)。h=paixu(h); / 整理函數(shù)，使之降幕排列PNode *p=h->next;if(p=h)printf("表達式為空n"

7、;);return;if(p->coef=1)printf("xA%d",p->exp);/用 if 語句判斷，若輸出XA。和XA1值為0和1直接輸出數(shù)據(jù)。 else if(p->exp=1)printf("%gx", p->coef);else if(p->exp=0)printf("%g", p->coef);elseprintf("%gxA%d", p->coef, p->exp);p=p->n ext;while (p!=h)if(p->coef&

8、gt;0)系數(shù)為負，printf("+");/不用輸出加號if(p->coef=1) printf("xA%d",p->exp);else if(p->exp=1)printf("%gx", p->coef);else if(p->exp=0)printf("%g", p->coef);elseprintf("%gxA%d", p->coef, p->exp); p=p->n ext;printf("n");主函數(shù)void

9、 main()PNode *F1F2JF3八foaf><FlHCeafpo_y()八F2HCeafpo_y()八 gnmvlf 1 (xH)showpoy(FI ) pinff(i2(xHshowp_oy(F2=F3HPO_yAdd(F1F2=F3Hpaixu(F3)八 pinmvlf1i2HP showp-oy(F3)八F3HPO_ysub(F1F2)八 showp-oy(F3)八 F3HP0_yMU交 F1F2)八 showp-oy(F3)八 scanf(=%rax)八 prinm/nfl (XH%.3fH%.3fn=><po_yva-ue(FlX)多項式求值dou

10、ble PolyValue(PNode *h, float x) /編寫算法，求以h為頭指針的多項式在 x點的值并返回 該值。double f=0.0;/ 求出 f=f(x);PNode *pa;h=paixu(h);pa=h->next;while(pa->exp!=-1) /使用 f+=coef*pow ，返回 ff+=(pa->coef)*pow(x,pa->exp);pa=pa->n ext;return f;多項式相減PNode * PolySub(PNode *f1,PNode *f2)/編寫此算法，實現(xiàn)兩多項式(頭指針分別為fl和f2 )相減，返回差

11、多項式 f3=f1-f2。PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head;建立頭指針f3=(PNode *)malloc(sizeof(PNode); /f3->exp=-1; /頭指針的初始化f3->next=f3;pc=f3; /pc 指向頭指針，便于操作。while(pb->exp!=-1) /返回頭指針時，跳出循環(huán)。q=(PNode *)malloc(sizeof(PNode); /建立新的q指針存放負指數(shù)的指針q->coef=pb->coef*(-1);q->exp=pb->exp

12、; / 將q插入鏈表中q->next=pc->next;pc->n ext=q;pc=q;pb=pb->n ext;head=PolyAdd(f1,f3); /調用加法函數(shù)做減法return head; / 返回頭指針多項式相乘PNode * PolyMult(PNode *f1,PNode *f2)/實現(xiàn)兩多項式(頭指針分別為fl和f2 )相乘，返回乘積多項式f3=f1*f2。PNode *pa=f1->next,*pb=f2->next,*pc,*u,*head;int exp;float coef;head=(PNode *)malloc(sizeof

13、(PNode); head->exp=-1;head->next=head;u指針，查pc=head;while(pa->exp!=-1) /多項式相乘，錄到頭指針。while(pb->exp!=-1)coef=pa->coef*pb->coef; exp=pa->exp+pb->exp;u=(PNode *)malloc(sizeof(PNode); u->coef=coef;u->exp=exp; u->next=pc->next; pc->next=u;pc=u;pb=pb->n ext;pb=pb-&g

14、t;n ext;pa=pa->n ext;return head; / 返回頭指針程序運行截圖測試成功!程序完整源代碼如下:#include <stdio.h>#include <stdlib.h>#include <math.h> typedef struct polynode float coef; /系數(shù)int exp; /指數(shù)下一結點指針struct polynode *next; / PNode;PNode * paixu(PNode *f) /PNode *p,*q,*r,*pO,*qO;p=f->n ext; q=p->n e

15、xt;p0=f；q0=p;while(p->exp!=-1) /p 值進行比較，while(q->exp!=-1) /q一圈if(p->exp>q->exp) /移q0=q;q=q->n ext;else if(p->expvq->exp) /將多項式降幕排列為q的前驅，q與p指數(shù)指數(shù)為頭指針推出循環(huán)，q移動比較，若p大于q貝U q后若p小于q貝U q插入、,、八 p之前r=q->n ext;q->next=pO->next;q0->n ext=r;p0->n ext=q;p=q；q=r;else if(p->

16、exp=q->exp) /若相等， p 的 coef與q的相加，然后刪除q節(jié)點，釋放q的空間p->coef+=q->coef;q0->next=q->next;q=q->n ext;p0=p;p=p->n ext;q=p->n ext;q0=p;return f;void ShowPloy(PNode *h)/用if語句判斷，當指數(shù)為0是，只輸出系數(shù)；當指數(shù)為1時，輸出系數(shù)和 X;當系數(shù)為1時，輸出X和指數(shù)。h=paixu(h); / 整理函數(shù)，使之降幕排列PNode *p=h->next;if(p=h)printf(" 表達式為

17、空n");return;if(p->coef=1)printf("xA%d",p->exp);/用 if 語句判斷，若輸出xAo和xA1值為0和1直接輸出數(shù)據(jù)。else if(p->exp=1)printf("%gx", p->coef);else if(p->exp=0)printf("%g", p->coef);elseprintf("%gxA%d", p->coef, p->exp);p=p->n ext;while (p!=h)if(p->

18、;coef>0)printf("+");/系數(shù)為負，不用輸出加號if(p->coef=1)printf("xA%d",p->exp);else if(p->exp=1)printf("%gx", p->coef);else if(p->exp=0)printf("%g", p->coef);elseprintf("%gxA%d", p->coef, p->exp);p=p->n ext;printf("n");PNo

19、de * CreatPoly() /建立多項式鏈表，返回頭指針PNode * head, *p, *s;int i,n;head=(PNode *)malloc(sizeof(PNode);head->exp=-1;p=head;printf(" 多項式的項數(shù)為：");scanf("%d",&n);for(i=1;i<=n; i+)s=(PNode *)malloc(sizeof(PNode);printf(" 請輸入多項式第%d項的系數(shù)和指數(shù)(用逗號 隔開)：",i)；scanf("%g,%d"

20、;，& s->coef, &s->exp);p->n ext=s;p=s;p->next=head;return head;void FreePoly(PNode *h)/編寫此算法，將以h為頭指針的多項式的鏈表結點逐個釋放。PNode *p,*q;p=h->n ext;while(p->exp)!+-1; q=p->n ext; free(p);p=q;free(h);return;跳出循環(huán)并實現(xiàn)加法功相加，返回/Free函數(shù)用于銷毀鏈表，最后指向頭指針，釋放頭指針。PNode * PolyAdd (PNode *f1, PNode

21、*f2) /能。 /實現(xiàn)兩多項式(頭指針分別為fl和f2)和多項式f3=f1+f2。PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;int exp;float coef;建立頭指針返回頭指針f3=(PNode *)malloc(sizeof(PNode); / f3->exp=-1; /對頭指針初始化f3->next=f3;pc=f3; / 將pc指向頭指針while (pa->exp!=-1 | pb->exp!=-1) / 時，跳出循環(huán)if (pa->exp>pb->exp)exp=pa->e

22、xp;coef=pa->coef; pa=pa->n ext;else if (pa->expvpb->exp)exp=pb->exp;coef=pb->coef;pb=pb->n ext; elseexp=pa->exp;coef=pa->coef+pb->coef;pa=pa->n ext;pb=pb->n ext;if (coef!=0)建立新q=(PNode *)malloc(sizeof(PNode); /的q指針存放負指數(shù)的指針q->exp=exp;q->coef=coef; / 將q插入鏈表中 q

23、->next=pc->next;pc->n ext=q;pc=q;return f3; / 返回PNode * PolySub(PNode *f1,PNode *f2)/編寫此算法，實現(xiàn)兩多項式(頭指針分別為 fl和f2 )相 減，返回差多項式 f3=f1-f2。PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head; f3=(PNode *)malloc(sizeof(PNode); /建立頭指針f3->exp=-1; / 頭指針的初始化f3->next=f3;pc=f3; /pc指向頭指針，便于操作。whi

24、le(pb->exp!=-1) /返回頭指針時，跳出循環(huán)。q=(PNode *)malloc(sizeof(PNode); /建立新的q指針存放負指數(shù)的指針q->coef=pb->coef*(-1);q->exp=pb->exp; / 將q插入鏈表中 q->next=pc->next;pc->n ext=q;pc=q;pb=pb->n ext;head=PolyAdd(f1,f3); /調用加法函數(shù)做減法return head; / 返回頭指針PNode * PolyMult(PNode *f1,PNode *f2)/實現(xiàn)兩多項式(頭指針分

25、別為fl和f2 )相乘，返回乘積多項式f3=f1*f2。PNode *pa=f1->next,*pb=f2->next,*pc,*u,*head;int exp;float coef;head=(PNode *)malloc(sizeof(PNode);head->exp=-1;head->next=head;pc=head;while(pa->exp!=-1) / 多項式相乘，錄入 u指針，查 到頭指針。while(pb->exp!=-1)coef=pa->coef*pb->coef;exp=pa->exp+pb->exp;u=(PNode *)malloc(sizeof(PNode);u->coef=coef;u->exp=exp;u->next=pc->next;pc->next=u;pc=u;pb=pb->n ext;pb=pb->n ext;pa=pa->n ext;return head;