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

1、數(shù)據(jù)結(jié)構(gòu)與算法實驗指導(dǎo)書（北京 ）計算機科學(xué)與技術(shù)系、乙前言數(shù)據(jù)結(jié)構(gòu) 是計算機及相關(guān)專業(yè)的一門核心基礎(chǔ)課程， 也是很多高校考研專業(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計能力及良好的程序設(shè)計習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的存儲案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機實驗是最佳的途徑之一。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。

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

3、可以根據(jù)實際需要選擇。2、實驗題目中帶者為較高要求，學(xué)生可自選；其余部分為基本容，應(yīng)盡量完成（至少完成70%，否則實驗不合格）。3 、 數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一， 希望有志于考研的學(xué)生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。五、實驗報告的書寫要求1 明確實驗的目的及要求；2 記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果；3 說明實驗中出現(xiàn)的問題和解決過程；4 寫出實驗的體會和實驗過程中沒能解決的問題；六、參考書目數(shù)據(jù)結(jié)構(gòu) （ C+ 語言描述） 紅梅等 清華大學(xué)出版社DATA STRUCTURE WITH C+ William Ford,William Topp清華

4、大學(xué)出版社（影印版）控制臺程序?qū)嶒炂脚_1、啟動Microsoft VC6.0集成開發(fā)環(huán)境如圖所示:2、單擊“文件”菜單，選擇“新建”項。3、選擇Win32控制臺應(yīng)用程序”選項，如下圖所示。4、在D盤建立文件夾“Testi"，并鍵入工程名'TestList”。Newfilrs Projects V/orkspaecs Olhrr Documctils.£AT1. COM AiWLartl工 Cluster IlcsourEC Type WizardCuctom AppWizard吉DhIhIih切 PrujtTl堂 DcvStudlo Add In MEHd盤 Ext

5、ended Stored Proc Wizard>£lSAPI Fxtsnslon WlznrriMakefile成 MFC ActiveX Controlwizard 性“FC AppWIZBM (dll) 9MrCAppWlrmd(exe)New Dalabosc WizardR Ulilliy ProjectWin32 A(jplimtiou Win32 C/rmtHc 也ppIicnQiunWin? DynamloLink LibnryWin32 Static LftniyFrajcct name：TestLietLocal nan：DATLSTIYTcstJst* C

6、jDcele new w<orli5(>6»Add to current wcrk&p ace廠 Dependency of:I3PlnllDtm：酮nW?OKCancel5、單擊“OK”按鈕，進(jìn)入下圖界面。6、選擇An empty project ”選項后，點擊Finish”按鈕，進(jìn)入下圖界面。7、單擊“文件”菜單，選擇“新建”項，如下圖所示。8、在彈出的窗口選擇“ C/C+HeaderFile : 在名稱框輸入SeqList"，如下圖所示。9、單擊“添加”按鈕后，進(jìn)入如下界面。10、將“實驗一”中順序表定義鍵入文件 SeqList.h中。11、單擊“

7、文件”菜單，選擇“新建”項，如下圖所示。12、在彈出的窗口選擇“ C+ SourceFile : 在名稱框輸入TestSeqList"，如下圖所示。13、將“實驗一"中順序表測試文件代碼鍵入 TestSeqList.cpp中。14、調(diào)試并運行程序，完成實驗容1中的要求。然后參照上述法，建立鏈表類的LinkList.h文件和TestLinkList.cpp 文件，然后完成實驗容2中的要求。實驗一 線性表的操作實驗類型：驗證性實驗要求：必修實驗學(xué)時： 2 學(xué)時一、實驗?zāi)康模簠⒄战o定的線性表順序表類和鏈表類的程序樣例，驗證給出的線性表的常見算法。二、實驗要求：1、掌握線性表順序表

8、類和鏈表類的特點。掌握線性表的常見算法。2、提交實驗報告，報告容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實驗容：1 設(shè)計一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類， 要求編程實現(xiàn)如下任務(wù)： 建立一個線性表，首先依次輸人數(shù)據(jù)元素1, 2, 3,，10,然后刪除數(shù)據(jù)元素6,最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過50 個。2設(shè)計一個帶頭結(jié)點的單鏈表類，要求：1） 生成一個整數(shù)線性表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間） 。2） 設(shè)計一個測試主函

9、數(shù)，實際運行驗證所設(shè)計單鏈表類的正確性。*3 設(shè)計一個不帶頭結(jié)點的單鏈表類，要求：1） 不帶頭結(jié)點單鏈表類的成員函數(shù)包括取數(shù)據(jù)元素個數(shù)、插入元素、刪除所有值為 k 的元素、取數(shù)據(jù)元素。（提示：要考慮在第一個數(shù)據(jù)元素結(jié)點前插入和刪除第一個數(shù)據(jù)元素結(jié)點時與在其他位置插入和刪除其他位置結(jié)點時的不同情況。 ）2） 設(shè)計一個測試主函數(shù)，實際運行驗證所設(shè)計循環(huán)單鏈表類的正確性。*4設(shè)計一個帶頭結(jié)點的循環(huán)雙向鏈表類，要求：1） 帶頭結(jié)點循環(huán)雙向鏈表類的成員函數(shù)包括：取數(shù)據(jù)元素個數(shù)、 插入、刪除、取數(shù)據(jù)元素。2） 設(shè)計一個測試主函數(shù)，實際運行驗證所設(shè)計循環(huán)雙向鏈表類的正確性。*5設(shè)計一個單鏈表實現(xiàn)一元多項式求

10、和問題。要求：（ 1）設(shè)計存儲結(jié)構(gòu)表示一元多項式；（ 2）設(shè)計算法實現(xiàn)一元多項式相加。四、程序樣例1 、順序表類定義：將該類保存在文件SeqList.h 中。#if !defined SEQ_LIST#define SEQ_LIST#include <iostream>using namespace std;const int MaxSize=100; /100 只是示例性的數(shù)據(jù)，可根據(jù)實際問題具體定義/ 定義模板類SeqList/ 按值查找，求線性表中值為 x 的元素序號/ 在線性表中第i 個位置插入值為 x 的元素/ 刪除線性表的第i 個元素/ 遍歷線性表，按序號依次輸出各元素

11、/ 存放數(shù)據(jù)元素的數(shù)組/ 線性表的長度template <class T> class SeqList public:SeqList( ) length=0; SeqList(T a , int n); SeqList( ) int Length( ) return length; T Get(int i);int Locate(T x );void Insert(int i, T x);T Delete(int i);void PrintList();private:T dataMaxSize; int length;/ 無參構(gòu)造函數(shù)/ 有參構(gòu)造函數(shù)/ 析構(gòu)函數(shù)為空/ 求線性表的

12、長度/ 按位查找，取線性表的第 i 個元素template <class T>SeqList<T>:SeqList(T a , int n)if (n>MaxSize) throw " 參數(shù)非法 "for (int i=0; i<n; i+) datai=ai;length=n;template <class T>T SeqList<T>:Get(int i)if (i<1 && i>length) throw " 查找位置非法"else return datai-1

13、;template <class T>int SeqList<T>:Locate(T x)for (i=0; i<length; i+)i+1if (datai=x) return i+1;下標(biāo)為i的元素等于x,返回其序號return 0;/ 退出循環(huán)，說明查找失敗template <class T>void SeqList<T>:Insert(int i, T x)if (length>=MaxSize) throw " 上溢 "if (i<1 | | i>length+1) throw "

14、 位置 "for (j=length; j>=i; j-)dataj=dataj-1; / 注意第 j 個元素存在數(shù)組下標(biāo)為 j-1 處datai-1=x;length+;template <class T>T SeqList<T>:Delete(int i)if (length=0) throw " 下溢 "if (i<1 | i>length) throw " 位置 "T x=datai-1;for (int j=i; j<length; j+)dataj-1=dataj; /注意此處 j 已

15、經(jīng)是元素所在的數(shù)組下標(biāo)length-; return x;template <class T>void SeqList<T> : PrintList( ) for (int i = 0; i < length; i+) cout << datai<<" "/ 依次輸出線性表的元素值#endif2 、順序表測試，新建 TestSeqList.cpp 文件。#include "SeqList.h" void main( )int r=1,2,3,4,5,6,7,8,9,10;SeqList<int&

16、gt; a(r,50);cout<<" 執(zhí)行刪除操作前數(shù)據(jù)為： "<<endl;a.PrintList( );a.Delete(6);cout<<" 執(zhí)行刪除操作后數(shù)據(jù)為： "<<endl;a.PrintList( );3、鏈表類定義：將該類保存在文件LinkList.h 中 。#if !defined SEQ_LIST#define SEQ_LIST#include <iostream> using namespace std;template <class T> struct N

17、odeT data;Node<T> *next; / 此處 <T> 也可以省略;template <class T> class LinkListpublic:LinkList( )first=new Node<T> first->next=NULL; / 建立只有頭結(jié)點的空鏈表LinkList(T a , int n);/ 建立有 n 個元素的單鏈表LinkList( );/ 析構(gòu)函數(shù)int Length( );/ 求單鏈表的長度T Get(int i);/取單鏈表中第i 個結(jié)點的元素值int Locate(T x);/求單鏈表中值為 x

18、 的元素序號void Insert(int i, T x);/在單鏈表中第i 個位置插入元素值為x 的結(jié)點T Delete(int i);/在單鏈表中刪除第 i 個結(jié)點void PrintList( );/ 遍歷單鏈表，按序號依次輸出各元素private:Node<T> *first; / 單鏈表的頭指針;template <class T>LinkList<T>: LinkList( )Node<T> *p=first; / 工作指針 p 初始化while (p)/ 釋放單鏈表的每一個結(jié)點的存儲空間Node<T> *q=p;/ 暫存

19、被釋放結(jié)點p=p->next; / 工作指針 p 指向被釋放結(jié)點的下一個結(jié)點，使單鏈表不斷開 delete q;template <class T>T LinkList<T>:Get(int i)p=first->next; j=1; / 或 p=first; j=0;while (p && j<i)p=p->next;/ 工作指針 p 后移j+;if (!p) throw " 位置 "else return p->data;template <class T>void LinkList<

20、;T>:Insert(int i, T x)p=first ; j=0;/ 工作指針 p 初始化while (p && j<i-1)p=p->next; / 工作指針 p 后移 j+;if (!p) throw " 位置 "else s=new Node<T> s->data=x;向存申請一個結(jié)點 s,其數(shù)據(jù)域為 xs->next=p->next;/ 將結(jié)點 s 插入到結(jié)點 p 之后p->next=s;template <class T>T LinkList<T>:Delete(i

21、nt i)p=first ; j=0;/ 工作指針 p 初始化while (p && j<i-1)/ 查找第 i-1 個結(jié)點p=p->next;j+;if (!p | | !p->next) throw " 位置 " /結(jié)點 p 不存在或結(jié)點 p 的后繼結(jié)點不存在 else q=p->next; x=q->data; / 暫存被刪結(jié)點 p->next=q->next; / 摘鏈delete q;return x;template <class T>LinkList<T>: LinkList(T a ,