首页 > 代码库 > 【指针】基于单向链表的list
【指针】基于单向链表的list
请实现以下基于单向链表的list类
enum Error_code
{
success,
underflow,
overflow
};
template <class List_entry>
struct Node
{
List_entry entry;
Node<List_entry> *next;
};
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内元素数量
Node<List_entry> *head; // 链表头指针
mutable int curPosition; // current指针的位置编号
mutable Node<List_entry> *current; // current指针
// 设置current指针的位置，指向第position个位置
void setPosition(int position) const;
};
解题思路：
首先，对于一个普通的list来说，最基本的不外乎增删查改，其他的赋值或清空都可以通过这4种操作来完成，写好这主要的4个函数就好了。
另外，注意到这个MyList类提供了current这个指针。
1.insert（增）：
position合理的情况下，若position为队头，则直接将position的next指向head，head再更新；
若position不是队头，position的next指向下一个位置，前一个节点的next指向position；
2.remove（删）：
position合理的情况下，若删除位置为队头，head=head->next，并注意将原本的队头delete；
若删除位置不是队头，则前节点直接指向potision的后节点，position节点delete即可；
3.retrieve（查）：
调用setPosition来查找目标，并返回值即可；
4.replace（改）：
调用setPosition查找目标，并修改值；
5.赋值运算：
不断从copy中读取（retrieve），并插入（insert）到MyList中；
6.clear（清空）：
可以不断调用remove来清空，这里代码我就直接用for循环来删除啦。
7.setPosition：是通过current指针来提高平均时间复杂度的一个函数；
当position比current大时，current只需向后更新；
若position小于current时，则current先更新为head，然后再更新到position位置
实现代码：
enum Error_code//错误信息{ success, underflow, overflow};template<class List_entry>struct Node{ List_entry entry; Node<List_entry>*next;};template<class List_entry>class MyList{ public: MyList() { curPosition = count = 0; head = current = 0; } ~MyList() { clear(); } // 拷贝构造函数和赋值运算符重载 MyList(const MyList<List_entry> ©) { curPosition = count = 0;//拷贝构造函数一定要对数据成员进行初始化！ head = current = 0; *this = copy; } void operator=(const MyList<List_entry> ©) { clear(); List_entry entry; for (count = 0; count < copy.size(); ) { copy.retrieve(count, entry);//读取 insert(count, entry); //增加 } setPosition(copy.curPosition); } // 清空list void clear() { Node<List_entry>* tmp1 = head; Node<List_entry>* tmp2; while (tmp1 != 0) { tmp2 = tmp1->next; delete tmp1; tmp1 = tmp2; } count = curPosition = 0; current = head = 0; } // 判断list是否为空 bool empty() const { if (count == 0) return true; else return false; } // 判断list是否已满 bool full() const { return false; } // 获取list的元素数量 int size() const { return count; } // 在第position个位置插入值为entry的元素，如果position为0则插入在链表头，依次类推 // 若position < 0 或者 position > count，则返回underflow Error_code insert(int position, const List_entry& entry) {// if (position < 0 || position > count) return underflow; else { count++; Node<List_entry>* tmp = new Node<List_entry>; tmp->entry = entry; if (position == 0) { if (head == 0) {//在队头增加 tmp->next = head; head = tmp; } current = head; } else { //在list中间增加 setPosition(position-1); tmp->next = current->next; current->next = tmp; current = tmp; curPosition++; } } return success; } // 删除第position个位置的元素，并将该元素的值保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code remove(int position, List_entry &entry) { if (position < 0 || position >= count) return underflow; else { count--; if (position == 0) //删队头 { Node<List_entry>* tmp= head; entry = tmp->entry; head= head->next; delete tmp; current = head; curPosition = 0; } else { //删除list中的元素 setPosition(position-1); Node<List_entry>* tmp = current->next; entry = tmp->entry; current->next = tmp->next; delete tmp; } return success; } } // 获取第position个位置的元素，保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code retrieve(int position, List_entry& entry) const { if (position < 0 || position >= count) return underflow; else { setPosition(position); entry = current->entry; return success; } } // 将第position个位置的元素替换为entry // 若position < 0 或者 position >= count，则返回underflow Error_code replace(int position, const List_entry &entry) { if (position < 0 || position >= count) return underflow; else { setPosition(position); current->entry = entry; return success; } } // 用visit函数遍历list内所有的元素 void traverse(void(*visit)(List_entry&)) { Node<List_entry>* tmp = head; for (int i = 0; i < count; i++) { (*visit)(tmp->entry); tmp = tmp ->next; } } protected: int count; // 记录list内元素数量 Node<List_entry>*head; // 链表头指针 mutable int curPosition; // current指针的位置编号 mutable Node<List_entry>* current; // current指针 // 设置current指针的位置，指向第position个位置 void setPosition(int position) const { if (position >= curPosition) for (; curPosition < position; curPosition++) current = current->next; else for (current = head, curPosition = 0; curPosition < position; curPosition++) current = current->next; }};
进一步思考：
这里，我们不妨再看看，常常runtime error让我们头疼的链表问题是非法访问内存地址，
比如，队列为空时，head==0，但我们常常不小心访问了head->next，或者企图访问head的前节点
而这个情况常常发生在增删的情况中，那我们可以使list初始情况就为非空
令head永远指向一个空节点node（node->next=0）,初始情况curPosition=-1，
这样每次插入新元素，不管新元素的位置在哪里，都不用再做特殊判断，直接更新position前节点的next即可
每次删除新元素，也不用管是不是队头，直接更新前节点的next即可
实现代码：
/*有空队头的情况*/enum Error_code//错误信息{ success, underflow, overflow};template<class List_entry>struct Node{ List_entry entry; Node<List_entry>*next;};template<class List_entry>class MyList{ public: MyList() { count = 0; curPosition = -1; head = current = new Node<List_entry>; head->next = 0; } ~MyList() { clear(); delete head; head = current = 0; count = curPosition = 0; } // 拷贝构造函数和赋值运算符重载 MyList(const MyList<List_entry> ©) { count = 0;//拷贝构造函数一定要对数据成员进行初始化！ curPosition = -1; head = current = new Node<List_entry>; head->next = 0; *this = copy; } void operator=(const MyList<List_entry> ©) { clear(); List_entry entry; while(count < copy.size()) { copy.retrieve(count, entry);//读取 insert(count, entry);//增加 } setPosition(copy.curPosition); } // 清空list void clear() { Node<List_entry>* tmp1 = head->next; Node<List_entry>* tmp2; while (tmp1 != 0) { tmp2 = tmp1->next; delete tmp1; tmp1 = tmp2; } count = 0; current = head; head->next = 0; curPosition = -1; } // 判断list是否为空 bool empty() const { if (count == 0) return true; else return false; } // 判断list是否已满 bool full() const { return false; } // 获取list的元素数量 int size() const { return count; } // 在第position个位置插入值为entry的元素，如果position为0则插入在链表头，依次类推 // 若position < 0 或者 position > count，则返回underflow 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->next = current->next; current->next = tmp; current = tmp; curPosition++; count++; } return success; } // 删除第position个位置的元素，并将该元素的值保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code remove(int position, List_entry &entry) { if (position < 0 || position >= count) return underflow; else { setPosition(position-1); Node<List_entry>* tmp = current->next; entry = tmp->entry; current->next = tmp->next; delete tmp; count--; return success; } } // 获取第position个位置的元素，保存在entry中 // 若position < 0 或者 position >= count，则返回underflow Error_code retrieve(int position, List_entry& entry) const { if (position < 0 || position >= count) return underflow; else { setPosition(position); entry = current->entry; return success; } } // 将第position个位置的元素替换为entry // 若position < 0 或者 position >= count，则返回underflow Error_code replace(int position, const List_entry &entry) { if (position < 0 || position >= count) return underflow; else { setPosition(position); current->entry = entry; return success; } } // 用visit函数遍历list内所有的元素 void traverse(void(*visit)(List_entry&)) { Node<List_entry>* tmp = head->next; for (int i = 0; i < count; i++) { (*visit)(tmp->entry); tmp = tmp ->next; } } protected: int count;// 记录list内元素数量 Node<List_entry>*head;// 链表头指针 mutable int curPosition;// current指针的位置编号 mutable Node<List_entry>* current;// current指针 // 设置current指针的位置，指向第position个位置 void setPosition(int position) const { if (position >= curPosition) for (; curPosition < position; curPosition++) current = current->next; else for (current = head, curPosition = -1; curPosition < position; curPosition++) current = current->next; }};
总结：
也许你觉得这不过是少了十几行代码，少了两段if语句，但下一篇，双向链表，我们能更进一步看见这种方法的安全性和便捷性。
【指针】基于单向链表的list