데이터 구조(C 언어 버전)에 대한 정보가 있나요?

데이터 구조 복습 핵심 요약 노트 [Tsinghua Yan Weimin 판]

데이터 구조 복습 핵심 요약 노트 [Tsinghua Yan edition 교과서에 적합]

1. 구조 장 구조 및 주요 구성 요소

데이터 구조 주제의 장은 기본적으로 소개, 선형 테이블, 스택 및 큐, 문자열, 다차원 배열 및 일반화 테이블, 트리 및 이진 트리, 그래프, 검색으로 나뉩니다. , 내부 행, 외부 행, 파일 및 동적 저장소 할당.

대부분의 학교에서 "아웃소싱, 파일 및 동적 저장소 할당"의 세 장은 기본적으로 대부분의 대학의 컴퓨터 학부 교육 과정에서도 테스트되지 않습니다. 기본적으로 강의는 진행되지 않습니다. 따라서 기본 개념만 알고 있다면 이 세 장에 너무 많은 에너지를 쏟을 필요는 없습니다. 하지만 명문 학교에 지원한다면, 특히 학교가 시험지에서 이 세 장을 평가한 이력이 있다면, 친구들은 이 세 장에 주의를 기울여야 합니다.

위에서 제공한 장과 마지막 세 장의 소개에 따르면 데이터 구조에 관한 장의 비율은 대략 다음과 같습니다.

소개: 내용이 거의 없음, 단순함 개념도 있고, 대부분의 점수가 소수에 불과합니다.

선형 테이블: 필수 시험 중 하나인 기본 장입니다. 대부분의 시험 문제는 기본 개념 문제입니다. 명문 학교의 시험 문제 중에는 대규모 알고리즘 설계 문제가 거의 없습니다. 그렇다면 다른 장의 내용과 결합됩니다.

스택과 큐: 기본 장, 기본 개념 질문을 쉽게 출제할 수 있는 필수 시험 중 하나. 스택은 다른 장과 연계하여 검토하는 경우가 많으며, 재귀와 같은 개념과 관련하여 검토하는 경우가 많습니다.

문자열: 기본 장이며 개념은 비교적 간단합니다. 이 장을 특별히 겨냥한 대규모 알고리즘 설계 질문은 거의 없습니다. 가장 일반적인 질문은 KMP를 기반으로 한 알고리즘 분석입니다.

다차원 배열 및 일반화된 테이블

: 기본 장, 배열 기반 알고리즘 질문도 일반적이며 분수 비율은 크게 변동하며 이는 "선택 단위" 또는 "호우"입니다. 질문의 보완 단위." 일반적으로 물어볼 질문이 있다면 대부분 큰 질문이 아닐 것입니다. 배열은 주요 테스트로 "검색 및 정렬"과 같은 장과 결합되는 경우가 많습니다.

트리 및 이진 트리

: 중요하고 어려운 장, 각 학교에 필요한 장. 본 장에서 각 학교에서 출제하는 질문의 차이는 본 장에서 대규모 알고리즘 설계 질문을 1개 또는 2개 출제하느냐에 있습니다. 많은 학교의 시험지 분석을 통해 대부분의 학교는 이 장에서 대규모 알고리즘 설계 문제를 설정한 이력을 가지고 있습니다.

사진: 핵심적이고 어려운 장, 특히 유명한 학교는 시험 보는 것을 좋아합니다. 시험의 초점으로 삼으면 분석 및 설계 문제에 주로 등장하게 되며, 트리 장***과 함께 알고리즘 설계 문제의 문제 설계를 구성할 수도 있습니다.

검색

: 핵심적이고 어려운 장에는 개념이 많고 밀접하게 연관되어 있어 혼동되기 쉽습니다. 질문은 분석 질문으로 출제될 수 있으며, 기본 개념 질문에서도 공통적으로 출제됩니다. 알고리즘 설계 질문은 배열 또는 트리 장과 결합하여 테스트할 수 있습니다.

정렬

: 장을 검색하는 것과 마찬가지로 이 장 역시 핵심적이고 어려운 장으로, 더 많은 개념과 더 긴밀한 연결이 있어 개념을 혼동하기 더 쉽습니다. 기본 개념을 검토할 때 특히 다양한 정렬 알고리즘의 장단점 비교와 같은 질문을 검토하는 것을 좋아합니다. 주요 알고리즘 설계 질문에 질문이라면 어레이와 조합하여 테스트하는 경우가 많습니다.

2. 데이터 구조 각 장의 핵심 포인트:

0장 개요

이 장에서는 주로 선도적인 역할을 하며 독자들이 데이터 구조를 배울 수 있도록 도와줍니다. 몇 가지 사전 준비가 이루어졌습니다. 누구나 주로 데이터 구조의 기본 개념, 시간과 공간 복잡도의 개념과 측정 방법, 알고리즘 설계 시 주의 사항에 주의를 기울입니다. 이 장에는 테스트 포인트가 많지 않으므로 이해하기 위해 약간의 주의를 기울이십시오.

1장 선형 테이블

선형 구조의 첫 번째 장으로서 선형 구조 및 전체 데이터 구조 분야 연구에서 선형 테이블의 역할을 과소평가할 수 없습니다. 이 장에서는 체인 스토리지의 개념이 처음으로 체계적으로 소개됩니다. 체인 스토리지의 개념은 어떤 장에서 이 개념을 포함하든 전체 데이터 구조 분야의 최우선 순위가 될 것입니다.

일반적으로 선형 테이블 장에서 검토할 중요한 테스트 포인트에는 다음 측면이 포함됩니다.

1. 선행 테이블, 후속 테이블과 같은 선형 테이블과 관련된 기본 개념 테이블 길고 빈 목록, 첫 번째 노드, 헤드 노드, 헤드 포인터 및 기타 개념.

2. 선형 테이블의 구조적 특징은 주로 첫 번째 요소와 마지막 요소를 제외하고 각 노드에는 하나의 선행 요소와 하나의 후속 요소만 있습니다.

3. 선형 테이블의 순차적 저장 방법과 특정 언어 환경에서의 두 가지 다른 구현: 테이블 공간의 정적 할당과 동적 할당. 정적 연결 목록과 순차 목록의 유사점과 차이점

4. 선형 목록의 연결 저장 방법과 일반적으로 사용되는 연결 목록인 단일 연결 목록, 순환 연결 목록, 이중 연결 목록 및 양방향 순환 연결 목록의 특성과 작동. 그 중 단일 연결 목록의 병합 알고리즘, 순환 연결 목록의 병합 알고리즘, 이중 연결 목록 및 이중 순환 연결 목록의 삽입 및 삭제 알고리즘은 모두 비교적 일반적인 검사 방법입니다. 또한 최근에는 단일 연결 목록 출력(순차 또는 역순일 수 있음)을 구현하기 위해 재귀 알고리즘을 사용해야 하는 문제가 많은 학교에서 반복적으로 나타났습니다.

작은 질문 유형의 연결 목록에서는 테이블이 비어 있는지 판단하는 것과 같은 질문을 자주 받습니다. 연결된 목록에 따라 목록이 비어 있는지 확인하는 방법이 다르므로 주의하시기 바랍니다.

5. 선형 테이블 순차 저장과 체인 저장의 경우 서로 다른 장점과 단점, 즉 각각의 적용 사례를 비교합니다. 단일 연결 리스트에서 헤드 포인터를 설정하는 것, 헤드 포인터를 설정하지 않고 원형 연결 리스트에서 테일 포인터를 설정하는 것, 그리고 인덱스 저장 구조의 각각의 이점.

제2장 스택과 큐

스택과 큐는 DS를 배우는 많은 학생들에게 첫 번째 걸림돌이 됩니다. 이 장부터 많은 사람들이 멀미를 느끼기 시작하고 이제 계속해서 기절합니다. 따라서 스택과 큐를 이해하는 것이 DS 마스터가 되는 유일한 방법입니다.

이 장을 공부하기 전에 다음 사항을 이미 알고 있는지 자문해 보세요.

1. 스택 및 큐의 정의와 다음을 포함한 관련 데이터 구조의 개념. 스택, 체인 스택, 공유 스택, 순환 큐, 체인 큐 등 스택 및 큐 데이터 액세스의 특성(저장 및 검색이라는 두 부분으로 구성되어 있음)

2. 재귀 알고리즘. 스택과 재귀 간의 관계, 그리고 스택을 사용하여 재귀를 비재귀로 바꾸는 고전적인 알고리즘: n! 계승 문제, fib 시퀀스 문제, 하노이 문제, 배낭 문제, 이진 트리의 재귀 및 비재귀 순회 문제, 그래프 및 스택 관계 등의 깊이 탐색 그 중 트리와 그래프에 관한 이슈는 주로 트리와 그래프 관련 장에서 살펴볼 예정이다.

3. 스택 적용: 수치 표현식, 괄호 쌍 등을 해결하는 원리는 원칙적으로만 이해됩니다. 이 주제를 구체적으로 테스트해야 하는 알고리즘 설계 질문은 많지 않습니다.

4. 순환 대기열에서 팀 비어 있음 및 대기열 가득 참 조건을 결정하고 순환 대기열에서 대기열 추가 및 대기열 제거 알고리즘.

위 내용을 이미 잘 알고 계시다면 스택과 큐에 관한 장을 읽을 필요는 없습니다. 제가 책을 읽을 필요가 없다고 말한 것이지, 질문을 할 필요가 없다는 것은 아닙니다.

3장 추안

스택 첫 번째 장의 고통스러운 고통을 겪은 후, 마침내 추안 첫 장의 어두운 미래가 찾아왔습니다.

문자열은 개념상 상대적으로 작은 장이고 스스로 배우기 가장 쉬운 장 중 하나이기도 합니다. 그러나 여기까지 온 모든 사람들이 알고 있듯이 KMP 알고리즘은 이 장에서 중요한 장애물입니다. . 이 고비를 뚫고 드디어 지나갈 때 다시 광활한 평원과 함께 아름다운 산과 강이 보였습니다. 하하.

문자열 장에서 극복해야 할 주요 요새는 다음과 같습니다.

1. 문자열의 기본 개념, 문자열과 선형 테이블의 관계(문자열은 특수한 선형 유형입니다.) 요소는 모두 문자 데이터임 표), 빈 문자열과 공백 문자열의 차이, 문자열 동일 조건

2. 문자열에 대한 기본 작업 및 이러한 기본 기능의 사용: 하위 문자열 가져오기, 연결 문자열, 문자열 바꾸기, 문자열 찾기 오래 기다리세요. 기본 문자열 연산을 사용하여 특정 알고리즘을 완성하는 것은 많은 학교의 기본 연산 시험의 초점입니다.

3. 시퀀스 문자열, 체인 문자열, 블록체인 문자열의 차이점과 연결 및 구현 방법.

4.KMP 알고리즘 아이디어. KMP에서 다음 배열과 nextval 배열을 찾는 방법.

기존 패턴 매칭 알고리즘의 단점을 명확히 하고 다음 배열을 개선해야 함을 명확히 합니다. 그 중 알고리즘을 이해하는 것이 핵심이고, 배열을 찾아내는 것이 점수입니다. 말할 필요도 없이 이 부분이 이 장의 초점이다. 가능한 조사 방법은 next 및 nextval 배열 값을 찾고, 획득된 next 또는 nextval 배열 값을 기반으로 KMP 알고리즘을 사용하여 일치 프로세스를 제공하는 것입니다.

4장 배열과 일반화된 테이블

프로그래밍 언어를 공부한 분들이라면 배열의 개념을 처음 접한 것은 아닙니다. 따라서 개념적으로는 큰 장애가 없을 것입니다. 그러나 대학원 과정인 만큼 이 장의 초점은 아래에서 소개할 대학의 프로그래밍 언어와는 다를 수 있다.

일반화된 테이블이라는 개념은 데이터 구조에서 처음으로 등장했습니다. 선형 리스트 또는 테이블 요소의 유한한 시퀀스입니다. 구조를 구성하는 각 하위 리스트나 요소도 선형 구조이므로 이 장도 선형 ​​구조에 포함됩니다.

이 장의 시험 핵심 사항은 다음과 같습니다.

1. 다차원 배열에서 배열 요소의 위치를 ​​해결합니다. 일반적으로 배열 요소의 첫 번째 요소의 주소와 각 요소가 차지하는 주소 공간이 다차원 배열의 차원과 함께 주어지며 배열에서 요소의 위치를 ​​찾으라고 요청합니다.

2. 행 저장과 열 저장의 차이점과 연관성을 명확히 하고, 이 두 가지 저장 방법에 따라 1의 문제 유형을 풀 수 있습니다.

3. 특수 행렬의 요소를 해당 변환 방법에 따라 배열에 저장합니다. 이러한 행렬에는 대칭 행렬, 삼각 행렬, 특정 특성을 갖는 희소 행렬 등이 포함됩니다. 희소 행렬의 세 가지 다른 저장 방법인 삼중항, 보조 행 벡터가 있는 이진 삼중항, 교차 연결 목록 저장 방법에 익숙합니다. 희소 행렬의 삼중 또는 튜플을 교차 연결된 목록으로 변환하는 알고리즘을 마스터하세요.

4. 일반화된 테이블의 개념, 특히 테이블 헤더와 테이블 바닥글의 정의가 명확해야 합니다. 이 점이 일반화된 테이블 알고리즘 전체를 이해하기 위한 기초가 된다. 최근 일부 학교에서는 특정 일반화 테이블 L의 여러 헤드 및 테일 연산 후 문자열 값이 주어지면 원래의 일반화 테이블 L을 찾아야 하는 유형의 질문이 나타났습니다. 모두가 주의를 기울여야 합니다.

5. 일반화된 테이블과 관련된 재귀 알고리즘. 일반화된 테이블의 정의는 재귀적이므로 일반화된 테이블과 관련된 알고리즘도 재귀적인 경우가 많습니다. 예: 테이블 깊이 찾기, 일반화된 테이블 복사 등 이러한 질문은 일반화된 표의 표현 형태에 따라 다양한 각도에서 두 가지 방식으로 대답할 수 있습니다. 하나는 일반화된 표를 머리글과 바닥글의 두 부분으로 간주하고 각각 머리글과 바닥글에 대해 작동하는 것입니다. 두 번째는 일반화된 테이블을 여러 개의 하위 테이블로 간주하고 각 하위 테이블을 별도로 운영하는 것입니다.

5장 트리와 이진 트리

선형 구조 연구에서 트리 구조 연구로의 전환은 데이터 구조 과정 연구의 도약입니다. 시험의 질은 실제 시험에서 높은 점수를 얻을 수 있는지 여부와 직접적인 관련이 있으며, 이 모든 것이 궁극적으로 전문 과정의 총점에 영향을 미칩니다. 그러므로 나무 장의 중요성은 자명합니다.

일반적으로 트리 장의 지식 포인트는 다음과 같습니다:

이진 트리의 개념, 속성 및 저장 구조, 이진 트리 탐색을 위한 세 가지 알고리즘(재귀 및 비재귀) , 기본 순회 알고리즘을 기반으로 이진 트리를 구현하기 위한 세 가지 다른 알고리즘에서는 단서 이진 트리의 개념, 단서 알고리즘 및 단서 검색 알고리즘, 최적 이진 트리의 개념과 구성 및 적용, 트리의 개념 및 저장 형태, 트리와 포리스트 간의 관계 순회 알고리즘과 이진 트리 순회 알고리즘에 대한 연결, 트리를 포리스트 및 이진 트리로 변환합니다.

위 지식에 대한 시험의 주요 테스트 방법을 살펴보겠습니다.

1. 이진 트리의 개념, 속성 및 저장 구조

테스트 방법은 다음과 같습니다. 이진 트리의 정의를 직접 검사하여 이진 트리와 일반 두 가지 트리의 차이점을 설명할 수 있습니다. 전체 이진 트리와 완전한 이진 트리의 속성과 5가지 속성을 검사합니다. 일반 이진 트리의 경우: i번째 레벨의 최대 노드 수, 깊이가 k인 이진 트리의 최대 노드 수 포인트 수, n0=n2의 속성 1, 완전 이진의 깊이 n개의 노드를 갖는 트리, 이진 트리를 순차적으로 저장할 때 자식 노드와 부모 노드 사이의 변환 관계(왼쪽: 2*i, 오른쪽: 2*i 1 ).

이진 트리의 순차 저장과 이진 연결 리스트 저장의 각각의 장단점과 적용 사례, 이진 트리의 삼항 연결 리스트 표현 방법.

2. 이진 트리에 대한 세 가지 탐색 알고리즘

이 지식 포인트의 품질은 트리 장의 알고리즘을 이해할 수 있는지 여부와 직접적으로 관련되며, 그 다음에는 트리와도 관련됩니다. 장. 알고리즘 설계 문제를 성공적으로 완료할 수 있는지 여부. 이진 트리 순회 알고리즘에는 선순서, 중위순, 후순의 세 가지가 있습니다. 분할 기준은 각 알고리즘의 루트 노드 데이터에 대한 액세스 순서에 따라 다릅니다. 세 가지 재귀 순회 알고리즘에 능숙하고 실제 실행 단계를 이해해야 할 뿐만 아니라 세 가지 비재귀 순회 알고리즘에도 능숙해야 합니다. 이진 트리에 관한 장의 많은 알고리즘은 세 가지 재귀 알고리즘(예: 잎 수 찾기)에서 직접 변환될 수 있으므로 순회를 위한 세 가지 비재귀 알고리즘을 마스터한 후에는 다음과 같은 문제를 처리할 수 있습니다. as: "비재귀 알고리즘을 사용하여 이진 트리 찾기" "잎의 수"는 제가 글을 쓰는데 많은 에너지를 쏟는 것처럼 느껴지는 주제입니다. 세 가지 순회 재귀 및 비재귀 알고리즘의 암기 버전은 다른 기사 시리즈(/ibbs.dll?bbsdisp?t_id=301583amp; bp=2amp; bt=0)에서 제공할 예정입니다. 그것을 기억하세요.

3. 세 가지 순회 알고리즘을 기반으로 수정될 수 있는 기타 이진 트리 알고리즘:

리프 수 찾기, 이진 트리 노드의 총 개수 찾기, 정도 찾기 1 또는 차수 총 노드 수는 2이고, 이진 트리를 복사하고, 이진 트리를 구축하고, 왼쪽 및 오른쪽 하위 트리를 교환하고, n 값을 갖는 지정된 노드를 찾고, n 값을 갖는 지정된 노드를 삭제하고, 등. 이진 트리의 재귀 및 비재귀 순회 알고리즘을 마스터할 수 있다면 위의 문제를 해결하는 것은 매우 쉬운 일이 될 것입니다.

4. 단서 이진 트리:

단서 이진 트리는 이진 트리 탐색과 같은 재귀적 솔루션을 피하기 위해 도입되었습니다. 우리 모두 알고 있듯이, 재귀는 형태적으로는 비교적 이해하기 쉽지만, 메모리 자원을 많이 소모하므로, 이러한 상황을 피하기 위해 재귀 수준이 너무 많으면 필연적으로 자원 고갈의 위험이 따릅니다. , 단서 이진 트리가 웅장한 모습으로 나타났습니다. 단서 이진 트리의 경우 단서의 본질, 세 가지 단서 알고리즘, 단서 후 이진 트리의 순회 알고리즘, 기본 단서 이진 트리의 기타 알고리즘 문제(예: 특정 노드의 전임자 또는 전임자 찾기)를 마스터해야 합니다. 특정 유형의 단서 이진 트리) 후속 노드는 자주 묻는 질문 유형입니다.

5. 최적 이진 트리(허프만 트리):

최적 이진 트리는 특정 문제를 해결하기 위해 도입된 특별한 이진 트리 구조입니다. 그 전제는 이진의 각 모서리를 제공하는 것입니다. 트리 가중치가 주어지면, 이렇게 형성된 이진 트리는 가중치에 따라 가장 작은 합을 갖습니다. 최적 이진 트리 섹션에서는 알고리즘의 소스 코드를 직접 검사하는 사람이 거의 없습니다. 일반적으로 데이터 세트가 제공되고 이 데이터 세트를 기반으로 최적 이진 트리를 구축하고 최소 가중치의 합을 구하라는 요청을 받습니다. 질문 유형은 어렵지 않습니다.

6. 나무와 숲:

이진 트리는 특별한 종류의 나무입니다. 이 특별함은 가지가 최대 2개라는 사실뿐만 아니라 다른 특성에도 기인합니다. 또한 가장 중요한 특징은 이진 트리가 정렬되어 있다는 것입니다! 즉, 이진 트리의 왼쪽과 오른쪽 자식은 교환할 수 없습니다. 교환되면 다른 이진 트리가 됩니다. 이러한 방식으로 교환 후의 이진 트리와 원래 이진 트리는 서로 다른 이진 트리라고 생각합니다. 나무. 그러나 일반적인 두 가지 트리에는 이 속성이 존재하지 않습니다.

트리와 포리스트의 순회는 이진 트리의 순회만큼 풍부하지 않습니다. 루트 우선 및 루트 사후 순회 알고리즘만 있습니다(포리스트의 경우 선주문 및 사후라고 함). -순회 순회).

더 어려운 시험에는 이 두 가지 알고리즘을 기반으로 확장하여 이 두 가지 알고리즘을 사용하여 다른 알고리즘을 설계하도록 요구하는 시험도 있습니다. 그러나 이러한 종류의 시험 방법은 일반 대학에서 거의 사용할 수 없습니다. , 다른 알고리즘을 설계하려면 이 두 가지 알고리즘만 사용하면 됩니다. 루트 또는 사후 루트가 순회 시퀀스를 작성합니다. 두 개의 루트 우선 및 마지막 루트 순회는 이진 트리의 순회 알고리즘에 해당합니다. 루트 우선 순회는 이진 트리의 선순 순회에 해당하고 루트 사후 순회는 이진 트리의 순차 순회에 해당합니다. 이것은 많은 학교에서 테스트 포인트가 되었으며 테스트 방법은 다양합니다. 일부는 이 문장을 직접 테스트하고 일부는 순회 시퀀스를 먼저 해결한 후 이 질문에 답하도록 요청합니다. 이진트리, 트리, 포레스트가 위와 같은 대응 관계를 가질 수 있는 이유는 모두 이진 연결 리스트 덕분이다. 이진 트리는 이진 연결 목록을 사용하여 왼쪽 및 오른쪽 자식을 각각 저장합니다. 트리는 이진 연결 목록을 사용하여 자식 및 형제 연결 목록(자식 및 형제 연결 목록이라고 함)을 저장하고 포리스트도 이진 연결 목록을 사용하여 다음을 수행합니다. 그 자녀와 형제를 저장하라.

트리의 모든 부분이 핵심이며 모든 단계는 테스트 문제입니다.

6장 그림

선형 구조에서 트리 구조 연구로의 전환이 데이터 구조 분야의 데이터 조직 형태 연구의 승화라면, 트리 구조 연구는 트리 구조로 전환된다. 그래프 구조에 대한 연구를 통해 실제 문제를 해결하는 데 데이터 구조의 중요한 역할을 확인할 수 있었습니다.

이 그래프 장의 특징은 이산 수학의 그래프 개념과 밀접한 관련이 있는 개념이 많고, 복잡한 알고리즘이 있으며, 테스트하기 쉽고, 큰 질문을 하기 쉽다는 것입니다. 특히 명문학교에서는 대학원 입시과정으로서 나무와 그림 두 장의 지식을 검토하지 않고서는 거의 상상할 수 없는 일이다.

이번 그래프 장의 주요 테스트 포인트와 이러한 테스트 포인트에 대한 테스트 방법을 살펴보겠습니다.

1. 그래프에 대한 기본 개념 질문을 테스트합니다.

이러한 개념은 그래프 장을 연구하기 위한 기초입니다. 이 장의 개념에는 그래프의 정의 및 특성, 무방향 그래프, 방향 그래프, 내차, 외차, 완전 그래프, 생성된 하위 그래프, 경로 길이가 포함됩니다. , 루프, (강하게) 연결된 그래프, (강하게) 연결된 구성 요소 및 기타 개념입니다. 이러한 개념과 관련된 계산 문제도 마스터해야 합니다.

2. 그래프의 여러 저장 형식을 살펴보세요.

그래프의 저장 형식에는 인접 행렬, (역) 인접 목록, 교차 연결 목록 및 인접 다중 목록이 포함됩니다. 시험 중에 일부 학교에서는 저장 형식을 제공하고 응시자에게 알고리즘을 사용하거나 주어진 구조에 해당하는 그래프의 다른 저장 형식을 직접 작성하도록 요구합니다.

3. 그래프에 대한 두 가지 순회 알고리즘 검토: 깊이 순회 및 너비 순회

깊이 순회와 너비 순회는 그래프에 대한 두 가지 기본 순회 알고리즘입니다. 한 장의 중요성은 이진 트리에 대한 장의 "선순서, 중순 및 후순 순회"의 중요성과 동일합니다. 검토 중에 그림 1의 알고리즘 설계 질문은 "가장 긴 최단 경로 문제 찾기" 및 "두 꼭지점 사이에 길이 K의 단순 경로가 있는지 확인"과 같은 두 가지 기본 순회 알고리즘을 기반으로 설계되는 경우가 많습니다. 문제"에서는 너비 탐색 알고리즘과 깊이 탐색 알고리즘이 각각 사용됩니다.

4. 스패닝 트리, 최소 스패닝 트리의 개념과 최소 스패닝 트리의 구성: PRIM 알고리즘과 KRUSKAL 알고리즘.

심사 과정에서는 일반적으로 알고리즘의 소스 코드를 작성할 필요가 없으며, 대신 이러한 알고리즘 아이디어를 기반으로 구축 과정과 최종 생성된 최소 스패닝 트리를 작성하는 것이 필요합니다. 두 개의 최소 스패닝 트리.

5. 위상 정렬 문제:

위상 정렬에는 두 가지 방법이 있습니다. 하나는 선행자가 없는 정점 우선 알고리즘이고 다른 하나는 후행자가 없는 정점 우선 알고리즘입니다. 즉, 하나는 "앞에서 뒤로" 정렬이고, 다른 하나는 "뒤에서 앞으로" 정렬입니다. 물론 후자 정렬의 결과는 "역위상 순서화"입니다.

6. 임계 경로 문제:

이 문제는 그림 1의 어려운 문제입니다. 주경로를 이해하는 데에는 세 가지 열쇠가 있습니다. 첫째, 주경로가 무엇인지, 둘째, 가장 이른 시간이 무엇을 의미하고 어떻게 찾는지, 셋째, 가장 늦은 시간이 무엇을 의미하고 어떻게 찾는가입니다. 간단히 말해서 "앞에서 뒤로" 방식으로 가장 빠른 시간을 구하고, "뒤에서 앞으로" 방식으로 가장 늦은 시간을 구하며, 가장 늦은 시간을 찾으려면 의 가장 빠른 시간이어야 합니다. 모두 모든 것이 요청된 후에만 수행될 수 있습니다.

이 질문은 알고리즘 소스 코드를 직접 테스트하는 데 거의 사용되지 않습니다. 일반적으로 책의 알고리즘에 따라 해결 과정과 단계를 설명하는 데 필요합니다.

실제로 임계 경로 알고리즘을 설계할 때 다음 사항에도 주의해야 합니다. 인접 목록의 저장 구조를 사용하면 가장 빠른 시간과 가장 늦은 시간을 찾기 위해 다양한 처리 방법을 사용해야 하며, 즉, 알고리즘 시작 시 먼저 모든 정점의 가장 빠른 시간을 0으로 설정해야 합니다. 주경로 문제는 프로젝트 진행 관리를 위한 중요한 방법이며 실용성이 뛰어납니다.

7. 최단 경로 문제:

그림 1에서는 임계 경로 문제와 함께 두 가지 걸림돌이라고 합니다. 개념적 이해는 상대적으로 쉬우며, 핵심은 알고리즘에 대한 이해입니다. 최단 경로 문제에는 두 가지 유형이 있습니다. 하나는 특정 지점에서 다른 지점까지의 최단 경로를 찾는 것이고, 다른 하나는 그래프의 각 정점 쌍 사이의 최단 경로를 찾는 것입니다. 이 문제 역시 매우 실용적인 배경적 특징을 갖고 있다. 대표적인 예가 관광지와 여행경로의 선택이다. 첫 번째 문제를 해결하기 위해 DIJSKTRA 알고리즘을 사용하고, 두 번째 문제를 해결하기 위해 FLOYD 알고리즘을 사용합니다. 구별에 주의하세요.

7장 검색

많은 자료 구조 교과서에서는 검색과 정렬이 고급 자료 구조에 담겨 있습니다. 검색과 정렬의 두 장은 우리가 이전에 배운 지식을 포괄적으로 적용한 것이라고 해야 합니다. 트리, 연결 목록 및 기타 지식이 사용됩니다. 이러한 데이터 구조의 특정 측면을 적용하면 검색과 정렬이 구성됩니다.

실생활에서 검색은 거의 모든 곳에서 이루어지며, 특히 현재 인터넷 시대에는 문서의 텍스트 검색부터 인터넷상의 대규모 검색까지 모든 것이 검색과 분리될 수 없습니다. 시간의.

이 장의 지식을 검토할 때 먼저 다음 개념을 명확히 해야 합니다.

키워드, 기본 키워드, 보조 키워드의 의미 정적 검색 및 동적 검색의 의미 검색의 차이점, 평균 검색 길이 ASL의 개념과 다양한 검색 알고리즘의 계산 방법 및 계산 결과, 특히 일부 일반적인 구조의 ASL 값을 기억해야 합니다.

DS 교과서에서 검색은 일반적으로 세 가지 범주로 나뉩니다. 첫 번째는 시퀀스 테이블에서 검색하고, 두 번째는 트리 테이블에서 검색하고, 세 번째는 해시 테이블에서 검색합니다. 다음은 테스트 지식 포인트와 테스트 방법에 대한 자세한 소개입니다.

1. 선형 테이블 검색:

주로 세 가지 선형 구조로 나뉩니다: 시퀀스 테이블, 순서가 지정된 시퀀스 테이블, 인덱스 시퀀스 테이블. 첫 번째로는 전통적인 검색 방법을 사용하여 하나씩 비교합니다. 순서가 있는 목록의 경우 이진 검색 방법을 사용합니다. 세 번째 인덱스 구조에는 인덱스 검색 알고리즘을 사용합니다. 응시자는 이 세 가지 테이블의 ASL 값과 세 가지 알고리즘의 구현에 주의를 기울여야 합니다. 그 중 이진 검색은 적용 조건과 재귀적 구현 방법에 특별한 주의가 필요합니다.

2. 트리 테이블에서 검색:

이것이 이 장의 초점이자 난이도입니다. 본 절에서 소개하는 내용은 트리 테이블을 이용한 조회이므로 트리 테이블의 일부 개념과 혼동되기 쉽습니다. 이 절의 내용은 나무 장의 내용과 관련이 있지만 차이점도 많이 있으므로 주의해야 합니다. 트리 테이블은 주로 이진 정렬 트리, 균형 이진 트리, B-트리, 키 트리 등의 유형으로 구분됩니다. 그중 처음 두 구조가 특히 중요하며 일부 명문 학교에서는 B-tree 시험을 선호합니다. 이진 정렬 트리와 균형 이진 트리는 특별한 이진 트리이므로 이진 트리와 더 밀접하게 관련되어 있습니다. 첫 번째 장에서 이진 트리에 대해 배웠다면 여기서는 어렵지 않을 것입니다.

간단히 말하면 이진 정렬 트리는 "왼쪽이 작고 오른쪽이 큽니다"이며 순회 결과는 증가하는 순서입니다. 균형 이진 트리는 이진 정렬 트리를 최적화한 것이며 그 본질도 이진 정렬 트리입니다. 그러나 균형 이진 트리는 왼쪽 및 오른쪽 하위 트리의 깊이에 제한이 있습니다. 즉, 깊이 차이의 절대값이 있어야 합니다. 1보다 클 수 없습니다. 이진 정렬 트리의 경우 "이진 트리가 이진 정렬 트리인지 결정"하는 알고리즘이 재귀적이거나 비재귀적일 수 있는 경우가 많습니다. 균형 이진 트리의 확립도 일반적인 테스트 포인트이지만 이 지식 포인트는 궁극적으로 균형 이진 트리의 네 가지 조정 알고리즘에 중점을 두므로 균형 이진 트리의 네 가지 조정 알고리즘을 숙지해야 합니다. - 조정 전과 조정 후의 순서 순회 결과는 동일합니다.

B-트리는 이진 정렬 트리를 더욱 개선한 것입니다. B-트리는 3포크, 4포크... 정렬 트리로도 이해할 수 있습니다. B-트리 검색 알고리즘 외에도 B-트리 삽입 및 삭제 알고리즘에 특별한 주의를 기울여야 합니다. 이 두 알고리즘은 B-트리 노드의 분할과 병합을 포함하기 때문에 어려운 점이 있습니다. B-트리는 명문고에 지원하는 학생들이 주목해야 할 부분 중 하나이다.

키 트리는 문자 트리라고도 하는데, 특히 영어 단어 검색에 적합합니다. 일반적으로 알고리즘 소스 코드를 완전히 설명할 필요는 없지만 대부분 알고리즘 아이디어를 기반으로 키 트리를 설정하고 대략적인 검색 프로세스를 설명합니다.

3. 기본 해시 테이블 검색 알고리즘:

해시라는 단어는 "해시"라는 단어에서 번역된 외국어입니다. 이는 해시 또는 해시를 의미합니다. 해시 테이블 검색의 기본 아이디어는 검색하려는 현재 데이터의 특성에 따라 기록된 키워드를 독립 변수로 사용하여 함수가 키워드를 변환한 후 해석 결과가 되는 주소입니다. 검색했습니다. 해시 테이블을 기반으로 한 검토 사항에는 해시 함수 설계, 충돌 해결 방법 선택, 충돌 처리 프로세스 설명 등이 포함됩니다.

8장 내부 정렬

내부 정렬은 DS 과정의 마지막 중요한 장입니다. 이 장을 기반으로 하는 시험 문제는 빈칸 채우기, 선택, 선택 등 다양한 유형이 있을 수 있습니다. 판단 큰 알고리즘 문제라도. 그러나 이는 다양한 정렬 알고리즘과 책에 나오는 아이디어, 장점과 단점, 성능 지표(시간 복잡도)를 철저히 이해하고 있는지 테스트하는 한 가지 지점으로 귀결됩니다.

이번 장에서는 이전 장들과 초점이 ​​다릅니다. 정렬 장의 전체 구조와 다양한 알고리즘을 보다 포괄적으로 이해하기 위해 다음 측면에서 정렬 장을 다르게 배열할 것입니다.

이 장에서는 정렬 알고리즘 유형의 관점에서 주로 삽입, 선택, 교환, 병합, 계산의 5가지 정렬 방법을 설명합니다.

그 중 삽입 정렬은 직접 삽입, 절반 삽입, 양방향 삽입, 힐 정렬로 나눌 수 있습니다. 이러한 삽입 정렬 알고리즘 간의 가장 근본적인 차이점은 최종 분석에서 새 요소의 삽입 지점을 찾는 데 사용되는 규칙입니다. 직접 삽입은 순서대로 검색하는 것을 의미하고, 반 삽입은 반으로 검색하는 것을 의미합니다. 힐 정렬은 매번 "작은 것부터 큰 것까지" 정렬에 참여하는 숫자의 전체 범위의 증가를 제어하여 정렬 효율성을 향상시키는 목적을 달성하는 것입니다.

버블 정렬이라고도 하는 교환 정렬은 교환 정렬을 기반으로 개선되어 빠른 정렬을 얻을 수 있습니다. 퀵 정렬의 개념은 한 문장으로 요약할 수 있습니다. 가운데 숫자를 사용하여 정렬할 데이터 그룹을 두 개로 나누는 것입니다. 퀵 정렬은 처리해야 할 "문제 규모"라는 개념에서 Hill과 다소 반대입니다. 퀵 정렬은 먼저 더 큰 규모를 처리한 다음 점차적으로 처리 규모를 줄여 최종적으로 정렬의 목적을 달성합니다.

선택 정렬은 이전 정렬 알고리즘보다 더 어렵습니다. 구체적으로는 단순선택, 트리선택, 스택배열로 나눌 수 있다. 이 세 가지 방법의 차이점은 가장 작은 숫자를 선택하는 규칙입니다. 단순 선택은 간단한 배열 순회 방식을 통해 최소 수를 결정하는 것입니다. 트리 선택은 "토너먼트"와 유사한 아이디어를 사용하여 두 숫자를 비교하고 계속해서 더 큰(더 작은) 숫자를 제거하고 마지막으로 가장 작은(더 큰) 숫자를 선택하는 것입니다. 정렬은 힙의 데이터 구조의 특성을 이용하여 힙 요소의 삭제, 조정 등 일련의 작업을 통해 가장 작은 숫자를 선택하고 이를 힙의 맨 위에 배치하는 것입니다. 힙 정렬 시 힙 설정 및 힙 조정은 중요한 테스트 포인트입니다. 트리 선택 정렬은 일부 학교의 대형 알고리즘 문제에도 등장했습니다.

병합 정렬은 이름에서 알 수 있듯이 "병합" 작업을 통해 정렬하는 목적이므로 병합을 위해서는 두 개 이상의 데이터 세트가 있어야 합니다. 따라서 병합 정렬에서 가장 우려되는 것은 2-way 병합이다. 알고리즘 아이디어는 비교적 간단하지만 명심해야 할 한 가지가 있습니다. 병합 정렬은 안정적인 정렬입니다.

기수 정렬은 매우 특별한 정렬 방법입니다. 바로 그 특별함 때문에 기수 정렬은 포커 카드 정렬 문제와 같은 특별한 경우에 더 적합합니다. 기수 정렬은 다중 키워드 정렬(카드 정렬)과 체인 정렬(정수 정렬)의 두 가지 유형으로 나뉩니다.

기수 정렬의 핵심 아이디어는 "기수 공간" 개념을 사용하여 문제의 크기를 표준화하고 줄이는 것입니다. 또한 정렬 과정에서 기수 정렬 아이디어를 따르는 한, 이렇게 해서 얻은 최종 시퀀스는 키워드를 비교할 필요가 없습니다.

이 장의 다양한 정렬 알고리즘에 대한 아이디어와 의사 코드 구현은 물론 시간 복잡성도 숙지해야 합니다. 학습할 때는 포함, 요약 및 비교에 더 많은 주의를 기울여야 합니다. 또한 교과서의 10.7절은 암기하고 이해를 바탕으로 암기해야 하는 부분인데, 이 부분은 매년 많은 학교에서 거의 필수 시험 과목이 되었습니다.

이 시점에서 우리는 데이터 구조의 모든 장에 핵심 문제를 포함시켰습니다. Tsinghua Yan edition 교과서를 사용하는 학생들은 복습하면서 이 게시물에 제시된 핵심 사항을 참고할 수 있습니다. 하지만 작성자의 수준 제한으로 인해 포함되지 않은 테스트 포인트가 많을 수도 있고, 일부 테스트 포인트가 잘못 포함되었을 수도 있습니다. 여기서는 모든 친구들이 직접 고민을 제기해 주시길 진심으로 바라며, 계속 진행하겠습니다. 새로운 데이터 구조 검토를 개선하고 게시합니다. 요약 및 메모

데이터 구조에 초점을 맞춘 Yan Weimin의 메모 2

2장: 선형 표(연습, 답변 및 핵심 사항 포함)

--- ----------------------------- -------- -------------

이 장의 초점은 다양한 기술을 익히는 것입니다. 시퀀스 목록 및 단일 연결 목록에 대한 기본 구현 알고리즘 및 관련 시간 성능 분석에서는 이 장에서 배운 기본 지식을 사용하여 선형 테이블과 관련된 응용 프로그램 문제를 해결하는 효과적인 알고리즘을 설계하는 것이 어렵습니다.

레벨 내용에는 lt; 암기 요구 사항을 충족해야 하며 선형 테이블에 정의된 기본 작업의 논리적 구조 특성, 더 복잡한 작업.

간단한 응용 문제를 해결하려면 시퀀스 테이블의 의미와 특성, 시퀀스 테이블에 대한 삽입 및 삭제 작업 및 평균 시간 성능 분석 등 포괄적인 응용 수준의 콘텐츠를 달성해야 합니다.

연결 목록이 선형 목록의 요소 간의 논리적 관계를 나타내는 방법, 단일 연결 목록, 이중 연결 목록 및 테이블 생성, 검색, 삽입과 같은 기본 알고리즘의 연결 방법 차이. , 단일 연결 목록에서 구현된 삭제 및 시간 복잡도. 헤드 포인터 대신 원형 연결 목록에서 꼬리 포인터의 역할과 단일 순환 연결 목록의 알고리즘과 단일 연결 목록의 해당 알고리즘 간의 유사점과 차이점. 이중 연결 목록 및 관련 알고리즘의 정의. 연결된 목록 디자인 알고리즘을 사용하여 간단한 응용 프로그램 문제를 해결합니다.

레벨의 내용은 시퀀스 목록과 연결 목록을 비교하고 더 나은 시공간 성능을 달성하기 위해 저장 구조로 선택하는 방법을 이해하는 데 필요합니다.

------------------------------- -- ------------------------

논리적 구조적 특징 선형 테이블 이름에서 알 수 있듯이 논리적 구조는 매듭이 있는 선과 같습니다. 이 선에 매듭이 있으면 비어 있지 않은 테이블만 가능합니다. 시작 노드에는 하나의 터미널 노드만 있고 다른 노드는 하나의 노드(직접 선행 노드 및 직접 후속 노드)에만 인접할 수 있습니다.

선형 테이블에 정의된 기본 작업에는 주로 빈 테이블 구성, 테이블 길이 찾기, 노드 가져오기, 검색, 삽입, 삭제 등이 포함됩니다.

------------------------------- -- ------------------------

논리적 구조와 선형 테이블의 합 스토리지 구조 간의 관계입니다. 컴퓨터에서 선형 테이블의 노드를 저장 장치에 저장하는 방법에는 여러 가지가 있습니다. 가장 간단한 방법은 순서대로 저장하는 것입니다. 즉, 선형 테이블의 논리적 구조에 따라 연속된 주소를 갖는 저장 단위 그룹에 저장된다. 저장 장치에 있는 각 요소의 물리적 위치와 논리적 구조에 있는 각 노드의 인접 관계는 일관됩니다.

시퀀스 테이블에 구현된 기본 연산은 삽입과 삭제라는 두 가지 연산을 주로 다룬다. 연습을 통해 관련 알고리즘을 마스터합니다. 시퀀스 테이블의 삽입 및 삭제 작업의 경우 평균 시간 복잡도는 O(n)입니다.

------------------------------- -- ------------------------

선형의 연계 저장소 테이블 구조. 이는 순차 목록과 다릅니다. 연결 목록은 임의의 저장 단위 집합을 사용하여 선형 목록의 노드를 저장합니다. 이 저장 단위 집합은 메모리의 모든 위치에 배포될 수 있습니다. 따라서 연결리스트의 노드들의 논리적 순서와 물리적 순서가 반드시 동일하지는 않습니다. 따라서 노드 간의 논리적 관계를 정확하게 표현하기 위해 각 노드의 값을 저장하는 동시에 후속 노드의 주소 정보도 저장합니다(예: