线性表

定义

零个或多个数据元素的有限序列。

抽象数据类型

ADT 线性表（List）
Data
    线性表的数据对象集合为{a1,a2,....,an}，每个元素的类型为DataType。其中除了第一个元素a1外，每一个元素都有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素都有且只有一个后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitLis(*L)：初始化操作，建立一个空的线性表L。
    ListEmpty(L):若线性表为空,返回true,否则返回false.
    ClearList(*L):将线性表清空.
    GetElem(L,i,*e):将线性表L中的第i个位置元素返回给e.
    LocateElem(L,e):在线性表L中查找给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败.
    ListInsert(*L,i,e):在线性表L中的第i个位置插入元素e.
    ListDelete(*L,i,*e):删除线性表L中第i个位置元素,并用e返回其值.
    ListLength(L):返回线性表的元素个数.
endADT

线性表的顺序存储结构

定义

指的是用一段地址连续的存储单元依次存储线性表的数据元素.

#define MAXSIZE 20;
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;    

这里描述三个属性:

• 存储空间的起始位置:数组data,他的存储位置就是存储空间的存储位置.
• 线性表的最大存储容量:数组长度MAXSIZE.
• 线性表的当前长度:length.

任意时候,线性表的长度应该小于等于数组的长度.

获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int STATUS;
/*STATUS 是函数的类型,其值是函数结果状态代码,如OK等*/
/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
/*操作结果:用e返回L中第i个数据元素的值*/
STATUS GetElem(SqList L,int i,ElemType *e) {
    if (L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

插入元素操作

思路:

• 如果位置不合理,抛出异常;

• 如果线性表长度大于等于数组长度,抛出异常或者动态增加容量;

• 从最后一个元素开始向前便利到第i个位置,分别将他们都向后移动一个位置;

• 将要插入的元素填入位置i处;

• 表长加1.

    /*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
    /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/
    STATUS ListInsert(SqList *L,int i,ElemType e) {
        int k;
        if (L->length == MAXSIZE) /*顺序线性表已满*/
            return ERROR;
        if (i < 1 || i > L->length + 1) /*当i不在范围内时*/
            return ERROR;
        if (i <= L->length){ /*若插入数据位置不在表尾*/
            for(k = L->length - 1; k >= i - 1; k-- ) { /*将要插入位置后的数据向后移动一位*/
                L->data[k+1] = L->data[k];
            }
        }
        L->data[i-1] = e; /*在L中第i个位置之前插入新的数据元素e*/
        L->length++; /*L的长度加1*/
        return OK;
    }
  

删除元素

思路:

• 如果位置不合理,抛出异常;

• 取出删除元素;

• 从删除元素位置开始遍历到最后一个元素位置,分别将他们都向前移动一个位置;

• 表长减1.

    /*初始条件:顺序线性表L已经存在,1<=i<=ListLength(L)*/
    /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1*/
    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 - 1];
        if (i < L->length) { /*如果删除不是最后位置*/
            for (k = i; k < L->length; k++) /*将删除位置后继元素前移*/
                L->data[k - 1] = L->data[k];
        }
        L->length--; //L的长度减1
        return OK;
    }
  

优缺点

优点:

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速的存取表中任一位置的元素

缺点:

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时,难以确定存储空间的容量
• 造成存储空间的碎片

线性表的链式存储结构