數(shù)據(jù)結(jié)構(gòu)線性表的應(yīng)用實(shí)驗(yàn)報(bào)告

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

2、值。測(cè)試該函數(shù)（從終端輸入 一個(gè)x的值，調(diào)用該函數(shù)并顯示返回結(jié)果）。6）多項(xiàng)式相減：編寫(xiě)一個(gè)函數(shù)，求兩個(gè)多項(xiàng)式相減的 多項(xiàng)式。7）多項(xiàng)式相乘：編寫(xiě)一個(gè)函數(shù)，求兩個(gè)多項(xiàng)式的乘積 多項(xiàng)式。3 .算法說(shuō)明：1）多項(xiàng)式的建立、顯示和相加算法見(jiàn)講義?？尚薷娘@示函數(shù)，使輸由的多項(xiàng)式更符合表達(dá)規(guī)范2)多項(xiàng)式減法：同次項(xiàng)的系數(shù)相減(缺項(xiàng)的系數(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)多項(xiàng)式乘法：兩個(gè)多項(xiàng)式的相乘是“系數(shù)相乘，指 數(shù)相加”。算法思想是用一個(gè)多項(xiàng)式中的各項(xiàng)分別

3、與 另一個(gè)多項(xiàng)式相乘，形成多個(gè)多項(xiàng)式，再將它們累 加在一起。例如， 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 .實(shí)驗(yàn)步驟:根據(jù)實(shí)驗(yàn)報(bào)告的要求，我對(duì)文件夾里的 C文件進(jìn)行了豐富和修改，步驟如下：鏈表結(jié)構(gòu)建立多項(xiàng)式：typedef struct polynode float coef; /系數(shù)int exp; /指數(shù)struct polynode *next; /下結(jié)

4、點(diǎn)指針 PNode;編寫(xiě)函數(shù)，實(shí)現(xiàn)多項(xiàng)式的加法運(yùn)算；PNode * PolyAdd (PNode *f1, PNode *f2) / 實(shí)現(xiàn)加法功臺(tái)匕 目匕。 / 實(shí)現(xiàn)兩多項(xiàng)式（頭指針?lè)謩e為fl和f2）相加，返回和多項(xiàng)式f3=f1+f2PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;int exp;建立頭指針?lè)祷仡^指針float coef;f3=(PNode *)malloc(sizeof(PNode); /f3->exp=-1; /對(duì)頭指針初始化f3->next=f3;pc=f3; / 將pc指向頭指針while (pa->e

5、xp!=-1 | pb->exp!=-1) /時(shí)，跳由循環(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指針存放負(fù)指數(shù)的指針q->exp=exp;q->coef=coef; / 將q插入鏈表中q->next=pc->next;pc->next=q;pc=q；return f3; /返回實(shí)現(xiàn)多項(xiàng)式的顯示；void ShowPloy(PNode *h)/用if語(yǔ)句判斷，當(dāng)指數(shù)為。是，只輸由系數(shù)；當(dāng) 指數(shù)為1時(shí)，輸由系數(shù)和 X;當(dāng)系數(shù)為1時(shí)，輸由X 和指數(shù)。h=paixu(h); /整理函數(shù)，使之降曷排列PNode *p=h->next;if(p=h)printf("表達(dá)式為空n");return;if(p-&

7、gt;coef=1)printf("xA%d",p->exp);/用 if 語(yǔ)句判斷，若輸由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ù)為負(fù),不用輸由加號(hào)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);多項(xiàng)式求值double PolyValue(PNode *h, float x) /編寫(xiě)算法，求以h為頭指針的多項(xiàng)式在 x點(diǎn)的值并返回 該值。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;多項(xiàng)式相減PNode * PolySub(PNode *f1,PNode *f2)/編寫(xiě)此算法，實(shí)現(xiàn)兩多項(xiàng)式(頭指針?lè)謩e為fl和f2)相減，返回差多項(xiàng)式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) /返回頭指針時(shí)，跳由循環(huán)。q=(PNode *)malloc(sizeof(PNode); /建立新的q指針存放負(fù)指數(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; / 返回頭指針多項(xiàng)式相乘PNode * PolyMult(PNode *f1,PNode *f2)/實(shí)現(xiàn)兩多項(xiàng)式(頭指針?lè)謩e

13、為 fl和f2)相乘，返回乘積 多項(xiàng)式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) /多項(xiàng)式相乘，錄入 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; / 返回頭指針程序運(yùn)行截圖曷昌昌 FJ rJI-CJ 號(hào)號(hào)號(hào)i數(shù) 系系系 的的3項(xiàng)項(xiàng)項(xiàng)3口口 B士戶土盧士尸數(shù)數(shù)數(shù)靠系的的的捐項(xiàng)-12 3 - 12 3 承第第第 式式 項(xiàng)項(xiàng)項(xiàng)點(diǎn)作項(xiàng) 的多多多多多項(xiàng)穗瑞項(xiàng)領(lǐng)瑞多請(qǐng)請(qǐng)耍.1清請(qǐng)請(qǐng)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- 測(cè)試成功!程序完整源代碼如下：#include <stdio.h>#include <stdlib.h>#

16、include <math.h>typedef struct polynode float coef; /系數(shù)int exp; /struct polynode *next; /指數(shù)下一結(jié)點(diǎn)指針 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值進(jìn)行比較，while(q->exp!=-1) /q一圈 if(p->exp>q->exp) / 移將多項(xiàng)式降哥排列為q的前驅(qū)，q與p指數(shù)指數(shù)

17、為頭指針推由循環(huán)，q移動(dòng)比較，若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é)點(diǎn)，釋放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語(yǔ)句判斷，當(dāng)指數(shù)為。是，只輸由系數(shù)；當(dāng)指數(shù)為1時(shí)，輸由系數(shù)和 X;當(dāng)系數(shù)為1時(shí)，輸由X和指數(shù)。h=paixu(h); / 整理函數(shù)，使之降曷排列PNode *p=h->next;if(p=h)printf("表達(dá)式為空n");return;if(p->coef=1)printf("xA%d",p->exp);/用 if 語(yǔ)句判斷，若輸由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ù)為負(fù)，不用輸由加號(hào)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() /建立多項(xiàng)式鏈表，返回頭指針PNode * head, *p, *s;int i,n;head=(PNode *)malloc(sizeof(PNode);head->exp=-1;p=head;printf(" 多項(xiàng)

21、式的項(xiàng)數(shù)為：")；scanf("%d",&n);for(i=1;i<=n; i+)s=(PNode *)malloc(sizeof(PNode);printf(" 請(qǐng)輸入多項(xiàng)式第項(xiàng)的系數(shù)和指數(shù)(用逗號(hào) 隔開(kāi)):",i);scanf("%g,%d”,&s->coef,&s->exp);p->next=s;p=s;p->next=head;return head;void FreePoly(PNode *h)/編寫(xiě)此算法，將以h為頭指針的多項(xiàng)式的鏈表結(jié)點(diǎn)逐個(gè)釋放。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) /實(shí)現(xiàn)加法功能。 /實(shí)現(xiàn)兩多項(xiàng)式(頭指針?lè)謩e為fl和f2)相加，返回和多項(xiàng)式f3=f1+f2PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;int exp;建立頭指針?lè)祷仡^指針float coef;f3=(PNode *)malloc(sizeof(PNo

23、de); /f3->exp=-1; /對(duì)頭指針初始化f3->next=f3;pc=f3; / 將pc指向頭指針while (pa->exp!=-1 | pb->exp!=-1) /時(shí)，跳由循環(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指針存放負(fù)指數(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ě)此算法，實(shí)現(xiàn)兩多項(xiàng)式(頭指針?lè)謩e為fl和f2)相減，返回差多項(xiàng)式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) /返回頭指針時(shí)，跳由循環(huán)。q=(PNode *)malloc(sizeof(PNode); /建立新的q指針存放負(fù)指數(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)/實(shí)現(xiàn)兩多項(xiàng)式(頭指針?lè)謩e為fl和f2)相乘，返回乘積多項(xiàng)式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) /多項(xiàng)式相乘，錄入 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