北郵資料結構實驗報告 圖

北郵資料結構實驗報告 圖

一、實驗報告規範

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

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->data.expdata.exp,則p_prior=p;p=p->nenx;

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

[2.2.1]將q結點加入到A連結串列p結點之前

[2.2.2]q指向B連結串列的下一個結點

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

[2.3.1]若p->data.coef為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->data.exp=0;p_prior->next=p->next;  p; p=p_prior;

[2.2]否則 p->data.coef*=p->data.exp; p->data.exp--;

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

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

[2]若p不為空,迴圈以下操作

a+=p->data.coef*pow(x,p->data.exp);

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->data.expdata.exp

(1)q結點不變

(2)p結點向下移

(1)p_prior=p;

(2)p=p->next;

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

(1) p_prior->next=q;

(2)p_prior=q;

(3)q=q->next;

(4)p_prior->next=p;

示意圖

:

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

(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.透過本次實驗，我發現自己分析問題不是很全面，容易忽略一些細節，以後分析問題時要仔細考慮認真分析，避免細節上的錯誤。