神马文学网第一章 绪论
来源：百度文库 编辑：神马文学网 时间：2024/04/28 02:20:10
第一节 数据结构讨论的范畴 瑞士的计算机专家在1976年出版了一本书，书名为《算法+数据结构 = 程序设计》，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组"指令"，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。
很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。
例一、求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。
例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。
例三、煤气管道的铺设问题。如右图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。
以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。很多问题求解最后都转化为求解数学方程或数学方程组，即使是不需要用计算机求解的简单问题也需要一个数学模型来描述，例如，大家都熟悉的"鸡兔同笼"问题，可转化为对"二元一次方程组"进行求解。又如在房屋设计或桥梁设计中的结构应力分析计算可化解为线性代数方程组求解的问题，再如，天天看到的天气预报，它的数学模型是一个环流模式方程。
而当计算机进入非数值计算领域、特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。
第二节 与数据结构相关的基本概念·数据
是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。
是计算机处理的信息的某种特定的符号表示形式。
数据是个集合，如果用集合的表示方法来写的话，就是
数据={x|x是计算机操作的对象}
·数据元素
是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"。
有两类数据元素：一类是不可分割的"原子"型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个"数据项"。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为"组合项"，而其它不可分割的数据项为"原子项"。
姓名 学号 性别 班号 出生日期 入学成绩 年 月 日
数据项是数据结构中讨论的"最小单位"。 它包括所有的数字和字符。图形和声音等信息最后也都可以转化为"字符"进行处理。而这些字符和数字是客观信息的一种描述。如"3000"，可以表示某个城市的3000万人口，也可表示3000元/平方的房价。
·关键字
指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。·数据对象
是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为"数据结构"，换句话说，数据结构是带"结构"的数据元素的集合。"结构"即指数据元素之间存在的关系。
在客观世界中存在的各个事物之间存在着千丝万缕的"联系"，因此在计算机对它进行处理的时候必然也要将这种关系描述进去，如数学方程就是变量之间的约束关系的一种描述，在此称这种关系为结构，因此，数据结构是一堆数据元素和这些数据元素之间的关系的总和。
意为 x 和 y 之间存在 "x领先于y" 的次序关系。
假设以三个4位的十进制数表示一个含12位十进制数的"长整数"，则可用如下描述的数学模型表示：它是一个含三个数据元素{a1,a2,a3}的集合，且在集合上存在下列次序关系：{，}。 例如，长整数 "321465879345" 可用 a1=3214，a2=4658 和 a3=9345 的集合表示，且三者之间的次序关系必须是，a1 表示最高4位，a3 表示最低的4位，a2 则是中间4位。
又如，可以用下述数据结构来描述2行3列的矩阵：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6} 的集合，且集合上存在"行关系"和"列关系"两个次序关系，其中行关系为{，，，}，列关系为
{，，}。
再如，描述1行6列的矩阵的数据结构的定义为：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上只存在一个次序关系，即：
{，，，，}。
从这两个例子可见，即使数据元素集合相同，而其上的关系不同，则构成的数据结构不同。 1.2.2 数据结构
数据结构的形式定义为：
数据结构是一个二元组
Data_Structures = ( D,S )
其中：D是数据元素的有限集，
S是D上关系的有限集。
按关系或结构分，数据结构可归结为以下四类：线性结构、树形结构、图状结构和集合结构。
数据结构应该包括数据的"逻辑结构"和数据的"物理结构"两个方面（层次）。
数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据"存储结构"。
上述对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机，完整的数据结构定义还应该包括它在计算机中的表示-即数据的存储结构。 存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
在计算机中表示信息的最小单位是"位(bit)"，任何一个数据元素都可以用一个 "位串" 表示，如，数值"321" 可用位串 101000001 表示，字母"A"可用位串 001000001 表示。当数据元素由多个数据项构成时，每个数据项即为表示数据元素的位串中的一个"子位串"。
由于逻辑结构包括数据元素集合和关系的集合，则讨论存储结构只需要分别讨论数据元素和关系在计算机中如何表示即可。 关系有两种表示方法：
其一为"顺序映象"。以 "y 相对于 x 的存储位置" 表示 "y 是x的后继"，例如，令 y 的存储位置和 x 的存储位置之间相差一个预设常量C，C本身是个隐含值，由此得到的数据存储结构为"顺序存储结构"。
其二为"链式映象"。以和x绑定在一起的附加信息(指针)表示后继关系，这个指针即为 y 的存储地址，由此得到的数据存储结构为"链式存储结构"。
可见，在顺序存储结构中只包含数据元素本身的信息，而链式存储结构中以"由数据元素 x 的存储映象和附加指针合成的结点"表示数据元素。
关系的最小单位是一个的有序对，则讨论关系的表示方法只需讨论这个有序对的表示方法即可，即如何表示 "y是x的后继"。
顺序映象
链式映象
1.2.3 数据类型和抽象数据类型
在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。
数据类型是一个"值"的集合和定义在此集合上的"一组操作"的总称。
所有高级语言中都有"整型"数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是"相同"的。程序员使用它们时仅需了解它们的数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个"整数类型"，而这个"整数类"的定义仅对"整数的数学特性"有明确规定。可称这个"整数类型"为"抽象数据类型"。
抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
例如，矩阵的抽象数据类型定义为，矩阵是一个由 m
n 个数排成 m 行 n 列的表，它可以进行初等变换、相加、相乘、求逆、……等运算。
抽象数据类型有两个重要特性：
·数据抽象
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
·数据封装
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。 在高级编程语言中实现的整数都具有下列"数学特性"：
它是这样一个序列：
……,-2,-1,0,1,2,……
此外，它可以进行"+"、"-"、"
"、"/"及"取模"等运算。
抽象"意为提取"数学特性"。
抽象数据类型必须给它的外部用户提供完整的 "接口"，例如，明确长整数是三个整数的序列以及可以对它进行的操作等。
同时，对外部用户来说，不需要了解它是如何实现的，内部实现的改变不影响外部的使用，更重要的是应该做到，不能让外部用户侵入内部。对外部用户来说，抽象数据类型应该完全是一个黑盒子。
很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。
例一、求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。
例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。
例三、煤气管道的铺设问题。如右图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。
以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。很多问题求解最后都转化为求解数学方程或数学方程组，即使是不需要用计算机求解的简单问题也需要一个数学模型来描述，例如，大家都熟悉的"鸡兔同笼"问题，可转化为对"二元一次方程组"进行求解。又如在房屋设计或桥梁设计中的结构应力分析计算可化解为线性代数方程组求解的问题，再如，天天看到的天气预报，它的数学模型是一个环流模式方程。
而当计算机进入非数值计算领域、特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。
第二节 与数据结构相关的基本概念·数据是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。
是计算机处理的信息的某种特定的符号表示形式。
数据是个集合，如果用集合的表示方法来写的话，就是
数据={x|x是计算机操作的对象}
·数据元素
是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"。
有两类数据元素：一类是不可分割的"原子"型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个"数据项"。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为"组合项"，而其它不可分割的数据项为"原子项"。
姓名 学号 性别 班号 出生日期 入学成绩 年 月 日
数据项是数据结构中讨论的"最小单位"。 它包括所有的数字和字符。图形和声音等信息最后也都可以转化为"字符"进行处理。而这些字符和数字是客观信息的一种描述。如"3000"，可以表示某个城市的3000万人口，也可表示3000元/平方的房价。
·关键字
指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。·数据对象
是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为"数据结构"，换句话说，数据结构是带"结构"的数据元素的集合。"结构"即指数据元素之间存在的关系。
在客观世界中存在的各个事物之间存在着千丝万缕的"联系"，因此在计算机对它进行处理的时候必然也要将这种关系描述进去，如数学方程就是变量之间的约束关系的一种描述，在此称这种关系为结构，因此，数据结构是一堆数据元素和这些数据元素之间的关系的总和。
假设以三个4位的十进制数表示一个含12位十进制数的"长整数"，则可用如下描述的数学模型表示：它是一个含三个数据元素{a1,a2,a3}的集合，且在集合上存在下列次序关系：{
又如，可以用下述数据结构来描述2行3列的矩阵：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6} 的集合，且集合上存在"行关系"和"列关系"两个次序关系，其中行关系为{
{
再如，描述1行6列的矩阵的数据结构的定义为：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上只存在一个次序关系，即：
{
从这两个例子可见，即使数据元素集合相同，而其上的关系不同，则构成的数据结构不同。 1.2.2 数据结构
数据结构的形式定义为：
数据结构是一个二元组Data_Structures = ( D,S )
其中：D是数据元素的有限集，
S是D上关系的有限集。
按关系或结构分，数据结构可归结为以下四类：线性结构、树形结构、图状结构和集合结构。
数据结构应该包括数据的"逻辑结构"和数据的"物理结构"两个方面（层次）。
数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据"存储结构"。
上述对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机，完整的数据结构定义还应该包括它在计算机中的表示-即数据的存储结构。 存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
在计算机中表示信息的最小单位是"位(bit)"，任何一个数据元素都可以用一个 "位串" 表示，如，数值"321" 可用位串 101000001 表示，字母"A"可用位串 001000001 表示。当数据元素由多个数据项构成时，每个数据项即为表示数据元素的位串中的一个"子位串"。
由于逻辑结构包括数据元素集合和关系的集合，则讨论存储结构只需要分别讨论数据元素和关系在计算机中如何表示即可。 关系有两种表示方法：
其一为"顺序映象"。以 "y 相对于 x 的存储位置" 表示 "y 是x的后继"，例如，令 y 的存储位置和 x 的存储位置之间相差一个预设常量C，C本身是个隐含值，由此得到的数据存储结构为"顺序存储结构"。
其二为"链式映象"。以和x绑定在一起的附加信息(指针)表示后继关系，这个指针即为 y 的存储地址，由此得到的数据存储结构为"链式存储结构"。
可见，在顺序存储结构中只包含数据元素本身的信息，而链式存储结构中以"由数据元素 x 的存储映象和附加指针合成的结点"表示数据元素。
关系的最小单位是一个
顺序映象
链式映象
1.2.3 数据类型和抽象数据类型在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及枚举型。
数据类型是一个"值"的集合和定义在此集合上的"一组操作"的总称。
所有高级语言中都有"整型"数据类型，它们的实现方法可以各自不同，但对程序员而言，它们是"相同"的。程序员使用它们时仅需了解它们的数学特性，而不需要了解它们在语言中是如何实现的。换句话说，各种语言中实现的是同一个"整数类型"，而这个"整数类"的定义仅对"整数的数学特性"有明确规定。可称这个"整数类型"为"抽象数据类型"。
抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
例如，矩阵的抽象数据类型定义为，矩阵是一个由 m
n 个数排成 m 行 n 列的表，它可以进行初等变换、相加、相乘、求逆、……等运算。抽象数据类型有两个重要特性：
·数据抽象
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
·数据封装
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。 在高级编程语言中实现的整数都具有下列"数学特性"：
它是这样一个序列：
……,-2,-1,0,1,2,……
此外，它可以进行"+"、"-"、"
"、"/"及"取模"等运算。抽象"意为提取"数学特性"。
抽象数据类型必须给它的外部用户提供完整的 "接口"，例如，明确长整数是三个整数的序列以及可以对它进行的操作等。
同时，对外部用户来说，不需要了解它是如何实现的，内部实现的改变不影响外部的使用，更重要的是应该做到，不能让外部用户侵入内部。对外部用户来说，抽象数据类型应该完全是一个黑盒子。