1

キーボードまたはファイルを介して単語を入力すると、単語が長さでソートされるプログラムを作成しています。単語の長さと数が固定されていないため、連結リストを使用するように言われました。

リンクされたリストを使用して単語を表す必要がありますか?

struct node{
    char c;
    struct node *next;
};

そして、どのようにqsortを使用して単語を長さでソートできますか? qsort は配列で動作しませんか?

私はプログラミングにかなり慣れていません。

ありがとうございました。

4

5 に答える 5

3

あなたが選ぶべきソートアルゴリズムよりも大きな問題があると思います。1 つ目は、定義している構造体が実際には単語のリストではなく、1 文字 (または 1 つの単語) のリストを保持することです。C の文字列は、null で終わる文字の配列として表されます。 、次のようにレイアウトされています。

| A | n | t | h | o | n | y | \0 |

この配列は、理想的には char[8] として宣言されます。文字ごとに 1 つのスロットと、ヌル バイト用の 1 つのスロット (文字通り、メモリ内のゼロの 1 バイト)。

おそらくこれを知っていると思いますが、明確にするためにこれを指摘する価値があります。配列を操作する場合、一度に複数のバイトを調べて速度を上げることができます。リンクされたリストを使用すると、真に直線的な時間でのみ物事を見ることができます。つまり、ある文字から次の文字へと進みます。これは、文字列に対して何かをすばやく実行しようとしている場合に重要です。

この情報を保持するためのより適切な方法は、非常に C に似たスタイルであり、C++ でvectorとして使用されます: malloc と realloc を使用して連続したメモリのブロックを自動的にサイズ変更します。

まず、次のような構造体をセットアップします。

struct sstring {
    char *data;
    int logLen;
    int allocLen;
};
typedef struct string sstring;

そして、これらのためにいくつかの機能を提供します:

// mallocs a block of memory and holds its length in allocLen
string_create(string* input); 

// inserts a string and moves up the null character
// if running out of space, (logLen == allocLen), realloc 2x as much
string_addchar(string* input, char c);

string_delete(string* input);

scanf を使用して簡単なバッファに読み込むことができないため、これは素晴らしいことではありませんが、getchar() のような関数を使用して単一の文字を取得し、string_addchar() を使用してそれらを文字列に配置して、使用を避けることができます。リンクされたリスト。文字列は可能な限り再割り当てを回避し、2^n 挿入ごとに 1 回だけで、C 文字列ライブラリから文字列関数を引き続き使用できます!! これは、ソートの実装に大いに役立ちます。

では、これで実際にソートを実装するにはどうすればよいでしょうか。同様の方法で文字列全体を保持することを目的とした同様の型を作成し、必要に応じて拡張して、コンソールからの入力文字列を保持できます。いずれにせよ、すべてのデータは配列としてアクセスできる連続したメモリ ブロックに存在するようになりました。これは配列であるためです。たとえば、次のようになったとします。

struct stringarray {
    string *data;
    int logLen;
    int allocLen;
};
typedef struct stringarray cVector;
cVector myData;

以前と同様の機能: 作成、削除、挿入。

ここで重要なのは、string.data 要素で strcmp() を使用してソート関数を実装できることです。これは C 文字列に過ぎないためです。関数ポインターを使用する qsort の組み込み実装があるため、これらの型で使用するために strcmp() をラップし、アドレスを渡すだけです。

于 2009-04-25T23:35:09.137 に答える
1

アイテムをどのように並べ替えるかがわかっている場合は、データを読み取るときに挿入並べ替えを使用して、すべての入力が入力されたら、出力を書き込むだけでよいようにする必要があります。リンクされたリストを使用しても問題ありませんが、O(N 2 ) のパフォーマンスがあることがわかります。長さ順に並べられたバイナリ ツリーに入力を格納すると (バランスのとれたツリーが最適です)、アルゴリズムのパフォーマンスは O(NlogN) になります。一度だけ行う場合は、効率よりも実装の単純さを優先してください。

擬似コード:

  list = new list
  read line
  while not end of file
      len = length(line)
      elem = head(list)
      while (len > length(elem->value))
          elem = elem->next
      end
      insert line in list before elem
      read line
  end

 // at this point the list's elements are sorted from shortest to longest
 // so just write it out in order
 elem = head(list)
 while (elem != null)
     output elem->value
     elem = elem->next
 end
于 2009-04-25T23:22:15.377 に答える
0

それを処理する方法はたくさんあります...試してみる勇気があれば、動的メモリ割り当てを介してreallocで配列を使用できます。

ただし、qsort の標準実装では、各要素を固定長にする必要があります。つまり、文字列へのポインタの配列を持つことになります。

ただし、リンクされたリストの実装は、ポインターへのポインターを使用する場合に比べて簡単なはずです。

あなたがするように言われたのは、文字列をリストとして保存しないことだったと思います。しかし、リンクされたリストでは:

struct node {
    char *string;
    node *next;
}

次に、文字列を読み取るたびに、新しいノードをリストの順序付けられた場所に追加するだけです。(現在の文字列の長さが今読んだ文字列よりも長くなるまで、リストをたどります。)

単語が固定長ではないという問題は一般的であり、通常は世界を一時的にバッファに格納し、それを適切な長さの配列にコピーすることで処理されます (もちろん、動的に割り当てられます)。

編集：

擬似コード:

array = malloc(sizeof(*char))
array_size = 1
array_count = 0

while (buffer = read != EOF):
    if(array_count == array_size)
        realloc(array, array_size * 2)
    array_count++
    sring_temp = malloc(strlen(buffer))
    array[array_count] = string_temp

qsort(array, array_count, sizeof(*char), comparison)

print array

もちろん、それにはかなりの磨きが必要です。array は typechar **arrayであることに注意してください。つまり、「char へのポインターへのポインター」 (ポインターの配列として処理します)。ポインターを渡しているため、バッファーを配列に渡すことはできません。

于 2009-04-25T23:30:32.223 に答える
0

はい、古典的な「C」ライブラリ関数 qsort() は配列に対してのみ機能します。これは、メモリ内の連続した値のコレクションです。

Tvanfosson のアドバイスは非常に優れています。連結リストを作成すると、正しい位置に要素を挿入できます。そうすれば、リストは常にソートされます。

リンクされたリストを使用するように言われたというあなたのコメントは興味深いと思います。実際、リストは多くの場合に使用できる優れたデータ構造ですが、欠点もあります。たとえば、要素を見つけるにはトラバースする必要があります。

アプリケーションによっては、ハッシュ テーブルを使用したい場合があります。C++ では、hash_set または hash_map を使用できます。

基本的なデータ構造の学習に時間を費やすことをお勧めします。ここで過ごす時間は、「リンクされたリストを使用する」などのアドバイスを評価するためのサーバーになります。

于 2009-04-25T23:31:43.700 に答える
0

リスト要素ごとに 1 つのポインターの配列を割り当てることによって、リンクされたリストを並べ替えます。

次に、その配列を並べ替えます。比較関数では、もちろんリスト要素へのポインターを受け取ります。

これにより、ポインタのソートされたリストが得られます。

次に、ポインターの配列をトラバースし、各要素を順番に調整することで、リストをトラバースします。リスト内の順序を並べ替えて、ポインタの配列の順序に一致させます。

于 2009-04-26T07:43:04.473 に答える