指点成金-最美分享吧

登录

Day2：单链表的基本操作

佚名 举报

篇首语：本文由小编为大家整理，主要介绍了Day2：单链表的基本操作相关的知识，希望对你有一定的参考价值。

单链表

  • 前言
  • 1、单链表的定义
  • 2、单链表的特点
  • 3、单链表的基本操作
    • 1、头文件
    • 2、初始化
    • 3、打印
    • 4、创建新节点
    • 5、尾插
    • 6、尾删
    • 7、头插
    • 8、头删
    • 9、插入
    • 10、删除
    • 11、查找
    • 12、销毁
    • 13、获取链表节点个数
  • 4、单链表的注意事项
  • 5、扩展
  • 6、源码

目录目录
顺序表单链表（不带附加头结点）

前言

  • 上一节实现了顺序表的基本操作，这一节我们来学习单链表（不带头结点），实现单链表的一些基本操作以及注意事项。

1、单链表的定义

  1. 单链表是链表中最简单的链表表示，也叫线性链表。链表是不连续的，用指针表示结点间的关系，一个节点包含两个域：

    数据域：一般用data表示，存储一个数据元素
    指针域：存放一个指针，指向下一个结点的开始存储地址，起到链接两个结点的作用

  2. 单链表的结构

    head：头指针，指向第一个结点
    datan：尾结点，没有后继，next指向NULL
    head=NULL的话，则说明该链表为空。

每个节点之间的关系：
第一个结点与头指针：a1=head;
第一个与第二个结点：a2=a1->next;
…
最后一个结点：a(n)=a(n-1)->next，a(n)->next=NULL

2、单链表的特点

  1. 长度很方便的进行扩充
  2. 逻辑顺序与物理顺序可不一致
  3. 可连续存储数据，也可以不连续
  4. 每个结点都有指针域，存储空间消耗比较大

3、单链表的基本操作

1、头文件

#include#include#include#include//bool头文件typedef int SLTDataType;//重命名，方便更改数据类型typedef struct SListNode{SLTDataType data; //数据域struct SListNode* next; //指针域}SLTNode;

2、初始化

  1. 初始化，给头指针开辟空间，开辟成功置空。
void SListInit(SLTNode** phead){assert(phead);*phead = (SLTNode*)malloc(sizeof(SLTNode));if (*phead == NULL){perror("SListInit");return;}(*phead) = NULL;}

3、打印

  1. 遍历根据单链表的结构进行遍历即可，记住不要用头指针去遍历，对头指针进行重命名为p在去进行遍历，可读性高
//遍历void SListPrint(SLTNode* phead){SLTNode* p = phead;while (p){printf("%d->", p->data);//打印数据p = p->next;//指向下一个结点，知道该结点为NULL}printf("NULL\n");}

4、创建新节点

  1. malloc开辟内存给node，开辟失败则退出，开辟成功则将node->data置为x，node->next 置空
//创建节点SLTNode* BuySListNode(SLTDataType x){SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("BuySListNode");exit(-1);}node->data = x;node->next = NULL;return node;}

5、尾插

  1. 当为空表时，相当于在链表头部插入结点，需要修改指针：newnode->next = *pphead; *pphead = newnode;
  2. 非空表时，在current的下一个节点后插入新节点newnode，需要修改指针：
    newnode->next = tail->next; tail->next = newnode;
  3. 这里利用了BuySListNode这个函数创建新节点，所以只用写current->next = newnode; 读者可以根据自己实现的方法去改变

void SListPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);if (*pphead == NULL)//如果链表为NULL，则第一个节点地址给头结点{SLTNode* newnode = BuySListNode(x);//创建新节点*pphead = newnode;//将新节点地址给头节点}else{SLTNode* tail = *pphead;//当有节点存在时while (tail->next)//这里判断下一个结点是否为空，不能是判断该结点是否为空，否则会直接找到末尾，末尾为NULL，插入会失败{tail = tail->next;}SLTNode* newnode = BuySListNode(x);//调用函数，创建新节点tail->next = newnode;}}

6、尾删

  1. 当只有一个结点时，用tail保存首元结点，修改指针：tail = *pphead; free(tail); tail=NULL;
  2. 当有多个结点，用prev保存前驱节点，tail为后继结点，遍历链表，找到尾结点，修改指针：prev = tail; tail = tail->next; free(tail); prev->next = NULL;

void SListPopBack(SLTNode** pphead){assert(pphead);//暴力方式assert(*pphead);//检测链表是否为空//温和方式/*if (*pphead == NULL){return;}*/SLTNode* prev = NULL;SLTNode* tail = *pphead;if (tail->next == NULL){free(tail);tail = NULL;}else{while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}}

7、头插

  1. 头插顾名思义在第一个节点之前插入，成为第一个节点，修改指针：newnode->next = head; head = newnode;

void SListPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;//指向第一个节点*pphead = newnode;//newnode地址给pphead成为第一个节点}

8、头删

1.头删，删除第一个节点，让头指针指向第二个结点，修改指针：next = head->next; head = next;

void SListPopFront(SLTNode** pphead){assert(pphead);assert(*pphead);SLTNode* nextnode = (*pphead)->next;*pphead = nextnode;free(*pphead);*pphead = NULL;}

9、插入

  1. 单链表一般在pos位置之后去插入结点
  2. 头部，修改指向：newnode->next = head; head = newnode;
  3. 既不是第一个结点也不是最后一个结点，修改指向：newnode->next = current->next; current->next = newnode;
  4. 最后一个结点，修改指向：newnode->next = current->next; current->next = newnode;

//在pos位置之后插入void SListInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}

10、删除

  1. 在第一个结点处删除，修改指向：del= head; head = head->next;
  2. 在中间或者尾部删除，修改指向：del= current->next; current->next = del->next;
void SListEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode* nextnode = pos->next;pos->next = pos->next->next;free(nextnode);nextnode = NULL;}

11、查找

  1. 一个一个结点查找值等于x的结点，找到返回该结点，反之返回NULL，修改指针：cur = cur->next;
SLTNode* SListFind(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* cur = *pphead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;}

12、销毁

  1. 一个一个结点释放，修改指针：next = cur->next; free(cur); cur = next;
void SListDestory(SLTNode** pphead){assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}

13、获取链表节点个数

  1. 有一个结点，size+1，修改指针：cur = cur->next;
size_t SListSize(SLTNode* phead){size_t size = 0;SLTNode* cur = phead;while (cur){size++;cur = cur->next;}return size;}

4、单链表的注意事项

注意事项：

  1. 尽量不要用头指针进行操作，可以使用类型重命名，防止找不到头指针，丢失链表，找不到头指针是非常麻烦的一件事，每个操作都涉及头结点，比如头插头删，遍历，反转链表等，都需要头指针，这样做的目的是增强可读性
  2. 遍历链表时要检查链表尾部是否为空
  3. 插入和删除结点时，需要找到插入点或删除点之前的结点
  4. 插入结点时，需要注意malloc开辟
  5. 删除结点，需要用free释放开辟的内存，防止内存泄漏（经常忘记）

5、扩展

关于插入和删除的问题：

  1. 为什么不在pos位置之前去插入结点：单链表是单向的，找到一个结点的后继结点相对来说比较容易，反之选择去找一个结点的前继结点是比较麻烦。
  2. 为什么不删除pos位置的结点：跟第一个问题一样，删除pos位置的结点也是需要去找pos位置的前驱结点，让前驱结点指向pos位置的后去结点才能将pos位置的结点删除，也是比较麻烦的。

解决办法：后面的循环双链表可以解决此类问题

6、源码

  • 需要源码的点击下面的链接即可查看：
    gitee: https://gitee.com/deng_yuniubi/data-structure.
    GitHub: https://github.com/yuxuanniu6/Data-Struct.

以上是关于Day2：单链表的基本操作的主要内容，如果未能解决你的问题，请参考以下文章

上一篇Vue 环境变量和模式(设置通用baseUrl)

下一篇FreeRTOS学习笔记 ——二值信号量

相关文章