数据结构第四次作业.docx

简介：
本作业为《数据结构》课程第四次作业，涵盖了链表、栈和队列等基本数据结构的应用与实现，包括多项编程任务及算法设计。 一、二叉树（二） 1. 写算法 (1) 定义：二叉树的直径是从根结点至叶子的最大路径长度。编写一个算法来求解给定的二叉树（以二叉链表形式存储）的直径。 (2) 已知一个由根节点指针bt表示的二叉树，以及两个节点p和q，设计并实现一个算法找出这两个结点之间的最近公共祖先，并返回该祖先结点地址。 (3) 基于给定的二叉树（以二叉链表形式存储），利用叶子结点的rchild指针域将所有叶子连接成单向链表。要求输出的是最左边第一个叶子节点地址作为单向链表头结点指针。 2. 编程题 (1) 从键盘输入一个不含重复字符的字符串，将其视为完全二叉树顺序存储结构中的元素，并建立对应的二叉链表形式的完全二叉树。输出该树的先序、中序和后序遍历结果。 (2) 使用先序遍历方法构建一棵以char类型为数据域的二叉树（用字符#表示NULL），实现其中序线索化，然后使用非递归算法输出中序遍历的结果正向序列及其逆向序列。 二、图 1. 根据给定无向图绘制其多重邻接表存储结构，并根据该存储结构写出从顶点v0出发的深度优先和广度优先搜索时结点访问顺序。 2. 编写一个算法来判断无向图中是否存在环。使用深度优先遍历方法，当在某个节点处发现回边（已访问过的邻接点）且其不是当前递归调用的直接前驱顶点，则判定存在环路。 3. 编程题：构建给定无向图的邻接表存储结构，并输出该图深度和广度优先搜索时结点被访问到次序。 4. 编写程序以创建AOE网络（Activity On Edge Network）的数据结构，计算并显示每个事件的时间最早发生时间ve[]以及最晚允许开始时间vl[]值。 5. 选做题：设计算法输出所有关键路径。给定的是一个已建立邻接表存储的AOE网络G，并且已经知道了各个节点的ve和vl值。要求以源点至汇点顶点序列的形式表示每一条关键路径，确保该序列是拓扑有序的。