1.线性表[ 矩阵|数组|字符串|堆栈|队列 ]
1).概念 除首尾元素外,每个元素都有唯一一个直接前驱和唯一直接后继2).特点 同一性,有穷性,有序性3).存储方式 a.顺序存储(连续空间) b.链式存储 a).单链表(数据域+指针域) b).循环链表(首尾相接的链表) c).双向链表(前驱指针域+数据域+后驱指针域) d).静态链表(顺序存储数组模拟链表,设置游标模拟指针)4).栈|队列|串|数组 a.栈(限定性线性表) a).后进先出 b).栈顶入栈,出栈 c).顺序栈|链栈 b.队列(限定性线性表) a).先进先出 b).队尾入,队首出 c).链队列|循环队列 c.串(特定的线性表) a).定长顺序串|块链串 d.数组(线性表的扩充) a).三角矩阵| 带状矩阵 | 稀疏矩阵(三元组表示&十字链表) e.广义表(线性表的扩充) a).头尾链表(表结点(标志域+表头指针+表尾指针),元素结点(标志域+值域)) b).扩展线性链表(表结点(标志域+表头指针+表尾指针),原子结点(标志域+值域+表尾指针))2.树
1).表示法 a.倒置树结构 b.文氏图 c.广义表[嵌套括号](A(B(C,D)),E(F),G) d.陷入式2).二叉树 a.概念 每个结点的度都不大于2 & 每个结点的孩子结点次序不能任意颠倒 b.存储结构 a).顺序存储 | 链式存储([二叉链表]左孩子域+数据域+右孩子域) c.遍历顺序 a).先序(根左右) | 中序(左根右) | 后序(左右根)3).线索二叉树 a.结构(左孩子域+前驱结点指针+数据域+后继结点指针+右孩子域)4).哈夫曼树 a.概念 带权路径长度最短的二叉树 b.哈夫曼编码(左分支0右分支1)3.图
1).网状数据结构2).存储方法 a.邻接矩阵(数组) b.邻接表(稀疏图) a).表头结构(数据域+链域) b).弧结点结构(邻接点域+数据域+链域) c.邻接多重表 a).顶点结构(data+firstedge) b).边结点结构(mark+ivex+ilink+jvex+jlink+info) d.十字链表 a).顶点结构(data+firstin+firstout) b).弧结点结构(tailvex+headvex+hlink+tlink+info)3).遍历 a.深度优先 b.广度优先4.查找
1).比较式查找 a.基于线性表查找 a).顺序查找 b).折半查找(二分查找) (顺序存储&有序) c).分块查找(块内无序&块块有序&关键字有序) b.基于树查找 a).二叉排序树 若左子树非空左子树小于根&若右子树非空右子树大于根&左右子树分别为二叉排序树 b).平衡二叉排序树 左右子树深度之差的绝对值小于等一 c).B_树(平衡的m路查找树)2).计算式查找(哈希查找)5.排序
1).内排序(内存中排序) a.插入排序 a).直接插入排序 新元素与已排序好的数据进行比较,关键字大于新元素向后移位 b).折半插入排序 有序表进行折半查找 c).希尔排序 拆分子序列进行插入排序 b.交换排序 a).冒泡排序 b).快速排序 选取首个记录(k)作为枢轴,小于k移到枢轴前边 c.选择排序 a).简单选择排序 最小值的与首个比较,剩余最小值与第二个比较... b).树形选择排序 c).堆排序 d.归并排序 e.分配排序 a).链式基数排序(低位优先)2).外排序(内存无法容纳,需要借助外部存储设备)
a.归并排序 a).文件分批次输入到内存中进行排序，再将排序好的归并段写回外存 b).使用归并方法进行多边归并b.磁盘排序 a).减少数据扫描遍数 b).增大批次读取数据量 内容出自<<数据结构>>仅供学习/复习参考