数据结构.ppt

河北理工大学 陈丽芳,数 据 结 构,Data Structure,河北理工大学 陈丽芳,此表必须记住！,河北理工大学 陈丽芳,数据的逻辑结构：含义：反映数据元素之间逻辑关系的数据结构。包含两方面的信息：第一，表示数据元素的信息；第二，表示各数据元素之间的前后件关系。例1：B=(D,R)，其中D是数据对象，R是该对象中所有数据成员之间的关系的有限集合。若有D=1,2,3,4,R=(1,2),(2,3),(3,4)，则我们可以用图的形式画出该数据结构B：,河北理工大学 陈丽芳,例2：家庭成员数据结构：B=(D,R),D=父亲，儿子，女儿，R=（父亲，儿子），（父亲，女儿），则图形表示如下：,河北理工大学 陈丽芳,例3：课程关系数据结构：B=(D,R),D=教师1，教师2，班级1，班级2，班级3，R=（教师1，班级1），（教师1，班级3），（教师2，班级1），（教师2，班级2），（教师2，班级3），则图形表示如下：,河北理工大学 陈丽芳,数据的逻辑结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,不讨论,非线性结构,河北理工大学 陈丽芳,数据的逻辑、物理结构,数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,河北理工大学 陈丽芳,分为：顺序存储结构 借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构 借助指示元素存储地址的指针表示数据 元素间的逻辑关系,数据的存储结构,NEXT,河北理工大学 陈丽芳,河北理工大学 陈丽芳,1536,元素2,1400,元素1,1346,元素3,元素4,h,链式存储,河北理工大学 陈丽芳,2.线性表,河北理工大学 陈丽芳,线性表的类型定义,线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继,河北理工大学 陈丽芳,线性表是一种典型的线性结构。,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,河北理工大学 陈丽芳,2.1 顺序表上基本运算的实现在c语言中，顺序表用一维数组来实现存储。算法：插入删除,河北理工大学 陈丽芳,定义：线性表的插入是指在第I（1i n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表,变成长度为n+1的线性表,需将第i至第n共（n-i+1)个元素后移,算法,插 入,河北理工大学 陈丽芳,线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表:(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n+1 表:(a1，a2，.，ai-1，x，ai，ai+1，.，an)。i 的取值范围为1=i=n+1。,河北理工大学 陈丽芳,x,河北理工大学 陈丽芳,顺序表上完成这一运算则通过以下步骤进行：(1)将aian 顺序向下移动，为新元素让出位置；(2)将 x 置入空出的第i个位置；(3)修改 last 指针(相当于修改表长)，使之仍指向最后一个元素。,河北理工大学 陈丽芳,算法如下：,for(j=n;j=i;j-)aj+1=aj;/元素后移ai=x;/插入元素n+;/表长度增加1,河北理工大学 陈丽芳,删除定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表,变成长度为n-1的线性表,),需将第i+1至第n共（n-i)个元素前移,河北理工大学 陈丽芳,河北理工大学 陈丽芳,算法如下：,for(j=i;jlen;j+)aj=aj+1;/元素前移len-;/表长度减1,河北理工大学 陈丽芳,2.2 线性表的链式实现和表示,线性链表线性链表的存储结构单链表的基本运算插入删除,河北理工大学 陈丽芳,特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置,线性表的链式存储结构,河北理工大学 陈丽芳,例 线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),头指针,河北理工大学 陈丽芳,实现,typedef struct node datatype data;struct node*next;LNode，*LinkList；;,定义的LNode是结点的类型，LinkList是指向Lnode类型结点的指针类型。,(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-next表示p指向结点的指针域,定义：结点中只含一个指针域的链表叫，也叫单链表,线性链表,河北理工大学 陈丽芳,单链表的基本运算,插入删除,河北理工大学 陈丽芳,s-next=p-next;,p-next=s;,单链表的插入,插入：在线性表两个数据元素a和b间插入x，已知p指向a,算法思路：1.找到第i-1个结点；若存在继续2，否则结束 2.申请、填装新结点；3.将新结点插入。结束。,河北理工大学 陈丽芳,删除：单链表中删除b，设p指向a,p-next=p-next-next;,单链表的删除,算法思路：1.找到第i-1个结点；若存在继续2，否则结束；2.若存在第i个结点则继续3，否则结束；3.删除第i个结点，结束。,河北理工大学 陈丽芳,循环链表,单链表上的访问是一种顺序访问，从其中某一个结点出发，可以找到它的直接后继，但无法找到它的直接前驱。因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存贮空间，仅对表的链接方式稍作改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点（或第一个结点）的地址，就使得整个链表构成一个环，又没有增加额外的存贮空间，称这样的链表为循环链表。,河北理工大学 陈丽芳,循环链表,优点：可以从任何一个结点出发访问到其他结点。单链表：只有从头结点（或第一个结点出发才能访问到其他结点）,河北理工大学 陈丽芳,3.栈和队列,河北理工大学 陈丽芳,栈,栈是特殊的线性表，是操作受限的线性表，称限定性DS,栈的定义栈的存储实现和运算实现顺序栈,河北理工大学 陈丽芳,栈定义,栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）,河北理工大学 陈丽芳,堆栈操作？,出栈元素顺序：B C D A,河北理工大学 陈丽芳,栈的存储实现和运算实现,由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。顺序栈链栈约定：栈顶指针指向栈顶元素。,河北理工大学 陈丽芳,3.2 队列,队列是特殊的线性表，是操作受限的线性表，称限定性DS,河北理工大学 陈丽芳,队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),3.2.1 队列的定义,河北理工大学 陈丽芳,初始时,队列为空,有 front=-1 rear=-1队列元素个数=rear-front,front 指出实际队头元素所在位置的前一个位置.,河北理工大学 陈丽芳,顺序队列出入队,河北理工大学 陈丽芳,循环队列,为充分利用向量空间，克服“假上溢”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列判断：空队列：s=0 并且 front=rear满队列：s=1 并且front=rear,河北理工大学 陈丽芳,利用模运算,河北理工大学 陈丽芳,计算循环队列元素个数方法：,若frontrear元素个数=n-（front-rear）其中n是循环队列的容量。,河北理工大学 陈丽芳,在前面讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，具有单一的前驱和后继的数据关系。而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构。,河北理工大学 陈丽芳,4.树与二叉树,树的基本概念二叉树二叉树的性质二叉树的存储结构二叉树的基本操作遍历二叉树,河北理工大学 陈丽芳,树的定义,树是一类重要的非线性数据结构，是以分支关系定义的层次结构定义：树(tree)是n(n0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点根树中各子树是互不相交的集合,河北理工大学 陈丽芳,根,子树,河北理工大学 陈丽芳,基本术语结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的兄弟(sibling)同一双亲的孩子树的度一棵树中最大的结点度数结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数,河北理工大学 陈丽芳,二叉树,定义性质特殊的二叉树二叉树的遍历,河北理工大学 陈丽芳,二叉树定义,定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态(5种）,河北理工大学 陈丽芳,二叉树的性质,性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k=1）。,性质2 深度（高度）为k的二叉树最多结点数为2k-1（k=1）。,证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和，既为 20+21+2k-1=2k-1。,河北理工大学 陈丽芳,性质3 对任意一棵二叉树，如果叶子结点(度为0)个数为n0，度为2的结点个数为n2，则有n0=n2+1。,证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2，而一棵二叉树中，除根结点外所有都为孩子 结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。,为继续给出二叉树的其它性质，先定义两种特殊的二叉树。,河北理工大学 陈丽芳,几种特殊形式的二叉树满二叉树定义：深度为k具有2k-1个结点的二叉树,特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。特点1、叶子结点只可能在层次最大的两层上出现2、对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1,河北理工大学 陈丽芳,河北理工大学 陈丽芳,特殊二叉树的性质,性质4：具有n个结点的完全二叉树高度为log2n+1 或 log2（n+1）。,河北理工大学 陈丽芳,习题解析,1、假设二叉树中所有非叶子结点都有左、右子树，则对这种二叉树：（1）试问：有n个叶子结点的树中共有多少个结点？性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,河北理工大学 陈丽芳,解：(1)依题意，这种二叉树中没有度为1 的结点，度为2的结点数n2和度为0的结点数n0之间满足关系：n0=n2+1；(性质2)所以总的结点数N=n2+n0=n0-1+n0=2n0-1=2n-1。,河北理工大学 陈丽芳,二叉树的遍历,二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。,河北理工大学 陈丽芳,二叉树的遍历,二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历有三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。,河北理工大学 陈丽芳,二叉树的遍历先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点,河北理工大学 陈丽芳,D L R,先序遍历序列：A B D C,先序遍历:,河北理工大学 陈丽芳,L D R,中序遍历序列：B D A C,中序遍历:,河北理工大学 陈丽芳,L R D,后序遍历序列：D B C A,后序遍历:,河北理工大学 陈丽芳,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,河北理工大学 陈丽芳,遍历算法应用举例,例 根据给出的二叉树的前序序列和中序序列，建立该二叉树.,分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：,河北理工大学 陈丽芳,1.用前序序列的第一个结点作为根结点;,2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);,3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;,4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。,假设前序序列为ABDGHCEFI，,中序序列为GDHBAECIF，,则得到的二叉树如下页所示,河北理工大学 陈丽芳,1。A为根结点,A BDGH CEFI,GDHB A ECIF,2.B为左子树的根结点,B DGH,GDH B,3.D为左子树的左子树的根结点,河北理工大学 陈丽芳,4。C为右子树的根结点,5。F为右子树的右子树的根结点,C E FI,E C IF,河北理工大学 陈丽芳,5.查 找,河北理工大学 陈丽芳,查 找,查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素,一、顺序查找,二、折半查找（二分查找）,河北理工大学 陈丽芳,1 顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述,64,监视哨,比较次数=5,比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1,河北理工大学 陈丽芳,2 折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表,河北理工大学 陈丽芳,河北理工大学 陈丽芳,河北理工大学 陈丽芳,河北理工大学 陈丽芳,排序,为了便于查找，通常希望计算机中的数据表是按关键码有序的。排序和查找一样，是一种非常重要的数据处理功能，计算机系统的很大一部分工作是对数据进行排序。,河北理工大学 陈丽芳,插入排序：直接插入排序交换排序：冒泡排序、快速排序选择排序：简单选择排序,排序,排序定义将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。,河北理工大学 陈丽芳,插入排序,基本思路：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的子序列的适当位置，直到全部记录插入完成为止。,河北理工大学 陈丽芳,直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序为止。,河北理工大学 陈丽芳,例,49 38 65 97 76 13 27,i=2 38(38 49)65 97 76 13 27,i=3 65(38 49 65)97 76 13 27,i=4 97(38 49 65 97)76 13 27,i=5 76(38 49 65 76 97)13 27,i=6 13(13 38 49 65 76 97)27,i=1(),i=7(13 38 49 65 76 97)27,27,97,76,65,49,38,27,河北理工大学 陈丽芳,算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：,记录移动次数：,若待排序记录按关键字从大到小排列(逆序)关键字比较次数：,记录移动次数：,若待排序记录是随机的，取平均值关键字比较次数：,记录移动次数：,河北理工大学 陈丽芳,交换排序,基本思路：通过排序表中两个记录关键码的比较，若与排序要求相逆，则将二者交换。,河北理工大学 陈丽芳,交换排序冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,河北理工大学 陈丽芳,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,河北理工大学 陈丽芳,算法评价时间复杂度最好情况（正序）比较次数：n-1移动次数：0最坏情况（逆序）比较次数：,移动次数：,河北理工大学 陈丽芳,快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。,河北理工大学 陈丽芳,完成一趟排序：(27 38 13)49(76 97 65 50),分别进行快速排序：(13)27(38)49(50 65)76(97),快速排序结束：13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,河北理工大学 陈丽芳,算法评价时间复杂度最好情况（正序）需要进行1趟排序比较次数：n-1最坏情况（逆序）需要进行n-1趟排序比较次数：n(n-1)/2,河北理工大学 陈丽芳,选择排序,基本思想是：每次从待排序的记录中选出关键字最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完为止,做法如下：首先在所有的记录中选出键值最小的记录，把它与第一个记录交换，然后在其余的记录中再选出键值最小的记录与第二个记录交换，依次类推，直到所有的记录排序完成。第i趟在n-i+1(i=1,2,.n-1)个记录中选择键值最小的记录作为有序序列的第i个记录。,河北理工大学 陈丽芳,void SelectSort(int r,int n)int temp;int i,j,k;for(i=1;in;i+)/做第i趟排序(1in-1)k=i;/在当前无序区Ri.n选最小的记录Rk for(j=i+1;j=n;j+)if(rjrk)k=j;/k记下目前找到的最小关键字所在的位置 if(k!=i)/交换Ri和Rk temp=ri;ri=rk;rk=temp;/if/for,河北理工大学 陈丽芳,排序方法 最好 最坏插入 n-1(n+2)(n-1)/2冒泡 n-1 n(n-1)/2快排 n-1 n(n-1)/2选择 n-1 n(n-1)/2堆排序 O(nlog2n),