c++ - 使用数据结构的日历和任务列表

Question

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

1. 日历天使用数组，然后为相应天制作任务链表。

2. 两者都使用链表。

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

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

问候

Answer 1

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

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

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