第1章绪论1.1什么是数据结构数据：是所有能被输入到计算机中且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合)中的一个“个体”，是数据的基本单位。1.1.1数据结构的定义数据对象：是具有相同性质的若干个数据元素的集合。例如,200402班为一个学生数据对象，而其中的“张三”是一个数据元素）。数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此，可时把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面：（1）数据元素之间的逻辑关系即数据的逻辑结构。(2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。(3）施加在该数据上的操作，即数据的运算。为了更确切地描述一种数据结构，通常采用二元组表示：B=(K,R)其中,B是一种数据结构,它由数据元素的集合K和K上二元关系的集合R所组成。其中：K=(ki|1≤i≤n,n≥0)R=(ril1≤j≤m,m≥0)逻辑结构的描述或表示：其中：ki表示集合K中的第i个结点或数据元素。n为K中结点的个数,特别地,若n=0,则K是一个空集,因而B也就无结构可言,有时也可以认为它具有任一结构。rj表示集合R中的第j个二元关系（后面均简称关系)。m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合K中的元结点间不存在任何关系,彼此是独立的。序偶<x,y>(xyEK）x为第一结点，y为第二结点。x为y的直接前驱结点（通常简称前驱结点）y为x的直接后继结点(通常简称后继结点)。若某个结点没有前驱结点,则称该结点为开始结点：若某个结点没有后继结点,则称该结点为终端结点。说明：<x,y>表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。1.1.2逻辑结构类型(1)线性结构结点之间关系：一对一。特点：开始结点和终端结点都是惟一的除了开始结点和终端结点以外，其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。(2)树形结构结点之间关系：一对多。特点：开始结点惟一，终端结点不一。除终端结点以外，每个结点有一个或多个后续结点；14
14 第 1 章 绪论 1.1 什么是数据结构 数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对 象的总称,也是计算机处理的信息的某种特定的符号表示形式。 数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。 1.1.1 数据结构的定义 数据对象：是具有相同性质的若干个数据元素的集合。 例如,200402 班为一个学生数据对象,而其中的“张三”是一个数据元素)。 数据结构：是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关 系的数据元素的集合。 因此,可时把数据结构看成是带结构的数据元素的集合。 数据结构包括如下几个方面： (1) 数据元素之间的逻辑关系,即数据的逻辑结构。 (2) 数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,也称为数 据的物理结构。 (3) 施加在该数据上的操作,即数据的运算。 为了更确切地描述一种数据结构,通常采用二元组表示： B=(K,R) 其中,B 是一种数据结构,它由数据元素的集合 K 和 K 上二元关系的集合 R 所组成。其 中： K={ki| 1≤i≤n,n≥0} R={rj| 1≤j≤m,m≥0} 逻辑结构的描述或表示： 其中： ki 表示集合 K 中的第 i 个结点或数据元素。 n 为 K 中结点的个数,特别地,若 n=0,则 K 是一个空集,因而 B 也就无结构可言,有时 也可以认为它具有任一结构。 rj 表示集合 R 中的第 j 个二元关系(后面均简称关系)。 m 为 R 中关系的个数,特别地,若 m=0,则 R 是一个空集,表明集合 K 中的元结点间不存 在任何关系,彼此是独立的。 序偶<x,y>(x,y∈K) x 为第一结点,y 为第二结点。 x 为 y 的直接前驱结点(通常简称前驱结点) y 为 x 的直接后继结点(通常简称后继结点)。 若某个结点没有前驱结点,则称该结点为开始结点；若某个结点没有后继结点,则称该 结点为终端结点。 说明：<x,y>表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。 1.1.2 逻辑结构类型 (1) 线性结构 结点之间关系：一对一。 特点：开始结点和终端结点都是惟一的,除了开始结点和终端结点以外,其余结点都有且仅有 一个前驱结点,有且仅有一个后继结点。顺序表就是典型的线性结构。 (2) 树形结构 结点之间关系：一对多。 特点：开始结点惟一,终端结点不惟一。除终端结点以外,每个结点有一个或多个后续结点；
除开始结点外，每个结点有且仅有一个前驱结点。(3)图形结构结点之间关系：多对多。特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。1.1.3存储结构类型（1）顺序存储方法(1)数据类型高级程序语言中，一般须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。数据类型是一个值的集合和定义在此集合上的一组操作的总称。1.1.4数据结构和数据类型如C/C++中的int就是整型数据类型。它是所有整数的集合（在16位计算机中为一32768~32767的全体整数)和相关的整数运算(如十、一、＊、/等)。(2）抽象数据类型抽象数据类型(AbstractDataType简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型=数据元素集合十抽象运算(2）链式存储方法(3）索引存储方法(4）散列存储方法1.2算法及其描述数据元素之间的关系有逻辑关系和物理关系，对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。通常把具体存储结构上的操作实现步骤或过程称为算法。算法的五个重要的特性（1）有穷性：在有穷步之后结束。(2）确定性：无二义性。（3）可行性：可通过基本运算有限次执行来实现。(4）有输入(5）有输出1.2.2算法描述本书中采用C/C++语言描述算法。说明：C++语言中提供了一种引用运算符“&”，引用是个别名，当建立引用时，程序用另一个已定义的变量或对象（目标）的名字初始化它，从那时起，引用作为目标的别名而使用，对引用的改动实际就是对目标的改动。1.3算法分析通常把算法中包含基本运算次数的多少称为算法的时间复杂度也就是说一个算法的时间复杂度是指该算法的基本运算次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作：T(n)=O(f(n))记号“O”读作“大O”它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。“O”的形式定义为若f(n)是正整数n的一个函数,则T(n)=O(f(n)表示存在一个正的常数M,使得当n≥nO15
15 除开始结点外，每个结点有且仅有一个前驱结点。 (3) 图形结构 结点之间关系：多对多。 特点：没有开始结点和终端结点，所有结点都可能有多个前驱结点和多个后继结点。 1.1.3 存储结构类型 (1) 顺序存储方法 (1) 数据类型 高级程序语言中,一般须对程序中出现的每个变量、常量或表达式,明确说明它们所属的 数据类型。不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。 数据类型是一个值的集合和定义在此集合上的一组操作的总称。 1.1.4 数据结构和数据类型 如 C/C++中的 int 就是整型数据类型。它是所有整数的集合(在 16 位计算机中为－ 32768~32767 的全体整数)和相关的整数运算(如＋、－、＊、／等)。 (2) 抽象数据类型 抽象数据类型(Abstract Data Type 简写为 ADT)指的是用户进行软件系统设计时从问 题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算,而不考虑计算机的具体 存储结构和运算的具体实现算法。 抽象数据类型=数据元素集合＋抽象运算 (2) 链式存储方法 (3) 索引存储方法 (4) 散列存储方法 1.2 算法及其描述 数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具 体存储结构上的操作实现。 通常把具体存储结构上的操作实现步骤或过程称为算法。 算法的五个重要的特性 (1) 有穷性:在有穷步之后结束。 (2) 确定性:无二义性。 (3) 可行性:可通过基本运算有限次执行来实现。 (4) 有输入 (5) 有输出 1.2.2 算法描述 本书中采用 C/C++语言描述算法。 说明：C++语言中提供了一种引用运算符“&”,引用是个别名,当建立引用时,程序用 另一个已定义的变量或对象(目标)的名字初始化它,从那时起,引用作为目标的别名而使用,对 引用的改动实际就是对目标的改动。 1.3 算法分析 通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复 杂度是指该算法的基本运算次数。 算法中基本运算次数 T(n)是问题规模 n 的某个函数 f(n),记作： T(n)=O(f(n)) 记号“O”读作“大 O”,它表示随问题规模 n 的增大算法执行时间的增长率和 f(n)的增长率 相同。“O”的形式定义为： 若 f(n)是正整数 n 的一个函数,则 T(n)=O(f(n))表示存在一个正的常数 M,使得当 n≥n0
时都满足：IT(n)|≤Mf(n)I也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时，算法的时间性能。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。各种不同数量级对应的值存在着如下关系：0(1)<0(log2n)<0(n)<0(n*1og2n)<0(n2)<0(n3)<0(2n)<0(n!)1.4数据结构十算法=程序数据结构对算法的影响主要在两方面（1）数据结构的存储能力数据结构存储能力强、存储信息多>算法将会较好设计（时间少），存储空间大。时间和空间的平衡（2）定义在数据结构上的操作在数据结构上定义基本操作>算法调用这些基本操作。选择数据结构需要考虑的几个方面：（1）数据结构要适应问题的状态描述（2）数据结构应与所选择的算法相适应（3）数据结构的选择同时要兼顾程序设计的方便（4）灵活应用已有知识本章小结本章介绍了数据结构的基本概念，主要学习要点如下：(1）数据结构的定义,数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。(2）各种逻辑结构即线性结构、树形结构和图形结构之间的差别。(3）数据结构和数据类型的差别和联系。（4)算法的定义及其特性。(5）算法的时间复杂度和空间复杂度分析。练习题1：习题3、习题5和习题6。上机题：熟悉VC++6.0环境16
16 时都满足： |T(n)|≤M|f(n)| 也就是只求出 T(n)的最高阶,忽略其低阶项和常系数,这样既可简化 T(n)的计算,又能比较客 观地反映出当 n 很大时,算法的时间性能。 其余常用的还有平方阶 O(n2)、立方阶 O(n3)、对数阶 O(log2n)、指数阶 O(2n)等。 各种不同数量级对应的值存在着如下关系： O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!) 1.4 数据结构＋算法＝程序 数据结构对算法的影响主要在两方面 （1）数据结构的存储能力 数据结构存储能力强、存储信息多＝＞算法将会较好设计（时间少），存储空间大。 时间和空间的平衡 （2）定义在数据结构上的操作 在数据结构上定义基本操作＝＞算法调用这些基本操作。 选择数据结构需要考虑的几个方面： （1）数据结构要适应问题的状态描述 （2）数据结构应与所选择的算法相适应 （3）数据结构的选择同时要兼顾程序设计的方便 （4）灵活应用已有知识 本章小结 本章介绍了数据结构的基本概念,主要学习要点如下： (1) 数据结构的定义,数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。 (2) 各种逻辑结构即线性结构、树形结构和图形结构之间的差别。 (3) 数据结构和数据类型的差别和联系。 (4) 算法的定义及其特性。 (5) 算法的时间复杂度和空间复杂度分析。 练习题 1： 习题 3、习题 5 和习题 6。 上机题： 熟悉 VC++6.0 环境