C 언어의 데이터 구조는 무엇입니까? 일반적인 데이터 구조는 무엇입니까?

C 언어에서 데이터 구조는 서로 하나 이상의 특정 관계를 갖는 데이터 요소의 모음을 의미합니다. 이는 컴퓨터가 데이터를 저장하고 구성하는 방식입니다. 일반적인 데이터 구조에는 선형 데이터 구조(배열, 연결 목록, 스택, 큐 및 선형 목록), 트리 구조(이진 트리, 완전 이진 트리, 이진 검색 트리, 힙), 그래프 구조(유향 그래프 및 무향 그래프).

이 튜토리얼의 운영 환경: Windows 7 시스템, c99 버전, Dell G3 컴퓨터.

데이터 구조란 무엇인가요?

데이터 구조는 컴퓨터가 데이터를 저장하고 구성하는 방식입니다. 데이터 구조는 서로 하나 이상의 특정 관계를 갖는 데이터 요소의 모음을 의미합니다

대부분의 데이터 구조를 구현하려면 C 언어의 포인터와 구조 유형의 도움이 필요합니다

이제 오늘의 초점을 살펴보겠습니다O( ∩_∩)O 몇 가지 일반적인 데이터 구조

(1) 선형 데이터 구조: 일반적으로 요소 간에 일대일 관계가 있습니다. 가장 일반적으로 사용되는 데이터 구조 유형은 배열, 스택, 큐 및 선형 목록

(2) 트리 구조: 노드 간에는 계층적 관계가 있습니다. 각 레이어의 노드는 이전 레이어의 노드와만 관련될 수 있지만 다음 레이어와도 관련될 수 있습니다. 여러 노드가 관련되어 있으며 이를 "일대다" 관계라고 합니다. 일반적인 유형은 트리, 힙

(3) 그래픽 구조: 그래프 구조에서는 여러 노드가 관련될 수 있으며 이를 "다"라고 합니다. -대-다" 관계. "다" 관계

다음은 이러한 각 데이터 구조에 대한 간략한 소개입니다.

1. 선형 데이터 구조: 일반적인 데이터 구조는 배열, 스택, 큐 및 선형 테이블입니다

(1) 배열 및 연결 리스트

a. 배열: 1차원 배열, 2차원 배열 등 배열의 길이를 미리 지정해야 합니다. , 다차원 배열 등

b. 연결 목록: 연결 목록은 C 언어에서 널리 사용되는 방법입니다. 구조는 동적 할당 메모리 형태로 구현되어 연결 목록을 저장하는 데 사용됩니다. 일반적으로 각 요소가 후속 요소를 가리키도록 포인터 필드가 추가됩니다.

c 배열과 연결 목록의 차이점:

논리 구조의 관점에서 볼 때 배열은 미리 정의된 고정 길이를 가져야 합니다. 데이터의 동적 증가 및 감소에 적응할 수 없습니다. 연결 목록은 동적으로 스토리지 할당을 수행하고 데이터의 동적 증가 및 감소에 적응할 수 있으며 항목을 쉽게 삽입 및 삭제할 수 있습니다(배열에 데이터 항목을 삽입하거나 삭제할 때). , 다른 데이터 항목은 이동해야 함)

메모리 저장 관점에서 볼 때: (정적) 배열은 스택(힙에서 NEW로 생성됨)에서 공간을 할당합니다. 이는 프로그래머에게 편리하고 빠르지만 자유도는 연결된 목록은 힙에서 공간을 할당하고 자유도는 크지만 응용 프로그램 관리가 더 번거롭습니다

접근 방법에서: 배열이 메모리에 지속적으로 저장되므로 아래 첨자 인덱스를 사용할 수 있습니다. 무작위 접근; 연결된 목록은 요소에 접근할 때 선형 방식으로 앞에서 뒤로 순차적으로만 접근할 수 있는 체인형 저장 구조이므로 접근 효율이 배열보다 낮습니다

(2) 스택, 큐 및 선형 테이블 : 순차 저장 및 체인화를 사용할 수 있음 저장 방법

순차 저장: 저장 공간 내 데이터 요소의 상대적 위치를 사용하여 요소 간의 논리적 관계를 표현

체인 저장: 데이터 요소의 저장 주소를 나타내는 포인터 사용 요소 간의 논리적 관계를 표현하기 위해

a. 스택: 작업은 시퀀스의 끝에서만 허용됩니다. 일반적으로 스택은 후입 우선(Last-In-First)이라고도 합니다. -out 또는 First-In-Last-Out 선형 구조.

순차 스택: 순차 저장 구조를 사용합니다. 스택을 순차 스택이라고 합니다. 즉, 스택의 요소를 저장하려면 연속적인 주소가 있는 공간이 필요합니다. . 순차 스택의 유형은 다음과 같이 정의됩니다.

체인 스택: 체인 저장 구조를 사용하는 스택을 체인 스택이라고 합니다.

b. 큐: 양쪽 끝에서 작업만 허용됩니다. 일반적으로 큐는 선입 선출 선형 구조라고도 합니다.
원형 큐: 순차 저장 구조를 사용하는 큐는 큐의 가능한 최대 길이에 따라 저장 공간을 할당해야 합니다.

체인 큐: 체인 저장 구조를 사용하는 큐를 체인 큐라고 합니다. 일반적으로 헤드 및 테일 포인터를 연결 목록의 헤드 및 테일 노드에만 설정해야 합니다.

c. 선형 테이블: 시퀀스의 모든 위치에서 작동 가능 선형 테이블의 작동 위치는 매우 유연합니다. 어떤 위치에서든 요소를 ​​쿼리하고 수정할 수 있습니다

순차 테이블: 순차 저장 구조로 표현되는 선형 테이블을 순차 테이블이라고 합니다. 연속된 주소를 갖는 저장 단위 집합을 사용하여 선형 테이블의 데이터 요소를 한 번에 저장합니다. 즉, 인접한 저장 위치는 다음을 나타냅니다. 순서대로 두 요소 사이의 거리 요소 이동을 피하기 위해 일반적으로 순서 테이블의 인터페이스 정의에서는 테이블 끝의 요소 삽입 및 삭제만 고려됩니다. way는 스택 테이블이라고도 할 수 있습니다:

선형 테이블: 일반적으로 단일 연결 목록, 이중 연결 목록, 순환 연결 목록 및 양방향 순환 연결 목록을 포함합니다.

단일 연결 목록:

이중 연결 목록 목록:

선형 테이블 두 저장 구조의 비교:

순차 테이블:

장점: 순서 테이블에서는 논리의 인접한 두 요소도 물리적 위치에서도 인접하므로 시간을 더 쉽게 검색할 수 있습니다. 모든 요소에 접근하는 복잡도는 O(1)

단점: 어떤 위치에서도 삽입이나 삭제에 적합하지 않습니다. 요소를 이동해야 하기 때문에 평균 시간 복잡도는 O(n)

링크된 목록:

장점 : 링크의 임의 위치에 요소를 삽입하거나 삭제하려면 해당 포인터만 수정하면 되며 요청 시 요소를 이동할 필요가 없습니다. 최대 수요

단점: 요소를 찾으려면 포인터 필드를 따라 헤드 포인터에서 검색해야 하므로 평균 시간 복잡도는 O(n)

2입니다. 각 계층의 노드는 이전 계층의 하나의 노드와만 관련될 수 있지만 다음 계층의 여러 노드와도 관련될 수 있습니다. 이를 "일대다"라고 합니다. " 관계. 일반적입니다. 유형은 다음과 같습니다: 트리, 힙

(1) 이진 트리: 이진 트리는 n(n>=0) 노드를 포함하는 유한 집합인 재귀적 데이터 구조입니다. 이진 트리는 다음과 같은 특징을 갖습니다. :

이진 트리는 빈 트리일 수 있습니다. 이진 트리의 각 노드에는 정확히 두 개의 하위 트리가 있으며, 그 중 하나 또는 둘 다 비어 있을 수 있습니다. 이진 트리에서 각 노드의 왼쪽 및 오른쪽 하위 트리 위치는 바뀔 수 없습니다. 둘의 위치가 변경되면 서로가 됩니다. 이진 트리

(2) 완전한 이진 트리: 루트에서 시작하여 위에서 아래로, 왼쪽에서 오른쪽으로, 전체 이진 트리의 각 노드에 연속적으로 번호를 매깁니다. 각 노드가 k의 깊이와 관련되어 있으면 1에서 n까지 전체 이진 트리에서 1부터 n까지 번호가 매겨진 노드는 1:1로 대응되며, 이를 완전 이진 트리라고 합니다

a. 1차원 배열은 완전한 이진 트리를 저장하는 데 사용되며 노드 수는 노드의 첨자와 관련됩니다(예: 루트는 1이고 루트의 왼쪽 자식은 2i=21=2이며, 오른쪽 자식은 2i+1=21+1=2)

b, 체인 저장 구조 사용:

이진 연결 목록:

3차 연결 목록: 노드에 포인터 필드 부모가 하나 더 있습니다. 노드의 부모를 실행하고 부모 노드 검색을 용이하게 하는 데 사용되는 이진 연결 목록보다

두 가지 저장 구조 비교: 완전한 이진 트리의 경우 순서가 사용됩니다. 공간을 절약할 뿐만 아니라 배열 요소의 첨자 값을 사용하여 이진 트리에서 노드의 위치와 노드 간의 관계를 결정합니다. 그러나 일반 이진 트리를 저장하기 위해 순차 저장 구조를 사용하면 공간 낭비가 발생하기 쉽습니다. .체인 구조는 이러한 단점을 극복할 수 있습니다.

(3) 이진 검색 트리: 이진 정렬 트리라고도 불리는 이진 검색 트리는 빈 이진 트리이거나 다음과 같은 특성을 갖는 이진 트리입니다.

a. 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리에 있는 모든 노드의 값이 루트 노드

b의 값보다 작습니다. 오른쪽 하위 트리가 비어 있지 않으면 모든 노드의 값이 루트 노드입니다. 오른쪽 하위 트리는 루트 노드의 값보다 큽니다.

c. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리입니다.

(4) 균형 이진 트리: 균형 이진 검색 트리를 균형 이진 트리라고 합니다. 균형 이진 트리는 빈 트리이거나 다음 속성을 갖는 이진 검색입니다. 트리: 왼쪽 하위 트리와 오른쪽 하위 트리는 모두 균형 이진 트리이며 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이의 절대값은 그렇지 않습니다. 1을 초과

균형 이진 트리의 불균형과 조정은 다음과 같이 요약할 수 있습니다. 네 가지 상황: LL 유형, RR 유형, LR 유형, RL 유형

(5) 트리: 트리는 n을 포함하는 유한 집합입니다. (n>=0) 노드. 비어 있지 않은 트리 종에는: a. 그리고 루트

b라는 특정 노드가 하나만 있습니다. n>1이면 나머지 노드는 m(m>0)으로 나눌 수 있습니다. 서로 분리된 유한 집합 T1, T2,...,Tm. 여기서 각 집합 자체는 트리이고 T1, T2,...,Tm은 루트의 하위 트리라고 합니다

(6) 힙: 힙은 다음과 같은 특징을 가진 완전한 이진 트리입니다. 리프가 아닌 모든 노드는 왼쪽 및 오른쪽 자식 노드보다 크지 않습니다(또는 작지 않습니다). 힙의 모든 비리프 노드가 왼쪽 및 오른쪽 자식 노드보다 크지 않은 경우 힙의 모든 비리프 노드가 왼쪽 및 오른쪽보다 작지 않은 경우 이를 작은 최상위 힙(작은 루트 힙)이라고 합니다. 하위 노드인 경우 이를 대형 힙(큰 루트 힙)이라고 합니다.

(7) Union-find 집합: Union-find 집합은 서로 분리된 하위 집합 집합으로 구성된 집합을 말하며 다음과 같이 표시됩니다. ={S1, S2, S3,…,Sn }

(8) B-tree

3. 그래프 구조: 그래프 구조에서는 여러 노드 간의 상관 관계가 허용되며 이를 "다대다"라고 합니다. 방향성 그래프와 무방향성 그래프로 나눌 수 있는 관계

튜토리얼 추천 : "c 언어 튜토리얼 영상"

위 내용은 C 언어의 데이터 구조는 무엇입니까? 일반적인 데이터 구조는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!