- 相關(guān)推薦
北郵數(shù)據(jù)結(jié)構(gòu)實驗報告 圖
一、實驗報告規(guī)范
實習報告的開頭應(yīng)給出題目、班級、姓名、學號和完成日期，并包括以下七個內(nèi)容：
1.需求分析
以無歧義的陳述說明程序設(shè)計的任務(wù)，強調(diào)的是程序要做什么?明確規(guī)定：
(1)輸入的形式和輸入值的范圍;
(2)輸出的形式;
(3)程序所能達到的功能;
(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。
2.概要設(shè)計
說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。
3.詳細設(shè)計
實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法;對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達到的詳細程度建議為：按照偽碼算法可以在計算機鍵盤直接輸入高級程序設(shè)計語言程序);畫出函數(shù)的調(diào)用關(guān)系圖。
4.調(diào)試分析
內(nèi)容包括：
(1)調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析;
(2)算法的時空分析(包括基本操作和其他算法的時間復雜度和空間復雜度的分析)和改進設(shè)想;
(3)經(jīng)驗和體會等。
5.用戶使用說明
說明如何使用你編寫的程序，詳細列出每一步的操作步驟。
6.測試結(jié)果
列出你的測試結(jié)果，包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴格，最好多于需求分析中所列。
7.附錄
帶注釋的源程序。如果提交源程序軟盤，可以只列出程序文件名的清單。
值得注意的是，實習報告的各種文檔資料，如：上述中的前三部分要在程序開發(fā)的過程中逐漸充實形成，而不是最后補寫(當然也可以應(yīng)該最后用實驗報告紙謄清或打印)。
數(shù)據(jù)結(jié)構(gòu)實驗報告;實驗名稱：實驗一線性表實現(xiàn)一個多項式;學生姓名：黃錦雨;班級：2011211109;班內(nèi)序號：20;學號：2011210263;日期：2012年10月31日;實驗目的：;1.熟悉C++語言的基本編程方法，掌握集成編譯環(huán);2.學習指針、模板類、異常處理的使用;3.掌握線性表的操作的實現(xiàn)方法;4.學習使用線性表解決實際問題的能力;實驗內(nèi)容：;
數(shù)據(jù)結(jié)構(gòu)實驗報告
實驗名稱： 實驗一線性表實現(xiàn)一個多項式
學生姓名： 黃錦雨
班 級：2011211109
班內(nèi)序號： 20
學 號： 2011210263
日 期： 2012年10月31日
實驗目的：
1.熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法
2.學習指針、模板類、異常處理的使用
3.掌握線性表的操作的實現(xiàn)方法
4.學習使用線性表解決實際問題的能力
實驗內(nèi)容：
利用線性表實現(xiàn)一個一元多項式Polynomial
f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn
要求：
1. 能夠?qū)崿F(xiàn)一元多項式的輸入和輸出
2. 能夠進行一元多項式相加
3. 能夠進行一元多項式相減
4. 能夠計算一元多項式在x處的值
5. 能夠計算一元多項式的導數(shù)(選作)
6. 能夠進行一元多項式相乘(選作) 7. 編寫測試main()函數(shù)測試線性表的正確性
2. 程序分析
由于多項式是線性結(jié)構(gòu)，故選擇線性表來實現(xiàn)，在這個程序中我采用的是單鏈表結(jié)構(gòu)，每個結(jié)點代表一個項，多項式的每一項可以用其系數(shù)和指數(shù)唯一的表示。如果采用順序存儲，那么對于結(jié)點的插入和刪除的操作會比較麻煩，而且順序表的結(jié)點個數(shù)固定，對于可能發(fā)生的情況無法很好的處理，而采用鏈表就會簡單許多，還能自由控制鏈表的長度。
兩個多項式要進行多次的計算，為了保護原始的數(shù)據(jù)，方便進行以后的計算，故選擇把結(jié)果存儲在一個新建的鏈表里。
2.1本程序完成的主要功能：
1. 輸入和輸出：需要輸入的信息有多項式的項數(shù)，用來向系統(tǒng)動態(tài)申請內(nèi)存;多項式
各項的系數(shù)和指數(shù)，用來構(gòu)造每個結(jié)點，形成鏈表。輸出即是將多項式的內(nèi)容
向屏幕輸出。
2. 多項式相加與相減：多項式的加減要指數(shù)相同即是同類項才能實現(xiàn)，所以在運算時
要注意判斷指數(shù)出現(xiàn)的各種不同的情況，分別寫出計算方法。將每項運算得到
的結(jié)果都插入到新的鏈表中，形成結(jié)果多項式。
3. 多項式的求導運算：多項式的求導根據(jù)數(shù)學知識，就是將每項的系數(shù)乘以指數(shù)，將
指數(shù)減1即可，將每項得到的結(jié)果插入到結(jié)果多項式的鏈表中。
4. 多項式在某點的值：由用戶輸入x的值，然后求出每項的值相加即可。
2.2存儲結(jié)構(gòu)
單鏈表: 其定義的結(jié)點包括三部分：系數(shù)、指數(shù)以及下一個結(jié)點的地址
2.3關(guān)鍵算法分析
[內(nèi)容要求]
關(guān)鍵算法：
1.一元多項式求和算法:
[1]初始化工作指針p和q,以及p節(jié)點前驅(qū)節(jié)點指針p_prior
[2]若p和q都不為空,則循環(huán)以下操作:
[2.1]若p->data.expdata.exp,則p_prior=p;p=p->nenx;
[2.2]否則,若p->data.exp>q->data.exp,則:
[2.2.1]將q結(jié)點加入到A鏈表p結(jié)點之前
[2.2.2]q指向B鏈表的下一個結(jié)點
[2.3]否則:p->data.coef=p->data.coef+q->data.coef;
[2.3.1]若p->data.coef為0,則刪除結(jié)點p
[2.3.2]p指向下一個結(jié)點
[2.3.3]刪除q結(jié)點
[2.3.4]q指向下一個結(jié)點
[3]若p為空并且q不為空,則將q結(jié)點及其后所有結(jié)點追加到A鏈表的最后端
[4]將B鏈表 制成空鏈表
2.一元多項式求導
[1]初始化工作指針p及p_prior
[2]若p不為空,循環(huán)以操作
[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,定義會參數(shù)a
[2]若p不為空,循環(huán)以下操作
a+=p->data.coef*pow(x,p->data.exp);
p=p->next;
4.輸出多項式
[1]獲取頭結(jié)點;
[2]循環(huán)n-1次(n為多項式的項數(shù))
[2.1]將指針的指向后移;
[2.2]依照多項式的各種情況，設(shè)置輸出方式
[2.2.1] 系數(shù)為1且指數(shù)不為1和0，輸出x^expn+;
[2.2.2] 系數(shù)不為0且指數(shù)為0，輸出(coef)+;
[2.2.3] 系數(shù)不為0且指數(shù)為1，輸出(coef)x+;
代碼詳細分析：
求和算法詳細分析:
1.若p->data.expdata.exp
(1)q結(jié)點不變
(2)p結(jié)點向下移
(1)p_prior=p;
(2)p=p->next;
2.若p->data.exp>q->data.exp執(zhí)行一下主要操作步驟
(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執(zhí)行以下操作步驟:
(a)若合并系數(shù)為零,則刪除p結(jié)點,主要步驟:
(1)p_prior->next=p->next;
(2) p;
(3)p=p_prior->next;
(4)Node*temp=q;
(5)q=q->next;
(6) temp;
示意圖
:
(b)合并系數(shù)不為零,將其從新賦予p結(jié)點,主要步驟:
(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、計算關(guān)鍵算法的時間,空間復雜度
時間復雜度(1)一元多項式的構(gòu)建(2)求和(3)減法(4)求導 時間復雜度都為O(n)
空間復雜度為:S(1)
2.3 其他
[內(nèi)容要求]說明:為了防止word版本不一樣而可能帶來的圖形錯亂,示意圖,流程圖都用截圖
3. 程序運行結(jié)果
測試主函數(shù)流程：流程圖如圖所示
4.總結(jié);[正文格式要求]見1實驗要求中的格式要求;1.這次實現(xiàn)一元多項式的運算運用了模版類,單鏈表;版類的的繼承,在掌握模版類及鏈表的同時又復習了上;2.這次試驗另一比較大的工程是一元多項式加法的算;點打出來又截圖完成的,真的是一個比較大工程!;3.這次一元多項式實驗問題讓我的收獲很大,對鏈表;的更加準確,在調(diào)試代碼,檢驗的時候,曾遇到很大的;4.通過本次
4. 總結(jié)
[正文格式要求] 見1實驗要求中的格式要求
1. 這次實現(xiàn)一元多項式的運算運用了模版類,單鏈表模版類,一元多項式模版類是單鏈表模
版類的的繼承,在掌握模版類及鏈表的同時又復習了上學期的相應(yīng)內(nèi)容.
2. 這次試驗另一比較大的工程是一元多項式加法的算法示意圖,以上截圖全是我自己一點
點打出來又截圖完成的,真的是一個比較大工程!
3.這次一元多項式實驗問題讓我的收獲很大,對鏈表的構(gòu)建更加熟練,對鏈表的向前推進把握
的更加準確,在調(diào)試代碼,檢驗的時候,曾遇到很大的阻礙,主要是內(nèi)存問題,通過自己一步步調(diào)試,解決了問題,自己也收獲了很多。
4.通過本次實驗，我發(fā)現(xiàn)自己分析問題不是很全面，容易忽略一些細節(jié)，以后分析問題時要仔細考慮認真分析，避免細節(jié)上的錯誤。
【北郵數(shù)據(jù)結(jié)構(gòu)實驗報告 圖】相關(guān)文章：
北郵研究生在京就業(yè)前景如何07-14
北郵的通信工程就業(yè)前景怎么樣07-14
北郵的工程管理專業(yè)好嗎？以后就業(yè)前景咋樣��？07-11
北郵網(wǎng)絡(luò)工程專業(yè)和通信工程就業(yè)前景誰更好？07-14
北郵通信，華科電氣工程及其自動哪個好？哪個就業(yè)前景好？07-11
同濟大學的土木工程和北郵的通信工程哪個就業(yè)前景更好07-14
調(diào)劑到北郵軟院讀通信工程專業(yè)怎么樣？就業(yè)前景好嗎？07-14
京東包郵嗎？07-11
關(guān)于實驗報告01-27