주어진 문자열 목록에서 구축된 Trie의 가능한 모든 노드를 인쇄합니다.

C++에서 트리는 트리 모음을 저장하는 데 사용되는 상위 수준 데이터 구조입니다. trie라는 단어는 검색(retrieval)이라는 단어에서 유래되었으며 이를 숫자 트리 또는 접두사 트리라고 합니다.

주어진 문자열 목록을 사용하여 가능한 모든 조인의 예를 들어 보겠습니다.

문자열 입력을 {"tutor", "true", "tuo"}

로 정의합니다.

서로 다른 문자열이 하나의 문자열로 연결되어 있는 것을 볼 수 있습니다. 따라서 여기 t 및 u는 가능한 모든 문자열을 연결하는 문자 목록입니다.

이 기사에서는 trie 데이터 구조를 사용하여 문자열 목록에서 가능한 모든 연결을 해결합니다.

문법

으아악

매개변수

• struct − 이 키워드는 구조 데이터 유형을 나타내는 데 사용됩니다.

• name_of_structure − 구조에 대한 이름을 제공합니다.

• 구조체는 다양한 관련 변수를 한 곳에 모아 놓은 것입니다.

으아악

alpha는 treetrie라는 구조 포인터/데이터 멤버를 가리키는 변수의 이름입니다. 알파벳은 문자의 총합 값을 정수로 표현하는 매크로입니다.

알고리즘

• 먼저 C++의 모든 표준 템플릿 라이브러리가 포함된 'bits/stdc++.h'라는 헤더 파일을 사용합니다.

• 알파벳의 총 문자 수와 최대 문자 값을 정의하는 'alphabet' 및 'max'라는 두 개의 매크로를 정의합니다.

• 우리는 'tree node'라는 구조를 만들고 'tree_node'에 대한 포인터를 정의하여 문자의 주소를 저장합니다. 문자열의 끝 문자로 사용될 변수 'end_word'를 bool 데이터 유형으로 정의합니다.

• 우리는 'buildNode'라는 함수를 정의하여 포인터를 사용하여 trie가 만든 트리를 나타내는 새 노드에 연결합니다.

• 문자열을 삽입하기 위해 itm, str(삽입할 문자열), i(처리 중인 현재 문자를 나타냄)의 세 가지 매개 변수를 허용하는 'ins_recursive_of_string'이라는 재귀 함수를 만들었습니다.

• 함수 ins()는 코드에서 ins_recursive_of_str()의 래퍼 함수로 정의됩니다. tree_trie* itm(tree_trie 개체) 및 string str(삽입할 문자열)의 두 가지 매개 변수를 허용합니다. 현재 노드, 삽입할 문자열, 시작 인덱스 0을 사용하여 재귀 함수를 호출합니다.

• 다음으로 tree_trie 객체를 매개변수로 받아들이고 리프 노드인지, 즉 자식이 없는지 확인하는 LeafNode()라는 함수를 생성합니다.

• 함수 display_joint()는 코드에 정의되어 있으며 4개의 매개변수 tree_trie* 루트, tree_trie* itm(현재 처리 중인 노드), char str[](상점용 문자 배열 str)을 허용합니다. 루트 노드에서 현재 노드까지 형성된 경로 문자열) 및 int 수준(현재 노드의 깊이를 나타내는 정수 수준)입니다.

• 이 코드는 display_joint()에 대한 래퍼 함수인 displayJ() 함수를 정의합니다. tree_trie 객체를 인수로 받아들이고 루트 노드, 빈 문자 배열 및 시작 레벨 0을 인수로 사용하여 display_joint() 함수를 호출합니다.

• 이 코드는 Trie 루트 노드로 새로운 tree_trie 개체를 생성하는 main() 함수를 정의합니다. 이는 Trie에 삽입될 문자열 목록을 포함하는 벡터 s를 생성합니다. 그런 다음 ins() 함수를 호출하여 각 문자열을 Trie에 삽입합니다.

• 마지막으로 출력 시작을 알리는 메시지를 인쇄하고 displayJ() 함수를 호출하여 모든 Trie 조인 포인트를 표시합니다.

예

이 프로그램에서는 주어진 문자열 목록에서 구축된 트라이의 가능한 모든 조인 포인트를 인쇄합니다.

으아악

출력

으아악

결론

우리는 주어진 문자열 목록에서 가능한 모든 트라이 조인 포인트를 구축하는 트라이 데이터 구조의 개념을 탐구했습니다. 출력에서 문자 u와 t는 tutorial, true 및 tuo와 같은 문자열을 사용하여 트라이의 가능한 모든 연결 지점을 연결하는 것을 볼 수 있습니다. 따라서 가능한 연결 지점을 제공함으로써 트리는 노드를 줄일 수 있습니다.

위 내용은 주어진 문자열 목록에서 구축된 Trie의 가능한 모든 노드를 인쇄합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!