數(shù)據(jù)結(jié)構(gòu)上機報告-實現(xiàn)一元多項式抽象數(shù)據(jù)類型

1、數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告數(shù)據(jù)結(jié)構(gòu)上機實習(xí)報告實驗題目： 實現(xiàn)一元多項式抽象數(shù)據(jù)類型班級： 姓名： 學(xué)號： 指導(dǎo)老師： 完成日期： 1、 需求分析1.1問題描述和規(guī)格說明已知一元n次多項式：設(shè)計程序?qū)崿F(xiàn)一元n次多項式的抽象數(shù)據(jù)類型，模擬一元n次多項式的操作行為。包括：數(shù)據(jù)元素：ai，存儲結(jié)構(gòu)，邏輯操作：1、構(gòu)造一個空的多項式2、多項式插入新的一項3、多項式合并同類項4、多項式的加法Pn(x)+Qn(x)=Rt(x)5、多項式的乘法Pn(x)*Qn(x)=Rt(x)6、打印多項式7、計算多項式的值 1.2功能需求1)首先構(gòu)造兩三個多項式供用戶使用；2)用戶可以進行添加多項式或是添加多項式中的項；3)或

2、是修改其中的項，或是對多項式進行刪除，或僅僅刪除其中的某項；4)或是查看當(dāng)前的某項多項式5) 用戶賦予多項式變量x值后可以計算多項式的值6)可以計算兩個或是多個多項式的和；7)可以計算兩個以上多項式的乘積8)可以對多項式中的同類項進行合并2、設(shè)計(目標(biāo)：有效組織與處理數(shù)據(jù))2.1抽象數(shù)據(jù)類型:因為每個多項式有n個項，每個項包含不同的系數(shù)和指數(shù)， 多項式的系數(shù)ai抽象為整數(shù)，變量x也是整數(shù)，x的次冪n也是整數(shù)，故多項式的每一項抽象為一個Nape類型的節(jié)點，包括：ai、x、n數(shù)據(jù)元素，最后整個一元n次多項式抽象為Polynomial數(shù)據(jù)類型。詳細(xì)設(shè)計如下：Nope類型設(shè)計為：class Nopef

3、riend class Polynomial; /設(shè)置Polynomial為Nope的友元類，方便Polynomial類訪問Nope的私有數(shù)據(jù)成員private:int m_factor; /項系數(shù)int m_times; /次冪public:Nope(int factor=0,int times=0);/構(gòu)造函數(shù)Nope();int GetFoctor()const; /獲取項系數(shù)int GetTimes()const; /獲取次冪void SetFactor(int factor); /設(shè)置項系數(shù)void SetTimes(int times); /設(shè)置次冪Nope & opera

4、tor=(const Nope& item); /賦值=int operator<=(const Nope& item); /比較<=/比較次冪的大小friend ostream &operator<<(ostream& out, const Nope&item); /輸出<<Nope(const Nope& item); /復(fù)制構(gòu)造&Polynoomial數(shù)據(jù)類型設(shè)計為：class Polynomialprivate:int m_x; /多項式中的變量xint m_size; /多項式的項數(shù)LinLi

5、stWithRear< Nope > m_list; /存儲多項式的帶尾指針的單向鏈表public:Polynomial(int size = 0,int factor= 1);/可以構(gòu)造系數(shù)為factor，個數(shù)為size的多項式，次冪依次增長Polynomial();Polynomial(const Polynomial&poly);int GetM_size()const; /獲取多項式的項數(shù)int GetM_x()const;int GetM_factor(const int& index)const; /獲取第index項的系數(shù)/從第1項開始（而不是第0項）

6、int GetM_times(const int& index)const; /獲取第index項的次冪inline double GetM_Number(const int& index)const; /獲取第index項的值,因為計算多項式的值時頻繁調(diào)用，所以設(shè)計為內(nèi)聯(lián)函數(shù)int Getfactor(const int& times)const; /獲取次冪為times的項的系數(shù) /失敗或沒有，返回0int GetIndex(const int& times)const; /獲取次冪為times的項的下標(biāo)/從1開始double GetNumber(const

7、 int& times)const; /獲取次冪為times的項的值 /失敗或沒有 返回0double GetTotalNumber()const; /獲取整個多項式的值int SetM_factor(const int& index,const int& factor); /設(shè)置第index項的系數(shù)/從第1項開始（而不是第0項）int Setfactor(const int& times,const int& factor); /設(shè)置次冪為times的項的系數(shù)/失敗返回0int SetM_times(const int& index, cons

8、t int& times); /設(shè)置次冪為times的項的系數(shù)/失敗返回0int SetM_x(const int & x); /給未知數(shù)m_x賦值bool DeleteIndex(const int & index); /刪除第index項bool DeleteTimes(const int & times); /刪除次冪為times的項bool DeleteFactor(const int& factor); /刪除所有系數(shù)為factor的項inline int InsertEnd(const int& factor, const int&a

9、mp; times); /從尾部插入新項，系數(shù)為factor，次數(shù)為times/失敗返回0inline void InsertEnd(const Nope& item);Polynomial& operator=(const Polynomial&Poly); /賦值void Combine(); /合并同類項且按次冪排序void Print()const; /打印多項式void OrderPolynomial(); /按次冪排序多項式int OrderInsert(const int& factor, const int& times); /有序插入新

10、項，系數(shù)為factor，次數(shù)為times/失敗返回0Polynomial operator+(const Polynomial&polyb); /多項式的加法Polynomial operator*(const Polynomial&polyb); /多項式的乘法friend ostream &operator<<(ostream& out, const Polynomial& item); /輸出<<2.2存儲結(jié)構(gòu)設(shè)計： 1)存儲結(jié)構(gòu)的確定數(shù)據(jù)結(jié)構(gòu)的目的是有效組織和處理數(shù)據(jù)。為了有效組織和處理數(shù)據(jù)，先要分析一元n次多項式邏輯操作

11、的特點和指針?biāo)伎臻g比例，然后確定最優(yōu)的存儲結(jié)構(gòu)。a) 確定采用鏈?zhǔn)酱鎯Y(jié)構(gòu)1. n次多項式在構(gòu)造時頻繁執(zhí)行插入操作，在程序運行階段頻繁執(zhí)行刪除或修改操作，且多項式的項數(shù)n不能確定，用戶對項數(shù)n的需求變化大。2. 如果采用鏈表，指針存儲開銷和整個結(jié)點內(nèi)容所占空間相比，其比例較小綜上所述，認(rèn)為不采用順序表，而采用鏈表。b) 選擇哪種鏈?zhǔn)酱鎯Y(jié)構(gòu)？1. 多項式在構(gòu)造時可能經(jīng)常在尾部插入或是在尾部修改數(shù)據(jù)，因此增設(shè)尾指針，尾指針始終指向鏈表的尾部結(jié)點。 通過增設(shè)尾指針，在表尾插入的算法時間復(fù)雜度為O（1）。綜上所述，采用帶尾指針的鏈表存儲結(jié)構(gòu)。2)設(shè)計帶尾指針的單鏈表a) 結(jié)構(gòu)描述b) 邏輯操作設(shè)帶

12、尾指針的循環(huán)單鏈表類型名為ListCWithRear，L 是ListCWithRear 型。通過分析n次多項式的抽象數(shù)據(jù)類型，進一步確定帶尾指針的單鏈表的邏輯操作如下所示：1. LinListCWithRear(L)/初始化2. IsEmpty(L)/ 判斷是否是空表。如果表為空，返回0，否則返回1。3. InsertEnd(L, x) /在表尾插入新結(jié)點x。插入成功返回1，失敗返回0。5. LinListCWithRear(L)/ 撤銷單鏈表6. void OrderInsert(const T& x);/單鏈表的有序插入7.int SetItem(const T& item

13、,const int &pos); /修改第pos個節(jié)點的數(shù)據(jù)8.void OrderList();/單鏈表內(nèi)元素按<=符合排序2.3算法設(shè)計void LinListWithRear<T>:OrderInsert(const T& x) /有序插入數(shù)據(jù)元素xListNode<T> *curr, *pre; curr = head->next;/curr指向首元結(jié)點pre = head;/pre指向頭結(jié)點while (curr != NULL && curr->data <= x)/*<= 比較符*/定位插入位

14、置pre = curr;curr = curr->next;ListNode<T> *q = new ListNode<T>(x, pre->next);/申請一個結(jié)點并賦值pre->next = q;/把新結(jié)點插入在pre所指結(jié)點后if (curr = NULL)rear = q;/尾指針始終指向鏈尾size+;/表長加1/*算法時間復(fù)雜度分析：很明顯，這個函數(shù)基本語句的執(zhí)行次數(shù)是f(n)=n，故時間復(fù)雜度T(n) = O(n);*/void LinListWithRear<T>:OrderList()ListNode<T>

15、*curr= head;/curr指向頭結(jié)點while (curr->next != NULL)/<= 比較符ListNode<T>*second = curr->next;/指向下一個節(jié)點while (second->next != NULL)/<= 比較符ListNode<T>*third = second->next;/指向下一個節(jié)點if (curr->next->data <= third->data) /繼續(xù)往下搜索second = second->next;else /third掉鏈，接在cu

16、rr后面second->next = second->next->next;third->next = curr->next;curr->next = third;curr = curr->next;rear = curr;/*算法時間復(fù)雜度分析：很明顯，這個函數(shù)基本語句的執(zhí)行次數(shù)是f()=n+n-1+n-2+.+2+1=(n-1)*n/2，故時間復(fù)雜度T(n) = O(n*n);*/Polynomial類：Polynomial Polynomial:operator+(const Polynomial&polyb) /多項式加法/Polyno

17、mial polyc; /局部變量，用于存儲相加的結(jié)果if (m_size + polyb.m_size = 0)return polyc;ListNode<Nope> *pa = m_list.head; /獲取第一個節(jié)點/pa指向頭指針ListNode<Nope> *pb = polyb.m_list.head;while (pa->Next() != NULL) polyc.InsertEnd(pa->Next()->Data().m_factor, pa->Next()->Data().m_times); /從尾部插入pa = pa

18、->Next(); /pa指向La的下一個元素while (pb->Next() != NULL)polyc.InsertEnd(pb->Next()->Data().m_factor, pb->Next()->Data().m_times);pb = pb->Next(); /pb指向Lb的下一個元素polyc.Combine(); /合并同類項return polyc; /返回相加結(jié)果/*算法時間復(fù)雜度分析：很明顯，這個函數(shù)基本語句的執(zhí)行次數(shù)是f()=n+n=2n，故時間復(fù)雜度T(n) = O(n);*/Polynomial Polynomial:

19、operator*(const Polynomial&polyb) /多項式乘法if (m_size = 0|polyb.m_size=0)return *this;Combine(); /先將當(dāng)前多項式合并同類項以減少乘法時間復(fù)雜度Polynomial polyc;ListNode<Nope> *pa = m_list.head; /獲取第一個節(jié)點/pa指向頭指針ListNode<Nope> *pb = polyb.m_list.head;while (pa->Next() != NULL ) Nope tempa(pa->Next()->D

20、ata();while (pb->Next() != NULL)Nope tempb(pb->Next()->Data();polyc.InsertEnd(tempa.m_factor*tempb.m_factor, tempa.m_times+tempb.m_times);pb = pb->Next(); /pb指向Lb的下一個元素pa = pa->Next(); /pa指向La的下一個元素polyc.Combine();/ 將相乘結(jié)果合并同類項再返回return polyc;/*算法時間復(fù)雜度分析：很明顯，這個函數(shù)基本語句的執(zhí)行次數(shù)是f()=n+n+n+n+.

21、+n+n=n*n，故時間復(fù)雜度T(n) = O(n*n);如果考慮InsertEnd(i);函數(shù)的執(zhí)行次數(shù)也為T(n)=O(1)，即時間復(fù)雜度仍然為T(n)=O(n*n);*/void Polynomial:Combine() /合并同類項且ListNode<Nope> *pa = m_list.Index(1); /獲取第一個數(shù)據(jù)節(jié)點int index1 = 0;while (pa->Next() != NULL) index1+;int index2 = 0;ListNode<Nope> *pb = pa;Nope tempa(pa->Data(); w

22、hile(pb->Next()!=NULL)index2+;Nope tempb(pb->Next()->Data();if (tempa.m_times = tempb.m_times)tempa.SetFactor(tempa.m_factor + tempb.m_factor);pa->SetData(tempa);/pb = pb->Next()->Next();m_list.Delete(index1 + index2);m_size-;index2-; /刪除一個else pb = pb->Next(); /pb指向Lb的下一個元素pa =

23、 pa->Next(); /pa指向La的下一個元素/*算法時間復(fù)雜度分析：很明顯，這個函數(shù)基本語句的執(zhí)行次數(shù)是f(n)=n+n-1+n-2+.+1=(n+1)*n/2，故時間復(fù)雜度T(n) = O(n的2次方);*/2.4模塊及調(diào)用關(guān)系文件包含關(guān)系調(diào)試類結(jié)構(gòu)：多項式類結(jié)構(gòu)：3、使用說明1 本程序運行在windows 系列的操作系統(tǒng)下，執(zhí)行文件為：ADT Polynomial.exe。2. 用戶需嚴(yán)格按照用戶界面的輸入提示說明輸入數(shù)據(jù)進行測試使用。3 在 使用中輸入的選擇項數(shù)請從第一項開始算起，而不是第零項。除非界面提示可以輸入；否則可能引起訪問越界導(dǎo)致程序退出！4 輸出結(jié)果表示多項式的當(dāng)前結(jié)構(gòu)，格式為Pn(x)= a*pow(x,y1 ) + b*pow(x,y2)+.Pow(x,y)表示x的y次方，a，b表示項的項數(shù)5.只有當(dāng)給多項式的變量x賦值之后才可以求出多項式的總值，否則求值為0；4、調(diào)試分析1.在看課本時我一直以為鏈表的head指針是另外一個單獨的指針，head->next是頭節(jié)點，head->next->next才是首元節(jié)點，所以寫代碼時出現(xiàn)了很多的錯誤，調(diào)試過程中才發(fā)現(xiàn)head是頭指針，head->next就是首元節(jié)點，才算深刻認(rèn)識了鏈表啊2.在測試類