数据结构复习资料(亲自整理)

一 简答题 1 链表 链表就是一串存储数据的链式结构 链式的优点在于 每个数据之间都是 相关联的 2 线性结构 线性结构是一个有序数据元素的集合 常用的线性结构有 线性表 栈 队列 双队列 数组 串 3 树与二叉树 二叉树是每个结点最多有两个子树的有序树 树是由 n n 1 个有限节点组成一个具有层次关系的集合 树和二叉树的 2 个主要差别 1 树中结点的最大度数没有限制 而二叉树结点的最大度数为 2 2 树的结点无左 右之分 而二叉树的结点有左 右之分 4 堆 堆通常是一个可以被看做一棵树的数组对象 堆总是满足下列性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树 5 二叉排序树 二叉排序数的 递归 定义 1 若左子树非空 则左子树所有节点的值均小于它 的根节点 2 若右子树非空 则右子树所有节点的值均大于于它的根节点 3 左右子树也分别为二叉排序树 二 应用题 1 树与二叉树 前中后序遍历序列 一 已知前序 中序遍历 求后序遍历 例 前序遍历 GDAFEMHZ 中序遍历 ADEFGHMZ 画树求法 第一步 根据前序遍历的特点 我们知道根结点为 G 第二步 观察中序遍历 ADEFGHMZ 其中 root 节点 G 左侧的 ADEF 必然 是 root 的左子树 G 右侧的 HMZ 必然是 root 的右子树 第三步 观察左子树 ADEF 左子树的中的根节点必然是大树的 root 的 leftchild 在前序遍历中 大树的 root 的 leftchild 位于 root 之后 所以左子树 的根节点为 D 第四步 同样的道理 root 的右子树节点 HMZ 中的根节点也可以通过前 序遍历求得 在前序遍历中 一定是先把 root 和 root 的所有左子树节点遍历 完之后才会遍历右子树 并且遍历的左子树的第一个节点就是左子树的根节 点 同理 遍历的右子树的第一个节点就是右子树的根节点 树与二叉树的转换 树转换为二叉树 树转换为二叉树 二叉树转换为树 二叉树转换为树 二叉树线索化 注意 图中的实线表示指针 虚线表示线索 结点 C 的左线索为空 表示 C 是中序序列的开始结点 无前趋 结点 E 的右线索为空 表示 E 是中序序列的终端结点 无后继 线索二叉树中 一个结点是叶结点的充要条件为 左 右标志均是 1 2 图 邻接表 一 邻接表 邻接表是图的一种链式存储结构 邻接表中 对图中每个顶点建立一个单链表 第 i 个单链表中的结点表示依附于顶 点 Vi的边 对有向图是以顶点 Vi为尾的弧 邻接表中的表结点和头结点结构 表 结 点 adjvexnextarcinfo 头结点 datafirstarc 二 无向图的邻接表 3 4 图 7 5 三 有向图的邻接表和逆邻接表 一 在有向图的邻接表中 第 i 个单链表链接的边都是顶点 i 发出的边 二 为了求第 i 个顶点的入度 需要遍历整个邻接表 因此可以建立逆邻接表 三 在有向图的逆邻接表中 第 i 个单链表链接的边都是进入顶点 i 的边 四 邻接表小结 设图中有 n 个顶点 e 条边 则用邻接表表示无向图时 需要 n 个顶点结点 2e 个表结点 用邻接表表示有向图时 若不考虑逆邻接表 只需 n 个顶点结点 e 个边结点 在无向图的邻接表中 顶点 vi的度恰为第 i 个链表中的结点数 在有向图中 第 i 个链表中的结点个数只是顶点 vi的出度 在逆邻接表中的第 i 个链表中的结点个数为 vi的入度 邻接矩阵 有向 无向 1 图的邻接矩阵表示法 图的邻接矩阵表示法 在图的邻接矩阵表示法中 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息 2 图的邻接矩阵 图的邻接矩阵 Adacency Matrix 设 G V E 是具有 n 个顶点的图 则 G 的邻接矩阵是具有如下性质的 n 阶方阵 例 下图中无向图 G 5 和有向图 G 6 的邻接矩阵分别为 A l 和 A 2 广度优先遍历 广度优先遍历是连通图的一种遍历策略 其基本思想如下 1 从图中某个顶点 V0 出发 并访问此顶点 2 从 V0 出发 访问 V0 的各个未曾访问的邻接点 W1 W2 Wk 然后 依次 从 W1 W2 Wk 出发访问各自未被访问的邻接点 3 重复步骤 2 直到全部顶点都被访问为止 例如下图中 1 从 0 开始 首先找到 0 的关联顶点 3 4 2 由 3 出发 找到 1 2 由 4 出发 找到 1 但是 1 已经遍历过 所以忽略 3 由 1 出发 没有关联顶点 由 2 出发 没有关联顶点 所以最后顺序是 0 3 4 1 2 深度优先遍历 深度优先遍历是连通图的一种遍历策略 其基本思想如下 设 x 是当前被访问顶点 在对 x 做过访问标记后 选择一条从 x 出发的未检测 过的边 x y 若发现顶点 y 已访问过 则重新选择另一条从 x 出发的未检测过的 边 否则沿边 x y 到达未曾访问过的 y 对 y 访问并将其标记为已访问过 然后 从 y 开始搜索 直到搜索完从 y 出发的所有路径 即访问完所有从 y 出发可达的 顶点之后 才回溯到顶点 x 并且再选择一条从 x 出发的未检测过的边 上述过程 直至从 x 出发的所有边都已检测过为止 例如下图中 1 从 0 开始 首先找到 0 的关联顶点 3 2 由 3 出发 找到 1 由 1 出发 没有关联的顶点 3 回到 3 从 3 出发 找到 2 由 2 出发 没有关联的顶点 4 回到 4 出 4 出发 找到 1 因为 1 已经被访问过了 所以不访问 所以最后顺序是 0 3 1 2 4 Prim 算法 基本思想 假设 G V E 是连通的 TE 是 G 上最小生成树中边的集合 算法从 U u0 u0 V TE 开始 重复执行下列操作 在所有 u U v V U 的边 u v E 中找一条权值最小的边 u0 v0 并入集合 TE 中 同 时 v0 并入 U 直到 V U 为止 此时 TE 中必有 n 1 条边 T V TE 为 G 的最小生成树 Prim 算法的核心 始终保持 TE 中的边集构成一棵生成树 注意 prim 算法适合稠密图 其时间复杂度为 O n 2 其时间复杂度与边得数目无关 而 kruskal 算法的时间复杂度为 O eloge 跟边的数目有关 适合稀疏图 Krusal 算法 图中先将每个顶点看作独立的子图 然后查找最小权值边 这条边是有限制条件的 边得两个顶点必须不在同一个图中 如上图 第一个图中找到最小权值边为 v1 v3 且 满足限制条件 继续查找到边 v4 v6 v2 v5 v3 v6 当查找到最后一条边时 仅仅只有 v2 v3 满足限制条件 其他的如 v3 v4 v1 v4 都在一个子图里面 不满足条件 至此已经找到最小生成树的所有边 拓扑排序 由某个集合上的一个偏序得到该集合上的一个全序 这个操作称之为拓扑排序 对上图进行拓扑排序的结果 2 8 0 3 7 1 5 6 9 4 11 10 12 5 检索 二叉排序建立 typedef struct node int data struct node lchild struct node rchild node void Init node t t NULL void InOrder node t 中序遍历输出 if t NULL InOrder t lchild printf d t data InOrder t rchild 二叉排序删除 btree DelNode btree p if p lchild btree r p lchild r 指向其左子树 btree prer p lchild prer 指向其左子树 while r rchild NULL 搜索左子树的最右边的叶子结点 r prer r r r rchild p data r data if prer r 若 r 不是 p 的左孩子 把 r 的左孩子作为 r 的父亲的 右孩子 prer rchild r lchild else p lchild r lchild 否则结点 p 的左子树指向 r 的左子树 free r return p else btree q p rchild q 指向其右子树 free p return q Huffman 树 编码与解码 例 给定有 18 个字符组成的文本 A A D A T A R A E F R T A A F T E R 求各字符的哈夫曼码 1 统计 2 构造 Huffman 树 3 在左分枝标 0 右分枝标 1 4 确定 Huffman 编码 5 译码 例 给定代码序列 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10 文本为 A A F A R A D E T 散列存储 6 内排序 希尔排序 void ShellPass SeqList R int d 希尔排序中的一趟排序 d 为当前增量 for i d 1 i n i 将 R d 1 n 分别插入各组当前的有序区 if R i key0i n i 依次插入 R 2 R n if R i key R i 1 key 若 R i key 大于等于有序区中所有的 keys 则 R i 应在原有位置上 R 0 R i j i 1 R 0 是哨兵 且是 R i 的副本 do 从右向左在有序区 R 1 i 1 中查找 R i 的插入位置 R j 1 R j 将关键字大于 R i key 的记录后移 j while R 0 key R j key 当 R i key R j key 时终止 R j 1 R 0 R i 插入到正确的位置上 endif InsertSort 选择排序 void SelectSort SeqList R int i j k for i 1 i n i 做第 i 趟排序 1 i n 1 k i for j i 1 j n j 在当前无序区 R i n 中选 key 最小的记录 R k if R j key R k key k j k 记下目前找到的最小关键字所在的位置 if k i 交换 R i 和 R k R 0 R i R i R k R k R 0 R 0 作暂存单元 endif endfor SeleetSort 交换排序 void BubbleSort SeqList R R l n 是待排序的文件 采用自下向上扫描 对 R 做冒泡排序 int i j Boolean exchange 交换标志 for i 1 i i j 对当前无序区 R i n 自下向上扫描 if R j 1 key R j key 交换记录 R 0 R j 1 R 0 不是哨兵 仅做暂存单元 R j 1 R j R j R 0 exchange TRUE 发生了交换 故将交换标志置为真 if exchange 本趟排序未发生交换 提前终止算法 return endfor 外循环 BubbleSort void QuickSort SeqList R int low int high 对 R low high 快速排序 int pivotpos 划分后的基准记录的位置 if low high 仅当区间长度大于 1 时才须排序 pivotpos Partition R low high 对 R low high 做划分 QuickSort R low pivotpos 1 对左区间递归排序 QuickSort R pivotpos 1 high 对右区间递归排序 QuickSort 归并排序 void Merge SeqList R int low int m int high 将两个有序的子文件 R low m 和 R m 1 high 归并成一个有序的 子文件 R low high int i low j m 1 p 0 置初始值 RecType R1 R1 是局部向量 若 p 定义为此类型指针速度更快 R1 ReeType malloc high low 1 sizeof RecType if R1 申请空间失败 Error Insufficient memory available while i m struct BiTNode lchild rchild BiTNode BiTree 先序建立二叉树 BiTree CreateBiTree char ch BiTree T scanf c if ch T NULL else T BiTree malloc sizeof BiTNode T data ch T lchild CreateBiTree T rchild CreateBiTree return T 返回根节点 先序遍历二叉树 void PreOrderTraverse BiTree T if T printf c T data PreOrderTraverse T lchild PreOrderTraverse T rchild 中序遍历 void InOrderTraverse BiTree T if T PreOrderTraverse T lchild printf c T data PreOrderTraverse T rchild 后序遍历 void PostOrderTraverse BiTree T if T PreOrderTraverse T lchild PreOrderTraverse T rchild printf c T data void main BiTree T T CreateBiTree 建立 PreOrderTraverse T 输出 getch 在二叉树中插入结点 x 找中序首点 顺着左支一直走 尾点 顺右 首先执行查找算法 找出被插结点的父亲结点 判断被插结点是其父亲结点的左 右儿子 将被插结点作为叶子结点插 入 若二叉树为空 则首先单独生成根结点 注意 新插入的结点总是叶子结点 一 typedef struct node int data struct node lchild struct node rchild node node Insert node t int key if t NULL node p p node malloc sizeof node p data key p lchild NULL p rchild NULL t p else if key data t lchild Insert t lchild key else t rchild Insert t rchild key return t important 二 typedef struct Node int data struct Node lc rc node Link void insert Link L int n if L NULL L new node 若找到插入位置 则新申请节点 L lc L rc NULL L data n else if n L data 若 n 与当前节点的值相等 则不需插入了 return else if n data 若 n 比当前节点的值小 则往当前节点 的左子树插 insert else 若 n 比当前节点的值大 则往当前节点的右子树插 insert 中序遍历 typedef struct BiTNode 结点结构 int data struct BiTNode lchild rchild BiTNode BiTree void Inorder BiTree T 中序遍历二叉树 if T Inorder T lchild 遍历左子树 printf d T data 访问结点 Inorder T rchild 遍历右子树 当调用该子函数时 加入传的就是根节点 他将不断的递归一直到最左 的一个叶子节点 就是不断重复 T 位最左叶子节点是那么第一句再递归式就失败了 所有退回上一层输出 紧接着就执行 开始递归 以此类推在递归第三句时候也是严格按着 1 2 3 这个顺序执行 求一度结点 叶子结点 int count 0 void preOrder TTree tree if tree NULL count 先根访问 且计数 这里显示 tree 的数据 if tree Left NULL preOrder tree Left if tree Right NULL preOrder tree Right main count 0 preOrder tree 显示 count 2 检索 二分法搜索 递归与非递归 必背 递归 void Search int p int low in