avatar

目录
408数据结构(C/C+)

gcc -v: gcc version 5.5.0 20171010 (Ubuntu 5.5.0-12ubuntu1~16.04)

线性表(Liner List)

线性表基本操作

  • InitList(&L) 初始化线性表
  • Length(L) 获取表长度
  • LocateElem(L,e) 按值查找
  • GetElem(L,i) 按位查找
  • ListInsert(&L, i, e) 在第i个元素后插入元素e
  • ListDelete(&L, i, &e) 删除第i个元素,用e返回被删除的元素
  • PrintList(L) 按顺序输出表内所有元素值
  • DestroyList(&L) 销毁线性表,即释放表所占内存

易错题

  • 由100个字符串组成的序列可以称为一个线性表。
  • 邻接表是一种存储结构,非线性表;线性表是一种逻辑结构。

线性表的顺序表示(Sequence List)

  • 基于数组
  • 顺序表逻辑上相邻的元素物理上也相邻
  • 自动扩容,扩容策略始终为原来容量的2倍
  • 顺序表位序从0开始(教材上要求从1开始)
  • 插入T(n)= O(n)
  • 删除T(n)= O(n)
  • 顺序查找T(n)= O(n)
cpp
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
#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define InitSize 10 // 定义顺序表的初始长度

typedef struct StudentInfo {
char* name;
int age;
} stu;

typedef struct SequenceList {
stu* data;
int Length; // 有效长度
} sqlist;

void InitList(sqlist &l);
void InitList(sqlist &l, int size);
int Length(sqlist &l);
int LocateElem(sqlist l, stu e); // 查找第一个包含e中元素的项
stu GetElem(sqlist l, int i);
void ListInsert(sqlist &l, stu e);
void ListInsert(sqlist &l, int i, stu e);
bool ListDelete(sqlist &l, int i, stu &e); // 按序号删除元素
void PrintList(sqlist &l);
void DestroyList(sqlist &l);

void InitList(sqlist &l) {
InitList(l, InitSize);
}

void InitList(sqlist &l, int size) {
sqlist mysqlist;
mysqlist.Length = 0;
mysqlist.data = (stu *)malloc(sizeof(stu) * size);
l = mysqlist;
}

int Length(sqlist &l) {
return l.Length;
}

int LocateElem(sqlist l, stu e) {
int index = -1;
for (int i = 0; i < l.Length; i++)
{
if (!strcmp(l.data[i].name, e.name) || l.data[i].age == e.age) {
index = i;
break;
}
}
return index;
}

stu GetElem(sqlist l, int i) {
if (i >=0 && i <= l.Length) {
return l.data[i];
} else {
// 越界
return stu();
}
}

void ListInsert(sqlist &l, stu e) {
ListInsert(l, l.Length, e);
}

void ListInsert(sqlist &l, int i, stu e) {
int current_list_max_length = malloc_usable_size(l.data) / sizeof(l.data[0]);
if (l.Length >= current_list_max_length)
{
// 溢出,扩容策略为容量×2
sqlist new_sqlist;
new_sqlist.Length = 0;
new_sqlist.data = (stu *)malloc(sizeof(stu) * current_list_max_length * 2);
for (int j = 0; j < l.Length + 1; j++) {
if (j == i) {
new_sqlist.data[j].name = e.name;
new_sqlist.data[j].age = e.age;
} else {
new_sqlist.data[j].name = l.data[j < i ? j : j - 1].name;
new_sqlist.data[j].age = l.data[j < i ? j : j - 1].age;
}
new_sqlist.Length++;
}
l = new_sqlist;
}
else
{
for (int j = l.Length; j > i; j--) {
l.data[j].name = l.data[j-1].name;
l.data[j].age = l.data[j-1].age;
}
l.data[i].name = e.name;
l.data[i].age = e.age;
l.Length++;
}
}

bool ListDelete(sqlist &l, int i, stu &e) {
if (i < 0 || i > l.Length)
return false;
for (int j = i; j < l.Length - 2; j++) {
l.data[j].name = l.data[j + 1].name;
l.data[j].age = l.data[j + 1].age;
}
l.Length--;
return true;
}

void PrintList(sqlist &l) {
for (int i = 0; i < l.Length; i++) {
printf("[%02d] 姓名: %s, 年龄: %d\n", i+1, l.data[i].name, l.data[i].age);
}
printf("\n");
}

void DestroyList(sqlist &l) {
if (l.data == NULL)
return;
free(l.data);
}

void TestSequenceList() {
sqlist mySqlist;
InitList(mySqlist, 3);
printf("当前顺序表长度(有效)为: %d\n", mySqlist.Length);
// 插入以及动态扩容
stu e, e1;
e.name = (char*)"Mary";
e.age = 18;
e1.name = (char*)"Billy";
e1.age = 19;
for (int i = 0; i < 10; i++) {
ListInsert(mySqlist, e);
e.age++;
}
ListInsert(mySqlist, 3, e1);
// 打印
PrintList(mySqlist);
printf("当前顺序表长度(有效)为: %d\n\n", mySqlist.Length);
// 按位查找
stu mystu = GetElem(mySqlist, 3);
printf("4号学生姓名: %s, 年龄: %d\n\n", mystu.name, mystu.age);
// 按关键字查找
stu locateByAge;
locateByAge.age = 19;
int index = LocateElem(mySqlist, locateByAge);
printf("第一个年龄为19的人是: %s,序号为: %d\n\n", mySqlist.data[index].name, index);
// 删除
ListDelete(mySqlist, 3, e1);
PrintList(mySqlist);
printf("当前顺序表长度(有效)为: %d\n\n", mySqlist.Length);
DestroyList(mySqlist);
printf("\n");
}

int main() {
TestSequenceList();
return 0;
}

P19 综合应用题

cpp
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
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MaxSize 30 // 定义顺序表的MAX长度

typedef struct SequenceList {
int* data;
int Length; // 有效长度
} sqlist;

void InitList(sqlist &L);
int Length(sqlist &L);
int LocateElem(sqlist L, int e); // 查找第一个包含e中元素的项
int GetElem(sqlist L, int i);
void ListInsert(sqlist &L, int e);
void ListInsert(sqlist &L, int i, int e);
bool ListDelete(sqlist &L, int i, int &e); // 按序号删除元素
void PrintList(sqlist &L);
void DestroyList(sqlist &L);

void InitList(sqlist &L) {
sqlist mysqlist;
mysqlist.data = (int*)malloc(sizeof(int) * MaxSize);
mysqlist.Length = 0;
L = mysqlist;
}

int Length(sqlist &L) {
return L.Length;
}

int LocateElem(sqlist L, int e) {
int pos = -1;
for (int i = 0; i < L.Length; i++)
{
if (L.data[i] == e) {
pos = i;
break;
}
}
return pos;
}

int GetElem(sqlist L, int i) {
i--;
if (i < 0 || i > L.Length ) {
printf("下标越界\n");
return -1;
}
return L.data[i-1];
}

void ListInsert(sqlist &L, int e) {
if (L.Length >= MaxSize) {
printf("容量不足, %d插入失败\n", e);
return;
}
L.data[L.Length] = e;
L.Length++;
}

void ListInsert(sqlist &L, int i, int e) {
if (L.Length >= MaxSize) {
printf("容量不足, %d插入失败\n", e);
return;
}
for (int j = L.Length; j > i - 1; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.Length++;
}

bool ListDelete(sqlist &L, int i, int &e) {
if (i < 0 || i > L.Length ) {
printf("下标越界\n");
return false;
}
e = L.data[i-1];
for (int j = i; j < L.Length; j++)
{
L.data[j-1] = L.data[j];
}
L.Length--;
return true;
}

void PrintList(sqlist &L) {
printf("[ ");
for (int j = 0; j < L.Length; j++) {
printf("%d ", L.data[j]);
}
printf("]\n");
}

void DestroyList(sqlist &L) {
if (L.data != NULL) {
free(L.data);
}
}

bool Del_min_P19_1(sqlist &L, int &del_val) {
if (L.Length < 1) {
printf("顺序表为空!\n");
return false;
}
int min_index = 0;
for (int i = 1; i < L.Length; i++) {
if (L.data[i] < L.data[min_index]) {
min_index = i;
}
}
del_val = L.data[min_index];
L.data[min_index] = L.data[L.Length - 1];
L.Length--;
return true;
}

void Reverse_P19_2(sqlist &L) {
int temp;
for (int i = 0; i <= (L.Length - 1) / 2; i++) {
temp = L.data[L.Length - 1 - i];
L.data[L.Length - 1 - i] = L.data[i];
L.data[i] = temp;
}
}

void Del_value_equal_x_P19_3_method_1(sqlist &L, int x) {
int x_times = 0;
for (int i = 0; i < L.Length; i++)
{
if (L.data[i] != x) {
L.data[i - x_times] = L.data[i];
}
else
{
x_times++;
}
}
L.Length -= x_times;
}

void Del_value_equal_x_P19_3_method_2(sqlist &L, int x) {
int k = 0;
for (int i = 0; i < L.Length - 1; i++) {
if (L.data[i] != x) {
L.data[k] = L.data[i];
k++;
}
}
L.Length = k;
}

bool Del_between_s_t_with_sorted_list_P19_4(sqlist &L, int s, int t) {
if (s >= t) {
printf("s、t不合理\n");
return false;
}
if (L.Length < 1) {
printf("顺序表为空\n");
return false;
}
int i, j;
for (i = 0; i < L.Length && L.data[i] < s; i++);
for (j = 0; j < L.Length && L.data[j] <= t; j++);
for (; j < L.Length; i++, j++)
{
L.data[i] = L.data[j];
}
L.Length = i;
return true;
}

bool Del_between_s_t_P19_5_method1(sqlist &L, int s, int t) {
if (s >= t) {
printf("s、t不合理\n");
return false;
}
if (L.Length < 1) {
printf("顺序表为空\n");
return false;
}
// l为无序顺序表
int between_s_t_times = 0;
for (int i = 0; i < L.Length; i++) {
if (L.data[i] >= s && L.data[i] <= t) {
between_s_t_times++;
} else {
L.data[i - between_s_t_times] = L.data[i];
}
}
L.Length -= between_s_t_times;
}

bool Del_between_s_t_P19_5_method2(sqlist &L, int s, int t) {
if (s >= t) {
printf("s、t不合理\n");
return false;
}
if (L.Length < 1) {
printf("顺序表为空\n");
return false;
}
// l为无序顺序表
int k = 0;
for (int i = 0; i < L.Length; i++)
{
if (L.data[i] < s || L.data[i] > t) {
L.data[k] = L.data[i];
k++;
}
}
L.Length = k;
}

bool Del_same_P19_6(sqlist &L) {
if (L.Length < 1) {
return false;
}
int del_times = 0;
for (int i = 0; i < L.Length; i++)
{
if (L.data[i] == L.data[i+1]) {
del_times++;
} else {
L.data[i - del_times] = L.data[i];
}
}
L.Length -= del_times;
return true;
}

bool Combine_two_sorted_list_P19_7(sqlist L1, sqlist L2, sqlist &L) {
if (L1.Length + L2.Length > MaxSize)
{
return false;
}
int i = 0, j = 0, k = 0;
while(i < L1.Length && j < L2.Length)
{
if (L1.data[i] < L2.data[j]) {
// L.data[k++] = L1.data[i++] 等价于 L.data[k] = L1.data[i]; k++; i++;
L.data[k++] = L1.data[i++];
}
else
{
L.data[k++] = L2.data[j++];
}
}
while (i < L1.Length) {
L.data[k++] = L1.data[i++];
}
while (j < L2.Length) {
L.data[k++] = L2.data[j++];
}
L.Length = k;
return true;
}

void Exchange_P19_8(sqlist &L, int m, int n) {
class {
public:
void run(sqlist &L, int start, int end) {
if (L.Length < 1 || start < 0 || start >= end || end > L.Length) {
return;
}
int temp;
for (int i = 0; i < (end - start + 1) / 2; i++)
{
temp = L.data[start + i];
L.data[start + i] = L.data[end - i];
L.data[end - i] = temp;
}
}
} Reverse;
Reverse.run(L, 0, L.Length - 1);
Reverse.run(L, 0, n - 1);
Reverse.run(L, n, m + n - 1);
}

void Search_X_Exchange_Or_Insert_P20_9(sqlist &L, int x) {
if (L.Length < 1) {
return;
}
int low = 0;
int high = L.Length - 1;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (x == L.data[mid]) break;
if (x > L.data[mid])
{
low = mid + 1;
} else {
high = mid - 1;
}
}
if (L.data[mid] == x)
{
if (mid < L.Length - 1) {
int temp = L.data[mid + 1];
L.data[mid + 1] = L.data[mid];
L.data[mid] = temp;
}
}
else
{
for (int i = L.Length - 1; i >= low; i--) L.data[i + 1] = L.data[i];
L.data[low] = x;
L.Length++;
}
}

void P20_10(int arr[], int n, int p) {
class {
public:
int t;
void run(int arr[], int start, int end) {
for (int i = 0; i <= (end - start - 1) / 2; i++) {
t = arr[start + i];
arr[start + i] = arr[end - i];
arr[end - i] = t;
}
}
} Reverse;
Reverse.run(arr, 0, n - 1);
Reverse.run(arr, 0, n - p - 1);
Reverse.run(arr, n - p, n - 1);
}

// 非最优解,该方法T(n) = O(n)
int P20_11_MyAnswer(int A[], int B[], int combineAB[], int n) { // n为A或B的长度
int i = 0, j = 0, k = 0;
while (i < n && j < n) {
if (A[i] < B[j]) {
combineAB[k++] = A[i++];
} else {
combineAB[k++] = B[j++];
}
}
while (i < n) {
combineAB[k++] = A[i++];
}
while (j < n) {
combineAB[k++] = B[j++];
}
return combineAB[(2 * n - 1) / 2];
}

// 参考答案
int P20_11_Correct(int A[], int B[], int n) {
int start1 = 0, end1 = n-1;
int start2 = 0, end2 = n-1;
int mid1, mid2;
while (start1 <= end1 && start2 <= end2)
{
mid1 = (start1 + end1) / 2;
mid2 = (start2 + end2) / 2;
if (A[mid1] == B[mid2]) {
return A[mid1];
} else if (A[mid1] > B[mid2]) {
// 扔掉A中较大的一半 不包括a
// 扔掉B中较小的一半 包括b
// 对于有奇数个元素的数组,去除同等数量的元素时,恰好可以以mid为分界线
// 对于有偶数个元素的数组,若去除同等数量的元素时,其中一个数组要多去掉一个,这里我们始终让舍弃较小的一半者多舍弃一个,这样保证A、B舍弃的元素数相同
if ((start1 + end1) % 2 == 0) { // 元素个数为奇数
end1 = mid1;
start2 = mid2;
} else { // 元素个数为偶数,需要多舍掉B一个
end1 = mid1;
start2 = mid2 + 1;
}
}
else
{
// 扔掉A中较小的一半 包括a
// 扔掉B中较大的一半 不包括b
if ((start1 + end1) % 2 == 0) { // 元素个数为奇数
start1 = mid1;
end2 = mid2;
} else { // 元素个数为偶数,需要多舍掉B一个
start1 = mid1 + 1;
end2 = mid2;
}
}
}
return A[start1] < B[start2] ? A[start1] : B[start2];
}

// T(n)=O(n)最优,S(n)=O(n)非最优
void P20_12_MyAnswer(int arr[], int n) {
int counter[n] = {0};
int main_number = arr[0];
for (int i = 0; i < n; i++)
{
counter[arr[i]]++;
}
for (int i = 0; i < n; i++) {
if (counter[i] > counter[main_number]) {
main_number = i;
}
if (counter[main_number] > n / 2) {
break;
}
}
printf("主元素为: %d\n", (counter[main_number] > n / 2) ? main_number : -1);
}

// 参考答案, T(n) = O(1)
// 只有一个主元素,且主元素至少连续出现两次
void P20_12_Correct(int A[], int n) {
int i, c, count = 1;
c = A[i];
for (int i = 1; i < n; i++) {
if (A[i] != c) {
count--;
if (count < 1) {
c = A[i];
}
} else {
count++;
}
}
count = 0;
// 确定c是否为主元素
for (int i = 0; i < n; i++) {
if (A[i] == c) {
count++;
}
}
printf("主元素为: %d\n", (count > n / 2) ? c : -1);
}

// 非最优速度
// T(n)=O(n^2)
void P21_13_MyAnswer(int arr[], int n) {
int no_see_min = 0;
int temp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 1; i < n; i++) {
if (arr[i] > 0 && arr[i] - 1 != arr[i - 1]) {
no_see_min = arr[i] - 1;
break;
}
}
printf("未出现的最小正整数: %d\n", no_see_min == 0 ? arr[n - 1] + 1 : no_see_min);
}

// 参考答案
// 速度最优先: T(n)=O(n)
void P21_13_Correct(int arr[], int n) {
// counter[0]表示1出现的次数,ounter[n-1]表示n出现的次数,...
// 如果数组长度为n,并且数组元素集合不完全是1到n这n个数,那么表示1-n中至少有一个数,在数组中没有出现
int counter[n] = {0};
int no_see_min = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] >= 1 && arr[i] <= n) {
counter[arr[i] - 1]++;
}
}
for (int i = 0; i < n; i++) {
if (counter[i] == 0) {
no_see_min = i + 1;
break;
}
}
printf("未出现的最小正整数: %d\n", no_see_min == 0 ? arr[n - 1] + 1 : no_see_min);
}

int main() {
sqlist mysqlist;
InitList(mysqlist);
// [ 1 2 3 4 5 6 6 7 8 8 ] 该数组通用所有题目
for (int i = 1; i < 9; i++) {
if (i == 6 || i == 8) { // 6、8插入双次
ListInsert(mysqlist, i);
}
ListInsert(mysqlist, i);
}
PrintList(mysqlist);
// ================================
// int del_value;
// Del_min_P19_1(mysqlist, del_value);
// printf("删除了最小元素: %d\n", del_value);
// ================================
// Reverse_P19_2(mysqlist);
// ================================
// Del_value_equal_x_P19_3_method_1(mysqlist, 6);
// Del_value_equal_x_P19_3_method_2(mysqlist, 6);
// ================================
// Del_between_s_t_with_sorted_list_P19_4(mysqlist, 4, 6);
// ================================
// Del_between_s_t_P19_5_method1(mysqlist, 4, 6);
// Del_between_s_t_P19_5_method2(mysqlist, 4, 6);
// ================================
// Del_same_P19_6(mysqlist);
// ================================
// sqlist combine, combine1;
// InitList(combine);
// InitList(combine1);
// Combine_two_sorted_list_P19_7(mysqlist, mysqlist, combine);
// Combine_two_sorted_list_P19_7(mysqlist, combine, combine1);
// PrintList(combine1);
// ================================
// 设a1 a2 ... an = mysqlist
// 设b1 b2 ... bm = mysqlist
// 则 a1 a2 ... an b1 b2 ... bm = mysqlist mysqlist
// for (int i = 1; i < 9; i++) {
// if (i == 6 || i == 8) { // 6、8插入双次
// ListInsert(mysqlist, i);
// }
// ListInsert(mysqlist, i);
// }
// int m = mysqlist.Length / 2;
// int n = mysqlist.Length / 2;
// Exchange_P19_8(mysqlist, m, n);
// ================================
// Search_X_Exchange_Or_Insert_P20_9(mysqlist, 5);
// Search_X_Exchange_Or_Insert_P20_9(mysqlist, 9);
// ================================
// int n = 10;
// int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// P20_10(arr, n, 3);
// printf("[ ");
// for (int i = 0; i < n; i++) {
// printf("%d ", arr[i]);
// }
// printf("]\n");
// ================================
// int n = 10;
// int A[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// int B[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// int combineAB[n * 2];
// // int mid = P20_11_MyAnswer(A, B, combineAB, n);
// int mid = P20_11_Correct(A, B, n);
// printf("mid = %d\n", mid);
// ================================
// int n = 10;
// int test1[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// int test2[] = {6, 6, 3, 6, 5, 6, 6, 7, 8, 6};
// // P20_12_MyAnswer(test1, n);
// // P20_12_MyAnswer(test2, n);
// P20_12_Correct(test1, n);
// P20_12_Correct(test2, n);
// ================================
// int n = 10;
// int test1[] = {-1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// int test2[] = {-1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
// // P21_13_MyAnswer(test1, n);
// // P21_13_MyAnswer(test2, n);
// P21_13_Correct(test1, n);
// P21_13_Correct(test2, n);
// ================================
PrintList(mysqlist);

return 0;
}

单链表(头插法建表/默认插入位置)

双向链表(尾插法建表/默认插入位置)

循环单链表

循环双向链表

静态链表

查找

  • mid = (low+high)/2 向下取整,即强转int即可
  • T(n) = O(log2n)
cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <math.h>
#include "../tools.h"

/* 二分查找 */
int binary_search(int arr[], int len, int find) {
int low = 0, high = len - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (find == arr[mid]) {
return mid;
} else if (find > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

附录一

  • tools.h
cpp
tools.h
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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include<malloc.h>
#include <iso646.h>

#define TYPE_INT 0
#define TYPE_FLOAT 1
#define TYPE_DOUBLE 2

using namespace std;

/* ==================================== */
/* 预定义 */

template <typename T>
void printf(T *list);

template <typename T>
int count(T *list);

void* rand_list(int size, int type);

template <typename T>
void swap(T *a, T *b);

/* ==================================== */


/* 快速打印数组 */
template <typename T>
void printf(T *list)
{
cout << "[";
for (int i = 0; i < count(list); i++)
{
if (i > 0)
{
cout << ", ";
}
cout << *(list + i);
}
cout << "]" << endl;
}

/* 获取数组长度 */
template <typename T>
int count(T *p)
{
return malloc_usable_size(p) / sizeof(*p) - 1;
}

/** 随机数组
* @param int size : size of array
* @param int type : the array-item's type
* @param bool can_repeat : repeat number in the array
*/
void* rand_list(int len, int type, bool can_repeat)
{
srand((unsigned)time(NULL));
if (type == TYPE_INT && len < 10)
{
int *p = (int*)malloc(sizeof(int) * len);
int rand_number = 0;
int repeat_flag = 0;
int sgn = 0; // 随机符号,0正 1负
for (int i = 0; i < len; i++)
{
regenerate:
sgn = rand() % (2 - 0) + 0;
rand_number = rand() % (10 - 0) + 0;
rand_number = (sgn == 0 ? rand_number : rand_number * (-1));
if (can_repeat)
{
// 允许数字重复
*(p + i) = rand_number;
}
else
{
repeat_flag = 0;
for (int j = 0; j < i; j++)
{
if (*(p + j) == rand_number) {
repeat_flag = 1;
break;
}
}
if (repeat_flag) {
// 重复了
goto regenerate;
} else {
*(p + i) = rand_number;
}
}
}
return p;
}
else if (type == TYPE_FLOAT)
{
return NULL;
}
else if (type == TYPE_DOUBLE)
{
return NULL;
}
}

/* 交换参数值 */
template <typename T>
void swap(T *a, T *b) {
T temp = *a;
*a = *b;
*b = temp;
}
文章作者: Bill
文章链接: http://blog.webpro.ltd/2020/08/13/408/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Bill's blog

评论