【教学课件】第6章算法与数据结构基础.ppt

第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作第六章 算法与数据结构基础 计算机程序主要对数据进行加工和处理。程序中需要说明数据结构:数据的组织形式和存储方式算法:操作数据的步骤和方法 数据结构算法1第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.1 数据结构基本概念 随着计算机技术的发展,其应用领域越来越广。计算机应用已不在局限于数值计算，更多地用于数据处理和信息管理等非数值计算。例如：学生、图书、财务和人事等信息管理系统。学号姓名性别出生日期班级专业20040001刘强男1984/02/1314001机械制造20040002 王晓红女1986/05/0614001机械制造20040003李明男1984/10/2514001机械制造20040041张宇男1984/06/1414002机械电子工程 每个学生对应一个数据，由学号、姓名、性别和出生日期等多个数据项构成，通常对学生信息进行插入、删除或查找等操作。2第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 数据结构的定义 数据结构是指具有相同特征、相互之间有关联的数据集合。现实世界中每个对象都可以映像成数据元素。数据元素可以由一个数、一个字符或一个名字等单个数据项组成，也可以由多个数据项组成。数据元素、结点数据结构中数据元素都具有某种共同特征数据结构中数据元素之间存在着某种关系 3第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作9向量2 2，4343，6868，4545，3232是数据结构每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 9季度名称组成的集合是数据结构：春，夏，秋，冬9家庭成员祖父、父亲、儿子是数据结构每个数据元素由一个数据项组成数据元素之间有层次上的高低关系 4第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 数据结构数据结构是指带有是指带有结构特性结构特性的的数据元素集合数据元素集合。主要研究：数据集合中数据元素之间所固有的关系，即数据逻辑结构；数据处理时数据在计算机中的存储关系，即数据存储结构(物理结构)；对数据所进行的操作。5第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作数据逻辑结构 数据结构中数据元素之间所固有的关系描述成前前后后件件(前驱与后继)关系。数据之间前后件关系是它们之间的逻辑关系，与它们在计算机中的存储位置无关，因此将这种关系称为逻辑结构。6第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作一个数据结构可以表示为 S=(D,R)季节数据结构可以定义成 S=(D,R)其中:D=春,秋,冬,夏 R=(春,夏),(夏,秋),(秋,冬)S表示数据结构D数据元素集合向量数据结构可以定义成 S=(D,R)其中:D=2,43,68,45,32 R=(2,43),(43,68),(68,45),(45,32)数据元素之间的前后件关系的集合7第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性结构：一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。数据元素之间是一对一的关系除第一个结点无前件外,其他结点都 只有一个前件除最后一个结点无后件外,其他结点都只有一个后件例如:春夏冬秋8第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作O数据之间存在一对多的关系O一个结点最多有一个前件,可以有多个后件O前件与后件之间有层次关系 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。树型结构：9第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作9数据元素之间存在多对多的关系9一个结点可以有多个前件和多个后件 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。图形结构：10第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。集合：是一种松散结构，数据元素之间的关系只是同属于一个集合，可以用其他结构来表示。集合11第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作数据物理结构 数据在计算机存储器中的存储方式称为数据物理结构(数据存储结构)。在数据存储结构中，不仅要存放各个数据元素信息，还要存放数据元素之间前后件关系信息。数据元素在计算机中通常有四种存储方式：顺序、链式、索引和散列。12第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作顺序存储结构 顺序存储结构是在内存中开辟一块连续内存单元用于存放数据，逻辑上相邻的结点在物理位置上也相邻。即：结点之间的逻辑关系由存储单元的相邻关系来体现。13第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作有如下顺序关系 a,b,c,d 例如：a a地址2000H2000H2001H2001Hc c2002H2002H2003H2003Hd d数据顺序存储结构 如果在b和c之间增加新数据x构成 a,b,x,c,d的顺序关系,应该如何存储？b b14第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 链式存储结构链式存储结构中，结点由两部分组成：用于存放数据元素(数据域)用于存放前件或后件的存储地址(指针域)即：通过指针反映数据元素之间的逻辑关系15第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 链式存储结构有如下顺序关系 a,b,c 例如：a a2000b bc c30011003300130011003100316第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作顺序存储结构与链式存储结构比较顺序存储结构：优点：每个结点占用存储空间最少 缺点：如果数据元素很多，则可能找不到一块足够大的连续存储单元 不能很好利用存储单元,容易产生碎片链式存储结构:优点：充分利用所有存储单元缺点：每个结点占用较多存储单元 17第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作链式存储的插入 J L U S在J,L之间插入接点S链式存储的删除 J L U 删除接点L显然,链式存储的插入和删除操作比较简单、方便18第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.2 算法基本概念 程序包含两方面的内容：对数据的描述 对操作的描述 算法就是操作步骤，是解决“做什么”和“怎么做”的问题。算法是程序的灵魂，广义来说，为解决一个问题而采取的方法和步骤就称为算法。19第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作计算机算法分为：数值算法 非数值算法 各种数学问题的解法 常用于事物管理领域，如排序、查询 算法是定义在逻辑结构上的操作，独立于计算机，但算法的实现依赖于数据的存储结构。20第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法的特征Z可行性Z确定性Z有穷性Z输入Z输出 采取的方法和步骤可行，结构另人满意。算法中的每一个步骤都必须确定，不能产生歧义。执行算法时从外界取得必要的信息。一个算法可以有零或多个输入。算法得到的结果就是输出,没有输出的算法是没有意义的,一个算法应该有一个或多个输出。算法必须由有限步组成，并能在有效时间内完成。21第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法描述方法 计算写出其算法。分析：分析：1 1、展开上面算式、展开上面算式 S=1+2+3+99+100S=1+2+3+99+1002 2、按传统方法求解、按传统方法求解 S 1 S S+2 S S+3 S S+99 S S+10022第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 计算写出其算法。main()main()int s=0;int s=0;s=1;s=1;s=s+2;s=s+2;s=s+3;s=s+3;s=s+99;s=s+99;s=s+100;s=s+100;printf(“s=%d/n”,s);printf(“s=%d/n”,s);利利用用程程序序设设计计中中的的顺顺序序结结构构很不理想算法23第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。自然语言：带序号的人类语言描述方法。1.1.将变量将变量s s清清0 0；2.2.将变量将变量n n置置1 1；3.3.把把s+ns+n的值赋给的值赋给s s；4.4.把把n+1n+1的值赋给的值赋给n n；5.5.判断判断 n n 100 100？是否成立？是否成立，若成立，转，若成立，转3 3；否则转否则转6 66.6.6.6.输出输出s s的值的值;S=1+2+3+99+100特点特点:易懂却不直观易懂却不直观,对复杂算法描述很对复杂算法描述很困难困难,易产生歧义。易产生歧义。若成立若成立,24第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作伪代码法：是一种假的代码不能被计算机所理解，但可以用你熟悉的计算机语言的语句加上自然语言构成。0 S 1 n while n 100 S+n S n+1 n print S 这样就接近于某种语这样就接近于某种语言编写的程序言编写的程序,便于转便于转换成编程语言。换成编程语言。25第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。流程图法：用一些图框、线条以及文字说明 来形象地、直观地描述算法。输入/输出处理判断起止连接点流程线符号说明：26第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作开始0 S1 nSn Sn1 n输出S结束T F n 100S=1+2+3+99+100S=1+2+3+99+100优点:直观形象缺点:算法复杂时,篇幅 较多,费时且不方便修改。27第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作N-S图:完全去掉了带箭头的流程线、算法的所有处理步骤都写在一个大矩形框内,框内还可以包含一些从属于它的小矩形框,适于结构化程序设计。顺序顺序AB判断判断条件FTBA“当型当型”循循环环当条件成立当条件成立A“直到型直到型”循循环环直到条件成立直到条件成立A0 S1 nn 100Sn Sn1 n输出输出S S的值的值28第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法评价 在计算机程序设计中,某一任务的算法设计得优与劣,将直接影响程序的运行效率、稳定性和可维护性。通常从以下4个方面评价一个算法。正确性可读性健壮性执行效率算法本身没有语法错误,执行时输入正确数据能够得到正确结果.算法要容易理解和阅读,容易实现，同时也要便于程序维护和完善。指算法执行的时间性能和空间性能 。算法能够对输入的各种数据给予适当的提示和处理。多多个个算算法法解解决决同同一一个个问问题题时时,执执行行时时间间短短的的算算法法时时间间效效率率高高;占占用用存存储储空空间间少少的的算算法法空间效率高。空间效率高。29第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法复杂度 算法复杂度是对算法效率的度量，是评价算法优劣的重要依据。一个算法复杂度高低体现在运行该算法所需要资源的多少。时间资源空间(即存储器)资源 因而,算法复杂度包含时间复杂度和空间复杂度。时间复杂度指执行算法所需时间:执行时间=语句执行时间语句执行次数 空间复杂度指在算法执行过程中,所占用附加空间数量30第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3 典型数据结构数据逻辑结构分为:线性结构 非线性结构有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前件和一个后件，线性结构也称为线性表。栈、队列、数组和串等是特殊线性表非线性结构包括树和图31第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3.1 线性表 线性表是一组特征相同数据的有限序列，表示为 L=(a1 1,a2 2,a3 3 an n)。非空线性表的特征:除a1 1无前件外,其它任意数据元素ai i有且只有一个前件ai-1i-1。除了an n无后件外,其它任意数据元素ai i有且只有一个后件ai+1i+1。线性表中数据元素个数n(n0)称为线性表长度。当n=0时,称为空表。在非空线性表中，每个数据元素都有一个确定位置，其位置取决于它的序号。a a1 1是第一个元素，是第一个元素，a a2 2 是第二个元素，是第二个元素，a an n是最后一个元素。是最后一个元素。32第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作向量2，43，68，45，32是线性表。季度名称 春，夏，秋，冬是线性表。学生基本信息:(20040001,(20040001,刘强刘强,男男,1984/02/13,14001,1984/02/13,14001,机械制造机械制造),),(20040002,(20040002,王晓红王晓红,女女,1986/05/06,14001,1986/05/06,14001,机械制造机械制造),),(20040003,(20040003,李明李明,男男,1984/10/25,14001,1984/10/25,14001,机械制造机械制造)是线性表。33第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性表顺序存储结构顺序存储结构具有以下两个基本特点特点：线性表中所有元素所占的存储空间是连续的。线性表中各元素在存储空间中按逻辑顺序依次存放,即线性表的逻辑结构与存储结构相一致一致。线性表通常采用顺序存储结构或链式存储结构。顺序表顺序表链表链表由此可以看出由此可以看出:在线性表的顺序存储结构中,其前后两个元素在存储空间中是紧邻的，前件元素一定存放在后件元素的前面。34第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例如：线性结构 a1 1，a2 2，a3 3，其中每个数据元素占2个存储空间，假设存储a1 1的首地址为2000。20002000a a1 1占占2 2个字节个字节a a2 2a a3 32004200420022002占占2 2个字节个字节占占2 2个字节个字节存储地址：存储地址：结论：假假设设一一个个数数据据元元素素占占用用d d个个字字节节,线线性性表表的的首首地地址址Addr(aAddr(a1 1)为为K K，则则存存储储任任意意一一个个数数据据元元素素a ai i的首地址为的首地址为:Addr(aAddr(ai i)=Addr(a)=Addr(a1 1)+(i-1)d=K+(i-1)d)+(i-1)d=K+(i-1)d 其中其中 1 i n 1 i n 优点：可以方便地随机读取表中任意元素缺点：插入和删除运算需要移动大量元素，浪费大 量时间，时间效率较低。35第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性表的链式存储 用一组存储单元(可以连续，也可以不连续)存储线性表中数据元素。为了反映数据元素之间的逻辑关系，每个数据元素由两部分组成：1用于存放数据元素(数据域)2用于存放前件或后件的存储地 址(指针域)数据域数据域指针域指针域结点之间逻辑关系由指针域来确定36第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作单链表 定义：每个结点只有一个指针域的链表 a1 a2a3a4a5headhead每个单链表都有一个头指针，存放表中第一个结点的存储地址。每个结点指针域存放后件结点的存储地址，最后一个结点无后件结点，指针域为空，用NULL或 表示。37第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环链表 循环链表中增设一个表头结点，其数据域的值可以任意或根据情况来设置，指针域指向第一个结点。将单链表最后一个结点的空指针域改为指向该链表的第一个结点，即首尾相连。head空循环链表非空循环链表a1a2.headan注意头指针和表头结点的区别38第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环链表特点：Z从表中任一结点出发，均可以找到其它所有结点；Z在任何情况下，带有表头结点的循环链表中至少有一个结点存在，从而使空表和非空表运算统一。循环链表运算与单链表区别：9对单链表进行操作时，要判断是否是表尾，即指针是否为NULL；9而对循环链表操作时，要判断是否是头指针。39第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 栈 定义：栈是只能在表的一端进行插入和删除运算的线性表。通常将允许插入和删除运算的一端称为栈顶(top)，另一端称为栈底(bottom)不含元素的栈称为空栈。向栈中插入元素称为入栈。从栈中删除元素称为出栈。40第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 设有一个栈S=a1,a2,an，入栈顺序是a1、a2最后是an n。栈的状态如图所示：a1 a2 an栈底栈底bottombottom栈顶栈顶toptop入栈入栈出栈出栈栈特点：栈特点：后进先出后进先出。故也称为“先进后出”表或“后进先出”表 41第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作栈的基本运算 栈初始化：构造一个空栈。空栈判断：判断栈是否为空。入栈：在栈顶插入一个元素。出栈：在栈顶删除一个元素。读栈：仅读取栈顶数据，并不删除元素。42第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作栈的顺序存储 设用变量top表示栈顶位置，用n表示栈中最多能容纳元素的个数。栈顺序存储结构是用一块连续存储区域存放栈中元素。连续区域的低地址一端作为栈底，栈底固定不变。43第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作入栈运算S1：如果top=n，则栈已满，提示入栈失败(栈“上溢”错误)，并结束入栈；S2：top+1 top；S3：将新元素放在当前栈顶位置(top)上。a1 a2a3bottomtopa444第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作出栈运算S1：如果top=0，则栈为空，提示出栈失败(栈“下溢”错误)，并结束出栈；S2：将当前栈顶(top)元素赋给一个变量；S3：top 1 top。a3top a1 a2bottom45第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 例如，容量为6的栈中已有3个元素,如图所示：123456A AC CB BbottomtopX、Y两个元素先后入栈X XY Y元素Y出栈46第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 队 列 允允许许在在一一端端进进行行插插入入、而而在在另另一一端端进进行行删删除除的的线线性性表表，允允许许插插入入的的一一端端称称为为队队尾尾，允允许许删删除除的的一一端端称称为为队队头头。入队退队队尾队尾abc队头队头47第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作队列的基本运算初始化队列空队列判断入队运算出队运算读队头元素队列长度48第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作队列顺序存储及其常用运算队列的特点:先进先出 入队和出队运算时队头和队尾位置要发生变化 队头队头 front(指向第一个元素的前一个单元位置)队尾队尾 rear(指向最后一个元素的位置)队列中容纳元素个数为n49第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作创建一个空队列,并令 front=rear=-11.初始化队列front -1-1 2 2 0 0 1 1rear50第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2.入队运算S1：如果rear=n-1，则队列已满，提示入队失败(队列“上溢”错误)，并结束入队；S2：rear+1 rear；S3：将新元素放在当前队列位置(rear)上frontrear -1 -1 2 2 0 0 1 1A AB BC C51第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作3.退队运算S1：如果front=rear，则队列已空,提示退队失败(队列“下溢”错误),并结束退队；S2：front+1 front;S3：取front所指元素frontrear -1 -1 2 2 0 0 1 1A AB BC C此时虽然队列有空位置，但也不能插入新结点。52第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，这样可以把退队的空间利用起来。0 02 23 31 10 02 21 13 34 453第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环队列的运算1.初始化队列创建一个空队列,并令 front=rear=01 13 3 2 24 40 0frontrear54第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作S1:先判断队列是否已满，若队满则入队失败，否则元素入队S2:(rear+1)%nrear当rear+1=n时，0 rearS3:将新元素放在当前队尾位置（rear）。循环队列的运算2.入队运算1 13 32 24 40 0 rear fronta ab bc c例如：插入结点a,b,c显然,再插入两个结点后front=rearfront=rear,此时为满队列55第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环队列的运算3.出队(退队)运算S1:先判断队列是否为空，若队空则出队失败（上溢）S2:(front+1)%nfront当front+1=n时，0 front0 02 21 13 34 4a ab bc c rear front例如：删除结点a显然,再删除两个结点后front=rearfront=rear,此时为空队列因此：通常需要增加一个变量用来标识当front=rear时，队列是满还是空。56第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 树 树是一种常用的非线性结构，树是由n(n0)个结点组成的有限集合。当n=0时，称为空树；否则，有且仅有一个根结点，当n1时，其余结点被分成m(m0)个互不相交的子集T1，T2,.,Tm，每个子集又是一棵树。树是递归定义的，即一棵树由根及若干子树构成，每棵子树又是由更小的子树构成。57第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作结点的度：一个结点所拥有后件个数树的度：树中所有结点的最大度 AEBCDFGHIJKL根子结点叶结点58第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 AEBCDFGHIJKL 结点的层次从根结点算起，根结点在第一层，根的直接后继结点在第二层，同一层上所有结点的后继结点均在下一层。1 1 2 2 3 3 4 4树中结点的最大层次称为树的深度或高度 59第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 二叉树非空二叉树有且只有一个根结点；每个结点最多有两棵子树,且有左右之分 二叉树是另一种树形结构，每个结点最多只有两个后件(即最大度为2)。特点：60第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树有五种基本形态 空二叉树只有根结点只有左子树有左和右子树只有右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TX XC CZ ZY YB BP P深度为4的二叉树61第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树基本性质 性质一：在二叉树的第i层上，最多有2i-1i-1个结点(i1).性质二：深度为k的二叉树最多有2k k-1个结点(k1).性质三：对于任意一棵二叉树，度为0的结点(即叶子结点)总比度为2的结点多一个.62第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作满二叉树 如果一个深度为k的二叉树拥有2k k-1个结点，则称它为满二叉树。每一层的结点数都达到最大值,叶子结点都在最下面的同一层上 完全二叉树 一棵深度为k的二叉树,如果第一层到第k-1层是一棵满二叉树,第k层上的结点数没有达到最大值2k-1k-1,但这些结点都满放在该层最左边,则称此二叉树为完全二叉树。如果某个结点没有左子树,则它一定没有右子树 63第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作注：满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。A AT TX XC CE EMMB BP P15个结点的满二叉树S SD DNNF FR RY YQQ64第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作完全二叉树性质：12个结点的完全二叉树A AT TX XC CR RB BP PS SE EG GF FY Y性质一：具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 表示取log2n的整数部分。65第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作完全二叉树性质：性质二：在有n个结点的完全二叉树中,将所有结点按从上到下,从左到右的顺序用自然数1,2,n进行编号,则对于编号为k的结点有如下结论：k=1时,该结点为根结点。k1时,该结点的父结点编号为int(k/2)。2k=n时,编号为k的结点的左子结点编号为2k,否则无左子结点。2k+1=n时,编号为k的结点的右子结点编号为 2k+1,否则无右子结点。A AT TX XC CR RB BP PS SE EQQF FY Y1 12 23 34 45 56 67 7101011 119 98 8121266第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树的顺序存储 二叉树顺序存储是指用一组连续存储单元存储二叉树中的结点。结点存储顺序是按着从上到下、从左到右顺序。ACBEGDFABCDE FG 1 2 3 4 5 6 7 按照完全二叉树每个结点编号的顺序存放结点,通过结点的编号准确地反映结点之间的逻辑关系。1 12 23 34 45 56 67 767第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作非完全二叉树顺序存储ACBEGFABC E FG 1 2 3 4 5 6 7 显然,顺序结构适用于完全二叉树，对于非完全二叉树，会浪费许多存储空间。68第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树链式存储二叉树每个结点由数据域和指针域组成。两个指针域：o 一个用于指向左子结点 o 一个用于指向右子结点 常见二叉树结点结构如图：LChildDataRChild数据域 存储左子结点的存储地址 存储右子结点的存储地址 69第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树二叉树链式存储A AT TX XC CZ ZY YB BP P深度为深度为4 4的的二叉树二叉树A AT TX XB BC CP PZ ZY YBTBT70第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树的遍历 遍历二叉树是指按照某种顺序访问二叉树中每个结点的过程，每个结点被访问一次且仅一次。根据对根访问的次序，二叉树的遍历分为先序遍历、中序遍历和后序遍历。71第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作先序遍历 访问根结点 先序遍历左子树 先序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A A遍历结果：T TB BZ ZX XC CP PY Y因为左子树因为左子树空，故遍历空，故遍历右子树右子树72第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作中序遍历 中序遍历左子树 访问根结点 中序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树空因为左子树空遍历结果：73第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 后序遍历左子树 后序遍历右子树 访问根结点后序遍历A AT TX XC CZ ZY YB BP P深度为4的二叉树遍历结果：A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树因为左子树空，故遍历空，故遍历右子树右子树74第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.4 典型算法 对非数值型数据通常有插入、删除、查找和排序等操作。其中查找和排序是数据处理中比较重要的算法。查找又称检索，是指在数据集合中查找某个数据元素的过程。若存在这样数据元素,则查找成功；否则，查找失败。6.4.1 6.4.1 查找查找75第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作1 顺序查找适用于线性表，其基本方法是 ：从线性表中第一个元素开始，依次将线性表中的元素与给定值进行比较。若相等，则查找成功；若直到最后一个元素，还没找到与给定值相等的元素，则查找失败。76第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例如：在顺序表(88,15,23,80,63,8,86,46,71,101)中,查找 值为71的数据元素。从线性表中第一个元素88开始,依次将 线性表中元素与71进行比较。直到第九个元素为71,查找成功。特点：顺序查找算法简单,但是执行效率较低 在下列两种情况下,只能使用顺序查找法：线性表是线性链表。线性表是顺序表，但表中元素无序排列。此题比较了9次77第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2 二分查找 又称折半查找,要求被查找的表采用顺序存储结构且数据元素按数据值升序或降序排列,即二分查找法只适用于有序表。基本思想是(设顺序表升序排列)：P将给定值与中间位置元素比较,若相等,则 查找成功；P若给定值小于元素值,则继续对前半部分 再进行折半查找；P若给定值大于中间位置元素值,则继续对后半部分再进行折半查找。78第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例：在有序顺序表(8，15，23，46，63，71，80，86，88，101)中，用折半查找法查找值为 71 的数据元素。key=71 8 15 23 46 63 71 80 86 88 101 1 2 3 4 5 6 7 8 9 101