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

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。

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

赞 (0)

相关推荐

  • 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++ 双链表的基本操作(详解)

    C++ 双链表的基本操作(详解)

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

  • 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++实现双链表基本接口的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍吧. 首先先简单通过图示区分单链表和双链表的结构差异: 单链表

  • C++将二叉树转为双向链表及判断两个链表是否相交

    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++实现

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

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

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

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

  • c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

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

  • 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;   

随机推荐