数据结构(2)-线性表之顺序存储

定义

线性表就是零个或者多个数据元素的有限序列

线性表的特点如下：

• 是一个序列。也就是说元素之间是有顺序的，其第一个元素无直接前驱，最后一个元素无直接后继之外。
• 元素的个数有限的。

线性表元素的个数n表示了线性表的长度。

线性表.png

如图所示，a1无直接前驱，an无直接后继。

线性表的抽象定义如下：

ADT List (线性表)
    Data: 线性表的数据对象集合为{a1,a2,......an}，每个元素的类型均为DataType。
    其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素；
    除了最后一个元素an外，每个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。
    
Operation
    1. 初始化线性表
    操作结果: 初始化操作，建立一个空的线性表L
    
    2. 判断线性表是否为空
    初始条件: 线性表L已存在
    操作结果: 若L为空表，则返回true，否则返回false
    
    3. 清空线性表
    初始条件: 线性表L已存在
    操作结果: 将L重置为空表
    
    4. 销毁线性表
    初始条件: 线性表L已存在
    操作结果: 销毁线性表L
    
    5. 获取线性表的长度
    初始条件: 线性表L已存在
    操作结果: 返回L中数据元素的个数
    
    6. 获取线性表的元素
    初始条件: 线性表L已存在,且1<=i<ListLength(L)
    操作结果: 用e返回L中第i个数据元素的值
    
    7. 查找某元素在线性表中的位置
    初始条件: 线性表L已存在
    操作结果: 返回L中第1个值与e相同的元素在L中的位置 若数据不存在则返回0
    
    8. 返回线性表中某元素的前驱元素
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败
    
    9. 返回线性表中元素的后继元素
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败。
        
    10. 插入元素
    初始条件: 线性表L已存在,且1<=i<=listLength(L)
    操作结果: 在L中第i个位置之前插入新的数据元素e，L长度加1
    
    11. 删除元素
    初始条件: 线性表L已存在,且1<=i<=listLength(L)
    操作结果: 删除L的第i个元素，L的长度减1
    
    12. 遍历元素
    初始条件: 线性表L已存在
    操作结果: 对线性表L进行遍历，在遍历的过程中对L的每个结点访问1次.
    
endADT

线性表的存储结构

线性表有两种存储结构：

1. 顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
2. 链式存储结构：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

下面我们就来仔细的探索一下这两种存储结构:

顺序存储结构

顺序存储结构的3个属性：

• 存储空间的起始位置
• 线性表的最大存储量
• 线性表的当前长度

代码实现如下：

typedef int ElementType;

struct LinearList {
    ElementType *data;
    int length;
};

typedef struct LinearList SeqList;

现在我们再来看看线性表的创建、元素插入、删除等操作。

创建线性表

#define L_MAX_SIZE 50
#define T_ERROR = -1
#define T_OK = 1
typedef int TStatus;

TStatus InitList(SeqList *l) {
    l->data = malloc(L_MAX_SIZE * sizeof(ElementType));
    if (l == NULL) {
        return T_ERROR;
    }
    l->length = 0;
    return T_OK;
}

可以在main函数使用以下代码进行验证：

SeqList sl;
TStatus st;
    
st = InitList(&sl);
printf("==创建线性表成功==长度为==%d==", sl.length);

获取元素

获取第i个元素，只要线性表有值，而且我们想要获取的位置在线性表的长度范围之内即可。

TStatus GetElement(SeqList *l, int i, ElementType *e) {
    if (l->length == 0 || i > l->length || i < 1) {
        return T_ERROR;
    }
    *e = l->data[i - 1];
    return T_OK;
}

遍历打印元素

TStatus TraversePrintList(SeqList *l) {
    printf("********循环输出********\n");
    ElementType a;
    for (int i = 1; i <= l->length; i++) {
        GetElement(l, i, &a);
        printf("==%d===\n", a);
    }
    return T_OK;
}

插入元素

在第i个位置插入元素：

• 插入位置不合理，抛出异常
• 如果线性表长度大于等于我们初始化时的长度，则需要抛出异常或者扩容
• 遍历线性表到要插入的位置i，将i及其之后的元素都向后移动1位
• 插入元素
• 表长加1

/***
 在线性表的第i个位置 插入元素e
 */
TStatus InsertElement(SeqList *l, int i, ElementType e) {
    if (i > l->length + 1 || i < 1) {
        return T_ERROR;
    }
    if (l->length == L_MAX_SIZE) {
        return T_ERROR;
    }
    // 1234
    // 12_34
    if (i <= l->length) {
        for (int j = l->length - 1; j >= i - 1; j--) {
            l->data[j + 1] = l->data[j];
        }
    }
    
    // 12a34
    l->data[i - 1] = e;
    l->length = l->length + 1;
    
    return T_OK;
}

验证：

线性表插入.png

删除元素

删除第i个位置的元素：

• 删除的位置不合理，抛出异常
• 取出删除的元素
• 从删除的位置开始遍历，将后面的每一个元素往前移动一位
• 表长减1

/***
删除线性表的第i个位置的元素e
*/
TStatus DeleteElement(SeqList *l, int i, ElementType *e) {
    if (l->length == 0 || i < 1 || i > l->length) {
        return T_ERROR;
    }
    *e = l->data[i - 1];
    for (int j = i - 1; j <= l->length; j++) {
        l->data[j] = l->data[j + 1];
    }
    l->length--;
    
    return T_OK;
}

返回元素的位置

• 容错处理
• 遍历元素对比
• 返回位置

/***
获取元素e的位置 是第几个
*/
TStatus GetElementIndex(SeqList *l, ElementType e, int *index) {
    if (l->length == 0) {
        return T_ERROR;
    }
    int hasE = -1;
    for (int i = 0; i <= l->length; i++) {
        if (l->data[i] == e) {
            hasE = 1;
            *index = i + 1;
            break;
        }
    }
    if (hasE == -1) {
        *index = -1;
        return T_ERROR;
    }
    return T_OK;
}

根据上述的代码，我们可以得出顺序线性表的优缺点：

• 优点：
  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速获取任意位置的元素，时间复杂度为O(1)
• 缺点：
  • 插入和删除操作需要移动大量的元素，时间复杂度为O(n)
  • 当线性表长度变化比较大的时候，存储空间大小难以确定
  • 造成存储空间碎片

总结

线性表分为顺序存储结构和链式存储结构。顺序存储结构是用一段地址连续的存储单元依次存储线性表的数据元素。其获取元素简单，但是插入或者删除比较麻烦。

参考文献：

• 《大话数据结构》