View Code
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4
5 template<class Type> class List
6 {
7 private:
8 template<class T> class LinkNode
9 {
10 public:
11 LinkNode<Type>* link;
12 Type data;
13
14 LinkNode(LinkNode<Type>* ptr=NULL)
15 {
16 link=ptr;
17 }
18 LinkNode(const Type& item,LinkNode<Type>* ptr=NULL)
19 {
20 data=item;
21 link=ptr;
22 }
23 };
24
25 public:
26 List()
27 {
28 first=new LinkNode<Type>();
29 }
30
31 void init(const Type& end)
32 {
33 LinkNode<Type> *newNode,*curr;
34 Type val;
35 cin>>val;
36 curr=first;
37 while(val!=end)
38 {
39 newNode=new LinkNode<Type>(val);
40 curr->link=newNode;
41 curr=curr->link;
42 cin>>val;
43 }
44 }
45
46 int length() const
47 {
48 int len=0;
49 LinkNode<Type> *curr=first;
50 while(curr->link!=NULL)
51 {
52 curr=curr->link;
53 len++;
54 }
55 return len;
56 }
57
58 LinkNode<Type>* getHead() const
59 {
60 return first;
61 }
62
63 void show()
64 {
65 LinkNode<Type> *curr;
66 curr=first->link;
67 while(curr!=NULL)
68 {
69 cout<<curr->data<<"";
70 curr=curr->link;
71 }
72 cout<<endl;
73 }
74
75
76 void bignumAdd(const List<Type>& list)
77 {
78 int result;
79 int len1=length();
80 int len2=list.length();
81 if(len1<len2)
82 {
83 for(int i=0;i<len2-len1;i++)
84 {
85 LinkNode<Type>* newNode=new LinkNode<Type>(0,first->link);
86 // cout<<first->link->data;
87 first->link=newNode;
88 }
89 len1=length();
90
91 }
92 result=addNode(first->link,list.getHead()->link,len1,len2);
93 if(result==1)
94 {
95 LinkNode<Type>* newNode=new LinkNode<Type>(first->link);
96 first->link=newNode;
97 newNode->data=1;
98 }
99 }
100
101 int addNode(LinkNode<Type>* head1,LinkNode<Type>* head2,int len1,int len2)
102 {
103
104 int result,temp;
105 result=0;
106 if(len1>len2)
107 {
108 result=addNode(head1->link,head2,len1-1,len2);
109 temp=head1->data+result;
110 head1->data=temp%10;
111 return temp/10==1?1:0;
112 }
113 else
114 if(head1!=NULL)
115 {
116 result=addNode(head1->link,head2->link,len1-1,len2-1);
117 temp=head1->data+head2->data+result;
118 head1->data=temp%10;
119 return temp/10==1?1:0;
120 }
121 return 0;
122 }
123
124 void bubbleSort()
125 {
126 LinkNode<Type> *curr1,*curr2;
127 for(curr1=first;curr1->link!=NULL;curr1=curr1->link)
128 {
129 for(curr2=first;curr2->link->link!=NULL;curr2=curr2->link)
130 if(curr2->link->data>curr2->link->link->data)
131 {
132 LinkNode<Type> *temp=curr2->link;
133 curr2->link=curr2->link->link;
134 temp->link=curr2->link->link;
135 curr2->link->link=temp;
136 }
137 }
138 }
139
140 void insertSort()
141 {
142 LinkNode<Type> *curr1,*curr2;
143 for(curr1=first->link;curr1->link!=NULL;)
144 {
145 bool flag=false;
146 for(curr2=first;curr2!=curr1;curr2=curr2->link)
147 if(curr1->link->data<curr2->link->data)
148 {
149 flag=true;
150 LinkNode<Type> *temp=curr2->link;
151 curr2->link=curr1->link;
152 curr1->link=curr1->link->link;
153 curr2->link->link=temp;
154 break;
155 }
156 if(flag==false&&curr1->link!=NULL) //注意如果插入了，便不需要作curr1后移操作。
157 curr1=curr1->link;
158 }
159 }
160
161 void selectSort()
162 {
163 LinkNode<Type> *curr1,*curr2,*min;
164 for(curr1=first;curr1->link!=NULL;curr1=curr1->link)
165 {
166 min=curr1;
167 for(curr2=curr1->link;curr2->link!=NULL;curr2=curr2->link)
168 if(curr2->link->data<min->link->data)
169 min=curr2;
170 if(min!=curr1)
171 {
172 if(curr1->link!=min)
173 {
174 LinkNode<Type> *temp1=curr1->link->link;
175 curr1->link->link=min->link->link;
176 min->link->link=temp1;
177 temp1=curr1->link;
178 curr1->link=min->link;
179 min->link=temp1;
180 }
181 else if(curr1->link==min)
182 {
183 LinkNode<Type>* temp=min->link->link;
184 min->link->link=curr1->link;
185 curr1->link=min->link;
186 min->link=temp;
187 }
188 }
189 }
190 }
191
192
193 void deleteDuplexElements()
194 {
195 int a[10000];
196 memset(a,0,sizeof(a));
197 LinkNode<Type>* curr=first;
198 while(curr->link!=NULL)
199 {
200 if(a[curr->link->data]!=0)
201 {
202 curr->link=curr->link->link;
203 if(curr->link==NULL)
204 break;
205 }
206 else
207 {
208 a[curr->link->data]=1;
209 curr=curr->link; //注意不能写到外面去。
210 }
211 }
212 }
213
214 private:
215 LinkNode<Type>* first;
216 };
217
218 int main()
219 {
220 List<int> list1,list2;
221 list1.init(-1);
222 list1.show();
223 // list1.bubbleSort();
224 // list1.insertSort();
225 // list1.selectSort();
226 list1.deleteDuplexElements();
227 list1.show();
228 }
插入排序：
外层循环i从第二个元素开始遍历，内层循环j从i向前遍历，如果找到比它小，便右移，等到比他大的时候，就与之交换，所以插入之后有序。
但是由于链表内外循环只能从前向后遍历，外i内j，j从0到i遍历，如果比它小，便果断插入。
冒泡排序：
外层循环i从n到0反向遍历，内层循环j从0到i遍历，碰到比它大的便交换。
链表也只能从前到后，只能每一次把最大的找出来放最后。但是显然这需要外层循环那么多次。
选择排序：
外层遍历一次，内层从i开始遍历一次，找最小元素，如果找到，则交换。
为什么不是稳定的呢，因为交换之后可能比较大的数交换到后面去了，所以不稳定。
链表用选择排序的方法一样。
总结一点，就是交换点的时候一定要注意。
从读题到解题，思维要更快。