데이터 구조 검토 요약 [칭화엄판 교재에 적합]
첫째, 장 구조와 데이터 구조의 핵심 구성 요소
데이터 구조 학과의 장은 기본적으로 소개, 선형 테이블, 스택 및 대기열, 문자열, 다차원 배열 및 광의표, 트리 및 이진 트리, 그림, 검색, 전문가, 문외한, 파일 및 동적 스토리지 할당으로 나뉩니다.
대부분의 학교에서는' 유출, 아카이브, 동적 스토리지 할당' 3 장이 기본적으로 시험을 치르지 않고, 대부분의 고교의 컴퓨터 학부 교육 과정에서 기본적으로 가르치지 않는다. 그래서 이 세 장은 너무 많은 정력을 들이지 않고 기본 개념만 알면 된다. 하지만 명문 학교, 특히 학교, 시험지에 이 세 장의 역사를 심사한 사람들에게는 이 세 장에 주의를 기울여야 한다.
위에 제시된 장과 마지막 세 장의 소개에 따르면, 데이터 구조에서 장이 차지하는 비율은 대략 다음과 같습니다.
소개: 내용이 적고, 개념이 간단하며, 대부분의 점수는 몇 점밖에 되지 않으며, 어떤 학교는 시험을 보지도 않는다.
선형 테이블: 기본 장, 필수 내용 중 하나. 시험 문제는 대부분 기본 개념 문제이고, 명교 대규모 알고리즘 설계 문제는 매우 적다. 있는 경우 다른 장과 결합됩니다.
스택 및 대기열: 기본 장, 기본 개념 문제, 필수 내용 중 하나입니다. 스택은 종종 다른 장과 함께 검사되고 재귀와 같은 개념과 연결되어 있습니다.
현악: 기본 장, 개념은 비교적 간단합니다. 이 장에 특화된 대규모 알고리즘 설계 문제는 거의 없으며 KMP 에 따라 알고리즘을 분석하는 것이 더 일반적입니다.
다차원 배열 및 광의표
기초편에서는 배열 기반 알고리즘 문제도 비교적 흔하며, 점수가 변동보다 크기 때문에 문제의' 선택형 셀' 이나' 대기셀' 이다. 보통 출제하면 대부분 큰 문제로 출제하지 않는다. 배열은 종종 "검색, 정렬" 과 같은 장과 결합되어 하나의 큰 문제로 사용됩니다.
나무와 이진 트리
: 초점과 어려움 장, 모든 학교가 요구합니다. 이 장 학교의 차이점은 이 장이 하나 또는 두 개의 큰 알고리즘 설계 문제를 제공한다는 것이다. 여러 학교의 시험지 분석을 통해 대부분의 학교는 이 장의 대규모 알고리즘 설계 문제의 역사를 가지고 있다.
그림: 중점난점 장, 특히 명문 학교. 시험에 중점을 두면 디자인 문제 분석에 더 많이 나타난다면 나무 장과 함께 알고리즘 디자인 문제의 문제형 디자인을 형성할 수 있다.
찾다
중점난점 장, 개념이 많고, 밀접한 연관이 있어 혼동하기 쉽다. 문제는 분석적 질문으로 주어질 수 있으며, 기본 개념 문제에서도 흔히 볼 수 있다. 알고리즘 설계 문제는 배열 조합을 통해 조사하거나 트리 장과 결합하여 조사할 수 있다.
분류
검색 장과 마찬가지로, 이 장은 중점적으로 어려운 장에 속하며, 개념이 많고, 더욱 밀접하게 연결되어 있으며, 혼동하기 쉽다. 기본 개념의 고사에서, 나는 특히 각종 정렬 알고리즘의 우열을 비교하는 것을 좋아한다. 알고리즘 설계라는 큰 문제에서, 만약 하나의 문제라면, 종종 배열과 결합하여 고찰한다.
둘째, 데이터 구조의 각 장의 요점을 요약합니다.
0 장 개요
이 장은 주로 독자가 데이터 구조를 배울 수 있도록 몇 가지 기초를 마련하는 안내 역할을 한다. 우리는 주로 데이터 구조의 기본 개념, 시간 및 공간 복잡성의 개념 및 측정 방법, 알고리즘 설계 고려 사항에 초점을 맞추고 있습니다. 이 장에서는 시험 지점이 많지 않으니, 이해에 주의하면 된다.
제 1 장 선형 테이블
선형 테이블 장은 선형 구조의 시작 장으로서 선형 구조 및 전체 데이터 구조 학과의 학습에 중요한 역할을 합니다. 이 장에서는 처음으로 체인 스토리지의 개념을 체계적으로 소개했으며, 어느 장에서 이 개념을 다루든 체인 스토리지는 전체 데이터 구조 학과에서 가장 중요한 부분이 될 것입니다.
일반적으로 선형표라는 장의 중요한 시험점은 다음과 같은 방면에서 고찰할 수 있다.
1. 선형 테이블과 관련된 기본 개념 (예: 이전, 승계, 테이블 길이, 빈 테이블, 헤더 노드, 헤더 노드, 헤더 포인터 등).
2. 선형 테이블의 구조적 특징은 주로 각 노드가 첫 번째 마지막 요소를 제외한 전임자 한 명과 후임자 한 명만 있다는 것을 의미합니다.
3. 선형 테이블의 순서 저장 방법 및 특정 로켈에서의 두 가지 구현: 테이블 공간의 정적 할당 및 동적 할당. 정적 연결된 목록과 순차 연결된 목록의 유사점과 차이점.
4. 선형 테이블의 체인 저장 방법 및 단일 체인 테이블, 루프 체인 테이블, 양방향 체인 테이블, 양방향 루프 체인 테이블 등 여러 가지 일반적인 체인 테이블의 특성과 작동. 여기서 단일 체인 테이블의 병합 알고리즘, 루프 체인 테이블의 병합 알고리즘, 양방향 체인 테이블 및 양방향 루프 체인 테이블의 삽입 및 삭제 알고리즘은 일반적인 검사 방법입니다. 또한 최근 몇 년 동안 많은 학교에서 단일 체인 테이블 출력 (또는 순서 또는 역순) 을 구현하기 위해 재귀 알고리즘이 필요한 문제가 발생했습니다.
연결된 목록의 작은 문제에서, 우리는 종종 빈 시계를 판단하는 것과 같은 몇 가지 문제를 얻는다. 연결된 목록마다 빈 테이블을 판단하는 방식이 다르다. 주의하세요.
5. 선형 테이블 순차 저장과 체인 저장의 경우 각기 다른 장단점, 즉 각각 적용 가능한 경우를 비교했습니다. 단일 체인 테이블에서 헤드 포인터를 설정하고, 루프 체인 테이블에서 헤드 포인터와 인덱스 저장 구조의 장점을 설정하지 않고 테일 포인터를 설정합니다.
제 2 장 스택 및 대기열
스택과 대기열은 DS 를 배우는 많은 학생들이 직면한 첫 번째 장애물이다. 많은 사람들이 이 장부터 멀미를 시작하여 지금까지 기절했다. 따라서 스택과 큐를 이해하는 것은 DS 를 마스터하는 데 꼭 필요한 길이다.
이 장을 공부하기 전에 다음과 같은 점을 이미 알고 있는지 자문해 볼 수 있다.
1. 스택 및 대기열 정의 및 순차 스택, 체인 스택, * * * * 공유 스택, 순환 대기열, 체인 대기열 등을 포함한 데이터 구조 관련 개념. 스택 및 대기열 액세스 데이터의 특징 (저장 및 검색 포함).
2. 재귀 알고리즘. 스택과 재귀의 관계, 스택을 통해 재귀를 비재귀적인 고전 알고리즘으로 전환: N! 계승 문제, fib 시퀀스 문제, Hanoi 문제, 배낭 문제, 이진 트리의 재귀적 및 비재귀적 순회 문제, 그림 깊이 순회와 스택 간의 관계 등이 있습니다. 그중 나무와 그림과 관련된 문제는 나무와 그림의 관련 장에서 많이 조사한다.
3. 스택 적용: 숫자 표현식의 해석 원리와 괄호의 일치는 원칙적인 이해일 뿐, 이 문제의 알고리즘 설계를 조사할 구체적인 요구는 별로 없다.
4. 순환 대기열에서 대기열이 비어 있는지 꽉 찼는지 여부를 결정하는 조건, 순환 대기열에서 대기열 및 대기열에서 빼기 알고리즘.
만약 네가 위의 몇 가지를 잘 알고 있다면, 너는 스택과 대열이라는 장을 건너뛸 수 있다. 주의, 내가 말한 것은 읽지 않아도 된다는 것이지, 문제를 쓰지 않아도 되는 것이 아니다.
제 3 장 현
스택 장의 고통스러운 고통을 겪은 후 마침내 연재장을 맞았다.
문자열, 개념적으로 비교적 적은 장이자 가장 독학하기 쉬운 장 중 하나이지만, 경험한 사람들은 KMP 알고리즘이 이 장의 중요한 관문이라는 것을 알고 있다. 이 관문을 통과하면 마평천의 또 다른 큰 DS 산강이다. ᄏ
주요 요새를 뚫어야 하는 장들은 다음과 같습니다.
1. 문자열의 기본 개념, 문자열과 선형 테이블의 관계 (문자열은 모든 요소가 문자 데이터인 특수 선형 테이블), 빈 문자열과 빈 문자열의 차이, 문자열이 같은 조건입니다.
2. 문자열의 기본 동작 및 하위 문자열, 문자열 연결, 문자열 대체, 문자열 길이 계산 등을 포함한 이러한 기본 함수의 사용. 문자열의 기본 연산을 이용하여 특정 알고리즘을 완성하는 것은 많은 학교가 기본 연산에서 중점적으로 하는 것이다.
3. 수열 문자열과 체인, 블록 체인 문자열의 차이점과 연결, 구현 방법.
4.KMP 알고리즘 아이디어. KMP next 어레이 및 nextval 어레이 솔루션. 기존 패턴 일치 알고리즘의 부족과 다음 단계에 개선이 필요한 부분을 명확히 합니다. 여기서 이해 알고리즘은 핵심이고 배열은 점수 포인트입니다. 말할 필요도 없이 이 섹션은 이 장의 가장 중요한 부분입니다. 가능한 검사 방법은 next 및 nextval 의 배열 값을 찾아 결과 next 또는 nextval 의 배열 값에 따라 KMP 알고리즘을 사용하는 일치 프로세스를 제공하는 것입니다.
제 4 장 배열 및 광의표
프로그래밍 언어를 배운 친구들은 배열의 개념을 처음 본 것이 아니라' 한 번, 두 번 익혀야 한다' 고 개념적으로 큰 장애물이 없을 것이다. 그러나 대학원 과정으로서 이 장의 중점은 대학의 프로그래밍 언어와 다를 수 있으며 아래에 소개될 것이다.
데이터 구조에서 처음으로 광의표의 개념이 나타났다. 선형 테이블 또는 테이블 요소의 유한 시퀀스이며 구조를 구성하는 각 하위 테이블 또는 요소도 선형이므로 이 장도 선형 구조로 분류됩니다.
이 장의 중점은 다음과 같습니다.
1. 다차원 배열에서 배열 요소의 위치를 해석합니다. 일반적으로 배열 요소의 첫 번째 요소의 주소와 각 요소가 차지하는 주소 공간, 다차원 배열의 차원을 지정한 다음 배열에서 요소의 위치를 찾도록 요청합니다.
2. 행 스토리지와 열 스토리지의 차이점과 연결을 명확히 하여 이 두 가지 다른 저장 방법에 따라 1 의 문제를 해결할 수 있습니다.
3. 해당 변환 방법에 따라 특수 행렬의 요소를 배열에 저장합니다. 이러한 행렬에는 대칭 행렬, 삼각형 행렬, 특정 특징을 가진 스파스 행렬 등이 포함됩니다. 스파스 매트릭스의 세 가지 저장 방법, 즉 트리플, 보조 행 벡터가 있는 이진 및 교차 링크 테이블 저장에 익숙합니다. 스파스 행렬의 삼원 또는 이원 그룹을 교차 체인 테이블로 변환하는 알고리즘을 파악합니다.
4. 넓은 의표의 개념, 특히 헤더와 바닥글의 정의. 이것은 광의표 전절 알고리즘을 이해하는 기초이다. 최근 일부 학교에서는 어떤 광의표 L 에 대해 몇 차례 머리를 맞대고 끝맺는 작업을 한 뒤 문자열 값을 제시하고, 원광의표 L 을 구하는 등의 문제가 나왔다. 주의를 기울여야 한다.
5. Guangyi 테이블과 관련된 재귀 알고리즘. 광의표의 정의는 재귀적이기 때문에 광의표와 관련된 알고리즘도 종종 재귀적이다. 예를 들면: 표의 깊이를 찾고, 광의표를 복사하는 등. 이 문제는 광의표의 표현에 따라 서로 다른 각도에서 두 가지 방법으로 해결할 수 있다. 하나는 광의표를 헤더와 바닥글로 취급하고 각각 헤더와 바닥글을 조작하는 것이다. 두 번째는 일반화된 테이블을 여러 개의 하위 테이블로 보고 각 하위 테이블을 개별적으로 조작하는 것입니다.
제 5 장 나무와 이진 트리
선형 구조에 대한 과도한 학습에서 트리 구조에 대한 학습에 이르기까지 데이터 구조 과정 학습의 도약이다. 이 도약의 완성은 실제 시험에서 높은 점수를 얻을 수 있는지 여부에 직접적인 영향을 미칠 것이며, 이 모든 것은 결국 당신의 전공 총점에 영향을 미칠 것입니다. 그러므로 이 장은 나무의 중요성에 대해 자명하다.
일반적으로 트리 장의 지식 포인트는 다음과 같습니다.
이진 트리의 개념, 특성 및 저장 구조, 이진 트리 순회의 세 가지 알고리즘 (재귀 및 비재귀), 세 가지 기본 순회 알고리즘을 기반으로 하는 기타 알고리즘, 단서 이진 트리의 개념, 단서 알고리즘 및 단서 후 검색 알고리즘, 최적 이진 트리의 개념, 구성 및 적용, 트리의 개념 및 저장 형식, 트리 및 포리스트의 순회 알고리즘 및 이진 트리 순회 알고리즘과의 관계, 트리 및 포리스트와 이진 트리
위의 지식이 시험에서 주요 고사 방식을 살펴봅시다.
1. 이진 트리의 개념, 특성 및 저장 구조
조사방법은 다이트리의 정의를 직접 조사함으로써 다이트리와 일반 쌍나무의 차이를 설명할 수 있다. 전체 이진 트리 및 전체 이진 트리의 특성을 검토합니다. 일반적인 이진 트리의 5 가지 특성: 첫 번째 계층의 최대 노드 수, 깊이가 k 인 이진 트리의 최대 노드 수, n0=n2+ 1 특성, n 개 노드의 전체 이진 트리의 깊이, 이진 트리의 하위 노드와 상위 노드의 변환 관계 (왼쪽:
이진 트리 순서 저장 및 2 차 링크 테이블 저장의 장단점 및 적용 가능한 경우 이진 트리 3 차 링크 테이블을 나타내는 방법입니다.
이진 트리의 세 가지 순회 알고리즘.
이 지식 포인트의 숙달은 트리 장의 알고리즘이 이해할 수 있는지 여부에 직접적인 영향을 미치며 트리 장의 알고리즘 설계 문제가 성공적으로 완료 될 수 있는지 여부에 영향을 미칩니다. 이진 트리에는 앞 순서, 중간 순서 및 뒤 순서의 세 가지 순회 알고리즘이 있습니다. 분할의 기준은 각 알고리즘의 루트 노드 데이터가 액세스되는 순서에 따라 달라집니다. 세 가지 순회의 재귀 알고리즘을 파악하고 이를 구현하는 실제 단계뿐만 아니라 세 가지 순회의 비반복 알고리즘도 파악해야 합니다. 이진 트리 장의 많은 알고리즘이 세 가지 재귀 알고리즘에서 직접 변환 될 수 있기 때문에 (예: 잎 수 찾기), 세 가지 순회의 비재귀 알고리즘을 파악한 후 "비재귀 알고리즘을 사용하여 이진 트리의 잎 수 찾기" 와 같은 주제를 처리하는 것은 신과 같습니다. 또 다른 문장 () 에서는 재귀와 비재귀적 알고리즘을 반복하는 세 가지 메모리 버전을 제공할 것이므로 주의 깊게 기억해 주시기 바랍니다. (데이비드 아셀, Northern Exposure (미국 TV 드라마), Northern Exposure
3. 세 가지 순회 알고리즘을 기반으로 개선할 수 있는 기타 이진 트리 알고리즘:
리프 수, 이진 트리 노드 수, 1 또는 도 2 의 총 노드 수, 이진 트리 복제, 이진 트리 만들기, 왼쪽 및 오른쪽 하위 트리 교환, 값 N 의 지정된 노드 찾기, 값 N 의 지정된 노드 삭제 등 이진 트리의 재귀적 및 비재귀적 순회 알고리즘에 능숙하다면 이러한 문제를 해결하는 것은 식은 죽 먹기다.
4. 단서 이진 트리:
단서 다이트리 도입은 다이트리 순회시 재귀적 해결을 피하기 위한 것이다. 재귀는 형식적으로 이해하기 쉽지만 많은 메모리 자원을 소비하는 것은 잘 알려져 있다. 재귀적인 계층이 많으면 자원 고갈의 위험을 초래할 수밖에 없다. 이런 상황을 피하기 위해 단서 이진 트리가 공개적으로 나타났다. 단서 다이트리 트리의 경우, 단서의 본질, 세 가지 단서 알고리즘, 단서 다이트리의 순회 알고리즘, 기본 단서 다이트리의 기타 알고리즘 문제 (예: 특정 종류의 단서 다이트리 트리에서 지정된 노드의 전임 또는 후임 노드를 찾는 것은 일반적인 문제) 를 파악해야 합니다.
최적의 이진 트리 (호프만 트리):
최적의 이진 트리는 특정 문제를 해결하는 데 사용되는 특수한 이진 트리 구조입니다. 이진 트리의 각 측면에 가중치를 부여하여 이진 트리의 가중치 합계를 최소화하는 것이 전제입니다. 최적의 이진 트리 섹션에서는 알고리즘 소스 코드에 대한 직접 테스트가 거의 없습니다. 일반적으로 이 데이터 세트에 따라 최적의 다이트리를 만들어 최소 가중치의 합계를 구하는 데이터 세트를 제공합니다. 이런 제목은 난이도가 크지 않아 부제에 속한다.
6. 나무와 숲:
다이트리는 특별한 나무로, 그것의 가지가 최대 2 등 특징일 뿐만 아니라 그 질서에도 있다! 즉, 이진 트리의 왼쪽과 오른쪽 하위 트리는 서로 바꿀 수 없습니다. 만약 그것들을 교환한다면, 다른 다이트리로 변할 것이다. 이렇게 우리는 교환된 다이트리와 원래의 다이트리가 다르다고 생각한다. 그러나, 보통의 쌍가지나무에 대해서는 이런 성질이 없다.
나무와 숲의 순회는 이진 트리가 풍부하지 않다. 그들은 단지 두 가지 순회 알고리즘, 즉 전근과 후근 (삼림의 전순과 후순순회라고 함) 만 가지고 있다. 더 어려운 시험에서도 두 가지 알고리즘이 있는데, 이 두 알고리즘에 따라 다른 알고리즘을 설계해야 한다. 일반 고교에서는 이런 방법이 거의 없으며, 최대 첫 번째 또는 두 번째 뿌리에 따라 순회 순서를 적어야 한다. 이진 트리의 첫 번째 및 두 번째 순회는 순회 알고리즘과 관련이 있습니다. 첫 번째 순회는 해당 이진 트리의 1 차 순회를, 두 번째 순회는 해당 이진 트리의 중급형 순회를 통과합니다. 이곳은 많은 학교의 시험점이 되어 시험 방식이 다양하다. 어떤 사람은 이 말을 직접 시험하고, 어떤 사람은 먼저 순회 순서를 풀고 나서 이 질문에 대답하라고 한다. 다이트리, 나무, 숲은 위와 같은 대응 관계를 가질 수 있는데, 이차링크표 덕분이다. 다이트리는 그의 좌우자를 이차체인표로 저장하고, tree 는 이차체인표로 아들과 형제 (자식이라고 하는 형제체인표) 를 저장하고, forest 는 이차체인표로 아들과 형제를 저장한다.
나무장, 곳곳이 관건이고, 길은 시험 문제이며, 모든 사람은 반드시 시험에 합격해야 한다.
제 6 장 그림
선형 구조에서 트리 구조로의 전환이 데이터 구조 학과의 데이터 조직 형식 연구에 대한 승화라면, 트리 구조 연구에서 그래픽 구조 연구로의 전환은 실제 문제 해결에서 데이터 구조의 중요한 역할을 더 설명한다.
이 장의 특징은 개념이 많고 이산 수학 속 그림의 개념과 밀접한 관계가 있고, 알고리즘이 복잡하고, 시험을 받기 쉬우며, 큰 문제가 생기기 쉬우며, 특히 명문 학교라는 점이다. 대학원 과정으로서 나무와 그림 장의 지식을 고찰하지 않으면 거의 상상도 할 수 없다.
이 장의 주요 시험 지점과 이러한 시험 지점의 시험 방법을 살펴 보겠습니다.
1. 도면의 기본 개념을 검사합니다.
이 개념들은 학습도의 제 1 장의 기초이다. 이 장의 개념에는 그래프의 정의와 특징, 무향도, 직접 그래프, 입도, 출도, 전체 그래프, 하위 그래프 생성, 길이, 원, (강함) 연결 그래프, (강함) 연결 컴포넌트 등이 포함됩니다. 이러한 개념과 관련된 계산 문제도 파악해야 한다.
2. 그래픽의 여러 저장 형식을 검사합니다.
그림의 저장 형식에는 인접 행렬, (역) 인접 테이블, 교차 링크 테이블 및 인접 다중 테이블이 포함됩니다. 시험을 볼 때, 일부 학교에서는 수험생이 알고리즘이나 수작업으로 주어진 구조에 해당하는 그림의 또 다른 저장 형식을 쓰도록 요구하는 저장 형식을 제공한다.
3. 검사 그래프의 두 가지 순회 알고리즘, 즉 깊이 순회와 폭 순회가 있습니다.
깊이 순회와 폭 순회는 그림의 장에 대한 중요도가 이진 트리의 장에 대한 "앞, 중간, 뒤 순회" 의 중요성에 해당하는 그래프의 두 가지 기본 순회 알고리즘입니다. 조사할 때 Figure 의 1 장의 알고리즘 설계 문제는 "가장 긴 최단 경로 문제 찾기" 와 "두 정점 사이에 길이가 K 인 간단한 경로 문제가 있는지 확인" 과 같은 두 가지 기본 트래버스 알고리즘을 기반으로 하는 경우가 많습니다. 각각 폭 트래버스 알고리즘과 깊이 트래버스 알고리즘을 사용합니다.
4. 스패닝 트리 및 최소 스패닝 트리의 개념과 최소 스패닝 트리의 구성: PRIM 알고리즘 및 KRUSKAL 알고리즘.
조사 시 일반적으로 알고리즘 소스 코드를 작성할 필요가 없습니다. 대신 이 두 개의 최소 스패닝 트리의 알고리즘 아이디어에 따라 구성 프로세스와 최종 생성된 최소 스패닝 트리를 작성합니다.
5. 토폴로지 정렬 문제:
토폴로지 정렬에는 두 가지 방법이 있습니다. 하나는 선행자가 없는 정점 우선 순위 알고리즘이고, 다른 하나는 후행되지 않은 정점 우선 순위 알고리즘입니다. 즉, 하나는 앞에서 뒤로, 다른 하나는 뒤에서 앞으로 정렬하는 것입니다. 물론, 다음 정렬의 결과는 "역토폴로지 순서" 입니다.
6. 주요 경로 문제:
이 문제는 그림의 제 1 장 중의 난제이다. 주요 경로를 이해하는 데는 세 가지 핵심 요소가 있습니다. 첫째, 주요 경로가 무엇입니까? 둘째, 가장 빠른 시간은 무엇이며 어떻게 얻을 수 있습니까? 셋째, 늦어도 언제고 어떻게 얻을까. 간단히 말해 가장 이른 시간은' 앞에서 뒤로' 방식으로, 가장 늦은 시간은' 뒤에서 앞으로' 방식으로, 가장 늦은 시간은 모든 가장 이른 시간을 찾은 후에야 찾을 수 있다. 이 문제는 알고리즘 소스 코드를 직접 테스트하는 데 사용되지 않습니다. 일반적으로 책의 알고리즘에 따라 해결의 과정과 단계를 설명해야 한다.
주요 경로에 대한 알고리즘을 설계할 때는 인접 테이블의 스토리지 구조를 사용하여 가장 이른 시간과 가장 늦은 시간을 찾는 데 다른 처리 방법을 사용해야 합니다. 즉, 알고리즘이 시작될 때 모든 정점의 가장 이른 시간을 모두 0 으로 설정해야 합니다. 주요 경로 문제는 프로젝트 진도 제어의 중요한 방법이며 실용성이 강하다.
7. 최단 경로 문제:
주요 경로 문제와 함께 그림 1 에서는 두 가지 장애물이라고 합니다. 개념은 이해하기 쉬우며, 핵심은 알고리즘에 대한 이해이다. 최단 경로 문제는 두 가지로 나뉩니다. 하나는 한 점에서 다른 점까지의 최단 경로를 찾는 것입니다. 두 번째는 그림에서 각 정점 쌍 사이의 최단 경로를 찾는 것입니다. 이 문제도 매우 현실적인 배경 특징을 가지고 있는데, 전형적인 하나는 관광지와 관광 노선의 선택이어야 한다. 첫 번째 문제는 DIJSKTRA 알고리즘으로 해결되고 두 번째 문제는 FLOYD 알고리즘으로 해결됩니다. 차이에 주의하다.
제 7 장 검색
많은 데이터 구조의 교과서에서 찾기 및 정렬은 고급 데이터 구조에 배치됩니다. 검색과 정렬이라는 두 장은 우리가 이전에 배운 지식을 종합적으로 적용한 것으로, 트리, 체인표 등의 지식을 활용하며, 이러한 데이터 구조의 한 방면 응용은 검색과 정렬을 구성한다고 말해야 한다.
실생활에서는 검색이 거의 어디에나 있는데, 특히 지금의 인터넷 시대에는 더욱 그렇다. 모든 것은 검색과 분리 할 수 없습니다. 문서의 문자에서 인터넷 검색까지, 검색은 인터넷 시간의 대부분을 차지합니다.
이 장의 지식을 복습할 때 먼저 다음 개념을 이해해야 한다.
키워드, 주요 키워드 및 보조 키워드의 의미 정적 검색과 동적 검색의 의미와 차이점 평균 검색 길이 ASL 의 개념과 다양한 검색 알고리즘에서의 계산 방법 및 결과, 특히 일부 일반적인 구조의 ASL 값은 기억해야 합니다.
DS 교과서에서 검색은 일반적으로 1st 의 세 가지 범주로 나뉩니다. 시퀀스 테이블에서 검색합니다. 2, 트리 테이블에서 검색; 3, 해시 테이블을 확인하십시오. 다음은 시험 지식 포인트 및 시험 방법에 대해 자세히 설명합니다.
1. 선형 테이블에서 찾기:
주로 순서표, 순서표, 색인순서표 세 가지 선형 구조로 나뉜다. 첫 번째 경우 기존 검색 방법을 사용하여 하나씩 비교합니다. 우리는 이진 검색 방법을 사용하여 정렬된 테이블을 정렬합니다. 세 번째 인덱스 구조의 경우 인덱스 조회 알고리즘을 사용합니다. 수험생은 이 세 표 아래의 ASL 값과 세 가지 알고리즘의 구현에 주의해야 한다. 여기서 이진 검색법은 적용 가능한 조건과 재귀 구현 방법에 특별한주의를 기울여야 합니다.
2. 트리 테이블에서 다음을 찾습니다.
이것은이 장의 초점과 어려움입니다. 이 섹션에서는 트리 테이블을 사용하는 검색에 대해 설명하므로 tree one 의 일부 개념과 쉽게 혼동할 수 있습니다. 이 섹션의 내용은 트리 장 내용과 관련이 있지만 많은 차이점이 있으므로 주의해야 합니다. 트리 테이블은 주로 2 차 정렬 트리, 균형 이진 트리, B 트리 및 키 트리 범주로 나뉩니다. 그중에서도 특히 처음 두 가지 구조가 더 중요하며, 일부 명문대는 B 나무를 시험하는 경향이 있다. 이진 정렬 트리와 밸런스 다이트리는 특수한 다이트리이기 때문에 다이트리와의 관계가 더욱 밀접하다. 여기서 이진 트리의 장을 배우는 것은 어렵지 않다.
이진 정렬 트리, 즉 "작은 왼쪽과 오른쪽" 은 중간 순서 트래버스 결과가 증가하는 순서입니다. 균형 이진 트리는 2 차 정렬 트리의 최적화이며, 그 특성도 2 차 정렬 트리입니다. 그러나 균형 이진 트리는 왼쪽 및 오른쪽 하위 트리의 깊이를 제한합니다. 깊이 차이의 절대값은 1 보다 클 수 없습니다. 이진 정렬 트리의 경우 "이진 트리가 이진 정렬 트리인지 여부 확인" 알고리즘을 자주 테스트합니다. 이 알고리즘은 재귀적이거나 비재적일 수 있습니다. 균형 이진 트리의 설립도 자주 시험되는 점이지만, 이 지식 포인트는 결국 균형 이진 트리의 네 가지 조정 알고리즘에 초점을 맞추고 있기 때문에 균형 이진 트리의 네 가지 조정 알고리즘을 파악해야 합니다. 조정에 대한 참조 중 하나는 조정 전후의 중간 순서 순회 결과가 동일하다는 것이다. (데이비드 아셀, Northern Exposure (미국 TV 드라마), 균형명언)
B 트리는 이진 정렬 트리의 추가 개선으로, 삼지창, 네 발 ... 정렬 트리로 해석될 수 있습니다. B 트리의 검색 알고리즘 외에도 B 트리의 삽입 및 삭제 알고리즘에 각별한 주의를 기울여야 합니다. 이 두 알고리즘은 B 트리 노드의 분할 및 병합과 관련이 있기 때문에 어려운 문제입니다. B 나무는 명문 학교를 신청하는 학생들이 주의해야 할 중점 중 하나이다.
문자 트리라고도 하는 키워드 트리는 영어 단어를 찾는 데 특히 적합합니다. 일반적으로 알고리즘의 소스 코드를 완전히 설명할 필요는 없습니다. 대신 알고리즘 아이디어에 따라 키 트리를 만들고 대략적인 검색 프로세스를 설명합니다.
3. 기본 해시 테이블 조회 알고리즘:
해시' 라는 단어는' 해시' 라는 단어에서 번역된 외래어로,' 해시' 또는' 해시' 를 의미한다. 해시 테이블 검색의 기본 아이디어는 현재 찾고 있는 데이터의 특성에 따라 키워드를 인수로 기록하는 함수를 설계하는 것입니다. 이 함수를 통해 키워드가 변환되면 해석 결과가 찾을 주소입니다. 해시 테이블을 기반으로 한 조사점에는 해시 함수의 설계, 충돌 해결 방법 선택, 충돌 처리 프로세스에 대한 설명이 포함됩니다.
제 8 장 내부 분류
내부 배열은 DS 과정의 마지막 중요한 장으로, 빈 칸 채우기, 선택, 판단, 심지어 큰 알고리즘 문제 등 많은 문제를 기반으로 합니다. 하지만 한 가지 귀결되는 것은 책의 다양한 정렬 알고리즘과 그 사상, 장단점 및 성능 지표 (시간 복잡도) 를 잘 알고 있는지 조사하는 것이다. (존 F. 케네디, Northern Exposure (미국 TV 드라마), 독서명언)
이 장에서, 우리의 중점은 상술한 장과 다를 것이다. 정렬 장의 전체 구조와 다양한 알고리즘을 보다 포괄적으로 이해할 수 있도록 다음과 같은 측면에서 정렬 장을 다르게 규정합니다.
정렬 알고리즘 유형에 따라 이 장에서는 주로 삽입, 선택, 교환, 병합 및 개수 정렬 방법에 대해 설명합니다.
여기서 삽입 정렬은 직접 삽입, 반삽입, 2 로 삽입, 힐 정렬로 나눌 수 있습니다. 이러한 삽입 정렬 알고리즘의 가장 근본적인 차이점은 결국 어떤 규칙을 사용하여 새 요소의 삽입점을 찾는 것입니다. 직접 삽입은 차례대로 찾고, 반삽입은 반으로 찾는다. 힐 정렬은 각 참여 정렬의 전체 숫자 범위에 대한 증분을 제어하여 정렬 효율성을 높입니다.
교환 정렬은 버블링 정렬이라고도 하며, 교환 정렬을 기반으로 개선하여 빠르게 정렬할 수 있습니다. 빠른 정렬의 아이디어는 한 문장이다: 중간 수로 정렬할 데이터 세트를 둘로 나누는 것이다. 빠른 정렬,' 문제 척도' 라는 개념상 힐의 개념과는 약간 반대이다. 빠른 정렬은 먼저 규모가 큰 것을 처리한 다음 처리 규모를 점차 줄여 정렬 목적을 달성하는 것이다.
정렬을 선택하는 것이 이전 정렬 알고리즘보다 더 어렵습니다. 단순 선택, 트리 선택 및 힙 배열로 나눌 수 있습니다. 이 세 가지 방법의 차이점은 어떤 규칙에 따라 최소 수를 선택하느냐에 있다. 단순 선택은 간단한 배열 순회 체계를 통해 최소 수를 결정하는 것입니다. 나무 선택은' 선수권대회' 와 같은 사고방식을 통해 두 숫자를 비교하고, 큰 (작은) 것을 끊임없이 제거하고, 마지막으로 가장 작은 (큰) 수를 뽑는다. 힙 정렬은 힙의 데이터 구조를 활용하여 힙 요소 삭제, 조정 등의 일련의 작업을 통해 힙 맨 위의 최소 수를 선택합니다. 힙 정렬에서 힙 설립과 힙 조정은 중요한 시험점이다. 나무 선택 순서는 일부 학교의 대규모 알고리즘 문제에도 등장했습니다. 주의하세요.
병합 정렬은 이름에서 알 수 있듯이' 병합' 작업을 통해 정렬 목적을 달성하는 것이다. 합병이기 때문에 세 개 이상의 데이터 집합이어야 병합할 수 있다. 따라서 병합 정렬에서 가장 주목받는 것은 2 번 병합이다. 알고리즘의 생각은 비교적 간단하므로 한 가지 기억해야 한다. 병합 정렬은 안정적인 정렬이다.
기수 정렬은 매우 특별한 정렬 방법이며, 바로 그것의 특수성 때문에 기수 정렬은 포커 정렬과 같은 특수한 상황에 더 적합하다. 기수 정렬은 다중 키 정렬 (포커 정렬) 과 체인 정렬 (정수 정렬) 의 두 가지 유형으로 나뉩니다. 기수 정렬의 핵심 사상은' 기수공간' 의 개념을 이용하여 문제의 규모를 규범화하고 줄이는 것이며, 정렬 과정에서 기수 정렬의 사상에 따라 키워드를 비교하는 한, 이렇게 얻어진 최종 순서는 질서 있는 순서다.
이 장에서는 다양한 정렬 알고리즘의 사상, 의사 코드 구현 및 시간 복잡성을 파악해야 하므로 학습 시 규범, 요약 및 비교에 더 많은 주의를 기울여야 합니다. 또한 교재의 10.7 부분에 대해서는 무턱대고 외워야 한다. 이해를 바탕으로, 이 단락은 거의 많은 학교의 매년 필수 시험점이 되었다.
이로써 데이터 구조의 모든 장에 대한 주요 문제가 규범화되었다. 청화엄판 교재를 사용하는 학생은 본첩이 제시한 요점을 참고하여 복습할 수 있다. 하지만 필자의 수준이 제한되어 있기 때문에, 많은 시험점이 규범화되지 않았거나, 일부 시험점이 규범적으로 틀릴 수도 있다. 여기서 필자는 여러분의 친구들이 직시하기를 진심으로 바라며, 저도 계속 보완하여 새로운 데이터 구조 복습 요약과 노트를 발표할 것입니다. (데이비드 아셀, Northern Exposure (미국 TV 드라마), 예술명언)
엄민 데이터 구조에 대한 주석.
제 2 장: 선형 테이블 (연습, 답변 및 요점 포함)
--
이 장의 중점은 순서표와 단일 링크표에서 구현된 다양한 기본 알고리즘과 관련 시간 성능 분석을 파악하는 것입니다. 어려움은 이 장에서 배운 기본 지식을 이용하여 효과적인 알고리즘을 설계하고 선형 테이블과 관련된 응용 문제를 해결하는 것이다.
달성해야 할 콘텐츠 계층은 선형 테이블의 논리적 구조적 특성입니다. 선형 테이블에 정의된 기본 연산은 더 복잡한 연산은 기본 연산을 사용하여 구성됩니다.
달성해야 할 계층 내용에는 시퀀스 테이블의 의미와 특성, 시퀀스 테이블 삽입 및 삭제 작업, 평균 시간 성능 분석, 간단한 애플리케이션 문제 해결 등이 포함됩니다.
연결된 목록이 선형 테이블에서 요소 간의 논리적 관계를 나타내는 방법 단일, 이중 및 순환 체인 테이블의 링크 방식 차이 단일 체인 테이블에서 구현된 테이블 작성, 찾기, 삽입 및 삭제와 같은 기본 알고리즘과 시간 복잡성 루프 체인 테이블의 끝 포인터는 헤드 포인터의 역할을 대체하며, 단일 루프 체인 테이블의 알고리즘과 단일 체인 테이블의 해당 알고리즘의 유사점과 차이점. 양방향 연결된 목록의 정의 및 관련 알고리즘 체인 테이블 설계 알고리즘을 사용하여 간단한 응용 프로그램 문제를 해결합니다.
계층 달성이 필요한 내용은 순서 테이블과 연결된 테이블의 비교이며, 더 나은 시공간 성능을 위해 저장 구조로 하나를 선택하는 방법입니다.
--
선형 테이블의 논리적 구조적 특징은 이해하기 쉽다. 이름에서 알 수 있듯이, 그것의 논리적 구조적 특징은 위에 매듭이 있는 선과 같이 매우 형상적이다. 이 선에 꼬임이 있는 경우 비어 있지 않은 테이블입니다. 시작 노드 하나, 끝 노드 하나, 다른 꼬임 앞뒤에 노드 하나 (직전 및 직접 승계) 만 있습니다.
선형 테이블에 정의된 기본 작업에는 주로 빈 테이블 구성, 테이블 길이 찾기, 노드 가져오기, 찾기, 삽입 및 삭제가 포함됩니다.
--
선형 테이블의 논리적 구조와 저장 구조의 관계. 컴퓨터에서 선형 테이블의 노드는 저장 장치에 여러 가지 방법으로 저장됩니다. 가장 쉬운 방법은 순서대로 저장하는 것입니다. 선형 테이블의 논리적 구조에 따라 연속 주소가 있는 스토리지 유닛 그룹에 순차적으로 저장됩니다. 스토리지 유닛에 있는 각 요소의 물리적 위치는 논리적 구조에 있는 각 노드의 인접 관계와 일치합니다.
시퀀스 테이블에서 구현되는 기본 작업은 주로 삽입 및 삭제 작업에 대해 설명합니다. 우리는 실천을 통해 관련 알고리즘을 파악한다. 순서 테이블 삽입 및 삭제의 경우 평균 시간 복잡도는 O(n) 입니다.
--
선형 테이블의 체인 저장 구조. 순서 테이블과 다릅니다. 체인 테이블은 메모리 내 어느 곳에나 분산될 수 있는 임의의 저장 장치 세트로 선형 테이블을 저장하는 노드입니다. 따라서 연결된 목록에 있는 노드의 논리적 및 물리적 순서가 반드시 같을 필요는 없습니다. 따라서 노드 간의 논리적 관계를 정확하게 나타내기 위해 각 노드의 값 (즉