《计算机导论》课件-计算机导论第四章

第四章数据结构和算法4.1数据结构4.2算

法

4.1数据结构4.1.1线性结构4.1.2树形结构4.1.3图状结构

4.1数据结构数据结构是计算机科学与技术的一个分支。它主要研究数据的逻辑结构，物理结构以及数据结构上的基本数据运算：（1）数据的逻辑结构。数据的逻辑结构是指数据元素之间的逻辑关系，它与数据在计算机的存储方式无关，数据的逻辑结构分为线性结构、树形结构和图形结构，其中树形结构和图形结构又统称为非线性结构。下面分别介绍这三种数据结构：线性结构

数据元素之间存在前后依次相邻的逻辑关系，除第一个元素和最后一个元素外，其余元素都有唯一一个直接前驱和直接后继。即元素之间是一对一的关系。如图4.1所示，线性结构包括线性表、栈、队列、数组以及串等。

4.1数据结构树形结构

数据元素之间存在的顺序关系，除了第一个根结点外，其余结点都有唯一的一个直接前驱，但可以有零个或多个后继结点。即元素之间是一对多的关系。如图4.2所示，树形结构包括二叉树、森林等。

4.1数据结构图形结构

也叫网状结构，其每个结点都可以有多个前驱和多个后继结点。数据元素之间是多对多的关系，如图4.3所示

4.1数据结构（2）数据的物理结构。

数据的物理结构是指数据在计算机中是如何存储的，即数据的逻辑结构在计算机存储上的实现。它有多种不同的方式，其中顺序存储结构和链式存储结构是最常用的两种存储方式。顺序存储结构

顺序存储结构是将逻辑上相邻的数据元素存储在物理上也相邻的一系列存储单元里，一般用数组来实现。其主要特点是：元素之间的逻辑关系由物理相邻关系体现，且每个结点仅存储元素的数据信息，因此存储密度大，空间利用率高。但是在进行插入和删除运算时会造成相应元素的大量移动，因此效率比较低。链式存储结构

链式存储即逻辑上相邻的数据元素可以存放在物理上不一定相邻的存储单元中。链式存储结构常用链表表示，链表中的结点除了包括数据域，还要包括相应的指针域，以存放该数据元素逻辑上相关的数据元素的地址。其主要特点是：由于结点除存储数据元素本身之外（数据域），还要存储逻辑上相关的相邻元素的地址（指针域），因此与顺序存储结构相比，存储密度小、空间利用率低，会占用更大的存储空间。但与顺序存储结构相比，这样的做的优点是：在进行插入和删除操作时仅需要修改相应指针域的值即可，不会造成其他元素的大量移动，因此使用灵活方便。线性表、树、图等多种逻辑结构均可以采用顺序存储结构和链式存储结构。

4.1数据结构（3）数据的运算（操作）

每一种类型的数据结构都有相应的基本运算或操作，主要包括插入、删除、修改、查找、排序等。数据结构与其上定义的基本操作封装在一起构成了抽象数据类型（Abstractdatatype,

ADT）。在程序设计中，有很多支持抽象数据类型的语言，如C++、JAVA等程序设计语言用“类”来支持抽象数据类型的表示。

4.1数据结构数据结构的主要研究内容可以用图4.4来表示：4.1数据结构4.1.1线性结构

1.线性表（1）线性表的定义。

线性表是由n(n≥0)个性质相同的数据元素(结点)a1,a2,…,an所组成的有限序列，是一种结构最

简单使用最多的数据结构。每一个线性表的数据元素根据不同的情况可以有不同的类型。例如，表4-1所示的学生成绩表也是一个线性表，这里的数据元素是一条条的学生记录，每一条记录为一个数据元素，数据元素由学号、姓名、性别、班级名称和成绩等多个数据项组成，这里的数据元素类型可以定义为结构体。4.1数据结构4.1.1线性结构

（2）线性表的存储结构。线性表的存储结构可以采用顺序存储或链式存储：

顺序存储结构的线性表，也叫顺序表。顺序表通常用数组来实现，用一组地址连续的存储单元来依次存放线性表中的每一个元素。数据元素之间物理上的先后关系和逻辑上的先后关系保持一致。由数组的特征可以得出，第i个数据元素的存储地址可由以下公式求得：Loc（ai）=Loc(a1)+(i-1)*L公式中，Loc(a1)是第一个数据元素的存储地址，L为每个元素所占存储单元的大小。由以上公式可以得出，任意数据元素的存储地址均可以直接计算出来，所以对任意数据元素的访问都可以采用直接访问的方式，因此速度快、效率高，这是它的优点。如图4.5所示，采用顺序存储结构实现对线性表，如果要访问第i个元素，计算表的长度等操作比较简单，但在实现插入或删除元素操作时，会造成其他大量相关元素的移动从而需要花费较多的时间，因此效率比较低。4.1数据结构4.1.1线性结构

链式存储结构的线性表，也叫链表。链表中的每一个结点在内存中的存储单元不一定连续。为了表示数据元素之间的逻辑关系，每个存储单元除了存放数据元素本身之外，还需要存储逻辑上相关的下一个元素的存储地址，所以每一个数据元素对应一个物理存储单元，包含数据域和指针域两部分，如图4.6所示。整个线性表的各个数据元素的存储区域之间，通过指针连接成为一个链式的结构，称为链表，如图4.7所示链式存储的优势是可以利用零散的存储单元存放数据元素，而且在实现插入和删除操作时，只需要修改局部指针，不会引起其他元素的移动，因此效率较高。但是，链表中的每一个结点除了存储数据元素本身之外还额外增加一个指针域，这将增加存储空间的开销，存储密度小。而且访问链表的数据元素，只能沿着头指针“顺藤摸瓜”顺序访问，效率也大大降低。4.1数据结构4.1.1线性结构

（3）线性表的运算

插入。在线性表L中插入一个数据元素ListInsert(L,i,e)，该运算的功能是将数据元素为e的元素插入到线性表L的第i个位置上。插入成功后，线性表L的元素个数增加1，即长度增加1。例如，在线性表L=（25,12,47,89,36,14）的第四个位置插入一个值为99的元素，插入成功后线性表成为L=（25,12,47,99,89,36,14），长度由6增加为7，如图4.8所示。4.1数据结构4.1.1线性结构

删除。删除线性表L中第i个数据元素ListDelete(L,i)。该运算的功能是将删除线性表L的第i个数据元素。删除成功后，线性表L的数据元素个数减1，即长度减1。

检索。获取线性表L中的某个数据元素内容GetElem(L,i,e)。该运算的功能是获取线性表L中第i个位置上的数据元素的值，并由参数e带回。

查找。查找值为e的数据元素LocateELem(L,e)，该运算用来在线性表L中查找指定的数据元素e。如果查找成功，则返回该元素线在性表中的位置，否则返回0。

求线性表的长度。求线性表L的长度ListLength(L)，该运算用来求线性表L的长度，即线性表L中数据元素的个数。

判断线性表是否为空。判断线性表L是否为空IsEmpty(L)，若为空则返回1，否则返回0。4.1数据结构4.1.1线性结构

2．栈（1）栈的定义。

栈是一种操作受限的特殊线性表，它只能在表的一端（栈顶）进行插入和删除运算。与线性表相同，数据元素之间仍为一对一关系。设栈S=（a1,a2,...,an），按照a1,a2,...,an顺序依次先后进栈，则称a1是栈底元素，an是栈顶元素。进栈和出栈只能在栈顶操作，且遵循后进先出（LastInFirstOut，LIFO）或先进后出（FirstInLastOut，FILO）的原则，如图4.9所示。4.1数据结构4.1.1线性结构

（2）栈的存储结构。用顺序存储（顺序栈）和链式存储（链栈）均可，但以顺序栈更常见，即用一个连续的存储区域来存放栈元素，并设置一个指针top指向栈顶元素或栈顶元素下一个位置。图4.10分别表示了栈的初始状态（空栈），以及栈元素A、B、C依次进站的过程。

4.1数据结构4.1.1线性结构

（3）栈的运算。设S为一个栈，则对栈可以进行以下一些基本运算：初始化空栈InitStack(S)。该运算将栈S初始化为空栈。进栈Push(S,x)。该运算将新的数据元素x压入栈S（图4.11）中，作为栈S的栈顶元素。例如，在栈S顶部压入素x，压入成功后栈的长度由3增加为4（图4.12）。过程如下：1)判断是否栈满，若满则出错2)元素X压入栈顶。3)栈顶指针加1。出栈Pop(S)。该运算删除栈S的栈顶元素，且栈S的元素少1。取栈顶元素GetTop（S）。该运算取得栈S的栈顶元素作为其函数值。4.1数据结构4.1.1线性结构

3.队列（1）队列的定义。队列（Queue）是一种先进先出(FIFO)的线性表，只允许在表的一端进行插入，而在另一端删除元素。允许入队操作的一端称作队尾，允许删除操作的一端称作队头。设队列Q=（a1,a2,...,an），按照a1,a2,...,an顺序依次入队，则称a1是队头元素，an是队尾元素，入队和出队操作遵循后进先出（LIFO）或先进后出（FILO）的原则，如图4.13所示。

4.1数据结构4.1.1线性结构

（2）队列的存储结构。与栈一样，队列也有顺序存储（顺序队列）和链式存储（链队列）两种。如果队列需要频繁地做插入和删除操作，那么队列采用链式存储结构较为适宜，它需要设置两个指针，一个为队头指针，另一个为队尾指针，分别指向队列的队头和队尾。链队列的结构如图4.14所示。

4.1数据结构4.1.1线性结构

（3）队列的运算。设Q为一个队列，则对Q可以进行以下一些基本运算：构造空队列InitQueue(Q)。该运算将队列Q初始化为空队列，具体过程是：首先申请一个结点，为该结点的指针域赋空值，并让队头指针front和队尾指针rear同时指向该结点。如图4.15所示。取队列长度QueueLength(Q)。该运算求队列Q的长度，即队列Q中数据元素的个数。取队头元素GetHead(Q)。该运算取得队列Q的队头元素作为其函数值。入队列EnQueue(Q,e)。该运算将新的数据元素值为e进入队列Q中，作为队尾元素。出队列DeQueue(Q)。该运算删除队列Q的队头元素。4.1数据结构4.1.2树形结构

1.树树（tree）是n(n≥0)个结点的有限集合。当n=0时，则称为空树。在一棵非空树中：（1）有且仅有一个特定的结点，称为树的根结点。（2）当n>1时，除根节点之外的其余结点被分成m（m

1）个互不相交的集合T1,T2,...，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树，称为根结点的子树。

在树中，一个结点可以看作是一个数据元素。图4.16是一个具有12个结点的树，根节点为A。

如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成

了不同的树，称这棵树为有序树。反之称之为无序树。零棵或有限棵不相交的树的集合称为森林（forest）。任何一棵树，删除根结点就变成了森林。由图4.16的树删除掉根结点后形成的森林如图4.17所示。

4.1数据结构4.1.2树形结构

1.树结点所拥有的子树的个数称为该结点的度，度为0的结点称为叶子结点，度不为0的结点称为分支节点。一棵树的结点除叶子节点之外，其余的都是分支节点。树中一个结点的子数的根结点称为该结点的孩子，这个结点称为它的子结点的父结点，具有同一个父结点的孩子互称为兄弟结点。如果一棵树的一串结点n1，n2，...，nk有关系：结点ni是ni+1的父结点（1≤i≤k），就把n1，n2，...，nk称为一条由n1到nk的路径。这条路径的长度是K-1。在树中如果有一条路径，从结点M到结点N，那么M就称为N的祖先，而N成为M的子孙。

规定树的根节点的层次为1，其余结点的层次等于它的父结点的层数加1。树中所有节点的最大层数称为树的深度，树中各节点度的最大值称为该树的度。

4.1数据结构4.1.2树形结构

2.二叉树（1）二叉树的概念二叉树（binarytree）是有限个结点的集合，该集合或为空或有一个称为根的节点及两个互不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。二叉树是有序的，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有5种基本形态：空二叉树、只有根节点的二叉树，只有根节点及左子树的二叉树，如图4.18所示。在二叉树中，左子树的根称为左孩子，右子树的根称为右孩子。如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。4.1数据结构4.1.2树形结构

2.二叉树一颗深度为K的有n个结点的二叉树，对树中的结点按从上至下从、左至到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点，在二叉树中的位置相同，则称这样二叉树为完全二叉树。完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。图4.19是一棵满二叉树，当然也是完全二叉树。图4.20是完全二叉树，但不是满二叉树。4.1数据结构4.1.2树形结构

2.二叉树（2）二叉树的主要性质性质1：一棵非空二叉树的第i层上最多只有2i-1个节点(i≥1)。性质2：深度为k的二叉树至多有2k-1个结点。性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）性质4：具有n个结点的完全二叉树的深度必为⌊log2n⌋＋1。性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为⌊i/2⌋。4.1数据结构4.1.2树形结构

2.二叉树二叉树的存储二叉树的存储结构也有顺序存储结构和链式存储结构两种：顺序存储结构二叉树的顺序存储，是用一组连续的存储单元（数组）存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。但这样的话，结点在存储位置上的前驱后继关系并不一定是它们在逻辑上的邻接关系（如父子关系）。依据二叉树的性质，只有完全二叉树和满二叉树才能很好体现出它们的逻辑关系，树中结点的序号可以唯一的反映出结点之间的逻辑关系，图4.20所示的完全二叉树的顺序存储如图4.21所示。而对于普通的二叉树，尤其是单支链的二叉树，会造成很多存储空间的浪费，如图4.22所示。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一的反映出结点之间的逻辑关系，这样能够最大可能的节省存储空间，又可以利用列表元素的索引值，确定结点在二叉树中的位置以及结点之间的关系。

4.1数据结构4.1.2树形结构

链式存储结构。二叉树的链式存储结构是指用链表来表示一棵二叉树。链表中每个节点都有三个域组成，除了数据之外，还有两个指针域，分别用来存储该结点的左孩子和右孩子结点所在的单元存储地址。结点的存储结构为图4.23所示：其中数据域存放结点（数据元素）的数据信息，若该结点的左孩子与右孩子不存在时，相应的地址即指针域的值为空（用符号^或者NULL表示）。图4.24给出了的二叉树的链式存储。4.1数据结构4.1.3图状结构

1.图的定义和术语

图（graph）是一种比树形结构更复杂的非线性结构。在树形结构中，数据元素间具有很明显的层次关系，每一层上的数据元素只能和上一层中的至多一个数据元素相关，但可能和下一层的多个数据元素有关。在图状结构中，任意两个数据元素之间都有可能有关，即数据元素之间的邻接关系可以是任意的。

4.1数据结构4.1.3图状结构

1.图的定义和术语

4.1数据结构4.1.3图状结构

2.图的存储结构图的存储结构有邻接矩阵和邻接表：邻接矩阵邻接矩阵存储结构,就是用一维数组记录图中顶点的信息，用一个邻接矩阵（二维数组）表示图中各个顶点之间关系。设图A=(V,E)有n个顶点，则图中各顶点相邻关系为一个n×n的矩阵。邻接矩阵是一个二维数组A.Edge[n][n]，定义为：用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵元素值为1，否则为0：1，如果<i,j>∈E或者（i,j）∈EA.Edge[i][j]=0，否则图4.25的邻接矩阵表示如下图所示：

4.1数据结构4.1.3图状结构

2.图的存储结构邻接表

邻接表是图的一种顺序存储与链式存储结合的存储方法。对每个顶点vi

建立一个单链表，

把与vi有关联的边的信息链接起来，形成单链表，并将图中所有顶点信息和邻接表头放在数组中，就构成了邻接表。链表中每个结点设为2个域，如图4.28所示。图4.29给出了无向图4.25对应的邻接表表示4.2算

法4.2.1算法概述4.2.2搜索4.2.3排序4.2.4并行算法

4.2算

法4.2.1算法概述

1.算法发展历史2.算法的概念和特征（1）算法的概念为了解决某个特定问题而采取的方法和步骤的一组有穷的指令集，称为算法。算法是被精确定义的一组规则，这些规则规定了先做什么再做什么，以及判断出现某种情况时做哪种操作，因此，算法是一个步进式的完成任务的过程。（2）算法的描述根据不同的应用场景和面向的任务不同，算法通过可以用自然语言、流程图、伪代码和程序设计语言来描述。（3）算法的特征输入：一个算法应该有0个或多个输入。输出：一个算法应该有1个或多个输出（即处理结果）。确定性：算法中的每一步定义都必须是确切的、无歧义的。有穷性：一个算法应在执行有穷步后可以结束。有效性：算法中描述的每一步操作都应该能有效地执行，并最终得到确定的结果。

4.2算

法4.2.1算法概述

2.算法的概念和特征（4）算法的评价

一般可以从正确性、时间复杂度和空间复杂度3个方面对算法进行评价。

正确性

算法的正确性是指算法能够正确的完成所要解决的问题。

时间复杂度时间复杂度指依据算法编写出程序后在计算机上运行时所耗费的时间度量。一个程序在计算机上运行的时间取决于程序运行时输入的数据、对源程序编译所需要的时间、执行每条语句所需要的时间及语句重复执行的次数等。其中，最重要的是语句重复执行的次数。通常，把算法中关键操作（循环和递归）重复执行次数之和作为该程序的时间复杂度，用T(n)表示，其中的n为问题规模。对于一个从线性表中查询某个数据的算法，设n为线性表的长度，即线性表中数据的个数。算法时间复杂度的渐进表示法，记作：T(n)=O(f(n))渐进符号（O）的定义：当且仅当存在一个正的常数C和n0，使得对所有的n

n0

，有T(n)

Cf(n)，则T(n)=O(f(n))。表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。4.2算

法4.2.1算法概述

2.算法的概念和特征

时间复杂度例如，分析下述count算法的时间复杂度。voidcount(){x=0;y=0;//T1(n)=O(1)for(intk=0;k<n;k++)x++;//T2(n)=O(n)for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;//T3(n)=O(n2)}算法的时间复杂度约等于该算法所有指令的执行的时间复杂度的最大值，即T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)。4.2算

法4.2.1算法概述

2.算法的概念和特征

时间复杂度时间复杂度T(n)按数量级递增顺序为：时间复杂度自左向右由低向高递增，当n取得很大时，指数时间算法和多项式时间算法在所需时间上会非常悬殊。图4.32是常数(1)、对数(logn)和线性(n)算法复杂度增长对比，图4.33是多项式

(nc)、指数(cn)和阶乘(n!)算法复杂度增长对比。4.2算

法4.2.1算法概述

2.算法的概念和特征

空间复杂度空间复杂度是指依据算法编写出程序后在计算机上运行时所需内存空间大小的度量，也就是和问题规模n有关的度量。记作:S(n)=O(f(n))其中n为问题的规模(或大小)。算法要占据的空间包括算法本身要占据的空间，输入/输出、指令、常数、变量以及算法要使用的辅助空间。例如，某个算法在执行过程中所占的存储空间为2n-1，则该算法的空间复杂度为O(2n)。若输入数据所占空间和算法无关，则不考虑输入本身所占空间，否则应同时考虑。4.2算

法4.2.2搜索

搜索即查找，是一种在列表中确定目标所在位置的算法。在列表中，搜索意味着给定一个值，并在包含该值的列表中找到第一个元素的位置。对于搜索中有两种基本的方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，没有要求，而折半查找则要求列表是有序的。1．顺序搜索（线性查找）顺序搜索一般用来查找表内元素之间无序的线性表，当查询的序列较大时，这种查找效率较低。顺序查找的查找过程是：从列表起始处开始查找，当找到关键字元素或确信查找关键字不在列表中时，查找过程结束。根据顺序搜索的算法，可以看出，对于任一数列，顺序搜索算法的时间复杂度为O(n)。4.2算

法4.2.2搜索

2.折半搜索如果查询的列表是无序的，则顺序查找是唯一的方法。但如果查询的序列较大，为了提高效率，最好将列表先排序，然后使用效率较高的折半查找进行查找。

折半搜索是通过查找列表的中间元素和待查找的关键字比较，以判别出目标在列表的前半部分还是后半部分。根据折半搜索的算法，可以看出，对于有序的数列，折半搜索算法的时间复杂度为O(log2n)。4.2算

法4.2.3排序

4种最基本的排序算法：选择排序、冒泡排序、插入排序和归并排序。1．选择排序基本思想：把待排序数字序