线性表——链式描述(双向链表)

双链表的迭代器类:

template<class T>
class iterator
{
public:
    //向前迭代
    typedef forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;

    //构造函数
    iterator(chainNode<T> * theNode = NULL)
    {
        node = theNode;
    }
    //解引用操作符
    T& operator*() const
    {
        return node->element;
    }
    T* operator->() const
    {
        return &node->element;
    }

    //迭代器加法操作
    iterator& operator++()//前加
    {
        node = node->next;
        return *this;
    }
    iterator operator++(int)//后加
    {
        iterator old = *this;
        node = node->next;
        return old;
    }

    //相等检验
    bool operator != (const iterator right) const
    {
        return node != right.node;
    }
    bool operator == (const iterator right) const
    {
        return node == right.node;
    }
    protected:
    chainNode<T>* node;

};

iterator begin()
{
    return iterator(firstNode);
}

iterator end()
{
    return irerator(NULL);
}

使用迭代器访问链表元素和get()方法访问元素,时间效率有很大的差别: get()函数:O(listSize²) 迭代器:O(listSize)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

基于Huffman编码的压缩软件的Python实现

2094
来自专栏calmound

Contest - 中南大学第六届大学生程序设计竞赛(Semilive)

题1:1160十进制-十六进制 注意他给的数据范围 2^31,int是 2^31-1 #include<iostream> using namespace st...

2654
来自专栏猿人谷

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

2558
来自专栏小樱的经验随笔

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 ...

2757
来自专栏GIS讲堂

Geotools中实现NC转等值面

前面的文章有实现IDW插值并生成等值面的,本文在前文基础上实现气象NC数据生成等值面。

2234
来自专栏数据结构与算法

P2485 [SDOI2011]计算器

题目描述 你被要求设计一个计算器完成以下三项任务: 1、给定y、z、p,计算y^z mod p 的值; 2、给定y、z、p,计算满足xy ≡z(mod p)的最...

41710
来自专栏mathor

KMP(3)

13310
来自专栏青青天空树

A除以B问题

描述:本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。

2322
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

3457
来自专栏calmound

uva Excuses, Excuses!

题意:给几个单词,在给几个句子,输出包含最多单词的那个句子,大小写不分,末尾空行 分析:这道题能A,还是挺开心的,但不说多难,而是又学会了个函数,又知道了个细节...

3675

扫码关注云+社区