算法与基本数据结构.ppt

算法与基本数据结构,1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,算法与基本数据结构,基本概念 基本数据结构 查找与排序,基本概念,数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。,数据结构的定义,数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，有时也称为元素、结点、顶点或记录,结构：是数据元素之间的关联关系,数据结构：数据结构带有结构的同性质数据元素的集合,数据结构包括以下三方面内容：逻辑结构、存储结构和对数据结构的操作 逻辑结构：数据元素之间逻辑上的关系，它是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构。具体可分为四类：集合 线性结构 树型结构 图状结构 其中、为非线性结构,基本概念,数据结构的内容,存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分：,基本概念,数据结构的内容,存储结点(简称结点),每个结点存放一个数据元素 数据元素之间关系的表示，也就是逻辑结构的计算机内部表示常用的数据存储结构：顺序存储方法链式存储方法索引存储方法散列存储方法数据的运算如查找、排序、增加、修改、删除,各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,数据的存储结构,数据的存储结构,链式存储结构是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系,算法：算法是对具体问题求解过程和步骤的一种描述，简单地说，就是解决问题的操作步骤。,基本概念,算法,算法四个基本特征：有穷性：算法在特定的执行环境中执行应当能够得出 满意的结果，即必须有一个或多个输出。确定性：对算法中的每一步的描述是明确的，无歧义 可行性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。拥有足够的情报：算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效。,算法通常由两个基本要素组成：对数据对象的运算和操作算法的控制结构,基本概念,算法,算法复杂度包括：时间复杂度：指执行算法时所需要的计算工作量，通常是用算法所执行的基本运算次数来度量。注：算法程序执行的具体时间和算法的时间复杂度并不是一致的。空间复杂度：指执行这个算法所需要的内存空间。,算法的描述用自然语言表示算法：就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来。用流程图表示算法：就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法。用程序设计语言表示算法：用计算机能理解和执行的程序设计语言把算法表示出来，然后把程序输入计算机并执行，计算机才能按照预定的算法去解决问题。,基本概念,算法,算法设计要求：正确性 可读性 健壮性效率高与低存储需求,基本概念,算法,基本数据结构,线性表:是n(nO)个同类型数据元素(结点)的有穷序列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成：(a1，a2，an),线性表的定义和基本特征,线性表,线性表逻辑结构的基本特征:存在惟一的一个被称为“第一个”的数据元素和惟一的一个被称为“最后一个”的数据元素；除第一个数据元素外，其他数据元素有且仅有一个直接前趋元素；除最后一个数据元素外，其他数据元素有且仅有一个直接后继元素。,顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。,特点：逻辑结构中相邻的结点在存储结构中仍相邻,基本数据结构,线性表的顺序存储结构,线性表,顺序表,应用范围：适合于小线性表或者建立之后其中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。,在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1)插入：在表的第i(1in+1)个位置上，插入一个新结点x，使线性表的长度加1。基本步骤为：将结点aian各后移一个位置,以便空出第i个位置；将新结点x置入第i个位置；表长加l,基本数据结构,插入、删除运算在顺序表上的实现,线性表,(2)删除：将表的第i(1in)个结点删去，使线性表的长度减1。基本步骤为：结点ai+1an依次前移一个位置(覆盖被删结点ai)；表长减1,基本数据结构,插入、删除运算在顺序表上的实现,线性表,单链表是用一组任意的存储单元来存放线性表的结点。单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成；数据域用于存储线性表一个数据元素；指针域用于存放一个指针，该指针指向其直接后继结点。这样，所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次序不一定相同,特点：指针为数据元素之间的逻辑关系的映像,基本数据结构,线性表的链式存储结构,线性表,单链表,循环链表是一种首尾相接的链表,双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。双(向)循环链表：头尾相链接的双向链表,基本数据结构,线性表的链式存储结构,线性表,其他链表,(1)插入：基本步骤如下：在单链表上找到插入位置；生成一个值为x的新结点；将新结点插入 假定指针p指向单链表中的第i-1个结点，s指向已生成的新结点，在单链表上插入结点s的操作过程如图所示。基本操作语句为：s-next=p-next；p-next=s；,基本数据结构,插入、删除运算在单链表上的实现,线性表,(2)删除：基本步骤如下：找到第i个结点；从单链表上摘除该结点。假定指针p指向待删结点的前一个结点，q指向待删结点，删除操作用c语言描述如下：p-next=q-next；free(q)；执行free(q)的结果是释放q所指结点占用的内存空间。若在删除算法中无此语句，则结点q虽已不在单链表上，但仍被用户程序闲置性占用。,基本数据结构,线性表,插入、删除运算在单链表上的实现,栈和队列都是操作受限的线性表,基本数据结构,栈和队列,栈的逻辑结构和线性表相同，但是，栈(Stack)是仅限在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底,表中无元素时为空栈,栈,栈的运算原则是“先进后出”插入运算称为进栈(或入栈)删除运算称为退栈(或出栈)基本运算为：入栈、出栈、取栈顶元素,栈的特点：,基本数据结构,栈和队列,（1）栈顶元素总是最后被插入的元素，也是最早被删除的元素。（2）栈底元素总是最早被插入的元素，也是最晚被删除的元素。（3）栈具有记忆作用。（4）在顺序存储结构下，栈的插入与删除运算都不需要移动其他元素。（5）栈顶指针Top动态反映了栈中元素的变化情况。,栈,栈,顺序栈的进栈运算 将入栈元素放入到栈顶下标所指的位置上,栈顶下标加l 顺序栈的退栈运算 退栈先将栈顶下标减1，再将栈顶元素取出,基本数据结构,栈和队列,队列,队列(Queue)，两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。,基本数据结构,栈和队列,队列的操作原则是先进先出队列的顺序存储一般采用循环队列。把队列设想成一个循环表，即设想数组首尾相连。这种存储结构称为循环队。通常front指向队头元素的前一个位置，real指向队尾元素,树是n(n0)个结点的有限集合。在任意一棵非空树中:有且仅有一个特定的称为根的结点：当nl时，其余结点分为m(m0)个互不相交的非空集合T1，T2，Tm，其中每一个集合本身又是一棵树，并称为根的子树。树是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”；所谓“层次”是指树上所有结点可以按它们的层数划分成不同的“层次”,基本数据结构,树,树型结构的基本概念和术语,(1)树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于O的结点称为非终端结点或分支结点。一棵树中所有结点的度的最大值称为该树的度。(2)若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子或子结点。父结点相同的结点互称为兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙。反之，若B是A的子孙，则称A是B的祖先。(3)结点的层数(或深度)从根开始算起：根的层数为l，其余结点的层数为其双亲的层数加l。一棵树中所有结点层数的最大值称为该树的高度或深度。,基本数据结构,树,树型结构的基本概念和术语,二叉树,二叉树：是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：有且仅有一个称为根的结点；其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且Tl与T2有顺序关系(T1在T2之前)，它们分别称为根的左子树和右子树。二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次序关系。二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。,基本数据结构,树,定义,二叉树,二叉树的特点：（1）二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点。（2）每个结点最多有两颗子树，即二叉树中不存在度大于2的结点。（3）二叉树的子树有左右之分，其次序不能任意颠倒。,基本数据结构,树,特点,形态和基本性质,二叉树有5种基本形态，如图所示,二叉树的基本性质 二叉树第i(i1)层上至多有2i-1个结点。深度为k(k1)的二叉树至多有2k-1个结点。对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,基本数据结构,树,二叉树,满二叉树 一棵深度为k(k1)且有2k-1个结点的二叉树称为满二叉树，这种树的特点是每一层上的结点数都是最大结点数。如图所示。,基本数据结构,树,形态和基本性质,二叉树,完全二叉树 深度为k(k1)有n个结点的二叉树，当且仅当其每一个结点都与深度为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个单元。若二叉树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。,基本数据结构,树,存储结构,二叉树,二叉树的链式存储（通常存储方式）结点结构中设两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。,基本数据结构,树,存储结构,二叉树,遍历,二叉树的遍历：就是按某种次序“访问”二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一次。二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、DRL、LDR、LRD、RDL、RLD 6种遍历二叉树方案。若限定先左后右，则只有DLR、LDR、LRD三种情况，分别称之为先根(序)、中根(序)和后根(序)遍历。,基本数据结构,树,二叉树,(1)先根（前序）遍历 访问根结点；先根遍历左子树；先根遍历右子树。,基本数据结构,树,遍历,二叉树,(2)中根（中序）遍历 中根遍历左子树；访问根结点；中根遍历右子树。,(3)后根（后序）遍历 后根遍历左子树；后根遍历右子树；访问根结点,下图二叉树的三种遍历序列 先根遍历序列：1、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,基本数据结构,树,遍历,二叉树,以顺序表作为存储结构查找过程：从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找失败。时间复杂度分析：（1）第一个元素就是要查找的元素，则比较次数为1次。（2）最后一个元素是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为n次。（3）需要比较n/2次。因此查找算法的时间复杂度为O(n)。,查找与排序,查找,(1)顺序查找,当线性表为无序表，不管何种存储结构，只能用顺序查找。,即使是有序线性表，如果采用链式存储结构，也只能用顺序查找,(2)二分查找(折半查找),“有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间(若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分)并在新的区间内重复上述过程，直到查找成功或查找区间长度为0(即查找不成功)为止。当有序表的长度为n时，时间复杂度为 o(log2n)，即在最坏的情况下，二分查找只需比较 次。,查找与排序,查找,使用二分查找的线性表满足两个条件：用顺序存储结构线性表是有序表,排序方法分类：,（1）交换类排序法：借助数据元素的“交换”来进行的一种方法。（A）冒泡排序法（B）快速排序法（2）插入类排序方法：每次将一个待排序的元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。（A）简单插入排序法（B）希尔排序法（3）选择类排序法：通过每一趟从排序序列中选出值最小的元素，顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。（A）简单选择排序法（B）堆排序法,查找与排序,排序,交换类排序：冒泡排序,首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，直至排序结束。冒泡排序每一遍的从前到后扫描都把排序范围内的最大元素沉到了表的底部，每一遍的从后往前扫描，都把排序范围内的最小元素像气泡一样浮到了表的最前面。在最坏的情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2。,查找与排序,排序,思想：通过两两相邻数据元素之间的比较和交换，不断消去逆序，直到所有数据元素有序为止。,交换类排序：快速排序法,查找与排序,排序,基本思想：在待排序的n个元素中取一个元素K（通常取第一个元素），以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为1为止，这时，线性表已经排好序了。快速排序的平均时间效率最佳，为O()。快速排序被认为是目前所有排序算法中最快的一种。,插入类排序：简单插入排序法,基本思想：把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表含有一个元素，而无序表中包含另外n-1个元素，每次取无序表中的第一个元素插入到有序表的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其其后的记录依次向后移动。最后有序表的长度为n，而无序表的长度为空，此时排序完成。在最坏的情况下，对长度为n的线性表排序，简单插入排序需要比较的次数为n(n-1)/2。最好的比较次数为n-1。,查找与排序,排序,插入类排序：希尔排序法,查找与排序,排序,基本思想：先取一个整数（称为增量）d1n，把全部数据分为d1个组，所有距离为d1倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序。然后取d2d1重复上述分组和排序工作；直至di=1，即所有记录在一组中为止。在最坏的情况下，希尔排序所需要的比较次数为O(),选择类排序：简单选择排序法,基本思想：首先从所有的n个待排序的数据元素中选择最小的元素，讲该元素与第1个元素交换，再从剩下的n-1个元素中选择最小的元素与第2个元素交换。重复这样的操作直到所有元素有序为止。在最坏的情况下，对长度为n的线性表排序，简单选择排序需要比较的次数为n(n-1)/2。,查找与排序,排序,选择类排序：堆排序法,查找与排序,排序,最坏的情况下，堆排序需要比较的次数是,各种排序法比较,