Programming abstractions in C阅读笔记：p181-p183

《Programming Abstractions In C》学习第61天，p181-p183总结。

一、技术总结

1.linear search algorithm

2.lexicographic order(字典顺序)

3.binary search algorithm(二分查找算法)

/*
 * 1.二分查找也应用了递归的思想。
 * 2.这里的代码只是demo
 */
#include 
#include "strlib.h"

int FindStringInSortedArray(string key, string array[], int n);

static int BinarySearch(string key, string array[], int low, int high);

/*
 * Function: FindStringInSortedArray
 * Usage: index = FindStringInSortedArray(key, array, n);
 * ------------------------------------------------------
 * This function searches the array looking for the specified
 * key. The argument n specifies the effective size of the
 * array, which must be sorted according to the lexicographic
 * order imposed by StringCompare. If the key is found, the
 * function returns the index in the array at which that key
 * appears. (If the key appears more that once in the array,
 * any of the matching indices may be return). If the key
 * does not exist in the array, the function returns -1. In
 * this implementation, FindStringInSortedArray is simply a
 * wrapper; all the work is done by the recursive function
 * BinarySearch.
 */
int FindStringInSortedArray(string key, string array[], int n) {
    return BinarySearch(key, array, 0, n - 1);
}

/*
 * Function: BinarySearch
 * Usage: index = BinarySearch(key, array, low, high);
 * ---------------------------------------------------
 * This function does the work for FindStringInSortedArray.
 * The only difference is that BinarySearch takes both the
 * upper and lower limit of the search.
 */
static int BinarySearch(string key, string array[], int low, int high) {
    int mid, cmp;

    if (low > high) {
        return -1;
    }
    mid = (low + high) / 2;
    cmp = StringCompare(key, array[mid]);
    if (cmp == 0) {
        return mid;
    }
    if (cmp < 0) {
        return BinarySearch(key, array, low, mid - 1);
    } else {
        return BinarySearch(key, array, mid + 1, high);
    }
}

int main() {
    int index;
    char *arr[] = {"Programming Abstractions in C", "Hello World", "C"};
    index = FindStringInSortedArray("C", arr, 3);
    printf("index is: %d", index);
    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
57
58
59
60
61
62
63
64
65

二、英语总结

1.lecicographic是什么意思？

答：

(1)lexicographic < lexicography: adj. of or relating lexicography(字典的)。

(2)lexicography: lexico-(“wordbook”，字典) + -graphy(“to write”)

2.adhere是什么意思？

答：p182，Although most of the recursive functions you encounter are likely to adhere to this style, the definition of the recursion is actually somewhat broader。ad-(“to”) + haerere(“to stick”)。vi. to stick firmely(附着，遵循)。后面常接介词to。

三、参考资料

1. 编程

(1)Eric S.Roberts，《Programming Abstractions in C》：https://book.douban.com/subject/2003414

2. 英语

(1)Etymology Dictionary：https://www.etymonline.com

(2) Cambridage Dictionary：https://dictionary.cambridge.org

欢迎搜索及关注：编程人(a_codists)