0

以我正在处理的任务为例。我们将使用二叉搜索树来查找一组数据中的一部分，然后使用链表查找该组中的另一部分。教授建议的方法是：

struct treeNode
{
    data * item;
    treeNode *left, *right;
};

struct listNode
{
    data * item;
    listNode *next, *prev;
};

class collection
{
public:
         ........
}

其中 data 是包含每条记录的详细信息的类。显然，由于它的设置，treeNode 不能存在于链表中。

会不会更简单：

struct node
{
    data * item;
    node *listNext, *listPrev, *treeLeft, *treeRight;
};

然后我们可以声明：

node * listHead;
node * treeRoot;

并将两种插入算法都包含在类中。

有什么我想念的吗？

4

3 回答 3

0

答案是什么？

如果您的数据小于 (hmmm) 兆字节，请不要担心内存消耗。1 或 2 GB 在当今的普通计算机中是典型的。

物品有多大？32个字符？64k 压缩多媒体？有什么大不了的？

使用这两种技术组织一个项目有多合理？如果数据确实相同，那么 5 指针结构很有趣——有人可以以一种顺序找到一个节点，然后以另一种顺序浏览相关节点。

这些项目是否无关，一些粉笔，一些奶酪？它们是多维的吗？人事记录？音频文件说明？食谱？

在学校里，一位好老师正试图给你一些常见技术和学科的经验。就像艺术课或作曲一样。铅笔，粉彩，5 段文章。所以老师可能希望你写两个不同的类和构造函数。对一部分数据使用一个结构，对其他数据使用不同的结构。或者一样。只是因为。

在学校之外，数据以某种格式出现，并且对其/带有所需的操作。“用例”是关于如何使用数据、必须保留什么、使用什么算法的故事。

这可能是双峰搜索，2对正交指针。它可能是联合，其中每个项目都与列表或树相关联，但不能同时与两者相关联。它可能是一系列轻量级的子集、树和列表，它们被比较和对比……

如有疑问，“数据结构 + 算法 = 程序”。但是了解老师试图提出的观点以及您是否想跟随他们的领导是值得的。（通常，在学校，你会这样做。）

于 2011-04-12T00:51:13.357 回答
0

你可以这样做，但是你用额外的指针浪费了内存。此外，混合这样的类型往往会更令人困惑。我是否正确假设数据要么放入列表或放入树中，但未插入两者？如果它们是不同的数据类型，真的没有太多理由让它们都使用相同的结构。如果您将相同的数据插入到两种类型中，那么如果您对此类操作有任何用途，则可能会从遍历树切换到遍历列表。

由于您将数据插入到两个列表中，因此使用复合节点结构可以节省内存。我会先插入二叉树，然后将分配的节点插入到链表中。你不会真的得到一个纯链表或二叉搜索树，但它可以像任何一个一样被遍历。

于 2011-03-09T20:08:29.540 回答
0

实际上，数据项将被插入到两个列表中。分配的（普通）目的是在集合中的两个不同元素中对数据集进行排序。

话虽如此，我不会节省内存吗？结合 2 个节点，我最终得到 5 个指针，如果我将它们分开，我将使用 6 个。此外，我真的只有这样一组数据。如果我有 250 个数据项要跟踪，我将拥有一组 1250 个指针，而不是 2 个 750 个列表。也许我误解了指针调用实际分配的内容。

于 2011-03-09T20:59:25.260 回答