《数据结构(C++版)》第1章 绪论.ppt

1、第1章 绪论,第1章 绪论,背景：1946年世界上第一台计算机诞生，至今已有60多年的历史。在这期间，计算机的发展和应用已经渗透到了人类社会的各个领域，计算机加工和处理的对象也从纯粹的数值发展到了字符、图像、声音等各种具有一定结构的数据。为了更好地设计程序，以提高计算机在解决复杂问题时的处理效率，研究数据的特性和数据之间存在的关系就显得至关重要。“数据结构”作为计算机科学与技术领域中的一门专业基础课，它专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。因此，“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬

2、件和计算机软件之间的一门核心课程，并将随着人类社会的各个领域中计算问题的不断深入研究而继续发展。,1.1 什么是数据结构,在计算机发展的初期，人们使用计算机主要用于科学计算所涉及的数据对象比较单纯，程序设计以算法为中心，而无需重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题显得越来越重要。这类问题涉及的数据结构更为复杂，无法用数学方程加以描述。为了编写出一个好的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系，以便设计出合理的数据结构。,当我们需要查找某个学生的有关情况的时候，或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某

3、种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。由这4张表构成的文件便是学生信息检索的数学模型。,例11 学生信息检索自动化问题。,图1.1 数学模型- - -线性表,在一个棋盘上放置4个皇后，使得任意两个皇后在行、列和斜方向上都不在一条线上。在四皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步就形成一个新的状态，整个试探过程形成了一棵隐含的

4、状态树，如图1.2所示 。,例12 四皇后问题,图1.2 四皇后问题的状态树,例1-3 教学计划编排问题,一个教学计划包含许多课程，在这些课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边 ，则表示课程i必须先于课程j进行。,C1,C9,C4,C2,C12,C10,C11,C5,C3,C6,C7,C8,图1.3 教学计划图,由上述例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而

5、是诸如表、树和图之类的数据结构。因此，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的课程。,1.2 基本概念,基本概念 （1）数据：信息的载体，是客观事物的符号表示。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如，实数、字符串、图像和声音等。 （2）数据项：具有独立的含义的最小标识单位。例如，字段、域、属性等。 （3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。例11学生信息表中的学生信息为一个数据元素，而学生信息中的每一项（如姓名、专业等）为一个数据项。,（4）数据对象：性质相同的数据元素的集合

6、，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。 （5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。 数据结构的形式化定义通常用一个二元组Data_Structure=(D, R)来表示，其中，D是数据元素的有限集（也即数据对象），R是D上关系的有限集。,1.2.1 数据的逻辑结构,数据的逻辑结构: 数据的逻辑结构是指数据元素以及它们相互之间的逻辑关系，数据的逻辑结构与数据的存储无关。 根据数据元素之间关系的不同特性，通常有4类逻辑结构： 集合，集合的逻辑结构中所有数据元素都属于同一个集合，所有数据元素杂

7、乱无章地聚集在一起，各个数据元素之间无任何联系； 线性结构，逻辑结构中的数据元素之间存在着一一对应的关系，各个数据元素之间通常有严格的先后次序关系； 树状结构，逻辑结构中的数据元素之间存在着一对多的关系，各个数据元素之间通常有严格的层次关系； 图状结构，逻辑结构中的数据元素之间存在着多对多的关系，各个数据元素之间均可能存在相互联系。,4类基本逻辑结构示意图,图1.4 4类基本逻辑结构的示意图,（c）树状结构,（a）集合结构,（b）线性结构,（d）图状结构,根据数据元素（结点）之间的相邻关系，数据的逻辑结构还可分为线性结构和非线性结构两大类： 线性结构的逻辑特征是，若结构是非空集，则有且仅有一个

8、开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱结点和一个直接后继结点。 线性表是一个典型的线性结构，栈、队列和串等都是线性结构； 非线性结构的逻辑特征是，一个结点可能有多个直接前驱结点和直接后继结点。 树和图都是非线性结构。,图示法表示数据的逻辑结构,对数据元素之间关系的描述是数据的逻辑结构，它可形式地用一个二元组表示为K=(D, R)，其中，D是由有限个结点所构成的集合，R是由有限个关系所构成的集合。有时为了直观起见，也用图示法来表示数据的逻辑结构。 逻辑结构与使用的计算机无关。例如，一批数据的逻辑结构K=(D, R)，其中，D=d1, d2, , d9，R=,，则该批数据的逻辑

9、结构如图1.5所示。对于R中包含多种关系的情况，也可用类似的方法描述。,图1.5 数据的逻辑结构,数据结构包括数据的逻辑结构和数据的物理结构。 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。 数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。,1.2.2 数据的存储结构,数据的存储结构 数据的存储结构（物理结构）是指数据在计算机中的存储表示，它包括数据元素的表示和

10、关系的表示。 数据的存储结构有以下4种。 顺序存储。该存储方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。该方法通常借助于高级程序设计语言中的数组来描述。 链式存储。该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构。该方法通常借助于高级程序设计语言中的指针类型来描述。 索引存储。该方法通常在存储结点信息的同时，还要建立附加的索引表。 散列存储。该方法根据结点的关键字直接计算出该结点的存储地址。,数据的逻辑结构和物理结构（存储结构）是密

11、切相关的两个方面，任何算法的设计都取决于选定的数据（逻辑）结构，而算法的实现则依赖于所采用的存储结构。 1.2.3 数据的运算 数据的运算是对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。在数据结构中，运算不仅是加、减、乘、除等运算，大多数的运算都涉及算法的实现问题。算法的实现与数据的存储结构是密切相关的。,1.3 数据类型和抽象数据类型,数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称，通常它可看作是高级程序设计语言中已经实现的数据结构。 在高级程序设计语言中，数据类型可分为两类： 1、原子类型。原子类型的值是不可分解的。比如，C语言中的整型、

12、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。 2、结构类型是由若干成分按某种结构组成的，是可分解的，并且它的成分既可以是非结构的，也可以是结构的。,抽象数据类型（abstract data type，ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，也即，不论其内部结构如何变化，只要它的数学特性不变，都不会影响其外部的使用。 抽象数据类型可表示为一个三元组（D, R, P），其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象

13、数据类型： ADT 抽象数据类型名 数据集合： 数据关系： 数据操作： ADT 抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为： 数据操作名(参数表) 输入： 返回结果：,1.4 算法和算法分析,算法（algorithm）：为了解决某一类问题而设计的一个有限长的操作序列。一个算法必须满足以下5个重要特性。 有穷性。算法对于合法的任意输入值，在执行有限步之后一定能结束。 确定性。算法中的每一个操作必须有确切的含义，无二义性，并在任何条件下，算法都只有一条执行路径。 可行性。算法中的所有操作都可通过已经实现的基本运算有限次地实现。 输入。算法具有0或多个输入，这些输

14、入为一组特定的数据对象集合。 输出。算法具有一个或多个输出，它是一组与“输入”有确定关系的量值。,1.4.1 算法的描述,算法可以使用各种不同的方法来描述： 最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读。缺点是不够严谨。 可以使用程序流程图、NS图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能直接在计算机上执行，若要将它转换成可执行的程序，还有一个编程的问题。 可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而且不太直观，常常需要借助于注释才能使人看明白。 为了解决理解与执行这两者之间的矛盾，人们常常使用

15、一种称为伪码语言的描述方法来进行算法描述。,用流程图表示算法,流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解,起止框,输入输出框,处理框,判断框,流程线,连接点,注释框,m被2整除,是,否,开始,判断一个数是否偶数的算法,输入m的值,输出m是偶数,输出m不是偶数,结束,用N-S流程图表示算法,N-S流程图用以下的流程图符号：,顺序结构,选择结构,循环结构,判断一个数是否偶数的算法,1.4.2 算法设计的要求,正确性（correctness）。算法的执行结果应当满足预先规定的4个要求：1）程序不含语法错误；2）程序对于几组输入数据能够得出满足规格说明要求的结果；3）程序对于

16、精心选择的典型、苛刻且带有刁难性的几组输入数据能得出满足规格说明要求的结果；4）程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 可读性（readability）。算法应有助于人们阅读、理解和调试，晦涩难懂的算法可能隐藏较多的错误，难以调试和修改。 稳健性（robustness）。当输入不合法的数据时，算法能够做出适当的反应或处理，不至于产生莫名其妙的结果。同时，处理出错的方法应该是返回一个表示错误或错误性质的值，并终止程序的执行，以便在更高的抽象层次上进行处理。 时空效率（efficiency）。要求算法执行的时间应该尽可能短、算法执行过程中占用的存储空间应该尽可能少。时空要求与求

17、解问题的规模有关，两者通常相互矛盾，因此，应在它们之间进行平衡。,1.4.3算法分析,算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，主要考察算法的时间效率和空间效率，以便比较和改进算法。通常，在算法的运算空间较为充裕的情况下，更多地关注算法的时间复杂度。 1、时间复杂度 算法执行的时间可通过依据该算法编制的程序在计算机上从开始运行到结束运行所消耗的时间来度量，也就是算法中每条语句的执行时间之和。 估算运行时间有两种可行的办法。 第一种是操作计数法，首先选择一种或多种基本操作，然后确定这些操作分别执行了多少次。一般情况下，操作的执行次数和包含它的语句的频度相同。语句的频度指的是该语句

18、重复执行的次数。 第二种是步骤计数法，确定算法总的执行步数，要统计算法或函数中的所有时间开销。,算法的时间复杂度分析,我们选用操作计数法，这种方法是否成功取决于识别基本操作的能力。 算法中基本操作重复执行的次数是规模n的函数T(n)。 许多时候要精确地计算T(n)是困难的，我们引入渐近时间复杂度在数量上估计算法的执行时间。一般而言，算法中基本操作的频度是问题规模n（如算法所处理的矩阵的阶数，线性表的长度）的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)，它表示随问题规模n的增大，算法的执行时间增长率与f(n)的增长率相同，称为算法的渐近时间复杂度（asymptotic time c

19、omplexity），简称时间复杂度。 一般定义为：当且仅当存在正整数c和n0，使得T(n) c f(n)对所有的n n0成立，则称该算法的渐近时间复杂度为T(n)=O(f(n)。,例1-4 分析算法时间复杂度,下面是一个nn阶矩阵A自乘得到B=AA的算法，试分析其时间复杂度。 int Ann； /全局数组 void mtxmlt( ) int Bnn； /语句频度 for (int i=0；in；i+) /n+1 for(int j=0；jn；j+) /n*(n+1) Bij=0； /n*n for(int k=0；kn；k+) /n*n*(n+1) Bij=Bij+Aik*Akj；/n*n*n ,时间复杂度T(n)=n+1+n(n+1)+nn+n2(n+1)+nnn=2n3+3n2+2n+1。当n时，T(n) n3，故算法时间复杂度的数量级为O(n3)。 在需要大O表示的任何分析中，低阶项