数据结构与算法-----单向线性链表(逆转和反向打印)
作者:hnlyyk浏览数:5345 

单向链表没有前指针,所以实现反向打印还是比较麻烦,我们这里使用递归原理解决此问题。
这里提到逆转,也就是将单链表的next指针指向前一个节点,我们也使用递归实现。

// 练习:实现单向线性链表的建立、测长、正向打印和
// 反向打印
// 逆转
#include <iostream>
using namespace std;
class List {
public:
// 构造函数中初始化为空链表
List (void) : m_head (NULL), m_tail (NULL) {}
// 析构函数中销毁剩余的节点
~List (void) {
 for (Node* next; m_head; m_head = next) {
  next = m_head -> m_next;
  delete m_head;
 }
}
// 追加
void append (int data) {
 Node* node = new Node (data);
 if (m_tail)
  m_tail -> m_next = node;
 else
  m_head = node;
 m_tail = node;
}
// 测长
size_t length (void) const {
 size_t len = 0;
 for (Node* node = m_head; node;
  node = node -> m_next)
  len++;
 return len;
}
// 正向打印
void print (void) const {
 for (Node* node = m_head; node;
  node = node -> m_next)
  cout << node -> m_data << ' ';
 cout << endl;
}
// 反向打印
void rprint (void) const {
 rprint (m_head);
 cout << endl;
}
//逆转
void reverse(void){
 reverse(m_head);
 swap(m_head,m_tail);
}
private:
// 节点
class Node {
public:
 Node (int data = 0, Node* next = NULL) :
  m_data (data), m_next (next) {}
 int   m_data; // 数据
 Node* m_next; // 后指针
};
// 反向打印以head为首的子链表
void rprint (Node* head) const {
 if (head) {//使用递归(也即堆栈方式)实现逆向打印链表
  rprint (head -> m_next);
  cout << head -> m_data << ' ';
 }//如果head为空,函数会一层一层的返回
}
void reverse(Node *head){
 if(head && head->m_next){
  reverse(head->m_next);
  head->m_next->m_next=head;
  head->m_next=NULL;
 }
}
Node* m_head; // 头指针
Node* m_tail; // 尾指针
};
int main (void) {
List list;
for (int i = 1; i <= 20; i++)
 list.append (i);
cout << list.length () << endl;
list.print ();
list.rprint ();
list.reverse ();
list.print ();
return 0;
}

联系管理员
 
 
 
 
 工作时间
周一至周五 :9:30-17:30
会员登录
登录
我的资料
留言
回到顶部