什么是線性表？數(shù)據(jù)結(jié)構(gòu)之線性表講解!

相信很多學(xué)習(xí)C語言、Java等編程語言的小伙伴們在掌握了基礎(chǔ)語法后就了解到了數(shù)據(jù)結(jié)構(gòu)與算法，這兩個學(xué)科熬禿了多少程序員的頭。數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系是依賴的，實現(xiàn)算法需要一定的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)有很多種類，其中最簡單的一種就是線性表，而線性表中又分為順序表和鏈式表（簡稱鏈表），我們就來介紹一下線性表的這兩種表。

基礎(chǔ)數(shù)據(jù)類型

我們知道，每一門語言都有一些基礎(chǔ)的數(shù)據(jù)類型，比如int,float,char，這些數(shù)據(jù)類型就像一個一個的點。但是我們在實際使用的時候會把一些有關(guān)聯(lián)的點組合起來使用，這就是有結(jié)構(gòu)的數(shù)據(jù)（比如將一個一個的數(shù)據(jù)存放在一起，這就是一個集合（枚舉類型））。

線性表

數(shù)據(jù)結(jié)構(gòu)不僅描述了數(shù)據(jù)的格式，還描述了數(shù)據(jù)與數(shù)據(jù)間的關(guān)系，最常見的就是數(shù)據(jù)與數(shù)據(jù)之間一一聯(lián)系，前一個數(shù)據(jù)和后一個數(shù)據(jù)相連，這種數(shù)據(jù)結(jié)構(gòu)最后會像線一樣連成一串，這種數(shù)據(jù)結(jié)構(gòu)也因此得名為線性表。

線性表的實現(xiàn)有兩種形式，這兩種實現(xiàn)方式的不同主要是內(nèi)存造成的：

順序表

實現(xiàn)線性表的最簡單的方式，就是在一片連續(xù)的內(nèi)存中按照順序填充數(shù)據(jù)，這樣每個數(shù)據(jù)都會像排隊一樣在內(nèi)存空間里有一定的位置。要訪問數(shù)據(jù)的前一個數(shù)據(jù)，只要在內(nèi)存中相應(yīng)偏移一定的量（通常是一個數(shù)據(jù)的長度），就能訪問到相應(yīng)的數(shù)據(jù)，訪問后一個數(shù)據(jù)也可以使用相同的方式。

實際上在看到連續(xù)的內(nèi)存這個字眼，小伙伴們應(yīng)該馬上就想到了吧？沒錯，就是數(shù)組（在python中沒有數(shù)組，但有隊列和元組，在此處對應(yīng)的是元組，下文會有所介紹）

如上所示，這就是一個典型的順序表。

順序表的問題

前文中我們提到，創(chuàng)建順序表需要開辟一塊固定的空間，通常這個空間開辟后就無法修改其容量，也就是所這個順序表初始化的時候只能存放10個數(shù)據(jù)，就不能存放超過十個數(shù)據(jù)。這樣的使用會存在這樣的問題：我怎么知道我需要多大的空間，換言之，在不知道需要多大空間的時候，使用順序表就要根據(jù)經(jīng)驗來判斷了，如果預(yù)先開辟過大的空間，就會有空間浪費的問題。另外，順序表的數(shù)據(jù)操作也有一定的資源浪費，修改數(shù)據(jù)上邏輯是正常的，我只要到固定的位置改動數(shù)據(jù)即可，刪除和添加最后一個數(shù)據(jù)也是正常的，還是到最后的位置處理數(shù)據(jù)即可，那么我要在順序表中間或者開頭插入一個數(shù)據(jù)呢？這個時候我就要在要插入的位置開始，將所有的數(shù)據(jù)后移一位，才能將新數(shù)據(jù)填充進去，刪除也有同樣的情況，要將要刪除的

此外還有另一個問題：如果我本身沒有這么多空間呢？內(nèi)存的使用并不是有規(guī)律的，開辟一塊固定寬度的空間很多時候只是一種奢求，如何在支零破碎的內(nèi)存中利用好每個空隙，這就是接下來的主角——鏈式表的優(yōu)勢了。

鏈式表

與順序表不同，順序表是將一堆數(shù)據(jù)捆在一起，使用物理相鄰的方式來確定他們的關(guān)系。而鏈式表這是數(shù)據(jù)與數(shù)據(jù)之間各自在其內(nèi)存空間，不過數(shù)據(jù)中保存著訪問下一個（或者上一個）數(shù)據(jù)的方法。如何通俗的理解這個方法呢？假如一群朋友去看電影，但是沒有辦法買到連坐的位置，想要知道某個人的位置，你可以問旁邊的你的朋友，因為你知道你旁邊的你的朋友在哪，而你的朋友又可以問你的另一個朋友，知道找到那個朋友。如下所示：

在C語言中使用指針來保存下一個（或上一個）數(shù)據(jù)的數(shù)據(jù)地址，在其他語言中使用引用來保存下一個（或者上一個）的數(shù)據(jù)（因為是引用，所以實際上也是保存了一個數(shù)據(jù)地址），如下所示：

一個node就是一個數(shù)據(jù)，也就是一個數(shù)據(jù)節(jié)點，每個節(jié)點由數(shù)據(jù)域和指針域構(gòu)成，數(shù)據(jù)域用來存放數(shù)據(jù)，而指針域用來指定下一個目標節(jié)點。

由于鏈表的這種特性，要在中間插入一個數(shù)據(jù)，只需要新建一個數(shù)據(jù)節(jié)點，然后將前一個數(shù)據(jù)的指針域指向這個新數(shù)據(jù)，然后將這個新數(shù)據(jù)指向后一個指針域即可。刪除也很簡單，我們只需要將前一個數(shù)據(jù)的指針域指向下一個數(shù)據(jù)，然后刪除這個數(shù)據(jù)即可（在c語言中線性表需要自行實現(xiàn)，或者使用相應(yīng)的庫，而在python中列表具有相應(yīng)的功能，但列表并不只是單純的鏈式表，你可以看做他是鏈式表的升級版或者超集）。

要想知道一個鏈表有多少個數(shù)據(jù)節(jié)點，只有將所有的數(shù)據(jù)遍歷過才能知道，當然，你可以選擇用一個數(shù)據(jù)節(jié)點來保存這個鏈表的長度，但是你需要訪問最后一個節(jié)點，假如這個鏈表的長度為十萬個，那么就需要執(zhí)行十萬次數(shù)據(jù)讀取才能得到這個節(jié)點的數(shù)據(jù)，而順序表只需要一次（他可以直接通過內(nèi)存偏移得到相應(yīng)的數(shù)據(jù)）

鏈表的C語言實現(xiàn)：單鏈表

#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//鏈表插入的函數(shù)，p是鏈表，elem是插入的結(jié)點的數(shù)據(jù)域，add是插入的位置
link * insertElem(link * p,int elem,int add);
//刪除結(jié)點的函數(shù)，p代表操作鏈表，add代表刪除節(jié)點的位置
link * delElem(link * p,int add);
//查找結(jié)點的函數(shù)，elem為目標結(jié)點的數(shù)據(jù)域的值
int selectElem(link * p,int elem);
//更新結(jié)點的函數(shù)，newElem為新的數(shù)據(jù)域的值
link *amendElem(link * p,int add,int newElem);
void display(link *p);
int main() {
    //初始化鏈表（1，2，3，4）
    printf("初始化鏈表為：\n");
    link *p=initLink();
    display(p);
   
    printf("在第4的位置插入元素5：\n");
    p=insertElem(p, 5, 4);
    display(p);
   
    printf("刪除元素3:\n");
    p=delElem(p, 3);
    display(p);
   
    printf("查找元素2的位置為：\n");
    int address=selectElem(p, 2);
    if (address==-1) {
        printf("沒有該元素");
    }else{
        printf("元素2的位置為：%d\n",address);
    }
    printf("更改第3的位置的數(shù)據(jù)為7:\n");
    p=amendElem(p, 3, 7);
    display(p);
   
    return 0;
}
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//創(chuàng)建一個頭結(jié)點
    link * temp=p;//聲明一個指針指向頭結(jié)點，用于遍歷鏈表
    //生成鏈表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
link * insertElem(link * p,int elem,int add){
    link * temp=p;//創(chuàng)建臨時結(jié)點temp
    //首先找到要插入位置的上一個結(jié)點
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置無效\n");
            return p;
        }
        temp=temp->next;
    }
    //創(chuàng)建插入結(jié)點c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向鏈表中插入結(jié)點
    c->next=temp->next;
    temp->next=c;
    return  p;
}
link * delElem(link * p,int add){
    link * temp=p;
    //遍歷到被刪除結(jié)點的上一個結(jié)點
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//單獨設(shè)置一個指針指向被刪除結(jié)點，以防丟失
    temp->next=temp->next->next;//刪除某個結(jié)點的方法就是更改前一個結(jié)點的指針域
    free(del);//手動釋放該結(jié)點，防止內(nèi)存泄漏
    return p;
}
int selectElem(link * p,int elem){
    link * t=p;
    int i=1;
    while (t->next) {
        t=t->next;
        if (t->elem==elem) {
            return i;
        }
        i++;
    }
    return -1;
}
link *amendElem(link * p,int add,int newElem){
    link * temp=p;
    temp=temp->next;//tamp指向首元結(jié)點
    //temp指向被刪除結(jié)點
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
}
void display(link *p){
    link* temp=p;//將temp指針重新指向頭結(jié)點
    //只要temp指針指向的結(jié)點的next不是Null，就執(zhí)行輸出語句。
    while (temp->next) {
        temp=temp->next;
        printf("%d",temp->elem);
    }
    printf("\n");
}

回到上文的問題

為什么在python中順序表對應(yīng)的是元組而不是列表?原因很簡單，python的列表是可以從中間插入數(shù)據(jù)的，而這是鏈式表的特性，元組不能實現(xiàn)這個功能。

小結(jié)：順序表和鏈式表的優(yōu)缺點比較