第十二章数据结构

第12章 数据结构与算法12.1算法12.2数据结构的基本概念12.3线性表及其顺序存储结构12.4栈和队列12.5线性链表12.6树与二叉树12.7查找与排序技术习题12.1算法12.1.1算法的基本概念1．算法的基本特征（1）可行性

（2）确定性

（3）有穷性

（4）有零个或多个输入

（5）有一个或多个输出一个算法，就是一组定义了运算顺序的规则，并且每个规则都是有效的、明确的，此运算顺序将在有限的步骤后终止。对数据对象的运算和操作，算法的控制结构。2．算法的基本要素（1）算法中对数据的运算和操作①算术运算：主要包括加、减、乘、除等运算。②逻辑运算：主要包括“逻辑与”、“逻辑或”、“逻辑非”等运算。③关系运算：主要包括“大于”、“大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等运算。④数据传输：主要包括赋值、输入、输出等操作。（2）算法的控制结构算法中各种操作之间的执行顺序称为算法的控制结构。一个算法一般都可以用顺序结构、选择结构、和循环结构这三种基本控制结构组合而成。3．算法设计基本方法（1）列举法列举法就是根据所要解决的问题，把所有可能的情况都一一列举出来，并用问题中给定的条件来检验哪些是需要的，哪些是不需要的。例如：设x,y为非负整数，求满足方程2x+3y=10的x,y。（2）归纳法归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。可以看出，归纳法可以解决列举量为无限的问题。

（3）递推递推是指从已知的初始条件出发，逐步推出所要求的结果。例如：求x2=a的递推公式：（4）递归在解决某些复杂问题时，为了降低问题的复杂程度（如问题的规模等），可以将问题逐层分解，最后归结为一些最简单的问题。例12.2有5个人坐在一起，问第5个人的岁数，他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人的岁数，他说比第2个人大2岁。问第2个人的岁数，他说比第1个人大2岁。问第1个人的岁数，他说是10岁。请问第5个人多大。这个问题可以用递归方法解决。递归过程如下：age（5）＝age（4）十2age（4）＝age（3）十2age（3）＝age（2）十2age（2）＝age（1）十2age（l）＝10（5）减半递推技术“减半”是指将问题的规模减半，而问题的性质不变；“递推”是指重复“减半”的过程。12.1.2算法的复杂度可分为时间复杂度和空间复杂度。

1．算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。例如：两个n阶方阵的乘积的乘法次数为n3。两种常用方法：（1）平均性态（2）最坏情况复杂性2．算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。类似算法的时间复杂度，空间复杂度作为算法所需存储空间的度量。12.2数据结构的基本概念数据结构主要研究三个问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。例12.5无序表的顺序查找与有序表的对分查找。12.2数据结构的基本概念

12.2.1什么是数据结构现实世界中存在的一切个体都可以是数据元素（简称元素）。例如：春、夏、秋、冬；26、56、65、73、26、…；父亲、儿子、女儿。数据元素之间的关系可用前后件关系例如，“春”是“夏”前件，“夏”是“春”的后件。1．数据的逻辑结构指数据之间的逻辑关系，与它们在计算机中的存储位置无关。有两个基本要素：①表示数据元素的信息，通常记为D；；②表示各数据元素之间的前后件关系，通常记为R。例12.2一年四季的数据结构可以表示成B=（D，R）D={春，夏，秋，冬}R={（春，夏），（夏，秋），（秋，冬）}例12.3家庭成员数据结构可以表示成B=（D，R）D={父亲，儿子，女儿}R={（父亲，儿子），（父亲，女儿）}2．数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

一种数据的逻辑结构可以表示成多种存储结构。

常用的存储结构有顺序、链接、索引等存储结构。12.2.2数据结构的图形表示12.2.3线性结构与非线性结构如果一个数据结构满足：（1）有且只有一个根结点；（2）每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。12.3线性表及其顺序存储结构12.3.1线性表的基本概念线性表是指n个数据元素的有限序列。线性表可以表示为（a1，a2，…，ai，…，an），当n=0时，称为空表。

12.3.2线性表的顺序存储结构顺序存储的特点如下：（1） 线性表中所有元素所占的存储空间是连续的；（2） 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。12.3.3顺序表的插入运算12.3.4线性表的删除运算12.4栈和队列12.4.1栈及其基本运算1．栈的基本概念栈（stack）是限定仅在一端进行插入和删除运算的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈的顺序存储结构如图所示。2．栈的基本运算有三种：入栈、退栈与读栈顶元素。（1）入栈运算首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置；（2）退栈运算首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一。（3）读栈顶元素是指将栈顶元素赋给一个指定的变量。栈顶指针不会改变。12.4.2队列及其基本运算1．队列的基本概念队列（queue）是在表的一端进行插入，在表的另一端进行删除的线性表。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为“先进先出”或“后进后出”的线性表。在队列中，常用指针front指向队头，用rear指向队尾，如图所示。图12.11是在队列中进行插入与删除的示意图。12.5线性链表12.5.1线性链表的基本概念1．线性链表其链表结构如图（a）所示。实际上，常用图（b）来表示它们的逻辑关系。双向链表：一个指向其前件结点，称为前件指针或左指针；另一指向其后件结点，称为后件指针或右指针。12.6树与二叉树12.6.1树的基本概念树（tree）是一种非线性结构，其所有数据元素之间的关系具有明显的层次特点。实际上，能用树结构表示的例子有许多。树的基本特征和基本术语：每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为根结点（简称根）。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。—个结点所拥有的后件的个数称为该结点的度。所有结点中的最大的度称为树的度。树的最大层数称为树的深度。以某结点的一个子结点为根构成的树称为该结点的一棵子树。12.6.2二叉树及其基本运算1．二叉树的基本概念两个特点：①非空二叉树只有一个根结点；②每个结点最多有两棵子树，且分别称为该结点的左子树与右子树。图中所示的是4颗不同的二叉树，但如果作为树，它们就相同了。2．满二叉树与完全二叉树（1）满二叉树在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。（2）完全二叉树完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，而在最后一层上只缺少右边的若干结点。3．二叉树的基本性质二叉树具有下列重要性质：性质1在二叉树中，第i层的结点数最多为2i-1个（i≥1）。性质2在深度为k的二叉树中，结点总数最多为2k-1个（k≥1）。例如，在图12.25所示的二叉树中，有5个叶子结点，有4个度为2的结点，度为0的结点比度为2的结点多一个。性质3对任意一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4（1）具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。（2）具有n个结点的完全二叉树的深度为[log2n]+1。性质5如果对一棵有n个结点的完全二叉树的结点从1到n按层序编号，则对任一结点i（1≤i≤n），有（1）如果i=1，则结点i是二叉树的根，它没有父结点；如果i>1，则其父结点编号为[i/2]。（2）如果2i>n，则结点i无左子结点（结点i为叶子结点）；否则，其左子结点是结点2i。（3）如果2i+1>n，则结点i无右子结点；否则，其右子结点是结点2i+1。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。12.6.3二叉树的存储结构二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。12.6.4二叉树的遍历分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法，并用D表示“访问根结点”L表示“遍历根结点的左子树R表示“遍历根结点的右子树”。1．前序遍历（DLR）是指首先访问根结点，然后遍历左子树，最后遍历右子树例如，对图12.31中的二叉树进行前序遍历，则为ABDGCEHIF。2．中序遍历（LDR）是指首先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图12.31中的二叉树进行中序遍历，则为DGBAHEICF。3．后序遍历（LRD）是指首先遍历左子树，然后遍历右子树，最后访问根结点。例如，对图12.31中的二叉树进行后序遍历，则为GDBHIEFCA。12.7查找与排序技术12.7.1顺序查找顺序查找又称为顺序搜索。顺序查找是指在线性表中查找指定的元素，例如在线性表（a1，a2，…，ai，…，an）中查找x。12.7.2二分法查找二分法查找只适用于顺序存储的有序表，即要求线性表中的元素按元素值的大小排列（递减排列或递增排列）。12.7.3交换类排序法1．冒泡排序法原序列628131957第1遍（从前往后）261318579（从后往前）126135879第2遍（从前往后）121356789（从后往前）112356789第3遍（从前往后）112356789最后结果112356789设当前要排序的线性表的下界为low，上界为high，则分割操作的步骤如下：（1）设两个指针i和j分别指向线性表的第一个元素和最后一个元素，即P（i）=low；P（j）=h