应考复习：数据结构与算法总结点

《应考复习：数据结构与算法总结点》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构分类：逻辑结构，存储结构分类按逻辑结构分类逻辑结构可以用二元组B=表示，其中k是节点的有穷集合，R是K上的一个关系。K上的二元组是K中元素的有序对，记为(k,k'属于K)。K上的一个关系就是K上的一些二元组组成的集合，K上不同的二元组集合构成不同的关系。前驱，后继，开始结点没有前驱的结点，终端结点没有后继的结点根据R可以将数据结构分为三类：线性结构只有一个前驱，一个后继，树形结构只有一个前驱，成二叉树等，复杂结构无限制，如有向图，无向图，网络图按存储结构分类主要包括结点表示和关系的表示存储的四种表示方法：顺序表示，链接表示，散列表示，索引表

2、示。结点与结构结点(把组成结构的那些元素成一个结点)结点是数据结构的基本单位分两大类：初等类型和组合类型外存数据的组织文件的分类：顺序文件，散列文件，索引文件，倒排文件文件的处理：检索，插入，删除，修改，排序第二章线性表存储方式：顺序存储，链式存储顺序表：通常把顺序表中k0的存储位置loc(k0)称为线性表的首地址或许基地址，则下标为i的元素k[i]的存储位置为loc(k[i])=loc(k0)+i*c其中c为每个元素占用c个存储单元一般情况下，在顺序表中插入一个元素时，需将下标为palist->n-1至下标为p的元素依次向后移动一个位置，移动时要注意从下标大的元素开始

3、?链接表示单链表表示每个结点包括2个域：数据域(info)，指针域(link)空指针，图示用^表示，算法中用NULL表示P41创建空链表单链表的扩充：循环链表，双链表，循环双链表代码常用函数malloc()：得到一个结点空间，并返回新结点的起始位置矩阵稀疏矩阵存储方法：三元组表示法，伪地址表示法，带辅助向量的二元组表示法，行-列表示法广义表深度：广义表中所含括号的层数如果广义表中的元素全部都是原子(如L=(a,b)),这种广义表就是线性表纯表：如果广义表中的元素允许有子广义表，但各层子广义表均无共享再入表：~~允许共享递归表：(范围最广)表示方法：单链表示法atom值为

4、0代表本结点为子广义表值为1代表本结点为原子info表示atom等于0时存放广义表中第一个元素所对应结点的地址atom=1时存放本原子的信息link存放与本元素同层的下一个元素所对应结点的地址当本元素是所在层的最后一个元素时，link=NULL带头结点的单链表示法结点的动态分配与回收动态分配：最佳适配，首先适配找到第一个符合条件就用，最大适配每次都是取最大的，参考p63-图2.25栈栈的特点栈顶，栈底，空栈上溢N>maxnum进栈运算，下溢，为避免溢出，需检测是否已满或者空空栈进行出栈运算队列queue队列特点队头，队尾，空队循环队列?二叉树结点的层数，度数，二叉树的高

5、度二叉树中结点的最大层数完全二叉树p119完全二叉树的性质：具有n个结点的完全二叉树的高度k为[log2n]如果i=0~如果i>0父结点的下标为[(i-1)/2]二叉树的周游先根次序根左右后根次序左右根对称(中根)次序哈夫曼树(最优二叉树)WPL为了使WPL最小，权值越大的近根，权值越小的远根散列法杂凑法关键码-地址转换法及其碰撞不等的关键码k1,k2用散列函数却得到相同的散列地址散列地址(hashadress)散列函数：数字分析，折叠，中平方。。负载因子碰撞处理开地址法，拉链法平衡二叉排序树的构造二叉树的应用堆小根堆结点最小，大根堆，左右排是怎么样的优先队列：遵循最小

6、元素先出的原则广度优先周游：先访问层数为0的结点，然后从左到右逐个访问层数为1的结点树林与二叉树的转换相互唯一对应二叉排序树的插入1若为空则新结点作为根结点2非空，新结点的关键码与根节点的关键码比较，相等则已经存在，小于则插入到根节点的左子树，大于则右子树3一直插插入排序直接插入排序正序：时间复杂度O(n)反序：O(n^2)平均时间复杂度：O(n^2)稳定的简单选择排序设所排序序列的记录个数为ｎ。i取1,2,…,n-1,从所有n-i+1个记录（R,R【i+1】,…,R【n】中找出排序码最小的记录，与第ｉ个记录交换。执行n-1趟后就完成了记录序列的排序。二分法插入排序注意

7、剩余两个数时就可判定次数表长是偶数时，取N/2平均时间复杂度：O(n^2)稳定的直接选择排序选出排序码最小的记录与第一个记录交换，以此类推时间复杂度：O(n^2)：它采用顺序存储方式，不稳定堆排序平均时间复杂度：O(nlog2n)快速排序最坏时间复杂度：n^2最好:nlog2n其实思想是蛮简单的，就第一步：首先我们从数组的left位置取出该数（20）作为基准（base）参照物。第二步：从数组的right位置向前找，一直找到比（base）小的数，:不稳定归并排序：二路归并排序时间复杂度：nlog2n稳是通过第一遍的遍历（让left和righ