흔히 볼 수 있 는 데이터 구조 소개

데이터 구조 데이터 구 조 는 일종 또는 여러 가지 관계 의 데이터 요소 의 집합 또는 이 데이터 집합 간 의 관계 구성 을 말한다.흔히 볼 수 있 는 데이터 구 조 는 배열, 대기 열, 더미, 스 택, 트 리, 그림, 산 목록, 링크 등 이 있다.
1. 선형 구조 1) 배열 배열 은 메모리 에 여러 요 소 를 저장 할 수 있 는 구조 로 메모리 에 있 는 구조 도 연속 적 이다.배열 의 요 소 는 아래 표 시 를 통 해 접근 합 니 다.아래 표 지 는 0 부터 시작한다.
장점: & nbsp 는 색인 에 따라 요 소 를 조회 하고 접근 속도 가 빠르다.nbsp 는 색인 에 따라 배열 을 옮 겨 다 니 는 것 이 편리 합 니 다.단점: 1) 배열 을 만 들 면 길이 가 고정 되 어 수정 할 수 없습니다.2) 배열 은 삽입 과 삭제 작업 이 느 립 니 다. 다른 요 소 를 이동 하려 면 3) 배열 은 한 가지 유형의 요소 만 저장 할 수 있 기 때 문 입 니 다.
장면 조회 가 빈번 하고 삽입 과 삭 제 를 거의 하지 않 으 며 저장 공간 에 대한 요구 가 크 지 않 은 경우.
2) 링크 링크 링크 는 물리 적 저장 장치 에서 비 연속 적 이 고 비 순차 적 인 저장 구조 로 데이터 요소 의 논리 적 순 서 는 링크 의 포인터 주 소 를 통 해 이 루어 집 니 다. 각 요 소 는 두 개의 노드 를 포함 하고 하 나 는 요 소 를 저장 하 는 데이터 필드 (메모리 공간) 이 며 다른 하 나 는 다음 노드 주 소 를 가리 키 는 포인터 필드 입 니 다.지침 의 방향 에 따라 체인 시 계 는 서로 다른 구 조 를 형성 할 수 있다. 예 를 들 어 단일 체인 표, 양 방향 링크, 순환 링크 등 이다.체인 테이블 의 장점: 체인 테이블 은 자주 사용 하 는 데이터 구조 로 용량 을 초기 화 할 필요 가 없고 원 소 를 임의로 가감 할 수 있다.요 소 를 추가 하거나 삭제 할 때 앞 뒤 두 요소 의 노드 를 바 꾸 는 포인터 도 메 인 이 주 소 를 가리 키 면 되 기 때문에 추가, 삭제 가 빠 릅 니 다.복잡 도: 증가: O (n) 삭제: O (n) 변경: O (n) 검사: O (n)
단점: 대량의 지침 역 이 함유 되 어 있어 사용 공간 이 비교적 크다.요 소 를 찾 으 려 면 링크 를 옮 겨 다 니 며 찾 아야 합 니 다. 시간 이 많이 걸 립 니 다.
적용 장면: 데이터 양 이 적 고 자주 증가 해 야 합 니 다. 작업 을 삭제 하 는 장면 3) 대기 열 은 스 택 과 마찬가지 로 선형 표 이기 도 합 니 다. 다른 것 은 대기 열 은 한 끝 에 요 소 를 추가 하고 다른 한 끝 에서 요 소 를 꺼 낼 수 있 습 니 다. 즉, 선진 적 인 것 입 니 다.한 끝 에 원 소 를 넣 는 조작 을 입 대 라 고 하고 원 소 를 꺼 내 는 것 을 출 대 라 고 합 니 다.
사용 장면: 대기 열 이 먼저 나 오 는 특징 때문에 다 중 스 레 드 차단 대기 열 관리 에 매우 적합 합 니 다.
4) 스 택 은 특수 한 선형 표 로 선형 표 의 한 끝 에서 만 조작 할 수 있 고 스 택 지붕 은 조작 을 허용 하 며 스 택 바닥 은 조작 을 허용 하지 않 는 다.스 택 의 특징 은 선진 적 인 후에 나 오 거나 후진 적 으로 먼저 나 오 거나 스 택 꼭대기 에서 요 소 를 넣 는 작업 을 스 택 에 들 어가 요 소 를 꺼 내 스 택 을 부 르 는 것 이다.
사용 장면: 대기 열 이 먼저 나 오 는 특징 때문에 다 중 스 레 드 차단 대기 열 관리 에 매우 적합 합 니 다.
둘째, 비 선형 구조 1) 트 리 는 데이터 구조 로 n (n > = 1) 개의 유한 노드 로 차원 관 계 를 가 진 집합 을 구성한다.그것 을 '나무' 라 고 부 르 는 것 은 거꾸로 걸 린 나무 처럼 보이 기 때문이다. 즉, 그것 은 뿌리 가 위로 향 하고 잎 이 아래로 향 하기 때문이다.그것 은 다음 과 같은 특징 을 가지 고 있다.

             ；
             ；
                ；
      ，                 ；

일상적인 응용 에서 우리 가 토론 하고 사용 하 는 것 은 나무의 한 가지 구조 이 고 바로 이 진 트 리 이다.
이 진 트 리 는 나무의 특수 한 종류 로 다음 과 같은 특징 을 가진다.
1. 각 결점 마다 최대 두 개의 자나무 가 있 고 결점 의 도 는 최대 2 이다.2. 왼쪽 나무 와 오른쪽 나 무 는 순서 가 있 고 순서 가 뒤 바 뀌 어 서 는 안 됩 니 다.3. 어떤 결점 에 나무 가 하나 밖 에 없어 도 좌우 자 나 무 를 구분 해 야 한다.
이 진 트 리 는 비교적 유용 한 절충 방안 으로 요 소 를 추가 하고 삭제 하 는 것 이 빠 르 며 검색 에 있어 서도 많은 알고리즘 최적화 가 있 기 때문에 이 진 트 리 는 링크 의 장점 도 있 고 배열 의 장점 도 있 으 며 이들 의 최적화 방안 으로 대량의 동적 데 이 터 를 처리 하 는 데 매우 유용 하 다.
확장: 이 진 트 리 는 많은 확 장 된 데이터 구 조 를 가지 고 있 습 니 다. 균형 이 진 트 리, 빨 간 검 은 나무, B + 나무 등 을 포함 합 니 다. 이런 데이터 구 조 는 이 진 트 리 를 바탕 으로 많은 기능 을 파생 시 켰 고 실제 응용 에서 광범 위 하 게 사용 되 었 습 니 다. 예 를 들 어 my sql 의 데이터 베이스 색인 구 조 는 B + 나무 이 고 HashMap 의 바 텀 소스 코드 에서 빨 간 검 은 나 무 를 사 용 했 습 니 다.이 두 갈래 나무의 기능 은 강하 지만, 알고리즘 상 으로 는 비교적 복잡 하 다.
2) 더 미 는 비교적 특수 한 데이터 구조 로 나무의 배열 대상 으로 볼 수 있 으 며 다음 과 같은 성질 을 가진다.
@ 더미 의 특정한 노드 의 값 은 항상 부모 노드 의 값 보다 크 거나 작 지 않 습 니 다.
@ 무 더 기 는 항상 완전 이 진 트 리 입 니 다.
뿌리 노드 의 가장 큰 더 미 를 최대 더미 나 큰 뿌리 더미 라 고 하고 뿌리 노드 의 가장 작은 더 미 를 최소 더미 나 작은 뿌리 더미 라 고 한다.흔히 볼 수 있 는 무 더 기 는 이 진 더미, 피 보 나 더미 등 이 있다.
사용 장면: 질서 있 는 특징 때문에 배열 의 정렬 을 하 는 데 사용 되 는데 쌓 기 정렬 이 라 고 합 니 다.3) 그림 은 결점 이 있 는 빈 집합 V 와 변 의 집합 E 로 구성 된다.그 중에서 나무 구조 와 구별 하기 위해 그림 구조 에서 결점 을 정점 이 라 고 부 르 고 변 은 정점 의 질서 있 는 짝 짓 기 이다. 만약 에 두 정점 사이 에 한 변 이 존재 하면 이 두 정점 이 서로 인접 한 관 계 를 가 진 다 는 것 을 나타 낸다.
정점 이 가리 키 는 방향 에 따라 무방 향도 와 유방 향도 로 나 눌 수 있다.
그림 은 비교적 복잡 한 데이터 구조 로 데 이 터 를 저장 하 는 데 비교적 복잡 하고 효율 적 인 알고리즘 을 가지 는데 각각 인접 행렬, 인접 표, 십자 링크, 인접 다 중 표, 변 집합 배열 등 저장 구조 가 있다.
4) 산열 표 산 목록 은 해시 표 라 고도 하 는데 관건 적 인 코드 와 값 (key 와 value) 에 따라 직접 방문 하 는 데이터 구조 로 key 와 value 를 통 해 집합 중의 한 위치 에 투사 하면 집합 중의 대응 요 소 를 빨리 찾 을 수 있다.