大学计算机基础 第4章.ppt

《大学计算机基础 第4章.ppt》由会员分享，可在线阅读，更多相关《大学计算机基础 第4章.ppt（35页珍藏版）》请在三一办公上搜索。

1、第4章 算法与基本数据结构,基本概念 基本数据结构 查找与排序,基本概念,数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。,数据结构的定义,数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，有时也称为元素、结点、顶点或记录,结构：是数据元素之间的关联关系,数据结构：数据结构带有结构的同性质数据元素的集合,数据结构包括以下三方面内容：逻辑结构、存储结构、和对数据的操作 逻辑结构：数据元素之间逻辑上的关系，它是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类

2、：线性结构和非线性结构。具体可分为四类：集合 线性结构 树型结构 图状结构 其中、为非线性结构,基本概念,数据结构的内容,存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分：,基本概念,数据结构的内容,存储结点(简称结点),每个结点存放一个数据元素 数据元素之间关系的表示，也就是逻辑结构的计算机内部表示常用的数据存储结构：顺序存储方法链式存储方法索引存储方法散列存储方法数据的运算如查找、排序、增加、修改、删除,算法：算法是对具体问题求解过程和步骤的一种描述,基本概念,算法,算法的5个特性：有穷性 确定性 可行性 零个或多个的输入 有1个或

3、多个的输出算法设计的要求：正确性 可读性 健壮性 效率与低存储量需求,效率是指一个算法在计算机上运行所花费的时间，以时间复杂度来衡量。所谓时间复杂度是指算法中所包含简单操作的执行次数。存储量需求指算法执行过程中所需要占用存储器的存储空间，以空间复杂度来衡量。时间复杂度：T(n)=O(f(n)其中的f(n)一般是算法中频度最大的语句频度，与问题的规模n有关。常见的时间复杂度，按数量级递增排列依次为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n),基本概念,算法,算法的描述用自然语言表示算法：就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来。用流程

4、图表示算法：就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法。用程序设计语言表示算法：用计算机能理解和执行的程序设计语言把算法表示出来，然后把程序输入计算机并执行，计算机才能按照预定的算法去解决问题。,基本概念,算法,基本数据结构,线性表:是n(nO)个同类型数据元素(结点)的有穷序列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成：(a1，a2，an),线性表的定义和基本特征,线性表,线性表逻辑结构的基本特征:存在惟一的一个被称为“第一个”的数据元素和惟一的一个被称为“最后一个”的数据元素；除第一个数据元素外，其他数据元素有且仅有一个直接前趋元

5、素；除最后一个数据元素外，其他数据元素有且仅有一个直接后继元素。,顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。,特点：逻辑结构中相邻的结点在存储结构中仍相邻,基本数据结构,线性表的顺序存储结构,线性表,顺序表,在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1)插入：在表的第i(1in+1)个位置上，插入一个新结点x，使线性表的长度加1。基本步骤为：将结点aian各后移一个位置,以便空出第i个位置；将新结点x置入第i个位置；表长加l,基本数据结构,插入、删除运算在顺序表上的实现,线性表,(2)删除：将表的第i(1in)个结点删去，使线性表的长度减1。

6、基本步骤为：结点ai+1an依次前移一个位置(覆盖被删结点ai)；表长减1,基本数据结构,插入、删除运算在顺序表上的实现,线性表,单链表是用一组任意的存储单元来存放线性表的结点。单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成；数据域用于存储线性表一个数据元素；指针域用于存放一个指针，该指针指向其直接后继结点。这样，所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次序不一定相同,特点：指针为数据元素之间的逻辑关系的映像,基本数据结构,线性表的链式存储结构,线性表,单链表,循环链表是一种首尾相接的链表,双向链表,就是在单链表的每个结点里再增加一个指向其直接前

7、趋的指针域prior,这样形成的链表就有两条不同方向的链。双(向)循环链表：头尾相链接的双向链表,基本数据结构,线性表的链式存储结构,线性表,其他链表,(1)插入：基本步骤如下：在单链表上找到插入位置；生成一个值为x的新结点；将新结点插入 假定指针p指向单链表中的第i-1个结点，s指向已生成的新结点，在单链表上插入结点s的操作过程如图所示。基本操作语句为：s-next=p-next；p-next=s；,基本数据结构,插入、删除运算在单链表上的实现,线性表,(2)删除：基本步骤如下：找到第i个结点；从单链表上摘除该结点。假定指针p指向待删结点的前一个结点，q指向待删结点，删除操作用c语言描述如下

8、：p-next=q-next；free(q)；执行free(q)的结果是释放q所指结点占用的内存空间。若在删除算法中无此语句，则结点q虽已不在单链表上，但仍被用户程序闲置性占用。,基本数据结构,线性表,插入、删除运算在单链表上的实现,栈和队列都是操作受限的线性表,基本数据结构,栈和队列,栈的逻辑结构和线性表相同，但是，栈(Stack)是仅限在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底,表中无元素时为空栈,栈,栈的运算原则是“先进后出”插入运算称为进栈(或入栈)删除运算称为退栈(或出栈)基本运算为：入栈、出栈、取栈顶元素,栈,顺序栈的进栈运算 将入栈元素放入

9、到栈顶下标所指的位置上,栈顶下标加l 顺序栈的退栈运算 退栈先将栈顶下标减1，再将栈顶元素取出,基本数据结构,栈和队列,队列,队列(Queue)，两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(real)，允许插入的一端称为队头(Front)。,基本数据结构,栈和队列,队列的操作原则是先进先出队列的顺序存储一般采用循环队列。把队列设想成一个循环表，即设想数组首尾相连。这种存储结构称为循环队。通常front指向队头元素的前一个位置，real指向队尾元素,树是n(n0)个结点的有限集合。在任意一棵非空树中:有且仅有一个特定的称为根的

10、结点：当nl时，其余结点分为m(m0)个互不相交的非空集合T1，T2，Tm，其中每一个集合本身又是一棵树，并称为根的子树。树是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”；所谓“层次”是指树上所有结点可以按它们的层数划分成不同的“层次”,基本数据结构,树,树型结构的基本概念和术语,(1)树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于O的结点称为非终端结点或分支结点。一棵树中所有结点的度的最大值称为该树的度。(2)若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子或子结点。父结

11、点相同的结点互称为兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙。反之，若B是A的子孙，则称A是B的祖先。(3)结点的层数(或深度)从根开始算起：根的层数为l，其余结点的层数为其双亲的层数加l。一棵树中所有结点层数的最大值称为该树的高度或深度。,基本数据结构,树,树型结构的基本概念和术语,二叉树,二叉树：是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：有且仅有一个称为根的结点；其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且Tl与T2有顺序关系(T1在T2之前)，它们分别称为根的左子树和右子树。二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次序关系。

12、二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。,基本数据结构,树,定义,形态和基本性质,二叉树有5种基本形态，如图所示,二叉树的基本性质 二叉树第i(i1)层上至多有2i-1个结点。深度为k(k1)的二叉树至多有2k-1个结点。对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,基本数据结构,树,二叉树,满二叉树 一棵深度为k(k1)且有2k-1个结点的二叉树称为满二叉树，这种树的特点是每一层上的结点数都是最大结点数。如图所示。,基本数据结构,树,形态和基本性质,二叉树,完全二叉树 深度为k(k1)有n个结点的二叉树，当且仅当其每一个结点都与深度

13、为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。如图所示。具有n个结点的完全二叉树的深度为log2n+l。,基本数据结构,树,形态和基本性质,二叉树,如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1in)的结点x有：若i=l，则结点x是根，无双亲；若i1，则x的双亲结点P的编号为i/2。若2in，则结点x无左孩子(且无右孩子)；否则，x的左孩子的编号为2i。若2i+1n，则结点x无右孩子；否则，x的右孩子的编号为2i+1。,基本数据结构,树,形态和基本性质,二叉树,二叉树的顺序存储 将一棵树中的所有n个结点按层编号，将编号为i的结点存入一维数组的第i个单元。若二叉

14、树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。,基本数据结构,树,存储结构,二叉树,二叉树的链式存储 结点结构中设两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。,基本数据结构,树,存储结构,二叉树,遍历,二叉树的遍历：就是按某种次序“访问”二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一次。二叉树是由三个基本单元组成

15、：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、DRL、LDR、LRD、RDL、RLD 6种遍历二叉树方案。若限定先左后右，则只有DLR、LDR、LRD三种情况，分别称之为先根(序)、中根(序)和后根(序)遍历。,基本数据结构,树,二叉树,(1)先根遍历 访问根结点；先根遍历左子树；先根遍历右子树。,基本数据结构,树,遍历,二叉树,(2)中根遍历 中根遍历左子树；访问根结点；中根遍历右子树。,(3)后根遍历 后根遍历左子树；后根遍历右子树；访问根结点,下图二叉树的三种遍历序列 先根遍历序列：1

16、、2、4、8、9、5、10、11、3、6、12、7 中根遍历序列：8、4、9、2、10、5、11、l、12、6、3、7 后根遍历序列：8、9、4、10、11、5、2、12、6、7、3、1,基本数据结构,树,遍历,二叉树,以顺序表作为存储结构查找过程：从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找失败。平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。长度为n的顺序表，在等概率情况下查找成功的平均查找长度为：(n

17、+1)2；若考虑到查找不成功的情形，则平均查找长度为：3(n+1)/4。,查找与排序,查找,顺序查找,二分查找(折半查找),对于任何一个顺序表，若其中的所有结点按键值的某种次序排列，则称为有序表。二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间(若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分)并在新的区间内重复上述过程，直到查找成功或查找区间长度为0(即查找不成功)为止。当有序表的长度为n时，时间复杂度为 o(log2n),查找与排序,查找,直接插入排序,依次将每个记录插入到一个有序的子序列中去。时间性能主要用于关键字的比较

18、和记录的移动直接插入排序算法的时、空性能 若各记录已排好序，关键字比较次数为n-1(最小值)，记录的移动次数为0(最小值)，时间复杂度是o(n)。当各记录恰好是逆序排序时，关键字比较次数为(n+2)(n-1)/2；记录的移动次数为(n-1)(n+4)/2。时间复杂度为o(n2)。平均时间复杂度为o(n2)；空间复杂度为o(1)。直接插入排序是稳定的排序。,查找与排序,排序,冒泡排序,首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使

19、得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，直至排序结束。若各记录已排好序，关键字比较次数为n-1(最小值)，记录的移动次数为0(最小值)。其时间复杂度是o(n)。当各记录恰好是逆序时,关键字比较次数为:(n+2)(n-1)/2(最大值)；记录的移动次数为:3n(n-1)/2(最大值)。此时的时间复杂度为o(n2);空间复杂度是o(1)。冒泡排序是稳定的排序。,查找与排序,排序,直接选择排序,首先在所有的记录中选出键值最小的记录，把它与第一个记录交换；然后在其余的记录中再选出键值最小的记录与第二个记录交换；依次类推，直至所有记录排序完成。在第i趟中，通过n-1次键值比较选出所需记录。直接选择排序算法的时、空性能 无论待排序的记录初始序列如何，直接选择排序都要执行n(n-1)/2次关键字比较。如果待排序的记录初始序列就是已排好序的正序，则不做记录移动，即移动记录0次：如果待排序的记录初始序列恰好是逆序，则要做3(n-1)次记录移动。直接选择排序是不稳定的排序，其时间复杂度是o(n2)，空间复杂度为o(1)。,查找与排序,排序,