数据结构课件

数据结构数据结构是计算机软件和计算机应用专业的核心课程之一，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。数据结构主要研究数据表示与存储的方法、抽象的逻辑结构及其上定义的各种基本操作。数据的逻辑结构常常采用数学描述的抽象符号和有关的理论。如使用串、表、数组、图等结构和理论来表示数据在存储时的逻辑结构，研究这些结构上定义的各种操作。本章内容7.1数据结构的概念7.2几种典型的数据结构7.3查找7.4排序7.1数据结构的概念在系统地学习数据结构知识之前，先对一些与数据结构相关的基本概念和术语赋予确切的含义。数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是指整数、实数或复数等，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、八皇后问题中状态树的一个状态、教学计划编排问题中的一个顶点等，都被称为一个数据元素。一个数据元素可由若干个数据项（DataItem）组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；数据对象（DataObject）或数据元素类（DataElementClass）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。

在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。

数据结构（DataStructure，简称DS）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

根据数据元素间关系的不同特性，通常有下列四类基本的结构：⑴集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。⑵线性结构。该结构的数据元素之间存在着一对一的关系。⑶树型结构。该结构的数据元素之间存在着一对多的关系。⑷图型结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。

（a）集合结构

（b）线性结构

（c）树型结构

（d）图形结构图7.1

四类基本结构的示意图表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构（全序关系），树(偏序或层次关系)和图（局部有序(weak/localorders)）是非线性结构。

一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。因此，在形式上，数据结构通常可以采用一个二元组来表示。数据结构的形式定义为：数据结构是一个二元组Data_Structure＝（D，R）其中，D是数据元素的有限集，R是D上关系的有限集。数据结构包括数据的逻辑结构和数据的物理结构两部分。数据的逻辑结构是从具体问题抽象出来的数学模型，它与数据的存储无关。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称存储结构。在计算机中信息表示的最小单位是二进制的一位，我们用若干位组合起来形成的一个位串表示数据元素，通常这个位串称为元素（Element）或结点（Node）。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域（DataField）。元素或结点可看成数据元素在计算机中的映象。即数据结构DS的物理结构P对应于从DS的数据元素到存储区M（维护着逻辑结构S）的一个映射：P：(DS)-->M。数据结构主要研究以下三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据的存储结构可采用顺序存储或链式存储的方法。顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存储方法。7.2几种典型的数据结构7.2.1线性表线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如前面提到的学生情况信息表就是一个线性表，表中每一个记录对应一名学生。线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：

(a1，a2，…ai-1，ai，ai+1，…an)，其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai

的直接前趋，ai+1称为ai

的直接后继。就是说：对于ai，当i=2，...，n时，有且仅有一个直接前趋ai-1.，当i=1，2，...，n-1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有前趋，an是最后一个元素无后继。需要说明的是：ai为序号为i的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型。线性表的存储方式共有两种：顺序存储和链式存储。顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。01…i-1i…n-1a1a2…ai-1aiai+1…andata…maxaize1-1,

…last这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。7.2.2堆栈1.栈的定义

栈是一种特殊的线性表，这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。2.栈的数学性质假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(LastInFirstOut)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。a1a2an-1an…栈底栈顶入栈出栈7.2.3队列1．队列的定义队列也是一种特殊的线性表。对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(FirstInFirstOut)表，简称FIFO表。2．队列的数学性质

假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。a1a2a3…an出队列入队列队头队尾7.2.4树线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、城市交通等。树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非空树T中:：（1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。在树的定义中用了递归概念，即用树来定义树。树的定义还可形式化的描述为二元组的形式：

T＝（D，R）其中D为树T中结点的集合，R为树中结点之间关系的集合树是很好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。

树具有下面两个特点：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。

G

ADBCFEF

AHEDBCEDCB

AEFGFGDCB

A

(a)一棵树结构(b)一个非树结构

(c)一个非树结构(d)一个非树结构

二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态：Φ左子树右子树左子树右子树

(a)

(b)

(c)

(d)(e)7.2.5图图状结构是一种比树形结构更复杂的非线性结构。在树状结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。1．图的定义图(Graph)是由非空的顶点集合和描述顶点之间关系的边（或者弧）的集合组成，其形式化定义为：

G＝（V，E）

V＝{vi|vi∈dataobject}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}V1V2V3V4V5V4V3V2V12．图的相关术语（1）无向图。在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。（2）有向图。在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

（3）顶点、边、弧、弧头、弧尾。图中，数据元素vi称为顶点(vertex)；P(vi,vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi,vj）来表示，称顶点vi和顶点vj互为邻接点，边（vi,vj）依附于顶点vi与顶点vj；（4）无向完全图。在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

（5）有向完全图。在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。（6）稠密图、稀疏图。若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。

（7）顶点的度、入度、出度。顶点的度（degree）是指依附于某顶点v的边数，通常记为TD(v)。在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点为终点的弧的数目。记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。有TD(v)=ID(v)＋OD(v)。

可以证明，对于具有n个顶点、e条边的图，顶点vi的度TD(vi)与顶点的个数以及边的数目满足关系：所有顶点度数之和等于边数的两倍（握手定理）。即：2e=∑ni=1TD(Vi)

（8）边的权、网图。与边有关的数据信息称为权（weight）。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图或网络（network）。V1V3V4V5V27.3查找计算机、计算机网络使信息查询变得更快捷、方便、准确。但要从计算机、计算机网络中查找特定的信息，就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释，就需要存储类似英汉字典这样的信息表，以及对该表进行的查找（Searching）操作。学号姓名性别

|||200109832001098420010985|||

|||

张三李四王五

|||

|||男男女

|||来源总分录取专业

|||包头一中保定三中易县中学

|||

|||593601598

|||

|||计算机计算机计算机

|||年月日

|||198219821983|||

|||110901|||

|||051225|||出生年月1.数据项(也称项或字段)项是具有独立含义的标识单位，是数据不可分割的最小单位。如表中“学号”、“姓名”、“年”等。项有名和值之分，项名是一个项的标识，用变量定义，而项值是它的一个可能取值，表中“20010983”是项“学号”的一个取值。项具有一定的类型，依项的取值类型而定。2.组合项由若干项、组合项构成，表中“出生日期”就是组合项，它由“年”、“月”、“日”三项组成。3.数据元素（记录）数据元素是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。

4.关键字关键字(Key)是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键字，称为主关键字(PrimaryKey)；

5.查找表是由具有同一类型（属性）的数据元素（记录）组成的集合。分为静态查找表(StaticSearchTable)和动态查找表(DynamicSearchTable)两类。

6.查找按给定的某个值A，在查找表中查找关键字为给定值A的数据元素（记录）。7.3.2查找的方法1顺序查找又称线性查找，是最基本的查找方法之一。其查找方法为：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键字，则查找失败，给出失败信息。2折半查找折半查找的思想为：在有序表（表中的元素按递增或递减的顺序排列）中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。3分块查找又