数据结构C语言版习题详细答案-严蔚敏

### 数据结构C语言版习题详细答案-严蔚敏 #### 第1章 绪论 ##### 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 - **数据**：在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 - **数据元素**：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 - **数据对象**：性质相同的数据元素的集合，它是数据的一个子集。 - **数据结构**：指相互之间存在一种或多种特定关系的数据元素的集合。 - **存储结构**：是数据结构在计算机中的表示形式，包括顺序存储、链式存储等。 - **数据类型**：是一个值的集合和定义在这个值集上的一组操作的总称，如整型、浮点型等。 - **抽象数据类型**：是指一个数学模型以及定义在该模型上的一组操作，它是对一般数据类型的扩展。 ##### 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 - **抽象数据类型**包含了更广泛的概念，并且比一般数据类型更加抽象。一般数据类型是由具体的编程语言内部定义的，比如`int`、`float`等，这些是预定义的数据类型，直接供程序员使用。而抽象数据类型是由程序员自定义的，不仅定义了数据的结构，还定义了可以在这些数据上执行的操作。 - 抽象数据类型的定义通常只关注数据的逻辑结构和操作说明，而不涉及具体的实现细节，这使得抽象数据类型具有更高的抽象层次，更容易为其他用户提供良好的使用接口。 ##### 1.3 设有数据结构(D,R)，其中 \[ D=\{d_1,d_2,d_3,d_4\}, R=\{r\}, r=\{(d_1,d_2),(d_2,d_3),(d_3,d_4)\} \] 试按图论中图的画法惯例画出其逻辑结构图。 根据给定的数据结构，可以绘制一个无向图来表示数据元素之间的关系： ``` d1 -- d2 -- d3 -- d4 ``` 在这个图中，每个顶点代表一个数据元素，每条边代表数据元素之间的关系。 ##### 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 **抽象数据类型复数 (ADT Complex)**: - **数据对象**: `D={r,i | r,i为实数}` - **数据关系**: `R={<r,i>}` - **基本操作**: - `InitComplex(&C,re,im)`：构造一个复数C，其实部和虚部分别为re和im。 - `DestroyComplex(&C)`：销毁复数C。 - `Get(C,k,&e)`：用e返回复数C的第k元的值。 - `Put(&C,k,e)`：改变复数C的第k元的值为e。 - `IsAscending(C)`：如果复数C的两个元素按升序排列，则返回1，否则返回0。 - `IsDescending(C)`：如果复数C的两个元素按降序排列，则返回1，否则返回0。 - `Max(C,&e)`：用e返回复数C的两个元素中值较大的一个。 - `Min(C,&e)`：用e返回复数C的两个元素中值较小的一个。 **抽象数据类型有理数 (ADT RationalNumber)**: - **数据对象**: `D={s,m | s,m为自然数，且m不为0}` - **数据关系**: `R={<s,m>}` - **基本操作**: - `InitRationalNumber(&R,s,m)`：构造一个有理数R，其分子和分母分别为s和m。 - `DestroyRationalNumber(&R)`：销毁有理数R。 - `Get(R,k,&e)`：用e返回有理数R的第k元的值。 - `Put(&R,k,e)`：改变有理数R的第k元的值为e。 - `IsAscending(R)`：若有理数R的两个元素按升序排列，则返回1，否则返回0。 - `IsDescending(R)`：若有理数R的两个元素按降序排列，则返回1，否则返回0。 - `Max(R,&e)`：用e返回有理数R的两个元素中值较大的一个。 - `Min(R,&e)`：用e返回有理数R的两个元素中值较小的一个。 #### 1.5 试画出与下列程序段等价的框图。 (1) `product=1;i=1; while(i<=n){ product*=i; i++; }` 这个程序片段计算n的阶乘。等价的流程图为： ``` [Start] --> [product=1, i=1] --> [i <= n?] | | V V [product *= i] --> [i++] | | V V [End] [No] | | V V [Yes] [Loop back to "i <= n?"] ``` (2) `i=0; do { i++; } while((i != n) && (a[i] != x));` 这个程序片段寻找数组a中第一个等于x的元素。等价的流程图为： ``` [Start] --> [i=0] --> [Loop start] | | V V [i++; i != n? && a[i] != x?] --> [End loop] | | V V [No] [Yes] | | V V [End] [Loop back to "Loop start"] ``` (3) `switch{ case x < y: z = y - x; break; case x == y: z = abs(x * y); break; default: z = (x - y) / abs(x) * abs(y); }` 这个程序片段根据x和y的关系计算z的值。等价的流程图为： ``` [Start] --> [x < y?] --> [Yes] | | | V V V [z = y - x] --> [End] [No] [x == y?] | | | V V V [End] [No] [Yes] | | | V V V [z = abs(x * y)] --> [End] [Default] | | | V V V [End] [z = (x - y) / abs(x) * abs(y)] ``` #### 1.6 在程序设计中，常用下列三种不同的出错处理方式： - **使用`exit`语句终止执行并报告错误**：这种方式简单粗暴，适用于处理严重的错误情况，例如内存分配失败等。优点是可以立即停止程序执行，防止进一步的错误发生；缺点是无法提供更多的错误恢复机制，可能会导致程序状态不确定。 - **以函数的返回值区别正确返回或错误返回**：这种方式通过返回一个特殊的值来表示错误，例如返回-1或者NULL。优点是比较灵活，可以根据不同的错误情况返回不同的错误代码；缺点是需要在调用者处检查每一个函数的返回值，增加了额外的工作量。 - **设置一个整型变量的函数参数以区别正确返回或某种错误返回**：这种方式通过传递一个额外的参数，用来记录错误信息。优点是能够提供更多关于错误的信息；缺点是需要额外的参数管理，并且在某些情况下可能会增加函数调用的复杂性。 每种出错处理方式都有其适用场景，程序员需要根据具体情况选择最合适的出错处理机制。