实验一 线性表的顺序表示和实现.doc

实验一线性表的顺序表示和实现
实验内容
1.线性表的顺序存储结构
C语言中的顺序表存储结构描述：
—————线性表的顺序存储结构————————
#defineMAXSIZE100/*顺序表允许的最大空间量*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*ElemType为抽象数据类型*/
intlength;/*当前顺序表长度*/
}SqList;

2.顺序表的基本操作
（1）初始化操作：为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length设为0。
（2）清空操作：将顺序表的长度设为0，是表为空表
（3）销毁操作：将顺序表所占用的空间释放
（4）定位操作：根据给定的数据元素e，在顺序表中找出和e相等的数据元素的位序，如果这样的数据元素不存在，则返回0
（5）插入操作：在顺序表的第i个数据元素前插入一个新的数据元素e，注意，在插入前必须判断i的值域，而在插入操作后必须使顺序表的长度增1.
（6）删除操作：删除顺序表中第i个数据元素，并且用e返回其值。注意，在删除操作前必须判断i的值域，而在删除操作后必须使顺序表的长度减1。
（7）输出操作：即将顺序表中各个元素按下标次序输出。

3.顺序表操作实现的操作步骤
（1）实现将顺序表的存储结构和基本操作程序代码。
（2）实现main主函数。

4.程序代码完整清单
#include<stdio.h>
#include<malloc.h>
#defineMaxSize50/*顺序表允许的最大空间量*/
typedefcharElemType;/*顺序表中元素类型为char*/
typedefstruct
{
ElemTypeelem[MaxSize];
intlength;
}SqList;/*顺序表结构定义*/
//基本操作函数声明
voidInitList(SqList*&L);/*初始化线性表*/
voidDestroyList(SqList*L);/*销毁线性表*/
intListEmpty(SqList*L);/*清空线性表*/
intListLength(SqList*L);/*求表长*/
voidDispList(SqList*L);/*输出表*/
intGetElem(SqList*L,inti,ElemType&e);/*取表中元素*/
intLocateElem(SqList*L,ElemTypee);/*定位表中元素*/
intListInsert(SqList*&L,inti,ElemTypee);/*插入元素*/
intListDelete(SqList*&L,inti,ElemType&e);/*删除表中元素*/
voidmain()
{
SqList*L;
ElemTypee;
printf("(1)初始化顺序表L\n");
InitList(L);
printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("(3)输出顺序表L:");
DispList(L);
printf("(4)顺序表L长度=%d\n",ListLength(L));
printf("(5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("(6)顺序表L的第3个元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));
printf("(8)在第4个元素位置上插入f元素\n");
ListInsert(L,4,'f');
printf("(9)输出顺序表L:");
DispList(L);
printf("(10)删除L的第3个元素\n");
ListDelete(L,3,e);
printf("(11)输出顺序表L:");
DispList(L);
printf("(12)释放顺序表L\n");
DestroyList(L);
}

voidInitList(SqList*&L)/*初始化线性表操作结果：构造一个空的顺序线性表*/
{
L=(SqList*)malloc(sizeof(SqList));
L->length=0;
}
voidDestroyList(SqList*L)/*释放线性表操作结果：释放空间*/
{
free(L);
}
intListEmpty(SqList*L)/*清