数据结构笔记01

顺序表的概念

顺序表是一种顺序存储结构，用来将一连串的数据存储到一起。

为了能高效利用存储空间，顺序表在存储数据时，会提前申请一块足够大小的物理空间，然后将数据依次存储，这样在存储时数据元素可以紧密排列，不留出空隙。下图所示是在线性表上存储数据 {1, 2, 3, 4, 5} 的内存空间示意：

观察上图数据的存储状态可以发现，顺序表存储数据类似数组。实际上，顺序表存储数据使用的就是数组。

顺序表的初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数。

因此，顺序表申请的存储容量应大于期望存储的数据长度。当达到最大存储容量时，应该不能再对顺序表添加新元素。

顺序表的表结构实现为：

typedef struct {
    int length;  // table length
    int size;    // actual allocated size
    int* body;   // table body
} table;

注意，body 字段是一个指针。它的用途是：通过 malloc() 函数申请到足够的存储空间，然后将其作为一个数组使用。

因此，新创建一个顺序表的步骤为：

给 body 指针申请足够的内存空间
给 length 和 size 字段赋一个合适的初始值

相应的C语言实现如下：

const int TABLE_SIZE = 32;  // expected size of the table

table new(void){
    table tb;
    tb.body = (int*)malloc(sizeof(int) * TABLE_SIZE);
    if (!tb.body) {   // fail to allocate memory for table
        /* other operations */
        exit(0);
    }
    tb.length = 0;   // empty table
    tb.size = TABLE_SIZE;  // expected size
    return tb; 
}

整个顺序表的新建被封装为了函数。该函数返回一个封装成功的顺序表。注意顺序表初始化过程中，要对内存空间的申请进行判断，对申请失败的情况进行处理。

有了顺序表的定义，很容易就可以使用顺序表，包括顺序表的添加元素、遍历、删除等。

元素的增删改查

插入元素

向已有的顺序表中插入元素，根据插入的位置，大致可分为两种情况：

向顺序表的末尾插入元素
向顺序表的中间位置或开头处插入元素

对于向中间位置插入元素的情况，需要将顺序表的后续元素整体后移，为插入的元素空出位置。下图展示了这种情况：

因此，顺序表插入数据元素的C语言实现如下：

/* insert a new element for table */
void insert(table* tb, int elem, int index) {
    // see if the inserted position is inappropriate
    if (index > tb->length + 1 || index < 1) {
        /* raise warnings */
        return;
    }
    // see if table have extra storage space for the inserted elements
    if (tb->length == tb->size) {
        /* raise warnings */
        return;
    }
    // insert oprations
    for (int i = tb->length - 1; i >= index; i--) 
        tb->body[i + 1] = tb->body[i];
    // insert new element to corresponding position
    tb->body[index] = elem;
    tb->length++;
}

顺序表的插入需要做两次判断：第一次判断插入数据的位置是否合适，第二次判断是否还有多余的空间让数据插入。

具体插入的方式为从最后一个元素开始，从后向前逐个将元素后移，直到将待插入位置的元素也后移了为止。

删除元素

有了插入元素的基础，从顺序表删除元素便很容易了。只需要将目标元素的后续元素整体前移即可，待删除元素便会被直接覆盖。

/* delete an element of table */
void delete(table* tb, int index) {
    // see if the inserted position is inappropriate
    if (index > tb->length + 1 || index < 1) {
        return;
    }
    for (int i = index; i < tb->length; i++)
        tb->body[i] = tb->body[i + 1];
    tb->length--;
}

查找元素

顺序表查找元素可以用多种算法实现，这里仅仅使用最基本的顺序查找算法，即遍历顺序表的逐个元素，直到找到需要的值为止。

C语言实现为：

/* find the position of element in table */
int find(table* tb, int elem) {
    for (int i = 0; i < tb->length; i++)
        if (elem == tb->body[i])
            return i;
        return -1;
}

如果找到了相应的元素，它会返回该元素的索引值；如果没有找到相应的元素，它会返回 -1 。

如果能成功查找到一个元素，凭借返回的索引值，就能轻松修改该元素的值。

顺序表