【数据布局】单链表&带头双向循环链表的实现

九天猎人  金牌会员 | 2024-7-31 17:44:57 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 955|帖子 955|积分 2865

一、链表的概念及布局

1.链表的概念

概念：链表是一种物理存储布局上非一连、非顺序的存储布局，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
2.链表的布局

一样平常讲的链表包罗数据域和指针域：


二、链表的种类

现实中链表的布局非常多样，由以下三组类型自由组合可得8种链表布局：
1.单向、双向：

2.带头、不带头：

3.循环、非循环：


   固然有这么多类型，但我们最长利用的就是以下两种：
  
在此我们只实现这两种链表
  
三、单链表的实现

1.自定义链表结点struct SListNode

  1. typedef int SLTDateType;
  2. typedef struct SListNode
  3. {
  4.         SLTDateType data;
  5.         struct SListNode* next;
  6. }SListNode;
复制代码
2.链表打印数据SListPrint

  1. //打印
  2. void SListPrint(SListNode* plist)
  3. {
  4.         if (plist == NULL)
  5.                 return;
  7.         while (plist)
  8.         {
  9.                 printf("%d->", plist->data);
  10.                 plist = plist->next;
  11.         }
  12. }
复制代码
3.链表创建结点BuyListNode

  1. //创建节点
  2. SListNode* BuySListNode(SLTDateType x)
  3. {
  4.         SListNode* new_node = (SListNode*)malloc(sizeof(SListNode));
  5.         if (new_node == NULL)
  6.         {
  7.                 perror("malloc fail");
  8.                 return NULL;
  9.         }
  10.         new_node->data = x;
  11.         new_node->next = NULL;
  12.         return new_node;
  13. }
复制代码
4.链表尾部插入数据SListPushBack

  1. //尾插
  2. void SListPushBack(SListNode** pplist, SLTDateType x)
  3. {
  4.         //无节点
  5.         if (*pplist == NULL)
  6.         {
  7.                 (*pplist) = BuySListNode(x);
  8.         }
  10.         //有节点
  11.         SListNode* tail = *pplist;
  12.         while (tail->next)
  13.         {
  14.                 tail = tail->next;
  15.         }
  16.         tail->next = BuySListNode(x);
  17. }
复制代码
5.链表头部插入数据SListPushFront

  1. //头插
  2. void SListPushFront(SListNode** pplist, SLTDateType x)
  3. {
  4.         SListNode* new_node = BuySListNode(x);
  5.         new_node->next = *pplist;
  6.         *pplist = new_node;
  7. }
复制代码
6.链表尾部删除数据SListPopBack

  1. //尾删
  2. void SListPopBack(SListNode** pplist)
  3. {
  4.         //空链表
  5.         if ((*pplist) == NULL)
  6.                 return;
  8.         //一个节点
  9.         if ((*pplist)->next == NULL)
  10.         {
  11.                 SListNode* tmp = *pplist;
  12.                 free(tmp);
  13.                 tmp = NULL;
  14.         }
  16.         //多个节点
  18.         else
  19.         {
  20.                 SListNode* cur = *pplist;
  21.                 SListNode* next = cur->next;
  23.                 //找尾
  24.                 while (cur->next->next)
  25.                 {
  26.                         cur = next;
  27.                         next = next->next;
  28.                 }
  29.                 free(next);
  30.                 cur->next = NULL;
  31.         }
  33. }
复制代码
7.链表头部删除数据SListPopFront

  1. //头删
  2. void SLPopFront(SListNode** pplist)
  3. {
  4.         //没有节点
  5.         if ((*pplist) == NULL)
  6.                 return;
  8.         //一个节点
  9.         //多个节点
  10.         SListNode* tmp = *pplist;
  11.         *pplist = (*pplist)->next;
  12.         free(tmp);
  13.         tmp = NULL;
  14. }
复制代码
8.链表查找数据

  1. //查找
  2. SListNode* SListFind(SListNode* plist, SLTDateType x)
  3. {
  4.         SListNode* cur = plist;
  5.         while (cur)
  6.         {
  7.                 if (cur->data == x)
  8.                 {
  9.                         return cur;
  10.                 }
  11.                 cur = cur->next;
  12.         }
  13.         return NULL;
  14. }
复制代码
9.链表在pos位置之后插入数据

  1. // 单链表在pos位置之后插入x
  2. void SListInsertAfter(SListNode* pos, SLTDateType x)
  3. {
  4.         SListNode* newnode = BuySListNode(x);
  5.         //在非尾节点插入
  6.         if (pos->next != NULL)
  7.         {
  8.                 newnode->next = pos->next;
  9.                 pos->next = newnode;
  10.         }
  11.         else
  12.         {
  13.                 SListPushBack(&pos, x);
  14.         }
  15. }
复制代码
10.删除pos位置之后的值

  1. // 单链表删除pos位置之后的值
  2. void SListEraseAfter(SListNode* pos)
  3. {
  4.         if (pos->next == NULL)
  5.         {
  6.                 printf("erroe");
  7.                 return;
  8.         }
  9.         SListNode* del = pos->next;
  10.         pos->next = del->next;
  11.         free(del);
  12.         del = NULL;
  13. }
复制代码
11.烧毁链表

  1. //销毁链表
  2. void SLTDestroy(SListNode** pphead)
  3. {
  4.         if (*pphead == NULL)
  5.                 return;
  6.         SListNode* next = (*(pphead))->next;
  7.         while (*pphead)
  8.         {
  9.                 //销毁
  10.                 SListNode* del = *pphead;
  11.                 free(del);
  12.                 del = NULL;
  14.                 //迭代
  15.                 *pphead = next;
  16.                 if(next)
  17.                 next = next->next;
  18.         }
  19. }
复制代码


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

1.自定义链表结点 ListNode

  1. typedef int LTDataType;
  2. typedef struct ListNode
  3. {
  4.         LTDataType _data;
  5.         struct ListNode* _next;
  6.         struct ListNode* _prev;
  7. }ListNode;
复制代码
2.创建新节点

  2. //创建新节点
  3. ListNode* BuyLTNode(LTDataType x)
  4. {
  5.         ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  6.         if (newnode == NULL)
  7.         {
  8.                 perror("malloc fail");
  9.                 return NULL;
  10.         }
  11.         newnode->_data = x;
  12.         newnode->_next = NULL;
  13.         newnode->_prev = NULL;
  15.         return newnode;
  16. }
复制代码
3.创建一个新链表，返转头结点

  1. // 创建返回链表的头结点.
  2. ListNode* ListCreate()
  3. {
  4.         ListNode* Phead = BuyLTNode(-1);
  5.         Phead->_next = Phead;
  6.         Phead->_prev = Phead;
  8.         return Phead;
  9. }
复制代码
4.打印链表

  1. //打印链表
  2. void ListPrint(ListNode* pHead)
  3. {
  4.         if (pHead == NULL)
  5.                 return;
  6.         ListNode* cur = pHead->_next;
  7.         printf("pHead <=> ");
  8.         while (cur!=pHead)
  9.         {
  10.                 printf("%d <=> ", cur->_data);
  11.                 cur = cur->_next;
  12.         }
  13. }
复制代码
5.在pos之前插入值为x节点

  1. //在pos前插入
  2. void ListInsert(ListNode* pos, LTDataType x)
  3. {
  4.         ListNode* pre = pos->_prev;
  5.         ListNode* newnode = BuyLTNode(x);
  6.         newnode->_next = pos;
  7.         pos->_prev = newnode;
  8.         pre->_next = newnode;
  9.         newnode->_prev = pre;
  10. }
复制代码
6.尾插

  1. //尾插
  2. void ListPushBack(ListNode* pHead, LTDataType x)
  3. {
  4.         ListInsert(pHead,  x);
  5. }
复制代码
7.头插

  1. //头插
  2. void ListPushFront(ListNode* pHead, LTDataType x)
  3. {
  4.         ListInsert(pHead->_next, x);
  5. }
复制代码
8.删除pos位置节点

  1. //删除pos位置的节点
  2. void ListErase(ListNode* pos)
  3. {
  4.         ListNode* pre = pos->_prev;
  5.         ListNode* next = pos->_next;
  6.         free(pos);
  7.         pos = NULL;
  8.         pre->_next = next;
  9.         next->_prev = pre;
  10. }
复制代码
9.双向链表头删

  1. // 双向链表头删
  2. void ListPopFront(ListNode* pHead)
  3. {
  4.         ListErase(pHead->_next);
  5. }
复制代码
10.双向链表尾删

  1. // 双向链表尾删
  2. void ListPopBack(ListNode* pHead)
  3. {
  4.         ListErase(pHead->_prev);
  5. }
复制代码
11.查找

  1. // 双向链表查找
  2. ListNode* ListFind(ListNode* pHead, LTDataType x)
  3. {
  4.         ListNode* cur = pHead->_next;
  5.         while (cur != pHead)
  6.         {
  7.                 if (cur->_data == x)
  8.                         return cur;
  10.                 cur = cur->_next;
  11.         }
  12.         return NULL;
  13. }
复制代码
12.烧毁链表

  1. //销毁链表
  2. void ListDestory(ListNode* pHead)
  3. {
  4.         ListNode* cur = pHead->_next;
  5.         while (cur)
  6.         {
  7.                 ListNode* next = cur->_next;
  8.                 free(cur);
  9.                 pHead->_next = next;
  10.                 cur = next;
  12.         }
  13. }
复制代码
  注：带头双向循环链表的头插头删，尾插尾删直接复用了插入删除代码。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

九天猎人

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表