資料結構之線性表的順序存儲實作

• 線性表的順序存儲實作

  線性表的順序存儲結構指的是用一段位址連續的存儲單元依次存儲線性表的資料元素. 顯然可以用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;
}