数据结构与算法

Lesson03 - 链表C语言实现（没有伪代码）

文章目录

• 数据结构与算法
• 前言
• 1 什么是链表
• • 1.1 基本概念
  • 1.2 链表的类型
• 二、无头单链表的实现（纯C语言）
• • 2.1 创建单个结点
  • 2.2 打印
  • 2.3 尾插
  • 2.4 尾删
  • 2.5 头插
  • 2.6 头删
  • 2.7 按值查找
  • 2.8 在pos位置之后插入 x
  • 2.9 在pos位置之前插入x
  • 2.10 删除pos位置之后的元素
• 3 带头双向循环链表的实现（纯C语言）
• • 3.1 创建单个结点
  • 3.2 初始化链表，并返回一个头结点的指针
  • 3.3 打印链表
  • 3.4 尾插
  • 3.5 头插
  • 3.6 尾删
  • 3.7 头删
  • 3.8 按值查找 - 返回结点的位置
  • 3.9 在pos位置之前插入x
  • 3.10 删除pos位置的元素
• //后记

前言

💘 Lesson03 主要讲解数据结构中的 - 链表，以及链表的C语言实现。

💘 本篇文章没有伪代码，帮助大家在理解顺序表的前提下，自己动手用C语言实现链表

1 什么是链表

1.1 基本概念

🏃 线性表的链式存储又称为链表
🏃 它是指通过一组任意的存储单元来存储线性表的数据结构
🏃 由于是任意结点，还得符合线性表的逻辑结构特点，因此每一个节点除了放自身的数据元素，还必须放一个指向其后继的指针

💘 类似于下图：

🏃 虽然在内存中它们是不连续的，但在逻辑上是相连的

1.2 链表的类型

💘相比较与顺序表，链表的类型就丰富多彩了

🏃 一个结点可以存很多信息，除了指向后继的指针，我们可以添加一个指向前驱的指针，于是可分成单向和双向
🏃 如果我们添加一个哨兵位的头结点，可以将插入和删除等操作变得容易一点，以此可分为带头结点和不带头结点
🏃 如果将尾结点的 next 指针指向头结点，这样就形成了一个循环结构，能够很好地找到头尾，因此可分为循环和非循环

通过排列组合，可以组合出8中不同的链表，它们各有优缺点，本篇文章重点介绍单链表和带头双向循环链表

💘 单链表

typedef int SListDataType;typedef struct SListNode{//存储结点数据SListDataType val;//指向下个结点的指针struct SListNode* next;}ListNode;

💘 带头双向循环链表

typedef int SListDataType;typedef struct SListNode{SListDataType val;struct SListNode* next;struct SListNode* prev;}ListNode;

二、无头单链表的实现（纯C语言）

2.1 创建单个结点

🏃 此接口为了方便增加新数据元素时，需要不断动态申请空间的问题

//创建单个结点ListNode* BuyListNode(SListDataType x){ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));if (tmp == NULL){perror("BuyListNode::malloc");}tmp->next = NULL;tmp->val = x;}

2.2 打印

🏃 遍历整个链表

void ListPrint(ListNode* pl){ListNode* i = pl;//遍历整个链表，直到遇到NULLwhile (i){printf("%d ", pl->val);i = i->next;}printf("\n");}

2.3 尾插

🏃 先找到链表的最后一个结点，然后将新建的结点放在他的后面

//尾插void ListPushBack(ListNode** ppl, SListDataType x){ListNode* tmp = BuyListNode(x);//如果传过来的是NULL指针，说明是第一个结点if ((*ppl) == NULL){(*ppl) = tmp;return;}ListNode* tail= (*ppl);//寻找尾结点while (tail->next){tail= tail->next;}tail->next = tmp;}

2.4 尾删

🏃 找到最后一个结点，将其 free 掉
🏃 但是不能直接 free ，因为我们要将倒数第二个结点的 next 置成 NULL，因此我们需要多加一个结点，用来保存尾结点的前一个结点

void ListPopBack(ListNode** ppl){//如果是NULL指针，不必删除if ((*ppl) == NULL){return;}//如果只有一个结点，直接freeif ((*ppl)->next == NULL){free((*ppl));(*ppl) = NULL;return;}//定义一个prev记录前一个结点ListNode* prev = NULL;ListNode* tail = *ppl;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}

2.5 头插

🏃 创建一个新结点，连在原来链表的前面即可

//从头部插入一个节点void ListPushFront(SListNode** pplist, SListDateType x){//即使传的NULL指针也没关系SListNode* newnode = BuySListNode(x);newnode->next = *pplist;//修改指针，使其指向新的第一个结点(*pplist) = newnode;newnode = NULL;}

2.6 头删

🏃 free 第一个结点，修改指针
🏃 处理一个NULL指针情况即可

//从头部删除一个节点void SListPopFront(SListNode** pplist){if (*pplist == NULL) return;//修改第一个结点的指针SListNode* tmp = *pplist;(*pplist) = tmp->next;free(tmp);tmp = NULL;}

2.7 按值查找

🏃 遍历整个链表，找到返回结点指针，没有找到返回 NULL

//按值查找,返回找到后的地址SListNode* SListFind(SListNode* plist, SListDateType x){while (plist){if (plist->date == x){return plist;}plist = plist->next;}return NULL;}

2.8 在pos位置之后插入 x

🏃 一定要先修改 newnode 的指针，如果先修改 pos 的指针，那么整个链表就会断开

//在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SListDateType x){assert(pos);SListNode* newnode = BuySListNode(x);//先修改newnode的指针newnode->next = pos->next;pos->next = newnode;}

2.9 在pos位置之前插入x

🏃

void SListInsert(SListNode** pplist, SListNode* pos, SListDateType x){assert(pos);SListNode* newnode = BuySListNode(x);//如果是第一个结点，相当于头插if ((*pplist) == pos){newnode->next = *pplist;*pplist = newnode;}else{//先找到pos位置的前一个结点SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}//找到后修改指针newnode->next = pos;prev->next = newnode;}

2.10 删除pos位置之后的元素

🏃 注意讨论 pos 为NULL，和 pos 为唯一结点的情况

void SListEraseAfter(SListNode* pos){if (pos == NULL && pos->next == NULL){return;}else{//记录后一个结点SListNode* tmp = pos->next;//让pos结点指向后一个结点的后一个结点pos->next = pos->next->next;free(tmp);tmp = NULL;}}

3 带头双向循环链表的实现（纯C语言）

3.1 创建单个结点

🏃 此接口为了方便增加新数据元素时，需要不断动态申请空间的问题

//创建一个新结点ListNode* BuyListNode(LTDataType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("BuyListNode::malloc");}newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;}

3.2 初始化链表，并返回一个头结点的指针

🏃 创建一个头结点

ListNode* ListInit(){ListNode* head = BuyListNode(0);//由于是循环链表，当只有头结点时，prev和next都指向自己head->next = head;head->prev = head;return head;}

3.3 打印链表

🏃 遍历整个链表

void ListPrint(ListNode* phead){ListNode* cur = phead->next;//循环链表判断结尾的标志是最后一个结点的next指向headwhile (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}

3.4 尾插

🏃 找到最后一个结点，然后插入新结点

void ListPushBack(ListNode* phead, LTDataType x){assert(phead);ListNode* newnode = BuyListNode(x);//不必遍历整个链表去找尾结点，头结点的prev即使尾结点ListNode* tail = phead->prev;//修改指针，使其还是一个循环链表tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

3.5 头插

🏃 创建一个新结点，连在原来链表的前面即可

//从头部插入一个结点xvoid ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* newnode = BuyListNode(x);//相当于在头结点和第二个结点之间插入新结点newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;}

3.6 尾删

🏃 head 的 prev 即是尾

//从尾部删除一个结点void ListPopBack(ListNode* phead){assert(phead);//如果只有头结点，不必删除if (phead->next == phead) return;//记录尾结点以及尾结点的前驱ListNode* tail = phead->prev;ListNode* p_tail = tail->prev;free(tail);tail = NULL;//修改指针使其还是循环链表phead->prev = p_tail;p_tail->next = phead;}

3.7 头删

🏃 记录第一个结点，以及第二个结点，方便修改指针

void ListPopFront(ListNode* phead){assert(phead);if (phead->next == phead) return;//记录第一个结点，以及第二个结点，方便修改指针ListNode* first = phead->next;ListNode* n_first = first->next;free(first);first = NULL;phead->next = n_first;n_first->prev = phead；}

3.8 按值查找 - 返回结点的位置

🏃 遍历链表，寻找 x

ListNode* ListFind(ListNode* phead, LTDataType x){assert(phead);ListNode* cur = phead->next;//注意尾结点的条件while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

3.9 在pos位置之前插入x

🏃 注意修改指针的顺序

void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

3.10 删除pos位置的元素

🏃 删除结点一定要注意不能让链表断开

void ListErase(ListNode* pos){assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}

💘 综上就是关于链表最核心的知识，对您有帮助的老铁，还望关注、点赞、收藏一键三连哦~~~

//后记

🏃 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。