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

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

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

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

線性表

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

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

順序表

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

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

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

順序表的問題

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

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

鏈?zhǔn)奖?/h2>

與順序表不同，順序表是將一堆數(shù)據(jù)捆在一起，使用物理相鄰的方式來確定他們的關(guān)系。而鏈?zhǔn)奖磉@是數(shù)據(jù)與數(shù)據(jù)之間各自在其內(nèi)存空間，不過數(shù)據(jù)中保存著訪問下一個(gè)（或者上一個(gè)）數(shù)據(jù)的方法。如何通俗的理解這個(gè)方法呢？假如一群朋友去看電影，但是沒有辦法買到連坐的位置，想要知道某個(gè)人的位置，你可以問旁邊的你的朋友，因?yàn)槟阒滥闩赃叺哪愕呐笥言谀模愕呐笥延挚梢詥柲愕牧硪粋€(gè)朋友，知道找到那個(gè)朋友。如下所示：

arr1 =W 下一個(gè)目標(biāo)是 第三格

null

arr2 =3 下一個(gè)目標(biāo)是 第五格

null

arr3 =C  下一個(gè)目標(biāo)是 第六格

arr4=/0 這里是鏈表尾部

null

在C語言中使用指針來保存下一個(gè)（或上一個(gè)）數(shù)據(jù)的數(shù)據(jù)地址，在其他語言中使用引用來保存下一個(gè)（或者上一個(gè)）的數(shù)據(jù)（因?yàn)槭且?，所以?shí)際上也是保存了一個(gè)數(shù)據(jù)地址），如下所示：

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

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

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

鏈表的C語言實(shí)現(xiàn)：?jiǎn)捂湵?/h2>

#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//鏈表插入的函數(shù)，p是鏈表，elem是插入的結(jié)點(diǎn)的數(shù)據(jù)域，add是插入的位置
link * insertElem(link * p,int elem,int add);
//刪除結(jié)點(diǎn)的函數(shù)，p代表操作鏈表，add代表刪除節(jié)點(diǎn)的位置
link * delElem(link * p,int add);
//查找結(jié)點(diǎn)的函數(shù)，elem為目標(biāo)結(jié)點(diǎn)的數(shù)據(jù)域的值
int selectElem(link * p,int elem);
//更新結(jié)點(diǎn)的函數(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)建一個(gè)頭結(jié)點(diǎn)
    link * temp=p;//聲明一個(gè)指針指向頭結(jié)點(diǎn)，用于遍歷鏈表
    //生成鏈表
    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)建臨時(shí)結(jié)點(diǎn)temp
    //首先找到要插入位置的上一個(gè)結(jié)點(diǎn)
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置無效\n");
            return p;
        }
        temp=temp->next;
    }
    //創(chuàng)建插入結(jié)點(diǎn)c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向鏈表中插入結(jié)點(diǎn)
    c->next=temp->next;
    temp->next=c;
    return  p;
}
link * delElem(link * p,int add){
    link * temp=p;
    //遍歷到被刪除結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//單獨(dú)設(shè)置一個(gè)指針指向被刪除結(jié)點(diǎn)，以防丟失
    temp->next=temp->next->next;//刪除某個(gè)結(jié)點(diǎn)的方法就是更改前一個(gè)結(jié)點(diǎn)的指針域
    free(del);//手動(dòng)釋放該結(jié)點(diǎn)，防止內(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é)點(diǎn)
    //temp指向被刪除結(jié)點(diǎn)
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
}
void display(link *p){
    link* temp=p;//將temp指針重新指向頭結(jié)點(diǎn)
    //只要temp指針指向的結(jié)點(diǎn)的next不是Null，就執(zhí)行輸出語句。
    while (temp->next) {
        temp=temp->next;
        printf("%d",temp->elem);
    }
    printf("\n");
}

回到上文的問題

為什么在python中順序表對(duì)應(yīng)的是元組而不是列表?原因很簡(jiǎn)單，python的列表是可以從中間插入數(shù)據(jù)的，而這是鏈?zhǔn)奖淼奶匦?，元組不能實(shí)現(xiàn)這個(gè)功能。

小結(jié)：順序表和鏈?zhǔn)奖淼膬?yōu)缺點(diǎn)比較