算法与数据结构C语言习题参考答案69章VIP专享VIP免费

1 1. 现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key 在字典中重复出现时算法能找出第一个key 出现的元素下标（用*position 来保存）。保持算法时间代价为 O(log n)。 【答】 思路 一般的二分法检索算法只要找出关键码key 在字典中的一个下标。在比较的过程中，一旦发现相等，记录下当前下标mid 就符合要求。程序如下： 数据结构 字典采用 6.1.4 节中的顺序表示法。 typedef int KeyType; typedef int DataType; 二分法检索算法 int binarySearch(SeqDictionary * pdic, KeyType key, int * position) { int low, mid, high; low = 0; high = pdic->n - 1; while (low <= high){ mid = (low + high) / 2; if (pdic->element[mid].key = = key) { *position = mid; return TRUE; } else if (pdic->element[mid].key > key) high = mid - 1; else low = mid + 1; } *position = low; return FALSE; } 改写后的算法想要找出关键码key 在字典中第一次出现的下标。在比较中，如果遇到相等（key 与 pdic->element[mid].key 相等），则需要分情形讨论。 （1）如果当前下标mid 等于 0，或者 key 与 pdic->element[mid-1].key 不等，那么 mid一定是 key 第一次出现的下标，返回 mid 即可。 （2）如果情形（1）不成立，那么 mid 一定大于等于 key 第一次出现的下标，需要在low和 mid-1 之间继续进行搜索，找出key 第一次出现的下标。 下面算法中，加粗的部分是对原算法的修改。 修改后的二分法检索算法 int binarySearch1(SeqDictionary * pdic, KeyType key, int * position) { /*算法结束后，*position 存放 key 第一次出现的下标*/ int low, mid, high; low = 0; high = pdic->n - 1; 2 while (low <= high){ mid = (low + high) / 2; if (pdic->element[mid].key = = key) { if (mid = = 0 || key != pdic->element[mid - 1].key) { *position = mid; return TRUE; } /*此时mid 就是key 在字典中第一次出现的下标*/ else high = mid - 1; /*在左半段继续搜索*/ } else if (pdic->element[mid].key > key) high = mid - 1; else low = mid + 1; } *position = low; return FALSE; } 代价分析 该算法的时间...