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

实验一 线性表的顺序表示和实现
实验内容
1.线性表的顺序存储结构
C语言中的顺序表存储结构描述：
—————线性表的顺序存储结构————————
#define MAXSIZE 100 /*顺序表允许的最大空间量*/
typedef struct
{
ElemType elem[MAXSIZE]; /* ElemType为抽象数据类型*/
int length; /*当前顺序表长度*/
} 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>
#define MaxSize 50 /*顺序表允许的最大空间量*/
typedef char ElemType; /*顺序表中元素类型为char*/
typedef struct
{
ElemType elem[MaxSize];
int length;
} SqList; /*顺序表结构定义 */
//基本操作函数声明
void InitList(SqList *&L); /*初始化线性表*/
void DestroyList(SqList *L); /*销毁线性表*/
int ListEmpty(SqList *L); /*清空线性表*/
int ListLength(SqList *L); /*求表长*/
void DispList(SqList *L); /*输出表*/
int GetElem(SqList *L,int i,ElemType &e); /*取表中元素*/
int LocateElem(SqList *L, ElemType e); /*定位表中元素*/
int ListInsert(SqList *&L,int i,ElemType e); /*插入元素*/
int ListDelete(SqList *&L,int i,ElemType &e); /*删除表中元素*/
void main()
{
SqList *L;
ElemType e;
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);
}

void InitList(SqList *&L) /*初始化线性表 操作结果：构造一个空的顺序线性表*/
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
void DestroyList(SqList *L) /*释放线性表 操作结果：释放空间*/
{
free(L);
}
int ListEmpty(SqList *L) /*清空线性表 操作结果：将L置为空表*/
{
return(L->length==0);
}
int ListLength(SqList *L) /*求表长 操作结果：返回表中元素个数*/
{
return(L->length);
}
void DispList(SqList *L) /*输出表 操作结果：若顺序表非空，则输出顺序表中所有*/
{ /*元素的值，否则为空操作*/
int i;
if (ListEmpty(L)) return;
for (i=0;i<L->length;i++)
printf("%c",L->elem[i]);
printf("\n");
}
int GetElem(SqList *L,int i,ElemType &e) /*取表中元素 操作结果：用e返回L中的第i*/
{ /*个元素的值*/
if (i<1 || i>L->length)
return 0;
e=L->elem[i-1];
return 1;
}
int LocateElem(SqList *L, ElemType e) /*定位表中元素 操作结果：返回L中第1个*/
{ /* 与e相等的元素位序*/
int i=0;
while (i<L->length && L->elem[i]!=e) i++;
if (i>=L->length)
return 0;
else
return i+1;
}
int ListInsert(SqList *&L,int i,ElemType e) /*向表中插入元素 操作结果：在L 中第i个*/
{ /*位置前插入新的数据元素e，L的长度加1*/
int j;
if (i<1 || i>L->length+1)
return 0;
i--; /*将顺序表位序转化为elem下标*/
for (j=L->length;j>i;j--) /*将elem[i]及后面元素后移一个位置*/
L->elem[j]=L->elem[j-1];
L->elem[i]=e;
L->length++; /*顺序表长度增1*/
return 1;
}
int ListDelete(SqList *&L,int i,ElemType &e) /*将表中元素删除 操作结果：将L 中第i
{ /*个位置的元素删除，L的长度减1

int j;
if (i<1 || i>L->length)
return 0;
i--; /*将顺序表位序转化为elem下标*/
e=L->elem[i];
for (j=i;j<L->length-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
return 1;
}

5. 运行结果清单
(1)初始化顺序表L
(2)依次采用尾插法插入a，b，c，d，e元素
(3)输出顺序表L：abcde
(4)顺序表L长度=5
(5)顺序表L为非空
(6)顺序表L 的第3个元素=c
(7)元素a的位置=1
(8)在第4个元素位置上插入f元素
(9)输出顺序表L：abcfde
(10)删除L的第3个元素
(11)输出顺序表L：abfde
(12)释放顺序表L