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

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

2022-11-27 119
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜双向链表（含头结点）＞《数据结构(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语言
链表结点
数据结构双向链表
新晓故知
目录
相关文章
土木林森
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
65 1
XIAZHI
|
2月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
65 4
XIAZHI
|
2月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
53 4
XIAZHI
|
2月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
55 4
XIAZHI
|
2月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
57 4
XIAZHI
|
2月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
50 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
39 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例，包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法，涵盖了链表操作的多种场景，旨在帮助读者深入理解链表数据结构的应用，提升算法设计与编程能力。
XIAZHI
49 4
RossyYan
|
7天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
24 5
三三是该溜子
|
21天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
31 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充

热门文章

最新文章

  • 1
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 2
    局域网屏幕监控系统中的Python数据结构与算法实现
  • 3
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 4
    Pandas数据结构：Series与DataFrame
  • 5
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 6
    【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
  • 7
    【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
  • 8
    【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
  • 9
    【C++数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】
  • 10
    【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
  • 1
    【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
    24
  • 2
    数据结构中二叉树，哈希表，顺序表，链表的比较补充
    31
  • 3
    【C语言】深入浅出：C语言链表的全面解析
    619
  • 4
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
    82
  • 5
    数据结构实验之链表
    69
  • 6
    数据结构之购物车系统(链表和栈)
    58
  • 7
    顺序表和链表（2）
    70
  • 8
    【数据结构】双向带头循环链表（c语言）（附源码）
    90
  • 9
    【数据结构】手把手教你单链表（c语言）（附源码）
    134
  • 10
    顺序表和链表（1）
    40

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅