0

我是科罗拉多梅萨大学的一名 csci 学生。系主任教给链表一个接地气的方法：

struct nodeType
{
    int id;
    nodeType *link;
};

void createList(nodeType *&head, nodetype *&tail)
{
    head = new nodetype;
    tail = new nodetype;
    head->id=-1; //some initialize value
    head->link=tail;
    tail->link=NULL;
}

void insertList(nodeType *&head, nodeType *&tail)
{
    nodetype *knew,*prior, *next;
    knew = new nodetype;

    knew ->name = name

    prior = head;
    next = head->link;
    while(next != tail && knew->id > next->id)
    {
        prior = next;
        next = next->link;
    }

    prior->link = knew;
    knew->link = next;
}

她教这个的原因很明显。使用接地的头和尾，更容易插入，因为你调用上面的函数，然后编写一个函数来追加这两个节点内的所有数据，编写删除函数时稍微容易一些，因为你永远不会删除头或尾部，因此更难丢失列表并产生垃圾。

我的算法教授说，我在“现实世界”中遇到的其他任何地方的列表，一个没有根据的列表会更好。其他语言，使用 STL 和在互联网上，我找不到实现头尾的列表函数。

我只是想为实际的现实世界中的编程做好准备，而不是我的教授认为的现实世界，所以我的问题是：使用一个或另一个更好，使用我觉得更容易的那个，还是接近每个问题都同时考虑？

提前感谢您抽出宝贵时间帮助我解决这场争执。

4

1 回答 1

0

在“现实世界”中，您将使用其他程序员设计、实现、优化和测试的列表，您永远不会知道它是否“接地”，因为这只是一个实现细节。

从您的算法课程中学到的重要一点是：

  • 性能特点。链表或向量是否具有更快的随机访问？更快的追加？更快地删除第一个元素？使用正确的容器并不是过早的优化。

  • 看到足够多的不同实现风格，因此如果您不得不使用调试器单步执行您的代码，您将不会感到非常困惑。如果您看到 at-end-of-list 测试返回 true，但下一个节点指针不是 NULL，那么如果您以前从未见过“接地”列表实现，您可能会感到非常困惑。

于 2012-02-06T23:16:04.297 回答