第2章 常用数据结构及其运算j

第 2章 常用数据结构及其运算2.1 概述 2.2 线性表2.3 栈与队 2.4 数组2.5 树与二叉树 2.6 图2.7 查找 2.8 排序 本章的特点及学习建议 数据结构是计算机软件技术中的基础课程，它介绍软件设计中几种常用的数据结构形式及相应的各种算法，并对各算法进行分析和比较1.语言要求Pascal、 c等，尤其 c语言的使用更为普遍。2.重视实践数据结构是一门实践性很强的课程，只有通过自己动手编制各种算法程序，并上机调试后，才能对课程内容有较深刻的了解，这也是真正检验学习效果的手段。因此上机操作是不可缺少的教学环节。2.1 概述2.1.1 什么是数据结构n 计算机科学是研究信息表示和信息处理的科学。n 信息在计算机内是用数据表示的。n 数据结构就是研究非数值运算的程序设计问题。2.1.1什么是数据结构数值计算问题通常是用分析数学的方程式来建立数学模型，称为数值型程序设计，其特点是涉及的操作对象比较简单，一般为整型、实型和布尔型数据。非数值性问题如文献检索、金融管理、商业系统数据处理、计算机辅助设计和制造以及以图论为基础的图像模式识别等。 2.1.1什么是数据结构非数值性问题 重点在于数据处理n 插入、删除、查找、更新等处理方法。n 了解数据集合中元素之间的关系。n 如何组织和表示这些数据以提高处理效率2.1 概述2.1.2 基本概念和术语n 数据 (data): 是用于描述客观事物的数值、字符，以及一些符号的集合。n 数据元素 (data element): 数据集合中的一个个体，是数据的基本单位。n 数据对象 (data object): 性质相同的数据元素的集合。n 数据类型 (data type): 是指程序设计语言中允许的变量类型。2.1 概述n 数据结构 (data structure): 是指同一数据对象中各数据元素间存在的关系。用集合论方法定义数据结构为S=（ D， R）数据结构 S是一个二元组，其中 D是一个数据元素的非空有限集合， R是定义在 D上的关系的非空有限集合。 2.1 概述n 逻辑结构与物理结构： 数据的逻辑结构是研究数据元素及其关系的数学特性；数据的物理结构是逻辑结构在计算机中的映象，也就是具体实现，通常用高级语言中各种数据类型来描述这种实现。以后简称 数据的逻辑结构为数据结构，数据的物理结构为存储结构 。2.1 概述n 算法 算法 是解决某一特定类型问题的有限运算序列。 算法的实现必须借助程序设计语言中提供的数据类型及其运算。 一个算法的效率往往与数据的表示形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。2.1 概述2.1.3 算法描述语言这里采用一种算法描述语言来描述各种算法，它不直接用于计算机，主要为了能简单明了地描述算法本身。本算法描述语言基本采用高级语言表达形式，但省略了高级语言形式化的类型说明、变量说明等，代之以较自由的自然语言作非形式化描述，有些部分增加必要的注释（用 / /表示），以增加算法的可读性。每一种算法均以函数（过程）的形式表示，即算法名 （参量表）例如： INSERTLIST（ V,i,n,x） /顺序表的插入 /2.1 概述算法描述语言和上机实验语言例 2.1 用简单选择排序算法，在长度为 n的数组 r中，使数组中的元素按由小到大的数值进行排序。2.1 概述2.1.4 算法分析技术初步一个可执行的算法不一定是一个好的算法，算法分析是一个复杂的问题，通常用计算机执行时在时间和空间资源方面的消耗多少作为评价该算法优劣的标准。时间复杂度 ：时间消耗 。空间复杂度 ：它是指在算法中所需的辅助空间单元，而不包括问题的原始数据占用的空间（因为这些单元与算法无关）。2.1 概述n 频度与时间复杂度1. for i=1 to n2. for j=1 to n3. Bi,j=0 4. for k=1 to n5. Bi,j=Bi,j+Ai,k*Ak,j 6. end (k)7. end (j)8. end (i)2.1 概述n 在上述算法中，语句 3重复次数为 n2，语句 5重复次数为 n3。若语句 3执行 1次时间为 t1,语句 5执行 1次时间为 t2,忽略其他控制语句的执行时间，此算法耗用时间近似为n T(n)=t_1*n2+t_2*n3n 当 n很大时，有n 表示当 n充分大时， T（ n）和 n3 的比值是常数，即 T（ n）与 n3 是同阶的， n2， n3 分别是语句 3和语句5的频度，时间复杂度是以算法中频度最大的语句来度量的，记作 T (n) =O (n3)。2.1 概述各种算法在时间复杂度的增长率2.2 线性表n 2.2.1 线性表的定义和运算n 2.2.2 顺序（向量）存储线性表 n 2.2.3 线性链表n 2.2.4 向量和链表的比较 在数据处理中，大量数据均以表格形式出现，称为线性表，它是一种最简单也是最常见的数据结构。线性表有两种存储结构 -向量和链表。线性表的主要运算有插入、删除、查找和排序。2.2 线性表2.2.1 线性表的定义和运算线性表的定义： 线性表是数据元素的有限序列，由零个或多个具有相同类型或性质的元素组成的一个有序集合。L=（ D， R）其中： L为线性表， D=a1 , a2 , ,a n ， R=| ai-1 , ai ,ai属于 D, 2in 。 n为元素个数称为表长， n=0为空表。若线性表中的数据元素相互之间可比较， ai-1 ai 则称该线性表为 有序表 ，否则称为 无序表 。2.2 线性表线性表的结构特点(1)只有一个首结点 a1 ，它没有前趋结点。 (2)只有一个终结点 an ，它没有后继结点。(3)除首结点和终结点以外，其他所有结点有且只有一个前趋结点和一个后继结点。2.2 线性表 n 线性表的基本运算 ：（ 1） 插入：在两个确定元素之间插入一个新元素。（ 2） 删除：删除线性表中某个元素。（ 3） 查找：按某种要求查找线性表中的一个元素， 需要时可以进行更新。（ 4） 排序：按给定要求对表中元素重新排序。2.2 线性表2.2.2 顺序存储线性表1. 顺序存储结构是一种最常用也是最简单的线性表结构，它是用一组地址连续的存储单元存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构，用高级语言中一维数组类型表示。 2.2 线性表2. 顺序存储的运算建表查找删除插入2.2 线性表建表由于顺序表在存储空间是以连续方式存放的，因此必须根据线性表的大小，事先为它开辟一个足够大的连续空间，也就是在程序执行前就要分配好空间，称为静态分配。因此建立一个顺序表，就是按线性表大小，定义一个足够大的数组单元，由高级语言中的数组定义语句完成。用静态赋值语句或输入语句对表中的元素进行赋值。2.2 线性表查找线性表最频繁的操作是从表中查找所需要的元素。这个过程一般是将欲查找的数据值与线性表中的元素逐个进行比较，直到查找到所需的元素为止，也可能由于没有查找到而告失败，这类查找方式称为顺序查找。此外由于顺序表在存储空间中是连续存放，因此在得知欲查找元素的序号后，可通过线性表元素的首地址及元素的序号，直接计算出该元素的地址称为直接查找。2.2 线性表删除若要在长度为 n的线性表中删除第 i 个元素，相当于将表（ a1,a2,a n）中的 ai 除去，而将 ai以后元素 ai+1,a n依次向前移动一个位置。a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 ai an-12.2 线性表n 顺序存储线性表的删除算法DELETELIST（ V， n， i）1. if(in+1)then参数错return2. for j=i to n-13. V j = Vj+14. end (j)5. n = n-16. return 2.2 线性表n 例：已知线性表 A(7， 10， 10， 21， 30， 42， 42， 42， 51)，其元素值按非递减有序排列。试设计算法，删除表中多余的重复值元素，成为(7， 10， 21， 30， 42， 51)。 2.2 线性表删除 A3的执行情况算法思想：设线性表用一维数组 A 表示，由于线性表中元素值已按非递减有序排列，则相同的元素必在相邻位置，因此只要比较相邻两元素，若数值相同，就删除后者。如 i表示当前扫描到的元素，如果 Ai=Ai+1，就将 Ai+1删除。图 2.1表示当 i=2时，删除 A3的执行情况 。2.2 线性表查找和删除是本算法中的基本运算，算法如下：DELL (A, n) /在长度为 n的线性表 A中删除重复元素 /1. i12. while (in-1) do3. if (AiAi+1) then ii+1 / 继续向下扫描 /4. else ( for j=i+2 to n5. Aj-1Aj / 删除表中第 i+1个元素 /6. end j7. nn-1) / 表长减 1/8. end (while)9. return2.2 线性表该算法问题这个算法中的时间复杂度为 O(n2)，它的缺点是每删除一个元素需将全部剩余元素向前移动一个位置，以致在整个执行过程中，有的元素要经过多次移动才能到达最终位置。例如其中 A9元素首先移动到 A8，再移动到 A7，最后才移动到A6。2.2 线性表