word實(shí) 驗(yàn) 報(bào) 告課程名稱 _數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)_實(shí)驗(yàn)項(xiàng)目 _線性表的應(yīng)用 _實(shí)驗(yàn)儀器 _PC機(jī)_系 別_電子信息與通信學(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)容：1) 編寫函數(shù)，實(shí)現(xiàn)用鏈表結(jié)構(gòu)建立多項(xiàng)式；2) 編寫函數(shù)，實(shí)現(xiàn)多項(xiàng)式的加法運(yùn)算；3) 編寫函數(shù)，實(shí)現(xiàn)多項(xiàng)式的顯示；4) 測(cè)試：編寫主函數(shù)，它定義并建立兩個(gè)多項(xiàng)式，顯示兩個(gè)多項(xiàng)式，然后將它們相加并顯示結(jié)果。變換測(cè)試用的多項(xiàng)式，檢查程序的執(zhí)行結(jié)果。選做容：修改程序，選擇實(shí)現(xiàn)以下功能：5) 多項(xiàng)式求值：編寫一個(gè)函數(shù)，根據(jù)給定的x值計(jì)算并返回多項(xiàng)式f(x)的值。測(cè)試該函數(shù)從終端輸入一個(gè)x的值，調(diào)用該函數(shù)并顯示返回結(jié)果。6) 多項(xiàng)式相減：編寫一個(gè)函數(shù)，求兩個(gè)多項(xiàng)式相減的多項(xiàng)式。7) 多項(xiàng)式相乘：編寫一個(gè)函數(shù)，求兩個(gè)多項(xiàng)式的乘積多項(xiàng)式。3. 算法說明：1) 多項(xiàng)式的建立、顯示和相加算法見講義。可修改顯示函數(shù)，使輸出的多項(xiàng)式更符合表達(dá)規(guī)。2) 多項(xiàng)式減法：同次項(xiàng)的系數(shù)相減缺項(xiàng)的系數(shù)是0。例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，如此a(x)-b(x)=4x3-5x2-x+3。提示：a(x)-b(x)= a(x)+(-b(x)。3) 多項(xiàng)式乘法：兩個(gè)多項(xiàng)式的相乘是“系數(shù)相乘，指數(shù)相加。算法思想是用一個(gè)多項(xiàng)式中的各項(xiàng)分別與另一個(gè)多項(xiàng)式相乘，形成多個(gè)多項(xiàng)式，再將它們累加在一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，如此a(x)*b(x)=(-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) =(20x5-8x4-12x3) +(-15x3+6x2+9x) = 20x5-8x4-27x3+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é)點(diǎn)指針 PNode; 編寫函數(shù)，實(shí)現(xiàn)多項(xiàng)式的加法運(yùn)算；PNode * PolyAdd (PNode *f1, PNode *f2) /實(shí)現(xiàn)加法功能。 /實(shí)現(xiàn)兩多項(xiàng)式頭指針分別為f1和f2相加，返回和多項(xiàng)式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; /對(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;else exp=pa->exp;coef=pa->coef+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; /返回實(shí)現(xiàn)多項(xiàng)式的顯示；void ShowPloy(PNode *h) /用if語(yǔ)句判斷，當(dāng)指數(shù)為0是，只輸出系數(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("x%d",p->exp); /用if語(yǔ)句判斷，假設(shè)輸出xo和x1值為0和1 直接輸出數(shù)據(jù)。 else if(p->exp=1) printf("%gx", p->coef);else if(p->exp=0) printf("%g", p->coef);else printf("%gx%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("x%d",p->exp);else if(p->exp=1) printf("%gx", p->coef);else if(p->exp=0) printf("%g", p->coef);else printf("%gx%d", p->coef, p->exp); p=p->next; printf("n");主函數(shù)void main()PNode *F1,*F2,*F3;float 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=:");ShowPloy(F3);printf("nx的值為: ");scanf("%f", &x);printf("nf1(x=%.3f)=%.3fn",x,PolyValue(F1,x);多項(xiàng)式求值double PolyValue(PNode *h, float x) /編寫算法，求以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->coef)*pow(x,pa->exp);pa=pa->next;return f;多項(xiàng)式相減PNode * PolySub(PNode *f1,PNode *f2)/編寫此算法，實(shí)現(xiàn)兩多項(xiàng)式頭指針分別為f1和f2相減，返回差多項(xiàng)式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) /返回頭指針時(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)式頭指針分別為f1和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->next;pb=pb->next;pa=pa->next;return head; /返回頭指針程序運(yùn)行截圖測(cè)試成功！程序完整源代碼如下：#include <stdio.h>#include <stdlib.h>#include <math.h>typedef struct polynode float coef; /系數(shù) int exp; /指數(shù) struct polynode *next; /下一結(jié)點(diǎn)指針 PNode; PNode * paixu(PNode *f) /將多項(xiàng)式降冪排列PNode *p,*q,*r,*p0,*q0;p=f->next;q=p->next;p0=f;q0=p; while(p->exp!=-1) /p為q的前驅(qū)，q與p指數(shù)指數(shù)值進(jìn)展比擬，while(q->exp!=-1) /q為頭指針推出循環(huán)，q移動(dòng)一圈if(p->exp>q->exp) /比擬，假設(shè)p大于q如此q后移 q0=q;q=q->next;else if(p->exp<q->exp) /假設(shè)p小于q如此q插入p之前r=q->next;q->next=p0->next;q0->next=r;p0->next=q;p=q;q=r;else if(p->exp=q->exp) /假設(shè)相等，p的coef 與q的相加，然后刪除q節(jié)點(diǎn)，釋放q的空間p->coef+=q->coef;q0->next=q->next;q=q->next;p0=p;p=p->next;q=p->next;q0=p;return f;void ShowPloy(PNode *h) /用if語(yǔ)句判斷，當(dāng)指數(shù)為0是，只輸出系數(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("x%d",p->exp); /用if語(yǔ)句判斷，假設(shè)輸出xo和x1值為0和1 直接輸出數(shù)據(jù)。 else if(p->exp=1) printf("%gx", p->coef);else if(p->exp=0) printf("%g", p->coef);else printf("%gx%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("x%d",p->exp);else if(p->exp=1) printf("%gx", p->coef);else if(p->exp=0) printf("%g", p->coef);else printf("%gx%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)式的項(xiàng)數(shù)為: ");scanf("%d",&n);for(i=1;i<=n; i+) s=(PNode *)malloc(sizeof(PNode);printf("請(qǐng)輸入多項(xiàng)式第%d項(xiàng)的系數(shù)和指數(shù)用逗號(hào)隔開: ",i);scanf("%g,%d",&s->coef,&s->exp);p->next=s;p=s; p->next=head;return head;void FreePoly(PNode *h) /編寫此算法，將以h為頭指針的多項(xiàng)式的鏈表結(jié)點(diǎn)逐個(gè)釋放。PNode *p,*q;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)式頭指針分別為f1和f2相加，返回和多項(xiàng)式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; /對(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;else exp=pa->exp;coef=pa->coef+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)/編寫此算法，實(shí)現(xiàn)兩多項(xiàng)式頭指針分別為f1和f2相減，返回差多項(xiàng)式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) /返回頭指針時(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; /返回頭指針PNode * PolyMult(PNode *f1,PNode *f2)/實(shí)現(xiàn)兩多項(xiàng)式頭指針分別為f1和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->next;pb=pb->next;pa=pa->next;return head; /返回頭指針double PolyValue(PNode *h, float x) /實(shí)現(xiàn)多項(xiàng)式求值功能。利用指針求出每一項(xiàng)的值，再用加法加起來(lái)。/編寫算法，求以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->coef)*pow(x,pa->exp);pa=pa->next;return f;void main()PNode *F1,*F2,*F3;float 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=:");ShowPloy(F3);printf("nx的值為: ");scanf("%f", &x);printf("nf1(x=%.3f)=%.3fn",x,PolyValue(F1,x);實(shí)驗(yàn)總結(jié)：這次試驗(yàn)提高了我的編程能力，讓我認(rèn)識(shí)到了我C語(yǔ)言的不足之處。也使我了解了線性鏈表是具有存儲(chǔ)結(jié)構(gòu)的線性表，它用節(jié)點(diǎn)存放線性表中的數(shù)據(jù)元素，邏輯上相鄰的節(jié)點(diǎn)不能隨機(jī)存取，因?yàn)檫@個(gè)原因我前期的程序一直出錯(cuò)，以后編程序的時(shí)候要牢記。25 / 25