實(shí)驗(yàn)介紹及實(shí)驗(yàn)一

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

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

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

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

5、供了將數(shù)據(jù)為節(jié)省實(shí)驗(yàn)時(shí)間，系統(tǒng)提供了將數(shù)據(jù)結(jié)構(gòu)存入磁盤文件和從文件中讀取結(jié)構(gòu)的功能，并且結(jié)構(gòu)存入磁盤文件和從文件中讀取結(jié)構(gòu)的功能，并且還提供了一些預(yù)制的數(shù)據(jù)結(jié)構(gòu)文件：還提供了一些預(yù)制的數(shù)據(jù)結(jié)構(gòu)文件：擴(kuò)展名擴(kuò)展名 適用結(jié)構(gòu)適用結(jié)構(gòu) 所在目錄所在目錄 支持文件支持文件. .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 圖結(jié)構(gòu)圖結(jié)構(gòu) Graphs Graph2Graphs Graph2.arr .arr 一維數(shù)組、二維數(shù)組，順序表，順序棧，順序隊(duì)列一維數(shù)組、二維數(shù)組，順序表，順序棧，順序隊(duì)列Arrays Grary1,Grary2,SeqLists,Sstack,SQueueArrays Grary1,Grary2,SeqLists,Sstack,SQueue84. 例子程序（例子程序（emps子目錄）：子目錄）：文件名形式為文件名形式為empX_YZ ，其中其中X的取值為的取值為110，指示頭文件的編號，指示頭文件

7、的編號，YZ為指示為指示該例程在這類頭文件例程中的序號，取值從該例程在這類頭文件例程中的序號，取值從00或或01開開始，各例所側(cè)重的內(nèi)容介紹如下：始，各例所側(cè)重的內(nèi)容介紹如下： 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.實(shí)驗(yàn)程序（實(shí)驗(yàn)程序（Test子目錄）子目錄）部分實(shí)驗(yàn)程序（主要是閱讀、填空及改錯類程序）放在部分實(shí)驗(yàn)程序（主要是閱讀、填空及改錯類程序）放在子目錄子目錄Test中，每一程序的文件名格式為中，每一程序的文件名格式為TestXY_Z，其中其中XY表示實(shí)驗(yàn)號，表示實(shí)驗(yàn)號，Z表示題號。表示題號。6.演示程序（演示程序（Demo子目錄）子目錄） 數(shù)據(jù)結(jié)構(gòu)課程中一些重要算法的演示程序，放在子目數(shù)據(jù)結(jié)構(gòu)課程中一些重要算法的演示程序，放在子

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

10、值的最大的值 int min(int i1, int i2); / 返回整數(shù)返回整數(shù)i1,i2的最小的值的最小的值 11實(shí)驗(yàn)一實(shí)驗(yàn)一 單鏈表單鏈表一、實(shí)驗(yàn)?zāi)康模阂?、?shí)驗(yàn)?zāi)康模?理解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。理解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)。熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)。 12二、實(shí)驗(yàn)工具介紹二、實(shí)驗(yàn)工具介紹 本實(shí)驗(yàn)所用到的工具在頭文件本實(shí)驗(yàn)所用到的工具在頭文件linklist.h中。中。（一）單鏈表的類型定義（一）單鏈表的類型定義struct node /結(jié)點(diǎn)類型結(jié)點(diǎn)類型 struct node * next; /下一結(jié)點(diǎn)的指針字段下一結(jié)點(diǎn)的指針字段 int

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

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