[CS 0]アルゴリズム-線形検索

せんけいたんさく
学習目標
線形検索は、指定された配列または構造体で行うことができます.
キーワード

線形探索

構造体

せんけいたんさく
検索する資料を検索するアルゴリズムはいくつかあります.1つは線形検索です.
必要な要素が見つかるまで、線形検索は最初から最後まで順次検索されます.
このように、線形検索では、探している資料が見つかるまですべての資料をチェックする必要があります.
能率が低い
線形探索アルゴリズムは正確で非効率な方法である.
配列の長さがnの場合、最悪の場合、配列内のすべての要素をチェックする必要があるため、n回実行します.
ここで最悪なのは、検索したい資料が最後にあるかリストにない場合です.
逆に、一番いいのは、最初の試みで探したい値があることです.
平均すると、線形検索は最悪の場合に終了/
線形検索は、データがソートされていない場合や、情報が1つずつ検索する必要がない場合に役立ちます.
この場合、ランダムナビゲーションよりも順次ナビゲーションの方が効率的です.
なぜ以前に検索前にソートしたのかがわかります.
ソートに時間がかかり、より多くのスペースが消費されます.
ただし、配列を複数回検索する必要がある場合や、非常に大きな配列を検索する必要がある場合は、時間を短縮できます.
線形検索を使用して特定の配列で特定の値を検索する場合は、次のコードを記述できます.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
  // numbers 배열 정의 및 값 입력
  int numbers[] = {4,8,15,16,23,42};

  // 값 50 검색
  for (int i = 0; i < 6; i++)
  {
    if (numbers[i] == 50)
      {
        printf("Found\n");
        return 0;
      }
  }
  printf("Not found\n");
  return 1;
}

配列のサイズに従ってループし、配列のインデックスに順次アクセスし、検索する値があるかどうかを確認します.
文字列からなる配列も同様に検索できます.
電話帳で特定の名前を検索し、対応する電話番号を印刷するプログラムを作成する場合は、どうすればいいですか?
最も簡単な例は以下のプログラムです.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

namesバックグラウンドとnumbers配列をそれぞれ定義し、names配列で検索し、対応するインデックスのnumbers配列値を出力します.
ただし、この場合、names配列とnumbers配列は同じインデックスを持つ必要があります.
より良い方法は、次のコードのように、新しい資料型で構造体を定義し、その名前と番号を組み合わせることです.

#include <cs50.h>
#include <stdio.h>
#indlude <string.h>

typedef struct
{
  string name;
  string number;
}
person;

int main(void)
{
    person people[4];

    people[0].name = "EMMA";
    people[0].number = "617–555–0100";
    people[1].name = "RODRIGO";
    people[1].number = "617–555–0101";
    people[2].name = "BRIAN";
    people[2].number = "617–555–0102";
    people[3].name = "DAVID";
    people[3].number = "617–555–0103";

    // EMMA 검색
    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

personという名前の構造体を資料型として定義し、.に接続してアクセスできるperson資料型の配置を宣言します.
person a; 変数がであれば、a.nameまたはa.numberはそれぞれ名前と電話番号を格納する変数となる.
これにより、より拡張性のある電話帳検索プログラムを作成できます.