CS- 5주차

데이터 구조

정보 구조는 기억 속에 정보를 정리하는 형태입니다. 메모리에 있는 데이터를 정리하는 방법은 다양합니다.

추상적 데이터 구조는 우리가 개념적으로 상상하는 구조입니다. 이러한 추상 구조에 익숙해지면 향후 실제로 데이터 구조를 구현하는 것이 더 쉬워집니다.

---

스택과 큐

큐는 추상적인 데이터 구조의 한 형태입니다.
Queue 데이터 구조는 FIFO (선입선출, "처음 추가된 요소가 먼저 나옵니다") 규칙에 따라 작동합니다.
어트랙션에 줄을 서 있는 사람들의 예를 상상해 볼 수 있습니다. 줄을 선 첫 번째 사람이 먼저 들어가고, 마지막 사람이 맨 마지막에 입장합니다.

큐:

를 사용하여 다음 작업을 수행할 수 있습니다.

• Enqueue: 대기열 끝에 새 요소를 추가합니다.
• Dequeue: 대기열의 시작 부분에서 요소를 제거합니다.

Stack 데이터 구조는 LIFO (Last In First Out, "마지막에 추가된 요소가 먼저 나옵니다") 규칙에 따라 작동합니다. 예를 들어 주방에 접시를 쌓는 경우 마지막 접시부터 가져옵니다.

스택에는 다음과 같은 작업이 있습니다.

• 푸시: 스택에 새 요소를 넣습니다.
• 팝: 스택에서 요소를 제거합니다.

---

정렬

Array는 데이터를 메모리에 순차적으로 저장하는 방식입니다. 배열은 다음과 같이 시각화할 수 있습니다.

메모리에는 다른 프로그램, 함수, 변수에 의해 저장된 다른 값뿐만 아니라 이전에 사용되었지만 더 이상 사용되지 않는 중복 값이 ​​포함될 수 있습니다.

배열에 새 요소(4)를 추가하려면 새 메모리를 할당하고 이전 배열을 그 안으로 옮겨야 합니다. 이 새로운 메모리는 쓰레기 값으로 가득 차 있을 수 있습니다

:

요소를 배열로 이동하고 새 값을 추가하면 새 값은 새로 할당된 메모리의 이전 불필요한 값 위에 쓰여집니다.

이 접근 방식의 단점은 새 요소가 추가될 때마다 전체 배열을 복사해야 한다는 것입니다.
4를 메모리의 다른 곳에 넣으면 어떻게 될까요? 그러면 정의에 따라 4는 메모리의 배열 요소와 연속되지 않기 때문에 더 이상 배열이 아닙니다.

때때로 프로그래머는 필요한 것보다 더 많은 메모리를 할당합니다(예: 30개 요소에 300개). 그러나 이는 시스템 리소스를 낭비하고 대부분의 경우 추가 메모리가 필요하지 않기 때문에 잘못된 설계입니다. 따라서 구체적인 필요에 따라 메모리를 할당하는 것이 중요합니다.

---

연결리스트

연결된 목록은 C 프로그래밍 언어에서 가장 강력한 데이터 구조 중 하나입니다. 서로 다른 메모리 영역에 있는 값을 단일 목록으로 결합할 수 있습니다. 또한 원하는 대로 목록을 동적으로 확장하거나 축소할 수 있습니다.

각 노드는 두 가지 값을 저장합니다.

• 가치;
• 은 다음 노드의 메모리 주소를 보유하는 포인터입니다. 그리고 마지막 노드에는 NULL이 포함되어 있어 그 뒤에 다른 요소가 없음을 나타냅니다.

연결된 목록의 첫 번째 요소의 주소를 포인터(포인터)에 저장합니다.

C 프로그래밍 언어에서는 node를 다음과 같이 작성할 수 있습니다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

연결된 목록을 만드는 과정을 살펴보겠습니다.

• 노드 *list를 선언합니다:

• 노드에 메모리 할당:

• 노드 값을 입력하세요: n->number = 1:

• 노드의 다음 인덱스를 NULL로 설정합니다: n->next = NULL:

• 목록을 다음과 같게 합시다:

• 같은 순서로 값이 2인 새 노드를 만듭니다.

• 두 노드를 연결하기 위해 n의 다음 인덱스를 목록으로 설정합니다.

• 마지막으로 목록을 n으로 설정했습니다. 이제 두 가지 요소로 구성된 연결 목록이 생겼습니다.

C 프로그래밍 언어에서는 이 프로세스의 코드를 다음과 같이 작성할 수 있습니다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

연결된 목록을 사용할 때 몇 가지 단점이 있습니다.

• 더 많은 메모리: 각 요소에 대해 요소 자체의 값뿐만 아니라 다음 요소에 대한 포인터도 저장해야 합니다.
• 인덱스로 요소 호출: 배열에서는 특정 요소를 인덱스로 호출할 수 있지만 연결 리스트에서는 불가능합니다. 특정 요소의 위치를 ​​찾으려면 첫 번째 요소부터 시작하여 모든 요소를 ​​순서대로 살펴봐야 합니다.

---

나무

이진 검색 트리 (BST)는 데이터를 효율적으로 저장, 검색, 조회할 수 있는 정보 구조입니다.
일련의 정렬된 숫자가 주어집니다:

위쪽 중앙에 요소를 배치하고 왼쪽 중앙에 있는 요소보다 작은 값을 오른쪽에 큰 값을 배치합니다.

포인터를 사용하여 각 요소를 서로 연결합니다.

다음 코드는 BST를 구현하는 방법을 보여줍니다.

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

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

각 노드에 메모리를 할당하고 그 값을 숫자로 저장하므로 각 노드에는 왼쪽과 오른쪽 표시가 있습니다. print_tree 함수는 왼쪽에서 오른쪽으로 순차적 재귀로 각 노드를 인쇄합니다. free_tree 함수는 데이터 구조의 모든 노드를 메모리에서 재귀적으로 해제합니다.

BST의 장점:

• 역동성: 요소를 효율적으로 추가하거나 제거할 수 있습니다.
• 검색 효율성: BST에서 특정 요소를 검색하는 데 걸리는 시간은 O(log n)입니다. 각 검색에서 트리의 절반이 검색에서 제외되기 때문입니다.

BST의 단점:

• 트리의 균형이 깨지면(예를 들어 모든 요소가 일렬로 배치되는 경우) 검색 효율이 O(n)으로 떨어집니다.
• 각 노드에 대해 왼쪽 및 오른쪽 포인터를 모두 저장해야 하므로 컴퓨터의 메모리 소비가 늘어납니다.

---

사전

사전은 사전책과 같습니다. 단어와 단어의 정의, 키 (키) 및 값 요소가 포함되어 있습니다. (값)이 있습니다.

Dictionary에 요소를 쿼리하면 O(1) 시간 안에 해당 요소가 반환됩니다. 사전은 해싱을 통해 정확히 이 속도를 제공할 수 있습니다.

해싱은 특수 알고리즘을 사용하여 입력 배열의 데이터를 일련의 비트로 변환하는 프로세스입니다.

해시 함수는 임의 길이의 문자열에서 고정 길이 비트의 문자열을 생성하는 알고리즘입니다.

해시 테이블은 배열과 연결 목록의 훌륭한 조합입니다. 다음과 같이 상상해 볼 수 있습니다.

충돌 (충돌)은 서로 다른 두 입력이 하나의 해시 값을 생성하는 경우입니다. 위 이미지에서는 충돌하는 요소들이 연결리스트로 연결되어 있습니다. 해시 함수를 개선하면 충돌 확률을 줄일 수 있습니다.

해시 함수의 간단한 예는 다음과 같습니다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

이 글은 CS50x 2024 소스를 사용했습니다.

위 내용은 CS- 5주차의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!