第一章数据结构.ppt

《第一章数据结构.ppt》由会员分享，可在线阅读，更多相关《第一章数据结构.ppt（87页珍藏版）》请在三一文库上搜索。

1、全国计算机等级考试 公共基础知识,全国计算机等级考试二级VFP语言试卷笔试满分100分，其中含公共基础知识部分的30分。 共有两种题型：选择70分30小题，填空30分15小题 全国计算机等级考试二级VFP语言上机满分为100分，共有三种类型考题。 1、基本操作题（30分） 2、简单应用题（40分） 3、综合应用题（30分）,基本数据结构和算法,第一章,引入算法,算法的五个重要特性 算法：解题方案的准确而完整的描述 基本特征 （1）有穷性：算法必须在执行有穷步之后结束，每一步都可在有穷时间内完成。 （2）确定性：对相同的输入只能得出相同的输出。 （3）可行性：算法所描述的操作都是可实现的。 （4

2、）拥有足够的情报。,算法设计的要求 （1）正确性：算法应当满足具体问题的需求； （2）可读性：可读性好的算法有助人们于对算法的理解； （3）健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果； （4）效率与低存贮量：效率指的是算法执行的时间，解决同一问题，执行时间短的算法效率高。存储量指算法执行过程中所需要的最大存储空间。,算法基本要素 一个算法通常由两个基本要素所组成： 1.对数据对象的运算和操作 2.算法的控制结构 基本运算和操作分为四类： 1.算术运算 2.逻辑运算 3.关系运算 4.数据传输 算法的控制结构： 顺序 选择 循环,算法优劣分析,同一问

3、题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适 算法和改进算法。 一个算法的评价主要从时间复杂度和空间复杂度来考虑。 时间复杂度 是指执行算法所需要的计算工作量，是由算法执行的基本运算次数来度量。 空间复杂度是指算法在计算机内执行时所需的内存空间。,数据结构,现实中对象之间的关系,线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系：如学校的组织结构、人的辈分关系等。 网状关系：如城市铁路交通网、电话网、计算机网络等。,应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表1-1所示的学生 信

4、息。,特点： l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； l 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,数据结构主要研究以下三个方面的问题： 数据的逻辑结构 数据的存储结构 对各种数据结构进行的运算,注意： 讨论以上问题主要目的是为了提高数据处理的效率，提高效率包括两个方面： 一是提高数据处理的速度 二是节省在数据处理过程中所占用的计算机存储空间,数据结构概论 数据：能输入到计算机中并被计算机存储、加工的符号的总称

5、。（数值型、布尔型、字符串、表格、语音、图片、图像等） 数据元素：数据的基本单位（结点、顶点或记录）通常作为一个整体进行处理。 数据项：数据的不可分割的最小单位。 一个数据元素可以由若干个数据项构成。,逻辑结构,1.数据的逻辑结构分为线性结构和非线性结构两大类。 (1)线性结构:包括数组、链表、 栈、队列、优先级队列等; 线性结构的基本特征 存在唯一的“第一个”数据元素； 存在唯一的“最后一个”数据元素； 除第一个外，每个数据元素均有且只有一个直接前驱元素； 除最后一个外，每个数据元素均有且只有一个直接后继元素。 (2)非线性结构:包括树、图等.,答：指数据元素之间的逻辑关系。即从逻辑关系上描

6、述数据，它与数据的存储无关，是独立于计算机的。,何为数据的逻辑结构？,存 储 结 构,存储结构概念：数据的逻辑结构在计算机存储空间中的存放形式 常见存储结构： (1)顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构. 即逻辑上相邻,物理上也相邻. (2)链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。 (3)索引存储结构:,线性表,线性表的概念 线性表：是线性结构的一种具体表现，所含结点的个数称为表长，表长为0的线性表称为空表。,春,夏,秋,冬,线性表（a1, a2 , ai, ai+1, , an）的顺序表示：用一组地址连续的存贮单元依

7、次存贮线性表的数据元素。 顺序表的特点：逻辑结构中相邻的结点在存储结构中仍相邻。 顺序表的容量（maxsize）：线性表实际达到的最大长度。 表长：当前表的长度，小于等于表的容量。,线性表的顺序存储结构,线性表的顺序表示（图示）,b数据元素a1的存储地址 l每个数据元素所需的存储单元大小,插入运算：在表的第i(1=i=n+1)个位置上，插入一个新结点x，使长度为n的线性表变成长度为n+1的线性表 插入算法的基本步骤： 将结点ai, ,an各后移一位； 将新结点x置入第i个位置； 表长加1 插入一个元素所需平均移动次数：n/2,线性表的插入运算,在线性表的第i个位置前插入一个元素的示意图如下：,

8、插入25,删除运算：将表的第i(1=i=n)个结点删去，使长度为n的线性表变成长度为n-1的线性表。 删除运算的基本步骤： 结点ai+1, ,an依次前移一个位置； 表长减1 删除一个元素所需平均移动次数： (n-1)/2,线性表的删除运算,删除顺序表中某个指定的元素的示意图如下：,链式存储结构,小 结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素。 解决问题的思路：改用另一种线性存储方式：,线性表的链式存储结构,线性表的链式表示：用一组任意的存储单元（可连续也可不连续）存储

9、线性表的数据元素。在链式存储结构方式下，存储数据元素的结点空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系由指针域来确定。,每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据， 指针域存放指针。,头指针H：,钱,孙,李,周,赵,吴,郑,王,H,31,（赵，钱，孙，李，周，吴，郑，王）的链式表示,单链表,数据域(data)：用于存储线性表一个数据元素的信息。 指针域(next)：用于存放一个指针，该指针指向本结点的后继结点。,Head称为头指针，指向链表中第一个结点； 如果为NULL，表示为空,单链表中结点的插入 （在指针p所指的结

10、点后插入指针s所指的结点）,插入前：,插入后：,a3,删除后：,单链表中结点的删除 （删除指针p后面的结点）,循环链表的特点表中的最后一个结点的指针域指向头结点, 整个链表形成一个环。 从表的任意结点出发可以找到表中其它结点。 循环链表和线性表的操作差别：仅在于算法中的循环条件不是L或L-next是否为空，而是它们是否等于头指针。,循环链表,双向链表,双向链表的特点表中的每个结点有两个指针域，一个指向后继结点，一个指向前趋结点， 整个链表形成两个环。 从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。,栈和队列,“取”操作必须在这端进行,“放”操作必须在同一端进行,栈,栈（stac

11、k）: 先进后出( FILO）的线性表。 或后进先出（ LIFO）的线性表。 或仅在表尾进行插入和删除操作的线性表。 栈顶（top）: 线性表的表尾端，即可操作端。 栈底（bottom）: 线性表的表头。,栈的基本操作,进栈操作 ： 将数据元素x插入栈S，使x成为S的栈顶元素； 出栈操作： 当栈不空时返回栈顶元素为该函数的值，然后删除栈顶 元素； 取栈顶元素 ： 当栈不空时返回栈顶元素为该函数的值，但栈顶保持不 变；,队列,排队只能排在尾部, 排在对头的先得到服务; “插队”是不允许的. 换言之, 插入和删除只能在线性表的两头分别进行; 插入的一端称为队尾, 删除的一端称为队头; 其特点是:

12、先进先出(FIFO),队列(Queues)是生活中“排队” 的抽象,队列（Queue）: 先进先出(First In First Out) (缩写为FIFO）的线性表。 仅在队尾进行插入和队头进行删除操作的线性表。 队头（front）: 线性表的表头端，即可删除端。 队尾（rear）: 线性表的表尾端，即可插入端。,队头,队尾,a1,a2,a3,an-1,an,循环队列（队列的顺序表示与实现）,采用顺序存储结构 约定: 1)初始空队列：front = rear=0 ; 2)循环队列中元素个数=rear-front,树和二叉树,特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,一对

13、多,社会的组织结构 家族的族谱 计算机中目录组织,树的类型定义,树是一类重要的非线性数据结构，是以分支关系定义的层次结构。,即树的数据元素 一个结点所拥有的后件的个数,结点 结点的度 根 叶子,树的度 树的深度 (或高度),即根结点(没有前驱) 即终端结点(没有后继),所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,（有几个直接后继就是几度）,二叉树,二叉树的五种基本形态：,(c)右子树为空的二叉树 (d)左、右子树均为非空的二叉树 (e)左子树为空的二叉树,(a) 空二叉树 (b)仅有根结点的二

14、叉树,逻辑结构： 一对二（1:2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒。,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,两种特殊的二叉树 1.满二叉树：一颗树中所有叶结点均在同一阶层，而其它非终端结点的分支度均为2，则此树为一颗满二叉树。 若该树的高度为h，则此满二叉树的结点为2h-1。 2. 完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；,二叉树的性质（重要）,性质1 在二叉树的第i层上最多有2i-1个结点 性质2 深度为k的二

15、叉树最多有2k-1个结点 性质3 设二叉树叶子结点数为n0，度为2的结点n2，则n0 = n2 +1,对完全二叉树的结点编号：从上到下，从左到右,二叉树的存储结构 链式存储结构,data,lchild,rchild,二叉链表中每个结点包含三个域：数据域、左指针域和右指针域,链式存储结构示例,树的二叉链表表示,遍历二叉树,遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。,一、二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,约定先左后右,有三种遍历方法：先序遍历、中序遍历、后序遍历,先序遍历（T L R） 若二叉树

16、非空， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,先序遍历序列：A,B,D,E,G,C,F,中序遍历（L T R） 若二叉树非空 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树,中序遍历序列： D,B,G,E,A,C,F,后序遍历（L R T） 若二叉树非空 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点,后序遍历序列： D,G,E,B,F,C,A,后序遍历序列：a,b,c,d,-,*,+,e,f,/,-,中序遍历序列：a,+,b,*,c,-,d,-,e,/,f,先序遍历序列：-,+,a,*,b,-,c,d,/,e,f,例：先序遍历、中序遍

17、历、后序遍历下图所示的二叉树,查找,基本概念,若表中存在特定元素，称查找成功，应输出该记录； 否则，称查找不成功（也应输出失败标志或失败位置）,查 找 查找成功 查找不成功 关键字 主关键字,查询(Searching)特定元素(关键字）是否在表中。,记录中某个数据项的值，可用来识别一个记录 可以唯一标识一个记录的关键字,例如“学号”,查找算法主要有：,一、顺序查找（线性查找） 二、折半查找（二分或对分查找）,顺序查找算法：,监视哨,根据上述算法可知： 查找成功时的平均查找次数为： 1+2+3+4+n)/n=(n+1)/2,顺序查找的优点：算法简单，无需排序，采用顺序 和链式存储均可。 顺序查找

18、的缺点：平均查找长度较大。,有序表的查找（折半查找/二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。,分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。,ST.elem,ST.length,例如: key = 64 的查找过程如下,low,high,mid,mid,mid = (low+high)/2 最理想的情况下1次比较就查找成功。 查找所需时间级最多为O（log2n）,折半查找的实现过程可

19、以用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中间记录，它的左子树、右子树分别对应区间的左子表和右子表，树中的每个结点对应一个记录。则上述有序序列构成的查找树如下图所示。,算法分析,排序,内部排序,排序将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。 排序方法的分类 （1）插入排序 （2）交换排序 （3）选择排序,插入排序,插入排序基本思想是：,插入排序有多种具体实现算法： 1) 直接插入排序 2) 希尔排序,每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,简言之，边插入边排序，保证子序列中随时都是排好

20、序的。,1 . 直接插入排序,直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。 这里利用 “顺序查找”实现“在R1i-1中查找Ri的插入位置”。,10. 2 插 入 排 序,对于有n个数据元素的待排序列，插入操作要进行n-1次,时间： 最好情形判断n次，无移动； 故时间复杂度：O(n2) 适用于：一边输入数据、一边排序,直接插入排序算法分析,2.希尔（shell）排序（又称缩小增量排序）,基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的

21、记录“基本有序”时，再对全体记录进行一次直接插入排序。 技巧：子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短(例如依次取5,3,1)，直到dk1为止。 优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。,具体实现: 首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序， 然后再取两个记录间的距离d2d1，在整个待排序记录序列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序 直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即整个待

22、排序记录序列。,例如：1 2 3 4 5 6 7 8 9 10 关键字：,49 38 65 97 76 13 27 49* 55 04,第一趟希尔排序，设增量 d =5， 分为5组，各组内进行直接插入排序,13 27 49* 55 04 49 38 65 97 76,第二趟希尔排序，设增量 d =3， 分为3组，各组内进行直接插入排序,13 04 49* 38 27 49 55 65 97 76,04 13 27 38 49* 49 55 65 76 97,第三趟希尔排序，设增量 d =1， 分为1组，各组内进行直接插入排序,时间效率： 当增量序列为d(k)=2t-k+1-1时，时间复杂度为O

23、(n1.5）。,交换排序,两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。,交换排序的主要算法有： 1) 冒泡排序 2) 快速排序,交换排序基本思想是：,1 冒泡排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构,21,08,25,49,25,16,21,49,25,25,16,08,21,49,25,25,16,08,初 始 关 键 字,第 一 趟 排

24、序,第 四 趟 排 序,第 二 趟 排 序,第 三 趟 排 序,21,49,25,25,16,08,第 五 趟 排 序,起泡排序的过程,最大者沉底,冒泡排序的算法分析,时间效率：O（n2) 因为要考虑最坏情况 空间效率：O（1） 只在交换时用到一个缓冲单元,2.快速排序(对冒泡的改进),从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。,基本思想：,优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺

25、序存储结构,( )，,设以首元素为枢轴中心,关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。,21， 25， 49， 25*，16， 08,初态： 第1趟： 第2趟： 第3趟：,08，16，21，25， 25*，(49),21,16，08,，( ),25，25*，49,(08)，16，21，,25，(25*，49),快速排序的过程,快速排序分析,快速排序的平均时间为T(n) = nlog(n) 经验表明,在同数量级的排序方法中,快速排序的常数因子k最小. 就平均时间而言,快速排序是最好的. 若初始序列按关键字基本有序,快速排序蜕化为起泡排序,其时间复杂度为O

26、(n2)。,选择排序,选择排序有多种具体实现算法： 1) 简单选择排序 2) 堆排序,选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。,1 简单选择排序,思路简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 首先，在n个记录中选择最小者放到r1位置；然后，从剩余的n-1个记录中选择最小者放到r2位置；如此进行下去，直到全部有序为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构,效率分析 简单选择排序比较次数与关键字初始排序无关。 找第一个最小记录需进行n-1次比较，找第二个

27、最小记录需要比较n-2次，找第i个最小记录需要进行n-i次比较，总的比较次数为： （n-1）+（n-2）+（n-i）+2+1=n(n-1)/2=n2/2 时间复杂度：O(n2) 辅助空间：O（1） 简单选择排序是不稳定的排序方法。,2 堆排序,1. 什么是堆？,堆的定义：设有n个元素的序列 k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。,或者,i=1, 2, n/2,解释：如果让满足以上条件的元素序列 （k1，k2，kn）顺次排成一棵完全二叉树，则此树的特点是： 树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。,2. 怎样建堆？,3. 怎样堆排序？,小根堆,大根堆,不是堆,不是堆,算法分析,堆排序方法对记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的.因为其运行时间主要耗费在建初始堆和调整新堆时进行的反复“筛选”上。 堆排序在最坏情况下，其时间复杂度也为O（nlog2n),相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。,