数据结构复习笔记

数据结构复习笔记一、绪论1.数据：能被计算机表示、存储和加工处理的一切信息（数值型和非数值型）2.数据的基本单位：数据元素3.组成数据元素的不可分割的最小单位：数据项4.数据对象：性质相同的数据元素的集合5.数据类型：指定一种数据对象的类型6.数据的逻辑结构：指数据之间的逻辑关系,即指数据元素之间的关联方式或邻接关系7.数据的存储结构：指数据在计算机中存储的位置8.运算的集合：定义在逻辑结构上的一组操作9.数据结构:按照某种逻辑关系组织起来的一批数据,按一定的存储方法把它存储在计算机中,并在这些数据上定义了一个运算的集合10.逻辑结构分类：线性结构、集合、树形结构、图型或网状结构11.线性结构：仅一个开始结点、仅一个终端结点；其它都是内部结点，且都有且仅有一个前驱和一个后驱（一对一）12.集合：结构中数据元素只具有“同属于一个集合”的关系13.树型结构的特点：有且仅有一个根结点，其它结点有且仅有一个前驱结点，对于非根结点都存在从根到该结点的一条路径（一对多）14.图型结构的特点：结构中的数据元素存在多对多的关系15.存储结构：顺序存储结构、链式存储结构16.顺序存储结构特点：逻辑结构上相邻的两个元素在物理结构上也相邻.即前驱的结束是后继的开始17.链式存储结构：存储空间不连续，但保持了逻辑关系18.算法的五个特征：有穷性、确定性、可行性、输入、输出19.算法与程序的区别：程序不一定满足有穷性；程序是机器可执行的语言编写的20.算法评价：正确、简单、可读、健壮、高效21.算法分析方法：事后统计和事前分析、时间复杂度和空间复杂度22.影响算法时间代价的因素：输入规模、算法效率、输入顺序、机器、设计者23.Ο(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜…＜O(2n)＜O(n!)二、线性表1.线性结构特点：唯一第一数据元素、唯一最后数据元素、其他数据元素仅有一个前趋和仅有一个后驱2.顺序表的优点：无需为表示数据元素之间的逻辑关系而增加额外存储空间；可方便地随机存取表中任一元素3.顺序表的缺点：预先为数据元素分配空间；插入和删除时必须移动大量元素4.单链表的插入：newnode→next=p→next；p→next=newnode5.单链表的删除：p→next=q→next；deleteq6.双向链表的删除：current-prior-next=current-next；current-next-prior=current-prior；deletecurrent7.双向链表的插入：p-prior=current；p-next=current-next；current-next-prior=p；current-next=p8.顺序表与链表：顺序表结点总数大概确定，表中结点数目稳定（插删操作少）；链表结点数目不预知且动态变化三、栈和队列1.栈的逻辑结构：允许插入和删除的一端称为栈顶，另一端称为栈底，特点是后进先出或先进后出2.先进后出题：若abc顺序入栈，a入栈后可以直接出栈3.队列的逻辑结构：在一端进行插入操作（队尾），而另一端进行删除操作的线性表（队头），特点是先进先出4.队满判定条件：(rear+1)%QueueSize==front5.队空判定条件：rear==front6递归算法设计方法：最小规模子问题、划分子问题并求解、子问题解的合成四、字符串和多维数组五、树和二叉树1.结点的度：结点所拥有的子树的个数2.树的度：树中各结点度的最大值3.前序遍历：根左右4.中序遍历：左根右5.后序遍历：左右根6.层序遍历：按层从左到右遍历7.满二叉树：叶结点只出现在最下一层，只有度为0和度为2的结点8.完全二叉树：在满二叉树中，从最后一个结点开始，连续去除任意个结点9.对于一棵具有n个结点的树,该树中所有结点度数之和为n-110.二叉树性质1：二叉树的第i层上最多有2i-1个结点（i≥1）11.二叉树性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点12.二叉树性质3：在一棵二叉树中，如果叶结点数为n0，度为2的结点数为n2，则有:n0＝n2＋113.完全二叉树性质1：具有n个结点的完全二叉树的深度为k=log2(n+1)取大整或k=log2n（取小整）+1(n0)14.完全二叉树性质2：序号i的结点，双亲结点的序号为i/2，左孩子的序号为2i，右孩子的序号为2i+115.已知前序序列ABCDEFGHI和中序序列BCAEDGHFI画出二叉树16.二叉树前序遍历递归算法voidBiTreeDataType::PreOrder(BiNodeDataType*bt){if(bt==NULL)return;//递归调用的结束条件else{coutbt-data;//访问根结点bt的数据域PreOrder(bt-lchild);//前序递归遍历bt的左子树PreOrder(bt-rchild);//前序递归遍历bt的右子树}}17.二叉树中序遍历递归算法voidBiTreeDataType::InOrder(BiNodeDataType*bt){if(bt==NULL)return;//递归调用的结束条件else{InOrder(bt-lchild);//中序递归遍历bt的左子树coutbt-data;//访问根结点bt的数据域InOrder(bt-rchild);//中序递归遍历bt的右子树}}18.二叉树后序遍历递归算法voidBiTreeDataType::PostOrder(BiNodeDataType*bt){if(bt==NULL)return;//递归调用的结束条件else{PostOrder(bt-lchild);//后序递归遍历bt的左子树PostOrder(bt-rchild);//后序递归遍历bt的右子树coutbt-data;//访问根结点bt的数据域}}19.二叉树层次遍历算法1.队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；voidBinaryTreeType::LevelOrder(){SeqQueuequ;BinTreeNode*p=root;qu.Enter(p);while(!qu.IsEmpty()){p=qu.Leave();coutp-data;if(p-leftChild)qu.Enter(p-leftChild);if(p-rightChild)qu.Leave(p-rightChild);}20.二叉树中序线索化：将二叉链表中的空指针改为指向前驱或后继的线索P11121.树转换二叉树：相邻兄弟加线、保留与第一子间连线删去其它子结点间连线、根结点为轴心顺时针转动P16222.树的前序遍历等价于二叉树的前序遍历23.树的后序遍历等价于二叉树的中序遍历24.森林转换二叉树：先将每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子P16925.二叉树转换为树或森林：P17226.哈夫曼树：给定一组具有确定权值的叶结点，带权路径长度最小的二叉树,也称最优二叉树27.构造哈夫曼数：初始化、选取与合并、删除与加入、重复2和328.n个叶结点构造出的哈夫曼树中总的结点数为2n-129.一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3}，设计最经济的编码方案30.字符集{a,b,c,d,e,f,g,h}出现概率分别是{0.14,0.08,0.11,0.23,0.29,0.05,0.03,0.07}六、图1.网图的邻接表P712.图的遍历：深度优先遍历和广度优先遍历3.最小生成树——Prim算法：每次选择解集合结点连接到待选集合结点最小边，将所连待选结点加入到解集合中，直到待选集合为空4.最小生成树——Kruscal算法：每次都选最小权边（不构成回路），直到选择n-1条边为止5.最短路径——Dijkstra算法：带方向的Prim算法6.关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径七、查找1.二叉树的插入与删除2.平衡二叉查找数：LR型调整、LL型调整、RR型调整、RL型调整3.散列表的建立：散列函数H(key)=keymodA4.散列表冲突解决方法：线性探测法、二次探测法、随机探测法、拉链法5.散列表平均查找长度八、排序1.排序的分类：内排序（待排元素在内存中）、外排序（待排序元素部分在内存中，需与外存多次交换）2.起泡排序法：每次找最小值的放到待排队首3.选择排序法：每次找最小值与待排队首交换4.最小堆：完全二叉树，每个结点的值都小于或等于其左右孩子结点的值5.最大堆：完全二叉树，每个结点的值都大于或等于其左右孩子结点的值6.将无序序列建成一个堆voidsift(intr[],intk,intm){//要筛选结点的编号为k，堆中最后一个结点的编号为mi=k;j=2*i;while(j=m){if(jm&&r[j]r[j+1])j++;//左右孩子中取较大者if(r[i]r[j])break;else{r[i]=r[j];i=j;j=2*i;}}}voidrSort(intr[],intn){for(i=n/2;i=1;i--)//初建最大堆sift(r,i,n);for(i=1;in;i++){-i+1];//移走堆顶sift(r,1,n-i);//重建堆}}7.归并排序：初始排序码[52][33][65][80][73][23][29]第一趟归并[3352][6580][2373][29]第二趟归并[33526580][232973]第三趟归并[23293352657380]8.稳定排序：简单插入排序、起泡排序和归并排序9.不稳定排序：希尔排序、简单选择排序、快速排序和堆排序10.各种排序方法的比较排序方法平均情况最好情况最坏情况直接插入排序O(n2)O(n)O(n2)希尔排序O(nlog2n)~O(n2)O(n1.3)O(n2)起泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)简单选择排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)归并排序O(nlog2n)O(nlog2n)O(nlog2n)基数排序O(d(n+m))O(d(n+m))O(d(n+m))