[Powered by Google Translate] [연습 - 문제 세트 5] [Zamyla 찬 - 하버드 대학교 (Harvard University)] [이 CS50입니다. - CS50.TV] 

괜찮아요. 안녕하세요 여러분, 연습 5에 오신걸 환영합니다. 

Pset5 우리가 맞춤법 검사기를 만드는 될에 맞춤법이 틀린 것입니다. 맞춤법 검사기는 매우 중요합니다. 이 당신에게 무슨 일이 있었습니까? 당신은 매우 일을, 매우 충돌에 대한 종이에 축적 그리고 아직도 D 또는 D = 같은 매우 글로우 무역을 받고 결국 모든 당신이 고래 다양한 단어 간 소시지 스포일러 때문입니다. 네, 후추를 교정하면의 문제, 최고의 발기 부전이다. 이 남자 다운, 남자 다운 학생에 영향을 미치는 문제입니다. 나는 일단 내가 좋은 동료로 얻을 안한다고 시스 등급 고문 기술자에 의해 말을 들었다. 그리고, 모든 어떤 꼬마가 내 나이에이 원한건 그게 내가 원했던 전부예요 그냥 좋은 동료로 얻을 수 있습니다. 뿐만 아니라 모든 동료. 아니, 아이보리 법률 동료에게 가고 싶어. 제가 개선 안하면, 사라는 하버드에가는 꿈이 될 것입니다 Jale, 또는 감옥 - 당신도 알다시피, 감옥에서, 뉴저지. 그래서 저 스스로 맞춤법 검사기를 가지고. 내가 제일 좋아하는 음성 단어 아티스트 테일러 말리 중 하나에서 약간 발췌입니다. 그가 말한대로 어쨌든, 맞춤법 검사기를 갖는의 중요성은 매우 중요합니다. 

그래서 우리가 pset5에 대해 얘기 될에 연습 5에 오신걸 환영합니다 : 철자를, 있는 우리의 맞춤법 검사기을합니다. 이번 주에 대한 도구 상자는 유통 코드는 보는 것이 중요 될 것입니다 그냥 사전 가야되는 다른 기능을 이해합니다. 우리는 실제로 우리의 pset를 여러. C 파일을 낳게 될거야. 그리고 우리가 실제로 수정하지 않았는데도, 서로 다른 측면을보고 이 dictionary.c과 관련하여 함께 작동하는 방법 알고있는 파일 중 하나 speller.c, 우리가 쓰기 될 아주 중요한 될 것입니다. pset 사양도 많은 유용한 정보가 포함되어 있습니다 당신이 추측 할 수있는 일의 관점에서, 그런 규칙 및 일, 그래서 팁을주의 깊게 pset 사양을 읽어 보시기 바랍니다. 그리고 때와 같은 규칙이나 뭐 의심하고 항상 pset 사양을 참조 또는 토론. 본 pset는 포인터에 의존 것입니다 그래서 우리는 우리가 추가 별의 차이를 이해하도록해야 할 을 확보하는 방법 포인터의 이름과 앰퍼샌드, 등의 앞 그럼 포인터의 마스터되는이 문제 세트에 많은 도움이 될 것입니다. 우리는 좀 더 링크 된 목록으로 보는거야 우리는 값뿐만 아니라 포인터가 모두 노드를 호출하는 요소가있는 다음 노드까지, 그래서 본질적으로 다른 요소에게 다른 후 하나를 연결. 실제 사전을 구현하는 몇 가지 옵션이 있습니다. 두 가지 주요 방법, 해시 테이블이며, 다음 시도로 보는거야. 그 모두, 그들은 연결리스트의 개념의 일부 종류를 포함 하나 다른 요소를 연결 한 곳입니다. 그래서 우리는, 당신이 연결된 목록을 주위에 작동 할 수있을 방식을 보는거야 그들을 만드는 방법의 관점에서 탐색, 예를 들어,에 노드를 삽입 나뿐만 아니라 노드의 모든 무료입니다. 자유롭게 노드의 측면에서, 정말 중요한 일이에요 우리 malloc 메모리, 나중에 우리가 해방 될 때마다. 그래서 우리는 우리가 어떤 메모리 누수가없는 것을 더 포인터가 unfreed 갈 수 없어되었는지 확인하고 싶습니다. 우리는 프로그램을 실행하는 Valgrind라는 도구를 소개 할거야 당신이 할당 한 모든 메모리 여부 확인은 다음 해제됩니다. , 작동 할 때 pset는 완료되어 있으며 모든 기능을 갖추고 있습니다 뿐만 아니라, Valgrind는 어떤 메모리 누수를 발견하지 않은 사실을 알려줍니다. 마지막으로,이 pset에 대해, 난 정말 강조하고 싶은 - 내 말은, 평소처럼, 분명히 문제 세트에 펜과 종이를 사용하는 후원자이고, 하지만이 하나의, 나는 펜과 종이가 특히 중요 할 것입니다 생각 당신은 사물에 화살표를 그릴 일이 어떻게 작동하는지 이해 할 할 때. 그래서 확실히 당신이 코딩을하기 전에 물건을 끌어 펜과 종이를 사용하려고하면 그것은 약간 혼란스러워 질수 수 있기 때문입니다. 

첫째,가 연결된 목록에 조금 가자. 연결된 목록은 모든 노드가와 연관된 값이 노드,로 구성 뿐만 아니라 다음으로 노드에 대한 포인터. 링크 된 목록을 가진 중요한 사항 몇 사람은 우리가 기억해야한다는 점입니다 첫 번째 노드가있는 곳 첫 번째 노드가있는 곳, 그리고 한 번 우리는 알고 그런 식으로 우리는 노드에 액세스 할 수 있습니다 거기에 첫 번째 노드 포인트 다음, 그 후 하나 그 후 한. 다음 연결리스트의 마지막 요소는 노드의 포인터입니다 항상 NULL을 가리 키도록 것이다. 노드 포인트가 null로하면, 다음이 목록의 끝에 도달 한 알, 그건 해당 노드 그 이후로 아무 것도없는, 마지막 하나입니다. 다음은이 도식에서, 당신은 화살표 포인터 있다는 것을 알 그리고 파란색 부분은 값이 저장되는 위치, 다음에 포인터로 빨간색 상자가 노드의 포인터입니다 그 다음으로 노드를 가리키는. 이 목록의 마지막 요소이기 때문에 그리고 당신이 여기서 보는, D 노드는 NULL를 가리킨 것입니다. 

의 우리가 노드에 대한 구조체를 정의하는 방법을 살펴 보도록하겠습니다. 그리고 우리는 여러 노드를 갖고 싶어 때문에, 이 typedef 구조체가 될 것입니다 있는 우리는 노드의 여러 인스턴스를 가지고거야. 그래서 우리는 새로운 데이터 형식으로 정의합니다. 여기, 우리는 typedef 구조체 노드가 있습니다. 이 예제에서, 우리는 정수 노드를 다루고 있습니다 , 그래서 우리는 정수라는 이름의 가치가, 그리고 나서 우리는 다른 포인터를 가지고 이 경우에는, 그 노드에 대한 포인터입니다, 그래서 우리는 다음이라는 구조체 노드 *을 갖추고 있습니다. 그리고 우리는이 모든 걸 노드를 호출하고 있습니다. 이 구문을 준수해야합니다. 해당 노드가 실제로뿐만 아니라 중괄호 다음과 같은 위 참조 확인할 수 있습니다. 그런 다음 첫 번째 노드가이 연결 목록에있는를 추적하기 위해, 그때 머리라는 노드 포인터를 가지고 있고, 노드의 크기만큼 나는 malloc 공간. 공지 그러나, 그 머리는 실제로 실제 노드 자체에 반대하는 등의 노드 포인터입니다. 그래서 머리는 실제로 어떤 값을 포함하지 않습니다 그것은 단지 내 연결된 목록의 첫 번째 노드가 중을 가리 킵니다. 

매우 중요하기 때문에 연결 목록의 더 나은 이해를 얻으려면 당신이 체인을 유지하는지 확인하는 추적하는 데, 라인에 사람들이 손을 잡고 같이 나도 그렇게 생각하고 어디에서 각 사람은 다음과 손을 잡고있다. 이 그림에서 볼 수는 없지만, 기본적으로 그들은 다음 사람을 가리키는하고 그 자신의 체인입니다. 그리고 당신은이 사람들 연결된 목록을 탐색하려면 - 사람들의 생각은 그들과 관련된 값을 가지고 또한 라인의 다음 사람에게 지적이야 - 이 링크 목록을 탐색하려는 경우, 예를 들어, 하나의 값을 수정하는 방법 이런 값이나 뭐 또는 검색 다음은 특정 사람에 대한 포인터를 갖고 싶어합니다. 그럼 우리는 데이터 형식 노드 포인터를 할 겁니다. 이 예를 들어,의 그것이 커서이라고 불러. 이 이름을 또 다른 일반적인 방법은 반복자 또는 그런 일 것 다 끝났 반복하고 사실은을 가리키는있어 어떤 노드 이동이 없기 때문입니다. 여긴 우리의 커서가 될 것입니다. 우리 커서는 먼저 목록의 첫 번째 요소를 가리 킵니다. 그리고 우리가 원하는 것은 우리는 기본적으로 커서를 계속됩니다 좌우로 이동. 이 경우, 우리는 목록에있는 다음 요소로 이동하고 싶습니다. 배열을 통해 우리가 갖고 싶은 건 우리가 우리가 1 인덱스를 증가 말할 것입니다. 이 경우, 우리가해야하는 것은 사실, 현재의 사람을 가리키는되는 사람 찾는 그리고 그 다음 값거야. 커서 우리가 원하는 것을 다음 단 노드 포인터면 우리가 커서가 가리키는되는 값 싶은 것입니다. 우리는 노드에 도착하고 가리키는 곳 다음 번 우리가 그 노드에있을거야, 찾고 싶어요. 커서가 가리키는되는 실제 노드에 도착하려면, 보통 우리는 (* 커서)하여 나타냅니다. 그게 당신에게 커서가 가리키는되는 실제 노드를 제공하게됩니다. 그리고 그 이후로, 어떻게 우리가 원하는 것은 우리가 액세스 싶은 노드의 다음 값이입니다 뭐든간에. 구조체의 내부 값을 액세스 할, 그런 식으로, 우리는 도트​​ 연산자가 있습니다. 그래서 그것은 (* 커서)가됩니다. 다음. 그러나 이것은, * 커서 주위에 괄호를 갖는 측면에서 약간의 혼란입니다 그래서 우리는 커서 ->로이 전체 문장을 대체합니다. 이건 너무 화살표를 만드는 대시 다음보다 큰 신호입니다. 커서 -> 다음. 그래서 실제로 노드 받게됩니다 거기에 커서를 가리 킵니다. 이 값은 다음입니다. 대신 별표와 점있는 것만도, 당신은 화살표가 그 대체하고 있습니다. 이 구문을 사용하려고 있는지 확인하기가 매우주의하십시오. 

우리가 값에 액세스하려는 경우이게 바로 우리는 우리의 커서가 전에, 우리는 커서 -> 옆에했다 하지만 커서가 가리키는되는 노드의 값에 액세스하기 위해 우리는 간단하게 말 노드 -> 값입니다. 여기에서 우리가 값과 될 수있는 노드를 정의 어떤 데이터 형식의입니다. 이 정수 노드이라면, 커서 -> 값은 정수가 될 것입니다. 그래서 우리는 그에 대한 작업을 할 수 그것을 다른 값 등을 지정 평등을 확인 그럼 당신은 다음 사람에게 커서를 이동하려는 경우 당신이 원하는 무엇 당신은 실제로 커서의 값을 변경합니다. 커서가 노드 포인터이기 때문에, 당신은 실제 포인터 주소를 변경 귀하의 목록에있는 다음 노드의 주소. 이 메시지는 반복 수있는 몇 가지 코드입니다. 나는 댓글이 뭔가를해야 할 경우, 당신도 그 값에 액세스 할거야 곳 이죠 또는 특정 노드와 일을. 을 시작하려면, 나는 내 커서가 처음 말 연결리스트의 첫 번째 요소를 가리 예정이다. 그리고 앞쪽에, 난 노드의 머리로 정의. 

내가 전에 언급 한 바와 같이, 자유롭게 정말 중요합니다. 당신은 당신이이 완료 한 후이 목록에 모든 요소를​​ 확보해야합니다 싶습니다. 더 이상 이러한 포인터 중 하나를 참조 할 필요가 없습니다 경우는, 당신은 그 포인터를 모두 확보되었는지 확인하고 싶습니다. 어떤 메모리 누수를 방지하려는 점에서 당신은 아주 조심했으면 좋겠어요. 포인터의 모든 노드 지점 거기에 그럼, 무료 한 사람 성급하게 경우 손실 될 것입니다. 그 약간 더 높은 말뚝하기 위해 사람의 예로 돌아 간다, 우선은이 경우에 그들은 괴물과 호수 위로 마우스를 가져 아르를 제외하고 사람들이 있습니다. 우리는 우리가 확보 할 때마다, 우리는 손실되지 않도록하려면 그리고 우리가 실제로 그들을 먹이기 전에 노드 가자. 예를 들어, 당신은 단순히 여기에서이 남자에 무료로 전화를 할 경우, 그런 다음 그는 해방 될,하지만이 사람들은 모두 후 손실 될 것입니다 그리고 그들은 흩어져서 표류하고 넘어 것입니다. 그래서 우리는 대신에, 우리는 나머지에 대한 링크를 유지하려면 있는지 확인하고 싶습니다. 목록에있는 첫 번째 요소를 가리키는 우리 헤드 포인터. 처음 사람을 고정 로프처럼 가지입니다. 귀하가 무료 때 여러분이 무엇을해야 할 수도 있습니다 어떤 목록이입니다 - 먼저 첫 번째 요소를 확보하려는 경우, 당신은 임시 포인터를 가질 수 그 점은 첫 번째 요소는 몰라도합니다. 그럼 당신은 임시 포인터가 여기 포인팅 있습니다. 이렇게, 우리는 첫 번째 노드의 보류가 있습니다. 그리고, 이후 우리는 첫 번째 노드 자유 로워지기를 간다는 걸 알고 그러면 우리는이 줄이 앵커, 우리의 머리를 이동할 수 있습니다 실제로 첫 번째를 가리키는 어떤 가리합니다. 그래서 머리는 실제로 지금 두 번째 요소로 지적했다. 이제 우리는 temp에 저장됩니다 어떤 자유롭게 허용하는 그래서 우리는 우리의 목록에있는 다른 노드의 모든 위험없이 그를 지울 수 있습니다. 이 작업을 수행 할 수있는 또 다른 방법은있을 수 때마다 당신은 목록의 마지막 요소를 공짜로 그들이 보장하기 때문에 어떤 점을 지적 할 수 없습니다. 그래서 그냥 다음이 한 후 무료로 이건, 무료이 하나를 해방 수 있습니다. 확실히 작동하지만 때문에 연결 목록의 성격에 의해, 약간 느린입니다 우리가 바로 마지막 하나에 점프 할 수 없습니다. 우리는 연결리스트의 각 요소를 통과해야 그 하나가 NULL을 가리키고 있는지 여부를 확인, 모든 시간을 확인 그리고 일단, 그 후 무료로 끝을 도달합니다. 이 과정을 수행 할 경우, 사실 여기에 확인됩니다 그것을 자유롭게, 여기에 알아보고 확인, 다음, 그것을 자유롭게 여기 알아보고 확인, 돌아가는 여기에 체크, 다음 자유롭게. 그건 시간이 좀 더 걸립니다. 그래. 

[학생]은 마지막에 출구 포인터를 저장하는 연결 목록을 만들 수 있을까? 그건 확실히 가능합니다. 질문을 반복하려면, 그것은 연결리스트 구조를 가지고 할 수 있습니다 이 연결리스트의 마지막을 가리키는 포인터를 가지고 같은? 그게 가능한지 말, 당신의 연결 목록에 무언가를 삽입 할 때마다 할 그처럼 그 포인터 물건을 업데이트해야합니다. 당신은 예를 들어, 노드 * 꼬리을 얻을 수 있습니다. 그러나이 기능을 구현 할 때, 당신은 무역 오프 생각해야 좋아 몇번이 이상 반복해야하는 건가 얼마나 어려운가 꼬리를 추적뿐만 아니라 머리를 유지 될 것입니다 뿐만 아니라 내 반복자, 그와 같은 것. 그 있습니까 -? >> [학생] 그래. 은 가능하지만 디자인 결정의 관점에서, 당신은 옵션을 무게해야합니다. 

다음은 연결리스트의 모든 요소를​​ 자유롭게 허용 코드의 골격입니다. 다시 말하지만, 난 연결된 목록을 통해 반복되어 있기 때문에, 나는 커서 어떤 종류의를 원하는거야 또는 반복기. 커서가 NULL 될 때까지 우리는 반복하고 있습니다. 귀하의 커서가 NULL 인 경우 반복하고 싶지 않아 그 목록에 아무것도 없다고 있다는 것을 의미 때문입니다. 그래서 나는 여기있는 임시 노드 *을 내 생각대로 지적하면, 내 목록의 첫 번째 그럼 내가 미리 1 필자가 임시 저장소에 있던 어떤 무료로 내 커서를 이동합니다. 

이제 우리는 링크 된 목록에 삽입에 있습니다. 내 링크 목록에 3 개의 노드를 가지고 있고, 간단한 경우로하자의 우리는 연결리스트의 끝 부분에 다른 노드를 삽입 할 위치. 이를 위해 우리가 할 모든은 우리가 통과 할거야 연결리스트의 현재 끝이 어딘지 찾으려면 NULL을 가리키고 중 노드 있도록 - 그게이 하나 - 그리고 말은 사실이 하나는 마지막 노드가 될 일이 아니; 우리는 실제로 다른 하나거야. 그래서 우리는 우리가 삽입하는 무엇이든이 현재 한 점을 얻을 수 있습니다. 그래서 지금이 빨간 사람이 여기에 연결리스트의 마지막 노드가됩니다. 그리고 연결리스트의 마지막 노드의 특성은 NULL을 가리키는 것입니다. 그럼 우리가해야 할 것입니다 것은 NULL이 붉은 사람의 포인터를 설정합니다. 가. 

그러나 우리는 두 번째와 세 번째 사이에 노드를 삽입하려면 어떻게 원한다면? 우리가 있는지 싶어서 하나는 매우 간단 아니라는 것을 우리는 연결리스트의 노드를 놔하지. 우리가해야 할 것은 우리가 각 사람에게 자신을 고정되었는지 확인합니다. 예를 들어,이 두 번째 전화가 보자. 당신이 말한 경우 두 번째는 지금이 새로운 하나를 가리키는 그리고 당신은이 남자가 손실 될 거라고 다음, 거기에 포인터를 만들어 그에게 어떤 링크가 없 거든. 대신 - 다시 이걸 그렸됩니다. 내 예술적 능력을 요. 우리는 우리가 직접 새로운 하나에 2를 연결할 수 알아요. 우리는 마지막에 개최 있는지 확인해야합니다. 우리가 할 할 수도 있습니다 임시 포인터하는거야 에 추가 할거야 요소. 그래서 우리는 거기에 임시 포인터가 있습니다. 우리가이 셋째 하나의 트랙을 유지하고 있는지 알고 있기 때문에, 2 지금 우리의 새로운 하나에 연결할 수 있습니다. 그리고이 새로운 붉은 사람이 2 ~ 3 될 것입니다 경우, 그 다음에는 그 사람의 포인터가 가리 키도록거야? >> [학생] 온도. 온도. 그래. 그럼이 빨간 사람의 다음 값은 temp 될 것입니다. 당신은 링크 된 목록에 삽입 할 때, 우리는 수 본 쉽게, 임시 배열을 생성하여 마지막에 뭔가를 추가 또는 우리는 우리의 배열의 중간에 무언가를 추가하고자 할 경우, 그때가 더 주변 셔플 링이 좀 걸릴 것입니다. 당신이 원하는 경우 예를 들어, 정렬 연결된 목록을 그리고 당신은 그런 비용과 혜택을 무게 가지해야 당신이 정렬 배열을하고 싶으면 그 말은 당신이에 삽입되는 그 때마다 의미하기 때문 그것은 시간이 좀 더 걸릴 거예요. 귀하 께서 나중에 원하는 경우에는, 우리가 찾을 수 있습니다처럼, 원하는 것 당신은 모든 순서입니다 알고있는 경우 연결된 목록을 검색 한 다음이 쉽게 될 수 있습니다. 그럼 당신은 그 비용과 혜택을 체중 할 수 있습니다. 

연결리스트에 삽입하는 또 다른 방법은 목록의 처음에 삽입하는 것입니다. 우리 마을은 우리 앵커를 그릴 경우 -이 우리의 머리입니다 - 그리고이 사람들은, 그것을에 연결 한 그리고 우리는 처음에 삽입 할 새 노드가 그리고 우리가해야 할 수 있습니다? 단지, 파란색에 빨간색을 연결하려는 말은 잘못 될 것을 그 첫 번째이기 때문에? 무슨 일이 일어날까요? 이 세의 모든 길을 잃지 것입니다. 그래서 우리는 그렇게되고 싶지 않아. 다시 말하지만, 우리는 임시 포인터 일종의가 필요하다는 걸 배웠어요. 이 사람에 임시 지점을 가지고 선택하자. 그런 다음 우리는 임시로 파란 1 점을 가질 수 있습니다 다음 파란색에 빨간색 가리 킵니다. 우리가 시각화 싶어서 여기 사람들이 사용하고있는 이유는 명에 연연 우리는 그들에게 링크를 확인하는 우리는 그와 같은 다른 손이나 뭔가를 놓아 전에. 

이게 바로 우리가 연결리스트의 감각을 가지고 - 우리가 링크 된 목록을 생성하는 방법을 그 노드에 대한 형식 정의로 구성에 대한 구조를 만들 그리고 우리가 그 연결리스트의 머리에 포인터를 가지고 있는지 확인하기 - 일단, 우리는이 우리는 배열을 탐색하는 방법을 알고 다양한 요소에 액세스, 우리는 삽입하는 방법을 알고 우리는 그들을 해방하는 방법을 알고 그런 다음에 우리가 맞춤법 오류로받을 수 있습니다. 늘 그렇듯이, 우리는 당신이 연결된 목록과 운영에 익숙해 것 질문 섹션을 와 같은 큐와 스택 등 다양한 구조. 그럼 우리가 잘못된 철자로 이동시킬 수 있습니다. 

잘못된 철자가 유통 코드에 중요한 파일의 몇 있습니다. 먼저 우리는 우리가 여기서 메이크이 표시 어떤 우리가 정말 전에 발생하지 않았습니다. 당신이 pset5 폴더 안에 보았다면, 당신은. H 파일이 표시 할 다음 두.의 C 파일을 갖고 있습니다. 이건 메이크가 수행하는 전에, 우리는 프로그램 이름 다음 확인 입력하고 것 그리고 우리는 컴파일러에 전달이 인수와 플래그를 모두 볼 것입니다. 무엇입니까 메이크는 것은 우리가 한 번에 여러 파일을 컴파일 할 수 있습니다 그리고 우리가 원하는 플래그를 전달합니다. 여기 우리는 헤더 파일이있다를 참조하십시오. 그럼 우리가 실제로 두 개의 소스 파일을 갖고 있습니다. 우리는 speller.c와 dictionary.c 있습니다. 당신이 원하는 경우 Makefile을 편집을 환영합니다. 당신의 결백을 입력하면 해당 여기서주의, 그때는 무엇을 아무것도 제거 실제로 그 핵심입니다. 당신이 세분화 오류가 있으면, 기본적으로 당신은 코어 덤프를 얻을. 그럼이 못생긴 작은 파일은 코어라는 디렉토리에 표시됩니다. 당신은 청소를 할 것을 제거하는 것이 좋습니다. 이 모든 exe​​ 파일을 제거합니다. O 파일. 

가 dictionary.h로 살펴 보자. 이것은 사전의 기능을 선언 있다고 말한다. 우리는 사전에 단어에 대한 최대 길이를 갖추고 있습니다. 우리는이 가장 긴 가능한 단어 될 것입니다 있다고합니다. 그것은 길이 45입니다. 그래서 우리는 그 길이를 초과하는 단어가 가지 않습니다. 여기 우리는 함수 프로토 타입을 갖추고 있습니다. 그게 우리가이 pset에 대해 뭘할지이기 때문에 우리는 실제 구현이 없습니다. 우리가 큰 파일을 상대하고 있기 때문에 그런데이 수행 것은 그리고 큰 규모의 기능은, 그건. H 파일을 가지고 유용 코드를 읽거나 사용하는 다른 사람이 무슨 일이 일어나고 있는지 이해 할 수 있도록. 이 해시 테이블 또는 그 반대의 짓을하면 아마 구현하고자하는 시도합니다. 그런 다음, 내 부하 기능을 말 것 실제 구현은 다를 것이다,이 프로토 타입은 변경되지 않습니다. 여기 주어진 단어가 사전에 있으면 true를 반환하는 확인했습니다. 그럼 우리가 기본적으로 사전 파일에 걸리는 부하를 가질 그리고 일부 데이터 구조에로드합니다. 우리는 전화했을 때, 사전의 크기를 반환하는, 크기가 , 거기에 얼마나 많은 단어 저장됩니다 그리고 이는 당신이 데리고 할 수있는 모든 메모리를 자유롭게, 언로드 당신의 사전을 활용하면서. 

가 dictionary.c를 살펴 보자. 우리는 지금은 단지 이러한 왜 그렇게 생각을 모두가 제외 dictionary.h 매우 유사 해 보입니다 것을 볼 수 있습니다. 그리고 그건 자네 일입니다. 결국,이 모든 코드와 speller.c를 작성됩니다. Dictionary.c는 실행할 때, 정말, 아무것도하지 않을 것이다 그래서 우리는 맞춤법 검사기의 실제 구현을 볼 수 speller.c으로 봐. 당신은이 코드의 편집을 할 않을거야하더라도 이 읽기 부하를 호출 할 때 이해하는 것이 중요합니다, 때 수표를 신고 할 거요, 그냥 이해를 밖으로 매핑 기능이 작동 방식을 볼 수 있습니다. 우리는 올바른 사용을 확인한다는 참조하십시오. 기본적으로 사람이 도전자를 실행하면,이은 선택 사항임을 나타냅니다 기본 사전 파일이있을거야 때문에 그들을 사전 파일에 통과하기. 그리고 그들은 맞춤법 검사 할 텍스트에 전달해야합니다. 시간이 rusage 계약은 나중에와 함께 pset의 일부를 처리합니다있는 때문 기능 맞춤법 검사기가 작동되고 있습니다뿐만 아니라 하지만 실제로 빠르게 할 려구요. rusage가 들어오고가는 곳 그리고 해당입니다 여기, 우리는 부하 인 우리 dictionary.c 파일 중 하나를 처음으로 호출을 참조하십시오. 성공시 사실, 실패시 허위 -로드는 true 또는 false를 반환합니다. 사전이 제대로로드되지 않은 경우 그럼, speller.c은 1을 반환하고 종료합니다. 제대로로드를 수행한다면, 다음 계속 할거야. 우리는 계속, 우리는 여기서 I는 / 일부 파일 O를 참조 이 텍스트 파일을 열어 처리 할 수​​있는 곳. 여기, 무슨 일이 있습니까 것은 텍스트의 모든 단어를 맞춤법 - 검사입니다. 따라서 speller.c 바로 여기서 뭐하는 지는 텍스트 파일에서 단어의 각을 이상 반복 is 그리고 사전에 확인. 여기, 우리는 수표 사실 여부를 반환하면 표시되는 맞춤법이 틀린 부울 수 있습니다. 단어가 사전에 실제로 경우 확인 사실 반환합니다. 그것은 단어의 철자가 잘못하지 않는 것을 의미합니다. 따라서 맞춤법이 잘못된 거짓이 될 것이며, 우리가 쿵를 산 이유는 표시입니다. 우리는 계속하고, 다음 단어를 맞춤법이 틀린 얼마나 많은 추적 파일에 있습니다. 그것은에 계속하고 파일을 닫습니다. 다음 여기, 당신이 가지고 얼마나 많은 맞춤법이 틀린 단어보고합니다. 마치 사전을로드하는데 얼마나 많은 시간을 계산합니다 어서, 어서 확인까지 얼마나 시간이 얼마나 그 크기를 계산했다 시간, 그 때문에 우리가에 가서 같이, 아주 작은이어야합니다 그리고 얼마나 시간이 사전을 언로드했습니다. 여기에 우리가 언로드 할 수있는 전화를 볼 수 위. 여기 크기를 확인하는 경우, 그러면 우리는 여기에서 사전의 크기를 결정합니다 크기로 호출이야. 짱이다. 

이 pset에 대한 우리의 작업은 사전을로드로드를 구현하는 것입니다 데이터 구조는 - 당신을 선택하든, 그건 해시 테이블이거나 시도 - 사전 파일의 단어. 그럼 당신은 사전에 단어의 수를 반환합니다 크기가 있습니다. 당신은 똑똑한 방법으로 부하를 구현하면 다음 크기는 매우 쉽게해야합니다. 그럼 당신은 주어진 단어가 사전에인지 확인되는 확인했습니다. 따라서 speller.c는 문자열에 전달, 그리고 당신은 여부 해당 문자열을 확인해야 사전에 포함되어 있습니다. 우리가 일반적으로 표준 사전이 표시, 하지만이 pset에 기본적으로 모든 사전은 어떤 언어로 통과 시켰습니다. 그래서 우리는 단지 단어가 안에 있다고 가정 할 수 없습니다. 단어 FOOBAR 우리가 인치 전달하는 특정 사전에 정의 할 수 있습니다 그리고 우리는 메모리에서 사전을 자유롭게하는 언로드했습니다. 

먼저, 해시 테이블 방법을 통해 가고 싶어요 우리가이 네 모든 기능을 구현하는 방법을 대한, 그리고, 우리가이 네 기능을 구현하는 방법에 방법을 시도 갈거야 그리고 몇 가지 일반적인 도움말에 대한 최종 이야기에 당신은 pset을 때 그리고 또한 사용할 수시킬 수있는 방법은 메모리 누수를 확인 Valgrind. 

가 해시 테이블 방법에 들어가 보자. 해시 테이블은 버킷리스트로 구성되어 있습니다. 모든 가치, 모든 단어는 이러한 버킷 중 하나에 들어갈 예정이다. 해시 테이블은 이상적으로 균일하게 귀하가 전달되고 있는지를 이러한 값을 모두 배포 그리고 그런 다음 그 통에서 그들을 채 웁니다 모든 버킷 거기에 값을 균등에 대해이 있습니다. 해시 테이블의 구조는, 우리는 연결된 목록의 배열을 갖추고 있습니다. 그 값이 속한 위치가 가치가 통과 할 때 우리가 할 것은, 우리는 확인 어떤 양동이가에 속해 있으며 해당 버킷에 연결된 연결 목록에 넣습니다. 여기 내가 가진 것은 해시 기능입니다. 이 정수 해시 테이블입니다. 따라서 첫 번째 버킷에 대한, 10 아래 정수는 첫 번째 버킷으로 이동합니다. 모든 10 위 정수하지만 아래에있는 두 번째로 20 가자, 그리고 등등 등등. 저를 들어, 각 버킷이 숫자를 나타내는 수 있습니다. 그러나 예를 들어, 50에 통과 했어요. 처음 세 번호가 10의 범위를 포함하는 것처럼 나타납니다. 하지만 내 해시 테이블은 정수의 종류에 취할 수 있도록하려면 그래서 나는 마지막 버킷에 30 위의 모든 번호를 필터링해야합니다. 그리고 그때 그 불균형 해시 테이블의 일종 될 것입니다. 반복하지만, 해시 테이블은 버킷 배열입니다 곳마다 양동이는 링크 된 목록입니다. 모든 값이 어디로 가는지 그리고 그로 전환하는 양동이를 결정하기 위해, 당신은 해시 함수라는 것을 원하는거야 다음 값을 소요하고이 값이 특정 양동이에 해당 말합니다. 입이 예에서 위, 제 해쉬 함수는 각 값을했다. 그것은 10보다 적습니다 여부를 확인 했어요. 만일 그랬다면, 그것은 첫 번째 양동이에 넣어 것입니다. 마치 20 명 미만인지, 아니면 확인 사실이라면 두 번째로를 게재, 수표가 다음 30 이하, 그리고 있다면이 세 번째 양동이에를 게재 그리고 모든 다른은 네 번째 버킷에 떨어진다. 당신이 값을 가지고 있으므로 때마다 당신의 해쉬 함수 해당 버킷에 해당 값을 배치합니다. 해쉬 함수는 기본적으로 당신이 얼마나 많은 양동이 알아야합니다. 귀하의 해시 테이블 크기, 당신이 가진 버킷 수, 즉, 당신이 결정하기 위해, 여러분에게 달려 있습니다 고정 된 숫자 될거야 하지만 고정 된 숫자가 생길거야. 모든 키에 맞춘 양동이를 확인하는 것이에 의존됩니다 해쉬 함수는 자 이 균일하게 분포되도록. 이 연결리스트의 우리의 구현, 해시 테이블에있는 모든 노드와 마찬가지로 실제로 형 숯불을 것입니다. 그래서 우리는, 단어라는 문자 배열하고 다음 노드에 다른 포인터를 가지고 어떤이 연결 목록이 될거에요 있기 때문에 의미가있다. 우리가 목록을 연결했을 때 기억 나는 머리라는 노드 * 한 그 연결리스트의 첫 번째 노드를 가리키는되었습니다. 그러나 우리의 해시 테이블에 대한, 우리는 여러 연결리스트를 가지고 있기 때문에, 우리가 원하는 건 우리가 해시 테이블처럼되고 싶지는 "양동이 무엇입니까?" 양동이, 그냥 노드 포인터의 목록입니다 그래서 통에있는 모든 요소는 실제로 해당 연결리스트를 가리키는됩니다. 이 설계도로 돌아가려면, 당신은 양동이 자체가 화살표 것을 볼 수 하지 실제 노드. 해시 기능 중 하나 필수 속성은 사람들이 결정 있다는 것입니다. 즉, 때마다 해시 숫자 2, 그 항상 같은 양동이를 반환해야합니다. 따라하면, 해쉬 함수로가는 모든 단일 값, 같은 인덱스를 얻을 수 있습니다. 당신의 해쉬 함수는 배열의 인덱스를 반환합니다 그래서 이 값은 어디에 있을까요. 내가 전에 언급 한 바와 같이, 버킷 수는 고정되어 그래서 당신이 반환 색인은 버킷의 수보다 작아야합니다 하지만 0보다 큰. 우리가 단순히 하나의 연결리스트의 해시 기능을 가지고 이유 또는 하나의 배열은 우리가 가장 쉽게 특정 섹션으로 이동 할 수 있도록 할 것입니다 우리는 가치의 특성을 알고있는 경우 - 대신 전체 전체 사전을 검색해야하는, 그것의 특정 섹션으로 이동할 수있는. 귀하의 해쉬 함수, 그 이상적으로 고려한다 각 버킷은 약 키의 같은 번호가 있습니다. 해시 테이블은 연결 목록의 일련의, 때문에 다음 링크 목록 자체가 하나 이상의 노드를 갖게 돼있다. 앞의 예에서, 그들은 동등하지 못했습니다 경우에도 두 개의 다른 숫자, 해시 때, 같은 인덱스를 반환합니다. 그래서 단어를 처리 할 때 하나의 단어를 해쉬 때 다른 단어와 같은 해시 값 것이다. 우리가 해시, 한 노드가있을 때 즉, 우리가 충돌 부르는거야 그 양동이에 링크 된 목록이 비어 있지 않습니다. 우리가 전화를하는 기술은 프로빙 선형 당신은 연결리스트로 가서 해당 노드를 삽입 할 위치를 찾을 수있는 곳 다음 당신은 충돌이 때문입니다. 당신은 여기 트레이드 오프가있을 수 있습니다 것을 알 수 있습니다? 당신은 아주 작은 해시 테이블, 양동이의 매우 작은 번호를 사용하면, 다음은 충돌을 많이 할 겁니다. 하지만 당신은 매우 큰 해시 테이블을하는 경우 당신은 아마, 충돌을 최소화 할거야 하지만 매우 큰 데이터 구조 될거야. 그와 함께 무역 오프가있을거야. 그럼 당신은 pset을 때, 주위를 재생하려고 어쩌면 작은 해시 테이블을 만드는 사이 하지만 그것이 다른 요소를 탐색하기 위해 좀 더 걸릴 것 알면서도 그 링크리스트의. 

어떤 부하가하려는 것은 사전의 모든 단어를 통해 반복합니다. 이 사전 파일에 대한 포인터에 전달합니다. 그래서 당신은 당신이 pset4에 마스터하는 I / O 함수 파일의 이점을 데려 갈거야 그리고 사전의 모든 단어를 이상 반복합니다. 당신은 새로운 노드가 될 수있는 사전의 모든 단어를 원하는 그리고 당신은 사전 데이터 구조의 내부 노드들 하나 하나를 게재 할거야. 당신이 새로운 단어를 때마다, 당신은이 노드가 될거야 알고. 그럼 당신이 가지고있는 모든 새 단어에 대한 노드 포인터를 곧바로 가서 malloc 할 수 있습니다. 여기 내 노드 포인터 new_node에 전화를하고 무엇을 mallocing 겠어? 노드의 크기입니다. 사전이 실제로 저장되기 때문에 다음 파일의 실제 문자열을 읽을 수 다음 단어와 우리가 활용 할 수있는 새 줄에 의해 , 함수 fscanf입니다 상기 파일은 우리가에 전달하고있는 사전 파일입니다 그래서 문자열의 파일을 검색하고 마지막 인자에 장소 그 문자열입니다. 당신은 우리가 위에 가서 강의 중 하나 다시 기억하는 경우 와 가지, CS50 라이브러리에 다시 레이어를 벗겨 우리가 fscanf의 구현을 보았다. fscanf로 돌아가려면 우리는 우리가 읽는하고있는 파일이 우리는 그 파일의 문자열을 찾고, 그리고 나서 우리는에을 배치하고 new_node가 노드 포인터이기 때문에 여기서 내가 new_node -> 단어를 가지고 하지 실제 노드. 그럼 제가 new_node을 말하려는 것은, 제가이 가리키는 있다는 노드에 가고 싶어 다음 단어에 해당 값을 지정한다. 우리는 그 단어를 타고 해시 테이블에 삽입하고 싶습니다. 우리가 노드 포인터를 new_node 한 거라고 생각 우리는 그 노드의 주소가 뭔지 알고 싶어 갈 거라서 우리는 때문에 구조체의 노드 자체의 구조, 안에 그것을 삽입 할 때 사람들이 새 노드에 대한 포인터를 가지고 있다는 것입니다. 그래서 가리하려고 해당 노드의 주소가 뭐야? 그 주소는 new_node 될 것입니다. 그 말이 돼, 왜 우리는 노드가 아닌 노드로 *를 new_node하는거야? 좋아,. 우리는 단어가 있습니다. 이 값은 new_node -> 단어입니다. 우리가 입력하고자하는 사전에서 단어가 포함되어 있습니다. 우리는 그 문자열에 우리의 해시 함수를 호출하려면 그래서 우리가 원하는 것은 우리 해쉬 함수는 문자열에서 소요하고 우리에게 정수를 반환하기 때문에 그 정수는 색인에 딕셔너리 그 양동이를 나타내는 인덱스입니다. 우리는 색인을 먹고 다음 해시 테이블의 인덱스로 이동 다음 new_node에서 노드를 삽입하는 그 연결리스트를 사용합니다. 그러나 귀하의 노드를 삽입하기로 결정 기억 당신이 그것을 정렬 할 경우에는 중간에 있는지 여부를 또는 시작이나 끝 부분에, 당신의 마지막 노드가 항상 NULL을 가리키는 있는지 확인 우리 연결리스트의 마지막 요소는 어디에 우리가 알고있는 유일한 방법이야 때문입니다. 

크기는 사전의 단어의 수를 나타냅니다 정수 경우는, 다음이 작업을 수행하는 방법 중 하나는 크기가 호출 될 때마다 그 우리는 우리의 해시 테이블에있는 모든 요소 통과 다음 해시 테이블 내의 모든 링크 목록을 반복 다음 1의 카운터 1 증가, 그 길이를 계산합니다. 물론 크기가 호출 될 때마다, 그 시간이 오래 걸릴 거예요 우리가 매일 연결리스트를 탐색 선형 될거야 때문입니다. 님이 내가 전달하는 방법을 많은 단어를 추적 대신, 그것은 훨씬 쉽게 될거야 귀하의로드 함수 내에서 카운터를 포함 그래서 경우 필요에 따라 업데이트 한 다음 카운터 즉, 당신은 전역 변수로 설정 한 경우, 크기에 액세스 할 수 있습니다. 그래서 크기가 단순히 할 수있는이 한 줄에, 그냥 카운터 값을 반환 이미 부하의 처리 사전의 크기. 그건, 내가 말 할 때 도움이 방식으로 부하를 구현하는 경우 제 말은 그게 그리고 크기는 매우 쉽게 될 것입니다. 

이제 우리는 확인하게. 이제 우리는, 입력 텍스트 파일에서 단어를 다루고 있습니다 그래서 우리는 그 입력 단어 여부를 모두 확인 할 것 사전에 여부 실제로 있습니다. 스크램블와 마찬가지로, 우리는 사건 무감각 할 수 있도록하고 싶습니다. 여러분, 저 사람들이 혼합 된 경우에 있는데도의 모든 단어가 통과되었는지 확인하려면 문자열 비교를 사용하여 호출 할 때 같습니다. 사전 텍스트 파일에있는 단어는 실제로 모두 소문자입니다. 또 다른 한가지는, 당신은 모든 단어가 모든 문자열에 전달한다고 가정 할 수 있다는 것입니다 알파벳 또는 아포스트로피를 포함 하나가 될 것입니다. 아포스트로피는 우리 사전에 유효한 단어가 될 것이다. 당신은 아포스트로피 S와 얘기를한다면, 그건 당신이 사전에 실제 합법적 인 단어 그건 당신이 해시 테이블에있는 노드 중 하나가 될거야. 단어가있는 경우에 작동 확인, 다음은 우리의 해시 테이블에 있어야 있어요. 단어가 사전에 있으면 다음 사전의 모든 단어는 해시 테이블에 그러니, 해시 테이블에서이 단어를 찾아 보자. 그 이후 우리는 해쉬 함수를 구현 알고 모든 고유 단어가 항상 같은 값으로 해시되는 등, 그리고 우리가 알고있는 그 대신 우리의 전체 해시 테이블을 통해 검색의, 우리는 실제로 그 단어가 속해야하는 링크 목록을 찾을 수 있습니다. 이 사전에 있다면, 지금 그 양동이에있을 것입니다. 단어에 전달 우리 문자열의 이름 인 경우 우리가 할 수있는 일, 우리는 해시 할 수있는 연결 목록에서 단어와 모습 딕셔너리의 값이 [해시 (단어)]에서. 여기에서 우리가 할 수있는 것은, 우리가이 단어를 검색 할 노드의 작은 하위 집합하는거야 그래서 우리는 연습에서 이전의 예를 사용하여 링크 된 목록을 탐색 할 수 있습니다 다음, 커서가 가리키는 곳에 문자열이 단어에 비교 전화 그 단어, 이러한 비교 있는지 확인하십시오. 귀하의 해쉬 함수를 구성하는 방식에 따라, 이 정렬되는 경우, 당신은 허위 조금 일찍 돌아올 수있을 가 정렬되지 않은가 있으면, 다음은 연결 목록을 가로 지르는 계속 하시겠습니까 당신은 목록의 마지막 요소를 찾을 때까지. 그리고 당신은 아직도 당신이 연결리스트의 마지막에 도달 한 시점에 단어를 발견하지 않은 경우, 귀하의 단어가 사전에 존재하지 않는다는 것을 의미한다, 그리고 그 단어가 잘못되었습니다 그리고 수표는 FALSE를 반환해야합니다. 

우리가 malloc'd 한 노드를 모두 확보하려는 이제 우리는, 언로드 온 그래서 무료로 우리 해시 테이블의 내부 노드의 모든. 우리는 연결 목록과 그의 노드의 모든 자유의 전부를 반복 할거야. 우리가 링크 된 목록을 확보 어디에 예를 연습 위 보면, 다음은 해시 테이블의 모든 요소에이 과정을 반복 할 것입니다. 그리고, 연습의 끝 부분이 이상 갈거야 하지만 Valgrind가 제대로 해제 한 경우 당신이 볼 수있는 도구입니다 당신이 malloc'd 또는 malloc'd 한 무엇, 다른 포인터 한 모든 노드. 우리가 버킷 유한 번호가있는 그 친구는, 해시 테이블입니다 그리고 값을 가지고 다음 특정 양동이에 그 값을 할당합니다 해쉬 함수. 

이제 우리는 시도에 있습니다. 이처럼 보이는 시도, 게다가 예를 그릴 수 있습니다. 기본적으로, 당신은 잠재적 인 문자의 배열 전체가 그리고 때마다 당신은 단어를 구성하는 그 편지는 가능성의 넓은 범위 사전에 연결할 수 있습니다. 어떤 단어들​​은, C로 시작하지만 계속 진행 하지만 다른 예를 들어, O를 계속합니다. trie 그 단어의 가능한 조합을 모두 표시하는 방법입니다. trie는 단어를 구성하는 문자의 순서를 추적 것입니다, 필요한 경우 하나의 문자는 문자의 배수에 의해 후속 될 수있는 경우, 해제 분기, 그리고 마지막에 그 단어가 유효 여부 각 지점에 표시 당신이 단어 MAT를 철자하는 경우, 내가 그렇게 생각하지 않는다 MA는 유효한 단어이지만, MAT입니다 때문입니다. 그리고 당신의 trie에, 그것은 MAT 후에 실제로 유효한 단어 것을 나타냅니다 것입니다. 우리 trie에있는 모든 노드가 실제로 노드 포인터의 배열을 포함하는 것입니다 우리는, 특히 그 노드 포인터의 27 할거야 알파벳의 모든 문자뿐만 아니라 아포스트로피 문자 한. 그 배열의 모든 요소는 그 자체가 다른 노드를 가리 예정이다. 해당 노드 그 이후로 아무 것도없는 경우 NULL이며,면 그러면 우리는 그 단어 순서에 더 이상 문자가 없다는 것을 알아요. 그 노드가 NULL이 아닌 경우 그러나, 저 문자 순서에 더 많은 글자가 있다는 것을 의미합니다. 그리고 게다가, 모든 노드는 단어 나하지의 마지막 캐릭터 있는지 여부를 나타냅니다. 

가 trie의 예에 가자. 우선이 배열의 27 노드위한 공간을 갖추고 있습니다. 나는 단어 BAR가있는 경우 - 나는 단어 BAR를 내가에서 해당을 삽입 할 경우는, 첫 글자는 내 trie가 비어 있다면, B입니다 B는 알파벳의 두번째 문자이기 때문에이 색인에 여기에 넣어 선택 겠어. 여기 B를 가졌어요. B는 모든 가능한 문자의 또 다른 배열로 가리키는 노드가 될거야 편지 B. 후 수행 할 수있는 이 경우, 나는 단어 BAR과 말하고, 그래서 여기 간다. 후, 정말 다음 문자 R, 자신의 조합에 대한 지금 포인트 있습니다 그리고 R은 여기입니다. BAR는 완전한 단어이기 때문에, 그때 다른 노드로 R 지점을 가야 겠어요 그 그 단어가 유효한지 말합니다. 해당 노드는 또한 노드의 배열을 갖게 돼 하지만 그건 NULL 일 수 있습니다. 그러나 기본적으로, 그것은 그런 식으로 계속 사용할 수 있습니다. 우리가 다른 예를 갈 때 즉, 좀 더 명백해질 것이다 그래서 그냥 참아. 이제 우리는 우리 사전의 내부 BAR가 있습니다. 지금 우리가 단어 Baz도가 있다고 가정 해 봅시다. 우리는 B로 시작, 우리는 이미 사전에 문자의 하나로서 B가 있습니다. A.을 따라 그게 바로 우리가 이미 있습니다. 하지만 대신에, 우리는 Z의 다음 수 있습니다. 그래서 우리 배열의 요소는 Z가 될 것입니다, 그리고 해당 하나는 단어의 또 다른 유효한 최종 가리 예정이다. 그래서 우리는, 우리가 다음 B를 계속하면 볼 수 B와 A.로 시작하는 단어에 대한 현재 우리의 사전에 두 가지 옵션이 있습니다 우리가 단어 FOOBAR를 삽입하고 싶어 해. 그럼 우리가 F.에서 항목을 보이게 될 것입니다 F는 전체 배열로 가리 노드입니다. 우리는 O로 이동, O를 찾을 거라고, O는 전체 목록 링크를 제공합니다. 우리는 B를 가지고 다음 계속 것입니다, 우리는이 할 다음 R. FOOBAR 때까지 그래서 FOOBAR 순회 모든 방법은 올바른 단어입니다. 그리고 다음이은 (는) 올바른 단어를 것입니다. 이제 사전에있는 다음 단어가 실제로 단어 FOO이라고 말을합니다. 우리는 F를 다음과 F. 어떤 말을하는거야? 사실 난 이미 O를위한 공간이 있습니다, 그래서 계속거야. 나는 새 하나를 만들 필요가 없습니다. 계속. FOO이 사전에 올바른 단어이기 때문에, 그때 나타내는거야 그 유효한지. 거기 내 순서를 중지하면, 그 말이 맞습니다 것입니다. 하지만 우리는 B에 FOO로부터 순서를 계속하는 경우 불과 FOOB을 가지고 FOOB는 말은 아니 겠지,하고는 유효한 하나로서 표시 않아. trie에서 모든 노드는 유효한 단어 나이 아니라, 여부를 나타내는 것 그리고 모든 노드는 27 노드 포인터의 배열을 가지고 자신의 노드를 가리 킵니다 그. 

다음은이 정의 할 수 방법에 대한 방법입니다. 우리는 노드 *의 머리를 한 곳에서 그러나, 해시 테이블의 예에서처럼 우리 연결리스트의 시작을 나타 내기 위해, 우리는 또한 원하는거야 우리 trie의 시작이 어디에 아는 몇 가지 방법입니다. 어떤 사람들은 전화가 나무를 시도하고, 루트에서 나오는 곳입니다. 그래서 우리는 우리의 트리의 루트는 우리가 접지 유지되었는지 확인하려면 우리 trie이있는 곳이면 어디든지합니다. 우리는 이미 가지에 갔어요 당신이 사전에 각 단어를로드 할 생각 수있는 방법입니다. 기본적으로 모든 단어를 당신의 trie를 통해 반복 할 거예요 우리가이 경우에 어린이라고 -와 아이들의 모든 요소가 있다는 자부심을 - 다른 문자에 해당하는, 당신은 그 값을 검사 할 거예요 문자에 해당하는 특정 인덱스에. 시저와 Vigenere로 모든 길을 생각 그래서, 알고 당신이 알파벳 색인으로 돌아지도의 종류 가능한 모든 편지 확실히 Z를 통해이 알파벳 문자에 매핑 꽤 쉽게 될 것입니다 하지만 불행하게도, 아포스트로피는 단어에서 인정 문자입니다. 내 말은, ASCII 값이 무엇인지 모르겠네요 그래서 거기에 당신은 당신이 처음 중 하나가 될 것인지 여부를 결정하는 인덱스를 찾으려면 또는 마지막, 당신은 거기에 하드 코딩 된 수표를해야합니다 그리고 그걸 쓸 예를 들어 지수 26 인치 그럼 당신은 [I] 아이들의 가치를 확인하는 중입니다 여기서 [I]에 해당하면에있어 어떤 편지합니다. 그 NULL이라면, 그 모든 가능한 문자는 현재도하지 않다는 것을 의미합니다 그 이전 순서에서 형태소 분석, 그래서 당신은 malloc 원하는거야 하고 새로운 노드를 만들고 거기에 그 아이가 [I] 포인트가 수 있도록 당신이 만들 - 우리가 사각형에 편지를 삽입 할 때 - 그 새 노드에 비 NULL을 가리 킵니다 어린이를 갖추고 있습니다. 그 NULL이 아닌 경우 그러나, FOO 우리의 예처럼 우리가 이미 FOOBAR을했을 때, 우리는 계속 우리는 어느 새 노드를 만드는 것이 아니라 단지 true로 is_word를 설정하지 않습니다 그 단어의 끝에서. 

그래서 예전에 여기 한 번에 모든 문자를 다루고 있기 때문에, 그 대신 계산하는 데에, 크기, 당신을 위해 쉽게 될거야 그리고 전체 트리를 통해 가서 내가 얼마나 많은 아이들이있어 계산 그리고 왼쪽에 있으며 오른쪽에 얼마나 많은 기억, 오프 분기 그리고 그런 식으로, 당신을 위해 더 쉽게 할 겁니다 당신은 당신이에 추가 얼마나 많은 단어를 추적하는 경우 당신은 부하를 처리 할 때. 그리고 해당 방법으로 크기는 크기의 전역 변수를 반환 할 수 있습니다. 

이제 우리는 확인 있습니다. 이전과 같은 표준, 우리가 경우 무감각을 허용 할 위치를. 뿐만 아니라, 우리는 문자열은 알파벳 문자 또는 아포스트로피있는 것으로 가정 아이들이 긴 27의 배열이기 때문에하면, 그래서 알파벳 플러스 아포스트로피의 편지의 모든. 당신이 원하는 일 거예요되어 있는지 여러분은 루트에서 시작하는 것이 좋습니다 루트가 포함 된 배열을 가리 키 때문에 단어의 가능한 시작 문자의 모든. 당신이 거기 시작할 거에요 다음 검사 할거야하면이 값이 NULL 여부입니다 값이 NULL 인 경우, 그 사전은 어떤 가치가없는 것을 의미하기 때문에 그 특정 순서에서 해당 문자가 포함되어 있습니다. 그게 NULL 경우, 저 사람이 단어가 바로 철자가 잘못되어 있다는 것을 의미합니다. 하지만 NULL이 아니라면 다음 당신은 계속할 수 있습니다 첫 글자가 단어의 첫 글자 수 있다는 말 그래서 지금은 두 번째 편지 그 순서, 내 사전 내에 있는지 확인하고 싶습니다. 그래서 첫 번째 노드의 아이의 인덱스에 가서 그 두번째 문자가 있는지 여부를 확인합니다. 그런 다음 그 순서가 유효 여부 확인이 과정을 반복 당신의 trie 내. 그 인덱스 지점에서 노드 아이들은 NULL을 할 때마다, 당신은 그 순서가 존재하지 않습니다 알고 하지만 당신은, 당신이 입력 된 한 단어의 끝 부분에 도달하면 다음 내가이 순서를 완료 한 지금 확인하려면 내 trie 내에서 발견 유효 여부 그 말은? 그리고 다음 그 확인하려는 그 때 그 순서를 발견 한 경우, 그리고 그 단어가 유효 여부 확인 하시겠습니까 때문에 우리가 FOOB 한 곳에서 제가 그린 다시 이전 경우에 기억 우리가 찾았으나 실제 유효 단어 자체가 없었던 올바른 순서했습니다. 

마찬가지로 당신이 trie의 노드를 모두 언로드 할 시도에 언로드하십시오. 미안 해요. 언로드에 우리가 모든 노드를 해제 해시 테이블과 유사, 우리는 또한 노드 모두를 해방하려는 시도 인치 언로드 실제로 정상에 바닥에서 가장 쉬운 일을합니다 이것들은 본질적으로 연결된 목록 때문입니다. 그래서 우리는 모든 값에 우리가 개최되었는지 확인하려면 그리고 명시 적으로 그들 모두 무료입니다. 당신은 trie로 작업하는 경우이하고 싶은 거에요 먼저 아래 무료로 가장 낮은 노드로 여행하는 것입니다 그리고 다음 아이들의 모든에 가서 다음 무료 모든 사람들의 가서하고 무료 등 trie 첫번째의 바닥 층을 다루는 같은 종류의 당신은 모든 해방 한 후 다음 정상을 갈. 이 재귀 함수는 쓸모가있을 곳의 좋은 예입니다. 일단 당신이 당신의 trie 하단의 레이어를 먹이기 그리고 당신은 그것의 나머지를 언로드 전화 당신이 모든 mini를 확보 있는지 확인하기 - 당신은 가지 그 작은 시도로 시각화 할 수 있습니다. 그래서 여기에 루트가 있습니다. 내가 그들 중 26 그릴 필요가 없도록 그냥 단순화거야. 당신이 있고, 다음이 단어의 순서를 나타냅니다 곳이 작은 서클의 모든 문자의 유효한 시퀀스 아르 편지입니다. 그냥 좀 더 계속 보자. 당신이하고 싶은 거예요 여기서하고 무료 이번 바닥 무료입니다 그리고 당신은 여기까지 상단을 아래에서 무료로이 하나가 공짜 전에 때문에 여기에 두 번째 수준의 같은 경우 무료로 뭔가 다음은 실제로 여기에이 값을 잃게됩니다. 당신이 먼저 바닥을 해방 있는지 확인하는 trie에 대한 언로드에 중요 이유입니다. 당신은 모든 노드에 대해 말되어 수행 할 수도 있습니다 무엇 나는 아이들을 모두 언로드하고 싶습니다. 

우리는 해시 테이블 방법뿐만 아니라 trie 방법에 대한 언로드 살펴 봤는데, 이젠 우리는 Valgrind보고 싶지거야. 다음 명령을 실행 Valgrind. 당신은 valgrind-V가 있습니다. 이 특정 텍스트를 주어진 도전자를 실행할 때 당신은 누출을 확인하고 도전자는 텍스트 파일에 걸릴해야하기 때문. 그래서 Valgrind는 프로그램을 실행하면 할당 얼마나 많은 바이트를 말해합니다 당신은 해방하고, 당신이 충분히를 풀어인지 알수있을 것이다 얼마나 많은 바이트 또는 충분히 무료 안, 여부 또는 때때로 당신은 무료로 노드처럼 그는 이미도 이상이없는 해방 된 수 있습니다 그리고 그것은 당신에게 오류를 반환합니다. 당신이 Valgrind 사용하는 경우, 그것은 당신에게 어떤 메시지를 줄 것이다 당신이 충분히 적은 충분 하나를 먹이기 여부를 나타내는 충분한 시간보다 이상을 사용하십시오. 

이 pset의 일부, 그것은 큰위원회에 이의를 제기하기위한 옵션입니다. 그러나 우리는 이러한 데이터 구조를 처리 할 때 이 데이터 구조는있을 수 얼마나 빨리 얼마나 효율적으로 볼 수 재미있어. 충돌이 많이에 해쉬 함수의 결과는 무엇입니까? 또는 데이터의 크기가 정말 크죠? 그것은 통과하기 위해 많은 시간이 걸립니까? 도전자의 로그에서는, 당신이로드하는 데 사용하는 얼마나 많은 시간을 출력 , 확인하는 크기를 실시하고, 언로드 그래서 그는 큰 보드에 게시되어 있습니다 당신의 친구들 경쟁 할 수있는 일부 직원들은 가장 빠른 맞춤법 검사기 권한이있는 사용자를 볼 수 있습니다. 나는 해쉬 테이블에 대해 유의하고자하는 한가지 우리가 생각 할 수있는 몇 가지 아주 간단한 해시 기능이 있다는 것입니다. 예를 들어, 모든 버킷 있도록 26 양동이를 가지고 있고, , 단어의 첫 글자에 해당하는 하지만 그건 매우 불균형 해시 테이블 될 겁니다 예를 들어, M로 시작보다 X로 시작 훨씬 덜 단어가 때문입니다. 도전자에 대해 갈 수있는 방법 중 하나는 당신이 다른 모든 기능을 얻으려면이며, 그런 다음 당신의 코드를 게재 할 수 있도록 간단한 해시 함수를 사용하여 그리고 돌아가서 해시 테이블과 정의의 크기를 변경합니다. 해시 함수를보기 위해 인터넷에 많은 자원이 있습니다 등이 pset에 대해 당신은 인터넷에 해시 기능을 연구하도록 허용 당신은 당신이 그것을 얻었나 인용했는지 확인하는 한 몇 가지 힌트와 영감을. 당신이 인터넷에서 찾을 수있는 몇 가지 해쉬 함수를보고 해석 할 수 있습니다. 다시 거기에, 당신은 사람이 trie를 사용한 경우 볼 수 있습니다 자신의 구현은 해시 테이블 여부보다 빠르고 여부. 당신은 큰 이사회에 여러 번 제출할 수 있습니다. 당신의 가장 최근의 항목을 기록합니다. 아마 넌 네 해쉬 함수를 변경 한 다음이 훨씬 빨리 실제로 걸 알았죠 또는 이전보다 느린 많은. 그건 재미있는 방법으로 약간입니다. 항상 1 또는 가장 느린 가능한 사전을 만들려고 노력이 직원도 있고 그래서는 ... 항상 재미 있어요. 

pset에 대한 사용은 선택 사항 사전과 도전자를 실행합니다 다음 필수 텍스트 파일입니다. 기본적으로 당신은 단지 텍스트 파일을 도전자를 실행하고 사전을 지정하지 않는 경우, 그것은 사전 텍스트 파일, 큰 하나를 사용 거에요 cs50/pset5/dictionaries 폴더 인치 그 하나는 100,000 이상의 단어가 있습니다. 또한 상당히 적은 단어가 작은 사전을 가지고 그 CS50 당신을 위해 만들었습니다. 그러나, 당신은 매우 쉽게 당신의 자신의 사전을 만들 수 있습니다 - 그냥 작은 예제에서 작동하려는 경우 예를 들어, 당신은 gdb를 사용하려는 경우에는 특정 값을 알고 귀하의 해시 테이블이에게 매핑 할. 그래서, 그냥 바, Baz도, FOO, 그리고 FOOBAR로 자신의 텍스트 파일을 삼을 수 텍스트 파일에서 해당을, 1 줄과 그 각각을 분리 그리고 그대로 만 어쩌면 1 개 또는 2 개의 단어가 포함 된 자신의 텍스트 파일을 만들 그래서 당신이 출력되어야 정확히 알고. 당신은 도전을 실행 빅위원회는 검사하는 샘플 텍스트 파일의 일부 전쟁과 평화와 제인 오스틴의 소설이나 그 비슷한입니다. 당신이 알아 시작하고 그래서 때, 자신의 텍스트 파일을 만들기 위해 많은 쉽게 그 밖에 단어의 몇 어쩌면 10이 포함되어 당신은 결과가 있어야 어떤 예측할 수 있도록 그리고 그 반대 제어 예를 들어 너무 더를 확인합니다. 그래서 우리는, 주변을 예측하고 그리기를 다루고 있기 때문에 다시 당신이 펜과 종이를 사용하는 것이 좋습니다하려면 정말이 하나가 당신을 도와거야 때문 - 당신의 trie의 모양을 해시 테이블이나 방법에 화살표를 그리기, 당신은 화살표가가는 일을 자유롭게 할 때, 당신은 충분히에 유지되고, 어떤 링크가 사라져 보이지 및 누수 된 메모리의 심연으로 떨어지고 있습니다. 그러니 제발, 당신​​이 코드를 작성하는에 도착도하기 전에 물건을 끌어 보시기 바랍니다. 당신이 일이 작업 할 방법을 이해하도록 일을 그립니다 때문에 그때 자네가 적은 포인터 muddles으로 실행됩니다 보장합니다. 

괜찮아요. 난 당신이 pset과 행운을 기원하고 싶습니다. 아마 가장 어려운 하나. 따라서 초기 시작하려고 할 일들을 그릴 상황을 그려, 행운을 비네. 이 연습 5 살. 

[CS50.TV]