C++ 双链表的基本操作(详解)
更新时间:2020年4月25日 17:33 点击:1755
1.概念
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
结构图如下所示:
2.基本操作实例
DoubleList.cpp
#include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h> #include <stdlib.h> DoubleList::DoubleList() { pDoubleListNode pDouList = NULL; // 创建双链表 CreateDouList(pDouList); PrintDouList(pDouList); // 打印逆序链表 PrintDouReverseList(pDouList); // 节点后插入节点 InsertNodeAfter(pDouList); PrintDouList(pDouList); // 节点前插入节点 InsertNodeBefore(pDouList); PrintDouList(pDouList); // 删除节点 DeleteNode(pDouList); PrintDouList(pDouList); // 删除链表 DeleteDouList(pDouList); PrintDouList(pDouList); system("PAUSE"); } DoubleList::~DoubleList() { } //创建双向链表 void DoubleList::CreateDouList(pDoubleListNode &head) { char x; // 定义成char型是用于输入'q'时可以退出,其实定义成int也能退出 pDoubleListNode p, s; head = (pDoubleListNode)malloc(sizeof(DoubleListNode)); head->next = NULL; head->prior = NULL; // 构造头结点p p = head; printf("\n输入双向链表的元素,每输入一个元素后按回车,输入q表示结束.\n"); fflush(stdin); //清空输入缓冲区 x = getchar(); while (x != 'q') { s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = x - '0'; // 得到的是输入字符的ASCII码,减去30H就变成想要的数字 s->next = NULL; s->prior = p; p->next = s; p = s; fflush(stdin); x = getchar(); } if (x == 'q') { printf("双向链表构造完毕!\n"); } } //打印双向链表 void DoubleList::PrintDouList(pDoubleListNode &head) { pDoubleListNode p; printf("\n打印出双向链表数据为:\n"); if (!IsDouListEmpty(head)) { p = head->next; while (p) { printf("%d\n", p->data); p = p->next; } } } //逆序打印双向链表 void DoubleList::PrintDouReverseList(pDoubleListNode &head) { pDoubleListNode p; printf("\n打印出逆序双向链表数据为:\n"); if (!IsDouListEmpty(head)) { p = head->next; while (p->next) { p = p->next; } while (p->prior) { printf("%d \n", p->data); p = p->prior; } } } //求链表长度 int DoubleList::GetDouListLength(pDoubleListNode &head) { int length = 0; if (head == NULL) { printf("链表不存在,请先初始化!\n"); } else { pDoubleListNode p = head->next; while (p) { length++; p = p->next; } } return length; } //判断链表是否为空 bool DoubleList::IsDouListEmpty(pDoubleListNode &head) { if (head == NULL) { printf("链表不存在,请先初始化!\n"); return true; } else if (head->next == NULL) { printf("链表为空!\n"); return true; } return false; } //把双向链表置空 void DoubleList::ClearDouList(pDoubleListNode &head) { if (head == NULL) { printf("链表不存在,请先初始化!\n"); } else { pDoubleListNode p, q; p = q = head->next; //是p、q指向第一个元素 head->next = NULL; while (p) //逐个释放元素所占内存 { p = p->next; free(q); q = p; } } } // 删除双向链表 void DoubleList::DeleteDouList(pDoubleListNode &head) { printf("\n删除双向链表\n"); ClearDouList(head); free(head); head = NULL; } // 在双向链表中第i个位置后面插入元素 void DoubleList::InsertNodeAfter(pDoubleListNode &head) { int data, pos; pDoubleListNode p, s; p = head; int i = 0; printf("\n在双向链表中第i个位置后面插入元素\n"); printf("请输入要插入的元素和位置:\n"); scanf_s("%d%d", &data, &pos, 100); if (head == NULL) { printf("链表不存在,请先初始化!\n"); } else if (head->next == NULL) { printf("链表为空,插入第一个元素!\n"); s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; s->prior = NULL; s->next = NULL; head->next = s; // 将新结点插入head后 } else if (pos<1 || pos>GetDouListLength(head) + 1) { printf("插入位置错误!\n"); } else { while (i < pos) { p = p->next; i++; } if (i == GetDouListLength(head)) //如果在最后一个元素后面插入data { s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; s->next = NULL; s->prior = p; p->next = s; } else { s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; s->next = p->next; p->next->prior = s; p->next = s; s->prior = p; } } } // 在双向链表中第i个位置前面插入元素 void DoubleList::InsertNodeBefore(pDoubleListNode &head) { int data, pos; pDoubleListNode p, s; p = head; int i = 0; printf("\n在双向链表中第i个位置前面插入元素\n"); printf("请输入要插入的元素和位置:\n"); scanf_s("%d%d", &data, &pos, 100); if (head == NULL) { printf("链表不存在,请先初始化!\n"); } else if (head->next == NULL) { printf("链表为空,插入第一个元素!\n"); s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; s->prior = NULL; s->next = NULL; head->next = s; // 将新结点插入head后 } else if (pos<1 || pos>GetDouListLength(head) + 1) { printf("插入位置错误!\n"); } else { while (i < pos) { p = p->next; i++; } if (i == 1) // 如果在第一个元素前面插入data { s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; head->next = s; // 将新结点插入head后 s->prior = head; // 新结点的前结点指向头结点 s->next = p; // 新结点的后结点指向原head的后结点 p->prior = s ; // 原第一个结点的前结点指向新结点 } else { s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); s->data = data; s->prior = p->prior; s->next = p; p->prior->next = s; p->prior = s; } } } //删除双向链表中的第i个元素 void DoubleList::DeleteNode(pDoubleListNode &head) { int pos; int i = 0; pDoubleListNode p = head; printf("\n在双向链表中删除第i个位置的元素\n"); printf("请输入要删除的位置:"); scanf_s("%d", &pos, 100); if (IsDouListEmpty(head)) { return; } else if (pos<1 || pos>GetDouListLength(head)) { printf("删除的位置不存在!\n"); } else { while (i < pos) { p = p->next; i++; } if (i == GetDouListLength(head)) { p->prior->next = NULL; free(p); } else { p->prior->next = p->next; p->next->prior = p->prior; free(p); } } }
DoubleList.h
#pragma once typedef struct DoubleListNode { int data; //数据 struct DoubleListNode *prior; //前驱 struct DoubleListNode *next; //后继 }DoubleListNode, *pDoubleListNode; class DoubleList { public: DoubleList(); ~DoubleList(); //初始化双向链表 void DoubleList::CreateDouList(pDoubleListNode &head); //打印双向链表 void DoubleList::PrintDouList(pDoubleListNode &head); //逆序打印双向链表 void DoubleList::PrintDouReverseList(pDoubleListNode &head); //求链表长度 int DoubleList::GetDouListLength(pDoubleListNode &head); //判断链表是否为空 bool DoubleList::IsDouListEmpty(pDoubleListNode &head); //把双向链表置空 void DoubleList::ClearDouList(pDoubleListNode &head); //删除双向链表 void DoubleList::DeleteDouList(pDoubleListNode &head); //在双向链表中第i个位置后面插入元素m void DoubleList::InsertNodeAfter(pDoubleListNode &head); // 在双向链表中第i个位置前面插入元素 void DoubleList::InsertNodeBefore(pDoubleListNode &head); //删除双向链表中的第i个元素 void DoubleList::DeleteNode(pDoubleListNode &head); };
3.对链表插入节点的理解
例如在节点i前插入一个新的节点(即上面代码中的InsertNodeBefore函数):
链表结构体为:
typedef struct DoubleListNode { int data; // 数据 struct DoubleListNode *prior; // 前驱 struct DoubleListNode *next; // 后继 }DoubleListNode, *pDoubleListNode;
假设该链表由五个节点构成,分别为A,B,C,D,E
图中假设了A,B,C,D,E的地址分别为:addressA,addressB,addressC,addressD,addressE。
下面将分析链表的前插的例子:
双链表的前插,下面这是在节点"D"前插入一个新的节点"S"的代码和分析
s = (pDoubleListNode)malloc(sizeof(DoubleListNode)); // 申请一段内存空间,指针指向首地址为addressS
s->data = data; // 给节点S的数据赋值data
s->prior = p->prior; // p指向D节点, p->prior表示addressC,将它赋给s->prior,则s->prior里面的值是addressC,从而指向addressC这个地址即节点C,如下图S节点的蓝线
s->next = p; // p是addressD,将它赋给s->next,s->next中的值为addressD,也即s->next指向了D,如下图S节点的红线
p->prior->next = s; // p->prior 是addressC,即节点C,所以p->prior->next相当于没插入S之前的addressD,插入S后,将S的首地址即addressS赋给这个位置,所以此时,由C 到D的红线断裂,这个红线目标变成了S,如下图C节点的红线
p->prior = s; // 同理,p->prior也指向了S,即p->prior中addressC变成了addressS, D指向C的蓝线断裂。变成如下图D节点指向S节点的蓝线.
以上这篇C++ 双链表的基本操作(详解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
上一篇: C++ Qt属性系统详细介绍
下一篇: C语言 栈的表示和实现详细介绍
相关文章
- 以前我们开发大型项目时都会用到svn来同步,因为开发产品的人过多,所以我们会利用软件来管理,今天发有一居然可以利用php来管理svn哦,好了看看吧。 代码如下 ...2016-11-25
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章介绍了在C#中对config文件的操作,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
nodejs文件操作模块FS(File System)常用函数简明总结
件系统操作相关的函数挺多的。首先可以分为两大类。一类是异步+回调的。 一类是同步的。在这里只对异步的进行整理,同步的只需要在函数名称后面加上Sync即可1. 首先是一类最常规的读写函数,函数名称和形式,应该是起源于C...2014-06-07- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C#模拟window操作鼠标的方法,可实现模拟鼠标移动到固定位置后点击右键的功能,涉及鼠标常用事件的操作技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了微信小程序手势操作之单触摸点与多触摸点的相关资料,需要的朋友可以参考下...2017-03-13
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25