實驗介紹及實驗一

1、1數據結構實驗數據結構實驗 實驗指導書：實驗指導書：計算機科學與技術專業(yè)軟件系列課程實踐教程計算機科學與技術專業(yè)軟件系列課程實踐教程數據結構實驗教程數據結構實驗教程 胡學鋼胡學鋼 主編主編 高等教育出版社高等教育出版社2上機時間 七、八、十周 周六上午 8:0011:20 五機房3 實驗報告：實驗報告： 實驗名稱實驗名稱 實驗任務實驗任務 實驗結果（及分析總結）實驗結果（及分析總結） 4數據結構實驗工具數據結構實驗工具TCDS簡介簡介 TCDS對數據結構課程中主要的數據結構：順序表、順對數據結構課程中主要的數據結構：順序表、順序棧、順序隊列、單鏈表、雙鏈表、二叉樹（包括線序棧、順序隊列、單鏈表

2、、雙鏈表、二叉樹（包括線索二叉樹）、樹（包括森林）、圖、一維數組、二維索二叉樹）、樹（包括森林）、圖、一維數組、二維數組等結構，提供了許多可供實驗用的功能，主要分數組等結構，提供了許多可供實驗用的功能，主要分為對結構的類型定義、建立、圖形化顯示和跟蹤調試為對結構的類型定義、建立、圖形化顯示和跟蹤調試等幾類，另外還編制了數據結構中重要算法的演等幾類，另外還編制了數據結構中重要算法的演示程序。示程序。 5實驗工具系統(tǒng)的組成實驗工具系統(tǒng)的組成 1. Turbo C 語言集成環(huán)境系統(tǒng)（語言集成環(huán)境系統(tǒng)（TC.*等）、安裝等）、安裝程序及一些標準頭文件。程序及一些標準頭文件。62. 工具庫：工具庫：本套

3、實驗工具系統(tǒng)是以本套實驗工具系統(tǒng)是以Turbo C的頭文件（擴的頭文件（擴展名為展名為.h）形式提供的，每個頭文件提供一類結構的有形式提供的，每個頭文件提供一類結構的有關功能。關功能。 Tools.h： 為界面設計提供基本工具為界面設計提供基本工具 SeqLists.h：支持順序表（結構類型支持順序表（結構類型SeqList）實驗實驗 SStack.h： 支持順序棧（結構類型支持順序棧（結構類型SeqStack）實驗實驗 SQueue.h：支持順序隊列（結構類型支持順序隊列（結構類型SeqQueue）實驗實驗 Linklist.h：支持單鏈表及雙鏈表（結構類型分別為支持單鏈表及雙鏈表（結構類型

4、分別為link和和Dulink）實驗實驗 Listses.h： 支持廣義表（結構類型支持廣義表（結構類型Lists）實驗實驗 Btrechar.h和和Btreint.h：支持二叉樹及線索二叉樹（結支持二叉樹及線索二叉樹（結構類型為構類型為BiTre）實驗實驗 Trees.h： 支持樹結構（結構類型支持樹結構（結構類型Tree）實驗實驗 Graph2.h：支持圖結構（結構類型支持圖結構（結構類型DataGraph）實驗實驗 Grary1.h：支持一維數組（結構類型為支持一維數組（結構類型為Aa的一維整型的一維整型數組）的實驗數組）的實驗 73. 數據結構文件：數據結構文件：為節(jié)省實驗時間，系統(tǒng)提

5、供了將數據為節(jié)省實驗時間，系統(tǒng)提供了將數據結構存入磁盤文件和從文件中讀取結構的功能，并且結構存入磁盤文件和從文件中讀取結構的功能，并且還提供了一些預制的數據結構文件：還提供了一些預制的數據結構文件：擴展名擴展名 適用結構適用結構 所在目錄所在目錄 支持文件支持文件. .lst lst 鏈表鏈表 Llists linklist.hLlists linklist.h.cbt .cbt 字符型二叉樹字符型二叉樹 Bitres Btrechar.hBitres Btrechar.h.ibt .ibt 整型二叉樹整型二叉樹 Bitres Btreint.hBitres Btreint.h.tre .tr

6、e 樹和森林樹和森林 Trees Trees.hTrees Trees.h.grp .grp 圖結構圖結構 Graphs Graph2Graphs Graph2.arr .arr 一維數組、二維數組，順序表，順序棧，順序隊列一維數組、二維數組，順序表，順序棧，順序隊列Arrays Grary1,Grary2,SeqLists,Sstack,SQueueArrays Grary1,Grary2,SeqLists,Sstack,SQueue84. 例子程序（例子程序（emps子目錄）：子目錄）：文件名形式為文件名形式為empX_YZ ，其中其中X的取值為的取值為110，指示頭文件的編號，指示頭文件

7、的編號，YZ為指示為指示該例程在這類頭文件例程中的序號，取值從該例程在這類頭文件例程中的序號，取值從00或或01開開始，各例所側重的內容介紹如下：始，各例所側重的內容介紹如下： emp1*：Tools頭文件例子程序頭文件例子程序 emp2*：SeqLists頭文件例子程序頭文件例子程序 emp3*：SStack和和SQueue頭文件例子程序頭文件例子程序 emp4*：linklist頭文件例子程序頭文件例子程序 emp5*：Btrechar或或Btreint頭文件例子程序頭文件例子程序 emp6*：Trees頭文件例子程序頭文件例子程序 emp7*：Graph2頭文件例子程序頭文件例子程序 e

8、mp8*：Grary1頭文件例子程序頭文件例子程序 emp9*：Grary2頭文件例子程序頭文件例子程序 emps10*：Listses頭文件例子程序頭文件例子程序 95.實驗程序（實驗程序（Test子目錄）子目錄）部分實驗程序（主要是閱讀、填空及改錯類程序）放在部分實驗程序（主要是閱讀、填空及改錯類程序）放在子目錄子目錄Test中，每一程序的文件名格式為中，每一程序的文件名格式為TestXY_Z，其中其中XY表示實驗號，表示實驗號，Z表示題號。表示題號。6.演示程序（演示程序（Demo子目錄）子目錄） 數據結構課程中一些重要算法的演示程序，放在子目數據結構課程中一些重要算法的演示程序，放在子

9、目錄錄Demo中，每一程序的文件名的格式為中，每一程序的文件名的格式為DemoXY_Z。 10TCDS中幾個基本函數中幾個基本函數 實驗工具中的實驗工具中的tools.h提供了一些常用函數：提供了一些常用函數： 出錯處理語句：出錯處理語句： void error_exit(char *s);/ 提示出錯信息串提示出錯信息串s，并結束算法的運行。并結束算法的運行。 等待按鍵：等待按鍵：void wait(); / 等待按鍵再繼續(xù)其后續(xù)語句的執(zhí)行。等待按鍵再繼續(xù)其后續(xù)語句的執(zhí)行。 最大最小函數：最大最小函數： int max(int i1, int i2); / 返回整數返回整數i1,i2的最大的

10、值的最大的值 int min(int i1, int i2); / 返回整數返回整數i1,i2的最小的值的最小的值 11實驗一實驗一 單鏈表單鏈表一、實驗目的：一、實驗目的： 理解線性表的鏈式存儲結構。理解線性表的鏈式存儲結構。 熟練掌握動態(tài)鏈表結構及有關算法的設計。熟練掌握動態(tài)鏈表結構及有關算法的設計。 12二、實驗工具介紹二、實驗工具介紹 本實驗所用到的工具在頭文件本實驗所用到的工具在頭文件linklist.h中。中。（一）單鏈表的類型定義（一）單鏈表的類型定義struct node /結點類型結點類型 struct node * next; /下一結點的指針字段下一結點的指針字段 int

11、 data; /元素值字段元素值字段 /此處省略部分與實驗程序無關此處省略部分與實驗程序無關; typedef node * link; 13（二）單鏈表的操作：（二）單鏈表的操作： 建單鏈表：建單鏈表： Create_HSLList(L) /建立帶頭結點的單鏈表建立帶頭結點的單鏈表L Create_SLList(L) /建立無頭結點的單鏈表建立無頭結點的單鏈表L/執(zhí)行時，依次輸入各結點值，并以執(zhí)行時，依次輸入各結點值，并以-9999 作為結束符作為結束符。顯示單鏈表：顯示單鏈表：（參數（參數title的類型為的類型為char*） Display_HSLList(title，L) /顯示帶頭結

12、點的單鏈表顯示帶頭結點的單鏈表L Display_SLList(title，L) /顯示無頭結點的單鏈表顯示無頭結點的單鏈表L菜單方式建立并顯示鏈表：菜單方式建立并顯示鏈表： Get_HSLList(L)Get_SLList(L)按預定的訪問模式訪問結點：按預定的訪問模式訪問結點： Visite_SNode(P,i) （為為node *型，為整型）型，為整型）/用訪問模式用訪問模式i(1i4)來訪問單鏈表指針來訪問單鏈表指針P所指的結點。所指的結點。14三、基本演示三、基本演示: :Demo02_1 / Demo02_1 / 建單鏈表建單鏈表15四、實驗任務四、實驗任務 （一）閱讀程序：（一）閱讀程序：指出算法的功能，寫出運行結果，并指出算法的功能，寫出運行結果，并通過運行算法來驗證。通過運行算法來驗證。 test02_1 test02_1（二）算法填空：二）算法填空：在算法的空白處填入適當內容來完成在算法的空白處填入適當內容來完成算法，以實現(xiàn)指定的功能，并通過運行來驗證。算法，以實現(xiàn)指定的功能，并通過運行來驗證。 test02_4 / test02