当前位置： 首页 > news >正文

数据结构基础(10) --单链表迭代器的设计与实现

news 来源：原创 2024/5/3 20:52:17

为了向 STL 致敬(O(∩_∩)O~), 我们模仿STL中的list的迭代器, 我们也自己实现一个MyList的迭代器, 以供遍历整个链表的所有元素:

首先:Node节点需要做如下修改(注意后缀有+的代码)

//链表节点
template <typename Type>
class Node
{
    friend class MyList<Type>;
    friend class ListIterator<Type>;	//+

    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);
private:
    Node(const Type &dataValue):data(dataValue), next(NULL) {}

    Type data;  //数据域:节点数据
    Node *next; //指针域:下一个节点
};

然后:MyList类同样也需要做修改,但是由于MyList类过长, 修改之处也较少, 因此在此就不贴出, 完整代码会附到博客最后

 

ListIterator的设计

template <typename Type>
class ListIterator
{
public:
    ListIterator(const MyList<Type> &_list):
        list(_list),
        currentNode((_list.first)->next) {}

    //重载 *operator
    const Type &operator*() const throw (std::out_of_range);
    Type &operator*() throw (std::out_of_range);

    //重载 ->operator
    const Node<Type> *operator->() const throw (std::out_of_range);
    Node<Type> *operator->() throw (std::out_of_range);

    //重载 ++operator
    ListIterator &operator++() throw (std::out_of_range);
    //注意:此处返回的是值,而不是reference
    ListIterator operator++(int) throw (std::out_of_range);

    bool isEmpty() const;

private:
    const MyList<Type> &list;
    Node<Type> *currentNode;
};

ListIterator类的实现 

template <typename Type>
const Type &ListIterator<Type>::operator*() const
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    // 返回当前指针指向的内容
    return currentNode->data;
}

template <typename Type>
Type &ListIterator<Type>::operator*()
throw (std::out_of_range)
{
    //首先为*this添加const属性,
    //以调用该函数的const版本,
    //然后再使用const_case,
    //将该函数调用所带有的const属性转除
    //operator->()的non-const版本与此类同
    return
        const_cast<Type &>(
            static_cast<const ListIterator<Type> &>(*this).operator*()
        );
}

template <typename Type>
const Node<Type> *ListIterator<Type>::operator->() const
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    //直接返回指针
    return currentNode;
}

template <typename Type>
Node<Type> *ListIterator<Type>::operator->()
throw (std::out_of_range)
{
    // 见上
    return
        const_cast<Node<Type> *> (
            static_cast<const ListIterator<Type> >(*this).operator->()
        );
}

template <typename Type>
ListIterator<Type> &ListIterator<Type>::operator++()
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    //指针后移
    currentNode = currentNode->next;
    return *this;
}
template <typename Type>
ListIterator<Type> ListIterator<Type>::operator++(int)
throw (std::out_of_range)
{
    ListIterator tmp(*this);
    ++ (*this); //调用前向++版本

    return tmp;
}

//判空
template <typename Type>
bool ListIterator<Type>::isEmpty() const
{
    if (currentNode == NULL)
        return true;
    return false;
}

附-ListIterator测试代码:

int main()
{
    std::list<int> iStdList;
    MyList<int>    iMyList;
    for (int i = 0; i < 10; ++i)
    {
        iStdList.push_back(i+1);
        iMyList.insert(i+1, i+1);
    }

    for (std::list<int>::iterator iter = iStdList.begin();
            iter != iStdList.end();
            ++ iter)
    {
        cout << *iter << ' ';
    }
    cout << endl;

    for (ListIterator<int> iter(iMyList);
            !iter.isEmpty();
            ++ iter)
    {
        cout << *iter << ' ';
    }
    cout << endl;

    cout << "Test: \n\t" << iMyList << endl;


    ListIterator<int> iter(iMyList);
cout << "first = " << *iter << endl;
}


附-MyList完整源代码 

//MyList.h
#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED

#include <iostream>
#include <stdexcept>
using namespace std;

//前向声明
template <typename Type>
class MyList;
template <typename Type>
class ListIterator;

//链表节点
template <typename Type>
class Node
{
    //可以将MyList类作为Node的友元
    //同时也可以将Node类做成MyList的嵌套类, 嵌套在MyList中, 也可以完成该功能
    friend class MyList<Type>;
    friend class ListIterator<Type>;

    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);
private:
    //constructor说明:
    //next = NULL;    //因为这是一个新生成的节点, 因此下一个节点为空
    Node(const Type &dataValue):data(dataValue), next(NULL) {}

    Type data;  //数据域:节点数据
    Node *next; //指针域:下一个节点
};

//链表
template <typename Type>
class MyList
{
    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);

    friend class ListIterator<Type>;
public:
    MyList();
    ~MyList();

    //将元素插入表头
    void insertFront(const Type &data);
    //将元素插入到位置index上(index从1开始)
    void insert(const Type &data, int index);
    //删除表中所有值为data的节点
    void remove(const Type &data);
    bool isEmpty() const;

    //链表反转
    void invort();
    //将链表(list)链接到本条链表的末尾
    void concatenate(const MyList<Type> &list);

private:
    //指向第一个节点的指针
    Node<Type> *first;
};

template <typename Type>
MyList<Type>::MyList()
{
    //first指向一个空节点
    first = new Node<Type>(0);
    first -> next = NULL;
}
template <typename Type>
MyList<Type>::~MyList()
{
    Node<Type> *deleteNode = NULL;
    while (first != NULL)
    {
        deleteNode = first;
        first = first -> next;
        delete deleteNode;
    }
}

template <typename Type>
void MyList<Type>::insertFront(const Type &data)
{
    Node<Type> *newNode = new Node<Type>(data);
    newNode -> next = first -> next;
    first -> next = newNode;
}

template <typename Type>
void MyList<Type>::insert(const Type &data, int index)
{
    //由于我们在表头添加了一个空节点
    //因此如果链表为空, 或者在链表为1的位置添加元素
    //其操作与在其他位置添加元素相同

    int count = 1;
    //此时searchNode肯定不为NULL
    Node<Type> *searchNode = first;
    // 找到要插入的位置
    // 如果所给index过大(超过了链表的长度)
    // 则将该元素插入到链表表尾
    // 原因是 searchNode->next != NULL 这个条件已经不满足了
    // 已经到达表尾
    while (count < index && searchNode->next != NULL)
    {
        ++ count;
        searchNode = searchNode->next;
    }

    // 插入链表
    Node<Type> *newNode = new Node<Type>(data);
    newNode->next = searchNode->next;
    searchNode->next = newNode;
}

template <typename Type>
void MyList<Type>::remove(const Type &data)
{
    if (isEmpty())
        return ;

    Node<Type> *previous = first;   //保存要删除节点的前一个节点
    for (Node<Type> *searchNode = first->next;
            searchNode != NULL;
            searchNode = searchNode->next)
    {
        if (searchNode->data == data)
        {
            previous->next = searchNode->next;
            delete searchNode;
            //重新调整searchNode指针
            //继续遍历链表查看是否还有相等元素

            //如果当前searchNode已经到达了最后一个节点
            //也就是searchNode->next已经等于NULL了, 则下面这条语句不能执行
            if (previous->next == NULL)
                break;

            searchNode = previous->next;
        }
        previous = searchNode;
    }
}
template <typename Type>
bool MyList<Type>::isEmpty() const
{
    return first->next == NULL;
}

template <typename Type>
void MyList<Type>::concatenate(const MyList<Type> &list)
{
    if (isEmpty())//如果自己的链表为空
    {
        first = list.first;
        return ;
    }
    else if (list.isEmpty())    //如果第二条链表为空
    {
        return ;
    }

    Node<Type> *endNode = first->next;
    //找到第一条链表的末尾节点
    while (endNode->next != NULL)
    {
        endNode = endNode->next;
    }

    //找到第二条链表的第一个真实元素
    Node<Type> *secondListNode = (list.first)->next;
    //注意: 需要将第二个链表中的元素值copy出来
    //不能直接将第二条链表的表头链接到第一条链表的表尾
    //不然在析构函数回收内存时会发生错误(即:同一段内存释放两次)
    while (secondListNode != NULL)
    {
        Node<Type> *newNode = new Node<Type>(secondListNode->data);
        newNode->next = NULL;
        endNode->next = newNode;

        //两条链表同时前进
        endNode = endNode->next;
        secondListNode = secondListNode->next;
    }
}

template <typename Type>
void MyList<Type>::invort()
{
    if (!isEmpty())
    {
        //p指向正向链表的第一个真实节点
        //随后, p也会沿正方向遍历到链表末尾
        Node<Type> *p = first->next;

        //q会成为倒向的第一个真实节点
        //首先将q设置为NULL: 保证反向之后
        //最后一个元素的指针域指向NULL, 以表示链表结束
        Node<Type> *q = NULL;
        while (p != NULL)
        {
            Node<Type> *r = q;  //暂存q当前指向的节点
            //q后退(沿着正向后退)
            q = p;
            //p前进(沿着正向前进), 保证p能够始终领先q一个位置
            p = p -> next;
            //将指针逆向反转
            //注意:一点要保证这条语句在p指针移动之后运行,
            //不然p就走不了了...(因为q改变了指针的朝向)
            q -> next = r;
        }

        //此时q成为反向链表的第一个真实元素
        //但是为了维护像以前一样的first指针指向一个无用的节点(以使前面的操作不会出错)
        //于是我们需要将first的指针域指向q
        first->next = q;
    }
}

//显示链表中的所有数据(测试用)
template <typename Type>
ostream &operator<<(ostream &os, const MyList<Type> &list)
{
    for (Node<Type> *searchNode = list.first -> next;
            searchNode != NULL;
            searchNode = searchNode -> next)
    {
        os << searchNode -> data;
        if (searchNode -> next != NULL) //尚未达到链表的结尾
            cout << " -> ";
    }

    return os;
}

//ListIterator的设计与实现
template <typename Type>
class ListIterator
{
public:
    ListIterator(const MyList<Type> &_list):
        list(_list),
        currentNode((_list.first)->next) {}

    //重载 *operator
    const Type &operator*() const throw (std::out_of_range);
    Type &operator*() throw (std::out_of_range);

    //重载 ->operator
    const Node<Type> *operator->() const throw (std::out_of_range);
    Node<Type> *operator->() throw (std::out_of_range);

    //重载 ++operator
    ListIterator &operator++() throw (std::out_of_range);
    //注意:此处返回的是值,而不是reference
    ListIterator operator++(int) throw (std::out_of_range);

    bool isEmpty() const;

private:
    const MyList<Type> &list;
    Node<Type> *currentNode;
};

template <typename Type>
const Type &ListIterator<Type>::operator*() const
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    // 返回当前指针指向的内容
    return currentNode->data;
}
template <typename Type>
Type &ListIterator<Type>::operator*()
throw (std::out_of_range)
{
    //首先为*this添加const属性,
    //以调用该函数的const版本,
    //然后再使用const_case,
    //将该函数调用所带有的const属性转除
    //operator->()的non-const版本与此类同
    return
        const_cast<Type &>(
            static_cast<const ListIterator<Type> &>(*this).operator*()
        );
}

template <typename Type>
const Node<Type> *ListIterator<Type>::operator->() const
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    //直接返回指针
    return currentNode;
}

template <typename Type>
Node<Type> *ListIterator<Type>::operator->()
throw (std::out_of_range)
{
    // 见上
    return
        const_cast<Node<Type> *> (
            static_cast<const ListIterator<Type> >(*this).operator->()
        );
}

template <typename Type>
ListIterator<Type> &ListIterator<Type>::operator++()
throw (std::out_of_range)
{
    if (isEmpty())
        throw std::out_of_range("iterator is out of range");
    //指针前移
    currentNode = currentNode->next;
    return *this;
}
template <typename Type>
ListIterator<Type> ListIterator<Type>::operator++(int)
throw (std::out_of_range)
{
    ListIterator tmp(*this);
    ++ (*this); //调用前向++版本

    return tmp;
}
template <typename Type>
bool ListIterator<Type>::isEmpty() const
{
    if (currentNode == NULL)
        return true;
    return false;
}

#endif // MYLIST_H_INCLUDED

相关文章：

  • 导游问题
  • 8611 大牛之路I
  • jCountdown倒计时插件jQuery
  • 【leetcode】Sort List (middle)
  • 模拟叫号系统
  • LINUX下如何开启FTP服务器
  • shell脚本中把txt文件中空格换成,逗号
  • 【问底】徐汉彬：Web系统大规模并发——电商秒杀与抢购
  • Java 中反射机制的深入研究
  • 从头开始学JavaScript (十二)——Array类型
  • FrameLayout的作用
  • 解决git push远程分支错误
  • Ubuntu 终端命令整理
  • 算法模板——线段树5（区间开根+区间求和）
  • 在Apache下开启SSI配置
  • 【技术性】Search知识
  • 2019.2.20 c++ 知识梳理
  • Electron入门介绍
  • JSDuck 与 AngularJS 融合技巧
  • Netty+SpringBoot+FastDFS+Html5实现聊天App(六)
  • OSS Web直传 （文件图片）
  • 阿里中间件开源组件：Sentinel 0.2.0正式发布
  • 大整数乘法-表格法
  • 技术胖1-4季视频复习— (看视频笔记)
  • 如何实现 font-size 的响应式
  • 深入浅出Node.js
  • 探索 JS 中的模块化
  • 小试R空间处理新库sf
  • ［地铁译］使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • linux 淘宝开源监控工具tsar
  • MyCAT水平分库
  • ​草莓熊python turtle绘图代码（玫瑰花版）附源代码
  • #多叉树深度遍历_结合深度学习的视频编码方法--帧内预测
  • $refs 、$nextTic、动态组件、name的使用
  • （003）SlickEdit Unity的补全
  • （1）(1.9) MSP (version 4.2)
  • （超简单）构建高可用网络应用：使用Nginx进行负载均衡与健康检查
  • (附源码)springboot课程在线考试系统 毕业设计 655127
  • (附源码)计算机毕业设计SSM在线影视购票系统
  • （含react-draggable库以及相关BUG如何解决）固定在左上方某盒子内（如按钮）添加可拖动功能，使用react hook语法实现
  • （一）spring cloud微服务分布式云架构 - Spring Cloud简介
  • （状压dp）uva 10817 Headmaster's Headache
  • **PHP二维数组遍历时同时赋值
  • *1 计算机基础和操作系统基础及几大协议
  • .Family_物联网
  • .net core 客户端缓存、服务器端响应缓存、服务器内存缓存
  • .NET Standard / dotnet-core / net472 —— .NET 究竟应该如何大小写？
  • .Net 代码性能 - (1)
  • .net 托管代码与非托管代码
  • .net经典笔试题
  • .Net小白的大学四年，内含面经
  • /usr/local/nginx/logs/nginx.pid failed (2: No such file or directory)
  • @select 怎么写存储过程_你知道select语句和update语句分别是怎么执行的吗？
  • []使用 Tortoise SVN 创建 Externals 外部引用目录
  • [2016.7 day.5] T2