数据结构系列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;
}