數(shù)據(jù)結(jié)構(gòu)上機(jī)指導(dǎo)書

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書中國石油大學(xué)()計(jì)算機(jī)科學(xué)與技術(shù)系它主要介紹線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些 典型算法及時(shí)、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計(jì)能力及良好的程序 設(shè)計(jì)習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問 題選取合適的存儲方案，設(shè)計(jì)出簡潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打 下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機(jī)實(shí)驗(yàn)是最 佳的途徑之一。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配 合學(xué)生實(shí)驗(yàn)，特編寫實(shí)驗(yàn)指導(dǎo)書。一、實(shí)驗(yàn)?zāi)康母玫睦斫馑?/p>

2、法的思想、培養(yǎng)編程能力。二、實(shí)驗(yàn)要求1、每次實(shí)驗(yàn)前學(xué)生必須根據(jù)試驗(yàn)容認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時(shí)所需的輸入數(shù)據(jù)。2 、在指導(dǎo)教師的幫助下能夠完成實(shí)驗(yàn)容，得出正確的實(shí)驗(yàn)結(jié)果。3 、實(shí)驗(yàn)結(jié)束后總結(jié)實(shí)驗(yàn)容、書寫實(shí)驗(yàn)報(bào)告。4、遵守實(shí)驗(yàn)室規(guī)章制度、不缺席、按時(shí)上、下機(jī)。5 、實(shí)驗(yàn)學(xué)時(shí)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機(jī)資格，平時(shí)成績扣10分。6 、實(shí)驗(yàn)報(bào)告有一次不合格，扣5分，兩次以上不合格者，平時(shí)成績以零分記。三、實(shí)驗(yàn)環(huán)境 VC+6.0或者VC2010四、說明1 、本實(shí)驗(yàn)的所有算法中元素類型可以根據(jù)實(shí)際需要選擇。2 、實(shí)驗(yàn)題目中帶*者為較高要求，學(xué)生可自選；其余部分

3、為基本容，應(yīng)盡量完成（至 少完成70%否則實(shí)驗(yàn)不合格）。3 、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。五、實(shí)驗(yàn)報(bào)告的書寫要求1 明確實(shí)驗(yàn)的目的及要求；2 記錄實(shí)驗(yàn)的輸入數(shù)據(jù)和輸出結(jié)果；3 說明實(shí)驗(yàn)中出現(xiàn)的問題和解決過程；4 寫出實(shí)驗(yàn)的體會和實(shí)驗(yàn)過程中沒能解決的問題；六、參考書目數(shù)據(jù)結(jié)構(gòu)（C+語言描述）王紅梅等清華大學(xué)DATA STRUCTURE WITH C+ William Ford,William Topp清華大學(xué)（影印版）實(shí)驗(yàn)平臺控制臺程序1啟動(dòng)Microsoft VC6.0集成開發(fā)環(huán)境如圖所示：

4、Miicra-tQfEC-i- +日田 £diU 詩m Jns*rt £roftfct £Uld 1打心1$ 出i&g 匕襯p”釦"H 0 1Jdijif 旦型亠2r卵Lpj.,.,創(chuàng)_4Build / D«bii X Fuid. uci FiLaa 1 Fmd itt Fil«iE RjseulIla | -4 |112、單擊“文件”菜單，選擇“新建”項(xiàng)。3、選擇“ Win32控制臺應(yīng)用程序”選項(xiàng)，如下圖所示。4、在D盤建立文件夾“ Testi ” ,并鍵入工程名“ TestList5、單擊“ OK'按鈕，進(jìn)入下圖界

5、面。6、選擇"An empty project"選項(xiàng)后，點(diǎn)擊“ Finish "按鈕，進(jìn)入下圖界面。7、單擊“文件”菜單，選擇“新建”項(xiàng)，如下圖所示。8、在彈出的窗口選擇“ C/C+HeaderFile ”，在名稱框輸入“ SeqList ”，如下圖所示。9、單擊“添加”按鈕后，進(jìn)入如下界面。10、將“實(shí)驗(yàn)一”中順序表定義鍵入文件SeqList.h中。11、單擊“文件”菜單，選擇“新建”項(xiàng)，如下圖所示。13、將“實(shí)驗(yàn)一”中順序表測試文件代碼鍵入TestSeqList.cpp 中。14、調(diào)試并運(yùn)行程序，完成實(shí)驗(yàn)容1中的要求。然后參照上述方法，建立鏈表類的LinkLi

6、st.h 文件和TestLinkList.cpp文件，然后完成實(shí)驗(yàn)容2中的要求。實(shí)驗(yàn)一線性表的操作實(shí)驗(yàn)類型：驗(yàn)證性實(shí)驗(yàn)要求：必修實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康模簠⒄战o定的線性表順序表類和鏈表類的程序樣例，驗(yàn)證給出的線性表的常見算法。二、實(shí)驗(yàn)要求：1、掌握線性表順序表類和鏈表類的特點(diǎn)。掌握線性表的常見算法。2、提交實(shí)驗(yàn)報(bào)告，報(bào)告容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、 程序清單、調(diào)試情況、設(shè)計(jì)技巧、心得體會。三、實(shí)驗(yàn)容：1. 設(shè)計(jì)一個(gè)靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類，要求編程實(shí)現(xiàn)如下任務(wù)： 建立一個(gè)線性表，首先依次輸人數(shù)據(jù)元素 1, 2, 3，10,然后刪除數(shù)據(jù)元素 6,最后依次顯示當(dāng)前

7、線性表中的數(shù)據(jù)元素。要求采用順序表實(shí)現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個(gè)數(shù)在最壞 情況下不會超過50個(gè)。2. 設(shè)計(jì)一個(gè)帶頭結(jié)點(diǎn)的單鏈表類，要求：1）生成一個(gè)整數(shù)線性表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已知的存儲空間）。2）設(shè)計(jì)一個(gè)測試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計(jì)單鏈表類的正確性。*3 .設(shè)計(jì)一個(gè)不帶頭結(jié)點(diǎn)的單鏈表類，要求：1）不帶頭結(jié)點(diǎn)單鏈表類的成員函數(shù)包括取數(shù)據(jù)元素個(gè)數(shù)、插入元素、刪除所有值為k的元素、取數(shù)據(jù)元素。（提示：要考慮在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入和刪除第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)時(shí)與在其他位置插入和刪除其他位置結(jié)點(diǎn)時(shí)的不同情況。）2）設(shè)計(jì)一個(gè)測試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證

8、所設(shè)計(jì)循環(huán)單鏈表類的正確性。*4 .設(shè)計(jì)一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表類，要求：1）帶頭結(jié)點(diǎn)循環(huán)雙向鏈表類的成員函數(shù)包括：取數(shù)據(jù)元素個(gè)數(shù)、插入、刪除、取數(shù)據(jù)2）設(shè)計(jì)一個(gè)測試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計(jì)循環(huán)雙向鏈表類的正確性。 *5 .設(shè)計(jì)一個(gè)單鏈表實(shí)現(xiàn)一元多項(xiàng)式求和問題。要求：（1）設(shè)計(jì)存儲結(jié)構(gòu)表示一元多項(xiàng)式；（2）設(shè)計(jì)算法實(shí)現(xiàn)一元多項(xiàng)式相加。四、程序樣例1、順序表類定義：將該類保存在文件SeqList.h中。#if !defi ned SEQ_LIST#defi ne SEQ_LIST#in clude <iostream>using n amespace std;const int

9、MaxSize=100; 100只是示例性的數(shù)據(jù)，可根據(jù)實(shí)際問題具體定義template <class T> / class SeqList public:SeqList( ) le ngth=O;/SeqList(T a , int n);/SeqList( ) /int Len gth( ) retur n len gth; / T Get(i nt i);/int Locate(T x );/void In sert(i nt i, T x); / T Delete(i nt i);/void Prin tList();/private:T dataMaxSize; /int

10、 len gth; /;定義模板類SeqListi+1上溢"位置"注意第j個(gè)元素存在數(shù)組下標(biāo)為j-1處無參構(gòu)造函數(shù)有參構(gòu)造函數(shù)析構(gòu)函數(shù)為空求線性表的長度按位查找，取線性表的第 i個(gè)元素 按值查找，求線性表中值為 x的元素序號 在線性表中第i個(gè)位置插入值為x的元素 刪除線性表的第i個(gè)元素遍歷線性表，按序號依次輸出各元素存放數(shù)據(jù)元素的數(shù)組線性表的長度template <class T> SeqList<T>:SeqList(T a , int n) if (n>MaxSize) throw "參數(shù)非法"for (i nt i=0

11、; i<n; i+) datai=ai;len gth=n;template <class T>T SeqList<T>:Get(int i)if (i<1 && i>length) throw "查找位置非法”else return datai-1;template <class T>int SeqList<T>:Locate(T x)for (i=0; i<le ngth; i+)if (datai=x) return i+1; /下標(biāo)為i的元素等于x,返回其序號return 0;/退出循環(huán)，

12、說明查找失敗template <class T>void SeqList<T>:I nsert(i nt i, T x) if (len gth>=MaxSize) throw " if (i<1 | i>le ngth+1) throw "for (j=le ngth; j>=i; j_) dataj=dataj-1; / datai-1=x;len gth+;template <class T> T SeqList<T>:Delete(int i) if (len gth=O) throw &quo

13、t; if (i<1 | i>le ngth) throw " T x=datai-1; for (i nt j=i; j<le ngth; j+) dataj-1=dataj; / len gth-; return x;template <class T> void SeqList<T> : Prin tList() for (i nt i = 0; i < len gth; i+) cout << datai<<"" #en dif2、順序表測試，新建TestSeqList.cpp#i n

14、clude "SeqList.h" void mai n()下溢”;位置"注意此處j已經(jīng)是元素所在的數(shù)組下標(biāo)/文件。依次輸出線性表的元素值int r=1,2,3,4,5,6,7,8,9,10;SeqList<i nt> a(r,50);cout<<"執(zhí)行刪除操作前數(shù)據(jù)為："<<endl;a.Prin tList();a.Delete(6);cout<<"執(zhí)行刪除操作后數(shù)據(jù)為："<<endl;a.Prin tList();3、鏈表類定義：將該類保存在文件LinkLis

15、t.h中。#if !defi ned SEQ_LIST#defi ne SEQ_LIST#i nclude <iostream> using n amespace std;template <class T>struct NodeT data;Node<T> *next; /此處<丁>也可以省略;template <class T> class Lin kListpublic:Lin kList( )first=new Node<T> first-next=NULL; /鏈表建立只有頭結(jié)點(diǎn)的空LinkList(T a ,

16、int n); L in kList( );/int Len gth();T Get(i nt i); int Locate(T x);void In sert(i nt i, T x);占八、T Delete(int i); void Prin tList();/建立有n個(gè)元素的單鏈表析構(gòu)函數(shù)/求單鏈表的長度/取單鏈表中第i個(gè)結(jié)點(diǎn)的元素值/求單鏈表中值為x的元素序號/在單鏈表中第i個(gè)位置插入元素值為x的結(jié)/在單鏈表中刪除第i個(gè)結(jié)點(diǎn)/遍歷單鏈表，按序號依次輸出各元素private:Node<T> *first; /單鏈表的頭指針;template <class T>Li

17、n kList<T>: Li nkList()Node<T> *p=first; /工作指針p初始化while (p) /釋放單鏈表的每一個(gè)結(jié)點(diǎn)的存儲空間Node<T> *q=p; /暫存被釋放結(jié)點(diǎn)p=p->next; /工作指針p指向被釋放結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使單鏈表不斷開delete q;template <class T> T LinkList<T>:Get(int i) p=first- >n ext; j=1; / while (p && j<i)p=p->n ext;/j+;或 p=f

18、irst; j=0;工作指針p后移if (!p) throw " 位置" else retur n p->data;template <class T>void Lin kList<T>:I nsert(i nt i, T x)p=first ; j=0; II工作指針p初始化while (p && j<i-1)p=p->next; II 工作指針p后移 j+;if (!p) throw " 位置"else s=new Node<T> s->data=x; II向存申請一個(gè)結(jié)點(diǎn)s

19、，其數(shù)據(jù)域?yàn)閤s->next=p->next;/將結(jié)點(diǎn)s插入到結(jié)點(diǎn) p之后p_>n ext=s;template <class T>T Li nkList<T>:Delete(i nt i)p=first ; j=0; /工作指針p初始化while (p && j<i-1) /查找第 i-1 個(gè)結(jié)點(diǎn)p=p->n ext;j+;p的后繼結(jié)點(diǎn)不存if仲|(zhì) !p->next) throw "位置"/ 結(jié)點(diǎn)p不存在或結(jié)點(diǎn)在else q=p-> next; x=q->data; /暫存被刪結(jié)點(diǎn)p_>n ext=q _>n ext; / 摘鏈delete q;return x;template <class T>LinkList<T>: LinkList(T a , int n)first =new Node<T>first- >n ext