不要懒惰

过去的就过去了，何必再想。把握现在和未来，才是最重要的。认真对待每一天，让生命不再有抱怨和遗憾。天道酬勤，一切从头开始!

统计

留言簿

阅读排行榜

评论排行榜

单链表的反转实现(C++)

数据结构和算法忘得差不多了，今天被问及链表反转怎样实现，老半天才想出来，惭愧死。

  1#include <iostream>
  2#include <cstdlib>
  3
  4using namespace std;
  5
  6class Node
  7{
  8       private:
  9         int data;
 10          Node* next;
 11       public:
 12          friend class List;
 13          Node(int theValue)
 14          {
 15              data = theValue;
 16              next = 0;              
 17          }                 
 18            
 19};
 20      
 21class List
 22{
 23     public:
 24            List()
 25            {
 26                  first = 0;
 27                  end = 0;
 28            }
 29            ~List()
 30            {
 31                   Node* next;
 32                   while (first)
 33                   {
 34                         next = first->next;
 35                         delete first;
 36                         first = next;
 37                   }
 38            }
 39            
 40            
 41            //增加item,从屁股后面插入 ^_^
 42            void Add(int value)
 43            {
 44                 if (first == 0)
 45                 {
 46                    first = end = new Node(value);
 47                 }
 48                 else
 49                 {
 50                     end->next = new Node(value);
 51                     end = end->next;
 52                 }
 53            }
 54            
 55            //反转List,从前面插入(原有的item,不要想歪了 ^_^)
 56            void Reverse()
 57            {
 58                 if (first == 0)
 59                    return;
 60                 
 61                 Node* newFirst = first;//临时变量，保存新的first. 
 62                 end = first;//反转后，first 刚好和end 互换. 
 63                 Node* nextOfFirst;//辅助变量，其值始终为first的下一个成员，即first->next. 
 64                 
 65                 first = first->next;                
 66                 while (first)
 67                 {
 68                       nextOfFirst = first->next;
 69                       
 70                       first->next = newFirst;
 71                       newFirst = first;
 72                       
 73                       first = nextOfFirst;
 74                 }
 75                 
 76                 first = newFirst;  
 77                 end->next = 0;
 78                 
 79            }
 80            
 81            //显示List的所有成员 
 82            void Display()
 83            {
 84                 if (first == 0)
 85                 {
 86                     cout << "The List has no items." << endl;
 87                     return;
 88                 }
 89                 else
 90                 {
 91                     cout << "The List's items:" << endl;
 92                 }
 93                    
 94                 Node* item = first;
 95                 while (item)
 96                 {
 97                       cout << item->data << " ";
 98                       item = item->next;                       
 99                 }
100                 
101                 cout << endl;
102            }
103
104     private:
105            Node* first;
106            Node* end;
107      
108};
109
110
111int main()
112{
113    List theList;
114    for (int i = 0; i < 10; i++)
115        theList.Add(i);
116        
117    //显示其初始值
118    cout << "List 的原始值为：" <<endl; 
119    theList.Display();
120    
121
122    //反转，并显示其值
123    cout << endl <<endl
124         <<"List 反转之后的值为：" << endl; 
125    theList.Reverse();
126    theList.Display();
127    
128    system("pause");  
129
130}
131
132
133

posted on 2006-02-28 19:46 不要懒惰 阅读(4148) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理