第6章--数据结构与算法教学课件PPT文档.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,第6章,数据结构与算法,第1页,主要内容,数据结构基础,实训数据结构应用,第2页,6-1数据结构基础,数据结构概述,基本数据结构,基本算法,第3页,数据结构概述,数据（Data）,数据是信息的载体。它能够被计算机识别、存储和加工处,理，是计算机程序加工的“原料”。,数据元素（DataElement）,数据元素是数据的基本单位。,数据结构（DataStructure）,数据结构指的是数据之间的相互关系，即数据的组织形式。,数据元素之间的逻辑关系，也称数据的逻辑结构（Logical,Structure）。,数据元素及其关系在计算机存储器内的表示，称为数据的存储结,构（StorageStructure）,数据的运算，即对数据施加的操作。,第4页,6-1-2基本数据结构,线性结构：线性结构的逻辑特征是：若结构是非,空集，则有且仅有一个开始结点和一个终端结点，,并且所有结点都最多只有一个直接前趋和一个直,接后继。,线性表是一个典型的线性结构。栈、队列、串等,都是线性结构。,非线性结构：非线性结构的逻辑特征是：一个结,点可能有多个直接前趋和直接后继。数组、广义,表、树和图等数据结构都是非线性结构。,第5页,线性表,线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结,构。,线性表的逻辑定义：,线性表（LinearList）是由n（n0）个数据元素（结点）a1，a2，,an组成的有限序列。,数据元素的个数n定义为表的长度（n=0时称为空表）。,将非空的线性表（n0）记作：（a1，a2，an）。,数据元素ai（1in）只是个抽象符号，其具体含义在不同情况下可以不,同。,线性表的逻辑结构特征：,对于非空的线性表：,有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2。,有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1。,其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1。,第6页,栈与队列,栈和队列是两种特殊的线性表，它们的逻,辑结构和线性表相同，只是其运算规则较,线性表有更多的限制，故又称它们为运算,受限的线性表。栈和队列被广泛应用于各,种程序设计中。,第7页,栈的定义及基本运算,栈的定义,栈的基本运算,第8页,栈的定义,栈（Stack）是限制仅在表的一端进行插入,和删除运算的线性表。,通常称插入、删除的这一端为栈顶（Top），,另一端为栈底（Bottom）。,当表中没有元素时称为空栈。,栈为后进先出（LastInFirstOut）的线性表，,简称为LIFO表。,第9页,栈示意图,第10页,栈的基本运算,nitStack（S）。构造一个空栈S。,StackEmpty（S）判栈空。若S为空栈，则返回True，否则,返回False。,StackFull（S）判栈满。若S为满栈，则返回True，否则返,回False。,注意：该运算只适用于栈的顺序存储结构。,Push（S，x）进栈。若栈S不满，则将元素x插入S的栈顶。,Pop（S）退栈。若栈S非空，则将S的栈顶元素删去，并返,回该元素。,StackTop（S）取栈顶元素。若栈S非空，则返回栈顶元素，,但不改变栈的状态,第11页,队列的定义及基本运算,定义,队列的基本逻辑运算,第12页,定义,队列（Queue）是只允许在一端进行插入，,而在另一端进行删除的运算受限的线性表。,允许删除的一端称为队头（Front）。,允许插入的一端称为队尾（Rear）。,当队列中没有元素时称为空队列。,队列亦称作先进先出（FirstInFirstOut）的,线性表，简称为FIFO表。,第13页,队列示意图,第14页,队列的基本逻辑运算,InitQueue（Q）置空队。构造一个空队列Q。,QueueEmpty（Q）判队空。若队列Q为空，则返回真值，,否则返回假值。,QueueFull（Q）判队满。若队列Q为满，则返回真值，否,则返回假值。注意：此操作只适用于队列的顺序存储结构。,EnQueue（Q，x）若队列Q非满，则将元素x插入Q的队尾。,此操作简称入队。,DeQueue（Q）若队列Q非空，则删去Q的队头元素，并返,回该元素。此操作简称出队。,QueueFront（Q）若队列Q非空，则返回队头元素，但不改,变队列Q的状态。,第15页,线性链表,定义,链表的结点结构,头指针head和终端结点指针域的表示,单链表的一般图示法,单链表类型描述,指针变量和结点变量,第16页,定义,链接方式存储的线性表简称为线性链表（Linked,List）。,链表的具体存储表示为：,用一组任意的存储单元来存放线性表的结点（这组存,储单元既可以是连续的，也可以是不连续的）。,链表中结点的逻辑次序和物理次序不一定相同。为了,能正确表示结点间的逻辑关系，在存储每个结点值的,同时，还必须存储指示其后继结点的地址（或位置）,信息（称为指针（pointer）或链（link）。,第17页,链表的结点结构,data：（数据域）表示数据元素自身值。,next：（指针域）表示与其他结点关系。,通过链域，可将n个结点按其逻辑顺序链接在一起（不论其物理次序,如何）。,每个结点只有一个指针域的链表称为单链表（SingleLinkedList）。,datanext,第18页,头指针head和终端结点指针域的表,示,单链表中每个结点的存储地址是存放在其,前趋结点next域中，而开始结点无前趋，故,应设头指针head指向开始结点。,注意：链表由头指针唯一确定，单链表可以,用头指针的名字来命名。,第19页,单链表的一般图示法,由于我们常常只注重结点间的逻辑顺序，,不关心每个结点的实际位置，可以用箭头,来表示链域中的指针，线性表（bat，cat，,fat，hat，jat，lat，mat）的单链表就可以表,示为如下图所示的形式。,第20页,单链表结构,第21页,单链表类型描述,typedefcharDataType;/假设结点的数据域类型为字符,DataTypedata;,structnode*next;/结点的指针域,typedefstructnode,/结点类型定义,/结点的数据域,ListNode;,typedefListNode*LinkList;,ListNode*p;,LinkListhead;,注意：,LinkList和ListNode*是不同名字的同一个指针类型（命名的不同是为,了概念上更明确）。,LinkList类型的指针变量head表示它是单链表的头指针。,ListNode*类型的指针变量p表示它是指向某一结点的指针。,第22页,指针变量和结点变量,说明：,*p：表示由指针p所指向的结点。,(*p).data或p-data：表示由p所指向结点的,p：指向链表中某一结点的指针。,数据域。,(*p).next或p-next：表示由p所指向结点的,指针域。,第23页,指针示意图,p,data,next,第24页,指针变量和结点变量,生成结点变量的标准函数,p=(ListNode*)malloc(sizeof(ListNode)；,/函数malloc分配一个类型为ListNode的结,点变量的空间，并将其首地址放入指针变,量p中。,释放结点变量空间的标准函数,free(p)；/释放p所指的结点变量空间,第25页,指针变量和结点变量,结点分量的访问,利用结点变量的名字*p访问结点分量。,方法1：(*p).data和(*p).next。,方法2：p-data和p-next。,指针变量p和结点变量*p的关系,指针变量p的值结点地址。,结点变量*p的值结点内容。,(*p).data的值p指针所指结点的data域的值。,(*p).next的值*p后继结点的地址。,*(*p).next)*p后继结点。,第26页,指针变量和结点变量,注意：,若指针变量p的值为空（NULL），则它不,指向任何结点。此时，若通过*p来访问结,点就意味着访问一个不存在的变量，从而,引起程序的错误。,有关指针类型的意义和说明方式的详细解,释，参考C语言的有关资料。,第27页,二叉树与树,树的概念,二叉树,第28页,树形图,第29页,树的概念,家庭树,树的定义,树（Tree）是n（n0）个结点的有限集T，T为空,时称为空树，否则它满足如下两个条件：,有且仅有一个特定的称为根（Root）的结点。,其余的结点可分为m(m0)个互不相交的子集Tl，,T2，Tm，其中每个子集本身又是一棵树，并称其,为根的子树（Subree）。,注意：树的递归定义刻画了树的固有特性：一棵非,空树是由若干棵子树构成的，而子树又可由若干,棵更小的子树构成。,第30页,二叉树,二叉树的递归定义。二叉树（BinaryTree）,是n（n0）个结点的有限集，它或者是空,集(n=0)，或者由一个根结点及两棵互不相,交的、分别称作这个根的左子树和右子树,的二叉树组成。,二叉树的五种基本形态。二叉树可以是空,集；根可以有空的左子树或右子树；或者,左、右子树皆为空。,第31页,二叉树的五种形态,（a）空树,（b）只有一个根结点的二叉树,（c）只有左子树的二叉树,（d）只有右子树的二叉树,（e）左右子树非空的二叉树,第32页,二叉树性质,二叉树第i层上的结点数目最多为2i-1(i1)。,深度为k的二叉树至多有2k-1个结点(k1)。,在任意-棵二叉树中，若终端结点的个数为,n0，度为2的结点数为n2，则no=n2+1。,第33页,满二叉树和完全二叉树是二叉树的,两种特殊情形,每一层上的结点数都达到最大值。即对给,定的高度，它是具有最多结点数的二叉树。,满二叉树中不存在度数为1的结点，每个分,支结点均有两棵高度相同的子树，且树叶,都在最下一层上。,第34页,非线性结构,至少存在一个数据元素有两个或两个以上,的直接前驱（或直接后继）元素的数据结,构。,图（Graph）也是一种复杂的非线性结构。,在人工智能、工程、数学、物理、化学、,生物和计算机科学等领域中，图结构有着,广泛的应用。,另外多维数组也属于非线性结构的范畴。,第35页,6-1-3基本算法,伪代码,线性结点的插入算法,顺序查找与二分法查找,排序（sort）或分类,第36页,伪代码,伪代码（Pseudocode）是一种算法描述语言。,伪代码的语法规则,在伪代码中，每一条指令占一行（elseif例,外），指令后不跟任何符号（Pascal和C中,语句要以分号结尾）。,第37页,线性结点的插入算法,插入运算的逻辑描述,线性表的插入运算是指在表的第i（1in+1）个位置上，,插入一个新结点x，使长度为n的线性表：,（a1，ai-1，ai，an）,变成长度为n+1的线性表：,（a1，ai-1，x，ai，an）,顺序表插入操作过程,在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持,一致，因此必须将表中位置为n，n-1，i上的结点，依,次后移到位置n+1，n，i+1上，空出第i个位置，然后,在该位置上插入新结点X，仅当插入设置i=n+1时，才无须,移动结点，直接将X插入表的末尾。,第38页,线性结点的插入算法,注意：,由于向量空间大小在声明时确定，当L-,lengthListSize时，表空间已满，不可再做,插入操作。,当插入位置i的值为in或i1时为非法位置，,不可做正常插入操作。,第39页,顺序查找与二分法查找,顺序查找,在表的组织方式中，线性表是最简单的一,种。,二分法查找（BinarySearch）,二分法查找又称折半查找，它是一种效率,较高的查找方法。,第40页,二分法查找要求,线性表是有序表，即表中结点按关键字有,序，并且要用向量作为表的存储结构。不,妨设有序表是递增有序的。,第41页,排序（sort）或分类,所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）,次序排列起来。其确切定义如下：,输入：n个记录R1，R2，Rn，其相应的关键字分别为K1，,K2，Kn。,输出：Ril，Ri2，Rin，使得Ki1Ki2Kin。(或,Ki1Ki2Kin)。,被排序对象文件。,文件由一组记录组成。,记录则由若干个数据项（或域）组成。其中有一项可用来标识一个记,录，称为关键字项。该数据项的值称为关键字（Key）。,注意：在不易产生混淆时，关键字项简称为关键字。,排序运算的依据关键字。,用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。,关键字的选取应根据问题的要求而定。,第42页,交换类排序,排序方法,排序算法分析,第43页,排序方法,初始。R1n为无序区。,第一趟扫描。从无序区底部向上依次比较相邻的两个气泡,的重量，若发现轻者在下、重者在上，则交换二者的位置。,即依次比较(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，,R1)；对于每对气泡(Rj+1，Rj)，若,Rj+1.keyRj.key，则交换Rj+1和Rj的内容。,第二趟扫描。扫描R2n。扫描完毕时，“次轻”的气,泡飘浮到R2的位置上,最后，经过n-1趟扫描可得到有序区R1n。,注意：第i趟扫描时，R1i-1和Rin分别为当前的有,序区和无序区。扫描仍是从无序区底部向上直至该区顶部。,扫描完毕时，该区中最轻气泡飘浮到顶部位置Ri上，结,果是R1.i变为新的有序区。,第44页,选择类排序,第1趟排序。在无序区R1n中选出关键字最小,的记录Rk，将它与无序区的第1个记录R1交换，,使R11和R2n分别变为记录个数增加1个的,新有序区和记录个数减少1个的新无序区。,第x趟排序。第i趟排序开始时，当前有序区和无,序区分别为R1x-1和Rxn(1xn-1)。该趟排,序从当前无序区中选出关键字最小的记录Rk，,将它与无序区的第1个记录Rx交换，使R1x,和Rx+1n分别变为记录个数增加1个的新有序,区和记录个数减少1个的新无序区。,第45页,基本思想,假设待排序的记录存放在数组R1n中。初始时，R1,自成1个有序区，无序区为R2n。从i=2起直至i=n为止，,依次将Ri插入当前的有序区R1i-1中，生成含n个记录,的有序区。,简单方法。首先在当前有序区R1i-1中查找Ri的正确,插入位置k(1ki-1)；然后将Rki-1中的记录均后移一,个位置，腾出k位置上的空间插入Ri。,注意：若Ri的关键字大于等于R1i-1中所有记录的关键,字，则Ri就是插入原位置。,改进的方法。一种查找比较操作和记录移动操作交替地进,行的方法。,第46页,6-2实训数据结构应用,实训目的,巩固数据结构线性表、数组、栈、队列和,二叉树的概念和基本操作。,掌握查找的算法过程描述和排序的算法过,程描述。,第47页,实训内容,线性表与数组的概念,线性表的概念。,线性表的特点。,线性表常用的基本算法。,数组的概念和基本操作以及存储格式。,学会将稀疏数组表示成三元组的格式，以便节省内存空间。,栈与队列,栈是受限的线性表，举例说明栈的先进后出的特点。,队列的概念，通过图表法举例说明队列的对头、对尾的概念。,线性链表,线性表与线性链表的不同。,掌握线性链表的算法。,插入某一个同学的数据。,单链表的定义以及结点分量的访问。,第48页,实训内容,树和二叉树,树与二叉树的区别。,二叉树的定义及性质。,举例说明什么是满二叉树和完全二叉树。,算法,设算法的输入实例中有序的关键字序列为：05、13、,19、21、37、56、64、75、80、88、92，要查找的关,键字K分别是21和85。写出使用二分法的具体查找过程。,写出对关键字序列为49、38、65、97、76、13、27的,文件进行冒泡排序的查找过程。,对初始关键字为49、38、65、97、76、13、27的文件,进行直接选择排序的过程。,第49页,