數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)順序結(jié)構(gòu)動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法減法乘法的實(shí)現(xiàn)

1、安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí) 10計(jì)本2班 學(xué)號(hào)10012116姓名 聯(lián)系方式 指導(dǎo)教師20 11 年 12 月 28 日目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目1.2、要求2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明3.2、算法的設(shè)計(jì)思想3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換4、調(diào)試與測(cè)試：4.1、調(diào)試方法與步驟：4.2、測(cè)試結(jié)果的分析與討論：4.3、測(cè)試過程中遇到的主要問題及采取的解

2、決措施：5、時(shí)間復(fù)雜度的分析：6、源程序清單和執(zhí)行結(jié)果7、c程序設(shè)計(jì)總結(jié)8、致謝9、參考文獻(xiàn)1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目要求順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)1順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)?？梢苑譃閹讉€(gè)模塊：輸入模塊、輸出模塊（升冪降冪）、數(shù)據(jù)處理模塊（多項(xiàng)式的加減乘）、主程序模塊。2在程序過程中加入漢字提示符，讓讀者清楚明白的操作該程序。運(yùn)行程序時(shí)看起來簡(jiǎn)潔有序，操作簡(jiǎn)單明了。3程序執(zhí)行時(shí)的命令：選擇創(chuàng)建兩個(gè)一元多項(xiàng)式輸入第一個(gè)一元多項(xiàng)式的項(xiàng)數(shù)依次輸入一

3、元多項(xiàng)式的系數(shù)和指數(shù)以相同方式輸入第二個(gè)一元多項(xiàng)式選擇操作方式選擇降冪或升冪排序輸出結(jié)果是否退出4.測(cè)試數(shù)據(jù)。輸入的一元多項(xiàng)式系數(shù)指數(shù)分別為7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法結(jié)果為；升冪 降冪減法結(jié)果為：升冪 降冪乘法結(jié)果為：升冪 降冪 3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明#include<stdio.h>#include<stdlib.h>typedef struct float coef; /系數(shù) int expn; /指數(shù)#include<stdio.h>#include<stdlib.h>type

4、def struct float coef; /系數(shù) int expn; /指數(shù)term;typedef struct lnode term data; /term多項(xiàng)式值 struct lnode *next;lnode,*linklist;typedef linklist polynomail;/*比較指數(shù)*/int cmp(term a,term b) if(a.expn>b.expn) return 1; if(a.expn=b.expn) return 0; if(a.expn<b.expn) return -1; else exit(-2);/*又小到大排列*/void

5、 arrange1(polynomail pa) polynomail h=pa,p,q,r; if(pa=null) exit(-2); for(p=pa;p->next!=null;p=p->next); r=p; for(h=pa;h->next!=r;)/大的沉底 for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next->data,p->next->next->data)=1) q=p->next->next; p->next->next=q

6、->next; q->next=p->next; p->next=q; r=p;/r指向參與比較的最后一個(gè)，不斷向前移動(dòng) /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=null) exit(-2); for(p=pa;p->next!=null;p=p->next); r=p; for(h=pa;h->next!=r;)/小的沉底 for(p=h;p->next!=r&&p!=r;p=p->next) if(cmp(p->next

7、->next->data,p->next->data)=1) q=p->next->next; p->next->next=q->next; q->next=p->next; p->next=q; r=p;/r指向參與比較的最后一個(gè)，不斷向前移動(dòng) /*打印多項(xiàng)式,求項(xiàng)數(shù)*/int printpolyn(polynomail p) int i; polynomail q; if(p=null) printf("無項(xiàng)！n"); else if(p->next=null) printf("y=

8、0n"); else printf("該多項(xiàng)式為y=");q=p->next;i=1; if(q->data.coef!=0&&q->data.expn!=0) printf("%.2fx%d",q->data.coef,q->data.expn); i+; if(q->data.expn=0&&q->data.coef!=0) printf("%.2f",q->data.coef);/打印第一項(xiàng) q=q->next; if(q=null)

9、 printf("n");return 1; while(1)/while中，打印剩下項(xiàng)中系數(shù)非零的項(xiàng)， if(q->data.coef!=0&&q->data.expn!=0) if(q->data.coef>0) printf("+"); printf("%.2fx%d",q->data.coef,q->data.expn); i+; if(q->data.expn=0&&q->data.coef!=0) if(q->data.coef>0

10、) printf("+"); printf("%f",q->data.coef); q=q->next; if(q=null) printf("n"); break; return 1;/*1、創(chuàng)建并初始化多項(xiàng)式鏈表*/polynomail creatpolyn(polynomail p,int m) polynomail r,q,p,s,q; int i; p=(lnode*)malloc(sizeof(lnode); r=p; for(i=0;i<m;i+) s=(lnode*)malloc(sizeof(lno

11、de); printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)和指數(shù)：",i+1); scanf("%f%d",&s->data.coef,&s->data.expn); r->next=s; r=s; r->next=null; if(p->next->next!=null) for(q=p->next;q!=null/*&&q->next!=null*/;q=q->next)/合并同類項(xiàng) for(p=q->next,r=q;p!=null;) if(q->data.ex

12、pn=p->data.expn) q->data.coef=q->data.coef+p->data.coef; r->next=p->next; q=p;p=p->next; free(q); else r=r->next; p=p->next; return p;/*2、兩多項(xiàng)式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r;int j; p=pa->next;q=pb->next; newp=(lnode*)mallo

13、c(sizeof(lnode); r=newp; while(p&&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p->data,q->data) case -1: s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef+q->data.coef; if(s->data.coe

14、f!=0.0) s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; q=q->next; break; case 1: s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnode); s->data.coef=p->data.coef; s-

15、>data.expn=p->data.expn; r->next=s; r=s; p=p->next; while(q) s=(lnode*)malloc(sizeof(lnode); s->data.coef=q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; r->next=null; for(q=newp->next;q->next!=null;q=q->next)/合并同類項(xiàng) for(p=q;p!=null&&a

16、mp;p->next!=null;p=p->next) if(q->data.expn=p->next->data.expn) q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); printf("升序 1 , 降序 2n"); printf("選擇:"); scanf("%d",&j); if(j=1) arrange1(ne

17、wp); else arrange2(newp); return newp;/*3、兩多項(xiàng)式相減*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r,q; int j; p=pa->next;q=pb->next; newp=(lnode*)malloc(sizeof(lnode); r=newp; while(p&&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p->data,q->data) case -1:

18、s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; break; case 0: s->data.coef=p->data.coef-q->data.coef; if(s->data.coef!=0.0) s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; q=q->next; break; case 1: s->data.coef=-

19、q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnode); s->data.coef=p->data.coef; s->data.expn=p->data.expn; r->next=s; r=s; p=p->next; while(q) s=(lnode*)malloc(sizeof(lnode); s->data.coe

20、f=-q->data.coef; s->data.expn=q->data.expn; r->next=s; r=s; q=q->next; r->next=null; if(newp->next!=null&&newp->next->next!=null)/合并同類項(xiàng) for(q=newp->next;q!=null;q=q->next) for(p=q->next,r=q;p!=null;) if(q->data.expn=p->data.expn) q->data.coef=q-&g

21、t;data.coef+p->data.coef; r->next=p->next; q=p;p=p->next; free(q); else r=r->next; p=p->next; printf("升序 1 , 降序 2n"); printf("選擇:"); scanf("%d",&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*4兩多項(xiàng)式相乘*/polynomail mulpolyn(polynomail

22、pa,polynomail pb) polynomail s,newp,q,p,r; int i=20,j; newp=(lnode*)malloc(sizeof(lnode); r=newp; for(p=pa->next;p!=null;p=p->next) for(q=pb->next;q!=null;q=q->next) s=(lnode*)malloc(sizeof(lnode); s->data.coef=p->data.coef*q->data.coef; s->data.expn=p->data.expn+q->dat

23、a.expn; r->next=s; r=s; r->next=null; printf("升序 1 , 降序 2n"); printf("選擇:"); scanf("%d",&j); if(j=1) arrange1(newp); else arrange2(newp); for(;i!=0;i-) for(q=newp->next;q->next!=null;q=q->next)/合并同類項(xiàng) for(p=q;p!=null&&p->next!=null;p=p->n

24、ext) if(q->data.expn=p->next->data.expn) q->data.coef=q->data.coef+p->next->data.coef; r=p->next; p->next=p->next->next; free(r); return newp;/*5、銷毀已建立的兩個(gè)多項(xiàng)式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=null) q=p; p=p->next; free(q);

25、p=pb; while(p!=null) q=p; p=p->next; free(q); printf("兩個(gè)多項(xiàng)式已經(jīng)銷毀n");void main() polynomail pa=null,pb=null; polynomail p,q; polynomail addp=null,subp=null,mulp=null; int n,m; int sign='y' printf("1、創(chuàng)建兩個(gè)一元多項(xiàng)式n"); printf("2、兩多項(xiàng)式相加得一新多項(xiàng)式n"); printf("3、兩多項(xiàng)式相減

26、得一新多項(xiàng)式n"); printf("4、兩多項(xiàng)式相乘得一新多項(xiàng)式n"); printf("5、銷毀已建立的兩個(gè)多項(xiàng)式n"); printf("6、退出n"); printf("n"); while(sign!='n') printf("請(qǐng)選擇："); scanf("%d",&n); switch(n) case 1: if(pa!=null) printf("已建立兩個(gè)一元多項(xiàng)式，請(qǐng)選擇其他操作！"); break; p

27、rintf("請(qǐng)輸入第一個(gè)多項(xiàng)式：n"); printf("要輸入幾項(xiàng)："); scanf("%d",&m); while(m=0) printf("m不能為0，請(qǐng)重新輸入m:"); scanf("%d",&m); pa=creatpolyn(pa,m); printpolyn(pa); printf("請(qǐng)輸入第二個(gè)多項(xiàng)式：n"); printf("要輸入幾項(xiàng)："); scanf("%d",&m); pb=cre

28、atpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=null) printf("請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式！n"); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=null) printf("請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式！n"); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=null) printf("請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式

29、！n"); break; mulp=mulpolyn(pa,pb); printpolyn(mulp); break; case 5: if(pa=null) printf("請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式！n"); break; delpolyn(pa,pb); pa=pb=null; break; case 6: if(addp!=null) p=addp; while(p!=null) q=p; p=p->next; free(q); if(subp!=null) p=subp; while(p!=null) q=p; p=p->next; free(q

30、); exit(-2); /switch /while3.2、算法的設(shè)計(jì)思想a) 相加運(yùn)算對(duì)于兩個(gè)稀疏矩陣相加，即行與行，列與列相加b）相乘運(yùn)算若設(shè)q=m*n 其中m是m1*n1矩陣，n是m2*n2矩陣，只有當(dāng)n1=m2時(shí)才可以相乘。乘積矩陣q中元素 q（i，j）=m（i，k）*n（k，j） 1im1，1jn2在算法中，不論m（i，k）和 n（k，j）的值是否為零，都要進(jìn)行一次乘法運(yùn)算，而實(shí)際上，這兩者有一個(gè)值為零時(shí)，其乘積也為零。因此，在對(duì)稀疏矩陣進(jìn)行運(yùn)算時(shí)，應(yīng)免去這種無效操作，只需在m.data和n.data中找到相應(yīng)的各對(duì)元素(即m.data中的j值和 n.data中的i值相等的各對(duì)元素)相乘即可。 c) 轉(zhuǎn)置運(yùn)算 對(duì)于一個(gè)m*n的矩陣m，它的轉(zhuǎn)置矩陣t是一個(gè)n*m的矩陣，且t（i，j）=m（j，i），1in，1jm。完成一個(gè)稀疏矩陣的轉(zhuǎn)置分為三步：（1）將矩陣的行列值相互交換；（2）將每個(gè)三元組中的i和j相互調(diào)換；（3）重排三元組之間的次序便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置；3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換a)加法運(yùn)算兩