数据结构：单链表

🕗 发布于 2024-07-21 17:13 数据结构

1、链表的概念和结构

链表是物理存储结构上非连续，非顺序的存储结构，逻辑顺序是通过链表指针实现的。

链式结构在逻辑上是连续的，在物理上是不一定连续的。

链表的结构像火车一样，一节一节的，每节车厢都是独立存在的。

单链表结构：

struct SListNode
{
    int data;//节点数据
    struct SListNode*next;//存放下一个数据的地址（节点）
};

节点是从堆上申请空间的，从堆上申请的空间可能连续，可能不连续。

2、单链表的实现

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLTDataType;

typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode*ps);

//尾插
void SLTPushBack(SLTNode**pps, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pps, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pps);
//头删
void SLTPopFront(SLTNode**pps);
//查找
SLTNode* SLTFind(SLTNode* ps, SLTDataType x);
//指定位置之前插入数据
void SLTInsert(SLTNode** pps, SLTNode* pos, SLTDataType x);
//指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pps, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pps);

#include"SList.h"
//打印
void SLTPrint(SLTNode* ps)
{
assert(ps);
SLTNode* pcur = ps;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;//动态内存只能用free释放，函数结束后并不会自动销毁
}
//尾插
void SLTPushBack(SLTNode** pps, SLTDataType x)
{
assert(pps);
SLTNode* newnode = SLTBuyNode(x);
if (*pps == NULL)
{
*pps = newnode;
}
else
{
//找尾
SLTNode* ptail = *pps;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pps, SLTDataType x)
{
assert(pps);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pps;
*pps = newnode;
}
//尾删
void SLTPopBack(SLTNode** pps)
{
assert(pps&&*pps);
if ((*pps)->next == NULL)//->优先级比*高
{
free(*pps);
*pps = NULL;
}
else
{
SLTNode* prev = *pps;
SLTNode* ptail = *pps;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pps)
{
assert(pps && *pps);
if ((*pps)->next == NULL)
{
free(*pps);
*pps = NULL;
}
else
{
SLTNode* pcur = (*pps)->next;
free(*pps);
*pps = NULL;
*pps = pcur;
}
}
//查找
SLTNode* SLTFind(SLTNode* ps, SLTDataType x)
{
assert(ps);
SLTNode* pcur = ps;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//指定位置之前插入数据
void SLTInsert(SLTNode** pps, SLTNode* pos, SLTDataType x)
{
assert(pps&&*pps);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
if (pos == *pps)
{
SLTPushFront(pps, x);
}
else
{
SLTNode* prev = *pps;
while (prev->next != *pps)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
//指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = pos->next;
pos->next = newnode;
newnode->next = prev;
}
//删除pos节点
void SLTErase(SLTNode** pps, SLTNode* pos)
{
assert(pps && *pps);
assert(pos);
if (pos == *pps)
{
SLTPopFront(pps);
}
else
{
SLTNode* prev = *pps;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* prev = pos->next;
pos->next = prev->next;
free(prev);
prev = NULL;
}
//销毁链表
void SLTDestroy(SLTNode** pps)
{
assert(pps&&*pps);
SLTNode* pcur=*pps;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pps = NULL;
}

3、链表的分类

链表的结构有很多，有8种（2*2*2）链表结构：

分别为带头/不带头单向/双向循环/不循环

带头就是链表一开始就有一个节点

双向就是节点可以指向下一个的节点以及上一个的节点（首尾节点除外）

循环就是尾节点的下一个节点指向首节点

链表种类有很多，但我们平常只使用无头单向非循环链表（单链表）和有头双向循环链表

4、单链表经典算法

反转链表：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    ListNode*n1=NULL;
    ListNode*n2=head;
    ListNode*n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}

移除链表元素：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode*newnode=NULL;
    ListNode*tailnode=NULL;
    ListNode*pcur=head;
    while(pcur)
    {
        if(pcur->val!=val)
        {
            if(newnode==NULL)
            {
                newnode=tailnode=pcur;
            }
            else
            {
                tailnode->next=pcur;
                tailnode=tailnode->next;
            }
        }
        pcur=pcur->next;
    }
    if(newnode)
        tailnode->next=NULL;
    return newnode;
}

链表的中间节点：

 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    ListNode*slow=head;
    ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

环形链表的约瑟夫问题：

typedef struct ListNode ListNode;
 ListNode*buyNode(int x)
 {
    ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));
    newnode->val=x;
    newnode->next=NULL;
    return newnode;
 }
 ListNode* createCircle(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;
 }
int ysf(int n, int m ) {
    ListNode*prev=createCircle(n);
    ListNode*pcur=prev->next;
    int count=1;
    while(prev->next!=prev)
    {
        if(count==m)
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        else 
        {
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return prev->val;
}

合并两个有序链表：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    ListNode*newhead=NULL;
    ListNode*newtail=NULL;
    ListNode*p1=list1;
    ListNode*p2=list2;
    while(p1&&p2)
    {
        if(p1->val<=p2->val)
        {
            if(newhead==NULL)
            {
                newhead=newtail=p1;
            }
            else
            {
                newtail->next=p1;
                newtail=newtail->next;
            }
            p1=p1->next;
        }
        else
        {
            if(newhead==NULL)
            {
                newhead=newtail=p2;
            }
            else
            {
                newtail->next=p2;
                newtail=newtail->next;
            }
            p2=p2->next;
        }
    }
    if(p1==NULL)
    {
        while(p2)
        {
            newtail->next=p2;
            newtail=newtail->next;
            p2=p2->next;
        }
    }
    if(p2==NULL)
    {
        while(p1)
        {
            newtail->next=p1;
            newtail=newtail->next;
            p1=p1->next;
        }
    }
    return newhead;
}

5、双链表的实现

之前说双链表就是带头双向循环链表，带头与头结点不一样，这里的头结点为“哨兵位”，哨兵位节点不存储任何有效元素，只是用来放哨的，存在的意义就是防止遍历循环链表时出现死循环。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;

//初始化
void LTInit(LTNode** pps);
//销毁
void LTDestroy(LTNode* ps);
//链表打印
void LTPrint(LTNode* ps);
//尾插
void LTPushBack(LTNode* ps, LTDataType x);
//头插
void LTPushFront(LTNode* ps, LTDataType x);
//尾删
void LTPopBack(LTNode* ps);
//头删
void LTPopFront(LTNode* ps);
//查找
LTNode* LTFind(LTNode* ps, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);

#include"List.h"

//初始化
LTNode* LTBuyNode(LTDataType x)
{
//申请节点
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(0);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
void LTInit(LTNode** pps)
{
//创建一个哨兵位
*pps = LTBuyNode(-1);
}
//销毁
void LTDestroy(LTNode* ps)
{
assert(ps);
LTNode* pcur = ps->next;
while (pcur != ps)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(ps);
ps = NULL;
}
//链表打印
void LTPrint(LTNode* ps)
{
assert(ps);
LTNode* pcur = ps->next;
while (pcur != ps)
{
printf("%d->", pcur->data);
pcur=pcur->next;
}
printf("\n");
}
//尾插，这里传一级是为了不改变哨兵位的地址
void LTPushBack(LTNode* ps, LTDataType x)//传二级也行，但不能修改哨兵位的地址
{
assert(ps);
LTNode* newnode = LTBuyNode(x);
newnode->prev = ps->prev;
newnode->next = ps;
ps->prev->next=newnode;
ps->prev = newnode;
}
//头插
void LTPushFront(LTNode* ps, LTDataType x)
{
assert(ps);
LTNode* newnode = LTBuyNode(x);
newnode->next = ps->next;
newnode->prev = ps;
ps->next->prev = newnode;
ps->next = newnode;
}
//尾删
void LTPopBack(LTNode* ps)
{
assert(ps&&ps->next!=ps);
LTNode* del = ps->prev;
del->prev->next = ps;
ps->prev = del->prev;
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* ps)
{
assert(ps && ps->next != ps);
LTNode* del = ps->next;
ps->next = del->next;
del->next->prev = ps;
free(del);
del = NULL;
}
//查找
LTNode* LTFind(LTNode* ps, LTDataType x)
{
assert(ps);
LTNode* pcur = ps->next;
while (pcur != ps)
{
if (pcur->data = x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}

顺序表和链表的优缺点：

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上一定连续，物理上不一定连续
随机访问	支持O(1)	不支持O(n)
任意位置插入/删除元素	效率低O(n)	只需要修改指针方向
插入	动态顺序表空间不够时，需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入/删除频繁

谢谢大家观看喽！

原文地址：https://blog.csdn.net/2302_81442125/article/details/140559482

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：java多线程等待唤醒机制详细介绍
下一篇：Emacs vs IDE：用Emacs写程序真的更方便吗？

excel如何快速选中某个数字或者某串数字
鼠标光标放在某个数字或者某串数字的末尾，进行双击鼠标左键即可（就会选中当前鼠标光标前相邻的所有数字）：
阅读更多2024-09-17
面试官问：请描述一次你成功解决问题的经历？
面试官为什么要这么问？面试官问你描述一次成功解决问题的经历，主要是为了评估你的几个关键方面：问题解决能力：了解你在面对挑战时的思维方式和应对策略。决策能力：考察你在压力下做出明智决定的能力。沟通技巧：
阅读更多2024-09-17
VLMEvalKit 评测实践:InternVL2 VS Qwen2VL
多模态技术的突破，正在改变我们理解和交互世界的方式。无论是强大的感知能力、复杂的推理分析，还是图文融合的创新应用，InternVL2 与 Qwen2-VL 展现了大模型的无限可能。
阅读更多2024-09-17
mybatis开启日志
步骤很详细，直接上教程……
阅读更多2024-09-17
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
阅读更多2024-09-17
Blender渲染太慢怎么办？blender云渲染已开启
此次，渲染101云渲染农场正式加入了对Blender的全面支持，涵盖Blender的所有版本，不论是较新的Blender 4.0还是早期版本，都可轻松对接渲染101平台服务。不论是小型独立项目还是大型
阅读更多2024-09-17
ubuntu安装mysql 8.0忘记root初始密码，如何重新修改密码
修改my.cnf文件，在文件新增 skip-grant-tables，在启动mysql时不启动grant-tables，授权表。5.注释掉skip-grant-tables后重启mysql。2、修改m
阅读更多2024-09-17
JVM面试真题总结（十一）
总的来说，Java内存模型主要解决了多线程环境下共享数据的一致性、可见性等问题，是Java并发编程的基础。这种模型的好处是，由于启动类加载器是最顶部的加载器，因此它加载的都是最可信任的类库（Java的
阅读更多2024-09-17
Ubuntu 软件仓库镜像使用帮助
选择镜像。
阅读更多2024-09-17
用于稀疏自适应深度细化的掩码空间传播网络 CVPR2024
图像引导的深度补全是一项通过利用稀疏深度测量和RGB图像来估计密集深度图的任务；它通过估算深度来填充未测量的区域。由于许多深度传感器（如LiDAR和飞行时间相机（ToF））只能提供稀疏的深度图，这项任
阅读更多2024-09-17