第1章数据结构与算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 数据结构与算法,第一节 算法,第二节 数据结构的基本概念,第三节 线性表及其顺序存储结构,第四节 栈和队列,第五节 线性链表,第六节 树与二叉树,第七节 查找技术,第八节 排序技术,第一节 算法,一、算法的基本概念,所谓算法是指解题方案的准确而完整的描述。,1,、算法的基本特征,（,1,）可行性,:,算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被,0,除的操作就是无效的，应当避免这种操作。,（,2,）确定性,:,算法中每一步的含义必须是确切的，不可出现任何二义性，如举起手；,（,3,）有穷性,:,一个算法必须在执行有限个操作步骤后终止,；,（,4,）拥有足够的情报（,有零个或多个输入、有一个或多个输出）,例：全真（,1,）,5,第一节 算法,一、算法的基本概念,2,、算法的基本要素,（,1,）算法中对数据的运算和操作,算术运算：加减乘除等,逻辑运算：与、或、非运算,关系运算：大于、小于、等于、不等于等运算,数据传输：赋值、输入、输出等运算,第一节 算法,一、算法的基本概念,2,、算法的控制结构,算法中各操作之间的执行顺序称为算法的控制结构。,一个算法可以用,顺序、选择、循环,三种基本控制结构组合而成。,第一节 算法,一、算法的基本概念,2,、算法设计的基本方法,（,1,）列举法：,根据提出的问题，列出所有可能的情况。,（,2,）归纳法：,通过列举少量的特殊情况，经过分析，得出一般的关系。,（,3,）递推：,从已知的初始条件出发，逐次递推出所要求的各中间结果和最后结果。,第二节 数据结构的基本概念,一、什么是数据结构,数据结构是指相互有关联的数据元素的集合。,如：春、夏、秋、冬,父亲、儿子、女儿,（,1,）数据元素有共同的特征,（,2,）各个元素之间存在着某种关系（联系）。用前后件关系来描述。如：夏是秋的前件，秋是夏的后件。父亲是儿子和女儿的前件，儿子和女儿都是父亲的后件,第二节 数据结构的基本概念,一、什么是数据结构,1,、数据的逻辑结构,数据结构是指带有结构的数据元素的集合。一个数据结,构应包含以下两方面的信息：,（,1,）表示数据元素的信息,（,2,）表示各数据元素之间的前后件关系，前后件关系是逻辑关系，与它们在计算机中的存储位置无关。,数据的逻辑结构反映数据元素之间的,逻辑关系,。,第二节 数据结构的基本概念,一、什么是数据结构,2,、数据的存储结构,数据的逻辑结构在计算机中的存放形式称为数据的存储,结构，也称数据的物理结构。,采用不同的存储结构，数据处理的效率不同。,一般情况下，数据的逻辑结构和存储结构是不同的。,例：全真（,3,）,6,第二节 数据结构的基本概念,二、数据结构的图形表示,每一个数据元素用中间标有元素值的方框表示，称为数,据结点，简称结点。用一条有向线段从前件结点指向后,件结点。,春,夏,秋,冬,父亲,儿子,女儿,第二节 数据结构的基本概念,二、数据结构的图形表示,在数据结构中，没有前件的结点称为,根结点,，没有后件,的结点称为终端结点（也称为叶子结点）。其他结点一,般称为内部结点。,插入与删除是对数据结构的两种基本运算,还有查找、分类、合并、分解、复制和修改等运算,第二节 数据结构的基本概念,三、线性结构与非线性结构,根据各数据元素之间前后件关系，将数据结构分为：,线性结构与非线性结构,线性结构满足以下两个条件：,（,1,）有且只有一个根结点,（,2,）每一个结点最多只有一个前件，也最多有一个后件,线性结构又称为,线性表,。,第三节 线性表及其顺序存储结构,一、线性表的基本概念,线性表是由,n,个数据元素,a,1,，,a,2,a,n,组成的一个有限序,列，表中的每一个数据元素，除了第一个外，有且只有,一个前件，除了最后一个外，有且只有一个后件。,特征：（,1,）有且只有一个根结点,a,1,，它无前件。,（,2,）有且只有一个终端结点,a,n,，它无后件。,（,3,）其它结点有且只有一个前件和一个后件。,线性表中结点的个数,n,称为线性表的长度，,n,为,0,称为空表,第三节 线性表及其顺序存储结构,二、线性表的顺序存储结构,线性表的顺序存储结构具有以下特点,（,1,）线性表中所有元素所占的存储空间是连续的。,（,2,）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,其特点可归结为：逻辑关系上相邻的两个元素在物理位置上也相邻，因此可随机存取任一元素。,其缺点是：插入或删除时，需移动大量元素。,a,1,a,2,a,i,a,n,第三节 线性表及其顺序存储结构,三、线性表的插入运算,要在第,i,个元素前插入一个,新元素，要从最后一个元,素开始，直到第,n-i+1,个元,素依次向后移动一个位置,第,i,个位置就被空出，然后,将新元素插入到第,i,项。,1,2,3,4,5,6,7,8,29,18,56,63,35,24,31,47,1,2,3,4,5,6,7,8,29,87,18,56,63,35,24,31,47,87,第三节 线性表及其顺序存储结构,四、线性表的删除运算,要删除第,i,个元素，要从第,i+1,个元素开始，直到第,n,个元素之间共,n-i,个元素依,次向前移动一个位置。,1,2,3,4,5,6,7,8,29,18,56,63,35,24,31,47,1,2,3,4,5,6,7,8,18,56,63,35,24,31,47,第四节 栈和队列,一、栈及其基本运算,栈是一种特殊的线性表。,一端是封闭的，不允许进行插入与删除，另一端是开口,的，允许进行插入与删除。允许插入与删除的一端被称为,栈顶,，另一端被 称为,栈底,，不含元素的称为,空栈,。,如：子弹夹,栈中的元素遵循“先进后出”或“后进先出”的原则,例：全真（,1,）,7,第四节 栈和队列,二、队列及其基本运算,队列是指允许在一端进行插入，而在另一端进行删除的,线性表。,允许插入的一端称为,队尾,，允许删除的一端称为排头,（也称为,队头,）。,遵循“先进先出”或“后进后出”的原则，体现了“先来先,服务”的原则,第四节 栈和队列,二、队列及其基本运算,队列有两种存储表示：链队列和循环队列。,用链表表示的队列称为链队列，它需要头指针和尾指针惟一确定。,循环队列,队列的顺序表示和实现,在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一位置。,2,3,4,5,第五节 线性链表,一、线性表的缺点,（,1,）插入与删除的效率低,（,2,）线性表的存储空间不便于扩充,（,3,）不便于对存储空间的动态分配,第五节 线性链表,二、线性链表的概念,在链式存储方式中，要求每个结点由两部分组成：,一部分用于存放数据元素值，称为数据域。,另一部分用于存放指针，称为指针域。,V(i)Next(i),数据域 指针域,第五节 线性链表,二、线性链表的概念,线性表的链式存储结构称为线性链表。,在线性链表中，各数据元素之间的前后件关系由各结点的,指针域来表，指向第一个结点的指针,HEAD,称为头指针。,数据,1,数据,1,数据,1 null,head,第五节 线性链表,二、线性链表的特点,线性表的链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点（插入或删除时，需移动大量元素），但同时也失去了顺序表可随机存取的优点。,第六节 树与二叉树,一、树的基本概念,树是一种简单的非,线性结构，所有元,素之间的关系具有,明显的层次特征。,R,K,P,Q,D,B,E,C,H,M,F,N,X,Y,G,O,S,T,W,A,L,Z,第六节 树与二叉树,1,、树的基本术语,（,1,）每一个结点只有一个前件，称为该结点的,父结点,（,2,）没有前件的结点只有一个，称为,根结点,（,3,）每一个结点可以有多个后件，称为该结点的,子结点,（,4,）没有后件的结点称为,叶子结点,（,5,）每一个结点所拥有的后件个数称为该结点的,度,，叶子结点的度为,0,（,6,）所有结点中的最大的度称为,树的度,第六节 树与二叉树,1,、树的基本术语,（,7,）树的最大层次称为树的,深度,（结点的层次从根开始定义）,（,8,）在树中，以某结点的一个子结点为根构成的树称为该结点的一棵,子树,。叶子结点没有子树。,第六节 树与二叉树,二、二叉树及其基本性质,1,、什么是二叉树,（,1,）非空二叉树只有一个根结点,（,2,）每一个结点最多有两棵子树，称为左子树与右子树,即每一个结点的度最大为,2,第六节 树与二叉树,二、二叉树及其基本性质,2,、二叉树的基本性质,（,1,）在第,k,层上，最多有,2,k-1,（,k1,）个结点,（,2,）深度为,m,的二叉树最多有,2,m,-1,个结点,（,3,）度为,0,的结点（即叶子结点）比度为,2,的结点多,1,个,（,4,）具有,n,个结点的二叉树，其深度至少为,log,2,n+1,其中,log,2,n,表示的,log,2,n,整数部分。,第六节 树与二叉树,二、二叉树及其基本性质,3,、满二叉树与完全二叉树,（,1,）满二叉树指，除最后一层外，每一层上的所有结点都有两个子结点。即每一层上的结点数均达到最大值。,满二叉树的第,k,层上有有,2,k-1,个结点,深度为,m,的满二叉树有,2,m,-1,个结点,第六节 树与二叉树,满二叉树,A,B,D,E,H,I,H,I,B,D,E,H,I,H,I,第六节 树与二叉树,二、二叉树及其基本性质,3,、满二叉树与完全二叉树,（,2,）完全二叉树指，除最后一层外，每一层上的结点数均达到最大值。在最后一层上只缺少右边的若干结点。,满二叉树是完全二叉树，但完全二叉树一般不是满二叉树,第六节 树与二叉树,完全二叉树,A,B,D,E,H,I,H,I,B,D,E,H,第六节 树与二叉树,三、二叉树的遍历（递归方法）,1,、前序遍历（,DLR,）,（,1,）访问根结点,（,2,）前序遍历左子树,（,3,）前序遍历右子树,第六节 树与二叉树,三、二叉树的遍历（递归方法）,2,、中序遍历（,LDR,）,（,1,）中序遍历左子树,（,2,）访问根结点,（,3,）中序遍历右子树,第六节 树与二叉树,三、二叉树的遍历（递归方法）,3,、后序遍历（,LRD,）,（,1,）后序遍历左子树,（,2,）后序遍历右子树,（,3,）访问根结点,第七节 查找技术,查找是指在一个给的数据结构中查找某个指定的元素。,1,、顺序查找,顺序查找一般是指在线性表中查找指定的元素。,过程：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等则表示找到（查找成功）。若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示没有找到要找的元素（查找失败）。,第七节 查找技术,2,、二分法查找,二分法查找只适用于顺序存储的有序表。,方法：设有序线性表的长度为,n,，被查元素为,x,（,1,）将,x,与线性表的中间项进行比较；,（,2,）做中间项等于,x,，则说明查到，查找结束；,（,3,）若,x,小于中间项，则线性表的前半部分以相同的方法继续进行查找。,（,4,）若,x,大于中间项，则线性表的后半部分以相同的方法继续进行查找。,第八节 排序技术,一、交换类排序法,1,、冒泡排序法,2,、快速排序法,第八节 排序技术,二、插入类排序法,1,、简单插入排序法,2,、希尔排序法,第八节 排序技术,三、选择类排序法,思想：扫描整个线性表，从中选中最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法。,1,、简单选择排序法,2,、堆排序法,