22.03.18資料構造

データ構造は、コンピュータのメモリをより効率的に管理するために再定義された構造です。

malloc & pointer

int main(void)
{
    int *x;
    int *y;

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;
}

pointer xにはmalloc(sizeof(int))メモリアドレス(空間)が割り当てられている.

pointer yにスペースが割り当てられていません.

pointer xが指す点記憶42、pointer yが指す点記憶13であるが、yは指す点を定義していない.

これにより、初期化されていないpointer yは任意の空間を指し、13という値を格納し、エラーを引き起こす可能性がある.

ごみの値があることを示します.

realloc

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // tmp 포인터에 메모리를 할당하고 list의 값 복사
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 list의 네 번째 값 저장
    list[3] = 4;

    // list의 값 확인
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    //list 의 메모리 초기화
    free(list);
}

既存のメモリに割り当てるサイズを調整する場合はreallocを使用します.

パラメータに変更するポインタとメモリサイズを渡します.

reallocを使用してメモリサイズを再設定する場合は、変更前にメモリを初期化する必要はありませんが、変更後のメモリは初期化する必要があります.

接続リスト

資料構造とは、プログラミング構造にすぎない.

データ構造により、コンピュータメモリに異なる方法で情報を格納できます.

struct:新しいタイプを設定する

:アクセス属性値(person.name->アクセスpersonタイプのname属性)

*:逆参照演算子.メモリブロックとしてアクセスするストレージ値を呼び出す

array(配列):値を保存するためのリスト.欠点:固定メモリブロック配列のサイズを調整してより多くの値を収容する場合は、より多くのメモリを割り当てる必要があります->O(n)/利点:[]を使用してインデックスを簡単に作成できます.早く.バイナリナビゲーションなどに適しています.インデックス値はメモリに連続的に格納されます.

接続リスト:これらの値のリストを保存する方法.独自の値を使用して、次の値のアドレス(ポインタ)を格納します.サイズを増やして数字を追加したり、既存の値を移動したりする手間を省きます.住所さえ指定すればいいから!Dynamic! 既存のものを移動しなくても、リストを増やすことができます./欠点:ランダムアクセスできない(中間値に直接アクセスできない)->バイナリブラウズできない->O(n)

自己値+以下の値のアドレス(ポインタ)=を「ノード」と呼びます.

次の値がない場合は、NULL(0 x 0)を次の値のアドレスとして保存します.

typedef struct node  // 2. 구조체 정의 시 node라는 단어를 설정해주었다.
{
    int number;
    struct node *next;  // 1. node를 내부에서도 사용하기 위해,
}
node;

接続リストは次のように定義できます.number:nodeが有する値/*next:次のnodeを指すポインタ

(*n).number = 2; // n의 메모리의 값의 number 속성에 2를 저장함.
n->number = 2; 로 바꿔서 사용 가능

#include <stdio.h>
#include <stdlib.h>

// Represents a node
typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    // List of size 0
    node *list = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 1;
    n->next = NULL;
    list = n;  // Pointing at new node (첫 번째 node의 주소)

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->next = NULL;
    list->next = n;  // list가 첫번째 node를 가리키고 있었으므로, 그 것의 next는 두 번째 node를 가리킨다.

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 3;
    n->next = NULL;
    list->next->next = n;  // list->next가 두번째 node를 가리키고 있었으므로, 그 것의 next는 세 번째 node를 가리킨다.

    // Print list
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);  // tmp가 가리키는 number 필드의 숫자를 출력
    }

    // Free list
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

今回の内容の理解にも時間がかかりました.私のlist->next->next->next-...この部分はあまりにも理解できないからです.アドレスの内容について、Pythonで簡単にコーディングを始めた私にとって、確かにとても難しい内容でした.これから慣れるので、なんとかして解決しました.

ポインタ

listの最初のノードのアドレスを指定し、最初のノードを指します.

list->nextは、第1のノードへのnext値、すなわち第2のノードへのポインタとなる.ここに2番目のノードのアドレスを割り当てます.

list->next->nextは、3番目のノードへのポインタとなる.やれやれCは難しすぎる

Binary search trees

各ノードの接続は2 Dです

ルートノード、サブノードとして構成

バイナリ検索を実行してノードを挿入するときの遊離:O(logn)

//이진 검색 트리의 노드 구조체
typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
} node;

// 이진 검색 함수 (node *은 이진 검색 트리를 가리키는 포인터. 변수로 tree 할당)
bool search(node *tree)  // 주소를 argument로 받고 bool 값을 반환하는 함수
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);  // 왼쪽 노드의 주소를 search 함수에 넘겨줌
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);  // 오른쪽 노드의 주소를 search 함수에 넘겨줌
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else 
    {
        return true;
    }
}

ハッシュ表

array+チェーンテーブル:接続リストの配列です.

[linked list1, linked list2, linked list3, linked list4...]

理想的なハッシュ関数が

の場合、配列内の接続リストには1つの値しかありません->O(1)

の最悪の場合、1つの配列にすべての値が含まれ、O(n)でもよいが、通常はハッシュ関数を使用してできるだけ多くのバスケットが作成されるため、O(1)にほぼ近い.

trie(略語の取得)

あるリソースを節約するために別のリソースを消費するモデル

ノードは配列ツリー

O(1)定数時間、大量メモリが必要
出典:全員向けコンピュータ科学(CS 502019)

Queue

FIFO (First In First Out)

下積み構造

人々が前に並んでいるように.

プリンタにも印刷キューがあります.(送信要求順に処理)

列に並ぶ

dequeue:ジャンプ

array&linkedlist:queue概念を実現するためのブロック

Stack

LIFO (Last In First Out)

上に積み重ねた構造

受信ボックス:デフォルトでスタックに設定されています(最近のメールは上部にあります)

push:エレメントをスタックにプッシュ

pop:一番上の要素を取り除く

array&linklist:スタックコンセプトを実現するためのブロック

Dictionary

Hash tableの概念とも考えられます

key-value pair