专升本数据结构课程总结.doc

PAGE PAGE 8 课 程 总 结(提要) 数据构造和抽象数据类型ADT 定义：一个数学模型以及定义在该模型上的一组操作。 构成一个抽象数据类型的三个要素是： 数据对象、数据关系、根本操作 数据构造(非数值计算程序设计问题中的数学模型) ·逻辑构造 〔描绘数据元素之间的关系〕 线性构造—— 线性表、栈、队列、串、数组、广义表 非线性构造 —— 树和森林、二叉树、图 集合构造 —— 查找表、文件 ·存储构造〔逻辑构造在存储器中的映象〕 按“关系〞的表示方法不同而分： 顺序构造—以数据元素在存储器中的一个固定的相对位置来表示“关系〞 链式构造—以指针表示数据元素的“后继〞或“前驱〞 ·根本操作(三类) 构造的建立和销毁 查找 —— 引用型操作〔不改变元素间的关系〕 按“关系〞进展检索 按给定值进展检索 遍历——访问构造中的每一个数据元素，且对每个元素只访问一次 修改 —— 加工型操作〔改变元素间的关系〕 插入 删除 更新〔删除+插入〕 二、线性构造 ·线性表和有序表 —— 不同存储构造的比拟 顺序表：可以实现随机存取；?(1) 插入和删除时需要挪动元素；?(n) 需要预分配存储空间; 适用于“不常进展修改操作、表中元素相对稳定〞的场合。 链表：只能进展顺序存取；?(n) 插入和删除时只需修改指针; ?(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长〞的场合。 —— 应用问题的算法时间复杂度的比拟 例如，以线性表表示集合进展运算的时间复杂度为?(n2), 而以有序表表示集合进展运算的时间复杂度为?(n) ·栈和队列 —— 数据类型的特点及其应用范畴 ·串 —— 和线性表的差异： 数据对象不同〔数据元素限定为单个字符〕、根本操作集不同〔串整体作为操作对象〕、存储构造不同 ?? 串的形式匹配算法 ·数组 —— 只有引用型的操作，∴只需要顺序存储构造 多维到一维的不同映象方法： 以行序为主序〔低下标优先〕 以列序为主序〔高低标优先〕 ·广义表 —— 多层次的线性构造 特性：次序性、长度、层次性、深度、递归等 独有的特性：共享 存储构造的特点 三、非线性构造 ?? 树和森林、二叉树、图 ? 数据类型的定义(构造特点和根本操作) ? 存储构造 ? 二叉树的特性及其证明方法 ? 遍历 ·何谓“遍历〞？对构造中的每个元素都访问到，且只被访问一次 ·对非线性构造的遍历需要确定一条搜索途径 ·两条搜索途径:深度优先搜索和广度优先搜索 ·逻辑定义 深度优先搜索 —— 以构造中的某个数据元素为起始点，首先访问该数据元素，然后依次以它的各个“后继〞为起始点进展“深度优先搜索遍历〞。 其特点为：在访问了起始数据元素之后，沿着某一条“途径〞(后继)向前，直至“到底〞，然后退回一步找另一个后继，再向前继续，……，直至所有通路都走遍。 广度优先搜索 ——以构造中的某个数据元素为起始点，首先访问该数据元素，然后先访问其所有后继；之后其它结点的访问次序由已被访问的结点的访问次序决定：先被访问的结点的后继“优先于〞后被访问的结点的后继。 其特点为：在访问了起始数据元素之后，先访问它的所有后继，然后再依这些后继被访问的先后次序访问它们的后继，……，直至没有后继未被访问为止。 ·算法的形式描绘 深度优先搜索 ——通常采用递归的形式 二叉树〔先序、中序、后序〕、树/图〔先根、后根〕 一般形式算法的描绘: void DFSearch(ADT DS, ElemType v) { // 从v开场，对DS进展深度优先搜索遍历 if (DS) { visit(v); (visited[v]=true;) w=FirstSucc(v); while (w) { if (!visited[v]) DFSearch(DS, w); w=NextSucc(DS, v, w); }//while }//if }//DFSearch 不同数据构造(逻辑和存储)有不同写法。 例如对森林，起始点只有一个(第一棵树的根)，只有两个后继，且各棵树互不相交，按搜索途径上的访问次序有先序遍历和中序遍历之分。 void PreOrder_F(CSTree T) { // 对以T为根指针的森林进展先序遍历 if (T) { visit(T-data); PreOrder_F( T-firstchild ); // 先序遍历第一棵树