定义

线性表是具有相同类型的n(n>=0)个数据元素的有限序列

线性表定义.png

性质

• a₁为线性表的第一个元素，只有一个后继；
• a_n为线性表的最后一个元素，只有一个前驱；
• 除a₁和a_n外的其它元素a_i，既有前驱，又有后继；
• 线性表能够逐项访问和顺序存取

存储结构

• 顺序存储结构

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

顺序存储结构.png

• 链式存储结构

  为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息

链式存储结构.png

实现线性表的顺序存储结构

在上面的顺序存储结构的定义中，用一段地址连续的存储单元来保存数据，那么我们可以选用一个容器来实现：一维数组。

一个线性表包含的信息有：

• 线性表的最大容量
• 线性表当前的长度
• 存储数据元素的数组起始位置

容量和长度都非常好理解，那插入线性表中的元素设置成什么类型呢? char? int? 或者其它？很显然，设置一种具体的数据类型都不利于代码的复用，不过我们可以往线性表中插入一个地址，这样的话就不需要关心你插入的数据元素是何种类型了。

memory.png

相关操作

首先我们会在头文件中声明一些我们将要实现的一些操作：

typedef void sequentList;
typedef void sequentListNode;

sequentList *createSequentList(int capacity);
void destroySequentList(sequentList *list);
void clearSequentList(sequentList *list);
int getSequentListLength(sequentList *list);
int getSequentListCapacity(sequentList *list);
sequentListNode *getSequentListElement(sequentList *list, int position);
int addSequentListElement(sequentList *list, sequentListNode *node, int position);
sequentListNode *deletesSequentListElement(sequentList *list, int position);

头文件中声明的这些函数，根据函数名就可知其功能，至于线性表以及表中的元素类型都是定义为void类型，是为了便于数据封装。接下来我们就来实现这些操作。

在上图中，一个线性表包含了三个部分，所以我们可以用一个结构体来实现

typedef unsigned long TSeqListNode;
typedef struct SequentList {
    int capacity;
    int length;
    TSeqListNode *node;
} TSeqList;

上文有谈到是用数组来保存数据元素，但是这里没有定义一个数组，原因是在元素的插入过程中，我们需要动态的改变当前线性表的长度，所以这里我们用一个指针来动态申请数组所需要内存空间。

那为什么定义成unsigned long指针类型了？

因为在插入元素时我们插入的是一个指针，在64位系统中，一个指针占的内存空间是8个byte，而在32位系统中，一个指针占的内存空间是4个byte，所以在64位系统是用unsigned long类型，而32位系统则用unsigned int类型。

• 创建一个线性表

    sequentList *createSequentList(int capacity) {
  
        TSeqList *ret = NULL;
        if (capacity >= 0) {
            ret = (TSeqList *) malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
        }
        if (ret != NULL) {
            ret->capacity = capacity;
            ret->length = 0;
            // 指针运算
            ret->node = (TSeqListNode *) (ret + 1);
        }
        return ret;
    }
  

  整个线性表需要多大的内存都是动态计算的。它其实包含两个部分，一部分是结构体的成员变量所占的内存空间，另外一部分就是保存数据元素的数组内存，而这个内存大小取决于用户需要创造多大容量的数组以及每个数组元素所占的内存。

• 获取线性表中指定位置的数据元素

    sequentListNode *getSequentListElement(sequentList *list, int position) {
  
        TSeqList *seqList = (TSeqList *) list;
        sequentListNode *node = NULL;
        /**判断线性表是否合法并且判断位置是否合法*/
        if (seqList != NULL && (position >= 0 && position < seqList->length)) {
             node = (sequentListNode *) seqList->node[position];
        }
        return node;
    }
  

• 在某个位置上添加一个元素

    int addSequentListElement(sequentList *list, sequentListNode *node, int position) {
  
        TSeqList *seqList = (TSeqList *) list;
        int ret = (seqList != NULL);
        /** step 1 判断是否还有空间可插入*/
        ret = ret && (seqList->length + 1 <= seqList->capacity);
        /** step 2 判断插入的位置是否合法*/
        ret = ret && (position >= 0);
        int i;
        if (ret) {
    
            /** step 3 若插入的位置大于当前线性表的长度，则直接插入到线性表的最后*/
            if (position >= seqList->length) {
    
                position = seqList->length;
            }
    
            /** step 4 从最后一个元素开始到第position个位置，分别将它们都向后移动一个位置*/
            for (i = seqList->length; i > position; i--) {
    
                /**
                 * 最后一个元素的index为seqList->length -1, 循环第一次，
                 * 把它移动到index为seqList-length处，后面的依此类推
                 */
                seqList->node[i] = seqList->node[i - 1];
            }
    
            /** step 5 将新元素插入到指定position*/
            seqList->node[i] = (TSeqListNode) node;
    
            /** step 6 更新线性表长度*/
            seqList->length++;
        }
        return ret;
    }
  

  插入元素的核心算法就是注释当中的step 4，可以通过图来加深理解：

addElement.png

• 删除某个位置的元素

    sequentListNode *deletesSequentListElement(sequentList *list, int position) {
  
        TSeqList *seqList = (TSeqList *) list;
        sequentListNode *node = NULL;
        int i;
        if (seqList != NULL && (position >= 0 && position <= seqList->length)) {
    
            /**step 1 取出被删除元素*/
            node = getSequentListElement(list, position);
            /** step 2 从删除位置的下一个元素开始向前移动一个位置*/
            for (i = position + 1; i < seqList->length; i++) {
    
                seqList->node[i - 1] = seqList->node[i];
            }
            /** step 3 更新线性表长度*/
            seqList->length--;
        }
        return node;
    }
  

  删除元素的核心算法就是step 2，可以通过图来加深理解:

deleteElement.png

其他操作都比较简单，就不在这里一一赘述了。完整代码。我们来分析一下上面四个操作函数的时间复杂度。

• 创建操作：每一行代码最多只执行一次，所以是：O(1)
• 获取操作：每一行代码最多只执行一次，所以是：O(1)
• 添加操作：for循环里面的代码会执行n次，所以是：O(n)
• 删除操作：for循环里面的代码会执行n次，所以是：O(n)

总结

• 优点

  • 无需为线性表中的逻辑关系增加额外的空间
  • 可以快速的获取表中合法位置的元素

• 缺点

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