跳到主要内容

北京邮电大学计算机专业“数据结构”课程实验/大作业

GitHub Website GitHub top language

实验一:约瑟夫问题/约瑟夫环

本实验属于线性表实验。

问题

据说著名犹太历史学家 Josephus 有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太 人与 Josephus 及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人抓到,于是决 定了一个自杀方式 41 个人排成一个圆圈,由第 1 个人开始报数,每报数到第 3 人该人就必须 自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并 不想遵从,Josephus 要他的朋友先假装遵从,他将朋友与自己安排在第 16 个与第 31 个位置, 于是逃过了这场死亡游戏。 17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事: 15 个教徒和 15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办 法: 30 个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循 环进行直到仅余 15 个人为止。问怎样排法,才能使每次投入大海的都是非教徒。

要求

  1. 从键盘输入人数 N (N < 50) 及 N 个人的编号(整型)、姓名、性别和年龄,正向建立带头节点的循环链表;
  2. 输出循环链表各结点的值;
  3. 输入开始报数的人的编号 S 、间隔的个数 M 和剩余人数 X;
  4. 在循环链表中查找到编号为 S 的结点;
  5. 从 1 开始向后报数,将报 M 的人(结点)从循环链表中删除,并输出该人的编号;
  6. 从刚才被删除人的下一个人开始重复步骤 5,直至最后只剩下 X 个人为止;
  7. 输出最后剩余的人的编号、姓名、性别和年龄;
  8. 能够处理异常输入输出。

样例

N 个人围成一圈,从第 S 个开始报数,每隔第 M 个将被杀掉,最后剩下 X 个,其余人 都将被杀掉。例如 N = 6, S = 1, M = 5 ,被杀掉的人的序号为 5, 4, 6, 2, 3 ,最后剩下 1 号。

思路

通过链表存储约瑟夫环的结构,加入时直接加入链表末端。之后,将链表首尾相接,首节 点的前指针指向末节点,末节点的后指针指向首节点。之后每次删除时,从链表中删除数据 (前一节点的后指针指向后一节点,后一节点的前指针指向前一节点)并释放内存,最后当人 数等于剩余人数时,输出结果。

编译运行

使用脚本

./build_run_unix.sh

手动运行

g++ lab1.cpp -std=c++14 -O2 -Wall -o lab1
./lab1

实验二:迷宫问题/最短路

本实验属于栈实验。

问题

迷宫(希腊文:λαβυνρινθωσ,拉丁转写:labyrinthos)在希腊神话中是一座精心制作的建筑物,由名匠代达罗斯为克里特岛的国王米诺斯所设计,建造于克诺索斯。Labyrinth这个词经常可以和maze(迷路园)互换使用,但现代专门学者使用更严格的定义。对他们而言,maze是一个游览拼图参观的形式,有着可以选择不同路径与方向的复杂分歧通道;而单一路径的labyrinth只有一条唯一的欧拉路径到达中心。(摘自:迷宫 - 维基百科)。

此处是图论的迷宫问题(类似maze):在一个无向图中,找到指定起点到终点的最短路。

注意

由于课程要求,这一图论问题不得使用图论中的最短路算法解决

要求

  1. 从开始位置start找出到出口end的通路,并从start到end输出;输出路径的长度。
  2. 可以将节点进行编号,从1开始编号,编号次序从上到下,从左到右;保存每条边,根据两个节点之间是否有边,来决定是否能够走通;
  3. 将边保存在文件中,用2个端点来表示一条边,第三个数表示边权;
  4. 每点的分支数不一样,要求根据分支数决定遍历的方向数,不能用恒定的遍历方向数;
  5. 补充:当迷宫有多个出口应该如何找到最近的出口。

样例

约定输入格式

第1行输入1个整数m,代表无向图的总边数;接下来m行,每行3个整数,其中第i(i= 1,2,···, m)行的三个整数ui, vi, wi,分别表示第i条边的起点、终点、边权;接下来1行输入1个整数s,代表迷宫的起点;接下来1行输入一个整数n,代表迷宫终点的个数;最后1行输入n个整数t1, t2,···, tn,每个数均为一个可行的终点。

样例

4
1 2 1
2 3 4
3 4 2
2 4 6
1
2
3 4

对应答案:不难发现,最短路径为1→2→3,总边权和为5。

思路

用栈模拟DFS,方法如下:

  1. 判断DFS栈是否为空,若为空则结束DFS,否则继续;

  2. 取DFS栈顶一点并弹出DFS栈顶;

  3. 判断该点是否为终点:

    若不是:

    1. 遍历每一个该点的出度的终点;
    2. 若该终点不存在于当前点的对应路径中,则将该终点加入栈顶;

    若是:

    1. 比较当前点的对应路径与已知最短路径;
    2. 若当前路径比已知最短路径要短,则将当前路径设置为最短路径

编译运行

使用脚本

./build_run_unix.sh

手动运行

g++ lab2.cpp -std=c++14 -O2 -Wall -o lab2
./lab2

版权

版权所有 © 2021 Zhenglong WU (itdevwu).

本项目“BUPT-data-structure”的文档采用知识共享署名 4.0 国际许可协议进行许可。

本项目的代码采用 MIT 协议进行许可。