数据结构实验指导实验一 抽象数据类型一 实验任务抽象数据类型Triplet的表示和实现。二 实验目的1）理解和掌握抽象数据类型的概念。2）熟悉数据结构的定义及基本操作。3）实践系统程序开发的规范步骤。三 实验原理1抽象数据类型的定义 抽象数据类型（ADT，Abstract Data Type）由具有一定关系的一组数据和定义在该组数据上的操作组成。抽象数据类型为我们提供了一个描述数据结构的架构。抽象数据类型的定义一般包括数据定义和操作定义两个部分。一个含抽象数据类型的模块通常包含定义、表示和实现3个部分。抽象数据类型的形式表示为如下三元组：（ D, S, O ）其中：D是数据对象，S是D上的关系集合，O是D上的基本操作集合。我们习惯上把抽象数据类型表示成如下格式：ADT 抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名例如，抽象数据类型Triplet的三元组定义：ADT Triplet 数据对象： D=e1, e2, e3 | e1, e2, e3 ElemSet 数据关系： R1= , 基本操作： InitTriplet ( & T, v1, v2, v3 ) 操作结果：构造了三元组T，元素e1, e2 和e3分别被赋以参数v1, v2 和v3的值 DestroyTriplet ( & T) 操作结果：三元组T被销毁。 Get ( T, i , &e ) 初始条件：三元组T已存在，1 i 3。 操作结果：用e返回T的第i元的值。 Put(&T，i，e) 初始条件：三元组T已经存在，1 i 3。 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条件：三元组T已存在。 操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。 IsDescending(T) 初始条件：三元组T已存在。 操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。 Max( T, &e) 初始条件：三元组T已存在。 操作结果：用e返回T中三个元素的最大值。 Min( T, &e) 初始条件：三元组T已存在。 操作结果：用e返回T中三个元素的最小值。 ADT Triplet 2抽象数据类型的表示与实现我们可以通过固有数据类型来表示和实现抽象数据类型，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。我们约定以C语言作为数据结果的描述工具。例如，抽象数据类型Triplet的表示和实现如下：typedef ElemType * Triplet;/基本操作的实现Status InitTriplet ( Triplet & T, ElemType v1, ElemType v2, ElemType v3 ) /构造三元组T，依次设置T 的三个元素的初值为v1, v2和v3。T=( ElemType * ) malloc ( 3*sizeof ( ElemType ) ) ;if ( ! T ) exit ( OVERFLOW ) ;T 0 = v1; T 1 = v2; T 2 = v3;return OK !Status DestroyTriplet ( Triplet & T) free ( T ) ; T=NULL ;return OK !Status Get ( Triplet T, int i , ElemType & e ) if ( i 3 ) return ERROR;e = T i - 1 ; return OK !Status Put ( Triplet & T , int i , ElemType e ) if ( i 3 ) return ERROR;T i - 1 = e; return OK !四 实验设备、仪器、工具及资料 微机、VC五 实验内容通过C语言实现一个可无误运行的完整程序，完成抽象数据类型Triplet的表示和实现。要求：程序运行时显示基本操作的菜单，由用户选择执行相应操作（如：可利用switch语句等），以此整合Triplet的各基本操作，实现程序设计。六 实验步骤（1）实验预习1）预习本实验原理中关于抽象数据类型Triplet的定义、表示及实现。2）熟悉程序运行环境VC的使用。（2）实验步骤1）问题分析与系统的结构设计。充分地分析和理解此实验项目，弄清要求作什么，限制条件是什么。按照以数据结构为中心的原则划分模块。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。2）详细设计和编码。详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码时，可以对详细设计的结果进一步求精，用高级语言表示出来。3）在VC环境下调试程序。七 实验报告要求实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：1）需求分析及规格说明：问题描述，求解的问题是什么。2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互关系。3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调用关系。4）调试报告。5）本实验项目的程序清单及运行结果。八 思考题 为什么用抽象数据类型描述数据结构？实验二 线性表一 实验任务1）线性表的顺序表示和实现2）线性表的链式结构表示和实现二 实验目的1）掌握线性表的类型定义和结构特点。2）掌握线性表的顺序存储表示、链式存储表示及其C语言实现。3）掌握顺序表的各种基本操作的实现。4）掌握线性表在链式存储结构上的各种操作。三 实验原理 1线性表的逻辑结构及特性所谓线性表（Linear_List），就是n（n0）个数据元素的集合 a1, a2, , an ，这些数据元素之间有逻辑上的线性关系。线性表的抽象数据类型定义如下：ADT List 数据对象：D=ai| aiElemSet, i=1,2, ,n, n0数据关系：R1= | ai1, aiD, i =2, n基本操作：CreatList(&L) 操作结果：生成一个空的线性表L。ListLength(L) 初始条件：线性表L已存在。操作结果：返回L中数据元素个数。ListInsert(&L, i, e) 初始条件：线性表L已存在，1iListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L, i, &e)初始条件：线性表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。GetElem(L, i, &e) 初始条件：线性表L已存在，1iListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L, e, compare( ) 初始条件：线性表L已存在，compare( )是数据元素判定函数。 操作结果：返回L中第1个与e满足关系compare( )的数据元素的位序。若这样的数据元素不存在，则返回值为0。ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。ClearList(&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ADT List2线性表的顺序表示线性表的顺序表示就是利用一组地址连续的内存空间依次存储线性表的各个数据元素，即以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。由于顺序存储结构是一种随机存取的存储结构，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序存储结构所需要的存储空间。可通过定义结构体类型来实现线性表的动态分配顺序存储结构。具体数据类型描述如下：#define MAXLEN 100#define LIST_INCREASE 10 /线性表存储空间的动态分配增量typedef structElemType *list; /线性表的存储空间的基地址int length; /线性表的当前长度int maxsize; /线性表当前分配的存储容量List_Sq;3线性表的链式结构链式存储结构具有以下特点：不要求逻辑上相邻的元素在物理结构上也相邻；允许迅速简单地插入或删除结点，而不必移动大量元素；但只能顺序存取而不能随机存取线性表中任一元素。线性表的链式存储结构可通过单链表来实现。此时，线性表中的每个元素对应单链表中的一个结点，每个结点的数据域存储线性表的数据元素，每个结点的指针域存储其后继元素所在结点的地址，可以通过每个结点的指针域访问到其后继结点，如图2.1所示。 图2.1 线性链表示例因此，单链表中每个结点都是由包含这个数据元素的信息和一个指示其直接后继的指针组成的一个结构体类型，具体描述如下：typedef struct LNodeElemType data;struct LNode * next; LNode, * List_Link;每个单链表的头指针L是List_Link型的变量，指向链表中第一个结点。由表头指针出发可以依次访问到每个结点，存取相应的数据元素值。线性表中数据元素间的线性关系都可以通过单链表中结点指针域的链接关系反映出来。当L=NULL时，意味着所表示的线性表为“空”表，其长度n为“零”。四 实验设备、仪器、工具及资料 微机、VC五 实验内容（1）实验任务1：顺序表的表示与实现请编制C程序，利用顺序存储方式来实现下列功能：1）建立主程序菜单，使之具有建立线性表、插入元素、删除元素、查找元素、销毁线性表、结束程序运行等菜单项。2）根据键盘输入数据生成一个线性表，并输出该原始线性表。3）根据屏幕菜单的提示选择，进行数据插入、删除、查找等操作。4）最后，输出修改之后的线性表并结束程序的运行。（2）实验任务2：线性表的链式存储表示与实现请编制C程序，利用链式存储方式来实现下列功能：1）建立主程