数据结构习题解析：循环与链表操作

"这份文档包含了数据结构（陈惠南主编第二版）的1-9章习题答案，是南邮本科教学使用的参考资料。" 在数据结构的学习中，理解和掌握算法的时间复杂度至关重要，因为它直接影响到程序的运行效率。文档中提到了几个关于时间复杂度的分析： 1. 绪论部分的题目涉及了对循环次数的计算和渐近时间复杂度的确定： - (1) 中的循环结构会执行 n-1 次，因此划线语句的执行次数为 n-1，渐近时间复杂度为 O(n)。 - (2) 中的循环会在 i 等于 2 的 n 次方时停止，因此划线语句执行次数为 log2n，渐近时间复杂度为 O(logn)。 - (3) 是三层嵌套循环，执行次数为 n(n+1)(n+2)/6，渐近时间复杂度为 O(n^3)。 - (4) 中的循环在 y 的平方大于等于 x 时停止，执行次数与 n 的平方根有关，渐近时间复杂度为 O(sqrt(n))。 2. 线性表部分主要讨论了两种类型的线性表——顺序表和单链表的操作及时间复杂度分析： - (2) 类 LinearList 的成员函数 `Invert()` 实现了顺序表的逆置，它通过交换表的一半元素实现，时间复杂度为 O(n/2) 或 O(n)，因为每个元素被交换一次。 - (5) 类 SingleList 的成员函数 `invert()` 实现了单链表的逆置，通过改变节点的链接方向完成，时间复杂度为 O(n)，每个节点只被访问和修改一次。 - (7) 类 SingleList 的成员函数 `DeleteAb(T a, T b)` 删除了值在 a 和 b 之间的所有节点。这个操作需要遍历链表，时间复杂度为 O(n)，其中 n 是链表的长度，因为可能需要检查链表中的所有节点。 这些题目和解答揭示了如何分析算法效率以及如何设计和优化数据结构操作。对于学习数据结构的学生来说，这些都是基础且重要的练习，有助于提高分析和解决问题的能力。