数据结构系列28 - 顺序查找 - C语言实现

  • 常规查找
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
/*************************************************************************
* File Name: SequenceSearch.c
* Author: TyrantLucifer
* E-mail: TyrantLucifer@gmail.com
* Blog: https://tyrantlucifer.com
* Created Time: Wed 03 Nov 2021 11:54:58 PM CST
************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct List {
int* data;
int length;
int num;
}List;

List* initList(int length) {
List* list = (List*)malloc(sizeof(List));
list -> length = length;
list -> data = (int*)malloc(sizeof(int) * length);
list -> num = 0;
return list;
}

void listAdd(List* list, int data) {
list -> data[list -> num] = data;
list -> num = (list -> num) + 1;
}

void printList(List* list) {
for (int i = 0; i < list -> num; i++) {
printf("%d -> ", list -> data[i]);
}
printf("NULL\n");
}

int search(List* list, int key) {
for (int i = 0 ; i < list -> num; i++) {
if (list -> data[i] == key)
return i;
}
return -1;
}

int main()
{
List* list = initList(5);
listAdd(list, 1);
listAdd(list, 2);
listAdd(list, 3);
listAdd(list, 4);
printList(list);
printf("%d\n", search(list, 5));
return 0;
}
  • 哨兵
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
/*************************************************************************
* File Name: SequenceSearch.c
* Author: TyrantLucifer
* E-mail: TyrantLucifer@gmail.com
* Blog: https://tyrantlucifer.com
* Created Time: Wed 03 Nov 2021 11:54:58 PM CST
************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct List {
int* data;
int length;
int num;
}List;

List* initList(int length) {
List* list = (List*)malloc(sizeof(List));
list -> length = length;
list -> data = (int*)malloc(sizeof(int) * length);
list -> num = 1;
return list;
}

void listAdd(List* list, int data) {
list -> data[list -> num] = data;
list -> num = (list -> num) + 1;
}

void printList(List* list) {
for (int i = 0; i < list -> num; i++) {
printf("%d -> ", list -> data[i]);
}
printf("NULL\n");
}

int search(List* list, int key) {
int i;
list -> data[0] = key;
for (i = (list -> num) - 1; list -> data[i] != key; i--) {
printf("i = %d\n", i);
}
return i;
}

int main()
{
List* list = initList(5);
listAdd(list, 4);
listAdd(list, 5);
listAdd(list, 6);
listAdd(list, 7);
printList(list);
printf("%d\n", search(list, 8));
return 0;
}