线性表的正向迭代器实现
发布日期：2021-06-30 22:08:18
浏览次数：2
分类：技术文章
本文共 7839 字，大约阅读时间需要 26 分钟。
线性表包括 : 数组(动态数组类,静态数组类), 链表, 栈, 队列
以双向链表为例, 实现正向迭代器.
测试程序
// testcase.cpp : Defines the entry point for the console application.//#include#include #include "LsDoublyLinkedList.h"void fnTestDbList(); ///< 测试CLsLinkedList 双链表的所有接口int main(int argc, char* argv[]){ fnTestDbList(); return 0;}void fnTestDbList(){ int i = 0; int iTmp = 0; CLsLinkedList list; CLsLinkedList ::iterator it = NULL; CLsLinkedList ::iterator itToDel = NULL; for (i = 1; i < 10; i++) { it = list.addTail(i); list.setAt(it, 100 + i); iTmp = list.getAt(it); it = list.addHead(i + 200); list.setAt(it, 100 + i); iTmp = list.getAt(it); if (0 == (i % 2)) { itToDel = it; list.insert(it, 300 + i); } } list.removeAt(itToDel); list.removeHead(); list.removeTail(); printf("[%d]\n", list.getLength()); it = list.getHead(); while (it != list.end()) { printf("%d ", *it); it++; } printf("\r\n"); it = list.getTail(); while(it != list.end()) { printf("%d ", *it); it++; } printf("\r\n"); }
带正向迭代器的双向链表实现
// LsDoublyLinkedList.h: interface for the CLsLinkedList class.////#if !defined(LSDOUBLYLINKEDLIST_H_82FEA8FE_F7B8_4CD7_A162_751580726632)#define LSDOUBLYLINKEDLIST_H_82FEA8FE_F7B8_4CD7_A162_751580726632/**链表总结空间 链式存储时间复杂度 尽量避免提供非常量阶的接口 增加操作: O(1) 常量阶, 快 删除操作: O(1) 常量阶, 快 修改操作:O(1) 快(条件:知道位置, 用的是先前返回的位置类或结点指针) 查询操作:O(n) 线性阶, 慢 随机访问:O(n) 线性阶, 慢使用场合 * 问题规模不确定 * 随机访问频率低 * 数据更新频率高(主要指的是添加和删除操作)缺点 * 查询速度慢(数组和链表查询速度都慢)原生new的时间复杂度 new实现是线性阶. 调用的memset是线性阶, 有循环操作. HeapAlloc中没源码, 但是有循环操作, 是线性阶. new不影响时间增长率.结论 当算法中, new次数较少时, 可以忽略new对算法时间复杂度的影响. 当new次数较多时, 可以一次多new几个元素(e.g. 10个), 下次就不用new, 直接取已经new好的数据操作, 等用完了, 才再次new几个元素出来. 这样对new操作做优化, 等于自己做堆管理, 需要再做一个链表, 将new出来的10个一组的小块内存空间管理起来, 当一个类指针不用了, 就称为闲置空间, 放在内存池中. 下次不用再申请了, 可以复用. 等链表析构时, 链表的原生操作完成后, 再一块释放内存池.*/#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000/// ----------------------------------------------------------------------/// CLsLinkedList 双链表 定义/// ----------------------------------------------------------------------templateclass CLsLinkedList {public: /// ---------------------------------------------------------------------- /// CLsLinkedNode 定义 /// ---------------------------------------------------------------------- /// LsDoublyLinkedList's Node template struct CLsLinkedNode { friend CLsLinkedList ; ///< 不需要前向声明, 用到的时候才检查 friend CLsLinkedList ::iterator; private: CLsLinkedNode(T Elem) :m_Elem(Elem) ,m_pNext(NULL) ,m_pPrev(NULL) { } ~CLsLinkedNode() { } T m_Elem; //数据元素 CLsLinkedNode * m_pPrev; //前驱 CLsLinkedNode * m_pNext; //后继 }; /// ---------------------------------------------------------------------- /// 正向迭代器 定义 /// ---------------------------------------------------------------------- class iterator { friend class CLsLinkedList ; public: iterator() { m_pNode = NULL; } iterator(CLsLinkedNode * pNode) { m_pNode = pNode; } iterator operator++() { m_pNode = m_pNode->m_pNext; return m_pNode; } iterator operator++(int) { CLsLinkedNode *pTemp = m_pNode; m_pNode = m_pNode->m_pNext; return pTemp; } iterator operator--() { m_pNode = m_pNode->m_pPrev; return m_pNode; } iterator operator--(int) { CLsLinkedNode *pTemp = m_pNode; m_pNode = m_pNode->m_pPrev; return pTemp; } T& operator* () { return m_pNode->m_Elem; } bool operator!= (const iterator& obj) { return m_pNode != obj.m_pNode; } bool operator== (const iterator& obj) { return m_pNode == obj.m_pNode; } private: CLsLinkedNode * GetNode() { return m_pNode; } private: CLsLinkedNode * m_pNode; };public: iterator begin() { return m_pHead; } iterator end() { return NULL; }public: CLsLinkedList(); virtual ~CLsLinkedList(); /// 只提供O(1)的接口^_^ iterator getTail() const; iterator getHead() const; inline bool isEmpty() const; inline size_t getLength() const; //表长 void clear(); iterator addTail(T newElem); bool removeTail(); iterator addHead(T newElem); bool removeHead(); T getAt(iterator it) const; void setAt(iterator it, T newElem); bool removeAt(iterator it); bool insert(iterator it, T newElem);private: CLsLinkedNode * m_pHead; //头结点 CLsLinkedNode * m_pTail; //尾结点 size_t m_nLength;};/// ----------------------------------------------------------------------/// CLsLinkedList 实现/// ----------------------------------------------------------------------template inline size_t CLsLinkedList ::getLength() const{ return m_nLength;}template inline bool CLsLinkedList ::isEmpty() const{ return (NULL == m_pHead) ? true : false;}template CLsLinkedList ::CLsLinkedList():m_pHead(NULL),m_pTail(NULL),m_nLength(0){}template CLsLinkedList ::~CLsLinkedList(){ clear();}template void CLsLinkedList ::clear(){ while (!isEmpty()) { removeTail(); }}template T CLsLinkedList ::getAt(CLsLinkedList::iterator it) const{ return *it;}template void CLsLinkedList ::setAt(CLsLinkedList::iterator it, T newElem){ *it = newElem;}template bool CLsLinkedList ::insert(CLsLinkedList::iterator it, T newElem){ CLsLinkedNode * pNewNode = NULL; CLsLinkedNode * pPrev = NULL; CLsLinkedNode * pNext = NULL; pPrev = it.GetNode(); if (NULL == pPrev) { return false; } pNewNode = new CLsLinkedNode (newElem); pNext = pPrev->m_pNext; /* 1 2 3 [6] 4 5 3.next = 6 4.prev = 6 6.prev = 3 6.next = 4 1 2 3 4 5 [6] */ pPrev->m_pNext = pNewNode; if (NULL != pNext) { pNext->m_pPrev = pNewNode; } pNewNode->m_pPrev = pPrev; pNewNode->m_pNext = pNext; m_nLength++; return true;}template bool CLsLinkedList ::removeTail(){ bool bRc = false; CLsLinkedNode * pPrev = NULL; if (NULL == m_pHead) { return false; } //1 2 [3] if (NULL != m_pTail) { pPrev = m_pTail->m_pPrev; if (NULL != pPrev) { pPrev->m_pNext = NULL; } else { m_pHead = NULL; } delete m_pTail; bRc = true; m_pTail = pPrev; m_nLength--; } return bRc;}template bool CLsLinkedList ::removeHead(){ if (NULL == m_pHead) { return false; } //[1] 2 3 CLsLinkedNode * pNext = m_pHead->m_pNext; if (NULL != pNext) { pNext->m_pPrev = NULL; } else { m_pTail = NULL; } delete m_pHead; m_nLength--; m_pHead = pNext; return true;}template bool CLsLinkedList ::removeAt(CLsLinkedList::iterator it){ CLsLinkedNode * pDelNode = it.GetNode(); CLsLinkedNode * pPrev = NULL; CLsLinkedNode * pNext = NULL; if ((NULL == m_pHead) || (NULL == pDelNode)) { return false; } /* 1 2 [3] 4 5 2.next = 4 4.prev = 2 [1] 2 3 4 5 1 2 3 4 [5] [1] */ pPrev = pDelNode->m_pPrev; pNext = pDelNode->m_pNext; if (NULL != pPrev) { pPrev->m_pNext = pNext; } else { m_pHead = pNext; } if (NULL != pNext) { pNext->m_pPrev = pPrev; } else { m_pTail = pPrev; } delete pDelNode; m_nLength--; return true;}template CLsLinkedList ::iterator CLsLinkedList ::addTail(T newElem){ CLsLinkedList ::CLsLinkedNode * pNewNode = new CLsLinkedList ::CLsLinkedNode (newElem); //空表 if (NULL == m_pHead) { m_pHead = m_pTail = pNewNode; } else { //1 2 3 4 5 [6] //5.next = 6 6.prev = 5 tail = 6 m_pTail->m_pNext = pNewNode; pNewNode->m_pPrev = m_pTail; m_pTail = pNewNode; } m_nLength++; return pNewNode;}template CLsLinkedList ::iterator CLsLinkedList ::addHead(T newElem){ CLsLinkedList ::CLsLinkedNode *pNewNode = new CLsLinkedList ::CLsLinkedNode (newElem); //空表 if (NULL == m_pHead) { m_pHead = m_pTail = pNewNode; } else { //[6] 1 2 3 4 5 //1.prev = 6 6.next = 1 head = 6 m_pHead->m_pPrev = pNewNode; pNewNode->m_pNext = m_pHead; m_pHead = pNewNode; } m_nLength++; return pNewNode;}template CLsLinkedList ::iterator CLsLinkedList ::getTail() const{ return m_pTail;}template CLsLinkedList ::iterator CLsLinkedList ::getHead() const{ return m_pHead;}#endif // !defined(LSDOUBLYLINKEDLIST_H_82FEA8FE_F7B8_4CD7_A162_751580726632)
转载地址：https://lostspeed.blog.csdn.net/article/details/50474674 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
表示我来过！
[***.240.166.169]2024年05月02日 07时50分24秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
基础架构系列篇-系统centos7中docker安装分布式文件存储服务minio
2019-04-30
知识点记录-java判断系统是linux或windows
2019-04-30
知识点记录-springboot静态资源映射路径
2019-04-30
微服务springcloud2系列篇-配置与注册nacos组件
2019-04-30
用户权限设计-基于RBAC模型
2019-04-30
微服务springcloud2系列篇-网关GATEWAY跨域问题
2019-04-30
软件质量的8个特性
2019-04-30
应届渣渣前端的艰难求职之路
2019-04-30
2021年不可错过的17种JS优化技巧（一）
2019-04-30
月薪15~20k的前端面试问什么？
2019-04-30
在 Vue 中用 Axios 异步请求API
2019-04-30
MySQL进阶查询（SELECT 语句高级用法）
2019-04-30
Mysql 之主从复制
2019-04-30
【工具使用】新版CSDN-markdown编辑器使用指南
2019-04-30
【NLP学习笔记】中文分词（Word Segmentation，WS）
2019-04-30
【超越白皮书7】你需要知道关于ETH2.0的几个事实
2019-04-30
对于时间复杂度的通俗理解
2019-04-30
如何输入多组数据并输出每组数据的和？
2019-04-30
行阶梯型矩阵
2019-04-30
图像处理学习笔记
2019-04-30
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 311238579 位访客
访问时间: 2024-05-06 01:07:12
访问IP: 3.144.25.74
Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1
手机版