[简答题] 数据结构

Source

前言

没想到吧离考试还有一小时我还能在这写
哈哈哈哈

三元组存储稀疏矩阵

行列下标和非零元值

在这里插入图片描述

快速转置法的三个数组

列
当前列有几个非零元
然后copt可以按照公式计算
在这里插入图片描述

矩阵的十字链表

对于每个元素[行][列][值] 和指向下和右的下标

在这里插入图片描述

完全二叉树顺序存储

先给元素标号

然后左孩子等于 2i 右孩子等于2i+1
在这里插入图片描述

二叉链表

lchild || data || rchild
在这里插入图片描述

三叉链表

在这里插入图片描述

根据中序 & (先序||后序)建树

先去先序或者后序找根然后找左右
在这里插入图片描述

先序遍历建树

根左右
在这里插入图片描述

线索二叉树

前驱 | 左孩子(0 表示有) | data | 右孩子 | 后继

在这里插入图片描述

二叉树和树的转换

树转换成二叉树

树转换成二叉树反过来即可

左孩子代表是孩子结点
右孩子代表是兄弟结点
在这里插入图片描述

森林转换成二叉树
先将森林转换成二叉树
森林转换成二叉树反过来即可

然后以第一个二叉树为根节点直接拼接上即可
在这里插入图片描述

Huffman树wpl计算和构建

WPL = 当前结点的值 * 到根节点的距离
在这里插入图片描述

构建huffman树两个两个的拿即可

在这里插入图片描述

求关键路径

ve 从头开始写最早开始时间
vl 从尾巴开始写最晚开始时间

在这里插入图片描述

折半查找转二叉树

在这里插入图片描述

二叉排序树的构建

直接把比他大的右边比他小的丢左边

二叉排序树的删除

如果当前结点没有子节点直接删除即可

如果当前结点有一个子节点直接把这个子节点题前

如果当前这个结点有两个子节点需要将他中序遍历的前驱提前即可

在这里插入图片描述

平衡二叉树

左旋右旋(太难了忙拆不考)

在这里插入图片描述

希尔排序

按d分组
在这里插入图片描述

快速排序

关键字比他小的swap到左边比他大的swap到右边

在这里插入图片描述

归并排序(二路归并)

分成两个一组的然后再合并组直到最后
在这里插入图片描述

基数排序(盲猜不考)

先按各位分组
然后在按十位分组即可

在这里插入图片描述