1 单链表翻转的非递归实现：
Node* reverse(Node *header) { Node* guard = NULL;//链表翻转后的头结点 Node* current = reinterpret_cast<Node*>(header);//当前结点 Node* prev = NULL;//前一结点 while(current != NULL) { Node* pNext = current->next;//下一结点 if(NULL == pNext)//如果是单结点链表 { guard = current; } current->next = prev;//当前结点的下一个结点指向前一结点,实现翻转只需要更改这一个指向 prev = current;//将前一结点移到当前结点位置（更新pre和current） current = pNext;//将当前结点后移 } return guard; }
单链表的操作汇总
template <typename T> class LinkedList:public List<T> { protected: struct Node:public Object { T value;//数据域 Node* next;//指针域 }; mutable struct:public Object { char reserved[sizeof(T)];//占位空间 Node* next; }m_header; int m_length; int m_step; Node* m_current; protected: Node* position(int index)const { //指针指向头结点 Node* ret = reinterpret_cast<Node*>(&m_header); //遍历到目标位置 for(int i = 0; i < index; i++) { ret = ret->next; } return ret; } public: LinkedList() { m_header.next = NULL; m_length = 0; m_step = 1; m_current = NULL; } virtual ~LinkedList() { clear(); }
/*
单链表的插入
*/
bool insert(int index, const T& value) { //判断目标位置是否合法 bool ret = (0 <= index) && (index <= m_length); if(ret) { //创建新的结点 Node* node = createNode(); if(node != NULL) { //当前结点定位到目标位置 Node* current = position(index); //修改插入结点的值 node->value = value; //将当前位置的下一个结点作为插入结点的下一个结点 node->next = current->next; //将要插入结点作为当前结点的下一个结点 current->next = node; m_length++;//链表结点长度加1 } else { THROW_EXCEPTION(NoEnoughMemoryException, "No enough memmory..."); } } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is invalid..."); } return ret; } bool insert(const T& value) { return insert(m_length, value); }
//////////////////////////// bool remove(int index) { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //当前结点指向头结点 Node* current = position(index); //使用toDel指向要删除的结点 Node* toDel = current->next; //将当前结点的下一个结点指向要删除结点的下一个结点 current->next = toDel->next; m_length--;//链表结点长度减1 destroy(toDel);//释放要删除的结点的堆空间 } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; }
///////// bool set(int index, const T& value) { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //将当前结点指向头结点 Node* current = position(index); //修改目标结点的数据域的值 current->next->value = value; } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; }
//////// bool get(int index, T& value)const { //判断目标位置是否合法 bool ret = (0 <= index) && (index < m_length); if(ret) { //当前结点指向头结点 Node* current = position(index); //遍历到目标位置 //获取目标结点的数据域的值 value = current->next->value; } else { THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter inde is invalid..."); } return ret; }
//重载版本 T get(int index)const { T ret; if(get(index, ret)) return ret; } int length()const { return m_length; }
/////////////// int find(const T& value)const { int ret = -1; //指向头结点 Node* node = m_header.next; int i = 0; while(node) { //找到元素，退出循环 if(node->value == value) { ret = i; break; } else { node = node->next; i++; } } return ret; }
////////////// void clear() { //遍历删除结点 while(m_header.next) { //要删除的结点为头结点的下一个结点 Node* toDel = m_header.next; //将头结点的下一个结点指向删除结点的下一个结点 m_header.next = toDel->next; m_length--; destroy(toDel);//释放要删除结点 } }
//////////// bool move(int pos, int step = 1) { bool ret = (0 <= pos) && (pos < m_length) && (0 < step); if(ret) { m_current = position(pos)->next; m_step = step; } return ret; }
/////////////// bool end() { return m_current == NULL; } T current() { if(!end()) { return m_current->value; } else { THROW_EXCEPTION(InvalidOperationException, "Invalid Operation..."); } }
//////////// bool next() { int i = 0; while((i < m_step) && (!end())) { m_current = m_current->next; i++; } return (i == m_step); } virtual Node* createNode() { return new Node(); } virtual void destroy(Node* node) { delete node; } };