List环的问题

View Code
  1 //环的问题、拆环。
  2 #include<iostream>
  3 using namespace std;
  4 
  5 template<class Type> class LinkNode
  6 {
  7 public:
  8     LinkNode<Type> *link;
  9     Type data;
 10 
 11     LinkNode(LinkNode<Type>* ptr=NULL)
 12     {
 13         link=ptr;
 14     }
 15     LinkNode(const Type& item,LinkNode<Type>* ptr=NULL)
 16     {
 17         data=item;
 18         link=ptr;
 19     }
 20 };
 21 
 22 template<class Type> class List
 23 {
 24 public:
 25     List()
 26     {
 27         first=new LinkNode<Type>;
 28     }
 29 
 30     void init(const Type& end)
 31     {
 32         LinkNode<Type>* curr=first;
 33         Type val;
 34         cin>>val;
 35         while(val!=end)
 36         {
 37             LinkNode<Type>* newNode=new LinkNode<Type>(val);
 38             curr->link=newNode;
 39             curr=curr->link;
 40             cin>>val;
 41         }
 42     }
 43 
 44     void addCircle()
 45     {
 46         LinkNode<Type>* curr=first;
 47         while(curr->link!=NULL)
 48             curr=curr->link;
 49         curr->link=first->link->link->link;
 50     }
 51 
 52     void show()
 53     {
 54         LinkNode<Type>* curr=first->link;
 55         while(curr!=NULL)
 56         {
 57             cout<<curr->data<<"";
 58             curr=curr->link;
 59         }
 60         cout<<endl;
 61     }
 62 
 63     void printCircle()
 64     {
 65         LinkNode<Type> *odd,*even;
 66         odd=even=first;
 67         while(odd!=NULL&&even!=NULL)
 68         {
 69             odd=odd->link;
 70             even=even->link->link;
 71             if(even==odd)
 72             {
 73                 odd=odd->link;
 74                 cout<<"环里面的元素为："<<endl;
 75                 while(odd!=even)
 76                 {
 77                     cout<<odd->data<<"";
 78                     odd=odd->link;
 79                 }
 80                 cout<<odd->data<<endl;
 81                 return ;
 82             }
 83         }
 84     }
 85 
 86     void unpackCircle()  //解除环里面要用到两个交叉链表判交点的知识。
 87     {
 88         int M=1;  //环的长度
 89         int N=1;
 90         LinkNode<Type> *odd,*even,*curr;
 91         odd=even=first;
 92         while(odd!=NULL||even!=NULL)
 93         {
 94             odd=odd->link->link;
 95             even=even->link;
 96             if(even==odd)
 97                 break;
 98         }
 99         while(even->link!=odd)  //从odd开始，长度为M
100         {
101             even=even->link;
102             M++;
103         }
104         curr=first->link;
105         while(curr->link!=odd)  //从curr->link开始，长度为N
106         {
107             curr=curr->link;
108             N++;
109         }
110  //       cout<<M<<N;     //犯错就因为环的长度求错了。
111         if(M>N)  //求交点
112         {
113             curr=first->link;
114             for(int i=0;i<M-N;i++)
115                 odd=odd->link;
116             while(odd->link!=curr->link)
117             {
118                 curr=curr->link;
119                 odd=odd->link;
120             }
121  //              cout<<odd->link->data<<endl;
122             odd->link=NULL;
123         }
124         else
125         {
126             curr=first->link;
127             for(int i=0;i<N-M;i++)
128                 curr=curr->link;
129             while((odd->link)!=(curr->link))
130             {
131                 curr=curr->link;
132                 odd=odd->link;
133             }
134 
135             odd->link=NULL;
136 
137         }
138     }
139 private:
140     LinkNode<Type>* first;
141 };
142 
143 
144 int main()
145 {
146     List<string> list;
147     list.init("end");
148     list.show();
149     list.addCircle();
150     list.printCircle();
151     list.unpackCircle();
152     list.show();
153 }