北京邮电大学
计算机学院
大二
数据结构课程设计--后端代码仓库
另外部分后端@Guo-Chenxu
课设得分98
[TOC]在整体架构上，我们选择了 B/S 架构，采用前后端分离的方式进行合作开发，前端部分采用目前较为流行的 Vue 框架进行开发，并调用后端提供的 API 进行数据交互；后端采用了Spring boot+Spring Cloud Alibaba微服务架构
- src/
- assets/：放置项目静态资源，如图片、字体等；
- components/：存放可复用的 Vue 组件；
- plugins/：存放与 Vue 应用程序的插件相关的文件；
- vuetify.js：这个文件是用来配置和安装 Vuetify 的主要文件。可以在其中引入 Vuetify 的组件、样式和主题，并进行全局配置。该文件应该导出一个函数，在函数中使用 Vue.use()来安装 Vuetify 插件。
- router/：存放路由配置文件，包括路由定义、路由守卫等；
- index.js：定义路由规则和导航逻辑，负责配置和创建 Vue Router 实例，并将路由与 Vue 实例关联起来，以实现前端路由功能。
- views/：用于存放应用程序的视图组件和页面级组件，以便于更好的组织和管理页面组件，同时作为路由配置的基础，每个路由规则都会映射到一个具体的组件。src/views/文件夹的结构通常与路由规则的配置相对应，方便在路由配置中引用正确的视图组件；
- Auth/AuthMgt.vue:实现了一个身份验证视图组件的功能。它包含了一个登录和注册的表单，用户可以通过输入邮箱和密码进行登录，或者填写姓名、邮箱、密码和组 ID 进行注册。
- Course/CourseMgt.vue：实现了用户的课程管理页面，包含课程概览、课程信息修改和课程删除（仅针对管理员）。
- Home/Home.vue：展示用户主页，如姓名、学号、Email、班级等个人信息和学院、专业等院系信息。
- Navigation/Navigation.vue：实现地图导航功能，包括点到点导航、途径多点导航。
- Schedule/ScheduleMgt.vue：实现用户日程管理功能，主要分集体活动和个人活动两个部分来展示，包括活动添加、活动修改、活动删除等操作。
- Schedule/ScheduleSearch.vue：实现活动搜索功能，包括通过活动名称、活动日期和活动简介三种不同的方式来进行搜索。
- App.vue：根组件，用于包裹整个应用程序的布局结构，可以在此处设置全局样式和引入全局组件，主要包括活动功能侧边栏和顶部工具栏的展示，以及系统模拟时间的各种操作。
- main.js：项目入口文件，用于初始化 Vue 应用和加载所需的插件、路由、状态管理，以及设置全局变量、函数等。
- 路由（Router）：使用 Vue Router 进行页面导航和路由管理，将路由配置拆分为多个文件，可以使用路由守卫进行权限控制和登录验证。
- UI 组件库（Vuetify）: 基于 Vuetify 2 组件库构建用户界面，使用 Vuetify 提供的组件、样式和布局来设计和构建应用程序的用户界面。
- Ajax 请求封装（Axios）: 使用 Axios 库来处理与后端的 AJAX 请求，可以创建通用的请求封装，设置统一的请求拦截器和响应拦截器，处理请求错误和统一的返回数据格式。
- 静态资源管理: 将图像、字体等静态资源放置在 assets/目录下，可以使用相对路径引用，或在构建过程中进行打包和处理。
- 使用 Vue CLI 脚手架工具进行项目初始化和构建，以便快速搭建开发环境、管理依赖和进行打包部署等。
- 在构建过程中，可以配置 Webpack 等工具来处理样式、静态资源、代码分割等优化策略，以提高应用程序的性能和加载速度。
直接的前后端请求通过 Spring boot 提供的端口映射，http 访问，其中跨域问题在后端通过@cors 解决
而服务器向用户主动推送的需求，比如课程提醒，模拟时间推进等，通过 webSocket 技术实现
主体的服务实现，基于 Spring boot 编写
其中服务的入口处通过 nginx 分流，JWT/spring security 来完成简单的登陆；后续如有空闲可以接入 sentinel 来考虑任务里强调的“用户量庞大的情景”的流量防护。
由于不是单人开发，尝试了通过 nacos 作为服务的注册中心，用 dubbo 来完成 gRPC 的远程服务调用。做到开发独立，架构灵活，测试简单，易于横向扩展
主要是解决在开发过程中多人合作时，接口管理困难，项目依赖混乱的问题
**是把 service 的抽象声明封装，提供一个统一的对外接口，然后实现和服务展示可以见仁见智
nacos 作为注册中心，通过 dubbo 实现服务的 gRPC 调用
数据主要通过 MySQL 数据库存储，也学习性的通过 redis 完成了地图信息等一部分存储主要起到一个方便的存储、读入的功能，核心算法由代码实现
-
project/
-
common-api/：放置通用的接口、文档等；
- document：项目文档
- weekly-doc：周报
- src：通用的服务接口、实体类、工具类等
-
gcx/：存放成员郭晨旭编写代码；
- schedule：学生的日程管理以及用户信息管理模块
-
gzy/：存放成员郭泽远编写代码；
- guide：地图导航模块
- login：用户登录注册及权限验证模块
- simulate：用户模拟系统时间推进模块
-
- 通过 maven 管理，将其导入之后 run 即可
- 打包已经在 pom 文件中配置插件，直接使用 package 指令
- 其他环境：mysql、redis 等，如果在校园网可以连接我们的服务器，否则需要自行配置，并运行项目中的 sql 文件创建表项
- 由于使用了 nacos 作为配置中心，所以如如果不是内网，需要自己运行 nacos 服务器并配置（没有使用 v6 的域名访问，因为网络不太稳定）
在项目开发的过程中，我们使用 Github 进行版本管理，团队成员可以协作开发、跟踪代码更改、审查代码、管理问题和版本，并实现持续集成和部署，极大地提高了开发效率，并促进团队的协作和沟通。
目前合作的仓库已有近两百次提交，贯穿开发全过程。现在已经设置为 public 仓库，可直接访问。
- 完成了所有日程(包括课程、考试、活动、临时事务和闹钟)的
增加、删除、修改和查询, 其中增加、删除和修改均有操作合法性的判断。 - 所有项目的增加和修改都完成了冲突检测, 集体活动和个人活动在发生冲突时均可以返回三个可用时间。
- 对于活动搜索功能，我们实现了按名称、按自定义类型和按时间查询(可以同时作为查询条件进行搜索, 如果没有输入时间则默认查询用户当前模拟时间的日程), 返回结果均以时间排序。
- 同时，用户也可以通过课程表和日程表快速地查看日程详情, 提高用户体验。
- 对于课程管理，我们实现了分别采用月视图、周视图、日视图和每四天的视图的方式呈现用户的课程和考试信息，同时，当用户点击某一课程或考试信息之后，会通过卡片形式弹出该课程的详细信息。
- 对于管理员用户，我们实现了课程类日程管理的添加、修改和删除操作。
- 对于地图导航功能，我们实现了点到点导航功能(P2P)和途径多点导航功能(VIAMANY)供用户选择，极大地满足了用户群体的需求差异。
- 在用户的实际体验优化方面，我们实现了用户直接点击地图，算法自动匹配距离最近的建筑坐标，极大地降低了用户的实际操作难度，从而不同年龄段的用户都可以很快上手。（见模块设计报告）
- 我们实现了根据日程提醒，自动规划导航路径的功能，用户无需手动选择，即可获得最优的路径规划。
- 在系统模拟时间功能上，我们实现了对模拟时间的启动、暂停、加速、减速、继续、翻转、重置和终止操作，这样的设计旨在满足当代不同用户群体的多样化需求，并为他们提供更丰富、灵活的体验选择。
- 多个微服务，每一个有自己的日志
- 具体内容如下图所示
- 还配置了按日志的日期自动打包并存档
- 我们选做了1、4两项，即日程管理和地图导航的可视化界面，界面详细展示可见[5 运行效果展示](#5 运行效果展示)。
使用拉链法自己实现哈希表的 put、remove、get、getOrDefault 以及扩容算法. 主要**为先求键值的哈希值然后放入哈希桶中, 如果发生冲突则插入到链表中, 其中还自己实现了 linkedlist 使得在 put 操作时直接在头部插入节点, 降低了时间复杂度,提高了性能。
复杂度分析：
哈希表增加和修改均使用 put 方法, 时间复杂度经过优化后为
数据结构说明：
线段树是一种用于解决区间查询问题的数据结构，它具有以下几个特点：
- 分治**：线段树采用分治**，将一个区间划分成多个子区间，并通过构建树状结构来表示这些子区间。
- 高效的查询和更新：线段树允许在 O(log n)的时间复杂度内进行区间查询和更新操作。通过对树的节点进行合并操作，可以在树的深度为 O(log n)的路径上完成对区间的查询或更新。
- 空间效率：线段树的空间复杂度为 O(n)，其中 n 为表示区间的元素个数。尽管它需要额外的空间来存储树状结构，但相对于存储所有可能的区间，它仍然是一种高效的数据结构。
- 动态性：线段树可以方便地支持动态的区间查询和更新。当区间发生变化时，只需要对相应的节点进行更新操作，而无需重新构建整个树。
- 广泛应用：线段树在解决区间最值、区间和、区间覆盖等问题上具有广泛的应用。它可以用于处理静态数据，也可以通过懒惰更新等技术扩展到处理动态数据。
在此项目实现中，选择该数据结构主要是用于检测用户的日程的冲突，以及快速的查询用户在某一时间段内的日程。
我们选取了合适的方式建树：以分钟为单位，整个树的大小就是常数的 1440，因此区间查和区间改的操作就都可以降低到近似 O(1)的复杂度。
同时，由于有插入课程/活动的操作，我们还采用了上面提到的懒惰更新，进一步提高了日程管理的性能
使用状压 dp 求解途径多点的导航的最短哈密顿路径
我们考虑到了在需要途径的点数非常多的情况下（超过 20 个点，虽然这种概率非常小），一次导航需要的时间就会达到秒级，可能对用户的操作体验造成影响。
因此，我们选择在途经点太多时放弃求精确解，转而采用简单的搜索方法来求出一个遍历途经点的近似解。
在这样的设计下，20 个途经点以内的导航会在一秒内给出最短遍历路径的精确解，而更多的点则会瞬间给出一个近似解
不过在测试中，这样超过 20 个途经点的近似解在人眼看来几乎不会有什么绕路的情况，说明并没有为了用户体验而牺牲掉正确性，而是兼顾了两者。
快速排序是通过每次排序将待排序的数据分为独立的两部分, 其中一部分比另一部分的所有数据都要小, 然后再分别排序, 时间复杂度为$O(nlogn)$.传统的快排算法会有分配不均导致时间复杂度退化到$O(n^2)$的情况发生, 所以我们进行了改进优化, 将固定的最低为作为枢轴替换为随机枢轴, 降低了时间复杂度退化的情况发生, 几乎是稳定的$O(nlogn)$，下图为两种算法的测试对比, 不难看出性能提升了$95%$。 另外我们还使用了泛型和比较器, 可以自定义待排数据的类型和排序的比较器。
求解一元线性同余方程组，在项目中用于查询两个日程最近的冲突日期（如：5 月 1 日周期为 3 天的日程和 5 月 2 日周期为 4 天的日程会在 5 月 10 日发生冲突），判断在有效期内两个日程是否会在同一天发生。
其中扩欧的复杂度为 O(lgn)，求逆元调用一次扩欧，同样为 O(lgn)。而 CRT 方法需要对输入的每一个同余方程进行遍历，然后调用一次求逆元，因此总的复杂度为 O(nlgm)，其中 n 为需求解的同余方程数目，m 为方程中系数的值，此处为一个较小的数（也就是日程循环的周期天数）。因此复杂度基本上可以看成是用户的日程数目遍历一次。
综合考虑了 SPFA、dijstra、floyd 这几类最短路算法。
由于地图导航的情形下不存在负权边/环，所以没有必要采用 SPFA；而 floyd 算法一次性 O(E^3)过于臃肿，所以我们使用了 dijstra+缓存的方案来完成最短路导航
复杂度分析：采用堆优化，最差为 O(ElgV)，并且采取了缓存路径的方式，空间换时间，每次导航都可以保存部分路径从而加速。
所以期望在进行了 E 次导航之后，复杂度可以降至 O(1)（直接从缓存取路径即可）
数据结构说明：
字典树（Trie 树）是一种用于高效存储和查找字符串的数据结构，它具有以下几个特点：
- 前缀匹配：字典树可以高效地实现对字符串的前缀匹配。通过将字符串按照字符逐级存储在树中，可以方便地找到具有相同前缀的字符串集合。
- 查找效率高：在字典树中查找一个字符串的时间复杂度仅与字符串的长度相关，而与存储的字符串数量无关。无论字典树中存储了多少字符串，查找操作都可以在 O(m)的时间复杂度内完成，其中 m 为待查找字符串的长度。
- 空间效率：字典树的空间复杂度相对较高，但它可以通过压缩存储来减小内存占用。例如，可以使用指针共享相同前缀的节点，从而减少存储空间。
- 动态性：字典树支持动态地插入和删除字符串。当需要插入或删除一个字符串时，只需要在树中相应的位置进行节点的插入或删除操作，而无需重新构建整个树。
- 适用范围广：字典树在解决字符串相关问题时具有广泛的应用。例如，在自动补全、拼写检查、字符串匹配等领域，字典树可以快速地找到匹配的字符串集合。
总的来说，字典树是一种高效的字符串查找和存储结构。它的主要优点是查找过程中具有较高的效率，能够快速地进行前缀匹配，并且支持动态插入操作
在项目中，考虑用来完成模糊匹配功能——即根据用户输入的前缀，查找能够羽织匹配的整个字符串
复杂度分析：
原始复杂度为 O(L)，L 为待查询字符串长度。由于存储的都是课程/地点名称，所以基本是小于 10 的常数。
因此，在我们项目的情形下，在树中插入、判断、查询均可视为 O(1)。
而获取所有模糊匹配的操作，其复杂度分析较复杂。可以确定最好情况 O(L)，最坏情况 O(nL)；推测平均情况为 O(
(大致推导思路：考虑平均情形下，什么时候才会插满字典树的一层——每一个分支节点想要增加一层都需要接近字符集大小的存储。同时考虑获取以某一个节点为前缀的子树的大小，以及将这棵子树变为 list 返回所需的复杂度（这个显然是 O（子树总结点数））。最后考虑一个字符串可能查询到哪一层的子树：字符串长度每加一，对应的子树就靠下一层，大小也平均会除以字符集大小（假设所有字符均匀出现）。三者综合得出这个结果，具体公式推导略)
平衡树通过不断调整左右子树的高度避免了排序树退化的情况，原先在项目中用于在内存中存储课程、用户等信息以便于快速查询，但后来在实际运用中被更好的哈希表替代
平衡树通过控制左右子树的高度差值不大于 1 从而达到平衡, 使得增删改查的时间复杂度均为$O(nlogn)$。
对有序的数据进行二分查找, 实现了自定义比较器, 时间复杂度为$O(nlogn)$。
见测试报告
-
用户可以通过"LOG IN"选项进行登录操作，当输入正确的 Email 和 Password 之后，页面会显示“登录成功”，并跳转到“我的主页”。
-
当用户点击左侧功能导航栏的"我的主页"模块之后，右侧展示用户的姓名、用户类别（分学生和管理员两种）、Email、学号、班级等个人信息，以及学生的学院、专业等院系信息，分别点击“学院、专业、班级”三个模块，即可查看对应的信息。
-
当用户点击左侧功能导航栏的"课程管理"模块之后，右侧展示用户的课程信息，用户可分别切换“日视图、周视图、月视图和每四天的视图”。
-
日视图
-
周视图
-
月视图
-
每四天的视图
-
同时，在每个界面，当用户点击某个课程时，可以查看该课程的详细信息。
-
如果当前用户为管理员还可以点击左上角的"pencil"图标，对课程信息进行修改操作；或者点击右上角的"delete"图标，对课程进行删除操作。
-
当用户点击左侧功能导航栏的"日程管理"模块之后，右侧从上到下依次展示活动搜索框、用户今日集体活动、用户今日个人活动。
-
在活动搜索框中，用户分别可以通过活动名称、活动日期以及活动描述来进行搜索。
-
当用户点击“今日集体活动”或“今日个人活动”右侧的加号时，可以添加集体/个人活动。
-
当用户点击每项活动右侧的"pencil"按钮时，可对所选活动的信息进行修改，如下图所示：
-
当用户点击"delete"图标时，可以对当前活动进行删除，若删除成功，则会显示“操作成功”的提示。
-
当用户点击左侧功能导航栏的"地图导航"模块之后，右侧展示北京邮电大学校园平面图，以及地图导航的操作按钮。
-
用户点击"选取导航坐标"按钮，之后可以在地图上的相应位置依次进行点击，选取坐标点，选取完成之后，点击"P2P"按钮，完成导航路径规划，再点击“动画展示”按钮，图上将会展示已经规划好的路径。
-
此时点击“动画展示”按钮，则会以动画的形式将路径展示出来。（路线上的红点按照规划好的导航路径正在移动）
-
用户点击"选取导航坐标"按钮，之后可以在地图上的相应位置依次进行点击，选取坐标点，选取完成之后，点击"VIAMANY"按钮，完成导航路径规划，再点击“动画展示”按钮，图上将会展示已经规划好的路径。
-
此时点击“动画展示”按钮，则会以动画的形式将路径展示出来（路线上的红点按照规划好的导航路径正在移动），与点到点导航方式不同的是，途径多点导航方式将会按照路径规划的现后顺序，在图上动态展示导航路径。
在右侧上方的位置，有一排按钮，他们分别实现对模拟系统时间的启动、暂停、加速、减速、继续、翻转、重置和终止的操作。同时根据该模拟系统时间，提示用户第二天的所有事务，以及用户下一个小时内的所有事务，并为用户自动规划导航路径。
-
下一小时事务提醒
-
第二天事务提醒
——————————另：据我实测 bug还很多 不过高水平的验收大忽悠糊弄过去了 所以如果有学弟用到这玩意 发现有bug 那很正常。也可以问我——如果有空 上面这个就是提交的概要课程报告