什么是線性表？數據結構之線性表講解!

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

基礎數據類型

我們知道，每一門語言都有一些基礎的數據類型，比如int,float,char，這些數據類型就像一個一個的點。但是我們在實際使用的時候會把一些有關聯的點組合起來使用，這就是有結構的數據（比如將一個一個的數據存放在一起，這就是一個集合（枚舉類型））。

線性表

數據結構不僅描述了數據的格式，還描述了數據與數據間的關系，最常見的就是數據與數據之間一一聯系，前一個數據和后一個數據相連，這種數據結構最后會像線一樣連成一串，這種數據結構也因此得名為線性表。

線性表的實現有兩種形式，這兩種實現方式的不同主要是內存造成的：

順序表

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

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

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

順序表的問題

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

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

鏈式表

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

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

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

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

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

鏈表的C語言實現：單鏈表

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

回到上文的問題

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

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