[음악 연주] 

ROB 보덴 : 안녕하세요. 롭 해요. 그리고의 이번 솔루션을 보자. 그래서 여기에 우리가 구현하는거야 일반 테이블. 우리는 볼이 우리의 구조체 노드 표는 다음과 같이 할 것입니다. 따라서 문자의 단어를 가지고거야 크기 길이 + 1의 배열입니다. , + 1을 잊지 마세요 이후 최대 사전에있는 단어는 45입니다 문자. 그리고, 우리는 하나가 추가 필요 해요 백 슬래시 제로 캐릭터. 

그리고 각 우리의 해시 테이블 버킷 저장하는 것입니다 노드의 연결리스트. 우리는 여기에서 프로빙 선형을하고 있지 않습니다. 그리고 순서에 따라 다음에 링크를 버킷에있는 요소는, 우리는 필요 구조체 노드 * 다음. OK. 그래서 노드가 어떻게 생겼는지입니다. 

지금 여기 선언은 우리의 해시 테이블. 그것은 16,834 버킷을 가질 것입니다. 그러나 그 수는 그리 중요하지 않습니다. 그리고 마지막으로, 우리는해야 할 것입니다 글로벌 변수 해시 테이블의 크기, 어떤 0으로 시작하는 것입니다. 그리고 그것은 어떻게 추적 할거야 많은 단어는 우리 사전에 있습니다. 

그럼 부하에 대해 살펴 보겠습니다. 그 부하를 주목, 그것은 부울을 반환합니다. 성공적이었다 경우 true를 반환 로드, 그렇지 않은 경우는 false. 그리고, const를 char *로 사전 소요 사전입니다 우리는 열려있다. 그래서 첫 번째 일이 우리가 할 것입니다. 

우리는은 fopen거야 독서를위한 사전. 그리고 우리는해야 돼 그것이 성공했는지 확인하십시오. 그것은 NULL을 반환 그렇다면, 우리는하지 않았다 성공적으로 사전을 엽니 다. 그리고 우리는 false를 반환해야합니다. 그러나 성공적으로 한 가정 열려있는, 우리가 읽고 싶은 사전. 우리는 몇 가지를 찾을 때까지 이렇게 반복 계속 이 루프의 탈옥 이유, 우리는 볼 수있다. 그래서 계속 루핑. 

그리고 지금 우리에가는거야 단일 노드를 MALLOC. 그리고 물론 우리는 필요 공기하려면 다시 확인. 그래서 mallocing 성공하지 않은 경우, 다음 우리는 우리의 모든 노드를 언로드 할 이전의 malloc에​​ 일어난 닫습니다 사전 및 false를 반환합니다. 그러나 무시, 가정 우리 성공, 우리는 fscanf 사용하려면 에서 하나의 단어를 읽을 수있는 우리의 우리의 노드에 사전. 그래서 입력> 단어를 기억 문자입니다 + 1 크기 LENGHTH의 단어 버퍼 우리는 안으로 단어를 저장하는 거라고 

그래서 fscanf는 한, 1을 반환 할 것입니다 그것은 수 성공적이었다로 파일에서 단어를 읽을. 오류 중 하나가 발생하면, 우리 파일의 끝에 도달, 그것을 1을 반환하지 않습니다. 그것은 1을 반환하지 않는 경우 우리는 마침내 탈옥거야 이 while 루프. 그래서 우리는 볼 우리는 성공적이되면 에 단어를 읽을 항목> 단어, 우리는 갈거야 우리의 해시 함수를 사용하여 단어. 

이제 살펴 보자 해시 함수. 그래서 당신이 정말로 필요로하지 않는다 이 문제를 이해하기. 그리고 실제로 우리는 단지이 해시를 뽑아 인터넷에서 작동합니다. 당신이 인식해야 할 유일한 일이다 이 const를 char *로 단어를 걸립니다. 그래서 문자열을 입력 복용하고 있어요 출력으로 서명 int를 반환. 그래서 그 모든 해시 함수입니다, 그것은이다 입력에 소요하고 당신에게를 제공합니다 해시 테이블에 인덱스. 

우리가 NUM_BUCKETS으로 moding 있다는 것을 주목 그래서 값이 반환 실제로 해시 테이블에 대한 인덱스는 그리고 않는 이상하지 인덱스 어레이의 경계. 그래서 기능, 우리는거야 주어진 우리가 읽고 단어를 해시 사전. 그리고 우리가 사용하는거야 삽입하는 해시 해시 테이블에 항목. 

이제 해시 테이블 해시 전류 표에 목록을 연결했다. 그리고 그것은 매우 가능 그냥 NULL 있다고. 우리는에서 우리의 항목을 삽입 할 이 연결리스트의 시작. 그래서 우리는 우리의 현재를해야 할 것입니다 무엇 해시 테이블에 엔트리 포인트 현재를 가리 킵니다. 그리고 우리는, 저장하는거야 의 해시 테이블에있는 해시, 현재 항목. 그래서이 두 줄이 성공적으로 삽입 의 시작 부분에 항목 그 인덱스에 연결된 목록 해시 테이블. 

우리가 그와 함께 완료되면, 우리는 알고있다 우리는 다른 단어를 발견 사전에, 우리는 다시 증가. 그래서 우리는 일을 계속하는 fscanf까지 마지막에 비 1 뭔가를 반환 어떤 순간 그 기억 우리는 항목을 해제해야합니다. 그래서 여기까지 우리는 항목을 malloc으로 할당. 그리고 우리는 무언가를 읽으려고 사전에서. 그리고 우리는 성공적으로 읽지 않았다 에서 사전에서 무엇인가, 우리는 항목을 해제해야하는 경우 우리는 실제로 투입 결코 해시 테이블, 그리고 마지막으로 휴식. 

우리가 파괴되면 우리가 볼 필요가, 잘, 때문에 우리는이 탈옥 않았다 오류가 파일에서 읽고 있었다? 아니면 우리가 탈옥 하니까 파일의 끝에 도달? 오류는 다음이 있다면 우리는 false를 반환합니다. 로드가 성공하지 않았기 때문입니다. 그 과정에서 우리는 언로드 할 모두 우리가 읽고 단어 및 사전 파일을 닫습니다. 

우리가 성공 않은 가정, 우리 단지 여전히 사전을 닫을 필요 파일, 그리고 마지막으로 true를 반환 이후 우리 성공적으로 사전 적재했다. 그리고 그 부하 그거야. 그래서 지금,로드 해시 테이블에 주어진 확인 다음과 같이 할 것입니다. 따라서, 이는이 부울을 반환 확인 통과했는지 여부를 표시하는 것 char *로 단어, 여부 전달 문자열에 우리의 사전에 있습니다. 그것은 사전에있는 경우에 따라서 우리의 해시 테이블에있는 경우, 우리는 true를 돌려줍니다. 그렇지 않은 경우에, 우리는 거짓을 반환합니다. 

이 단어에 전달 감안할 때, 우린 단어를 해시하는 것. 이제 인식 중요한 것은 부하에 우리가 알고있는 것을 그 모든 우리가 낮은 경우가 될 것입니다 단어. 그러나 여기에서 우리는 그렇게 확실하지 않다. 우리는 우리의 해시 함수를 살펴 경우, 실제로 우리 해시 함수 하부 케이싱은 각 캐릭터 단어의. 그래서 관계없이 총액 단어, 우리의 해시 함수는 반환합니다 무엇에 대해 동일한 인덱스 대문자는 것 등이다 완전히 소문자에 대해 반환 단어의 버전. 좋아. 즉, 우리의 인덱스로이다의 이 단어를 해시 테이블. 

이제 루프이 예정 연결리스트를 반복 즉, 해당 인덱스에 있었다. 그래서 우리는 항목을 초기화하는 통지 해당 인덱스를 가리 키도록. 우리는 계속할 예정 항목! = NULL있다. 그리고 기억하는 포인터를 업데이트 다음에 우리의 링크리스트의 항목 항목을 =>. 그래서 현재의 엔트리 포인트가 링크 된 목록에서 다음 항목을 선택합니다. 

따라서 링크 된 목록의 각 항목에 대한, 우리는 strcasecmp를 사용하는 것입니다. 그것은에서는 StrComp 아니다. 다시 한 번, 우리가 원하기 때문에 소문자를 구별 가지 사례를 않습니다. 그래서 우리는 비교 strcasecmp를 사용하는 이 통과 된 단어 단어에 대한 기능 즉,이 항목에 있습니다. 그것은 0을 반환하면 해당이있었습니다 의미 우리가 할 경우 경기 일정, true를 반환합니다. 우리는 성공적으로 발견 우리의 해시 테이블에있는 단어입니다. 

일치가 아니었다면, 우리는거야 다시 루프에 가서 봐 다음 항목. 그리고 우리는 거기있는 동안 루프를 계속합니다 이 연결 목록에있는 항목입니다. 우리가 중단하면 어떻게됩니까 루프이 중? 즉, 우리는 항목을 찾을 수 없습니다 의미 이 경우,이 단어를 일치 우리는 표시 할 false를 반환 우리의 해시 테이블은이 단어를 포함하지 않았다. 그리고 그 수표입니다. 

그래서 크기에 대해 살펴 보겠습니다. 현재 크기는 매우 간단 될 것입니다. 이후 각 단어에 대해, 부하 기억 우리는 우리가 글로벌을 증가 발견 변수 해시 테이블의 크기입니다. 그래서 크기 기능은 것입니다 전역 변수를 반환합니다. 그리고 바로 그거야. 

이제 마지막으로, 우리는 언로드 할 필요가 사전에 모든 것을 끝낼 번. 그래서 우리가 어떻게 그렇게 할거야? 바로 여기에 우리는 이상 반복하고 우리 테이블의 모든 버킷. 그래서 NUM_BUCKETS 버킷이 있습니다. 그리고 각 연결리스트에 대한 우리의 해시 테이블, 우리는 반복 할거야 연결리스트의 전체, 각 요소를 자유롭게. 

이제 우리는주의해야합니다. 그래서 여기에 우리는 임시 변수가 그 다음에 포인터를 저장하는 것 링크 된 목록의 요소입니다. 그리고 우리는 자유에가는거야 현재 요소. 우리는 우리가 우리 때문에이 작업을 수행해야 할 필요가 다만 현재 요소에게 무료로 할 수 다음 다음 포인터에 액세스하려고, 한 번 있기 때문에 우리는 그것을 해제했습니다, 메모리는 무효가됩니다. 

그래서 우리는 포인터를 주위에 유지해야 다음 요소는, 우리가 확보 할 수 있습니다 현재 요소, 그리고, 우리는 업데이트 할 수 있습니다 를 가리 키도록 현재의 요소 다음 요소. 우리는 요소는 루프가 있습니다 동안 이 연결리스트에서. 우리는 모든 연결을 위해 그렇게 할 것이다 해시 테이블에있는 목록. 우리가 그와 함께 완료되면, 우리는했습니다 완전히 해시 테이블을 언로드하고, 우리는 끝났어. 그래서 언로드 불가능 이제까지 false를 반환합니다. 그리고 우리가 끝나면, 우리 진실이 돌아갑니다. 

의이 솔루션 시도해 보자. 그럼 어떻게 우리를 살펴 보자 구조체의 노드가 같이 표시됩니다. 여기에서 우리는 우리가 부울을해야 할 것입니다 참조 단어와 구조체 노드 * 어린이 브래킷의 알파벳입니다. 당신이있을 수 있습니다 그래서 우선 궁금, 왜 알파벳입니다 ED (27)로 정의? 글쎄, 우리가 필요 해요 기억 아포스트로피를 처리합니다. 그래서 어느 정도 될 것 이 프로그램 전반에 걸쳐 특별한 경우. 

지금 기억하는 방법 트라이 실제로 작동합니다. 의 우리가 단어를 색인하고 있다고 가정 해 봅시다 "고양이." 그런 다음 트라이의 루트에서, 우리는 아이들을 보는거야 배열, 우리는 보는거야 문자에 해당하는 인덱스 2 색인화 할 C. 그래서. 그래서 주어진, 그 의지 우리에게 새 노드를 제공합니다. 그리고 우리는 그 노드에서 작동합니다. 

그래서 노드 주어, 우리는 다시 한 번이야 아이들의 배열을 볼 줄. 그리고 우리는 인덱스 0에 보는거야 고양이에 해당합니다. 그래서 우리는 그 노드에 가서, 해당 노드 주어진 우리는거야 최종보고는 대응의 T. 그리고 그 노드로 이동,에 마지막으로, 우리는 완전히 보았다 을 통해 우리의 단어 "고양이." 그리고 지금을 bool 단어 여부를 표시하도록되어 이 주어진 단어는 실제로 단어입니다. 

그럼 왜 우리는 특별한 경우를 필요합니까? 그럼 어떤 단어의 "재앙" 우리 사전에 있지만 단어 "고양이"아닌가요? 그래서와보고 찾고 경우 단어 "고양이" 우리의 사전에, 우리는 야한다 성공적으로 통해 볼 것 지역 노드의 인덱스는 C-A-T. 하지만 그건 단지 때문에 재앙 길에 노드를 만들 수 있었 C-A-T에서 모든 방법을 단어의 끝. 그래서 BOOL 단어 여부를 나타내는 데 사용된다 이 특정 위치 실제로 단어를 나타냅니다. 

괜찮아요. 그래서 지금 우리가 트라이가 무엇인지 알고 처럼 보이게하는 것,의를 살펴 보자 기능을로드합니다. 그래서 부하는 부울을 반환하는 것입니다 여부를 우리가 성공적으로 나에 대한 실패 사전 적재했다. 그리고 이것은 사전이 될 것입니다 우리는로드 할 것을. 

우리가 할 수있는 좋은 방법입니다 그래서 일단 열려 독서하는 사전입니다. 그리고 우리는 확인해야 우리는 실패하지 않았다. 사전은 아니었다 그렇다면 성공적으로 열려, 그것은 반환 널 (null),이 경우 우리는 야 false를 반환하는 것. 그러나 가정 그것이 성공적으로 열, 우리는 실제로 읽을 수 있습니다 사전을 통해. 

우리가 갈거야 그래서 일단 하고 싶은 우리는이 가지고있다 전역 변수 루트. 이제 루트 * 노드가 될 것입니다. 그것은 우리가있어 우리의 트라이의 정상의 반복 할 것. 우리는거야 그래서 우선 하고 싶어하는 할당입니다 우리의 뿌리에 대한 기억. 우리는 buf는을 사용하는 것을 알 수 기본적으로 동일 기능, 의 malloc 함수를 제외하고는의 무언가를 반환 보장 완전히 제로. 우리의 malloc을 사용하는 경우에, 우리는해야합니다 의 모든 포인터를 이동 우리 노드 및 있는지 확인 그들은 모두 널 (null)입니다. 그래서 buf는 우리를 위해 그렇게 할 것이다. 

지금 만의 malloc처럼, 우리가해야 할 할당이 사실은 확인 성공. 이 null을 반환하는 경우에, 우리 닫거나 사전 필요 파일 및 false를 반환합니다. 그래서 할당 된 가정 성공, 우리는 * 노드를 사용하는 것입니다 우리의 트라이를 반복하는 커서. 그래서 우리의 뿌리를 변경하려고하지 않습니다, 그러나 우리는 커서를 사용하는 것입니다 실제로 노드에서 노드로 이동합니다. 

그래서 이것 루프 우리가 읽고 사전 파일을 통해. 그리고 우리는 fgetc를 사용하고 있습니다. 는 fgetc는 하나를 잡아 것입니다 파일에서 문자. 우리는 잡는 계속할 예정 자 우리가 도달하지 않는 동안 파일의 끝. 

우리가 처리해야하는 두 가지 경우가 있습니다. 첫 번째, 만약 문자 새로운 라인이 아니었다. 그래서 우리는 그 다음, 새 줄 있었는지 우리는 새로운 단어로 이동하려합니다. 하지만, 그것이 새로운 라인이 아니었다 가정 여기에 우리가 알아 내야 할 인덱스 우리는에 인덱스에가는거야 어린이 배열이 우리는 전에 바라 보았다. 

그래서, 내가 전에 말했듯이, 우리는 필요 특별한 경우 아포스트로피. 우리가 삼진을 사용하는주의 여기 운영자. 그래서 우리는 경우에,이 글을 읽을거야 우리가 읽은 문자가 있었다 아포스트로피, 우리는 만들 것이다 인덱스 = "ALPHABET"-1, 어떤 것 인덱스 26 수. 

그렇지 않으면, 아포스트로피가 아니었다면,이 우리는 인덱스를 설정하는거야 C에 해당 -. 그래서 다시 이전 P-세트의 기억, C -이 우리에게 줄 수 있겠나? C.의 알파벳 위치의 경우 지금 C는이 것, 편지입니다 우리 지수 제로를 제공합니다. 문자 B의 경우, 줄 것이다 그래서 우리 인덱스 1합니다. 

그래서 이것은 우리에 대한 인덱스를 제공 우리가 원하는 것을 아이 배열입니다. 지금이 지수는 현재 null의 경우 아이들은 그 의미 노드 현재 존재하지 않는 그 길에서. 그래서 우리는 할당해야 해당 경로에 대한 노드. 즉, 우리가 여기서 무엇을 할 거 야입니다. 

그래서 우리는 다시 calloc을 사용할 예정입니다 기능은, 우리가 할 필요가 없도록 모든 포인터를 제로. 그리고 우리는 다시 확인해야합니다 그 buf는 실패하지 않았다. buf는 실패 않은 경우에, 우리는 필요 모든 언로 닫으 우리 사전 및 false를 반환합니다. 그래서 그 다음, 실패하지 않았다고 가정 이것은 우리의 새로운 아이를 작성합니다. 그리고 우리는 그 아이로 이동합니다. 우리의 커서가 반복됩니다 그 아이에 이르기까지. 

지금은 처음부터 null이 있다면, 다음 커서가 단지 반복 할 수 실제로하지 않고 그 아이에 이르기까지 아무것도 할당하는 데. 이것은 우리가 처음 일어난 경우입니다 단어 할당 "고양이." 과 우리가 할당 갈 때 그 의미 "재앙,"우리는 만들 필요가 없습니다 다시 C-A-T에 대한 노드. 그들은 이미 존재합니다. 

다른 사람이 무엇입니까? 이 C 한 상태이다 C는 새로운 라인이었다 백 슬래시 N,. 이것은 우리가 성공적으로해야 함을 의미 단어를 완료했습니다. 지금 우리는 무엇을 하시겠습니까 때 우리 성공적으로 단어를 완성? 우리는이 단어 필드를 사용하는 것입니다 우리의 구조체 노드의 내부. 우리는 참으로이 부분을 설정합니다. 그래서 나타냅니다이 노드 성공을 나타냅니다 단어, 실제 단어. 

이제 참으로 그 설정합니다. 우리는 점에 우리의 커서를 재설정 할 다시 트라이의 시작. 그리고 마지막으로, 우리의 사전을 증가 크기, 우리는 다른 일을 찾을 수 있기 때문이다. 그래서 우리는 그 일을 계속하는 것입니다, , 문자로 문자 독서 우리의 트라이에 새 노드를 구성하고 사전에, 때까지 각 단어에 대한 우리는 마침내 C에 도달! = EOF,하는 경우 우리는 파일의 탈옥. 

지금 이가지 경우에 따라이 있습니다 우리는 EOF 칠 수도있다. 오류가 발생했을 경우는 우선 파일 읽기. 오류가 발생했습니다 그래서, 우리 일반적인 작업을 수행해야합니다. 가까운 모든 것을 언로드 파일은 false를 반환합니다. 오류가 없었습니다 가정하면 우리가 실제로의 끝을 명중 의미 파일은,이 경우에, 우리는 이서 파일 및 true를 반환 이후 우리 성공적으로로드 사전 우리의 트라이에. 

그래서 지금의이 체크 아웃을 확인 할 수 있습니다. 체크 기능을 보면, 우리는 참조 그 검사는 부울을 반환하는 것입니다. 이 단어가 있다는 경우는 true를 반환 전달되는 우리의 트라이에 있습니다. 그것은 그렇지 않으면 false를 반환합니다. 어떻게 당신이 있는지 여부를 확인하는 이 말씀은 우리의 트라이에? 

우리는 여기에서 보는 그 직전처럼, 우리는 반복하는 커서를 사용하는 것입니다 우리의 트라이를 통해. 지금 여기에 우리가 반복하는거야 우리의 전체 단어 이상. 그래서, 우리는 지난 수있는 단어 반복 우리가 결정하는거야 인덱스 어린이 배열에 그 단어 브래킷 I.에 해당 따라서이 정확히처럼 보이는 것입니다 부하 여기서 경우 ​​단어 [I] 아포스트로피는, 우리가 원하는됩니다 인덱스 "알파벳"사용하기 - 1. 우리는 결정하기 때문이 우리가 저장가는 곳입니다 아포스트로피. 

그렇지 않으면 우리는 아래 두 단어를 사용하는 것입니다 브래킷 I. 그래서 그 단어를 기억할 수 임의의 총액이있다. 그래서 우리는 우리가다는 것을 확인하고 싶다 사물의 소문자 버전을 사용하여. 그리고 그 'A'1 회에서 빼기 다시 우리에게 알파벳을 제공 그 문자의 위치. 그래서 색인 될 것 어린이 배열에. 

그리고 지금의 경우 자녀에 해당 인덱스 배열이 null, 그것은 우리에게 의미 더 이상 반복 할을 계속할 수 우리의 트라이 다운. 그런 경우,이 단어는 할 수 없습니다 아마도 우리의 트라이로합니다. 그것이 있다면, 그 것 때문에 경로가 될 것이다 의미 그 단어에 이르기까지. 그리고 당신은 널 (null)이 발생하지 않을 것입니다. 그래서 널 (null)가 발생, 우리는 false를 반환합니다. 이 단어는 사전에없는 것입니다. null이 아니었다면, 우리는거야 반복하기를 계속하는 것. 

그래서 우리는 거기에 커서를거야 특정를 가리 키도록 해당 인덱스의 노드. 우리는 내내 그 일을 계속 전체 단어, 가정 우리는 널 (null)에 충돌하지 마십시오. 즉, 우리가 통과 할 수 있었다 의미 전체 단어 찾기 우리 시도의 노드. 그러나 우리는 확실히 아직 끝나지 않았습니다. 

우리는 단지 true를 반환하지 않습니다. 우리는 커서> 단어를 반환합니다. 다시 기억 때문에, "고양이"이용하실 수 있습니다 우리의 사전에, 그리고 "재앙" , 우리는 성공적으로 우리가 얻을 것이다 을 통해 단어 "고양이." 그러나 커서 말은 거짓과 진실되지 않습니다. 그래서 우리는 표시하기 위해 커서의 단어를 반환 여부를이 노드는 실제로 단어입니다. 그리고 그 확인을 위해의. 

그래서 크기를 확인 할 수 있습니다. 그래서 크기는 매우 쉽게 될 것입니다 이후, 부하 기억, 우린 위한 사전의 크기를 증가 우리는 발생하는 각 단어. 그래서 크기는 단지 예정 사전의 크기를 반환합니다. 그리고 바로 그거야. 

그래서 마지막으로 우리는 언로드했다. 그래서 언로드, 우리가 사용하는거야 실제로 모든 할 수있는 재귀 함수 우리의 작업. 그래서 우리의 기능을 것입니다 언 로더를 호출 할. 무엇 언 로더는 할거야? 우리는 언 로더가 예정 여기를 참조하십시오 모든 아이들에서을 반복 이 특정 노드. 및 자식 노드가 아닌 경우 널 (null), 우리는거야 자식 노드를 언로드. 

그래서이 재귀 적으로 언로드합니다 우리 아이들의 모든. 우리는 있는지 들어가면 우리 아이들의 모든 언로드 된, 우리 자신을 확보, 그렇게 할 수 있습니다 자신을 언로드. 이 재귀 적으로 작동합니다 전체 트라이 언로드. 그리고 그 끝났어하면, 우리는 단지 true를 반환 할 수 있습니다. 언로드가 실패 할 수 없습니다. 우리는 단지 물건을 확보하고 있습니다. 그래서 일단 우리가 확보 완료 모든 것이 true를 반환. 그리고 바로 그거야. 내 이름은 롭입니다. 그리고 이것은 철자했다. 

[음악 연주]