【数据结构】单链表&带头双向循环链表的实现
一、链表的概念及结构
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;
}
}注：带头双向循环链表的头插头删，尾插尾删直接复用了插入删除代码。
原文地址：https://blog.csdn.net/t5y22/article/details/140666119
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！