数据结构和算法.ppt

数据结构和算法现在学习的是第1页，共54页数据结构(Data Structure)是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。线性结构：结构中的数据元素之间存在一对一的关系。树型结构：结构中的数据元素之间存在一对多的关系。图状结构或网状结构：结构中的数据元素之间存在多对多的关系。现在学习的是第2页，共54页数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。现在学习的是第3页，共54页逻辑结构和物理结构数据的逻辑结构数据的逻辑结构非线性结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列数据逻辑结构层次关系图数据逻辑结构层次关系图图图1-4 逻辑结构与所采用的存储结构逻辑结构与所采用的存储结构线性表线性表树树图图顺序存储结构顺序存储结构链式存储结构链式存储结构复合存储结构复合存储结构逻辑结构逻辑结构物理结构物理结构现在学习的是第4页，共54页数据结构的运算数据结构的主要运算包括：建立(Create)一个数据结构；消除(Destroy)一个数据结构；从一个数据结构中删除(Delete)一个数据元素 把一个数据元素插入(Insert)到一个数据结构中；对一个数据结构进行访问(Access)；对一个数据结构(中的数据元素)进行修改(Modify)；对一个数据结构进行排序(Sort)；对一个数据结构进行查找(Search)。现在学习的是第5页，共54页线性表线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：存在一个唯一的被称为“第一个”的数据元素；存在一个唯一的被称为“最后一个”的数据元素；除第一个元素外，每个元素均有唯一一个直接前驱；除最后一个元素外，每个元素均有唯一一个直接后继。现在学习的是第6页，共54页线性表的顺序存储 在高级语言(如C语言)环境下，数组具有随机存取的特性，因此，借助数组来描述顺序表。顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等现在学习的是第7页，共54页线性表的链式存储用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中结点的一组任意的存储单元以是连续的或不连续的，甚至是零散分布在内存中的任意位置。为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。现在学习的是第8页，共54页双向链表双向链表(Double Linked List)指的是构成链表的每个结点中设立两个指针域，一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双向链表一般增加头指针也能使双链表的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。双向链表是为了克服单链表的单向性的缺陷而引入的。现在学习的是第9页，共54页双向链表的结点及其类型定义data nextprior双向链表结点形式双向链表结点形式非空双向链表非空双向链表heada2a1an空双向链表空双向链表head带头结点的双向链表形式带头结点的双向链表形式现在学习的是第10页，共54页栈和队列 栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。栈在计算机的实现有多种方式：硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；软堆栈：这类堆栈主要在内存中实现。实现方式又有动态方式和静态方式两种。现在学习的是第11页，共54页栈的基本概念 栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(Last In First Out)或先进后出FILO(First In Last Out)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。现在学习的是第12页，共54页栈的顺序存储表示 栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否根据需要增大，又分为静态顺序栈和动态顺序栈。静态顺序栈实现简单，但不能根据需要增大栈的存储空间；动态顺序栈根据需要增大栈的存储空间，但实现稍为复杂。现在学习的是第13页，共54页栈的链式存储表示 栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针现在学习的是第14页，共54页栈的应用 由于栈具有的“后进先出”的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子 后缀表达式计算 中缀表达式变后缀表达式 栈与递归调用的实现现在学习的是第15页，共54页队 列队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。队首(front)：允许进行删除的一端称为队首。队尾(rear)：允许进行插入的一端称为队尾。队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，即队列的修改是依先进先出的原则进行的现在学习的是第16页，共54页循环队列 为充分利用向量空间，克服“假溢出”现象，将队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。123450(a)空队列空队列frontrear123450(b)d,e,b,g入入队队frontdebgrear123450(c)d,e出队出队bgfrontrear现在学习的是第17页，共54页队列的链式表示和实现 队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点现在学习的是第18页，共54页树与二叉树现在学习的是第19页，共54页树和二叉树 树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，用树来组织信息；在分析算法的行为时，用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构的操作及应用等。现在学习的是第20页，共54页树的定义 树(Tree)是n(n0)个结点的有限集合T，若n=0时称为空树，否则：有且只有一个特殊的称为树的根(Root)结点；若n1时，其余的结点被分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成现在学习的是第21页，共54页树的基本术语 结点(node)：一个数据元素及其若干指向其子树的分支。结点的度(degree)、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。树的示树的示例形式例形式AABDCEGFHIMJNKL(a)只有根结点只有根结点(b)一般的树一般的树现在学习的是第22页，共54页树的基本术语叶子(left)结点、非叶子结点 树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。孩子结点、双亲结点、兄弟结点 一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。森林(forest)：是m(m0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。现在学习的是第23页，共54页树的表示形式 倒悬树。是最常用的表示形式 嵌套集合。是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合 广义表形式 凹入法表示形式树的表示树的表示形式形式(a)嵌套集合嵌套集合形式形式(b)广义表广义表形式形式(A(B(E(K,L),F),C(G(M,N),D(H,I,J)HIJDFBKLECM NGA现在学习的是第24页，共54页二叉树二叉树(Binary tree)是n(n0)个结点的有限集合。若n=0时称为空树，否则：有且只有一个特殊的称为树的根(Root)结点；若n1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。由此可知，二叉树的定义是递归的。二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关树的术语也都适用于二叉树。现在学习的是第25页，共54页二叉树的基本形态AAAA(a)(b)(c)(d)(e)(a)空空二叉树二叉树(b)单结点单结点二叉树二叉树(c)右子树为空右子树为空(d)左子树为空左子树为空(e)左左、右子树都不空右子树都不空二叉二叉树的基本树的基本形态形态现在学习的是第26页，共54页二叉树的性质 性质1：在非空二叉树中，第i层上至多有2i-1个结点(i1)。性质2：深度为k的二叉树至多有2k-1个结点（k1)。性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。现在学习的是第27页，共54页满二叉树 一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。满二叉树的特点：每一层上的结点数总是最大结点数。所有的支结点都有左、右子树。可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。现在学习的是第28页，共54页完全二叉树完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。其中 2k-1 n2k-1 完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。完全二叉树的特点是，若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。现在学习的是第29页，共54页894101151213614157213894101152112673(a)满二叉树满二叉树(b)完全二叉树完全二叉树1362455674213(c)非完全二叉树非完全二叉树特殊形态的特殊形态的二叉二叉树树现在学习的是第30页，共54页二叉树的存储结构 顺序存储结构 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素 对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中 对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中现在学习的是第31页，共54页abcdhiejklfg(a)完全二叉树完全二叉树(b)非完全二叉树非完全二叉树abcdefgh1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l (c)完全二叉树的顺序存储形式完全二叉树的顺序存储形式1 2 3 4 5 6 7 8 9 10 11a b c d e h f g(d)非完全二叉树的顺序存储形式非完全二叉树的顺序存储形式现在学习的是第32页，共54页链式存储结构 设计不同的结点结构可构成不同的链式存储结构。二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域 三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点Lchild data RchildLchild data parent Rchild(a)二叉链表结点二叉链表结点(b)三三叉链表结点叉链表结点链表结点结构链表结点结构形式形式现在学习的是第33页，共54页二叉树的链式存储形式 有一棵一般的二叉树，以二叉链表和三叉链表方式存储的结构图二叉树及其二叉树及其链式存储结构链式存储结构(a)二叉树二叉树afedcbg(c)三三叉链表叉链表 a b c d e f g T(b)二二叉链表叉链表 a b c d e g f T现在学习的是第34页，共54页遍历二叉树及其应用遍历二叉树(Traversing Binary Tree)是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。现在学习的是第35页，共54页遍历二叉树 若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是：DLR先(根)序遍历。LDR中(根)序遍历。LRD后(根)序遍历。现在学习的是第36页，共54页构建二叉搜索树 又名二叉排序树 用递归的方法构建树 实现对树的增删改查功能现在学习的是第37页，共54页算法现在学习的是第38页，共54页查找算法 顺序查找 从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。现在学习的是第39页，共54页查找算法 二分法查找 先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。现在学习的是第40页，共54页查找算法 二分法查找现在学习的是第41页，共54页排序算法排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程，其定义为：给定一组记录序列：R1,R2,Rn，其相应的关键字序列是K1,K2,Kn。确定1,2,n的一个排列p1,p2,pn，使其相应的关键字满足如下非递减(或非递增)关系：Kp1Kp2 Kpn的序列Kp1,Kp2,Kpn，这种操作称为排序。关键字Ki可以是记录Ri的主关键字，也可以是次关键字或若干数据项的组合。Ki是主关键字：排序后得到的结果是唯一的；Ki是次关键字：排序后得到的结果是不唯一的。现在学习的是第42页，共54页排序算法若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(ij，i,j=1,2,n)，且在排序前Ri先于Rj(ij)，排序后的记录序列仍然是Ri先于Rj，称排序方法是稳定的，否则是不稳定的。排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性。若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1)，则称排序方法是就地排序，否则是非就地排序。现在学习的是第43页，共54页排序的分类 待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。待排序的记录数不太多，所有的记录都能存放在内存中进行排序，称为内部排序；待排序的记录数太多，所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。现在学习的是第44页，共54页内部排序的基本操作对内部排序地而言，其基本操作有两种：比较两个关键字的大小；存储位置的移动，从一个位置移到另一个位置。第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的；记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；记录存储在一组连续地址的存储空间：构造另一个辅助表来保存各个记录的存放地址(指针)：排序过程不需要移动记录，而仅需修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。现在学习的是第45页，共54页冒泡排序依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。现在学习的是第46页，共54页插入排序 采用的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1,R2,.,Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。最基本的插入排序是直接插入排序(Straight Insertion Sort)。现在学习的是第47页，共54页直接插入排序 将待排序的记录Ri，插入到已排好序的记录表R1,R2,.,Ri-1中，得到一个新的、记录数增加1的有序表。直到所有的记录都插入完为止。设待排序的记录顺序存放在数组R1n中，在排序的某一时刻，将记录序列分成两部分：R1i-1：已排好序的有序部分；Rin：未排好序的无序部分。显然，在刚开始排序时，R1是已经排好序的。现在学习的是第48页，共54页直接插入排序示例 设有关键字序列为：7,4,-2,19,13,6，直接插入排序的过程如图初始记录的关键字：初始记录的关键字：7 4 -2 19 13 6第一趟排序：第一趟排序：4 7 -2 19 13 6第二趟排序：第二趟排序：-2 4 7 19 13 6第三趟排序：第三趟排序：-2 4 7 19 13 6第四趟排序：第四趟排序：-2 4 7 13 19 6第五趟排序：第五趟排序：-2 4 6 7 13 19现在学习的是第49页，共54页选择排序 每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。直接选择排序的过程直接选择排序的过程初始记录的关键字：初始记录的关键字：7 4 -2 19 13 6第一趟排序：第一趟排序：-2 4 7 19 13 6第二趟排序：第二趟排序：-2 4 7 19 13 6第三趟排序：第三趟排序：-2 4 6 19 13 7第四趟排序：第四趟排序：-2 4 6 7 13 19第五趟排序：第五趟排序：-2 4 6 7 13 19第六趟排序：第六趟排序：-2 4 6 7 13 19现在学习的是第50页，共54页快速排序 是一类基于交换的排序，系统地交换反序的记录的偶对，直到不再有这样一来的偶对为止 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。现在学习的是第51页，共54页排序过程 设待排序的记录序列是Rst，在记录序列中任取一个记录(一般取Rs)作为参照(又称为基准或枢轴)，以Rs.key为基准重新排列其余的所有记录，方法是：所有关键字比基准小的放Rs之前；所有关键字比基准大的放Rs之后。以Rs.key最后所在位置i作为分界，将序列Rst分割成两个子序列，称为一趟快速排序。现在学习的是第52页，共54页算法分析 快速排序的平均时间复杂度是：T(n)=O(n2n)从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为2n+1。快速排序的空间复杂度是：S(n)=O(2n)从排序的稳定性来看，快速排序是不稳定的。现在学习的是第53页，共54页THE END现在学习的是第54页，共54页