(11)--第5章计算机中的数据结构.ppt

第五章计算机中的数据结构目录查找算法与排序5.3数据结构的基本概念5.1基本数据结构5.235.1、数据结构的基本概念数据结构的定义数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。数据元素：数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，例如：学生（学号，姓名，成绩）有时也称为元素、结点、顶点或记录结构：结构：是数据元素之间的关联关系数据结构：数据结构带有结构的同性质数据元素的集合4逻辑结构数据元素之间逻辑上的关系，数据的组织形式。简称为数据结构.存储结构对数据的操作数据结构5.1、数据结构的基本概念5集合线性结构树形结构图状结构逻辑结构分类5.1、数据结构的基本概念6存储结构01存储结点每个结点存放一个数据元素02数据元素之间关系的表示即逻辑结构的计算机内部表示03常用的数据存储结构顺序存储方法链式存储方法数据数据元素以及数据元素以及数据元素之间的逻辑关元素之间的逻辑关系在计算机系在计算机内存中内存中的表示的表示。5.1、数据结构的基本概念7修改插入查找排序数据的运算删除5.1、数据结构的基本概念8目录查找算法与排序5.3数据结构的基本概念5.1基本数据结构5.29是是n(nO)n(nO)个个同同类类型型数数据据元元素素(结结点点)的的有有穷穷序序列列。其其中中数数据据元元素素的的个个数数n n称称为为线线性性表表的的长长度度(简简称称表表长长)。表表长长为为O O的的线线性性表表称为空表。称为空表。表示成：表示成：(a(a1 1，a a2 2 ，a an n)12线性表5.2、基本数据结构10线性表逻辑结构的基本特征:存在唯一的一个被称为“第一个”的数据元素和唯一的一个被称为“最后一个”的数据元素；除第一个数据元素外，其他数据元素有且仅有一个直接前趋元素；除最后一个数据元素外，其他数据元素有且仅有一个直接后继元素。5.2、基本数据结构11顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。元素元素a1a2a3ai-1aiai+1an相对相对地址地址012i-2i-1in-1特点：逻辑结构中相邻的结点在存储结构中仍相邻线性表的顺序存储结构顺序表顺序表5.2、基本数据结构12 在顺序表上实现插入和删除运算必须移动结点才能够在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化反映出结点间逻辑关系的变化(1)插入：在表的第i(1in+1)个位置上，插入一个新结点x，使线性表的长度加1。基本步骤为：将结点aian各后移一个位置,以便空出第i个位置；将新结点x置入第i个位置；表长加l元素元素a1a2a3ai-1aiai+1an相对地址相对地址012i-2i-1in-1插入、删除运算在顺序表上的实现5.2、基本数据结构13(2)删除：将表的第i(1in)个结点删去，使线性表的长度减1。基本步骤为：结点ai+1an依次前移一个位置(覆盖被删结点ai)；表长减1元素元素a1a2a3ai-1aiai+1an相对地址相对地址012i-2i-1in-1插入、删除运算在顺序表上的实现5.2、基本数据结构14单链表单链表是用一组任意的存储单元来存放线性表的结点。单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成；数据域用于存储线性表一个数据元素；指针域用于存放一个指针，该指针指向其直接后继结点。这样，所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次序不一定相同 a1anhead特点：指针为数据元素之间的逻辑关系的映像线性表的链式存储结构单链单链表表5.2、基本数据结构151000a210161004a110001008a4null1016a310081004head5.2、基本数据结构16栈的逻辑结构和线性表相同，但是，栈(Stack)是仅限在表的一端一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底,表中无元素时为空栈栈的运算原则是“先进后出”插入运算称为进栈(或入栈)删除运算称为退栈(或出栈)基本运算为：入栈、出栈、取栈顶元素栈底栈顶入栈出栈a1a2an 5.2、基本数据结构栈17队列(Queue)，两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。q队列的操作原则是先进先出栈和队列都是操作受限的线性表5.2、基本数据结构队列181.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:数据结构A逻辑结构B顺序存储结构C链式存储结构D提交单选题1分192.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是110A108B100C120D提交单选题1分203.线性表若采用链式存储结构时,要求内存中可用存储单元的地址:必须是连续的A部分地址必须是连续的B一定是不连续的C连续或不连续都可以D提交单选题1分224.一个栈的元素进栈序列是a、b、c、d、e,那么下面的（）不能做为一个出栈序列。e、d、c、b、aAd、e、c、b、aBd、c、e、a、bCa、b、c、d、eD提交单选题1分2324252627282930树是n(n0)个结点的有限集合。在任意一棵非空树中:有且仅有一个特定的称为根的结点：当nl时，其余结点分为m(m0)个互不相交的非空集合T1，T2，Tm，其中每一个集合本身又是一棵树，并称为根的子树。ABCDEFG5.2、基本数据结构树31树是一种树是一种“分支层次分支层次分支层次分支层次”结构。结构。“分支分支”是指树中任一结点的子孙可以按是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的它们所在的子树的不同而划分成不同的“分支分支”；“层次层次”是指树上所有结点可以按它们的层是指树上所有结点可以按它们的层数划分成不同的数划分成不同的“层次层次”树的概念5.2、基本数据结构32ABCDEFG(1)度度:树上任一结点所拥有的子树的数目称为该结点的度度。叶子或终端结点叶子或终端结点:度为0的结点称为叶子或终端结点叶子或终端结点。非终端结点或分支结点终端结点或分支结点:度大于O的结点称为非终端结终端结点或分支结点点或分支结点。树的度树的度:一棵树中所有结点的度的最大值称为该树的树的度度。树型结构的基本概念和术语5.2、基本数据结构33若树中结点A是结点B的直接前趋，则称A为B的双亲双亲或父结点，称B为A的孩子或子结点孩子或子结点。父结点相同的结点互称为兄弟兄弟。一棵树上的任何结点(不包括根本身)称为根的子孙子孙。反之，若B是A的子孙，则称A是B的祖先祖先。ABCDEFG5.2、基本数据结构34(3)结点的层数(或深度)从根开始算起：根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。ABCDEFG5.2、基本数据结构35ABCDEFG定义5.2、基本数据结构二叉树二叉树二叉树：是结点的有穷集合，它或者是空集，或者同时满足下述两个是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：条件：有且仅有一个称为根的结点；有且仅有一个称为根的结点；其余结点分为两个互不相交的集合其余结点分为两个互不相交的集合T1T1、T2T2，T1T1与与T2T2都是二叉树，都是二叉树，并且并且TlTl与与T2T2有顺序关系有顺序关系(T1(T1在在T2T2之前之前)，它们分别称为，它们分别称为根的左子树和右根的左子树和右子树。子树。二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次序关系。二叉树上任一结点左、右子树的根分别称为该结点的左孩子序关系。二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子和右孩子36形态和基本性质形态和基本性质二叉树有5 5种种基本形态，如图所示二叉树的基本性质二叉树的基本性质 二叉树第二叉树第i(i1)i(i1)层上至多有层上至多有2 2i-1i-1个结点。个结点。深度为深度为k(k1)k(k1)的二叉树至多有的二叉树至多有2 2k k-1-1个结点。个结点。对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n n0 0，度为，度为2 2的结点数为的结点数为n n2 2，则，则n n0 0=n=n2 2+1+1。空树 只有根节点 只有左子树 只有右子树 有左右子树5.2、基本数据结构二叉树375.2、基本数据结构满二叉树满二叉树一棵深度为一棵深度为k(k1)k(k1)且有且有2 2k k-1-1个结点的二个结点的二叉树称为叉树称为满二叉树满二叉树，这种树的特点是每一这种树的特点是每一层上的结点数都是最层上的结点数都是最大结点数。如图所示。大结点数。如图所示。385.2、基本数据结构完全完全二叉树二叉树深度为深度为k(k1)k(k1)有有n n个个结点的二叉树，当且结点的二叉树，当且仅当其每一个结点都仅当其每一个结点都与深度为与深度为k k的满二叉的满二叉树中编号从树中编号从1 1至至n n的结的结点一一对应时，称之点一一对应时，称之为为完全二叉树完全二叉树。395.2、基本数据结构若若i=l，则结点，则结点x是根，无双亲；若是根，无双亲；若i1，则，则x的双亲结点的双亲结点P的编号为的编号为i/2若若2*in，则结点，则结点x无左孩子无左孩子(且无右且无右孩子孩子)；否则，；否则，x的左孩子的编号为的左孩子的编号为2*i若若2*i+1n，则结点，则结点x无右孩子；无右孩子；否则，否则，x的右孩子的编号为的右孩子的编号为2*i+1基本性质基本性质如果将一棵有如果将一棵有n个结点的完全二叉树按个结点的完全二叉树按层编层编号号，则对任一编号为，则对任一编号为i(1in)的结点的结点x有：有：40二叉树的顺序存储 将一棵树中的所有n个结点按层编号，将编号为i的结点存入一维数组的第i个单元。若二叉树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。元素 ABCDEFG地址 12345678910115.2、基本数据结构存储结构ABCDEFG41二叉树的链式存储链式存储 结点结构中设两个指针域lchildlchild和rchildrchild分别指向该结点的左孩子左孩子和右孩子右孩子，另有一个数据域datadata存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。5.2、基本数据结构存储结构ABCDEFG425.2、基本数据结构遍历二叉树的遍历：二叉树的遍历：就是按某种次序就是按某种次序“访问访问”二叉树上的所有结点，二叉树上的所有结点，使得每个结点使得每个结点被访问一次被访问一次，而且，而且仅被访问一次仅被访问一次。二叉树二叉树是由三个基本单元组成：是由三个基本单元组成：根结点、左子树和右子树根结点、左子树和右子树根结点、左子树和右子树根结点、左子树和右子树。因。因此，若能依次遍历这三部分，便是遍历了整个二叉树。此，若能依次遍历这三部分，便是遍历了整个二叉树。限定先左后右，则遍历有限定先左后右，则遍历有先根先根先根先根(序序序序)、中根、中根、中根、中根(序序序序)和后根和后根和后根和后根(序序序序)遍历。遍历。遍历。遍历。43(1)先根遍历 访问根结点；先根遍历左子树；先根遍历右子树。(2)中根遍历 中根遍历左子树；访问根结点；中根遍历右子树。(3)后根遍历 后根遍历左子树；后根遍历右子树；访问根结点 5.2、基本数据结构遍历44下图二叉树的三种遍历序列 先根遍历序列：中根遍历序列：后根遍历序列：1248951011361278、4、9、2、10、5、11、l、12、6、3、78、9、4、10、11、5、2、12、6、7、3、15.2、基本数据结构454.在一棵二叉树上第3层的结点数最多为()(根为第0层)。2A4B6C8D提交单选题1分46设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（）。349350255351ABCD提交单选题1分47已知某二叉树的先序遍历序列为CEDBA，中序遍历序列为DEBAC，则它的后序遍历序列为（）。DABECACBEDDEABCDECABABCD提交单选题1分496543ABCD6.设栈设栈S的初始状态为空，元素的初始状态为空，元素a，b，c，d，e，f依次依次入栈入栈S，出栈的序列为，出栈的序列为b，d，f，e，c，a，则栈，则栈S的容量的容量至少应该是（至少应该是（）。）。提交单选题10分507.若在一棵非空树中，某结点若在一棵非空树中，某结点A有有3个兄弟结个兄弟结点（包括点（包括A自身），自身），B是是A的双亲结点，则的双亲结点，则B的的度为（度为（）。）。2345ABCD提交单选题10分51目录查找算法与排序算法5.3数据结构的基本概念5.1基本数据结构5.252顺序查找顺序查找5.3、查找与排序算法查找以顺序表作为存储结构以顺序表作为存储结构查找过程：查找过程：从表中最后一个（或第一个）记录开始，逐从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，键字和给定值比较相等，则查找成功则查找成功；反之，若直至第；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，没有所查记录，查找失败查找失败。53二分查找二分查找(折半查找折半查找)对于任何一个顺序表顺序表，若其中的所有结点按键值的某种次序排列，则称为有序表有序表。二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间(若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分)并在新的区间内重复上述过程，直到查找成功或查找区间长度为0(即查找不成功)为止。5.3、查找与排序算法查找54lowhighmidhighlowmidlowhighmid10 16 20 36 46 68 80 98第一次查找第二次查找第三次查找例：在下列数列中查找数据25：1 2 3 4 5 6 7 8mid=low+（high-low）/2high=mid-15.3、查找与排序算法55结束开始Low=1 High=8mid=low+（high-low)/2）low=high and arreymid!=keylow=mid+1High=mid-1输入数组array的值和要查找的值keyYarreymidkeymid=low+（high-low)/2）arreymid=key输出mid输出未找到NYNYN56直接插入排序直接插入排序依次将每个记录插入到一个有序的子序列中去。初始状态：946582第一趟：496582第二趟：46 9582第三趟：456982第四趟：456892第五趟：2456895.3、查找与排序算法排序5758冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，直至排序结束。5.3、查找与排序算法排序59初始状态：946582第一趟：496582 4 69582 4 65982 465892 4 65829第二趟:45628第三趟：4526第四趟：425第五趟：245.3、查找与排序算法6061直接选择排序直接选择排序首先在所有的记录中选出键值最小的记录，把它与第一个记录交换；然后在其余的记录中再选出键值最小的记录与第二个记录交换；依次类推，直至所有记录排序完成。在第i趟中，通过n-i次键值比较选出所需记录。初始状态：946582第一趟：246589第二趟：246589第三趟：245689 第四趟：245689第五趟：2456895.3、查找与排序算法排序62结束开始i=0i5 ai aj输入数组a的值Yjaj输出数组aNYNj=i+1YNi=i+1流流程程指指向？向？63需掌握基本知识点：（1）掌握线性表的结构（2）掌握栈和队列的概念及操作；（3）掌握树形结构、二叉树概念、性质及其遍历方法。（4）掌握查找与排序算法小结