数据结构与算法.ppt

第一章 数据结构与算法,1.1算法,算法的基本概念 所谓算法是指解题方案的准确而完整的描述。,一.算法的基本特征,可行性:执行后能得到满意结果。确定性:算法中每个步骤必须明确定义，不允许多义性。有穷性:算法必须在有限时间内做完。拥有足够的情报:确保算法有效还取决于情报是否足够。,二.算法的基本要素,算法对数据的运算和操作：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序、选择、循环,四.算法复杂度,算法的时间复杂度执行算法所需要的计算工作量算法的空间复杂度执行算法所需要的内存空间,1.2数据结构的基本概念,数据结构作为计算机的一门学科，主要研究以下三个方面的问题:P71.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。2.在对数据进行处理时，各数据元素在计算机中在存储关系，即数据的存储结构。3.对各种数据结构进行的运算。,一.数据的逻辑结构,数据结构是指相互有关联的数据元素的集合。更通俗地说，数据结构是指带有结构的数据元素的集合。P11一个数据结构应包含以下两个方面的信息：元素的信息数据元素之间的前后件关系。所谓数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。,前后件：前驱、后件。,二.数据的存储结构,数据的逻辑结构是在计算机存储空间的存放形式称为数据的存储结构。,三.数据结构的图形表示,A,B,C,D,E,F,其中D称为是E的前件,C的后件.其他相同.,父亲,儿子,女儿,其中“父亲”是“儿子”和“女儿”的前件，“儿子”和“女儿”是“父亲”的后件。,四.线性结构和非线性结构,空数据结构:一个元素都没有。数据结构一般分为:线性结构和非线性结构。非空线性结构满足:有且只有一个根节点；每个节点最多有一个前件节点、也最多有一个后件节点。如果一个数据结构不是线性结构，则称之为非线性结构。,1.3线性表与顺序存储结构,线性表是最简单、最常用的一种数据结构。线性表是n(n=0)个元素构成的有限序列(a1,a2,an)。(1)有且只有一个根结点a1,它无前件；(2)有且只有一个终端结点an,它无后件；(3)其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数称为线性表的长度,当n=0时，称为空表.,一.线性表的顺序存储结构,线性表在计算机中采用顺序存储。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个特点:线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,二.线性表的插入运算,线性表为:(a1,a2 ai-1,ai,ai+1an)在第i个位置之前上插入新的结点x:线性表变为:(a1,a2 ai-1,x,ai,ai+1an)长度变为n+1。在最好的情况下,不需要移动表中的元素。在最坏的情况下,需要移动表中的所有元素。在平均情况下,需要移动表中一半的元素。,三.线性表的删除运算,线性表为:(a1,a2 ai-1,ai,ai+1an)在第i个位置上删除新的结点ai:线性表变为:(a1,a2 ai-1,ai+1an)长度变为n-1。在最好的情况下,不需要移动表中的元素。在最坏的情况下,需要移动表中的所有元素。在平均情况下,需要移动表中一半的元素。,1.4栈和队列,1.什么是栈？栈是限定在一端进行插入和删除运算的线性表。允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。假设栈s=(a1,a2,an),则a1称为栈底元素，an成为栈顶元素。栈也称为先进后出或后进先出的线性表。,1.4栈和队列,进栈,退栈,top,bottom,栈:后进先出表,1.4栈和队列,2.栈的顺序存储及其运算 P21,栈空,栈满,正常,进栈时会发生上溢错误,退栈时会发生下溢错误,1.4栈和队列,1.什么是队列 队列是指只允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头.假设队列q=(a1,a2,an),则a1称为队头元素，an成为队尾元素。,队列(queue)的运算示意,一个队列,插入(入队),删除(退队),1.4栈和队列,2.循环队列及其算法循环队列：将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。,1.4栈和队列,front,rear,分析可知：当front=rear时，不能确定循环队列是空还是满，于是需要要一个标记S,用来判断队列的状态:S=0 表示队列为空S=1 表示队列为非空,由此得出：队列为空的条件是:s=0队列为满的条件是:s=1且front=rear,1.5线性链表,1.什么是链式存储？线性表顺序存储的缺点：插入删除时移动大量元素；有“上溢”情况；空间不便于动态分配。在链式存储方式中,每个结点有两部分组成:一部分用于存放数据元素的值,称为数据域；另一部分存放指针,称为指针域。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的.,2.线性单链表,在线性单链表中,结点的数据域存放数据元素的值,指针域存放下一个数据元素的存储序号,即指向后件结点.,1,1,10,10,6,6,8,8,3.线性双向链表,在线性单链表中从一个结点只能找到它的下一个结点,但找不到前一个结点.为解决这一问题,将线性链表中每一个结点设置两个指针:左指针和右指针.这样的链表称为双向链表.,head,4.带链的栈和队列 P27,(1)栈也是线性表。带链的栈称为可利用栈。,(2)队列也是线性表。也可以采用链式存储结构。,5.线性链表的基本运算,插入：删除：合并：分解：逆转：复制：排序：查找：,(1).在线性链表中查找指定元素,在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法:从头结点指向的结点开始往后沿指针进行扫描,直到后面已没有结点或下一个结点的数据域为x为止.,(2).线性链表的插入,线性链表插入过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。,(3).线性链表的删除,线性链表删除过程中不发生数据元素移动现象，只要改变有关结点的指针即可，提高了效率。,6.双向链表的基本运算(插入),6.双向链表的基本运算(删除),7.循环链表及其基本运算,单链表的最后一个结点的指针域为HULL;如果将它改为存放链表中头结点的地址，这样就构成了一个环。,其插入与删除操作与单链表相同,1.6树与二叉树,树是一种简单的非线性结构.具有层次结构。基本术语:P32父结点、根结点、子结点、叶子结点。结点的度、树的度，树的深度、子树。,a,b,c,s,d,q,w,v,x,u,v,e,r,f,g,h,t,p,y,n,m,1.二叉树的定义,非空二叉树具有以下两个特点：(1)非空二叉树只有一个根结点(2)每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。在二叉树中，每一个结点的度最大为2，即所有子树也均为二叉树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树，当一个结点既没有左子树也没有右子树时，该结点称为叶子结点。,2.二叉树的基本性质,性质1:在二叉树的第k层上至多有2K-1个结点性质2:深度为m的二叉树至多有2m-1个结点。性质3:对任意一棵二叉树，度为0的结点数总比度为2的结点数多1。(n0=n2+1)性质4:具有n个结点的完全二叉树深度至少为log2n+1。(性质2反推),3.满二叉树与完全二叉树,满二叉树:除最后一层外,每一层上的所有结点都有两个子结点.即所有层的结点数均达到最大值.完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点.,3.满二叉树与完全二叉树,完全二叉树还具有以下两个性质：性质5:具有n个结点的完全二叉树的深度为log2n+1性质6:设完全二叉树共有n个结点，如果从根结点开始，按层序用自然数1,2,3n给结点进行编号，则对于编号为k的结点有如下特点：若k=1则该结点为要根结点。若2k=n，则编号为k的结点，其左子树为2k,右结点为2k+1若2k+1=n，则编号为k的结点的右子树编号为2k+1。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,4.二叉树的存储结构,在计算机中，二叉树通常采用链式存储结构。存储结点的结构:数据域,左指针域,右指针域。,5.二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点.(1)前序遍历(根-左-右)(2)中序遍历(左-根-右)(3)后序遍历(左-右-根),前序遍历：中序遍历：后序遍历：,前序遍历：中序遍历：后序遍历：,1.7查找技术,所谓查找是指在一个给定的数据结构中查找某个指定的元素。1.顺序查找:从表的一端开始,顺序扫描,依次将扫描的关键字和待寻找的k值比较,若相等,则查找成功;若扫描完毕,仍未找到,则扫描失败。以下情况只能采用顺序查找:(1)线性表示无序表；(2)有序线性表采用链式存储结构,平均情况下，大约要与表中一半的元素进行比较.,最坏情况下，要查找n次.,1.7查找技术,2.二分法查找:只适用于顺序存储的有序表.设有序表的长度为n,被查元素为x,则查找方法:将x与线性表的中间项相比较；若中间项等于x,则说明查到，查找结束；若x小于中间项,则在线性表的前半部分查找;若x大于中间项,则在线性表的后半部分查找.,最坏的情况下，查找 log2n 次,1.7查找技术,8，17，25，44，68，77，98，100，115，125,查找k=98,一次查找后:,二次查找后:,三次查找:,最坏的情况下，查找 log2n 次,成功,1.8排序技术,所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列.交换类排序法插入类排序法选择类排序法,交换类排序法,1.冒泡排序:是一种最简单的交换类排序法,它是通过相邻数据元素的交换逐步将线性表变成有序.从表头开始扫描整个线性表,比较相邻两个数据的大小,若前面的数大于后面的数,则将它们进行交换.依次进行,则第一次可找出最大的数.此后,将其余的数再进行相同的比较.,最坏的情况下，查找 n(n-1)/2 次,原序列,49 38 65 97 76 13 27 30,38,49,76,97,97,13,27,97,97,30,2.快速排序,任取待排序列中的某个元素（一般为第一个元素）作基准，通过一趟排序，将待排元素分为左右两个子序，左子序列元素排序码均小于或等于基准元素排序码，右子序列元素排序码均大于基准元素排序码。然后分别对两个子序排序，直至整个序列有序。,插入类排序,每次将一个待排的纪录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。简单插入排序法希尔排序法,一、简单插入排序示例,简单的插入类排序最坏的情况：n(n-1)/2,2.希尔排序法,先将整个待排元素序列分割成若干个子序列，分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。,在最坏的情况下：希尔排序法需要的比较次数是 O(n1.5),选择类排序,每一趟从待排序的记录中选出关键字最小的纪录，顺序放在已排好序的子序列最后。直到全部记录排序完毕。简单选择排序法堆排序法,简单的选择排序的过程示例,最坏的简单选择类排序法需要比较n(n-1)/2 次,1.堆排序,图,91,85,53,36,47,30,24,12,所有根结点的大于或等于左右孩子的值-大根堆。,所有根结点的小于或等于左右孩子的值-小根堆。,在最坏的情况下：堆排序法需要的比较次数是 O(nlog2n),查找技术,排序技术,顺序查找,二分法查找,交换类排序,插入类排序,选择 类排序,快速排序法,冒泡排序法,希尔排序法,简单插入排序法,简单选择排序法,堆排序法,n,log2n,O(nlog2n),n(n-1)/2,最快情况下的次数（时间复杂度）,