IT小白

这个屌丝很懒，什么也没留下！

热门标签

NzN的数据结构--单链表及实现

作者：IT小白 | 2024-05-03 04:37:41

踩

NzN的数据结构--单链表及实现

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。上一节我们了解到顺序表的内存空间必须是连续的，而当顺序表中有非常多的元素时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。那今天我们先来学习最基本的单链表吧！！！

一、链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

以火车车厢为例，淡季时车厢会减少，旺季时车厢会增加，只需要将火车里的某节车厢去掉/加上，每节车厢都是独立存在的。每节车厢都有车门，假设车门全都锁上了，需每次只能携带一把钥匙打开车门，最简单的做法就是每节车厢里都放下一节车厢的钥匙。

与顺序表不同的是，链表里的每节"车厢"都是独立申请的空间，称为“结点/节点”。链表是由一个个节点组成。一个节点主要由两部分组成：当前节点要保存的数据和一个指针用于保存下一个节点的地址（结构体指针）。

上图中指针变量 plist保存的是第一个节点的地址，plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只要把plist保存的内容修改为0x0012FFA0。

Q：为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

据此，我们就可以写出节点的结构：


//链表是由节点组成
typedef int SLTDataType;//方便代码的复用
typedef struct SListNode 
{
	SLTDataType data;//数据域
	struct SListNode* next;//指针域
}SLTNode;

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。

注意：

链式机构在逻辑上是连续的，在物理结构上不一定连续
节点一般是从堆上申请的
从堆上申请的空间，是按一定策略分配的，每次申请的空间可能连续，可能不连续

二、单链表的实现

首先在头文件中定义我们想要实现的功能接口：


//SList.h头文件
#include<stdio.h>
#include<stdlib.h>
//链表是由节点组成
typedef int SLTDataType;
typedef struct SListNode 
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
 
//打印单链表
void SLTPrint(SLTNode* phead);
 
//单链表的头插/尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
 
//单链表的头删/尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
 
//在单链表中查找存放x的节点
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除指定位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置的后一个节点
void SLTEraseAfter(SLTNode* pos);
//销毁单链表
void SListDestroy(SLTNode** pphead);

1. 打印单链表


//打印链表
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
    //从头节点开始依次遍历
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;//让pcur保存下一个节点的地址
	}
	printf("NULL\n");
}

2. 头插/尾插新节点

当我们需要插入新节点时，首先要申请一个新节点，为了提高代码的复用率，我们可以将申请新节点的功能单独封装。


//单链表定义新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return 1;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

现在已经申请了存放数据为x的新节点了，下面就可以进行插入操作。


//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//单链表为空，新节点作为phead
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	//单链表不为空，找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//出循环表明ptail->next为空，此时ptail就是尾结点
	ptail->next = newnode;
}
//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3. 头删/尾删节点


//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//单链表不能为空
	assert(*pphead);
	//单链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	//销毁尾节点
	free(ptail);
	ptail = NULL;
}
//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//单链表不能为空
	assert(*pphead);
	//让第二个节点变成新的头节点，释放第一个节点
	SLTNode* next = (*pphead)->next;//->的优先级高于*
	free(*pphead);
	*pphead = next;
}

4. 查找节点


SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//遍历单链表
	SLTNode* pcur = *pphead;
	while (pcur)//等价于pcur！=NULL
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

5. 在指定位置之前插入数据


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//单链表不能为空，否则pos就为空了
	assert(*pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//pos是头结点，直接头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
		return;
	}
	//pos不是头结点
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

6. 在指定位置之后插入数据


void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//注意顺序，防止pos->next指向新节点后，找不到下一个节点
	//先让newnode->next=pos->next
	//再让pos->next=newnode
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

7. 删除指定位置的节点


void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//pos刚好是头节点,执行头删
	if (*pphead == pos) 
	{
		SLTPopFront(pphead);
		return;
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

8. 删除指定位置的后一个节点


void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//pos->next不能为空(pos不能是尾节点)
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

9. 销毁单链表


void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不能为空
	SLTNode* pcur = *pphead;
	//链表需要一个一个节点去销毁，因为每个节点都是独立的
	while (pcur)
	{
		//先把后一个节点保存起来
		//再释放当前节点
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

三、单链表经典算法

1. 移除链表元素

题目链接：移除链表元素 - 力扣（LeetCode）


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //思路1：遍历链表，删除等于val的元素（执行删除操作比较麻烦）
    //思路2：定义新链表，遍历原链表，把值不为val的存到新链表里
    //定义新链表
    ListNode*newHead,*newTail;
    newHead=newTail=NULL;
    //遍历原链表
    ListNode*pcur=head;
    while(pcur)
    {
        //不是val，执行插入
        //刚开始新链表为空，插入的第一个节点既是头也是尾
        //插入第一个节点后，后面插入的节点都是新的尾节点
        if(pcur->val!=val)
        {
            if(newHead==NULL)
                newHead=newTail=pcur;
            else{
                newTail->next=pcur;
                newTail=newTail->next;
            }
        }
        pcur=pcur->next;
    }
    if(newTail)
        newTail->next=NULL;
    //返回新链表
    return newHead;
}

2. 反转链表/链表逆置

题目链接：反转链表 - 力扣（LeetCode）


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //思路1：创建新链表，遍历原链表的节点插入新链表
    //思路2：创建三个节点，分别指向前驱节点、当前节点和后继节点
    //假设n1指向空，n2指向第一个节点，n3指向第二个节点
    //n2不为空，就让n2反转指向n1，然后n1=n2，n2=n3，n3=n3->next
    //重复上面的步骤，只要n2不为空，就改变指向
    //先单独处理空链表
    if(head==NULL){
        return head;
    }
    ListNode* n1,*n2,*n3;
    n1=NULL,n2=head,n3=head->next;
    //遍历原链表，修改指向
    ListNode* pcur=head;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3){
            n3=n3->next;
        }
    }
    return n1;
}

3. 合并两个有序链表

题目链接：合并两个有序链表 - 力扣（LeetCode）


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //思路：定义两个指针和一个新链表，分别遍历两个链表，比较节点大小，决定插入顺序
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    ListNode *l1, *l2;
    l1 = list1, l2 = list2;
    //定义新链表
    ListNode *newHead, *newTail;
    newHead = newTail = NULL;
    //可以优化为newHead = newTail =(ListNode*)malloc(sizeof(ListNode))
    while (l1 && l2) {
        if (l1->val < l2->val) {
            // l1小，插入新链表
            if (newHead == NULL) {
                //链表为空
                newHead = newTail = l1;
            } else {
                //链表不为空，执行尾插
                newTail->next = l1;
                newTail = newTail->next;
            }
            l1 = l1->next;
        } else {
            // l2小，插入新链表
            if (newHead == NULL) {
                //链表为空
                newHead = newTail = l2;
            } else {
                //链表不为空，执行尾插
                newTail->next = l2;
                newTail = newTail->next;
            }
            l2 = l2->next;
        }
    }
    //跳出循环有两种情况，要么l1为空l2不为空，要么l2为空l1不为空
    //不可能l1和l2都为空
    if (l1) {
        newTail->next = l1; //把l1后面剩余的所有节点都插入进来
    }
    if (l2) {
        newTail->next = l2; //把l2后面剩余的所有节点都插入进来
    }
    return newHead;
}

我们可以对上面这段代码进行优化：


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //代码优化：主要问题在于链表可能为空，因此可以插入一个头节点（哨兵位）
    //后面所有的节点直接插在头节点（哨兵位）后面
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    ListNode *l1, *l2;
    l1 = list1, l2 = list2;
    //定义新链表
    ListNode *newHead, *newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));//申请头节点
    while (l1 && l2) {
        if (l1->val < l2->val) {
            //不需要判断头节点是否为空
            newTail->next = l1;
            newTail = newTail->next;
            l1 = l1->next;
        } else {
            //不需要判断头节点是否为空
            newTail->next = l2;
            newTail = newTail->next;
            l2 = l2->next;
        }
    }
    //跳出循环有两种情况，要么l1为空l2不为空，要么l2为空l1不为空
    //不可能l1和l2都为空
    if (l1) {
        newTail->next = l1; //把l1后面剩余的所有节点都插入进来
    }
    if (l2) {
        newTail->next = l2; //把l2后面剩余的所有节点都插入进来
    }
    //return newHead;//头节点（哨兵位）不存储有效数据
    ListNode*ret=newHead->next;
    free(newHead);//释放malloc申请的空间
    return ret;
}

4. 链表的中间节点

题目链接：链表的中间结点 - 力扣（LeetCode）


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    //思路1：遍历链表，计算节点个数，除2找到中间节点
    //思路2：快慢指针，让快指针每次走两步，慢指针每次走一步
    //当fast或者fast->next为空时，slow刚好是中间节点
    ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)//有一个为NULL都不能进入循环
    //注意fast&&fast->next顺序不能颠倒，因为如果fast为空，那它就不存在next了
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

5. 分割链表

题目链接：分割链表 - 力扣（LeetCode）


/**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    //思路：定义大链表和小链表，遍历原链表，把节点放到对应的链表里
    //最后把小链表的尾节点和大链表的第一个节点相连
    //注意：为了防止链表为空，两个链表我们都设置一个哨兵位
    //因此两个链表相连时，小链表的尾节点要指向greaterHead->next
    if(head==NULL)
        return head;
    //创建两个带头链表
    ListNode*lessHead,*lessTail;
    ListNode*greaterHead,*greaterTail;
    lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
    greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));
    //遍历原链表，将节点放到对应的链表中
    ListNode*pcur=head;
    while(pcur){
        if(pcur->val < x){
            //放到小链表里
            lessTail->next=pcur;
            lessTail=lessTail->next;
        }else{
            //放到大链表里
            greaterTail->next=pcur;
            greaterTail=greaterTail->next;
        }
        pcur=pcur->next;
    }
    greaterTail->next=NULL;//必须要把大链表尾节点置空
    //大小链表相连
    lessTail->next=greaterHead->next;
    ListNode*ret=lessHead->next;
    free(greaterHead);
    free(lessHead);
    return ret;
}

6. 环形约瑟夫问题

题目链接：环形链表的约瑟夫问题_牛客网 (nowcoder)


#include <stdlib.h>
typedef struct ListNode ListNode;
//创建新节点
ListNode* BuyNode(int x){
    ListNode*newNode=(ListNode*)malloc(sizeof(ListNode));
    //可写可不写，一般不会申请失败
    //if(newNode==NULL){
    //    exit(1);
    //}
    newNode->val=x;
    newNode->next=NULL;
    return newNode;
}
//创建不带头单向循环链表
ListNode* createList(int n){
    ListNode*phead=BuyNode(1);
    ListNode*ptail=phead;
    for(int i=2;i<=n;i++)
    {
        ptail->next=BuyNode(i);
        ptail=ptail->next;
    }
    //链表要首尾相连，才是循环链表
    ptail->next=phead;
    return ptail;//避免m=1，刚开始就要删除，但prev还为NULL
}
int ysf(int n, int m ) {
    //创建不带头单向循环链表
    ListNode*prev=createList(n);//接收尾节点
    ListNode*pcur=prev->next;
    int count=1;
    //逢m删除当前节点
    while(pcur->next!=pcur){
        if(count==m){
            //删除当前节点
            prev->next=pcur->next;
            free(pcur);
            //删除pcur节点后，要让pcur走到新的位置，count置为初始值
            pcur=prev->next;
            count=1;
        }else{
            //pcur往后走
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    //此时pcur就是剩下的唯一一个节点
    return pcur->val;
}

四、链表的分类

链表结构多样，不同组合共有8种：

单向：只能通过前驱节点找到下一个节点

双向：当前节点有指向下一节点的指针，下一个节点也有指向前驱节点的指针

不带头：每个节点都保存有效数据

带头：在第一个节点之前还有一个无效节点，不保存任何有效数据（头节点：哨兵位）

不循环：最后一个节点的指针指向NULL

循环：最后一个节点的指针指回第一个节点

虽然链表结构多样，但是最常用还是单链表和双向带头循环链表，环形链表也比较常见，但考察不如前面两个多。

单链表：单链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空NULL 。
环形链表：如果我们令单链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：与单链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

本章已经向大家讲解了单链表的相关内容，那下一章我们就一起来学习双向链表的具体实现吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/527824

NzN的数据结构--单链表及实现

一、 链表的概念及结构

二、单链表的实现

1. 打印单链表

2. 头插/尾插新节点

3. 头删/尾删节点

4. 查找节点

5. 在指定位置之前插入数据

6. 在指定位置之后插入数据

7. 删除指定位置的节点

8. 删除指定位置的后一个节点

9. 销毁单链表

三、单链表经典算法

1. 移除链表元素

2. 反转链表/链表逆置

3. 合并两个有序链表

4. 链表的中间节点

5. 分割链表

6. 环形约瑟夫问题

四、链表的分类

一、链表的概念及结构