數(shù)據(jù)結(jié)構課程設計報告-一元多項式加減運算

1、山東理工大學計算機學院課 程 設 計（數(shù)據(jù)結(jié)構）班 級計科1102姓 名張汝全學 號 指導教師肖愛梅2013年 1 月 7 日課程設計任務書及成績評定課題名稱動態(tài)鏈表結(jié)構下的一元多項式的加法、減法和乘法的實現(xiàn)。 、題目的目的和要求： 1.鞏固和加深對數(shù)據(jù)結(jié)構的理解，通過上機實驗、調(diào)試程序，加深對課本知識的理解，最終使學生能夠熟練應用數(shù)據(jù)結(jié)構的知識寫程序。（1）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結(jié)構的基本操作。（2）能針對給定題目，選擇相應的數(shù)據(jù)結(jié)構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。2.設計題目要求：1) 首先判定一元多項式是否稀疏2) 分別采用順序和鏈式結(jié)構實現(xiàn)

2、；3) 結(jié)果在M(x)中無重復階項和無零系數(shù)項；4) 要求結(jié)果以升冪排列輸出、設計進度及完成情況日 期內(nèi) 容1.7-1.9選取參考書，查閱有關文獻資料，完成資料搜集和系統(tǒng)分析工作。1.10-1.12創(chuàng)建相關數(shù)據(jù)結(jié)構,錄入源程序。1.13-1.15調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設計報告。1.16上交課程設計報告打印版并進行課程設計答辯，要求每個同學針對自己的設計回答指導教師3-4個問題。1.17考核結(jié)束后將課程設計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。、主要參考文獻及資料1 嚴蔚敏 數(shù)據(jù)結(jié)構（C語言版）清華大學出版社 19992 嚴蔚敏 數(shù)據(jù)結(jié)構題集（C語言版）清華大學出版社 19

3、993 譚浩強 C語言程序設計 清華大學出版社4 與所用編程環(huán)境相配套的C語言或C+相關的資料、成績評定：設計成績： （教師填寫）指導老師： （簽字）二 年 月 日目 錄第一章 概述1第二章 系統(tǒng)分析2第三章 概要設計3第四章 詳細設計4第五章 運行與測試18第六章 總結(jié)與心得20參考文獻21第一章 概述課程設計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎，可以涉及和課程相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。數(shù)據(jù)結(jié)構是一門重要的專業(yè)基礎課，是計算機理論和應用的核心基礎課程。數(shù)據(jù)結(jié)構課程設計，要求學生在數(shù)據(jù)

4、結(jié)構的邏輯特性和物理表示、數(shù)據(jù)結(jié)構的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。在這次的課程設計中我選擇的題目是動態(tài)鏈表結(jié)構下的一元多項式的加法、減法和乘法的實現(xiàn)。一元多項式計算是用C語言設計一個一元多項式簡單計算器。它能夠?qū)崿F(xiàn)按指數(shù)升序排列建立并輸出多項式，并且能夠完成兩個多項式的相加、相減與相乘的運算和將其結(jié)果輸入的功能。通過設計一元多項式，初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能提高，綜合運用所學的理論知識和方法獨立分析和解決問題的能力；加深對常用數(shù)據(jù)結(jié)構

5、的理解，強化邏輯思維能力和動手能力，鞏固良好的編程習慣，掌握工程軟件設計的基本方法，為后續(xù)課程的學習打下堅實基礎。第二章 系統(tǒng)分析1 動態(tài)鏈表結(jié)構下的一元多項式的加法、減法、乘法的實現(xiàn)。可以分為幾個模塊：輸入模塊、輸出模塊（升冪）、數(shù)據(jù)處理模塊（多項式的加減乘）、主程序模塊。2 在程序執(zhí)行過程中加入漢字提示符，讓使用者清楚明白的操作該程序。運行程序時看起來簡潔有序，操作簡單明了。3 程序執(zhí)行時的命令：創(chuàng)建兩個一元多項式輸入第一個一元多項式的項數(shù)依次輸入一元多項式的系數(shù)和指數(shù)以相同方式輸入第二個一元多項式數(shù)據(jù)處理輸出結(jié)果。4 測試數(shù)據(jù)。輸入的一元多項式系數(shù)指數(shù)分別為7 0,3 1,9 8,5 1

6、7和8 1,22 7,-9 8。加法結(jié)果為：7+11x+22x(7)+5x(17)減法結(jié)果為：7-5x-22x(7)+18x(8)+5x(17)5 乘法結(jié)果為：56x+24x(2)+154x(7)+3x(8)+45x(9)+198x(15)-81x(16)+40x(18)+110x(24)-45x(25)第三章 概要設計1. 數(shù)據(jù)結(jié)構的設計為了節(jié)省存儲空間，只存儲多項式中系數(shù)非零的項，本程序使用鏈式存儲結(jié)構。2. 算法的設計本設計從總體上劃分為3個模塊。a) 主函數(shù)模塊。程序的入口，主要實現(xiàn)各個函數(shù)的調(diào)用。b) 頭文件模塊。定義類和結(jié)構體。c) 函數(shù)模塊。數(shù)據(jù)處理和實現(xiàn)每個功能。3. 抽象數(shù)據(jù)

7、類型ADT list數(shù)據(jù)對象：D=ai | ai ElenSet, i=1,2,n,n0數(shù)據(jù)關系：R1= | ai-1,aiD,i=2,n基本操作：InitLink(&head, len)初始條件：鏈表為空。操作結(jié)果：創(chuàng)建鏈表。Sparsity(&head, len)初始條件：鏈表已存在。操作結(jié)果：判斷是否稀疏。Display(head)初始條件：鏈表已存在。操作結(jié)果：輸出多項式。 Merge(&head)初始條件：鏈表已存在。操作結(jié)果：合并指數(shù)相同的項。 SelectSort(&head)初始條件：鏈表已存在。操作結(jié)果：選擇排序。 Negative(&head)初始條件：鏈表已存在。操作結(jié)果

8、：取負。 DelZero(&head)初始條件：鏈表已存在。操作結(jié)果：刪除系數(shù)為0的項。 operator + (&head，&b);初始條件：鏈表已存在。操作結(jié)果：重載+。 operator * (&head，&b);初始條件：鏈表已存在。操作結(jié)果：重載*。第四章 詳細設計1. 類定義。polynomial.h#ifndef POLYNOMIAL_H_INCLUDED#define POLYNOMIAL_H_INCLUDEDtemplate struct Node T coef; /定義系數(shù) T expn; /定義指數(shù) Node *next; /定義結(jié)構體template /模板類class

9、 LinkList private: Node *head; /定義頭結(jié)點 public: LinkList(); /初始化鏈表 void InitLink(int len); /建立鏈表 void Sparsity(int len); /是否稀疏 void Display(); /顯示 void Merge(); /合并指數(shù)相同的項 void SelectSort(); /選擇排序 void Negative(); /取負 void DelZero(); /刪除系數(shù)為0的項 LinkList operator + (LinkList &b); /重載+ LinkList operator *

10、 (LinkList &b); /重載*;#endif / POLYNOMIAL_H_INCLUDED2. 成員函數(shù)。polynomial.cpp#include#includepolynomial.husing namespace std;template LinkList:LinkList() head=new Node; head-next=NULL;/初始化template void LinkList:InitLink(int len) Node *p, *q; q=head; cout 系數(shù) 指數(shù)： endl; while(len-) p=new Node; cin p-coef p

11、-expn; p-next=NULL; q-next=p; q=p; /建立多項式template void LinkList:Display() DelZero(); Node *q; q=head-next; if (!q) /空鏈表輸出0 cout 0 coef) if (q-coef = 1) if (q-expn = 0) cout coef; else if(q-expn = 1) cout x; else cout x ( expn coef = -1) if (q-expn = 0) cout coef; else if(q-expn = 1) cout -x; else co

12、ut -x ( expn expn = 0) cout coef; else if(q-expn = 1) cout coef x; else cout coef x ( expn next; while(q) if (q-coef) if (q-coef 0) if (q-coef = 1) if (q-expn = 0) cout expn = 1) cout +x; else cout +x ( expn expn = 0) cout + coef; else if(q-expn = 1) cout + coef x; else cout + coef x ( expn coef = -

13、1) if (q-expn = 0) cout coef; else if (q-expn = 1) cout -x; else cout -x ( expn expn = 0) cout coef; else if(q-expn = 1) cout coef x; else cout coef x ( expn next; cout endl;/輸出多項式template void LinkList:Sparsity(int len) if (head-next = NULL) cout 0 endl; cout 不稀疏！ endl; return ; Node *p, *q; q=head

14、; p=head-next; while(q-next) q=q-next; double x=1.0*len/(q-expn-p-expn); Display(); if (x = 0.05) cout 稀疏！ endl; else cout 不稀疏！ endl;/判斷是否稀疏template void LinkList:Merge() Node *p, *q, *t; for (q=head-next; q; q=q-next) for (p=q-next; p & p-expn = q-expn; ) q-coef+=p-coef; q-next=p-next; t=p; p=p-nex

15、t; free(t); /合并指數(shù)相同的項template void LinkList:SelectSort() Node *p, *q; for (q=head-next; q; q=q-next) for (p=q-next; p; p=p-next) if (q-expn p-expn) swap(q-coef,p-coef); swap(q-expn,p-expn); Merge();/選擇排序 升冪template void LinkList:Negative() Node *p; p=head-next; while(p) p-coef=0-p-coef; p=p-next; /取

16、負template void LinkList:DelZero() Node *p, *q, *t; p=head-next; q=head; while(p) if (p-coef = 0) q-next=p-next; t=p; p=p-next; free(t); else q=p; p=p-next; /刪除系數(shù)為0的項template LinkList LinkList:operator+ (LinkList &b) LinkList m; Node *q, *p; Node *pa, *pb; pa=head-next; pb=b.head-next; q=m.head; whil

17、e(pa & pb) T x=pa-expn - pb-expn; if (x 0) p=new Node; p-coef=pa-coef; p-expn=pa-expn; p-next=NULL; q-next=p; q=p; pa=pa-next; else if(x 0) p=new Node; p-coef=pb-coef; p-expn=pb-expn; p-next=NULL; q-next=p; q=p; pb=pb-next; else T coef=pa-coef+pb-coef; if (coef) p=new Node; p-coef=coef; p-expn=pa-ex

18、pn; p-next=NULL; q-next=p; q=p; pa=pa-next; pb=pb-next; else pa=pa-next; pb=pb-next; while(pa) p=new Node; p-coef=pa-coef; p-expn=pa-expn; p-next=NULL; q-next=p; q=p; pa=pa-next; while(pb) p=new Node; p-coef=pb-coef; p-expn=pb-expn; p-next=NULL; q-next=p; q=p; pb=pb-next; return m;/重載+template LinkL

19、ist LinkList:operator* (LinkList &b) LinkList m; Node *q, *p; Node *pa, *pb; q=m.head; for (pa=head-next; pa; pa=pa-next) for (pb=b.head-next; pb; pb=pb-next) p=new Node; p-coef=pa-coef*pb-coef; p-expn=pa-expn+pb-expn; p-next=NULL; q-next=p; q=p; return m;/重載*void menu() for (int i=0; i80; i+) cout

20、*; cout endl; cout 1.建立多項式tt2.輸出多項式tt3.多項式相加 endl;cout 4.多項式相減tt5.多項式相乘tt0.退出系統(tǒng) endl; for (i=0; i80; i+) cout *; cout endl; cout 請選擇：;3. 主函數(shù)。main.c#include #include #include #include #include #include polynomial.cppusing namespace std;int main() /freopen(data1.in, r, stdin); /輸入重定向 /freopen(data1.ou

21、t, w, stdout); /輸出重定向 LinkList a, b, m1, m2, m3; int n, flag; int ALen, BLen; menu(); while(cin n, n) system(cls); switch(n) case 0: cout 歡迎下次使用！ endl; exit(0); case 1: flag=0; cout ALen; a.InitLink(ALen); /建立一元多項式 a.SelectSort(); /升冪排序 cout BLen; b.InitLink(BLen); /建立一元多項式 b.SelectSort(); /升序排序 break; case 2: cout a=; a.Sparsity(ALen); /判斷是否稀疏 cout b=; b.Sparsity(BLen); /判斷是否稀疏 break; case 3: m1=a+b; m1.SelectSort(); cout a+b=; m1.Display(); /輸出a+b break; case 4: if (flag = 0) b.Negative(); /對b取負 flag=