3

私はプログラミングを始めたばかりで、現在 C を学んでいます。この問題に 1 週​​間取り組んでいますが、ロジックをまっすぐに理解できないようです。これは私が使用している本から直接です：

文字列の配列を使用して次の名前を格納するプログラムを作成します。

  • 「フロリダ」
  • "オレゴン"
  • 「カリフォルニア」
  • 「ジョージア」

上記の文字列配列を使用して、関数sort()を使用して各州の名前をアルファベット順に表示する独自の関数を作成しますstrcmp()。

だから、私が持っているとしましょう：

char *statesArray[4] = {"Florida", "Oregon", "California", "Georgia"};

のように for ループをネストする必要がありますstrcmp(string[x], string[y])...か? 私はハッキングしてハッキングしました。これをいくらか効率的に解決するために必要なアルゴリズムに頭を悩ませることはできません。どうもありがとうございました!!!

4

6 に答える 6

6

配列を並べ替える必要があると想像してください。カードに書かれた各状態を考えてみてください。どのように並べ替えますか。それを行うには多くの方法があります。一つ一つをアルゴリズムと呼ぶ

1 つの方法は、すべてのカードを見て最初の状態を見つけ、これまでに見た最も低い状態を頭の中で追跡することです。各カードを見た後、最も低いカードが表示されます。それを新しい山に入れます。今繰り返します - あなたが残したものの中で最も低いものを見つけようとしています.

元の山にカードがなくなるまで繰り返します

これはよく知られているシンプルですが遅いアルゴリズムです。それは私が最初にやるだろう

他にもあります

于 2013-08-23T17:44:58.723 に答える
5

はい、ネストされた for ループを使用して並べ替えることができます。strcmp() がどのように機能するかを理解すれば、かなり簡単です。

strcmp(char *string1, char *string2)

  • 戻り値が の< 0場合、それstring1はより小さいことを示しますstring2

  • 戻り値が の> 0場合、それstring2はより小さいことを示しますstring1

  • 戻り値が次の場合は、等しい= 0ことを示しますstring1string2

この時点から、任意の並べ替え方法を 1 回選択できます。

このサイトには、実行されているさまざまな種類の優れたグラフィカルな例がたくさんあり、特定のアルゴリズムの疑似コードが含まれています。

于 2013-08-23T17:43:56.790 に答える
4

「任意の」並べ替えアルゴリズム、または「効率的な」並べ替えアルゴリズムが必要ですか?

簡単にするために、簡単ではあるが効率的ではないソート アルゴリズムを実装する方法を紹介します。そのdouble for方法です!! 次に、同じアイデアで、他の効率的なアルゴリズム (シェルやクイックソートなど) に変更できます。

数値の場合、次のように配列を順番に並べることができます (おそらくご存じのとおり)。

int intcmp(int a, int b) {
    return (a < b)? -1: ((a > b)? +1: 0);
}

int main(void) {
   int a[5] = {3, 4, 22, -13, 9};

   for (int i = 0; i < 5; i++) {
      for (int j = i+1; j < 5; j++)
         if (intcmp(a[i], a[j]) > 0) {
            int temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp; 
         }
       printf("%d ", a[i]);
   }
}

現在変更されている唯一のことは、整数の代わりに文字列があることです。したがって、文字列の配列を考慮する必要があります。

 char *a[] = {"Florida", "Oregon", "Califoria", "Georgia"};

temp次に、 の型をに変更する必要がありchar*、
最後に のstrcmp()代わりに関数を配置しますintcmp()。

この関数strcmp(s1, s2)(< string.h > から) は、s1 が s2 より「小さい」文字列の場合は < 0 を返し、s1 が s2 と「等しい」場合は == 0 を返し、それ以外の場合は > 1 を返します。

プログラムは次のようになります。

#include <stdio.h>
#include <string.h>
int main(void) {
   char *a[] = {"Florida", "Oregon", "Califoria", "Georgia"};

   for (int i = 0; i < 4; i++) {
      for (int j = i+1; j < 4; j++)
         if (strcmp(a[i], a[j]) > 0) {
            char* temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp; 
         }
       printf("%s ", a[i]);
     }
   getchar();
   return 0;  
}

printf()文については、文字列を適切に表示するために , に 変更"%d "したことに注意してください。"%s "

最後のコメント:クイック ソートのようなより良いアルゴリズムをプログラムする場合、比較するデータの種類に関係なく、アルゴリズムは同じであるため、比較関数を変更するだけで十分です。

注意：私は「トリッキーな」方法を使用しました。ご覧のとおり、変数を string へのポインターaとして。初期化子は文字列の定数配列を取得し、それを使用して変数を初期化しました。変数は、正確に 4 つの文字列へのポインターの配列として安全に処理およびインデックス付けできるようになりました。 これが、「スワップ」が double-for アルゴリズムで正常に機能する理由です。文字列 全体ではなく、メモリ アドレスがスワップされます。aa

于 2013-08-23T20:11:01.117 に答える
3

次の手順を実行する必要があります。

  1. 状態名を配列に入力する
  2. 配列内の 2 つの状態を入れ替えるメソッドを作成する
  3. この時点で、strcmp を使用して選択した並べ替えアルゴリズムを実装するために必要なすべてのツールが揃っています。

ほとんどのソート方法は、2 つのことに依存しています。

  1. リストを並べ替えることができる (つまり、スワップ)
  2. リスト内のアイテムを比較して、交換する必要があるかどうかを確認できる

私はこれら2つのことを正しく機能させることに取り組み、残りは特定のソートアルゴリズムを学習するだけです

于 2013-08-23T17:36:48.350 に答える
1

少し面倒な問題に注意してください。文字列は ASCII 数値表現でソートされるため、このようにアルファベット順にソートすると、大文字が小文字の前に来ます。たとえば、「alpha」、「beta」、「gamma」、「Theta」は次のようになります。並べ替え: シータ、アルファ、ベータ、ガンマ

于 2014-05-03T13:14:45.167 に答える
0

ここにリストしたサンプル配列に関しては、前述の単純なアルゴリズムが実際に最も効率的である可能性があります。私が参照しているアルゴリズムは、最初の要素から始めて、それを他の要素と比較し、見つけた最小のもので置き換えてから、次の要素に移動して同じことを行うアルゴリズムです。既にソートされているものと比較しないでください。要素。

このアルゴリズムの実行時間は O(n^2) です。ここで、n は配列内の要素の数です。通常、小さい配列の場合、クイック ソート (実行時間 O(n*log(n))) などよりも高速になります。その理由は、クイック ソートのオーバーヘッドが大きいためです。大きい配列の場合、クイック ソートは他の方法よりも優れています。別の回答では「ダブルフォー」と言及されていますが、メモリが正しく機能する場合、これは置換ソートと呼ばれます。

于 2013-08-23T20:33:06.173 に答える