数据结构学习第一弹 线性表（１）

线性表

定义：

线性表：是一种典型的线性结构，由零个或多个数据元素组成的
有限数列

• 首先他是一个序列，也就是说在相互数据元素之间是有顺序的
• 其次线性表强调的是有限个数据元素
• 除了开头元素只有一个后继，结尾元素只有一个前驱之外，其他元素有且仅有一个后继元素和一个前驱元素

若把线性表表示为a1,a2,a3...ai,ai+1...an，这里a1为开始
结点，an为终端结点，ai-1是ai的前驱元素，ai+1是ai的后继元素。

我们把线性表中的元素的个数n定义为线性表的长度，当n = 0时称为
空表

线性表的基本操作

在线性表这种逻辑结构上定义了八种基本的运算

• InitList(*L): 对表L初始化，建立一个空的线性表
• ListEmpty(L): 判断线性表是否为空表
• ClearList(*L): 将线性表清空
• GetElem(L, i, *e): 将线性表L中的第i个位置的元素值返回给e
• LocateElem(L, e): 在线性表中查找一个值为e的元素，若找到则返回该元素的位置，否则返回一个特殊值表示查找失败
• ListInsert(*L, i, e): 在线性表L中第i个位置插入一个元素e
• ListDelete(*L, i, *e): 删除线性表L中第i个位置元素，并用e返回其值
• ListLength(L): 表L的长度

由于存储方式的不同，这几种基本运算的实现方式亦不同，线性表主要
有两种存储方式：

• 顺序存储结构

• 链式存储结构

线性表的顺序存储结构

线性表的顺序存储结构指的是用一段地址连续的存储单元以此存储线性表的数据元素。
所以逻辑上相邻的数据元素其物理存储位置必须紧邻

线性表顺序存储结构的类型定义：

#define MAXSIZE 20          //线性表的最大容量
typedef int ElemType;       //线性表的数据类型
typedef struct
{
    ElemType data[MAXSIZE];
    int length;             //线性表的当前长度
}SqList;

线性表顺序存储结构的具体操作：

//状态码定义
#define OK 1
#define ERROR 0
typedef int Status;

//初始化顺序线性表
Status InitList(SqList *L)
{
    L->length = 0;
    return OK;
}
//判断顺序线性表是否为空表
int ListEmpty(SqList L)
{
    if(L.length)
        return 0;
    return 1;
}
//清空线性表
Status ClearList(SqList *L)
{
    L->length = 0;
    return OK;
}
//GetElem的具体操作
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length == 0 || i<1 || i>L.length)
        return ERROR;
    else *e = L.data[i];
    return OK;
}
//LocateElem操作
int LocateElem(SqList L,ElemType e)
{
    int i;
    for(i=1;i<=L.length;i++)
    {
        if(L.data[i]==e)
            return i;
    }
    return ERROR;
}
//ListInsert操作
Status ListInsert(SqList *L,int i,ElemType e)
{
    if(L->length == MAXSIZE-1)
    {
        //顺序线性表已经满了
        return ERROR;
    }
    if(i<1 || i>L->length+1)
    {
        //当插入的位置不合理时
        return ERROR;
    }
    if(i<=L->length) //当插入的位置不是表尾时
    {
        //所有元素向后移一位
        int k;
        for(k=L->length;k>=i;k--)
            L->data[k+1]=L->data[k];
    }
    L->data[i]=e;
    L->length++;
    return OK;
}
//ListDelete操作
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
    //判断线性表是否为空表
    if(L->length == 0)
        return ERROR;
    //判断删除的元素位置是否异常
    if(i<1 || i>L->length)
        return ERROR;
    //返回删除的值
    *e=L->data[i];
    for(k=i;k<L->length;k++)
        L->data[k]=L->data[k+1];
    L->length--;
    return OK;
}
//ListLength操作
int ListLenght(SqList L)
{
    return L.length;
}

线性表顺序存储结构的优缺点:

优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间

• 可以快速的存取表中任意位置的元素

缺点

• 插入和删除操作需要移动大量元素（O（n））

• 线性表的长度难以确定
• 容易造成存储空间的“碎片”，因为申请空间时，是成块成块的，所以块与块之间肯能会存在碎片