使用链表排序
我有两个字段，即 ID 和名称。在链表中插入节点后，我想按 ID 降序对其进行排序。假设不同的人有可能拥有相同的ID。例如，
1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL
最终列表应如下所示：
1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL
我按升序对具有相同 ID 的名称进行排序，而 ID 按降序排序。这是我的代码：
NODE* insert_std(NODE *head, NODE* std){
NODE *prev, *cur;
if(head==NULL) return std;
cur = head;
while (cur != NULL && std->ID < cur->ID){
prev = cur;
cur = cur->next;
}
if(std->ID == cur->ID){
while (cur != NULL && strcmp(std->name, cur->name)>=0){
prev = cur;
cur = cur->next;
}
}
if (head==cur){
if(std->ID >= head->ID) {
std->next = head;
head = std;
}
} else {
std->next = cur;
prev->next = std;
}
return head;
}
但是没有按照我想要的方式排序。我做错了什么？
I have two fields namely ID and name. Upon inserting a node in a linked list, I would like to sort it by ID in descending order. Assuming that it is possible that different persons can have the same ID. For Example
1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL
The final list should look like this:
1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL
I sort the names with the same ID in ascending order while the IDs are sorted in descending order. Here is my code:
NODE* insert_std(NODE *head, NODE* std){
NODE *prev, *cur;
if(head==NULL) return std;
cur = head;
while (cur != NULL && std->ID < cur->ID){
prev = cur;
cur = cur->next;
}
if(std->ID == cur->ID){
while (cur != NULL && strcmp(std->name, cur->name)>=0){
prev = cur;
cur = cur->next;
}
}
if (head==cur){
if(std->ID >= head->ID) {
std->next = head;
head = std;
}
} else {
std->next = cur;
prev->next = std;
}
return head;
}
But is is not being sorted the way I want it. What am I doing wrong?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在插入函数中，每当比较两个节点时，首先比较两个 ID。如果一个比另一个小，这会告诉您哪个节点应该排在第一位。如果ID相同，则需要比较名称来决定哪个节点在前。
这相当于修改
std->ID <= cur->ID和std->ID > 。头->ID。如果我是你，我会编写一个辅助函数，它需要两个指向NODE的指针（将它们称为 A 和 B），以上述方式比较它们并返回true如果节点 A 在节点 B 之前。将此函数合并到您的insert_std中就很简单了。In your insertion function, whenever you compare two nodes, compare the two IDs first. If one is smaller than the other, this tells you which node should come first. If the IDs are the same, you need to compare the names to decide which node comes first.
This amounts to modifying
std->ID <= cur->IDandstd->ID > head->ID. If I were you, I would write a helper function that would take two pointers toNODE(call them A and B), compare them in the manner described above and returntrueif node A comes before node B. Incorporating this function into yourinsert_stdis then trivial.只需替换 ID 值的比较，并在 ID 值相同时也考虑名称（例如使用 strcmp）。最简单的方法是编写一个单独的函数来比较执行此任务的两个记录。
Simply replace your comparisons on ID values, and take into account the name as well (for example using strcmp) when the ID values are the same. The easiest way is to write a separate function for comparing two records which does this job.
添加
&& while 循环中的 std->ID == cur->IDAdd
&& std->ID == cur->IDon the while loop