数据结构与算法设计复习提纲。
---穆继辉。
第一章。一、数据结构的概念：相互之间存在一种或多种特定关系的数据元素的集合。
二、四类基本结构：1. 集合结构 2. 线性结构 3. 树形结构4. 图状结构。
三、算法的五种特性：1.有穷性2.确定性3.可行性4.输入5.输出。
四、一个“好”的算法要达到的要求：①正确性 ②可读性③健壮性 ④高效率与低存储量需求。
数据元素的存储结构：顺序存储结构、链式存储结构。
第二章。一、线性表是最简单最基本、也是最常用的一种线性结构。他的两种存储方法：顺序存储和链式存储。
二、线性表的概念：线性表是具有相同数据类型的n个数据元素的有限序列。
三、线性表的基本操作：（1）线性表初始化。
2）求线性表的长度。
3）取表元。
4) 按值查找。
5）插入操作。
6）删除操作。
四、栈的操作规则：后进先出、先进后出。
队列的操作规则：先进先出。
第四章。一、串的定义：由零个或多个任意字符组成的字符序列。
子串：子串中任意连续的字符组成的子序列成为该字符的子串。
主串：包含子串的串相应地成为主串。
子串的位置：子串的第一个字符在主串中的序号成为子串的位置。
二、串的静态存储、采用顺序结构。
串的动态存储：采用链式存储结构、堆存储结构。
三、brute-force算法！！（p91）
kmp算法！！（p93）
递归算法是一种有效的算法设计方法。递归是自调用。递归算法就是指包含有调用算法本身语句的算法。（p109）
第七章。一、树的定义：树是n个有限数据元素的集合当n等于o时，为空树。
树的特点：1.树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。
2.树中所有节点可以有零个或多个后继节点。
树的表示方法：直观表示法、嵌套集合表示、广义表形式表示、凹入表示法。
树的基本术语：
节点的度：节点所拥有的子树的个数称为该节点的度。
树的度： 树中各节点的最大值称为该树的度。
树的深度； 树中所有节点的最大层数称为数的深度。
森林： 零棵或有限棵不相交的树的集合称为森林。
叶节点： 度数为零的节点。
分枝节点：度数不为零的节点。
二、树的存储结构：顺序存储结构、链式存储结构。
树的的存储方式：双亲表示法 （p142—图7-5）
孩子表示法指针方式( p142图7-6)
数组方式（p143图7-7）
树的链式方式 (p144图7-8)
孩子兄弟表示法 （图7-9）
树的遍历树的前序遍历---根左右。
树的后序遍历---左右根。
树的层次序遍历---第一层、第二层、……
参见p145图7-10
三、 二叉树 ：每个节点至多只有两棵子树。
二叉树的性质：1.
二叉树的存储结构：顺序存储结构（p148）、链式存储。
二叉树的遍历：前序遍历 --根左右。
中序遍历 --左根右。
后序遍历 --左右根。
参见（p150图7-18）
四、 线索二叉树（p157）先对一棵二叉树线索化、求出其要的某种遍历对照得出某种遍历的线索二叉树。
五、 树、森林和二叉树的转换。
树或森林转换成其对应的二叉树的方法如下：
（1）在所有兄弟节点之间添加一条连线，如果是森林，则在其所有树的树根之间同。
样也添加一条线。
2）对于树、森林中的每个节点，除保留其到第一个孩子的连线外，撤销其到其他。
孩子的连线。
（3）将以上得到的树顺时针旋转45ˊ
参见（图7-20 图7-21）
二叉树到树、森林的转换。
（1）首先将二叉树逆时针45ˊ旋转。
2）若某节点是其双亲的左孩子，则把该节点的右孩子，右孩子的孩子…..都与该。
节点的双亲用线连起来。
3）最后去掉原二叉树中所有双亲到其右孩子的连线。
参见p16图7-22
六、 哈夫曼树：带权路径长度最小的二叉树也称最优树。
哈夫曼树的构造过程p163
哈弗曼编码p165例题7-2
重点题p168例题
第八章图。一、图的概念：由一个非空的顶点集合和一个描述顶点之间关系---边的集合组成。
n个顶点的无向完全图有n（n-1）／2条边。
n个顶点的有向完全图有n（n-1）条边。
二、图的存储结构。
1、邻接矩阵。
2、邻接表（p184图8-11）
三、图的遍历概念：从图中任一顶点出发对图中的所有顶点访问一次且只访问一次。
图的遍历的两种方式：深度优先搜索遍历（搜索规则p191、p193—图8-18）
广度优先搜索。
四、最小生成树（生成树里面不能有回路）
prim算法构造最小生成树p196—图-8-19
kruskal算法构造最小生成树图8-20
习题八。第九章查找
1.概念：在一组数据集合中找到满足某种条件的数据。
2.衡量查找算法效率的标准是平均查找长度。
3.顺序查找、二分法查找。
4.数表的动态查找：二叉排序树的查找(定义)
1）如果左子树不空，则左子树上所有节点的值均小于根节点的值。
2）如果右子树不空，则右子树上所有节点的值均大于根节点的值。
3）它的左右子树也分别为二叉排序树。
5.二叉排序树的插入和删除（p234、p237）
6.概念：平衡二叉树所具有的性质它的左子树和右子树都是平衡二叉树且左右字数的深度不超过一。
习题9第十章排序。
概念：将一组记录的任意序列按照规定顺序重新排列。
七种排序法：
1.直接插入排序（p274）
排序 （p275）
3.直接选择排序（p277）
4.堆排序 （p278-p279）
5.冒泡排序 （p238）
7.快速排序 （p284）
8.归并排序 （p286）
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...