单链表上的简单插入排序 c++
目前，我并不担心效率，我只是在学习。我想知道是否有人可以帮助我学习单链表的简单插入排序。这是我的作业，所以我想理解它。这是代码：
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，因此我需要在读入时对其进行排序。顺便说一句，Node 是一个结构体。有人可以帮我吗？
For now, Im not worried about efficiency and I am just learning. I was wondering if anyone could help me out with learning a simple insertion sort for a singly linked list. This is for my homework so I would like to understand it. Here is the code:
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
}
}
}
so far I have it read into an istream so I need to sort it as it gets read in. Node is a struct btw. Could anyone help me please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
看起来您要在列表末尾添加一个额外的节点。我怀疑您最终会在最后一个节点中得到未初始化的数据。
目前，您只需将每个新节点添加到列表的末尾。
您应该从前面迭代整个列表，并找到正确的排序位置，而不是将每个节点添加到列表的末尾。然后将节点插入到该排序位置而不是末尾（我相信这是您尝试在
//insertion sort循环中实现的逻辑。It looks like you're adding one extra node at the end of your list. I suspect you'll wind up with uninitialized data in your last node.
Currently you're just adding each new node to the end of the list.
Instead of adding each node to the end of the list, you should iterate over the entire list from the front, and find the correct sorted location. Then insert the node into that sorted location instead of at the end (I believe that's the logic you attempted to implement in your
//insertion sortloop.尝试构建一个基于 STL 的有效模型。如果你有一个有序列表，你可以通过 lower_bound 找到好的地方：
Try build an effective one based on STL. If you have an ordered list, you could find the good place by lower_bound: