數據結構 – 單鏈表 C++ 實現

• 2022 年 3 月 30 日
• 筆記
• 數據結構

單鏈表

單鏈表的定義

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

此處 LNode 強調一個結點，*LinkList 強調一個單鏈表的頭指針，本例中只有頭指針使用 *LinkList ；

單鏈表的頭指針和頭節點

若單鏈表沒有頭節點，那麼單鏈表的頭指針則指向鏈表的第一個元素；若由頭節點，頭指針指向頭節點；例如頭指針為 L；如果鏈表為空，則有 L == NULL，若有頭節點，則有 L->next = NULL；

注意此處的指向問題應當透徹理解指針的概念，指向理解為元素地址；此處的 L 為頭指針；在沒有頭節點時指向第一個元素，L 就是第一個元素的地址，若沒有元素，即沒有第一個元素，那麼 L == NULL；如果有頭節點，那麼 L 為頭節點的地址，因此 L->next 即為元素的第一個結點，故當鏈表為空時 L->next == NULL；

本例中的單鏈表均為帶頭節點的單鏈表；

初始化一個單鏈表

初始化單鏈表的主要目的在於建立一個頭節點，並讓 L 指向頭節點；

L 為指向結點的指針，動態申請的記憶體大小為 sizeof(LNode)，L 的類型為 LinKList 或者說 LNode* 因此需要轉化為 LinkList；程式碼如下：

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

創建一個單鏈表

頭插法

即將新元素插入到鏈表的第一個位置

void List_HeadInsert(LinkList &L) {
    for(int i = 1; i <= 10; i++) { //將 1 ~ 10 按頭插法插入單鏈表
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }
    //按照頭插法的插入方式結果為倒序
    Show_List(L);
}

測試本段程式碼

#include<iostream>
#include<cstdlib>
using namespace std; 

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_HeadInsert(LinkList &L) {
    for(int i = 1; i <= 10; i++) { //將 1 ~ 10 按頭插法插入單鏈表
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }
    //按照頭插法的插入方式結果為倒序
    Show_List(L);
}

int main() {
    LinkList L;
    ListInitite(L);
    List_HeadInsert(L);
    return 0;
}

運行結果

10 9 8 7 6 5 4 3 2 1

尾插法

即新的元素放在鏈表尾

使用尾插法，需要定義一個尾指針 r，尾指針始終指向鏈表的最後一個元素；剛開始為空鏈表，尾指針指向頭節點，即和 L 相等，此後每插入一個新的結點，新的結點成為新的尾結點，r 指向此結點；

void List_TailInsert(LinkList &L) {
    LNode* r = L;
    for(int i = 1; i <= 10; i++) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = r->next;
        r->next = p;
        r = p;
    }
}

測試：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_HeadInsert(LinkList &L) {
    for(int i = 1; i <= 10; i++) { //將 1 ~ 10 按頭插法插入單鏈表
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }
    //按照頭插法的插入方式結果為倒序
    Show_List(L);
}

void List_TailInsert(LinkList &L) {
    LNode* r = L;
    for(int i = 1; i <= 10; i++) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = r->next;
        r->next = p;
        r = p;
    }
}

int main() {
    LinkList L;
    ListInitite(L);
    List_TailInsert(L);
    //按尾插法插入為順序 
    Show_List(L);
    return 0;
}

測試結果：

1 2 3 4 5 6 7 8 9 10

返回鏈表的長度

int Length(LinkList L) {
    LNode* p = L;
    int length = 0;
    while (p->next) {
        length++;
        p = p->next;
    }
    return length;
}

鏈表的查詢

按序號查找結點的值

即查找第 i 個結點的值，最終返回此結點

LNode* GetElem(LinkList L, int i) {
    if(i == 0) {
        return L;
    }
    if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
        return NULL;
    }
    LNode* p = L;
    int now = 0;
    while(p && now < i) {
        p = p->next;
        now++;
    }
    return p;
}

測試：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_TailInsert(LinkList &L) {
    LNode* r = L;
    for(int i = 1; i <= 10; i++) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = r->next;
        r->next = p;
        r = p;
    }
}

int Length(LinkList L) {
    LNode* p = L;
    int length = 0;
    while (p->next) {
        length++;
        p = p->next;
    }
    return length;
}


LNode* GetElem(LinkList L, int i) {
    if(i == 0) {
        return L;
    }
    if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
        return NULL;
    }
    LNode* p = L;
    int now = 0;
    while(p && now < i) {
        p = p->next;
        now++;
    }
    return p;
}


int main() {
    LinkList L;
    ListInitite(L);
    List_TailInsert(L);
    LNode* ip = GetElem(L, 5);
    Show_List(L);
    if(ip) {
        printf("\n%d", ip->data);
    }
    return 0;
}

測試結果：

1 2 3 4 5 6 7 8 9 10
5

按值查找結點

LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while(p && p->data != e) {
        p = p->next;
    }
    return p;
}

插入結點

在鏈表的第 i 個位置插入元素 e

插入新的元素後共有 len + 1 個元素，插入位置也必須在 [1, len + 1]，因此插入位置必須在這個範圍內；首先獲得第 i – 1 個結點，然後進行操作；

bool ListInsert(LinkList &L, int i, ElemType e) {
    if(i < 1 || i > Length(L) + 1) {
        printf("插入位置錯誤\n");
        return false;
    }
    LNode *pre, *s;
    s->data = e;
    pre = GetElem(L, i - 1);
    s->next = pre->next;
    pre->next = s;
    return true;
}

測試程式碼：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
}

void Show_List(LinkList L) {
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
}

void List_HeadInsert(LinkList &L) {
	for(int i = 1; i <= 10; i++) { //將 1 ~ 10 按頭插法插入單鏈表
		LNode* p = (LNode*)malloc(sizeof(LNode));
		p->data = i;
		p->next = L->next;
		L->next = p;
	}
}


int Length(LinkList L) {
	LNode* p = L->next;
	int length = 0;
	while(p) {
		length++;
		p = p->next;
	}
	return length;
}


LNode* GetElem(LinkList L, int i) {
	if(i == 0) {
		return L;
	}
	if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
		return NULL;
	}
	LNode* p = L;
	int now = 0;
	while(p && now < i) {
		p = p->next;
		now++;
	}
	return p;
}


bool ListInsert(LinkList &L, int i, ElemType e) {
    if(i < 1 || i > Length(L) + 1) {
        printf("插入位置錯誤\n");
        return false;
    }
    LNode *pre = GetElem(L, i - 1);
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = pre->next;
    pre->next = s;
    return true;
}

int main() {
	LinkList L;
	ListInitite(L);
	List_HeadInsert(L);
	ListInsert(L, 5, 100);
	Show_List(L);
	return 0;
}

測試結果：

10 9 8 7 100 6 5 4 3 2 1

前插和後插

前插即在一個已知結點的前面插入新的結點，後插即在一個已知結點的後面插入新的結點；

上面的插入函數即在結點的後面插入新的結點，首先需要得到第 i – 1 個結點，然後再此結點後面插入新的結點，即為後插；

前插操作也是類似，在某個結點的前面插入結點，首先獲取到此結點的前一個結點，然後在前一個結點後面插入新的結點；但這種插入方式必須首先獲取到已知結點的前一個結點，查找過程必須遍歷當前結點之前的所有元素才能找到前一個結點；時間複雜度為 O(n)，採用另一種方式可以巧妙的將複雜度降低到 O(1)；方法為在已知結點的後面插入新的結點，然後交換新節點與已知結點的值，就實現了相同的目的；

void FrontInsert(LNode* node, ElemType e) {
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = node->next;
    node->next = s;
    ElemType temp = node->data;
    node->data = s->data;
    s->data = temp;
}

2~5 行操作為將新的結點插入到已知結點的後面，6~8 行操作為交換兩個結點內的值；

測試：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_HeadInsert(LinkList &L) {
    for(int i = 1; i <= 10; i++) { //將 1 ~ 10 按頭插法插入單鏈表
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }
}


int Length(LinkList L) {
    LNode* p = L->next;
    int length = 0;
    while(p) {
        length++;
        p = p->next;
    }
    return length;
}


LNode* GetElem(LinkList L, int i) {
    if(i == 0) {
        return L;
    }
    if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
        return NULL;
    }
    LNode *p = L;
    int now = 0;
    while(p && now < i) {
        p = p->next;
        now++;
    }
    return p;
}


void FrontInsert(LNode* &node, ElemType e) {
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = node->next;
    node->next = s;
    ElemType temp = node->data;
    node->data = s->data;
    s->data = temp;
}


int main() {
    LinkList L;
    ListInitite(L);
    List_HeadInsert(L);
    Show_List(L);
    LNode *node = GetElem(L, 5);
    FrontInsert(node, 50);
    printf("\n");
    Show_List(L);
    return 0;
}

測試結果：

10 9 8 7 6 5 4 3 2 1
10 9 8 7 50 6 5 4 3 2 1

刪除結點操作

刪除鏈表位置為 i 的結點，並將刪除的結點存放在 node 中

bool ListDelete(LinkList &L, int i, LNode* &node) {
    if(i < 1 || i > Length(L)) {
        printf("刪除位置錯誤");
        return false;
    }
    LNode *p = GetElem(L, i - 1);
    LNode *q = p->next;
    p->next = q->next;
    node = q;
    free(q);
    return true;
}

上述程式碼有錯，free(void* p) 函數的作用是回收 動態分配給 p 的空間，不論有多少指針指向 p 所指向的空間，因此將對於 node = q，在 free(q) 以後 node 所指向的空間也被回收了，因此此處最好不返回結點，返回結點中的值；修正後的程式碼如下：

bool ListDelete(LinkList &L, int i, ElemType &del) {
    if(i < 1 || i > Length(L)) {
        printf("刪除位置錯誤");
        return false;
    }
    LNode *p = GetElem(L, i - 1);
    LNode *q = p->next;
    p->next = q->next;
    del = q->data;
    free(q);
    return true;
}

測試：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_TailInsert(LinkList &L) {
    LNode* r = L;
    for(int i = 1; i <= 10; i++) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = r->next;
        r->next = p;
        r = p;
    }
}

int Length(LinkList L) {
    LNode* p = L->next;
    int length = 0;
    while(p) {
        length++;
        p = p->next;
    }
    return length;
}


LNode* GetElem(LinkList L, int i) {
    if(i == 0) {
        return L;
    }
    if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
        return NULL;
    }
    LNode *p = L;
    int now = 0;
    while(p && now < i) {
        p = p->next;
        now++;
    }
    return p;
}


bool ListDelete(LinkList &L, int i, ElemType &del) {
    if(i < 1 || i > Length(L)) {
        printf("刪除位置錯誤");
        return false;
    }
    LNode *p = GetElem(L, i - 1);
    LNode *q = p->next;
    p->next = q->next;
    del = q->data;
    free(q);
    return true;
}

int main() {
    LinkList L;
    ListInitite(L);
    List_TailInsert(L);
    Show_List(L);
    ElemType del;
    ListDelete(L, 7, del);
    printf("\n");
    Show_List(L);
    printf("\n刪除的元素為：%d", del);
    return 0;
}

結果：

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 8 9 10
刪除的元素為：7

此處刪除的實現依然為後刪，即找到將要刪除結點的前一個結點進行刪除；即給定一個已知結點需要對其進行刪除，首先應該找到其前驅節點才能進行刪除；和前插法類似，也有減少其複雜度的方法，即首先交換待刪除結點後其後繼節點的值，然後刪除其後繼節點；實現方式和前插法類似：

void Del(LinkList &L, LNode* &p) {
    LNode* q = p->next;
    ElemType temp = q->data;
    q->data = p->data;
    p->data = temp;
    p->next = q->next;
    free(q);
}

當然此時對於極端情況，即要刪除的元素為最後一個元素時不適用；

測試：

#include<iostream>
#include<cstdlib>
using namespace std;

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

void ListInitite(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
}

void Show_List(LinkList L) {
    LNode* p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

void List_TailInsert(LinkList &L) {
    LNode* r = L;
    for(int i = 1; i <= 10; i++) {
        LNode* p = (LNode*)malloc(sizeof(LNode));
        p->data = i;
        p->next = r->next;
        r->next = p;
        r = p;
    }
}

int Length(LinkList L) {
    LNode* p = L->next;
    int length = 0;
    while(p) {
        length++;
        p = p->next;
    }
    return length;
}


LNode* GetElem(LinkList L, int i) {
    if(i == 0) {
        return L;
    }
    if(i < 1 || i > Length(L)) {   //若超出鏈表範圍
        return NULL;
    }
    LNode *p = L;
    int now = 0;
    while(p && now < i) {
        p = p->next;
        now++;
    }
    return p;
}



void Del(LinkList &L, LNode* &p) {
    LNode* q = p->next;
    ElemType temp = q->data;
    q->data = p->data;
    p->data = temp;
    p->next = q->next;
    free(q);
}

int main() {
    LinkList L;
    ListInitite(L);
    List_TailInsert(L);
    Show_List(L);
	LNode *p = GetElem(L, 4);
	Del(L, p);
	printf("\n");
	Show_List(L);
    return 0;
}

結果：

1 2 3 4 5 6 7 8 9 10
1 2 3 5 6 7 8 9 10

單鏈表的銷毀

void Destory(LinkList &L) {
    LNode* p = L;
    LNode* q = L;
    while (q)
    {
        p = q;
        q = q->next;
        free(p);
    }
   free(L);  
   L=NULL;
}