《大數(shù)據(jù)結(jié)構(gòu)線性表格地指導(dǎo)應(yīng)用實驗資料報告材料》由會員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)線性表格地指導(dǎo)應(yīng)用實驗資料報告材料（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 實 驗 報 告 課程名稱 ____數(shù)據(jù)結(jié)構(gòu)上機實驗__________ 實驗項目 ______線性表的應(yīng)用 ____________ 實驗儀器 ________PC機___________________ 系 別_____電子信息與通信學(xué)院___ 專 業(yè)________ ___ 班級/學(xué)號______ __ 學(xué)生 ______ ___________ 實驗日期 _______________________ 成 績 ____________________

2、___ 指導(dǎo)教師 _______________________ 實驗一. 線性表的應(yīng)用 1. 實驗?zāi)康模赫莆站€性鏈表的存儲、運算與應(yīng)用。利用鏈表實現(xiàn)一元多項式計算。 2. 實驗容： 1) 編寫函數(shù)，實現(xiàn)用鏈表結(jié)構(gòu)建立多項式； 2) 編寫函數(shù)，實現(xiàn)多項式的加法運算； 3) 編寫函數(shù)，實現(xiàn)多項式的顯示； 4) 測試：編寫主函數(shù)，它定義并建立兩個多項式，顯示兩個多項式，然后將它們相加并顯示結(jié)果。變換測試用的多項式，檢查程序的執(zhí)行結(jié)果。 選做容：修改程序，選擇實現(xiàn)以下功能： 5) 多項式求值：編寫一個函數(shù)，根據(jù)給定的x值計算并返回多項式f(x)的值。測試該函數(shù)〔從終端

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

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

5、 //指數(shù) struct polynode *next; //下一結(jié)點指針 } PNode; 編寫函數(shù)，實現(xiàn)多項式的加法運算； PNode * PolyAdd (PNode *f1, PNode *f2) //實現(xiàn)加法功能。 { //實現(xiàn)兩多項式〔頭指針分別為f1和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; //

6、對頭指針初始化 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->expexp) { exp=pb->exp; coef=pb->coef; pb=pb->next; } else { exp=pa->exp; coef=pa->coef+pb->

7、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; //返回 } 實現(xiàn)多項式的顯示； void ShowPloy(PNode *h) //用if語句判斷，當(dāng)指數(shù)為0是，只輸出系數(shù)；當(dāng)指數(shù)為1時，輸出系數(shù)和X；當(dāng)系數(shù)為1

8、時，輸出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語句判斷，假設(shè)輸出x^o和x^1值為0和1 直接輸出數(shù)據(jù)。 else if(p->exp==1) printf("%gx", p->coef); else if(p->exp==0) printf("%g", p->coef); else printf("

9、%gx^%d", p->coef, p->exp); p=p->next; while (p!=h) { if(p->coef>0) printf("+"); //系數(shù)為負(fù)，不用輸出加號 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->nex

10、t; } 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=:"); Show

11、Ploy(F3); F3=PolyMult(F1,F2); printf("\nf1*f2=:"); ShowPloy(F3); printf("\nx的值為: "); scanf("%f", &x); printf("\nf1(x=%.3f)=%.3f\n",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->n

12、ext; while(pa->exp!=-1) //使用f+=coef*pow，返回f { f+=(pa->coef)*pow(x,pa->exp); pa=pa->next; } return f; } 多項式相減 PNode * PolySub(PNode *f1,PNode *f2) {//編寫此算法，實現(xiàn)兩多項式〔頭指針分別為f1和f2〕相減，返回差多項式f3=f1-f2。 PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head; f3=(PNode *)malloc(sizeof(PNode)); //建立頭指

13、針 f3->exp=-1; //頭指針的初始化 f3->next=f3; pc=f3; //pc指向頭指針,便于操作。 while(pb->exp!=-1) //返回頭指針時，跳出循環(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

14、); //調(diào)用加法函數(shù)做減法 return head; //返回頭指針 } 多項式相乘 PNode * PolyMult(PNode *f1,PNode *f2) {//實現(xiàn)兩多項式〔頭指針分別為f1和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!=

15、-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->next; } pb=pb->next; pa=pa->next; } return head; //返回頭指針 } 程序運行截圖 測試成功~！ 程序完整

16、源代碼如下： #include #include #include typedef struct polynode { float coef; //系數(shù) int exp; //指數(shù) struct polynode *next; //下一結(jié)點指針 } PNode; PNode * paixu(PNode *f) //將多項式降冪排列 { PNode *p,*q,*r,*p0,*q0; p=f->next; q=p->next; p0=f;

17、q0=p; while(p->exp!=-1) //p為q的前驅(qū)，q與p指數(shù)指數(shù)值進(jìn)展比擬， { while(q->exp!=-1) //q為頭指針推出循環(huán)，q移動一圈 { if(p->exp>q->exp) //比擬，假設(shè)p大于q如此q后移 { q0=q; q=q->next; } else if(p->expexp) //假設(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->ex

18、p) //假設(shè)相等，p的coef 與q的相加，然后刪除q節(jié)點，釋放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語句判斷，當(dāng)指數(shù)為0是，只輸出系數(shù)；當(dāng)指數(shù)為1時，輸出系數(shù)和X；當(dāng)系數(shù)為1時，輸出X和指數(shù)。 { h=paixu(h); //整理函數(shù)，使之降冪排列 PNode *p=h->next; if(p==h) {

19、 printf("表達(dá)式為空\n"); return; } if(p->coef==1) printf("x^%d",p->exp); //用if語句判斷，假設(shè)輸出x^o和x^1值為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)

20、printf("+"); //系數(shù)為負(fù)，不用輸出加號 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() //建立多項式鏈表，返回頭指針 { PN

21、ode * 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",&s->coef,&s->exp); p->next=s; p=s; } p->next=h

22、ead; return head; } void FreePoly(PNode *h) { //編寫此算法，將以h為頭指針的多項式的鏈表結(jié)點逐個釋放。 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) //實現(xiàn)加法功能。 { //實現(xiàn)兩多項式〔頭指針

23、分別為f1和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->exp;

24、 coef=pa->coef; pa=pa->next; } else if (pa->expexp) { 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;

25、 //將q插入鏈表中 q->next=pc->next; pc->next=q; pc=q; } } return f3; //返回 } PNode * PolySub(PNode *f1,PNode *f2) {//編寫此算法，實現(xiàn)兩多項式〔頭指針分別為f1和f2〕相減，返回差多項式f3=f1-f2。 PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head; f3=(PNode *)malloc(sizeof(PNode)); //建立頭指針 f3->exp=-1; //頭指針的初始化 f3->nex

26、t=f3; pc=f3; //pc指向頭指針,便于操作。 while(pb->exp!=-1) //返回頭指針時，跳出循環(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; //

27、返回頭指針 } PNode * PolyMult(PNode *f1,PNode *f2) {//實現(xiàn)兩多項式〔頭指針分別為f1和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-

28、>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) //實現(xiàn)多項式求值功能。利用指針求出每一項的

29、值，再用加法加起來。 { //編寫算法，求以h為頭指針的多項式在x點的值并返回該值。 double f=0.0; //求出f=f(x); PNode *pa; h=paixu(h); pa=h->next; while(pa->exp!=-1) //使用f+=coef*pow，返回f { f+=(pa->coef)*pow(x,pa->exp); pa=pa->next; } return f; } void main() { PNode *F1,*F2,*F3; float x; F1=CreatPoly(); F2=CreatPoly();

30、 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)=%.3f\n",x,PolyValue(F1,x)); } 實驗總結(jié)： 這次試驗提高了我的編程能力，讓我認(rèn)識到了我C語言的不足之處。也使我了解了線性鏈表是具有存儲結(jié)構(gòu)的線性表，它用節(jié)點存放線性表中的數(shù)據(jù)元素，邏輯上相鄰的節(jié)點不能隨機存取，因為這個原因我前期的程序一直出錯，以后編程序的時候要牢記。 25 / 25