当我被告知“排序单链接列表”时，预期的是什么 [英] What is expected when I am told "Sort a singly linked list"
问题描述
这个问题是否希望我通过交换列表中每个节点的值来排序列表，以便这些值按照某种顺序（升序/降序）排列。这里将改变节点的原始值（排序前），以反映排序的列表。这里返回相同的早期头指针，但现在它的最小元素可能与之前的元素不同。
像下面的C代码一样以下代码可能无法按原样编译，但我可以正常工作。发布于此作为说明，以清除我的观点）：
struct lnk_lst
{
int val;
struct lnk_lst * next;
};
main（）
{
//假设curr是使用某些值创建的单链表的头节点
curr = llist_bubble_sort（curr ）;
}
struct lnk_lst * llist_bubble_sort（struct lnk_lst * lst）
{
int i，n = 0，tmpint;
struct lnk_lst * tmp = lst，* tmp2 = lst;
while（tmp-> next）
{
lst = tmp2;
while（lst-> next）
{
if（lst-> val> lst-> next-> val）
{
tmpint = lst-> val;
lst-> val = lst-> next-> val;
lst-> next-> val = tmpint;
}
lst = lst-> next;
}
tmp = tmp-> next;
}
return tmp2;
}
或
预期在原始排序中具有最小元素（假定升序）的节点的指针被移动为新的头节点，则具有下一个最小元素的节点被链接到头节点，并且所以列表完全重新排序，现在返回的头节点与前面的指针不一样。
如果列表排序的解释是第二个，那么我有看看如何在代码中完成这个想法。
链表中的整个想法是链接可以在没有影响内容。有时候，改变指针有时会创建指向指针变量的指针。另外：如果你只是交换内容，你也可以省略 - >下一个指针，使用数组，并交换数组的内容。
自然排序链表的方式是mergeesort。下面的片段将列表分为两部分：已经存在的节点以及没有的节点。第二个列表被排序，并且两个列表合并。分裂和合并都涉及一些指针指针变量。
#include< stdio.h>
#include< string.h>
struct llist {
struct llist * next;
char * payload;
};
int llist_cmp（struct llist * l，struct llist * r）;
struct llist * llist_split（struct llist ** hnd
，int（* cmp）（struct llist * l，struct llist * r））;
struct llist * llist_merge（struct llist * one，struct llist * two
，int（* cmp）（struct llist * l，struct llist * r））;
struct llist * llist_sort（struct llist * ptr
，int（* cmp）（struct llist * l，struct llist * r））;
struct llist * llist_split（struct llist ** hnd，int（* cmp）（struct llist * l，struct llist * r））
{
struct llist * this， *保存，**尾;
for（save = NULL，tail =& save; this = * hnd;）{
if（！this-> next）break;
if（cmp（this，this-> next）< = 0）{hnd =& this-> next;继续; }
* tail = this-> next;
this-> next = this-> next-> next;
tail =&（* tail） - > next;
* tail = NULL;
}
return save;
}
struct llist * llist_merge（struct llist * one，struct llist * two，int（* cmp）（struct llist * l，struct llist * r））
{
struct llist * result，** tail;
for（result = NULL，tail =& result; one&& two; tail =&（* tail） - > next）{
if（cmp ，2）< = 0）{* tail = 1; one = one-> next; }
else {* tail = two;两个=二次>下一个}
}
* tail = 1？一二;
返回结果;
}
struct llist * llist_sort（struct llist * ptr，int（* cmp）（struct llist * l，struct llist * r））
{
struct llist *保存;
save = llist_split（& ptr，cmp）;
if（！save）return ptr;
save = llist_sort（save，cmp）;
return llist_merge（ptr，save，cmp）;
}
int llist_cmp（struct llist * l，struct llist * r）
{
if（！l）return 1;
if（！r）return -1;
返回strcmp（1>有效载荷，r-有效载荷）;
}
struct llist lists [] =
{{lists + 1，one}
，{lists + 2，two }
，{lists + 3，three}
，{lists + 4，four}
，{lists + 5，five}
，{lists +6，six}
，{lists + 7，seven}
，{lists + 8，eight}
，{NULL，nine}
};
int main（）
{
struct llist * root，* tmp;
root = lists;
fprintf（stdout，##％s\\\
，initial：）;
for（tmp = root; tmp; tmp = tmp-> next）{
fprintf（stdout，％s\\\
，tmp-> payload）;
}
fprintf（stdout，##％s\\\
，sorting ...）;
root = llist_sort（root，llist_cmp）;
for（tmp = root; tmp; tmp = tmp-> next）{
fprintf（stdout，％s\\\
，tmp-> payload）;
}
fprintf（stdout，##％s\\\
，done）;
return 0;
}
结果：
##初始：
一
二
三
四
五
六
七
八
九
##排序...
八
五
四
九
一
七
六
三
二
##完成。
It might be for pedantic purposes but not homework. I have below question about 'Sorting a singly linked list' (Any kind of list for that matter) Assume for this questions we want to sort in ascending order of values in each node.
Does this question expect me to just sort the list by swapping the values of each node in the list so that the values are in some order(ascending/descending). Here the original values of nodes (before sorting) would be changed in order to reflect the sorted list. Here the same earlier head pointer is returned but now having the smallest element in it, which might be different than its earlier element.
Like this C code I have below(The code below might not compile as is , but I have it working fine. Posted here as illustrative to clear my point):
struct lnk_lst
{
int val;
struct lnk_lst *next;
};
main()
{
//Assume curr is the head node of the singly linked list created with some values
curr = llist_bubble_sort(curr);
}
struct lnk_lst* llist_bubble_sort(struct lnk_lst *lst)
{
int i,n=0,tmpint;
struct lnk_lst *tmp=lst,*tmp2=lst;
while(tmp->next)
{
lst = tmp2;
while(lst->next)
{
if(lst->val > lst->next->val)
{
tmpint = lst->val;
lst->val = lst->next->val;
lst->next->val = tmpint;
}
lst = lst->next;
}
tmp = tmp->next;
}
return tmp2;
}
OR
Is it expected to that the pointer to the node with the smallest element(assuming ascending order) in the original ordering is moved as new head node, then the node having the next smallest element is linked to the head node, and so on such that the list is reordered completely and now the head node returned is not same pointer as earlier.
If the interpretation of list sort is this second, then I have to see how yet get the idea done in code.
The whole idea behind linked lists is that the links can be changed without affecting the content. Changing a pointer sometimes involves creating a pointer to pointer variable. Also: if you only swap the contents, you could just as well leave out the ->next pointers, use an array instead, and swap the array's contents.
IMHO the natural way of sorting a linked list is mergesort. The fragment below splits the list in two part: the nodes that are already in place, and those that are not. The second list is sorted, and the two lists are merged. Both splitting&merging involve some pointer-to-pointer variables.
#include <stdio.h>
#include <string.h>
struct llist {
struct llist *next;
char *payload;
};
int llist_cmp(struct llist *l, struct llist *r);
struct llist * llist_split(struct llist **hnd
, int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_merge(struct llist *one, struct llist *two
, int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_sort(struct llist *ptr
, int (*cmp)(struct llist *l, struct llist *r) );
struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;
for (save=NULL, tail = &save; this = *hnd; ) {
if (! this->next) break;
if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
*tail = this->next;
this->next = this->next->next;
tail = &(*tail)->next;
*tail = NULL;
}
return save;
}
struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;
for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
if (cmp(one,two) <=0) { *tail = one; one=one->next; }
else { *tail = two; two=two->next; }
}
*tail = one ? one: two;
return result;
}
struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *save;
save=llist_split(&ptr, cmp);
if (!save) return ptr;
save = llist_sort(save, cmp);
return llist_merge(ptr, save, cmp);
}
int llist_cmp(struct llist *l, struct llist *r)
{
if (!l) return 1;
if (!r) return -1;
return strcmp(l->payload,r->payload);
}
struct llist lists[] =
{{ lists+1, "one" }
,{ lists+2, "two" }
,{ lists+3, "three" }
,{ lists+4, "four" }
,{ lists+5, "five" }
,{ lists+6, "six" }
,{ lists+7, "seven" }
,{ lists+8, "eight" }
,{ NULL, "nine" }
};
int main()
{
struct llist *root,*tmp;
root = lists;
fprintf(stdout, "## %s\n", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
fprintf(stdout, "%s\n", tmp->payload);
}
fprintf(stdout, "## %s\n", "sorting..." );
root = llist_sort(root, llist_cmp);
for (tmp=root; tmp; tmp=tmp->next) {
fprintf(stdout, "%s\n", tmp->payload);
}
fprintf(stdout, "## %s\n", "done." );
return 0;
}
RESULT:
## initial:
one
two
three
four
five
six
seven
eight
nine
## sorting...
eight
five
four
nine
one
seven
six
three
two
## done.
这篇关于当我被告知“排序单链接列表”时，预期的是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
