0

目前，我不担心效率，我只是在学习。我想知道是否有人可以帮助我学习一个简单的单链表插入排序。这是我的作业，所以我想了解它。这是代码：

char c[13];
    r >> c;
    r >> NumberOfInts;

    Node *node = new Node;
    head = node; //start of linked list

    for(int i = 0; i < NumberOfInts; i++) //this reads from the file and works
    {
        r >> node->data;
        cout << node->data << endl;
        node ->next = new Node; //creates a new node
        node = node->next;

        if(_sortRead) //true
        {
            for(int k = 0; k < i; k++)
            {
                         //insertion sort
            }
        }
    }

到目前为止，我已将它读入 istream，因此我需要在读入时对其进行排序。节点是一个结构 btw。有人可以帮我吗？

4

2 回答 2

0

看起来您正在列表末尾添加一个额外的节点。我怀疑您最终会在最后一个节点中获得未初始化的数据。

目前，您只是将每个新节点添加到列表的末尾。

与其将每个节点都添加到列表的末尾，不如从前面遍历整个列表，并找到正确的排序位置。然后将节点插入到该排序位置而不是最后（我相信这是您尝试在//insertion sort循环中实现的逻辑。

于 2011-04-25T19:36:20.500 回答
0

尝试基于 STL 构建一个有效的。如果你有一个有序列表，你可以通过 lower_bound 找到好地方：

template<class T> std::list<T>::iterator insert( std::list<T> &my_list, const T &value )
{
  return my_list.insert( std::lower_bound( my_list.begin(), my_list.begin(), value ), value );
}
于 2011-04-25T19:46:56.450 回答