数据结构 – 单链表 C++ 实现

单链表

单链表的定义

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 = (LinkList)malloc(sizeof(LNode)) 此处申请一个头节点的空间并返回申请到空间的地址返回,必须传入 L 的应用或者二级指针;

若直接传入 L 那么将会拷贝一份 L 指针给 L1 ,那么申请到的空间地址将返回给 L1 而不是L,如下图

image-20220330232913595

因此必须传入 L 的引用或者 L 的指针;

传入 L(无效)

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

传入引用

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

传入 L 的指针

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;
} 
页面下部广告