Cでリンクリストをソートする（選択ソート）

Question

リンクリストをソートするとき、直接値をスワップする、または次のポインタのアドレスを変更するときの方が良いでしょう。

私はswaping値技法を使用して多くの例に出くわしたが、どれアドレス変更メカニズムを使用していない

メソッドを使用：選択ソート

ポインタ

のアドレスを変更介して、それを実行する方法があります

Answer 1

リンクリストは、通常、ポインタに基づいてスワップされます。これは、各要素がスワップするには大きすぎる可能性があり、リンクされたリストの要素がオーバーロードされることがあるためです。例えば

：

struct myelement 
{ 
    linked_list ll; 
    lot_of_data; 
} 

ポインタを入れ替えるには、そこにサイズを知るwhitout聖霊降臨祭のリンクリストを、オーバーロードされている要素のいずれかのタイプを交換することができます。

Answer 2

まあ、それが可能だ：

struct node { 
int val; 
struct node *next; 
}; 

void sort(struct node **list) { 
if (!*list) return; 
struct node **minadr=list,*cur=*list; 
int min=(*list)->val; 
while (cur) { 
    if (cur->val<min) { 
    min=cur->val; 
    minadr=&(cur->next); 
    } 
    cur=cur->next; 
} 
if (minadr!=list) { 
    cur=*minadr; 
    *minadr=*list; 
    *list=cur; 
} 
sort(&((*list)->next)); 
} 

Answer 3

ポインタをスワップは常に望ましいです。その理由は、リンクされたリストでは、データ構造には任意のデータと、必要に応じて次のノードへのポインタが含まれているからです。したがって、スワップでは、ポインタとデータをコピーするよりも、ポインタのみをコピーする方が効率的です。

Answer 4

実際の値を入れ替えることもできます。しかし、リストが巨大である場合や、各ノードに多くのフィールドがある場合は、特にリストが崩れる可能性があります。いくつかのフィールドを交換し、残りの部分を変更せずに矛盾を引き起こす可能性があります。そのすべてのことを避けるためにノードへのポインタを使用する方が良いし、asaelrが提案したようにかなり簡単です。