C++ 数据结构中单链表的示例分析

小编给大家分享一下C++ 数据结构中单链表的示例分析，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

一、链表是什么

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

• 由图，链式结构在逻辑上是连续的，但是物理上不一定连续

• 显示中结点一般是从堆上申请出来的

• 从堆上申请的空间，是按照一定的策略划分的，两次申请的空间，可能连续，可能不连续，见顺序表

链表的分类

链表也可以分为很多种

1. 单向或者双向
2. 带头或者不带头
3. 循环或非循环

我们最常用的还是无头单向非循环链表和带头双向循环链表 本篇我们实现无头单向非循环链表增删查改

二、链表的实现

基本结点结构

typedef int SLTDateType;typedef struct SListNode{SLTDateType data;struct SListNode* next;}SListNode;

头文件

//llist.h#pragma once#include #include #include #include typedef int SLTDateType;typedef struct SListNode{        SLTDateType data;        struct SListNode* next;}SListNode;// 动态申请一个节点SListNode* BuySListNode(SLTDateType x);// 单链表打印void SListPrint(SListNode* plist);// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删void SListPopBack(SListNode** pplist);// 单链表头删void SListPopFront(SListNode** pplist);// 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入？void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置？void SListEraseAfter(SListNode* pos);// 单链表的销毁void SListDestory(SListNode* plist);

动态申请一个节点

// 动态申请一个节点SListNode* BuySListNode(SLTDateType x){        SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));        if (newnode == NULL)//申请失败        {                printf("malloc fail\n");                exit(-1);        }        else        {                newnode->data = x;                newnode->next = NULL;        }        return newnode;}

单链表打印

链表单个结点中，data存储数据，next存储下一个结点的地址，可以通过next访问下一个结点

// 单链表打印void SListPrint(SListNode* plist){        SListNode* cur = plist;        while (cur != NULL)        {                printf("%d->", cur->data);                cur = cur->next;//访问下一个结点        }        printf("NULL\n");}

单链表尾插

这里传入了头结点的地址的指针，是因为有可能要改变头结点的情况，传址调用幻术，如果只传入*plist，相当于只改变形参，实参不会有实际改变，通过pplist可以解决这个问题

// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x){        SListNode* newnode = BuySListNode(x);        if (*pplist == NULL)//空链表        {                *pplist = newnode;        }        else        {                SListNode* tail = *pplist;//遍历至最后插入                while (tail->next != NULL)                {                        tail = tail->next;                }                tail->next = newnode;        }}

单链表的尾删

一前一后遍历，找到空后直接free（tail），将prev->next置空即可

// 单链表的尾删void SListPopBack(SListNode** pplist){        assert(pplist);        if (*pplist == NULL)//空链表，无需删除        {                return;        }        else        {                SListNode* prev = NULL;                SListNode* tail = *pplist;                {                        while (tail->next != NULL)                        {                                prev = tail;                                tail = tail->next;                        }                        free(tail);                        tail = NULL;                        prev->next = NULL;                }        }}

单链表的头插

有点绕，要多想想

// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x){        assert(pplist);        SListNode* newnode = BuySListNode(x);        newnode->next = *pplist;        *pplist = newnode;}

单链表头删

比较简单

// 单链表头删void SListPopFront(SListNode** pplist){        assert(pplist);        if (*pplist == NULL)//链表为空        {                return;        }        else        {                SListNode* next = (*pplist)->next;                free(*pplist);                *pplist = next;        }}

// 单链表查找遍历即可SListNode* SListFind(SListNode* plist, SLTDateType x){        SListNode* cur = plist;        while (cur != NULL)        {                if (cur->data = x)                {                        return cur;                }                cur = cur->next;        }        retuen NULL;}

*单链表在pos位置之后插入x

为什么不在pos之前插入，由于我们是单向链表，需要从头遍历查找pos，如果在pos之前插入，找到pos还需找到pos之前的地址，对所传参数不友好，所以我们一般在后插入

//单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x){        assert(pos);        SListNode* newnode = BuySListNode(x);        newnode->next = pos->next;        pos->next = newnode;}

单链表删除pos位置之后的值 为什么不删除pos位置，同上，在逻辑上和传参不友好.

// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos){        assert(pos);        SListNode* next = pos->next;        if (next)        {                pos->next = next->next;                free(next);                next = NULL;        }}

单链表的销毁 链表不像顺序表连续删头就可以，由于链表是一个一个分散的结点，需要逐一删除

// 单链表的销毁void SListDestory(SListNode** pplist){        assert(*pplist);        SListNode* cur = *pplist;        while (cur)        {                SListNode* next = cur->next;                free(cur);                cur = next;        }        *pplist = NULL;}

看完了这篇文章，相信你对"C++ 数据结构中单链表的示例分析"有了一定的了解，如果想了解更多相关知识，欢迎关注行业资讯频道，感谢各位的阅读！