天天看點
傳回

一文帶你看懂連結清單的奧秘 手把手教你實作連結清單的各項操作

一文帶你看懂連結清單的奧秘 手把手教你實作連結清單的各項操作

很多人剛開始學習資料結構與算法這門課的時候都對連結清單有一些恐懼、懵逼，看不懂書上要表達的意思，照抄書上代碼卻又運作不起來，真的是10行代碼9個error，把小夥伴們折磨的苦不堪言，今天部落客就帶領大家來探究一下線性表的順序表達和鍊式表達，手把手的教大家實作連結清單的各種操作。

本文最後有完整的實作函數和完整的測試樣例

什麼的連結清單

說到連結清單，首先我們要知道連結清單是什麼。很多小夥伴都知道連結清單，但是對順序表都不太了解。其實連結清單是線性表的一種鍊式表達，而順序表則是線性表的順序表達。

那線性表又是什麼呢？線性表是具有相同資料類型的n(n≥0)個元素的有限序列，n為表長即表的長度，當n為0時，為空表。

線性表一般有以下9個基本操作，其他的複雜操作一般依賴于這些基本操作來實作：

  1. InitList(&L):初始化表。建構一個空的線性表
  2. Length(L):求表長。傳回線性表L的長度，即L中元素的個數。
  3. LocateElem(L,e):按值查找操作。在表L中查找具有給定關鍵字值的元素。
  4. GetElem(L,i):按位查找操作。擷取表L中第i個位置的元素的值。
  5. ListInsert(&L,i,e):插入操作。在表L中的第i個位置插入指定元素e。
  6. ListDelect(&L,i,&e):删除操作。删除表L中第i個位置的元素，并用e傳回删除元素的值。
  7. PrintList(L):輸出操作。按前後順序輸出線性表L的所有元素值。
  8. Empty(L):判空操作。若L為空表，則傳回true,否則傳回false。
  9. DestroyList(&L):銷毀操作。銷毀線性表，并釋放線性表L所占的記憶體空間。

實作操作之前的采坑指南

在實作各個操作之前，先做一些說明一些采坑指南，做一些基礎的補充說明。

  • 在函數參數中使用&，這是在C++中是一種方法，表示引用。如果傳入變量，并且在函數内需要對變量進行改變，則需要使用引用&。當時，指針學的比較好的同學也可以使用指針來完成，這裡為了簡單，都将使用&，引用來進行。
  • 在各個教材的代碼中都會出現ElemType的資料類型，其實這是一個抽象的寫法，這裡的ElemType可以是任何一種資料類型，例如int,char,double等等，書上為了統一，都使用了ElemType這種抽象的寫法，以至于很多同學照抄書上的代碼會一直報錯，運作不了。
  • 線性表中的元素位序是從1開始的，而數組是從0開始。
  • 基本操作的實作取決于采用哪種存儲結構，儲存結構不同，實作算法也不同

就先做這4點補充說明，我們下面進行實作，語音描述我們使用C++進行描述，但是沒有使用過多的C++專用文法，隻要有C基礎的同學都能夠看懂，不需要學過C++。

由于大家都對連結清單比較感興趣，那本文我們就先說說連結清單。

連結清單的實作

連結清單，即線性表的鍊式表達。鍊式存儲線性表時，不需要使用位址連續的存儲單元，即它不要求邏輯上相鄰的兩個元素在實體位置上也相鄰，它通過“鍊”建立起元素之間的邏輯關系，是以對線性表的插入、删除不需要移動元素，而隻需要修改指針。

單連結清單的定義

線性表的鍊式存儲又稱作單連結清單，它是指通過一組任意存儲單元來存儲線性表中的資料元素。為了建立元素之間的線性關系，對于每個連結清單結點，除存放元素自身的資訊外，還需要存放一個指向其後繼的指針。

結點類型描述如下

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNoed,*LinkList;

其中data的資料類型可以是任意資料類型，例如int，char，或者一些結構體資料類型。。。下面實作過程中，我們統一使用int類型做示範。

typedef struct LNode{
    int data;
    struct LNode *next;
}LNoed,*LinkList;

建立單連結清單

初始化一個連結清單

int InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //申請一個頭結點
    if (!L)  return 0;
    L->next = NULL;                   //頭結點的指針域置空
    return 1;
}

全部程式為：建立成功則輸出1，否則輸出0

#include<iostream>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNoed,*LinkList;

int InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //申請一個頭結點
    if (!L)  return 0;
    L->next = NULL;                   //頭結點的指針域置空
    return 1;
}


int main(){
    LinkList L;
    cout<<InitList(L);
    return 0;
}

向連結清單中插入資料

插入資料有很多種實作方法，這裡提供4種實作方法供大家參考，其他的實作方法都和這類似。

  1. 一直插入，直到輸入特定的值停止

    1.1 頭插法

    1.2 尾插法

  2. 将一個特定的值插入到特定的位置

    2.1 插在該位置之前

    2.2 插在該位置之後

一直插入，直到輸入特定的值停止 頭插法實作

頭插法是每次插入的資料都會插入到第一個資料的位置，其他的資料在其後面。

代碼實作如下:直到輸入6666，停止插入。

LinkList List_Insert_1(LinkList &L){
    int mid;//用于接收輸入
    scanf("%d",&mid);//讀取輸入值
    while(mid != 6666){//如果輸入的不是6666的話，就一直插入
        LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
        s->data = mid;//為新結點指派
        s->next = L->next;//新結點的下一個位置指向連結清單的第一個元素
        L->next = s;//連結清單的下一個位置指向s
        scanf("%d",&mid);//讀取輸入值
    }
    return L;
}

一直插入，直到輸入特定的值停止 尾插法實作。

因為頭插法插入的資料順序是輸入順序的倒序，所有我們有時候需要使用尾插法。尾插法的話就需要一個指針來記錄連結清單中最後一個元素的位置，來進行插入。代碼實作如下：

LinkList List_Insert_2(LinkList &L){
    int mid;//用于接收輸入
    scanf("%d",&mid);//讀取輸入值
    LNode *r = L;//用于記錄最後一個結點
    while (r->next)//走到目前連結清單的最後
        r = r->next;
    while(mid != 6666){//如果輸入的不是6666的話，就一直插入
        LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
        s->data = mid;//為新結點指派
        s->next = NULL;//下一個位置為空
        r->next = s;//将新結點插入到連結清單的最後
        r = s;//連結清單最後的位置為s
        scanf("%d",&mid);//讀取輸入值
    }
    return L;
}

将一個特定的值插入到特定的位置 插在該位置之前 

//将一個特定的值插入到特定的位置 插在該位置之前
//在連結清單L中，在第i個位置前面插入資料e
LinkList List_Insert_3(LinkList &L,int i,int e){
    int pos = 1;//用于記錄位置
    LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
    s->data = e;//指派新結點
    LNode *mid = L->next;//用來移動到指定位置
    while (pos < i-1){
        mid = mid->next;
        pos++;
    }
    s->next = mid->next;
    mid->next = s;
    return L;
}

将一個特定的值插入到特定的位置 插在該位置之後 

//将一個特定的值插入到特定的位置 插在該位置之後
//在連結清單L中，在第i個位置後面插入資料e
LinkList List_Insert_4(LinkList &L,int i,int e){
    int pos = 1;//用于記錄位置
    LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
    s->data = e;//指派新結點
    LNode *mid = L->next;//用來移動到指定位置
    while (pos < i){
        mid = mid->next;
        pos++;
    }
    s->next = mid->next;
    mid->next = s;
    return L;
}

列印連結清單中所有元素

為了同學們友善調試，驗證自己的代碼，我們先實作一下列印操作，這樣便于同學們調試、驗證

//列印連結清單中所有的元素
void Print_List(LinkList L){
    LNode *mid = L->next;
    while (mid){//隻要mid不為空，則一直輸出
        printf("%d ",mid->data);//列印目前值
        mid = mid->next;//走到下一個結點
    }
    cout<<endl;
}

按序号擷取連結清單中結點的值 

//按序号擷取連結清單中結點的值
LNode *GetElem(LinkList L,int i){//擷取連結清單L中第i個結點
    int pos = 1;//用于記錄序号，連結清單是從1開始計數的
    LNode * mid = L->next;
    if(i == 0)//i = 0時傳回表頭
        return L;
    if(i < 1)//i < 1時無效，傳回NULL
        return NULL;
    while (pos < i && mid) {//移動到第i個結點
        mid = mid->next;
        pos++;
    }
    return mid;
}

按值查找連結清單中的結點 

//按值查找表結點
//擷取表中第一個值為e的結點
LNode *LocateElem(LinkList L,int e){
    LNode * mid = L->next;
    while (mid){
        if(mid->data == e)
            return mid;
        mid = mid->next;
    }
    return NULL;
}

删除第i個結點 

//删除第i個結點，傳回删除的值，并且用e将删除的值傳出來
int DeleteNode_1(LinkList &L,int i,int &e){
    int pos = 1;//用于記錄結點序号
    LNode * mid = L->next;
    while (pos < i-1 && mid){//移動到第i-1個結點
        mid = mid->next;
        pos++;
    }
    e = mid->next->data;//用e傳輸删除的值
    LNode * mid_2 = mid->next;//指向第i個結點
    mid->next = mid_2->next;//第i-1個結點直接指向第i+1個結點
    free(mid_2);//釋放第i個結點的記憶體
    return e;//傳回删除的值
}

求表長 

//求表長
int List_Length(LinkList L){
    int length = 0;
    LNode * mid = L;
    while (mid->next){
        length++;
        mid = mid->next;
    }
    return length;
}

完整的程式 

#include<iostream>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一個單連結清單
int InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //申請一個頭結點
    if (!L)  return 0;
    L->next = NULL;                   //頭結點的指針域置空
    return 1;
}

//一直插入，直到輸入特定的值停止 頭插法
LinkList List_Insert_1(LinkList &L){
    int mid;//用于接收輸入
    scanf("%d",&mid);//讀取輸入值
    while(mid != 6666){//如果輸入的不是6666的話，就一直插入
        LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
        s->data = mid;//為新結點指派
        s->next = L->next;//新結點的下一個位置指向連結清單的第一個元素
        L->next = s;//連結清單的下一個位置指向s
        scanf("%d",&mid);//讀取輸入值
    }
    return L;
}

//一直插入，直到輸入特定的值停止 尾插法
LinkList List_Insert_2(LinkList &L){
    int mid;//用于接收輸入
    scanf("%d",&mid);//讀取輸入值
    LNode *r = L;//用于記錄最後一個結點
    while (r->next)//走到目前連結清單的最後
        r = r->next;
    while(mid != 6666){//如果輸入的不是6666的話，就一直插入
        LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
        s->data = mid;//為新結點指派
        s->next = NULL;//下一個位置為空
        r->next = s;//将新結點插入到連結清單的最後
        r = s;//連結清單最後的位置為s
        scanf("%d",&mid);//讀取輸入值
    }
    return L;
}

//将一個特定的值插入到特定的位置 插在該位置之前
//在連結清單L中，在第i個位置前面插入資料e
LinkList List_Insert_3(LinkList &L,int i,int e){
    int pos = 1;//用于記錄位置
    LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
    s->data = e;//指派新結點
    LNode *mid = L->next;//用來移動到指定位置
    while (pos < i-1){
        mid = mid->next;
        pos++;
    }
    s->next = mid->next;
    mid->next = s;
    return L;
}

//将一個特定的值插入到特定的位置 插在該位置之後
//在連結清單L中，在第i個位置後面插入資料e
LinkList List_Insert_4(LinkList &L,int i,int e){
    int pos = 1;//用于記錄位置
    LNode *s = (LNode *)malloc(sizeof(LNode));//建立新結點，并配置設定空間
    s->data = e;//指派新結點
    LNode *mid = L->next;//用來移動到指定位置
    while (pos < i){
        mid = mid->next;
        pos++;
    }
    s->next = mid->next;
    mid->next = s;
    return L;
}

//列印連結清單中所有的元素
void Print_List(LinkList L){
    LNode *mid = L->next;
    while (mid){//隻要mid不為空，則一直輸出
        printf("%d ",mid->data);//列印目前值
        mid = mid->next;//走到下一個結點
    }
    cout<<endl;
}

//按序号擷取連結清單中結點的值
//擷取連結清單L中第i個結點
LNode *GetElem(LinkList L,int i){
    int pos = 1;//用于記錄序号，連結清單是從1開始計數的
    LNode * mid = L->next;
    if(i == 0)//i = 0時傳回表頭
        return L;
    if(i < 1)//i < 1時無效，傳回NULL
        return NULL;
    while (pos < i && mid) {//移動到第i個結點
        mid = mid->next;
        pos++;
    }
    return mid;
}

//按值查找表結點
//擷取表中第一個值為e的結點
LNode *LocateElem(LinkList L,int e){
    LNode * mid = L->next;
    while (mid){
        if(mid->data == e)
            return mid;
        mid = mid->next;
    }
    return NULL;
}

//删除第i個結點，傳回删除的值，并且用e将删除的值傳出來
int DeleteNode_1(LinkList &L,int i,int &e){
    int pos = 1;//用于記錄結點序号
    LNode * mid = L->next;
    while (pos < i-1 && mid){//移動到第i-1個結點
        mid = mid->next;
        pos++;
    }
    e = mid->next->data;//用e傳輸删除的值
    LNode * mid_2 = mid->next;//指向第i個結點
    mid->next = mid_2->next;//第i-1個結點直接指向第i+1個結點
    free(mid_2);//釋放第i個結點的記憶體
    return e;//傳回删除的值
}

//求表長
int List_Length(LinkList L){
    int length = 0;
    LNode * mid = L;
    while (mid->next){
        length++;
        mid = mid->next;
    }
    return length;
}
int main(){
    LinkList La,Lb;

    //建立連結清單
    cout<<"建立一個空連結清單 La"<<endl;
    if(InitList(La))
        cout<<"La建立成功"<<endl;
    else
        cout<<"La建立失敗"<<endl;
    cout<<"建立一個空連結清單 Lb"<<endl;

    if(InitList(Lb))
        cout<<"Lb建立成功"<<endl;
    else
        cout<<"Lb建立失敗"<<endl;
    cout<<"============================分隔符============================"<<endl<<endl;

    //插入資料
    //1. 一直插入資料，隻到輸入6666時停止，采用頭插法。 向La中按順序插入1 3 5 7 9 11 13 15
    cout<<"一直插入資料，隻到輸入6666時停止，采用頭插法。 向La中按順序插入1 3 5 7 9 11 13 15"<<endl;
    List_Insert_1(La);
    //2. 一直插入資料，隻到輸入6666時停止，采用尾插法。 向La中按順序插入2 4 6 8 10 12 14
    cout<<"一直插入資料，隻到輸入6666時停止，采用尾插法。 向La中按順序插入2 4 6 8 10 12 14"<<endl;
    List_Insert_2(Lb);
    //列印La
    cout<<"La為："<<endl;
    Print_List(La);
    //列印Lb
    cout<<"Lb為："<<endl;
    Print_List(Lb);
    //3. 在La第三個位置前插入333
    cout<<"在La第三個位置前插入333"<<endl;
    List_Insert_3(La,3,333);
    //列印插入後的La
    cout<<"插入後的La為："<<endl;
    Print_List(La);
    //4. 在LB第三個位置後插入444
    cout<<"在La第三個位置前插入333"<<endl;
    List_Insert_4(Lb,3,444);
    //列印插入後的Lb
    cout<<"插入後的Lb為："<<endl;
    Print_List(Lb);
    cout<<"============================分隔符============================"<<endl<<endl;

    //擷取La第2個值
    cout<<"La的第2個值為: "<<GetElem(La,2)->data<<endl;
    //擷取Lb第3個值
    cout<<"Lb的第3個值為: "<<GetElem(Lb,3)->data<<endl;
    cout<<"============================分隔符============================"<<endl<<endl;

    //擷取La中值為5的結點
    cout<<"La中值為5的結點的值為: "<<LocateElem(La,5)->data<<endl;
    cout<<"============================分隔符============================"<<endl<<endl;

    //删除La中第4個值
    int e;
    cout<<"La為："<<endl;
    Print_List(La);
    cout<<"删除La中第4個值"<<endl;
    DeleteNode_1(La,4,e);
    cout<<"删除後的La為："<<endl;
    Print_List(La);
    cout<<"Lb為："<<endl;
    Print_List(Lb);
    cout<<"删除Lb中第6個值"<<endl;
    DeleteNode_1(Lb,6,e);
    cout<<"删除後的Lb為:"<<endl;
    Print_List(Lb);
    cout<<"============================分隔符============================"<<endl<<endl;

    cout<<"La為："<<endl;
    Print_List(La);
    cout<<"La的表長為："<<List_Length(La)<<endl;
    cout<<"Lb為："<<endl;
    Print_List(Lb);
    cout<<"Lb的表長為："<<List_Length(Lb)<<endl;
    cout<<"============================分隔符============================"<<endl<<endl;


    return 0;
}      
建立一個空連結清單 La
La建立成功
建立一個空連結清單 Lb
Lb建立成功
============================分隔符============================

一直插入資料，隻到輸入6666時停止，采用頭插法。 向La中按順序插入1 3 5 7 9 11 13 15
1 3 5 7 9 11 13 15 6666
一直插入資料，隻到輸入6666時停止，采用尾插法。 向La中按順序插入2 4 6 8 10 12 14
2 4 6 8 10 12 14 6666
La為：
15 13 11 9 7 5 3 1 
Lb為：
2 4 6 8 10 12 14 
在La第三個位置前插入333
插入後的La為：
15 13 333 11 9 7 5 3 1 
在La第三個位置前插入333
插入後的Lb為：
2 4 6 444 8 10 12 14 
============================分隔符============================

La的第2個值為: 13
Lb的第3個值為: 6
============================分隔符============================

La中值為5的結點的值為: 5
============================分隔符============================

La為：
15 13 333 11 9 7 5 3 1 
删除La中第4個值
删除後的La為：
15 13 333 9 7 5 3 1 
Lb為：
2 4 6 444 8 10 12 14 
删除Lb中第6個值
删除後的Lb為:
2 4 6 444 8 12 14 
============================分隔符============================

La為：
15 13 333 9 7 5 3 1 
La的表長為：8
Lb為：
2 4 6 444 8 12 14 
Lb的表長為：7
============================分隔符============================


Process finished with exit code 0
結點 連結清單 線性表
上一篇: protocol family unavailable
下一篇: You Must Rebuild It With Bitcode Enabled (Xcode Setting ENABLE_BITCODE) 解決方案

繼續閱讀