数据结构概念---中南大学教程

1、数据结构的概念美国计算机科学家 Don aid Ervin Kn uth首次提出了数据结构和算法的概念，并在他所著 的计算机程序设计艺术第 1卷基本算法中首次较系统地阐述了数据的逻辑结构、存储 结构及其操作。随后，美国的一些大学开始设立与数据结构相关的课程。同时，结构化程序 设计逐渐成为当时程序设计的主流方法，人们也越来越重视数据结构。各种版本的数据结构著作也相继出现。数据结构作为计算机科学的一门分支学科，主要研究非数值计算的程序设计问题中计算机的操作对象、对象之间的关系和操作等。为了编写出“好”的程序，必须分析待处理对象 的特性及各处理对象之间存在的关系。数据结构的内容包括 3个层次的5个“

2、要素”，如表1-1所示。其中的3个层次分别为 抽象、实现与评价。通过抽象，舍弃数据元素的具体内容，就得到逻辑结构表示，通过分解 将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到基本操作的定义。上述两个 方面的结合将问题变换为数据结构，这是一个从具体（即具体问题）到抽象（即数据结构） 的过程。最后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务，而这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练掌握这两个过 程是数据结构课程在专业技能培养方面的基本目标。在这个过程中需要对不同结构及其实现的性能进行评价，从而获得最佳实践方案。实现存储结构算法评价不同数据

3、结构的比较艮算法分析针对要处理的问题，设计最有利于操作系统处理的数据结构时需考虑下列因素。数据的数量。数学系统设计）.算子关系 数据类型数据表示法数据的操作 数据结构硬件（计算机图1-1数据结构的地位代数系统编码理论文件系统存储装置数据存取数据组织器组织信息检索软件（计算机程序设计）（2）数据的使用次数和方式。（3）数据的性质是动态的还是静态的。（4）数据结构化后需要多大的存储空间。（5）存取结构化后的数据所需花费的时间。（6）是否容易程序化。目前，“数据结构”已经是计算机科学及相 关专业的一门专业基础课。它与数学、计算机硬件和计算机软件之间的关系如图1-1所示。在计算机科学中，数据结构不仅是

4、一般程序设计的基 础，而且是设计和实现编译程序、操作系统以及 数据库系统等大型程序的基础。所有的计算机系 统软件和应用软件都要用到各种类型的数据结构。因此，学好“数据结构”这门课程，对学习计算机专业的其他课程都是十分有益的。为什么要学习数据结构在计算机发展的初期， 人们使用计算机的主要目的是处理数值计算问题。使用计算机解决具体问题一般需要经过以下几个步骤： 首先从具体问题抽象出适当的数学模型， 然后设计 或选择解此数学模型的算法，接着编写程序并进行调试、测试，直至得到最终的解答。由于最初涉及的运算对象是简单的整型、实型或布尔型数据，所以程序设计者的主要精力集中于程序设计的技巧上，而无需重视数据

5、结构。随着计算机应用领域的扩大和软硬件的 发展，非数值计算问题显得越来越重要。据统计，当今处理非数值计算问题占用了90%A上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。著名的瑞士计算机科学家沃思(N.Wirth )教授曾提出：算法+数据结构=程序程序设计的实质是对实际问题设计/选择好的数据结构和好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。例1-1 电话号码查询问题。编写一个查询某个私人电话号码的程序。要求任意给出的 一个姓名，若该人有电话号码，则迅

6、速找到其电话号码；否则指出该人没有电话号码。要解决此问题首先需构造一张电话号码登记表。表中每个结点存放两个数据项：姓名和电话号码。能否写出好的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结 点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是遍历 整个表均没有找到为止。这种查找算法对一个有少量私人电话的区域或许是可行的，但对 一个有成千上万私人电话的城市就不适用了。若这张表是按姓氏排列的，则可另建一张姓 氏索引表，采用如图 1-2所示的存储结构。查找时先在左边的索引表中查对姓氏，然后根 据索引表中的地址到右边的电话号码登记表中核查姓名，这样查找登记表时就无

7、需查找其他姓氏的名字了。因此，在这种新的结构上产生的查找算法就更加有效。诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文 档管理的数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系。这类数学 模型可称为线性的数据结构。姓名电话号码张二地址张明张 m 李张志a H.坐文 r李真图1-2电话号码的索引存储例1-2 四皇后问题，即在一个 4 4的棋盘上放置4个皇后，使得任意两个皇后在行、 列和斜方向上都不在一条线上。在四皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状

8、态开始,一步步地进行试探，每试探一步形成一种新的状态，整个试探过程形成了一棵隐含的状态树， 如图1-3所示。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。图1-3四皇后问题中隐含的状态树例1-3田径赛的时间安排问题。假设某校的田径选拔赛共设6个项目，即跳高、跳远、标枪、铅球、100米短跑和200米短跑，规定每个选手至多参加3个项目的比赛。现有 5名选手报名参赛，选手所选择的项目如表 1-2所示。要求设计一个竞赛日程安排表，使得在尽可能短的时间内完成比赛。（1）首先选择一种合适的数据结构，如图1-4所示。图中顶点代表竞赛

9、项目，让代表所连接的两个竞赛项目的比赛时间不发生冲突，因此选手选择的项目中应该两两有边相连。（2）竞赛项目的时间安排问题可以抽象为对无向图进行“着色”操作，即用尽可能少的颜色给图中每个顶点着色，使得任意两个有边连接的相邻顶点具有不同的颜色。每一种颜色表示一个比赛时间，同一种颜色表示可以安排在同一时间进行比赛。由此可得，只要安排4个不同的比赛时间即可。比如，在时间1比赛跳高（A）和标枪（C）,在时间2比赛跳远（B）和铅球（D）,在时间3和时间4分别比赛表1-2参赛选干比赛项目表100 米（E）和 200 米（F）。项目1项目2项目3丁一跳高跳远100米马刚标枪铅球张明标枪100米200米李远强铅

10、球200米跳高TV7跳远200米K1-4安排竞赛硕目的数据姑杓模型由以上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。相应地解决问题的一个关键步骤是设计合适的数据结构表示该 问题，然后才能写出有效的算法。有关概念和术语在系统地学习数据结构知识之前，你应该先了解一些基本概念和术语。数据（data ）是信息的载体，能够被计算机识别、存储和处理。它可以是数值数据；也 可以是非数值数据，如字符、文字、图形、图像和语音等。数据元素（data element ）是数据的基本单位。在不同的条件下，数据元素又可称为元 素、结点、顶点和记录等。一个数据元素可由若

11、干个 数据项（data item ）组成。例如，学生信息表中的一个记录 可以包括学号、姓名、性别、籍贯、出生年月和成绩等数据项。数据项可以分为两种：一种 叫做原子项（如学生的性别、籍贯等），是数据处理时不能再分割的最小单位；另一种叫做组合项（如学生的成绩，可以再划分为数学、物理和化学等更小的项）。数据对象（data object ）或数据元素类（data element class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），是数据元素类的一个实例，属于同一个数据元素类。例如，例1-3中，所有的顶点集合是一个数据元素类，顶点 A和顶点B各自代

12、表一个运动项目，是该数据元素类中的两个实例。数据结构（data structure）是指互相之间存在着一种或多种关系的数据元素的集合。根据数据元素之间关系的不同特性，通常有下列4类基本结构。集合结构。其中所有的数据元素都属于同一个集合。集合是元素关系极为松散的一种结构，因此也可用其他结构来表示。线性结构。数据元素之间存在着一对一的关系。树型结构。数据元素之间存在着一对多的关系。图形结构。数据元素之间存在着多对多的关系。图形结构也称作网状结构。图1-5表示了上述4类基本结构的示意图。(b)线性结构图1-54类基本结构由此可知，一个数据结构具有两个要素：一个是数据元素的集合，另一个是关系的集合。

13、因此在形式上数据结构可以采用一个二元组来表示。数据结构的形式定义为：Data_Structure= ( D R其中，D是数据元素的有限集，R是D上关系的有限集。例如，复数可被定义为一种数据结构Complex = ( D, R)D = x | x是实数R = v x , y > | x , y Dx称为实部，y称为虚部=。研究数据结构主要是研究数据的逻辑结构、存储结构及其相关操作。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，与数据的存储无关。数据结构在计算机中的标识(或映像)称为数据的存储结构(物理结构)，它表示数据结构在计算机中的实现方法，即数据结构中元素及元素间关系的表示。操

14、作是数据结构对外表现的行为或方法。1. 数据的逻辑结构数据的逻辑结构描述数据元素之间的逻辑关系，分为线性结构和非线性结构。 线性结构的逻辑特征是，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。例如，线性表、栈、队列和串等都是线性结构。非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。例如，数组、广义表、树和图等都是非线性结构。2. 数据的存储结构一般来说，一个存储结构包括以下3个主要部分。存储结点：在不致混淆时简称为结点，每个存储结点存放一个数据元素。 数据元素之间的关联方式表示。附加设施，如为便于运算实现而设置的“哑结点”

15、等。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。 一般可用以下4种基本存储方法。(1)顺序存储方法。该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里， 结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 顺序存储方法为使用整数编码访问数据结点提供了便利。顺序存储结构中没有存储其他附加的信息，所以也称为紧凑存储结构。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。(2) 链接存储方法。该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构，通常

16、借助于程序语言的指针类型描述。链接存储方法适用于那些需要经常进行增删结点的复杂数据结构。(3) 索引存储方法。该方法是顺序存储方法的一种推广，用于大小不等的数据结点的顺序存储。通过建造一个由整数域映射到存储地址域的函数，把整数索引值映射到结点的存储地址，从而形成一个存储一串指针的索引表，每个指针指向存储区域的一个数据结点。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则称该索引表为稠密索引(dense index )。若一组结点在索引表中只对应一个索引项，则称该索引表为稀疏索 引(spare in dex)。索引项的一般形式是：关键字地址关键字是能唯一标识一个结点的数据项。稠密索引中索引项的地址指示结点所在的存储位置，稀疏索引中索引项的地址指示一组结点的起始存储位置。(4) 散列存储方法。作为索引存储方法的一种延伸和扩展，散列存储方法利用散列函数 进行索引值的计算，然后通过索引表求出结点的指针地址。以上4种基本存储方法既可单独使用，