什么是線性表？

所謂線性，即一條線，這條線可以是直線，也可以是曲線，

所謂表，肯定都不陌生，生活中有各種各樣的表或者表格，我們在表格中填寫各種各樣的資訊，通過表格，能夠很好地對資訊進行分類儲存和分析，

表的特點有：

表由若干單元格組成
單元格之間有順序
除特殊位置的單元格（首起和結尾）有一個“鄰居”外，其他單元格都有兩個“鄰居”，

那么什么是線性表呢？簡單來說，就是使用“直線”或“曲線”連接起來的表，

明確幾個名詞：

我們在表中稱呼的“單元格”，在線性表中可以稱之為元素，
對于某個元素，在其前鄰的元素稱之為直接前驅元素，在其后鄰的元素稱之為直接后繼元素，
線性表中元素的個數稱之為線性表的長度，
第一個元素稱之為首元素，最后一個元素稱之為尾元素，

由上圖可以總結出線性表的特點：

線性表由若干元素組成，用來存盤資訊，
元素之間有順序，
除了首元素（只有一個直接后繼元素）和尾元素（只有一個直接前驅元素）外，其它元素都有且僅有一個直接前驅元素和一個直接后繼元素，

線性表的順序存盤方式

不管資料結構的形式再怎么變，資料結構的最根本的目的始終不會變，那就是為了更高效地對資料進行存盤、修改、洗掉和訪問，這種高效通常體現在時間上和空間上，也即程式運算速度快慢和所用存盤空間的少多，

那么線性表這種資料結構是如何進行存盤的呢？前面介紹了一種“用直線連接”的線性表，“直線”只是形象化的語言，實際上的存盤中是不會有所謂“直線”這種東西的，

所謂“直線連接”即順序存盤，那么什么是順序存盤呢？

首先得先解釋一下什么是記憶體，記憶體是計算機的存盤器的一種，它扮演著非常重要的角色，世上的一切東西，即使是虛擬的，也需要有物理的物體作為載體，

舉個例子，孩子們的玩耍需要有土地來承載，公園、游樂園等都是這種載體，沒有土地作為載體，再活潑的孩子也沒法活潑起來，對于代碼來說，記憶體就是玩耍時需要的那塊土地，

總之，記憶體就是代碼運行時各種資訊資料的載體空間，有了記憶體，我們才能施展拳腳，

既然涉及到空間，那該空間的東西肯定會以某種形式排列起來，通常來說，無外乎“整齊劃一”和“雜亂無章”兩種形式，

比如，一群孩子肩并肩地站成一排，占據一定的連續土地，

反映在記憶體中，就是資料緊密相接，占據一定的連續記憶體，

這種“占據連續的記憶體空間”即為順序存盤方式，

可以把記憶體比作一幢大樓，樓中有許多房間，每個房間都有房間號，一個房間剛好住一個人，當 A、B、C、D 四位小朋友來到大樓里，選了連續的 4 個房間分別入住，那么我們就可以認為，這四位小朋友是“順序入住”的，

記憶體 = 大樓，房間 = 記憶體單元，房間號 = 記憶體地址，入住的人 = 要存盤的資料，

反映在記憶體中，所謂順序存盤，即用一段連續的記憶體單元分別存盤線性表中的資料，

如上圖所示，線性表的順序存盤是在記憶體空間中開辟一塊連續的空間，開辟好之后，這塊空間就被這個線性表“占用”了，

實作思路

線性表的每個資料元素的型別都相同、資料元素個數有限，根據這個特性我們很容易想出可以用一維陣列來實作順序存盤結構，

注意：是先占用再使用，也即線性表的長度不能超過最大存盤容量（陣列的長度），

如何用代碼表示一個用陣列實作的線性表？首先搞清楚一個這樣的線性表有哪些必要的東西，

線性表需要一個陣列用來存盤資料元素；
線性表需要一個最大存盤容量（陣列長度），即你想要“占”多少個位子，是要事先宣告的，不再輕易改變；
線性表需要一個長度用來表示存了多少資料元素，線性表的長度隨著資料的增刪而變化，沒有這個就可能導致你“塞”的資料比“占”的位子多，而“溢”出來，

總結一下，一個順序存盤方式的線性表 (ArrayList) 由以下三部分組成：

用來實際存盤資料的陣列——data[]；
用來表示線性表的最大存盤容量的值——MAXSIZE；
用來表示線性表的長度的值——length，

具體實作

那么下面就可以使用 C 語言的結構體來實作這種線性表了，

為了說明問題簡單，我們這里的線性表只存盤整數，

#define MAXSIZE 10 //線性表的最大存盤容量

typedef struct {
    int data[MAXSIZE]; //存盤資料的陣列
    int length; //線性表的長度
} ArrayList;

這樣的一個結構體就能完美地表示一個順序存盤結構的線性表了，

初始化

孩子們已經知道公園了在哪了，但還未踏上去，

到此為止，我們已經知道了什么是順序存盤，也知道了如何用代碼表示線性表，但僅停留在“知道”這一步，我們還未將其實際地“創造”出來放到記憶體中，

要想使用一個線性表，那么我們得先宣告一個線性表，然后將其初始化為空線性表，也即 length = 0：

/**
 * 初始化線性表，將線性表的長度置為0
 * list : 要操作的線性表的地址
 */
void init(ArrayList *list)
{
    list->length = 0;
}

注意：我們要改變線性表的長度 length，所以要傳給 init 函式的引數是一個 ArrayList 型別的指標，

ArrayList list; //宣告線性表list
init(&list); //初始化list

插入和洗掉操作

現在孩子們已經來到公園了，并且已經肩并肩地排好隊開始玩游戲了，現在有一名小伙伴想要加入到隊伍中和他們一塊玩，所以有一部分孩子為他“騰”出了位置，讓他“插隊”，

由于甲要站在 B 的后面，所以 C、D、E 都要后退一個位置給甲“騰空位”，然后甲才能“插隊”到 B 后面，

可以把孩子們站成的隊伍看成線性表，把孩子看成元素，下圖所示程序就是線性表的插入元素的操作程序，

孩子們從最后一個人開始逐個后退，后退到需要的空位為止，線性表的元素也是如此，不過線性表是使用“向后賦值”來實作“后退”的效果的，

分析到此，代碼就可以寫出來了，

/**
 * 向線性表的指定位置插入指定值
 * list : 線性表的地址
 * position : 要插入的位置 (1 <= position <= list->length + 1)
 * elem : 要插入的值
 * return 0 : 插入失敗；return 1 : 插入成功
 */
int insert(ArrayList *list, int position, int elem)
{
    if (list->length == MAXSIZE) {
        printf("線性表已滿\n");
        return 0;
    }
    if (position < 1 || position > list->length + 1) {
        printf("插入位置不合法\n");
        return 0;
    }
    for (int i = list->length - 1; i >= position - 1; i--) {
        list->data[i + 1] = list->data[i]; //向后賦值
    }
    list->data[position - 1] = elem;
    list->length++;
    return 1;
}

注意：

需檢查線性表是否已滿（length 是否等于 MAXSIZE）
需檢查插入位置是否合法（不能插入到表外）
插入成功后，線性表的長度要加一

現在，剛剛插隊的小孩被媽媽喊回家吃飯了，所以他需要離開隊伍，這時隊伍中“空出”了一個位置，所以他后面的小孩都自覺的向前一步走，使隊伍更緊湊，

孩子離隊后，“空位”之后的每個孩子都逐個“向前一步走”，線性表洗掉元素時，使用“向前賦值”來實作孩子“向前一步走”的效果，洗掉操作和插入操作剛好相反，下圖是其程序：

下面是代碼實作：

/**
 * 洗掉指定位置的元素，并保存其值
 * list : 線性表的地址
 * position : 要洗掉的元素位置
 * elem : 保存變數的地址
 * return 0 : 洗掉失敗；return 1 : 洗掉成功
 */
int delete(ArrayList *list, int position, int *elem)
{
    if (list->length == 0) {
        printf("線性表為空\n");
        return 0;
    }
    if (position < 1 || position > list->length) {
        printf("洗掉位置不合法\n");
        return 0;
    }
    *elem = list->data[position - 1];
    for (int i = position - 1; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return 1;
}

同樣注意：

需檢查線性表是否為空
需檢查洗掉位置是否合法
洗掉成功后，線性表長度要減一

其他操作

至此，已經介紹了基本的“增、刪、改、查”的“增和刪”，

至于“改和查”，由于順序存盤結構的線性表是用陣列來實作的，而陣列的查詢和修改是及其方便的，如：

int a = array[1]; //查詢
array[2] = 5; //修改

所以，順序存盤的線性表的查詢和修改也極為方便，

下面是查詢的代碼：

/**
 * 查詢指定位置的元素
 * list : 要操作的線性表
 * position : 要查詢的元素位置
 * elem : 保存變數的地址
 * return 0 : 查詢失敗；return 1 : 查詢成功
 */
int get(ArrayList list, int position, int *elem)
{
    if (list.length == 0) {
        printf("線性表為空\n");
        return 0;
    }
    if (position < 1 || position > list.length) {
        printf("位置不合法\n");
        return 0;
    }
    *elem = list.data[position - 1];
    return 1;
}

下面是更新的代碼：

/**
 * 更新指定位置的元素
 * list : 要操作的線性表的地址
 * position : 要更新的元素位置
 * elem : 要更新的值
 * return 0 : 更新失敗；return 1 : 更新成功
 */
int update(ArrayList *list, int position, int elem)
{
    if (list->length == 0) {
        printf("線性表為空\n");
        return 0;
    }
    if (position < 1 || position > list->length) {
        printf("位置不合法\n");
        return 0;
    }
    list->data[position - 1] = elem;
    return 1;
}

以上即為針對順序存盤結構的最基礎的增刪改查操作，會了這四種，其他的操作也基本上可以觸類旁通了，

順序存盤線性表的優缺點

上面的那個小孩加入隊伍的時候，為了給他騰位置，很多人都而向后退一步，但是才玩了一會，他就被叫回去吃飯了，之前向后退步的人又不得不再向前走一步，因為一個人，而導致很多人不得不為之變動，小孩們很不樂意，

寫過上面四個函式，我們也會有小孩們的體會，

增加和洗掉一個元素太麻煩了，當元素很少還不明顯，但當有成百上千個元素時，就需要移動大量的元素了，很麻煩，我們很不樂意，

查詢和修改一個元素卻很簡單，這是陣列的功勞，

另外，線性表的容量是固定的，大多數情況下，我們并不會提前知道線性表的容量，所以容量的分配是一個很大的問題，少了不夠用，多了太浪費，像極了在快速長身體的青春期時買衣服的你，

總結一下：

優點：

查詢和修改元素方便快捷

缺點：

增加和洗掉某個元素需要移動大量的其他元素
難以確定容量大小（所以通常會盡可能分多一點來“兜底”，但這極易造成浪費從而影響性能）

如有錯誤，還請指正，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263248.html

標籤：其他

上一篇：「SOL」Bad Cryptography(Codeforces)

下一篇：翻轉影像

圖示加代碼 搞懂線性表（一）