数据结构笔记.docx

第一章第二章第三章队列1、循环队列的判断队满的条件:(rear+1)%maxsize==front,判断对空的条件:rear==front第四章第五章数组和广义表1、压缩存储稀疏矩阵的三元组存储方法2、第六章树(存在一对多的关系)1、数的存储结构分为:双亲表示法、孩子表示法、孩子兄弟表示法(二叉链表表示法)2、树的链式存储结构,空指针域的个数为n(k-1)+1,其中n为节点数,k为度3、深度为k完全二叉树结点数为2的k次方-1,n个结点的满二叉树深度为log2n+1取下限4、中序遍历、前序遍历、后续遍历5、给定一组权重值,构造哈夫曼树,哈夫曼树的高度不是唯一的,唯一的是权重之和6、最小生成树(普里姆算法时间复杂度O(n2),克鲁斯卡尔算法时间复杂度O(eloge)e为网边数7、第七章图(存在多对多的关系)1、广度优先遍历、深度优先遍历2、图的存储结构:数组表示法、领接表、领接多重表、十字链表第八章动态存储管理第九章查找1、查找分为:静态查找、动态查找2、顺序表的查找:(1)顺序查找(假设每个记录的查找概率相等,当一定能查找成功时,平均查找长度为(n+1)/2;当加入查找不成功的因素后,平均查找长度为3(n+1)/4。(2)折半查找的平均查找长度为log2(n+1)-1(3)用顺序查找确定所在块,则分块查找的平均查找长度为(n/s+s)/2+1;用折半查找确定所在块,则分块查找的平均查找长度为log2(n/s+1)+s/2,其中n为总长度,s为每一分块儿的长度。(4)二叉排序树,查找长度最差情况(n+1)/2,最好情况与log2n成正比,平均为o(lg10)(5)平衡二叉树,平均查找长度为o(lg10)(6)哈希函数的构造方法:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法;处理冲突的方法:开放地址法、再哈希法、链地址法、建立一个公共溢出区。查找不成功的平均查找长度1/(1-a),查找成功的平均查找长度-1/a*ln(1-a)第十章内部排序1、直接插入排序、折半插入排序时间复杂度为O(n2)2、冒泡排序时间复杂度为O(n2)3、快速排序时间复杂度O(nlnn)、最坏情况O(n2)4、树形选择排序时间复杂度O(nlnn)5、堆排序(最坏情况下/平均)时间复杂度O(nlnn)6、归并排序(最坏情况下/平均)时间复杂度O(nlnn)7、排序分析:(1)从平均时间性能而言,快速排序最佳,其所需时间最省,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是,在n较大时,归并排序所需时间较堆排序省,但它所需的辅助存储量最多。      (2)上表中的“简单排序”包括除希尔排序之外的所有插入排序,起泡排序和简单选择排序,其中以直接插入排序为最简单,当序列中的记录“基本有序”或n值较小时,它是最佳的排序方法,因此常将它和其它的排序方法,诸如