实验介绍及实验一

1、1数据结构实验数据结构实验 实验指导书：实验指导书：计算机科学与技术专业软件系列课程实践教程计算机科学与技术专业软件系列课程实践教程数据结构实验教程数据结构实验教程 胡学钢胡学钢 主编主编 高等教育出版社高等教育出版社2上机时间 七、八、十周 周六上午 8:0011:20 五机房3 实验报告：实验报告： 实验名称实验名称 实验任务实验任务 实验结果（及分析总结）实验结果（及分析总结） 4数据结构实验工具数据结构实验工具TCDS简介简介 TCDS对数据结构课程中主要的数据结构：顺序表、顺对数据结构课程中主要的数据结构：顺序表、顺序栈、顺序队列、单链表、双链表、二叉树（包括线序栈、顺序队列、单链表

2、、双链表、二叉树（包括线索二叉树）、树（包括森林）、图、一维数组、二维索二叉树）、树（包括森林）、图、一维数组、二维数组等结构，提供了许多可供实验用的功能，主要分数组等结构，提供了许多可供实验用的功能，主要分为对结构的类型定义、建立、图形化显示和跟踪调试为对结构的类型定义、建立、图形化显示和跟踪调试等几类，另外还编制了数据结构中重要算法的演等几类，另外还编制了数据结构中重要算法的演示程序。示程序。 5实验工具系统的组成实验工具系统的组成 1. Turbo C 语言集成环境系统（语言集成环境系统（TC.*等）、安装等）、安装程序及一些标准头文件。程序及一些标准头文件。62. 工具库：工具库：本套

3、实验工具系统是以本套实验工具系统是以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. 数据结构文件：数据结构文件：为节省实验时间，系统提

5、供了将数据为节省实验时间，系统提供了将数据结构存入磁盘文件和从文件中读取结构的功能，并且结构存入磁盘文件和从文件中读取结构的功能，并且还提供了一些预制的数据结构文件：还提供了一些预制的数据结构文件：扩展名扩展名 适用结构适用结构 所在目录所在目录 支持文件支持文件. .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(); / 等待按键再继续其后续语句的执行。等待按键再继续其后续语句的执行。 最大最小函数：最大最小函数： int max(int i1, int i2); / 返回整数返回整数i1,i2的最大的

10、值的最大的值 int min(int i1, int i2); / 返回整数返回整数i1,i2的最小的值的最小的值 11实验一实验一 单链表单链表一、实验目的：一、实验目的： 理解线性表的链式存储结构。理解线性表的链式存储结构。 熟练掌握动态链表结构及有关算法的设计。熟练掌握动态链表结构及有关算法的设计。 12二、实验工具介绍二、实验工具介绍 本实验所用到的工具在头文件本实验所用到的工具在头文件linklist.h中。中。（一）单链表的类型定义（一）单链表的类型定义struct node /结点类型结点类型 struct node * next; /下一结点的指针字段下一结点的指针字段 int

11、 data; /元素值字段元素值字段 /此处省略部分与实验程序无关此处省略部分与实验程序无关; typedef node * link; 13（二）单链表的操作：（二）单链表的操作： 建单链表：建单链表： Create_HSLList(L) /建立带头结点的单链表建立带头结点的单链表L Create_SLList(L) /建立无头结点的单链表建立无头结点的单链表L/执行时，依次输入各结点值，并以执行时，依次输入各结点值，并以-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（二）算法填空：二）算法填空：在算法的空白处填入适当内容来完成在算法的空白处填入适当内容来完成算法，以实现指定的功能，并通过运行来验证。算法，以实现指定的功能，并通过运行来验证。 test02_4 / test02