數(shù)據(jù)結構實驗指導書C語言連接表操作

1、數(shù)據(jù)結構實驗參考資料目 錄一、課程編號2二、課程類型2三、本課程的地位、作用與任務2四、課程基本要求2五、實驗安排21、數(shù)據(jù)結構實驗機器與環(huán)境2（一）計算機的硬件配置2（二）計算機的軟件配置22、VisualC+6.0開發(fā)C語言程序2（一）進入C+工作環(huán)境2（二）編譯、運行C程序33、上機實驗6實驗1：線性表操作6實驗2：單鏈表操作11實驗3：二叉樹操作17實驗4：圖的運算23數(shù)據(jù)結構（C語言版）實驗一、課程編號（本科）二、課程類型課程類型：必修課。適用專業(yè)：計算機大類各專業(yè)實驗學時：16學時三、本課程的地位、作用與任務數(shù)據(jù)結構在計算機科學中是一門綜合性的專業(yè)基礎課。數(shù)據(jù)結構的研究不僅涉及到計

2、算機硬件的研究范圍，而且和計算機軟件的研究有密切的關系，可以認為數(shù)據(jù)結構是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。在計算機科學中，數(shù)據(jù)結構不僅是一般程序設計的基礎，而且是設計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應用程序的重要基礎，它的主要任務是討論各種數(shù)據(jù)結構的邏輯結構，存儲結構及有關操作的算法。目的是使學生學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術。另一方面，通過對本課程算法設計和上機實踐的訓練，還應培養(yǎng)學生的數(shù)據(jù)抽象能力和程序設計的能力，從而為提高學生的實

3、際分析問題和解決問題的編程能力打下基礎。四、課程基本要求1、 學生應根據(jù)每個上機實驗的任務和教師所提的要求，上機前準備好上機內(nèi)容。2、 上機輸入程序并調(diào)試出結果。3、 上機結束后應按時提交實驗報告，對于上機未完成部分，應該下機后利用課余時間完成。實驗報告包括以下內(nèi)容：(1) 實驗題目(2) 實驗目的(3) 實驗要求(4) 實驗內(nèi)容(5) 實驗總結五、實驗安排1、數(shù)據(jù)結構實驗機器與環(huán)境（一）計算機的硬件配置PC系列微機，包括286、386、486、奔騰及各種兼容機，要求內(nèi)存為64M以上，一個硬盤驅(qū)動器和一個軟盤驅(qū)動器，80列字符監(jiān)視器，配備鼠標器。（二）計算機的軟件配置DOS6.22或Windo

4、ws 98、Windows 2000、Windows xp、Windows 7；VC+6.0或Turbo C。2、VisualC+ 6.0開發(fā)C語言程序（一）進入C+工作環(huán)境雙擊Windows桌面上的Visual C+ 6.0圖標或單擊Windows桌面上“開始”按鈕，在“程序”中選擇“Visual C+ 6.0”運行即可。（二）編譯、運行C程序創(chuàng)建一個新的工程文件（Project file）啟動Visual C+ 6.0 編譯系統(tǒng)后，出現(xiàn)“Microsoft Developer Studio”窗口，該窗口菜單條有9個菜單項（如圖1所示）：（1）單擊“File”菜單，在其下拉菜單中選擇“New

5、”，屏幕上出現(xiàn)一個“New”對話框，在該對話框中選擇“Projects”標簽，出現(xiàn)“Project”對話框。（2）選擇工程類型為“Win32 Console Application”，這時，在右邊的Platforms選框中就會出現(xiàn)Win 32。（3）輸入工程名字。在“Project name”選框中輸入所指定的工程文件名字，例如： 1st。（4）輸入路徑名。在“Location”選框中，輸入你將要把所建立的工程文件放人何處的路徑名。例如，要將工程文件放在E 盤下已建立好的子目錄E:sw1001子目錄中，所以該選取路徑為：E:sw10011st。選擇“OK”按鈕，該工程文件已建立。圖1 創(chuàng)建新的

6、工程文件建立源文件再次選擇“File”菜單中的“New”選項，在四個標簽中選擇“File”標簽，在其對話框選項中，選擇“C+ Source File”，并在右邊的Add project的選擇框內(nèi)打勾，激活其下面的選項，然后在File框內(nèi)輸入源文件名（如1st），單擊“OK”按鈕，出現(xiàn)編輯屏幕，即可編寫程序（如圖2和圖3所示）。圖2 建立源文件圖3 編輯源文件編譯連接和運行源程序程序編好后要進行編譯連接和運行，步驟如下：（1）選擇“Build”菜單，單擊下拉菜單中的“Compile 1st.cpp”，這時系統(tǒng)開始對當前的源程序進行編譯，在編譯過程中,將所發(fā)現(xiàn)的錯誤顯示在屏幕下方的“Build”窗

7、口中。根據(jù)錯誤提示，修改程序后再重新編譯，如還有錯誤，再繼續(xù)修改、編譯，直到?jīng)]有錯誤為止。（2）編譯無誤后進行連接，這時選擇“Build”菜單中的“Build 1st.exe”選項。同樣，對出現(xiàn)的錯誤要進行更改，直到編譯連接無錯為止。這時，在“Build”窗口中會顯示如下信息：1st.obj- 0 error(s), 0 warning(s)，說明編譯連接成功，并生成以源文件名為名字的可執(zhí)行文件（1st.exe）。（3）運行程序，選擇“Build”菜單中的“! Execute 1st.exe”選項。這時，會出現(xiàn)一個“MS-DOS”窗口，輸出結果顯示在該窗口中（如圖4和圖5所示）。（4）運行結束

8、后，可以回到“File”菜單，點擊“Close Workspace”選項，關閉當前文件窗口。若要編輯新的源程序，可以再次打開“File”菜單，重新建立工程文件，步驟如上所述；也可以點擊“File”菜單中的“Open Workspace”選項，打開一個已經(jīng)存在的源文件。圖4 編輯運行源程序圖5 編譯連接及結果3、上機實驗實驗1：線性表操作1實驗目的1、 會定義線性表的順序存儲類型。2、 熟悉C或C+程序的基本結構，掌握程序中的用戶頭文件、實現(xiàn)文件和主文件之間的相互關系及各自的作用。3、 熟悉對線性表的一些基本操作和具體的函數(shù)定義。4、 熟悉Turbo C或VC+操作環(huán)境的使用以及多文件程序的輸入

9、、編輯、調(diào)試和運行的全過程。2實驗要求1、 認真閱讀和掌握本實驗內(nèi)容所給的全部程序。2、 保存和打印出程序運行結果，并結合程序進行分析。3、 按照你對線性表操作的需要，重新改寫主文件并運行，打印出文件清單和運行的結果。3實驗內(nèi)容該程序的功能是對元素類型為整型的順序存儲的線性表進行一些操作。該程序包含三個文件，一個為頭文件，用來存儲定義的線性表結構類型以及對線性表進行的各種操作的函數(shù)聲明；第二個為線性表操作的實現(xiàn)文件，用來存儲每一種線性表操作的具體函數(shù)定義；第三種為主文件，用來定義線性表和調(diào)用線性表的一些操作，實現(xiàn)對給定線性表的具體運算。整個程序如下：/頭文件linearlist1.h/定義El

10、emType為int類型/頭文件linearlist1.h/定義ElemType為int類型typedef int ElemType;/線性表順序存儲類型struct LinearList ElemType* list; /存線性表元素int size; /存線性表長度int MaxSize; /存list數(shù)組長度; /初始化線性表 void InitList(LinearList& L, int ms); /清空線性表 void ClearList(LinearList& L); /求線性表長度 int ListSize(LinearList& L); /檢查線性表是

11、否為空 bool ListEmpty(LinearList& L); /檢查線性表是否為滿 bool ListFull(LinearList& L); /遍歷線性表 void TraverList(LinearList& L); /從線性表中查找元素 bool FindList(LinearList& L, ElemType& item); /更新線性表中的給定元素 bool UpdateList(LinearList& L, const ElemType& item); /向線性表插入元素 bool InsertList(LinearL

12、ist& L, const ElemType& item, int mark); /從線性表中刪除元素 bool DeleteList(LinearList& L, ElemType& item, int mark);/對線性表進行有序輸出 void OrderOutputList(LinearList& L, int mark);/實現(xiàn)文件linearlist1.cpp #include<iomanip.h> #include <stdio.h> #include <stdlib.h> #include"l

13、inearlist1.h"/初始化線性表void InitList(LinearList& L, int ms) L.list=new ElemTypems;if(!L.list) printf("Memory allocation failure!");exit(1); L.size=0;L.MaxSize=ms;/清空線性表void ClearList(LinearList& L) L.size=0;/求線性表長度int ListSize(LinearList& L) return L.size;/檢查線性表是否為空bool ListE

14、mpty(LinearList& L) return L.size=0; /檢查線性表是否為滿bool ListFull(LinearList& L) return L.size=L.MaxSize; /遍歷線性表void TraverList(LinearList& L) for(int i=0; i<L.size; i+) printf(" %d",L.listi);printf("n"); /從線性表中查找元素bool FindList(LinearList& L, ElemType& item) fo

15、r(int i=0; i<L.size; i+)if(L.listi=item) item=L.listi;return true;return false; /更新線性表中的給定元素bool UpdateList(LinearList& L, const ElemType& item) for(int i=0; i<L.size; i+)if(L.listi=item) L.listi=item;return true;return false; /向線性表的表頭、表尾或合適位置插入元素bool InsertList(LinearList& L, cons

16、t ElemType& item, int mark) if(ListFull(L) return false;if(mark>0) for(int i=L.size-1; i>=0; i-)L.listi+1=L.listi;L.list0=item; else if(mark<0) L.listL.size=item;else for(int i=0; i<L.size; i+) if(item<L.listi) break; for(int j=L.size-1; j>=i; j-) L.listj+1=L.listj; L.listi=ite

17、m;L.size+;return true; /從線性表中刪除表頭、表尾或等于給定值的元素bool DeleteList(LinearList& L, ElemType& item, int mark)if(ListEmpty(L) return false;if(mark>0) item=L.list0;for(int i=1; i<L.size; i+)L.listi-1=L.listi; else if(mark<0) item=L.listL.size-1;else for(int i=0; i<L.size; i+) if(L.listi=it

18、em) break; if(i>=L.size) return false; else item=L.listi; for(int j=i+1; j<L.size; j+) L.listj-1=L.listj;L.size-;return true; /對線性表按升序或降序輸出void OrderOutputList(LinearList& L, int mark)int* b=new intL.size;int i,k;for(i=0; i<L.size; i+)bi=i;for(i=1; i<L.size; i+) k=i-1;for(int j=i; j&

19、lt;L.size; j+) if(mark=1 && L.listbj<L.listbk) k=j; /升序 if(mark!=1 && L.listbk<L.listbj) k=j; /降序if(k!=i-1) int x=bi-1; bi-1=bk; bk=x;for(i=0; i<L.size; i+)printf(" %d",L.listbi);printf("n");/主文件listmain1.cpp#include <iomanip.h>/要用到格式控制符#include <

20、;stdio.h>#include"linearlist1.h"const int ML=10; void main()LinearList a;InitList(a,ML);int i;ElemType x; /依次向線性表a表尾插入5個整數(shù)元素printf("從鍵盤輸入5個整數(shù):n");for(i=0; i<5; i+)scanf("%d",&x);InsertList(a,x,-1); /依次向線性表a表頭插入2個整數(shù)元素printf("從鍵盤輸入2個整數(shù):");scanf("%

21、d",&x);InsertList(a,x,1);scanf("%d",&x);InsertList(a,x,1); /按不同次序遍歷輸出線性表aTraverList(a);OrderOutputList(a,1);OrderOutputList(a,0); /把線性表a中的所有元素依次有序插入到一個新線性表b中" LinearList b;InitList(b,ML);for(i=0; i<a.size; i+)InsertList(b, a.listi, 0); /輸出線性表bTraverList(b); /從線性表a中分別刪除

22、表頭、表尾、給定值元素if(DeleteList(a,x,1) printf("Delete success!");else printf("Delete fail!n");if(DeleteList(a,x,-1) printf("Delete success!n");else printf("Delete fail!n");printf("從鍵盤上輸入一個待刪除的整數(shù):n");scanf("%d",&x);if(DeleteList(a,x,0) printf(&

23、quot;Delete success!n");else printf("Delete fail!n"); /輸出線性表aTraverList(a);（選作）試著參照算法寫出C語言程序，實現(xiàn)下列題目要求！（1）試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表逆置為。解：/ 順序表的逆置Status ListOppose_Sq(SqList &L)int i;ElemType x;for(i=0;i<L.length/2;i+)x=L.elemi;L.elemi=L.elemL.length-1-i;L.elemL.length-1-i=x;return OK;（2） 假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元素值各不相同），現(xiàn)要求另辟空間構成一個線性表C，其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對順序表編寫求C的算法。解：/ 將A、B求交后的結果放在C表中Status ListCross_Sq(SqList &A,SqList &B,SqList &C)int i=0,j=0,k=0;while(i<A