2018-05-19算法与数据结构
2018-05-21 本文已影响0人
ROC_XU的日记本
知识体系
数组
计算存储地址:1.按行还是按列存储;2.每个元素所占的字节
例题:已知5行5列的二维数组a中的各个元素各占两个字节,求元素a[2][3]按行存储的地址。
解析:a+13*2
矩阵(稀疏矩阵:一个矩阵中大量的元素都为0)
计算某一元素的一维数组对应下标(采用代入法)
数据结构(提高运行效率)
顺序存储:
链式存储:
队列与栈
队:先进先出
栈:先进后出
队空:head=tail
队满:(tail+1)%size=head
广义表
基本运算:取表头head(Ls)和取表尾tail(Ls)。若有LS1=(a,(b,c),(d,e))
1.求长度和深度
解析:长度为3,深度为2。
2.求取出b的操作
解析:head(head(tail(LS1)))
树与二叉树
图示二叉树的第i层上最多有2*(i-1)次方个算其他的可以类比;
二叉树遍历
四种遍历的方式,每一次都按照相同的标准(比如采用前序,访问根后在访问左的时候,又遵循根左右,又是2、4、5,其他类同);
反向构造二叉树
一般是给两个序列,在反构,结合两个图分析。
树转二叉树:1.保留第一个子节点连线,去除其他的子节点连线,2.连接兄弟节点,每层重复。
实例ddd