introduction data structures c
C ++의 데이터 구조에 대한 입문 자습서.
“데이터 구조는 프로그램이 데이터에 효율적이고 빠르게 액세스하여 전체 프로그램이 효율적인 방식으로 작동 할 수 있도록 도와주는 조직화 된 데이터 모음으로 정의 할 수 있습니다. “
프로그래밍 세계에서 데이터는 중심이며 모든 것은 데이터를 중심으로 이루어집니다. 데이터 저장, 검색, 정렬, 구성 및 액세스를 포함한 모든 데이터 작업을 효율적으로 수행해야하며, 그래야만 프로그램이 성공할 수 있습니다.
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
학습 내용 :
개요
동적 솔루션을 구축하는 데 도움이 될 수있는 가장 효율적인 데이터 저장 방법을 찾아야합니다. 데이터 구조는 이러한 솔루션을 구축하는 데 도움이됩니다.
데이터를 구조로 구성하거나 배열하는 동안 배열이 거의 실제 객체를 나타내는 지 확인해야합니다. 둘째,이 배열은 누구나 쉽게 액세스하고 필요할 때마다 처리 할 수 있도록 충분히 간단해야합니다.
이 시리즈에서는 기본 및 고급 데이터 구조에 대해 자세히 알아 봅니다. 또한 데이터 구조에서 수행 할 수있는 다양한 검색 및 정렬 기술에 대해 자세히 알아 봅니다.
이 튜토리얼 시리즈를 학습 한 후 독자는 각 데이터 구조와 해당 프로그래밍에 대해 잘 알고 있어야합니다.
데이터 구조를 다루는 동안 사용하는 몇 가지 용어를 살펴 보겠습니다.
예를 들어,특정 학생을 데려가십시오. 학생은 그림으로 표현 된 다음과 같은 세부 사항을 가질 수 있습니다.
- 데이터: 기본 값입니다. 위 그림에서 학생 롤 번호는 데이터가 될 수 있습니다.
- 그룹 항목 : 하위 항목이 두 개 이상있는 데이터 항목입니다. 위 그림에서 Student_name에는 이름과 성이 있습니다.
- 기록: 데이터 항목의 모음입니다. 위의 예에서 학생 롤 번호, 이름, 클래스, 나이, 학년 등과 같은 데이터 항목은 함께 레코드를 형성합니다.
- 실재: 레코드 클래스입니다. 위의 다이어그램에서 학생은 엔티티입니다.
- 속성 또는 필드 : 엔터티의 속성을 특성이라고하며 각 필드는 특성을 나타냅니다.
- 파일: 파일은 레코드 모음입니다. 위의 예에서 학생 엔터티는 수천 개의 레코드를 가질 수 있습니다. 따라서 파일에는 이러한 모든 레코드가 포함됩니다.
독자는 우리가 다양한 데이터 구조를 사용할 때 때때로 사용하는 모든 용어를 알고 있어야합니다.
데이터 구조는 프로그램의 주요 빌딩 블록이며 프로그래머로서 사용할 데이터 구조에 대해주의해야합니다. 사용할 정확한 데이터 구조는 프로그래밍에 관한 한 가장 어려운 결정입니다.
프로그래밍에서 데이터 구조의 필요성에 대해 논의하겠습니다.
프로그래밍에서 데이터 구조 필요
데이터의 양이 계속 증가함에 따라 응용 프로그램이 점점 더 복잡해 지므로 프로그래머가이 데이터와 소프트웨어를 관리하기가 어려워집니다.
일반적으로 애플리케이션은 언제든지 다음과 같은 장애물에 직면 할 수 있습니다.
# 1) 많은 양의 데이터 검색 : 많은 양의 데이터가 처리되고 저장되는 상황에서 언제든지 특정 데이터를 검색하기 위해 프로그램이 필요할 수 있습니다. 데이터가 너무 크고 제대로 구성되지 않은 경우 필요한 데이터를 가져 오는 데 많은 시간이 걸립니다.
데이터 구조를 사용하여 데이터를 저장하고 구성하면 데이터 검색이 더 빠르고 쉬워집니다.
# 2) 처리 속도 : 데이터를 검색하고 액세스하는 데 많은 시간이 낭비되므로 데이터가 잘못 구성되면 처리 속도가 느려질 수 있습니다.
데이터를 저장하는 동안 데이터 구조에 적절하게 구성하면 매번 검색, 구성과 같은 활동에 시간을 낭비하지 않습니다. 대신 원하는 출력을 생성하기 위해 데이터 처리에 집중할 수 있습니다.
# 3) 여러 동시 요청 : 요즘 많은 애플리케이션에서 데이터를 동시에 요청해야합니다. 애플리케이션이 원활하게 실행 되려면 이러한 요청을 효율적으로 처리해야합니다.
데이터가 무작위로 저장되면 모든 동시 요청을 동시에 처리 할 수 없습니다. 따라서 동시 요청 처리 시간을 최소화하기 위해 데이터를 적절한 데이터 구조로 배열하는 것이 현명한 결정입니다.
데이터 구조 분류
C ++에서 사용되는 데이터 구조는 다음과 같이 분류 할 수 있습니다.
데이터 구조는 데이터를 구성하는 방법입니다. 따라서 우리는 데이터 구조를 기본 또는 표준 데이터 구조와 비 기본 또는 사용자 정의 데이터 구조로 분류 할 수 있습니다.
우리는 C ++에서 지원되는 모든 데이터 유형을 보았습니다. 이것은 또한 데이터를 구성하는 방법이므로 표준 데이터 구조라고합니다.
다른 데이터 구조는 원시적이지 않으며 프로그램에서 사용하기 전에 사용자가 정의해야합니다. 이러한 사용자 정의 데이터 구조는 선형 및 비선형 데이터 구조로 더 분류됩니다.
선형 데이터 구조
선형 데이터 구조에는 모든 요소가 선형 또는 순차 방식으로 배열됩니다. 선형 데이터 구조의 각 요소에는 선행 요소 (이전 요소)와 후속 요소 (다음 요소)가 있습니다.
선형 데이터 구조는 정적 및 동적 데이터 구조로 더 나뉩니다. 정적 데이터 구조는 일반적으로 고정 된 크기를 가지며 컴파일 타임에 크기가 선언되면 변경할 수 없습니다. 동적 데이터 구조는 크기를 동적으로 변경하고 수용 할 수 있습니다.
선형 정적 데이터 구조의 가장 인기있는 예는 배열입니다.
정렬
배열은 동일한 유형의 요소를 순차적으로 모은 것입니다. 배열의 각 요소는 배열의 인덱스 또는 첨자라고하는 배열에서의 위치를 사용하여 액세스 할 수 있습니다. 배열의 이름은 배열의 첫 번째 요소를 가리 킵니다.
위의 그림은 n 개 요소의 배열 'a'입니다. 요소는 0에서 n-1까지 번호가 매겨집니다. 배열의 크기 (이 경우 n)는 배열의 차원이라고도합니다. 위의 그림에 표시된 것처럼 배열의 이름은 배열의 첫 번째 요소를 가리 킵니다.
배열은 가장 단순한 데이터 구조이며 첨자를 사용하여 요소에 직접 액세스 할 수 있으므로 효율적입니다. 배열의 세 번째 요소에 액세스하려면 a [2]라고 말하면됩니다.
그러나 배열 요소를 추가하거나 삭제하는 것은 어렵습니다. 따라서 우리는 단순한 애플리케이션 또는 요소 추가 / 삭제가 필요하지 않은 애플리케이션에서만 배열을 사용합니다.
인기있는 선형 동적 데이터 구조는 연결 목록, 스택 및 대기열입니다.
연결된 목록
연결 목록은 노드 모음입니다. 각 노드에는 데이터 요소와 다음 노드에 대한 포인터가 포함됩니다. 노드는 동적으로 추가 및 삭제할 수 있습니다. 연결 목록은 각 노드에 다음 요소에 대한 포인터 만있는 단일 연결 목록이 될 수 있습니다. 마지막 요소의 경우 다음 포인터가 null로 설정됩니다.
이중 연결 목록에서 각 노드에는 이전 노드에 대한 포인터와 다음 노드에 대한 두 번째 포인터가 있습니다. 첫 번째 노드의 경우 이전 포인터는 null이고 마지막 노드의 경우 다음 포인터는 null입니다.
위 그림과 같이 목록의 시작 부분을 헤드라고하고 연결 목록의 끝 부분을 꼬리라고합니다. 위에 표시된 것처럼 각 노드에는 다음 요소에 대한 포인터가 있습니다. 포인터를 다음 노드로 변경하여 요소를 쉽게 추가하거나 삭제할 수 있습니다.
스택
스택은 스택의 '상단'이라고하는 한쪽 끝에서만 요소를 추가하거나 제거 할 수있는 선형 데이터 구조입니다. 이러한 방식으로 스택은 LIFO (Last In, First Out) 유형의 메모리 액세스를 나타냅니다.
위에 표시된 것처럼 스택의 요소는 항상 한쪽 끝에 추가되고 동일한 끝에서도 제거됩니다. 이것을 스택의 '상단'이라고합니다. 요소가 추가되면 스택 아래로 밀리고 스택의 맨 위가 한 위치 씩 증가합니다.
마찬가지로 요소가 제거되면 스택의 맨 위가 감소합니다. 스택이 비어 있으면 스택의 맨 위가 -1로 설정됩니다. 스택에서 수행되는 두 가지 주요 작업 'Push'및 'Pop'이 있습니다.
열
큐는 요소가 '후면'이라는 한쪽 끝에 추가되고 '전면'이라는 다른 쪽 끝에서 삭제되는 또 다른 선형 데이터 구조입니다. 대기열은 FIFO (선입 선출)에서 메모리 액세스 방법의 유형을 보여줍니다.
위의 다이어그램은 후면과 전면이있는 대기열을 보여줍니다. 대기열이 비어 있으면 후면 및 전면 포인터가 서로 일치합니다.
비선형 데이터 구조
비선형 데이터 구조에서 데이터는 순차적으로 배열되지 않고 비선형 방식으로 배열됩니다. 요소는 비선형 배열로 서로 연결됩니다.
비선형 데이터 구조는 트리와 그래프입니다.
배열 자바의 복사본 만들기
나무
트리는 요소간에 계층 적 관계가있는 비선형 다단계 데이터 구조입니다. 트리의 요소를 노드라고합니다.
맨 위에있는 노드를 트리의 루트라고합니다. 루트에는 하나 이상의 자식 노드가있을 수 있습니다. 후속 노드에는 하나 이상의 자식 노드가있을 수도 있습니다. 자식 노드가없는 노드를 리프 노드라고합니다.
위의 다이어그램에서 우리는 6 개의 노드가있는 트리를 보여주었습니다. 이 세 노드 중 리프 노드, 최상위 노드 중 하나는 루트이고 다른 노드는 자식 노드입니다. 노드 수, 자식 노드 등 또는 노드 간의 관계에 따라 다른 유형의 트리가 있습니다.
그래프
그래프는 다음과 같은 노드 집합입니다. 정점 호출 된 링크를 통해 서로 연결 가장자리 . 그래프는 내부에주기를 가질 수 있습니다. 즉, 동일한 정점이 특정 경로의 시작점과 끝 점이 될 수 있습니다. 나무는 순환을 가질 수 없습니다.
위의 다이어그램은 무 방향 그래프입니다. 또한 방향 화살표를 사용하여 모서리를 나타내는 방향 그래프를 가질 수 있습니다.
데이터 구조에 대한 작업
모든 데이터 구조는 해당 요소에 대해 다양한 작업을 수행합니다.
이는 모든 데이터 구조에 공통이며 다음과 같이 나열됩니다.
- 수색: 이 작업은 특정 요소 또는 키를 검색하기 위해 수행됩니다. 가장 일반적인 검색 알고리즘은 순차 / 선형 검색 및 이진 검색입니다.
- 정렬 : 정렬 작업에는 오름차순 또는 내림차순으로 특정 순서로 데이터 구조의 요소를 정렬하는 작업이 포함됩니다. 데이터 구조에 사용할 수있는 다양한 정렬 알고리즘이 있습니다. 그중 가장 인기있는 것은 Quicksort, Selection sort, Merge sort 등입니다.
- 삽입: 삽입 작업은 데이터 구조에 요소를 추가하는 작업을 처리합니다. 이것은 가장 중요한 작업이며 요소 추가의 결과로 배열이 변경되며 데이터 구조가 손상되지 않도록주의해야합니다.
- 삭제: 삭제 작업은 데이터 구조에서 요소를 제거합니다. 삭제 작업의 경우에도 삽입을 위해 고려되는 동일한 조건이 충족되어야합니다.
- 횡단 : 우리는 구조의 모든 요소를 방문 할 때 데이터 구조를 순회한다고 말합니다. 데이터 구조에서 특정 작업을 수행하려면 순회가 필요합니다.
다음 주제에서는 먼저 데이터 구조에서 수행 할 다양한 검색 및 정렬 기술을 배웁니다.
데이터 구조의 장점
- 추출: 데이터 구조는 종종 추상 데이터 유형으로 구현됩니다. 사용자는 기본 구현에 대해 걱정하지 않고 외부 인터페이스에만 액세스합니다. 따라서 데이터 구조는 추상화 계층을 제공합니다.
- 능률: 데이터를 적절하게 구성하면 데이터에 효율적으로 액세스하여 프로그램을보다 효율적으로 만들 수 있습니다. 둘째, 요구 사항에 따라 적절한 데이터 구조를 선택할 수 있습니다.
- 재사용 성: 우리가 설계 한 데이터 구조를 재사용 할 수 있습니다. 라이브러리로 컴파일하여 클라이언트에 배포 할 수도 있습니다.
결론
이것으로 데이터 구조 소개에 대한이 튜토리얼을 마칩니다. 이 자습서에서는 각 데이터 구조를 간략하게 소개했습니다.
이어지는 튜토리얼에서는 다양한 검색 및 정렬 기술과 함께 데이터 구조에 대해 자세히 살펴볼 것입니다.
=> Absolute C ++ 교육 시리즈를 보려면 여기를 클릭하십시오.
추천 도서
- C ++ 데이터 유형
- 그림이있는 C ++의 큐 데이터 구조
- 프로그래밍을 없애기위한 2021 년 상위 10 개의 데이터 과학 도구
- 사용자 정의 변수를 사용한 JMeter 데이터 매개 변수화
- 데이터 수집 전략을 갖춘 10 개 이상의 최고의 데이터 수집 도구
- 2021 년 데이터 요구 사항을 충족하는 10 개 이상의 최고의 데이터 거버넌스 도구
- 테스트 데이터 관리를위한 IBM Rational Quality Manager의 데이터 풀 기능
- 일러스트레이션이있는 C ++의 스택 데이터 구조