数据结构与算法总结2010-彩色版

《数据结构与算法总结2010-彩色版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程的知识体系定义及相关术语ò线性表、栈、队列、多维数组定义逻辑结构及其特征基本操作（算法）ò二叉树、树存储结构（描述）ò无向图、有向图存储结构特点ADTò查找表实现存储结构的定义操作（算法）实现ò排序表算法的性能分析应用课程的核心算法：遍历（搜索、查找、检索）算法绪论绪论数据结构数据结构算法算法基逻存基算本辑储本法关系概结结概分念构构念析⑴数据⑴逻辑结构⑴存储结构⑴算法⑴问题规模⑵数据元素⑵数据结构⑵常用存储⑵算法特性⑵基本操作⑶数据对象的分类方法⑶评价方法⑶时间复杂度⑷ADT⑷描述算法⑷大O记号

2、线性表线性表逻辑结构逻辑结构存储结构存储结构基抽象顺链其本数据序接他概类型存比较存存念定义储储储⑴线性表定义⑴ADT定义⑴顺序表的特点⑴单链表的特点⑴循环链表⑵逻辑特征⑵基本操作⑵顺序表类定义⑵单链表类定义⑵双链表⑶基本操作的实⑶基本操作的实⑶静态链表现及时间性能现及时间性能⑷间接寻址特殊线性表栈比较队列逻辑结构存储结构逻辑结构存储结构⑴栈的定义顺链⑴队列定义循链⑵操作特性序比较⑵操作特性环比较队⑶ADT定义栈栈⑶ADT定义队列列⑴基本操作的实现⑴基本操作的实现⑵时间性能⑵时间性能多维数组逻辑结构存

3、储结构⑴数组的定义顺压⑵基本操作序缩⑶ADT定义存存储储按按特殊矩阵稀疏矩阵行列·对称矩阵优优·三角矩阵先先转置算法·对角矩阵寻址的计算方法树结构树二叉树相互转换逻辑结构存储结构逻辑结构存储结构树基抽树双孩孩二特二抽二顺二三线象亲子子叉殊叉象叉序的本数的表表兄树的树数树存叉叉索弟定术据遍示示表的二的据的储链链链类法法示定叉性类遍结义语历表表表型法义树质型历构⑴前序遍历⑴斜树⑴前序遍历⑴遍历操作的实现⑵后序遍历⑵满二叉树⑵中序遍历⑵基于遍历的其他⑶层序遍历⑶完全二叉树⑶后序遍历算法⑷层序遍历图逻辑结构

4、存储结构应用抽邻图基图接邻最最拓关象的本数的矩接小表生短扑键定术据搜阵比较表表成路排路类示义语索示法树径径型序法深广度度优比较优先先搜搜索索查找°熟练掌握顺序表和有序表的查找方法。°熟练掌握BST的构造和查找方法。°熟练掌握AVL树和B-树的结构、性质以及查找方法。°熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。°掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。时间复杂度比较排序方法平均情况最好情况最坏情况直接插入排序O(

5、n2)O(n)O(n2)希尔排序O(nlogn)O(n1.3)O(n2)2起泡排序O(n2)O(n)O(n2)快速排序O(nlogn)O(nlogn)O(n2)22简单选择排序O(n2)O(n2)O(n2)堆排序O(nlogn)O(nlogn)O(nlogn)222归并排序O(nlogn)O(nlogn)O(nlogn)222空间复杂度比较排序方法辅助空间直接插入排序O(1)希尔排序O(1)起泡排序O(1)快速排序O(logn)~O(n)2简单选择排序O(1)堆排序O(1)归并排序O(n)内容及要求

6、ò以线性表、树、二叉树、图等常用的数据结构的逻辑结构、存储结构和基本操作（算法）以及各种常用数据结构上实现的查找和排序算法为主要内容，ò培养和训练对算法的复杂性的分析能力以及选择合适的数据结构对简单的应用问题进行有效算法的设计能力。绪论绪论要求：ò要求掌握数据结构中常用的各种基本概念和术语，ò掌握算法描述和分析方法。ò重点掌握数据结构的逻辑结构、存储结构及操作（算法）三方面的概念及相互关系，ò难点是算法复杂性的分析方法。绪论内容和知识点：1．数据结构的基本概念和术语（识记）1．1数据、数据元素、数据

7、项、数据结构等基本概念。1．2数据结构的逻辑结构、存储结构及操作（算法）的含义及其相互关系。1．3数据结构的两大类逻辑结构和四种常用的存储表示方法。2．数据结构在软件系统中的作用（识记）。2．1数据结构在各种软件系统中所起的作用。2．2选择合适的数据结构是解决应用问题的关键步骤。3．算法的描述和分析（领会）3．1算法、算法的时间复杂性和空间复杂性、最坏的和平均的时间复杂性等概念。3．2算法的时间复杂性不仅仅依赖于问题的规模，也取决于输入实例的初始状态。3．3算法描述和算法分析的方法，对于一般算法能分

8、析出时间复杂性。线性表要求：ò线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本操作（算法）及其在存储结构上如何实现这些基本操作（算法）。ò在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。ò重点是熟练掌握顺序表和单链表上实现的各种基本操作（算法）及相关的时间性能分析，ò难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题线性表内容和知识点：1．线性表的逻辑结构