妙趣横生的算法(C语言实现)勘误表

### 妙趣横生的算法(C语言实现)勘误表知识点详解 #### 一、链表删除节点修正 **勘误内容**：在第14页上的第二段代码中，`if(q==list)`应改为`if(q==*list)`。 **详细解释**： 在C语言中，链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。此段代码实现了删除链表中指定节点的功能。原代码中有一处逻辑错误：`if(q==list)`的比较方式是错误的。这里的`list`是指向链表头部的指针，而`q`是指向待删除节点的指针。正确的比较方式应当是比较`q`指向的地址是否与链表头所指向的地址相同，即`if(q==*list)`。这样可以确保当待删除的节点是链表的第一个节点时，能够正确地更新链表头部指针。 **修正后代码**： ```c void delLink(LinkList *list, LinkList q) { LinkList r; if (q == *list) { /* 改为 if(q==*list) */ *list = q->next; free(q); } else { for (r = *list; r->next != q; r = r->next); /* 遍历链表, 找到 q 的前驱结点的指针 */ if (r->next != NULL) { r->next = q->next; free(q); } } } ``` #### 二、入队列操作修正 **勘误内容**：在第26页，入队列操作的代码第4行应改为`if(p==NULL)exit(0);`。 **详细解释**： 入队列操作通常涉及创建新的节点并将新节点添加到队列的末尾。在此处的代码中，原本的逻辑检查是针对头结点的创建情况，而不是新元素结点的创建情况。正确的做法是在创建新元素结点后，检查新元素结点是否创建成功。如果创建失败（即`p`为空），则应退出程序。 **修正后代码**： ```c if (p == NULL) exit(0); /* 创建元素结点失败 */ ``` #### 三、树的子树名称修正 **勘误内容**：第33页，1.62节上面一行，“这3棵树为根结点A的子树(TubTree)”将TubTree改为SubTree。 **详细解释**： 在描述树的结构时，经常会提及“子树”的概念。子树是指树中某个节点及其所有后代构成的树。这里的勘误将“TubTree”更正为“SubTree”，使得描述更加准确和清晰。 #### 四、动态规划问题修正 **勘误内容**： 1. 第85页，代码上面倒数第3行“循环执行上述操作，直到w[i]<=c，表明…”改为`w[i]>c`。 2. 第85页，代码中第一个注释：/*动态开辟一个临时数组，存放w[]的下标，如果t[i],t[j],i<j，则w[t[i]]≤w[t[j]]*/ **详细解释**： 此处涉及的是一个动态规划问题。在解决这类问题时，条件判断和数组索引的使用尤为重要。第一项勘误中，条件`w[i]<=c`应改为`w[i]>c`，以确保正确终止循环。第二项勘误中，注释中关于数组`t`的使用也进行了修正，以保证数组索引的正确性。 #### 五、寻找矩阵鞍点算法修正 **勘误内容**：第119页，寻找矩阵鞍点的算法描述，改为更清晰的描述。 **详细解释**： 鞍点是指在一个矩阵中，某一行的最大值同时也是这一列的最小值。此勘误提供了寻找鞍点的算法描述，包括逐行查找最大值、比较其他行中对应列的值等步骤，以确定是否存在鞍点。修正后的描述更加清晰明了，有助于理解算法的具体实现。 #### 六、寻找亲密数算法修正 **勘误内容**：第161页，寻找3000以内亲密数的算法描述，将n改为3000。 **详细解释**： 亲密数是指两个数，其中一个数的所有真因子之和等于另一个数，反之亦然。此处的勘误调整了算法中变量的取值范围，使其更符合实际应用。 #### 七、数字翻译算法修正 **勘误内容**：第163页，数字翻译算法描述，将第4行的10~999改为1~999。 **详细解释**： 此勘误是对一个数字翻译算法的描述进行了修正。数字翻译算法旨在将数字转换为英文形式。修正后的描述更准确地反映了处理范围，确保算法能正确处理1到999之间的数字。 以上是《妙趣横生的算法(C语言实现)》勘误表中的部分关键知识点及其详细解释。这些修正不仅改进了代码的正确性和效率，还提高了读者对算法的理解。