一直觉得数据结构是很好的东西，早就说要看，直到现在才静下心来。
下面就从简单的线性表开始，慢慢学习吧。
线性表综合运用：
约瑟夫循环：设有n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m的人出列，然后从出列的人下一个人重新开始报数，数到第m的人出列......如此反复直到所有的人全部出列为止。约瑟夫循环问题是：对于任意给定的n,s和m,求出按出列次序得到的n个人员的序列。
1.顺表表实现（数组）
1
//
Josephus-seqList.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include " stdafx.h "
5 #include < stdlib.h >
6 #include < malloc.h >
7 #define MAXNUM 100
8 #define FALSE 0
9 #define TRUE 1
10 #define SPECIAL 2147483647
11 typedef int DataType;
12
13 struct SeqList
14 {
15 DataType element[MAXNUM];
16 int n;
17 };
18
19 typedef struct SeqList * PSeqList;
20
21 PSeqList createNullList_seq( void )
22 {
23 PSeqList palist;
24 palist = (PSeqList)malloc( sizeof ( struct SeqList));
25 if (palist != NULL)
26 {
27 palist -> n = 0 ;
28 }
29 else
30 {
31 printf( " Out of space!!\n " );
32 }
33 return (palist);
34 }
35
36 int insert_seq(PSeqList palist, int p, DataType x)
37 {
38 int q;
39 if (palist -> n == MAXNUM)
40 {
41 printf( " Overflow!\n " );
42 return (FALSE);
43 }
44 if (p < 0 || p > palist -> n)
45 {
46 printf( " Not exist!\n " );
47 return (FALSE);
48 }
49 for (q = palist -> n - 1 ; q >= p; q -- )
50 {
51 palist -> element[q + 1 ] = palist -> element[q];
52 }
53 palist -> element[p] = x;
54 palist -> n += 1 ;
55 return (TRUE);
56 }
57
58 int delete_seq(PSeqList palist, int p)
59 {
60 int q;
61 if (p < 0 || p > palist -> n - 1 )
62 {
63 printf( " Not exist!\n " );
64 return (FALSE);
65 }
66 for (q = p; q < palist -> n - 1 ; q ++ )
67 {
68 palist -> element[q] = palist -> element[q + 1 ];
69 }
70 palist -> n = palist -> n - 1 ;
71 return (TRUE);
72 }
73
74 int locate_seq(PSeqList palist, DataType x)
75 {
76 int q;
77 for (q = 0 ; q < palist -> n; q ++ )
78 {
79 if (palist -> element[q] == x)
80 return (q);
81 }
82 return ( - 1 );
83 }
84
85 DataType retrieve_seq(PSeqList palist, int p)
86 {
87 if (p >= 0 && p < palist -> n)
88 {
89 return (palist -> element[p]);
90 }
91 printf( " Not exist.\n " );
92 return (SPECIAL);
93 }
94
95 int isNullList_seq(PSeqList palist)
96 {
97 return (palist -> n == 0 );
98 }
99
100 void josephus_seq(PSeqList palist, int s, int m)
101 {
102 int s1,i,w;
103 s1 = s - 1 ;
104 for (i = palist -> n; i > 0 ; i -- )
105 {
106 s1 = (s1 + m - 1 ) % i;
107 w = retrieve_seq(palist,s1);
108 printf( " Out element %d\n " , w);
109 delete_seq(palist,s1);
110 }
111 }
112 int _tmain( int argc, _TCHAR * argv[])
113 {
114 PSeqList jos_alist;
115 int i, k;
116 int n,s,m;
117 printf( " \nplease input the values(<100) of n = " );
118 scanf_s( " %d " , & n);
119 printf( " please input the value of s = " );
120 scanf_s( " %d " , & s);
121 printf( " please input the value of m = " );
122 scanf_s( " %d " , & m);
123 jos_alist = createNullList_seq();
124 for (i = 0 ; i < n; i ++ )
125 {
126 k = insert_seq(jos_alist, i, i + 1 );
127 if (k == FALSE)
128 exit( 1 );
129 }
130 josephus_seq(jos_alist,s,m);
131 free(jos_alist);
132 return 0 ;
133 }
134
2 //
3
4 #include " stdafx.h "
5 #include < stdlib.h >
6 #include < malloc.h >
7 #define MAXNUM 100
8 #define FALSE 0
9 #define TRUE 1
10 #define SPECIAL 2147483647
11 typedef int DataType;
12
13 struct SeqList
14 {
15 DataType element[MAXNUM];
16 int n;
17 };
18
19 typedef struct SeqList * PSeqList;
20
21 PSeqList createNullList_seq( void )
22 {
23 PSeqList palist;
24 palist = (PSeqList)malloc( sizeof ( struct SeqList));
25 if (palist != NULL)
26 {
27 palist -> n = 0 ;
28 }
29 else
30 {
31 printf( " Out of space!!\n " );
32 }
33 return (palist);
34 }
35
36 int insert_seq(PSeqList palist, int p, DataType x)
37 {
38 int q;
39 if (palist -> n == MAXNUM)
40 {
41 printf( " Overflow!\n " );
42 return (FALSE);
43 }
44 if (p < 0 || p > palist -> n)
45 {
46 printf( " Not exist!\n " );
47 return (FALSE);
48 }
49 for (q = palist -> n - 1 ; q >= p; q -- )
50 {
51 palist -> element[q + 1 ] = palist -> element[q];
52 }
53 palist -> element[p] = x;
54 palist -> n += 1 ;
55 return (TRUE);
56 }
57
58 int delete_seq(PSeqList palist, int p)
59 {
60 int q;
61 if (p < 0 || p > palist -> n - 1 )
62 {
63 printf( " Not exist!\n " );
64 return (FALSE);
65 }
66 for (q = p; q < palist -> n - 1 ; q ++ )
67 {
68 palist -> element[q] = palist -> element[q + 1 ];
69 }
70 palist -> n = palist -> n - 1 ;
71 return (TRUE);
72 }
73
74 int locate_seq(PSeqList palist, DataType x)
75 {
76 int q;
77 for (q = 0 ; q < palist -> n; q ++ )
78 {
79 if (palist -> element[q] == x)
80 return (q);
81 }
82 return ( - 1 );
83 }
84
85 DataType retrieve_seq(PSeqList palist, int p)
86 {
87 if (p >= 0 && p < palist -> n)
88 {
89 return (palist -> element[p]);
90 }
91 printf( " Not exist.\n " );
92 return (SPECIAL);
93 }
94
95 int isNullList_seq(PSeqList palist)
96 {
97 return (palist -> n == 0 );
98 }
99
100 void josephus_seq(PSeqList palist, int s, int m)
101 {
102 int s1,i,w;
103 s1 = s - 1 ;
104 for (i = palist -> n; i > 0 ; i -- )
105 {
106 s1 = (s1 + m - 1 ) % i;
107 w = retrieve_seq(palist,s1);
108 printf( " Out element %d\n " , w);
109 delete_seq(palist,s1);
110 }
111 }
112 int _tmain( int argc, _TCHAR * argv[])
113 {
114 PSeqList jos_alist;
115 int i, k;
116 int n,s,m;
117 printf( " \nplease input the values(<100) of n = " );
118 scanf_s( " %d " , & n);
119 printf( " please input the value of s = " );
120 scanf_s( " %d " , & s);
121 printf( " please input the value of m = " );
122 scanf_s( " %d " , & m);
123 jos_alist = createNullList_seq();
124 for (i = 0 ; i < n; i ++ )
125 {
126 k = insert_seq(jos_alist, i, i + 1 );
127 if (k == FALSE)
128 exit( 1 );
129 }
130 josephus_seq(jos_alist,s,m);
131 free(jos_alist);
132 return 0 ;
133 }
134
135
2.链表实现
1
//
Josephus_link.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include " stdafx.h "
5 #include < stdlib.h >
6 #include < malloc.h >
7 #define FALSE 0
8 #define TRUE 1
9 struct Node;
10 typedef struct Node * PNode;
11 typedef int DataType;
12 struct Node
13 {
14 DataType info;
15 PNode link;
16 };
17
18 typedef struct Node * LinkList;
19 typedef LinkList * PLinkList;
20
21 LinkList createNullList_link( void )
22 {
23 LinkList llist;
24 llist = (LinkList)malloc( sizeof ( struct Node));
25 if (llist != NULL)
26 llist -> link = NULL;
27 return (llist);
28 }
29
30 int insert_link(LinkList llist, int i, DataType x)
31 {
32 PNode p,q;
33 int j = 0 ;
34 p = llist;
35 while (p != NULL && j < i)
36 {
37 p = p -> link;
38 j ++ ;
39 }
40 if (j != i)
41 {
42 printf( " The value of i = %d is not reasonable.\n " , i);
43 return ( 0 );
44 }
45 q = (PNode)malloc( sizeof ( struct Node));
46 if (q == NULL)
47 {
48 printf( " Out of space!!!\n " );
49 return ( 0 );
50 }
51 else
52 {
53 q -> info = x;
54 q -> link = p -> link;
55 p -> link = q;
56 return ( 1 );
57 }
58 }
59
60 int delete_link(LinkList llist, DataType x)
61 {
62 PNode p, q;
63 p = llist;
64 while (p -> link != NULL && p -> link -> info != x)
65 p = p -> link;
66 if (p -> link == NULL)
67 {
68 printf( " Not exist!\n " );
69 return ( 0 );
70 }
71 else
72 {
73 q = p -> link;
74 p -> link = p -> link -> link;
75 free(q);
76 return ( 1 );
77 }
78 }
79
80 PNode locate_link(LinkList llist, DataType x)
81 {
82 PNode p;
83 if (llist == NULL)
84 return (NULL);
85 p = llist -> link;
86 while (p != NULL && p -> info != x)
87 p = p -> link;
88 return (p);
89 }
90
91 PNode find_link(LinkList llist, int i)
92 {
93 PNode p;
94 int j;
95 if (i < 0 )
96 {
97 printf( " The value of i = %d is not reasonable.\n " ,i);
98 return (NULL);
99 }
100 p = llist;
101 for (j = 0 ; j <= i; j ++ )
102 {
103 p = p -> link;
104 if (p == NULL)
105 return (NULL);
106 }
107 return (p);
108 }
109
110 int isNullList_link(LinkList llist)
111 {
112 if (llist == NULL)
113 return ( 1 );
114 else
115 return (llist -> link == NULL);
116 }
117
118 int init_clink(PLinkList pclist, int n)
119 {
120 PNode p, q;
121 int i;
122 q = (PNode)malloc( sizeof ( struct Node));
123 if (q == NULL)
124 return (FALSE);
125 * pclist = q;
126 q -> info = 1 ;
127 q -> link = q;
128 if (n == 1 )
129 return (TRUE);
130 for (i = 2 ; i < n + 1 ; i ++ )
131 {
132 p = (PNode)malloc( sizeof ( struct Node));
133 if (p == NULL)
134 return (FALSE);
135 p -> info = i;
136 p -> link = q -> link;
137 q -> link = p;
138 q = p;
139 }
140 return (TRUE);
141 }
142
143 void josephus_clink(PLinkList pclist, int s, int m)
144 {
145 PNode p, pre;
146 int i;
147 p = * pclist;
148 // 如果s是第一个节点，特殊处理，通过循环将pre指向最后一个节点
149 if (s == 1 )
150 {
151 pre = p;
152 p = p -> link;
153 while (p != * pclist)
154 {
155 pre = p;
156 p = p -> link;
157 }
158 }
159 else
160 {
161 for (i = 1 ; i < s; i ++ )
162 {
163 pre = p;
164 p = p -> link;
165 }
166 }
167 while (p != p -> link)
168 {
169 for (i = 1 ; i < m; i ++ )
170 {
171 pre = p;
172 p = p -> link;
173 }
174 printf( " Out element: %d \n " , p -> info);
175 // 删除第一个节点时特殊处理一下
176 if ( * pclist == p)
177 * pclist = p -> link;
178 pre -> link = p -> link;
179 free(p);
180 p = pre -> link;
181 }
182 printf( " Out element: %d \n " , p -> info);
183 * pclist = NULL;
184 free(p);
185
186
187 }
188 int _tmain( int argc, _TCHAR * argv[])
189 {
190 LinkList jos_clist;
191 int n,s,m;
192 printf( " \nplease input the value of n = " );
193 scanf_s( " %d " , & n);
194 printf( " please input the value of s = " );
195 scanf_s( " %d " , & s);
196 printf( " please input the value of m = " );
197 scanf_s( " %d " , & m);
198 if (init_clink( & jos_clist,n))
199 josephus_clink( & jos_clist, s,m);
200 else
201 printf( " Out of space!\n " );
202
203 return 0 ;
204 }
205
2 //
3
4 #include " stdafx.h "
5 #include < stdlib.h >
6 #include < malloc.h >
7 #define FALSE 0
8 #define TRUE 1
9 struct Node;
10 typedef struct Node * PNode;
11 typedef int DataType;
12 struct Node
13 {
14 DataType info;
15 PNode link;
16 };
17
18 typedef struct Node * LinkList;
19 typedef LinkList * PLinkList;
20
21 LinkList createNullList_link( void )
22 {
23 LinkList llist;
24 llist = (LinkList)malloc( sizeof ( struct Node));
25 if (llist != NULL)
26 llist -> link = NULL;
27 return (llist);
28 }
29
30 int insert_link(LinkList llist, int i, DataType x)
31 {
32 PNode p,q;
33 int j = 0 ;
34 p = llist;
35 while (p != NULL && j < i)
36 {
37 p = p -> link;
38 j ++ ;
39 }
40 if (j != i)
41 {
42 printf( " The value of i = %d is not reasonable.\n " , i);
43 return ( 0 );
44 }
45 q = (PNode)malloc( sizeof ( struct Node));
46 if (q == NULL)
47 {
48 printf( " Out of space!!!\n " );
49 return ( 0 );
50 }
51 else
52 {
53 q -> info = x;
54 q -> link = p -> link;
55 p -> link = q;
56 return ( 1 );
57 }
58 }
59
60 int delete_link(LinkList llist, DataType x)
61 {
62 PNode p, q;
63 p = llist;
64 while (p -> link != NULL && p -> link -> info != x)
65 p = p -> link;
66 if (p -> link == NULL)
67 {
68 printf( " Not exist!\n " );
69 return ( 0 );
70 }
71 else
72 {
73 q = p -> link;
74 p -> link = p -> link -> link;
75 free(q);
76 return ( 1 );
77 }
78 }
79
80 PNode locate_link(LinkList llist, DataType x)
81 {
82 PNode p;
83 if (llist == NULL)
84 return (NULL);
85 p = llist -> link;
86 while (p != NULL && p -> info != x)
87 p = p -> link;
88 return (p);
89 }
90
91 PNode find_link(LinkList llist, int i)
92 {
93 PNode p;
94 int j;
95 if (i < 0 )
96 {
97 printf( " The value of i = %d is not reasonable.\n " ,i);
98 return (NULL);
99 }
100 p = llist;
101 for (j = 0 ; j <= i; j ++ )
102 {
103 p = p -> link;
104 if (p == NULL)
105 return (NULL);
106 }
107 return (p);
108 }
109
110 int isNullList_link(LinkList llist)
111 {
112 if (llist == NULL)
113 return ( 1 );
114 else
115 return (llist -> link == NULL);
116 }
117
118 int init_clink(PLinkList pclist, int n)
119 {
120 PNode p, q;
121 int i;
122 q = (PNode)malloc( sizeof ( struct Node));
123 if (q == NULL)
124 return (FALSE);
125 * pclist = q;
126 q -> info = 1 ;
127 q -> link = q;
128 if (n == 1 )
129 return (TRUE);
130 for (i = 2 ; i < n + 1 ; i ++ )
131 {
132 p = (PNode)malloc( sizeof ( struct Node));
133 if (p == NULL)
134 return (FALSE);
135 p -> info = i;
136 p -> link = q -> link;
137 q -> link = p;
138 q = p;
139 }
140 return (TRUE);
141 }
142
143 void josephus_clink(PLinkList pclist, int s, int m)
144 {
145 PNode p, pre;
146 int i;
147 p = * pclist;
148 // 如果s是第一个节点，特殊处理，通过循环将pre指向最后一个节点
149 if (s == 1 )
150 {
151 pre = p;
152 p = p -> link;
153 while (p != * pclist)
154 {
155 pre = p;
156 p = p -> link;
157 }
158 }
159 else
160 {
161 for (i = 1 ; i < s; i ++ )
162 {
163 pre = p;
164 p = p -> link;
165 }
166 }
167 while (p != p -> link)
168 {
169 for (i = 1 ; i < m; i ++ )
170 {
171 pre = p;
172 p = p -> link;
173 }
174 printf( " Out element: %d \n " , p -> info);
175 // 删除第一个节点时特殊处理一下
176 if ( * pclist == p)
177 * pclist = p -> link;
178 pre -> link = p -> link;
179 free(p);
180 p = pre -> link;
181 }
182 printf( " Out element: %d \n " , p -> info);
183 * pclist = NULL;
184 free(p);
185
186
187 }
188 int _tmain( int argc, _TCHAR * argv[])
189 {
190 LinkList jos_clist;
191 int n,s,m;
192 printf( " \nplease input the value of n = " );
193 scanf_s( " %d " , & n);
194 printf( " please input the value of s = " );
195 scanf_s( " %d " , & s);
196 printf( " please input the value of m = " );
197 scanf_s( " %d " , & m);
198 if (init_clink( & jos_clist,n))
199 josephus_clink( & jos_clist, s,m);
200 else
201 printf( " Out of space!\n " );
202
203 return 0 ;
204 }
205
206
运行结果：
please input the value of n =8
please input the value of s =1
please input the value of m =4
Out element: 4
Out element: 8
Out element: 5
Out element: 2
Out element: 1
Out element: 3
Out element: 7
Out element: 6