数据结构实验一
1、实验目的
? ?
掌握线性表的逻辑特征
掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算
2、实验内容：
建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；
1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：
? ? ? ? ? ? ? ? ? ? ?
创建一个新的顺序表，实现动态空间分配的初始化；
根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；
根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)； 利用最少的空间实现顺序表元素的逆转； 实现顺序表的各个元素的输出；
彻底销毁顺序线性表，回收所分配的空间；
对顺序线性表的所有元素删除，置为空表； 返回其数据元素个数；
按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；
按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；
判断顺序表中是否有元素存在，对判断结果进行返回；
.编写主程序，实现对各不同的算法调用。
2．实现要求：
? ?
“初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；
“位置插入算法” 的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；
操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1； ? “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ； 操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ； ? “逆转算法”的初始条件：顺序线性表L 已存在；
操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序 表的元素进行交换；
? “输出算法”的初始条件：顺序线性表L 已存在； 操作结果：依次对L 的每个数据元素进行输出； ? “销毁算法”初始条件：顺序线性表L 已存在；
操作结果：销毁顺序线性表L；
? “置空表算法”初始条件：顺序线性表L 已存在； 操作结果：将L 重置为空表；
? “求表长算法”初始条件：顺序线性表L 已存在； 操作结果：返回L 中数据元素个数； ?
“按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)
操作结果：返回L 中第i 个数据元素的值
? “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e； 操作结果：返回L 中数据元素值为e 的元素位置；
“判表空算法”初始条件：顺序线性表L 已存在；
操作结果：若L 为空表，则返回TRUE，否则返回FALSE；
?
分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
3、实验指导
一个简单程序通常主要由三部分构成：
1、常量定义（#define），类型重定义(typedef)及函数原型(#include)声明；还有针对每一种数据结构的类型定义。 2、算法函数，对于顺序表，每一个函数具有独立的功能，组合成为模块的形式，如ListInit_Sq、 ListInsert_Sq、ListDelete_Sq、ListReverse_Sq、ListPrint_Sq 等。 3、主函数（main）。
【说明1】――顺序表的定义与操作
1．可以将这三部分组合在一个文件中，也可以按照项目的方式（多个不同的文件组合在一起，共同完成一个功能）进行组织（本课程的实验强烈推荐这种形式），如将本课程后续所有算法几乎都要使用的常量定义（#define）和系统函数原型定义(#include)声明组合成一个文件，存储为一个头文件（取名为pubuse.h），只需建立一次，以后凡涉及到相关的内容，只需在你的文件的前面加上一条#include “pubuse. h”即可，无需重复输入。
2．对于类型定义，由于每一种数据结构的定义都不一样，因此要进行专门的类型定义，也可以将数据结构的定义组合成为一个文件，存储为一个头文件（如线性表的顺序存储结构定义取名为seqlistDef. h），只需建立一次，以后凡涉及到关于顺序表操作的相关内容，一定要在你的文件的前面加上一条#include“seqlistDef. h”即可，无需重复进行顺序存储结构的定义。
3．关于实验内容要完成的操作，一般都以独立的算法出现，关于某类数据结构的各种不同算法函数组合在一个文件之中，存储为一个头文件（如取名为seqlistAlgo. h），以后凡涉及到要使用本文件中的顺序表算法，一定要在你的文件的前面加上一条#include “seqlistAlgo. h”即可，无需重复定义类似的算法，就象使用系统函数一样，只需进行函数原型的声明即可。
4．还应包含一个main 函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为seqlistUse. cpp）。
5．为了对实际问题更加通用和适应，在算法中使用的数据类型为ElemType，为了与实际数据类型一致，一般要将ElemType 用typedef 重定义：如实际问题中顺序表的每个元素是整型，则使用typedef int ElemType；定义语句；如实际问题中顺序表的每个元素是单精度实数的话，使用typedef float ElemType；定义语句。
4、基本实验的参考程序
线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）
(1) 文件1： pubuse. h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文件。 #include
#include
#include
#include
#include
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/ typedef int Status； /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ typedef int Boolean； /* Boolean 是布尔类型,其值是TRUE 或FALSE */
(2) 文件2：seqlistDef. h 进行线性表的动态分配顺序存储结构的表示 #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量*/ typedef struct {
ElemType *elem； /* 存储空间基址*/ int length； /* 当前长度*/
int listsize； /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList；
(3)文件3：seqlistAlgo. h 进行线性表顺序存储结构的基本实验算法定义 Status ListInit_Sq(SqList &L) /* 算法2. 3 */
{ /* 操作结果：构造一个空的顺序线性表*/
L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))； if(!L. elem)
exit(OVERFLOW)； /* 存储分配失败*/ L. length=0； /* 空表长度为0 */
L. listsize=LIST_INIT_SIZE； /* 初始存储容量*/ return OK；