首页 > 代码库 > 【指针】基于双向链表的list
【指针】基于双向链表的list
Description：
请实现以下基于双向链表的list类
enum Error_code{ success, underflow, overflow}; template <class List_entry>struct Node{ List_entry entry; Node<List_entry> *next; Node<List_entry> *back;}; template <class List_entry>class MyList{public: MyList(); ~MyList(); // 拷贝构造函数和赋值运算符重载，注意深拷贝与浅拷贝的差异 MyList(const MyList<List_entry> ©); void operator =(const MyList<List_entry> ©); // 清空list void clear(); // 判断list是否为空 bool empty() const; // 判断list是否已满 bool full() const; // 获取list的元素数量 int size() const; // 在第position个位置插入值为entry的元素，如果position为0则插入在链表头，依次类推 // 若position < 0 或者 position > count，则返回underflow Error_code insert(int position, const List_entry &entry); // 删除第position个位置的元素，并将该元素的值保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code remove(int position, List_entry &entry); // 获取第position个位置的元素，保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code retrieve(int position, List_entry &entry) const; // 将第position个位置的元素替换为entry // 若position < 0 或者 position >= count，则返回underflow Error_code replace(int position, const List_entry &entry); // 用visit函数遍历list内所有的元素 void traverse(void (*visit)(List_entry &)); protected: int count; // 记录list内元素数量 mutable int curPosition; // current指针的位置编号 mutable Node<List_entry> *current; // current指针 // 设置current指针的位置，指向第position个位置 void setPosition(int position) const;};
解题思路：
上一篇http://www.cnblogs.com/zengyh-1900/p/4067679.html讲到，
在处理基于单向链表的list时，在list中始终保持空队头的方法来避免出现非法访问内存地址的问题。
这里，我们探讨更为复杂的双向链表，原本，在队尾队头插入时都需要特殊判断，
但如果在队列中始终有一个空队头和空队尾，那么在队列中增加元素永远只有一种情况：
那么你就可以放心地，直接更新前节点的next，后节点的back以及新节点的这两个指针；
删除也类似：
（注意！curPosition的初始值为-1哦！）
实现代码：
enum Error_code{ success, underflow, overflow};template<class List_entry>struct Node{ List_entry entry; Node<List_entry>* next; Node<List_entry>* back;};template<class List_entry>class MyList{public: MyList() { curPosition= -1; count = 0; current = new Node<List_entry>; current->next = new Node<List_entry>; current->back = 0; current->next->next = 0; current->next->back = current; } ~MyList() { clear(); Node<List_entry>* tmp = current->next; delete tmp; delete current; count = curPosition = 0; current = 0; } MyList(const MyList<List_entry> ©){ curPosition= -1; count = 0; current = new Node<List_entry>; current->next = new Node<List_entry>; current->back = 0; current->next->next = 0; current->next->back = current; *this = copy; } void operator=(const MyList<List_entry>& copy){ clear(); List_entry entry; while (count < copy.size()) { copy.retrieve(count, entry); insert(count, entry); } setPosition(copy.curPosition); } void clear() { List_entry entry; while (size()) { remove(count-1, entry); } } bool empty() const { if (count) return false; else return true; } bool full() const { return false; } int size() const { return count; } Error_code insert(int position, const List_entry &entry) { if (position < 0 || position > count) return underflow; else { Node<List_entry>* tmp = new Node<List_entry>; tmp->entry = entry; setPosition(position-1); tmp->back = current; tmp->next = current->next; current->next = tmp; tmp->next->back = tmp; current = tmp; curPosition++; count++; return success; } } Error_code remove(int position, List_entry &entry) { if (position < 0 || position >= count) return underflow; else { setPosition(position); Node<List_entry>* tmp = current; entry = current->entry; current->back->next = current->next; current->next->back = current->back; current = current->next; delete tmp; count--; return success; } } Error_code retrieve(int position, List_entry &entry) const { if (position < 0 || position >= count) return underflow; else { setPosition(position); entry = current->entry; return success; } } Error_code replace(int position, const List_entry &entry) { if (position < 0 || position >= count) return underflow; else { setPosition(position); current->entry = entry; return success; } } void traverse(void(*visit)(List_entry&)) { for (int i = 0; i < size(); i++) { setPosition(i); (*visit)(current->entry); } }protected: int count; mutable int curPosition; mutable Node<List_entry>* current; void setPosition(int position) const { if (position >= curPosition) { for (; curPosition < position; curPosition++) current = current->next; } else { for (; curPosition > position; curPosition--) current = current->back; } }};
【指针】基于双向链表的list
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。