数据结构复习笔记.doc

《数据结构复习笔记.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习笔记一、绪论1.数据：能被计算机表示、存储和加工处理的一切信息（数值型和非数值型）2.数据的基本单位：数据元素3.组成数据元素的不可分割的最小单位：数据项4.数据对象：性质相同的数据元素的集合5.数据类型：指定一种数据对象的类型6.数据的逻辑结构：指数据之间的逻辑关系,即指数据元素之间的关联方式或邻接关系7.数据的存储结构：指数据在计算机中存储的位置8.运算的集合：定义在逻辑结构上的一组操作9.数据结构:按照某种逻辑关系组织起来的一批数据,按一定的存储方法把它存储在计算机中,并在这些数据上定义了一个运算

2、的集合10.逻辑结构分类：线性结构、集合、树形结构、图型或网状结构11.线性结构：仅一个开始结点、仅一个终端结点；其它都是内部结点，且都有且仅有一个前驱和一个后驱（一对一）12.集合：结构中数据元素只具有“同属于一个集合”的关系13.树型结构的特点：有且仅有一个根结点，其它结点有且仅有一个前驱结点，对于非根结点都存在从根到该结点的一条路径（一对多）14.图型结构的特点：结构中的数据元素存在多对多的关系15.存储结构：顺序存储结构、链式存储结构16.顺序存储结构特点：逻辑结构上相邻的两个元素在物理结构上也相邻.即前驱

3、的结束是后继的开始17.链式存储结构：存储空间不连续，但保持了逻辑关系18.算法的五个特征：有穷性、确定性、可行性、输入、输出19.算法与程序的区别：程序不一定满足有穷性；程序是机器可执行的语言编写的20.算法评价：正确、简单、可读、健壮、高效21.算法分析方法：事后统计和事前分析、时间复杂度和空间复杂度22.影响算法时间代价的因素：输入规模、算法效率、输入顺序、机器、设计者23.Ο(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜…＜O(2n)＜O(n!)二、线性表1.线性结构特点：

4、唯一第一数据元素、唯一最后数据元素、其他数据元素仅有一个前趋和仅有一个后驱2.顺序表的优点：无需为表示数据元素之间的逻辑关系而增加额外存储空间；可方便地随机存取表中任一元素3.顺序表的缺点：预先为数据元素分配空间；插入和删除时必须移动大量元素4.单链表的插入：newnode→next=p→next；p→next=newnode5.单链表的删除：p→next=q→next；deleteq6.双向链表的删除：current->prior->next=current->next；current->next->prior=

5、current->prior；deletecurrent7.双向链表的插入：p->prior=current；p->next=current->next；current->next->prior=p；current->next=p8.顺序表与链表：顺序表结点总数大概确定，表中结点数目稳定（插删操作少）；链表结点数目不预知且动态变化三、栈和队列1.栈的逻辑结构：允许插入和删除的一端称为栈顶，另一端称为栈底，特点是后进先出或先进后出2.先进后出题：若abc顺序入栈，a入栈后可以直接出栈3.队列的逻辑结构：在一端进行插入

6、操作（队尾），而另一端进行删除操作的线性表（队头），特点是先进先出4.队满判定条件：(rear+1)%QueueSize==front5.队空判定条件：rear==front6递归算法设计方法：最小规模子问题、划分子问题并求解、子问题解的合成四、字符串和多维数组五、树和二叉树1.结点的度：结点所拥有的子树的个数2.树的度：树中各结点度的最大值3.前序遍历：根左右4.中序遍历：左根右5.后序遍历：左右根6.层序遍历：按层从左到右遍历7.满二叉树：叶结点只出现在最下一层，只有度为0和度为2的结点8.完全二叉树：在满二叉

7、树中，从最后一个结点开始，连续去除任意个结点9.对于一棵具有n个结点的树,该树中所有结点度数之和为n-110.二叉树性质1：二叉树的第i层上最多有2i-1个结点（i≥1）1.二叉树性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点2.二叉树性质3：在一棵二叉树中，如果叶结点数为n0，度为2的结点数为n2，则有:n0＝n2＋13.完全二叉树性质1：具有n个结点的完全二叉树的深度为k=log2(n+1)取大整或k=log2n（取小整）+1(n>0)4.完全二叉树性质2：序号i的结点，双亲结点的序号为i

8、/2，左孩子的序号为2i，右孩子的序号为2i+15.已知前序序列ABCDEFGHI和中序序列BCAEDGHFI画出二叉树6.二叉树前序遍历递归算法voidBiTree::PreOrder(BiNode*bt){if(bt==NULL)return;//递归调用的结束条件else{cout<data;//访问根