北郵數據結構實驗報告 圖

一、實驗報告規範

實習報告的開頭應給出題目、班級、姓名、學號和完成日期，幷包括以下七個內容：

1.需求分析

以無歧義的陳述説明程序設計的任務，強調的是程序要做什麼?明確規定：

(1)輸入的形式和輸入值的範圍;

(2)輸出的形式;

(3)程序所能達到的功能;

(4)測試數據：包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。

2.概要設計

説明本程序中用到的所有抽象數據類型的定義、主程序的流程以及各程序模塊之間的層次(調用)關係。

3.詳細設計

實現概要設計中定義的所有數據類型，對每個操作只需要寫出偽碼算法;對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達到的詳細程度建議為：按照偽碼算法可以在計算機鍵盤直接輸入高級程序設計語言程序);畫出函數的調用關係圖。

4.調試分析

內容包括：

(1)調試過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析;

(2)算法的時空分析(包括基本操作和其他算法的時間複雜度和空間複雜度的分析)和改進設想;

(3)經驗和體會等。

5.用户使用説明

説明如何使用你編寫的程序，詳細列出每一步的操作步驟。

6.測試結果

列出你的測試結果，包括輸入和輸出。這裏的測試數據應該完整和嚴格，最好多於需求分析中所列。

7.附錄

帶註釋的'源程序。如果提交源程序軟盤，可以只列出程序文件名的清單。

值得注意的是，實習報告的各種文檔資料，如：上述中的前三部分要在程序開發的過程中逐漸充實形成，而不是最後補寫(當然也可以應該最後用實驗報告紙謄清或打印)。

數據結構實驗報告;實驗名稱：實驗一線性表實現一個多項式;學生姓名：黃錦雨;班級：2011211109;班內序號：20;學號：2011210263;日期：2012年10月31日;實驗目的：;1.熟悉C++語言的基本編程方法，掌握集成編譯環;2.學習指針、模板類、異常處理的使用;3.掌握線性表的操作的實現方法;4.學習使用線性表解決實際問題的能力;實驗內容：;

數據結構實驗報告

實驗名稱： 實驗一線性表實現一個多項式

學生姓名： 黃錦雨

班 級：2011211109

班內序號： 20

學 號： 2011210263

日 期： 2012年10月31日

實驗目的：

1.熟悉C++語言的基本編程方法，掌握集成編譯環境的調試方法

2.學習指針、模板類、異常處理的使用

3.掌握線性表的操作的實現方法

4.學習使用線性表解決實際問題的能力

實驗內容：

利用線性表實現一個一元多項式Polynomial

f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn

要求：

1. 能夠實現一元多項式的輸入和輸出

2. 能夠進行一元多項式相加

3. 能夠進行一元多項式相減

4. 能夠計算一元多項式在x處的值

5. 能夠計算一元多項式的導數(選作)

6. 能夠進行一元多項式相乘(選作) 7. 編寫測試main()函數測試線性表的正確性

2. 程序分析

由於多項式是線性結構，故選擇線性表來實現，在這個程序中我採用的是單鏈表結構，每個結點代表一個項，多項式的每一項可以用其係數和指數唯一的表示。如果採用順序存儲，那麼對於結點的插入和刪除的操作會比較麻煩，而且順序表的結點個數固定，對於可能發生的情況無法很好的處理，而採用鏈表就會簡單許多，還能自由控制鏈表的長度。

兩個多項式要進行多次的計算，為了保護原始的數據，方便進行以後的計算，故選擇把結果存儲在一個新建的鏈表裏。

2.1本程序完成的主要功能：

1. 輸入和輸出：需要輸入的信息有多項式的項數，用來向系統動態申請內存;多項式

各項的係數和指數，用來構造每個結點，形成鏈表。輸出即是將多項式的內容

向屏幕輸出。

2. 多項式相加與相減：多項式的加減要指數相同即是同類項才能實現，所以在運算時

要注意判斷指數出現的各種不同的情況，分別寫出計算方法。將每項運算得到

的結果都插入到新的鏈表中，形成結果多項式。

3. 多項式的求導運算：多項式的求導根據數學知識，就是將每項的係數乘以指數，將

指數減1即可，將每項得到的結果插入到結果多項式的鏈表中。

4. 多項式在某點的值：由用户輸入x的值，然後求出每項的值相加即可。

2.2存儲結構

單鏈表: 其定義的結點包括三部分：係數、指數以及下一個結點的地址

2.3關鍵算法分析

[內容要求]

關鍵算法：

1.一元多項式求和算法:

[1]初始化工作指針p和q,以及p節點前驅節點指針p_prior

[2]若p和q都不為空,則循環以下操作:

[2.1]若p->,則p_prior=p;p=p->nenx;

[2.2]否則,若p->>q->,則:

[2.2.1]將q結點加入到A鏈表p結點之前

[2.2.2]q指向B鏈表的下一個結點

[2.3]否則:p->=p->+q->;

[2.3.1]若p->為0,則刪除結點p

[2.3.2]p指向下一個結點

[2.3.3]刪除q結點

[2.3.4]q指向下一個結點

[3]若p為空並且q不為空,則將q結點及其後所有結點追加到A鏈表的最後端

[4]將B鏈表 製成空鏈表

2.一元多項式求導

[1]初始化工作指針p及p_prior

[2]若p不為空,循環以操作

[2.1]若p->=0;p_prior->next=p->next; p; p=p_prior;

[2.2]否則 p->*=p->; p->--;

3.一元多項式求在X處的值

[1]初始化工作指針p,定義會參數a

[2]若p不為空,循環以下操作

a+=p->*pow(x,p->);

p=p->next;

4.輸出多項式

[1]獲取頭結點;

[2]循環n-1次(n為多項式的項數)

[2.1]將指針的指向後移;

[2.2]依照多項式的各種情況，設置輸出方式

[2.2.1] 係數為1且指數不為1和0，輸出x^expn+;

[2.2.2] 係數不為0且指數為0，輸出(coef)+;

[2.2.3] 係數不為0且指數為1，輸出(coef)x+;

代碼詳細分析：

求和算法詳細分析:

1.若p->

(1)q結點不變

(2)p結點向下移

(1)p_prior=p;

(2)p=p->next;

2.若p->>q->執行一下主要操作步驟

(1) p_prior->next=q;

(2)p_prior=q;

(3)q=q->next;

(4)p_prior->next=p;

示意圖

:

3.若p->==q->執行以下操作步驟:

(a)若合併係數為零,則刪除p結點,主要步驟:

(1)p_prior->next=p->next;

(2) p;

(3)p=p_prior->next;

(4)Node*temp=q;

(5)q=q->next;

(6) temp;

示意圖

:

(b)合併係數不為零,將其從新賦予p結點,主要步驟:

(1)p_prior=p;

(2)p=p_prior->next;

(3)Node*temp=q;

(4)q=q->next;

(5) temp;

示意圖:

5. 若p為空且q不為空的情況

p_prior->next=q;

示意圖:

3、計算關鍵算法的時間,空間複雜度

時間複雜度(1)一元多項式的構建(2)求和(3)減法(4)求導 時間複雜度都為O(n)

空間複雜度為:S(1)

2.3 其他

[內容要求]説明:為了防止word版本不一樣而可能帶來的圖形錯亂,示意圖,流程圖都用截圖

3. 程序運行結果

測試主函數流程：流程圖如圖所示

4.總結;[正文格式要求]見1實驗要求中的格式要求;1.這次實現一元多項式的運算運用了模版類,單鏈表;版類的的繼承,在掌握模版類及鏈表的同時又複習了上;2.這次試驗另一比較大的工程是一元多項式加法的算;點打出來又截圖完成的,真的是一個比較大工程!;3.這次一元多項式實驗問題讓我的收穫很大,對鏈表;的更加準確,在調試代碼,檢驗的時候,曾遇到很大的;4.通過本次

4. 總結

[正文格式要求] 見1實驗要求中的格式要求

1. 這次實現一元多項式的運算運用了模版類,單鏈表模版類,一元多項式模版類是單鏈表模

版類的的繼承,在掌握模版類及鏈表的同時又複習了上學期的相應內容.

2. 這次試驗另一比較大的工程是一元多項式加法的算法示意圖,以上截圖全是我自己一點

點打出來又截圖完成的,真的是一個比較大工程!

3.這次一元多項式實驗問題讓我的收穫很大,對鏈表的構建更加熟練,對鏈表的向前推進把握

的更加準確,在調試代碼,檢驗的時候,曾遇到很大的阻礙,主要是內存問題,通過自己一步步調試,解決了問題,自己也收穫了很多。

4.通過本次實驗，我發現自己分析問題不是很全面，容易忽略一些細節，以後分析問題時要仔細考慮認真分析，避免細節上的錯誤。