数据结构课件

算法与数据结构主讲虞闯

2012.08.27算法与数据结构主讲虞闯2012.08.1前言

计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。前言2数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据的能力，告诉学生如何编写效率高、结构好的程序。学习数据结构这门课程之后，你就可以掌握大量基本的具有复杂结构的数据组的方法，数据存储的方法，掌握大量基本算法的设计方法，具有分析算法好坏的能力。为后续课程的学习，为由业余的软件工作者向专业的软件工作者的转变打下坚实的理论基础。数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据31引言

2数据结构的发展简史及其在计算机科学中所处的地位3什么是数据结构

4基本概念和术语

5算法和算法的描述

第一章绪论

本章介绍数据结构这门学科诞生的背景、发展历史以及在计算机科学中所处的地位，重点介绍数据结构有关的概念和术语，读者学习本章后应能掌握数据、数据元素、逻辑结构、存储结构、数据处理、数据结构、算法设计等基本概念，并了解如何评价一个算法的好坏。1引言2数据结构的发展简4

1.1引言

众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科学计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。

1.1引言5

因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（DateStructure）。数据结构课件61.2数据结构的发展简史及其在计算机科学中所处的地位发展史：1、“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。2、1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》和第三卷《查找和排序》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。1.2数据结构的发展简史及其在计算机科学中所处的地位7地位：“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。地位：8数学代数系统数据组织算子关系软件（计算机程序设计）硬件（计算机系统设计）编码理论数据类型数据表示法数据的运算数据结构数据存取机器组织文件系统信息检索存储装置P4图1.4“数据结构”所处的地位数学代数系统数据组织算子关系软件9

1.3什么是数据结构

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改等操作的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。直观定义：《数据结构》课程是研究非数值计算的程序设计中计算机操作的对象以及它们之间的关系和操作的一门学科。

1.3什么是数据结构

10例1.1图书馆的书目检索系统自动化问题（表）001高等数学樊映川S01……002理论力学罗远祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02……..………………………………………高等数学001,003,…理论力学002,…线性代数004,…樊映川001,…华罗庚003,…栾汝书004,…L002,…S001,003,…图1.1图书目录文件示例书名索引表作者索引表分类号索引表例1.1图书馆的书目检索系统自动化问题（表）001高等数11例1.2计算机和人对弈问题（树）○○××○××○××○××○××○×××××××○○○○○例1.2计算机和人对弈问题（树）○○××○××○××○×12例1.3多叉路口交通灯的管理问题（图）EABCD(b)表示通路的图11111112223344(a)五叉路口EDABACADBABCBDDADBDCEAEBEC例1.3多叉路口交通灯的管理问题（图）EABCD(b)13例1.4电话号码查询问题的稀疏索引存储（表）姓氏地址张李姓名电话号码张三张林张洁李四李中………………例1.4电话号码查询问题的稀疏索引存储（表）姓氏地址张李14例1.5田径赛的时间安排问题（图）姓名项目1项目2项目3丁一A跳高B跳远E100米马二C标枪D铅球---张三C标枪E100米F200米李四D铅球F200米A跳高王五B跳远F200米---。。。。。。BACDEF表1。2参赛选手比赛项目表安排竞赛项目的数据结构模型例1.5田径赛的时间安排问题（图）姓名项目1项目2项目3151.4基本概念和术语1．数据

数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据是描述客观事物的符号，我们把一切能够被计算机识别并被计算机存储、处理的信息，包括文字、表格、图象等，都称为数据。是计算机化的信息。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。1.4基本概念和术语16表1-1个人书库表1-1个人书库172．结点结点也叫数据元素，它是组成数据的基本单位，是数据集合中的个体。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位(存取的最小单位)来考虑，故该数据由10个结点构成。数据结构课件183数据项：是数据不可分割的最小单位一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。3数据项：是数据不可分割的最小单位一般情况下，一个结点中含194．逻辑结构数据元素的集合以及定义在该集合上的关系。形式定义为一个二元组：

Data_Structure=(D,R)

其中：D是数据元素的有限集，R是D上关系的有限集。在表1-1所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了10个结点在表中排列的前后顺序。根据这种线性关系，可以看出表中第一本书是什么书，第二本书是什么书，等等。4．逻辑结构20

集合线性树图数据的逻辑结构示例

215．存储结构（物理结构）数据在计算机中的存储表示称为数据的存储结构。或者说是数据的逻辑结构在计算机中的映像（包括数据元素的映像和元素间关系的映像两部分）。在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。5．存储结构（物理结构）22两种基本的存储结构：数据元素之间的关系在计算机里有两种映像：顺序映像和非顺序映像。对应两种存储结构。

顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

链式存储结构：不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

两种基本的存储结构：236．数据处理数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算。进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的比例必将进一步增大。数据结构课件247.数据对象数据对象是性质相同的数据元素的集合，是一个数据的子集。7.数据对象数据对象是性质相同的数据元素的集合，是一个数据的258．数据结构（DataStructure）数据结构是研究数据元素（DataElement）之间抽象化的相互关系和这种关系在计算机中的存储表示（即数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构统称为数据结构（LogicalStructure），把数据的物理结构统称为存储结构（StorageStructure）。8．数据结构（DataStructure）269．数据类型数据类型是指程序设计语言中被操作对象可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。因此，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。9．数据类型27按“值”的不同特性,高级程序语言中的数据类型可分为两类:

非结构的原子类型。其值不可再分。如C语言中的基本类型：整型、实型、字符型、枚举型、指针类型和空类型。

结构类型。其值由若干成分按某种结构组成，可以分解，其成分可以是非结构的，也可以是结构的。如数组、结构体、共同体等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而结构类型可以看成有一种数据结构和定义在其上的一组操作组成。

抽象数据类型（简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的格式为：

ADT抽象数据类型名{数据对象：＜数据对象的定义＞结构关系：＜数据关系的定义＞基本操作：＜基本操作的定义＞}ADT抽象数据类型名按“值”的不同特性,高级程序语言中的数据类型可分为两类:28

8．算法

简单地说就是解决特定问题的方法和步骤（关于算法的严格定义，在此不作讨论,祥见1.5节）。特定的问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。8．算法29一般说来，在数值算法中主要进行算术运算，而在非数值算法中主要进行比较和逻辑运算。另一方面，特定的问题可能是递归的，也可能是非递归的，因而解决它们的算法就有递归算法和非递归算法之分。从理论上讲，任何递归算法都可以通过循环，堆栈等技术转化为非递归算法。数据结构课件301.5算法和算法的描述

1.5.1算法算法是执行特定计算的有穷过程。这个过程有5个特点：1.动态有穷性（有限性）：当执行一个算法时，不论是何种情况，在经过有限步骤后，这个算法一定要终止。2.明定性：算法中每条指令都必须是无二义性的。3.输入：具有0个或0个以上由外界提供的量。4.输出：产生1个或多个结果。5.可行性：通过算法得出一定的结果。注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本书中，我们只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。1.5算法和算法的描述

1.5.1算法31

1.5.2算法的描述

一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用类C语言作为描述算法的工具。现简单说明类C语言的语法结构如下：

1.5.2算法的描述32

1．预定义常量和类型：#defineTRUE1；#defineFALSE0；#defineOK1；#defineERROR0；#defineINFEASIBLE-1；#defineOVERFLOW-2；

数据结构课件332．函数的形式

[数据类型]函数名（[形式参数]）[形式参数说明；]{内部数据说明；执行语句组；}/*函数名*/

函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用“；”号分隔。可将函数中的表达式的值通过return语句返回给调用它的函数。最后的花括号“}”之后的/*函数名*/为注释部分，可舍去。

2．函数的形式343．赋值语句简单赋值：〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；〈变量〉++，它表示变量加1后赋值给变量；〈变量〉--，它表示变量减1后赋值给变量；3．赋值语句35成组赋值：

（〈变量1〉,〈变量2〉,〈变量3〉,…〈变量k〉）=（〈表达式1〉，〈表达式2〉,〈表达式3〉,…〈表达式k〉）;

〈数组名1〉[下标1…下标2]=〈数组名2〉[下标1…下标2]；数据结构课件36串联赋值：〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；条件赋值：〈变量名〉=〈条件表达式〉？〈表达式1〉：〈表达式2〉；交换赋值：〈变量1〉←→〈变量2〉，表示变量1和变量2互换；串联赋值：374．条件选择语句if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；情况语句switch（〈表达式〉）{case判断值1；语句组1；break；case判断值2；语句组2；break；……case判断值n；语句组n；break；[default：语句组n+1；]}注意：switchcase语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。4．条件选择语句386．输入、输出语句输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，特别当要输出字符数据时，用putchar函数实现。数据结构课件397．其他一些语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。8．注释形式

可用/*字符串*/或者单行注释或//文字序列。7．其他一些语句409．一些基本的函数如：max函数，用于求一个或几个表达式中的最大值；min函数，用于求一个或几个表达式中的最小值；abs函数，用于求表达式的绝对值；eof函数，用于判定文件是否结束；eoln函数，用于判断文本行是否结束。10.逻辑运算与运算&&:对于A&&B,当A的值为0时,不再对B求值；与运算||:对于A||B,当A的值为非0时,不再对B求值；9．一些基本的函数41例计算f=1！+2！+3！+…+n！用C语言描述。voidfactorsum（n）{intn,i,j,f,w；f=0；for（i=1;i〈=n；i++）{w=1；for（j=1;j〈=i；j++）w=w*j；f=f+w；}returnf；}上述算法所用到的运算有乘法、加法、赋值和比较，其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。所以，整个算法所作的乘法操作总数是：f（n）=1+2+3+…n=n（n+1）/2。例计算42

1．正确性

“正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：①程序不含语法错误；②程序对于几组输入数据能够得出满足规格说明要求的结果；③程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；④程序对一切合法的输入数据都能产生满足规格说明要求的结果。

1.5.3算法评价

设计一个好的算法应考虑以下几个方面：1．正确性1.5.3算法评价432.可读性

可读性指算法容易被别人看懂并容易调试和修改。3.健壮性当输入数据非法时，能进行合理的反映和处理，或给出错误的提示并终止程序。2.可读性444．运行时间运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。数据结构课件455．占用的存储空间一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。分析一个算法所占用的存储空间要从各方面综合考虑。算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。5．占用的存储空间466．简单性最简单和最直接的算法往往不是最有效的，但算法的简单性使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。数据结构课件471.5.4算法效率度量的两个方面：时间复杂度和空间复杂度（1）时间复杂度：总的执行次数T（N)与规模N间的数量级关系．，这里用Ｏ来表示数量级．Ｔ（Ｎ）＝Ｏ（Ｆ（Ｎ））它表示随问题规模Ｎ增大，算法执行时间增长率与Ｆ（Ｎ）的增长率相同．Ｆ（Ｎ）算法的时间复杂性。在多数情况下,算法中关键操作执行的次数和包含它的语句的频度相同。语句的频度（frequencycount)指的是该语句重复执行的次数。所以，在实际应用时，用算法中语句的最大频度作为算法的时间复杂性1.5.4算法效率度量的两个方面：时间复杂度和空间复杂度48（2）空间复杂性Ｓ（Ｎ）＝Ｏ（Ｆ（Ｎ））主要分析算法实现时所需要的辅助空间单元个数，与算法无关．（2）空间复杂性491.5.5对算法性能的分析虽然，算法不是程序，不能上机运行，但是对算法性能的分析，完全可以用对程序性能的分析方法进行。见下例：1.5.5对算法性能的分析50求两个n阶方阵的乘积C=A×B，其算法如下：#definen100VoidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n],){inti,j,k;for(i=0;i<n;i++)……………n+1for(j=0;j<n;j++){………n(n+1)C[i][j]=0;………………n2for(k=0;k<n;k++)……n2(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];………n3}}所有语句频度之和（即算法的时间耗费）为：T（n）=2n3+

3n2+2n+1n为问题的规模limT(n)/n3=lim（2n3+3n2+2n+1）/n3=2

这表明，当n充分大时，T（n）和n3之比是一个不等于零的常数，即T（n）和n3是同阶的（数量级相同），记为T（n）=O（n3）。称为该算法的渐近时间复杂度。简称为时间复杂度（复杂性）。n→∞n→∞各语句的频度求两个n阶方阵的乘积C=A×B，其算法如下：所有语句频度之和51例如：在下面的三个程序段中

1.

{++x;s=0}

2.for(i=1;i<=n;++i){++x;s+=x;}

3.for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}关键操作++x的语句的频度分别为1，n，n²，则这三个程序段的时间复杂性分别为O（1），O（n），O（n²）分别称为常数阶，线性阶，平方阶。例如：在下面的三个程序段中52例：常量级时间复杂性t=i;i=j;j=t;for(i=0;i<9999;i++)x++;for(i=0;i<1000;i++)for(j=0;j<300;j++)for(k=0;k<8000;k++)x=x+5;x=91;y=100;while(y>0){if(x>100){x-=10;y--;}elsex++;}nT(n)例：线性级时间复杂性for(k=0;k<n;k++)x++;T(n)n例：常量级时间复杂性nT(n)例：线性级时间复杂性T(n)n53例：对数级时间复杂性i=1;while(i<=n)i=i*3;i依此取1，3，32，…，3i-1，根据循环条件有3i-1≤n,，i≤log3n+1，语句执行频度为log3n+1=O(log3n)例：对数级时间复杂性54200log2nT(n)n2n0.5n35n2100n20002000100030005101520常见函数的增长率200log2nT(n)n2n0.5n35n2100n20055常见的时间复杂度的函数增长率有如下规律：Log3n<log2n<n<n2<n3<2n常见的时间复杂度的函数增长率有如下规律：Log3n<lo56本章小结本章主要介绍了如下一些基本概念：数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。本章小结本章主要介绍了如下一些基本概念：57结点：结点也叫数据元素，它是组成数据的基本单位。逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。存储结构：数据在计算机中的存储表示称为数据的存储结构。数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。

结点：结点也叫数据元素，它是组成数据的基本单位。58

注意:作业与习题参考本课件中的

“习题集”部分

习

题

一1．简述下列术语：数据、结点、逻辑结构、存储结构、数据处理、数据结构和数据类型。2．试根据以下信息：校友姓名、性别、出生年月、毕业时间、所学专业、现在工作单位、职称、职务、电话等，为校友录构造一种适当的数据结构（作图示意），并定义必要的运算和用文字叙述相应的算法思想。3．什么是算法？算法的主要特点是什么？4．如何评价一个算法？

注意:作业与习题参考本课件中的

“习题集”部分

习题59算法与数据结构主讲虞闯

2012.08.27算法与数据结构主讲虞闯2012.08.60前言

计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。前言61数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据的能力，告诉学生如何编写效率高、结构好的程序。学习数据结构这门课程之后，你就可以掌握大量基本的具有复杂结构的数据组的方法，数据存储的方法，掌握大量基本算法的设计方法，具有分析算法好坏的能力。为后续课程的学习，为由业余的软件工作者向专业的软件工作者的转变打下坚实的理论基础。数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据621引言

2数据结构的发展简史及其在计算机科学中所处的地位3什么是数据结构

4基本概念和术语

5算法和算法的描述

第一章绪论

本章介绍数据结构这门学科诞生的背景、发展历史以及在计算机科学中所处的地位，重点介绍数据结构有关的概念和术语，读者学习本章后应能掌握数据、数据元素、逻辑结构、存储结构、数据处理、数据结构、算法设计等基本概念，并了解如何评价一个算法的好坏。1引言2数据结构的发展简63

1.1引言

众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科学计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。

1.1引言64

因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（DateStructure）。数据结构课件651.2数据结构的发展简史及其在计算机科学中所处的地位发展史：1、“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。2、1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》和第三卷《查找和排序》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。1.2数据结构的发展简史及其在计算机科学中所处的地位66地位：“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。地位：67数学代数系统数据组织算子关系软件（计算机程序设计）硬件（计算机系统设计）编码理论数据类型数据表示法数据的运算数据结构数据存取机器组织文件系统信息检索存储装置P4图1.4“数据结构”所处的地位数学代数系统数据组织算子关系软件68

1.3什么是数据结构

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改等操作的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。直观定义：《数据结构》课程是研究非数值计算的程序设计中计算机操作的对象以及它们之间的关系和操作的一门学科。

1.3什么是数据结构

69例1.1图书馆的书目检索系统自动化问题（表）001高等数学樊映川S01……002理论力学罗远祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02……..………………………………………高等数学001,003,…理论力学002,…线性代数004,…樊映川001,…华罗庚003,…栾汝书004,…L002,…S001,003,…图1.1图书目录文件示例书名索引表作者索引表分类号索引表例1.1图书馆的书目检索系统自动化问题（表）001高等数70例1.2计算机和人对弈问题（树）○○××○××○××○××○××○×××××××○○○○○例1.2计算机和人对弈问题（树）○○××○××○××○×71例1.3多叉路口交通灯的管理问题（图）EABCD(b)表示通路的图11111112223344(a)五叉路口EDABACADBABCBDDADBDCEAEBEC例1.3多叉路口交通灯的管理问题（图）EABCD(b)72例1.4电话号码查询问题的稀疏索引存储（表）姓氏地址张李姓名电话号码张三张林张洁李四李中………………例1.4电话号码查询问题的稀疏索引存储（表）姓氏地址张李73例1.5田径赛的时间安排问题（图）姓名项目1项目2项目3丁一A跳高B跳远E100米马二C标枪D铅球---张三C标枪E100米F200米李四D铅球F200米A跳高王五B跳远F200米---。。。。。。BACDEF表1。2参赛选手比赛项目表安排竞赛项目的数据结构模型例1.5田径赛的时间安排问题（图）姓名项目1项目2项目3741.4基本概念和术语1．数据

数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据是描述客观事物的符号，我们把一切能够被计算机识别并被计算机存储、处理的信息，包括文字、表格、图象等，都称为数据。是计算机化的信息。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。1.4基本概念和术语75表1-1个人书库表1-1个人书库762．结点结点也叫数据元素，它是组成数据的基本单位，是数据集合中的个体。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位(存取的最小单位)来考虑，故该数据由10个结点构成。数据结构课件773数据项：是数据不可分割的最小单位一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。3数据项：是数据不可分割的最小单位一般情况下，一个结点中含784．逻辑结构数据元素的集合以及定义在该集合上的关系。形式定义为一个二元组：

Data_Structure=(D,R)

其中：D是数据元素的有限集，R是D上关系的有限集。在表1-1所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了10个结点在表中排列的前后顺序。根据这种线性关系，可以看出表中第一本书是什么书，第二本书是什么书，等等。4．逻辑结构79

集合线性树图数据的逻辑结构示例

805．存储结构（物理结构）数据在计算机中的存储表示称为数据的存储结构。或者说是数据的逻辑结构在计算机中的映像（包括数据元素的映像和元素间关系的映像两部分）。在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。5．存储结构（物理结构）81两种基本的存储结构：数据元素之间的关系在计算机里有两种映像：顺序映像和非顺序映像。对应两种存储结构。

顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

链式存储结构：不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

两种基本的存储结构：826．数据处理数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算。进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的比例必将进一步增大。数据结构课件837.数据对象数据对象是性质相同的数据元素的集合，是一个数据的子集。7.数据对象数据对象是性质相同的数据元素的集合，是一个数据的848．数据结构（DataStructure）数据结构是研究数据元素（DataElement）之间抽象化的相互关系和这种关系在计算机中的存储表示（即数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构统称为数据结构（LogicalStructure），把数据的物理结构统称为存储结构（StorageStructure）。8．数据结构（DataStructure）859．数据类型数据类型是指程序设计语言中被操作对象可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。因此，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。9．数据类型86按“值”的不同特性,高级程序语言中的数据类型可分为两类:

非结构的原子类型。其值不可再分。如C语言中的基本类型：整型、实型、字符型、枚举型、指针类型和空类型。

结构类型。其值由若干成分按某种结构组成，可以分解，其成分可以是非结构的，也可以是结构的。如数组、结构体、共同体等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而结构类型可以看成有一种数据结构和定义在其上的一组操作组成。

抽象数据类型（简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的格式为：

ADT抽象数据类型名{数据对象：＜数据对象的定义＞结构关系：＜数据关系的定义＞基本操作：＜基本操作的定义＞}ADT抽象数据类型名按“值”的不同特性,高级程序语言中的数据类型可分为两类:87

8．算法

简单地说就是解决特定问题的方法和步骤（关于算法的严格定义，在此不作讨论,祥见1.5节）。特定的问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。8．算法88一般说来，在数值算法中主要进行算术运算，而在非数值算法中主要进行比较和逻辑运算。另一方面，特定的问题可能是递归的，也可能是非递归的，因而解决它们的算法就有递归算法和非递归算法之分。从理论上讲，任何递归算法都可以通过循环，堆栈等技术转化为非递归算法。数据结构课件891.5算法和算法的描述

1.5.1算法算法是执行特定计算的有穷过程。这个过程有5个特点：1.动态有穷性（有限性）：当执行一个算法时，不论是何种情况，在经过有限步骤后，这个算法一定要终止。2.明定性：算法中每条指令都必须是无二义性的。3.输入：具有0个或0个以上由外界提供的量。4.输出：产生1个或多个结果。5.可行性：通过算法得出一定的结果。注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本书中，我们只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。1.5算法和算法的描述

1.5.1算法90

1.5.2算法的描述

一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用类C语言作为描述算法的工具。现简单说明类C语言的语法结构如下：

1.5.2算法的描述91

1．预定义常量和类型：#defineTRUE1；#defineFALSE0；#defineOK1；#defineERROR0；#defineINFEASIBLE-1；#defineOVERFLOW-2；

数据结构课件922．函数的形式

[数据类型]函数名（[形式参数]）[形式参数说明；]{内部数据说明；执行语句组；}/*函数名*/

函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用“；”号分隔。可将函数中的表达式的值通过return语句返回给调用它的函数。最后的花括号“}”之后的/*函数名*/为注释部分，可舍去。

2．函数的形式933．赋值语句简单赋值：〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；〈变量〉++，它表示变量加1后赋值给变量；〈变量〉--，它表示变量减1后赋值给变量；3．赋值语句94成组赋值：

（〈变量1〉,〈变量2〉,〈变量3〉,…〈变量k〉）=（〈表达式1〉，〈表达式2〉,〈表达式3〉,…〈表达式k〉）;

〈数组名1〉[下标1…下标2]=〈数组名2〉[下标1…下标2]；数据结构课件95串联赋值：〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；条件赋值：〈变量名〉=〈条件表达式〉？〈表达式1〉：〈表达式2〉；交换赋值：〈变量1〉←→〈变量2〉，表示变量1和变量2互换；串联赋值：964．条件选择语句if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；情况语句switch（〈表达式〉）{case判断值1；语句组1；break；case判断值2；语句组2；break；……case判断值n；语句组n；break；[default：语句组n+1；]}注意：switchcase语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。4．条件选择语句976．输入、输出语句输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，特别当要输出字符数据时，用putchar函数实现。数据结构课件987．其他一些语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。8．注释形式

可用/*字符串*/或者单行注释或//文字序列。7．其他一些语句999．一些基本的函数如：max函数，用于求一个或几个表达式中的最大值；min函数，用于求一个或几个表达式中的最小值；abs函数，用于求表达式的绝对值；eof函数，用于判定文件是否结束；eoln函数，用于判断文本行是否结束。10.逻辑运算与运算&&:对于A&&B,当A的值为0时,不再对B求值；与运算||:对于A||B,当A的值为非0时,不再对B求值；9．一些基本的函数100例计算f=1！+2！+3！+…+n！用C语言描述。voidfactorsum（n）{intn,i,j,f,w；f=0；for（i=1;i〈=n；i++）{w=1；for（j=1;j〈=i；j++）w=w*j；f=f+w；}returnf；}上述算法所用到的运算有乘法、加法、赋值和比较，其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。所以，整个算法所作的乘法操作总数是：f（n）=1+2+3+…n=n（n+1）/2。例计算101

1．正确性

“正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：①程序不含语法错误；②程序对于几组输入数据能够得出满足规格说明要求的结果；③程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；④程序对一切合法的输入数据都能产生满足规格说明要求的结果。

1.5.3算法评价

设计一个好的算法应考虑以下几个方面：1．正确性1.5.3算法评价1022.可读性

可读性指算法容易被别人看懂并容易调试和修改。3.健壮性当输入数据非法时，能进行合理的反映和处理，或给出错误的提示并终止程序。2.可读性1034．运行时间运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。数据结构课件1045．占用的存储空间一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。分析一个算法所占用的存储空间要从各方面综合考虑。算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。5．占用的存储空间1056．简单性最简单和最直接的算法往往不是最有效的，但算法的简单性使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。数据结构课件1061.5.4算法效率度量的两个方面：时间复杂度和空间复杂度（1）时间复杂度：总的执行次数T（N)与规模N间的数量级关系．，这里用Ｏ来表示数量级．Ｔ（Ｎ）＝Ｏ（Ｆ（Ｎ））它表示随问题规模Ｎ增大，算法执行时间增长率与Ｆ（Ｎ）的增长率相同．Ｆ（Ｎ）算法的时间复杂性。在多数情况下,算法中关键操作执行的次数和包含它的语句的频度相同。语句的频度（frequencycount)指的是该语句重复执行的次数。所以，在实际应用时，用算法中语句的最大频度作为算法的时间复杂性1.5.4算法效率度量的两个方面：时间复杂度和空间复杂度107（2）空间复杂性Ｓ（Ｎ