數(shù)據(jù)結(jié)構(gòu)(C語言)一元稀疏多項式計算器_第1頁
數(shù)據(jù)結(jié)構(gòu)(C語言)一元稀疏多項式計算器_第2頁
數(shù)據(jù)結(jié)構(gòu)(C語言)一元稀疏多項式計算器_第3頁
數(shù)據(jù)結(jié)構(gòu)(C語言)一元稀疏多項式計算器_第4頁
數(shù)據(jù)結(jié)構(gòu)(C語言)一元稀疏多項式計算器_第5頁
已閱讀5頁,還剩7頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論