西安石油大學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告--設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器和集合的并,交和差運(yùn)算

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目一：設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器 題目二：集合的并，交和差運(yùn)算班 級(jí)： 計(jì)1101姓 名： 張文江學(xué) 期：2012-2013學(xué)年第二學(xué)期 上機(jī)實(shí)驗(yàn)報(bào)告（一） 一、 題目：設(shè)計(jì)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器二、問(wèn)題描述：（1）定義兩個(gè)單鏈表用于存儲(chǔ)兩個(gè)多項(xiàng)式，存儲(chǔ)好在輸出時(shí)按指數(shù)降序輸出。（2）按指數(shù)降序排列時(shí)要注意指數(shù)的比較以及指數(shù)相同與不同時(shí)的計(jì)算方法。（3）設(shè)計(jì)出其運(yùn)算的加、減函數(shù)。（4）再設(shè)計(jì)一個(gè)釋放空間的函數(shù)用于退出系統(tǒng)操作。（5）設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)現(xiàn)對(duì)基于順序隊(duì)列結(jié)構(gòu)的一元多項(xiàng)式算法的測(cè)試。（6）為了界面顯示友好期間可以設(shè)計(jì)一下輸出后的界面格式。三、基本要求

2、：（1）輸入并建立多項(xiàng)式，輸出多項(xiàng)式，序列按指數(shù)降序排列；（2）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式；（3）多項(xiàng)式a和b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式；（4）用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。四、測(cè)試數(shù)據(jù)：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)五、算法思想： 利用單鏈表來(lái)存儲(chǔ)多項(xiàng)式，因此這里需要?jiǎng)?chuàng)建兩個(gè)單鏈表分別用于存儲(chǔ)多項(xiàng)式a和b，然后逐項(xiàng)在鏈表中按指數(shù)降序排列插入；利用數(shù)學(xué)中的加法方法，比較兩個(gè)

3、多項(xiàng)式，利用指數(shù)進(jìn)行比較，進(jìn)行減法計(jì)算方法時(shí)利用加法的逆運(yùn)算實(shí)現(xiàn)，最后將輸入的多項(xiàng)式按不同的要求提示進(jìn)行函數(shù)調(diào)用實(shí)現(xiàn)。六、模塊劃分：頭文件為：# include<stdio.h># include<stdlib.h>/結(jié)點(diǎn)結(jié)構(gòu)體typedef struct PolyNode float coef;/系數(shù)域 int exp;/指數(shù)域 struct PolyNode *next; /指針域*Poly,PolyNode;/1、按指數(shù)降序插入多項(xiàng)式void Insert(Poly p,Poly h)/2、創(chuàng)建多項(xiàng)式(帶有頭結(jié)點(diǎn)且有m項(xiàng))Poly Create(Poly head

4、, int m)/3、對(duì)兩個(gè)多項(xiàng)式進(jìn)行比較判別/4、實(shí)現(xiàn)多項(xiàng)式相加/5、實(shí)現(xiàn)多項(xiàng)式相減（思想：兩數(shù)相減=兩個(gè)正數(shù)的相反數(shù)相減）/6、輸出多項(xiàng)式void Print(Poly P)/7、銷毀多項(xiàng)式(使用完后用于退出，釋放空間)測(cè)試主int main() int m,n,flag=0;Poly pa=0,pb=0,pc,pd; /輸出菜單printf("*n");printf(" 1.輸入多項(xiàng)式 2.輸出多項(xiàng)式a和b 3.建立多項(xiàng)式a+b 4.建立多項(xiàng)式a-b 5.退出程序 n");printf("*n");for(;flag=0)pri

5、ntf("執(zhí)行操作為:") ;scanf("%d",&flag);if(flag=1) /定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請(qǐng)輸入a的項(xiàng)數(shù):") ;scanf("%d",&m);pa=CreateList(pa,m); /建立多項(xiàng)式aprintf("請(qǐng)輸入b的項(xiàng)數(shù):" );scanf("%d",&n);pb=CreateList(pb,n); /建立多項(xiàng)式b if(flag=2)printf("多項(xiàng)式a為:&q

6、uot;);OutputList(pa);printf("多項(xiàng)式b為:");OutputList(pb);continue;if(flag=3)pc=AddPoly(pa,pb);printf("多項(xiàng)式a+b為：");OutputList(pc);DestroyList(pc);continue;if(flag=4)pd=SubtractPoly(pa,pb);printf("多項(xiàng)式a-b為：");OutputList(pd);DestroyList(pd);continue;if(flag=5) break;if(flag<1

7、|flag>5) printf("輸入錯(cuò)誤!請(qǐng)重新選擇!n");continue;DestroyList(pa);DestroyList(pb);return 0; 函數(shù)：7、 源程序：int main() int m,n,flag=0;Poly pa=0,pb=0,pc,pd; /輸出菜單printf("*n");printf(" 1.輸入多項(xiàng)式 2.輸出多項(xiàng)式a和b 3.建立多項(xiàng)式a+b 4.建立多項(xiàng)式a-b 5.退出程序 n");printf("*n");for(;flag=0)printf("

8、;執(zhí)行操作為:") ;scanf("%d",&flag);if(flag=1) /定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請(qǐng)輸入a的項(xiàng)數(shù):") ;scanf("%d",&m);pa=CreateList(pa,m); /建立多項(xiàng)式aprintf("請(qǐng)輸入b的項(xiàng)數(shù):" );scanf("%d",&n);pb=CreateList(pb,n); /建立多項(xiàng)式b if(flag=2)printf("多項(xiàng)式a為:");Out

9、putList(pa);printf("多項(xiàng)式b為:");OutputList(pb);continue;if(flag=3)pc=AddPoly(pa,pb);printf("多項(xiàng)式a+b為：");OutputList(pc);DestroyList(pc);continue;if(flag=4)pd=SubtractPoly(pa,pb);printf("多項(xiàng)式a-b為：");OutputList(pd);DestroyList(pd);continue;if(flag=5) break;if(flag<1|flag>

10、5) printf("輸入錯(cuò)誤!請(qǐng)重新選擇!n");continue;DestroyList(pa);DestroyList(pb);return 0; 八、測(cè)試情況：（1）（2）測(cè)試結(jié)果分析：程序設(shè)計(jì)結(jié)果和人工模擬分析過(guò)程完全相同，說(shuō)明程序正確。（3）思想感悟：經(jīng)過(guò)這次的課程設(shè)計(jì)，我學(xué)到了好多，也越發(fā)的感覺(jué)到自己不知道的東西很多，一開(kāi)始，對(duì)多項(xiàng)式的創(chuàng)建一竅不通，感覺(jué)很難，無(wú)法入手，后來(lái)，經(jīng)過(guò)上網(wǎng)查詢，與隊(duì)友的討論，逐漸有了頭緒，慢慢寫(xiě)出了程序，第一次運(yùn)行時(shí)，錯(cuò)誤很多，改了好多次，終于成功了，讓我感覺(jué)到了團(tuán)隊(duì)的力量！ 上級(jí)實(shí)驗(yàn)報(bào)告（二）一、題目：集合的并、交和差運(yùn)算二、問(wèn)題

11、描述：（1）創(chuàng)建單鏈表用于存儲(chǔ)集合，存儲(chǔ)好集合在輸出時(shí)按字母排好順序輸出。（2）設(shè)計(jì)出其運(yùn)算的合并、求交、求差函數(shù)。（3）再設(shè)計(jì)一個(gè)釋放空間的函數(shù)用于退出系統(tǒng)操作。（4）設(shè)計(jì)一個(gè)測(cè)試主函數(shù)，實(shí)現(xiàn)對(duì)基于順序隊(duì)列結(jié)構(gòu)的集合運(yùn)算的測(cè)試。（5）為了界面顯示友好期間可以設(shè)計(jì)一下輸出后的界面格式。三、基本功能編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。四、基本要求(1) 集合的元素限定為小寫(xiě)字母字符a.z；(2) 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行。五、測(cè)試數(shù)據(jù)(1) Set1 = ”magazine”, Set2 = ”paper”,Set1Set2 = ”aegimnprz”, Set1Set2

12、= ”ae”, Set1-Set2 = ”gimnz”；(2) Set1 = ”012oper4a6tion89”, Set2 = ”error data”,Set1Set2 = ”adeinoprt”, Set1Set2 = ”aeort”, Set1-Set2 = ”inp”。 六、算法思想： 創(chuàng)建一個(gè)單鏈表用于存儲(chǔ)一個(gè)集合，限定集合元素字母為“a”“z”，計(jì)算出集合的長(zhǎng)度以用于對(duì)集合中的元素排序，排序時(shí)從第一個(gè)元素開(kāi)始逐個(gè)向后比較。計(jì)算時(shí)，合并思想為：將兩個(gè)集合進(jìn)行比較，有相同元素時(shí)只輸入一個(gè)，元素不同時(shí)均輸入；求交思想：兩個(gè)集合比較將相同的元素輸出；求差思想：用第一個(gè)集合中的元素和第二

13、個(gè)集合比較，如果相同就刪除，最后輸出剩余的元素。利用銷毀和清空方法釋放占據(jù)的空間，最后在主函數(shù)中將集合按不同的要求提示進(jìn)行函數(shù)調(diào)用實(shí)現(xiàn)。七、模塊劃分：頭文件：#include<stdio.h>#include<stdlib.h>#define ElemType char /宏定義一個(gè)字符型的元素類型，以下使用不用定義/定義集合結(jié)構(gòu)體typedef struct ElemNode ElemType elem; /集合元素域 struct ElemNode *next;*Set,ElemNode;/1、計(jì)算一個(gè)集合的長(zhǎng)度用于對(duì)集合排序int Length(Set src)/

14、2、創(chuàng)建一個(gè)從a-z字母集合void Create(Set dest)/3、清空一個(gè)集合void Empty(Set dest)/4、銷毀集合void Destroy(Set dest)/5、對(duì)一個(gè)字母集合進(jìn)行從小到大的排序void Sort(Set dest)/6、打印集合的所有元素void Display(Set src)/7、判斷元素是否存在于集合中int ExistElem(Set dest, ElemType e)/8、刪除集合中的一個(gè)元素一次void DelElem(Set dest, ElemType e)/9、在鏈表尾部追加一個(gè)元素void AddElem(Set dest,

15、ElemType e)/10、集合合并運(yùn)算void Add(Set dest, Set src1, Set src2)/11、集合求交集運(yùn)算void Mul(Set dest, Set src1, Set src2)/12、集合求差運(yùn)算void Subtract(Set dest, Set src1, Set src2)/測(cè)試主函數(shù)int main()八、源程序：#include<stdio.h>#include<stdlib.h>#define ElemType char /宏定義一個(gè)字符型的元素類型，以下使用不用定義/定義集合結(jié)構(gòu)體typedef struct El

16、emNode ElemType elem; /集合元素域 struct ElemNode *next;*Set,ElemNode;/1、計(jì)算一個(gè)集合的長(zhǎng)度用于對(duì)集合排序int Length(Set src) int i=0; while(src->next != NULL) /集合元素不為空時(shí)i+1 i+; src=src->next; /依次向后 return i;/2、創(chuàng)建一個(gè)從a-z字母集合void Create(Set dest) ElemType ch; Set p = dest,n;for(;) ch = getchar(); /輸入字符 if(ch = 'n&

17、#39;) /遇到換行（一個(gè)集合輸入完成）就返回終止 break; if(ch<97 | ch>122) /輸入的字符不屬于a-z 就終止運(yùn)行,用于實(shí)現(xiàn)限定元素功能 continue; n = (Set)malloc(sizeof(ElemNode); /為集合n分配存儲(chǔ)空間 p->next = n; n->elem = ch; /將字符插入集合 n->next = NULL; p = n; return ;/3、清空一個(gè)集合void Empty(Set dest) Set p,n; while(dest->next != NULL) p = dest; n

18、 = p->next; for(;n->next!=NULL;) p = n; n = n->next; free(n); p->next = NULL; /4、銷毀集合void Destroy(Set dest) Empty(dest); free(dest);/5、對(duì)一個(gè)字母集合進(jìn)行從小到大的排序void Sort(Set dest) int i,j,l,flag; Set p,q,n; l=Length(dest); if(l<2) return; flag=1; for(i=l-1;i>0 && flag=1;i-) flag = 0

19、; p = dest; q = p->next; n = q->next; for(j=0;j<i;j+) if(q->elem>n->elem) flag = 1; p->next = n; q->next = n->next; n->next = q; q = p->next; n = q->next; p = q; q = n; n = n->next; /6、打印集合的所有元素void Display(Set src) Set p; if(src->next = NULL) printf("

20、"); return ; p = src; p = p->next; putchar(p->elem); while(p->next != NULL);/7、判斷元素是否存在于集合中int ExistElem(Set dest, ElemType e) Set p=dest; if(Length(p)=0) return 0; else p=p->next; while(p->elem != e) if(p->next=NULL) return 0; p=p->next; return 1; /8、刪除集合中的一個(gè)元素一次void DelEl

21、em(Set dest, ElemType e) Set p=dest,q; if(Length(p)=0) return ; q=p->next; if(Length(p)=1) p->next=NULL; free(q); while(q->elem!=e) p=p->next; q=q->next; if(q->next=NULL) p->next=NULL; free(q); Else p->next=q->next; /9、在鏈表尾部追加一個(gè)元素void AddElem(Set dest, ElemType e) Set p=de

22、st, n; while(p->next!=NULL) p=p->next; n=(Set)malloc(sizeof(ElemNode); p->next=n; n->elem=e; n->next=NULL; /10、集合合并運(yùn)算void Add(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i=0,j=0,len1 = Length(src1),len2=Length(src2); src1=src1->next; src2=src2->next; while(i<len

23、1 && j<len2) if(src1->elem <= src2->elem) i+; if(!ExistElem(dest, src1->elem) AddElem(dest, src1->elem); src1 = src1->next; else src1 = src1->next; else j+; if(!ExistElem(dest, src2->elem) AddElem(dest, src2->elem); src2 = src2->next; else src2 = src2->nex

24、t; while(i<len1) i+; if(!ExistElem(dest, src1->elem) AddElem(dest, src1->elem); src1 = src1->next; while(j<len2) j+; if(!ExistElem(dest, src2->elem) AddElem(dest, src2->elem); src2 = src2->next; /11、集合求交集運(yùn)算void Mul(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i=0

25、,j=0; int len1=Length(src1),len2=Length(src2); src1=src1->next;src2=src2->next; while(i<len1&&j<len2) if(src1->elem<src2->elem) i+;src1=src1->next; else if(src1->elem>src2->elem) j+;src2=src2->next; else i+;j+; if(!ExistElem(dest, src1->elem) AddElem(de

26、st, src1->elem); src1=src1->next; src2=src2->next; /12、集合求差運(yùn)算void Subtract(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i = 0; int len = Length(src1); src1 = src1->next; while(i<len) i+; if(!ExistElem(src2, src1->elem) if(!ExistElem(dest, src1->elem) AddElem(dest, s

27、rc1->elem); src1 = src1->next; else src1 = src1->next; /測(cè)試主函數(shù)int main() int a,f; Set dest=(Set)malloc(sizeof(ElemNode); Set src1=(Set)malloc(sizeof(ElemNode); Set src2=(Set)malloc(sizeof(ElemNode); dest->next=NULL; printf("*n"); printf("* t歡迎使用集合運(yùn)算系統(tǒng) *n"); printf("* 請(qǐng)輸入兩個(gè)集合：n"); Create(src1); Create(src2); printf("* Set1 = "); Display(src1); printf("n"); printf("* Set2 = "); Display(src2); printf("n"); printf("*n"); printf("* 集合運(yùn)算的操作菜單 *n&qu