双向链表的初始化、插入、删除、遍历
/*** @file name ： DoubleLnList.c
* @brief :实现一个双向不循环链表的接口，可实现链表的增删改查，另外为了提高可移植性，所以链表中
* 数据元素的类型为DataType_t，用户可以根据实际情况修改链表中元素的类型
* @author :MINDSETT@163.com
* @date :2025/6/30
* @version :1.0
* @note :特别说明：此接口实现的双向链表中首结点的直接前驱指针指向NULL,并不是头结点的地址
* CopyRight (c)2025MINDSETT@163.comAll Right Reserved
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//指定链表中元素的数据类型，用户可根据需要进行修改
typedef int DataType_t;
//构造链表的结点，链表中所有结点的数据类型应该是相同的（数据域+指针域）
typedef struct DoubleLinkedList
{
DataType_t data; //结点的数据域
struct DoubleLinkedList * prev; //直接前驱指针域
struct DoubleLinkedList * next; //直接后继的指针域
}DoubleLnList_t;
/**
* @name :DoubleLnList_Create
* @brief :创建一个空链表，空链表应该有一个头节点，对链表进行初始化
* @param :None
* @retval:返回头结点的地址
* @date :2025/6/30
* @version :1.0
* @note :None
*/
DoubleLnList_t *DoubleLnList_Create(void)
{
//创建一个头结点并对头结点申请内存
DoubleLnList_t* Head=(DoubleLnList_t*)calloc(1,sizeof(DoubleLnList_t));
if (NULL==Head){
perror("calloc memory for Head is failed\n");
exit(-1);
}
//对头结点进行初始化,头结点不存储数据域，指针域指向NULL
Head->prev=NULL;
Head->next=NULL;
//将头结点的地址返回
return Head;
}
/**
* @name :DoubleLnList_NewNode
* @brief :创建一个新结点，并为新结点申请堆内存以及对新结点的数据域和指针域进行初始化
* @param :
* @data:新结点的数据
* @retval:返回新结点的地址
* @date :2025/6/30
* @version :1.0
* @note :None
*/
DoubleLnList_t * DoubleLnList_NewNode(DataType_t data)
{
//创建新结点，并未新结点申请堆内存
DoubleLnList_t * New=(DoubleLnList_t*)calloc(1,sizeof(DoubleLnList_t));
if (NULL==New){
perror("calloc memory for NewNode is failed\n");
return NULL;
}
//对新结点的数据域和指针域进行初始化
New->data=data;
New->prev=NULL;
New->next=NULL;
return New;
}
/**
* @name :DoubleLnList_FirstInsert
* @brief :创建一个新结点,并把新结点插入链表的首部
* @param :
* @Head:插入的链表
* @data:新结点的数据
* @retval:功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_FirstInsert(DoubleLnList_t * Head,DataType_t data)
{
//创建新结点，并对新结点进行初始化
DoubleLnList_t* New=DoubleLnList_NewNode(data);
if (NULL==New){
perror("Create New node is failed\n");
return false;
}
//判断链表是否为空，如果为空，则将新结点直接插入
if (NULL==Head->next){
Head->next=New;
return true;
}
New->next=Head->next;//新结点的next指向原首结点
Head->next->prev=New;//原首结点的prev指向新结点
Head->next=New;//头结点的next指向新结点
return true;
}
/**
* @name :DoubleLnList_tailInsert
* @brief :创建一个新结点,并把新结点插入链表的尾部
* @param :
* @Head:插入的链表
* @data:新结点的数据
* @retval:成功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_tailInsert(DoubleLnList_t * Head,DataType_t data)
{
//创建新结点，并对新结点进行初始化
DoubleLnList_t* New=DoubleLnList_NewNode(data);
if (NULL==New){
perror("Create New node is failed\n");
return false;
}
//判断链表是否为空，如果为空，则将新结点直接插入
if (NULL==Head->next){
Head->next=New;
return true;
}
//备份首结点的地址
DoubleLnList_t * tail=Head->next;
//找到尾结点
while(tail->next){
tail=tail->next;
}
tail->next=New;//尾结点的next指向新结点
New->prev=tail;//新结点的prev指向尾结点
return true;
}
/**
* @name :DoubleLnList_DestInsert
* @brief :创建一个新结点,并把新结点插入链表的指定位置
* @param :
* @Head:插入的链表
* @Dest:指定需要新结点插入位置的直接前驱的数据
* @data:新结点的数据
* @retval:成功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_DestInsert(DoubleLnList_t * Head,DataType_t Dest,DataType_t data)
{
//创建新结点，并对新结点进行初始化
DoubleLnList_t* New=DoubleLnList_NewNode(data);
if (NULL==New){
perror("Create New node is failed\n");
return false;
}
//判断链表是否为空，如果为空，则将新结点直接插入
if (NULL==Head->next){
Head->next=New;
return true;
}
//备份首结点的地址
DoubleLnList_t * curr=Head->next;
//如果链表为非空，遍历链表，目的是找到目标结点
while( NULL!=curr && Dest!=curr->data){
curr=curr->next;
}
//未找到目标结点，错误输出
if ( NULL==curr ){
printf("Dest is not found\n");
free(New);
return false;
}
if(curr->next){
New->next=curr->next;//当前结点并不是尾结点时，新结点的next指向目标节点的next
curr->next->prev=New;//当前结点并不是尾结点时，目标结点的直接后继的prev指向新结点
}
New->prev=curr; //新结点的prev指向目标结点
curr->next=New; //目标结点的next指向新结点
return true;
}
/**
* @name :DoubleLnList_FirstDel
* @brief :删除链表的首结点
* @param :
* @Head:链表的头结点
* @retval:成功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_FirstDel(DoubleLnList_t* Head)
{
//备份首结点
DoubleLnList_t * first=Head->next;
//判断传参错误或链表为空
if (NULL==Head || NULL==Head->next){
perror("Linked list is empty\n");
return false;
}
//1.只有一个首结点
if (Head->next->next==NULL){
Head->next=NULL;
first->next=NULL;//首结点的next指向NULL,从链表中断开(避免野指针)
free(first);
return true;
}
//2.链表有多个结点
Head->next->next->prev=NULL;//原首结点的直接后继的prev指向NULL
Head->next=Head->next->next;//头结点的next指向原首结点的直接后继
//旧的首结点的指针域指向NULL,从链表中断开(避免野指针)
first->next=NULL;
//释放首结点占用的内存
free(first);
return true;
}
/**
* @name :DoubleLnList_tailDel
* @brief :删除链表的尾结点
* @param :
* @Head:链表的头结点
* @retval:成功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_tailDel(DoubleLnList_t* Head)
{
//备份头结点和首结点
DoubleLnList_t * prev=Head;
DoubleLnList_t * tail=Head->next;
//判断传参错误或链表为空
if (NULL==Head || NULL==Head->next){
perror("Linked list is empty\n");
return false;
}
//1.只有一个首结点
if (Head->next->next==NULL){
Head->next=NULL;
tail->next=NULL;//首结点的next指向NULL,从链表中断开(避免野指针)
free(tail);
return true;
}
//2.链表有多个结点
//找到尾结点和它的直接前驱
while(tail->next){
prev=tail;
tail=tail->next;
}
//尾结点的直接前驱的prev指向NULL
prev->next=NULL;
//旧的尾结点的指针域指向NULL,从链表中断开(避免野指针)
tail->prev=NULL;
free(tail);
return true;
}
/**
* @name :DoubleLnList_DestDel
* @brief :删除链表的指定结点
* @param :
* @Head:链表的头结点
* @Dest:需要删除的指定结点
* @retval:功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_DestDel(DoubleLnList_t* Head,DataType_t Dest)
{
//备份头结点和首结点
DoubleLnList_t * prev=Head;
DoubleLnList_t * curr=Head->next;
//判断传参错误或链表为空
if (NULL==Head || NULL==Head->next){
perror("Linked list is empty\n");
return false;
}
//1.只有一个首结点
if (Head->next->next==NULL){
Head->next=NULL;
curr->next=NULL;//首结点的指针域指向NULL,从链表中断开(避免野指针)
free(curr);
return true;
}
//2.链表有多个结点
//遍历链表，目的是找到目标结点和它的直接前驱
while( NULL!=curr && Dest!=curr->data){
prev=curr;
curr=curr->next;
}
//未找到目标结点，错误输出
if( NULL==curr ){
printf("Dest is not found\n");
return false;
}
//找到目标结点
prev->next=curr->next;//目标结点的直接前驱的next指向目标结点的直接后继
if(curr->next){
if(curr==Head->next){
curr->next->prev=NULL;//当前结点是首结点时，目标结点的直接后继的prev指向NULL
}else{
curr->next->prev=prev;//当前结点并不是首结点或尾结点时，目标结点的直接后继的prev指向目标结点的直接前驱
}
}
//目标结点的指针域指向NULL,从链表中断开(避免野指针)
curr->prev=NULL;
curr->next=NULL;
free(curr);
return true;
}
/**
* @name :DoubleLnList_Print
* @brief :遍历输出链表中各个结点的数据
* @param :
* @Head:需要遍历的链表
* @retval:成功返回true，失败返回false
* @date :2025/6/30
* @version :1.0
* @note :None
*/
bool DoubleLnList_Print(DoubleLnList_t* Head)
{
//判断传参错误或链表为空
if (NULL==Head || NULL==Head->next){
perror("CurrentDoubleLinkedList is empty\n");
return false;
}
//对链表的头节点的地址进行备份
DoubleLnList_t *curr=Head;
//循环遍历链表
while( curr->next){
curr=curr->next;
printf("Data=%d ",curr->data);
}
return true;
}
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]