西安石油大學數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序設計報告 設計一個一元稀疏多項式簡單計算器和集合的并

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

2、、基本要求： （1）輸入并建立多項式，輸出多項式，序列按指數(shù)降序排列； （2）多項式a和b相加，建立多項式a+b，輸出相加的多項式； （3）多項式a和b相減，建立多項式a-b，輸出相減的多項式； （4）用帶頭結(jié)點的單鏈表存儲多項式。 四、測試數(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) 五、算法思想： 利用單鏈表來存儲多項式，因此這里需要創(chuàng)建兩個單鏈表分別用于存儲多項式a和b，然后逐項在鏈表中按指數(shù)降序排列插入；

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

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

5、ag); if(flag=1) /定義各式的頭指針，pa與pb在使用前付初值NULL printf(請輸入a的項數(shù):) ; scanf(%d,&m); pa=CreateList(pa,m); /建立多項式a printf(請輸入b的項數(shù): ); scanf(%d,&n); pb=CreateList(pb,n); /建立多項式b if(flag=2) printf(多項式a為:); OutputList(pa); printf(多項式b為:); OutputList(pb); continue; if(flag=3) pc=AddPoly(pa,pb); printf(多項式a+b為：);

6、OutputList(pc); DestroyList(pc); continue; if(flag=4) pd=SubtractPoly(pa,pb); printf(多項式a-b為：); OutputList(pd); DestroyList(pd); continue; if(flag=5) break; if(flag5) printf(輸入錯誤!請重新選擇!n); continue; DestroyList(pa); DestroyList(pb); return 0; 函數(shù)： 七、源程序： int main() int m,n,flag=0; Poly pa=0,pb=0,pc,p

7、d; /輸出菜單 printf(*n); printf( 1.輸入多項式 2.輸出多項式a和b 3.建立多項式a+b 4.建立多項式a-b 5.退出程序 n); printf(*n); for(;flag=0) printf(執(zhí)行操作為:) ; scanf(%d,&flag); if(flag=1) /定義各式的頭指針，pa與pb在使用前付初值NULL printf(請輸入a的項數(shù):) ; scanf(%d,&m); pa=CreateList(pa,m); /建立多項式a printf(請輸入b的項數(shù): ); scanf(%d,&n); pb=CreateList(pb,n); /建立多項式

8、b if(flag=2) printf(多項式a為:); OutputList(pa); printf(多項式b為:); OutputList(pb); continue; if(flag=3) pc=AddPoly(pa,pb); printf(多項式a+b為：); OutputList(pc); DestroyList(pc); continue; if(flag=4) pd=SubtractPoly(pa,pb); printf(多項式a-b為：); OutputList(pd); DestroyList(pd); continue; if(flag=5) break; if(flag5

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

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

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

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

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

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

15、mType elem; /集合元素域 struct ElemNode *next; *Set,ElemNode; /1、計算一個集合的長度用于對集合排序 int Length(Set src) int i=0; while(src-next != NULL) /集合元素不為空時i+1 i+; src=src-next; /依次向后 return i; /2、創(chuàng)建一個從a-z字母集合 void Create(Set dest) ElemType ch; Set p = dest,n; for(;) ch = getchar(); /輸入字符 if(ch = n) /遇到換行（一個集合輸入完成）就

16、返回終止 break; if(ch122) /輸入的字符不屬于a-z 就終止運行,用于實現(xiàn)限定元素功能 continue; n = (Set)malloc(sizeof(ElemNode); /為集合n分配存儲空間 p-next = n; n-elem = ch; /將字符插入集合 n-next = NULL; p = n; return ; /3、清空一個集合 void Empty(Set dest) Set p,n; while(dest-next != NULL) p = dest; n = p-next; for(;n-next!=NULL;) p = n; n = n-next; f

17、ree(n); p-next = NULL; /4、銷毀集合 void Destroy(Set dest) Empty(dest); free(dest); /5、對一個字母集合進行從小到大的排序 void Sort(Set dest) int i,j,l,flag; Set p,q,n; l=Length(dest); if(l0 & flag=1;i-) flag = 0; p = dest; q = p-next; n = q-next; for(j=0;jelemn-elem) flag = 1; p-next = n; q-next = n-next; n-next = q; q =

18、 p-next; n = q-next; p = q; q = n; n = n-next; /6、打印集合的所有元素 void Display(Set src) Set p; if(src-next = NULL) printf( ); 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

19、(p-elem != e) if(p-next=NULL) return 0; p=p-next; return 1; /8、刪除集合中的一個元素一次 void DelElem(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、在鏈表尾

20、部追加一個元素 void AddElem(Set dest, ElemType e) Set p=dest, n; while(p-next!=NULL) p=p-next; n=(Set)malloc(sizeof(ElemNode); p-next=n; n-elem=e; n-next=NULL; /10、集合合并運算 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=s

21、rc2-next; while(ilen1 & jelem 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-next; while(ielem) AddElem(dest, src1-elem); src1 = src1-next

22、; while(jelem) AddElem(dest, src2-elem); src2 = src2-next; /11、集合求交集運算 void Mul(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i=0,j=0; int len1=Length(src1),len2=Length(src2); src1=src1-next;src2=src2-next; while(ilen1&jelemelem) i+;src1=src1-next; else if(src1-elemsrc2-elem) j+;src2=src

23、2-next; else i+;j+; if(!ExistElem(dest, src1-elem) AddElem(dest, src1-elem); src1=src1-next; src2=src2-next; /12、集合求差運算 void Subtract(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i = 0; int len = Length(src1); src1 = src1-next; while(ielem) if(!ExistElem(dest, src1-elem) AddElem(dest, s

24、rc1-elem); src1 = src1-next; else src1 = src1-next; /測試主函數(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歡迎使用集合運算系統(tǒng) *n); printf(* 請輸入兩個集合：n); Create(src1); Create(src2); printf(* Set1 = ); Display(src1); printf(n); printf(* S