数据结构期末总结范文.docx

该【数据结构期末总结范文 】是由【min】上传分享，beplayapp体育下载一共【18】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【数据结构期末总结范文 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。数据结构期末总结范文第一篇数据结构期末总结范文第一篇-将待排序的序列分到若干个桶中,每个桶内的元素再进行个别排序。-时间复杂度最好可能是线性O(n),桶排序不是基于比较的排序参考:桶排序总结来说:当键的值的范围N与序列大小n相比很小时,桶排序是高效的,但是N相比于n开始增大时,性能降低。稳定排序:对于S中任意两个条目(ki,vi),(kj,vj),ki=kj,排序前和排序后相对位置不变基数排序:很简单,通俗来说就是为了保持稳定性,每一项都进行稳定排序,得到的结果很自然。如先按第二项稳定排序再对第一项,得到的结果就是第一项相等的情况下,第二项递增。数据结构期末总结范文第二篇定义:允许添加元素,且对总体大小没有明显的限制增减规则:当数组已满时,创建新数组是原数组的两倍,并将原数组元素存入;当实际元素个数小于数组大小的1/4,创建新数组是原数组的1/2,并将原数组元素存入。摊销:通过增加某些操作的投入,来减少其他操作所需的代价,来达到整体平均的目的分析append()时间复杂度:设动态数组从k增大到2k需要k个硬币,而我们将每个操作索取三个硬币,对不需要扩大数组的增添操作多付了两枚,我们将多收的两枚视为存入,则从k/2增长到k的过程中预留了k个硬币,正好供给我们进行从旧数组到新数组复制所需的k个硬币,综上,我们进行了k/2次append()共花费3k/2枚硬币,即每个append()操作的时间复杂度为O(1)例题:在动态数组中调用append()时,增幅由100%调整为25%,能否证明append()的复杂度为O(1)设原数组为k,增幅25%,则新数组为,设一次append()存储n枚硬币,增添元素消耗一枚,每次增幅后每个存储一枚则:(n-1)=解得:n=6即O(6n)所以每次操作为O(1)头哨兵(header)和尾哨兵(tailer):占用极小的空间极大地简化操作地逻辑数据结构期末总结范文第三篇树是由N个结点组成的有限集合,且只有一个结点是树的根结点,其余结点不相交。树的逻辑表达方法:树形表示法、文氏图表示法、凹入表示法、括号表示法。1、结点的度与树的度:树中某个结点的子树的个数称为该结点的度,树中所有结点的度中最大的为树的度。2、分支结点与叶子结点:度为0的是叶子结点,度为1的为单支结点、度为2的为双分支结点3、路径长度是该路径所通过的结点数目减14、孩子结点、双亲结点、兄弟结点5、结点层次(从树根开始定义),树中结点最大的层次称为树的高度或树的深度6、有序树和无序树7、森林:n个互不相交的树称为森林,把多个子树的根去掉就是森林数据结构期末总结范文第四篇分离链表:使每个桶A[j]存储其自身的二级容器,容器存储元组(k,v),如h(k)=j负载因子lambda<开放寻址:我们采用将每个元组直接存储到一个小的列表插槽中作为代替的方法,节省空间负载因子lambda<(python中为2/3)线性探测及其变种:线性探测:是使用开放寻址处理冲突的一个简单方法是线性探测。使用这种方法时,如果我们想要将一个元组(k,v)插入桶A[j]的位置,在这里j=h(k),但是A[j]被占用,那么我们将尝试使用A[(j+i)modN],以此重复操作。对于删除操作,我们不能简单地从插槽中移除,因为如果简单移除,随后搜寻原来插入的位置会失败(该位置在删除位置之后),一个典型办法是用一个带标记的特殊对象来代替被删除的对象。二次探测:反复探测A[(h(k)+f(i))modN]其中f(i)=i^2,它可以避免在线性探测中发生的聚集模式,而且还创建了自己的聚集方法:二次聚集。当N是素数且桶数组填充了不到一半时,二次探测保证可以找到空闲位置。但是当N不是素数且桶数组填充超过一半时,二次探测无法保证找到空闲位置。双哈希策略:一种不会引起线性探测和二次探测所引起的聚集问题的策略,迭代探测桶A[(h(k)+f(i))modN]f(i)=i*h’(k),h’(k)为二次哈希函数。另一种避免聚集的开放寻址是迭代地探测桶A[(h(k)+f(i))modN],f(i)是一个基于伪随机数产生器的函数这个数据结构允许我们以对数时间复杂度来实现插入和删除操作数据结构期末总结范文第五篇数据结构心得体会【篇1:数据结构学****总结】数据结构学****总结通过一学期对《数据结构与算法》的学****大概的了解了基本的数据结构和相应的一些算法。下面总结一下自己一个学期学****的收获和心得。数据结构是什么:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构重要性:一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率。在许多类型的程序的设计中,数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候,确定了数据结构后,算法就容易得到了。有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。不论哪种情况,选择合适的数据结构都是非常重要的。选择了数据结构,算法也随之确定,是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现,面向对象的程序设计语言就是其中之一。常见的数据结构::定义:顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。基本运算:置表空:sqlsetnull(l)判表满:sqlempty(l)求表长:sqllength(l)插入:sqlinsert(l,i,x)按序号取元素:sqlget(l,i)删除:sqldelete(l,i)按值查找:sqllocate(l,x):链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。相比于线性表顺序结构,链表比较方便插入和删除操作。分类:单链表—用一组地址任意的存储单元存放线性表中的数据元素。循环链表—循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。基本运算:建立链表,插入节点,删除节点。:堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。要点:堆:顺序随意栈:后进先出(last-in/first-out)。基本算法:置空栈:initstack(s)判栈空:stackempty(s)判栈满:stackfull(s)取栈顶元素:gettop(s)入栈:push(s)出栈:pop(s):队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(fifo—firstinfirstout)的线性表。分类:顺序队列;链队;基本运算:初始化队列qini(q)入队qadd(q,x)出队qdel(q,x)判断队列是否为qempty(q)判断队列是否为满qfull(q):对阵矩阵;三角矩阵;稀疏矩阵;:二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2的i-1次方个结点;深度为k的二叉树至多有2^(k)-1个结点;对任何一棵二叉树t,如果其终端结点数(即叶子结点数)为n0,度为2的结点数为n2,则n0=n2+1。(1)完全二叉树——若设二叉树的高度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层有叶子节点,并且叶子节点都是从左到右依次排布,这就是完全二叉树。(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。(3)深度——二叉树的层数,就是高度。性质:(1)在二叉树中,第i层的结点总数不超过2^(i-1);(2)深度为h的二叉树最多有2^h-1个结点(h=1),最少有h个结点;(3)对于任意一棵二叉树,如果其叶结点数为n0,而度数为2的结点总数为n2,则n0=n2+1;(4)具有n个结点的完全二叉树的深度为int(log2n)+1(5)有n个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:若i为结点编号则如果i1,则其父结点的编号为i/2;如果2*i=n,则其左儿子(即左子树的根结点)的编号为2*i;若2*in,则无左儿子;如果2*i+1=n,则其右儿子的结点编号为2*i+1;若2*i+1n,则无右儿子。(6)给定n个节点,能构成h(n)种不同的二叉树。h(n)为卡特兰数的第n项。h(n)=c(n,2*n)/(n+1)。(7)设有i个枝点,i为所有枝点的道路长度总和,j为叶的道路长度总和j=i+2i。二叉树遍历:遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设l、d、r分别表示遍历左子树、访问根结点和遍历右子树,则对一棵二叉树的遍历有三种情况:dlr(称为先根次序遍历),ldr(称为中根次序遍历),lrd(称为后根次序遍历)。(1)前序遍历访问根;按前序遍历左子树;按前序遍历右子树(2)中序遍历按中序遍历左子树;访问根;按中序遍历右子树(3)后序遍历按后序遍历左子树;按后序遍历右子树;访问根(4)层次遍历即按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)。:若结构中存在和关键字k相等的记录,则必定在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(hashfunction),按这个思想建立的表为散列表。散列函数:直接定址法;除留余数法;数字分析法;平方取中法;折叠法。冲突处理方法:开放地址法(线性探测再散列,二次探测再散列,伪随机探测再散列)链地址法。:一种较线性表和树更为复杂的数据结构。存储结构:邻接矩阵;邻接表;逆邻接表;十字链表;邻接多重表。图的遍历:深度优先遍历:深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为:从图中某个顶点v出发,访问该顶点,然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点,直至图中所有与v有路径相通的顶点都被访问完为止。广度优先遍历:对图的广度优先遍历方法描述为:从图中某个顶点v出发,在访问该顶点v之后,依次访问v的所有未被访问过的邻接点,然后再访问每个邻接点的邻接点,且访问顺序应保持先被访问的顶点其邻接点也优先被访问,直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。:在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较,直到找出与给定关键字相同的数为止。:首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。:先选取各块中的最大关键字构成一个索引表;查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。:定义:二叉排序树(binarysorttree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;查找:若根结点的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。若子树为空,查找不成功。排序算法::插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为o(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素。在第一部分排序后,再把这个最后元素插入到此刻已是有序的第一部分里的位置。:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2d1重复上述的分组和排序,直至所取的增量dt=1(dtdt-l?d2d1),即所有记录放在同一组中进行直接插入排序为止。