数据结构与算法-顺序链表

我们首先来看几个概念：

线性数据结构的特点：

(1)存在唯一的一个被称作“第一个”的数据元素；

(2)存在唯一的一个被称为“最后一个”的数据元素；

(3)除第一个之外，集合中的每个数据元素均只有一个前驱；

(4)除了最后一个之外，集合中每个数据元素均只有一个后继。

线性表:

线性表是最基本、最简单、也是最常用的一种线性数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

线性表的表示和实现由两种，顺序表示和链式表示，我们今天来看顺序表示：

顺序表示：

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

C语言中通常用数组来表示数据结构中的顺序存储结构，如下图所示：

 在上述的定义中，数组指针base指示顺序表的基地址，capacity指示顺序表当前分配的空间容量，size指示顺序表当前长度。

对mylist初始化函数如下：

//seqlist.h

#define SEQ_INIT_SIZE 8
#define INC_SIZE 8

void InitSeqList(SeqList *list)
{
    list->base = (ElemType *)malloc(SEQ_INIT_SIZE * sizeof(ElemType));
    assert(list->base != NULL);
    list->capacity = SEQ_INIT_SIZE;
    list->size = 0;
    printf("Seqlist initialized.
");
    return;
}

在这种存储结构中，容易实现线性表的某些操作，如随机存取第i个数据元素等，只是要注意C语言中数组下标是从“0”开始；

下面重点讨论线性表的插入和删除操作：

(a)插入元素到position位置

比如下面的顺序表中，我们希望把6插入3，4之间(位置position=3)：

那么我们首先需要做的是移动4，3位置的元素，即5移至位置5，4移至位置4(即把position及之后所有元素往后移动1位)：

最后插入元素6：

用C代码实现如下：

void insert_pos(SeqList *list, ElemType data, int position)
{
    if (list->size >= list->capacity && !increase_size(list)) //判断顺序表是否已满
    {
        printf("Seqlist is full,can't insert data:%d
", data);
        return;
    }

    if (position < 0 ||position > list->size)//判断输入的位置是否合法
    {
        printf("position inputed is invalid
");
        return;
    }

    for (int i = list->size; i > position; i--)//移动position位置及之后的数据
    {
        list->base[i] = list->base[i - 1];
    }

    list->base[position] = data; //插入数据
    list->size++;
    return;
}

(b)删除position位置的数据：

假如我们从下面的顺序表中删除位置1的元素2：

我们删除元素2后，2之后的元素都需要往前移动一个位置：

移动后顺序表如下：

C代码实现：

void delete_pos(SeqList *list, int position)
{
    if (list->size == 0)//判断顺序表是否为空
    {
        printf("Seqlist is empty,can't delete data
");
        return;
    }

    if (position < 0 || position > list->size)//判断输入的删除位置是否合法
    {
        printf("position inputed is invalid
");
        return;
    }

    for (int i = position; i < list->size; i++)//对position位置后的数据往前移动一个位置
    {
        list->base[i] = list->base[i + 1];
    }

    list->size--;
    return;
}

从上面的实现来看，当在顺序表中某位置插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。