
2023年数据结构知识点整理.doc
8页数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序辨认和解决的符号(数值、字符等)的集合数据元素(数据成员)是数据的基本单位在不同的条件下,数据元素又可称为元素、结点、顶点、记录等数据对象具有相同性质的数据元素(数据成员)的集合数据结构由某一数据对象及该对象中所有数据成员之间的关系组成记为Data_Structure = {D, R}其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合数据类型是指一种类型,以及定义在这个值集合上的一组操作的总称判断一个算法的优劣重要标准:对的性、可使用性、可读性、效率、健壮性、简朴性算法效率的衡量方法:后期测试,事前估计算法分析是算法的渐进分析简称数据结构涉及“逻辑结构” 和“物理结构”两个方面(层次):逻辑结构是对数据成员之间的逻辑关系的描述,它可以用一个数据成员的集合和定义在此集合上的若干关系来表达物理结构是逻辑结构在计算机中的表达和实现,故又称“存储结构” 线性表的定义:n( ³ 0)个表项的有限序列 L =(a1, a2, …, an) ai是表项,n是表长度第一个表项是表头,最后一个是表尾线性表的特点:表中元素的数据类型相同;线性表中,结点和结点间的关系是一对一的,有序表和无序表线性表的存储方式。
一,顺序存储方式,二,链表存储方式顺序表的存储表达有2种方式:静态方式和动态方式顺序表的定义是:把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中顺序表的特点:用地址连续的一块存储空间顺序存放各表项,各表项的逻辑顺序与物理顺序一致,对各个表项可以顺序访问,也可以随机访问 单链表是一种最简朴的链表表达,也叫线性链表,用她来表达线性表时,用指针表达结点间的逻辑关系特点:是长度可以很方便地进行扩充连续存储方式(顺序表)特点:存储运用率高,存取速度快缺陷:插入、删除等操作时需要移动大量数据:链式存储方式(链表) 特点:适应表的动态增长和删除缺陷:需要额外的指针存储空间单链表的类定义:多个类表达一个概念(单链表)分为:链表结点(ListNode)类 ,链表(List)类循环链表的概念:是另一种形式的表达线性表的链表,它的结点结构与单链表相同,与单链表不同的是链表中表尾结点的LINK域中不是NULL,而是存放了一个指向链表开始结点的指针,这样,只要知道表中任何一个结点的地址,就能遍历表中其他任何一结点双向链表的概念:在双向链表的没饿结点中应有两个链接指针作为它的数据成员:1LINK指示它的前驱结点,RLINK指示它的后继结点,因此,双向链表的每个结点至少有3个域:1LINK(前驱指针) DADA(数据) RLINK(后继指针)。
栈:定义为只允许在表的末端进行插入和删除的线性表特点是:后进先出递归的定义 :若一个对象部分地包含它自己,或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程以下三种情况经常用到递归方法一 定义是递归的二 数据结构是递归的三问题的解法是递归的队列:队列是只允许在一端删除,在另一端插入的顺序表允许删除的一端叫做队头,允许插入的一端叫做队尾特性:先进先出优先级队列:是不同于先进先出队列的另一种队列每次从队列中取出的是具有最高优先权的元素多维数组是一维数组的推广多维数组是一维数组的推广多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简朴字符串是 n ( ³ 0 ) 个字符的有限序列, 记作S : “c1c2c3…cn”其中,S 是串名字c1c2c3…cn”是串值ci 是串中字符n 是串的长度,n = 0 称为空串广义表是 n ( ≥0 ) 个表元素组成的有限序列,记作LS (a1, a2, a3, …, an),LS 是表名,ai 是表元素,可以是表(称为子表),可以是数据元素(称为原子)。
n为表的长度n = 0 的广义表为空表n > 0时,表的第一个表元素称为广义表 的表头(head),除此之外,其它表元素组成的表称为广义表的表尾(tail有根树:一棵有根树 T,简称为树,它是n (n≥0) 个结点的有限集合当n = 0时,T 称为空树;否则,T 是非空树,记作 T={ 空集 n=0 {r,T1,T2….Tn},n>0r 是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱;根以外的其他结点划分为 m (m ³ 0) 个互不相交的有限集合T1, T2, …, Tm,每个集合又是一棵树,并且称之为根的子树每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继二叉树的定义:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成完全二叉树 :─ 若设二叉树的深度为 k,则共有 k 层除第 k 层外,其它各层 (1~k-1) 的结点数都达成最大个数,第k层从右向左连续缺若干结点,这就是完全二叉树二叉树的遍历就是按某种顺序访问树中的结点,规定每个结点访问一次且仅访问一次。
设访问根结点记作 V遍历根的左子树记作 L 遍历根的右子树记作 R则也许的遍历顺序有:前序 VLR 镜像 VRL;中序 LVR 镜像 RVL;后序 LRV 镜像 RLV前序遍历二叉树算法的框架是:若二叉树为空,则空操作;否则访问根结点 (V);前序遍历左子树 (L);前序遍历右子树 (R)遍历结果- + a * b - c d / e f树的后根顺序遍历:当树非空时依次后根遍历根的各棵子树访问根结点:树后根遍历 EFBCGDA;相应二叉树中序遍历 EFBCGDA;树的后根遍历结果与其相应二叉树表达的中序遍历结果相同:树的后根遍历可以借助相应二叉树的中序遍历算法实现最小堆和最大堆:假如有一个关键码集合K={K0,K1,K2,K3,….,Kn-1},把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中并满足Ki≤K2i+1且Ki≤K2i+2(或者Ki≥K2i+1且KiK2i+2 )i=0,1,….[(n-2)/2],则称这个集合为最小堆或最大堆堆是最高效的一种数据结构,每次出队列的是优先权最高的元素用堆实现其存储表达,可以高效运作堆的建立:有2种方式建立最小的堆,一种方式是通过第一个构造函数建立一个空堆,其大小通过动态存储分派得到,另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。
途径:从树中一个结点到达另一个结点之间的分支构成该两结点之间的途径途径长度:是指途径上的分支条数,树的途径长度是从树的根结点到每一个结点的途径长度之和由树的定义,从根结点到达书中每一结点有且仅有一条途径Huffman树:带权途径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树 带途径长度最小的扩充二叉树不一定是完全二叉树集合是成员(元素)的一个群集集合中的成员可以是原子(单元素),也可以是集合字典是一些元素的集合,每个元素有一个称作关键码(key)的域,不同元素的关键码互不相同散列方法:抱负的搜索方法是可以不通过比较,一次直接从字典中得到要搜索的元素假如在元素存储位置与其关键码之间建立一个拟定的相应函数关系Hash(), 使得每个关键码与结构中一个唯一的存储位置相相应:Address = Hash(key)在插入时依此函数计算存储位置并按此位置存放在搜索时对元素的关键码进行同样的计算,把求得的函数值当做元素存储位置,在结构中按此位置搜索这就是散列方法在散列方法中所用转换函数叫做散列函数按此方法构造出来的表叫做散列表使用散列方法进行搜索不必进行多次关键码的比较, 搜索速度比较快, 可以直接到达或逼近具有此关键码的表项的实际存放地址。
散列函数是一个压缩映象函数关键码集合比散列表地址集合大得多因此有也许通过散列函数的计算,把不同的关键码映射到同一个散列地址上,这就产生了冲突搜索就是在数据集合中寻找满足某种条件的数据对象搜索的结果通常有两种也许:搜索成功,即找到满足条件的数据对象这时,作为结果,可报告该对象在结构中 的位置, 还可给出该对象中的具体信息搜索不成功,或搜索失败作为结果,应报告一些信息, 如失败标志、位置等 搜索结构通常称用于搜索的数据集合为搜索结构,它是由同一数据类型的对象(或记录)组成在每个对象中有若干属性,其中有一个属性,其值可唯一地标记这个对象称为关键码使用基于关键码的搜索,搜索结果应是唯一的但在实际应用时,搜索条件是多方面的,可以使用基于属性的搜索方法,但搜索结果也许不唯一实行搜索时有两种不同的环境静态环境,搜索结构在插入和删除等操作的前后不发生改变¾ 静态搜索表 动态环境,为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整,结构也许发生变化¾ 动态搜索表顺序搜索重要用于性表中搜索设若表中有 CurrentSize 个元素,则顺序搜索从表的先端开始,顺序用各元素的关键码与给定值 x 进行比较若找到与其值相等的元素,则搜索成功,给出该元素在表中的位置。
若整个表都已检测完仍未找到关键码与 x 相等的元素,则搜索失败给出失败信息二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:1每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同2左子树(假如非空)上所有结点的关键码都小于根结点的关键码3右子树(假如非空)上所有结点的关键码都大于根结点的关键码4左子树和右子树也是二叉搜索树二叉搜索树为二叉排序树假如对一棵二叉搜索树进行中序遍历,可以按从小到大的顺序,将各结点关键码排列起来,所以也称二叉搜索树为二叉排序树在二叉搜索树上进行搜索,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程它可以是一个递归的过程假设想要在二叉搜索树中搜索关键码为 x 的元素,搜索过程从根结点开始假如根指针为NULL,则搜索不成功;否则用给定值 x 与根结点的关键码进行比较:若给定值等于根结点关键码,则搜索成功,返回搜索成功信息并报告搜索到结点地址若给定值小于根结点的关键码,则继续递归搜索根结点的左子树;否则递归搜索根结点的右子二叉搜索树的插入算法:为了向二叉搜索树中插入一个新元素,必须先检查这个元素是否在树中已经存在在插入之前,先使用搜索算法在树中检查要插入元素有还是没有。
假如搜索成功,说明树中已有这个元素,不再插入;假如搜索不成功,说明树中本来没有关键码等于给定值的结点,把新元素加到搜索操作停止的地方 图定义:图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构:Graph=( V, E ) 其中 V = { x | x Î 某个数据对象} 是顶点的有穷非空集合; E = {(x, y) | x, y Î V } 或E = {
