로그인
로그인

마인드 맵 갤러리 데이터 구조

데이터 구조

이것은 선형 테이블, 스택 및 큐, 문자열, 트리 및 이진 트리, 검색, 정렬 등을 포함한 데이터 구조에 대한 마인드 맵입니다. 매우 실용적이며 수집할 가치가 있습니다.

2021-09-25 14:52:15에 편집됨

슈퍼직장인

최근 작업 더 많은 작업 보기>>

(III) 저산소 유도 인자 프롤릴 하이드 록 실라 제 억제제
이것은 (III) 저산소증-유도 인자 프롤릴 하이드 록 실라 제 억제제에 대한 마인드 맵이며, 주요 함량은 다음을 포함한다 : 저산소증-유도 인자 프롤릴 하이드 록 실라 제 억제제 (HIF-PHI)는 신장 빈혈의 치료를위한 새로운 소형 분자 경구 약물이다. 1. HIF-PHI 복용량 선택 및 조정. Rosalasstat의 초기 용량, 2. HIF-PHI 사용 중 모니터링, 3. 부작용 및 예방 조치.
Kuka 산업용 로봇의 개발 및 Kuka 산업 로봇의 모션 제어 명령
이것은 Kuka Industrial Robots의 개발 및 Kuka Industrial Robot의 모션 제어 지침에 대한 마인드 맵입니다. 주요 내용에는 쿠카 산업 로봇의 역사, 쿠카 산업 로봇의 특성, 쿠카 산업 로봇의 응용 분야, 2. 포장 프로세스에서 쿠카 로봇은 빠르고 일관된 포장 작업을 달성하고 포장 효율성을 높이며 인건비를 줄입니다. 2. 인건비 감소 : 자동화는 운영자에 대한 의존성을 줄입니다. 3. 조립 품질 향상 : 정확한 제어는 인간 오류를 줄입니다.
1.1 컴퓨터 네트워크 요약
408 컴퓨터 네트워크가 너무 어렵습니까? 두려워하지 마세요! 나는 피를 구토하고 지식 맥락을 명확히하는 데 도움이되는 매우 실용적인 마인드 맵을 분류했습니다. 컨텐츠는 매우 완전합니다. 네트워크 아키텍처에서 응용 프로그램 계층, TCP/IP 프로토콜, 서브넷 디비전 및 기타 핵심 포인트에 이르기까지 원칙을 철저히 이해하는 데 도움이 될 수 있습니다. 📈 명확한 논리 : Mindmas 보물, 당신은 드문 기회가 있습니다. 서둘러! 이 마인드 맵을 사용하여 408 컴퓨터 네트워크의 학습 경로에서 바람과 파도를 타고 성공적으로 해변을 얻으십시오! 도움이 필요한 친구들과 공유해야합니다!

데이터 구조

슈퍼직장인

최근 작업 더 많은 작업 보기>>

추천 사항
개요

데이터 구조
- 11
슈퍼직장인
데이터 구조 - 선형 테이블
- 4
슈퍼직장인
데이터 구조 마인드 맵
- 23
슈퍼직장인
데이터 구조 선형 테이블 스택 큐 지식 포인트 노트
- 7
슈퍼직장인
데이터 구조 2장 - 선형 테이블
- 6
슈퍼직장인
데이터 구조 및 알고리즘의 기본 개념
- 4
슈퍼직장인
데이터 구조 선형 테이블
- 6
슈퍼직장인
데이터 구조
- 9
슈퍼직장인
데이터 구조 코스 프레임워크
- 6
슈퍼직장인
데이터 구조
- 8
슈퍼직장인

데이터 구조 8.26

1. 소개

1.1 데이터 구조의 기본 개념

1.1.1기본 개념 및 용어

1.데이터

이는 컴퓨터에 입력되어 컴퓨터 프로그램에 의해 인식되고 처리될 수 있는 기호 모음인 정보 전달자입니다.

2. 데이터 요소

데이터의 기본 단위로, 데이터 요소는 여러 데이터 항목으로 구성될 수 있습니다.

데이터 항목: 데이터 요소를 구성하는 분할할 수 없는 가장 작은 단위

3. 데이터 객체

동일한 성격을 지닌 데이터 요소들의 집합으로서 데이터의 하위 집합(예: 학생 정보 객체는 전체 학생 정보 및 교과목 정보의 하위 집합)

4.데이터 유형

값 집합과 이 집합에 정의된 연산 집합의 총칭입니다(예: int 유형 변수, 해당 값 집합은 특정 간격에서 정수입니다(간격의 크기는 기계에 따라 다릅니다). ), 이에 대한 연산은 덧셈, 뺄셈, 곱셈, 나눗셈, 모듈로 및 기타 연산으로 정의됩니다)

1.원자형

값을 세분화할 수 없는 데이터 유형

2. 구조 유형

값이 여러(구성요소)로 나누어질 수 있는 데이터 유형

3. 추상 데이터 구조 ADT

수학적 모델과 모델에 정의된 일련의 연산을 의미합니다(논리적 특성만 강조됨).

그림 1-4

1.1.2 데이터 구조와 세 가지 요소

데이터 구조

서로 특정한 관계를 갖고 있는 데이터 요소의 집합입니다.

세 가지 요소

1. 데이터의 논리적 구조

선형 구조

일반 선형 테이블

제한된 선형 테이블

스택, 큐

끈

선형 테이블 승격

정렬

비선형 구조

모으다

트리 구조

그래프 구조

2. 데이터 저장 구조(이미지, 물리적 구조)

순차 저장

장점: 1. 무작위 액세스가 가능합니다. 2. 각 요소가 최소한의 저장 공간을 차지합니다. 단점: 1. 인접한 저장 장치 블록 전체만 사용할 수 있으므로 더 많은 외부 조각을 생성하기 쉽습니다.

체인 스토리지

장점: 1. 논리적으로 인접한 요소가 물리적으로 인접할 필요가 없으므로 조각화가 발생하지 않습니다. 단점: 1. 포인터는 추가 공간을 소비합니다. 2. 무작위 액세스는 달성할 수 없으며 순차 액세스만 가능합니다.

인덱스 저장

요소 정보를 저장하는 동안 추가 인덱스 테이블이 생성되며 인덱스 테이블의 각 항목을 인덱스 항목(키, 주소)이라고 합니다. 장점: 1. 빠른 검색: 1. 추가 인덱스 테이블은 추가 저장 공간을 차지합니다. 2. 데이터를 추가하거나 삭제할 때 인덱스 테이블을 수정해야 하는데 시간이 많이 걸립니다.

해시 저장

요소 키워드를 기반으로 요소의 저장 주소(해시 저장)를 직접 계산합니다. 장점: 1. 노드 추가, 삭제 및 확인 작업이 매우 빠릅니다. 단점: 1. 해시 함수가 좋지 않으면 충돌이 발생합니다. 요소 저장 단위가 발생하고 충돌을 해결하면 시간과 공간 오버헤드가 증가합니다.

3. 데이터 작업

운영의 정의

논리적 구조를 고려하여 연산 기능을 지적하시오.

운영 구현

저장 구조에 대한 구체적인 작업 단계를 지적하십시오.

1.2 알고리즘과 알고리즘 평가

이는 특정 문제를 해결하는 방법에 대한 설명이며 유한한 지침 순서입니다.

시간 복잡도

문제 크기가 n인 경우 실행 시간은 O(1<log2n<n<nlog2n<n^2<n3<2^n<n!<n^n)에 비례합니다.

공간 복잡도

문제 크기는 n이고, 입력과 프로그램 이외의 추가 공간은 알고리즘이 제자리에서 작동합니다. 알고리즘에 필요한 보조 공간은 일정합니다. 즉, O(1)입니다.

2선형 테이블

2.1 선형 테이블의 정의

동일한 데이터 유형을 갖는 n개의 데이터 요소로 구성된 유한 시퀀스

2.2 선형 테이블의 순차적 표현

시퀀스 테이블

끼워 넣다

Bool ListInsert(SqList &L,int i,ElemType e){ If(i < 1 || i > L.length 1) false를 반환합니다. If(L.length >= MaxSize)는 false를 반환합니다. For(int j = L.length;j>=i;j- -) //L.length는 배열 첨자의 마지막 요소 다음 위치입니다. L.data[j] = L.data[j-1]; L.data[i-1] = e; L. 길이; 사실을 반환; }

시간 복잡도 최고 최저 평균 O(1) O(n) O(n)

삭제

Bool ListDelete(SqList &L,int i,ElemType &e){ If( i<1 || i>L.length) return false; e = L.data[i-1]; For(int j = i;j<L.길이;j) L.데이터[j-1] = L.데이터[j]; L. 길이 - -; 참을 반환합니다. }

O(1) O(n) O(n)

값으로 검색(순차적으로 검색)

Int LocateElem(SqList L,ElemType e){ For(int i=0;i<L.길이;i) If(L.data[i] == e) return i 1; 0을 반환합니다. }

O(1) O(n) O(n)

2.3 선형 테이블의 연결 표현

단일 목록 typedef 구조체 LNode{ ElemType 데이터; 구조체 LNode *next; }LNode,*LinkList;

단일 연결 리스트 생성

헤드 삽입 방법

LinkLIst List_HeadInsert(링크리스트 &L){ L노드 *s;int x; L = (LNode*)malloc(sizeof(LNode)); L->다음 = NULL; scanf("%d",&x); 동안(x != 9999){ s = (LNode*)malloc(sizeof(LNode)); s->데이터 = x;s->다음 = L->다음; L->다음 = s; s->데이터 = x; scanf("%d",&x); } L을 반환;}

꼬리 삽입 방법

LinkList List_TailInsert(링크리스트 &L){ 정수 x; L = (LNode*)malloc(sizeof(LNode)); L노드 *s,*r = L; scanf("%d",&x); 동안(x != 9999){ s = (LNode*)malloc(sizeof(LNode)); s->데이터 = x; r->다음 = s; s = r; scanf("%d",&x); } r-다음 = NULL; L 반환: }

일련번호로 노드 찾기

LNode *GetElem(LinkList L,int i){ int j = 1; LNode *p = L->다음; if(i == 0) return L; if(i < 1) NULL을 반환합니다. 동안(p && j<i){ p = p ->다음; 제이; } p를 반환; }

값으로 노드 테이블 노드 찾기

LNode *LocateElem(LinkList L,ElemType e){ LNode *p = L->다음; while(p != NULL && p->data != e) p = p->next; p를 반환; }

노드 삽입

p = GetElem(L,i-1); s->다음 = p->다음; p->다음 = s; (i-1은 p이고, p 뒤에 삽입됨)

시간 O(n)

s->다음 = p->다음; p->다음 = s; 온도 = p->데이터; p->데이터 = s->데이터; s->데이터 = 임시; (i는 p이고, p 뒤에 데이터를 삽입하고 교환하며, p 정방향 삽입을 구현합니다)

시간 O(1)

노드 삭제

p = GetElem(L,i-1); q = p->다음; p->다음 = p->다음->다음; 무료(q);

시간 O(n)

q = p->다음; p->데이터 = q->데이터; p->다음 = p->다음->다음; 무료(q);

시간 O(1)

테이블 길이 문의

테이블 길이에는 헤드 노드가 포함되지 않습니다.

에)

이중 연결 리스트 typedef 구조체 Dnode{ ElemType 데이터; struct DNode *prior,*next; }Dnode,*DLinkList;

노드 삽입

s->다음 = p->다음; s->다음->이전 = s; s->이전 = p; p->다음 = s;

오(1)

노드 삭제

p->이전->다음 = p->다음; p->다음->이전 = p->이전; 무료(p);

오(1)

순환 연결 리스트 명백한 특징: 마지막 노드 포인터는 NULL이 아닙니다. null 조건은 헤드 노드가 헤드 포인터와 같은지 여부이며, NULL이 아닙니다. 즉, (L->next == L)입니다.

순환형 단일 연결 리스트

순환 이중 연결 리스트

정적 연결리스트 배열을 사용하여 선형 목록의 연결된 저장 구조를 설명합니다. 특징: 포인터는 커서라고도 알려진 노드(배열 아래 첨자)의 상대 주소입니다. 시퀀스 목록과 마찬가지로 정적 연결 목록도 연속 메모리 공간을 미리 할당해야 합니다. #define 최대 크기 50 형식 정의 구조체{ ElemType 데이터; int 다음; }SLinkList[최대 크기];

3개의 스택과 큐

스택 카텔란수: 1/n 1(Ｃ2n n)

스택의 순차적 저장(순차적 스택) #define 최대 크기 50 형식 정의 구조체{ ElemType 데이터[MaxSize]; int top; //스택 상단 포인터 }SqStack;

초기화 무효 InitStack(SqStack &S){ 상단 = -1; }

스택이 비어 있습니다. bool StackEmpty(SqStack S){ if(S.top == -1) true를 반환합니다. 그렇지 않으면 false를 반환합니다. }

스택에 밀어넣기 bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) return false; S.data[ S.top] = x; //top은 -1로 초기화됩니다. 사실을 반환; }

팝 bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) false를 반환합니다. x = S.data[S.top- -]; 사실을 반환; }

스택의 최상위 요소 읽기 bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) false를 반환합니다. x = S.data[S.top]; 사실을 반환; }

공유 스택(Shared stack): 상대적으로 변하지 않는 스택 하단 위치의 이점을 활용하여 두 개의 순차 스택이 1차원 배열 공간을 공유하도록 합니다. 두 스택의 하단은 공유 공간의 양쪽 끝에 설정되며, 두 개의 스택이 공유 공간의 중앙으로 확장됩니다. 공유 스택은 저장 공간을 보다 효율적으로 사용할 수 있으며, 두 스택 공간은 서로 조정되며 전체 저장 공간이 가득 찬 경우에만 오버플로가 발생합니다.

초기: top0 = -1 top1 = MaxSize 스택 가득 참: 두 스택 포인터가 인접한 경우에만 top1 - top0 = 1

체인 스택 typedef 구조체 링크노드{ ElemType 데이터; 구조체 링크노드 *next; }*링크스택;

대기줄

대기열 주문 저장 #define 최대 크기 50 형식 정의 구조체{ ElemType 데이터[MaxSize]; 전면, 후면; }SqQueue;

순차 대기열

대기열 비어 있음 조건: Q.front == Q.rear ==0; Q.rear == MaxSize는 팀이 가득 찼음을 판단하는 조건으로 사용할 수 없으며 false이거나 오버플로될 수 있습니다.

순환 대기열 순환 대기열의 대기열 제거, 조인 및 전체 작업에는 %가 있어야 합니다. 빈 조건은 Q.rear == Q.front입니다.

초기화 무효 InitQueue(SqQueue &Q){ Q.rear = Q.front = 0; }

팀이 비어 있습니다 bool isEmpty(SqQueue Q){ if(Q.rear == Q.front) return true; 그렇지 않으면 false를 반환합니다. }

팀에 합류하세요 bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear 1)%MaxSize == Q.front) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear 1)%MaxSize; 사실을 반환; }

대기열에서 빼기 bool DeQueue(SqQueue &Q,ElemType &x){ if(Q.rear == Q.front) return false; x = Q.data[Q.front]; Q.front = (Q.front 1)%MaxSize; 사실을 반환; }

대기열의 체인 저장(체인 큐) typedef 구조체 LNode{ ElemType 데이터; 구조체 LNode* 다음; }L노드; 형식 정의 구조체{ L노드 *전면,*후면; }링크큐; 체인 큐는 데이터 요소가 상대적으로 크게 변경되는 상황에 적합하며 큐가 가득 차서 오버플로가 발생하는 상황이 없습니다.

초기화 무효 InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkQueue))) //헤드 노드 생성 Q.프론트 ->다음 = NULL; }

팀이 비어 있습니다 bool IsEmpty(LinkQueue&Q){ if(Q.front == Q.rear) return true;//헤드 노드 포함 그렇지 않으면 false를 반환합니다. }

팀에 합류하세요 void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL;//새 노드를 생성하고 체인 끝에 삽입합니다. Q.뒤->다음 = s; Q.뒤 = s; }

대기열에서 빼기 bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.rear == Q.front) return false; LinkNode *p = Q.front->next; x = p->데이터; Q.앞->다음 = p->다음; if(Q.rear == p) Q.rear = Q.front;//원래 큐에는 노드가 하나만 있습니다. 무료(p); 사실을 반환; }

양면 큐: 양쪽 끝이 큐에 넣기와 빼기 작업을 수행할 수 있도록 하는 큐의 요소 논리 구조는 여전히 선형 구조입니다. 큐의 두 끝을 각각 프런트 엔드와 백 엔드라고 합니다.

입력 제한 데크

한쪽 끝에서는 삽입과 삭제가 허용되지만 반대쪽 끝에서는 삭제만 허용됩니다.

출력 제한 deque

한쪽 끝에서는 삽입 및 삭제가 허용되지만 다른 쪽 끝에서는 삽입만 허용됩니다.

스택과 큐의 응용

브래킷 매칭에 스택 적용

[]()([][]())는 올바른 형식입니다. (] [)는 잘못된 형식입니다.

빈 스택을 설정하고 괄호를 순서대로 읽습니다. 오른쪽 괄호이면 검사를 위해 스택의 맨 위 요소를 팝하고, 그렇지 않으면 오류가 보고됩니다. 왼쪽 괄호는 스택에 푸시하고, 스택이 비어 있는지 확인하여 비어 있지 않으면 대괄호 시퀀스가 일치하지 않습니다.

표현식 평가에 스택 적용

중위 표현식: 연산자 우선순위에 따라 다르지만 괄호도 처리합니다. 후위 표현식: 연산자 우선 순위가 이미 고려되었으며 괄호가 없습니다(표현 트리의 후위 순회). 중위 표현식을 후위 표현식으로 변환

후위 표현식 처리: 표현식의 각 항목을 순차적으로 스캔하고, 피연산자인 경우 스택에 푸시하고, 스택에서 두 피연산자 Y와 X를 계속해서 종료하여 X<OP>Y를 형성합니다. put 계산 결과가 스택에 다시 푸시됩니다.

재귀에서 스택 적용

계층적 순회에서 큐 적용

루트 노드가 큐에 들어갑니다. 큐가 비어 있으면(모든 노드가 처리됨) 순회가 종료됩니다. 그렇지 않으면 큐의 첫 번째 루트 노드가 큐에서 제거되고 액세스됩니다. 왼쪽 자식이 팀에 합류합니다. 오른쪽 자식이 있으면 오른쪽 자식을 팀에 추가하고 이전 단계로 돌아갑니다.

컴퓨터 시스템의 큐 적용

1. 호스트와 외부 장치 간의 속도 불일치 문제를 해결합니다. 2. 다수의 사용자로 인한 자원 경쟁 문제 해결

1. 호스트 및 프린터: 인쇄 데이터 버퍼를 설정합니다. 버퍼가 가득 차면 호스트는 출력을 일시 중지합니다. 프린터는 차례로 fcfs를 대기열에서 꺼낸 다음 인쇄 후 호스트에 요청을 보냅니다.

2.CPU 리소스 할당: FCFS

특수 매트릭스의 압축 저장 문제 해결: 이제 해당 조건에 따라 스케치를 그리고 추론을 해보세요. 공식을 암기하기보다는 저장 논리를 이해하는 것이 중요합니다.

정렬 동일한 유형의 n개 데이터 요소의 유한 시퀀스 차원 경계: 아래 첨자의 값 범위 배열은 선형 테이블을 일반화한 것입니다. 1비트 배열은 선형 테이블로 볼 수 있고, 2차원 배열은 요소가 고정 길이 선형 테이블인 선형 테이블로 볼 수 있습니다. 배열이 정의되고 해당 크기와 범위는 더 이상 변경되지 않으므로 초기화 및 소멸 외에도 배열은 요소에 액세스하고 요소를 수정하는 작업만 수행합니다. 2차원 배열은 물리적으로 1비트에 매핑되어 저장됩니다. 정렬!

어레이 저장 구조 행 주요; 열 주요

매트릭스의 압축 저장 압축된 저장소: 동일한 값을 가진 여러 요소에는 하나의 저장 공간만 할당되고, 0개 요소에는 저장 공간이 할당되지 않습니다. 특수 행렬: 정규 분포를 사용하여 동일한 행렬 요소가 많거나 요소가 0개입니다.

대칭행렬

A[1 n][1 n]은 B[n(n 1)/2]에 저장됩니다. 한쪽에서는 공식을 전개하고 다른 쪽에서는 i와 j를 교환합니다.

삼각행렬

A[1 n][1 n]은 B[n(n 1)/2 1]에 저장됩니다. 한쪽의 수식을 추론한 후 다른 쪽은 n(n 1)/2에만 숫자를 저장하는데, 이는 첨자가 0부터 시작하기 때문입니다.

상부 삼각 행렬

하부 삼각 행렬

삼중대각 행렬

k=2i j-3 1비트 배열 B의 첨자 k가 i=(k 1)/3 1이면 j=k-2i 3이 제한됩니다. ! ! ! 암기하지 마세요! ! ! 이해하려면 삼중대각 행렬의 해당 행을 스케치하세요! ! !

희소 행렬 행렬에서 0이 아닌 요소 t의 개수는 행렬 요소 s의 개수에 비해 매우 작습니다. 즉, s>>t인 행렬을 희소 행렬이라고 합니다. 예를 들어, 100x100 행렬에는 0이 아닌 요소가 100개 미만입니다.

삼중항(행 레이블, 열 레이블, 값) 또는 교차 연결 목록 방법 사용

꼬치 4개

문자열의 정의와 구현

문자열의 정의: 문자열은 컴퓨터에서 숫자가 아닌 처리의 대상은 기본적으로 문자열 데이터입니다. 문자열(String) S; 문자열에서 임의의 여러 연속 문자열로 구성된 하위 시퀀스를 문자열의 하위 문자열이라고 하며 하위 문자열을 포함하는 해당 문자열을 기본 문자열이라고 합니다. 문자열의 논리적 구조는 선형 테이블의 구조와 매우 유사합니다. 유일한 차이점은 데이터 개체가 문자 집합으로 제한되는 반면 선형 테이블의 작업 개체는 단일 요소라는 것입니다. 하위 문자열입니다!

문자열 저장 구조

고정 길이 순차 저장소 #MaxLen 255 정의 형식 정의 구조체{ char ch[MaxLen]; 정수 길이; }S문자열; 또한 길이를 기록하지 않고 문자열 길이에 포함되지 않은 '\0'을 사용하여 문자열 길이를 암시할 수도 있습니다.

힙 할당 스토리지 표현(동적 할당) 형식 정의 구조체{ 문자*ch; 정수 길이; }HString; C언어에서는 동적으로 할당된 공간을 힙에 저장하고, 할당에 실패하면 NULL을 반환한다.

블록체인 저장 표현: 각 노드를 블록이라고 하며, 블록은 하나의 문자 또는 여러 문자를 저장할 수 있습니다. 전체 연결 목록을 블록체인 구조라고 합니다. 마지막 노드가 한 블록 미만을 차지하면 일반적으로 "#"으로 채워집니다.

기본 문자열 연산 최소 작업 집합: 문자열 할당, 문자열 비교, 문자열 길이 찾기, 문자열 연결 및 하위 문자열 찾기 즉, 이러한 작업은 다른 문자열 작업을 사용하여 구현할 수 없습니다.

문자열 할당 StrAssign(&T,chars)는 T 값을 chars에 할당합니다.

문자열 비교 StrCompare(S,T) if S>T,return>0;S=T,return 0;S<T,return<0

문자열 길이 찾기 StrLength(S)는 S 요소의 수를 반환합니다.

계열 연결 Concat(&T,S1,S2)는 T를 사용하여 S1과 S2를 연결하여 형성된 새 문자열을 반환합니다.

하위 문자열 찾기 SubString(&Sub,S,pos,len) Sub를 사용하여 S 문자열의 pos 문자부터 시작하여 len 길이까지 이어지는 하위 문자열을 반환합니다.

문자열 패턴 매칭 하위 문자열의 위치 지정 작업을 일반적으로 문자열의 패턴 일치라고 합니다. 발견되는 것은 기본 문자열에서 하위 문자열(흔히 패턴 문자열이라고 함)의 위치입니다.

간단한 패턴 매칭 알고리즘

int 인덱스(SString S,SString T){ int i=1,j=1; while(i<=S.길이 && j<=T.길이){ if(S.ch[i] == T.ch[j]){ 나는 ;j ; } 또 다른{ i = i-j 1 1;j = 1; } if(j > T.length) return i - T.length; 그렇지 않으면 0을 반환합니다. } 최악의 시간 복잡도 O(mn)

향상된 패턴 일치 알고리즘 - KMP 알고리즘 일치 과정에서 이미 얻은 일치 정보를 사용하여 기본 문자열 포인터 i가 더 이상 역추적되지 않고 현재 위치에서 계속 역방향으로 일치하도록 합니다. 모드를 뒤로 밀기 위한 자릿수 계산은 모드 자체의 구조에만 관련됩니다! 기본 문자열과 관련이 없습니다. 일반 모드는 O(m n)이지만 KMP 알고리즘에서 인식되는 시간 복잡도는 O(n·m)입니다.

관련 개념: 접두사: 마지막 문자를 제외한 문자열의 모든 헤더 하위 문자열입니다. 접미사: 첫 번째 문자를 제외한 문자열의 모든 후행 하위 문자열입니다. 부분 일치(PM): 문자열의 가장 긴 접두사와 접미사 길이입니다. 예: 'ababa' 주의! ! 주 문자열의 첫 번째 문자부터 시작하여 모든 하위 문자열을 분할한 후 접두사와 접미사의 길이, 가장 긴 동일한 접미사와 접미사를 각각 분석합니다. 'a' 접두사와 접미사는 빈 집합이고, 가장 긴 접두사와 접미사의 길이는 0이다 'ab' 접두사 'a' 접미사 'b' 가장 긴 동일 일치 길이는 0입니다. 'aba' 접두사 'a' 'ab' 접미사 'a' 'ba' {'a' 'ab'} ^ {'a' 'ba'} = 'a', 가장 긴 동일 접미사 길이는 1입니다. 'abab' 접두사 'a' 'ab' 'aba' 접미사 'b' 'ab' 'bab', 가장 긴 접두사와 접미사 길이는 2입니다. 'ababa' 접두사 'a' 'ab' 'aba' 'abab' 접미사 'a' 'ba' 'aba' 'baba' ,{ } ^ { } = {'a' 'aba'}, 가장 긴 접미사 길이와 동일 삼 따라서 최종 문자열의 부분 일치 값은 00123입니다.

KMP 알고리즘을 사용할 때 먼저 패턴 문자열(하위 문자열)의 PM 테이블을 작성하고 하위 문자열이 기본 문자열과 일치하지 않을 때 PM 테이블에서 하위 문자열의 마지막 일치 요소의 PM 값을 찾은 다음 substring 뒤로 이동한 거리(일치한 문자 수 - 마지막으로 일치한 문자의 PM 값), 특정 여행에서 불일치가 발생한 경우 해당 부분의 부분 일치 값이 0이면 등호 접미사가 없음을 의미하며, 이동된 자릿수는 가장 크며(일치 길이 - 0), 다음 비교를 위해 이때 메인 문자열이 가리키는 위치로 바로 이동됩니다. 이동 = (j-1) - PM[j-1];

다음 어레이의 생성 및 수정: 불일치를 용이하게 하기 위해 문자를 기대하는 대신 현재 일치하지 않는 문자 위치의 PM 값을 직접 확인하므로 PM의 모든 요소가 오른쪽으로 1자리 이동되고 첫 번째 위치는 -1로 채워집니다. , 마지막 위치는 무시됩니다. 다음 배열이라 불리는 Move = (j-1)-next[j]; 이때 j는 j로 돌아갑니다. = j-Move = next[j] 1; 그런 다음 모든 next에 1을 더하고 j = next[j]가 되도록 다음 배열을 업데이트합니다. (이때 다음 배열의 첫 번째 위치는 0이 됩니다.) 최종 next 배열의 의미: 부분 문자열의 j번째 문자가 일치하지 않으면 다음 일치 라운드를 위해 부분 문자열의 next[j] 위치로 점프합니다! ! !

최종 다음 배열을 사용하여 코드를 작성합니다. int index_KMP(문자열 T,문자열 S,int next[]){ int i=1,j=1; while(i<=S.길이 && j<=T.길이){ if(S.ch[i] == T.ch[j]){i ;j ;} 그렇지 않으면 j = 다음[j]; } if(j > T.length) return i-T.length; 그렇지 않으면 0을 반환합니다. }

KMP 알고리즘의 추가 최적화 예: 메인 문자열 'aaabaaaab'과 패턴 문자열 'aaaab'이 일치하는 경우 네 번째 위치에 불일치가 있습니다. 위의 next[j] 배열을 사용하면 매번 왼쪽으로 하나씩 이동하고 그런 다음 비교하지만 Pj = Pnext[ j]가 나타나 중복 비교가 발생합니다. 해결책: Pj = Pnext[j]가 나타나지 않는지 확인하십시오. 그렇다면 재귀를 다시 수행하고 next[j]를 next[next[j]]로 수정하고 이름을 nextval[j]로 지정하십시오.

5개의 트리와 이진 트리

나무와 숲

개념

트리는 n(n>0) 노드의 유한 집합입니다. n=0이면 빈 트리라고 합니다. 루트 노드가 하나만 있고 나머지 노드는 하위 트리라고 하는 분리된 유한 집합으로 나눌 수 있습니다. 1. 트리의 루트 노드에는 선행 노드가 없으며 루트 노드 이외의 노드에는 하나의 선행 노드만 있습니다. 2. 트리의 모든 노드에는 0개 이상의 후속 노드가 있을 수 있습니다. 계층적 구조; 3. 용어: 1. 조상-후손(하향식 관계가 있는 한 여러 수준에 걸쳐 있을 수 있음), 자식-부모-형제(동일한 부모 노드 사용) 2. 트리에 있는 노드의 자식 수를 노드의 차수라고 합니다. 트리에 있는 노드의 최대 차수는 트리의 차수입니다. 3. 차수가 0보다 큰 노드를 분기 노드(비말단 노드)라고 하며, 차수가 0인 노드를 리프 노드(말단 노드)라고 합니다. 4. 노드의 수준은 트리의 루트부터 시작하여 정의되며, 루트 노드는 첫 번째 수준입니다. 부모 노드가 동일한 수준에 있는 노드는 서로 사촌입니다. 노드의 깊이는 루트 노드부터 시작하여 위에서 아래로 한 겹씩 누적됩니다. (트리의 뿌리가 아래쪽으로 깊어지는 것을 상상해 보세요.) 노드의 높이는 리프 노드에서 시작하여 아래에서 위로 층별로 누적됩니다. (아래에서 위로 보면 매우 높게 보입니다.) 트리의 높이 또는 깊이는 트리의 최대 노드 수준 수입니다. 4. 정렬된 트리와 정렬되지 않은 트리, 정렬된 트리는 서로 바꿔 사용할 수 없습니다. 5. 경로 및 경로 길이: 경로는 두 노드 사이를 통과하는 노드의 순서로 구성되며, 경로 길이는 통과한 간선의 수입니다! 6. 숲: m개의 분리된 나무들의 집합입니다. 루트 노드가 삭제되면 트리는 숲이 되고, 반대로 m개의 트리에 루트 노드가 추가되면 숲은 트리가 됩니다.

자연

자연: 1. 트리의 노드 수는 모든 노드의 차수의 합(총 가지 수) 1(루트 노드)과 같습니다. 2. 차수가 m인 트리의 i번째 수준에는 최대 m^i-1개의 노드(i>1)가 있습니다. 3. 높이가 h인 m-진 트리에는 최대 (m^i - 1)/(m-1)개의 노드가 있습니다. 4. n 노드가 있는 m-진 트리의 최소 높이는 다음과 같습니다.

저장 구조

1. 순차 저장: 부모 표기법: 큰 구조는 작은 구조를 설정하고 작은 구조는 데이터와 부모 포인터입니다. 큰 구조는 여러 개의 작은 구조와 노드 수로 구성된 배열입니다. #define Max_Tree_SIze 100 형식 정의 구조체{ ElemType 데이터; int 부모; }PT노드; 형식 정의 구조체{ PT노드 노드[Max_Tree_Size]; int n; }P트리; 이 구조는 각 노드(루트 노드 제외)에 하나의 상위 노드만 있다는 점을 활용합니다. 각 노드의 상위 노드는 빠르게 얻을 수 있지만 노드의 하위 노드를 찾으려면 전체 트리를 탐색해야 합니다.

2. 자식 표현에서: 각 노드의 자식 노드를 단일 연결 목록으로 연결하여 n개의 노드에 대한 n개의 연결된 목록이 있습니다(리프 노드의 자식 연결 목록은 빈 연결 목록입니다). 이 방법은 자식을 찾는 것이 매우 간단하지만 부모를 찾으려면 n 노드의 자식 연결 목록 포인터가 가리키는 n 자식 연결 목록을 순회해야 합니다. 크리티컬 테이블과 유사

3. 하위 형제 표현: 이진 트리 표현이라고도 알려져 있습니다. typedef 구조체 CSNode{ ElemType 데이터; struct CSNode *firstchild,*nextsibling; }CS노드,*CSTree; 트리를 이진트리로 변환하는 연산을 편리하게 구현 왼쪽 아이는 남동생이 있어요

작업: 트리, 포리스트 및 이진 트리의 변환

트리와 이진 트리 간의 변환: 트리와 이진 트리는 모두 이진 연결 목록으로 표현될 수 있습니다. 물리적 구조는 동일하지만 트리를 이진 트리로 변환하는 규칙은 다릅니다. 루트 노드에는 형제가 없으므로 루트 노드에는 오른쪽 하위 트리가 없습니다. 필기 변환 단계: 1. 형제 노드 사이에 선을 연결합니다. 2. 각 노드와 첫 번째 자식 사이의 연결만 유지하고 다른 노드를 사용합니다. 모든 자식 연결을 삭제합니다. 3. 나무의 뿌리를 축으로 삼아 시계방향으로 45도 회전시킵니다.

포레스트에서 이진 트리로의 변환 1. 먼저 포리스트의 각 트리를 이진 트리로 변환합니다. 2. 각 트리의 루트는 형제 관계로 간주되며, 이후 트리는 순차적으로 이전 트리의 오른쪽 노드로 간주됩니다. 3. 첫 번째 트리의 루트를 시계 방향으로 45도 회전합니다.

이진 트리를 포리스트로 변환합니다. 1. 오른쪽 하위 트리 없이 루트 노드가 하나만 남을 때까지 루트 노드의 오른쪽 하위 트리를 차례로 연결 해제합니다. 2. 연결이 끊어진 모든 이진 트리를 트리로 변환하여 원래 포리스트를 얻습니다. 이진 트리를 트리나 포리스트로 변환하는 것은 고유합니다.

이진 트리를 트리로 변환 1. 루트 노드의 왼쪽 하위 트리에서 오른쪽 노드, 오른쪽 노드, 오른쪽 노드를 모두 제거합니다. . . 모두 루트의 자식으로 2. 순서대로 조정

횡단

트리 순회

루트 순회 먼저 해당 이진 트리의 선주문 순회와 동일

백 루트 순회 해당 이진 트리의 순차 순회와 동일합니다! ! ! ! !

레벨 순회

숲속을 여행하다

숲의 순회를 예약 주문하세요 앞에서 뒤로 각 트리는 루트를 먼저 통과합니다.

순차적으로 숲을 횡단 각 트리의 루트를 앞에서 뒤로 탐색합니다(포리스트에서는 순차 탐색이 해당 이진 트리에 상대적이라고 말합니다).

트리 적용 - 조합 검색

Union-find는 3가지 작업을 지원하는 간단한 집합 표현입니다. 통합 검색 세트의 구조 정의: #크기 100 정의 int UFSets[크기]; 통합 검색의 집합은 트리이고 여러 집합이 숲을 형성합니다.

초기화 작업(S는 통합 검색 집합), 집합 S의 각 요소를 하나의 단일 요소만 포함하는 하위 집합으로 초기화합니다. S는 상위 표현 배열에 저장된 전체 집합, 즉 포리스트입니다(둘 다 - 현재 1개) 무효 초기(int S[]){ for(int i=0;i<크기;i) S[i] = -1; }

찾기 작업은 집합 S에서 단일 요소 x가 있는 하위 컬렉션을 찾고 하위 컬렉션의 이름을 반환합니다. int Find(int S[],int x){ while(S[x]>=0)//x의 근을 찾기 위해 루프를 돌립니다. x = S[x];//x의 루트에 x를 할당합니다. x를 반환; }

통합 작업은 S 세트의 하위 세트 root2를 root1로 병합합니다. 이를 위해서는 root1과 root2가 서로 교차하지 않아야 합니다. 그렇지 않으면 병합되지 않습니다. 무효 유니온(int S[],int Root1,int Root2){ //Root1과 Root2가 달라야 함 S[Root2] = Root1; //Root2를 다른 Root1에 연결 } 부모 표현 배열의 포리스트에 있는 각 트리의 루트 노드 값은 음수이며, 절대값은 루트 아래의 총 노드 수입니다.

이진 트리

개념: 각 노드에는 최대 2개의 하위 트리가 있으며 순서는 바뀔 수 없습니다. 이진 트리의 노드 순서는 다른 노드와 관련이 없으며 결정됩니다. (차수가 2인 트리와 다름) 몇 가지 특별한 이진 트리: 1. 완전 이진 트리: 각 레벨에는 가장 많은 노드가 포함됩니다. 2. 완전한 이진 트리: 1-n 시퀀스 번호는 전체 이진 트리의 노드와 완전히 일치합니다. 3. 이진 정렬 트리의 왼쪽 하위 트리에 있는 모든 노드의 키는 루트 노드의 키보다 작고, 오른쪽에 있는 키는 루트보다 큽니다. 4. 균형 이진 트리: 트리에 있는 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 간의 깊이 차이가 1을 초과하지 않습니다. 5. 단서 이진 트리

단서 이진 트리(낯설어서 특별히 확장됨) typedef struct TreadNode{ ElemType 데이터; struct TreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; 이진 트리의 저장 구조로서 노드 구조로 구성된 이진 연결 리스트를 단서 연결 리스트라고 하며, 노드의 선행 노드와 후행 노드를 가리키는 포인터를 단서라고 합니다. 단서가 있는 이진 트리를 단서 이진 트리라고 합니다.

특성 및 정의: 이진 트리의 널 포인터를 사용하여 선행자 또는 후속자 포인터를 저장하면 연결 목록을 탐색하는 것처럼 쉽게 탐색할 수 있습니다. 단서 이진 트리는 노드의 이전 및 후속 노드를 찾는 속도를 높여줍니다! 규정: 왼쪽 하위 트리가 없으면 lchild가 이전 노드를 가리키도록 하고, 오른쪽 하위 트리가 없으면 rchild가 후속 노드를 가리키도록 합니다. (lchild,ltag,data,rtag,rchild) ltag = 0,lchild는 왼쪽 하위를 참조하고, ltag = 1,lchild는 노드 선행 노드를 참조합니다. rtag = 0, rchild는 오른쪽 자식을 나타내고, rtag = 1, rchild는 노드의 후속 노드를 나타냅니다.

순차 단서 이진 트리 구축 이진 트리 단서의 본질은 이진 트리를 한 번 순회하는 것입니다. 무효 InTread(ThreadTree &p,ThreadTree &pre){ if(p!=NULL){ InThread(p->lchild,pre); if(p->lchild == NULL){ p->lchild = 사전; p->ltag = 1; } if(pre!=NULL && pre->next->rchild == NULL){ pre->rchild = p; 사전->rtag = 1; } 사전 = p; InThread(p->rchild,pre); } } 무효 CreateInThread(ThreadTree T){ ThreadTree 사전 = NULL; if(T!=NULL){ InThread(T,pre); 사전>자식 = NULL; 사전->rtag = 1; } } 또한 이진 트리의 단서 목록에 헤드 노드를 추가할 수 있으며, lchild는 이진 트리의 루트 노드를 참조하고 rchild는 이진 트리의 마지막 방문 노드를 참조하도록 할 수 있습니다. 또한 이진 트리에서 처음 방문한 노드의 lchild와 마지막 방문 노드의 rchild는 모두 헤드 노드를 가리킵니다. 이는 단서 이진 트리를 앞에서 뒤로, 뒤에서 앞으로 순회하는 것을 용이하게 하는 양방향 단서 연결 목록이 됩니다.

중위 단서가 있는 이진 트리 순회 순차 단서 이진 트리의 노드는 단서 이진 트리의 선행 정보와 후행 정보를 숨깁니다. 1. 순차 단서 이진 트리의 순차 시퀀스 아래에서 첫 번째 노드를 찾습니다. ThreadNode *Firstnode(ThreadNode *p){ while(p->ltag == 0) p = p->lchild; p를 반환; }//왼쪽 아래 노드 찾기(반드시 리프 노드일 필요는 없음) 2. 순차 단서 이진 트리에서 순차 시퀀스에서 노드 p의 후속자를 찾습니다. ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag == 0) return Firstnode(p->rchild); 그렇지 않으면 p->rchild를 반환합니다. } 3. 주요 기능 무효 중순(ThreadNode *T){ for(ThreadNode *p = Firstnode(T);p!=NULL;p-Nextnode(p)) 방문(p); }

선주문 단서 이진 트리 및 후주문 단서 이진 트리 스레드 변환의 코드 세그먼트와 스레드 왼쪽 및 오른쪽 하위 트리 재귀 함수가 호출되는 위치만 변경하면 됩니다. NULL을 가리키는 방향은 다를 수 있습니다. 선행 작업은 NULL을 참조하고 후속 작업은 NULL을 참조합니다. 특정 선행자와 후임자는 순회 순서에 따라 자세히 분석되어야 합니다. 특수: 후위 단서 이진 트리에서 후속 항목을 찾으려면 노드 부모를 알아야 합니다. 즉, 저장 구조로 플래그 필드가 있는 삼지창 연결 목록을 사용해야 합니다(삼지창 연결 목록에는 세 개의 필드가 있습니다). , 상위 노드에 대한 포인터가 추가됩니다)

자연: 1. 비어 있지 않은 이진 트리의 리프 노드 수는 2차 노드 수와 같습니다. 1, 즉 n0 = n2 1 2. 비어 있지 않은 이진 트리의 k번째 수준에는 최대 2^(k-1)개의 노드가 있습니다. 3. 높이가 h인 비어 있지 않은 이진 트리에는 최대 2^h-1개의 노드가 있습니다. 4. 완전한 이진 트리: i>1 부모 노드는 i/2로 제한됩니다. i는 짝수, i/2, i는 홀수, (i-1)/2 2i<=n i의 왼쪽 자식은 2i이고, 그렇지 않으면 왼쪽 자식이 없습니다. 2i 1<=n i의 오른쪽 자식은 2i 1이고, 그렇지 않으면 오른쪽 자식이 없습니다. 5. 두 가지 공식: 2^(h-1)-1<n<=2^h-1;2^(h-1) <=n <2^h

저장 구조: 1. 순차 저장 구조: 완전 이진 트리와 완전 이진 트리는 순차 저장 구조에 적합합니다. 일반 이진 트리는 많은 빈 노드(배열에 0)를 추가해야 합니다. 배열 첨자 1에서 저장을 시작하는 것이 좋습니다. 완전 이진 트리 i 2. 체인 저장 구조: 순차 저장 구조(일반 이진 트리)보다 공간 활용도가 높습니다. typedef 구조체 BiTNode{ ElemType 데이터; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

작동하다

횡단

DFS 각 노드는 한 번만 방문됩니다. 시간 복잡도와 공간 복잡도는 모두 O(n)입니다. 재귀 작업 스택의 깊이는 트리의 깊이입니다.

선주문 순회 사전주문 무효(바이트리T){ if(T!=NULL){ 방문(T); 사전주문(T->lchild); PreOreder(T->자식); } } 비재귀적: 사전주문2 무효(바이트리T){ InitStack(S);BiTree p = T; while(p || !isEmpty(S)){ 만약(피){ 방문(p);푸시(S,p); p = p->lchild; } 또 다른{ 팝(S,p); p = p->rchild; } } }

중위순회 무효 InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); 방문(T); InOrder(T->자식); } } 비재귀적: 무효 InOrder2(바이트리 T){ InitStack(S);BiTree p = T; while(p || !isEmpty(S)){//p가 비어 있지 않거나 스택이 비어 있지 않습니다 루프 if(p){ //왼쪽 끝까지 푸시(S,p); p = p->lchild; } 또 다른{ 팝(S,p);방문(p); p = p->rchild; //p는 오른쪽 하위 트리로 이동합니다. } } }

후순위 순회 PostOrder 무효(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); PostOrder(T->자식); 방문(T); } }

BFS

레벨 순회 void LevelOrder(BiTree T){ 초기화큐(Q); BiTree p = T; 대기열에 넣기(Q,p); 동안(!isEmpty(Q)){ 큐에서 제거(Q,p); 방문(p); if(p->lchild != NULL) Enqueue(Q,p->lchild); if(p->rchild != NULL) Enqueue(Q,p->rchild); } }

애플리케이션

이진 정렬 트리 BST (이진 검색 트리)

BST 조회 BST노드 *BST_Search(BiTree T,ElemType 키){ while(T!=NULL&&key!=T->데이터){ if(key<T.data) T = T->lchild; 그렇지 않으면 T=T->rchild; } T를 반환; }

BST 삽입: 삽입된 노드는 새로 추가된 리프 노드여야 합니다. int BST_Insert(BiTree &T,KeyType k){ if(T==NULL){ T = (BiTree)malloc(sizeof(BSTNode)); T->키 = k; T->lchild = T->rchild = NULL; 1을 반환합니다. } else if(k==T->key) 0을 반환합니다; else if(k<T->key) return BST_Insert(T->lchild,k); 그렇지 않으면 BST_Insert(T->rchild,k)를 반환합니다. }

BST의 구조 void Creat_BST(BiTree &T,KeyType str[],int n){ T = NULL; int i =0; 동안(i<n){ BST_Insert(T,str[i]); 나; } }

BST 삭제

삭제된 노드는 리프 노드이며 직접 삭제됩니다.

삭제된 노드 z에 왼쪽 하위 트리 또는 오른쪽 하위 트리가 하나만 있는 경우 왼쪽 하위 트리 또는 오른쪽 하위 트리가 z를 대체하도록 합니다.

삭제된 노드 z에 왼쪽 및 오른쪽 하위 트리가 모두 있는 경우 z를 z의 직접 후속 노드(또는 직접 선행 노드)로 대체한 다음 BST에서 이 직접 후속 노드(또는 직접 선행 노드)를 삭제하여 처음 두 상황으로 전환합니다.

BST 검색 효율성 분석

BST의 검색 효율성은 주로 트리의 높이에 따라 달라집니다. BST의 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이가 1을 초과하지 않는 경우 이러한 이진 정렬 트리를 균형 이진 트리라고 하며 평균 검색 길이는 O(log2n)입니다. BST가 단일 트리인 경우 평균 검색 길이는 O(n)입니다.

평균 검색 길이 ASL=∑PiCi (i=1,2,3,…,n)Pi는 룩업 테이블에서 i번째 데이터 요소의 확률이고, Ci는 찾을 때 비교된 횟수입니다. i번째 데이터 요소.

BST와 이진 검색의 비교: 이진 검색의 결정 트리는 고유하지만 BST 검색은 고유하지 않습니다(삽입 순서는 트리 모양에 영향을 미칩니다). 삽입 및 삭제: 이진 검색의 개체는 O(n)이 필요한 정렬된 시퀀스 목록입니다. BST는 노드를 이동할 필요가 없지만 완료하려면 포인터만 수정하면 됩니다. 이는 O(log2n)입니다. 요약: 정렬된 테이블이 정적 조회 테이블인 경우 순차 테이블 저장에 적합하며 이진 검색을 사용합니다. 정렬된 테이블이 동적 조회 테이블인 경우 논리적 구조로 이진 정렬 트리를 선택해야 합니다.

균형 이진 트리

이진 정렬 트리의 성능 저하를 방지하도록 설계됨 정의: 모든 노드의 왼쪽 단어와 오른쪽 단어 사이의 높이 차이의 절대값은 1을 초과하지 않으며 이를 균형 트리라고 합니다. 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 사이의 높이 차이는 노드의 균형 인자입니다. 균형 이진 트리 노드의 균형 인자는 -1 0 1일 수 있습니다. 따라서 균형 이진 트리는 다음과 같이 정의될 수 있습니다. 빈 나무.

균형 이진 트리에 삽입: 각 조정의 대상은 최소 불균형 하위 트리, 즉 삽입 경로에서 삽입된 노드에 가장 가까운 균형 인자의 절대값이 1보다 큰 노드를 루트로 하는 하위 트리입니다! 균형 이진 트리의 삽입 과정 전반부는 이진 정렬 트리와 동일하지만 삽입 후 불균형이 발생하면 4가지 상황으로 나누어진다. (향상된 BST); 여기서 LL RR LR RL은 최소 불균형 하위 트리의 루트 노드(자식의 특정 하위 트리 위치)를 기준으로 삽입된 노드의 위치를 나타냅니다.

LL 균형 회전(오른쪽 단일 회전) 노드는 A의 왼쪽 하위 트리(바로 인접해야 함)의 왼쪽 아래(바로 인접할 필요는 없음)에 삽입되고 첫 번째 L(최소 불균형 하위 트리 루트 노드의 왼쪽 자식)에 있는 B 노드는 다음과 같습니다. A를 대체하기 위해 오른쪽으로 회전하고 A는 B의 오른쪽 자식이므로 B는 원래 A의 왼쪽 하위 트리로 자식을 가졌습니다.

RR 균형 스핀(왼쪽 단일 스핀) 노드는 A의 오른쪽 자식의 오른쪽 아래에 삽입됩니다. 첫 번째 R의 B 노드는 A를 대체하기 위해 왼쪽으로 회전됩니다. A는 B의 왼쪽 하위 트리로 사용되고 B의 원래 왼쪽 하위 트리는 A의 오른쪽 하위 트리 ps: LL 및 RR 모드는 모두 불균형 하위 트리 노드 A의 왼쪽/오른쪽 하위 B가 "나타나도록" 도와줍니다.

LR 균형 회전(먼저 왼쪽, 그 다음 오른쪽으로 이중 회전) 노드 A의 왼쪽 자식의 오른쪽 하위 트리에 노드가 삽입됩니다. 먼저 A의 왼쪽 자식 B의 오른쪽 하위 트리의 루트 노드 C를 왼쪽 위 방향으로 B의 위치로 회전시킨 다음, 오른쪽 위 방향의 C 노드를 A 노드의 위치로 회전시킵니다.

RL 균형 회전(오른쪽 및 왼쪽 이중 회전) 노드 A의 오른쪽 자식의 왼쪽 하위 트리에 노드가 삽입됩니다. 먼저 노드 A의 오른쪽 자식 B의 왼쪽 하위 트리 루트 노드 C를 B의 위치로 회전시킨 다음 C를 노드 A의 위치로 회전시킵니다. ps: LR과 RL이 회전할 때 새 노드가 C의 왼쪽 하위 트리에 삽입되거나 C의 오른쪽 하위 트리에 삽입되는지 여부는 회전 프로세스에 영향을 주지 않습니다. LR 및 RL 모드는 불균형 하위 트리의 왼쪽/오른쪽 하위 트리 "상위"의 오른쪽/왼쪽 하위 트리의 루트 노드 C를 돕는 것입니다.

균형 이진 트리 찾기 이진 정렬 트리 검색과 동일합니다. n개의 노드를 포함하는 균형 이진 트리의 최대 깊이는 O(log2n)이므로 최대 검색 길이도 O(log2n)입니다. 주어진 노드 수로 균형 이진 트리를 찾는 데 필요한 최대 비교 횟수입니다.

높이 h의 균형 이진 트리 최대 2^h - 1개의 노드가 있습니다. 적어도 h(n)개의 노드가 있습니다. h(n)=h(n-1) h(n-1) 1,h(0)=0,h(1)=1,h(2)=2c

레드 블랙 트리

레드 블랙 트리 개념

레드-블랙 트리의 기본 연산

레드 블랙 트리 속성

레드-블랙 트리의 응용

레드-블랙 트리 성능 분석

허프만 트리와 허프만 코딩

허프만 트리 정의 트리의 노드에는 노드의 가중치라고 하는 특정 의미를 나타내는 값이 할당됩니다. 트리의 루트에서 임의의 노드까지의 경로 길이(통과된 모서리 수)와 노드의 가중치를 곱한 값을 노드의 가중치 경로 길이라고 합니다. 트리에 있는 모든 리프 노드의 가중치 경로 길이의 합을 트리의 가중치 경로 길이라고 하며 WPL(Weighted Path Length of Tree)로 기록됩니다. n개의 가중치 리프 노드가 있는 이진 트리에서 가장 작은 가중치 경로 길이 WPL을 갖는 이진 트리를 허프만 트리라고 합니다! 최적 이진 트리라고도 함

허프만 트리의 구조 가중치가 각각 w1,w2,..,wn인 n개의 노드가 주어지면 새로운 루트 노드를 생성하고, 매번 가장 작은 가중치를 갖는 두 개의 노드를 선택하여 두 노드의 가중치를 추가하고 이를 원래 계열에 있는 새 루트 노드 가중치로 처리합니다. 루트 노드가 삭제되고 가중치가 있는 새 루트 노드가 추가됩니다. 더 이상 독립 노드가 없을 때까지 이 과정을 반복합니다.

허프만 트리의 특성 1. 각 초기 노드는 결국 리프 노드가 되며, 가중치가 작을수록 해당 노드에서 루트 노드까지의 경로 길이가 길어집니다. 2. 구축 과정에서 총 n-1개의 새 노드(이중 가지 노드)가 생성되므로 허프만 트리의 총 노드 수는 2n-1개입니다. 3. 각 구성은 새 노드의 자식으로 2개의 트리를 선택하므로 허프만 트리에는 차수가 1인 노드가 없습니다.

허프만 코딩

몇 가지 관련 개념: 고정 길이 인코딩: 각 문자의 동일한 길이 이진 표현 가변 길이 인코딩: 서로 다른 문자는 서로 다른 길이의 이진 비트로 표시됩니다. 가변길이 인코딩은 고정길이 인코딩에 비해 발생빈도가 높은 문자에는 숏코드를 할당하고, 발생빈도가 낮은 코드에는 긴 코드를 할당함으로써 문자의 평균 인코딩 길이를 단축시키고 데이터를 압축하는 효과가 훨씬 뛰어나다. , 허프만 코딩은 널리 사용되며 매우 효과적인 데이터 압축 코딩입니다. 코드 중 어느 것도 접두사의 코드가 아니며, 접두사의 코드입니다. 앞에서 뒤로 식별하고 원래 코드로 변환합니다.

허프만 트리는 루트에서 내려와 한쪽에 0을 할당하고 다른쪽에 1을 할당합니다(항상 통합되는 한 왼쪽과 오른쪽에 0 또는 1). 허프만 트리의 WPL은 최종 인코딩으로 얻은 이진 코드 길이로 간주할 수 있습니다. 허프만 트리는 고유하지 않으며 WPL은 최적이어야 합니다.

사진 6장

그래프의 기본 개념

G=(V,E), 정점 세트 V, 모서리 세트 E; V(G)는 그래프 G의 비어 있지 않은 유한 정점 세트를 나타냅니다. E(G)는 그래프의 정점 사이의 관계(모서리) 세트를 나타냅니다. G |V|는 정점 수를 나타내고, |E|는 가장자리 수를 나타냅니다. 선형 테이블은 빈 테이블이 될 수 있고 트리는 빈 트리가 될 수 있지만 그래프는 빈 그래프가 될 수 없습니다. 그래프의 정점 세트 V는 비어 있으면 안 되며, E도 비어 있을 수 있습니다.

유방향 그래프, 무방향 그래프 방향 그래프: E는 방향이 있는 모서리(호)이고 호는 <v,w>로 표시되는 정렬된 정점 쌍입니다. 무방향 그래프: E는 무방향 간선(edge)이고 간선은 순서가 지정되지 않은 정점 쌍이며 (v, w)로 기록됩니다.

단순 그래프, 다중 그래프 간단한 다이어그램: 1. 중복된 간선이 없습니다. (유향 그래프에서 인접한 두 노드 사이에서 서로를 가리키는 간선은 중복 간선으로 간주되지 않습니다.) 2. 꼭지점에서 그 자체까지의 가장자리는 없습니다. 다중 플롯: 1. 두 정점 사이의 간선 개수가 1보다 큽니다. 2. 정점이 가장자리를 통해 서로 관련되도록 허용 다중 그래프와 단순 그래프의 정의는 상대적입니다. 데이터 구조에서는 단순 그래프만 설명합니다.

전체 그래프(간단한 전체 그래프) 무방향 그래프의 경우 |E|의 값 범위는 0-n(n-1)/2입니다. n(n-1)/2개의 간선이 있는 무방향 그래프를 완전 그래프라고 하며 두 정점 사이에 간선이 있습니다. 유향 그래프의 경우 |E|의 값 범위는 0-n(n-1)입니다. n(n-1)개의 호를 갖는 유향 그래프를 유향 완전 그래프라고 하며 두 꼭지점 사이에 반대 호가 있습니다.

서브플롯 G=(V,E),G'=(V',E'); V'가 V의 부분 집합이고 E'가 E의 부분 집합이면 G'를 G의 부분 그래프라고 합니다. V(G')=V(G)가 충족되면 G'를 G의 생성된 하위 그래프라고 합니다. V와 E의 어떤 부분 집합도 G 부분 그래프를 형성할 수 없습니다. 왜냐하면 E 부분 집합의 일부 간선과 연관된 정점이 V의 이 부분 집합에 속하지 않을 수 있기 때문입니다.

연결성, 연결된 그래프 및 연결된 구성요소 정점 v에서 정점 w까지의 경로가 있으면 v와 w는 연결되어 있다고 합니다. G의 두 정점이 연결되면 연결된 그래프가 되고, 그렇지 않으면 연결되지 않은 그래프가 됩니다. 무방향 그래프에서 최대 연결된 부분 그래프를 연결된 구성요소라고 합니다. 연결된 그래프에는 최소한 n-1개의 간선이 있습니다. 간선 수가 n-1보다 작으면 연결되지 않은 그래프여야 합니다. 연결이 끊긴 그래프는 최대 몇 개의 간선을 가질 수 있습니까? : 완전한 그래프를 형성하는 n-1개의 정점의 임계 상태(언제든지 간선을 추가하여 연결된 그래프를 형성)

최대 연결 하위 그래프: 다른 연결된 하위 그래프에 포함되지 않은 그래프 G의 연결된 하위 그래프(여기서 최대값은 특정 수량의 최대값이 아니라 포함되지 않는 관계로 실제로 연결된 하위 그래프와 가장자리의 모든 정점을 의미함) 존재하다) 최소 연결 하위 그래프: 그래프 G의 스패닝 트리는 최소 연결 하위 그래프입니다.

강하게 연결된 그래프, 강하게 연결된 구성요소 유향 그래프에서 v에서 w로, w에서 v로의 한 쌍의 정점이 경로를 갖는 경우 두 정점은 강하게 연결되어 있다고 합니다. 그래프의 한 쌍의 정점이 강하게 연결되어 있는 경우 해당 그래프를 강하게 연결된 그래프라고 합니다. 유향 그래프에서 최대로 강하게 연결된 부분 그래프를 유향 그래프의 강하게 연결된 구성 요소라고 합니다. 유향 그래프가 강하게 연결되어 있을 때 간선 수가 가장 적은 상황: 순환을 형성하려면 최소한 n개의 간선이 필요합니다.

스패닝 트리, 스패닝 포리스트 연결 그래프의 스패닝 트리는 그래프의 모든 꼭지점을 포함하는 최소 연결 하위 그래프입니다. 고정 꼭지점의 수가 n이면 스패닝 트리의 간선은 n-1개입니다. 스패닝 트리에서 가장자리가 잘리면 연결되지 않은 하위 그래프가 되고, 가장자리가 추가되면 순환이 형성됩니다. 연결이 끊긴 그래프에서 연결된 구성 요소의 스패닝 트리는 연결이 끊긴 그래프의 스패닝 포리스트를 구성합니다.

정점 차수, 내차수 및 외차수 무방향 그래프: TD(v), 무방향 그래프의 모든 정점의 차수의 합은 간선 수의 2배와 같습니다. 방향 그래프: 정점 v의 각도는 내부 차수 ID(v)와 외부 차수 OD(v)로 나누어집니다. 정점 v의 차수는 내부 차수와 외부 차수의 합: TD(v)와 같습니다. =ID(v) OD(v) , 유향 그래프의 모든 정점의 진입 차수는 가장자리 수와 동일한 진출 차수와 같습니다.

비안의 Quanhe.com 각 간선은 특정 의미를 갖는 숫자 값으로 표시될 수 있으며, 이를 간선의 가중치라고 합니다. 가중치 간선이 있는 그래프를 네트워크라고도 하는 가중치 그래프라고 합니다.

조밀한 그래프, 희소 그래프 간선이 적은 그래프를 희소 그래프(sparse graph)라고 하고, 반대 그래프를 조밀 그래프(dense graph)라고 합니다. 일반적으로 G가 |E|<|V|log|V|를 만족하면 G는 희소 그래프로 간주됩니다.

경로, 경로 길이 및 루프 경로: 정점 vp에서 vq까지의 경로는 정점 시퀀스 vp,vi1...vim,vq를 나타냅니다. 경로의 가장자리 수를 경로 길이라고 합니다. 첫 번째 정점과 마지막 정점이 동일한 경로를 사이클 또는 사이클이라고 합니다. 그래프에 n개의 정점과 n-1개보다 많은 간선이 있는 경우 그래프에는 사이클이 있어야 합니다.

간단한 경로, 간단한 루프 경로 시퀀스에서 정점이 반복적으로 나타나지 않는 경로를 단순 경로라고 합니다. 첫 번째 꼭지점과 마지막 꼭지점을 제외하고 나머지 꼭지점이 해당 그래프에서 멈추지 않는 주기를 단순주기라고 합니다.

거리 정점 u에서 정점 v까지의 최단 경로가 존재하는 경우 이 경로의 길이는 u에서 v까지의 거리입니다. u에서 v까지의 경로가 전혀 없으면 거리가 로 기록됩니다.

방향성 트리 한 꼭지점의 진입차수가 0이고 나머지 꼭짓점의 진출차수가 1인 방향 그래프를 방향성 트리라고 합니다.

그래프 저장

인접 행렬 방법

1차원 배열을 사용하여 그래프의 꼭지점 간의 관계를 저장하는 것을 말하며, 2차원 배열을 사용하여 그래프의 모서리 정보(꼭지점 간의 인접 관계)를 저장하는 것을 말합니다. 정점 간의 인접 관계를 인접 행렬이라고 합니다. 전체 그래프 G의 저장 구조: #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; 형식 정의 구조체{ VertexType Vex[MaxVertexNum] //정점 테이블 EdgeType Edge[MaxVertexNum][MaxVertexNum];//인접 행렬, 엣지 테이블 int vexnum,arcnum; }M그래프;

알아채다: 1. 간단한 응용에서는 2차원 배열을 그래프의 인접 행렬로 직접 사용할 수 있습니다. 2. 무방향 그래프에서 인접 행렬은 대칭 행렬(고유)이며 압축하여 저장할 수 있습니다. 3. 인접 행렬이 Edge 존재 여부만 나타내는 경우 ElemType은 0과 1의 열거 유형을 채택할 수 있습니다. 4. 인접 행렬 표현의 공간 복잡도는 O(n^2)이고, n은 정점 수 |V|

인접 행렬 표현의 특징: 1. 무방향 그래프의 i번째 행(또는 j열)에 있는 0이 아닌 요소(또는 0이 아닌 요소)의 개수는 노드의 차수 TD(v)를 나타냅니다. 유향 그래프의 i번째 행과 j번째 열에 있는 0이 아닌 요소(또는 0이 아닌 요소)의 수는 노드의 외차 OD(v) 및 내차 ID(v)를 나타냅니다. 2. 인접 행렬을 사용하여 그래프를 저장하면 그래프의 두 꼭지점 사이에 간선 연결이 있는지 확인하기가 쉽지만 그래프에 간선 수를 확인하려면 각 요소를 행별로 감지해야 합니다. 그리고 컬럼은 시간이 많이 소요됩니다. 3. 조밀한 그래프는 인접 행렬을 사용한 저장 표현에 적합합니다. 4. 그래프 G의 인접 행렬은 A이고, A^n의 요소 A^n[i][j]는 정점 i에서 정점 j까지 길이 n인 경로의 수와 같다고 가정합니다.

인접 목록 방법

그래프가 희소 그래프인 경우 인접 목록 방법을 사용하면 많은 공간이 절약됩니다. 그래프 인접 목록 방법은 순차 저장 방법과 체인 저장 방법을 결합합니다. 그래프의 각 꼭지점에 대해 단일 연결 리스트를 만듭니다. i번째 단일 연결 리스트의 노드는 꼭지점의 모서리 vi에 연결됩니다. 이 단일 연결 리스트는 꼭짓점 vi의 모서리 리스트입니다. 나가는 에지 목록) (에지 목록은 "Edge"라는 것이 정말 놀랍습니다.) 에지 테이블의 각 노드는 에지를 나타내지만 정점 번호를 저장하고 다른 정점 번호를 생략합니다(정점 테이블에서). 에지 테이블의 헤드 포인터와 그래프 G의 정점 데이터 정보가 순차적으로 저장됩니다(정점 테이블이라고 함). #define MaxVertexNum 100 typedef struct ArcNode{//edge 테이블 노드 int adjvex;//호가 가리키는 정점의 위치 구조체 ArcNode *next; //Info Typeinfo; //네트워크의 에지 가중치 }ArcNode; typedef 구조체 VNode{ VertexType 데이터;//정점 정보 struct VNode *first;//정점에 연결된 첫 번째 호에 대한 포인터 }VNode, AdjList[MaxVertexNum]; 형식 정의 구조체{ AdjList 정점;//인접 목록 int vexnum,arcnum;//그래프의 꼭지점과 호의 개수 }알그래프

특징: 1. 무방향 그래프의 경우 필요한 저장 공간은 O(|V| 2|E|)입니다(각 모서리는 인접 목록에 두 번 나타납니다). 유방향 그래프의 경우 필요한 저장 공간은 O(|V| |E|)입니다. 2. 희소 그래프의 경우 인접 목록을 사용하면 저장 공간을 크게 절약할 수 있습니다. 3. 인접 목록에서 정점이 주어지면 인접 행렬에서 모든 가장자리를 쉽게 찾을 수 있습니다. 한 행을 스캔해야 합니다(O(n)). 주어진 두 정점 사이에 간선이 있는지 확인하려면 인접 행렬에서 빠르게 찾을 수 있지만(비트 랜덤 액세스), 인접 행렬은 해당 노드에 해당하는 간선 테이블에서 다른 노드를 찾아야 합니다. , 이는 더 낮습니다. 4. 유향 그래프에서 정점의 아웃 차수를 찾으려면 인접 인접 목록의 노드 수만 계산해야 하지만 아웃 차수를 찾으려면 모든 인접 목록을 순회해야 하므로 역 인접 목록을 사용하여 다음을 수행할 수 있습니다. 정점 솔루션의 내부 차수를 가속화합니다. 5. 그래프의 인접 목록은 고유하지 않으며 에지 노드의 연결 순서는 임의적입니다.

교차 목록 방법

교차 연결 목록은 방향성 그래프의 연결된 저장 구조입니다. 그래프의 각 호에는 노드가 있습니다. 아크 노드에는 5개의 필드가 있습니다: (tailvex, headvex, hlink, tlink, info) tailvex 및 headvex는 각각 가장자리의 시작 및 삽입 정점입니다. hlink 및 tlink는 각각 동일한 시작 및 삽입 정점의 가장자리 노드를 연결합니다. 정점 노드에는 3개의 필드(data, firstin, firstout)가 있습니다. 교차연결리스트는 고유하지 않지만 교차연결리스트는 특정 그래프를 나타냅니다. Cross Linked List에서는 V의 in-degree와 out-degree를 쉽게 찾을 수 있습니다.

인접 다중 목록 방법

인접 다중 리스트는 무방향 그래프의 체인 저장 구조입니다. 에지 노드(mark,ivex,ilink,jvex,jlink,info) mark는 이 에지가 검색되었는지 여부를 표시할 수 있는 플래그 필드입니다. ivex와 jvex는 그래프의 에지에 연결된 두 정점의 위치입니다. ilink는 ivex에 연결된 다음 에지를 가리킵니다. 정점에 첨부된 jvex edge info는 가장자리와 관련된 다양한 정보를 가리키는 포인터 필드입니다. 정점(데이터,첫 번째 가장자리)

그래프의 기본 작업

인접(G,x,y);이웃(G,x);정점 삽입(G,x);정점 삭제(G,x); AddEdge(G,x);RemoveEdge(G,x,y);FirstNeighbor(G,x);NextNeighbor(G,x); Get_edge_value(G,x,y);Set_edge_value(G,x,y,v);

그래프 순회 특정 정점에서 시작하여 모든 정점을 한 번만 방문하는 것은 연결 문제, 위상 정렬 및 임계 경로 알고리즘 문제를 해결하기 위한 기초입니다. 트리와는 달리 동일한 정점을 여러 번 방문하는 것을 방지하기 위해 정점을 순회한 후 기록해야 하며 보조 배열이 방문되었습니다[]; 그래프 순회에는 BFS 및 DFS가 포함됩니다. 인접 행렬을 사용하면 시간 복잡도는 O(n^2)이고, 인접 목록을 사용하면 시간 복잡도는 O(|V| |E|)입니다. BFS\DFS에는 공간 O(n)이 필요합니다. (시간 및 공간 복잡도는 BFS\DFS의 방법 선택과 관련이 없으며 주로 저장 방법에 따라 다릅니다.)

너비 우선 탐색 트리와 같은 계층적 순회 계층별로 액세스하므로 보조 대기열이 필요합니다. 부울 방문[MAV_VERTEX_NUM]; 무효 BFSTraverse(그래프 G){ for(int i=0;i<G.vexnum;i) 방문[i] = 거짓; 초기화큐(Q); for(int i=0;i<G.vexnum;i) if(!visited[i]) BFS(G,i); } 무효 BFS(그래프 G,int v){ 방문(v); 방문[v] = TRUE; 대기열에 넣기(Q,v); 동안(!isEmpty(Q)){ for(w=첫 번째 이웃(G,v);w>=0;w=다음 이웃(G,v,w)) if(!방문[w]){ 방문(w); 방문[w] = TRUE; 대기열에 넣기(Q,w); } } }

BFS는 단일 소스 최단 경로 문제를 해결합니다. void BFS_MIN_Distance(Graph G,int u){ for(i=0;i<G.vexnum;i) //d[i]는 u에서 i까지의 최단 경로를 나타냅니다. d[i]=무한대;//경로 길이 초기화 방문함[u]=TRUE; d[u]=0; 엔큐(Q,u); 동안(!isEmpty(Q)){ DeQueue(Q,u); for(w=FirstNeighbor(G,u);w>=0;w=다음N 이웃(G,u,w)) if(방문[w]){ 방문[w]=TRUE; d[w]=d[u] 1;//경로 길이 1 EnQueue(Q,w); } } }

너비 우선 스패닝 트리 인접 행렬은 고유하게 저장됩니다. 너비 우선 스패닝 트리는 고유합니다. 인접 목록 저장소는 고유하지 않습니다. 너비 우선 스패닝 트리가 고유하지 않습니다.

깊이 우선 탐색

트리의 선주문 순회와 유사 부울 방문[MAX_VERTEX_NUM]; 무효 DFStraverse(그래프 G){ for(v=0;v<G.vexnum;v) 방문[v] = 거짓; for(v=0,v<G.vexnum;v) if(!방문[v]) DFS(G,v); } 무효 DFS(그래프 G,int v){ 방문(v); 방문[v] = TRUE; for(w=첫 번째 이웃(G,v);w>=0;w=다음 이웃(G,v,w)) if(!방문[w]){ DFS(G,w); } }

깊이 우선의 나무와 숲 연결된 그래프는 깊은 스패닝 트리를 생성할 수 있고, 연결되지 않은 그래프는 포리스트를 생성할 수 있습니다.

그래프 연결성

그래프 순회 알고리즘을 사용하여 그래프의 연결성을 결정할 수 있습니다. 방향이 지정되지 않은 그래프가 연결된 경우 모든 정점에서 시작하여 단 한 번의 순회를 통해 그래프의 모든 정점에 액세스할 수 있습니다. 유향 그래프가 연결되어 있고 초기점에서 그래프의 모든 꼭지점까지 경로가 있으면 그래프의 모든 꼭지점에 접근할 수 있습니다.

다이어그램의 응용

최소 스패닝 트리 가장자리가 잘리면 스패닝 트리는 연결이 끊긴 그래프가 됩니다. 가장자리가 추가되면 경로를 따라 루프가 형성됩니다. 최소 스패닝 트리는 스패닝 트리 집합에서 간선 가중치의 합이 가장 작은 스패닝 트리여야 합니다. 각 간선의 가중치가 다른 경우 최소 스패닝 트리는 일반적으로 고유하지만 최소 스패닝 트리는 반드시 고유하지는 않습니다. 최소 스패닝 트리의 가장자리 가중치의 합은 항상 고유하고 최소입니다. GENERIC_MST(G){ T=NULL; T는 스패닝 트리를 형성하지 않습니다. 최소 비용 가장자리(u, v)를 찾으면 T를 추가한 후에 루프가 생성되지 않습니다. T=T∪(u,v); }

프림 알고리즘(BFS) Dijkstra와 유사하게 처음에는 그래프에서 정점을 선택하여 트리 T에 추가한 다음 T의 현재 정점 집합에 가장 가까운 정점을 선택하고 T의 정점 수만큼 정점과 가장자리를 트리에 추가합니다. 각 작업 후 그래프의 모든 정점이 트리 T에 추가될 때까지 간선 수가 1씩 증가합니다. T는 최소 스패닝 트리입니다. T에는 n-1개의 간선이 있어야 합니다. voidPrim(G,T){ T=빈 세트; U={W}; while((V-U)!=empty set){//트리에 모든 정점이 포함되어 있지 않은 경우 (u, v)를 u∈U 및 v∈(V-U)로 만들고 가장 작은 가중치를 갖는 간선으로 설정합니다. T=T∪{(u,v)};//가장자리는 트리로 분류됩니다. U=U∪{v};//정점은 트리로 분류됩니다. } } Prim 알고리즘의 시간 복잡도는 O(|V^2|)이고 |E|에 의존하지 않으므로 조밀한 간선을 갖는 그래프의 최소 신장 트리를 푸는 데 적합합니다.

크루스칼 알고리즘 정점에서 확장하여 최소 신장 트리를 생성하는 Prim의 알고리즘과 달리 Kruskal의 알고리즘은 가중치가 증가하는 순서로 적절한 모서리를 선택하여 최소 신장 트리를 구성합니다. 처음에는 각 정점이 연결된 구성 요소를 형성한 다음 가장자리 가중치가 작은 것부터 큰 순서로 가장자리에 연결된 정점이 다른 연결에 속하면 아직 선택되지 않은 가중치가 가장 작은 가장자리를 계속 선택합니다. T 구성 요소의 구성 요소인 경우 이 가장자리를 T에 추가하고, 그렇지 않으면 T의 모든 정점이 연결된 구성 요소에 있을 때까지 이 가장자리를 삭제합니다. 무효 크루스칼(V,T){ T=V; //T를 초기화하고 정점만 numS=n;//연결된 구성 요소의 수 while(numS>1){//연결된 컴포넌트의 개수가 1보다 큰 경우 E에서 가중치가 가장 작은 간선(v,u)을 가져옵니다. if (v와 u는 T의 서로 다른 연결 구성요소에 속함) T=T∪{(v,u)}; numS--; } } } Kruskal의 알고리즘은 힙을 사용하여 모서리 세트를 저장하므로 매번 새 모서리를 추가할 때마다 가장 작은 가중치를 갖는 모서리를 선택하는 데 O(log|E|) 시간만 소요됩니다. T를 설명하기 위한 데이터 구조, 시간 복잡도는 O(|E|log|E|)이므로 Kruskal은 희소한 간선과 많은 정점을 갖는 그래프에 적합합니다.

최단 경로 최단 경로를 해결하기 위한 이전 그림의 BFS 순회는 비가중 그래프에 대한 것입니다. 여기서는 최단 가중치 경로 길이를 갖는 최단 경로에 대해 설명합니다. 최단 경로를 해결하기 위한 알고리즘은 모두 속성에 의존합니다. 두 점 사이의 최단 경로에는 경로의 다른 정점 사이의 최단 경로도 포함됩니다.

다익스트라 알고리즘(BFS) 단일 소스 최단 경로; Dijkstra의 알고리즘은 획득한 최단 경로의 정점을 기록하기 위해 집합 S를 설정합니다. 처음에는 소스 포인트 v0가 S에 배치됩니다. 새 정점 vi가 세트 S에 통합될 때마다 소스 포인트 v0가 수정되어야 합니다. 설정된 V-S의 가장 짧은 정점에 대한 음의 가중치 값은 허용되지 않습니다. 두 개의 보조 어레이를 설정하십시오. dist[]: 소스 지점 v0에서 다른 정점까지의 현재 최단 경로 길이를 기록합니다. 초기 상태: v0에서 vi까지 호가 있으면 dist[i]는 호의 가중치입니다. 그렇지 않으면 dist[i를 설정합니다. ]~무한대. (dist[]는 한 번에 한 단계만 뒤로 이동합니다 - BFS 아이디어) path[]: path[i]는 소스점에서 정점 i까지의 최단 경로의 선행 노드를 나타냅니다. 알고리즘이 끝나면 소스 포인트 v0에서 정점 vi까지의 최단 경로를 추적할 수 있습니다. 수동으로 해결할 때 가장 중요한 것은 집합 S를 선택할 때마다 정점을 추가하고 각 점의 경로 거리를 업데이트한 후 집합의 마지막 정점부터 다음 단계를 수행하는 것입니다. 에스. 시간 복잡도 O(|V|^2)

플로이드 알고리즘 각 정점 쌍 사이의 최단 경로 재귀는 n차 정사각 행렬 시퀀스를 생성합니다. A^-1,A^0,..A^N; 여기서 A^k[i][j]는 정점 i에서 j까지의 길이를 나타내고 k번째 정점이 사용됩니다. 중간 꼭지점을 완화하면서 시간 복잡도는 O(|V|^3)입니다(각 정점 O(|V^2|)*|V|에 대해 Dijkstra 알고리즘을 한 번 실행하는 것과 동일). 음수 가중치가 있는 간선은 허용되지 않으며 유향 그래프\무향 그래프(양측이 동일한 유향 그래프로 변환됨)에 작용할 수 있습니다.

방향성 비순환 그래프 설명 표현 DAG(Directed acycle graph): 방향성 그래프에는 순환이 없습니다. 공통 하위 표현식이 포함된 표현식을 설명하는 데 효과적인 도구입니다. 예를 들어, 중위 표현식의 문자열은 이진 트리(루트 노드는 연산자를 저장하고 하위 트리는 피연산자를 저장함)로 표현될 수 있습니다. 방향성 비순환 그래프를 사용하면 동일한 하위 표현식이 공유될 수 있습니다.

토폴로지 순서 방향성 비순환 그래프의 꼭지점들로 구성된 시퀀스로, 각 꼭지점은 한 번만 나타나며, 시퀀스에서 꼭지점 A가 꼭지점 B보다 앞에 위치하면 그래프에서 B에서 A로 가는 경로가 없습니다. 이는 다음과 같이 이해될 수도 있습니다: 위상수열은 방향성 비순환 그래프의 정점 순서입니다. 각 AOV 네트에는 위상적으로 정렬된 하나 이상의 시퀀스가 있습니다.

AOV 네트워크(정점 네트워크에서의 활동) DAG가 프로젝트를 나타내는 데 사용되고 정점은 활동을 나타내고 방향성 에지 <Vi, Vj>는 Vi가 Vj보다 선행해야 하는 관계를 나타내는 경우 이러한 종류의 그래프를 활동을 나타내는 정점이 있는 네트워크라고 합니다. AOV 네트워크의 위상 정렬을 위한 많은 알고리즘이 있으며 일반적으로 사용되는 알고리즘 중 하나는 다음과 같습니다. 1. AOV 네트워크에서 선행 정점이 없는 정점을 선택하여 출력 2. 네트워크에서 정점과 정점에서 시작하는 모든 방향 가장자리를 삭제합니다. 3. AOV 네트워크가 비어 있거나 현재 네트워크에 선행자가 없는 정점이 없을 때까지(그래프에 사이클이 있어야 함을 나타냄) 1.2단계를 반복합니다. 각 정점을 출력하려면 시작 가장자리를 삭제해야 하므로 위상 정렬의 시간 복잡도는 O(|V| |E|)입니다. 또한 DFS를 사용하여 토폴로지 정렬을 구현할 수도 있습니다. (in-degree가 0이고 out-degree가 0이 아닌 꼭지점부터 하나씩 시작하여 스트로크가 완료될 때까지 역추적이 발생하는 한 실패합니다.) ) 역위상 정렬 외차가 0인 꼭지점에서 시작 AOV 네트워크는 인접 행렬 저장소를 사용합니다. 삼각 행렬인 경우 위상 순서가 있어야 하며 그 반대의 경우도 마찬가지입니다.

bool TopologicalSort(그래프 G){ 초기화스택(S); for(int i=0;i<G.vexnum;i) if(정도[i]==0) Push(S,i);//차수가 0인 모든 정점을 스택에 밀어 넣습니다. 정수 개수=0; 동안(!isEmpty(S)){ 팝(S,i); print[count]=i;//정점 출력 for(p=G.vertices[i].firstarc;p;p=p->nextarc){ //i가 가리키는 모든 정점의 진입차수를 1만큼 감소시키고, 진입차수가 0으로 감소된 정점을 스택에 푸시합니다. v = p->부형; if(!(--indegree[v])) 푸시(S,v); } if(개수<G.vexnum) 거짓을 반환; 또 다른 사실을 반환; }

중요 경로

AOE 네트워크(에지 네트워크에서의 활동) 이벤트는 꼭짓점으로 표시되고, 활동은 방향이 지정된 가장자리로 표시되며, 활동 완료 비용은 가장자리의 가중치(예: 활동을 완료하는 데 필요한 시간)로 표시됩니다. AOE 네트워크의 두 가지 속성: 1. 꼭지점으로 표현되는 이벤트가 발생한 후에야 꼭지점에서 시작하여 방향성 에지로 표현되는 활동이 시작될 수 있습니다. 2. 꼭지점의 이벤트는 꼭지점의 들어오는 가장자리로 표시되는 활동이 완료된 후에만 발생할 수 있습니다. AOE 네트워크에는 전체 프로젝트의 시작을 나타내는 시작 정점(소스 포인트)이라고 하는 진입 차수가 0인 정점이 하나만 있습니다. AOE 네트워크에도 진출 차수가 0인 정점이 하나만 있습니다. , 끝 정점(싱크)이라고 하며 전체 프로젝트의 끝을 나타냅니다. AOE 네트워크의 일부 활동은 병렬로 수행될 수 있지만 모든 경로의 모든 활동은 완료될 때까지 종료될 수 없습니다. 따라서 소스에서 싱크까지의 모든 경로 중에서 경로 길이가 가장 긴 경로를 임계 경로라고 합니다. 경로에 있는 활동을 중요 활동이라고 합니다(중요 활동을 찾는 것은 중요 경로를 찾는 것과 같습니다). 전체 프로젝트를 완료하는 데 걸리는 최단 시간은 주 경로의 길이입니다.

주요 활동 찾기 1. 사건이 가장 먼저 발생한 시간 vk ve(k) 소스 포인트 v1에서 정점 vk까지의 가장 긴 경로 길이를 의미합니다. 이벤트 vk의 가장 빠른 발생 시간은 vk에서 시작하는 모든 활동이 시작될 수 있는 가장 빠른 시간입니다. vk를 vj의 후계자로 두세요. if(ve[j] Weight(vj,vk) > ve(k)) then ve[k]=ve[j] Weight(vj,vk) "장력 동작" ve() 값을 계산할 때는 앞에서 뒤로 순서대로 진행하며, 위상 정렬(topological sorting)을 기반으로 계산할 수 있다. 2. 이벤트 vk의 최근 발생 시간 vl(k) 전체 프로젝트의 완료를 지연시키지 않고 k가 발생할 수 있는 가장 늦은 시간 vl(k)를 나타냅니다. vl() 값을 계산할 때는 뒤에서 앞으로 진행하며, 역위상수열을 기반으로 계산할 수 있다. 3. 활동 ai의 가장 빠른 시작 시간 e(i) 4. 활동 ai의 가장 늦은 시작 시간은 l(i)입니다. 5. 활동 ai의 가장 늦은 시작 시간 l(i)와 가장 빠른 시작 시간 e(i) d(i)=l(i)-e(i)의 차이 활동 완료 시간에 대한 시간 여유를 말하며, 직설적으로 말하면 AI가 얼마나 지연할 수 있는지를 의미한다. d(i)=0이면 i가 핵심 활동입니다. 네트워크의 핵심 경로는 고유하지 않으며, 여러 핵심 경로가 있는 네트워크의 경우 하나의 핵심 경로에서 주요 활동의 속도를 높이는 것은 전체 프로젝트 기간을 단축할 수 없습니다. 이는 모든 핵심 경로에 포함된 핵심 상호 작용을 가속화해야만 달성할 수 있습니다. 공사기간 단축을 목적으로 합니다.

해의 이해 vl(k): ve(k)는 소스점에서 싱크점으로의 가장 부지런한 이동이고, vl(k)는 싱크점에서 소스점으로의 이동이며, 싱크점에 가장 가까운 이동입니다. 싱크 포인트가 선택되었습니다. (역시 그냥 직진하세요. 가장 게으른 방법입니다. 가능하면 드래그하세요.)

7찾기

검색의 기본 개념

검색: 데이터 세트에서 특정 조건을 만족하는 데이터 요소를 찾는 프로세스 조회 테이블(조회 구조): 조회에 사용되는 데이터 모음입니다. 조회 테이블에는 일반적으로 사용되는 네 가지 작업이 있습니다. 1. 특정 데이터 요소가 조회 테이블에 있는지 쿼리 2. 조건을 충족하는 특정 데이터 요소 검색 3. 조회 테이블에 데이터 요소를 삽입합니다. 4. 조회 테이블에서 데이터 요소 삭제 정적 조회 테이블: 위의 한 단계와 두 단계만 포함하는 조회 테이블로, 조회 테이블을 동적으로 수정할 필요가 없습니다(순차 조회, 절반 조회, 해시 조회 등). 동적 조회 테이블(이진 정렬 트리 조회, 해시 조회 등) , 등.) 키워드: 요소를 고유하게 식별하는 데이터 요소의 데이터 항목 값 평균 검색 길이: 검색 과정에서 비교해야 하는 키워드 수를 의미합니다. 평균 검색 길이는 모든 검색 과정에서 키워드를 비교한 평균 횟수입니다.

성공과 실패를 탐색할 때 ASL을 연습하세요

순차 검색과 이진 검색

순차 검색 선형 검색이라고도 하며 순차 목록과 연결 목록 모두에 적합합니다. 장점: 데이터 요소 저장 및 정렬에 대한 요구 사항이 없습니다. 단점: n이 크면 효율성이 낮습니다.

일반 선형 테이블의 순차 검색 typedef struct{//룩업 테이블의 데이터 구조 ElemType *elem; //요소 저장 공간 기본 주소 int TableLen;//테이블의 길이 }SS테이블; int Search_Seq(SSTable ST,ElemType 키){ ST.elem[0] = 키;//센티널 for(i=ST.TableLen;ST.elem[i]!=key;--i);//뒤에서 앞으로 봅니다. 내가 반환; } 위 알고리즘에서 ST.elem[0]은 센티넬이라고 불리며, Search_Seq의 내부 루프는 배열이 경계를 벗어날지 여부를 판단할 필요가 없습니다. 만족하는. 센티널을 도입하면 불필요한 판단 진술을 많이 피할 수 있어 프로그램 효율성이 향상됩니다.

정렬된 목록에서 순차적 검색 테이블의 키워드가 순서대로 검색되기 전에 알려진 경우 비교가 실패한 후 검색 실패를 반환하기 위해 테이블의 다른 쪽 끝과 비교할 필요가 없으므로 평균 검색 길이가 줄어 듭니다. 검색 실패. 의사결정 트리는 정렬된 선형 목록의 검색 프로세스를 설명하는 데 사용할 수 있습니다. 원형 노드는 정렬된 선형 목록에 존재하는 요소를 나타냅니다. n개의 노드가 있는 경우 직사각형 노드는 실패 노드입니다. , 그에 따라 검색이 실패한 노드가 n개 있습니다. 실패한 검색의 평균 검색 길이(ASL)는 (1 2 .. n n)/(n 1)입니다. 각 '실패한 노드'를 찾을 확률은 1/n 1입니다.

무질서한 순차탐색과 순서화된 순차탐색의 차이는 탐색이 실패했을 때의 차이일 뿐입니다.

ASL 성공=(n 1)/2

절반 검색(이진 검색) 순차적 저장 구조에만 적합하고 체인 저장 구조에는 적합하지 않으며, 요소를 키워드별로 순서대로 배열해야 합니다. 시간은 O(log2n)입니다.

int Binary_Search(SeqList L,ElemType 키){ int low=0,high=L.TableLen-1,mid; 동안(낮음<=높음){ 중간 = (낮음 높음)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]<키){ 낮음 = 중간 1; // 중간 = (낮음 높음)/2; } 또 다른{ 높음 = 중간-1; // 중간 = (낮음 높음)/2; } } -1을 반환합니다. }

블록 검색(인덱스 순서 검색) 순차 검색과 이진 검색의 장점을 모두 흡수한 동적 구조로 빠른 검색에 적합합니다. 블록 검색의 기본 아이디어는 룩업 테이블을 여러 개의 하위 블록으로 나누는 것입니다. 블록 내의 요소는 순서가 지정되지 않을 수 있지만 블록은 순서가 지정됩니다(첫 번째 그룹의 가장 큰 키워드는 두 번째 블록의 모든 키워드보다 작습니다). 그런 다음 테이블의 각 요소를 인덱싱하는 인덱스 테이블을 만듭니다. 각 블록의 최대 키와 각 블록의 첫 번째 요소 주소를 포함하며 인덱스 테이블은 키별로 정렬됩니다. 블록 검색 과정은 다음과 같습니다. 1. 인덱스 테이블에서 검색할 레코드가 위치한 블록을 결정합니다(순차 또는 반 검색). 2. 블록 내에서 순차 검색 차단된 검색 평균 검색 길이: 인덱스 검색과 블록 내 검색의 평균 길이의 합

B-트리와 B-트리

B-트리(다중 균형 검색 트리)(BST 개선 버전) B-트리에 있는 모든 노드의 최대 자식 수를 B-트리의 순서라고 하며 일반적으로 m으로 표시합니다. m차 B-트리는 빈 트리이거나 다음 특성을 만족합니다. 1. 트리의 각 노드에는 최대 m개의 하위 트리가 있습니다. 즉, 최대 m-1개의 키워드를 포함합니다. 2. 루트 노드가 터미널 노드가 아닌 경우 하위 트리가 2개 이상 존재 3. 루트 노드를 제외한 모든 비리프 노드에는 최소 m/2개의 상한 하위 트리가 있습니다. 즉, 최소 m/2개의 상한-1 키워드를 포함합니다. 4. 리프가 아닌 모든 노드의 구조는 다음과 같습니다 (n, P0, K1, P1, K2, P2,..., Kn, Pn) Ki는 키워드이고 K1<K2<..<Kn을 만족합니다. Pi는 하위 트리의 루트 노드에 대한 포인터입니다. Pi 포인터가 가리키는 하위 트리의 모든 노드는 Ki보다 크고 1보다 작습니다. 노드 수의 키워드입니다. 5. 모든 리프 노드는 동일한 수준에 나타나며 실제로는 존재하지 않습니다. 이 노드에 대한 포인터는 비어 있습니다.

B 트리 높이 B-트리의 대부분 작업에 필요한 디스크 액세스 횟수는 B-트리의 높이에 비례합니다. 트리의 각 노드는 최대 m개의 하위 트리와 m-1개의 키워드를 가지며, 키워드 수는 n≤m^h-1을 충족해야 합니다. h1번째 레이어에는 최소 2(m/2 상한)^(h-1)개의 노드가 있고, h1번째 레이어는 어떠한 정보도 포함하지 않는 리프 노드입니다. n개의 키워드가 있는 B-트리의 경우 리프 노드 검색이 실패한 노드는 n 1이므로 n 1>=2(m/2가 상한을 취함)^(h-1), 즉 h≤log( M/2는 상한)((n 1)/2 1)을 취합니다.

B-트리 검색 1. B-트리에서 노드 찾기 2. 노드 내에서 키워드 찾기 1.의 검색 동작은 디스크에서 수행되고, 2.의 검색 동작은 메모리에서 수행된다. 대상 노드를 찾은 후 메모리에 읽어들인 후 노드 내에서 순차 탐색 방식이나 이진 탐색 방식을 사용한다.

B-트리에 삽입 위치를 찾을 수 없는 상태에서 직접 삽입하면 B-트리 정의의 요구 사항이 파괴됩니다. 1. 위치 지정: 가장 낮은 레이어에서 리프가 아닌 노드를 찾습니다(리프 노드를 찾고, 이전 레이어의 리프가 아닌 노드를 가져옴). 2. 삽입: 실패하지 않은 각 노드의 키워드 수는 [m/2가 상한 -1, m-1을 취함] 간격 내에 있으며 직접 삽입할 수 있습니다. 삽입된 노드 키워드의 개수가 m-1보다 크면 노드가 분할됩니다. 분할 방법: 중간 위치 m/2에서 상한을 취하고 키워드를 두 부분으로 나눕니다. 왼쪽 부분은 원래 노드에 포함되고 오른쪽 부분은 중간 위치의 매듭에 배치됩니다. m/2는 상한을 취하여 원래 노드의 상위 노드를 삽입합니다.

B-트리 삭제 삭제된 키워드 k가 단말 노드(최하위 비리프 노드)에 없을 때, k는 k의 선행자(후속자) k'로 대체될 수 있으며, 이후 해당 노드에서 k'가 삭제되어 키워드로 변환되는 상황 터미널 노드에서; 삭제된 키워드가 터미널 노드(리프가 아닌 가장 낮은 노드)에 있는 경우 세 가지 상황이 있습니다. 1. 키워드 직접 삭제: 키워드 수 ≥ m/2는 상한 -1을 취합니다. 2. 형제이면 충분합니다. 키워드 수 = m/2, 상한 -1을 취하고 왼쪽 및 오른쪽(인접) 형제 키워드의 수가 m/2보다 크거나 같고 상한을 취합니다. 그런 다음 형제, 부모 및 자신이 아버지-아들 전치 방법을 사용하여 균형을 이룹니다. 3. 형제 수가 충분하지 않습니다. 삭제된 키워드 수 = m/2이고 상한은 -1입니다. 이때 왼쪽 및 오른쪽(인접) 형제의 노드도 = m/2이며 상한입니다. 는 1입니다. 그러면 키워드는 삭제된 후 왼쪽(오른쪽) 형제 노드와 상위 노드의 키워드와 병합됩니다. 상위 노드의 키워드 수는 1만큼 감소합니다. 루트 노드는 직접 0으로 줄어들 수 있습니다(루트 노드 삭제). 새 노드를 루트라고 합니다.

B-트리 관련 속성 키워드 수와 하위 트리 수의 관계를 파악해야 합니다. 즉, 키워드 수는 하위 트리 수보다 1개 적습니다. 루트 노드를 제외한 모든 비종단 노드에는 최소 m/2개의 상한 하위 트리가 있습니다(m/2 상한 - 1개의 키워드). 노드의 키워드는 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다. 즉, m/2는 -1≤n≤m-1의 상한을 취합니다. 즉, [m/2는 -1, m-1의 상한을 취합니다.]

B-트리

B-트리는 데이터베이스의 요구에 따라 나타나는 변형된 B-트리 트리입니다. m차 B-트리는 다음 조건을 충족합니다. 1. 각 가지 노드에는 최대 m개의 하위 트리가 있습니다. 2. 리프가 아닌 루트 노드에는 최소한 두 개의 하위 트리가 있습니다. 3. 노드의 하위 트리 수는 키워드 수와 같습니다. 4. 모든 리프 노드에는 모든 키워드와 해당 레코드에 대한 포인터가 포함됩니다. 키워드는 리프 노드에 크기 순서로 정렬되며 인접한 리프 노드는 크기 순서로 서로 연결됩니다.

B-트리와의 주요 차이점: 1. B 트리에서 n개의 키워드가 있는 노드에는 n개의 하위 트리가 있고 각 키워드는 하위 트리에 해당합니다. B 트리의 n개의 키워드 노드에는 n-1개의 하위 트리가 포함됩니다. 2. B 트리의 각 노드에 대한 키워드 수 n의 범위는 [m/2가 상한, m을 취함](B 트리의 노드 키워드 수 n의 상한과 하한에 1을 더한 값에 상대적)입니다. ); 루트 노드 B: [1,m],B:[1,m-1] 3. 트리 B에서 리프 노드에는 정보(모든 키워드)가 포함되고, 리프가 아닌 노드는 인덱스 역할만 합니다. 4. B-트리의 모든 검색은 성공 여부에 관계없이 루트 노드에서 리프 노드까지의 경로입니다.

해시 테이블

해시 테이블의 기본 개념

기존의 선형 테이블 및 트리 검색으로 인해 테이블 내 레코드의 위치와 레코드의 키 사이에는 명확한 관계가 없습니다. 따라서 이러한 테이블의 레코드를 검색할 때는 일련의 키워드를 비교해야 합니다. 이 검색 방법은 비교를 기반으로 하며 비교 횟수에 따라 검색 효율성이 달라집니다. 해시 함수: 조회 테이블의 키워드를 해당 키워드에 해당하는 주소로 매핑하는, 즉 키워드 자체의 특성을 이용하고 "비교" 검색을 최대한 적게 사용하는 Hash(key)=Addr 함수입니다. 해시 함수는 여러 개의 서로 다른 키워드를 동일한 주소에 매핑할 수 있으며, 이를 '충돌'이라고 합니다. 충돌하는 서로 다른 키워드를 동의어라고 합니다. 한편으로, 잘 설계된 해시 함수는 충돌을 최소화하는 반면, 충돌은 불가피하며 이를 처리하는 방법을 설계해야 합니다. 해시 테이블(Hash Table): 키워드를 기반으로 직접 접근하는 데이터 구조, 즉 해시 테이블은 키워드와 저장 주소 간의 직접적인 매핑 관계를 구축한다. 이상적으로 해시 테이블 검색의 시간 복잡도는 O(1)입니다. 이는 요소 수와 관련이 없음을 의미합니다.

해시 함수를 구성하는 방법

1. 해시 함수의 정의 도메인은 모든 저장 키를 포함해야 하며 값 범위는 해시 테이블의 크기 또는 주소 범위에 따라 다릅니다. 2. 해시 함수로 계산된 주소는 전체 주소 공간에 동일한 확률로 고르게 분포되어 충돌 발생을 줄여야 합니다. 3. 해시 함수는 최대한 단순해야 하며, 어떤 키워드에 해당하는 해시를 짧은 시간 내에 계산할 수 있어야 합니다.

1. 직접 어드레싱 방식 키워드의 선형 함수 값을 해시 주소로 직접 가져옵니다. H(키)=키 또는 H(키)=ax 키 b 이는 키워드 분포가 기본적으로 연속적인 상황과 일치하며, 키워드 분포가 불연속적이고 빈 공간이 많으면 저장 공간이 낭비됩니다.

갈등 처리 방법

해시 조회 및 성능 분석

8 정렬

정렬의 기본 개념

알고리즘의 안정성: 정렬할 목록에는 Ri와 Rj라는 두 개의 요소가 있으며 해당 키워드는 동일한 keyi=keyj입니다. 특정 정렬 알고리즘을 사용한 후에도 Ri와 Rj의 상대 위치가 변경되지 않으면 정렬이 수행됩니다. 알고리즘은 안정적이지만 그렇지 않으면 그렇지 않습니다. 안정성은 알고리즘의 품질을 반영하지 않고 알고리즘의 특성만을 설명합니다. 정렬 알고리즘은 정렬 프로세스 중에 데이터 요소가 완전히 메모리에 있는지 여부에 따라 두 가지 범주로 나눌 수 있습니다. 1. 내부 정렬: 정렬하는 동안 모든 요소는 정렬을 위해 메모리에 저장됩니다. 2. 외부 정렬: 정렬 중에는 모든 요소를 동시에 메모리에 저장할 수 없으며 정렬 프로세스 중 요구 사항에 따라 내부 메모리와 외부 메모리 사이를 지속적으로 이동해야 합니다. 일반적으로 내부 정렬에는 비교와 이동이 필요하지만 모든 내부 정렬에 기수 정렬과 같은 비교가 필요한 것은 아닙니다.

삽입 정렬 정렬할 레코드가 키워드의 크기에 따라 이전에 녹음된 하위 시퀀스에 삽입될 때마다.

직접 삽입 정렬

순서가 있는 시퀀스 L[1..i-1]L(i) 순서가 없는 시퀀스 L[i 1…n] void InsertSort(ELemType A[],int n){ int i,j; for(i=2;i<=n;i){//앞에 다음 n-1개 숫자를 삽입합니다. if(A[i]<A[i-1]){ A[0] = A[i];//센티널로 복사, A[0]에는 어떤 요소도 저장되지 않습니다. for(j=i-1;A[0]<A[j];j--){//뒤에서 앞으로 삽입 위치 찾기 A[j 1] = A[j]; A[j 1] = A[0]; } } 공간 복잡도 O(1), 공간 복잡도 O(n^2) 최선의 경우: 테이블의 요소가 이미 정렬되어 있으며 시간은 O(n)입니다. 최악의 경우: 테이블의 요소 순서가 반대입니다. 시간은 O(n^2)입니다. 각각의 비교는 뒤에서 앞으로 하기 때문에 안정됩니다. 순차 목록 및 연결 목록에 적합합니다(지정된 요소 위치를 앞에서 뒤로 찾을 수 있음) 데이터 양이 적은 기본적으로 정렬된 정렬 테이블에 적합

반삽입 정렬

void InsertSort(ElemType A[],int n){ int i,j,낮음,높음,중간; for(i=2;i<=n;i ){ A[0] =A[i]; 낮음=1;높음=i-1; 동안(낮음<=높음){ 중간 = (낮음 높음)/2; if(A[mid]>A[0])high=mid-1; 그렇지 않으면 낮음=중간 1; } for(j=i-1;j>=높은 1;j--) A[j 1] = A[j]; A[높은 1]=A[0]; } } 시간 복잡도 O(n^2) 비교 횟수는 정렬할 목록의 초기 상태와 아무런 관련이 없으며 목록의 요소 수 n에만 의존합니다. 이동 횟수는 정렬할 목록의 초기 상태와 관련이 있습니다.

힐소트

먼저 정렬 테이블을 여러 하위 테이블로 나누고(동일한 증분을 갖는 레코드는 하위 테이블 di 1=di/2를 형성하고 마지막 증분은 1과 같음) 각 하위 테이블에 대해 직접 삽입 정렬을 수행합니다. 전체 테이블의 요소가 기본적으로 순서대로 정렬되어 있는 경우 모든 레코드에 대해 직접 삽입 정렬이 수행됩니다. void ShellSort(ELemType A[],int n){ //A[0]은 센티널이 아닌 임시 저장 단위입니다. j<=0이면 삽입 위치에 도달한 것입니다. for(dk=n/2;dk>=1;dk/=2)//단계 크기 변경 for(i=di 1;i<=n;i) if(A[i]<A[i-dk]){//A[i]를 순서가 지정된 증분 하위 테이블에 삽입해야 합니다. A[0]=A[j];//A[0]에 임시 저장됨 for(j=i-dk;j>0&&A[0]<A[j];j-=dk) A[jdk]=A[j]; } } 시간복잡도에 대해서는 명확한 결론은 없지만 O(n^2)로 추정됩니다. 정렬 불안정 시퀀스 테이블에 적합

교환 정렬 키워드 비교 결과에 따라 순서대로 두 레코드의 위치를 바꿉니다.

버블정렬

인접한 요소들의 값을 뒤에서 앞으로(앞에서 뒤로) 비교하고, 역순이면 교환한다. 키워드는 점차 거품처럼 표면으로 떠오릅니다. void BubbleSort(ELemType A[],int n){ for(int i=0;i<n-1;i){//n-1회 플래그 = 거짓; for(j=n-1;j>i;j--) if(A[j-1]>A[j]){//역순인 경우 swap(A[j-1],A[j]); 플래그 = 참; } if(flag==false)//버블 정렬 종료 플래그: 단일 교환이 아님 반품; } } 공간 O(1), 시간 O(n^2) 안정성: 요소가 동일하고 안정적이면 요소가 교환되지 않습니다. 버블 정렬로 생성된 시퀀스는 전역적으로 정렬되는데, 이는 삽입 정렬의 로컬 순서와 동일하지 않습니다.

빠른 정렬 분할 정복 사고를 바탕으로

목록에서 피벗(보통 첫 번째 요소)으로 정렬할 요소를 선택하고 정렬된 시퀀스를 두 개의 독립적인 부분으로 나눕니다. L[1..k-1] L(k) L[k 1, ...n] , 전반부가 피벗보다 작고 후반부가 피벗보다 크며 최종 위치 L(k)에 피벗이 위치하도록 하는 과정을 원패스 퀵 정렬(원패스 분할)이라고 합니다. void QuickSort(ELemType A[],int low,int high){ if(low<high){//재귀적 점프아웃 조건 int 피봇포스 = 파티션(A,low,high);//파티션 QuickSort(A,low,pivotpos-1); QuickSort(A,피벗 위치 1,높음); } } 빠른 정렬 알고리즘의 성능과 핵심은 분할 작업에서 비롯됩니다. 분할 작업에는 여러 버전이 있습니다. 여기서 첫 번째 요소는 분할을 위한 피벗 피벗으로 사용됩니다. int Partition(ElemType A[],int low,int high){ ElemType 피벗=A[낮음]; while(low<high){//루프 중단 조건 while(낮음<높음 && A[높음]>=피벗) --높음; A[낮음]=A[높음]; whilie(낮음<높음 && A[낮음]<=피벗) 낮음; A[높음] = A[낮음]; } A[낮음] = 피벗; 낮게 반환; } 공간: 재귀 작업 스택이 필요하며 바람직하게는 O(log2n), 평균 O(log2n)(완전한 이진 트리처럼 가능한 한 절반으로 분할), 최악의 경우 O(n) (두 개의 분할 영역의 요소 수는 n-1과 0, n-1 재귀 호출이 필요하며 스택 깊이는 O(n)). 시간: 빠른 정렬의 실행 시간은 나눗셈이 대칭인지 여부와 관련됩니다. 최악의 경우는 절반은 n-1이고 절반은 0입니다. 최대 비대칭성은 각 재귀 수준에서 발생하며 이는 초기 정렬 순서(순차 또는 역방향)에 해당합니다. 차수) 는 O(n^2)입니다. 안정성: 불안정합니다. 동일한 요소가 다른 부분으로 전송되고 상대적 위치가 변경됩니다. 참고: 빠른 정렬은 순서가 지정된 하위 시퀀스를 생성하지 않지만 피벗 요소는 각 패스의 최종 위치에 배치됩니다. 효율성 향상: 1. 시퀀스를 최대한 나눌 수 있는 피벗 요소를 선택합니다. 2. 피벗 요소를 무작위로 선택합니다. 가장 이상적인 나눗셈: 두 단어 문제 모두 n/2보다 작고, 시간은 O(nlog2n)이며, 퀵 정렬의 실행 시간은 평균적으로 최상의 경우에 매우 가깝습니다. Quicksort는 모든 내부 정렬 알고리즘 중에서 평균 성능이 가장 좋은 정렬 알고리즘입니다.

선택 정렬 각 패스는 n-1이 패스될 때까지 원래 시퀀스에 있는 키워드의 가장 작은 요소를 정렬된 하위 시퀀스의 i번째 요소로 선택합니다.

단순 선택 정렬

void SelectSort(ElemType A[],int n){ for(i=0;i<n-1;i)//총 n-1회 min=i;//최소 요소 위치 기록 for(j=i 1;j<n;j) if(A[j]<A[min]) min = j; if(min!=i) swap(A[i],A[min]); } } 공간 O(1), 시간 O(n^2) 안정성: 동일한 요소를 포함하는 키워드의 상대적 위치가 변경될 수 있어 불안정합니다.

힙 정렬

힙은 트리의 배열 객체입니다. 1차원 배열은 속성을 만족하는 완전한 이진 트리로 간주될 수 있습니다. 1.L(i)>=L(2i) 및 L(i)>=L(2i 1) 또는 2.L(i)<=L(2i) 및 L(i)<=L(2i 1) ( 1<=i<=n/2 (한계를 취함); 1.을 만족하는 것은 큰 루트 힙(큰 상위 힙)으로 간주되고, 2.를 만족하는 것은 작은 루트 힙(작은 상위 힙)으로 간주됩니다. 힙 정렬: 먼저 배열의 n개 요소가 초기 힙에 내장됩니다. 힙의 최상위 요소를 출력한 후 힙의 최하위 요소가 힙의 맨 위로 전송됩니다. 이때 루트 노드는 더 이상 전송되지 않습니다. 큰 루트 힙의 속성을 충족하며 힙이 파괴됩니다. 힙의 맨 위 요소가 힙의 맨 위로 이동하여 큰 맨 위 더미의 특성을 계속 유지할 수 있도록 조정합니다. 그런 다음 타워의 최상위 요소를 출력하고 힙에 요소가 하나만 남을 때까지 반복합니다. 힙 정렬 알고리즘: void HeapSort(ElemType A[],int len){ BuildMaxHeap(A,len); for(i=len;i>1;i--){ Swap(A[i],A[1]);//힙의 맨 위 요소를 출력하고 힙의 맨 아래 요소와 교환합니다. HeadAdjust(A,1,i-1);//나머지 i-1 요소를 더미로 배열합니다. } } 힙 정렬은 키워드가 많은(수억개 정도) 상황에 적합합니다. 예: 1억 개의 숫자 중에서 상위 100개의 최대값을 선택하려면 먼저 100개의 배열을 사용하고 처음 100개의 숫자를 읽고 작은 상위 힙을 구성한 다음 나머지 숫자가 다음보다 작으면 순서대로 읽습니다. 그렇지 않으면 힙 상단을 이 숫자로 바꾸고 힙 크기를 조정합니다. 데이터를 읽은 후 힙에 있는 100개의 숫자가 필수 숫자입니다. 공간 효율성 O(1), 시간 효율성 O(nlog2n) 불안정한

1. 정렬되지 않은 시퀀스를 초기 힙으로 구성하는 방법 (n/2 경계) 번째 노드를 루트로 하여 하위 트리를 필터링합니다. (큰 루트 힙인 경우 루트 노드 키워드와 왼쪽 및 오른쪽 하위 트리 키워드의 크기를 비교하여 만족하지 않으면 교환합니다. 큰 루트 힙 규칙), 이 하위 트리를 힙으로 만듭니다. 그런 다음 각 노드(n/2에서 경계 -1,1을 뺀 값)에 루트가 있는 하위 트리가 앞으로 스크리닝됩니다. 완전한 이진 트리로 볼 때 루트 노드는 아래에서 위로 점진적으로 조정됩니다(루트 노드와 하위 노드 간에 키가 교환됨). 배열에서 루트 노드는 오른쪽에서 왼쪽으로 조정됩니다(키워드가 교환됨). void BuildMaxHeap(ElemType A[],int len){ for(int i=len/2;i>0;i--)//i=n/2부터 1까지 힙을 반복적으로 조정합니다. HeadAdjust(A,i,len); } void HeadAdjust(ElemType A[],int k,int len){ //HeadAdjust는 k 요소를 루트로 하여 하위 트리를 조정합니다. A[0]=A[k]; for(i=2*k;i<=len;i*=2){//더 큰 키를 사용하여 하위 노드를 따라 아래로 필터링합니다. if(i<len && A[i]<A[i 1]) i ;//더 큰 키를 가진 하위 노드의 첨자를 가져옵니다. if(A[0]>=A[i]) break;//필터링 끝 또 다른{ A[k] = A[i];//A[i]를 상위 노드로 조정 k=i;//아래로 계속 필터링하려면 k 값을 수정하세요. } } A[k]=A[0]; } 조정 시간은 트리 높이 O(h)와 관련이 있으며 시간 복잡도는 O(n)입니다. 정렬되지 않은 숫자는 선형 시간에 힙에 구축될 수 있습니다.

2. 힙의 최상위 요소를 출력한 후 나머지 요소를 새 힙으로 조정하는 방법은 무엇입니까? 힙의 최상위 요소가 출력된 후 힙의 마지막 요소가 힙의 최상위 요소와 교환됩니다. 이때 힙의 속성은 파괴되므로 하향 필터링이 필요합니다. 위에서 아래로 필터링(루트 노드 키워드와 하위 트리 키워드 교환)

힙 삽입 꼬리를 삽입하고 아래에서 위로 조정하십시오.

병합 정렬과 기수 정렬

병합 정렬 병합의 의미는 두 개 이상의 순서 목록을 새로운 순서 목록으로 결합하는 것입니다.

정렬할 테이블에 n개의 레코드가 포함되어 있다고 가정하면 각각 길이가 1인 n개의 정렬된 하위 테이블로 간주한 다음 쌍으로 병합하여 길이가 2 또는 1인 n/2개의 상한 레코드를 얻을 수 있습니다. 시퀀스 목록; 길이가 n인 정렬된 목록으로 병합될 때까지 2개씩 계속 병합합니다. 이 방법을 양방향 병합 정렬이라고 합니다. ElemType *B=(ElemType*)malloc((n 1)*sizeof(ElemType));//보조 배열 B void Merge(ElemType A[],int low,int mid,int high){ //테이블 A[low..mid]A[mid 1..high]는 각각 순서가 지정되어 순서가 지정된 목록으로 병합됩니다. for(int k=낮음;k<=높음;k) B[k]=A[k]; for(i=low;j=mid 1;k=i,i<=mid&&j<=high;k ){ if(B[i]<=B[j]) A[k]=B[i ]; 그렇지 않으면 A[k]=B[j]; } while(i<=mid) A[k ]=B[i ]; while(j<=high) A[k ]=B[j ]; } void MergeSort(ELemType A[],int low,int high){ if(낮음<높음){ int mid=(낮음 높음)/2; MergeSort(A,낮음,중간); MergeSort(A,mid 1,high); Merge(A,낮음,중간,높음); } } 공간 효율성: n 단위의 보조 공간, 공간 복잡도 O(n) 시간 효율성: 각 병합은 O(n)이고, log2n 상한 병합이 필요합니다. 알고리즘 시간 복잡도는 O(nlog2n)입니다. 안정성: Merge() 작업은 동일한 키워드를 사용하는 레코드의 상대적 순서를 변경하지 않습니다.

일반적으로 N개의 요소를 k-way 병합하는 경우 정렬 횟수 m은 k^m=N을 만족하므로 m=logkN이고, m은 정수이므로 m=logkN이 상한을 취합니다.

기수 정렬 다중 키워드 정렬 아이디어를 활용하여 단일 논리적 키워드 정렬

키워드 크기를 기준으로 정렬합니다. 각 노드 aj의 키워드는 d개의 튜플로 구성되며, kd-1j는 기본 키워드, kj0은 보조 키워드입니다. 다중 키워드 정렬을 수행하려면 일반적으로 두 가지 방법이 있습니다. 1. MSD(Most Significant Bit First), 키워드의 가중치 감소에 따라 여러 개의 작은 하위 시퀀스를 계층별로 나누고 마지막으로 모든 하위 시퀀스를 순서 있는 시퀀스로 연결합니다. 2. 가장 낮은 숫자부터(LSD), 키워드 가중치에 따라 오름차순으로 정렬되어 정렬된 순서를 형성합니다. 작동하다: 1. 배포: Q0...Qr-1 큐를 비운 다음 각 노드의 해당 비트에 따라 해당 큐에 추가합니다. 2. 수집: Q0..Qr-1의 큐 노드를 끝에서 끝까지 연결하여 새 노드 시퀀스를 얻어 새 선형 테이블을 형성합니다. 예: 1000 미만의 시퀀스를 정렬하려면 먼저 기본 r을 결정합니다(r 기본으로 간주할 수 있음). 1000의 기본은 10이므로 정렬 프로세스 중에 10개의 체인 큐가 필요합니다. 1000 이하의 숫자는 세 자리이므로 세 번의 "분배" 및 "수집" 작업이 필요합니다. 동일한 최하위 키워드(단위 자리)를 가진 모든 레코드가 대기열에 할당된 후 "수집" 작업이 수행됩니다. 공간 효율성: 한 번의 정렬 여행에 필요한 보조 저장 공간은 r(r개 대기열: r개 대기열 헤드 포인터, r개 대기열 꼬리 포인터), O(r)입니다. 시간 효율성: d 패스의 할당 및 수집, 한 패스의 할당에는 O(n)이 필요하고, 한 패스의 컬렉션에는 O(r)이 필요하며, 시간 복잡도는 시퀀스의 초기 상태에 관계없이 O(d(n r))입니다. . 안정성: 기수 정렬 자체에서는 비트별 정렬이 안정적이어야 하므로 안정적입니다!

다양한 내부 정렬 알고리즘 비교 및 적용

내부 정렬 알고리즘 비교

내부 정렬 알고리즘 적용

1. n이 작은 경우에는 직접 삽입 정렬이나 단순 선택 정렬을 사용할 수 있습니다. 직접 삽입 정렬은 단순 선택 정렬보다 더 많은 레코드 이동이 필요하므로 레코드 자체에 많은 양의 정보가 포함되어 있는 경우에는 단순 선택 정렬이 더 좋습니다. 2. 파일의 초기 상태가 기본적으로 키워드별로 정렬되어 있는 경우에는 직접 삽입이나 버블 정렬을 사용하는 것이 적합합니다. 3. n이 큰 경우 O(nlog2n) 정렬 방법(퀵 정렬, 힙 정렬 또는 병합 정렬)을 사용합니다. 퀵 정렬은 현재 비교 기반 내부 정렬의 가장 좋은 방법으로 간주됩니다. 정렬할 키워드가 무작위로 분포되어 있는 경우 퀵 정렬은 퀵 정렬보다 보조 공간이 덜 필요하며 퀵 정렬은 평균 시간이 가장 짧습니다. 최악의 시나리오는 발생하지 않습니다. 그러나 두 정렬 모두 불안정합니다. 안정적인 O(nlog2n) 알고리즘이 필요한 경우 병합 정렬이 사용되지만 단일 레코드의 쌍 병합은 일반적으로 직접 삽입 정렬과 함께 사용할 수 없습니다. 먼저 직접 삽입 정렬을 사용하여 더 긴 순서의 세분화를 얻습니다. 파일을 2개씩 병합합니다. 직접 삽입 정렬도 안정적이고, 향상된 병합 정렬도 안정적입니다. 4. 비교 기반 정렬 방법에서는 두 개의 키워드 크기를 비교할 때마다 두 개의 가능한 전송만 발생하므로 이진 트리를 사용하여 비교 결정 과정을 설명할 수 있습니다. 키워드가 무작위로 배포되는 경우 "비교"에 의존하는 모든 정렬 알고리즘에는 최소한 O(nlog2n) 시간이 필요합니다. 5. n이 매우 크고, 기록된 키워드의 개수가 적어서 분해가 가능한 경우에는 기수정렬(radix sorting)을 사용하는 것이 좋다. 6. 레코드 자체에 많은 양의 정보가 있는 경우, 레코드를 이동하는 데 많은 시간을 소비하지 않기 위해 연결 목록을 저장 구조로 사용할 수 있습니다.

외부 정렬

외부 정렬 알고리즘의 기본 개념

메모리에서 수행되는 정렬을 내부 정렬이라고 합니다. 많은 응용 프로그램에서는 대용량 파일을 정렬해야 하며 정렬을 위해 전체 파일을 메모리에 복사할 수 없습니다. 따라서 정렬할 레코드는 외부 메모리에 저장되어야 하며, 정렬 과정에서는 데이터가 메모리 부분별로 전송되어 메모리와 외부 저장소 간에 여러 번의 교환이 필요합니다. 이러한 정렬을 외부 정렬이라고 합니다.

외부 정렬 방법

외부 정렬 과정에서 소요되는 시간은 주로 디스크 접근 횟수, 즉 IO 횟수를 고려합니다. 외부 정렬은 일반적으로 병합 정렬을 사용합니다. 1. 메모리 버퍼의 크기에 따라 외부 저장소의 파일을 l 길이의 하위 파일로 나누고, 순서대로 메모리에 읽어들인 후 내부 정렬 방법을 사용하여 정렬한 후 순서대로 하위 파일을 씁니다. 외부 저장소로 다시 정렬한 후 얻은 이러한 정렬된 하위 파일을 병합된 세그먼트 또는 순차 문자열이라고 합니다. 2. 이러한 병합된 세그먼트를 하나씩 병합하여 전체 정렬된 파일을 얻을 때까지 병합된 세그먼트가 작은 것에서 큰 것으로 점차 증가하도록 합니다. 원패스 병합은 현재 동일한 레벨의 모든 세그먼트를 하나로 병합하는 것을 의미합니다. 총 외부 정렬 시간 = 내부 정렬 소요 시간, 외부 정보 읽기 및 쓰기 시간, 내부 병합 소요 시간 외부 저장소 정보를 읽고 쓰는 시간은 내부 정렬 및 내부 병합 시간보다 훨씬 깁니다. 외부 저장소 정보 읽기 및 쓰기는 "디스크 블록"을 기반으로 합니다. 따라서 필요한 총 읽기 및 쓰기 횟수는 다음과 같습니다. 2*총 레코드 수/디스크 블록의 레코드 수*n(회수) 총 레코드 수/레코드 수 디스크 블록(내부 정렬에도 전체 읽기 및 쓰기가 필요함) r개의 초기 병합 세그먼트에 대해 k-방향 균형 병합을 수행합니다. 트리 높이(역 k-진 트리) = logkr 및 상한 = 병합 패스 수 S 병합 경로 k의 수를 늘리거나 초기 병합 세그먼트 r의 수를 줄이면 병합 패스 수 S를 줄여 디스크 I/O 수를 줄이고 외부 정렬 속도를 향상시킬 수 있음을 알 수 있습니다.

다중 방향 균형 병합 및 패자 트리

병합 경로 k의 수를 늘리면 병합 경로 S의 수를 줄일 수 있지만 내부 병합 시간은 늘어납니다. 내부적으로 병합하는 경우 k개 요소 중 가장 작은 키워드를 선택하면 k-1개의 비교가 필요하며, n개 요소를 병합할 때마다 (n-1)(k-1)개의 비교가 필요하며 총 S번 비교해야 합니다. 병합에 필요한 비교 횟수는 다음과 같습니다. S(n-1)(k-1)=log2r은 상한을 취하고 (n-1)(k-1)/log2k는 상한을 취하고, 여기서 (k-1)/log2k는 상한을 취하고 k의 성장. 따라서 일반적인 내부 병합 정렬 알고리즘은 사용할 수 없습니다.

k의 증가로 인해 내부 병합이 영향을 받는 것을 방지하기 위해 패자 트리(loser tree)가 도입되었습니다. 패자 트리는 트리 정렬의 변형으로 완전한 이진 트리로 간주될 수 있습니다. k개의 리프 노드는 각각 현재 병합 과정에서 비교에 참여하고 있는 k개의 병합 세그먼트의 기록을 저장하고 있으며, 내부 노드는 왼쪽 및 오른쪽 노드의 "패자"를 기록하는 데 사용되며 승자는 최대 1개까지 계속해서 비교할 수 있습니다. 루트 노드. 루트 노드가 승자입니다. S(n-1) log2k가 상한을 취함 = log2k가 상한을 취함 (n-1) log2k가 상한을 취함 = (n-1) log2r이 상한을 취함 패자 트리를 사용한 후 내부 병합 정렬 비교 순서는 k와 관련이 없지만 병합 경로 k의 개수는 메모리 공간에 의해 제한되므로 특정 공간 내에서 버퍼 용량이 줄어들 수 있습니다. k 값이 너무 크면 병합 패스 수가 줄어들더라도 IO 수는 계속 증가합니다. ps: 승자 트리와 비교하여 승자 트리를 재구성할 때는 형제 노드와 비교한 다음 상위 노드를 변경해야 합니다. 패자 트리를 재구성할 때는 상위 노드만 비교하면 됩니다.

대체 선택 정렬(초기 병합 세그먼트 생성)

r을 줄이기 위해 r=n/l은 상한을 취하므로 더 긴 초기 병합 세그먼트 l을 생성하는 방법을 찾아야 합니다. 정렬할 초기 파일은 FI, 초기 병합 세그먼트 출력 파일은 FO, 메모리 작업 영역은 WA, FO와 WA는 처음에 비어 있고 WA는 w 레코드를 수용할 수 있다고 가정합니다. 교체 선택 알고리즘의 단계는 다음과 같습니다. 1. FI의 w 레코드를 작업 공간 WA에 입력합니다. 2. WA에서 최소 키워드 값이 있는 레코드를 선택하여 MINIMAX로 기록합니다. 3. MINIMAX를 FO에 녹음 4. FI가 비어 있지 않으면 FI에서 WA로 다음 레코드를 출력합니다. 5. WA의 모든 레코드 중에서 MINIMAX 레코드의 키워드보다 큰 키워드가 포함된 가장 작은 키워드 레코드를 새 MINIMAX 레코드로 선택합니다. 6. WA에서 새로운 MINIMAX를 선택할 수 없을 때까지 3~5단계를 반복하고, 초기 병합 세그먼트를 획득하고, 병합 세그먼트의 종료 플래그를 FO에 출력합니다. 7. WA가 비어 있고 모든 초기 병합 세그먼트를 얻을 때까지 2~6단계를 반복합니다. WA에서 MINIMAX 레코드를 선택하는 과정에는 패자 트리를 사용해야 합니다.

최고의 병합 트리

대체 선택을 통해 파일을 정렬한 후 서로 다른 길이의 초기 병합 세그먼트를 얻습니다. IO 수를 최소화하기 위해 길이가 다른 초기 병합 세그먼트의 병합 순서를 구성하는 방법은 무엇입니까? 해당 병합 트리를 그립니다. 트리의 가중치 경로 길이 WPL은 재귀 프로세스 중에 읽은 총 레코드 수입니다. 허프만 트리의 개념을 k-ary 트리의 경우로 확장하면, 병합 트리에서는 레코드 수가 적은 초기 병합 세그먼트를 먼저 병합하고, 레코드 수가 많은 초기 병합 세그먼트를 병합합니다. 마지막으로 병합된 총 IO는 최소 횟수로 최상의 병합 트리를 설정할 수 있습니다. 최상의 병합 트리를 구축하는 방법: 초기 병합 세그먼트가 엄격한 k-진 트리를 형성하기에 충분하지 않은 경우 길이가 0인 "가상 세그먼트"를 추가해야 합니다. 추가할 가상 세그먼트 수를 결정하는 방법은 무엇입니까? 엄격한 k-진 트리는 n0=(k-1)nk 1입니다. (n0-1)%(k-1)=0이면 k-fork 병합 북은 nk 내부 노드로 구성될 수 있습니다. (n0-1)%(k-1)=u!=0이면 k-u-1 빈 병합 세그먼트를 추가하여 병합 트리를 만들 수 있습니다.

AOV 네트워크와 AOE 네트워크는 모두 DAG이며 둘의 Edge와 Vertex는 서로 다른 의미를 갖습니다. AOV 네트워크의 가장자리에는 가중치가 없으며 정점 간의 컨텍스트만 나타냅니다. AOE 네트워크의 가장자리에는 가중치가 있으며 활동 완료 비용을 나타냅니다.

Dijkstra와 Prim의 차이점: Prim의 최소 스패닝 트리에 있는 모든 모서리의 합은 가장 작아야 하며, Dijkstra의 MST(단위점 최단 경로 트리)에서 두 점 사이의 거리만 반드시 최소 스패닝 트리보다 작을 필요는 없습니다. 원래 그래프 AB는 소스 지점까지의 거리가 추가되기 때문에 더 짧습니다. 두 지점 사이의 차이는 완화 작업에 있습니다. 또한 Prim은 무방향 그래프에만 사용할 수 있고, Dijkstra는 \ 무방향 그래프를 가질 수 있습니다(무방향 그래프는 유방향 그래프로 변환, ij 양측).

인접 행렬의 순회는 고유하지만, 인접 목록의 순회는 고유하지 않습니다.

연결성은 무방향 그래프에서 논의되고 강한 연결성은 유향 그래프에서 논의됩니다.