广东微信网站制作哪家好,怎样免费给自己的公司做网站,揭东建设局网站,宝安网站制作网站建设文章目录 前言#xff1a;1. 主要数据结构2. 迭代器的实现3. 链表的实现3.1 基本结构3.2 链表的插入与删除3.3 其他成员函数 4. 迭代器操作与遍历链表5. 拷贝构造与赋值运算符6. 总结 前言#xff1a; 在 C 标准库中#xff0c;std::list 是一种非常常用的数据结构#xff… 文章目录 前言1. 主要数据结构2. 迭代器的实现3. 链表的实现3.1 基本结构3.2 链表的插入与删除3.3 其他成员函数 4. 迭代器操作与遍历链表5. 拷贝构造与赋值运算符6. 总结 前言 在 C 标准库中std::list 是一种非常常用的数据结构其底层采用了双向链表的实现。在实际开发中双向链表是一种具有灵活插入和删除操作的数据结构尤其适合那些需要频繁操作非连续内存数据的场景。本文将通过一个手动实现的双向链表类 list 来讲解双向链表的底层结构和实现原理。 1. 主要数据结构
在链表的实现中节点是最基本的元素每个节点存储数据以及指向前后节点的指针。为了支持双向操作链表的每个节点都有两个指针分别指向前驱节点和后继节点。下面的 list_node 是一个模板类存储泛型类型 T 的数据。
template class T
struct list_node {T _data; // 存储节点数据list_node* _next; // 指向下一个节点list_node* _prev; // 指向上一个节点// 构造函数list_node(const T x T()): _data(x), _next(nullptr), _prev(nullptr) {}
};2. 迭代器的实现
在链表的操作中迭代器是至关重要的它提供了与链表元素交互的机制。通过迭代器用户可以像使用数组指针一样访问链表的元素。我们实现了 list_iterator 模板类用于模拟标准库的迭代器。它不仅支持对节点的访问还支持前后移动和增减操作。
template class T, class Ref, class Ptr
struct list_iterator {typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr self;Node* _node; // 当前迭代器指向的节点list_iterator(Node* node) : _node(node) {}Ref operator*() { return _node-_data; }Ptr* operator-() { return _node-_data; }// 前置移动到下一个节点self operator() {_node _node-_next;return *this;}// 前置--移动到上一个节点self operator--() {_node _node-_prev;return *this;}// 后置移动到下一个节点返回之前的状态self operator(int) {self tmp(*this);_node _node-_next;return tmp;}// 后置--移动到上一个节点返回之前的状态self operator--(int) {self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self s) { return _node ! s._node; }bool operator(const self s) { return _node s._node; }
};迭代器主要提供以下功能
operator* 和 operator-实现解引用操作返回当前节点的数据。 operator 和 operator–支持迭代器的前进和后退。 operator! 和 operator支持迭代器的比较判断是否到达链表末尾。 通过实现这些运算符我们可以像操作指针一样操作链表中的元素。
3. 链表的实现
接下来我们实现链表的主体类 list。这是一个模板类可以存储任意类型的数据并提供一些常见的链表操作。
3.1 基本结构
首先我们在链表类中定义一个哨兵节点 _head这个节点没有实际的数据作用它的存在是为了简化链表的边界处理。通过让哨兵节点的 _next 和 _prev 指向自己可以避免处理链表为空时的特殊情况。
template class T
class list {typedef list_nodeT Node; // 节点类型
public:typedef list_iteratorT, T, T* iterator; // 可修改的迭代器typedef list_iteratorT, const T, const T* const_iterator; // 常量迭代器// 构造函数list() {empty_init();}// 拷贝构造函数list(const listT lt) {empty_init();for (auto e : lt) {push_back(e);}}// 赋值操作符listT operator(listT lt) {swap(lt);return *this;}// 析构函数~list() {clear();delete _head;_head nullptr;}private:Node* _head; // 哨兵节点size_t _size; // 链表的大小// 初始化空链表void empty_init() {_head new Node();_head-_next _head;_head-_prev _head;_size 0;}
};在 list 的实现中除了常见的构造、析构函数我们还实现了拷贝构造函数和赋值操作符。这确保了链表在被拷贝时能够正确复制内容。
3.2 链表的插入与删除
在双向链表中插入和删除操作是其核心功能。我们通过 insert 函数将新元素插入到链表的指定位置。它首先获取要插入位置前后的节点然后重新设置这些节点的指针使新节点正确链接到链表中。
iterator insert(iterator pos, const T val) {Node* cur pos._node;Node* newnode new Node(val);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);
}对于删除操作我们通过 erase 函数实现。erase 函数移除指定位置的节点并将该节点前后的节点重新连接。
iterator erase(iterator pos) {assert(pos ! end());Node* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;return iterator(next);
}3.3 其他成员函数
我们还实现了链表的其他常用操作如 push_back 和 push_front用于在链表尾部和头部插入元素。pop_back 和 pop_front 则用于删除尾部和头部的元素。
void push_back(const T x) {insert(end(), x);
}void push_front(const T x) {insert(begin(), x);
}void pop_back() {erase(--end());
}void pop_front() {erase(begin());
}这些操作都依赖于 insert 和 erase 函数实现起来相对简单。
4. 迭代器操作与遍历链表
我们为链表提供了 begin() 和 end() 函数用于获取链表的起始和结束迭代器。通过这些迭代器用户可以遍历整个链表访问每个元素。
iterator begin() {return iterator(_head-_next);
}iterator end() {return iterator(_head);
}
可以通过以下代码遍历链表的元素
listint lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);for (auto it lt.begin(); it ! lt.end(); it) {cout *it ;
}
// 输出: 1 2 35. 拷贝构造与赋值运算符
我们实现了拷贝构造函数和赋值运算符通过它们可以确保链表被正确复制。赋值运算符通过 swap 函数交换两个链表的内部结构从而实现高效的赋值。
listT operator(listT lt) {swap(lt);return *this;
}void swap(listT tmp) {std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}6. 总结
本文从底层实现的角度详细讲解了如何手动实现一个双向链表容器 list。我们设计了双向链表的数据结构通过节点、迭代器、基本的插入、删除操作最终实现了一个功能完整的链表容器。以下是本文的主要内容回顾
1.双向链表节点设计每个节点存储数据元素同时通过两个指针 _prev 和 _next 链接到前一个和后一个节点。这种设计使得我们可以在链表中进行双向遍历并支持 O(1) 时间复杂度的插入和删除操作。
2.迭代器的实现为了让链表可以像标准库中的容器一样被遍历我们实现了 list_iterator。通过运算符重载用户可以使用迭代器访问链表元素进行正向和反向遍历。迭代器操作封装了链表内部的指针操作使链表的使用更加简洁直观。
3.链表类的实现
插入和删除我们实现了常见的 insert 和 erase 操作它们负责在指定位置插入新元素或移除已有元素。双向链表的优势在于我们可以在常数时间内完成这些操作而无需像数组那样需要移动后续元素。push_back 和 push_front为了方便用户插入元素我们提供了头部和尾部的插入操作分别对应在链表的首位插入新元素。pop_back 和 pop_front链表的首尾删除操作也被封装在这两个函数中方便用户快速删除首尾元素。
4.迭代器操作与遍历通过 begin() 和 end() 函数我们可以使用 C 标准的范围遍历方式遍历链表的所有元素。这使得链表容器的使用方式与 C 标准库中的其他容器一致降低了使用门槛。
5.拷贝构造与赋值运算符为了确保链表可以被正确拷贝我们实现了拷贝构造函数和赋值操作符。在赋值操作中我们通过 swap 函数实现高效的资源交换避免了复杂的手动赋值操作。
