3-1-data-structures

Data Structures

北邮计算机类本科二年级数据结构课程作业。

⚠️不能保证正确性，请不要作为作业提交。

Lab1 加里森的任务

有 n 个加里森敢死队的队员要炸掉敌人的一个军火库，

谁都不想去，队长加里森决定用轮回数数的办法来决定哪个战士去执行任务。规则如下：如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个编号为 x 的战士开始计数，当数到 y 时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第 y 时，此战士接着去执行任务。以此类推，直到任务完成为止。

加里森本人是不愿意去的，假设加里森为 1 号，请你设计一程序为加里森支招，求出 n,x,y 满足何种条件时，加里森能留到最后而不用去执行任务。

要求：

• 主要数据结构采用链式结构存储。

• 自拟一个实验实例验证程序正确性（即：n,x,y 自拟）。

Lab2_1 2/8 进制转换器

编写程序，从终端输入一串 0/1 表示二进制数，以“#”结束，输出它的 8 进制表示形式。要求：采用栈来实现。

Lab2_2 判别回文字符串

正读和反读都一样的字符串称为回文字符串。编写程序，在键盘上输入一个字符串，以“#”作为结束标志，判别它是否为回文字符串。要求：采用栈和队列来实现。

Lab3

假设稀疏矩阵 A 和 B 均以三元组表作为存储结构，试写出矩阵相加和相乘的算法，另设三元组表 C 存放结果矩阵。

要求：

• 从键盘输入稀疏矩阵 A 和 B。
• 检测 A 和 B 能否相加/相乘。
• 如能，做矩阵相加和相乘运算，并打印运算结果。
• 如不能，应显示出原因。

Lab4_1

用先序递归过程建立二叉树（存储结构：二叉链表）输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入 * 号，如输入 abc**d**e**。

Lab4_2

将任意一个指定的文件进行哈夫曼编码，并以真正的二进制位生成一个二进制文件（压缩文件）；反过来，可将一个压缩文件解码还原为原来的文件。

提示：对选定的文件以二进制方式读入，一次读入一定的长度如 1024bytes，然后对每一字节（一字节 8bit，所以刚好对应 256 个 ASCII 字符）进行统计，如此循环统计。

Lab5

已知某图是边带权（权值为正数）的有向无环图，采用邻接表存储，求出图中距离最远的两个结点。