c-排序链表时遇到

Question

我正在尝试用包含动物名称及其权重的节点按字母顺序递增对链表进行排序。我实现了一个函数来实现它，但我得到了意外的输出。我确实试着调试了很长一段时间，但我很难找到问题所在。如果有任何意见，我将不胜感激。我的代码如下：

typedef struct Animal_Info{
char animal_name[1000];
float animal_weight;
}AnimalInfo;
typedef struct my_node{
AnimalInfo info;
struct my_node *next;
}Animal_Node;
Animal_Node *sortAnimalList(Animal_Node *head)
{
Animal_Node *a = NULL;
Animal_Node *b = NULL;
a = head;
b = head->next;
char name_copy[MAX_STR_LEN];
float weight_copy;
while (a != NULL){
while (b != NULL){
if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
strcpy(name_copy, b->info.animal_name);
weight_copy = b->info.animal_weight;
deleteNode(b->info.animal_name, b->info.animal_weight, head); // finds and deletes the node
insertNode(name_copy, weight_copy, head); // insert at head of linked list
}
else if (strcmp(a->info.animal_name, b->info.animal_name) == 0){
weight_copy = 1.0; /* "do nothing" statement */
}
b = b->next;
}
a = a->next;
}
}

Answer 1

您的代码中有很多东西看起来很奇怪。

第一部分：

else if (strcmp(a->info.animal_name, b->info.animal_name) == 0){
weight_copy = 1.0; /* "do nothing" statement */
}

当它什么都不做时，只需删除它！

现在看看这个和我的内联评论：

Animal_Node *sortAnimalList(Animal_Node *head)
{
Animal_Node *a = NULL;
Animal_Node *b = NULL;
a = head;
b = head->next;
char name_copy[MAX_STR_LEN];
float weight_copy;
while (a != NULL){
while (b != NULL){
if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
strcpy(name_copy, b->info.animal_name);
weight_copy = b->info.animal_weight;
// Here you delete node b
deleteNode(b->info.animal_name, b->info.animal_weight, head);
insertNode(name_copy, weight_copy, head);
}
// Here you use node b
b = b->next;
}
a = a->next;
}
}

当您进入删除节点b的代码时，不能在语句b = b->next;中使用该节点，因为b不再指向有效节点。

当b变为NULL时，执行a = a->next;，但不更改b，因此不会执行内部循环。

我想你需要这样的东西：

while (a != NULL){
// Assign new value to b whenever a has changed
b = a->next;
while (b != NULL){
if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
strcpy(name_copy, b->info.animal_name);
weight_copy = b->info.animal_weight;
// Here you delete node b
deleteNode(b->info.animal_name, b->info.animal_weight, head);
insertNode(name_copy, weight_copy, head);
}
// Here you use node b
b = b->next;
}
a = a->next;
}

最后，我认为你的算法是错误的。当您更改链接列表时，您总是将元素放在列表的前面。那行不通。考虑：

"c" -> "a" -> "b"

因此，步骤是：

compare "c" and "a"
delete "a" and insert "a" in front, i.e. you have "a" -> "c" -> "b"
compare "c" and "b"
delete "b" and insert "b" in front, i.e. you have "b"->"a" -> "c"

因此得到的列表是未排序的"b"->"a" -> "c"。

你需要重新考虑你的算法。

您可以考虑交换节点，而不是"在前面删除并插入"。也许这可以帮助交换链接列表中的节点