主题 3 SD

负责人

• Robert Grancsa
• Baldovin Razvan-Mihai-Marian
• Chitan Rafael

发布日期：2024 年 5 月 10 日

截止日期：2024 年 5 月 26 日，晚上 11:59

! 重要：这个主题将由两人一组完成，可以与 CA 系列中的任何人或复习材料的任何人一起完成。为了更容易地批改主题，您必须在 README 中务必写一个消息，形式如下

Echipa tema 3 SD:
id.moodle1
id.moodle2

例如，andrei.popescu。如果您想单独完成主题，这不建议，您可以只写一个名字。

更新

• 2024 年 5 月 14 日（00:23）- 添加了索引说明

目标

完成这个主题后，您将

• 学习如何在日常任务中使用图
• 练习实现树状数据结构
• 了解如何实现社交媒体平台

简介

由于上一主题中的 Marcel（云存储服务的巨大成功），他开始思考如何扩展他的服务以与行业巨头竞争，并希望在全球化市场上推出。经过几天的头脑风暴，他意识到如果不需要如此分散的需求将非常有益。他不再需要在 "Gogu Drive" 上有云存储，在 "InstaBook" 上有社交网络，以及他最喜欢的意见分享应用程序 "Z"，如果所有这些都集中在同一个地方将会更简单。

他已经在先前的项目中实现了云存储部分，现在是时候创建他最喜欢的社交网络了，随着会话的临近，他需要您的帮助。他为您提供了他希望在 Alpha 版平台中拥有的功能，并且如果你们能及时帮助他，他承诺给你们一个稳定的职位和平台利润的一部分！

这个主题分为 3 个阶段，前两个阶段可以并行进行，没有相互依赖。主题的框架应该允许你在不使用任务 1 或任务 2 的代码的情况下工作。

每个输入始终有效，因此您不需要担心处理参数缺失或无效的情况。

我们建议您在前两个阶段独立工作，但这不是强制性的。

本主题设计得允许您在不使用先前阶段代码的情况下工作，但我们建议使用GitHub等平台以实现更轻松的协作。

任务1（好友网络）

添加好友

add<名字-1> <名字-2>

创建两个用户之间的联系。这是一个双向联系，即双方都将对方作为好友。

示例

> add Mihai Andrei
< Added connection Mihai - Andrei

!信息 对于每个输入，都保证不会使用列表中不存在的用户，或者重复的用户。

删除好友

remove<名字-1> <名字-2>

删除两个用户之间的联系。

示例

> add Mihai Andrei
> remove Mihai Andrei
< Removed connection Mihai - Andrei

查询距离

distance<名字-1> <名字-2>

计算平台上的两个人之间的距离。距离被认为是每条好友关系为1。

示例

> add Mihai Andrei
> add Andrei Alex
> add Alex Mihnea
> distance Mihai Mihnea
< The distance between Mihai - Mihnea is 3

!信息 如果两个用户之间没有联系，将显示 "There is no way to get from <name-1> to <name-2>"

建议

suggestions<名字>

找到并显示所有不是您好友的好友的朋友。好友将按用户ID升序显示。

示例

> add Alex Andrei
> add Andrei Maria
> add Andrei Mihai
> add Andrei Vlad
> suggestions Alex
< Suggestions for Alex:
< Maria
< Vlad
< Mihai

!信息 如果没有针对用户的建议，将显示 "There are no suggestions for <name>"

共同好友

common<名字-1> <名字-2>

需要找到两个用户的好友。一个共同好友是一个同时与 <name-1> 和 <name-2> 都是好友的人。您将按用户ID升序显示好友列表。

示例

> common Alex Ana
< The common friends between Alex and Ana are:
< Maria
< Andrei
< Ioana

!信息 如果没有共同好友，将显示："No common friends for <name-1> and <name-2>"

好友数量

friends<名字>

需要显示一个人的连接数。

> friends Andrei
< Andrei has 5 friends

最受欢迎

popular<名字>

需要显示具有最多连接的 <name> 用户及其好友。

示例（假设Andrei - Mihai - Ana都是好友）

> friends Andrei
< 10
> friends Mihai
< 15
> friends Ana
< 9
> popular Ana
< Mihai is the most popular friend of Ana
> popular Mihai
< Mihai is the most popular

!信息 在他和其他好友相等的情况下，将优先选择他自己作为最受欢迎的好友。在好友相等的情况下，将按ID考虑第一个。

任务2（帖子与转发）

对于这个阶段，我们将使用一种树形数据结构，用于存储帖子与转发。每个帖子都将有一个唯一的ID，并且可以有许多转发。一个转发将是一个帖子本身，它将有一个唯一的ID，并将与原始帖子相关联。我们将使用一棵树来存储这些帖子与转发，其中每个节点都有一个 events 字段，它是一个帖子与转发树。

struct {
    id: number,
    titlu: string,
    user_id: number,
    events: tree
}

创建帖子

create<名字> <标题>

用户 <name> 将创建一个标题为 <title> 的帖子。每个帖子都将有一个唯一的ID，该ID在每次创建新帖子时递增。

示例

> create Mihai "Titlu postare"
< Created "Titlu postare" for Mihai

限制与说明

• 一个用户可以有多个帖子
• 一个用户可以有多个标题相同的帖子
• 帖子标题的最大长度为280个字符
• 帖子ID将是一个正整数，对于每个帖子都是唯一的

！警告：Indexarea începe de la 1

重新发布

重新发布<名字> <发布-id> [重新发布-id]

创建一个现有帖子的重新发布。如果repost命令有一个重新发布id，那么它将被视为对重新发布的重新发布。

示例

• 在运行命令之前，我们有

> repost Alex 1 2
< Created repost #3 for Alex

• 运行命令后，我们有

限制

• 重新发布具有与帖子完全相同的结构（唯一的id将递增，就像正常帖子一样），但没有由用户指定的标题（在结构中可以将其设置为NULL）。
• 重新发布将存储在原始帖子的events树中，具体取决于重新发布的时间（可能是另一个重新发布或原始帖子的子树）。
• 重新发布的events字段将为空（设置为NULL）。
• 重新发布也可以由原始帖子以外的用户进行（我们将在重新发布结构中存储进行重新发布的用户的id）。

第一个共同重新发布

common-重新发布<发布> <重新发布-id-1> <重新发布-id-2>

找到两个重新发布之间的第一个共同重新发布。

示例

> common-repost 1 4 7
< The first common repost of 4 and 7 is 2.

喜欢

喜欢<名字> <发布-id> [重新发布-id]

向帖子或重新发布添加喜欢。如果提供了重新发布id，则喜欢将添加到重新发布中。

示例

> create Mihai "Titlu postare"
< Created "Titlu postare" for Mihai
> like Alex 1
< User Alex liked post "Titlu postare"
> like Alex 1
< User Alex unliked post "Titlu postare"

说明

• 用户只能对一个帖子或重新发布给予一次喜欢
• 如果用户对已经给予喜欢的帖子或重新发布下达'like'命令，则喜欢数量将递减（相当于dislike）。
• 您可以通过修改post_t结构来存储帖子/重新发布的喜欢。
• 如果用户对重新发布给予喜欢，则喜欢不会添加到原始帖子中。

比率

比率<发布-id>

在互联网俚语中，比率意味着一个对帖子的回复有比原始帖子更多的喜欢（这意味着回复的意见比原始帖子的意见更被接受）。

因此，在我们的情况下，我们将实现类似的比率，但对于重新发布，如果重新发布有比原始帖子更多的喜欢，我们可以说它给了比率。

示例

> create Mihai "Opinie nepopulară"
> repost Alex 1
> like Alex 1 2
> like Ana 1 2
> ratio 1
< Post 1 got ratio'd by repost 2

说明

• 如果重新发布有比原始帖子更多的喜欢，将显示原始帖子已被该重新发布比率。
• 如果有多个重新发布给帖子比率，将显示喜欢数量最多的（在相等的情况下，显示id较高的第一个重新发布）。
• 如果原始帖子比所有重新发布有更多的喜欢，将显示The original post is the highest rated。

删除帖子/重新发布

删除<发布-id> [重新发布-id]

删除帖子或重新发布。一旦帖子或重新发布被删除，所有依赖于此的重新发布也将被删除。

！警告：注意 - 帖子和重新发布的ID不会重用。

示例

> delete 1
< Deleted "Titlu postare"

获取喜欢

获取-喜欢<发布-id> [重新发布-id]

显示帖子或重新发布的喜欢数量。

示例

> get-likes 1 2
< Repost #2 has 5 likes
> get-likes 1
< Post "Titlu postare" has 0 likes

获取重新发布

获取-重新发布<发布> [重新发布-id]

显示帖子/重新发布的所有重新发布层次结构。

将按创建顺序显示重新发布，包括进行重新发布的用户的姓名。例如，我们将考虑以下事件树，用于id为1的帖子

我们将考虑第一个帖子的标题为Cat video，而所有重新发布都是同一用户Alex进行的。

> get-reposts 1
< "Cat video" - Post #1 by Alex
< Repost #2 by Alex
< Repost #4 by Alex
< Repost #5 by Alex
< Repost #7 by Alex
< Repost #3 by Alex
< Repost #6 by Alex

限制

• 将按id的升序显示同一级别的所有重新发布
• 如果一个重新发布有重新发布，它们将按id的升序显示，然后显示同一级别的下一个重新发布

任务3（社交媒体）

动态信息

动态信息<名字> <动态信息-大小>

显示用户及其好友的最新 <feed-size> 帖子。

!警告 由于我们要显示最新的帖子，所以将按照发布顺序的相反顺序显示帖子，即最后发布的帖子将首先显示。

示例

> create Andrei "Prima mea postare"
> create Mihai "Al doilea"
> create Mihnea "Vand Golf 4"
> create Alex "Buna TPU, merita sa dau la Poli?"
> create Ana "Ati auzit ultima melodie a lui Kanye?"
> create Luca "Nu-mi vine sa cred cine a castigat Grand Prix-ul de la Miami"
> feed Andrei 5
< Luca: "Nu-mi vine sa cred cine a castigat Grand Prix-ul de la Miami"
< Ana: "Ati auzit ultima melodie a lui Kanye?"
< Alex: "Buna TPU, merita sa dau la Poli?"
< Mihnea: "Vand Golf 4"
< Mihai: "Al doilea"

查看个人资料

查看-个人资料<名字>

显示用户发布的所有帖子及其转发的帖子，按照发布/转发顺序。

示例

> create Andrei "Prima mea postare"
> create Mihai "Al doilea"
> create Alex "Shaorma e veatza mea"
> repost Andrei 3
> view-profile Andrei
< Posted: "Prima mea postare"
< Reposted: "Shaorma e veatza mea"

转发的朋友

friends-重新发布<名字> <发布-id>

显示所有给 <post-id> 帖子进行转发的用户的好友。显示的名单将按照用户ID的升序排列。

示例

...
> repost Mihai 5
> repost Alex 5
> repost Ana 5
> friends-repost Andrei 5
< Friends that reposted:
< Ana
< Alex
< Mihai

点击

common-小组<名字>

查找并显示包含特定用户的最大好友小组。

一个好友小组被定义为小组内所有彼此都是朋友的人。显示的名单将按照用户ID的升序排列。

示例

> common-group Alex
< The closest friend group of Alex is:
< Ana
< Alex
< Mihai
< Ioana
> common-group Luca
< The closest friend group of Luca is:
< Alex
< Luca
< Mihai

从这张图中可以看出，Ana - Alex - Ioana - Mihai 构成了一个完整的小组，而 Luca 不属于这个小组，因为他只有2个共同朋友。

!信息 一个点击可以只由一个用户组成，在这种情况下，输出将只显示他的名字。

有用链接

https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm#Without_pivoting

建议

为了更轻松地工作，我们有一些技巧要分享。

1. 以使您的生活更轻松的方式使用 GitHub。我们建议不要将所有代码都写在 main 中，为每个任务创建 一个分支，然后创建 拉取请求 以减少冲突。
2. 为了更轻松地使用 GitHub，我们建议创建一个 私有 的我们的仓库的分支，邀请您的同事并直接在那里编写代码。
3. 如果您使用 GitHub，一个优点是您可以在每次给任何分支推送时使用 Moodle 的检查器，并可以在 actions 标签中查看运行结果。接下来，您需要将主题加载到 Moodle 上，但这是一种更简单的调试方法，因为它们都在同一个系统上运行，所以 Moodle 上的问题也会出现在这里，反之亦然。

评分

• 任务 1 - 30 分
• 任务 2 - 30 分
• 任务 3 - 30 分
• 编码风格和 README 中的解释清晰度 - 10 分

常见问题解答

Q: 我们可以用 C++ 实现主题吗？A: 不可以。

Q: 我们可以使用全局变量吗？A: 不可以。

Q: 我们可以修改骨架/添加函数吗？A: 可以。

Q: 我们可以独立完成主题吗？A: 可以，但是分数不会缩放，你将会有更多的工作要做。

检查器

! 注意，检查器使用 valgrind 运行所有测试。如果您遇到 valgrind 错误，则不会在 Moodle 上的检查器中获得分数。要激活检查器上的 valgrind，请按 v 键，将出现红色窗口。

安装步骤

!信息 如果您已经安装了 IOCLA 第 1 个主题的检查器，您可以直接跳到步骤 2。

您可以通过运行命令 ./install.sh 来安装检查器。如果在运行命令时出现任何错误，请尝试并遵循以下步骤

1. 下载 rustup（应独立于平台） curl https://sh.rustup.rs -sSf | sh -s -- -y。如果在后续步骤中出现问题，请尝试将 cargo（Rust 的包管理器）添加到 PATH 中，运行以下命令 source "$HOME/.cargo/env"。

2. 运行以下命令来安装 checker

$ cargo install hw_checker

安装后，您可以直接从主题根目录运行 checker，使用命令 hw_checker，或者可以在当前文件夹中创建一个符号链接。

checker 指令

要查看 checker 的完整命令列表，请阅读 README-checker.md 中的说明。如果图形界面出现问题，可以使用以下命令在没有图形界面的情况下运行 checker：hw_checker --legacy