数组

（2*5+3）*2=26

a+26

 

稀疏矩阵

 

稀疏矩阵：一个矩阵中大量的元素为零

A

 

数据结构定义

 

 

 

 

 

 

 

线性表

 

 

 

 

 

 

 

 

 

 

线性表-顺序存储与链式存储对比

 

 

 

 

 

 

 

 

 

 

线性表-队列与栈

不考虑入栈就出栈：

c-》b-》a

考虑入栈就出栈

a-》b-》c

a-》c-》b

b-》a-》c

b-》c-》a

 

 

D

 

 

广义表

表头：最外层的第一个表元素

表尾：除第一个元素外的其他所有元素

 

1. 长度3，深度2
2. b=head(head(tail(LS1)))

 

 

树与二叉树

结点的度：一个结点拥有的孩子结点数

树的度：所有结点中度数最高的结点的度       2

叶子结点：无孩子结点       7

分支结点：有分支的结点           2，3，6

内部结点：不是叶子结点和根结点的结点       2，3，6

父结点：相对而言

子结点：相对而言

兄弟结点：同一父亲下的同级结点

层次：级别

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

树与二叉树-二叉树遍历

前序遍历：中左右       12457836

中序遍历：左中右       42785 6

后序遍历：左右中       48752631

层次遍历：一层层，从左向右    12345678

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

树与二叉树-反向构造二叉树

 

 

 

树与二叉树-树转二叉树

 

树与二叉树-查找二叉树

 

 

 

 

 

 

 

 

树与二叉树-最优二叉树（哈夫曼树）

树的路径长度：结点的连线的数量

权：叶子结点代表的字符出现的频度

带权路径长度：路径长度乘以权值           （2叶子）带权路径长度：2*2=4

树的带权路径长度（树的代价）：叶子结点的带权路径长度的和

 

哈夫曼树：树的代价最小

 

构造哈夫曼树：

1. 先构建最小的树，选最小的两个值
2. 选择未使用的最小值继续构建

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

树与二叉树-线索二叉树

 

二叉树的叶子存在大量的空指针，所以构建线索二叉树

 

前序线索二叉树：ABDEHCFGI

 

树与二叉树-平衡二叉树

 

平衡度：左结点的深度减去右结点的深度

 

 

图

 

 

图的存储-邻接矩阵

 

 

 

 

图的存储-邻接表

图的遍历-

 

 

 

 

 

图-拓扑排序

 

 

 

 

 

 

 

 

 

 

 

 

图的最小生成树-普里姆算法

 

树与图的区别：树没有环路

 

由根点选出最小的路径，注意不能形成环

AàB

AàE

AàF

FàD

DàC

 

图的最小生成树-克鲁斯卡尔算法

选出最小的5条边：注意不能形成环

AàB

AàE

AàF

FàD

DàC

 

算法基础-算法的特性

算法的复杂度

查找-顺序查找

 

 

二分查找

 

 

 

 

查找-散列表

存在重复的问题：解决思路：扩大空间或提高算法复杂度，减小重复度

 

排序

稳定排序：排序前后相等值的相对前后不变

内排序：内存中排序

外排序：外部存储空间排序

 

效率：直接插入排序《《希尔排序

         冒泡排序《《快速排序

         简单排序《《堆排序

排序-直接插入排序

 

排序-希尔排序

数据量少的时候选择直接插入排序，数据量大的时候，选择希尔排序

 

 

 

 

排序-直接选择排序

 

排序-堆排序

小顶堆：所有孩子结点都大于根节点

大顶堆：所有孩子结点都小于根节点

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

排序-冒泡排序

 

 

 

 

 

 

 

 

排序-快速排序

 

 

排序-归并排序

 

 

 

 

 

排序-基数排序

 

 

排序-总结