AI 助理
备案控制台
开发者社区 人工智能 文章 正文

＜双向链表（含头结点）＞《数据结构(C语言版)》

2022-11-27 107
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜双向链表（含头结点）＞《数据结构(C语言版)》

 目录

《数据结构(C语言版)》实战项目之双向链表（增删查改）功能实现

                                                                           ——By 作者：新晓·故知

一、完整源码：

                       完整源码如下，欢迎复制测试指正！

     双向链表（增删查改）功能实现测试示例：

              完整源码：

二、双向链表的实现分析：

      双向链表的功能函数：

1.双向链表打印+初始化：

2.双向链表动态开辟新结点：

3.双向链表尾插：

（1）尾插法1

（2）尾插法2——附用ListInsert函数版

4.双向链表尾删：

（1）尾删法1

（2）尾删法2——附用ListErase版

5.双向链表头插：（附用ListInsert函数版）

6.双向链表头删：（附用ListErase函数版）

7.双向链表在指定数据位置（pos）处插入数据：

8.双向链表在指定数据位置（pos)  处删除数据：

9.双向链表的销毁：

三、顺序表和链表的区别总结：

 后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                              ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之双向链表（增删查改）功能实现

                                                                           ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

双向链表（增删查改）功能实现测试示例：image.gif编辑

完整源码：

Test.c:

#include "DList.h"
//双向链表测试
//尾插+尾删测试
void TestDList1()
{
  //使用二级指针需传一级指针的地址
  //LTNode* pList = NULL;
  //ListInit(&pList);
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //1.一个一个创建数据
  //ListPushBack(pList, 1);
  //ListPushBack(pList, 2);
  //ListPushBack(pList, 3);
  //ListPushBack(pList, 4);
  //ListPushBack(pList, 5);
  //ListPushBack(pList, 6);
  //ListPrint(pList);
  //2.使用尾插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushBack(pList,i);
  }
  ListPrint(pList);
  //1.一个一个删除数据
  ListPopBack(pList);
  ListPopBack(pList);
  ListPopBack(pList);
  ListPopBack(pList);
  ListPopBack(pList);
  ListPopBack(pList);
  //ListPopBack(pList);
  ListPrint(pList);
}
//在指定数值(pos)位置处插入测试
void TestDList2()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用尾插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushBack(pList, i);
  }
  ListPrint(pList);
  //查找+在指定数值(pos)位置处插入
  LTNode* pos = ListFind(pList, 3);
  if (pos)
  {
    ListInsert(pos, 30);
  }
  ListPrint(pList);
}
//在指定数值(pos)位置处删除测试
void TestDList3()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用尾插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushBack(pList, i);
  }
  ListPrint(pList);
  //查找+在指定数值(pos)位置处删除
  LTNode* pos = ListFind(pList, 3);
  if (pos)
  {
    ListErase(pos);
  }
  ListPrint(pList);
}
//头删——附用ListErase版测试
void TestDList4()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用尾插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushBack(pList, i);
  }
  ListPrint(pList);
  //头删
  ListPopFront(pList);
  ListPrint(pList);
  ListPopFront(pList);
  ListPrint(pList);
}
//尾删——附用ListErase版测试
void TestDList5()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用尾插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushBack(pList, i);
  }
  ListPrint(pList);
  //尾删
  ListPopBack(pList);
  ListPrint(pList);
  ListPopBack(pList);
  ListPrint(pList);
}
//头插——附用ListInsert版
void TestDList6()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用头插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushFront(pList, i);
  }
  ListPrint(pList);
  //头删
  ListPopFront(pList);
  ListPrint(pList);
  ListPopFront(pList);
  ListPrint(pList);
}
//销毁测试
void TestDList7()
{
  //初始化
  //使用一级指针传变量的地址
  LTNode* pList = ListInit();
  //使用头插+循环创建连续有序数据
  for (int i = 0; i < 6; ++i)
  {
    ListPushFront(pList, i);
  }
  ListPrint(pList);
  //销毁
  ListDestory(pList);
  pList = NULL;
}
int main()
{
  TestDList1();
  TestDList2();
  TestDList3();
  TestDList4();
  TestDList5();
  TestDList6();
  TestDList7();
  return 0;
}
image.gif

DList.c:

#include "DList.h"
//双向链表功能函数
//打印
void ListPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//动态开辟新结点
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//初始化——写法1
//优化此处--减少二级指针的使用
//void ListInit(LTNode** pphead)
//{
//  assert(pphead);
//  *pphead = BuyLTNode(0);
//  (*pphead)->next = *pphead;
//  (*pphead)->prev = *pphead;
//
//}
// 初始化——写法2
//使用一级指针
LTNode* ListInit()
{
  LTNode* phead = BuyLTNode(0);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
////尾插
//void ListPushBack(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  
//  LTNode* tail = phead->prev;
//  LTNode* newnode = BuyLTNode(x);
//
//  tail->next = newnode;
//  newnode->prev = tail;
//
//  newnode->next = phead;
//  phead->prev = newnode;
//}
//尾插——附用Insert版
void ListPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead, x);
}
////尾删
//void ListPopBack(LTNode* phead)
//{
//  assert(phead);
//  //判断链表为空
//  assert(phead->next != phead);
//  LTNode* tail = phead->prev;
//  LTNode* tailPrev = tail->prev;
//
//  free(tail);
//  tail = NULL;
//
//  tailPrev->next = phead;
//  phead->prev = tailPrev;
//}
//尾删——附用ListErase版
void ListPopBack(LTNode* phead)
{
  assert(phead);
  //判断链表为空
  assert(phead->next != phead);
  ListErase(phead->prev);
}
//查找
 LTNode* ListFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在指定数值(pos)位置处插入
////写法1：要求注意顺序
//void ListInsert(LTNode* pos, LTDataType x)
//{
//  assert(pos);
//  LTNode* newnode = BuyLTNode(x);
//  pos->prev->next = newnode;
//  newnode->prev = pos->prev;
//
//  pos->prev = newnode;
//  newnode->next = pos;
//}
//写法2：不要求顺序
void ListInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* posPrev = pos->prev;
  newnode->next = pos;
  pos->prev = newnode;
  posPrev->next = newnode;
  newnode->prev = posPrev;
}
//头插——附用ListInsert版
void ListPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead->next, x);
}
//头删——附用ListErase版
void ListPopFront(LTNode* phead)
{
  assert(phead);
  //判断链表为空
  assert(phead->next != phead);
  ListErase(phead->next);
}
//在指定数值(pos)位置处删除
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  pos = NULL;
  prev->next = next;
  next->prev = prev;
}
//销毁双向链表
//保持接口的一致性，传一级指针
void ListDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    //附用——ListErase版 没必要，即将销毁，何必再去链接Erase函数
    //ListErase(cur);
    //自己free
    free(cur);
    cur = next;
  }
  free(phead);
  //phead = NULL;  效果不大，一级传参的形参不改变实参
}
image.gif

DList.h:

#include "DList.h"
//双向链表头函数
//打印
void ListPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//动态开辟新结点
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
//初始化——写法1
//优化此处--减少二级指针的使用
//void ListInit(LTNode** pphead)
//{
//  assert(pphead);
//  *pphead = BuyLTNode(0);
//  (*pphead)->next = *pphead;
//  (*pphead)->prev = *pphead;
//
//}
// 初始化——写法2
//使用一级指针
LTNode* ListInit()
{
  LTNode* phead = BuyLTNode(0);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
////尾插
//void ListPushBack(LTNode* phead, LTDataType x)
//{
//  assert(phead);
//  
//  LTNode* tail = phead->prev;
//  LTNode* newnode = BuyLTNode(x);
//
//  tail->next = newnode;
//  newnode->prev = tail;
//
//  newnode->next = phead;
//  phead->prev = newnode;
//}
//尾插——附用Insert版
void ListPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead, x);
}
////尾删
//void ListPopBack(LTNode* phead)
//{
//  assert(phead);
//  //判断链表为空
//  assert(phead->next != phead);
//  LTNode* tail = phead->prev;
//  LTNode* tailPrev = tail->prev;
//
//  free(tail);
//  tail = NULL;
//
//  tailPrev->next = phead;
//  phead->prev = tailPrev;
//}
//尾删——附用ListErase版
void ListPopBack(LTNode* phead)
{
  assert(phead);
  //判断链表为空
  assert(phead->next != phead);
  ListErase(phead->prev);
}
//查找
 LTNode* ListFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在指定数值(pos)位置处插入
////写法1：要求注意顺序
//void ListInsert(LTNode* pos, LTDataType x)
//{
//  assert(pos);
//  LTNode* newnode = BuyLTNode(x);
//  pos->prev->next = newnode;
//  newnode->prev = pos->prev;
//
//  pos->prev = newnode;
//  newnode->next = pos;
//}
//写法2：不要求顺序
void ListInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = BuyLTNode(x);
  LTNode* posPrev = pos->prev;
  newnode->next = pos;
  pos->prev = newnode;
  posPrev->next = newnode;
  newnode->prev = posPrev;
}
//头插——附用ListInsert版
void ListPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead->next, x);
}
//头删——附用ListErase版
void ListPopFront(LTNode* phead)
{
  assert(phead);
  //判断链表为空
  assert(phead->next != phead);
  ListErase(phead->next);
}
//在指定数值(pos)位置处删除
void ListErase(LTNode* pos)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* next = pos->next;
  free(pos);
  pos = NULL;
  prev->next = next;
  next->prev = prev;
}
//销毁双向链表
//保持接口的一致性，传一级指针
void ListDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    //附用——ListErase版 没必要，即将销毁，何必再去链接Erase函数
    //ListErase(cur);
    //自己free
    free(cur);
    cur = next;
  }
  free(phead);
  //phead = NULL;  效果不大，一级传参的形参不改变实参
}
image.gif

二、双向链表的实现分析：

双向链表的功能函数：

1.双向链表打印+初始化：

打印：image.gif编辑

初始化：image.gif编辑

2.双向链表动态开辟新结点：image.gif编辑

3.双向链表尾插：

（1）尾插法1image.gif编辑

（2）尾插法2——附用ListInsert函数版image.gif编辑

4.双向链表尾删：

（1）尾删法1image.gif编辑

（2）尾删法2——附用ListErase版image.gif编辑

5.双向链表头插：（附用ListInsert函数版）image.gif编辑

6.双向链表头删：（附用ListErase函数版）image.gif编辑

7.双向链表在指定数据位置（pos）处插入数据：image.gif编辑

8.双向链表在指定数据位置（pos)  处删除数据：image.gif编辑

9.双向链表的销毁：

image.gif编辑

双向链表调试测试：image.gif编辑

删除过多数据测试：image.gif编辑

注意事项：

1.删除哨兵位置的头结点，会形成野指针

2.Find是按照顺序查找，有局限性。若需要查找有重复的数据，则需要自己另写算法！

三、顺序表和链表的区别总结：

image.gif编辑image.gif编辑

image.gif编辑

image.gif编辑

image.gif编辑image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                           ——By 作者：新晓·故知

文章标签：
算法
关键词：
数据结构c语言
C语言数据结构
链表结点
数据结构双向链表
链表c语言
新晓故知
目录
相关文章
aliyun3611036241
|
12天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
aliyun3611036241
49 4
Codelinghu
|
19天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
Codelinghu
52 1
ephemerals__
|
23小时前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
10 3
aliyun1622584902-46568
|
1天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
aliyun1622584902-46568
6 2
那年春天
|
1天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念，通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中，理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
那年春天
5 1
aliyun3611036241
|
12天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
aliyun3611036241
59 1
c的前世今生
|
20天前
|
存储 缓存 C语言
C语言：链表和数组有什么区别
C语言中，链表和数组是两种常用的数据结构。数组是一种线性结构，元素在内存中连续存储，通过下标访问，适合随机访问且大小固定的情况。链表由一系列不连续的节点组成，每个节点存储数据和指向下一个节点的指针，适用于频繁插入和删除操作的场景，链表的大小可以动态变化。
c的前世今生
19 2
GuGuStudy
|
21天前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
18 2
阿客不是客
|
19天前
|
存储
探索数据结构：便捷的双向链表
探索数据结构：便捷的双向链表
阿客不是客
12 0
java冯坚持
|
20天前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
18 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器