[[394255]]

本文轉(zhuǎn)載自微信公眾號(hào)「二十二畫程序員」，作者行小觀。轉(zhuǎn)載本文請(qǐng)聯(lián)系二十二畫程序員公眾號(hào)。 

什么是線性表?

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

所謂表，肯定都不陌生，生活中有各種各樣的表或者表格。我們?cè)诒砀裰刑顚懜鞣N各樣的信息，通過(guò)表格，能夠很好地對(duì)信息進(jìn)行分類儲(chǔ)存和分析。

表的特點(diǎn)有：

• 表由若干單元格組成
• 單元格之間有順序
• 除特殊位置的單元格(首起和結(jié)尾)有一個(gè)“鄰居”外，其他單元格都有兩個(gè)“鄰居”。

那么什么是線性表呢?簡(jiǎn)單來(lái)說(shuō)，就是使用“直線”或“曲線”連接起來(lái)的表。

明確幾個(gè)名詞：

• 我們?cè)诒碇蟹Q呼的“單元格”，在線性表中可以稱之為元素。
• 對(duì)于某個(gè)元素，在其前鄰的元素稱之為直接前驅(qū)元素，在其后鄰的元素稱之為直接后繼元素。
• 線性表中元素的個(gè)數(shù)稱之為線性表的長(zhǎng)度。
• 第一個(gè)元素稱之為首元素，最后一個(gè)元素稱之為尾元素。

由上圖可以總結(jié)出線性表的特點(diǎn)：

• 線性表由若干元素組成，用來(lái)存儲(chǔ)信息。
• 元素之間有順序。
• 除了首元素(只有一個(gè)直接后繼元素)和尾元素(只有一個(gè)直接前驅(qū)元素)外，其它元素都有且僅有一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。

線性表的順序存儲(chǔ)方式

不管數(shù)據(jù)結(jié)構(gòu)的形式再怎么變，數(shù)據(jù)結(jié)構(gòu)的最根本的目的始終不會(huì)變，那就是為了更高效地對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)、修改、刪除和訪問(wèn)，這種高效通常體現(xiàn)在時(shí)間上和空間上，也即程序運(yùn)算速度快慢和所用存儲(chǔ)空間的少多。

那么線性表這種數(shù)據(jù)結(jié)構(gòu)是如何進(jìn)行存儲(chǔ)的呢?前面介紹了一種“用直線連接”的線性表，“直線”只是形象化的語(yǔ)言，實(shí)際上的存儲(chǔ)中是不會(huì)有所謂“直線”這種東西的。

所謂“直線連接”即順序存儲(chǔ)，那么什么是順序存儲(chǔ)呢?

首先得先解釋一下什么是內(nèi)存。內(nèi)存是計(jì)算機(jī)的存儲(chǔ)器的一種，它扮演著非常重要的角色。世上的一切東西，即使是虛擬的，也需要有物理的實(shí)體作為載體。

舉個(gè)例子，孩子們的玩耍需要有土地來(lái)承載，公園、游樂(lè)園等都是這種載體。沒(méi)有土地作為載體，再活潑的孩子也沒(méi)法活潑起來(lái)。對(duì)于代碼來(lái)說(shuō)，內(nèi)存就是玩耍時(shí)需要的那塊土地。

總之，內(nèi)存就是代碼運(yùn)行時(shí)各種信息數(shù)據(jù)的載體空間。有了內(nèi)存，我們才能施展拳腳。

既然涉及到空間，那該空間的東西肯定會(huì)以某種形式排列起來(lái)。通常來(lái)說(shuō)，無(wú)外乎“整齊劃一”和“雜亂無(wú)章”兩種形式。

比如，一群孩子肩并肩地站成一排，占據(jù)一定的連續(xù)土地。

反映在內(nèi)存中，就是數(shù)據(jù)緊密相接，占據(jù)一定的連續(xù)內(nèi)存。

這種“占據(jù)連續(xù)的內(nèi)存空間”即為順序存儲(chǔ)方式。

可以把內(nèi)存比作一幢大樓，樓中有許多房間，每個(gè)房間都有房間號(hào)，一個(gè)房間剛好住一個(gè)人。當(dāng) A、B、C、D 四位小朋友來(lái)到大樓里，選了連續(xù)的 4 個(gè)房間分別入住，那么我們就可以認(rèn)為，這四位小朋友是“順序入住”的。

內(nèi)存 = 大樓，房間 = 內(nèi)存單元，房間號(hào) = 內(nèi)存地址，入住的人 = 要存儲(chǔ)的數(shù)據(jù)。

反映在內(nèi)存中，所謂順序存儲(chǔ)，即用一段連續(xù)的內(nèi)存單元分別存儲(chǔ)線性表中的數(shù)據(jù)。

如上圖所示，線性表的順序存儲(chǔ)是在內(nèi)存空間中開(kāi)辟一塊連續(xù)的空間，開(kāi)辟好之后，這塊空間就被這個(gè)線性表“占用”了。

實(shí)現(xiàn)思路

線性表的每個(gè)數(shù)據(jù)元素的類型都相同、數(shù)據(jù)元素個(gè)數(shù)有限。根據(jù)這個(gè)特性我們很容易想出可以用一維數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。

注意：是先占用再使用，也即線性表的長(zhǎng)度不能超過(guò)最大存儲(chǔ)容量(數(shù)組的長(zhǎng)度)。

如何用代碼表示一個(gè)用數(shù)組實(shí)現(xiàn)的線性表?首先搞清楚一個(gè)這樣的線性表有哪些必要的東西。

1. 線性表需要一個(gè)數(shù)組用來(lái)存儲(chǔ)數(shù)據(jù)元素;
2. 線性表需要一個(gè)最大存儲(chǔ)容量(數(shù)組長(zhǎng)度)，即你想要“占”多少個(gè)位子，是要事先聲明的，不再輕易改變;
3. 線性表需要一個(gè)長(zhǎng)度用來(lái)表示存了多少數(shù)據(jù)元素，線性表的長(zhǎng)度隨著數(shù)據(jù)的增刪而變化，沒(méi)有這個(gè)就可能導(dǎo)致你“塞”的數(shù)據(jù)比“占”的位子多，而“溢”出來(lái)。

總結(jié)一下，一個(gè)順序存儲(chǔ)方式的線性表 (ArrayList) 由以下三部分組成：

用來(lái)實(shí)際存儲(chǔ)數(shù)據(jù)的數(shù)組——data[];

用來(lái)表示線性表的最大存儲(chǔ)容量的值——MAXSIZE;

用來(lái)表示線性表的長(zhǎng)度的值——length。

具體實(shí)現(xiàn)

那么下面就可以使用 C 語(yǔ)言的結(jié)構(gòu)體來(lái)實(shí)現(xiàn)這種線性表了。

為了說(shuō)明問(wèn)題簡(jiǎn)單，我們這里的線性表只存儲(chǔ)整數(shù)。

#define MAXSIZE 10 //線性表的最大存儲(chǔ)容量 
 
typedef struct { 
    int data[MAXSIZE]; //存儲(chǔ)數(shù)據(jù)的數(shù)組 
    int length; //線性表的長(zhǎng)度 
} ArrayList; 

這樣的一個(gè)結(jié)構(gòu)體就能完美地表示一個(gè)順序存儲(chǔ)結(jié)構(gòu)的線性表了。

初始化

孩子們已經(jīng)知道公園了在哪了，但還未踏上去。

到此為止，我們已經(jīng)知道了什么是順序存儲(chǔ)，也知道了如何用代碼表示線性表，但僅停留在“知道”這一步，我們還未將其實(shí)際地“創(chuàng)造”出來(lái)放到內(nèi)存中。

要想使用一個(gè)線性表，那么我們得先聲明一個(gè)線性表，然后將其初始化為空線性表，也即 length = 0：

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

注意：我們要改變線性表的長(zhǎng)度 length，所以要傳給 init 函數(shù)的參數(shù)是一個(gè) ArrayList 類型的指針。

ArrayList list; //聲明線性表list 
init(&list); //初始化list 

插入和刪除操作

現(xiàn)在孩子們已經(jīng)來(lái)到公園了，并且已經(jīng)肩并肩地排好隊(duì)開(kāi)始玩游戲了，現(xiàn)在有一名小伙伴想要加入到隊(duì)伍中和他們一塊玩。所以有一部分孩子為他“騰”出了位置，讓他“插隊(duì)”。

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

可以把孩子們站成的隊(duì)伍看成線性表，把孩子看成元素，下圖所示過(guò)程就是線性表的插入元素的操作過(guò)程。

孩子們從最后一個(gè)人開(kāi)始逐個(gè)后退，后退到需要的空位為止，線性表的元素也是如此，不過(guò)線性表是使用“向后賦值”來(lái)實(shí)現(xiàn)“后退”的效果的。

分析到此，代碼就可以寫出來(lái)了。

/** 
 * 向線性表的指定位置插入指定值 
 * list : 線性表的地址 
 * position : 要插入的位置 (1 <= position <= list->length + 1) 
 * elem : 要插入的值 
 * return 0 : 插入失?。?/span>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)

需檢查插入位置是否合法(不能插入到表外)

插入成功后，線性表的長(zhǎng)度要加一

現(xiàn)在，剛剛插隊(duì)的小孩被媽媽喊回家吃飯了，所以他需要離開(kāi)隊(duì)伍，這時(shí)隊(duì)伍中“空出”了一個(gè)位置，所以他后面的小孩都自覺(jué)的向前一步走，使隊(duì)伍更緊湊。

孩子離隊(duì)后，“空位”之后的每個(gè)孩子都逐個(gè)“向前一步走”。線性表刪除元素時(shí)，使用“向前賦值”來(lái)實(shí)現(xiàn)孩子“向前一步走”的效果。刪除操作和插入操作剛好相反，下圖是其過(guò)程：

下面是代碼實(shí)現(xiàn)：

/** 
 * 刪除指定位置的元素，并保存其值 
 * list : 線性表的地址 
 * position : 要?jiǎng)h除的元素位置 
 * elem : 保存變量的地址 
 * return 0 : 刪除失?。?/span>return 1 : 刪除成功 
 */ 
int delete(ArrayList *list, int position, int *elem) 
{ 
    if (list->length == 0) { 
        printf("線性表為空\(chéng)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; 
} 

同樣注意：

需檢查線性表是否為空

需檢查刪除位置是否合法

刪除成功后，線性表長(zhǎng)度要減一

其他操作

至此，已經(jīng)介紹了基本的“增、刪、改、查”的“增和刪”。

至于“改和查”，由于順序存儲(chǔ)結(jié)構(gòu)的線性表是用數(shù)組來(lái)實(shí)現(xiàn)的，而數(shù)組的查詢和修改是及其方便的，如：

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

所以，順序存儲(chǔ)的線性表的查詢和修改也極為方便。

下面是查詢的代碼：

/** 
 * 查詢指定位置的元素 
 * list : 要操作的線性表 
 * position : 要查詢的元素位置 
 * elem : 保存變量的地址 
 * return 0 : 查詢失?。?/span>return 1 : 查詢成功 
 */ 
int get(ArrayList list, int position, int *elem) 
{ 
    if (list.length == 0) { 
        printf("線性表為空\(chéng)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 : 更新失?。?/span>return 1 : 更新成功 
 */ 
int update(ArrayList *list, int position, int elem) 
{ 
    if (list->length == 0) { 
        printf("線性表為空\(chéng)n"); 
        return 0; 
    } 
    if (position < 1 || position > list->length) { 
        printf("位置不合法\n"); 
        return 0; 
    } 
    list->data[position - 1] = elem; 
    return 1; 
} 

以上即為針對(duì)順序存儲(chǔ)結(jié)構(gòu)的最基礎(chǔ)的增刪改查操作，會(huì)了這四種，其他的操作也基本上可以觸類旁通了。

順序存儲(chǔ)線性表的優(yōu)缺點(diǎn)

上面的那個(gè)小孩加入隊(duì)伍的時(shí)候，為了給他騰位置，很多人都而向后退一步。但是才玩了一會(huì)，他就被叫回去吃飯了，之前向后退步的人又不得不再向前走一步。因?yàn)橐粋€(gè)人，而導(dǎo)致很多人不得不為之變動(dòng)，小孩們很不樂(lè)意。

寫過(guò)上面四個(gè)函數(shù)，我們也會(huì)有小孩們的體會(huì)。

增加和刪除一個(gè)元素太麻煩了，當(dāng)元素很少還不明顯，但當(dāng)有成百上千個(gè)元素時(shí)，就需要移動(dòng)大量的元素了，很麻煩，我們很不樂(lè)意。

查詢和修改一個(gè)元素卻很簡(jiǎn)單，這是數(shù)組的功勞。

另外，線性表的容量是固定的，大多數(shù)情況下，我們并不會(huì)提前知道線性表的容量，所以容量的分配是一個(gè)很大的問(wèn)題，少了不夠用，多了太浪費(fèi)。像極了在快速長(zhǎng)身體的青春期時(shí)買衣服的你。

總結(jié)一下：

優(yōu)點(diǎn)：

• 查詢和修改元素方便快捷

缺點(diǎn)：

• 增加和刪除某個(gè)元素需要移動(dòng)大量的其他元素
• 難以確定容量大小(所以通常會(huì)盡可能分多一點(diǎn)來(lái)“兜底”，但這極易造成浪費(fèi)從而影響性能)