数据结构顺序表的实现

一、实验目的

1. 熟练掌握顺序表的类型定义和基本操作算法（以建立、插入、删除、遍历、排序和归并等操作为重点）的实现。

2. 通过实验加深对C语言的使用（特别是函数、数组、结构体和指针）。

3. 掌握模块化程序设计方法。

二、预备知识

1. 顺序表的类型定义

//线性表存储空间的初始分配量 #define LIST_Init_Size 100 //线性表存储空间的分配增量 #define LISTINCREMENT 10 typedef struct{

ElemType *elem; //存储区域基地址 int length; //当前有效长度 int listsize； //当前分配的存储容量 } SqList, *PSqList;

2. 顺序表的基本操作

1）初始化线性表InitList(&L)

该运算的结果是构造一个空的线性表L，为线性表分配存储空间用于存放数据元素。

2）销毁线性表DestroyList(&L )

该运算的结果是释放线性表L占用的内存空间。 3）判定是否为空表ListEmpty(L)

该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。 4）求线性表的长度ListLength(L)

该运算返回顺序表L的长度。实际上只需返回length成员的值即可。 5） PriorElem( L, cur_e, &pre_e )

该运算返回给定数据元素的前驱数据元素的值 6）NextElem( L, cur_e, &next_e )

该运算返回给定数据元素的后继数据元素的值 7）输出线性表DispList(L)

该运算当线性表L不为空时,顺序输出L中各数据元素的值。 8）求某个数据元素值GetElem(L,i,&e)

该运算返回L中第 i(1≤i≤ListLength(L))个元素的值,存放在e中。 8）按元素值查找LocateElem(L,e)

该运算顺序查找第1个值域与e相等的数据元素的序号。若这样的元素不存在,则返回值为0。

9）插入数据元素ListInsert(&L,i,e)

该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素e。 10） 删除数据元素ListDelete(&L,i,&e)

该运算删除顺序表L的第i(1≤i≤ListLength(L))个元素。 11）清空线性表ClearList( &L )

删除线性表L中的所有数据元素，但不释放已分配给线性表的存储空间。

2. 两个有序表的归并算法

void MergeList(SqList La, SqList Lb, PSqList PLc) {

InitList(PLc); // 构造空的线性表 Lc i = j = 1; k = 1; La_len = ListLength(La); Lb_len = ListLength(Lb);

while ((i <= La_len) && (j <= Lb_len)) // La 和 Lb 均不空 {

GetElem(La, i, ai); GetElem(Lb, j, bj);

if (ai <= bj) { // 将 ai 插入到 Lc 中 ListInsert(Lc, k++, ai); i ++; }

else { // 将 bj 插入到 Lc 中 ListInsert(Lc, k++, bj); j ++; } }

while (i<=La_len) //若La不空, 插入La中剩余的数据元素 {

GetElem(La, i++, ai); ListInsert(Lc, k++, ai); }

while (j<=Lb_len) //若 Lb不空, 插入Lb中剩余的数据元素 {

GetElem(Lb, j++, bj); ListInsert(Lc, k++, bj); } }

三、实验题目

1. 用C语言实现顺序表的ADT（包括顺序表的类型定义和基本操作）,假定数据元素的类型为整型。 2.设计一个测试应用程序完成如下功能： ⑴建立顺序L；

⑵依次插入数据元素13,5,27,9,32,123,76,98,54,87； ⑶输出顺序表L； ⑷输出顺序表L的长度； ⑸判断顺序表L是否为空； ⑹输出顺序L的第3个数据元素； ⑺输出数据元素76的位置； ⑻在第4个位置上插入数据元素56； ⑼输出顺序表L的长度； ⑽删除顺序表L的第7个元素； ⑾输出顺序表L； ⑿销毁顺序表L；

以上为必做题。下面为选做题。

⒀建立两个有序的顺序表La和Lb，并分别向顺序表La和Lb插入为m个和n个有序的整数；（注意：m和n的大小，具体的整数值都由自己确定） ⒁输出顺序表La和Lb；

⒂将顺序表La和Lb归并为新的有序表Lc；

⒃输出顺序表Lc；

⒄销毁顺序表La、Lb和Lc。

四、实验要求

1. 顺序表类型定义和基本操作函数声明放在Sqlist.h文件中； 2. 基本操作函数的实现放在Sqlist.c文件中； 3. 测试应用程序放在SqListTestApp.c文件中。