データ構造とアルゴリズム入門

私はできるだけ初心者フレンドリーなこのチュートリアルを作成したい.あなたが何かを理解していないならば、コメントで私に尋ねてください.私はこのチュートリアルのためにCとC +を使用します.それで、私はあなたがそれぞれこの言語の基礎を知っていることを期待します.私はあなたがそれを読むことができるCのブログを書きました.
DSAに深いダイビングの前にこれらの条件で我々の基礎を片づけましょう.データ構造とアルゴリズムは2つの異なるものです.
データ構造-これらは、効率的なアルゴリズムを構築するために必要な成分のようです.これらはデータ(主にメモリにデータを使用できるように)を配置する方法です.Ex :配列、スタック、リンクリスト、および多く.
アルゴリズムは、データの効率的なデータ構造を使用して与えられた問題を解決するために実行される手順のシーケンスは、基本的なまたは実際の生活ベースの1つである.:配列をソートする.
その他重要な用語
データベース-高速検索とupdeationのための永久記憶の情報の収集.例:MySQL、MongoDBなど.
データウェアハウス-優れた分析のためにレガシーデータの膨大なデータの管理(データベース内の我々の新鮮なデータから別の場所に検索し、高速化のプロセスを作るデータ)の管理.
大きいデータ－あまりに大きいか複雑なデータ(それは伝統的なデータ処理アプリケーションに対処することができない)の分析.
Cプログラムのメモリレイアウト
プログラムが起動すると、そのコードがメインメモリにコピーされます.
スタックは、関数が占有するメモリを保持する.プログラムで使用する関数の活性化レコードを格納します.を実行します.
ヒープは、ポインタを使用して動的メモリとしてプログラムによって要求されるデータを含んでいる.
初期化されて初期化されていないデータセグメントはそれぞれ初期化され初期化されたグローバル変数を保持します.

いくつかのアルゴリズム例

ビッグO表記
大きいO表記法は、アルゴリズムの性能または複雑さを記述するためにコンピューターサイエンスで使われます.BIG - Oは特に最悪のシナリオを記述し、必要な実行時間や、使用しているスペース(例えば、メモリやディスク上の)をアルゴリズムで記述するために使用することができます.

O ( 1 )

void printFirstElementOfArray(int arr[])
{
    printf("First element of array = %d",arr[0]);
}

この関数は、入力に対してo ( 1 ) time (または"time time ")で実行されます.入力配列は1アイテムまたは1000アイテムであるかもしれません、しかし、この機能はまだ1つのステップを必要とするでしょう.

O ( n )

void printAllElementOfArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", arr[i]);
    }
}

この関数はo ( n ) time (または"linear time ")で実行されます.ここでNは配列の項目数です.配列が10の項目を持っているなら、私たちは10回印刷しなければなりません.1000品目なら1000回印刷しなければならない.

O ( N 2 )

void printAllPossibleOrderedPairs(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            printf("%d = %d\n", arr[i], arr[j]);
        }
     }
}

ここでは2つのループを入れ子にしています.もし我々の配列がn個の項目を持っていれば、外側のループはN回実行され、外側のループの繰り返しごとに内側のループがN倍になります.したがって、この関数はO(N 2)時間(または“二次時間”)で実行される.配列が10の項目を持っているなら、私たちは100回印刷しなければなりません.1000の項目があれば、100000回印刷する必要があります.

データ構造
連結リスト:
リンクリストは、一連の接続されたノードを含む線形データ構造である.ここで、各ノードは次のノードのデータとアドレスを記憶する.例えば、

あなたはどこかを開始する必要がありますので、我々は最初のノードのアドレスを頭と呼ばれる特別な名前を与える.また、次の部分がNULLになっているので、リンクリストの最後のノードを識別できます.
リンクリストは、複数のタイプをすることができます:シングル、二重、および円形のリンクリスト.この記事では、シングルリンクリストに焦点を当てます.
連結リストの表示
リンクされたリストの各々のノードがどのように表されるかについて見ましょう.各ノードは以下の通りである:
データ項目
他のノードのアドレス
データ項目と次のノード参照の両方を構造体でラップします.

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

各structノードには、データ項目と別の構造体ノードへのポインターがあります.どのように動作するかを理解するために、3つの項目を持つ簡単なリンクリストを作成しましょう.

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

リンクリストの力は、チェーンを中断し、それを再結合する能力から来ている.例えば、1と2の間に要素4を入れたいならば、手順は以下のようになります.
-新しいstructノードを作成し、メモリに割り当てます.
-データ値を4として追加する
-データ値として2を含むstructノードへの次のポインタを指し示す
- 1の次のポインタを作成したノードに変更します.
-配列で同じようなことをするには、
-以降のすべての要素の位置を移動する.
バイナリ検索ツリー:
バイナリ検索ツリーはすぐに私たちの番号のソートリストを維持することができますデータ構造です.
それぞれの木のノードが2人の子供の最大を持つので、それは二分木と呼ばれています.
それはo(log(n))時間の数の存在を捜すのに使用できるので、検索木と呼ばれています.
正規のバイナリツリーからバイナリ検索ツリーを分離するプロパティ
左側のサブツリーのすべてのノードは
右のサブツリーのすべてのノードは
各ノードの両方のサブツリーもbstsです.すなわち、上記の2つのプロパティがあります.

ノード“3”の右のサブツリーがそれより小さい値を含んでいるので、右側の2進木はバイナリ探索木でありません.
キーの検索
値を検索するために、ソートされた配列があれば、バイナリ検索を行うことができました.配列内の数を検索したい場合は、バイナリ検索で、最初に完全なリストを検索スペースとして定義します.ここで検索対象の検索回数や検索対象の中央要素(中央値)で検索する要素を比較し、検索されたレコードが中間要素より小さい場合は左半分で検索し、右半分で検索します.バイナリ検索では、' n '要素を検索空間で開始し、Mid要素が探している要素でない場合は、検索スペースを' n/2 'に減らします.探索空間を縮小しています.

// C function to search a given key in a given BST
struct node* search(struct node* root, int key)
{
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->key == key)
    return root;

    // Key is greater than root's key
    if (root->key < key)
    return search(root->right, key);

    // Key is smaller than root's key
    return search(root->left, key);
}

ツリーの下に6を検索するイラスト

ルートからスタートします.

根より小さい場合、検索要素をルートと比較し、再帰的に左のサブツリーを呼び出します.そうでなければ再帰的に右のサブツリーを呼び出します.

検索する要素がどこでも見つかった場合、trueを返します.

キーの挿入
新しいキーは常に葉に挿入されます.リーフノードを押すまで、キーからルートを検索し始めます.リーフノードが見つかったら、新しいノードを葉ノードの子として追加します.

// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;

class BST {
    int data;
    BST *left, *right;

public:
    // Default constructor.
    BST();

    // Parameterized constructor.
    BST(int);

    // Insert function.
    BST* Insert(BST*, int);

    // Inorder traversal.
    void Inorder(BST*);
};

// Default Constructor definition.
BST ::BST()
    : data(0)
    , left(NULL)
    , right(NULL)
{
}

// Parameterized Constructor definition.
BST ::BST(int value)
{
    data = value;
    left = right = NULL;
}

// Insert function definition.
BST* BST ::Insert(BST* root, int value)
{
    if (!root) {
        // Insert the first node, if root is NULL.
        return new BST(value);
    }

    // Insert data.
    if (value > root->data) {
        // Insert right node data, if the 'value'
        // to be inserted is greater than 'root' node data.

        // Process right nodes.
        root->right = Insert(root->right, value);
    }
    else {
        // Insert left node data, if the 'value'
        // to be inserted is greater than 'root' node data.

        // Process left nodes.
        root->left = Insert(root->left, value);
    }

    // Return 'root' node, after insertion.
    return root;
}

// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
    if (!root) {
        return;
    }
    Inorder(root->left);
    cout << root->data << endl;
    Inorder(root->right);
}

// Driver code
int main()
{
    BST b, *root = NULL;
    root = b.Insert(root, 50);
    b.Insert(root, 30);
    b.Insert(root, 20);
    b.Insert(root, 40);
    b.Insert(root, 70);
    b.Insert(root, 60);
    b.Insert(root, 80);

    b.Inorder(root);
    return 0;
}

出力:
20
30
40
50
60
70
80

配列

C/C++の配列、または任意のプログラミング言語では、隣接するメモリの場所に格納されている類似のデータ項目のコレクションであり、要素は配列のインデックスを使用してランダムにアクセスすることができます.これらは、int、float、double、charなどの基本的なデータ型のコレクションを格納するために使用できます.これを追加するには、C/C++の配列が構造体やポインタなどの派生データ型を格納できます.以下に示す配列は、配列の画像表現です.
配列を宣言できるさまざまな方法があります.これは、その型またはサイズを指定することによって行うことができます.
サイズ指定による配列宣言

//C code below
// Array declaration by specifying size
int arr1[10];

// With recent C/C++ versions, we can also
// declare an array of user specified size
int n = 10;
int arr2[n];

// Array declaration by initializing elements
int arr[] = { 10, 20, 30, 40 }

// Compiler creates an array of size 4.
// above is same as "int arr[4] = {10, 20, 30, 40}"

サイズを指定し、要素を初期化することによる配列宣言

// Array declaration by specifying size and initializing
// elements
int arr[6] = { 10, 20, 30, 40 }

// Compiler creates an array of size 6, initializes first
// 4 elements as specified by user and rest two elements as
// 0. above is same as "int arr[] = {10, 20, 30, 40, 0, 0}"

C/C++の配列の利点
-配列インデックスを使用した要素のランダムアクセス.
-コードの少ない行を使用して、複数の要素の配列を作成します.
すべての要素に-簡単にアクセスできます.
-配列を通る横断は、単一のループを使用して簡単になります.
-並べ替えは、コードの少ない行を書くことによって達成できます.
//////////////

読書ありがとう!
今日は新しい何かを学びました
乾杯!