c++ - 使用数据结构的日历和待办事项列表

Question

我希望为任何相应的一天制作日历和任务列表 - 就像大多数日历应用程序一样。这种实践的主要目的是有效地使用数据结构。 我想到了两种方法:

1. 使用数组表示日历日，然后制作相应日期的任务链接列表。

2. 两者都使用链接列表。

另一个问题是:我可以在上述场景中使用树吗？ 也许我完全错了。请指导我，我很想学习。

注意:我将使用 C++ 作为我的工具，但不使用 STL。

问候

Answer 1

就时间复杂度而言，您的第一种方法更加高效，因为可以在数组中以恒定的时间访问与任何一天相关的任务。但缺点是它会比链表占用更多的空间。
如果您对日历日使用链接列表，则可以一次为每一天添加一个新节点，而不是一次添加所有节点(如在数组中)。因此两种情况下的最终空间使用量将是相同的。

就树而言，可以使用 Map - 像Associative containers ，通常实现为 Self-balancing BST ，从而在时间(对数)和空间/内存(与日历中存储的天数成比例，但没有空间浪费，与数组不同)方面提供了不错的效率。在这种情况下，您可以将日期与字符串链接列表相关联。

如果我是你，我会使用 map<date,vector<string> >尽管。