欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 教育 > 培训 > 【数据结构】单链表带头双向循环链表的实现

【数据结构】单链表带头双向循环链表的实现

2025/5/4 5:57:44 来源:https://blog.csdn.net/t5y22/article/details/140666119  浏览:    关键词:【数据结构】单链表带头双向循环链表的实现

一、链表的概念及结构

1.链表的概念

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

2.链表的结构

一般讲的链表包括数据域和指针域:

二、链表的种类

实际中链表的结构非常多样,由以下三组类型自由组合可得8种链表结构:

1.单向、双向:

2.带头、不带头:

3.循环、非循环:

虽然有这么多类型,但我们最长使用的就是以下两种:

在此我们只实现这两种链表

三、单链表的实现

1.自定义链表结点struct SListNode
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
2.链表打印数据SListPrint
//打印
void SListPrint(SListNode* plist)
{if (plist == NULL)return;while (plist){printf("%d->", plist->data);plist = plist->next;}
}
3.链表创建结点BuyListNode
//创建节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* new_node = (SListNode*)malloc(sizeof(SListNode));if (new_node == NULL){perror("malloc fail");return NULL;}new_node->data = x;new_node->next = NULL;return new_node;
}
4.链表尾部插入数据SListPushBack
//尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{//无节点if (*pplist == NULL){(*pplist) = BuySListNode(x);}//有节点SListNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = BuySListNode(x);
}
5.链表头部插入数据SListPushFront
//头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* new_node = BuySListNode(x);new_node->next = *pplist;*pplist = new_node;
}
6.链表尾部删除数据SListPopBack
//尾删
void SListPopBack(SListNode** pplist)
{//空链表if ((*pplist) == NULL)return;//一个节点if ((*pplist)->next == NULL){SListNode* tmp = *pplist;free(tmp);tmp = NULL;}//多个节点else{SListNode* cur = *pplist;SListNode* next = cur->next;//找尾while (cur->next->next){cur = next;next = next->next;}free(next);cur->next = NULL;}}
7.链表头部删除数据SListPopFront
//头删
void SLPopFront(SListNode** pplist)
{//没有节点if ((*pplist) == NULL)return;//一个节点//多个节点SListNode* tmp = *pplist;*pplist = (*pplist)->next;free(tmp);tmp = NULL;
}
8.链表查找数据
//查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
9.链表在pos位置之后插入数据
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{SListNode* newnode = BuySListNode(x);//在非尾节点插入if (pos->next != NULL){newnode->next = pos->next;pos->next = newnode;}else{SListPushBack(&pos, x);}
}

10.删除pos位置之后的值

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

11.销毁链表

//销毁链表
void SLTDestroy(SListNode** pphead)
{if (*pphead == NULL)return;SListNode* next = (*(pphead))->next;while (*pphead){//销毁SListNode* del = *pphead;free(del);del = NULL;//迭代*pphead = next;if(next)next = next->next;}
}

四.带头双向循环链表的实现

1.自定义链表结点 ListNode

typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;

2.创建新节点


//创建新节点
ListNode* BuyLTNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->_data = x;newnode->_next = NULL;newnode->_prev = NULL;return newnode;
}

3.创建一个新链表,返回头结点

// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* Phead = BuyLTNode(-1);Phead->_next = Phead;Phead->_prev = Phead;return Phead;
}

4.打印链表

//打印链表
void ListPrint(ListNode* pHead)
{if (pHead == NULL)return;ListNode* cur = pHead->_next;printf("pHead <=> ");while (cur!=pHead){printf("%d <=> ", cur->_data);cur = cur->_next;}
}

5.在pos之前插入值为x节点

//在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{ListNode* pre = pos->_prev;ListNode* newnode = BuyLTNode(x);newnode->_next = pos;pos->_prev = newnode;pre->_next = newnode;newnode->_prev = pre;
}

6.尾插

//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListInsert(pHead,  x);
}

7.头插

//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListInsert(pHead->_next, x);
}

8.删除pos位置节点

//删除pos位置的节点
void ListErase(ListNode* pos)
{ListNode* pre = pos->_prev;ListNode* next = pos->_next;free(pos);pos = NULL;pre->_next = next;next->_prev = pre;
}

9.双向链表头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{ListErase(pHead->_next);
}

10.双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{ListErase(pHead->_prev);
}

11.查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_data == x)return cur;cur = cur->_next;}return NULL;
}

12.销毁链表

//销毁链表
void ListDestory(ListNode* pHead)
{ListNode* cur = pHead->_next;while (cur){ListNode* next = cur->_next;free(cur);pHead->_next = next;cur = next;}
}

注:带头双向循环链表的头插头删,尾插尾删直接复用了插入删除代码。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词