实验名称
顺序表的基本操作
实验日期
2019.9.23
实验成绩
1、实验目的：
1．掌握线性表的顺序存储结构的表示和实现方法。
2．掌握顺序表基本操作的算法实现。
3．了解顺序表的应用。
2、实验内容：
    编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为 char），
并在此基础上设计一个主程序完成如下功能：
（1）初始化顺序表 L；
（2）依次采用尾插法插入 a、b、c、d、e 元素；
（3）输出顺序表 L；
（4）输出顺序表 L 的长度；
（5）判断顺序表 L 是否为空；
（6）输出顺序表 L 的第 3 个元素；
（7）输出元素 a 的位置
（8）在第 4 个元素位置上插入 f 元素
（9）输出顺序表 L；
（10）删除 L 的第 3 个元素；
（11）输出顺序表 L；
（12）释放顺序表 L。
3、核心算法或代码片段：
核心算法：
1．顺序表插入操作的基本步骤：要在顺序表中第 i 个数据元素之前插入一
个数据元素 x，首先要判断插入位置 i 是否合法，假设线性表的长为 n，则 i 的
合法值范围： 1≤i≤n+1，若是合法位置，就再判断顺序表否满，如果满，则增
加空间或结束操作，如果不满，则将第 i 个数据元素及其之后的所有数据元素都
后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x 插入到该位
置上，最后将线性表的长增加 1。
2．顺序表删除操作的基本步骤：要删除顺序表中第 i 个数据元素，首先仍然
要判断 i 的合法性， i 的合法范围是 1≤i≤n，若是合法位置，则将第 i 个数据
元素之后的所有数据都前移一个位置，最将线性表长减 1。
3．顺序表查操作的基本步骤：要在顺序表中查一个给定值的数据元素
则可以采用顺序查的方法，从表中第 1 个数据元素开始依次将值与给定值进行
比较，若相等则返回该数据元素在顺序表中的位置，否则返回 0 值。
线性表的动态分配顺序存储结构—C语言实现
#define MaxSize 50//存储空间的分配量
Typedef char ElemType；
Typedef struct{
ElemType data[MaxSize];
int length; //表长度（表中有多少个元素）
}SqList;
动态创建一个空顺序表的算法：
void InitList(SqList *&L) //初始化线性表
{
L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L->length=0; //置空线性表长度为0
}
线性表的插入：
status Sqlist_insert(Sqlist &L,int i,Elemtype x)
/*在顺序表L中第i个元素前插入新元素x*/
{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/
if (L.length>=MAXLEN)return OVERFLOW;
/*顺序表L中已放满元素，再做插入操作则溢出*/
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; /*将第i个元素及后续元素位置向后移一位*/
L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/
L.length++; /*顺序表L的长度加1*/
return OK;
}
线性表的删除：
status Sqlist_delete(Sqlist &L,int i,Elemtype &e)
/*在顺序表L中删除第i个元素*
{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/
L.length--;/*顺序表L的长度减1*/
return OK；
}
线性表元素的查：
int LocateElem(SqList *L, ElemType e) //按元素值查
{
int i=0;
while (i<L->length && L->data[i]!=e)
i++; //查元素e
if (i>=L->length) //未到时返回0printf输出格式顺序
return 0;
else
return i+1; //到后返回其逻辑序号
}
输出线性表：
void DispList(SqList *L) //输出线性表
{
int i;
if (ListEmpty(L)) return;
for (i=0;i<L->length;i++)
printf("%c ",L->data[i]);
printf("\n");
}
输出线性表第i个元素的值：
bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值
{
if (i<1 || i>L->length)
return false; //参数错误时返回false
e=L->data[i-1]; //取元素值
return true; //成功到元素时返回true
}
代码：
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
      int length;
} SqList;
void InitList(SqList *&L);
void DestroyList(SqList *L);
bool ListEmpty(SqList *L);
int ListLength(SqList *L);
void DispList(SqList *L);
bool GetElem(SqList *L,int i,ElemType &e);
int LocateElem(SqList *L, ElemType e);
bool ListInsert(SqList *&L,int i,ElemType e);
bool ListDelete(SqList *&L,int i,ElemType &e);
void InitList(SqList *&L)    //初始化线性表
{
    L=(SqList *)malloc(sizeof(SqList));    //分配存放线性表的空间
    L->length=0;                        //置空线性表长度为0
}
void DestroyList(SqList *L)        //销毁线性表
{
    free(L);
}
bool ListEmpty(SqList *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->data[i]);
    printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)    //求线性表中某个数据元素值
{
    if (i<1 || i>L->length)
        return false;            //参数错误时返回false
    e=L->data[i-1];                //取元素值
    return true;                //成功到元素时返回true
}
int LocateElem(SqList *L, ElemType e)    //按元素值查
{
    int i=0;
    while (i<L->length && L->data[i]!=e)
        i++;                    //查元素e
    if (i>=L->length)            //未到时返回0
        return 0;
    else
        return i+1;                //到后返回其逻辑序号
}
bool ListInsert(SqList *&L,int i,ElemType e)    //插入数据元素
{
    int j;
    if (i<1 || i>L->length+1)
        return false;            //参数错误时返回false
    i--;                        //将顺序表逻辑序号转化为物理序号
    for (j=L->length;j>i;j--)    //将data[i]及后面元素后移一个位置
        L->data[j]=L->data[j-1];
    L->data[i]=e;                //插入元素e
    L->length++;                //顺序表长度增1
    return true;                //成功插入返回true
}
bool ListDelete(SqList *&L,int i,ElemType &e)    //删除数据元素
{
    int j;
    if (i<1 || i>L->length)        //参数错误时返回false
        return false;
    i--;                        //将顺序表逻辑序号转化为物理序号
    e=L->data[i];
    for (j=i;j<L->length-1;j++)    //将data[i]之后的元素前移一个位置
        L->data[j]=L->data[j+1];
    L->length--;                //顺序表长度减1
    return true;                //成功删除返回true
}
void main()
{
    SqList *L;
    ElemType e;
    printf("顺序表的基本运算如下:\n");
    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);
}
4、实验结果分析及总结体会：
    实验结果：
心得体会：
  通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。