CS- 주 5

데이터 구조에 대한 자세한 설명 : 배열에서 트리로, 해시 테이블로

이 기사에서는 배열, 링크 된 목록, BST (Binary Search Tree) 및 해시 테이블을 포함하여 깊이있는 몇 가지 공통 데이터 구조에 대해 설명하고 메모리에서 조직과 장점과 단점을 설명합니다.

정보 구조 및 추상 데이터 구조

정보 구조는 정보가 메모리에서 구성되는 방식을 말하고, 추상 데이터 구조는 이러한 구조에 대한 개념적 이해입니다. 추상 데이터 구조를 이해하면 실제로 다양한 데이터 구조를 더 잘 구현할 수 있습니다.

---

스택과 대기열

대기열은 대기중인 대기와 유사한 FIFO (첫 번째, 첫 번째) 원칙을 따르는 추상 데이터 구조입니다. 주요 작업에는 Enqueuing (대기열의 꼬리에 요소 추가) 및 Dequeuing (대기열의 헤드 요소 제거)이 포함됩니다.

스택은 플레이트를 쌓는 것과 마찬가지로 Lifo (First in First Out) 원리를 따릅니다. 그 작업에는 푸시 (스택 상단에 요소 추가) 및 팝핑 (스택의 상단 요소 제거)이 포함됩니다.

---

정렬

배열은 메모리에 데이터를 지속적으로 저장하는 구조입니다. 아래 그림에서 볼 수 있듯이 배열은 메모리의 연속 저장 공간을 차지합니다.

다른 프로그램, 기능 및 변수는 이전에 사용 된 중복 데이터뿐만 아니라 메모리에 존재할 수 있습니다. 배열에 새 요소를 추가 해야하는 경우 메모리를 재 할당하고 비효율적 일 수있는 전체 배열을 복사해야합니다.

너무 많은 메모리를 사전에 올리 칠하면 복사 작업이 줄어들 수 있지만 시스템 리소스를 낭비합니다. 따라서 실제 요구에 따라 메모리를 할당하는 것이 중요합니다.

---

링크 목록

링크 된 목록은 다른 메모리 영역에 위치한 값을 목록으로 연결하고 동적 확장 또는 감소를 지원하는 강력한 데이터 구조입니다.

각 노드에는 데이터 값과 다음 노드에 대한 포인터의 두 가지 값이 포함됩니다. 마지막 노드의 포인터 값은 NULL이므로 링크 된 목록의 끝을 나타냅니다.

C 언어에서 노드는 다음과 같이 정의 할 수 있습니다.

 <code class="c">typedef struct node { int number; struct node *next; } node;</code>

다음 예제는 링크 된 목록을 작성하는 프로세스를 보여줍니다.

링크 된 목록의 단점에는 추가 메모리 저장 포인터의 필요성과 인덱스를 통해 요소에 직접 액세스 할 수없는 것이 포함됩니다.

---

이진 검색 트리 (BST)

이진 검색 트리는 데이터를 효율적으로 저장, 검색 및 검색하는 트리 구조입니다.

BST의 장점은 역동적이고 검색 효율 (O (log n))이며, 단점은 트리가 불균형하고 추가 메모리 저장 포인터가 필요할 때 검색 효율이 O (n)로 떨어진다는 것입니다.

---

해시 테이블

해시 테이블은 사전과 유사하며 키 값 쌍이 포함되어 있습니다. 해시 함수를 사용하여 키를 배열 인덱스에 매핑하므로 O (1)의 평균 조회 시간을 달성합니다.

해시 충돌 (동일한 인덱스에 매핑 된 다중 키)은 연결된 목록 또는 기타 방법으로 해결할 수 있습니다. 해시 기능의 설계는 해시 테이블의 성능에 중요합니다. 간단한 해시 함수의 예는 다음과 같습니다.

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

이 기사는 CS50X 2024 소스 코드를 기반으로 편집됩니다.

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