Data Structures and Algorithms in C

Data Structures and Algorithms in C

기타 소스코드

1.0.0

다운로드

c

여기에서 C에서 구현 된 일부 데이터 구조 및 알고리즘을 찾을 수 있습니다.이 알고리즘은 주로 Thomas H. Cormen의 알고리즘 소개를 기반으로합니다.

지침

모든 모듈은 하나 이상의 헤더 파일 (.H)과 코드 코퍼스 (.C)를 포함하는 하나의 소스 파일로 구성됩니다. 이 모듈 중 하나를 사용하려면 다음을 수행하는 것이 좋습니다.

/modules 에서 필요한 데이터 구조 또는 알고리즘 찾기
소스 코드 .C 파일 (예 : List.c )이 포함 된 모듈 디렉토리 (예 : /modules/List )를 다운로드하십시오.
/include/ 폴더로 이동하여 원하는 헤더 (.H) 파일 (예 : List.h )을 찾아 다운로드하십시오.
❕ 아직 끝나지 않았다. 이제 가서 헤더 파일 (.H)을 확인하고 포함 된 내용을 다운로드하십시오 (명령 #include "foo.h" ). 대부분의 모듈에는 예를 들어 HashFunctions 또는 Comparators 또는 기타 데이터 구조가 포함됩니다. 필요한 것을 발견하고 모든 파일을 다운로드하십시오.
현재 폴더 구조를 변경하면 #include "foo.h" 로 경로를 수정하십시오.
모든 것이 준비되었습니다. 도움이 되었기를 바랍니다!

컴파일 및 실행

전체 폴더를 복제하면 실행할 수 있습니다.

make : 모든 모듈을 만족시킵니다
make run-tests : 모든 모듈을 컴파일하고 모든 테스트를 실행합니다.
make valgind-tests : 모든 모듈을 컴파일하고 Valgrind를 사용하여 모든 테스트를 실행합니다.

충수

데이터 구조	정의
블룸 필터	블룸 필터는 1970 년 버튼 하워드 블룸 (Burton Howard Bloom)이 고안 한 공간 효율적인 확률 적 데이터 구조로 요소가 세트의 구성원인지 테스트하는 데 사용됩니다. 잘못된 양의 일치가 가능하지만, 잘못된 부정은 아닙니다. 즉, 쿼리는 "설정 가능"또는 "확실히 세트가 아님"을 반환합니다. 요소는 세트에 추가 될 수 있지만 제거되지는 않습니다 (카운팅 블룸 필터 변형으로 해결할 수 있지만). 항목이 많을수록 잘못된 양성의 확률이 커집니다.
빨간색 나무	빨간색-블랙 트리는 일종의 자체 밸런싱 바이너리 검색 트리입니다. 각 노드는 삽입 및 삭제 중에 트리가 균형을 유지하는 데 사용되는 "색상"( "빨간색"또는 "검은 색")을 나타내는 추가 비트를 저장합니다. 트리가 수정되면 새 나무가 재 배열되고 "다시 페인트"되어 나무가 최악의 경우에 균형을 잡을 수있는 색상을 제한하는 채색 특성을 복원합니다. 특성은이 재 배열 및 재 탄체를 효율적으로 수행 할 수 있도록 설계되었습니다. 재 발전은 완벽하지는 않지만 O (logn) 시간으로 검색을 보장합니다. 여기서 n은 트리의 노드 수입니다. 트리 재 배열 및 재 탄체와 함께 삽입 및 삭제 작업은 O (LOGN) 시간으로 수행됩니다.
링크 된 목록	링크 된 목록은 메모리의 물리적 배치에 의해 순서가 제공되지 않는 데이터 요소의 선형 모음입니다. 대신 각 요소는 다음 요소를 가리 킵니다. 시퀀스를 나타내는 노드 모음으로 구성된 데이터 구조입니다.
대기줄	우선 큐는 각 요소가 추가로 "우선 순위"와 관련된 일반 큐 또는 스택 데이터 구조와 유사한 추상 데이터 유형입니다. 우선 순위 대기열에서 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 제공됩니다.
목록이있는 해시 가능	키와 체인이있는 매우 간단한 해시 가능의 일반적인 구현. 재구성이 제공되지 않았습니다.
빨간색 나무로 해시 가능	테이블로 구성되며, 모든 행에 레드 블랙 트리에 대한 포인터가있는이 방법으로 우리는 위의 최고의 복잡성을 얻고 동시에 너무 많은 충돌을 피합니다.
버킷이있는 해시 가능	해시 테이블은 붉은 검은 나무에 대한 포인터 버킷으로 구성되었습니다
맥해	Max-Heap은 각 내부 노드의 값이 해당 노드의 어린이의 값보다 크거나 같거나 같은 완전한 이진 트리입니다. 힙의 요소를 배열에 매핑하는 것은 사소한 일입니다. 노드에 인덱스 k가 저장되면 왼쪽 자식은 색인 2k+1에 저장되고 오른쪽 하위는 색인 2k+2에 저장됩니다.
disjointset	Union-find 데이터 구조 또는 Merge-find 세트라고도하는 Disjoint 설정 데이터 구조는 Disjoint (비 겹치는) 세트 모음을 저장하는 데이터 구조입니다. 동등하게, 세트의 파티션을 분리 서브 세트에 저장합니다. 새 세트를 추가하고 세트를 병합 (노조로 교체) 및 세트의 대표 구성원을 찾기위한 작업을 제공합니다. 마지막 작업을 통해 두 요소가 동일하거나 다른 세트에 있는지 효율적으로 알 수 있습니다.
스레드가있는 작업 스케줄러	Unix pthreads를 사용하는 멀티 스레드 작업 스케줄러.

연산	정의
heapSort	Heapsort는 비교 기반 분류 알고리즘입니다. Heapsort는 개선 된 선택 정렬로 생각할 수 있습니다. 선택 정렬과 마찬가지로 Heapsort는 입력을 정렬 된 영역으로 나누고 IT에서 가장 큰 요소를 추출하여 분류 된 영역에 삽입하여 반복되지 않은 영역을 반복적으로 축소합니다. 선택 정렬과 달리, Heapsort는 소멸되지 않은 영역의 선형 시간 스캔으로 시간을 낭비하지 않습니다. 오히려, 힙 정렬은 힙 데이터 구조에서 미분식 영역을 유지하여 각 단계에서 가장 큰 요소를 더 빨리 찾습니다.
QuickSort	QuickSort는 효율적인 정렬 알고리즘입니다. 1959 년 영국 컴퓨터 과학자 Tony Hoare가 개발하고 1961 년에 발표 한이 건물은 여전히 정렬에 일반적으로 사용되는 알고리즘입니다. 잘 구현되면 Merge 정렬보다 다소 빠르고 Heapsort보다 약 2 ~ 3 배 더 빠를 수 있습니다.

연산

정의

heapSort

Heapsort는 비교 기반 분류 알고리즘입니다. Heapsort는 개선 된 선택 정렬로 생각할 수 있습니다. 선택 정렬과 마찬가지로 Heapsort는 입력을 정렬 된 영역으로 나누고 IT에서 가장 큰 요소를 추출하여 분류 된 영역에 삽입하여 반복되지 않은 영역을 반복적으로 축소합니다. 선택 정렬과 달리, Heapsort는 소멸되지 않은 영역의 선형 시간 스캔으로 시간을 낭비하지 않습니다. 오히려, 힙 정렬은 힙 데이터 구조에서 미분식 영역을 유지하여 각 단계에서 가장 큰 요소를 더 빨리 찾습니다.

QuickSort

QuickSort는 효율적인 정렬 알고리즘입니다. 1959 년 영국 컴퓨터 과학자 Tony Hoare가 개발하고 1961 년에 발표 한이 건물은 여전히 정렬에 일반적으로 사용되는 알고리즘입니다. 잘 구현되면 Merge 정렬보다 다소 빠르고 Heapsort보다 약 2 ~ 3 배 더 빠를 수 있습니다.