计算机导论 第5章 算法与数据结构

计算机导论教师：第5章算法与数据结构05目录CONTENTS1算法2数据结构的概念3几种常见的数据结构4查找和排序本章学习目标了解算法的概念了解算法与数据结构的关系掌握数据结构的逻辑结构掌握数据结构的存储结构了解常用的查找与排序算法本章学习目标算法算法（Algorithm）是指对解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表用系统的方法描述解决问题的策略机制。算法不是程序，但程序员可以使用某种编程语言来实现算法。算法被公认为是计算机科学的灵魂。从理论角度来看，对算法的研究（有时称为“算法学”）已经被公认为是计算机科学的基石。

算法的概念算法的基本特性一个算法必须在有限步骤之内结束，不能形成死循环。这种有限性使算法不能保证一定有解。有限性算法中的每条指令必须有确定含义，无二义性，不会产生理解偏差。算法可以有多条执行路径，但是对某个确定的条件值只能选择其中一条路径执行。确定性一个算法有多个或0个输入，输入取自某些特定对象的集合。有些输入在算法执行过程中输入，有些算法不需要外部输入。输入至少有一个或多个输出，输出与输入之间存在某些特定的关系。不同的输入可以产生不同或相同的输出，但是相同的输入必须产生相同的输出。输出算法是可行的。描述的操作可通过已实现的基本运算执行有限次而完成。可行性用自然语言描述算法用自然语言描述算法的优点是简单，但容易出现歧义。例5-1用自然语言描述求两个整数的最大公约数的算法。步骤1：输入两个整数x和y；步骤2：x和y整除余数为r；步骤3：判断余数r是否为0，如果为0，则转步骤5；否则转步骤4；步骤4：x的值是y的值，y的值是r的值,转步骤2；步骤5：输出y。y为所求的两个整数的最大公约数。

算法的描述用流程图描述算法美国国家标准化协会（AmericanNationalStandardsInstitute,ANSI）曾规定了一些常用的流程图符号，可以用这些流程图符号描述算法的执行步骤。例5-2用流程图描述求两个整数的最大公约数的算法：如图5-2所示。

算法的描述用伪代码描述算法伪代码（Pseudocode）是一种非正式的，用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。使用伪代码的目的是使被描述的算法可以容易地以任何一种编程语言（Pascal、C、Java等）来实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。

算法的描述用类C语言描述算法

算法的描述算法设计要求算法的正确性是指在给定有效输入后，经过有限时间的计算并产生正确的答案。正确性算法的可读性是指一个算法可供人们阅读的容易程度。可读性算法的健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。健壮性算法的效率通常是指算法的执行时间。对于一个具体问题的解决，通常有多个算法，执行时间短的算法其效率就高。计算机的另一个有限资源就是内存，希望一个算法的执行所需要的最大存储空间尽可能得少。高效率和低存储数据结构的发展计算机加工处理对象范围、类型不断扩展，由纯数值发展到字符、表格、声音和图像的各种具有一定结构的数据。为了应对信息时代计算机处理对象特点的变化，迫切需要分析待处理数据对象的特性及其各处理对象间的关系。1968年，美国著名计算机科学家高德纳（DonaldErvinKnuth）开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本系统阐述数据结构的著作。瑞士计算机科学家尼古拉斯·沃斯（NiklausWirth）在1976年出版的著作中指出：“算法+数据结构=程序”，可见数据结构在程序设计中的重要性。数据结构的概念数据结构的定义数据结构的概念数据（Data）是描述客观事物的数值、字符及能输入机器且能被处理的各种符号的集合。数据元素（DataElement）作为数据的基本单位。一个数据元素可由一个或多个数据项（DataItem）组成，数据项是具有独立含义的数据最小单位。数据对象（DataObject）是指性质相同的数据元素的集合，它是数据的一个子集。数据结构（DataStructure）是指相互之间存在一种或多种特定关系的数据元素集合，数据结构应该包括数据元素集合及元素间关系的集合。因此，我们可以把数据结构看成带结构的数据元素的集合。数据结构的研究内容通常包括3个方面：数据结构的概念数据的逻辑结构由数据元素之间的逻辑关系构成，是独立于计算机的，因此数据逻辑结构可以看作从具体问题抽象出来的数学模型。数据的逻辑结构数据元素及其关系在计算机存储器中的存储表示，也称为数据的物理结构。显然，数据的存储结构是依赖于计算机的。数据的存储结构数据的运算是施加在数据上的操作，常用的有查找、插入、删除、更新和排序等。数据的运算需要在对应的存储结构上用算法实现。数据的运算逻辑结构的定义逻辑结构

基本的数据结构逻辑结构集合结构：结构中的数据元素之间除“同属于一个集合”的关系以外别无其他关系。线性结构：结构中的数据元素之间存在一对一的线性关系。其特点是，除第一个元素和最后一个元素外，每个元素都有且仅有一个前驱元素，有且仅有一个后继元素。树形结构：结构中的数据元素之间存在着一对多的层次关系。其特点是，如果数据元素集合非空，则有且仅有一个元素被称为根元素，除根元素以外的其他元素有且仅有一个前驱元素。所有元素有0个或多个后继。图形结构：结构中的数据元素之间存在着多对多的任意关系。其特点是，每个元素的前驱元素和后继元素的个数可以是任意的。逻辑结构数据的存储结构存储结构数据的逻辑结构在计算机存储器中的存储表示被称为数据的存储结构（也称为映像），也就是逻辑结构在计算机中的存储实现，它包括数据对象的表示和数据对象中数据元素关系的表示。顺序存储结构存储结构顺序存储结构采用一组连续的存储单元存放所有的数据元素，并映射元素之间的逻辑关系。也就是说，所有的数据元素在计算机存储器中占用一整块存储空间。一般来说，顺序存储结构是高级语言的数组。链式存储结构存储结构链式存储结构是指使用“链表”存储映像数据的逻辑结构，链表是由节点构成的，每个节点对应一个数据元素，每个节点是单独分配的，所有节点的地址不一定是连续的。为了表示元素之间的逻辑关系，每个节点有一个或多个指针域，用于存储逻辑上相邻节点的地址，也就是通过指针域将所有节点连接起来而形成链表。索引存储结构存储结构索引存储结构是指在存储数据元素信息的同时还要建立附加的索引表。存储所有数据元素信息的表称为主数据表，其中每个数据元素有一个关键字和对应的存储地址。散列存储结构存储结构散列存储也称哈希存储。散列存储的基本思想是根据元素的关键字通过散列函数直接计算出一个值，并将这个值作为该元素的存储地址。与前3种存储结构不同的是，散列存储不涉及数据元素之间关系的映射，所以散列存储主要应用于元素间没有逻辑关系的集合结构，以便数据的查找和插入运算。数据运算数据运算是指对数据实施的操作。每种数据结构都有一组相应的运算，常用的运算有查找、插入、删除、遍历、排序等。数据运算分为运算定义和运算实现两个层面。运算定义是运算功能的描述，是抽象的，基于逻辑结构的。运算实现是基于存储结构的，同样的运算定义，如果存储结构不同，运算实现的算法基本不同。对于一种数据结构，其逻辑结构总是唯一的，但它可能对应多种存储结构，并且在不同的存储结构中同一运算的实现过程可能不同。线性表的定义线性表

线性表的存储结构线性表线性表的存储结构有两种：顺序存储和链式存储。线性表的顺序存储，是把线性表中的所有元素按照逻辑顺序依次存储到一块地址连续的存储空间中，逻辑上相邻的两个元素，物理上也是相邻的。线性表的顺序存储结构简称为顺序表。线性表的链式存储也称链表。一般采用带头节点的单链表存储线性表。操作受限的线性表线性表栈（Stack）是指将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶，将表的另一端称为栈底。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作被称为出栈或退栈。队列（Queue）是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。在队列中，允许插入的一端叫作队尾，允许删除的一端叫作队头。树的基本概念和特征树型结构

二叉树树型结构二叉树（BinaryTree）是一个有限的节点集合，这个集合或为空，或由一个根节点和两棵不相交的称为左子树和右子树的二叉树构成。二叉树的定义也是递归定义。二叉树有5种基本形态。二叉树中的节点最多有两个孩子，分别称为左孩子和右孩子。满二叉树和完全二叉树树型结构在一棵二叉树中，如果所有分支节点都有两个孩子节点，并且叶子节点都集中在二叉树的最下面一层，这样的二叉树称为满二叉树。若二叉树中最多只有最下面两层节点的度数可以小于2，并且最下面一层的叶子节点都排列在该层最左边的位置上，则这样的二叉树被称为完全二叉树。二叉树的二叉链表存储结构树型结构二叉树也有顺序存储结构和链式存储结构，常用的是链式存储结构。因为二叉树最多有两个孩子，因此链表节点有两个指针域，分别指向左孩子和右孩子。二叉树的顺序存储结构树型结构二叉树的顺序存储就是用一组地址连续的存储单元来存放二叉树的数据元素。对于完全二叉树和满二叉树，树中节点的层序编号可以唯一地反映节点之间的逻辑关系，所以可以用一维数组按从上到下，从左到右的顺序存储二叉树中的所有节点的值，即编号为的节点存储在下标为的数组单元中。二叉树的遍历树型结构二叉树的遍历是指按照一定的次序访问二叉树中的所有节点，并且每个节点仅被访问一次的过程。一棵二叉树由3部分组成，即根节点、左子树和右子树，若规定遍历时先左后右，则对于非空二叉树，可以得到3种递归的遍历方法，即先序遍历、中序遍历和后序遍历。对于非空二叉树：先序遍历：访问根节点、先序遍历左子树、先序遍历右子树。中序遍历：中序遍历左子树、访问根节点、中序遍历右子树。后序遍历：后序遍历左子树、后序遍历右子树、访问根节点除此之外，还可以对一棵二叉树按层遍历，即按照从上到下，从左到右的顺序遍历二叉树。二叉树的遍历树型结构按层遍历：ABCDEFG先序遍历：ABDGCEF中序遍历：BGDAECF后序遍历：GDBEFCA图的基本概念图形结构

图的存储结构图形结构常用的两种图的存储结构是邻接矩阵和邻接表。邻接矩阵：使用一个一维数组来存储图中的顶点信息，每个顶点都被分配了一个唯一的编号，该编号与数组下标一一对应。使用另一个二维数组，也即邻接矩阵来存储图中顶点之间的连接关系，元素的值为0或1，1表示有边或弧相连，而0则表示没有。

图的存储结构图形结构常用的两种图的存储结构是邻接矩阵和邻接表。邻接表：使用一个一维数组存储图，一维数组元素包含两个数据项：顶点信息及这个顶点所有邻接点的单链表的头指针。由于一个顶点的所有邻接点以单链表存储，因此这种存储结构是顺序+链式存储结构。图的遍历图形结构从图中某一顶点出发访问图中的所有顶点，且每个顶点仅被访问一次，这一过程就叫作图的遍历。通常有两种遍历策略：深度优先遍历和广度优先遍历。深度优先遍历，也称为深度优先搜索(DepthFirstSearch,DFS)：从图中某个顶点v出发，先访问此顶点，然后从v的未被访问的邻接点出发进行DFS，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中的所有顶点都被访问到为止。图的遍历图形结构从图中某一顶点出发访问图中的所有顶点，且每个顶点仅被访问一次，这一过程就叫作图的遍历。通常有两种遍历策略：深度优先遍历和广度优先遍历。广度优先遍历，又称为广度优先搜索（BreathFirstSearch，BFS）：从图中某顶点v出发，在访问了v之后依次先访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问”，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。查找查找和排序查找又称检索，是指在某种数据结构中找出满足给定条件的元素，主要有基于线性表的查找、基于树的查找和哈希表查找。

查找查找和排序查找又称检索，是指在某种数据结构中找出满足给定条件的元素，主要有基于线性表的查找、基于树的查找和哈希表查找。二分查找又称折半查找，要求待查找的顺序表是按关键字有序的。算法的思想是：将顺序表中间位置的元素的关键字与查找关键字做比较，如果两者相等，则查找成功；否则如果中间位置元素的关键字大于查找关键字，则在前半部分继续查找，否则在后半部分继续查找，重复以上过程，直到找到满足条件的元素或查找范围为空。因为每比较一次或会查找成功，或使查找范围缩小一半，因此该算法称为折半查找算法。排序查找和排序排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法是计算机领域的重要课题之一。冒泡排序查找和排序冒泡排序算法是一种典型的交换排序算法，基本思想是通过无序区中相邻元素关键字的比较和相邻元素的交换使关键字小的元素如气泡般往上“漂浮”。快速排序算法查找和排序快速排序算法采用分治策略，对无序区，首先选取某个称为基准的元素（一般为无序区的第1个元素），利用这个基准元素，把无序区分成两个子序列，第1个子序列的所有元素值都小于或等于这个基准，第2个子序列的所有元素都大于或等于这个基准。然后递归对两个子序列采用同样的算法划分，子序列规模越来越小，直到每个子序列只有一个元素或空为止。这时整个序列也就有序了。直接插入排序查找和排序直接插入排序算法的思想：初始时，将序列中第一个元素作为有序区，剩下的n-1个元素作为无序区。每一次，把无序区的第一个元素插入有序区，每插入一个元素后依然保持有序区有序，有序区元素个数增一，无序区元素个数减一，经过n-1趟后即成为有序序列。简单选择排序查找和排序简单选择排序算法的基本思想：每次总是从无序序列中选出最小元素并把其放在无序序列的起始位置。每选择一次会使无序序列元素个数减一，使有序序列元素个数增一，共需要n-1趟选择。初始时，无序序列元素个数为n。扩展阅读：密码与安全一直在国际上广泛