-1

最小から最大の順に int を格納するタイプのリンク リストを作成する必要があります。リンクされたリストの並べ替え関数を持っているか、作成する方法を知っている場合は、ここでオフになっていることを示してください。また、C++ でコーディングする方法を教えてください。

4

3 に答える 3

3

私はしばしばインデックス ポインター リストを介してリンクされたリストを並べ替えます。1 つを構築するには、ノード数 (N) * ノード ポインターのサイズに相当するメモリ割り当てが必要です。コンセプトは至ってシンプル。

注: このアルゴリズムは C です。OP がこれを C++ の質問として分類することを意図しているかどうかは完全にはわかりませんでした (C++ でリンクされたリストを自由に使用できる標準コンテナーを使用するのは誰ですか??)

  1. リスト内のノードの数 (N) を決定する
  2. N ノードポインターのポインター配列を割り当てます。
  3. リスト内のすべてのノード ポインターを使用してポインター配列を読み込みます。つまり、リストをたどって、ポインター配列の各スロットにポインターを置き、進むにつれてインクリメントします。
  4. このノード ポインタ配列をソート アルゴリズムに送信します (ランタイム ライブラリqsort()が標準装備されているので気に入っています)。
  5. ソート後、ポインター配列全体 (少ない方) をウォークし、各ノードの「次の」ポインターが次のポインターを指すように設定します。最後のものは、その「次の」ポインタを NULL に設定します。
  6. ヘッド ポインターをポインター配列の最初のポインター [0] に設定します。
  7. ポインタ配列のメモリを解放します

リンクされたリストが並べ替えられました。

ノードが次のようなものであると仮定します。

struct node
{
   ..data fields..
   int keyField;  // << determines sort order
   struct node *next;
};

リスト内のノードの数を決定します。私はあなたがこれを行うことができるprocを持っていると仮定していますが、これは簡単です:

size_t list_count(struct node* head)
{
   size_t count = 0;
   while (head)
   {
      ++count;
      head = head->next;
   }
   return count;
}

リストのサイズのポインター配列を割り当てます。ここで、nItems は 1 より大きいリスト ノード カウントです (長さが 0 または 1 のリストを気にする意味はありません)。

struct node **ptrs = malloc(sizeof(*ptrs)*nItems);

リスト内のすべての項目をポインター配列に入力します。

struct node *ptr = head;
size_t i=0;
for (;i<nItems;++i,ptr = ptr->next)
    ptrs[i] = ptr;

qsort()適切な比較機能を使用して、これを に送信します。keyField構造体の に基づいてソートする比較関数の例を以下に示します。

int compare_node_ptrs(const void* left, const void* right)
{
    struct node *l = *(struct node**)left;
    struct node *r = *(struct node**)right;
    return l->keyField - r->keyField;
}

qsort() を呼び出すと、次のようになります。

qsort(ptrs, nItems, sizeof(*ptrs), compare_node_ptrs);

リスト全体を見てみましょう。「次の」ポインタの再配線:

for (i=0;i<(nItems-2);++i)
    ptrs[i]->next = ptrs[i+1];
ptrs[nItems-1] = NULL;

ヘッドポインタを再配線します。

head = ptrs[0];

最後に、ポインター配列を解放します。

free(ptrs);

リンクされたリストが並べ替えられました。

サイドバーのマージソートは、私が知っている唯一の O(nlogn) アルゴリズムであり、追加のスペース要件なしでリンクされたリストをソートできます。次のプロトタイプを作成する一般的なソリューションは、ナッツになります。

mergesort_list(void **head, size_t offset_ptr, int(*comp)(void*,void*))

head: address of the head pointer.
offset_ptr: offset in bytes from a node ptr where the 'link' pointer can be found.
comp: comparison function.
于 2012-11-15T23:36:14.847 に答える
2

単純にコードを見せれば、あなたに大きな損害を与えることになります。代わりに、2 つの異なるアプローチを紹介します。好きな方を実装してください。

最初のアプローチは、挿入するときに「ソート」することです。値、たとえば 7 を挿入するときは、リストの最初のエントリから始めて、ノードがなくなるまで次の手順に従います。

調べているノードの値が 7 より大きい場合は、調べているノードの前に新しいノードを挿入して返します。それ以外の場合は、次のノードを調べます。次のノードがない場合は、. リストの最後に新しいノードを挿入します。これは、7 がリスト内の他のすべてのエントリよりも大きく、戻ることを意味するためです。

2 番目の方法は、多くのソート アルゴリズムの 1 つを使用してリスト全体をソートすることです。理解しやすく実装しやすい BubbleSort を使用することをお勧めします。ウィキペディアでバブルソート (および他の多くのソートアルゴリズム) について詳しく読むことができます。

于 2012-11-15T23:23:47.523 に答える
1

古き良きクイックソートがそのトリックを行います (C++03 フレンドリー):

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>

using namespace std;

void qsort(list<int>::iterator first, list<int>::iterator last)
{
    if (distance(first, last) < 2)
        return;
    int pivot = *first;

    list<int>::iterator it = partition(first, last, bind2nd(less<int>(), pivot));

    qsort(first, it);
    qsort(it, last);
}

int main()
{
    std::list<int> l;
    l.push_back(5);
    l.push_back(4);
    l.push_back(1);
    l.push_back(10);
    l.push_back(3);
    l.push_back(6);
    l.push_back(7);

    cout << "List:";
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " "));
    cout << endl;

    qsort(l.begin(), l.end());

    cout << "Sorted list:";
    copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, " "));
    cout << endl;
    return 0;
}

チェック: http://ideone.com/OOGXSp

于 2012-11-15T23:40:47.613 に答える