Lab 1实验报告
实验要求
1 .读入文本并生成有向图：
将文本数据转换为有向图结构，各单词作为节点，有向边表示单词在文本中的相邻关系及其出现次数。
2. 展示有向图：
图形化展示生成的有向图，并可保存为图形文件。
3. 查询桥接词：
查询两个单词之间的桥接词，即图中存在两条边word1→word3和word3→word2，则称word3为word1和word2的桥接词。
4. 根据桥接词生成新文本：
在输入的新文本中插入旧图得到的桥接词，生成新的文本。
5. 计算两个单词之间的最短路径：
计算图中两个单词之间的最短路径，并突出显示路径。
6. 随机游走：
从图中随机选择一个节点，进行随机游走，记录路径并展示结果。
待求解问题描述
输入数据：
是纯英文的一个txt文件，可分为多行。读取文本时，换行符、回车符、标点符号以及任何非字母字符均被忽略，仅仅读入单词。
输出数据：
一个有向图，且支持依据该图进行多种操作。具体的输出有：
展示有向图、查询桥接词、根据桥接词生成新文本、计算最短路径、随机游走路径。
约束条件：
1. 有向图的结点为文本的单词，边的方向体现文本中相邻两个单词出现的顺序，边的权重体现按此顺序相邻的一对单词的出现次数，
2. 所有的操作均在文本文件生成的有向图上进行。
3. 程序以命令行或GUI方式交互，并满足所有功能需求。
算法与数据结构设计
设计思路与算法流程图
模块1：根据文本生成图
算法步骤：
- 打开并读取文本文件。
- 将文本中的所有非字母字符替换为空格，并将其转换为小写。
- 按空格分割文本，生成单词数组。
- 遍历单词数组，相邻的单词之间生成边。
- 将每对相邻单词添加到图中，并记录边的权重（即相邻出现的次数）。
流程图：
模块2：展示图
算法步骤：
- 初始化图形界面组件。
- 计算每个节点的位置（例如，圆周分布）。
- 绘制每个节点及其标签。
- 遍历图的边，绘制每条边及其权重。
- 如果是有向图，绘制箭头表示方向。
流程图：
模块3：查询桥接词
算法步骤：
- 输入两个单词 word1 和 word2。
- 检查这两个单词是否在图中。
- 遍历 word1 的邻接节点，检查是否有共同的邻接节点与 word2 相连。
- 如果找到，记录并返回桥接词列表；否则，返回提示信息。
流程图：
模块4：根据桥接词生成新文本
算法步骤：
- 输入新文本。
- 将新文本按空格分割成单词数组。
- 遍历新文本的每对相邻单词。
- 查找每对相邻单词的桥接词，并将其插入两者之间。
- 返回新的文本。
流程图：
模块5：计算最短路径
算法步骤：
- 输入起始单词和终止单词。
- 使用 Dijkstra算法计算最短路径。（具体算法流程在流程图给出）
- 返回最短路径及其长度。
流程图：
模块6：随机游走
算法步骤：
- 选择起始节点
- 执行随机游走
- 返回游走路径。
流程图：
数据结构设计
主要使用了以下几种数据结构来构建和操作有向图：
- Map (HashMap)：用于存储图的邻接表和节点。
- Node：表示图中的节点。
- PriorityQueue：用于实现 Dijkstra 算法的优先队列。
有向图的数据结构
Node 类：
- word：表示节点的名称或标识符，这里是一个单词。
- distance：用于 Dijkstra 算法，表示从起点到该节点的当前已知最短距离。
Graph 类：
- nodes：使用 Map<String, Node> 来存储图中的所有节点，键是节点的名称，值是节点对象。
- adjList：使用 Map<String, Map<String, Integer>> 来表示邻接表，键是节点的名称，值是一个嵌套的 Map，表示该节点的邻接节点及其边的权重。
Dijkstra 算法的数据结构
- PriorityQueue：用于实现 Dijkstra 算法的优先队列。
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::getDistance));
- distances 和 previousNodes：用于记录从起点到每个节点的最短距离和路径。
Map<String, Integer> distances = new HashMap<>();
Map<String, String> previousNodes = new HashMap<>();
算法时间复杂度分析
- 根据文本生成图：
- 假设文本总长度为 N 个字符，平均每行长度为 L，总行数为 M，则 N = M * L。
- 处理每行的正则表达式替换和分割操作需要 O(L) 时间。
- 每行分割成单词后添加边的时间为 O(L)。
- 总时间复杂度：O(M * L) = O(N)。
- 展示图：
- 遍历节点集 nodes：O(V)，其中 V 是节点数。
- 遍历每个节点的邻接节点集：总时间为 O(E)，其中 E 是边数。
- 总时间复杂度：O(V + E)。
- 查询桥接词：
- 检查节点存在：O(1)。
- 遍历 word1 的邻接节点：O(d1)，其中 d1 是 word1 的出度。
- 遍历 word3 的邻接节点：O(d3)，其中 d3 是 word3 的出度。
- 总时间复杂度：O(d1 * d3)。
- 根据桥接词生成新文本：
- 假设新文本长度为 K，分割操作需要 O(K) 时间。
- 对每对相邻单词调用 findBridgeWords，每次查询桥接词的时间复杂度为 O(d1 * d3)。
- 总时间复杂度：O(K * d1 * d3)。
- 计算最短路径 (Dijkstra 算法)：
- 初始化距离和前驱节点：O(V)。
- 每个节点进入和出优先队列操作：O((V + E) log V)。
- 总时间复杂度：O((V + E) log V)。
- 随机游走：
- 随机选择起始节点：O(1)。
- 每次选择邻接节点：遍历邻接节点集和其权重 O(d)，其中 d 是当前节点的出度。
- 假设最大游走长度为 L，总时间复杂度：O(L * d)
实验与测试
设计1个至少包含50个单词的输入文本文件，使之可覆盖本题目中关于输入文件和功能的各种特殊情况，作为你开发的程序的输入。
针对在有向图上操作的每项功能，为其设计各种可能的输入数据。输入数据的数量不限，以测试程序的充分性为评判标准（下面各节中的表格的行数请自行扩展）。
记录程序的输出结果，判断输出结果是否与期望一致，并记录程序运行截图。
读取文本文件并展示有向图
文本文件中包含的内容：
The cat sat on the mat. The mat was warm and soft. The cat liked the mat.
The cat purred on the mat. The cat was happy. The mat was warm.
The cat sat and purred. The mat was soft and warm. The cat liked the mat.
The mat was warm and soft. The cat purred on the mat.
期望生成的图（手工计算得到）：
程序实际生成的图：
二者是否一致：
一致
给出实际运行得到结果的界面截图。
查询桥接词
|
序号 |
输入（2个单词） |
期望输出 |
实际输出 |
运行是否正确 |
|
1 |
word1:,man word2:out |
No word1 or word2 in the graph! |
No word1 or word2 in the graph! |
正确 |
|
2 |
word1:cat word2:sat |
No bridge words from cat to sat! |
No bridge words from cat to sat! |
正确 |
|
3 |
word1:happy word2:cat |
The bridge words from happy to cat are: the |
The bridge words from happy to cat are: the |
正确 |
给出实际运行得到结果的界面截图。
根据桥接词生成新文本
|
序号 |
输入（一行文本） |
期望输出 |
实际输出 |
运行是否正确 |
|
1 |
man out |
man out |
man out |
正确 |
|
2 |
happy cat and on mat |
happy the cat sat and purred on the mat |
happy the cat sat and purred on the mat |
正确 |
|
3 |
warm cat like mat mat warm soft |
warm the cat like mat the mat was warm and soft |
warm the cat like mat the mat was warm and soft |
正确 |
给出实际运行得到结果的界面截图。
计算最短路径
|
序号 |
输入（两个单词、或一个单词） |
期望输出 |
实际输出 |
运行是否正确 |
|
1 |
happy and |
Shortest path from happy to and is: happy -> the -> cat -> was -> soft -> and with total weight 11 |
Shortest path from happy to and is: happy -> the -> cat -> was -> soft -> and with total weight 11 |
正确 |
|
2 |
soft the |
Shortest path from soft to the is: soft -> the with total weight 2 |
Shortest path from soft to the is: soft -> the with total weight 2 |
正确 |
|
3 |
cat on |
Shortest path from cat to on is: cat -> sat -> on with total weight 3 |
Shortest path from cat to on is: cat -> sat -> on with total weight 3 |
正确 |
给出实际运行得到结果的界面截图。
随机游走
该功能无输入，让你的程序执行多次，分别记录结果。
|
序号 |
实际输出 |
程序运行是否正确 |
|
1 |
Random walk starting from on: on -> the -> mat -> was -> warm -> the -> cat -> purred -> on |
正确 |
|
2 |
Random walk starting from mat: mat -> was -> warm -> the -> mat |
正确 |
|
3 |
Random walk starting from and: and -> warm -> and -> soft -> the -> mat -> was -> soft -> and |
正确 |
给出实际运行得到结果的界面截图。
编程语言与开发环境
- IntelliJ IDEA 2024.1.1
- Java(TM) SE Runtime Environment (build 1.8.0_333-b02)
- Windows 10
- Git version 2.39.0.windows.1
- Apache Maven 3.9.6
结对编程
分组依据
为何你们两位组成了结对编程的小组？从性格、能力、编程技能等方面简要介绍。
- A同学：
- 对各种编程语言、数据结构和算法有深入了解，特别是 Java。熟悉软件开发的最佳实践和设计模式，能够编写高效、可维护的代码。
- 擅长通过实际操作和调试解决问题，能够快速找到并修复代码中的错误。
- B同学：
- 注重代码质量，喜欢编写清晰、简洁且易于维护的代码。
- 能够快速识别潜在的代码问题和优化点，提供建设性的反馈 ，帮助提高代码质量。
角色切换与任务分工
|
日期 |
时间( HH:MM -- HH:MM) |
“驾驶员” |
“领航员” |
本段时间的任务 |
|
5/18 |
10:00 – 11:45 |
A |
B |
确定代码结构 |
|
5/18 |
11:45 – 12:30 |
B |
A |
完成基本Graph类 |
|
5/18 |
13:45 – 14:30 |
A |
B |
完成命令行交互 |
|
5/18 |
14:30 – 15:30 |
B |
A |
完成GUI界面 |
|
5/19 |
10:00 – 11:00 |
A |
B |
完成GUI绑定事件 |
|
5/19 |
11:00 – 12:00 |
B |
A |
规范函数签名 |
工作照片
工作日志
|
日期/时间 |
问题描述 |
最终解决方法 |
两人如何通过交流找到解决方法 |
|
5/18 |
生成图的图片没有箭头来表示有向。 |
添加相关方法，完善该功能 |
阅读实验报告，确定需求，提出代码缺陷。 |
|
5/18 |
GUI中的图片显示不会更新 |
显示时先读取图片缓存，而不是直接输入到ImageIcon |
实操确定Bug，交流分析确定该Bug原因，检查相关代码。 |
Git操作过程
实验场景(1)：仓库创建与提交
·R0：在进行每次git操作之前，随时查看工作区、暂存区、git仓库的状态，确认项目里的各文件当前处于什么状态；
命令：git status
·R1：本地初始化一个git仓库，将自己在Lab1中所创建项目的全部源文件加入进去，纳入git管理；
.初始化仓库命令：git init
（此处已经提前init一次）
.将源文件纳入git管理并查看：git add src ; git status
·R2：提交、手工对提交的部分文件进行修改；
.提交命令：git commit
·R3：查看上次提交之后都有哪些文件修改、具体修改内容是什么；
查看文件修改情况：git status
截图见R2最后部分
查看具体修改：git diff <filename>
·R4：重新提交；再次对部分文件进行修改；
重新提交：1.git add <filename>(重新将修改后的文件放入暂存)
2.git commit -m ‘再次提交’(将暂存的文件提交)
再次对部分文件进行修改，并查看具体改动；
·R5：重新提交
git add <filename>
git commit -m ‘R5’
·R6：把最后一次提交撤销
git revert HEAD(并在打开的vim编辑中直接退出，不进行任何编辑)
·R7：查询该项目的全部提交记录
git log
·R8：在GitHub上创建名为“Lab1-学号”的仓库，并在本地仓库建立相应的远程仓库；
git remote add origin [email protected]/xxxx/Lab1-xxxxx.git
git push -u origin main
实验场景(2)：分支管理
·R1：获得本地Lab1仓库的全部分支，切换至分支master；
git branch
git checkout master
·R2：在master基础上建立两个分支B1、B2；
git checkout -b B1
git checkout -b B2
·R3：在B2分支基础上创建一个新分支C4；
git checkout -b C4
·R4：在C4上，对2个文件进行修改并提交；
git status（查看状态，确认分支）
git add input.txt input2.txt
git status
git commit -m "R4"
·R5：在B1分支上对同样的2个文件做不同修改并提交；
git checkout B1
git status
git add <同样的2个文件的文件名)
git commit -m "R5"
·R6：将C4合并到B1分支，若有冲突，手工消解；
git branch（确保在B1中）
git merge C4
·R7：在B2分支上对2个文件做修改并提交；
git checkout B2
git status
git add .
git status
git commit -m “R7”
git status
·R8：查看目前哪些分支已经合并、哪些分支尚未合并；
git branch –-merged
git branch --no-merged
·R9：将已经合并的分支删除，将尚未合并的分支合并到一个新分支上， 分 支名字为你的学号；
git checkout -b xxxx
git merge B2
git merge main
git merge B1
<手动解决冲突>
git add <filename>
git commit -m “merge B1”
git merge C4
git branch --no-merged
git branch -d B2
git branch -d B1
git branch -d C4
git branch -d main
git branch
·R10：将本地以你的学号命名的分支推送到GitHub上自己的仓库内；
之前，已经添加过remote，所以直接git push -u origin xxxxx即可。
·R11：查看完整的版本变迁树；
git log --oneline --graph --decorate --all
·R12：在Github上以web页面的方式查看你的Lab1仓库的当前状态。
在IDE中使用Git Plugin
- 在IDE中，将自己的Lab1纳入Git管理；
点击VCS 创建git仓库，选择当前项目
点击完成之后打开我们本地项目路径就可以看到一个.git文件。
- 对Lab1进行若干修改，对其进行本地仓库提交操作；
如图，修改在Changes里可见，通过勾选来纳入管理，然后点击Commit在本地提交。
3. 将Lab1内容推送至个人GitHub的Lab1仓库。
上图中，可以选 Commit and Push来推送到个人的Github仓库。
也可以通过，Git一栏来操作：
小结
结对编程的优势
结对编程（Pair Programming）是一种有效的编程实践方法，两名程序员在同一台电脑上协同工作，共同完成代码的编写和调试。在经历过结对编程的实践后，我有以下几点体悟：
- 提高代码质量：
- 双方实时审查代码，减少错误和缺陷，确保代码质量。
- 知识共享：
- 双方在合作过程中相互学习，提升编程技能和技术水平。
- 增强团队协作：
- 增强沟通和协作能力，促进团队内部的信任和合作。
Git实践项目中的应用：
-
- 在实际项目中，使用Git和Github来管理项目源代码，可以有效地跟踪代码变化、版本回退以及分支管理。
- Git的基本指令（如git init, git add, git commit, git push, git pull等）是项目管理的基础。熟练使用这些指令，可以确保代码的版本控制和安全。