算法与数据结构C语言习题参考答案6-9章.docx

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;}elseif (pdic->element[mid].key > key)high = mid - 1;elselow = 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;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 在字典中第一次出现的下标 */elsehigh = mid - 1;/*在左半段继续搜索*/}elseif (pdic->element[mid].key > key)high = mid - 1;elselow = mid + 1;}*position = low;return FALSE;}代价分析该算法的时间复杂度为 O(log n)。

2. 试编写一算法求出指定结点在给定的二叉排序树中所在的层数答】数据结构采用 7.1.3 节中字典的二叉排序树表示算法int search_layer(PBinTree pbtree, PBinTreeNode pnode) {/* 返回二叉排序树*pbtree 中结点 *pnode 所在层数，要求所给结点在树中 */int layer = 0;PBinTreeNode p = *pbtree;while (p != NULL) {if (p->key = = pnode->key)return layer;/* 查找结点成功，返回层数*/if (p->key > pnode->key) {p = p->llink;/* 进入左子树继续查找*/layer++;}else {p = p->rlink;/* 进入右子树继续查找*/layer++;}}return -1;/* 查找结点失败*/}代价分析假设二叉排序树有n个结点，高度是h(log2n<=h<=n),算法执行的时间代价最坏为0(h)注意 根结点为零层3. 试编写一算法在给定的二叉排序树上找出任意两个不同结点最近的公共祖先(若在两结点 A ， B 中， A 是 B 的祖先，则认为A， B 最近的公共祖先就是A)。

数据结构同上题算法int FindLowestCommonAncestor(pBinSearchNode root, int value1, int value2) {pBinSearchNode curnode = root;while(1) {if (curnode->key>value1&&curnode->key>value2)curnode = curnode->llink;else if(curnode->keykeyrlink;else return curnode->key;}}4. 设计一个有效的算法，在1000 个无序的元素中，挑选出其中前5 个最大的元素答】数据结构typedef int KeyType;typedef int DataType;typedef struct{ KeyType key; /* 排序码字段*/DataType info;/* 记录的其它字段*/}RecordNode;typedef struct{ int n;/* n 为文件中的记录个数*/RecordNode *record;}SortObject;思路这里不需要整体排序，故选择一种能较快得出最终排序段的前一部分的算法改造即可，如直接选择排序， 起泡排序， 堆排序都能最先得出前5 个最大元素。

综合考虑算法的时间代价，选择直接选择排序算法改造即可算法函数返回一个数组，数组中存着挑出的元素，为动态分配的RecordNode* Outmax(SortObject *pvector, int out) {int i, j, k;RecordNode *outpart;RecordNode temp;if(out>pvector->n) {printf("the given value is wrong!");return NULL;}outpart=(RecordNode*)malloc(out*sizeof(RecordNode));if(outpart==NULL) {printf("No space!\n");return NULL;}for(i=0;in;j++) if(pvector->record[j].key>pvector->record[k].key) k=j;if(k!=i) {temp=pvector->record[i];pvector->record[i]=pvector->record[k];pvector->record[k]=temp;}outpart[i]=pvector->record[i];} return outpart;}代价分析O(n*m) (设从n 个元素中选出 m 个最大元素)。

5. 写一个算法来判断对给定有向图中的指定顶点是否至少存在一条有向边指向它答】图有三种表示方法：出边表(邻接表的一种) ，入边表(邻接表的一种)和邻接矩阵相应的有三种算法设n 为顶点数， m 为边数对于出边表，顺次搜索一遍边即可，时间代价为 O(m)对于入边表，判断指定顶点的边表头指针是否非空即可，时间代价为 O(1)对于邻接矩阵， 搜索矩阵中指定顶点对应的列， 判断其中是否有非0 元即可， 时间代价为 O(n)以出边表为例，给出一个算法如下数据结构采用 9.1.3 节中有向图的邻接表(出边表)表示法算法int is_end(GraphList g, int k) {/* 判断图 g 中是否有边指向第k 个结点 (0<=k<=*/EdgeList p;int i;for ( i = 0;i < ;i++) {p = [i].edgelist;while (p != NULL) {if (p->endvex = = i) return 1;p = p->nextedge;}}return 0;}代价分析该算法的时间复杂度为 O(m)6. 设计一个算法，确定(无权)图中每一对结点之间的可达关系。

答】数据结构采用图的邻接矩阵表示法define MAXVEX 100typedef char * VexType;typedef int AdjType;typedef struct{/* 顶点信息 *//* 边信息 *//* 图的顶点个数 */VexType vexs[MAXVEX];AdjType arcs[MAXVEX][MAXVEX];int n;}GraphMatrix;思路这里介绍 Warshall 算法，该算法解决了(无权)图的可达性问题算法用到了一个矩阵a( a 作为算法的参数之一) 开始时，对矩阵a 中元素赋值，使a与图的邻接矩阵相等 这样， 矩阵 a 记录的就是所有直接的边连接 算法的核心部分是一个 三重循环其中外重循环的循环次数为 n ，每次循环更新a 中的元素循环一次后， a 中记录的就是所有直接连接或者只经由结点0而形成的通路的情况循环 k (1n; i++)/*对矩阵a中元素赋值，使a与图的邻接矩阵相等*/for ( j = 0; j < pgraph->n; j++)a[i][j] = pgraph->arcs[i][j];for ( m = 0; m < pgraph->n; m++)/*算法的核心部分，一个三重循环 */for ( i = 0; i < pgraph->n; i++)for (j = 0; j < pgraph->n; j++)a[i][j] = a皿]II (a[i][m] && a[m][j]);}代价分析算法的核心部分是一个三重循环，每重的循环次数为n,因此该算法的时间代价为O(n3)o调试结果该示例程序计算下图的可达性：运。