-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.m
320 lines (243 loc) · 9.95 KB
/
main.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
//
// main.m
// List
//
// Created by Vincent_D on 15/10/21.
// Copyright © 2015年 Vincent_D. All rights reserved.
//
#import <Foundation/Foundation.h>
#import "ViDataStructures.h"
void insertSort(int * arr, int length);
void selectSort(int * arr, int length);
void quickSort(int * arr, int length);
int main(int argc, const char * argv[]) {
@autoreleasepool {
//测试代码
//链表 List
printf("一、链表 List\n");
List *list = [[List alloc] init];//构建空链表
[list insertObjectAtFirstIndex:@"firstObject"];//插入头结点
[list insertObjectAtLastIndex:@"lastObject"];//插入尾结点
[list insertObject:@"middleObject" inIndex:2];//按目录插入结点
printf("\n第一次构造测试及插入测试\n");
NSLog(@"%@",list);
[list removeObjectInIndex:2];
printf("\n移除结点测试\n");
NSLog(@"%@",list);
NSArray *arr = @[@3,@9,@0,@7,@627,@67];
list = nil;
list = [[List alloc] initWithArray:arr];//用数组构建链表
// arr = nil;
NSLog(@"length is %ld",list.length); //查询长度,由于头结点存在,长度为自添加长度+1
printf("\n第二次构造测试\n");
NSLog(@"%@",list);
[list mergeSort];
printf("\n数字归并排序测试\n");
NSLog(@"%@",list);
list = [[List alloc] initWithArray:arr];
[list sortWithComparisonBlock:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] < [obj2 integerValue]) {
return NSOrderedAscending;
}else{
return NSOrderedDescending;
}
}];// 排序器排序
printf("\n排序器排序测试\n");
NSLog(@"%@",list);
printf("\n遍历测试(数字均为原值+1)\n");
[list travelList:^(ListNode *currentNode, NSInteger index) {
printf("%ld\n",[(NSNumber*)currentNode.Object integerValue] + 1);
}];
//栈 stack
printf("\n\n栈 stack\n");
Stack *stack = [[Stack alloc] init]; //构造空栈
[stack push:@"one"];
[stack push:@"two"];
[stack push:@"three"]; //元素进栈
printf("\nlength is %ld\n",stack.length);
NSLog(@"%@",[stack top]); //栈顶元素
if ([stack isEmpty]) { //测试空栈验证方法
NSLog(@"此时为空栈");
}else{
NSLog(@"此时非空栈");
}
NSString *str;
while ((str = [stack pop])) { //元素出栈
NSLog(@"%@",str);
}
str = nil;
[stack clearStack]; //清栈
if ([stack isEmpty]) { //测试空栈验证方法
NSLog(@"此时为空栈");
}else{
NSLog(@"此时非空栈");
}
stack = [[Stack alloc] initWithArray:arr];
while (([stack top])) { //元素出栈
NSLog(@"%@",[stack pop]);
}
//队列 queue
printf("\n\n三、队列 queue\n");
Queue *queue = [[Queue alloc] initWithMaxLength:5];//构造一个最大长度为5的队列
[queue enQueue:@"0"]; //入队列
[queue enQueue:@"1"];
[queue enQueue:@"2"];
[queue enQueue:@"3"];
[queue enQueue:@"4"];
[queue enQueue:@"5"];
[queue enQueue:@"6"];
[queue enQueue:@"7"];
[queue travelQueue:^(id object) { //遍历队列元素
NSLog(@"%@",object);
}];
printf("\n溢出区\n");
for (NSString *str in queue.overflows){ //溢出区元素
NSLog(str);
}
printf("\n出队列\n");
while (queue.Head) { //出队列
NSLog(@"%@",[queue deQueue]);
}
//二叉树 binaryTree
printf("\n\n三、二叉树 binaryTree\n");
NSArray *arr1 = @[@"A",@"B",@"C",@"D",@"E",@"F",@"G"];
NSArray *arr2 = @[@"C",@"B",@"E",@"D",@"A",@"F",@"G"];
BinaryTree *tree = [BinaryTree treeWithPreSequence:arr1 andInSequence:arr2]; //用先序序列与中序序列构造二叉树
printf("\n先序遍历二叉树\n");
[tree preOrderTraverseWithBlock:^(BinaryTreeNode *currentNode) {
NSLog(@"%@",currentNode.value);
}];
printf("\n中序遍历二叉树\n");
[tree inOrderTraverseWithBlock:^(BinaryTreeNode *currentNode) {
NSLog(@"%@",currentNode.value);
}];
printf("\n后序遍历二叉树\n");
[tree postOrderTraverseWithBlock:^(BinaryTreeNode *currentNode) {
NSLog(@"%@",currentNode.value);
}];
tree = nil;
//邻接表图 AdGraph
printf("\n\n邻接表图 AdGraph\n");
NSArray *VNodeArray = [NSArray arrayWithObjects:@1,@2,@3,@4,@5,@6,@7,@8,nil];
////将结点对象数据打包成数组
NSArray *parameter = [NSArray arrayWithObjects:@"head",@"tail",@"info", nil];
NSArray *date1 = [NSArray arrayWithObjects:@0,@1,[NSNull null], nil];
NSArray *date2 = [NSArray arrayWithObjects:@0,@2,[NSNull null], nil];
NSArray *date3 = [NSArray arrayWithObjects:@1,@3,[NSNull null], nil];
NSArray *date4 = [NSArray arrayWithObjects:@1,@4,[NSNull null], nil];
NSArray *date5 = [NSArray arrayWithObjects:@3,@7,[NSNull null], nil];
NSArray *date6 = [NSArray arrayWithObjects:@4,@7,[NSNull null], nil];
NSArray *date7 = [NSArray arrayWithObjects:@2,@5,[NSNull null], nil];
NSArray *date8 = [NSArray arrayWithObjects:@2,@6,[NSNull null], nil];
NSArray *date9 = [NSArray arrayWithObjects:@5,@6,[NSNull null], nil];
NSDictionary *dic1= [NSDictionary dictionaryWithObjects:date1 forKeys:parameter];
NSDictionary *dic2= [NSDictionary dictionaryWithObjects:date2 forKeys:parameter];
NSDictionary *dic3= [NSDictionary dictionaryWithObjects:date3 forKeys:parameter];
NSDictionary *dic4= [NSDictionary dictionaryWithObjects:date4 forKeys:parameter];
NSDictionary *dic5= [NSDictionary dictionaryWithObjects:date5 forKeys:parameter];
NSDictionary *dic6= [NSDictionary dictionaryWithObjects:date6 forKeys:parameter];
NSDictionary *dic7= [NSDictionary dictionaryWithObjects:date7 forKeys:parameter];
NSDictionary *dic8= [NSDictionary dictionaryWithObjects:date8 forKeys:parameter];
NSDictionary *dic9= [NSDictionary dictionaryWithObjects:date9 forKeys:parameter];
////准备弧数据
NSArray *arcArray = [NSArray arrayWithObjects:dic1,dic2,dic3,dic4,dic5,dic6,dic7,dic8,dic9,nil];
///打包成数组
AdGraph *graph = [AdGraph creatAdGraphWithNodeValue:VNodeArray andArc:arcArray];
///构造图
///
printf("\n\n广度优先遍历\n");
[graph BFSWithBlock:^(AdGraphVNode *currentNode) {
NSLog(@"%@",currentNode.value);
}];
printf("\n\n深度优先遍历\n");
[graph DFSWithBlock:^(AdGraphVNode *currentNode) {
NSLog(@"%@",currentNode.value);
}];
//由于十字链表图方法名跟效果与邻接表图十分相近,固不再作测试演示
}
return 0;
}
void insertSort(int *arr,int length)
{
for (int i = 1; i<length; i++) {
for (int j = i - 1; j >= 0 ; j--) {
if (arr[i] <= arr[j] &&( (j == 0) || (arr[i] > arr[j-1])) ) {
int temp = arr[i];
for (int k = i - 1; k >= j; k--) {
arr[k+1]= arr[k];
}
arr[j] = temp;
}
}
printf("\n第%d次\n",i);
for (int index = 0;index < 10 ; index++) {
// arr[i] = rand()%20;
NSLog(@"%d",arr[index]);
}
printf("\n");
}
}
void selectSort(int *arr, int length)
{
for (int i = 0; i < length; i++) {
int min = arr[i];
int minIndex = i;
for (int j = i; j < length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = min;
arr[minIndex] = temp;
}
}
}
void shellSort(int* arr, int length)
{
for (int gap = length/2; gap; gap /= 2) {
for (int i = 1; i<length; i += gap) {
for (int j = i - gap; j >= 0 ; j -= gap) {
if (arr[i] <= arr[j] &&((j == 0) || (arr[i] > arr[j-gap]) )) {
int temp = arr[i];
for (int k = i - gap; k >= j; k -= gap) {
arr[k+gap]= arr[k];
}
arr[j] = temp;
}
}
}
}
}
void quickSorting(int* arr,int head,int tail)
{
if (head > tail) {
return;
}
int base = arr[head];
int i = head;
int j = tail;
while (!(i == j)) {
while ((arr[j] >= base) && (i < j)) {
j--;
}
while ((arr[i] <= base) && (i < j)) {
i++;
}
if (i < j) {
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
arr[head] = arr[i];
arr[i] = base;
quickSorting(arr, head,i - 1);
quickSorting(arr, i + 1, tail);
}
void quickSort(int* arr,int length)
{
quickSorting(arr, 0, length - 1);
}