数据结构概论

第一章 总述

1、 第一章 导论

2、 数据结构是组织数据的方式

3、 数据是信息的载体，可被计算机识别、存储和处理，作为程序运行的基础原料。随着计算机应用范围不断拓展，数据类型日益丰富，涵盖整数、实数、字符串，以及图像、声音等多种形式。

4、 数据元素是构成数据的基本单元，常被称为元素、节点、顶点或记录。每个数据元素可包含多个数据项，数据项亦称字段、域或属性，是具有独立意义的最小标识单位。数据元素通过其组成的数据项表达更复杂的信息结构，是数据组织的重要基础。

5、 数据结构是指数据元素之间的逻辑关系，反映数据的组织与存储方式。

6、 数据结构通常包含逻辑结构、存储结构及操作运算。

7、 数据元素间的逻辑关系，即数据在逻辑上的组织形式，称为数据的逻辑结构。

8、 数据的逻辑结构描述数据间的逻辑关系，与存储方式无关，独立于计算机系统。它可视为从实际问题中抽象出的数学模型，反映数据元素之间的内在联系。

9、 数据元素及其相互关系在计算机内存中的具体体现，被称为数据的存储结构。

10、 数据的存储结构是逻辑结构在计算机语言中的具体实现，也称映象，其形式依赖所用的语言。对于机器语言，存储结构较为具体，通常我们仅在高级语言层面讨论这一概念。

11、 对数据进行的各种处理与操作。

12、 数据的运算基于其逻辑结构定义，每种结构对应一组特定操作。常见的检索、插入、删除、更新和排序等操作，本质上是对抽象数据进行的一系列逻辑处理，体现了数据结构与操作之间的紧密关联。

13、 抽象操作关注的是做什么而非如何做，其具体实现方式需在确定存储结构之后才予以考虑。

14、 通过实例讲解，帮助理解数据结构的基本概念，增强直观感受。

15、 在表格中标注数据元素、数据项、起始结点与终止结点等关键概念。

16、 表中的每一行代表一个数据元素，也称为记录或结点，包含学号、姓名、各科成绩以及平均成绩等信息。这些数据元素之间存在着特定的逻辑关系：对于表中任意一个结点，至多只有一个结点紧邻其前，称为直接前趋；同样，至多只有一个结点紧接其后，称为直接后继。这意味着每个元素在序列中都有唯一的前驱和后继（除了首尾元素）。整个表中仅有一个结点没有前趋，即它前面没有其他结点，这个结点被称为开始结点；也仅有一个结点没有后继，即它后面没有其他结点，称之为终端结点。例如，在这张学生成绩表中，马二所在的结点，其直接前趋是丁一所在的结点，而其直接后继则是张三所在的结点。正是通过这种前后相继的关系，所有结点按照线性方式组织起来，形成了该表格的逻辑结构。这种结构体现了数据元素之间的有序性和唯一关联性，构成了典型的线性关系模式。

17、 存储结构是指在计算机中如何表示数据元素之间的逻辑关系，即采用顺序存储方式将节点存放在连续的内存单元中，还是通过指针链接各个节点，形成链式结构来实现数据的组织与管理。

18、 在学生成绩表中，常需查询特定学生的成绩，学生退学时需删除对应记录，新增学生则要添加新记录。这些操作涉及如何高效地查找、删除和插入数据，正是数据运算需要解决的核心问题。

19、 明确上述三点，即可掌握学生成绩表的数据结构。

20、 数据逻辑结构的分类方式

21、 在无歧义时，数据逻辑结构常简称为数据结构，主要分为两大类型。

22、 线性结构

23、 线性结构的逻辑特点是：非空集合中仅存在一个首结点和一个尾结点，其余每个结点至多有一个前驱和一个后继。

24、 线性表是典型的线性结构，栈、队列和串也均属于此类结构。

25、 非线性架构

26、 非线性结构中，结点可拥有多个前趋和后继，数组、广义表、树与图均属于此类数据结构。

27、 数据四种基本存储方式

28、 数据存储结构可通过四种基本方法实现。

29、 顺序存储方式

30、 将逻辑上相邻的节点存放在物理位置相邻的存储单元中，通过存储单元的邻接关系反映节点间的逻辑联系。

31、 这种存储表示方式被称为顺序存储结构，一般通过程序设计语言中的数组来实现和描述。

32、 该方法适用于线性数据结构，非线性结构可通过线性化处理实现顺序存储。

33、 链式存储方式

34、 该方法中，逻辑上相邻的节点在物理位置上不必相连，其逻辑关系通过附加的指针字段来体现。这种存储方式称为链式存储结构，通常利用编程语言中的指针类型进行描述，能够灵活地表示数据元素之间的前后关联，具有较高的动态性和扩展性。

35、 索引的存储方式

36、 该方法在存储节点信息时，通常会同时构建额外的索引表。

37、 索引表由多个索引项构成。当每个结点在索引表中均拥有独立的索引项时，称为稠密索引；而当多个结点共同对应一个索引项时，则称为稀疏索引。索引项通常包含指向数据结点的指针以及相应的关键字，用于加快查找速度。这种结构在文件系统和数据库中广泛应用，以提升数据访问效率。

38、 关键词与位置信息

39、 关键字是唯一确定结点的数据项。稠密索引中，索引项指向单个结点的存储位置；稀疏索引中，索引项则指向一组结点的起始地址。

40、 散列法存储数据

41、 通过关键字直接计算出结点的存储位置，实现快速定位与访问。

42、 四种基础存储方式可独立或组合运用，实现数据结构的存储映射。

43、 不同的存储方式可实现同一逻辑结构，形成多样的存储结构。具体选用哪种方式，需根据实际需求决定，重点考虑操作便捷性以及算法在时间和空间上的效率。

44、 数据处理与计算

45、 为提升数据处理效率，需按特定逻辑结构对数据进行组织，并选用合适的存储方式将其保存在计算机内存中。数据运算基于逻辑结构定义，但实际执行需依托存储结构完成。每种逻辑结构对应一组特定的运算操作，形成相应的运算集合。常见的基本运算包括数据的插入、删除、查找、遍历和排序等，这些操作在不同逻辑结构下具有不同的实现方式和效率表现，是数据处理中的核心操作。

46、 在数据结构中查找符合特定条件的节点。

47、 插入：在数据结构中添加新的节点。

48、 移除数据结构中指定的节点。

49、 更新操作用于修改特定节点中一个或多个字段的内容。

50、 保持节点数量不变，按指定顺序在线性结构中重新排列节点序列。

51、 算法应具备以下特性：

52、 算法必须在有限步骤内完成并终止。

53、 算法每一步都必须有明确无误的定义。

54、 算法可有零个或多个输入数据。

55、 每个算法至少产生一个结果输出。

56、 算法必须具备实际可操作性。

57、 算法是步骤，程序是实现。

58、 通常程序无需具备有穷性，且以机器可执行语言编写；而算法则无此限制，常以更通用的形式表达，不局限于特定编程语言。

59、 数据结构三要素及其相互关系

60、 数据的逻辑结构、存储结构与运算三者密不可分，必须整体把握。片面孤立地看待其中某一环节，忽视彼此间的关联，将难以真正理解数据的本质与运作机制。

61、 存储结构是数据结构的重要组成部分，相同的逻辑结构采用不同存储方式时，可被命名为不同的数据结构。

62、 线性表是一种逻辑结构，使用顺序存储时称为顺序表，采用链式存储时称为链表，若以散列方式存储，则被称为散列表。不同存储方式对应不同的实现形式。

63、 数据的运算与数据结构密不可分。即使逻辑和存储结构相同，若定义的运算集合及其特性不同，也可能形成截然不同的数据结构。

64、 当线性表的插入和删除操作仅限于表的一端进行时，该结构称为栈；若插入限定在一端，删除限定在另一端，则称为队列。根据存储方式的不同，线性表可采用顺序存储或链式存储。在此基础上施加上述操作限制后，分别形成顺序栈、链栈、顺序队列和链队列，它们是栈与队列在不同存储结构下的具体实现形式。

65、 附录一：各类数据的类型说明

66、 数据类型指的是一组值的集合及其上定义的操作总和，通常可视为程序设计语言中已实现的数据结构形式。

67、 C语言中的整数类型规定了整数所能取值的范围，其上限INT_MAX因机器而异，同时还定义了可对整数执行的加、减、乘、除及取模等基本运算操作。

68、 根据值能否分解，数据类型可分为可分与不可分两类。

69、 原子类型指不可再分的值，通常由编程语言直接支持。

70、 C语言中的基本类型如整型、字符型及指针等简单衍生类型。

71、 结构类型是指可拆分为多个组成部分的类型，由用户利用语言提供的机制自行定义，通常基于基本类型扩展而来，因此也属于一种派生类型。

72、 C语言中的数组与结构类型。

73、 附录二：抽象数据类型（简称ADT），描述数据的逻辑结构与操作集合。

74、 抽象数据类型指数据的逻辑组织形式及在其上定义的一系列操作，体现了数据结构与其操作方法的结合。

75、 一种数据类型可定义为：

76、 数据来源及说明

77、 描述数据元素间的逻辑关联

78、 操作指南：请按步骤执行相关操作。

79、 操作1通常可用C或C++语言的函数原型进行描述。

80、 输入数据的详细描述与要求说明

81、 执行该操作前，系统需处于特定状态，此状态为操作启动的前提条件。

82、 处理数据所进行的具体操作步骤

83、 返回数据的具体内容及格式说明。

84、 操作执行完毕后，系统所处的最终状态。

85、 执行第二步操作流程

86、 ……

87、 抽象数据类型可视为描述问题的模型，具有独立于具体实现的特点。其主要优势在于将数据与操作封装为一体，用户程序仅能通过ADT所定义的操作来访问数据，有效实现了信息隐藏。在C++中，可通过类（包括模板类）的声明来表达ADT，而类的实现部分则完成ADT的具体功能。因此，C++中的类实质上不仅定义了数据的存储结构，还包含了作用于该结构上的各种操作，形成一个完整的数据操作体系。

88、 ADT与类体现了软件设计中的两种抽象层次：ADT侧重于概念层面的问题描述，关注的是数据的逻辑结构与操作接口；而类则处于实现层面，是对ADT的具体编码实现。在C++中，类是一种用户自定义的数据类型，可用于创建变量，这些变量称为对象或类的实例。程序通过操作这些对象来完成具体功能，因此对象的使用构成了应用层。例如，main函数作为程序入口，通常体现为用户的实际应用场景，通过调用和操作各类对象来实现所需功能，从而将抽象设计转化为实际运行的程序行为。

89、 由于C语言不支持类这种数据类型，无法实现抽象数据类型（ADT），因此本文不采用ADT形式描述数据结构，以精简内容。需注意的是，这并不影响实质，其本质仍是我们所定义数据的逻辑结构及其上的一系列抽象操作，两者在概念上是等价的。

90、 附录三：算法说明

91、 数据的处理由算法描述，算法研究是数据结构课程的核心内容之一。

92、 算法

93、 算法是一种明确的计算步骤，接收一个或多个输入值，经过一系列规则处理，生成一个或多个输出结果。

94、 算法是解决计算问题的有效方法与步骤集合。

95、 算法是将输入经由一系列计算步骤转化为输出的过程。

96、 将一组数字按从小到大的顺序重新排列。

97、 问题形式化为符合特定关系的输入与输出序列组合。

98、 输入一个包含n个数字的序列，记为a?到a?。

99、 输出一个序列的排列〈a1,a2,…,an〉，满足a1≤a2≤…≤an。

100、 对输入序列〈31，41，59，26，41，58〉进行排序后，应得到升序排列的输出结果〈26，31，41，41，58，59〉。

101、 输入示例

102、 一个输入实例包含满足问题条件的所有数据，是求解该问题所需的基础信息集合。

103、 正确与错误的算法之分

104、 若算法对所有输入都能终止并输出正确结果，即为正确算法，它能够有效解决指定的计算问题。

105、 错误算法指对部分输入无法终止，或虽终止却得出非预期结果的情况，通常我们只关注能够正确处理所有输入并输出准确答案的算法。

106、 算法描述

107、 算法可用自然语言或编程语言等形式表达，关键在于准确清晰地描述出每一步计算过程，确保执行时无歧义。

108、 描述算法最常用的是介于自然语言与编程语言之间的伪代码。其控制结构通常借鉴Pascal、C等语言的语法形式，但允许灵活运用表达力强的描述方式，突出算法逻辑，避免陷入具体编程语言的语法细节，从而使算法表述更清晰、简洁且易于理解。

109、 为便于上机验证算法并提升编程实践能力，选用C语言进行算法描述。

110、 定义一个错误处理函数，用于输出错误信息并终止程序运行，以便在后续多个程序中简化错误处理代码。

111、 包含标准库头文件，其中声明了exit函数，用于程序正常退出。

112、 包含标准输入输出头文件，其中定义了标准错误输出stderr。

113、 {

114、 将错误信息通过标准错误流输出，显示格式为Error:后接具体消息内容。

115、 终止程序运行，并向操作系统返回状态码1。

116、 }

117、 算法分析附录四

118、 衡量算法优劣的依据

119、 面对同一计算问题的多种算法，应如何评估其优劣，从而选择更高效、更可靠的解决方案？

120、 算法应首先确保正确性，其次重点考虑效率、可读性和可维护性。

121、 算法执行所需的时间消耗。

122、 主要考虑算法运行时所需的额外存储空间消耗。

123、 算法应简洁明了，便于理解、编写与调试。

124、 优选算法性能

125、 设计一个占用空间小、运行速度快且整体性能优越的算法十分困难，因为这些要求往往相互矛盾。追求时间效率通常需要更多存储空间，而节省空间则可能增加计算耗时。因此，在实际应用中需根据具体需求权衡取舍，突出重点，选择最合适的方案。

126、 若程序使用频率低，优先选择简单易懂的算法。

127、 针对频繁调用的程序，应优先选择执行效率高的算法。

128、 当问题数据庞大而内存有限时，算法设计应优先考虑降低空间占用。

129、 算法时间性能评估

130、 算法耗时与执行次数密切相关

131、 算法总耗时等于其中所有语句执行时间的累加和。

132、 每条语句的运行时长等于其执行次数乘以单次执行所耗费的时间。

133、 算法转化为程序后，每条语句的执行时间受机器指令效率、运行速度和编译代码质量等复杂因素影响，难以准确预估。

134、 为独立分析算法时间复杂度，可假设每条语句执行一次耗时均为一个单位时间，此时算法的总时间耗费等于其中所有语句执行次数的总和。

135、 计算两个n阶方阵相乘得到C，算法过程如下所示。

136、 将n定义为100，可根据实际需求调整该数值大小。

137、 右侧列出各语句出现频率

138、 }

139、 }

140、 算法中各语句执行次数的总和即为其时间复杂度。

141、 分析：

142、 语句（1）的循环变量i从初始值递增至n，当i等于n时条件成立，循环结束，因此该语句被执行了n+1次，频度为n+1，但循环体实际运行n次。作为其内部语句，语句（2）随循环体执行n次，而每次循环中它自身又被调用n+1次，故其总频度为n(n+1)。依同样逻辑推导，语句（3）、（4）和（5）的执行频度分别为n?、n?(n+1)和n?。

143、 矩阵阶数n决定了算法MatrixMultiply的时间复杂度。

144、 问题规模与算法时间复杂度的关系分析

145、 问题规模指算法求解时输入量的大小，通常以整数表示。

146、 算法的时间复杂度是指执行该算法所需时间随问题规模n变化的函数关系。当输入规模n逐渐增大至无穷时，时间复杂度所呈现的数量级或增长趋势，被称为渐进时间复杂度，它反映了算法在大规模数据下的效率表现，是衡量算法性能的重要指标之一。

147、 当n趋于无穷大时，算法MatrixMultiply的时间复杂度T(n)如式(1.1)所示，其增长趋势明显。

148、 这说明当n足够大时，T(n)与n?的比值趋近于一个非零常数，二者具有相同的增长量级，即同阶。因此，可认为T(n)的数量级与n?相当，通常记为T(n)=O(n?)，这表示算法MatrixMultiply的渐近时间复杂度为n的三次方阶。

149、 大O符号的严谨数学定义如下

150、 若两个函数T(n)和f(n)定义在正整数集上，T(n)=O(f(n))表示存在正常数C与n?，使得对所有n≥n?，均有0≤T(n)≤C·f(n)成立。

151、 渐进时间复杂度用于评估算法的时间性能。

152、 通常通过算法时间复杂度的数量级来评估其时间性能，反映算法运行时间随输入规模增长的趋势。

153、 有两个算法A1和A2用于解决同一问题，其时间复杂度分别为T1(n)=100n?与T2(n)=5n?。

154、 当输入量n小于20时，T1(n)大于T2(n)，说明后者运行时间更短。

155、 随着问题规模n增大，两算法时间开销比值5n?/100n?＝n/20也随之上升，表明在大规模问题下，算法A1相比A2显著更高效。

156、 其渐近时间复杂度分别为O(n?)和O(n?)，从整体上反映了这两个算法在运行时间上的性能表现。在算法分析中，通常不对时间复杂度与渐近时间复杂度做严格区分，而是将渐近时间复杂度T(n)=O(f(n))直接称为时间复杂度，其中f(n)一般对应算法中执行频率最高的语句频度。

157、 交换变量i与j的值。

158、 上述三条语句各执行一次，程序运行时间不随问题规模n变化，属于常数时间，因此算法的时间复杂度为常数阶，记为T(n)=O(1)。

159、 当问题规模增大时，若算法执行时间保持不变，即便包含大量语句，其耗时仍为常量级别，这种算法的时间复杂度记为O(1)。

160、 变量计数示例一。

161、 通常分析步进循环语句时，主要关注循环体内语句的执行次数，而忽略步长递增、终值判断及控制跳转等操作。在上述程序段中，执行频率最高的语句是第(6)条，其执行次数为f(n)=n?，因此该程序段的时间复杂度为T(n)=O(n?)。

162、 当存在多个循环时，算法的时间复杂度取决于嵌套最深的内层循环语句的执行次数f(n)。

163、 变量计数方法的进一步示例。

164、 该程序段中执行频率最高的语句是(5)。虽然内循环的运行次数不直接依赖问题规模n，但受外层循环变量值的影响，而最外层循环次数与n直接相关。因此，应从内向外逐层分析语句(5)的执行频次。

165、 该程序段的时间复杂度为T(n)=O(n?/6+低阶项)，简化后为O(n?)。

166、 算法运行时间不仅受问题规模影响，还与其输入数据的初始状态密切相关。

167、 在数组A中寻找指定值K的步骤大致如下：从首元素开始逐个比对，直到找到K或遍历完毕为止。

168、 该算法中语句(3)的执行次数不仅取决于问题规模n，还受数组A各元素值及K值的影响。

169、 当A中不存在与K相等的元素时，语句(3)的执行次数为n。

170、 若A的末尾元素与K相等，则语句(3)的执行次数为0。

171、 最坏与平均情况下的时间复杂度分析

172、 最坏时间复杂度是指算法在最不利情况下的运行时间。通常情况下，若无特别说明，所讨论的时间复杂度即为最坏情况下的时间复杂度。

173、 因为最坏情况下的时间复杂度代表算法在所有输入上运行时间的上限，确保其执行时间不会超过该界限。

174、 平均时间复杂度是在各种输入等概率出现时，算法运行时间的数学期望值。

175、 常见的时间复杂度按增长速度从低到高排列为：常数阶O(1)、对数阶O(log?n)、线性阶O(n)、线性对数阶O(nlog?n)、平方阶O(n?)、立方阶O(n?)，以至k次方阶O(n?)，最后是指数阶O(2?)。其中，指数阶的增长速度极快，对应算法的执行效率很低，一旦输入规模n稍大，运算时间便会急剧上升，难以在实际中有效应用。

176、 空间复杂度S(n)表示一个算法在运行过程中所需存储空间随问题规模n变化的函数关系，类似于时间复杂度的概念。通常所说的渐近空间复杂度即简称为空间复杂度。时间和空间复杂度共同构成算法复杂度的核心内容，用于衡量算法在时间和内存资源上的消耗情况，是评估算法效率的重要指标之一。

177、 练习题 P15

178、 见书中插图所示

179、 3、

180、 算法如下：

181、 取数组首元素作为初始最大值m

182、 i从1开始，每次加1，循环至n-1结束。

183、 若A大于m，则

184、 记录下标 i 的值。

185、 输出最大值及其对应下标。

186、 算法终止。

187、 源代码如下所示

188、 {

189、 {

190、 }

191、 }