Programming abstractions in C阅读笔记：p181

笔记：p181"/>

Programming abstractions in C阅读笔记：p181

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

一、技术总结

1.linear search algorithm

2.lexicographic order(字典顺序)

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

/** 1.二分查找也应用了递归的思想。* 2.这里的代码只是demo*/
#include <stdio.h>
#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》：

2. 英语

(1)Etymology Dictionary：

(2) Cambridage Dictionary：

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