《数据结构——用C语言描述》第一章 基础概念与习题_数据结构用c语言描述第三版耿国华答案

一、数据结构基础概念

1. 数据(data)是描述客观事物的数值、字符以及能输入计算机且能被处理的各种符号集合。

简而言之，数据就是 计算机化的信息。
数据特点：（1）可被计算机接收（2）可被加工\处理
数据构成：（1）数据元素（2）数据对象

2. 数据元素(data element)是组成数据的基本单位，是数据集合的个体。

数据项是最小单位，，一个数据元素可由一个或多个数据项组成。

3. 数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。

4. 数据结构(data structure)是指相互之间存在一种或多种特定关系的数据元素集合。

数据结构包括（1）数据元素集合（2）元素之间关系的集合

5. 数据类型(data type)是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。

按“值”的不同特性分为两大类：
（1）原子类型，其值不可再分，eg:C语言中的整型，实型，字符型和 指针
（2） 结构类型 ，其值由若干成分按某种结构组合而成，eg: 数组 ， 结构体
用户自定义类型：由用户先定义后使用（C语言中由struct构造新类型）

6. 抽象数据类型(abstract data type,ADT)定义一个数据对象、数据对象中各元素间的结构关系以及一组处理数据的操作。

抽象数据类型包括定义和实现，且定义独立于实现，定义给出抽象数据类型的逻辑特性，实现则需要考虑计算机和代码。

抽象数据类型 最重要的特点是（1） 数据抽象——复用性/可移植性
（2） 信息隐蔽——对用户而言，隐藏数据存储和操作实现的细节
抽象数据类型的 特征：使用与实现分离，实现 信息隐蔽和 封装。前者对应使用者，后者对应实现者。

简而言之，抽象数据类型包括（1）数据对象（2）数据元素间的结构关系（3）数据元素间的基本操作

二、数据结构的内容

数据元素间的相互关系包括数据的（1）逻辑结构（2）存储结构（3）运算集合。

1. 数据的逻辑结构

定义：数据元素之间的逻辑关系的描述。

形式定义：数据结构是一个二元组 Data_Structure=（D，R）

根据数据元素之间的关系的不同特性，有4类基本结构：

（1）集合结构，属于同一集合
（2）线性结构，一对一的线性关系
（3）树形结构，一对多的层次关系
（4）图结构或网状结构，多对多的任意关系

用其他结构代替集合结构后，4类基本逻辑结构可分为：

（1） 线性结构——线性表、栈、队、字符串、数组、广义表
（2） 非线性结构——树、图

2. 数据的存储结构\物理结构

定义：逻辑结构在计算机中的存储映像，包括数据元素映像和关系映像。

逻辑结构与存储结构的关系：逻辑结构是数据结构的抽象，存储结构是数据结构的实现，二者共同建立了数据元素之间的结构关系。

数据元素之间的关系和关系映像在计算机中有两种表示方法：顺序映像（顺序存储结构）和非顺序映像（非顺序存储结构）。

3. 数据的运算集合

数据的运算集合即对数据的操作，基本可以概括为增、删、改、查。

数据结构课程的基本内容：按某种逻辑关系组织起来的一批数据，按一定的映像方式将其存放在计算机的存储器中，并在这些数据上定义一个运算的集合。
数据结构的主要研究内容：（1）怎样合理地组织数据
（2）建立合适的结构
（3）提高执行程序所用的时空效率

三、算法

1. 沃思提出一个著名的公式：算法+数据结构=程序。

2. 算法定义：是规则的有限集合，是为解决特定问题而规定的一系列操作。

3. 算法的五大特性：（1）有限性；（2）确定性；（3）可行性；（4）输入，0个或多个；（5）输出，至少有一个

最基本的三个特性：有限性，确定性，可行性

4. 算法设计的要求

算法设计的目标是正确、可读、健壮、高效和低耗（低存储量）。

算法设计的基本特征：（1）正确性，能应对带有刁难性的数据
（2）可读性，有助于人们理解算法
（3）健壮性（鲁棒性），对非法数据能加以识别，做出处理
（4）高效率和低存储量，执行时间尽可能短，存储空间尽可能小

四、算法描述

1. 设计实现算法过程的步骤

（1）建立结构关系，即找出与求解有关的数据元素之间的关系

（2）确定在某一数据对象上所施加的运算

（3）考虑数据元素的存储表示

（4）选择描述算法的语言

（5）设计实现求解的算法，并用程序设计语言加以描述

2. 描述算法的语言选择

采用接近于高级语言而又不是严格的高级语言——类语言，具有高级语言的一般语句，撇掉语言中的细节，以便把注意力集中在算法处理步骤本身上的描述上。

五、算法性能评价

算法的性能评价是对问题规模与该算法在运行时所耗费时间与所占用空间给出一个数量关系的评价。

算法与问题规模的关系：算法效率是问题规模的函数。

算法的时间复杂度和空间复杂度合称为算法的复杂度。

1. 算法的时间性能分析

算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间=该条语句的执行次数*执行一次所需的实际时间。语句执行一次所需的实际时间与计算机的软硬件环境相关。

语句频度是指该语句在一个算法中 重复执行的次数。
一个算法的时间耗费就是该算法中所有语句频度之和。
时间复杂度指随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为 时间复杂度。

常将渐进时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

当算法的执行时间与问题规模无关时，该算法的时间复杂度为常数阶，记作T(n)=O(1)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

最优算法是随n的增大，T(n)的增长较慢的算法。
比较算法的性能，一般是比较时间复杂度增长的平缓程度，增长平缓的是更优的算法。
多种数量级的时间复杂度比较：log2n优于n优于nlog2n优于n^2优于n^3优于2^n
不做特别说明时，讨论的时间复杂度均为最坏时间复杂度
平均时间复杂度:在所以可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

2. 算法的空间性能分析

算法空间分析度量的标准是计算整个算法所需要的辅助空间单元个数。

算法的空间复杂度S(n)定义为该算法所耗费的存储空间的数量级，是问题规模n的函数。

3. 算法性能选择

一般算法只能侧重于时间或空间，若需要节约时间，往往需要以牺牲更多空间为代价；若要节省空间，则会以时间为代价。因此，需根据具体情况进行取舍。

（1）若给程序使用次数较少，则力求算法简明易懂。

（2）对于反复使用的程序，应尽可能选用快速的算法。

（3）若待解决的问题数据量极大，计算机的存储空间较小，则算法主要考虑如何节省空间。

以上内容，基于耿国华老师主编的第三版《数据结构——用C语言描述》，可搭配慕课视频更深入的学习。