内网小网站的建设,360帝国模板网欢迎大家来访_济南网站建设,推广_济南 去114网,邢台专业做移动网站,我是做网站的 哪里有单接✨个人主页#xff1a; 熬夜学编程的小林
#x1f497;系列专栏#xff1a; 【C语言详解】 【数据结构详解】【C详解】
目录 1、基本结构
2、基本函数实现
2.1、默认构造函数
2.2、尾插数据
3、迭代器的封装
3.1、迭代器的基本结构
3.2、迭代器重载函数的实现
4、迭…
✨个人主页 熬夜学编程的小林
系列专栏 【C语言详解】 【数据结构详解】【C详解】
目录 1、基本结构
2、基本函数实现
2.1、默认构造函数
2.2、尾插数据
3、迭代器的封装
3.1、迭代器的基本结构
3.2、迭代器重载函数的实现
4、迭代器与list进行关联
4.1、使用迭代器打印链表数据
4.2、其他相关函数
总结 1、基本结构
namespace lin
{templateclass Tstruct ListNode//双向循环链表的基本结构{ListNodeT* _prev;//前驱指针ListNodeT* _next;//后继指针T _data;//数据值//不传值时使用T()默认值构造传值则传值构造ListNode(const T val T())//默认构造 传值构造:_prev(nullptr),_next(nullptr),_data(val){}};templateclass Tstruct ListIterator//迭代器封装类成员都会被调用因此使用struct{typedef ListNodeT Node;Node* _node;//结点指针}templateclass Tclass list//链表模板类成员变量定义及函数封装{typedef ListNodeT Node;//将链表结构取别名简化代码public:typedef ListIteratorT iterator;//迭代器重命名private:Node* _head;//链表头指针size_t size;//链表长度}
}
上述代码实现了双向循环链表的基本结构其中包含了四个部分
1.namespace lin命令空间 lin 是用于封装代码避免同名类型和函数冲突。
2.在命名空间中定义了模板类ListNode(双向循环链表基本结构)该类包含三个成员变量
_prev : 存储指向前一个结点的指针_next : 存储指向后一个结点的指针_data : 存储数据
ListNode类还实现一个有缺省值(T())的构造函数如果构造函数没有提供参数则使用T类型的默认构造来初始化_data如果传值则使用该值来初始化_data该构造函数也会将_prev和_next指针指向nullptr。 3.模板类ListIterator(迭代器封装)该类包含一个成员变量即链表的结点指针
为什么链表需要封装一个迭代器的类呢 链表的物理空间是不连续的是通过结点的指针依次链接。不能像string和vector一样直接解引用去访问其数据。结点的指针解引用还是结点结点指针还是结点指针。在string和vector的物理空间是连续的所以这俩不需要实现迭代器类可以直接使用。 4.模板类list(链表的基本成员变量及其函数接口)该类包含两个成员变量
_head : 链表的头结点指针_size : 链表的长度 2、基本函数实现
注意我们实现的是带头双向循环链表。
2.1、默认构造函数
list() 默认构造的函数功能是构造一个没有元素的空容器。 思路我们实现的是带头双向循环链表因此默认构造时我们需要创建(new)一个头结点并将链表长度初始化为0。
//构造头结点函数
void empty_init()
{_head new Node;//创建新结点_head-_next _head;_head-_prev _head;_size 0;
}//默认构造 构造一个头结点
list()
{empty_init();
}
为了后序使用方便我们将构造头结点封装成了一个函数。 2.2、尾插数据
为什么在第二个函数就写尾插呢因为后面的函数会大量用到尾插函数。
push_back()
思想
先找到尾结点即头结点的前一个结点。然后将尾结点新结点以及头结点进行链接。
void push_back(const T val)
{//tail _head-_prevNode* tail _head-_prev;Node* newnode new Node(val);//创建一个值为val的新结点//tail newnode _head //链接关系的顺序tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;_size;//尾插之后长度要
} 我们尾插完数据之后想要遍历整个链表怎么遍历呢
我们在使用链表的时候是通过迭代器进行遍历如下代码
void test_list1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;cout lt.size() endl;
}
此时我们就需要对链表的迭代器进行封装 3、迭代器的封装
此时的迭代器是一个结点指针(Node*)。
3.1、迭代器的基本结构
templateclass T
struct ListIterator
{typedef ListNodeT Node;//类型起别名Node* _node;//成员变量ListIterator(Node* node)//构造函数:_node(node){}
};但是我们使用迭代器时是在list内部进行使用的且类型名称为iterator因此需要在list内部重命名迭代器类型(公有的因为我们需要在类外访问)。
templateclass T
class list
{
public: typedef ListIteratorT iterator;//迭代器重命名
};迭代器实质是一个结点指针因此类的成员是_node(结点指针)此处我们使用一个结点的指针对其初始化。
typedef ListNodeT Node;//类型起别名Node* _node;//成员变量ListIterator(Node* node)//构造函数:_node(node){}
3.2、迭代器重载函数的实现 前置 先再使用返回的是后的结点用引用返回。 //前置
typedef ListIteratorT Self//对返回迭代器类型重命名因为原类型较长
Self operator()
{_node _node-_next;return *this;
}
后置 先使用再返回的是前的结点传值返回。 typedef ListIteratorT Self
Self operator(int)
{Self tmp(*this);//构造一个临时变量存储之前的结点_node _node-_next;return tmp;//返回临时对象
}
注意前置和后置的区别是后置需要在形参中传一个占位符一般使用int类型。 前置-- 先--再使用返回的是--后的结点用引用返回。 Self operator--()
{_node _node-_prev;return *this;
} 后置-- 先使用再返回的是前的结点传值返回。 Self operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
}
为什么前置返回的是类对象引用而后置返回的是结点类型呢 因为在前置中我们返回的是类本身而后置我们返回的是一个局部的类对象局部的类对象出了函数会自动销毁。 operator* 对该迭代器位置的数据进行解引用类似与指针解引用。 T operator*()//遍历及修改
{return _node-_data;//访问链表的data数据
} operator! 重载两个迭代器不相等指针不相等则返回true相等则返回false。 bool operator!(const Self lt)
{return _node ! lt._node;//两个迭代器不相等即指针不相等
}
operator
bool operator(const Self lt)
{return _node lt._node;
} 注意比较迭代器是否相等比较的是的地址。 4、迭代器与list进行关联 4.1、使用迭代器打印链表数据
void test_list1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;cout lt.size() endl;
} 根据打印的测试函数我们可以知道我们需要获取链表的第一个结点的迭代器即第一个结点的地址但是这个地址只有在list类中有因此我们需要在list类中封装一个获取第一个结点的迭代器(begin)获取end()也是同理。 begin() 第一个结点的迭代器即头结点的下一个位置(_head-next)。 iterator begin()
{return iterator(_head-_next);//调用迭代器类的构造函数//return _head-next;//单参数的隐式类型转换
} end() 最后一个结点的下一个位置即_head位置。 iterator end()
{return iterator(_head);//return _head;
}
封装完迭代器之后我们就可以进行打印了。
list类代码
templateclass T
class list
{typedef ListNodeT Node;
public:typedef ListIteratorT iterator;iterator begin() //打印链表时只能访问数据不能修改内容及指向的内容{return iterator(_head-_next);}iterator end(){return iterator(_head);}
private:Node* _head;//链表头指针size_t _size;//链表大小
}; 测试结果 4.2、其他相关函数
insert() 在pos位置之前插入val。 思路
先获取当前结点的地址然后通过前驱指针找到前面一个结点的地址再创建一个新的结点最后将前驱结点新结点当前结点构成链接关系
void insert(iterator pos, const T val)//在pos位置前面插入val
{Node* cur pos._node;//当前结点指针Node* prev cur-_prev;Node* newnode new Node(val);//prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;
} erase() 删除pos位置的值并返回删除前的下一个结点的地址。 思路
先获取当前结点的地址然后通过前驱指针找到前一个结点地址通过后继指针找到后一个结点的地址将prev 前驱指针与后继指针建立链接关系释放当前结点返回next结点
iterator erase(iterator pos)//删除pos位置值迭代器失效问题
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev nextprev-_next next;next-_prev prev;delete cur;_size--;return iterator(next);//返回迭代器中结点指针
}
头插尾插头删尾删 复用insert()函数和erase()函数实现。 void push_back(const T val)
{insert(end(), val);//end()之前插入
}
void push_front(const T val)
{insert(begin(),val);//begin()之前插入
}
void pop_back()
{erase(--end());//删除end前面一个结点
}
void pop_front()
{erase(begin());//删除begin位置结点
} 总结 本篇博客就结束啦谢谢大家的观看如果公主少年们有好的建议可以留言喔谢谢大家啦
