数据结构期末复习资料教程.docxVIP

数据结构复习资料 绪论 基本概念和术语 1.数据是对客观事物的符号表示；数据元素是数据的基本单位，一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位；数据对象是性质相同的数据元素的集合，是数据的一个子集。 2.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 3. A.数据结构的三要素：①数据的逻辑结构②数据的存储结构③数据的运算（算法） B.任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构 4.数据的逻辑结构:①集合②线性结构③树型结构④图状结构或网状结构 1.2算法和算法分析 1.算法的五个特性：①有穷性②确定性③可行性④输入⑤输出 2.时间复杂度：时间复杂度是指执行算法所需要的计算工作量 空间复杂度：空间复杂度是指执行这个算法所需要的内存空间 线性表 2.1线性表的顺序表示和实现 1.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 2.优点：线性表的顺序存储结构是一种随机存取的存储结构 3.顺序线性表插入： 顺序线性表删除： 4.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(可连续，可不连续) 5.对数据元素来说，除了存储其自身的信息之外，还需存储一个指示其直接后继的信息(存储位置)，这两部分信息组成数据元素的存储映像，称为结点。他包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或域。N个结点链结成一个链表，即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。 6.链表的插入与删除 7.双向链表的插入与删除 栈和队列 3.1 栈 1．栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。 2.栈又称为后进先出的线性表 3.栈的进栈与出栈操作 3.2队列 1．队列是一种先进先出的线性表，它只允许在表的一段进行插入，而在另一端删除元素。 2.允许插入的一端叫做队尾，允许删除的一端则称为对头。 第四章 串 4.1串类型的定义 1.串（或字符串）是由零个或多个字符组成的有限序列。串中字符的数目n称为串的长度。零个字符的串称为空串。 2.串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置。 3.只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。 第五章 树和二叉树 5.1树的定义和基本术语 1.树是n个结点的有限集 2.结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点拥有的子树数。度为0的结点称为叶子或终端结点。度不为0的结点称为非终端结点或分支结点。 树的度：树内各结点的度的最大值。 孩子：结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。 兄弟：同一个双亲的孩子之间互称兄弟。 祖先：结点的祖先是从根到该结点所经分支上的所有结点，反之，以某结点为根的子树中任一结点都称为该结点的子孙。 结点所处层次：从根开始定义起，根为第一层，根的孩子为第二层。 树的深度：树中结点的最大层次称为树的深度或高度。 有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。 森林：是m棵互不相交的树的集合。 5.2二叉树 1.二叉树是另一种树型结构，特点是：每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，次序不能换。 2.二叉树的性质： ①在二叉树的第i层上至多有2i-1个结点(i=1) ②深度为k的二叉树至多有2k-1个结点（k=1） 3.满二叉树：每一层上的结点数都是最大结点数，深度为k且有2k-1个结点的二叉树 4完全二叉树：若设二叉树的深度为h，则共有h层。除第h层外，其它各层(0~h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。 5.3遍历二叉树 1.先序遍历DLR 遍历结果：- + a * b - c d / e f 2.中序遍历LDR 遍历结果：a + b * c - d - e / f 3.后序遍历LRD 遍历结果：a b c d - * + e f / - 4.树的综合算法 求深度… 5.4树和森林 1.森林与二叉树的转换 ①在同胞兄弟之间加连线； ②保留结点与第一个孩子之间的连线，去掉其余连线； ③顺时针旋转45度。以根结点为轴；左孩子不再旋转。 5.5赫夫曼树及其应用 1.路径长度：两个结点之间的路径长度是连接两结点的路径上的分支数。 树的路径长度：树的路径长度是各结点到根结点的路径长