《数据结构》实验指导书(信管13用).doc

韶关学院信息科学与工程学院 数据结构实验指导书 （龙腾芳编） 实验一 顺序表实现及应用 [实验目的] 1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。 [实验内容] 实验1．顺序表的实践。 在参考程序的main()函数的注解部分有实验的要求，请按要求完成实验 [实验要点及说明] 线性表（linear list）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。 其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。 通常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号， ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。 顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。 可定义顺序表如下： typedef struct { ElemType *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList; [参考程序] // /****************** 实验一、 顺序表的操作 ************************/ // 以下程序已有基本的函数，可以运行，先仔细阅读以下代码段及注解， //然后请按要求补充完整，完成其余要求的操作。 // 2013信管（1）（2）用 // 教材：邮电出版的严蔚敏《数据结构》（C语言版） #include iostream.h #include stdlib.h #define MAXSIZE 100 //最大长度 #define OK 1 #define ERROR 0 #define OVERFLOW -2 /*****************************************************************/ typedef int Status; typedef int ElemType ; /************************表的结构*********************************/ typedef struct { ElemType *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList; Status InitList_Sq1(SqList L){ //构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; } Status InitList_Sq2(SqList *L){ //构造一个空的顺序表L L- elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L- elem) exit(OVERFLOW); //存储分配失败 L- length=0; //空表长度为0 return OK; } /******************************撤销表***************************/ void DestroyList(SqList L) { if (L.elem) delete[]L.elem; //释放存储空间 } /********************************清空表***********************/ void ClearList(SqList L) { L.length=0; //将线性表的长度置为0 } /************************