一、双向循环链表的原理与应用
双向循环链表与双向链表的区别:指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点,并且双向循环链表的尾结点里的next指针成员指向链表的首结点,所以双向循环链表也属于环形结构。
由于带头结点更加方便用户进行数据访问,所以本次创建一条带头结点的双向循环的链表。
(1) 创建一个空链表,由于是使用头结点,所以就需要申请头结点的堆内存并初始化即可!
(2) 创建新结点,为新结点申请堆内存并对新结点的数据域和指针域进行初始化,操作如下:
(3) 根据情况可以从链表中插入新结点,此时可以分为尾部插入、头部插入、指定位置插入:
- 头插
- 尾插
- 中插
(4) 根据情况可以从链表中删除某结点,此时可以分为尾部删除、头部删除、指定结点删除:
- 头删
- 尾删
- 中删
代码
/**
* @file name : DoubleLinkedList.c
* @brief : 实现双向循环链表的相关功能
* @author :[email protected]
* @date :2024/11/07
* @version :1.0
* @note :
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
双向循环链表公式
/**
* 声明双向循环链表的结点
*
* 双向循环链表总结成公式
* struct xxx
* {
* //指针域(直接前驱的指针域)
* //数据域(需要存放什么类型的数据,你就定义对应的变量即可)
* //指针域(直接后继的指针域)
* };
* 双向循环链表的基本操作:
* 初始化单向循环链表 √
* 插入数据 √
* 删除数据 √
* 修改数据
* 查询打印数据√
*/
初始化双向循环链表
构建双向循环链表结点
DoubleLList_t[ *prev | data |*next ]
// 指的是双向链表中的结点有效数据类型,用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
struct DoubleLinkedList *prev; // 直接前驱的指针域
DataType_t data; // 结点的数据域
struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;
创建一个空链表(仅头结点)
/**
* @name DoubleCirLList_Create
* @brief 创建一个空双向循环链表,空链表应该有一个头结点,头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
* @param
* @return
* @retval Head 头结点地址
* @date 2024/11/07
* @version 1.0
* @note
*/
DoubleLList_t *DoubleCirLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化,头结点是不存储数据域,指针域指向自身即可,体现“循环”
Head->prev = Head;
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
创建一个新结点
/**
* @name DoubleCirLList_NewNode
* @brief 创建新的结点,并对新结点进行初始化(直接前驱指针域+ 数据域 + 直接后继指针域) [*prev|data|*next]
* @param data 要创建结点的元素
* @return 程序执行成功与否
* @retval NULL 申请堆内存失败
* @retval New 新结点地址
* @date 2024/11/07
* @version 1.0
* @note 新结点指针域初始化后默认指向自己
*/
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域(2个)进行初始化,指针域指向结点自身,体现“循环”
New->prev = New;
New->data = data;
New->next = New;
return New;
}
插入数据
头插
/**
* @name DoubleCirLList_HeadInsert
* @brief 在双向循环链表的头结点后插入
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
// 备份头指针, 创建操作指针
DoubleLList_t *Current = Head;
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("Failed to create a node, can not insert new node \n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
Head->next->prev->next = New; // 首结点前驱为尾结点地址, 将尾结点链接新首结点
New->prev = Head->next->prev; // 将新结点前驱链接尾结点
New->next = Head->next; // 新首结点链接旧首结点
Head->next->prev = New; // 旧首结点链接新结点
Head->next = New; // 头结点链接新首结点
return true;
}
中插
/**
* @name DoubleCirLList_DestInsert
* @brief 双向循环链表中的指定元素后面插入新结点
* @param Head 头指针
* @param dest 要查找的结点
* @param data 要插入的数据
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data)
{
DoubleLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node , Failed to create a node\n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
// 3.若双向循环链表非空,需要让尾结点的next指针指向新结点,新结点指向首结点
// 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
while (Current->data != dest)
{
Current = Current->next; // 进入下一个结点
if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
{
printf("The target doesn't exist! \n");
return false;
}
} // 找到目标结点, Current此时指向目标
if (Current->next == Head->next) // 目标结点是尾结点
{
New->next = Head->next; // 尾处理: 新结点直接后继链接首结点
Head->next->prev = New; // 头处理: 首结点直接前驱链接新结点
New->prev = Current; // 内部处理: 新结点直接前驱链接旧尾结点
Current->next = New; // 内部处理: 旧结点链接新尾结点
}
else // 目标结点是中间结点 或首结点
{
New->next = Current->next;
New->prev = Current;
Current->next->prev = New;
Current->next = New;
}
return true;
}
尾插
/**
* @name DoubleCirLList_TailInsert
* @brief 将新元素插入到尾结点后面
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node , Failed to create a node\n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
// 3.如果双向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
New->next = Head->next; // 新结点链接首结点
New->prev = Head->next->prev; // 新结点链接尾结点
Head->next->prev->next = New; // 内部处理: 旧尾结点链接新尾结点
Head->next->prev = New; // 首结点链接新尾结点
return true;
}
删除数据
头删
/**
* @name DoubleCirLList_HeadDel
* @brief 删除首节点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head == Head->next)
{
printf("DoubleLList is Empty! \n");
return false;
}
// 3.判断链表非空链表
// ①若只有首结点
if (Head->next == Head->next->next)
{
Head->next->prev = NULL; // 首结点指针域处理, 防止内存泄漏
Head->next->next = NULL;
free(Head->next); // 释放首结点, 防止内存泄漏
Head->next = Head; // 头结点指向自己, 表示循环
return true;
}
// ②若不止首结点
Head->next->prev->next = Head->next->next; // 尾结点直接后继指针域链接新首结点
Current = Head->next; // 操作指针备份首结点地址
Head->next = Current->next; // 头结点链接新首结点
Head->next->prev = Current->prev; // 新首结点直接前驱指针域链接尾结点
Current->prev = NULL;
Current->next = NULL;
free(Current); // 释放首结点, 防止内存泄漏
return true;
}
中删
/**
* @name DoubleCirLList_DestDel
* @brief 中删, 删除双向循环链表某个元素结点
* @param Head 头指针
* @param dest 要删除的目标元素
* @return 程序执行成功与否
* @retval false 删除失败, 未找到目标元素结点
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head == Head->next)
{
printf("DoubleLList is Empty! \n");
return false;
}
// 3.若双向循环链表非空
// 寻找目标结点
while (Current->data != dest)
{
Current = Current->next; // 进入下一个结点, 第一次从头结点跳到尾结点
if ((Current->next == Head->next) && (Current->data != dest)) // 若尾结点不是目标结点
{
printf("The target doesn't exist! \n");
return false;
}
} // 找到目标结点, Current此时指向目标
// 目标结点是首结点
if (Current == Head->next)
{
// ①若链表只有首结点
if (Current->next == Head->next)
{
// 删除首结点, 变成空链表
Head->next = Head;
} // ②若链表不止首节点
Head->next->prev->next = Current->next; // 更新尾结点指针域为新首结点地址
Current->next->prev = Head->next->prev; // 更新新首节点的前驱指针域链接尾结点
Head->next = Current->next; // 更新首结点链接新首结点
}
else if (Current->next == Head->next) // ③目标结点是尾结点
{
Current->prev->next = Head->next; // 新尾结点链接首结点, 行成循环
Head->next->prev = Current->prev;
}
else // ④目标结点是中间结点
{
Current->prev->next = Current->next;
Current->next->prev = Current->prev;
}
// 删除目标结点
Current->prev = NULL;
Current->next = NULL;
free(Current); // 防止内存泄漏
return true;
}
尾删
/**
* @name DoubleCirLList_TailDel
* @brief 删除尾结点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败, 链表为空
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head->next == Head)
{
printf("Error, Double Circular Linked List is empty! \n");
return false;
}
Current = Head->next->prev; // 备份尾结点
// 3.①若双向循环链表非空
// 若链表只有首结点
if (Head->next == Head->next->next)
{
// 删除首结点, 变成空链表
Head->next = Head;
// printf("只有首节点的值 %d \n", Head->next->data);
}
else if (Head->next != Head->next->next) // ②若首结点直接前驱不是自己, 则还有别的结点
{
// printf("不止只有首节点的值 %d \n", Head->next->data);
Head->next->prev = Current->prev; // 首结点直接前驱链接新尾结点
Current->prev->next = Head->next; // 新尾结点的直接后继指针域链接首结点
}
}
查询打印数据
遍历打印
/**
* @name DoubleCirLList_Print
* @brief 从头到尾遍历链表
* @param Head 头指针
* @return 无
* @date 2024/11/07
* @version 1.0
* @note
*/
void DoubleCirLList_Print(DoubleLList_t *Head)
{
// 判断是否为空链表
if (Head->next == Head)
{
printf("The list is empty.\n");
return;
}
DoubleLList_t *Current = Head->next; // 指向首结点
printf("Double Circular Linked List: ");
while (Current->next) // 不断向下检查结点指针域
{
printf(" -> %d", Current->data); // 打印结点数据
if (Current->next == Head->next) // 结束条件: 达尾结点
{
break;
}
Current = Current->next; // 进入下一个结点
}
printf("\n"); // 刷新行缓冲, 输出缓冲区
}
测试
#include "DoubleCirLList.h"
int main(int argc, char const *argv[])
{
// 创建单向循环链表, 空链表
DoubleLList_t *Manager = DoubleCirLList_Create();
// 头插法 向链表中插入新结点
printf("*********************************DoubleCirLList_HeadInsert********************************\n");
DoubleCirLList_HeadInsert(Manager, 7);
DoubleCirLList_HeadInsert(Manager, 4);
DoubleCirLList_HeadInsert(Manager, 1);
DoubleCirLList_HeadInsert(Manager, 8);
DoubleCirLList_HeadInsert(Manager, 5);
DoubleCirLList_HeadInsert(Manager, 2);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 5 -> 8 -> 1 -> 4 -> 7*/
// 中插法 向链表中插入新结点
printf("*********************************DoubleCirLList_DestInsert********************************\n");
DoubleCirLList_DestInsert(Manager, 7, 9);
DoubleCirLList_DestInsert(Manager, 4, 6);
DoubleCirLList_DestInsert(Manager, 2, 3);
DoubleCirLList_DestInsert(Manager, 5, 10);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9*/
// 尾插法 向链表中插入新结点
printf("*********************************DoubleCirLList_TailInsert********************************\n");
DoubleCirLList_TailInsert(Manager, 13);
DoubleCirLList_TailInsert(Manager, 12);
DoubleCirLList_TailInsert(Manager, 11);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/
// 头删法 删除首结点
printf("*********************************DoubleCirLList_HeadDel********************************\n");
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/
// 中删法 删除指定结点
printf("*********************************DoubleCirLList_DestDel********************************\n");
DoubleCirLList_DestDel(Manager, 10);
DoubleCirLList_DestDel(Manager, 1);
DoubleCirLList_DestDel(Manager, 6);
DoubleCirLList_DestDel(Manager, 11);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 8 -> 4 -> 7 -> 9 -> 13 -> 12*/
// 尾删法 删除尾结点
printf("*********************************DoubleCirLList_TailDel********************************\n");
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 8 -> 4*/
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
/*Error, Double Circular Linked List is empty! */
DoubleCirLList_HeadInsert(Manager, 66);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 66*/
// 等待用户响应
printf("***Press any key to exit the test***\n");
getchar();
return 0;
}
测试结果:
*********************************DoubleCirLList_HeadInsert********************************
Double Circular Linked List: -> 2 -> 5 -> 8 -> 1 -> 4 -> 7
*********************************DoubleCirLList_DestInsert********************************
Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9
*********************************DoubleCirLList_TailInsert********************************
Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************DoubleCirLList_HeadDel********************************
Double Circular Linked List: -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************DoubleCirLList_DestDel********************************
Double Circular Linked List: -> 8 -> 4 -> 7 -> 9 -> 13 -> 12
*********************************DoubleCirLList_TailDel********************************
Double Circular Linked List: -> 8 -> 4
Error, Double Circular Linked List is empty!
Double Circular Linked List: -> 66
***Press any key to exit the test***
完整代码
DoubleCirLList.h
#ifndef __DOUBLECIRLLIST_H // ifndef是(如果 没有 定义 那么) (__该头文件的名称)
#define __DOUBLECIRLLIST_H // #define是 进行定义
/**
* @file name : DoubleLinkedList.c
* @brief : 实现双向循环链表的相关功能
* @author :[email protected]
* @date :2024/11/07
* @version :1.0
* @note :
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
/**
* 声明双向循环链表的结点
*
* 双向循环链表总结成公式
* struct xxx
* {
* //指针域(直接前驱的指针域)
* //数据域(需要存放什么类型的数据,你就定义对应的变量即可)
* //指针域(直接后继的指针域)
* };
* 双向循环链表的基本操作:
* 初始化单向循环链表 √
* 插入数据 √
* 删除数据 √
* 修改数据
* 查询打印数据√
*/
// 指的是双向链表中的结点有效数据类型,用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
struct DoubleLinkedList *prev; // 直接前驱的指针域
DataType_t data; // 结点的数据域
struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;
/**
* @name DoubleCirLList_Create
* @brief 创建一个空双向循环链表,空链表应该有一个头结点,头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
* @param
* @return
* @retval Head 头结点地址
* @date 2024/11/07
* @version 1.0
* @note
*/
DoubleLList_t *DoubleCirLList_Create(void);
/**
* @name DoubleCirLList_NewNode
* @brief 创建新的结点,并对新结点进行初始化(直接前驱指针域+ 数据域 + 直接后继指针域) [*prev|data|*next]
* @param data 要创建结点的元素
* @return 程序执行成功与否
* @retval NULL 申请堆内存失败
* @retval New 新结点地址
* @date 2024/11/07
* @version 1.0
* @note 新结点指针域初始化后默认指向自己
*/
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data);
/**
* @name DoubleCirLList_HeadInsert
* @brief 在双向循环链表的头结点后插入
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data);
/**
* @name DoubleCirLList_DestInsert
* @brief 双向循环链表中的指定元素后面插入新结点
* @param Head 头指针
* @param dest 要查找的结点
* @param data 要插入的数据
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data);
/**
* @name DoubleCirLList_TailInsert
* @brief 将新元素插入到尾结点后面
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data);
/**
* @name DoubleCirLList_HeadDel
* @brief 删除首节点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadDel(DoubleLList_t *Head);
/**
* @name DoubleCirLList_DestDel
* @brief 中删, 删除双向循环链表某个元素结点
* @param Head 头指针
* @param dest 要删除的目标元素
* @return 程序执行成功与否
* @retval false 删除失败, 未找到目标元素结点
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest);
/**
* @name DoubleCirLList_TailDel
* @brief 删除尾结点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败, 链表为空
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailDel(DoubleLList_t *Head);
/**
* @name DoubleCirLList_Print
* @brief 从头到尾遍历链表
* @param Head 头指针
* @return 无
* @date 2024/04/26
* @version 1.0
* @note
*/
void DoubleCirLList_Print(DoubleLList_t *Head);
#endif
// 结束定义
DoubleCirLList.c
/**
* @file name : DoubleCirLList.c
* @brief : 实现双向循环链表的相关功能
* @author :[email protected]
* @date :2024/04/26
* @version :1.0
* @note :
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
#include "DoubleCirLList.h"
/**
* @name DoubleCirLList_Create
* @brief 创建一个空双向循环链表,空链表应该有一个头结点,头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
* @param
* @return
* @retval Head 头结点地址
* @date 2024/11/07
* @version 1.0
* @note
*/
DoubleLList_t *DoubleCirLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化,头结点是不存储数据域,指针域指向自身即可,体现“循环”
Head->prev = Head;
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
/**
* @name DoubleCirLList_NewNode
* @brief 创建新的结点,并对新结点进行初始化(直接前驱指针域+ 数据域 + 直接后继指针域) [*prev|data|*next]
* @param data 要创建结点的元素
* @return 程序执行成功与否
* @retval NULL 申请堆内存失败
* @retval New 新结点地址
* @date 2024/11/07
* @version 1.0
* @note 新结点指针域初始化后默认指向自己
*/
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域(2个)进行初始化,指针域指向结点自身,体现“循环”
New->prev = New;
New->data = data;
New->next = New;
return New;
}
/**
* @name DoubleCirLList_HeadInsert
* @brief 在双向循环链表的头结点后插入
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
// 备份头指针, 创建操作指针
DoubleLList_t *Current = Head;
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("Failed to create a node, can not insert new node \n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
Head->next->prev->next = New; // 首结点前驱为尾结点地址, 将尾结点链接新首结点
New->prev = Head->next->prev; // 将新结点前驱链接尾结点
New->next = Head->next; // 新首结点链接旧首结点
Head->next->prev = New; // 旧首结点链接新结点
Head->next = New; // 头结点链接新首结点
return true;
}
/**
* @name DoubleCirLList_DestInsert
* @brief 双向循环链表中的指定元素后面插入新结点
* @param Head 头指针
* @param dest 要查找的结点
* @param data 要插入的数据
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data)
{
DoubleLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node , Failed to create a node\n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
// 3.若双向循环链表非空,需要让尾结点的next指针指向新结点,新结点指向首结点
// 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
while (Current->data != dest)
{
Current = Current->next; // 进入下一个结点
if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
{
printf("The target doesn't exist! \n");
return false;
}
} // 找到目标结点, Current此时指向目标
if (Current->next == Head->next) // 目标结点是尾结点
{
New->next = Head->next; // 尾处理: 新结点直接后继链接首结点
Head->next->prev = New; // 头处理: 首结点直接前驱链接新结点
New->prev = Current; // 内部处理: 新结点直接前驱链接旧尾结点
Current->next = New; // 内部处理: 旧结点链接新尾结点
}
else // 目标结点是中间结点 或首结点
{
New->next = Current->next;
New->prev = Current;
Current->next->prev = New;
Current->next = New;
}
return true;
}
/**
* @name DoubleCirLList_TailInsert
* @brief 将新元素插入到尾结点后面
* @param Head 头指针
* @param data 新元素
* @return 程序执行成功与否
* @retval false 插入失败
* @retval true 插入成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失
// 1.创建新结点并对新结点进行初始化
DoubleLList_t *New = DoubleCirLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node , Failed to create a node\n");
return false;
}
// 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
if (Head->next == Head)
{
Head->next = New; // 让头结点的next指针指向新结点
return true;
}
// 3.如果双向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
New->next = Head->next; // 新结点链接首结点
New->prev = Head->next->prev; // 新结点链接尾结点
Head->next->prev->next = New; // 内部处理: 旧尾结点链接新尾结点
Head->next->prev = New; // 首结点链接新尾结点
return true;
}
/**
* @name DoubleCirLList_HeadDel
* @brief 删除首节点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head == Head->next)
{
printf("DoubleLList is Empty! \n");
return false;
}
// 3.判断链表非空链表
// ①若只有首结点
if (Head->next == Head->next->next)
{
Head->next->prev = NULL; // 首结点指针域处理, 防止内存泄漏
Head->next->next = NULL;
free(Head->next); // 释放首结点, 防止内存泄漏
Head->next = Head; // 头结点指向自己, 表示循环
return true;
}
// ②若不止首结点
Head->next->prev->next = Head->next->next; // 尾结点直接后继指针域链接新首结点
Current = Head->next; // 操作指针备份首结点地址
Head->next = Current->next; // 头结点链接新首结点
Head->next->prev = Current->prev; // 新首结点直接前驱指针域链接尾结点
Current->prev = NULL;
Current->next = NULL;
free(Current); // 释放首结点, 防止内存泄漏
return true;
}
/**
* @name DoubleCirLList_DestDel
* @brief 中删, 删除双向循环链表某个元素结点
* @param Head 头指针
* @param dest 要删除的目标元素
* @return 程序执行成功与否
* @retval false 删除失败, 未找到目标元素结点
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head == Head->next)
{
printf("DoubleLList is Empty! \n");
return false;
}
// 3.若双向循环链表非空
// 寻找目标结点
while (Current->data != dest)
{
Current = Current->next; // 进入下一个结点, 第一次从头结点跳到尾结点
if ((Current->next == Head->next) && (Current->data != dest)) // 若尾结点不是目标结点
{
printf("The target doesn't exist! \n");
return false;
}
} // 找到目标结点, Current此时指向目标
// 目标结点是首结点
if (Current == Head->next)
{
// ①若链表只有首结点
if (Current->next == Head->next)
{
// 删除首结点, 变成空链表
Head->next = Head;
} // ②若链表不止首节点
Head->next->prev->next = Current->next; // 更新尾结点指针域为新首结点地址
Current->next->prev = Head->next->prev; // 更新新首节点的前驱指针域链接尾结点
Head->next = Current->next; // 更新首结点链接新首结点
}
else if (Current->next == Head->next) // ③目标结点是尾结点
{
Current->prev->next = Head->next; // 新尾结点链接首结点, 行成循环
Head->next->prev = Current->prev;
}
else // ④目标结点是中间结点
{
Current->prev->next = Current->next;
Current->next->prev = Current->prev;
}
// 删除目标结点
Current->prev = NULL;
Current->next = NULL;
free(Current); // 防止内存泄漏
return true;
}
/**
* @name DoubleCirLList_TailDel
* @brief 删除尾结点
* @param Head 头指针
* @return 程序执行成功与否
* @retval false 删除失败, 链表为空
* @retval true 删除成功
* @date 2024/11/07
* @version 1.0
* @note
*/
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
// 1.创建操作指针
// 指向头结点, 操作指针
DoubleLList_t *Current = Head;
// 2.判断双向循环链表是否为空链表,如果为空, 则退出
if (Head->next == Head)
{
printf("Error, Double Circular Linked List is empty! \n");
return false;
}
Current = Head->next->prev; // 备份尾结点
// 3.①若双向循环链表非空
// 若链表只有首结点
if (Head->next == Head->next->next)
{
// 删除首结点, 变成空链表
Head->next = Head;
// printf("只有首节点的值 %d \n", Head->next->data);
}
else if (Head->next != Head->next->next) // ②若首结点直接前驱不是自己, 则还有别的结点
{
// printf("不止只有首节点的值 %d \n", Head->next->data);
Head->next->prev = Current->prev; // 首结点直接前驱链接新尾结点
Current->prev->next = Head->next; // 新尾结点的直接后继指针域链接首结点
}
}
/**
* @name DoubleCirLList_Print
* @brief 从头到尾遍历链表
* @param Head 头指针
* @return 无
* @date 2024/11/07
* @version 1.0
* @note
*/
void DoubleCirLList_Print(DoubleLList_t *Head)
{
// 判断是否为空链表
if (Head->next == Head)
{
printf("The list is empty.\n");
return;
}
DoubleLList_t *Current = Head->next; // 指向首结点
printf("Double Circular Linked List: ");
while (Current->next) // 不断向下检查结点指针域
{
printf(" -> %d", Current->data); // 打印结点数据
if (Current->next == Head->next) // 结束条件: 达尾结点
{
break;
}
Current = Current->next; // 进入下一个结点
}
printf("\n"); // 刷新行缓冲, 输出缓冲区
}
projecttesting.c
/**
* @file name : projecttesting.c
* @brief : 实现双向循环链表的相关功能测试
* @author :[email protected]
* @date :2024/11/07
* @version :1.0
* @note :
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
#include "DoubleCirLList.h"
int main(int argc, char const *argv[])
{
// 创建单向循环链表, 空链表
DoubleLList_t *Manager = DoubleCirLList_Create();
// 头插法 向链表中插入新结点
printf("*********************************DoubleCirLList_HeadInsert********************************\n");
DoubleCirLList_HeadInsert(Manager, 7);
DoubleCirLList_HeadInsert(Manager, 4);
DoubleCirLList_HeadInsert(Manager, 1);
DoubleCirLList_HeadInsert(Manager, 8);
DoubleCirLList_HeadInsert(Manager, 5);
DoubleCirLList_HeadInsert(Manager, 2);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 5 -> 8 -> 1 -> 4 -> 7*/
// 中插法 向链表中插入新结点
printf("*********************************DoubleCirLList_DestInsert********************************\n");
DoubleCirLList_DestInsert(Manager, 7, 9);
DoubleCirLList_DestInsert(Manager, 4, 6);
DoubleCirLList_DestInsert(Manager, 2, 3);
DoubleCirLList_DestInsert(Manager, 5, 10);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9*/
// 尾插法 向链表中插入新结点
printf("*********************************DoubleCirLList_TailInsert********************************\n");
DoubleCirLList_TailInsert(Manager, 13);
DoubleCirLList_TailInsert(Manager, 12);
DoubleCirLList_TailInsert(Manager, 11);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/
// 头删法 删除首结点
printf("*********************************DoubleCirLList_HeadDel********************************\n");
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_HeadDel(Manager);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/
// 中删法 删除指定结点
printf("*********************************DoubleCirLList_DestDel********************************\n");
DoubleCirLList_DestDel(Manager, 10);
DoubleCirLList_DestDel(Manager, 1);
DoubleCirLList_DestDel(Manager, 6);
DoubleCirLList_DestDel(Manager, 11);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 8 -> 4 -> 7 -> 9 -> 13 -> 12*/
// 尾删法 删除尾结点
printf("*********************************DoubleCirLList_TailDel********************************\n");
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 8 -> 4*/
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
DoubleCirLList_TailDel(Manager);
/*Error, Double Circular Linked List is empty! */
DoubleCirLList_HeadInsert(Manager, 66);
DoubleCirLList_Print(Manager);
/*Double Circular Linked List: -> 66*/
// 等待用户响应
printf("***Press any key to exit the test***\n");
getchar();
return 0;
}
二、栈的原理与应用
大家学习数据结构的目的是为了更好的处理和存储数据,对于顺序表而言改查比较容易,增删比较麻烦,对于链式表而言,增删比较简单,改查比较麻烦,所以每种数据结构都有不同的特点,用户需要选择合适的数据结构。
思考:数据结构中有一种结构称为栈,而linux内存中的栈空间就是基于此设计的,请问栈应该如何设计?
之前学习linux内存分区的时候,已经知道栈内存自顶向下进行递增,其实栈和顺序表以及链式表都一样,都属于线性结构,存储的数据的逻辑关系也是一对一的。
只不过栈是一种特殊的线性表,特殊在栈的一端是封闭的,数据的插入与删除只能在栈的另一端进行,也就是栈遵循“*后进先出*”的原则。也被成为“LIFO”结构,意思是“last input first output”。
栈(stack),存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈(PUSH)、出栈(POP)的说法。
栈就像是一摞书,拿到新书时我们会把它放在书堆的最上面,取书时也只能从最上面的新书开始取。
闭合的一端被称为栈底(Stack Bottom),允许数据的插入与删除的一端被称为栈顶(Stack Top),不包含任何元素的栈被称为空栈。
- 把数据插入到栈空间的动作被称为入栈或者压栈
- 从栈空间中删除数据的动作被称为出栈或者弹栈
由于栈也是一种线性结构,所以可以以数组或者链表作为基础,在此基础上实现栈的操作。
-
以数组作为基础实现栈空间(顺序栈)
数组在内存中占用一块连续的空间,也就是数组元素的内存地址是连续的。为了实现栈,一般是把数组头作为栈底,数组头部到数组尾部作为栈的增长方向,也就是用户只在数组尾部对数据进行插入和删除。
为了方便管理顺序栈所以需要构造管理顺序栈信息的结构体类型,用于记录重要参数,如下:
(1) 创建一个空的顺序栈,并为记录顺序栈信息的结构体申请堆内存,并进行初始化即可!
(2) 根据栈的特性,把新元素从栈顶入栈,也就是从数组的尾部进行元素插入,操作如下:
(3) 根据栈的特性,把元素从栈顶出栈,也就是把元素从数组的尾部把元素删除,操作如下:
(4) 对顺序栈中的元素进行遍历,只需要从顺序栈的栈底开始向栈顶进行遍历,操作如下:
-
以链表作为基础实现栈空间(链式栈)
如果打算实现链式栈,一般是以链表作为基础,一般是把链表头部作为栈顶,方便数据的插入和删除(头插+头删),链式栈相当于是一个单向不循环的链表。
练习:
设计一个进制转换程序,使用顺序栈设计一个把十进制数转换为十六进制数的接口,实现当通过键盘输入一个非负的十进制数,可以在终端输出对应的十六进制数。
/********************************************************************************************************
*
*
* 该程序实现顺序栈元素的增删改查,目的是提高设计程序的逻辑思维,另外为了提高可移植性,所以顺序栈中元素的
* 数据类型为DataType_t,用户可以根据实际情况修改顺序表中元素的类型。
*
* 另外,为了方便管理顺序栈,所以用户设计SeqStack_t结构体,该结构体中包含三个成员:栈底地址+栈容量+栈顶元素的下标
*
*
*
* Copyright (c) 2023-2024 [email protected] All right Reserved
* ******************************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//指的是顺序栈中的元素的数据类型,用户可以根据需要进行修改
typedef int DataType_t;
//构造记录顺序栈SequenceStack各项参数(栈底地址+栈容量+栈顶元素的下标)的结构体
typedef struct SequenceStack
{
DataType_t * Bottom; //记录栈底地址
unsigned int Size; //记录栈容量
int Top; //记录栈顶元素的下标
}SeqStack_t;
//创建顺序表并对顺序栈进行初始化
SeqStack_t * SeqStack_Create(unsigned int size)
{
//1.利用calloc为顺序栈的管理结构体申请一块堆内存
SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));
if(NULL == Manager)
{
perror("calloc memory for manager is failed");
exit(-1); //程序异常终止
}
//2.利用calloc为所有元素申请堆内存
Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));
if (NULL == Manager->Bottom)
{
perror("calloc memory for Stack is failed");
free(Manager);
exit(-1); //程序异常终止
}
//3.对管理顺序栈的结构体进行初始化(元素容量 + 最后元素下标)
Manager->Size = size; //对顺序栈中的容量进行初始化
Manager->Top = -1; //由于顺序栈为空,则栈顶元素的下标初值为-1
return Manager;
}
//判断顺序栈是否已满
bool SeqStack_IsFull(SeqStack_t *Manager)
{
return (Manager->Top + 1 == Manager->Size) ? true : false;
}
//入栈
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
//1.判断顺序栈是否已满
if ( SeqStack_IsFull(Manager) )
{
printf("SeqStack Full is Full!\n");
return false;
}
//2.如果顺序栈有空闲空间,则把新元素添加到顺序栈的栈顶
Manager->Bottom[++Manager->Top] = Data;
return true;
}
//判断顺序栈是否为空
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
return (-1 == Manager->Top) ? true : false;
}
//出栈
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
DataType_t temp = 0; //用于存储出栈元素的值
//1.判断顺序栈是否为空
if ( SeqStack_IsEmpty(Manager) )
{
printf("SeqStack is Empty!\n");
return;
}
//2.由于删除了一个元素,则需要让顺序栈的栈顶元素下标-1
temp = Manager->Bottom[Manager->Top--];
return temp;
}
//遍历顺序表的元素
void SeqStack_Print(SeqStack_t *Manager)
{
for (int i = 0; i <= Manager->Top; ++i)
{
printf(" Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
}
}
//十进制转换为十六进制
void SeqStack_Dec2Hex(SeqStack_t *Manager,unsigned int Data)
{
int remainder; //用于存储求余之后的余数
//1.循环对非负整数进行求余 Data % 16
do
{
remainder = Data % 16;
//分析余数的范围 0~9 10~15 -->A~F
if (remainder < 10)
{
SeqStack_Push(Manager,remainder+'0');
}
else
{
SeqStack_Push(Manager,remainder+'A'-10);
}
Data /= 16;
}while(Data != 0);
//2.把顺序栈中的元素依次出栈
printf("0x");
while( !SeqStack_IsEmpty(Manager) )
{
printf("%c", SeqStack_Pop(Manager) );
}
printf("\n");
}
// ")hel()()loworl(()d"
bool SeqStack_IsStringVaild(SeqStack_t *Manager,const char *Str)
{
char *Pstr = Str; //备份地址,防止地址丢失
//1.循环遍历字符串,寻找'('
while( *Pstr )
{
//判断当前地址下的字符是否为'(',如果是则入栈
if (*Pstr == '(')
{
SeqStack_Push(Manager,'(');
}
if( *Pstr == ')' )
{
//判断空栈
if(SeqStack_IsEmpty(Manager))
{
return false;
}
SeqStack_Pop(Manager);
}
Pstr++;
}
//2.判断栈是否为空
if(!SeqStack_IsEmpty(Manager))
{
return false;
}
return true;
}
int main(int argc, char const *argv[])
{
return 0;
}
通过键盘输入一个包括 '(' 和 ')' 的字符串string ,判断字符串是否有效。要求设计算法实现检查字符串是否有效,有效的字符串需满足以下条件:
A. 左括号必须用相同类型的右括号闭合。
B. 左括号必须以正确的顺序闭合。
C. 每个右括号都有一个对应的相同类型的左括号。
标签:Current,结点,C语言,DoubleCirLList,Head,next,链表,数据结构 From: https://www.cnblogs.com/wyfm/p/18534046