數(shù)據(jù)結構線性表的應用實驗報告

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

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

3、與 另一個多項式相乘，形成多個多項式，再將它們累 加在一起。例如， a(x)=-5x 2+2x+3, b(x)=-4x 3+3x, 則a(x)*b(x)(-4x 3)*(-5x 2+2x+3)+(3x)*(-5x2+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 polynode *next; /下結

4、點指針 PNode;編寫函數(shù)，實現(xiàn)多項式的加法運算；PNode * PolyAdd (PNode *f1, PNode *f2) / 實現(xiàn)加法功臺匕 目匕。 / 實現(xiàn)兩多項式（頭指針分別為fl和f2）相加，返回和多項式f3=f1+f2PNode *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->e

5、xp!=-1 | pb->exp!=-1) /時，跳由循環(huán)if (pa->exp>pb->exp)exp=pa->exp;coef=pa->coef;pa=pa->next;else if (pa->exp<pb->exp)exp=pb->exp;coef=pb->coef;pb=pb->next;elseexp=pa->exp;coef=pa->coef+pb->coef;pa=pa->next;pb=pb->next;if (coef!=0)q=(PNode *)malloc(siz

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

7、gt;coef=1)printf("xA%d",p->exp);/用 if 語句判斷，若輸由xAo和xA1值為。和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->next;while (p!=h)if(p->coef>0)printf("+"

8、;);/系數(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->next;printf("n");主函數(shù)void main()PNode *F1,*F2,*F3;fl

9、oat x;F1=CreatPoly();F2=CreatPoly();printf("nf1(x)=");ShowPloy(F1);printf("nf2(x)=");ShowPloy(F2);F3=PolyAdd(F1,F2);F3=paixu(F3);printf("nf1+f2=:");ShowPloy(F3);F3=PolySub(F1,F2);printf("nf1-f2=:");ShowPloy(F3);F3=PolyMult(F1,F2);printf("nf1*f2=:");S

10、howPloy(F3);printf("nx 的值為:");scanf("%f", &x);printf("nf1(x=%.3f)=%.3fn”,x,PolyValue(F1,x);多項式求值double 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-

11、>coef)*pow(x,pa->exp);pa=pa->next;return f;多項式相減PNode * PolySub(PNode *f1,PNode *f2)/編寫此算法，實現(xiàn)兩多項式(頭指針分別為fl和f2)相減，返回差多項式f3=f1-f2 oPNode *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(p

12、b->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->next=q;pc=q；pb=pb->next;head=PolyAdd(f1,f3); / 調(diào)用加法函數(shù)做減法return head; / 返回頭指針多項式相乘PNode * PolyMult(PNode *f1,PNode *f2)/實現(xiàn)兩多項式(頭指針分別

13、為 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=(PN

14、ode *)malloc(sizeof(PNode);u->coef=coef;u->exp=exp;u->next=pc->next;pc->next=u;pc=u;pb=pb->next;pb=pb->next;pa=pa->next;return head; / 返回頭指針程序運行截圖曷昌昌 FJ rJI-CJ 號號號i數(shù) 系系系 的的3項項項3口口 B士戶土盧士尸數(shù)數(shù)數(shù)靠系的的的捐項-12 3 - 12 3 承第第第 式式 項項項點作項 的多多多多多項穗瑞項領瑞多請請耍.1清請請globail me mldoublef2<x>

15、=6x2ri*f2"：3«rt3 *12x2fi-£2-：3Krt3£1*£2-：10«5 *3Gk*4m的值為；2.»ao>=4s.aasi*ess any hey to continuevoid m U <PModP *F1,*F2,*F3;flojt x;Fl=CreatPoip();“ I'nnfi niiir jiM nn * 1 - Wi n?fc? hphim- 測試成功!程序完整源代碼如下：#include <stdio.h>#include <stdlib.h>#

16、include <math.h>typedef struct polynode float coef; /系數(shù)int exp; /struct polynode *next; /指數(shù)下一結點指針 PNode;PNode * paixu(PNode *f) /PNode *p,*q,*r,*p0,*q0;p=f->next;q=p->next;p0=f;q0=p;while(p->exp!=-1) /p值進行比較，while(q->exp!=-1) /q一圈 if(p->exp>q->exp) / 移將多項式降哥排列為q的前驅(qū)，q與p指數(shù)指數(shù)

17、為頭指針推由循環(huán)，q移動比較，若p大于q則q后q0=q;q=q->next;若p小于q貝U q插入)else if(p->exp<q->exp) /p N刖(r=q->next;q->next=p0->next;q0->next=r;p0->next=q;p=q；q=r;)else if(p->exp=q->exp) /若相等， p 的 coef與q的相加，然后刪除q節(jié)點，釋放q的空間(p->coef+=q->coef;q0->next=q->next;q=q->next;)p0=p;p=p->

18、;next;q=p->next;q0=p； return f;void ShowPloy(PNode *h)/用if語句判斷，當指數(shù)為。是，只輸由系數(shù)；當指數(shù)為1時，輸由系數(shù)和 X;當系數(shù)為1時，輸由X和指數(shù)。h=paixu(h); / 整理函數(shù)，使之降曷排列PNode *p=h->next;if(p=h)printf("表達式為空n");return;if(p->coef=1)printf("xA%d",p->exp);/用 if 語句判斷，若輸由xAo和xA1值為0和1直接輸由數(shù)據(jù)。else if(p->exp=1)pr

19、intf("%gx”, p->coef);else if(p->exp=0)printf("%g”, p->coef);elseprintf("%gxA%d", p->coef, p->exp);p=p->next;while (p!=h)if(p->coef>0)printf("+"); /系數(shù)為負，不用輸由加號if(p->coef=1)printf("xA%d",p->exp);else if(p->exp=1)printf("%gx&

20、quot;, p->coef);else if(p->exp=0)printf("%g", p->coef);elseprintf("%gxA%d", p->coef, p->exp);p=p->next;printf("n");PNode * CreatPoly() /建立多項式鏈表，返回頭指針PNode * head, *p, *s;int i,n;head=(PNode *)malloc(sizeof(PNode);head->exp=-1;p=head;printf(" 多項

21、式的項數(shù)為：")；scanf("%d",&n);for(i=1;i<=n; i+)s=(PNode *)malloc(sizeof(PNode);printf(" 請輸入多項式第項的系數(shù)和指數(shù)(用逗號 隔開):",i);scanf("%g,%d”,&s->coef,&s->exp);p->next=s;p=s;p->next=head;return head;void FreePoly(PNode *h)/編寫此算法，將以h為頭指針的多項式的鏈表結點逐個釋放。PNode *p,*q

22、;p=h->next;while(p->exp)!+-1;q=p->next;free(p)；p=q；free(h);return;/Free函數(shù)用于銷毀鏈表，最后指向頭指針，跳由循環(huán)并釋放頭指針。PNode * PolyAdd (PNode *f1, PNode *f2) /實現(xiàn)加法功能。 /實現(xiàn)兩多項式(頭指針分別為fl和f2)相加，返回和多項式f3=f1+f2PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;int exp;建立頭指針返回頭指針float coef;f3=(PNode *)malloc(sizeof(PNo

23、de); /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->exp;coef=pa->coef;pa=pa->next;else if (pa->exp<pb->exp)exp=pb->exp;coef=pb->coef;pb=pb->next;elseexp=pa->exp;coef=pa->coef

24、+pb->coef;pa=pa->next;pb=pb->next;if (coef!=0)q=(PNode *)malloc(sizeof(PNode); /建立新的q指針存放負指數(shù)的指針q->exp=exp;q->coef=coef; / 將q插入鏈表中q->next=pc->next;pc->next=q;pc=q；return f3; / 返回PNode * PolySub(PNode *f1,PNode *f2)/編寫此算法，實現(xiàn)兩多項式(頭指針分別為fl和f2)相減，返回差多項式f3=f1-f2 oPNode *pa=f1->n

25、ext,*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; / 將q插入鏈表中 q->next=pc->n

26、ext;pc->next=q;pc=q;pb=pb->next;head=PolyAdd(f1,f3); /調(diào)用加法函數(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(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