App下載

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

草莓夾餅干 2022-01-18 11:18:12 瀏覽數(shù) (5254)
反饋

相信很多學(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)有很多種類,其中最簡單的一種就是線性表,而線性表中又分為順序表和鏈?zhǔn)奖恚ê喎Q鏈表),我們就來介紹一下線性表的這兩種表。

基礎(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)的是元組,下文會有所介紹)

 null arr0=W arr1=3  arr2=C  arr3=S  arr4=C  arr5=H  arr6=o  arr7=o  arr8=l 
 null null  null  null  null  null  null  null  null  null 

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

順序表的問題

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

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

鏈?zhǔn)奖?/h2>

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

 arr1 =W
下一個目標(biāo)是
第三格
 null arr2 =3
下一個目標(biāo)是
第五格 
 null arr3 =C 
下一個目標(biāo)是
第六格
arr4=/0
這里是鏈表尾部 
 null

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


一個node就是一個數(shù)據(jù),也就是一個數(shù)據(jù)節(jié)點,每個節(jié)點由數(shù)據(jù)域和指針域構(gòu)成,數(shù)據(jù)域用來存放數(shù)據(jù),而指針域用來指定下一個目標(biāo)節(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)的功能,但列表并不只是單純的鏈?zhǔn)奖?,你可以看做他是鏈?zhǔn)奖淼纳壈婊蛘叱?/p>

要想知道一個鏈表有多少個數(shù)據(jù)節(jié)點,只有將所有的數(shù)據(jù)遍歷過才能知道,當(dāng)然,你可以選擇用一個數(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為目標(biāo)結(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ù)的,而這是鏈?zhǔn)奖淼奶匦?,元組不能實現(xiàn)這個功能。

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

   順序表 鏈?zhǔn)奖?nbsp;
 內(nèi)存使用 連續(xù)的一塊空間,數(shù)據(jù)相鄰,通過物理相鄰的方式實現(xiàn)數(shù)據(jù)之間的聯(lián)系 。
因此不能動態(tài)調(diào)整長度
(內(nèi)存使用率較低)
每個數(shù)據(jù)節(jié)點不一定相鄰,通過指針的方式實現(xiàn)數(shù)據(jù)之間的聯(lián)系
因此可以調(diào)整動態(tài)長度 
 刪除 可以刪除最后一個數(shù)據(jù),刪除其他位置的數(shù)據(jù)的時候需要將相應(yīng)的數(shù)據(jù)前移
(刪除成本高)
 數(shù)據(jù)可以隨意刪除,只需要將前一個節(jié)點的指針指向后一個節(jié)點
 插入 可以在順序表最后添加一個新的數(shù)據(jù),在其他位置插入數(shù)據(jù)的時候需要將相應(yīng)的數(shù)據(jù)后移再插入
(插入成本高)
數(shù)據(jù)可以隨意插入,只需要將前一個節(jié)點的指針指向新的節(jié)點,再將新的節(jié)點的指針指向下一個節(jié)點 
 元素查詢 索引與內(nèi)存偏移正相關(guān),只需要知道索引就可以得到相應(yīng)的內(nèi)存地址,只需要執(zhí)行一次數(shù)據(jù)訪問就可以得到數(shù)據(jù)  需要一個節(jié)點一個節(jié)點的查找才能得到數(shù)據(jù),當(dāng)節(jié)點在末尾的時候需要遍歷整個鏈表才能得到數(shù)據(jù)。
(查詢成本高) 


1 人點贊