数据结构实验一:线性表

实验一 线性表的顺序存储实验

一、实验目的

1、掌握用Visual C++6.0上机调试顺序表的基本方法

2、掌握顺序表的基本操作，插入、删除、查找等算法的实现

二、实验内容

1、顺序表基本操作的实现

[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。

报告内容为小组共同完成

一、实验目的
1、熟练掌握线性表的结构特点，掌握顺序表的基本操作。   
2、验证顺序表及其基本操作的实现；
3、理解算法与程序的关系，灵活运用顺序表算法。

二、实验内容
1、顺序表的建立，建立 n 个元素的顺序表；
2、对已建立的顺序表实现基本操作：包括初始化顺序表、表头插入元素、表尾插入元素、删除元素、查找元素、判断表是否为空、表的清空、表的销毁。
编写程序实现顺序表的各种基本运算：
（1）初始化顺序表L；
（2）表头插入元素；
（3）输出顺序表L及长度、大小；
（4）清空顺序表L;
（5）判断顺序表L是否为空；
  (6)  在顺序表表尾插入元素；
（6）输出顺序表L的第i个元素；
（9）输出顺序表L;
（10）删除L的第i元素；
（11）销毁顺序表L。

三、代码实现

#include<iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
typedef int Boolean;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量
#define LIST_INCREMENT 2 // 线性表存储空间的分配增量
//线性表的动态分配顺序存储结构
struct SqList
{
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
};

void InitList(SqList &L)
{ // 操作结果：构造一个空的顺序线性表L
    L.elem=new ElemType[LIST_INIT_SIZE];
//L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
exit(OVERFLOW); // 存储分配失败
L.length=0; // 空表长度为0
L.listsize=LIST_INIT_SIZE; // 初始存储容量
}
void DestroyList(SqList &L)
{ // 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
//free(L.elem);
    delete L.elem;
L.elem=NULL;
L.length=0;
L.listsize=0;
}
void ClearList(SqList &L)
{ // 初始条件：顺序线性表L已存在。操作结果：将L重置为空表
L.length=0;
}
Status ListEmpty(SqList L)
{ // 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE；否则返回FALSE
if(L.length==0)
return TRUE;
else
return FALSE;
}
int ListLength(SqList L)
{ // 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素的个数
return L.length;
}
Status GetElem(SqList L,int i,ElemType &e)
{ // 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值
if(i<1||i>L.length)
return ERROR;
e=*(L.elem+i-1);
return OK;
}

int LocateElem(SqList L,ElemType e)
{//在顺序表中查找值为e的元素，返回其序号
    for(int i=0;i<L.length;i++)
    if(*(L.elem+i)==e)
        return i+1;//查找成功，返回序号i+1
    return ERROR;//查找失败
}


Status ListInsert(SqList &L,int i,ElemType e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
ElemType *newbase,*q,*p;
if(i<1||i>L.length+1) // i值不合法
return ERROR;
if(L.length>=L.listsize) // 当前存储空间已满,增加分配
{
if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType))))
exit(OVERFLOW); // 存储分配失败
L.elem=newbase; // 新基址
L.listsize+=LIST_INCREMENT; // 增加存储容量
}
q=L.elem+i-1; // q为插入位置
for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移
*(p+1)=*p;
*q=e; // 插入e
++L.length; // 表长增1
return OK;
}
Status ListDelete(SqList &L,int i,ElemType &e)
{ // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p为被删除元素的位置
e=*p; // 被删除元素的值赋给e
q=L.elem+L.length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被删除元素之后的元素左移
*(p-1)=*p;
L.length--; // 表长减1
return OK;
}
int main()
{
SqList L;
ElemType e;
Status i;
int a,j,k;
InitList(L);
    cout<<"初始化后："<<"L.elem="<<L.elem<<" ";
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
for(j=1;j<=5;j++)
i=ListInsert(L,1,j);
printf("在L的表头依次插入1～5后：元素为：");
for(j=1;j<=5;j++) cout<<*(L.elem+j-1)<<" ";
    cout<<endl;
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
ClearList(L);
    cout<<"清空L后：";
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
i=ListEmpty(L);
//printf("L是否空：i=%d(1:是 0:否)\n",i);
    cout<<"L是否空：";
    if(i==1)cout<<"是"<<endl;
    else cout<<"否"<<endl;
for(j=1;j<=10;j++)
ListInsert(L,j,j);
cout<<"在L的表尾依次插入1～10后：元素为：";
for(j=1;j<=10;j++) cout<<*(L.elem+j-1)<<" ";
    cout<<endl;
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
ListInsert(L,1,0);
cout<<"在L的表头插入0后：元素为：";
for(j=1;j<=ListLength(L);j++) cout<<*(L.elem+j-1)<<" ";// ListLength(L)为元素个数
    cout<<endl;
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
GetElem(L,5,e);
    cout<<"第5个元素的值为"<<e<<endl;

    cout<<"输入元素值：";
    cin>>a;
    cout<<"元素"<<a<<"的序号为"<< LocateElem(L,a)<<endl;
k=ListLength(L); // k为表长
for(j=k+1;j>=k;j--)
{
i=ListDelete(L,j,e); // 删除第j个数据
if(i==ERROR)
    cout<<"删除第"<<j<<"个元素失败\n";
else
    cout<<"删除第"<<j<<"个元素成功，其值为"<<e<<endl;
}
    cout<<"依次输出L的元素：";
    for(j=1;j<=ListLength(L);j++) // ListLength(L)为元素个数
    cout<<*(L.elem+j-1)<<" ";
    cout<<endl;
DestroyList(L);
    cout<<"销毁L后："<<"L.elem="<<L.elem<<" ";
    cout<<"L.length="<<L.length<<" ";
    cout<<"L.listsize="<<L.listsize<<endl;
}

四、实验难点
1、顺序表结构定义
为合理地利用空间，采用动态分配的存储结构。构造struct SqList顺序存储，定义ElemType *elem为存储空间基址，定义长度length，存储空间的初始分配量，存储空间的分配增量以及当前存储容量listsize。
2、初始化顺序表
即构造一个长度为0的顺序表L。要判断储存分配是否成功(L.elem)。
3、在顺序表中插入元素
要判断插入的位置是否合法，即插入的位置要在1和表长加1之间；要判断顺序表的存储空间是否已满，如果已满。就为其增加分配容量。在元素插入位置及之后的元素要一次往后移动一个位置，并且从最后一个元素开始移动，利用for循环实现；在完成元素插入后，表长要加1。
4、在顺序表中删除元素
实现和在顺序表中删除元素大同小异，需要注意的是元素从删除位置之后的一位开始依次前移，最后表长减1。
5、在顺序表中查找元素
在顺序表中查找值为e的数据元素，返回e的序号，需要从第一个元素起，依次和e相比较，查找成功返回序号i+1，失败返回0。

五、实验结果
运行程序：
初始化后：L.elem=0x10052c7e0 L.length=0 L.listsize=10
在L的表头依次插入1～5后：元素为：5 4 3 2 1 
L.length=5 L.listsize=10
清空L后：L.length=0 L.listsize=10
L是否空：是
在L的表尾依次插入1～10后：元素为：1 2 3 4 5 6 7 8 9 10 
L.length=10 L.listsize=10
在L的表头插入0后：元素为：0 1 2 3 4 5 6 7 8 9 10 
L.length=11 L.listsize=12
第5个元素的值为4
输入元素值：5
元素5的序号为6
删除第12个元素失败
删除第11个元素成功，其值为10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9 
销毁L后：L.elem=0x0 L.length=0 L.listsize=0
Program ended with exit code: 0

六、实验心得
收获：在顺序表的存储时如果用数组存储顺序表，就意味着要分配固定长度的数组空间，必须要确定数组的长度，即存放线性表的数组空间的长度。而不采用固定数组作为线性表的存储结构，而采用动态分配的存储结构，这样可以合理地利用空间，使长表占用的存储空间多， 短表占用的存储空间少。故动态分配的顺序表存储结构。顺序表取值算法的时间复杂度为O(1)，执行效率高，适合频繁获取数据的场景。在写程序的过程中，线性表的顺序结构的相关代码已经渐渐熟悉，基本算法思想学习得到进一步的复习与巩固。在后来的调试过程中，又因各种各样的错误和不断解决问题而丰富了个人编程的经历和经验和提高个人解决问题的能力。对于已经忘记的知识，在进行实验过程中查阅书籍，使得知识得到复习与巩固。