数据结构导论

自考02142,计算机专业数据结构导论知识点汇总。

标签删除则不用判断表满标签数据结构导论一 概论1.1 数据结构(Data structure是计算机组织数据存储数据的方式是指一组相互之间存在一种或多种特定关系数据组织方式和它们在计算机内的存储方式,以及定义在该组数据上的一组操作计算机解决问题的步骤数据的逻辑结构:是指数据及数据的组织方式数据结构、算法 和 程序 的关系算法 + 数据结构 = 程序(1976年瑞士计算机科学家尼克劳斯·维尔特[Niklaus Wirth]提出)1.2 基本概念和术语数据(Data)数据元素(Data Element数据项(Data Item数据组织的3个层次数据库中,数据项又称为字段 / 域。它是数据的不可分割的最小标识单位。实际问题中的数据称为原始数据数据元素常常还可分为若干个数据项,数据项是数据具有意义的最小单位逻辑结构(Logical Structure数据元素之间的结构关系物理结构(Physical Structure)/存储结构指数据结构在机内的表示,数据的逻辑结构在计算机中的实现是数据这个集合中的一个个体即数据的基本单位所有能被计算机处理的符号的集合数据的逻辑结构(D, {R}) 可分为下列几种: D = {d1,d2, …, dn} 集合线性结构树形结构图结构任意两个结点之间都没有邻接关系组织形式松散 数据元素同“属于一个集合”。R = { }结点按逻辑关系依次排列形成一条“链”,结点之间一个一个依次相邻接 R= {(d1, d2), (d2, d3), …, (dn-1, dn)},即除起始节点和终端结点d1、dn外,每个节点有一个前驱和一个后继具有分支、层次特性,上层的结点可以和下层多个结点相邻接,但下层结点只能和上层的一个结点相邻接(D, {R}) 构成树,即每个元素最多有一个前驱,可以有多个后继最复杂,任何两个结点都可以相邻接(D, {R})构成一个图数据的存储结构存储结构的主要部分存储结点(每个存储结点存放一个数据元素)数据元素之间关联方式的表示数据结构的存储=数据元素的存储+元素逻辑关系的存储顺序结构借助数据元素的相对存储位置来表示数据的逻辑结构线性表的顺序存储方法将表中的结点一次存放在计算机内存中一组连续的存储单元中顺序的方法将元素存储到一片连续的存储区特点预先分配好长度,需要预估存储数据需要的存储量插入和删除需要移动其他元素存取快捷,是随机存取结构链式结构链式存储方式借助数据元素地址的指针表示数据的逻辑结构这种结构是给结点附加一个指针字段,指出其后继节点的位置,即存放结点的存储单元分为两部分特点动态分配,不需要预先确定内存分配插入和删除不需要移动其他元素非随机存取结构索引存储方式散列存储方式借助索引表中的索引指示各存储节点的存储位置用散列函数指示各节点的存储位置1.3 算法及描述算法算法规定了求解给定类型问题所需的所有“处理步骤”执行顺序,使给定类型问题能在有限时间内被机械的求解算法必须使用某种语言描述程序介于自然语言和程序设计语言的伪代码非形式算法(自然语言)框图(N-S图)类C语言描述算法一个算法是对特定问题求解步骤的一种描述,它是指令的有穷序列特性有穷性: 一个算法总是在执行有穷步后结束确定性: 算法的每一步都必须是明确地定义的可行性: 算法中的每一步都是可以通过已经实现的操作来完成的输入: 一个算法有零个或者多个输入,这些输入取自于特定的对象集合输出:一个算法有一个或者多个输出,它们是与输入有特定关系的量1.4 算法分析算法的设计应满足正确性易读性健壮性时空性对于合法的输入产生符合要求的输出算法应该易读、便于交流, 这也是保证算法正确性的前提;添加注释也是一种增加可读性的办法当输入非法数据时, 算法还能做出适当的反应而不会崩溃, 如输出错误信息;算法中应该考虑适当的错误处理指算法的时间复杂度空间复杂度,算法分析主要分析算法时间复杂度空间复杂度,目的是提高算法的效率选择最优算法的2个度量时间复杂度空间复杂度算法运行时需要的总步数,通常是问题规模的函数算法执行时所占用的存储空间,通常是问题规模的函数确定算法的计算量合理地选择一种或几种操作作为“标准操作”,无特殊说明,默认以赋值语句作为标准操作确定每个算法共执行多少次标准操作,并将此次数规定为该算法的计算量算法的最坏情况时间复杂度:以算法在所有输入下的计算量的最大值作为算法的计算量算法的平均情况时间复杂度:以算法在所有输入下的计算量的加权平均值作为算法的计算量最坏情况时间复杂度平均情况时间复杂度统称为时间复杂度例:设变量a、b、c、d中各含一个整数,求a、b、c中的最大值与d的乘积:算法max1的最坏情况时间复杂度为5;算法max2的最坏情况时间复杂度为3