专升本数据结构课程总结.doc
《专升本数据结构课程总结.doc》由会员分享,可在线阅读,更多相关《专升本数据结构课程总结.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、课 程 总 结(提要)一、 数据结构和抽象数据类型ADT定义:一个数学模型以及定义在该模型上的一组操作。构成一个抽象数据类型的三个要素是:数据对象、数据关系、基本操作数据结构(非数值计算程序设计问题中的数学模型)逻辑结构 (描述数据元素之间的关系) 线性结构 线性表、栈、队列、串、数组、广义表非线性结构 树和森林、二叉树、图集合结构 查找表、文件存储结构(逻辑结构在存储器中的映象) 按“关系”的表示方法不同而分:顺序结构以数据元素在存储器中的一个固定的相对位置来表示“关系”链式结构以指针表示数据元素的“后继”或“前驱”基本操作(三类) 结构的建立和销毁 查找 引用型操作(不改变元素间的关系)
2、按“关系”进行检索 按给定值进行检索 遍历访问结构中的每一个数据元素,且对每个元素只访问一次修改 加工型操作(改变元素间的关系) 插入 删除 更新(删除+插入)二、线性结构 线性表和有序表 不同存储结构的比较顺序表:可以实现随机存取;O(1)插入和删除时需要移动元素;O(n)需要预分配存储空间;适用于“不常进行修改操作、表中元素相对稳定”的场合。链表:只能进行顺序存取;O(n)插入和删除时只需修改指针; O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 应用问题的算法时间复杂度的比较例如,以线性表表示集合进行运算的时间复杂度为O(n2),而以有序表表示集合
3、进行运算的时间复杂度为O(n) 栈和队列 数据类型的特点及其应用范畴 串 和线性表的差异:数据对象不同(数据元素限定为单个字符)、基本操作集不同(串整体作为操作对象)、存储结构不同 串的模式匹配算法 数组 只有引用型的操作,只需要顺序存储结构 多维到一维的不同映象方法:以行序为主序(低下标优先)以列序为主序(高下标优先) 广义表 多层次的线性结构特性:次序性、长度、层次性、深度、递归等独有的特性:共享存储结构的特点三、非线性结构 树和森林、二叉树、图 数据类型的定义(结构特点和基本操作) 存储结构 二叉树的特性及其证明方法 遍历 何谓“遍历”?对结构中的每个元素都访问到,且只被访问一次 对非线
4、性结构的遍历需要确定一条搜索路径 两条搜索路径:深度优先搜索和广度优先搜索逻辑定义 深度优先搜索 以结构中的某个数据元素为起始点,首先访问该数据元素,然后依次以它的各个“后继”为起始点进行“深度优先搜索遍历”。其特点为:在访问了起始数据元素之后,沿着某一条“路径”(后继)向前,直至“到底”,然后退回一步找另一个后继,再向前继续,直至所有通路都走遍。广度优先搜索 以结构中的某个数据元素为起始点,首先访问该数据元素,然后先访问其所有后继;之后其它结点的访问次序由已被访问的结点的访问次序决定:先被访问的结点的后继“优先于”后被访问的结点的后继。其特点为:在访问了起始数据元素之后,先访问它的所有后继,
5、然后再依这些后继被访问的先后次序访问它们的后继,直至没有后继未被访问为止。算法的形式描述深度优先搜索 通常采用递归的形式 二叉树(先序、中序、后序)、树/图(先根、后根)一般形式算法的描述: void DFSearch(ADT DS, ElemType v) / 从v开始,对DS进行深度优先搜索遍历 if (DS) visit(v); (visitedv=true;) w=FirstSucc(v); while (w) if (!visitedv) DFSearch(DS, w); w=NextSucc(DS, v, w); /while /if /DFSearch不同数据结构(逻辑和存储)有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 总结
限制150内