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

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

2022-11-27 103
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜双向链表（含头结点）＞《数据结构(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语言数据结构
链表结点
链表数据结构
数据结构双向链表
新晓故知
目录
相关文章
2的n次方_
|
6天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
28 10
【数据结构】链表从实现到应用，保姆级攻略
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
22 6
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
21 6
小徐在进步
|
2天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
16 5
小徐在进步
|
2天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
10 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
14 3
小徐在进步
|
2天前
|
存储 C语言
C语言程序设计核心详解 第九章 结构体与链表概要详解
本文档详细介绍了C语言中的结构体与链表。首先，讲解了结构体的定义、初始化及使用方法，并演示了如何通过不同方式定义结构体变量。接着，介绍了指向结构体的指针及其应用，包括结构体变量和结构体数组的指针操作。随后，概述了链表的概念与定义，解释了链表的基本操作如动态分配、插入和删除。最后，简述了共用体类型及其变量定义与引用方法。通过本文档，读者可以全面了解结构体与链表的基础知识及实际应用技巧。
小徐在进步
14 3
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
13 2
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
12 2
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
10 1

热门文章

最新文章

  • 1
    LeetCode 141：环形链表 Linked List Cycle
  • 2
    带头结点的链表的逆置
  • 3
    [LintCode] 删除链表中倒数第n个节点
  • 4
    [剑指offer] 链表中倒数第k个结点
  • 5
    史上最简单的C语言链表实现，没有之一
  • 6
    [剑指offer] 复杂链表的复制
  • 7
    《C语言及程序设计》实践参考——改造链表
  • 8
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 9
    字节跳动笔试题——复杂链表的复杂——剑指 Offer 35. 复杂链表的复制——python && C++源代码
  • 10
    【刷题】反转链表 2种解法：迭代&递归 对比分析
  • 1
    redis数据结构与应用场景
    35
  • 2
    数据结构考试测试编程题
    25
  • 3
    数据结构第六课 -------迭代排序（快速排序和归并排序）
    24
  • 4
    数据结构第五课 -----线性表之树
    41
  • 5
    数据结构第六课 -----链式二叉树的实现
    21
  • 6
    数据结构第五课 -----二叉树的代码实现
    35
  • 7
    栈与队列练习题
    25
  • 8
    操作数栈的字节码指令执行分析
    36
  • 9
    D1. Range Sorting (Easy Version)(单调栈+思维)
    33
  • 10
    线段树最大连续子段板子😂单调栈
    33

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    对象存储 OSS 如何创建 bucket|学习笔记