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