>> ZAMYLA CHAN : 만들자 맞춤법 검사기.
당신이 speller.c를 열 경우, 당신은 볼 것이다 그것을위한 대부분의 기능
대해 텍스트 파일을 검사 사전은 이미 당신을 위해 만들어.
사전 텍스트로 전달합니다. / 철자, 신청하고 다른 텍스트 파일,
텍스트 파일을 확인합니다 사전에.
>> 이제, 사전 텍스트 파일이 포함됩니다 유효한 단어, 한 줄에 하나씩.
그런 speller.c은 부하를 호출합니다 사전 텍스트 파일에.
그것은라는 기능이 확인 전화 할게 입력 된 텍스트 파일에있는 모든 단어,
모든 맞춤법이 틀린 단어를 인쇄.
>> Speller.c은 또한 크기를 호출합니다 단어의 개수를 결정
사전 호출 언로드 메모리를 확보합니다.
speller.c는 방법을 추적합니다 많은 시간은 이들의 수행하는 데 사용됩니다
프로세스, 그러나 우리는거야 나중에 얻을.
>> 그렇다면 우리는 어떻게해야합니까?
우리는 dictionary.c를 입력해야합니다.
dictionary.c에서, 우리는 도우미가 로드 기능로드,
사전.
경우 검사 기능 점검, 주어진 단어는 사전에 있습니다.
함수의 크기는 수를 반환 사전에있는 단어.
그리고 마지막으로, 우리는, 언로드이있는 메모리에서 사전을 해제합니다.
>> 그래서 첫째, 부하를 해결 할 수 있습니다.
사전 텍스트의 각 단어에 대한 파일로드에서 그 단어를 저장할
사전 데이터 구조 당신의 선택, 하나의
테이블이나 트라이 해시.
나는 모두에 갈거야 이를 통해 도보.
>> 첫 번째의 해시 테이블에 대해 이야기하자.
당신이 10 당구 공을 가지고 있었고, 말 당신이 그들을 저장하고 싶었습니다.
당신은 양동이에 그들 모두를 넣을 수 있습니다, 당신은 특정을 필요로 할 때
공 번호, 당신은 하나를 것 한 번에 양동이
그 공을 찾고.
그리고 10 공, 당신은해야한다 합리적인에서 공을 찾을 수
시간.
>> 그러나 당신이 20 공을 가지고 있다면?
지금은 조금 더 오래 걸릴 수 있습니다.
어떤 약 100?
1000?
지금, 그것은 훨씬 쉬울 것입니다 경우 여러 개의 버킷을했다.
아마 공 하나의 버킷 번호가 0 구, 또 다른 버킷을 통해
공 (10)을 통해 번호 19, 등등.
>> 지금 당신은 특정을 찾기 위해 필요한 경우 공, 자동으로 할 수
하나의 특정 양동이로 이동 그 양동이를 통해 검색 할 수 있습니다.
그리고 각 버킷은 대략 10가있는 경우 공, 당신은 쉽게 검색 할 수
그것을 통해.
>> 이제, 우리는 다루고 있기 때문에 에 대한 사전, 하나의 버킷
사전에있는 단어의 모든 것 아마 너무 적은 버킷합니다.
그럼 해시 테이블에 대해 살펴 보겠습니다.
>> 버킷의 배열로 생각합니다.
이 경우, 버킷 우리의 연결된 목록입니다.
그리고 우리는 우리의 모든 단어를 배포합니다 이러한 다수의 연결리스트에있는 사이
해시 함수를 사용하여 편성 방법 우리에게 할 어떤
지정된 키 물통, 주어진 단어에 속한다.
>> 의 개략적이를 표현하자.
여기에 파란색 상자 값을 포함하고 빨간색 상자는 다른 값을 가리
포인터 쌍.
우리는이 쌍 노드를 호출 할 수 있습니다.
이제, 각 버킷은, 나는 말했다 이전에 링크 된 목록입니다.
연결리스트에서, 각각의 노드는 값을 가지고, 뿐만 아니라 포인터
다음 값.
>> 이제 연결된 목록을 처리, 그것은 매우 중요합니다 당신에게 그
어떤 링크를 잃지 않는다.
그리고 기억해야 할 또 다른 사실은 그 마지막 노드, 그것을 가리 키지 않는 경우
다른 노드는, 널 (null)를 가리 킵니다.
>> 그렇다면 우리는 C이 표시합니까?
우리는 여기에서 우리의 구조체를 정의합니다.
이 경우 값은 길이의 문자 배열.
길이가 길이 더하기 1 최대 어떤 단어의 길이, 플러스 1
널 (NULL) 종료.
그리고 우리는 포인터를 가지고 다음라는 또 다른 노드.
>> 그래서 작은 연결리스트를 만들어 보자.
첫째로, 당신은 당신의 노드를 MALLOC 할 것이다, 메모리 공간을 생성하는
노드 유형의 크기입니다.
다른 노드를 확인, 다시 mallocing.
>> 지금 당신은에 값을 지정하려면 단어, 우리는 노드 1의 화살표를 말할 수있다
워드는 "안녕하세요."와 동일 이 화살표 연산자 포인터를 역 참조
구조체의 변수에 액세스합니다.
이 방법은 우리 모두를 사용할 필요가 없습니다 점과 별 연산자.
>> 그래서 그때는 노드 2의 화살표 단어가 동일해야 "세계." 그리고 거기, 값은
내 노드에 채워집니다.
링크를 만들려면, 내가 노드 1을 전달합니다 다음 화살표를 해당 노드 별에 액세스
노드 포인터, 노드 2에 해당, 두 노드 2에 노드 1을 가리키는.
그리고 거기에 우리가 링크 된 목록이 있습니다.
>> 그래서 하나의 연결리스트,하지만 해시 테이블의 전체 배열
연결리스트.
글쎄, 우리는 같은 노드를해야합니다 이전 구조.
그러나 우리는 실제 해시 테이블을 원하는 경우, 우리는 단지 노드 포인터를 만들 수 있습니다
여기에 배열.
예를 들어, 크기 500.
>> 이제 통지, 무역있을거야 의 크기 사이의 쉬는
해시 테이블의 크기 링크 된 목록.
당신은 정말 높은 숫자가있는 경우 버킷은 다시 실행할 필요 상상
앞뒤에 줄 당신의 물통을 찾을 수 있습니다.
그러나 당신은 또한 적은 수의 원하지 않는 버킷, 우리는 위로이기 때문에
가지는 방법의 원래 문제 우리의 양동이에 너무 많은 공.
>> OK,하지만 어디서부터 우리의 공을 이동 하는가?
글쎄, 우리가 먼저 필요 오른쪽으로 공을?
그래서 모든에 대한 노드를 MALLOC하자 우리가 가지고있는 것을 새로운 단어.
노드 * new_node의 등호 의 malloc (sizeof 연산자 (노드)).
>> 우리는이 구조를 가지고 지금, 우리 함수를 사용하여 스캔 할
fscanf, 우리의 파일에서 문자열, 경우 즉로, 사전 파일의
new_node 화살표 단어, 어디 new_node 화살표 단어는 우리입니다
그 단어의 대상.
>> 다음으로, 우리는 해시 할 수 있습니다 해시 함수를 이용하여 단어.
해시 함수는 문자열을 사용 및 인덱스를 반환합니다.
이 경우, index가 마련되어 의 수보다 작아야
당신이 양동이.
>> 이제, 해시 함수, 당신은 시도 할 때 하나를 발견하고 다음 중 하나를 만들 수 있습니다
자신의 기억 그들이 결정해야합니다.
즉, 동일한 값이 필요한 것을 의미 같은 양동이에 모든 시간을 매핑
당신은 그것을 해시있다.
>> 그것은 종류의 라이브러리처럼.
당신은에 따라 책을 가지고 갈 때 저자는, 당신이 알고있는 선반이해야
이 선반 번호의 여부에 이동 하나, 둘, 또는 세.
그리고 그 책은 항상 속할 선반 하나, 둘, 또는 세 하나.
>> 그래서, 만약 new_node 화살표 단어가 당신의 사전에서 단어, 다음
해시 new_node 화살표 단어 것 우리의 인덱스를 제공
해시 테이블의 버킷.
그리고 우리는 그것으로 그 삽입합니다 로 표시된 특정 링크리스트
우리의 해시 함수의 값을 반환합니다.
>> 의는의 예를 살펴 보자 에 노드를 삽입
연결리스트의 시작.
헤드 나타내는 노드 포인터이면 링크의 시작
목록 및 new_node는 새를 나타냅니다 당신은 단지에 입력 할 노드
new_node 머리를 할당하는 잃을 것 리스트의 나머지 링크.
그래서 우리는이 작업을 수행 할 수 없습니다.
>> 오히려, 우리가 있는지 확인하려면 우리는 모든를 잡고 있음
우리의 프로그램에서 단일 노드.
그래서 실행 new_node 화살표 다음 등호 머리 다음 머리 new_node 동일
모든 유지됩니다 링크 및 손실되지.
>> 그러나 당신은 당신의 목록으로 무엇을하려는 경우 정렬 된 연결하는 데 있기 때문에, 우선 순위
목록은 쉽게 될 수 있습니다 그것을 나중에 검색?
음, 위해, 당신은 알아야합니다 어떻게 연결리스트를 탐색하는 방법.
>> 연결리스트를 탐색하기 위해,가 보자 역할을하는 노드 포인터, 노드 *
나타내는 커서, 어떤 당신은 시작에있어 노드
첫 번째 요소.
커서 때까지 반복하는 것은 우리가 할 수있는 null입니다 다음 특정 프로세스 및 수행
우리가 필요로 할 때 커서를 이동 커서 화살표 값을 사용.
>> 기억하십시오,이 같은 일이 역 참조, 스타 커서를 말
다음 사용하여 커서를 도트 연산자 값입니다.
따라서 할당함으로써 커서를 갱신한다 다음에 커서가 화살표로 커서.
>> 당신은 D가있는지는 확인 말 C와 E는 노드를 삽입하려면 사이에,
에 new_node의 D 지점이 다음에 커서입니다 노드 E,.
그리고, C, 커서가 다음 가리킬 수 D. 그 방법, 당신은 목록을 유지한다.
하여 링크를 분실하지 않도록주의 다음에 D 커서 화살표 이동
바로.
>> 괜찮아요.
그래서, 당신이 노드를 삽입하는 방법입니다 이들로, 부하 단어를있는로드
노드 및 그 삽입 당신의 해시 테이블에.
그래서 지금의이 시도를 살펴 보자.
>> 트라이에서, 모든 노드가 포함됩니다 노드 포인터, 모든 하나의 배열
알파벳의 편지 플러스 아포스트로피.
그리고 배열의 각 요소에 다른 노드를 가리 킵니다.
해당 노드가 널 (null), 그 편지의 경우 다음 문자의 될 수 없습니다
시퀀스의 모든 단어 때문에 모든 단어는 마지막의 여부를 나타냅니다
단어 나하지의 문자.
>> 의이 그림을 살펴 보자.
희망을 가지 것 조금 더 명확합니다.
이 그림에서 우리는 볼 만이 특정 문자와 특정 문자열
밖으로 나와되고있다.
그래서 당신은 어떤 경로를 따라 할 수 있습니다 그 경로는 모두에게 당신을 이끌 것입니다
다른 단어.
>> 그렇다면 우리는 C이 표시합니까?
음, 모든 노드가 지금해야 할 것입니다 있는지 여부를 나타내는 부울 값
그 노드의 끝 주어진 단어 나하지.
그리고 또한 배열을드립니다 노드 자식이라고 포인터와
그 중 27있을 것입니다.
그리고 당신이 또한 원하는 것, 기억 첫 번째 노드를 추적.
우리는 그 루트를 호출하는 것입니다.
>> 그래서 트라이의 구조입니다.
우리는 어떻게이 문제를 표시합니까 사전으로?
음, 모든을 위해, 단어를로드 사전에 나오는 단어, 당신이 원하는거야
트라이를 반복합니다.
그리고 아이들의 각 요소 다른 문자에 해당합니다.
>> 그래서 아이들을 값을 확인 내가 나타내는 인덱스 나,
편지의 특정 인덱스가 당신은 삽입 할 노력 중입니다.
음, 널 (null)의 경우에, 당신은 원하는 것 새 노드를 MALLOC와 아이들이
그 노드를 가리 킵니다.
>> null가 아닌 경우에, 그 것을 의미한다 주어진 지점, 즉 주어진
문자열은 이미 존재합니다.
그래서 당신은 단지로 이동합니다 새로운 노드를 계속합니다.
당신은 단어의 끝 부분이 있다면 그 당신은에로드하려는
사전에, 당신은 그것을 설정할 수 있습니다 true로에있어 현재 노드.
>> 그럼 삽입의 예를 살펴 보자 에 단어 "여우"우리의
사전.
우리가 시작 척 빈 사전.
첫 번째 편지, F는있는​​ 것 아이의 인덱스의 뿌리 다섯
아이들의 배열입니다.
그래서 우리는 그 안으로 삽입
>> 문자 O는 아이들에있을 것입니다 그 후 F. 지수 (15), 그리고 X
분기, 심지어 아래에있을 것입니다 O의 아이의 해제.
그리고 X는 마지막 문자이기 때문이다 단어의 "여우"그때에 갈거야
나타 내기 위해 그 녹색 색깔이 그것은 단어의 끝.
C에서, 그인가요에게 설정 될 것입니다 말씀은 참 값을 부울입니다.
>> 지금 만약에 당신이하고있는 다음 단어 에로드하면 단어 "foo는"인가?
글쎄, 당신은 더 이상 MALLOC 할 필요가 없습니다 F 또는 O를위한 공간 때문에
사람들은 이미 존재합니다.
하지만 foo는의 마지막 O?
그 하나는, 당신의 malloc해야합니다.
설정, 그것을위한 새로운 노드를 만들 true로되어있는 Word 부울.
>> 그래서 지금의 삽입하자 "개." 개는 것 뿌리의 인덱스 세 시작
어린이, D가되지 않았기 때문에 아직 생성.
그리고 우리는 비슷한 과정 등을 수행합니다 이전 문자열 개를 작성,
여기서 G는 녹색 있기 때문에 색이야 그 단어의 끝.
>> 이제, 우리는 "할"삽입 무엇을해야할까요?
음,이 강아지의 문자열, 그래서 우리는 더 이상 MALLOC 할 필요가 없습니다.
그러나 우리는 우리가했습니다 위치를 표시해야합니까 그 단어의 끝에 도달.
그래서 O는 녹색으로 표시됩니다.
하나 하나에 대해 그 과정을 계속 당신의 사전에있는 단어, 당신은했습니다
도 당신에 그들을로드 테이블 또는 트라이 해시.
>> speller.c을 위해 문자열을 전달합니다 이를 확인하기 위해 dictionary.c.
이제, 확인 기능이 작동합니다 소문자 구분에서.
즉, 즉, 대문자와 소문자 모두의 혼합
모든 사실을 동일시한다 (있는 경우) 그 조합에
사전.
또한 문자열이 있다고 가정 할 수 있습니다 알파벳 만 포함 할 것
문자 나 아포스트로피.
>> 그래서 당신이 확인하는 방법을 살펴 보자 해시 테이블 구조.
음, 단어가 존재하는 경우, 다음 해시 테이블에서 찾을 수있다.
그래서 당신은 찾을 것을 시도 할 수있다 관련 양동이에 단어.
>> 그래서 어떤 버킷 해당 단어가있는 것입니까?
글쎄, 당신은 수, 해당 인덱스를 얻을 것 물통, 그 단어를 해시하여
다음 링크 된 목록에서 검색, 전체를 통해 통과
문자열을 사용하여 연결리스트, 기능을 비교합니다.
>> 링크 된리스트의 끝이면 의미에 도달하는 커서
널 (null)에 도달, 다음 단어는 아니다 사전에서 찾을 수 있습니다.
그것은 다른 통에 수 없습니다.
그래서 여기, 당신이하는 방법을 볼 수 있습니다 하나를 갖는 사이의 트레이드 오프가 될
정렬 연결리스트 또는 정렬되지 않은 것.
하나는 동안 더 많은 시간이 걸릴 것입니다 검사 중 시간을로드 이상.
>> 어떻게에서 확인 할 수 트라이 구조?
우리는 아래로 여행을거야 트라이에.
입력 된 단어의 각 문자 우리는 확인하고 있는지, 우리는 그에게 갈거야
아이들의 요소를 해당.
>> 그 요소가 null의 경우, 그 수단 어떤 문자열이 없는지
우리의 입력 단어를 포함, 그래서 단어의 철자가 잘못되었습니다.
null가 아닌 경우에, 우리는로 이동할 수 있습니다 우리가하고있는 단어의 다음 문자
이 과정을 확인하고 계속 우리가 끝에 도달 할 때까지
입력 단어.
그리고 우리는 확인할 수 있습니다 인가요 단어에 해당하는 경우.
그것은 다음 큰 경우.
말씀이 맞습니다.
그러나 그렇지 않은 경우, 비록 그 문자열 트라이에 존재하는 단어입니다
맞춤법이 틀린.
>> 함수의 크기가 호출, 크기 단어의 수를 반환해야 함
당신의 주어진 사전에 데이터 구조입니다.
당신은 당신이 해시 테이블을 사용하는 경우 그래서 하나 하나를 통과 할 수 있습니다
하나 하나의 연결리스트 버킷 수를 계산
단어가 있습니다.
당신이 트라이를 사용하는 경우, 당신은 할 수 모든 null 이외의 통과
당신의 트라이의 경로입니다.
아니면 사전을로드하는 동안 에, 어쩌면 당신은 어떻게 추적 할 수 있습니다
당신이 안으로로드하는 많은 단어
>> speller.c는 검사 완료되면 사전 대하여 텍스트 파일, 다음
그것을 할 그리고 그것은 언로드를 호출 어디 당신의 직업이 무엇이든을 확보하는 것입니다
당신은 malloc으로 할당 한 것을.
그런 다음, 당신이 해시 테이블을 사용하는 경우 그래서 않도록 특히주의해야
아무것도 해제하지 않음으로써 메모리 누수 중간에 모든 잡고
당신은 무료로 전에 단일 링크.
>> 따라서 해시 테이블의 모든 요소에 대한 그리고 링크 된 목록의 모든 노드에 대해,
해당 노드를 무료로 할 수 있습니다.
당신은 어떻게 확보 가야합니까 연결리스트?
노드 포인터 커서로 설정 상순 헤드
연결리스트, 다음 커서 동안 null이 아닌, 당신은 임시을 설정할 수 있습니다
커서를 노드 포인터.
그런 다음 커서를 이동.
그리고 당신은 일시적으로 확보 할 수 있습니다 값 동안 계속 들고
그 후 모든 것을 제공합니다.
>> 당신이 트라이를 사용하는 경우?
그런 다음이 작업을 수행하는 가장 좋은 방법 매우에서 언로드 할 수 있습니다
아래에서 위로.
가능한 가장 낮은 여행으로 노드, 당신은 모든 포인터를 확보 할 수 있습니다
그 다음 어린이 및 역 추적 위쪽으로, 모두의 모든 요소를​​ 자유롭게
아이 배열의, 때까지 당신은 당신의 최고 루트 노드를 누르십시오.
여기에 위치를 재귀 편리합니다.
>> 당신이 아마 해제했는지 확인하려면 당신이 malloc으로 할당 한 모든 것을,
당신은 Valgrind의를 사용할 수 있습니다.
Valgrind의를 실행하면 프로그램이 실행됩니다 메모리의 바이트 수를 계산
당신이 사용하고했는지 확인하는거야 말하고, 그들 모두를 해제
당신이해야 할 수도 있습니다 곳 무료로 잊어.
Valgrind의 당신을 알려줍니다 그래서 일단 그 실행 당신에게 다음 진행을 준다
당신은 언로드를 완료했습니다.
>> 자, 당신은 팁을 몇 가기 전에 오프 및 구현 시작하여
사전.
나는 작은 전달하는 것이 좋습니다 것 당신은 테스트하려는 경우 사전
GDP와 함께 일하기 및 디버깅.
철자의 사용입니다. / 철자, 선택적 사전, 다음 텍스트.
>> 기본적으로에로드 큰 사전.
그래서 당신은 작은에 통과 할 수 있습니다 사전, 또는 어쩌면 확인하여
자신의 사용자 정의, 당신의 사전 당신의 텍스트 파일.
>> 그리고 마지막으로, 나는 또한 권 해드립니다 펜과 종이를 가지고 그릴
일하기 전, 중, 후의 당신은 당신의 모든 코드를 작성했습니다.
그냥 당신이 가지고 있는지 확인 그 포인터는 바로.
>> 나는 당신에게 행운을 기원합니다.
그리고 설정이 완료되면, 당신은 좋아 한 경우 큰 보드에 도전합니다
당신의 프로그램에 비해 얼마나 빨리 참조 반 친구들 '나는 격려
당신은을 확인합니다.
>> 그와 함께, 당신은 완료했습니다 철자의 PSET.
내 이름은 Zamyla이며,이 CS50입니다.