数据结构课程总结和思考.docVIP

XX大学 数据结构总结 姓 名： 专业班级： 学 号： 任课教师： 完成时间： 目录 ☆ 学习总结………………………………………………………3 ☆ 对赫夫曼树的研究……………………………………………5 ? 赫夫曼树的基本定义………………………………………………………5 ? 赫夫曼树的构造……………………………………………………………5 ? 动态赫夫曼编码的实现 …………………………………………………11 ☆ 对各类排序方法的总结………………………………………16 ☆ 学习感悟………………………………………………………18 ☆ 学习总结 学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。 第一章相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。 第二章具体地介绍链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。 堆栈与队列两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。 第四章串和数组中，我们知道串是一种特殊的线性表，是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。 基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。 第章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。 树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。 介绍了图的概念及其应用，图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。））夫曼树（ Huffman ）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。首先需要弄清楚关于路径和路径长度的概念。树中两个结点之间的路径由一个结点到另一结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点的路径长度之和。　　对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） （2）选取左右子树 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 （3）删除左右子树 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 （4）重复左右两步 重复二和三两步，直到集合F中只有一棵二叉树为止。 ◎ 举个例子 有个序列