软件开发技术基础 第4版 课件 第2章 数据结构及其应用

数据结构

——基本概念及线性数据结构基本概念1．数据（data）

数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。

2．数据元素（dataelement）

数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位西安交通大学计算机教学实验中心赵英良2基本概念3．数据结构

是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构数据的存贮结构对数据所施加的运算。西安交通大学计算机教学实验中心赵英良3基本概念3．数据的逻辑结构西安交通大学计算机教学实验中心赵英良4线性结构——通迅录、成绩单、花名册树形结构——电子字典、家谱、目录图状结构——交通线路、通信网络基本概念3．数据的存储结构西安交通大学计算机教学实验中心赵英良5(1)顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存贮所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮（略） (4)散列存贮（略）基本概念3．算法分析西安交通大学计算机教学实验中心赵英良61）时间复杂度一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化2）空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。线性数据结构

线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋，an无后继。线性表的存储结构主要有顺序存储结构和链式存储结构两种。西安交通大学计算机教学实验中心赵英良7线性数据结构：顺序表采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*d

西安交通大学计算机教学实验中心赵英良8顺序表主要算法判定线性表是否为空求线性表的长度在表中第i个位置插入新元素x

在表中删除第i个元素在表中查找某个元素西安交通大学计算机教学实验中心赵英良9线性数据结构：栈栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。西安交通大学计算机教学实验中心赵英良10a1a3a2进栈出栈top线性数据结构：栈的主要操作创建空栈。进栈(push)操作:在栈顶插入元素。出栈(pop)操作:在栈顶删除元素。读栈顶元素:只是读出栈顶元素，并不改变栈内元素。

西安交通大学计算机教学实验中心赵英良11线性数据结构：循环队列队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。循环队列的基本操作方式为：入队列时先执行rear=(rear+1)%M，再将新元素在rear指示位置加入；出队列时先执行front=(front+1)%M，再将下标为front的元素取出。

西安交通大学计算机教学实验中心赵英良12线性数据结构：循环队列西安交通大学计算机教学实验中心赵英良13将队空和对满的条件加以区分:

队空条件:

front=rear

队满条件:(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循环队列空(b)非空循环队列(c)循环队列满线性数据结构：单链表西安交通大学计算机教学实验中心赵英良14单链表用一组地址任意的存储单元存放线性表中的数据元素。由于逻辑上相邻的元素其物理位置不一定相邻，为了建立元素间的逻辑关系，需要在线性表的每个元素中附加其后继元素的地址信息。这种地址信息称为指针。附加了其他元素指针的数据元素称为结点。带头结点单链表的逻辑结构西安交通大学计算机教学实验中心赵英良15为了能顺次访问每个结点，需要保存单链表第一个结点的存储地址。这个地址称为线性表的头指针，本节用head表示。为了操作上的方便，可以在单链表的头部增加一个特殊的头结点。头结点的类型与其他结点一样，只是头结点的数据域为空。head

a1a2an∧带头结点的单链表带头结点单链表的逻辑结构西安交通大学计算机教学实验中心赵英良16head38数据域指针域38229486

a2

86…

…

94…

…

a3

NULL

a1

22

存储地址单链表存储结构示意图单链表中指针移动西安交通大学计算机教学实验中心赵英良17图2单链表指针后移一步ai2167ai+17650ai-192579257p=p.next2167pp

图1带头结点的空链表head∧∧单链表插入结点西安交通大学计算机教学实验中心赵英良18(a)第1步,生成结点s(b)第2步，s结点指向结点ai

(c)第3步，结点ai-1指向s结点图3

在单链表中插入结点x

pai-1

xai

sp.next=s③ai-1

ai

px

s②s.next=p.nextai-1

ai

px

s①单链表删除结点西安交通大学计算机教学实验中心赵英良19删除第i个结点，需进行如下操作：

①若第i个结点存在则找到第i和第i-1个结点的指针p和q②通过语句q.next=p.next将第i-1个结点的指针域赋值为第i+1个结点的指针，将第i个结点从链表中断开。③释放第i个结点所占空间以便于重用。qpai-1aiai+1q.next=p.next

20精勤求学敦笃励志果毅力行忠恕任事西安交通大学计算机教学实验中心赵英良查找和排序查找基本概念查找表:

由同一类数据构成的用于查找的集合称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。

22查找基本概念静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。

23查找基本概念平均查找长度：

为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：24其中：在等概率条件下（

Pi=1/n）这时平均查找长度为：1．顺序查找顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。25顺序表查找的平均查找长度为：2．折半查找(也称二分查找)26假定元素按关键字的值升序排列，折半查找的思路是将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。

2．折半查找(也称二分查找)27折半查找算法的步骤描述如下：①设置查找区间初值，设下界low=0，设上界high=length-1②若low≤high则计算中间位置mid=(low+high)/2③若key<data[mid]，则设high=mid-1并继续执行步骤②；若key>data[mid]，则设low=mid+1并继续执行步骤②；若key=data[mid]则查找成功，返回目标元素位置mid+1

（位置从1计数）。④若当low=high时，key!=data[mid]则查找失败，返回0。

2．折半查找(也称二分查找)西安交通大学计算机教学实验中心28对给定有序数列{5，6，11，17，21，23，28，30，32，40}进行半查找算法，查找关键字值为30的数据元素。则查找过程如下：第1次：{5，6，11，17，21，23，28，30，32，40}

low=0mid=(0+9)/2=4high=9第2次：{5，6，11，17，21，23，28，30，32，40}

low=5mid=7high=9排序基本概念

排序的定义为：假设含n个记录的序列为{R1，R2，…，Rn}，其相应的关键字序列为{K1,K2,…，Kn}。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1≤Kp2≤…≤Kpn，按此固有关系将最初的记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。西安交通大学计算机教学实验中心29排序基本概念

排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法

30排序基本概念

内部排序方法有很多类型。按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复杂度大约为O(nlog2n)。西安交通大学计算机教学实验中心311、直接插入排序

西安交通大学计算机教学实验中心32初始状态：[35] 22 16 19 22第1趟：[22 35] 16 19 22第2趟：[16 22 35] 19 22第3趟：[16 19 22 35] 22第4趟：[16 19 22 22 35]直接插入排序执行过程在序列{35，22，16，19，22}上应用插入排序的过程，为了对序列中相同记录加以区别，使用了下划线。

2、简单选择排序西安交通大学计算机教学实验中心33在序列{35，22，16，19，22}上应用简单选择排序的过程。

初始状态：[35 22 16 19 22]

第1趟：[16] [22 35 19 22]

第2趟：[16 19] [35 22 22]

第3趟：[16 19 22]

[35 22]

第4趟：[16 19 22 22] [35]3、冒泡排序西安交通大学计算机教学实验中心34基本思路：第一趟排序对全部记录R1，R2，…，Rn自左向右顺次两两比较，若Rk大于Rk+1则交换Rk和Rk+1(k=1,2,…,n-1)，第一趟排序完成后Rn成为序列中最大记录。第二趟排序对序列前n-1个记录采用同样的比较和交换方法，第二趟排序完成后Rn-1成为序列中仅比Rn小的次大的记录。第三趟排序对序列前n-2个记录采用同样处理方法。如此做下去，最多做n-1趟排序，整个序列就排序完成。3、冒泡排序西安交通大学计算机教学实验中心35

下图显示了在序列{35，22，16，19，22}上应用冒泡排序的过程。

初始状态：3522 16 19 [22

第1趟：2216 19 22 [35]

第2趟：1619 22 [22

[35]

第3趟：1619 [22

22 [35]

第4趟：16[19

22 22 [35]4、快速排序西安交通大学计算机教学实验中心36任取待排序序列中某个记录S(例如第一个记录)作为基准，经过比较和交换，将整个序列划分为如下形式：{左侧子序列}S{右侧子序列}并且满足：

①左侧子序列中所有记录的关键字都小于或等于S的关键字。②右侧子序列中所有记录的关键字都大于或等于S的关键字。然后分别对左右两个子序列重复执行上述过程，直到排序完成4、快速排序西安交通大学计算机教学实验中心37

在{22,35,27,16,45,19,22}上应用划分算法（即一趟快速排序）4、快速排序西安交通大学计算机教学实验中心38

当22的位置已经确定后，只需对{19，16}和{27,45,35,22}分别排序即可。可分别取19和27为基准元素。

{22，35，27，16，45，19，22}

{19，16}22{27，45，35，22}

{16}19

22{22}27{35，45}

1619222227

35{45}

39精勤求学敦笃励志果毅力行忠恕任事西安交通大学计算机教学实验中心赵英良非线性数据结构

—树与图树的递归定义树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。2）除根以外的集合可划分为m个不相交子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。

西安交通大学计算机教学实验中心41GACFDEB树的一般形式与树相关的术语结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。结点的度：结点拥有的非空子树的个数。树的度：树中所有结点的度的最大值。叶子结点：没有非空子树的结点。分支结点：至少有一个非空子树的结点。孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。西安交通大学计算机教学实验中心42与树相关的术语兄弟结点：具有相同父结点的结点互为兄弟结点。结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。树的深度：树中结点所在的最大层次。有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。森林：由零棵或有限棵互不相交的树组成的集合。

西安交通大学计算机教学实验中心43二叉树的定义二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。特殊形式的二叉树西安交通大学计算机教学实验中心44AFC满二叉树GDBEAC完全二叉树DBE二叉树有下列重要性质在二叉树的第k层上至多有2k-1个结点(k≥1)深度为h的二叉树上至多含2h-1个结点(h≥1)包含n(n>0)个结点的二叉树总的分支数为n-1任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1具有n个结点的完全二叉树的深度为[log2(n)]+1西安交通大学计算机教学实验中心45二叉树有下列重要性质6.若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：①若i=1，则该结点是二叉树的根，无父结点。否则，编号为[i/2]的结点为其父结点；②若2i>n，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；③若2i+1>n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。西安交通大学计算机教学实验中心46二叉树的链式存储西安交通大学计算机教学实验中心47二叉树的链式存储ABC∧∧D∧∧E∧∧利用结点形式存储的树称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。

二叉树的遍历西安交通大学计算机教学实验中心48三种主要的遍历算法——先序遍历、中序遍历和后序遍历。

1）先序遍历：首先访问根结点，然后按先序遍历方式访问左子树，最后按先序遍历方式访问右子树。2）中序遍历：首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。3）后序遍历：首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。图的基本概念西安交通大学计算机教学实验中心49图是由顶点集合及顶点间的关系集合组成的一种数据结构。一般记作Graph＝(V,E)。其中V是顶点的有限非空集合；E是顶点之间关系的有限集合。•

边：顶点x到y的一条双向通路，称为边，用(x,y)表示。•

弧：顶点x到y的一条单向通路，则称为弧，用<x,y>表示。•

邻接点：如果(x,y)是图中的一条边，则称x与y互为邻接点；如果<x,y>是图中的一条弧，则称y为x的邻接点。•

顶点的度：一个顶点v的度是与它相关联的边的条数。图的基本概念西安交通大学计算机教学实验中心50•无向图：若图是由一些顶点和边构成则称之为无向图。•

有向图：若图是由一些顶点和弧构成则称之为有向图。•

权：某些图的边或弧具有与它相关的数，称之为权。这种带权图叫做网络。0132528130123410234(a)无向图

(b)有向图

(c)网络

图的基本概念西安交通大学计算机教学实验中心51•路径：在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1、vp2、…、vpm到达顶点vj。则称顶点序列(vi，vp1，…，vpm，vj)为从顶点vi到顶点vj的路径。若路径上各顶点均不互相重复，则称这样的路径为简单路径。•路径长度：非带权图的路径长度是指此路径上边或弧的条数，带权图的路径长度