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

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

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

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

4、二、概要設(shè)計為實現(xiàn)上述程序的功能，應(yīng)以帶頭結(jié)點的單鏈表表示多項式。為此，需要一個抽象數(shù)據(jù)類型：單鏈表。2.1單鏈表的抽象數(shù)據(jù)類型定義ADT LinkList數(shù)據(jù)對象：D=ai|aiTermSet,i=1,2,m,m0 TermSet中的每個元素包含一個表示系數(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項的系數(shù)和指數(shù)，建立一元多項式p。DestoryLinkList(&p)初始條件：一元多項式p已存在。操作結(jié)果：銷毀一元

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

6、處理命令；（循環(huán)一直為真直至接受退出命令）；2）單鏈表單元模塊實現(xiàn)單鏈表的抽象數(shù)據(jù)類型；3）結(jié)點結(jié)構(gòu)單元模塊定義單鏈表的結(jié)點結(jié)構(gòu)。三、詳細設(shè)計3.1元素類型、結(jié)點類型和指針類型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指向下一個多項式的頭結(jié)點head、后繼為空的結(jié)點，并返回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é)點free(q1);        q1=q2;    

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

10、inkList a,LinkList b) /節(jié)點進行比較: a的指數(shù) >b的指數(shù)   return 1; a的指數(shù)=b的指數(shù)   return 0;a的指數(shù)<b的指數(shù)    return -1.LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多項式a+b，返回其頭指針LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多項式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é)點以接收數(shù)據(jù)        printf("請輸入第%d項的系數(shù)與指數(shù):&

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

13、60;     /調(diào)用Insert函數(shù)插入結(jié)點     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多項式已空，但b多項式非空    else return 1;/b多項式已空，但a多項式非空/ comparefloat ValueLinkList(LinkList head,int x)  /輸入x值，計算并返回多項式的值       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，進行除法            elset*=x;i-;   /指數(shù)大于0，進行乘法 

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

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ù)相同的項  return hf;/ MultiplyLinkList3.3主函數(shù)和其他函數(shù)的偽碼算法void main()/主函數(shù)Initiation();  /多項式初始化     PrintCommand();/輸出菜單   

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

20、60;   printf("請輸入a的項數(shù):");    scanf("%d",&m);    pa=CreateLinkList(pa,m);/建立多項式a    printf("請輸入b的項數(shù):");    scanf("%d",&n);    pb=CreateLinkList(pb,n);/建立多項式b printf("多項式已創(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       您的選擇錯誤，請重新選擇!

23、n"); / Interpter函數(shù)說明：Initiation(); /多項式初始化PrintCommand(); /輸出菜單Interpter() ; /具體的操作命令PrintLinkList() ; /打印多項式(降序輸出)AddLinkList() ; /兩個多項式相加SubtractLinkList(); /兩個多項式相減DestroyLinkList(); /銷毀多項式compare() ; /兩個節(jié)點比較CreateLinkList(); /創(chuàng)建多項式Insert() ; /將節(jié)點插入已知多項式中四、源程序#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é)點 初始化多項式節(jié)點為空*/static LinkLi

25、st pa=NULL;static LinkList pb=NULL;static LinkList pc=NULL;/*將節(jié)點p插入到多項式鏈表h*/void Insert(LinkList p,LinkList h) if(p->coef=0) free(p); /系數(shù)為0的話釋放結(jié)點 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的話釋放結(jié)點 q1->next=q2->next; free(q2); else /指數(shù)為新時將結(jié)點插入 p->next=q2; q1->next=p; /創(chuàng)建一元多項式 LinkList CreateLinkList(LinkList head,int m) /建立一個頭指針為head、項數(shù)為m的一元多項式 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é)點以接收數(shù)據(jù) printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;void DestroyLinkList(LinkList p) /銷毀多項式p LinkList q1,q2; q1=p-&

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

29、 /系數(shù)大于0且不是第一項 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é)點進行比較/ 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多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空LinkList AddLinkList(LinkList pa,LinkList pb)/求解并建立多

32、項式a+b，返回其頭指針 LinkList qa=pa->next; LinkList qb=pb->next; LinkList headc,hc,qc; hc=(LinkList)malloc(sizeof(struct LNode);/建立頭結(jié)點 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);/當相加系數(shù)為0時

34、，釋放該結(jié)點 return headc;LinkList SubtractLinkList(LinkList pa,LinkList pb)/求解并建立多項式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;/多項式初始化void Initiation() int m, n ; printf("請輸入a的項數(shù):"); scanf("%d",&m); pa=CreateL