1 #include <stdio.h>
2 #include <stdlib.h>
3
4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
5
6 /***********************************************************************
7 單向鏈表
8 ***********************************************************************/
9 typedef int dataType;
10
11 typedef struct sgNode {
12 dataType data;
13 struct sgNode *pNext;
14 } sgNode;
15
16 typedef sgNode sgLinkList;
17
18 sgLinkList *createSgLinkList( char bHead )
19 {
20 sgLinkList *pHead = NULL;
21 sgNode *pNew = NULL, *pPre = NULL;
22 dataType data = ( dataType )0;
23
24 if ( NULL == ( pHead = ( sgNode* )malloc( sizeof( sgNode ) ) ) ) {
25 return NULL;
26 }
27
28 setbuf( stdin, NULL );
29
30 if ( 0 == bHead ) {
31 if ( 1 > scanf( "%d", &data ) ) {
32 free( pHead );
33 return NULL;
34 }
35 }
36
37 pHead->data = data;
38 pHead->pNext = NULL;
39 pPre = pHead;
40
41 while ( scanf( "%d", &data ) ) {
42 if ( NULL == ( pNew = ( sgNode* )malloc( sizeof( sgNode ) ) ) ) {
43 break;
44 }
45
46 pPre->pNext = pNew;
47 pNew->data = data;
48 pNew->pNext = NULL;
49 pPre = pNew;
50 }
51
52 if ( 1 == bHead ) {
53 if ( NULL == pHead->pNext ) {
54 free( pHead );
55 return NULL;
56 }
57 }
58
59 return pHead;
60 }
61
62 void printSgLinkList( char bHead, sgLinkList *pLink )
63 {
64 sgNode *pNode = NULL;
65
66 if ( NULL == pLink ) {
67 return;
68 }
69
70 if ( 0 == bHead ) {
71 pNode = pLink;
72
73 } else {
74 pNode = pLink->pNext;
75 }
76
77 for ( ; NULL != pNode->pNext; pNode = pNode->pNext ) {
78 printf( "%d ", pNode->data );
79 }
80
81 printf( "%d\n", pNode->data );
82
83 return;
84 }
85
86 int getSgLinkListCount( char bHead, sgLinkList *pLink )
87 {
88 int count = 0;
89 sgNode *pNode = NULL;
90
91 if ( NULL == pLink ) {
92 return count;
93 }
94
95 if ( 0 == bHead ) {
96 pNode = pLink;
97
98 } else {
99 pNode = pLink->pNext;
100 }
101
102 for ( ; NULL != pNode; pNode = pNode->pNext ) {
103 count++;
104 }
105
106 return count;
107 }
108
109 sgNode *insertNodeIntoSgLinkList( char bHead, sgLinkList *pLink, int position, dataType data )
110 {
111 int count = 0;
112 sgNode *pNode = NULL, *pNew = NULL;
113
114 if ( NULL == pLink ) {
115 return NULL;
116 }
117
118 if ( 1 > position ) {
119 return NULL;
120 }
121
122 if ( 0 == bHead ) {
123 pNode = pLink;
124
125 } else {
126 pNode = pLink->pNext;
127 }
128
129 for ( count = 1; count < position - 1; pNode = pNode->pNext ) {
130 if ( NULL != pNode ) {
131 count++;
132
133 } else {
134 return NULL;
135 }
136 }
137
138 if ( NULL == ( pNew = ( sgNode* )malloc( sizeof( sgNode ) ) ) ) {
139 return NULL;
140 }
141
142 pNew->data = data;
143 pNew->pNext = pNode->pNext;
144 pNode->pNext = pNew;
145
146 return pNew;
147 }
148
149 void deleteSgLinkListNode( char bHead, sgLinkList *pLink, int position )
150 {
151 int count = 0;
152 sgNode *pNode = NULL, *pOld = NULL;
153
154 if ( NULL == pLink ) {
155 return;
156 }
157
158 if ( 1 > position ) {
159 return;
160 }
161
162 if ( 0 == bHead ) {
163 pNode = pLink;
164
165 } else {
166 pNode = pLink->pNext;
167 }
168
169 for ( count = 1; count < position - 1; pNode = pNode->pNext ) {
170 if ( NULL != pNode ) {
171 count++;
172
173 } else {
174 return;
175 }
176 }
177
178 pOld = pNode->pNext;
179 pNode->pNext = pOld->pNext;
180 free( pOld );
181 }
182
183 sgLinkList *reverseSgLinkList( char bHead, sgLinkList *pLink )
184 {
185 sgNode *pFirst = NULL, *pNode = NULL, *pNext = NULL;
186
187 if ( NULL == pLink ) {
188 return NULL;
189 }
190
191 if ( 0 == bHead ) {
192 pFirst = pLink;
193
194 } else {
195 pFirst = pLink->pNext;
196 }
197
198 pNode = pFirst->pNext;
199 pFirst->pNext = NULL;
200
201 while ( pNode ) {
202 pNext = pNode->pNext;
203 pNode->pNext = pFirst;
204 pFirst = pNode;
205 pNode = pNext;
206 }
207
208 if ( 0 == bHead ) {
209 pLink = pFirst;
210
211 } else {
212 pLink->pNext = pFirst;
213 }
214
215 return pLink;
216 }
217
218 sgNode *getBottomOfSgLinkList( char bHead, sgLinkList *pLink, int bottom )
219 {
220 int count = 0;
221 sgNode *pNode = NULL, *pBottom = NULL;
222
223 if ( NULL == pLink ) {
224 return NULL;
225 }
226
227 if ( 0 == bHead ) {
228 pNode = pBottom = pLink;
229
230 } else {
231 pNode = pBottom = pLink->pNext;
232 }
233
234 while ( pNode ) {
235 count++;
236 if ( bottom < count ) {
237 pBottom = pBottom->pNext;
238 }
239 pNode = pNode->pNext;
240 }
241
242 if ( bottom > count ) {
243 return NULL;
244 }
245
246 return pBottom;
247 }
248
249 sgLinkList *sortSgLinkList( char bHead, sgLinkList *pLink )
250 {
251 sgNode *pFirst = NULL, *pNode = NULL, *pNext = NULL, *pMove = NULL;
252
253 if ( NULL == pLink ) {
254 return NULL;
255 }
256
257 if ( 0 == bHead ) {
258 pFirst = pLink;
259
260 } else {
261 pFirst = pLink->pNext;
262 }
263
264 pNode = pFirst->pNext;
265 pFirst->pNext = NULL;
266
267 while ( pNode ) {
268 pNext = pNode->pNext;
269 pMove = pFirst;
270 while ( pMove ) {
271 if ( ( pMove == pFirst ) && ( pNode->data < pMove->data ) ) {
272 pNode->pNext = pFirst;
273 pFirst = pNode;
274 break;
275 }
276
277 if ( ( pMove->pNext ) && ( pMove->data <= pNode->data ) && ( pNode->data < pMove->pNext->data ) ) {
278 pNode->pNext = pMove->pNext;
279 pMove->pNext = pNode;
280 break;
281 }
282
283 if ( ( NULL == pMove->pNext ) && ( pMove->data <= pNode->data ) ) {
284 pNode->pNext = pMove->pNext;
285 pMove->pNext = pNode;
286 break;
287 }
288
289 pMove = pMove->pNext;
290 }
291 pNode = pNext;
292 }
293
294 if ( 0 == bHead ) {
295 pLink = pFirst;
296
297 } else {
298 pLink->pNext = pFirst;
299 }
300
301 return pLink;
302 }
303
304
305
306
307 /***********************************************************************
308 雙向鏈表
309 ***********************************************************************/
310 typedef struct dbNode {
311 dataType data;
312 struct dbNode *pPrev;
313 struct dbNode *pNext;
314 } dbNode;
315
316 typedef dbNode dbLinkList;
317
318 dbLinkList *createDbLinkList( char bHead )
319 {
320 dbLinkList *pHead = NULL;
321 dbNode *pNew = NULL, *pPre = NULL;
322 dataType data = ( dataType )0;
323
324 if ( NULL == ( pHead = ( dbNode* )malloc( sizeof( dbNode ) ) ) ) {
325 return NULL;
326 }
327
328 setbuf( stdin, NULL );
329
330 if ( 0 == bHead ) {
331 if ( 1 > scanf( "%d", &data ) ) {
332 free( pHead );
333 return NULL;
334 }
335 }
336
337 pHead->data = data;
338 pHead->pPrev = NULL;
339 pHead->pNext = NULL;
340 pPre = pHead;
341
342 while ( scanf( "%d", &data ) ) {
343 if ( NULL == ( pNew = ( dbNode* )malloc( sizeof( dbNode ) ) ) ) {
344 break;
345 }
346
347 pPre->pNext = pNew;
348 pNew->data = data;
349 pNew->pPrev = pPre;
350 pNew->pNext = NULL;
351 pPre = pNew;
352 }
353
354 if ( 1 == bHead ) {
355 if ( NULL == pHead->pNext ) {
356 free( pHead );
357 return NULL;
358 }
359 }
360
361 return pHead;
362 }
363
364 void printDbLinkList( char bHead, dbLinkList *pLink )
365 {
366 dbNode *pNode = NULL;
367
368 if ( NULL == pLink ) {
369 return;
370 }
371
372 if ( 0 == bHead ) {
373 pNode = pLink;
374
375 } else {
376 pNode = pLink->pNext;
377 }
378
379 for ( ; NULL != pNode->pNext; pNode = pNode->pNext ) {
380 printf( "%d ", pNode->data );
381 }
382
383 printf( "%d\n", pNode->data );
384
385 return;
386 }
387
388 void printDbLinkListBack( char bHead, dbLinkList *pLink )
389 {
390 dbNode *pNode = NULL;
391
392 if ( NULL == pLink ) {
393 return;
394 }
395
396 if ( 0 == bHead ) {
397 pNode = pLink;
398
399 } else {
400 pNode = pLink->pNext;
401 }
402
403 while ( pNode->pNext ) {
404 pNode = pNode->pNext;
405 }
406
407 for ( ; NULL != pNode->pPrev; pNode = pNode->pPrev ) {
408 printf( "%d ", pNode->data );
409 }
410
411 if ( 0 == bHead ) {
412 printf( "%d\n", pNode->data );
413
414 } else {
415 printf( "\n" );
416 }
417
418 return;
419 }
420
421 int getDbLinkListCount( char bHead, dbLinkList *pLink )
422 {
423 int count = 0;
424 dbNode *pNode = NULL;
425
426 if ( NULL == pLink ) {
427 return count;
428 }
429
430 if ( 0 == bHead ) {
431 pNode = pLink;
432
433 } else {
434 pNode = pLink->pNext;
435 }
436
437 for ( ; NULL != pNode; pNode = pNode->pNext ) {
438 count++;
439 }
440
441 return count;
442 }
443
444 dbNode *insertNodeIntoDbLinkList( char bHead, dbLinkList *pLink, int position, dataType data )
445 {
446 int count = 0;
447 dbNode *pNode = NULL, *pNew = NULL;
448
449 if ( NULL == pLink ) {
450 return NULL;
451 }
452
453 if ( 1 > position ) {
454 return NULL;
455 }
456
457 if ( 0 == bHead ) {
458 pNode = pLink;
459
460 } else {
461 pNode = pLink->pNext;
462 }
463
464 for ( count = 1; count < position - 1; pNode = pNode->pNext ) {
465 if ( NULL != pNode ) {
466 count++;
467
468 } else {
469 return NULL;
470 }
471 }
472
473 if ( NULL == ( pNew = ( dbNode* )malloc( sizeof( dbNode ) ) ) ) {
474 return NULL;
475 }
476
477 pNew->data = data;
478 pNew->pPrev = pNode;
479 pNew->pNext = pNode->pNext;
480 pNode->pNext = pNew;
481 pNew->pNext->pPrev = pNew;
482
483 return pNew;
484 }
485
486 void deleteDbLinkListNode( char bHead, dbLinkList *pLink, int position )
487 {
488 int count = 0;
489 dbNode *pNode = NULL, *pOld = NULL;
490
491 if ( NULL == pLink ) {
492 return;
493 }
494
495 if ( 1 > position ) {
496 return;
497 }
498
499 if ( 0 == bHead ) {
500 pNode = pLink;
501
502 } else {
503 pNode = pLink->pNext;
504 }
505
506 for ( count = 1; count < position - 1; pNode = pNode->pNext ) {
507 if ( NULL != pNode ) {
508 count++;
509
510 } else {
511 return;
512 }
513 }
514
515 pOld = pNode->pNext;
516 pNode->pNext = pOld->pNext;
517 pOld->pNext->pPrev = pNode;
518
519 free( pOld );
520 }
521
522 dbLinkList *reverseDbLinkList( char bHead, dbLinkList *pLink )
523 {
524 dbNode *pFirst = NULL, *pNode = NULL, *pNext = NULL;
525
526 if ( NULL == pLink ) {
527 return NULL;
528 }
529
530 if ( 0 == bHead ) {
531 pFirst = pLink;
532
533 } else {
534 pFirst = pLink->pNext;
535 }
536
537 pNode = pFirst->pNext;
538 pFirst->pPrev = pFirst->pNext;
539 pFirst->pNext = NULL;
540
541 while ( pNode ) {
542 pNext = pNode->pNext;
543 pNode->pPrev = pNode->pNext;
544 pNode->pNext = pFirst;
545 pFirst = pNode;
546 pNode = pNext;
547 }
548
549 if ( 0 == bHead ) {
550 pLink = pFirst;
551
552 } else {
553 pLink->pNext = pFirst;
554 pFirst->pPrev = pLink;
555 }
556
557 return pLink;
558 }
559
560 dbLinkList *sortDbLinkList( char bHead, dbLinkList *pLink )
561 {
562 dbNode *pFirst = NULL, *pNode = NULL, *pNext = NULL, *pMove = NULL;
563
564 if ( NULL == pLink ) {
565 return NULL;
566 }
567
568 if ( 0 == bHead ) {
569 pFirst = pLink;
570
571 } else {
572 pFirst = pLink->pNext;
573 }
574
575 pNode = pFirst->pNext;
576 pFirst->pNext = NULL;
577
578 while ( pNode ) {
579 pNext = pNode->pNext;
580 pMove = pFirst;
581 while ( pMove ) {
582 if ( ( pMove == pFirst ) && ( pNode->data < pMove->data ) ) {
583 pNode->pNext = pFirst;
584 pNode->pPrev = pFirst->pPrev;
585 pFirst->pPrev = pNode;
586 pFirst = pNode;
587 break;
588 }
589
590 if ( ( pMove->pNext ) && ( pMove->data <= pNode->data ) && ( pNode->data < pMove->pNext->data ) ) {
591 pNode->pNext = pMove->pNext;
592 pNode->pPrev = pMove;
593 pMove->pNext->pPrev = pNode;
594 pMove->pNext = pNode;
595 break;
596 }
597
598 if ( ( NULL == pMove->pNext ) && ( pMove->data <= pNode->data ) ) {
599 pNode->pNext = pMove->pNext;
600 pNode->pPrev = pMove;
601 pMove->pNext = pNode;
602 break;
603 }
604
605 pMove = pMove->pNext;
606 }
607 pNode = pNext;
608 }
609
610 if ( 0 == bHead ) {
611 pLink = pFirst;
612
613 } else {
614 pLink->pNext = pFirst;
615 }
616
617 return pLink;
618 }
619
620
621
622
623 /***********************************************************************
624 鏈棧
625 ***********************************************************************/
626 typedef struct sgStack {
627 sgNode *pTop;
628 } sgStack;
629
630 sgStack *pushNodeToSgStack( sgStack *pStack, dataType data )
631 {
632 sgNode *pNode = NULL, *pNew = NULL;
633
634 if ( NULL == pStack ) {
635 return NULL;
636 }
637
638 if ( NULL == ( pNew = ( sgNode* )malloc( sizeof( sgNode ) ) ) ) {
639 return NULL;
640 }
641
642 pNew->data = data;
643 pNew->pNext = pStack->pTop;
644 pStack->pTop = pNew;
645
646 return pStack;
647 }
648
649 dataType popNodeFromSgStack( sgStack *pStack )
650 {
651 sgNode *pNode = NULL;
652 dataType data = ( dataType )0;
653
654 if ( NULL == pStack ) {
655 return data;
656 }
657
658 if ( NULL == pStack->pTop ) {
659 return data;
660 }
661
662 pNode = pStack->pTop;
663 data = pNode->data;
664 pStack->pTop = pNode->pNext;
665
666 free( pNode );
667
668 return data;
669 }
670
671 sgStack *createSgStack( void )
672 {
673 sgStack *pStack = NULL;
674 dataType data = ( dataType )0;
675
676 if ( NULL == ( pStack = ( sgStack* )malloc( sizeof( sgStack ) ) ) ) {
677 return NULL;
678 }
679
680 pStack->pTop = NULL;
681
682 setbuf( stdin, NULL );
683
684 while ( scanf( "%d", &data ) ) {
685 pStack = pushNodeToSgStack( pStack, data );
686 }
687
688 return pStack;
689 }
690
691 void printSgStack( sgStack *pStack )
692 {
693 if ( NULL == pStack ) {
694 return;
695 }
696
697 while ( pStack->pTop ) {
698 printf( "%d ", popNodeFromSgStack( pStack ) );
699 }
700
701 printf( "\n" );
702
703 return;
704 }
705
706
707
708
709 /***********************************************************************
710 隊列
711 ***********************************************************************/
712 typedef struct sgQueue {
713 sgNode *pFront;
714 sgNode *pRear;
715 } sgQueue;
716
717 sgQueue *enSgQueue( sgQueue *pQueue, dataType data )
718 {
719 sgNode *pNode = NULL, *pNew = NULL;
720
721 if ( NULL == pQueue) {
722 return NULL;
723 }
724
725 if ( NULL == ( pNew = ( sgNode* )malloc( sizeof( sgNode ) ) ) ) {
726 return NULL;
727 }
728
729 pNew->data = data;
730 pNew->pNext = NULL;
731
732 if ( NULL != pQueue->pRear ) {
733 pQueue->pRear->pNext = pNew;
734 }
735
736 pQueue->pRear = pNew;
737
738 if ( NULL == pQueue->pFront ) {
739 pQueue->pFront = pNew;
740 }
741
742 return pQueue;
743 }
744
745 dataType deSgQueue( sgQueue *pQueue )
746 {
747 sgNode *pNode = NULL;
748 dataType data = ( dataType )0;
749
750 if ( NULL == pQueue ) {
751 return data;
752 }
753
754 if ( NULL == pQueue->pFront ) {
755 return data;
756 }
757
758 pNode = pQueue->pFront;
759 data = pNode->data;
760 pQueue->pFront = pNode->pNext;
761
762 if ( NULL == pQueue->pFront ) {
763 pQueue->pRear = NULL;
764 }
765
766 free( pNode );
767
768 return data;
769 }
770
771 sgQueue *createSgQueue( void )
772 {
773 sgQueue *pQueue = NULL;
774 dataType data = ( dataType )0;
775
776 if ( NULL == ( pQueue = ( sgQueue* )malloc( sizeof( sgQueue ) ) ) ) {
777 return NULL;
778 }
779
780 pQueue->pFront = NULL;
781 pQueue->pRear = NULL;
782
783 setbuf( stdin, NULL );
784
785 while ( scanf( "%d", &data ) ) {
786 pQueue = enSgQueue( pQueue, data );
787 }
788
789 return pQueue;
790 }
791
792 void printSgQueue( sgQueue *pQueue )
793 {
794 if ( NULL == pQueue ) {
795 return;
796 }
797
798 while ( pQueue->pFront ) {
799 printf( "%d ", deSgQueue( pQueue ) );
800 }
801
802 printf( "\n" );
803
804 return;
805 }
806
807
808
809
810 int main(int argc, char *argv[])
811 {
812 char bHead = 0;
813 sgLinkList *pSgLinkList = NULL;
814 dbLinkList *pDbLinkList = NULL;
815 sgNode *pSgNode = NULL;
816 dbNode *pDbNode = NULL;
817 sgStack *pStack = NULL;
818 sgQueue *pQueue = NULL;
819
820 // 單向鏈表
821 printf( "\nPlease input data one by one:\n" );
822 if ( NULL == ( pSgLinkList = createSgLinkList( bHead ) ) ) {
823 printf( "Create sgLinkList fail.\n" );
824 //return 0;
825 }
826
827 printf( "\nLink data:\n" );
828 printSgLinkList( bHead, pSgLinkList );
829 printf( "\nLink count: %d\n", getSgLinkListCount( bHead, pSgLinkList ) );
830
831 pSgNode = insertNodeIntoSgLinkList( bHead, pSgLinkList, 2, 2 );
832 printf( "\nLink data:\n" );
833 printSgLinkList( bHead, pSgLinkList );
834 printf( "\nLink count: %d\n", getSgLinkListCount( bHead, pSgLinkList ) );
835
836 deleteSgLinkListNode( bHead, pSgLinkList, 3 );
837 printf( "\nLink data:\n" );
838 printSgLinkList( bHead, pSgLinkList );
839 printf( "\nLink count: %d\n", getSgLinkListCount( bHead, pSgLinkList ) );
840
841 pSgLinkList = reverseSgLinkList( bHead, pSgLinkList );
842 printf( "\nLink data:\n" );
843 printSgLinkList( bHead, pSgLinkList );
844 printf( "\nLink count: %d\n", getSgLinkListCount( bHead, pSgLinkList ) );
845
846 pSgLinkList = sortSgLinkList( bHead, pSgLinkList );
847 printf( "\nLink data:\n" );
848 printSgLinkList( bHead, pSgLinkList );
849 printf( "\nLink count: %d\n", getSgLinkListCount( bHead, pSgLinkList ) );
850
851 if ( NULL == ( pSgNode = getBottomOfSgLinkList( bHead, pSgLinkList, 3 ) ) ) {
852 printf( "\nNo.%d Node data: NULL\n", 3 );
853
854 } else {
855 printf( "\nNo.%d Node data: %d\n", 3, pSgNode->data );
856 }
857
858
859
860
861 // 雙向鏈表
862 printf( "\nPlease input data one by one:\n" );
863 if ( NULL == ( pDbLinkList = createDbLinkList( bHead ) ) ) {
864 printf( "Create dbLinkList fail.\n" );
865 //return 0;
866 }
867
868 printf( "\nLink data:\n" );
869 printDbLinkList( bHead, pDbLinkList );
870 printDbLinkListBack( bHead, pDbLinkList );
871 printf( "\nLink count: %d\n", getDbLinkListCount( bHead, pDbLinkList ) );
872
873 pDbNode = insertNodeIntoDbLinkList( bHead, pDbLinkList, 2, 2 );
874 printf( "\nLink data:\n" );
875 printDbLinkList( bHead, pDbLinkList );
876 printDbLinkListBack( bHead, pDbLinkList );
877 printf( "\nLink count: %d\n", getDbLinkListCount( bHead, pDbLinkList ) );
878
879 deleteDbLinkListNode( bHead, pDbLinkList, 3 );
880 printf( "\nLink data:\n" );
881 printDbLinkList( bHead, pDbLinkList );
882 printDbLinkListBack( bHead, pDbLinkList );
883 printf( "\nLink count: %d\n", getDbLinkListCount( bHead, pDbLinkList ) );
884
885 pDbLinkList = reverseDbLinkList( bHead, pDbLinkList );
886 printf( "\nLink data:\n" );
887 printDbLinkList( bHead, pDbLinkList );
888 printDbLinkListBack( bHead, pDbLinkList );
889 printf( "\nLink count: %d\n", getDbLinkListCount( bHead, pDbLinkList ) );
890
891 pDbLinkList = sortDbLinkList( bHead, pDbLinkList );
892 printf( "\nLink data:\n" );
893 printDbLinkList( bHead, pDbLinkList );
894 printDbLinkListBack( bHead, pDbLinkList );
895 printf( "\nLink count: %d\n", getDbLinkListCount( bHead, pDbLinkList ) );
896
897
898
899
900 // 鏈棧
901 printf( "\nPlease input data one by one:\n" );
902 pStack = createSgStack();
903 printf( "\nStack data:\n" );
904 printSgStack( pStack );
905
906
907
908
909 // 隊列
910 printf( "\nPlease input data one by one:\n" );
911 pQueue = createSgQueue();
912 printf( "\nQueue data:\n" );
913 printSgQueue( pQueue );
914
915 return 0;
916 }
917