![]()
1 // LinkListDemo.cpp : Defines the entry point for the console application.
2 //
3
4 #include "stdafx.h"
5
6 #include <iostream>
7 #include <assert.h>
8 using namespace std;
9
10 #define random(x) (rand()%x)
11
12 #define INVALIDVALUE -1000000000
13
14 typedef struct LNode
15 {
16 int data;
17 LNode* pnext;
18 LNode(){data = INVALIDVALUE; pnext = NULL;}
19 }BINODE, *PBINODE;
20
21 class CLinkList
22 {
23 public:
24 CLinkList();
25 ~CLinkList();
26
27 private:
28 CLinkList(const CLinkList &rh);
29 CLinkList& operator=(const CLinkList &rh);
30
31 public:
32
33 //
34 // 函数功能：获取链表中元素个数
35 int getcount();
36
37 //
38 // 函数功能：清空链表
39 void clear();
40
41 //
42 // 函数功能：获取链表第nPos个位置上的结点指针
43 PBINODE getnode(int nPos);
44
45 //
46 // 函数功能：获取中间结点
47 // 注：这个获取的方式是通过连个指针，一个步长为1，另一个步长为2.步长为2的走到底后步长为1的正好到中间
48 int getmid();
49
50 //
51 // 函数功能：获取根结点
52 PBINODE getroot();
53
54 //
55 // 函数功能：在nPos位置上插入元素
56 bool insertnode(PBINODE pNode, int nPos);
57
58 //
59 // 函数功能：在nPos位置上插入元素
60 bool insertnode(int value, int nPos);
61
62 //
63 // 函数功能：删除第nPos位置上的元素
64 bool deletenode(int nPos);
65
66 //
67 // 函数功能：打印链表
68 void printnode();
69
70 //
71 // 函数功能：值为nValue元素的第n次出现的位置
72 int locate(int nvalue,int n);
73
74 //
75 // 函数功能：逆置
76 void reverse();
77
78 //
79 // 函数功能：排序（冒泡排序法）
80 void BubbleSort();
81
82 private:
83 PBINODE m_root;
84 int m_nCount;
85 };
86
87 CLinkList::CLinkList()
88 {
89 m_root = new LNode();
90 m_nCount = 0;
91 assert(m_root != NULL);
92 }
93
94 CLinkList::~CLinkList()
95 {
96 clear();
97 }
98
99 //
100 // 函数功能：获取链表中元素个数
101 int CLinkList::getcount()
102 {
103 return m_nCount;
104 }
105
106 //
107 // 函数功能：清空链表
108 void CLinkList::clear()
109 {
110 PBINODE pNode = m_root;
111 PBINODE ptmpNode = NULL;
112 while(pNode != NULL)
113 {
114 ptmpNode = pNode->pnext;
115 delete pNode;
116 pNode = ptmpNode;
117 }
118 m_root = NULL;
119 }
120
121 //
122 // 函数功能：获取根结点
123 PBINODE CLinkList::getroot()
124 {
125 return m_root;
126 }
127
128 //
129 // 函数功能：获取链表第nPos个位置上的结点指针
130 PBINODE CLinkList::getnode(int npos)
131 {
132 if (m_root == NULL)
133 {
134 return NULL;
135 }
136
137 if (npos > getcount())
138 {
139 return NULL;
140 }
141
142 PBINODE pNode = m_root;
143 int i = 0;
144 while (i < npos)
145 {
146 pNode = pNode->pnext;
147 i++;
148 }
149 return pNode;
150 }
151
152 //
153 // 函数功能：获取中间结点
154 // 注：这个获取的方式是通过连个指针，一个步长为1，另一个步长为2.步长为2的走到底后步长为1的正好到中间
155 int CLinkList::getmid()
156 {
157 /*
158 // 方法一，通过对象本身的个数来求中间的元素
159 if (getcount() <= 1)
160 {
161 return INVALIDVALUE;
162 }
163
164 int nMid = getcount() / 2;
165
166 PBINODE pNode = getnode(nMid);
167 assert(pNode != NULL);
168
169 return pNode->data;
170 */
171
172 PBINODE pNode = getroot();
173 PBINODE pTNode = pNode->pnext;
174 while (pTNode != NULL)
175 {
176 pNode = pNode->pnext;
177 pTNode = pTNode->pnext;
178 if (pTNode != NULL)
179 {
180 pTNode = pTNode->pnext;
181 }
182 }
183 assert(pNode != NULL);
184 return pNode->data;
185 }
186
187 //
188 // 函数功能：在nPos位置上插入元素
189 bool CLinkList::insertnode(PBINODE pNode, int nPos)
190 {
191 if (pNode == NULL || nPos <= 0 || nPos > getcount() + 1)
192 {
193 return false;
194 }
195
196 PBINODE pPreNode = getnode(nPos - 1);
197 assert(pPreNode != 0);
198 PBINODE ptmp = pPreNode->pnext;
199 pPreNode->pnext = pNode;
200 pNode->pnext = ptmp;
201 m_nCount++;
202
203 return true;
204 }
205
206 //
207 // 函数功能：在nPos位置上插入元素
208 bool CLinkList::insertnode(int value, int nPos)
209 {
210 if (nPos <= 0 || nPos > getcount() + 1)
211 {
212 return false;
213 }
214
215 PBINODE pNode = new LNode();
216 assert(pNode != NULL);
217 pNode->data = value;
218
219 PBINODE pPreNode = getnode(nPos - 1);
220 assert(pPreNode != NULL);
221
222 PBINODE ptmp = pPreNode->pnext;
223
224 pPreNode->pnext = pNode;
225 pNode->pnext = ptmp;
226
227 m_nCount++;
228
229 return true;
230 }
231
232 //
233 // 函数功能：删除第nPos位置上的元素
234 bool CLinkList::deletenode(int nPos)
235 {
236 if (nPos <= 0 || nPos > getcount())
237 {
238 return false;
239 }
240
241 PBINODE pNode = getnode(nPos - 1);
242 assert(pNode != NULL);
243 PBINODE pDNode = pNode->pnext;
244 assert(pDNode != NULL);
245 pNode->pnext = pDNode->pnext;
246
247 delete pDNode;
248 pDNode = NULL;
249
250 return true;
251 }
252
253 //
254 // 函数功能：打印链表
255 void CLinkList::printnode()
256 {
257 PBINODE root = getroot();
258 PBINODE pNode = root->pnext;
259 while(pNode != NULL)
260 {
261 cout<< pNode->data<< " ";
262 pNode = pNode->pnext;
263 }
264 cout<<endl;
265 }
266
267 //
268 // 函数功能：值为nValue元素的第n次出现的位置
269 int CLinkList::locate(int nvalue,int n)
270 {
271 PBINODE root = getroot();
272 PBINODE pNode = root->pnext;
273 int i = 0;
274
275 int nNum = 0;
276 while (pNode != NULL /*&& pNode->data != nvalue*/)
277 {
278 if (pNode->data == nvalue)
279 {
280 nNum++;
281 }
282 pNode = pNode->pnext;
283 i++;
284 if (nNum == n)
285 {
286 break;
287 }
288 }
289
290 if (pNode == NULL)
291 {
292 return 0;
293 }
294 else
295 {
296 return i;
297 }
298
299 }
300
301 //
302 // 函数功能：逆置
303 void CLinkList::reverse()
304 {
305 PBINODE root = getroot();
306 assert(root != NULL);
307
308 PBINODE prenode = root->pnext;
309 assert(prenode != NULL);
310
311 PBINODE curnode = prenode->pnext;
312 prenode->pnext = NULL;
313 while (curnode != NULL)
314 {
315 PBINODE nextnode = curnode->pnext;
316 curnode->pnext = prenode;
317 prenode = curnode;
318 curnode = nextnode;
319 }
320
321 root->pnext = prenode;
322 }
323
324 //
325 // 函数功能：排序（冒泡排序法）
326 void CLinkList::BubbleSort()
327 {
328 PBINODE root = getroot();
329 assert(root != NULL);
330
331 for (int i = 0; i < getcount(); i++)
332 {
333 PBINODE pNode = root->pnext;
334 for (int j = 0; j < getcount() - i; j++)
335 {
336 PBINODE pNodeNext = pNode->pnext;
337 if (pNodeNext == NULL)
338 {
339 break;
340 }
341 if (pNode->data > pNodeNext->data)
342 {
343 int tmp = pNode->data;
344 pNode->data = pNodeNext->data;
345 pNodeNext->data = tmp;
346 }
347 pNode = pNode->pnext;
348 if (pNode == NULL)
349 {
350 break;
351 }
352 }
353 }
354 }
355
356 //已知指针la和lb分别指向两个链表。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。
357 void DeleteAndInsertSub(CLinkList &la, CLinkList &lb, int i, int len)
358 {
359 if (i + len - 1 > la.getcount() || i <= 0 || len < 0 || i > lb.getcount())
360 {
361 return;
362 }
363
364 if (la.getroot() == lb.getroot())
365 {
366 return;
367 }
368
369 PBINODE pLa = la.getnode(i);
370 if (pLa == NULL)
371 {
372 return;
373 }
374
375 int nCount = 0;
376 while (nCount < len && pLa != NULL)
377 {
378 int nvalue = pLa->data;
379 lb.insertnode(nvalue, i + nCount);
380 pLa = pLa->pnext;
381 nCount++;
382 }
383 }
384
385 //已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序
386 void Merge(CLinkList &la, CLinkList &lb)
387 {
388
389 }
390
391 //如何检查一个单向链表上是否有环,同样两个指针，一个步长为1，另一个步长为2，如果两个指针能相遇则有环。
392 bool IsCircle(const CLinkList &la)
393 {
394
395 }
396
397 //只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。将p后面那个节点的值复制到p，删除p后面的节点
398 void DeleteNode(int nPos)
399 {
400
401 }
402
403 //在p前面插入一个节点 。在p后面插入新节点，将p的值与新建的节点值互换。
404 void InsertNode(int nPos)
405 {
406
407 }
408
409 //给定单链表头结点，删除链表中倒数第k个结点. 一个指针指向链表头，另一个指针指向第k个指针，然后两个指针一起移动，第二个指针到了末端则第一个指针就是倒数第k个节点
410 void ReverseDelete(int npos)
411 {
412
413 }
414
415 //判断两个链表是否相交。两种情况，如果链表有环，则先在环里设定一个指针不动，另一个链表从头开始移动，如果另一个链表能够与环中的指针相遇则是相交。如果没有环，则判断两个链表的最后个节点是否相同，相同则相交
416 bool IsCross(const CLinkList &la, const CLinkList &lb)
417 {
418
419 }
420
421 //两个链表相交，找出交点求出两个链表的长度a和b，一个指针指向较短链表的头head，另一个指针指向较长链表的第head+|a-b|，然后两个指针一起移动，相遇处即为交点。
422 int CrossNode(const CLinkList &la, const CLinkList &lb)
423 {
424
425 }
426
427 int _tmain(int argc, _TCHAR* argv[])
428 {
429 CLinkList link1;
430
431 cout<<"初始化链表link1："<<endl;
432 int i = 0;
433 for (i = 1; i <= 15; i++)
434 {
435 int val = random(100);
436 if (!link1.insertnode(val, i))
437 {
438 return 0;
439 }
440 }
441
442 link1.insertnode(41, 10);
443 link1.printnode();
444 cout<<"link1链表长度为："<<link1.getcount()<<endl;
445 cout << "41在link1中第2次出现的位置："<<link1.locate(41, 2)<<endl;
446 cout<<"link1链表逆序为："<<endl;
447 link1.reverse();
448 link1.printnode();
449 cout<<endl;
450
451 CLinkList link2;
452 cout<<"初始化链表link2："<<endl;
453 for (i = 1; i <= 20; i++)
454 {
455 int val = random(100);
456 if (!link2.insertnode(val, i))
457 {
458 return 0;
459 }
460 }
461 link2.insertnode(41, 17);
462 link2.printnode();
463 cout<<"link2链表长度为："<<link2.getcount()<<endl;
464
465 DeleteAndInsertSub(link1, link2, 3, 3);
466 link2.printnode();
467 cout<<"修改后link2链表长度为："<<link2.getcount()<<endl;
468
469 cout<<endl<<"两个链表进行排序，排序后显示："<<endl;
470 link1.BubbleSort();
471 link1.printnode();
472
473 link2.BubbleSort();
474 link2.printnode();
475
476 cout<<"获取link1的中间元素：";
477 cout<<link1.getmid()<<endl;
478 return 0;
479 }
