第1章 绪论 数据结构（C++描述）

目录 1。1 什么是数据结构 1。2 算法的描述 1。3 算法分析 1。4 退出

1.1什么是数据结构 1.1.1 数据结构示例 1。线性表示例

2。树形结构示例 一层 二层 三层 四层

3。图形结构示例

1.1.2基本术语 1． 数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。 例如：数字、字母、汉字、图形、图像、声音都称为数据。 2．数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。

3． 数据对象（data object） 是性质相同的数据元素组成的集合，是数据的一个子集。 例如，整数数据对象的集合可表示为N＝{0，±1，±2…….}，字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。 4． 数据类型（data type） 是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。 例如，高级语言中用到的整数数据类型，是指由－32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。

5． 抽象数据类型（Abstract Data Type） 是指一个数学模型以及定义在该模型上的一组操作。 在本书中，描述一种抽象数据类型将采用如下书写格式： ADT <抽象数据类型名> is Data: < 数据描述> Operations:<操作声明> END

1.1.3 数据结构 1． 数据结构（data structure） 是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固有的。 （2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 （3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。

2． 从逻辑结构划分数据结构 数据结构从逻辑结构划分为： （1）线性结构 元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。 （2）非线性结构 元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。

3． 从存贮结构划分数据结构 数据结构从存贮结构划分为： (1)顺序存贮（向量存贮） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存贮 所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑 上相邻的元素存放到计算机内存后不一定是相邻的。

(3)索引存贮 使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。 (4)散列存贮 通过构造散列函数，用函数的值来确定元素存放的地址。

4． 数据结构的抽象描述 数据结构可用二元组D=(K,R)的形式来描述。其中，K={a1,a2,…,an}为元素集合，R={r1,r2,…,rm}为关系的集合。 例1-5 设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K={a1,a2,a3,a4,a5},R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，则它的逻辑结构用图描述见图1-4 。 a1 a2 a3 a4 a5 图1-4 线性表的逻辑结构描述

例1-6 设一个数据结构的抽象描述为D=(K,R),其中K={a,b,c,d,e,f,g,h},r={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<c,g>,<d,h>},则它的逻辑结构用图描述见图1-5。

例 1-7 设一个数据结构的抽象描述为D=(K,R),其中K={1,2,3,4},而R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}, 则它的逻辑结构用图描述见图1-6。

1.2 算法的描述 1.2.1 基本概念 1．算法（algorithm） 通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）： （1）输入：具有0个或多个输入的外界量（算法开始前的初始量） （2）输出：至少产生一个输出，它们是算法执行完后的结果。 （3有穷性：每条指令的执行次数必须是有限的。 （4)确定性：每条指令的含义都必须明确，无二义性。 （5)可行性：每条指令的执行时间都是有限的。

2．算法和程序的关系 算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。

1.2.2算法描述 1． 用流程图描述算法 一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。 2． 用自然语言描述算法 用我们日常生活中的自然语言（可以是中文形式，也可以是英形式）也可以描述算法。

3． 用其它方式描述算法 我们还可以用数学语言或约定的符号语言来描述算法。 4． 用C++描述算法 在本教材中，我们将采用C＋＋或类C++来描述算法。并且用C＋＋描述算法遵循如下规则： （1）所有算法的描述都用C＋＋中的函数形式 函数类型 函数名（形参及类型说明） { 函数语句部分 return(表达式值)； }

（2）函数中的形式参数有两种传值方式 若为一般变量名，则为单向传值，若在变量前面增加“&“符号，则为双向传地址。 例如有一个函数为 Void swap(&i, &j,k)则i，j为双向传地址参数，k为单向传值参数。 （3）函数的说明部分与函数的实现部分分离 在C＋＋中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离开来。 （4）输入函数 C＋＋中的输入函数调用为: cin>>变量名。

（5）输出函数 C＋＋中的输出函数调用为:cout<<变量名。 (6) C++中的类 C++对于面向对象程序设计的支持,核心部分就是类的定义。类的定义体现了抽象数据类型的思想，可以支持说明与实现的分离，将抽象数据类型的实现封装在类的内部，使之达到信息隐蔽的目的。 （7）public 说明 对于C++的类，类成员可以用public 声明，表示这些东西为公有的，可以在此类及其它类中使用。

（8）private 说明 对于C++类，类成员可以用private声明，表示这些东西为私有的，只能在本类中使用。 （9）protected说明 对于C++类，类成员可以用protected声明，表示这部分是受保护的，只能在本类及它的所有派生类中使用。

（10）C++的作用域 在C++中，每个变量都有一个作用域。在函数内声明的变量，仅能在该函数内部有效，在类中声明的变量，可以在该类内部有效，在整个程序中都能使用的变量，为全局变量，否则称为局部变量。若一个全局变量与一个局部变量同名，则该范围内全局变量不起作用。若要使之起作用，可以使用域操作符：：来实现。 （11）函数名重载 C++中允件多个函数取相同的函数名,但形式参数或返回类型可以不同。

（12）友元函数 在C++的类的声明中,可以使用保留字friend定义友元函数，使用友元函数可以在一个类中访问另一个类中的私有成员(PRIVATE)和被保护成员 (protected)。 （13）内联（inline）函数 在一个函数定义前加上inline前缀就成为内联函数。使用内联函数可减少函数调用和参数传递的系统开销。

1.3 算法分析 1.3.1 时间复杂度 1． 时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

例1-8 求下列算法段的语句频度   for(i=1; i<=n; i++) for(j =1; j <=i ; j++) x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+…+n=

2． 时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 设T(n)的一个辅助函数为g(n),定义为当n大于等于某一足够大的正整数n0时，存在两个正的常数A和B（其中A≤B），使得A≤T(n)/g(n)≤B均成立，则称g(n)是T(n)的同数量级函数。把 T(n)表示成数量级的形式为：T(n)=Ｏ(g(n)),其中大写字母Ｏ为英文Order（即数量级）一词的第一个字母。

例如，若T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2), 即Ｔ(n)与n2 数量级相同。 例1-9 分析下列算法段的时间频度及时间复杂度   for （i=1;i<=n;i++） for (j=1;j<=i;j++) for ( k=1;k<=j;k++) x=i+j-k;

分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n) = + = [ + ] 由于有1/6 ≤ T（n)/ n3 ≤1，故时间复杂度为Ｏ(n3)。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间 复杂度有： 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

1.3.2 空间复杂度 1． 空间频度 一个算法在执行时所占有的内存开销，称为空间频度，但我们一般是讨论算法占用的辅助存储空间。讨论方法与时间频度类似，不再赘述。 ２． 空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。