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.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