C中链接列表合并排序实现中丢失的节点
此实现用于按升序字母顺序排列字符串。我已经包含了负责划分节点的函数。head是链接列表的首字母。
我认为mergeSort函数的工作原理是将列表划分开来。见以下输出：
Head: lady apple stone red queen
fast:
slow: stone
front: lady apple stone
back: red queen
Head: lady apple stone
fast:
slow: apple
front: lady apple
back: stone
Head: lady apple
fast:
slow: lady
front: lady
back: apple
Head: red queen
fast:
slow: red
front: red
back: queen它清楚地显示了初始列表，lady apple stone red queen被划分为各个节点，所有这些都得到了考虑。
当节点被比较并合并到新的列表中时，问题就出现了。例如:最初，将lady与apple进行比较。它们被合并到列表中：apple, lady。那么这个列表应该与stone合并。但是，首先，将lady与stone进行比较，而不是将apple与stone进行比较。然后生成列表：lady, stone (apple留在后面，而不是在比较中使用)。应该发生的是，将apple与stone进行比较，然后将lady与stone进行比较，然后将条目排序并相应地合并到：apple, lady, stone中。
实际的最终输出是：lady, red, stone。很明显，apple和queen在某个地方迷路了。我不知道什么是违规代码。
void mergeSort(Node *head) {
Node *front = NULL, *back = NULL, *fast, *slow;
if(head == NULL || head->next == NULL)
return;
...
mergeSort(front);
mergeSort(back);
head = mergeLists(front, back);
}回答 3
Stack Overflow用户
发布于 2017-12-13 13:58:30
你的代码几乎是完美的。您正在合并两个列表并将其返回给head。但是，您不能将确切的head返回到以前的mergeSort调用。
Node* mergeSort(Node *head) {
Node *front = NULL, *back = NULL, *fast, *slow;
if(head == NULL || head->next == NULL)
return head; // return head
...
front = mergeSort(front); // save it to front
back = mergeSort(back); // save it to back
head = mergeLists(front, back); // save it to head
return head; // return head
}在调用mergeSort的主函数中，使用head = mergeSort(head)。代码现在应该起作用了。
Stack Overflow用户
发布于 2017-12-13 13:29:03
一个更容易(而且可能更有效，尤其是对于大列表)的方法是首先将链接列表转换为数组。请考虑以下代码：
char ** arr;
int size=getLinkedListSize(head);
arr = malloc(sizeof(*arr)*size);
linkedList2Array(head, arr);
mergeSort(arr, size);
array2LinkedList(arr, size, head);注意，我使用的是char **类型。点(合)是指向链接列表中的数据。如果数据比简单的字符或ints更复杂，则可以避免不必要的数据复制。
这是更容易写，即使它有一些样板，它不影响任何事情。函数(您必须编写) getLinkedListSize、linkedList2Array和array2LinkedList都可以具有O(n)的复杂性，而mergeSort无论做什么都是O(n*log )。此外，要考虑到此方法对缓存更友好。
唯一的缺点是，它需要更多的内存，但不是太多。数组的最大大小将与列表相同。
我提到的三个函数编写起来很简单。下面是其中的两个：
int getLinkedListSize(Node * head)
{
int ret=0;
while(head) {
ret++;
head=head->next;
}
return ret;
}
void linkedList2Array(Node * head, char ** arr)
{
int index=0;
while(head) {
arr[index++]=&head->data;
head=head->next;
}
}Stack Overflow用户
发布于 2017-12-13 15:12:53
不需要慢/快方法(Floyds algoritm)。它也是计数器-effective:排序将总是采取N个日志(N)操作，即使是在排序列表上。
您可以利用现有的订单，只需删除无序元素，并保留其余的元素。然后(递归)对无序部分进行排序，并合并这两个部分。
struct list {
struct list *next;
char* data;
};
#define COMPARE(a,b) strcmp((a),(b))
struct list *splitmerge(struct list *org)
{
struct list *rest ,*this, **pp;
if(!org|| !org->next) return org;
/* Split off out-of-order nodes*/
rest = NULL;
for (this = org; this; ){
struct list* next;
if(!this->next)break;
next = this->next;
if(COMPARE( this->data, next->data) <= 0) {
this= next;continue;
}
/* Cut next out of the chain */
this->next = next->next;
next->next = rest;
rest = next;
}
/* At this point, org is guaranteed to be sorted
** rest is not.
*/
/* Order the trash */
rest = splitmerge(rest);
/* Merge with the trash */
this=NULL;
for(pp = &this; org && rest; pp = &(*pp)->next ) {
if(COMPARE( org->data, rest->data) <= 0) {
*pp = org; org=org->next;
}
else {
*pp = rest; rest=rest->next;
}
}
*pp = (org) ? org : rest;
return this;
}https://stackoverflow.com/questions/47793914
复制相似问题
腾讯云开发者
