C/C++ 双链表之逆序的实例详解

2024-02-29 21:30:16

C/C++ 双链表之逆序的实例详解

一、结点结构

双向链表的数据结构定义如下：

 typedef struct node
    {
      ElemType data;
      struct node *prior
      struct node *next;
    }list;

其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、带头结点

本文描述的是双向链表逆序，链表逆序需要维护3个指针，分别指向前一个节点、当前节点和下一个节点，具体代码如下：

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head->next, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;      // 保存当前结点的下一结点
        p2->next = p1;      // 改变当前结点的next域，指向它的前一个结点
        p1->prior = p2;     // 改变前一个结点的prior域，指向它的后一个结点
        p1 = p2;         // 指针移到下一个结点
        p2 = p3;
      }
      head->next = p1;       // 恢复头结点
      p1->prior = head;
      return head;
    }

在链表逆序过程中，非常重要的一点是要防止断链问题，因此，在移动指针逆序某个结点时，需要用一个指针指向该结点的下一结点，防止下一结点丢失。

三、不带头结点

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;
        p2->next = p1;
        p1->prior = p2;
        p1 = p2;
        p2 = p3;
      }
      head = p1;
      return head;
    }

不带头结点的链表逆序与带头结点的区别在于红色部分代码，即初始p1指向的是第一个结点而不是头结点，最后head直接指向p1而不是用其next来指向p1。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

深入解析C++的循环链表与双向链表设计的API实现

循环链表设计与API实现基本概念循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素循环链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos 删除位置pos处的元素新增功能:游标的定义在循环链表中可以定义一个"当前"指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素. 循环链表新操作将游标重置指向链表中的第一个数据元素 CircleListNode* CircleList_Res
C++将二叉树转为双向链表及判断两个链表是否相交

把二叉查找树转变成排序的双向链表例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空
C++ 双链表的基本操作(详解)

1.概念双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>
关于双向链表的增删改查和排序的C++实现

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 由于双向链表可以方便地实现正序和逆序两个方向的插入.查找等功能,在很多算法中经常被使用, 这里用C++构造了一个双向链表,提供了对双向链表的插入.查找.删除节点.排序等功能,其中排序提供了插入排序和冒泡排序两种方式 #include<iostream> using namespace std;
C++ 模版双向链表的实现详解

代码如下所示: 复制代码代码如下: #include <iostream>template <typename T>class double_linked{ struct node { T data; node* prev; node* next; node(T t, node* p, node* n) : data(t), prev(p), next(n) {} }; node* head;
C++ 构造双向链表的实现代码

构造双向链表,不足之处,还望指正! 复制代码代码如下: // DoubleLinkedList.cpp : 定义控制台应用程序的入口点.//构造双向链表,实现从控制台输入,插入,删除,求大小size等操作#include "stdafx.h"#include <iostream>using namespace std;//定义双向链表的节点template<class T>struct NODE{ NODE<T>* pre; T data; NO
如何用C++实现双向循环链表

双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表.各种链表的简单区别如下:单向链表:基本链表:单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代操作到表头前即是尾部:双向链表:比单向链表多出指向前一个节点的指针,但实际上使用双向链表时很少使用不循环的:双向循环链表:相对于单向循环链表,双向循环链表可从头部反向迭代,这在链表长度很大且需要获取.插入或删除靠近链表尾部元素的时候十分高效.单向循环列表只能从表头正向迭代,执行的时间大于从反向
C++ 实现双向链表的实例

双向链表C++ 的实现本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt
c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. (1)定义双向链表的基本结构复制代码代码如下: typedef struct _DOUBLE_LINK_NODE { int data; struct _DOUBLE_LINK_NODE* prev; struct _DOUBLE_LINK_NODE* nex
利用C++实现双链表基本接口示例代码

链表链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,链表比较方便插入和删除操作. 本文主要给大家介绍了关于C++实现双链表基本接口的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍吧. 首先先简单通过图示区分单链表和双链表的结构差异: 单链表

C/C++ 双链表之逆序的实例详解

相关推荐

随机推荐