如何用C++实现双向循环链表

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


代码如下:

/*
* 节点类型。三个成员分别是:指向前一个节点的指针,元素本身,指向后一个节点的指针。
*/
class Node {
public:
    int element;
    Node *next;
    Node *previous;
    Node(int element, Node *next, Node *previous) {
        this->element = element;
        this->next = next;
        this->previous = previous;
    }
};
linkedlist.h:
#include "node.h“
struct LinkedList {
    LinkedList();
    void addFirst(int);
    void addLast(int);
    void add(int index, int element);
    int getFirst();
    int getLast();
    int get(int);
    int removeFirst();
    int removeLast();
    int remove(int);
    void iterate();
private:
    Node *header;
    int size;
};
linkedlist.cpp:
#include "linkedlist.h"
#include <iostream>
using std::cout;
/*
* 构造方法。
* 生成一个空的节点介于表头和表尾之间,初始前后指针都指向自己。
*/
LinkedList::LinkedList() {
    header = new Node(NULL, NULL, NULL);
    header->next = header;
    header->previous = header;
    size = 0;
}
/*
* 在链表头部添加一个元素。
* 生成一个新的节点,向前指向空节点,向后指向原来空节点的下一个节点,即原来的第一个节点。
* 空节点向后指向此节点,原来的第一个节点向前指向此节点。
*/
void LinkedList::addFirst(int i) {
    header->next = new Node(i, header->next, header);
    header->next->next->previous = header->next;
    ++size;
}
/*
* 在链表最后添加一个元素。
* 生成一个新的节点,向前指向原来空节点的前一个节点,即原来的最后一个节点,向后指向空节点。
* 原来的最后一个节点向后指向此节点,空节点向前指向此节点。
*/
void LinkedList::addLast(int i) {
    header->previous = new Node(i, header, header->previous);
    header->previous->previous->next = header->previous;
    ++size;
}
/*
* 在指定的索引前插入一个元素。0 <= 索引 <= 链表长度。
* 如果索引值小于链表长度的一半,向后(正向)迭代获取索引值位置的节点,反之则向前(反向)。
* 生成一个新的节点,向前指向原来这个位置的节点的前一个节点,向后指向原来这个位置的节点。
* 原来这个位置的节点的前一个节点向后指向此节点,原来这个位置的节点向前指向此节点。
* (在指定的索引删除一个元素实现方法类似)
*/
void LinkedList::add(int index, int i) {
    if(index > size || index < 0) {
        cout << "Exception in add(): Index out of bound." << '\n';
    return;
    }
    Node *entry;
    if(index < size / 2) {
        entry = header->next;
        for(int i = 0; i < index; ++i)
            entry = entry->next;
    }
    else {
        entry = header;
        for(int i = size; i > index; --i)
            entry = entry->previous;
    }
    entry->previous->next = new Node(i, entry, entry->previous);
    entry->previous = entry->previous->next;
    ++size;
}
/*
* 获取链表第一个元素。
* 空节点向后指向的节点即是第一个元素。
*/
int LinkedList::getFirst() {
    if(!size)
        cout << "Exception in getFirst(): List is empty." << '\n';
    return header->next->element;
}
/*
* 获取链表最后一个元素。
* 空节点向前指向的节点即是最后一个元素。
*/
int LinkedList::getLast() {
    if(!size)
        cout << "Exception in getLast(): List is empty." << '\n';
    return header->previous->element;
}
/*
* 删除并返回链表第一个元素。
* 链表第二个节点向前指向空节点,空节点向后指向第二个节点。
*/
int LinkedList::removeFirst() {
    int remove = header->next->element;
    header->next->next->previous = header;
    header->next = header->next->next;
    --size;
    return remove;
}
/*
* 删除并返回链表最后一个元素。
* 链表倒数第二个节点向后指向空节点,空节点向前指向倒数第二个节点。
*/
int LinkedList::removeLast() {
    int remove = header->previous->element;
    header->previous->previous->next = header;
    header->previous = header->previous->previous;
    --size;
    return remove;
}
/*
* 用来输出所有元素的迭代方法。
*/
void LinkedList::iterate() {
    if(!size) {
        cout << "Exception in iterate(): List is empty." << '\n';
        return;
    }
    for(Node *entry = header->next; entry != header; entry = entry->next)
        cout << entry->element << " ";
    cout << '\n';
}

时间: 2013-05-27

用C++实现单向循环链表的解决方法

用C++实现一个单向循环链表,从控制台输入整型数字,存储在单项循环链表中,实现了求链表大小.不足之处,还望指正! 复制代码 代码如下: // TestSound.cpp : 定义控制台应用程序的入口点.//实现单向循环链表#include "stdafx.h"#include <iostream>#include <string>using namespace std;//定义链表一个节点的结构体template <class T>struct NO

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

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

关于双向链表的增删改查和排序的C++实现

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

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++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之

C++ 构造双向链表的实现代码

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

浅析C++中单链表的增、删、改、减

首先是是一个简单的例子,单链表的建立和输出.程序1.1 复制代码 代码如下: #include<iostream>#include<string>using namespace std;struct Student{ string name; string score; Student *next;//定义了指向Candidate类型变量的指针};int main(){ int n;// cout<<"请输入学生的总数:"; cin>>n

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

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

C++中单链表的建立与基本操作

准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data   //数据结点类型 { string key;  //关键字  string name; int age;};struct CLType  //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以

C++数据结构与算法之反转链表的方法详解

本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /

用C++类实现单向链表的增删查和反转操作方法

数据结构这东西,理解起来不算难,但是实现难度就不小了,虽然思路很清晰,但不知道从何下手还有语言的细节问题一直是阻碍初学者的主要障碍(比如我).今天用了一下午时间终于独立完成了链表操作. 找网上的代码,大多用了结构体,还有些并不适合刚学c++或者数据结构的人看,于是我是用类写的,代码比较符合学生的习惯和水平. 先看类定义 class node { public: int data; node *next; }; class linklist { node *h; --//一些函数 } 两个类,no

C++数据结构与算法之判断一个链表是否为回文结构的方法

本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

Python数据结构与算法之列表(链表,linked list)简单实现

Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

Python编程判断一个正整数是否为素数的方法

本文实例讲述了Python编程判断一个正整数是否为素数的方法.分享给大家供大家参考,具体如下: import string import math #判断是否素数的函数 def isPrime(n): if(n<2): return False; elif(n==2): return True; elif(n>2): for d in range(2,int(math.ceil(math.sqrt(n))+1)): if(n%d==0): return False; return True;

Python实现判断一个字符串是否包含子串的方法总结

本文实例总结了Python实现判断一个字符串是否包含子串的方法.分享给大家供大家参考,具体如下: 1.使用成员操作符 in >>> s='nihao,shijie' >>> t='nihao' >>> result = t in s >>> print result True 2.使用string模块的find()/rfind()方法 >>> import string >>> s='nihao,s

Python cookbook(数据结构与算法)将序列分解为单独变量的方法

本文实例讲述了Python cookbook(数据结构与算法)将序列分解为单独变量的方法.分享给大家供大家参考,具体如下: 如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 20:32:19) [MSC v.1500 32 bit (Intel)] on wi

Python cookbook(数据结构与算法)实现查找两个字典相同点的方法

本文实例讲述了Python实现查找两个字典相同点的方法.分享给大家供大家参考,具体如下: 问题:寻找两个字典中间相同的地方(相同的键.相同的值等) 解决方案:通过keys()或者items()方法来执行常见的集合操作(比如求并集.交集和差集) >>> a={'x':1,'y':2,'z':3} >>> b={'ww':10,'x':11,'y':2} >>> a.keys()& b.keys() #键的交集 {'y', 'x'} >>

Python cookbook(数据结构与算法)将名称映射到序列元素中的方法

本文实例讲述了Python将名称映射到序列元素中的方法.分享给大家供大家参考,具体如下: 问题:希望通过名称来访问元素,减少结构中对位置的依赖性 解决方案:使用命名元组collections.namedtuple().它是一个工厂方法,返回的是python中标准元组类型的子类,提供给它一个类型名称以及相应的字段名称,它就返回一个可实例化的类,为你以定义好的字段名称传入值等. 命名元组的主要作用在于将代码同它所控制的元素位置间进行解耦 >>> from collections import

php判断一个数组是否为有序的方法

本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag

java判断一个文件是否为二进制文件的方法

本文实例讲述了java判断一个文件是否为二进制文件的方法.分享给大家供大家参考.具体如下: public static boolean isBinary(File file) { boolean isBinary = false; try { FileInputStream fin = new FileInputStream(file); long len = file.length(); for (int j = 0; j < (int) len; j++) { int t = fin.rea

判断一个无向图是否为连通图的方法

无向图的连通性 判断一个无向图是否为连通图.输入为无向图的邻接矩阵. 输入 输入有若干行 第一行为正整数N(0<N<=3000),代表图中点的个数 接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵. 输出 一行.连通yes, 否则no. 测试输入 3 1 1 1 1 1 1 1 1 1 测试输出 yes 源代码 #include<stdio.h> #define N 3002 int a[N][N]; int main() { int i,j,k,n; scanf(&q