數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言)一元稀疏多項(xiàng)式計(jì)算器

1、實(shí)驗(yàn)報(bào)告一題目：編制一個(gè)一元稀疏多項(xiàng)式計(jì)算器班級(jí)：1302018 姓名：王雪 學(xué)號(hào)完成日期：2014.4.5一、需求分析1、一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器的功能是：1.1 輸入并建立多項(xiàng)式；1.2 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列； 1.3多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；1.4 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。2、設(shè)計(jì)思路:2.1 定義線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)；2.2 建立多項(xiàng)式存儲(chǔ)結(jié)構(gòu)，定義指針*next2.3利用鏈表實(shí)現(xiàn)隊(duì)列的構(gòu)造。每次輸入一項(xiàng)

2、的系數(shù)和指數(shù)，可以輸出構(gòu)造的一元多項(xiàng)式2.4演示程序以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式執(zhí)行，即在計(jì)算機(jī)終站上顯示“提示信息”之后，由用戶(hù)在鍵盤(pán)上輸入演示程序中規(guī)定的運(yùn)行命令；最后根據(jù)相應(yīng)的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項(xiàng)式以及多項(xiàng)式相加的運(yùn)行結(jié)果在屏幕上顯示。多項(xiàng)式顯示的格式為：c1xe1+c2xe2+cnxen3、設(shè)計(jì)思路分析要解決多項(xiàng)式相加，必須要有多項(xiàng)式，所以必須首先建立兩個(gè)多項(xiàng)式，在這里采用鏈表的方式存儲(chǔ)鏈表，所以我將結(jié)點(diǎn)結(jié)構(gòu)體定義為序數(shù)coef指數(shù)expn指針域next運(yùn)用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個(gè)一元多項(xiàng)式a和b，a+b的求和運(yùn)算等同于

3、單鏈表的插入問(wèn)題（將單鏈表polyn p中的結(jié)點(diǎn)插入到單鏈表polyn h中），因此“和多項(xiàng)式”中的結(jié)點(diǎn)無(wú)須另生成。為了實(shí)現(xiàn)處理，設(shè)p、q分別指向單鏈表polya和polyb的當(dāng)前項(xiàng)，比較p、q結(jié)點(diǎn)的指數(shù)項(xiàng)，由此得到下列運(yùn)算規(guī)則： 若p->expn<q->expn，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移。 若p->expn=q->expn，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。 若p->expn>q->expn，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來(lái)的鏈表上后移。

4、二、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序的功能，應(yīng)以帶頭結(jié)點(diǎn)的單鏈表表示多項(xiàng)式。為此，需要一個(gè)抽象數(shù)據(jù)類(lèi)型：?jiǎn)捂湵怼?.1單鏈表的抽象數(shù)據(jù)類(lèi)型定義ADT LinkList數(shù)據(jù)對(duì)象：D=ai|aiTermSet,i=1,2,m,m0 TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：R1=<ai-1,ai>ai-1,aiD且ai-1中的指數(shù)值<ai中的指數(shù)值,i=2,n基本操作： CreatLinkList(&p,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式p。DestoryLinkList(&p)初始條件：一元多項(xiàng)式p已存在。操作結(jié)果：銷(xiāo)毀一元

5、多項(xiàng)式p. PrintLinkList(p)初始條件：一元多項(xiàng)式p已存在。操作結(jié)果：打印輸出一元多項(xiàng)式p. AddLinkList（&pa,&pb）初始條件：一元多項(xiàng)式pa和pb已存在。操作結(jié)果：完成多項(xiàng)式的相加運(yùn)算，即：pa=pa+pb,并銷(xiāo)毀一元多項(xiàng)式pb. SubtractLinkList(&pa,&pb)初始條件：一元多項(xiàng)式pa和pb已存在。操作結(jié)果：完成多項(xiàng)式的想減運(yùn)算，即：pa=pa-pb,并銷(xiāo)毀一元多項(xiàng)式pb.ADT LinkList2.2本程序包括個(gè)模塊：1）主程序模塊：Void main（） 初始化； 輸出菜單； While（1） 接受命令；

6、處理命令；（循環(huán)一直為真直至接受退出命令）；2）單鏈表單元模塊實(shí)現(xiàn)單鏈表的抽象數(shù)據(jù)類(lèi)型；3）結(jié)點(diǎn)結(jié)構(gòu)單元模塊定義單鏈表的結(jié)點(diǎn)結(jié)構(gòu)。三、詳細(xì)設(shè)計(jì)3.1元素類(lèi)型、結(jié)點(diǎn)類(lèi)型和指針類(lèi)型typedef int Status; typedef int ElemType;typedef struct LNode    float     coef;                  

7、;    /系數(shù)    ElemType  expn;                   /指數(shù)    struct    LNode *next;            LNode,*LinkList;Status MakeN

8、ode(LinkList &p,LinkList head) /分配由p指向下一個(gè)多項(xiàng)式的頭結(jié)點(diǎn)head、后繼為空的結(jié)點(diǎn)，并返回TRUE， /若分配失敗，則返回FALSE p= (LinkList)malloc(sizeof(struct LNode);if(!p)return false;p=head;p->next=null;return ture;void FreeNode(LinkList &p) /釋放p所指結(jié)點(diǎn)free(q1);        q1=q2;    

9、;    q2=q2->next;3.2單鏈表的基本操作設(shè)置如下：void Insert(LinkList p,LinkList h)； /將節(jié)點(diǎn)p插入到多項(xiàng)式鏈表hLinkList CreateLinkList(LinkList head,int m);/建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式,并返回該多項(xiàng)式的頭結(jié)點(diǎn)；/若分配空間失敗，則返回FALSEvoid DestroyLinkList(LinkList p); /銷(xiāo)毀多項(xiàng)式pvoid PrintLinkList(LinkList P);/輸出構(gòu)造的一元多項(xiàng)式PStatus compare(L

10、inkList a,LinkList b) /節(jié)點(diǎn)進(jìn)行比較: a的指數(shù) >b的指數(shù)   return 1; a的指數(shù)=b的指數(shù)   return 0;a的指數(shù)<b的指數(shù)    return -1.LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多項(xiàng)式a+b，返回其頭指針LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多項(xiàng)式a-b，返回其頭指針其中部分操作的偽碼如下：LinkList CreateLinkList(LinkLis

11、t head,int m)   p=head=(LinkList)malloc(sizeof(struct LNode);    head->next=NULL;    for(i=0;i<m;i+)         p=(LinkList)malloc(sizeof(struct LNode);   /建立新結(jié)點(diǎn)以接收數(shù)據(jù)        printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):&

12、quot;,i+1);        scanf("%f %d",&p->coef,&p->expn);        Insert(p,head);                       

13、60;     /調(diào)用Insert函數(shù)插入結(jié)點(diǎn)     return head;/ CreateLinkListStatus compare(LinkList a,LinkList b)    if(a&&b)        if(!b|a->expn>b->expn) return 1;        else if(!a|a->expn<b->

14、;expn) return -1;        else return 0;    else if(!a&&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空    else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/ comparefloat ValueLinkList(LinkList head,int x)  /輸入x值，計(jì)算并返回多項(xiàng)式的值       for(p=head->next;p;p=p-&

15、gt;next)        t=1; for(i=p->expn;i!=0;)       / i 為指數(shù)的系數(shù) pow(x,i)  if(i<0)t/=x;i+;       /指數(shù)小于0，進(jìn)行除法            elset*=x;i-;   /指數(shù)大于0，進(jìn)行乘法 

16、60;      sum+=p->coef*t;  return sum;/ ValueLinkListLinkList MultiplyLinkList(LinkList pa,LinkList pb)/求解并建立多項(xiàng)式a*b，返回其頭指針     LinkList qa=pa->next;    LinkList qb=pb->next;    hf=(LinkList)malloc(sizeof(struct LNode);/建立頭結(jié)點(diǎn)  &

17、#160; hf->next=NULL;    for(;qa;qa=qa->next)  for(qb=pb->next;qb;qb=qb->next)  pf=(LinkList)malloc(sizeof(struct LNode);            pf->coef=qa->coef*qb->coef;        &#

18、160;   pf->expn=qa->expn+qb->expn;            Insert(pf,hf); /調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng)  return hf;/ MultiplyLinkList3.3主函數(shù)和其他函數(shù)的偽碼算法void main()/主函數(shù)Initiation();  /多項(xiàng)式初始化     PrintCommand();/輸出菜單   

19、60; while(1)   /循環(huán)一直為真 知道選擇j|J即退出命令時(shí)，程序退出        printf("n請(qǐng)選擇操作：");        scanf("%c",&flag);        Interpter(flag);  /具體的操作命令   /mainvoid Initiation() 

20、60;   printf("請(qǐng)輸入a的項(xiàng)數(shù):");    scanf("%d",&m);    pa=CreateLinkList(pa,m);/建立多項(xiàng)式a    printf("請(qǐng)輸入b的項(xiàng)數(shù):");    scanf("%d",&n);    pb=CreateLinkList(pb,n);/建立多項(xiàng)式b printf("多項(xiàng)式已創(chuàng)建n");/ Initi

21、ationvoid PrintCommand()  /輸出菜單顯示鍵入命令的提示信息；Printf（A,B,C,D,E）;/ PrintCommand void Interpter(char flag)   /具體的操作命令  switch(flag)  case 'A': case 'a': PrintLinkList(pa); break;case 'B':case 'b': PrintLinkList(pb); break;case'C': case'

22、c':   AddLinkList(pa,pb); PrintLinkList(pc); break;case'D': case'd': SubtractLinkList(pa,pb);PrintLinkList(pc); break;case'E': case'e': DestroyLinkList(pa); DestroyLinkList(pb);exit(0) ; default:printf("n       您的選擇錯(cuò)誤，請(qǐng)重新選擇!

23、n"); / Interpter函數(shù)說(shuō)明：Initiation(); /多項(xiàng)式初始化PrintCommand(); /輸出菜單Interpter() ; /具體的操作命令PrintLinkList() ; /打印多項(xiàng)式(降序輸出)AddLinkList() ; /兩個(gè)多項(xiàng)式相加SubtractLinkList(); /兩個(gè)多項(xiàng)式相減DestroyLinkList(); /銷(xiāo)毀多項(xiàng)式compare() ; /兩個(gè)節(jié)點(diǎn)比較CreateLinkList(); /創(chuàng)建多項(xiàng)式Insert() ; /將節(jié)點(diǎn)插入已知多項(xiàng)式中四、源程序#include<stdio.h>#include&

24、lt;malloc.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; typedef int ElemType;typedef struct LNode float coef; /系數(shù) ElemType expn; /指數(shù) struct LNode *next; LNode,*LinkList;/*全局節(jié)點(diǎn) 初始化多項(xiàng)式節(jié)點(diǎn)為空*/static LinkLi

25、st pa=NULL;static LinkList pb=NULL;static LinkList pc=NULL;/*將節(jié)點(diǎn)p插入到多項(xiàng)式鏈表h*/void Insert(LinkList p,LinkList h) if(p->coef=0) free(p); /系數(shù)為0的話(huà)釋放結(jié)點(diǎn) else LinkList q1,q2; q1=h; q2=h->next; while(q2&&p->expn<q2->expn) /查找插入位置 q1=q2; q2=q2->next; if(q2&&p->expn=q2->

26、expn)/將指數(shù)相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef)/系數(shù)為0的話(huà)釋放結(jié)點(diǎn) q1->next=q2->next; free(q2); else /指數(shù)為新時(shí)將結(jié)點(diǎn)插入 p->next=q2; q1->next=p; /創(chuàng)建一元多項(xiàng)式 LinkList CreateLinkList(LinkList head,int m) /建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; LinkList p; p=head=(LinkList)malloc(sizeof(struct LNode

27、); head->next=NULL; for(i=0;i<m;i+) p=(LinkList)malloc(sizeof(struct LNode); /建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;void DestroyLinkList(LinkList p) /銷(xiāo)毀多項(xiàng)式p LinkList q1,q2; q1=p-&

28、gt;next; q2=q1->next; while(q1->next) free(q1); q1=q2; q2=q2->next; /輸出構(gòu)造的一元多項(xiàng)式Pvoid PrintLinkList(LinkList P) LinkList q=P->next; int flag=1;/項(xiàng)數(shù)計(jì)數(shù)器 if(!q) /若多項(xiàng)式為空，輸出0 putchar('0'); printf("n"); return; while(q) if(q->coef>0&&flag!=1) putchar('+');

29、 /系數(shù)大于0且不是第一項(xiàng) if(q->coef!=1&&q->coef!=-1) /系數(shù)非1或-1的普通情況 printf("%g",q->coef); if(q->expn=1) putchar('X'); else if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'

30、;); else printf("X%d",q->expn); if(q->coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; printf("n");/ 節(jié)點(diǎn)進(jìn)行比較/ a的指數(shù) >b的指數(shù) return 1/ a的指數(shù)=b的指數(shù) return 0/ a的指數(shù)<b的指數(shù)

31、 return -1Status compare(LinkList a,LinkList b) if(a&&b) if(!b|a->expn>b->expn) return 1; else if(!a|a->expn<b->expn) return -1; else return 0; else if(!a&&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多

32、項(xiàng)式a+b，返回其頭指針 LinkList qa=pa->next; LinkList qb=pb->next; LinkList headc,hc,qc; hc=(LinkList)malloc(sizeof(struct LNode);/建立頭結(jié)點(diǎn) hc->next=NULL; headc=hc; while(qa|qb) qc=(LinkList)malloc(sizeof(struct LNode); switch(compare(qa,qb) case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=q

33、a->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case -1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; if(qc->coef!=0) qc->next=hc->next; hc->next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時(shí)

34、，釋放該結(jié)點(diǎn) return headc;LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多項(xiàng)式a-b，返回其頭指針 LinkList h=pb; LinkList p=pb->next; LinkList pd; while(p) /將pb的系數(shù)取反 p->coef*=-1; p=p->next; pd=AddLinkList(pa,h); for(p=h->next;p;p=p->next) /恢復(fù)pb的系數(shù) p->coef*=-1; return pd;/多項(xiàng)式初始化void Initiation() int m, n ; printf("請(qǐng)輸入a的項(xiàng)數(shù):"); scanf("%d",&m); pa=CreateL