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

• 线性表的顺序存储实现

  线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素. 显然可以用C语言中的一维数组实现.

  

  使用数组实现线性表关键在以下几点:
  1. 线性表长度未知, 要为数组预留足够大的存储空间, 数组的长度即为线性表的最大长度.
  2. 数组的下标是从0开始的, 而常说的线性表的第几个元素是从1开始计数的, 所以线性表第i个元素存储在数组下标为i-1的位置, 线性表的长度和数组的长度指的是存储单元的个数, 从1开始计数.
  3. 由于采用数组实现, 所以必须记录线性表当前的长度.
• 存储结构伪代码

#define MAXSIZE 20 // 数组的长度
typedef struct {
    element_type element_array[MAXSIUZE]; // 存储数据元素的数组
    int list_length; // 线性表的长度
} list;

bool get_element(list *l, int i, element_type *data); // 获取链表l的第i个元素, 存储到data
bool insert_element(list *l, int i, element_type *data); // 将data中的元素, 插入到链表l的第i个位置
bool delete_element(list *l, int i); // 删除链表l中第i个元素
           

• 实现

  get_element

  函数

  思路: 通过指针访问数组i-1的位置

bool get_element(list *l, int i, element_type *data)
{
    if(l->list_length ==  || i <  || i > l->list_length)
        return false;
    *data = l->list[i-]; // 第i个元素在数组下标为i-1

    return true;
}
           

• 实现

  insert_element

  函数

  思路:

  1. 先将插入位置i之后的所有元素(包括i位置的元素)全部向后移动一个位置
  2. 后移需要从线性表最后一个元素开始
  3. 插入后需要更新线性表的长度
  4. 注意数组下标与位置的区别

     

bool insert_element(list *l, int i, element_type *data)
{
    // 检查线性表是否为空
    if(l->list_length == MAXSIZE)
        return false;
    // 检查插入位置是否正确
    if(i <  || i > l->list_length)
        return false;
    // 插入位置非线性表末尾需要先移动元素
    if(i <= l->list_length) {
        int j;
        for(j = l->list_length-; j >= i-; j--) {
            l->element_array[j+] = l->element_array[j];
        }
    }
    // 插入
    l->element_array[i-] = *data;
    // 更新线性表长度
    l->list_length++;

    return true;
}
           

• 实现

  delete_element

  函数

  思路: 删除元素的操作是插入操作的逆, 删除元素后需要将删除位置后的元素前移一个位置.

bool delete_element(list *l, int i)
{
    // 检查线性表是否为空
    if(l->list_length == MAXSIZE)
        return false;
    // 检查删除位置是否正确
    if(i <  || i > l->list_length)
        return false;
    // 删除
    *data = l->element_array[i-];
    // 删除位置非线性表末尾需要将元素前移
    if(i < l->list_length) {
        int j;
        for(j = i; j < l->list_length; j++) {
            l->element_array[j-] = l->element_array[j];
        }
    }
    // 更新线性表长度
    l->list_length--;

    return true;
}