[음악 재생] 

ANDI 펭 : 섹션의 6 주에 오신 것을 환영합니다. 우리는 우리의 표준에서 이탈 화요일 부분 시간 이 아름다운 일요일 아침에 오후. 모든 주셔서 감사합니다 그 오늘, 그러나 진지하게 나를 합류 박수. 

그것은 꽤 큰 노력이다. 나는 거의 심지어 그것을하지 않았다 시간에,하지만 그것은 확인했다. 그래서 나는 당신의 모든 것을 알고있다 단지 퀴즈로 만들었습니다. 우선,에 오신 것을 환영합니다 그 레코드의 B면. 

둘째, 우리는 그것에 대해 이야기 할 것이다. 우리는 퀴즈에 대해 이야기 할 것입니다. 우리는 방법에 대해 얘기하자 당신은 클래스에서 일을하고 있습니다. 당신은 괜찮을거야. 나는 당신의 퀴즈에 대한이 여기의 끝에 당신, 그래서 너희들은 수행하려는 경우 , 그것을 완전히 좋아 보이는데. 

이렇게 빨리 우리가를 시작하기 전에 다음과 같이 오늘의 일정입니다. 당신이 볼 수 있듯이, 우리는있어 기본적으로 빠른 발사 데이터 구조의 모두를 통해 정말, 정말, 정말 빨리. 같은 그래서, 그것은되지 않습니다 슈퍼 인터랙티브 오늘. 그것은 단지 나 종류의 소리가 될 것이다 이것은 당신, 내가 당신을 혼동하는 경우, 내가 너무 빨리거야 경우, 알려주세요. 그들은 단지 다양한 데이터이야 구조 및 일부로 이에 대한 당신의 PSET의 이번 주, 당신은거야 그들 중 하나를 구현하도록 요청, 아마도 두 그들의 them-- 두 당신의 PSET에서. 좋아, 그럼 난 그냥에 갈거야 일부 발표로 시작합니다. 우리는 스택 및 더 많은 큐를 통해 갈거야 우리는 퀴즈 전에했던 것보다 깊이. 우리는 가서 연결합니다 다시, 한번 나열 보다 깊이에서 더 많은 것을 우리는 퀴즈 전에했다. 그리고 우리는 해시에 대해 얘기하자 테이블, 나무와 시도, 어떤 모든 PSET을 위해 매우 필요하다. 그리고 우리는 몇 가지를 통해 갈거야 pset5에 대한 유용한 정보. 

좋아, 그럼 퀴즈 0. 평균은 58 %였다. 그것은 매우 낮은, 그래서 너희들 모두 에 따라 매우 잘했다 그것으로. 

당신이 있다면 꽤 많이, 엄지 손가락의 규칙은 평균으로부터 표준 편차 이내 우리는 더 적은에있어 특히 이후 편안한 섹션, 당신은 완전히 괜찮아요. 당신은 트랙에있어. 인생은 좋은 것입니다. 

나는 생각하는 무서운 알고 나는이 퀴즈의 40 %처럼되었다. 나는이 클래스를 실패 할거야. 내가 당신을 약속, 당신은 아니에요 클래스를 실패 할 것. 당신은 완전히 괜찮아요. 

이상 가지고 사람들을 위해 평균, 감동, 감동, 같은, 심각하게 잘. 나는 나와 함께 그들을있다. 그들을 데리러 주시기 바랍니다 섹션의 끝에. 당신은 어떤이있는 경우 알려주세요 문제, 그들과 함께 질문. 우리는 당신의 점수를 추가하는 경우 잘못 알려. 

확인, pset5 그래서,이 정말이다 의미에서 예일에 대한 이상한 주 우리의 PSET이 때문이라고 포함 정오 수요일 늦은 날은, 그래서 사실이다 정오 화요일 이론적으로 인해. 아마 아무도 완료하지 정오 화요일에. 즉 완전히 괜찮아요. 우리는 근무 시간을 할거야 오늘 밤뿐만 아니라 월요일 밤. 그리고 모든 섹션이 주는 것 실제로 워크숍으로 전환 될, 그래서에서 팝업 주시기 원하는 섹션, 그들은 종류의 미니 PSET 수 있습니다 그에 도움 워크숍. 그래서 같은 이것은 유일한 부분이다 여기서 우리가 자료를 교육하고 있습니다. 다른 모든 부분은 집중 될 것이다 전용 PSET에 대한 도움말에. 네? 

청중 : 어디에 근무 시간은? 

ANDI 펭 : 영업 시간 오, 좋은 질문을 tonight--. 생각 근무 시간 오늘 밤 청록이나 풍경에 있습니다. 온라인 CS50을 선택하면 당신은, 근무 시간에 이동 스케줄이 있어야 그 그들 모두가 당신을 알려줍니다. 

오늘 밤 중 하나를 알고 또는 내일 청록색이며, 그리고 나는 우리가 가질 수있는 생각 다른 밤 풍경. 잘 모르겠 는데요. 좋은 질문. CS50에 확인합니다. 

관련 쿨, 질문 삼일 같은 다음에 대한 일정? 나는 다윗 같은 너희들을 약속 이 언덕의 정상입니다 말했다. 너희들은 거의있다. 그냥 세 일 이상. 거기에 도착하고 우리는 내려합니다. 우리는 좋은 CS-무료 휴식을해야합니다. 우리는 다시 올 것이다. 우리는 웹에 뛰어 것 프로그래밍 및 개발, 매우 재미있는 것들을 비교 다른하여 pset의 일부. 그리고 그것은 진정, 그리고 것 우리는 재미를 많이해야합니다. 우리는 더 많은 사탕을해야합니다. 사탕 죄송합니다. 나는 사탕을 잊어 버렸습니다. 그것은 거친 아침이었다. 그래서 사람들은 거의가 나는 너희들 정말 자랑 스럽습니다. 

좋아, 그럼 스택. 누가 잭에 대한 질문을 사랑 퀴즈에 자신의 옷? 아무도? 좋아, 괜찮아요. 

그래서 기본적으로 당신이 할 수 사진 잭, 여기이 사람, 옷을 사랑 스택의 상단에서, 그는에 그것을 다시 넣습니다 그 후 스택은 이루어집니다. 이런 식으로 그래서 그는 결코 지고있는 것 같다 하단에 그의 옷에 스택. 그래서이 종류의 설명 기본적인 데이터 구조 스택이 구현되는 방법. 

기본적으로, 생각 개체의 스택으로 스택 당신은 상단에 물건을 넣어, 어디 당신은 정상에서 그들을 팝업. 그래서 LIFO는 우리가 좋아하는 글자입니다 마지막으로, 첫 번째 아웃 use--합니다. 그리고 상단에 지속 스택 나오는 첫 번째입니다. 그리고 두 용어 우리는 연결하려면 그와 푸시와 팝이라고합니다. 때에 뭔가를 밀어 스택, 당신은 다시 그것을 팝업. 

그래서 나는이 가지 추측 당신의 사람들을 위해 추상적 인 개념 사람처럼보고 싶​​어 이것의 실제 구현 현실 세계에서. 얼마나 많은 당신이 에세이를 작성했습니다 아마 한 시간처럼 인해 전에 당신은 실수로 거대한 삭제 실수로 같은 그것의 덩어리? 그리고 무엇을 제어 할 우리는 그것을 다시 넣어 사용할 수 있습니까? 제어-Z, 그래? 제어 Z 때문에 배의 양 제어-Z는 나의 생명을 구했다고, 모든 시간을 내 엉덩이를 저장하고있다 즉 스택을 통해 구현입니다. 

본질적으로 모든 정보 즉, Word 문서에의 그것은 밀어 의지에 튀어됩니다. 그래서 기본적으로 때마다를 아무것도 삭제, 당신은 위로를 다시 팝. 그리고 다음에 다시해야하는 경우를 제어-C가 무엇 인 밀어 넣습니다. 그리고 실제 기능 방법 간단한 데이터 구조 일상 생활에 도움이 될 수 있습니다. 

그래서 구조체는 방법입니다 우리가 실제로 스택을 만들 수 있습니다. 우리는 다음 구조체를 정의 입력 우리는 아래에서 호출 스택. 그리고 스택 내에서, 우리는 두 개의 매개 변수를 가지고 우리는 본질적으로 조작 할 수 그래서 우리는 문자 스타 문자열 능력을 가지고있다. 

이하고있는 모든 것을 배열을 생성한다 우리는 당신이 원하는대로 저장할 수 이는 우리가 용량을 확인할 수 있습니다. 용량은 단지 최대 금액입니다 항목 우리는이 배열에 넣을 수 있습니다. INT 크기는 유지 카운터 얼마나 많은 항목의 트랙은 현재 스택. 그러므로 우리는, 추적 할 수 있습니다 두 스택 실제가 얼마나 큰 와, B, 어떻게 스택의 많은 우리가 원하지 않기 때문에 우리는 가득 우리의 능력이 무엇인지를 통해 오버 플로우. 

예를 들어,이 사랑스러운 그래서 문제는 퀴즈에 있었다. 기본적으로 우리가 어떻게 추진 할 스택의 맨 위에. 매우 간단하다. 당신이 그것을 보면, 우리는이를 통해 걸을 것이다. [들림] size-- 경우 때마다, 기억 에 액세스 할 구조체 내에서 매개 변수, 당신은 struct.parameter의 이름을. 

이 경우, S는 우리의 스택의 이름입니다. 우리는 크기에 액세스하려면 그것을, 그래서 우리는 s.size을한다. 크기가 아니기 때문에 너무 오래 용량 또는 한 동일 이 용량보다 적은 것에 따라, 하나 여기에 작동합니다. 

당신은 내부에 액세스하려면 스택의, s.strings 때문에, 당신은 그 새 번호를 넣어거야 당신은 거기에 삽입 할 것을. 그냥 우리가 원하는 것입니다 가정 해 봅시다 스택에 INT n을 삽입, 우리는 s.strings을 할 수 브래킷, s.size는 N 같습니다. 크기는 곳이기 때문에 우리 현재 스택에 우리는 밀어려고하는 경우에 거기에, 우리는 단지 액세스 크기가 어디에 있든, 스택의 현재의 충만, 우리는 그것에 INT의 N을 누릅니다. 그리고 우리는이 있는지 확인하려면 또한, N의 크기를 증가시키는 것 우리는했습니다의 그래서 우리는 추적 할 수 있습니다 스택에 추가로 일을했다. 이제 우리는 더 큰 크기를 가지고있다. 이 여기에 의미가 있는가 모두, 어떻게 논리적으로 작동? 그것은 종류의 빨랐다. 청중 : 당신은 가서 수 s.stringss.strings [s.size] 다시? ANDI 펭 : 물론, 그래서 무엇을 수행 우리에게 현재 s.size? 청중 : 그것은 현재 크기입니다. ANDI 펭 : 정확히, 그래서 우리의 크기에있다 현재 인덱스, 그래서 우리는 새로운 정수를 넣을 우리는 s.size에 삽입 할 것을. 말이 돼? s.strings 때문에, 모든 인은 어레이의 이름이다. 그것이 모든 액세스이며 우리의 구조체 내의 배열, 그래서 우리는 원하는 경우 그 인덱스로 N을 배치, 우리는 단지 그것을 액세스 할 수 있습니다 사용 브래킷 s.size. 시원한. 

좋아, 팝, 나는 그것을 밖으로 의사 너희들,하지만 비슷한 개념. 말이 돼? 크기가 크면 다음 제로보다 당신 당신이 뭔가를 먹고 싶어 알고 아웃 크기가 아닌 경우 때문에 제로보다 큰, 당신은 스택에 아무​​것도 없다. 

그래서 당신은 단지 실행할 이 코드는, 단지 수 갑자기 뭔가가있는 경우 팝업. 크기가 너무 크면 0이 아닌, 우리를 뺀 크기입니다. 우리는 크기를 감소 후 반환 그것 때문에 내부에 어떤입니다 터지는으로, 우리는 원하는 저장되어있는 어떤 액세스 스택 상부의 인덱스. 모든 것이 이해가? 내가 만든 경우 너희들은 이것을 쓰기 너희들은 그것을 쓸 수 있을까? 좋아, 너희들은 주위를 재생할 수 있습니다. 걱정은 당신이 그것을 얻을하지 않는 경우. 우리는 코드에 시간이 없어 그것을 밖으로 오늘 우리가했습니다 때문에 이러한 구조를 많이 가지고 통과하지만, 본질적으로합니다 의사, 매우, 매우 유사 밀어. 그냥 논리를 따라. 당신은 모든에 액세스하고 있는지 확인 제대로 구조체의 기능을 제공합니다. 네? 

청중 : 윌이 슬라이드와 이 모든 것은 오늘까지 흉내 수? ANDI 펭 : 항상, 네. 내가 넣어하려고거야 이 업 후 시간 등을들 수있다. 내가 다윗을 이메일로 보내 드리겠습니다, 다윗을 시도합니다 이 후 한 시간처럼졌습니다. 

좋아, 그럼 우리는이 다른로 이동 스러운 데이터 구조는 큐라고. 너희들은 여기에서 볼 수 있듯이, 큐, 우리 사이에 영국에 대한, 그것이 모든 라인입니다. 그렇게 반대 무엇 당신은 스택이 생각 큐가 정확히 무엇이다 논리적으로 당신은 그것이라고 생각합니다. 또, FIFO의 규칙에 의해 열리는 이는, 가장 먼저입니다. 첫 번째 인 경우 라인에 하나, 당신이있어 그 첫 번째 라인 나옵니다. 

그래서 우리는이 전화를 좋아하는지 dequeueing과가 대기 상태입니다. 우리는 무언가를 추가하려면 우리의 큐에, 우리는 대기열에. 우리가 원하는 경우 대기열에서 제외, 또는 취할 뭔가 멀리, 우리는 큐에서. 

우리가 가지있어 그래서 같은 의미 고정 된 크기의 요소를 생성하는 우리 특정 저장할 수 있습니다 일, 그러나 우리는 또한 수 우리는 배치하고 위치를 변경 그들 내부의 매개 변수 어떤 유형에 따라 기능을 우리는 할 수 있습니다. 스택 그래서, 우리는 마지막을 원했다 하나는, N은 첫 번째 아웃합니다. 큐는 우리가 처음 일을 할 것입니다 에서 첫 일이 될 수 있습니다. 

구조체 형 그래서 당신이 볼 수 있듯이, 정의, 그것은 조금 다르다 스택이 무엇에서 단지 우리가 계속해야하지 때문에 크기가 현재 위치를 추적, 또한 머리를 추적 할 뿐만 아니라 곳으로 우리는 현재. 그래서 쉽게 생각 나는이를 작성합니다. 그래서 우리가 큐를 가지고 가정 해 봅시다, 그래서 머리가 바로 여기 가정 해 봅시다. 라인의 머리하자 다만, 그가 현재의 말 우리는 삽입 할 큐에 뭔가. 나는 기본적으로 크기를 호출하는거야 꼬리와 같은 일이며, 대기열이 곳의 끝. 그냥 크기가 바로 여기에 있다고 가정 해 봅시다. 

그럼 어떻게 하나 실행 가능하게합니까 큐에 뭔가입니까? 무엇 인덱스 우리가 배치 할 할 여기서 우리는에 삽입 할. 이의 시작입니다 경우 이 큐는 그것의 끝 또는 그것의 크기, 어디까지 할 다음 개체를 추가하려면? 

청중 : [들리지] ANDI 펭 : 정확히, 당신은 추가 할 에 따라 당신은 그것을 작성했습니다. 어느 쪽이 비어 있거나 비어 있습니다. 그래서 당신은 아마 그것을 추가 할 여기에 있기 때문에 크기가 말한 데로라면 이 모든 전체 경우, 당신이 원하는 바로, 바로 여기에 추가하는 방법? 

그래서 즉,이다 아주, 아주 잠시 간단한, 꽤 항상 올바른 주요 차이점 때문에 큐와 스택 사이 그 큐 수있다 실제로 조작 할 수 그 때문에, 헤드 변경 당신이 원하는 위치에 따라 당신의 큐의 시작은 시작합니다. 그 결과로, 꼬리 또한 바꿀 것입니다. 그래서 좀 봐 지금이 코드. 너희들도에했다으로 대기열, 퀴즈에 써. 어쩌면 우리는 그 이유를 얘기하자 대답은 그것이 무엇이었다. 

나는 아주, 하나이 줄을 맞지 않을 수 있습니다 코드 그러나 기본적으로이 작품 한 줄에 있어야합니다. 30초처럼 보내십시오. 봐, 왜 참조 이것은 인 방법이다. 

아주, 아주 유사한 구조체, 아주, 아주 이전과 유사한 구조 아마도 제외 스택 한 줄의 코드. 그리고 한 줄의 코드가 기능을 결정합니다. 그리고 그것은 정말 차별화 스택에서 큐. 

누군가는 자상을 먹고 싶어 당신이했습니다 이유를 설명에서 여기에서이 복잡한 일이있어? 우리의 반환을 볼 우리의 멋진 친구 계수. 너희들은 곧 올 것이다으로 프로그램에서 인식하는, 거의 언제 당신이 뭔가를 필요 아무것도 주위에 포장하기, 계수는 그것을 할 수있는 방법이 될 것입니다. 그래서를 알고, 사람이 원하는 않습니다 코드의 라인을 설명하는 시도? 그래, 모든 대답은 허용과에 오신 것을 환영합니다. 청중 : 당신이 나에게 말을하는거야? ANDI 펭 : 네. 청중 : 아, 아니 죄송합니다. ANDI 펭 : 좋아, 그럼하자 이 코드를 통해 도보. 그래서 때 당신이 노력하고 큐에 무언가를 추가, 머리가 발생하는 사랑스러운 경우 바로 여기에, 그것은 우리에게 매우 쉽다 다만 끝으로 이동 바로 뭔가를 삽입? 그러나 큐의 전체 지점입니다 그 수 실제로 동적 헤드 위치에 따라 변경 우리 우리의 Q의 시작이 원하는, 와 같은, 꼬리 등 또한 바꿀 것입니다. 

그리고이없는 것을 상상 큐, 오히려이 큐이었다. 의 머리가 바로 여기에 있다고 가정 해 봅시다. 의 우리의 큐는이처럼 보였다 가정 해 봅시다. 우리는 어디로 이동하고 싶었다면 라인의 시작이고, 의 우리가 머리를 옮겨 봅시다 이런 식으로 여기에 크기. 

이제 우리는 뭔가를 추가 할 이 큐,하지만 너희들이 볼 수 있듯이, 그냥 할 수 있도록 간단하지 크기 이후 어떤 추가 우리가 부족하기 때문에 우리의 실제 배열의 경계입니다. 우리가 정말 추가 할 경우 여기에있다. 즉, 큐의 아름다움 즉, 시각적으로, 우리에게있다 라인이 이렇게 가고처럼 보이는 그러나, 데이터 구조에 저장 될 때, 그들은주기 등을 제공합니다. 그것은 종류의 주위에 래핑 전면 동일한 방법으로 또한 줄 수있는 래핑 주변 어디든지 당신을에 따라 할 줄의 시작 부분으로합니다. 그래서 우리는이 걸릴 경우 여기에 내려다 볼,하자 우리를 만들고 싶었 말 기능은 대기열을했다. 우리는 그 질문에 INT의 N을 추가하고 싶었다. q.size 우리는 우리의 데이터를한다는 전화 할게 q-- 경우 우리의 queue.size하지 않는 경우는 structure-- 용량 또는 경우와 동일 그것은 용량보다 적은이다 q.strings은 우리의 Q 내에서 배열입니다. 우리는 설정하는거야 그 q.heads 동일, 이는 바로 여기, 플러스 q.size 용량에 의해 계수하는 여기 우리를 다시 포장. 

이 예를 들어, 인덱스에 따라서 머리의 오른쪽 1? 크기의 인덱스 0, 1, 2, 3, 4이다. 그래서 우리는 1 플러스 4 계수 작업을 수행 할 수 있습니다 5 우리의 능력에 의해. 무슨 우리를 주는가? 인덱스는 무엇인가 그 이 나온다? 

청중 : 0. 

ANDI 펭 : 0, 어떤 여기 될 일이, 그래서 우리가 할 수 있도록하려면 여기에 삽입합니다. 그리고이 방정식 여기 종류 단지 어떤 숫자와 함께 작동 위치에 따라 당신의 머리와 당신의 크기입니다. 당신은 어떤 사람들을 알고있는 경우 일이 당신이 알고있는이다 정확히 삽입 할 위치 무엇이든은 큐 후입니다. 그 모두에게 의미가 있습니까? 

나는 뇌의 종류를 알고 티저 특히 이후이 퀴즈의 여파로했다. 그러나 희망이 모두 지금 이해할 수 왜이 솔루션 또는이 함수는 인 방법이다. 누구나 약간은 명확하지? 그래. 

그리고 지금, 당신의 경우 이 작업을 대기열에서 제외하고 싶어 우리의 머리가 이동 될 곳이다 우리가 대기열에서 제외한다면, 때문에 우리는 Q의 말을하지 않습니다. 우리는 오른쪽 머리 벗고 싶어? 그래서 그 결과로, 머리를 바꿀 것입니다, 당신이 대기열에 때 왜, 즉, 당신은 추적 할 수있어 여기서 당신의 머리와 크기 삽입 할 수 있습니다 올바른 위치에. 

그리고 당신이 대기열에서 제외 할 때, 나는 또한 그것을 의사. 당신이 원한다면 언제든지 이것을 코딩을 시도한다. 당신이 바로, 머리를 이동하려면? 나는 큐에서 제거하고 싶었다면, 나는 머리를 통해 이동합니다. 이것은 머리가 될 것입니다. 

그리고 우리의 현재 크기는 것 빼기 때문에 우리는 더 이상 배열의 네 가지 요소가있다. 우리는 세 가지가 있고, 우리는 원하는 내부에 저장된대로 돌아갑니다 머리의 우리는 이것을 먹고 싶어하기 때문에 스택에 이렇게 아주 유사한 값 아웃. 그냥 당신이 복용하고 다른 장소에서, 당신은 당신의 포인터를 재 할당해야 그 결과로 다른 장소. 논리적으로, 모두가 따라? 큰. 

좋아, 그래서 우리는 조금 이야기거야 연결리스트에 대한 깊이 더 그들은 매우, 매우 도움이 될 것이기 때문에 금주의 과정에서 당신을 위해 psets를. 연결리스트, 같은 너희들 그들은 모두, 기억 특정의 노드입니다 노드는 값과 포인터의 값 양쪽 즉, 서로 연결되어 그 포인터에 의해. 방법에 대한 그래서 구조체 우리는 여기에 노드가 우리입니다 만들 인 INT의 N이 어떤 상점 또는 문자열 N의 값 또는 당신이 원하는 무엇이든 문자 스타 N, 호출. 포인터가 구조체 노드 스타, 각 노드에있는 것인지, 당신은이 겁니다 다음으로 포인터 포인트. 당신은 머리를해야합니다 의 연결리스트의 나머지 가리 예정 등등 등등 값 당신은 결국 끝에 도달 할 때까지. 그리고이 마지막 노드는 그냥 포인터가없는 것. 그것은 가리 것 null의 경우, 그 때의 당신은 당신을 공격 한 알 당신의 연결리스트의 끝 때 마지막 포인터 아무것도 가리 키지 않습니다. 

그래서 우리는 더에 조금 갈거야 에 대한 깊이 어떻게 가능성 것 링크 된 목록을 검색 할 수 있습니다. 의 일부를 어떤 기억 연결리스트의 단점 검색에 대한 배열을 구절. 배열 할 수 있습니다 이진 검색하지만, 왜 연결리스트에서 그렇게 할 수 있습니까? 

청중 : 그들은 모두 연결되어 있기 때문에, 하지만 당신은 아주 어디 모른다 [알아들을 수 없는]. 

ANDI 펭 : 네, 정확히 그렇게 기억 그 배열의 광채 우리가 가지고 있었던 사실이었다 랜덤 액세스 메모리 어디에 나는 인덱스의 값을 원하는 경우 여섯, 난 그냥, 인덱스 여섯 말할 수 나에게 그 값을 제공합니다. 배열이 분류되어 있기 때문에 그건 메모리의 연속 된 공간에서 한 곳에서 반면, 연결리스트 가지 있습니다 무작위로, 주변의 모든 산재 유일한 방법은 당신이 하나를 찾을 수 있습니다 를 알려주는 포인터를 통해입니다 그 다음 노드가 어디의 주소. 

그리고 그 결과, 유일한 방법 링크 된 목록을 검색 할 수 선형 탐색이다. 나는 정확히 알 수 없기 때문에 링크 된 목록에서 12 값이며, 나는 전체를 통과해야 링크 된 목록을 하나의 첫 번째 노드에 머리에서 하나, 제 2 노드에 상기 제 3 노드에, 나는 마침내 얻을 때까지 모든 방법 내가 찾고 해당 노드는 곳. 그리고 이러한 의미에서, 검색 연결리스트에 항상 n은. 항상 N입니다. 그것은 선형 시간에 항상. 

그래서 코드하는 우리는이를 구현하고,이 당신 이후 너희들을위한 약간의 새로운 사람은 정말 대해 또는 이제까지 이야기하지 않은 방법에서 볼 포인터 포인터를 검색, 그래서 우리는 걸을 것이다 이 아주, 아주 천천히. 그래서 부울 검색, 오른쪽, 의 우리가 원하는 가정 해 봅시다 라는 함수를 만드는 방법 true를 돌려 검색 링크 된 내부 가치를 발견하는 경우 나열하고, 그렇지 않으면 false를 반환합니다. 노드 별 목록입니다 현재 단지 포인터 당신의 연결리스트의 첫 번째 항목에. INT n을 당신이있어 값이다 그 목록을 검색. 

그래서 노드 스타 포인터는 목록 같습니다. 그것은 우리가 설정하는 의미 및 포인터를 만드는 목록의 내부에 첫 번째 노드. 나와 함께 모두? 우리가 갈 것 인 경우에 따라서 다시 여기에, 나는 것 가리키는 포인터를 초기화 머리는 무엇의 목록입니다. 

그리고 당신은, 여기로 일단 포인터가 동일한 null을하지 않지만, 그래서 우리가되는 루프입니다 통과 이후가 될 것 무엇 때문에 우리의 목록의 나머지 포인터가 null 같을 때 어떻게됩니까? 우리는 우리가 잔 마셔요 것을 알고있다 

청중 : [들리지] 

ANDI 펭 : 정확히, 그래서 우리는 알고 우리는 오른쪽 목록의 끝에 도달했습니다? 여기에 다시 갈 경우, 각 노드 다른 노드를 가리키는해야 등 등 당신은 결국 히트까지 당신의 연결리스트의 꼬리, 이는 포인터를 갖는다 단지 더 이상 아무 곳이나 가리 키지 않습니다. 그래서 당신은 기본적으로 알고 목록은 여전히​​를하다 포인터가 동일하지 않을 때까지 널 (null)이 널 (null)에 해당하면 때문에, 당신은 더 이상 물건이 없다는 것을 알고있다. 

그래서 우리가있어하는 루프입니다 실제 검색을해야 할 것. 그리고 pointer--는 참조 할 경우 이 화살표 기능의 종류? 그래서 포인터 포인트 경우 N에, 경우 N과 동일 같음 N에서 포인터 그래서 의미하는 경우 그 당신이있어 포인터 각각의 단부에 대한 검색 노드 값과 실제로 동일하다 그런 다음, 찾고 당신은 true를 반환하고 싶습니다. 그러니까 기본적으로, 당신은 노드에서라면 그 , 당신이 찾고있는 값을 갖는다 당신은 당신이 있었던 것을 알고있다 성공적으로 검색 할 수. 

그렇지 않으면, 당신은 설정하려면 다음 노드에 대한 포인터. 즉, 여기에 라인이하고있는 것입니다. 포인터는 다음 포인터 같습니다. 그 작업을 어떻게 모든 사람이 볼 수? 

그리고 기본적으로 당신은거야 단지 목록의 전체를 횡단 포인터 각 때까지 재설정 결국에는리스트의 끝을 쳤다. 그리고 당신은이 있음을 알 수 없다 더 많은 노드를 통해 검색 할 수 그리고 당신은 거짓을 반환 할 수 있습니다 당신이 알고 있기 때문에, 그 아니라, 오, 나는 검색 할 수있었습니다 경우 리스트의 전체 관통. 이 예제의 경우, 내가 원하는 경우 10의 값을 찾아, 나는 머리에서 시작하고, 나는 끝까지 검색 나는 결국,이에 도착하는 null로 가리키는 포인터, 내가 아닌, 쓰레기, 나는 10를 추측 것을 알고있다 이 목록 나는 그것을 찾을 수 없습니다 때문입니다. 그리고리스트의 마지막에 있어요. 그리고이 경우 당신은 알고있다 나는 false를 반환거야. 

그 조금을 위해에 흠뻑 젖어 보자. 이 꽤 될 것입니다 당신의 PSET 중요. 그 로직은 아마도 매우 간단 구문 그냥 구현. 너희들은 만들고 싶어 당신이 이해하고 있는지 확인하십시오. 시원한. 

좋아, 그럼 우리는 어떻게 될 것 오른쪽 노드를 삽입, 리스트로 인해 기억 어떤 혜택 무엇인가 의 연결리스트 대를 가진 저장소의 측면에서 배열? 

청중 : 그것은 동적이다, 그래서 쉽게 이러시면 

ANDI 펭 : 정확히, 그래서, 동적이다하는 그것을 확장하고 축소 할 수 있음을 의미합니다 사용자의 필요에 따라. 그리고, 이러한 의미에서, 우리는 필요하지 않습니다 불필요한 메모리를 낭비하는 나는 때문에 내가 원하는 얼마나 많은 값을 모르는 경우 가게에, 나를 위해 이해가되지 않습니다 배열 때문에를 만들려면 나는 10의 값을 저장하려면 나는 1000의 배열, 그건 생성 낭비 많은 메모리, 할당. 우리가 링크 사용하려는 이유 목록은 동적으로 할 수 있도록 변경하거나 크기를 축소. 

그리고 그 삽입한다 조금 더 복잡합니다. 우리는 랜덤 요소에 액세스 할 수 없기 때문에 우리가 배열의 것이 방법. 나는 요소를 삽입 할 경우 일곱 번째 인덱스로, 난 그냥 삽입 할 수 있습니다 일곱 번째 인덱스에. 연결리스트, 그것은하지 않습니다 아주 쉽게 작동, 그래서 우리는 삽입하기를 원한다면 링크 된 목록에 여기에 하나, 시각적으로, 그것을보고 매우 간단합니다. 우리는, 바로 거기를 삽입 할 오른쪽 목록의 시작 부분에서, 바로 머리 후. 

그러나 우리가하는 방식은 재 할당하기 포인터는 약간 선상됩니다 또는, 논리적으로는, 의미가 있지만, 당신은 당신이 그것을 가지고 있는지 확인하려면 완전히 때문에 당신이 원하는 마지막 일 포인터를 재 할당하는 것입니다 우리가 여기에서하고있는 방법입니다. 당신이 만약 역 참조 (1) 머리에서 포인터, 다음 갑자기 모든 당신의 연결리스트의 나머지 당신이 실제로 있기 때문에 손실 임시 아무것도를 만들었습니다. 즉이 지적입니다. 그런 다음 포인터를 재 할당하는 경우 목록의 나머지는 완전히 없어집니다. 그래서 당신이되고 싶어 여기에 매우, 매우 조심 먼저를 지정하려면 당신이 어떤에서 포인터 어디든지에 삽입 할 당신이 원하는, 다음을 목록의 나머지 반 참조 할 수 있습니다. 

그래서 이것은 어디든지 적용 당신은에 삽입하려는. 당신은에 삽입 할 경우 머리, 여기에 응답 할 경우, 당신은에 삽입 할 경우 결국, 잘, 최종 I 추측 당신은 단지 것 어떤 포인터가 없지만, 그렇게하지 ​​있는지 확인하려면 목록의 나머지 부분을 잃게됩니다. 당신은 항상 있는지 확인하려면 새 노드가 가리키는 무엇으로 당신 에 삽입 할, 다음은 체인에 추가 할 수 있습니다. 모두 명확한? 

이 될 것입니다 진짜 문제 중 하나. 대부분의 주요 문제 중 하나 당신은 당신의 PSET에 할거야 당신이 만들려고하는거야 것입니다 링크 된 목록과 삽입 것들 그러나 단지를 잃을 당신의 연결리스트의 나머지. 그리고 당신처럼 될거야, 내가 이런 일이 왜 몰라? 그리고 그것은 통과하는 고통 및 포인터를 모두 검색 할 수 있습니다. 

그리고 나는이 PSET에 당신을 보장, 이러한 노드를 작성하고 그리기 매우 도움이 될 것입니다. 그래서 당신은 완벽하게 추적 할 수 있습니다 모든 포인터가있는 곳의, 무슨 잘못이야 모든 노드가있는 곳, 당신이 액세스 할 수 무엇을해야하는지 또는 삽입 또는 삭제하거나의. 그 좋은 모두? 시원한. 

우리는 코드를보고 싶어한다면? 아, 알 수없는 경우 우리 그래서, 짓이야 확인을 볼 수 있습니다 상단 그것이 모든 함수이다 우리가 원하는 이름을 삽입 연결리스트로 INT의 N을 삽입합니다. 우리는이를 통해 걸을 것입니다. 그것은 코드의 많은 새로운 구문을 많이합니다. 우리는 확인을 할 수 있습니다. 

상단마다에서 최대 그래서 우리는 무엇을 만들려면 우리는 무엇을해야합니까 특히 경우 그것은 스택에 저장되지 할 하지만 힙? 우리는 오른쪽의 malloc로 이동? 그래서 우리는 포인터를 만들 것입니다. 노드, 포인터, 새로운 같음 노드의 크기의 malloc 우리가 원하기 때문에 해당 노드가 생성된다. 우리는의 양을 원하는 노드가 차지하는 메모리 에 할당 할 새 노드의 생성. 

그리고 우리는 확인거야 새로운 등호가 null 동일한 경우를 참조하십시오. 우리가 말을 기억 하는가? malloc에​​ 무엇이든을, 당신은 항상 무엇을해야 하는가? 당신은 항상 확인해야합니다 여부를 그 null입니다. 

예를 들어, 운영 시스템은 완전히 가득했다 당신은에서 더 이상 메모리가 있다면 모든 당신이 malloc을 시도, 당신을 위해 null을 반환합니다. 그리고 당신은 그것을 사용하려고하면 이 null로 지적 할 때, 당신은 할 수 않을거야 해당 정보에 액세스 할 수 있습니다. 그리고 같은, 우리는 확인하고 싶었 때마다 mallocing하고 있는지, 당신은 항상 있는지 확인하고 당신에게 주어진 메모리는 null입니다. 그렇지 않은 경우에, 우리는 이동할 수 있습니다 우리의 코드의 나머지에. 

그래서 우리는 갈거야 새 노드를 초기화합니다. 우리는 새로운 n은 N과 동일 할 것입니다. 그리고 우리가 할거야 새로운 새로운 포인터를 설정 null로 지금 우리는하지 않기 때문에 그것을 가리 키도록 아무것도 할 수 있습니다. 우리는 아무 생각이 곳이 없다 그것은 당신을 넣어 것 그리고 우리가 원하는 경우 머리에 삽입, 우리는 다시 할당 할 수 있습니다 머리에 대한 포인터. 모든 사람이 논리를 따라 하는가 여기서의 그 일이야? 

우리가하고있는 모든 새를 만드는 것입니다 노드 null에 포인터를 설정하는, 다음 재 할당 그것은 머리에 우리의 경우 우리가 머리를 삽입 할 알고있다. 그리고 머리에 것입니다 그 새로운 노드를 향해 가리 킵니다. 그와 확인을 모두? 

그래서 두 단계 프로세스이다. 먼저 할당 할 수있어 당신이 무엇을 만들고있어. 해당 포인터를 설정 당신을 참조하고 수 역 참조 가지 첫 번째 포인터 새로운 노드쪽으로 가리 킵니다. 당신이 그것을 삽입하여 원하는 목적지, 그 논리는 성립 할 것이다. 

그것은 할당과 같은 종류의 임시 변수. 기억, 당신은있어 확인하는 그 당신이 교환하는 경우의 트랙을 잃지 않습니다. 당신은 당신이 있는지 확인하려면 종류의 유지 임시 변수 여기서 그 일을 추적 그래서 저장 당신 과정에서 어떤 값을 잃지 말고 의 그것으로 장난처럼. 

좋아, 그럼 코드는 여기에있을 것입니다. 너희들은 섹션 다음에 보자. 그것은있을 것입니다. 

그래서 내가 어떻게하는지 추측 우리가 원하는 경우이 다를 중간이나 끝 부분에 삽입하는 방법? 사람은 무엇의 아이디어가 있습니까 논리적 기준으로 의사 우리가 원하는 경우에 우리가 수행하게 중간에 삽입하는 방법? 그래서 만약 우리가 그것을 삽입하고 싶어 헤드는, 우리가 모든 새로운 노드를 생성하는 것이다. 우리는 그 포인터를 설정 어떤 머리에 새 노드, 그리고, 우리는 머리를 설정 새 노드에, 오른쪽? 우리는 중간에 삽입하고 싶었다면 목록으로, 우리는 무엇을해야 할 것인가? 

청중 : 그것은 아직도 것 유사한 과정이 될 의 포인터를 할당 추천하고 다음, 그 포인터를 할당 그러나 우리는이 위치해야 할 것입니다. 

ANDI 펭 : 정확히, 정확하게 그래서 만약 제외한 동일한 공정 정확히 어디를 찾을 수있는 당신 그 새로운 포인터에 가고 싶어, 내가 삽입 할 경우 이렇게 확인 list-- 링크의 중간, 의가 우리의 연결리스트 말할 수 있습니다. 우리가 여기를 삽입 할 경우, 우리는 새로운 노드를 만들 것입니다. 우리는 malloc을 것입니다. 우리는 새로운 노드를 만들 것입니다. 우리는을 할당 할거야 여기에이 노드의 포인터. 

그러나 문제는 그 상이 머리가 어디에서 우리가 정확히 알고 있다는 것입니다 여기서 헤드이다. 그것은 바로, 처음 옳았다? 그러나 여기에서 우리는 추적 할 수있어 여기서의 우리는 그것을에 삽입하고 있습니다. 우리가 삽입하는 경우 우리의 여기에 노드, 우리는있어 확인하는 그 이 노드로 이전 포인터를 재 할당입니다. 그럼 당신은 가지를해야합니다 두 가지의 추적합니다. 당신이있는 곳을 추적하는 경우 노드는 현재에 삽입된다. 또한 추적 할 당신이보고있는 이전 노드 또한 거기에 있었다. 그 좋은 모두? 그래. 

어떻게 끝 부분에 삽입하는 방법에 대한? 내가 원한다면 나는 here-- 추가하고 싶다면 목록의 마지막에 새로운 노드를 추가, 나는 그 일에 대해 어떻게 갈 수 있는가? 청중 : 그래서 현재, 마지막의 널을 지적했다. ANDI 펭 : 네. 정확히, 그래서이 하나 현재 알고 지적이다, 그래서 나는이 점에서, 그것의 추측 리스트의 마지막에 추가하는 것은 매우 쉽습니다. 당신이 할 일은 그것을 설정 널 (null) 다음 붐과 동일. 바로 거기, 매우 간단합니다. 매우 간단합니다. 

매우 유사 당신 머리,하지만 논리적으로 단계가 있는지 확인하려면 당신은이 중 하나를 수행하기 위해 취해야 당신은 함께 다음과 같은 것입니다. 그것은 중간에, 아주 쉽게 코드의,에 휘말리고 아, 나는 너무 많은 포인터를 가지고있다. 어디서 몰라 아무것도 가리키는. 나는 심지어 내가에있어 어느 노드 모른다. 무슨 일이야? 

심호흡을, 진정, 휴식을 취하십시오. 당신의 연결 목록을 그립니다. 당신이 말하는 경우에, 나는 어디에 정확히 알고 나는이 점을 삽입해야 그리고 내 재 할당하는 방법을 정확히 알고 포인터는, 훨씬, 훨씬 더 쉽게 사진합니다 out-- 훨씬, 훨씬 더 쉽게하지 코드의 버그에서 분실. 그와 확인을 모두? 그래. 

그래서 나는 우리가하지 않은 개념을 생각한다 정말, 지금은 전에 이야기 나는 아마 당신을 추측 많은 yet--가 발생하지 않습니다 그것은 고급 concept-- 가지의 우리가 실제로 데이터를 가지고있다 구조는 이중 연결리스트라고합니다. 너희들이 볼 수 그래서, 우리가하고있는 모든 만들고있다 실제 값, 추가 우리의 각 노드에 대한 포인터 그 또한 이전 노드를 가리 킵니다. 그래서뿐만 아니라 우리는 우리가 할 노드는 다음 중 하나를 가리 킵니다. 또한 이전에 가리. 지금은이 두 가지를 무시하는거야. 

그럼 당신은 체인을 가지고 그 두 가지를 이동할 수 있습니다, 다음은 조금 더 쉽다 논리적으로 따라 할 수 있습니다. 여기 같은 대신 오, 추적을 유지, 나는 이 노드가 있음을 알고있다 내가 다시 할당해야 하나, 난 그냥 여기와 있습니다 단지 앞 당깁니다. 그럼 정확히 알고 즉, 다음을 를 통과 할 필요가 없습니다 연결리스트의 전체. 그것은 조금 더 쉽다. 

그러나 같은, 당신은 이중이 포인터의 양 즉, 메모리의 두 배입니다. 또한 추적 할 포인터 많이있다. 그것은 조금 더 복잡하지만, 그건 사용자 친화적 따라 조금 더 당신이 달성하기 위해 노력하고 무엇에. 

따라서 이러한 유형의 데이터 구조는 완전히 존재 과에 대한 구조는 매우이다 당신이 가지고있는 모든이를 제외하고 단순, 대신 다음에 그냥 포인터, 당신은 또한 이전에 대한 포인터를 가지고있다. 즉, 모든 차이했다입니다. 그 좋은 모두? 시원한. 

좋아, 그래서 지금은 해요 정말 아마 지출 15~20분 또는 대량 등 섹션의 나머지 시간의 해시 테이블에 대해 얘기. 어떻게 사람의 많은 pset5 사양을 읽고? 좋아, 좋아. 즉 보통의 50 % 이상이다. 괜찮아요. 

너희들이 볼 수 그래서, 당신은 pset5에 도전있어 사전을 구현하는 것입니다 당신은 14 만 단어를 통해로드 어디에 우리는 및 맞춤법 검사에게 당신에게 있음을 모든 텍스트에 대한 그것. 우리는 당신에게 무작위주지 문학의 조각. 우리는 당신에게 오디세이을 줄 것이다. 우리는 당신에게 일리아드를 줄 것이다. 우리는 당신에게 오스틴 파워를 줄 것이다. 

그리고 당신의 도전 체크를 주문하는 것입니다 모두의 모든 하나의 단어 그 사전 기본적으로 우리의 맞춤법 검사기와. 그리고 몇 부분있다 이 PSET를 생성, 먼저이되고 싶어 실제로로드 할 수 에 모든 단어 당신의 사전, 다음을 할 수 있도록하려면 그들 모두를 맞춤법 검사. 그리고 같은, 당신이 필요로하는거야 이 빠르게 수행 할 수있는 데이터 구조 효율적 동적. 

그래서 가장 쉬운 가정 이 작업을 수행하는 방법을 아마 오른쪽 배열을 만들까요? 저장하는 가장 쉬운 방법은 당신입니다 140,000 단어의 배열을 만들 수있다 그냥 거기에 그들 모두를 배치하고 이진 검색에 의해 그들을 통과 또는 선택하거나 싫든 죄송합니다 그 정렬입니다. 당신은 그 (것)를 정렬 한 다음를 통과 할 수 이진 검색하거나 선형 검색 그냥 마지막 단어,하지만 메모리의 엄청난 금액을 소요 그리고 그것은 매우 비효율적이다. 

그래서 우리는 시작하는거야 만드는 방법에 대해 이야기 우리의 실행 시간이 더 효율적입니다. 그리고 우리의 목표는 얻을 것입니다 일정 시간 곳 거의 배열처럼 당신은 즉시 액세스 할 수 있습니다. 난 아무것도를 검색하고 싶다면, 나는 단지 할 수 있도록하려면 붐, 정확하게 그것을 발견하고 잡아 당깁니다. 그리고 구조하는 우리는 매우 가까이되는거야 일정에 액세스 할 수 시간이 성배 상수의 프로그래밍 시간은 해시 테이블이라고합니다. 그래서 다윗은 앞서 언급 한 [들림] 강의에 조금, 하지만 우리가 정말거야 깊은 이번 주에 다이빙 에 관한 것 조각에 어떻게 해시 테이블 작동합니다. 

그 길을 따라서 해시 테이블 작업, 예를 들면, 나는 단어의 무리를 저장하기를 원한다면, 영어 단어의 무리, 나는 이론적으로 넣을 수 바나나, 사과, 키위, 망고, 쌍, 모든 단지 배열에 멜론. 그들은 모두에 맞게 수 있고 찾을 수. 그것은에 통증 종류의 것 액세스를 검색, 하지만 이렇게 쉬운 방법은 우리는 구조를 실제로 만들 수 있습니다 우리는 해시 해시 테이블이라고합니다. 우리는을 통해 우리의 키를 모두 실행 해시 함수, 방정식 그로 모두 전환 값의 일종 우리는에 저장할 수 연결리스트의 본질적으로 배열. 

그래서 여기에 우리가 원하는 경우 영어 단어를 저장하기 위해, 우리는 잠재적으로 단지 수, 나는하지 않습니다 알다시피, 모든 첫 글자를 켜 다수의 일종으로. 그래서, 예를 들어, 내가 원 이 apple--과 동의어가 될 0의 인덱스, 및 B는 1과 동의어가 될 우리는 26 항목을 가질 수 있습니다 그건 그냥 저장할 수 있습니다 의 모든 문자 우리가 시작합니다 알파벳입니다. 그리고 우리는 할 수 있습니다 0의 인덱스에 사과. 우리의 인덱스에 바나나를 가질 수있다 1, 2의 인덱스 멜론, 등 등. 그리고 이렇게 내가 검색하기를 원한다면 내 해시 테이블 및 액세스 사과, 나는 사과로 시작 알고 그리고 나는 정확하게 알고 그것은하고 해시해야 인덱스 0 때문에에 테이블 기능의 이전에 할당. 

나도 몰라 그래서, 우리는 사용자 프로그램 어디에 당신과 함께 청구됩니다 임의하지 arbitrarily--, 신중에 노력과 좋은 식의 생각 확산 할 수 있도록 당신의 가치를 모두 밖으로 방법들은 쉽게 접근 할 수 그것은 나중에와 방정식 등 당신 것을 자신은 알고있다. 나는에 가고 싶은지 의미에서 이렇게 망고, 나는 아, M로 시작, 알고있다. 그것은 12의 인덱스에 있어야합니다. 난 아무것도를 검색 할 필요가 없습니다. 난 그냥 갈 수 exactly-- 나는 알고있다 12의 인덱스는 빼냅니다. 

방법에 모두 클리어 해시 테이블의 기능이 작동? 그것은 단지 더 복잡한 배열 가지입니다. 즉, 모든이다. 그래. 

그래서 나는 우리가로 실행 같아요 이 문제를 어떻게 여러 가지가있는 경우 발생 그것은 당신에게 같은 인덱스를 제공? 그래서 모두에게, 그것을 우리의 기능을 말한다 한 첫 번째 편지를 가지고 있었다 과에 그 설정 0 인덱스 (25)를 통해 각각의. 그 경우 완전히 괜찮아요 당신은 각각 하나 있습니다. 그러나 두 번째는 당신이 시작 더 가지고, 당신이있어 충돌라고 무엇을해야 할 것. 

내가 삽입하려고하면 해시에 묻어 그래서 이미에 바나나를 가지고 테이블, 무엇을 할 때 일어날 당신은을 삽입하려고? 나쁜 일 때문에 바나나 이미 인덱스 내에 존재 당신은에 저장하려는. 베리 종류의 나는 무엇을해야합니까, 아, 같은입니까? 나는 어디로 가야 모르겠어요. 나는이 문제를 어떻게 해결합니까? 

그래서 너희들 것이다 가지 우리는이 어려운 일을 참조 여기서 우리는 종류의 실제로 수 우리의 배열에 연결된 목록을 만들 수 있습니다. 그래서 가장 쉬운 방법 이것에 대해 생각하는, 모든 해시 테이블 인 연결리스트의 배열입니다. 그리고, 그런 의미에서, 당신은 포인터의이 아름다운 배열, 다음 각 포인터에 그 값, 해당 인덱스에, 실제로 다른 일을 가리킬 수 있습니다. 그래서 당신은 모든 개별이 하나의 큰 배열의 떨어져오고 체인. 

그래서 여기에, 나는 경우 베리를 삽입하고 싶었다, 내가 좋아, 내가 입력에 갈거야, 알 그것은 내 해시 함수를 통해. 나는의 인덱스로 끝날거야 1을 입력 한 다음 내가 가질 수있을거야 이 단지 작은 부분 집합 거대한 140,000 단어 사전. 그리고 난 그냥 볼 수 있습니다 그것의 1/26을 통해. 

그리고 그럼 난 그냥 삽입 할 수 있습니다 전이나 바나나 후 두 베리 이 경우? 후, 오른쪽? 그래서 당신이 원하는거야 바나나 후이 노드를 삽입, 그래서 당신은 삽입 할거야 그 연결리스트의 꼬리에서. 나는 돌아갈거야 이 이전 슬라이드로, 그래서 너희들은 어떻게 볼 수 있습니다 해시 기능이 작동합니다. 

그래서 해시 함수는이 방정식은 당신은 당신의 입력의 종류를 실행하는 것을 얻을 수있는 어떤 색인을 통해 당신은 방향을 지정하려면. 그래서,이 예제에서는, 우리는 원 수행은 첫 글자를 가지고 있었다 우리는 그 다음 인덱스로 그 설정 우리의 해시 함수에 그 저장할 수 있습니다. 우리가 여기서하고있는 모든 우리가있어입니다 첫 글자를 변환. 그래서 keykey [0] 단지 첫 글자 어떤 문자열 우리는 데있어, 우리가 전달하고 있습니다. 우리는 상부에 그 변환하고있어 우리는 대문자로 차감하고 이렇게되는 모든 우리에게 번호를주고있다 있는 우리는 우리의 가치를에 해시 수 있습니다. 

그리고 우리는 갈거야 해시 계수의 크기를 반환합니다. 아주, 아주 조심 이론적으로, 여기에, 때문에 당신의 해시 값은 무한 될 수 있습니다. 그것은 단지에와 계속적으로 갈 수 있었다. 그것은 정말 일부가 될 수 정말 큰 값, 하지만 해시 테이블 때문에 그 사용자가 만든 만 26 인덱스가, 당신이 있는지 확인하려면 당신의 modulusing 있도록 이 같은입니다 run--하지 않습니다 당신의 queue-- 같은 일이 그래서 당신은 떨어져 실행하지 않는 것이 당신의 해시 함수의 바닥. 

당신은 주위를 다시 포장 할 [들리지] 경우에 같은 방법으로 당신은 아주 좋아했다 매우 큰 편지, 당신 에 그것을 원하지 않았다 다만 끝을 실행합니다. 여기에 같은 일이, 당신이 있는지 확인하려면 그것은 포장으로 끝을 실행하지 않습니다 주위 테이블의 상단에. 그래서이 그냥 아주 간단한 해시 함수. 했던 그 모든 걸릴 처음 무엇이든 우리의 입력의 편지였다 그리고 인덱스로 그를 설정하는 것이 우리는 우리의 해시 테이블에 넣을 수 있습니다. 

그래, 그래서 내가 전에 말했듯이 우리가 충돌을 해결하는 방법 우리의 해시 테이블을 가지고있다, 우리는 체인, 무엇을 호출합니다. 여러 삽입하려고한다면 같은 일 시작하는 단어, 당신은 하나의 해시 값을 가질 것입니다. 아보카도와 사과, 당신이 한 경우 우리의 해시 함수를 통해 실행, 당신에게 줄거야 같은 수의 0의 수. 그래서 방법은 우리가 즉 해결 우리는 실제로 가지를 연결 할 수있는 함께 연결리스트를 통해. 

그리고 이러한 의미에서, 너희들은 종류 볼 수 있습니다 방법의 데이터 구조 그 우리는 이전에 설정했습니다 건포도 연결리스트의 종류 등 중 하나에 함께 올 수 있습니다. 그리고 당신은 지금까지 생성 할 수 있습니다 보다 효율적인 데이터 구조 즉, 더 많은 양을 처리 할 수​​ 있습니다 데이터, 즉 동적으로 따라 크기를 조정 사용자의 요구에. 모두 명확한? 클리어의 모든 종류 여기에 무슨 일에? 

내가 insert--하고 싶다면 무엇 나도 몰라, 시작 과일, 베리 이외의 B, 바나나. 

청중 : 블랙 베리. 

ANDI 펭 : 블랙 베리, 블랙 베리. 어디에서 블랙 베리는 여기입니까? 글쎄, 우리가 실제로 분류되지 않은 이 아직 있지만, 이론적으로 우리는이를 원한다면 알파벳 순서로, 어디로 가야 블랙 베리해야합니까? 

청중 : [들리지] 

ANDI 펭 : 정확히, 여기에 후, 오른쪽? 그러나 그것은 매우 어려운 이후 reorder-- 나는 너희들에게 달려 같아요. 너희들 완전히 수 당신이 원하는대로 구현합니다. 보다 효율적인 방법 아마도이 일을 당신의 링크를 정렬하는 것입니다 알파벳 순서로 나열 그래서 당신이있을 때 물건을 삽입, 당신이 원하는 를 삽입해야합니다 알파벳 순서로 그래서 당신이있을 때 를 검색하려고, 당신은 모든 것을 통과 할 필요가 없습니다. 당신은 정확히 알고 그것은이며 쉽다. 

하지만 당신은 가지가있는 경우 일이 무작위로 산재 당신은 여전히​​ 할 겁니다 어쨌든 그것을 통과한다. 그래서 내가 원한다면 단지 블랙 베리 여기에 삽입 내가 검색 싶어 그것은, 내가 오, 알고, 블랙 베리 1의 인덱스로 시작, 그래서해야한다 순간적으로 단지 1 검색 알고있다. 그리고 나는 종류의 수 연결리스트를 순회 내가 블랙 베리에 도달 할 때까지, 그리고 그래 then--? 

청중 : 당신은 create--하려는 경우 이것은 매우 간단한 해시처럼 같아요 기능. 그리고 우리는 무엇을 원하는 경우 그런 여러 계층, 확인, 우리는로 구분합니다 모든 알파벳 문자 등 다시 또 다른 세트를 좋아합니다 그 내에서 알파벳 문자, 우리는 해시처럼 퍼팅 해시 테이블 내의 테이블, 또는 함수 내에서 함수처럼? 아니면 that--입니다 

ANDI 펭 : 당신의 해시 그래서 당신의 해시 테이블을 function-- 당신이 원하는만큼 커질 수있다. 그래서 이런 의미에서, 나는 생각했다 그것은 매우 쉬웠다 나를 위해 간단한 단지 종류를 기반으로하는 첫 번째 단어의 문자에. 그리고 만 26 옵션이있다. 난 단지 26 옵션을 얻을 수 있습니다 0-25 때문에 그들은 단지 수 에서 (Z)로 시작하지만, 당신이 원하는 경우 아마도 더 복잡성을 추가하는 또는 빠른 시간을 실행하여 해시 테이블, 당신이 절대적으로 모든 종류의 것들을 할 수 있습니다. 당신은 당신의 자신의 수 당신을 제공 방정식 더 많은 분배하여 말은, 당신은, 검색 할 때 더 빨리 될 것. 

그것은 완전히 너희들에게 달려 당신은 어떻게 그것을 구현하려는. 단지 버킷이라고 생각. 내가하고 싶어하는 경우 26 양동이, 내가 갈거야 그 양동이에 물건을 정렬 할 수 있습니다. 하지만 무리가 갈거야 각 버킷의 물건, 당신이 그것을 만들고 싶어 이렇게 더 빠르고 더 효율적인 나 백 버킷을 보자. 

하지만 당신은을 파악해야 그들이 있도록 방법은 일을 정렬하려면 적절한 양동이에 그들에 있어야합니다. 그러나 때 실제로 그 통에보고 싶은, 거기에 있기 때문에 훨씬 빠릅니다 각 양동이에 작은 물건. 그리고, 네, 사실입니다 pset5에서 너희들을위한 트릭 당신이 될 것이다 바로 만들 수 도전 가장 효율적인 무엇이다 당신이 생각할 수있는 기능을 할 수 저장하고이 값을 확인할 수. 

완전히 너희들까지 그러나 당신이 그것을하고 싶은, 하지만 그건 정말 좋은 점이다. 그 논리의 종류의 에 대해 생각을 시작하려는 물론, 내가 왜 더 버킷을하지 않는 것입니다. 그리고 내가 검색해야 적은 것, 그리고 아마 내가 서로 다른 해시 함수를 갖는다. 

그래,이 작업을 수행하는 방법은 여러가지가있다 PSET, 일부는 다른 사람보다 더 빠르다. 나는 완전히 얼마나 볼거야 빠른 가장 빠른 너희들 것이었다 당신의 기능을 작동시킬 수 있습니다. 확인, 모두 좋은에 체인 및 해시 테이블? 그것은 매우 간단한처럼 사실이다 당신은 그것에 대해 개념을 생각하면. 그것이 모두 분리 무엇이든 당신의 입력은 버킷에 있습니다, 그들을 정렬하고 찾고 거기 연관된 것을 보여줍니다. 

시원한. 자, 이제 우리는 다른 종류가 데이터 구조의 트리라고있다. 의가 가자와 시도에 대해 이야기 이는, 분명히 다르다 하지만 같은 범주에. 기본적으로 모든 나무 대신하다 선형의 방식으로 데이터를 조직 해시 테이블을 does-- 있음 그것은 상단과 하단을 가지고 알고 그리고 당신은 가지 그건 ... 떨어져 링크 나무는, 루트를 호출하는 상단이 다음 모든 주위 잎을 가지고있다. 

그리고 모든 당신은 여기에있다 다만 최상위 노드입니다 즉, 다른 노드에, 가리 포인트 더 많은 노드들, 및 등등 등등. 그래서 당신은 분할 지점을 가지고. 그것은 조직의 단지 다른 방법 데이터, 우리가 나무 호출하기 때문에, 너희들은 그냥 그냥 ... 나무처럼 밖으로 모델. 우리가 나무를 호출하는 이유입니다. 

해시 테이블은 테이블처럼 보인다. 나무는 나무처럼 보인다. 그것이 전부 별도 노드를 조직하는 방법 사용자의 요구가 무엇인지에 따라 달라집니다. 

그래서 당신은 루트를 가지고 당신은 잎이있다. 방법이 우리가 특히 수 이 이진 트리입니다 생각, 이진 트리 단지입니다 나무의 특정 유형 여기서 각 노드는 포인트 에, 최대의, 두 개의 다른 노드. 그래서 여기에 당신은 별개의이 당신의 나무에 대칭 즉, 쉽게 가지 볼 수 있습니다 값 무엇 당신은 당신 때문입니다 항상 왼쪽 또는 오른쪽 있습니다. 에서 왼쪽 세 번째처럼 결코 없다 왼쪽 또는 왼쪽에서 네 번째. 그것은 당신이 왼쪽과 오른쪽이 단지 당신은 그 두 가지 중 하나를 검색 할 수 있습니다. 그리고 왜이 유용합니다? 이되는 방법 당신이 찾고있는 경우에 유용입니다 오른쪽 값을 검색하는 방법? 오히려 바이너리를 구현하는 것보다 오류 배열 검색 당신은 노드를 삽입 할 수 원한다면 마음대로 또한 노드를 빼앗아 검색을 보존 이진 검색의 용량. 그래서이 방법으로, 우리는 종류의 것 때 기억 tricking-- 연결리스트는 이진 검색을 할 수 없습니다했다? 우리는 가지 데이터 구조를 만드는 트릭 작업에 그 것이다. 

그래서 때문에 연결리스트는, 선형 그들은 단지 차례로 연결한다. 우리는 종류의 수 있습니다 포인터의 다른 종류 서로 다른 노드를 가리키는 즉, 검색으로 우리를 도울 수있다. 그리고 여기, 경우 내가 원한 이진 검색 트리를 가지고, 나도 내 중간 그 (55)의 경우. 나는 단지를 만들거야 내 중간으로, 내 루트로, 다음 내가 가진거야 값은 그것의 스핀 오프. 

그래서 여기, 내가 검색거야 경우 (66)의 값은, 나는 55에서 시작할 수 있습니다. 그것은 55 이상 66 이상입니까? 네, 그것은, 그래서 내가 검색 뮤스 알고 나는 N이 트리의 오른쪽 포인터. 나는 77로 이동합니다. OK보다 작거나 77보다 66? 오, 그것보다, 그래서 당신이 알고, 즉, 왼쪽 노드 수있다. 

그래서 여기에 우리가 가지 보존하고 배열에 대한 중대한 것의 모든, 그래서 동적 크기 조정 등 객체로, 인 삽입하고 마음대로 삭제할 수, 고정에 대해 걱정할 필요없이 공간의 양. 우리는 여전히 모든 보존 그 놀라운 일들 또한 보존 할 수있는 동안 로그인 이진 검색의 시간을 검색 우리가 이전 만 있다고 문구를 얻을 수. 

쿨 데이터 구조, 종류의 복합체는, 노드를 구현하는 방법. 당신은 모든 것을 볼 수 있듯이 노드의 구조체이다 당신이 왼쪽을 가지고있다 그리고 오른쪽 포인터. 즉, 모든이다. 그래서 오히려 단지보다 X 또는 이전을 가진. 그런 다음 왼쪽 또는 오른쪽, 그리고이 당신은 가지를 함께 연결할 수 있습니다 그러나 그렇게 선택합니다. 

확인, 우리가 실제로거야 몇 분 정도 걸릴. 그래서 우리는 여기에 다시 갈 것입니다. 나는 이전에 말했듯이, 나는 종류의 설명 우리 방법 뒤에 논리 이를 통해 검색 할 것입니다. 우리는 시도 할거야 이 아웃 pseudocoding하면 볼 수 우리는 가지를 적용 할 수있는 경우 이진 검색의 같은 논리 데이터 구조의 다른 타입. 너희들은 몇처럼 먹고 싶어하는 경우 분은이에 대해 생각합니다. 그래. 좋아, 내가 갈거야 실제로 당신이 어떤을 가까이 대고주지, 우리는 먼저 의사에 대해 이야기 할 것입니다. 그래서 사람이 원하는 않습니다 에 자상을주고 무엇을 당신이 때 수행 할 첫 번째 일 당신은 검색이 밖으로 시작하는거야? 우리는을 찾고 있다면 (66)의 값은, 무엇이다 우리가 경우 수행 할 첫 번째 일 우리는이 트리를 검색 이진 싶어? 

청중 : 당신이 바로보고 싶어 및 [들리지]을 왼쪽을보고 참조 더 많은 수의. 

ANDI 펭 : 네, 정확히. 그래서 당신은 루트 볼 것입니다. 당신이 호출 할 수있는 많은 방법이있다 그것은 당신의 부모 노드 사람들은 말한다. 나는 때문에 루트를 말씀 드리고 이는 트리의 루트 같다. 당신은 볼거야 루트 노드, 당신은있어 볼가는 66 크다 이상 또는 55 미만. 그리고 물론, 그것이보다 큰 있다면 보다 큰, 우리는 어디에서 볼 하시겠습니까? 어디 우리가 바로 지금 검색 하시겠습니까? 우리는을 검색 할 이 나무의 오른쪽 절반. 

그래서 우리가 편리하게, 오른쪽을 가리키는 포인터. 그래서 우리는 설정할 수 있습니다 우리의 새로운 루트 77합니다. 우리는 어디든지 갈 수 포인터가 가리키는. 음, 아, 우리가 시작하고 77, 우리는 할 수 반복적으로 또 다시 이렇게. 이러한 방법으로, 당신 종류 의 기능을 갖는다. 당신은 당신이 있는지 검색하는 방법이 단지 이상 이상 이상 반복 할 수 있습니다, 당신이보고 싶은 위치에 따라 당신은 결국 값에 도달 할 때까지 당신이 검색하는 그. 이해가? 

나는 당신에게 실제를 보여 주려고 코드, 그리고 많은 코드이다. 필요가 흥분 없습니다. 우리는 그것을 통해 이야기 할 것이다. 

사실, 아니. 그건 그냥 의사였다. 좋아, 그냥 의사이었다 이는 조금 복잡, 하지만 완전히 괜찮아요. 여기에 모든 사람을 따라 다음? 루트가 null의 경우, 반환 거짓 그 의미하기 때문에 당신도 거기에 아무것도하지 않습니다. 

루트 N은 그렇다면 값이되어 있으면 당신이보고있는 하나 될 일이, 당신은 true를 돌려거야 당신이 알고 있기 때문에 당신은 그것을 발견했다. 하지만, 값이 작 으면 N의 루트가 아닌, 당신이있어 왼쪽을 검색 할 것 아이 또는 왼쪽 잎, 당신은 전화를 원하는대로. 및 루트 값보다 크면, 당신은 바로 트리를 검색 할거야, 다음 단지 기능을 실행할 검색을 통해 다시. 

그리고 루트는 널 (null)입니다 그 경우 당신은 끝에 도달 한 것을 의미? 즉, 더 당신이 가지고있는 의미 더 많은 잎을 검색하려면 당신은 나는, 오, 알고 그것은 여기에없는 것 같아요 내가 통해 검토 한 후 때문에 그것은 여기 없어 모든 일, 그냥 여기되지 않을 수 있습니다. 

그 모두에게 의미가 있습니까? 그래서 보존 이진 검색처럼 연결리스트의 기능을 제공합니다. 쿨, 그래서 제 2 타입 데이터 구조 너희들의 당신의 PSET에 구현하는 시도 할 수 있습니다, 당신은 단지 하나의 방법을 선택해야합니다. 그러나 아마 다른 방법에 해시 테이블은 우리가 트라이를 호출 할 것입니다. 

모든 트라이 인 나무의 특정 유형이 다른 값에 가서 값을 가지고있다. 그래서 대신에 바이너리를 갖는 의미에서 나무 하나 그 일이 두 가지를 가리킬 수 있습니다, 당신은 할 수 있습니다 많은, 많은 일을 한 가지 포인트. 당신은 본질적으로 배열을 가지고 그 중 당신이 저장 내부 다른 배열을 가리 포인터. 

그래서 우리는 방법의 노드 트라이을 정의하는 것 우리가 가지고 싶은 것입니다 부울, C 단어, 오른쪽? 따라서 노드는 부울 , 참 또는 거짓 같은 의 머리에 먼저 그 배열이 단어는? 둘째, 당신은 포인터를 갖고 싶어 무엇에 나머지입니다. 비트 단지, 비트 추상,하지만 나는 무엇을 모든 수단을 설명합니다. 

그래서 여기, 상단에, 당신의 경우 배열 이미 선언 한, 부울이 노드 전면에 저장된 값 즉,이 단어는 이야기? 이되지는 말씀인가요? 그리고 당신은이 배열의 나머지 그 실제로 저장 모든 그것이 될 수 있는지의 가능성. 따라서, 예를 들어, 추천 상단에, 당신은 true 또는 말한다 먼저 거짓, 예 또는 아니오,이 단어입니다. 

그리고 당신은 26을 통해 0이 당신이 저장할 수있는 문자. 나는 검색하고 싶다면 박쥐, 나는 상단으로 이동 그리고 내가에서 B를 찾을 B. 찾아 내 배열, 그래서 나는 알고있다, 확인, B는 말씀입니까? B 정도로 따라서, 워드 아니다 나는 검색을 유지해야합니다. 나는 B에서 이동하고 난에 보면 B쪽으로 가리키는 포인터 나는, 정보의 또 다른 배열을 참조 우리가 전에했던 동일한 구조. 

그리고, 오 다음을 here-- [들림]에 편지 A.입니다 그래서 우리는 그 배열에 봐. 우리는 여덟 번째 값을 찾아, 그리고, 우리는, 아,보고보고 이봐,하는 말 것을, B-은 단어인가? 이 단어가 아닙니다. 우리는 계속 찾고있어. 

그래서 우리는 어디에보고 포인트 포인터 그리고 다른 방법을 가리키는 이는 우리가 더 많은 값을 저장해야합니다. 그리고 결국, 우리는 도착 단어 B-A-T,. 그래서 다음 번에 당신이 보면, 당신은거야 예,의 확인을 가지고, 이 부울 함수는 사실이다. 그래서 의미에서 우리는 친절 배열과 나무를 가진. 

그럼 당신은 가지 아래를 검색 할 수 있습니다. 오히려 기능을 해싱 이상 및 연결리스트로 값을 할당, 당신은 단지를 구현할 수 있습니다 downwords 검색 트라이. 정말, 정말 물건을 복잡. 내가 좋아하는이기 때문에 생각하는 것은 쉽지 않다 많은 데이터 구조를 침 당신,하지만 가지 모두를 수행 이 논리가 작동하는 방법을 이해? 

그래 좋아. 그래서 B-A-T, 다음 당신은 검색 할 것입니다. 당신이거야 다음에 오, 이봐, 그 사실을 참조하고, 따라서 나는이 단어해야합니다 알고 있습니다. 

동물원에 대한 똑같은. 그래서 여기 일이 있다면, 지금의 우리 지금, 동물원을 검색하고 싶어, 현재 동물원은 아니다 우리의 사전에있는 단어 때문에 너희들은,를 볼 수 있습니다 우리는 부울이 처음 반환 진정한 줌의 끝 부분에 있습니다. 우리는 Z-O-O-M이있다. 

그리고 여기, 우리가 실제로 필요가 없습니다 우리 사전에 단어, 동물원, 이 확인란을 선택하지 않은 때문이다. 그래서 컴퓨터는하지 않습니다 동물원이 단어는 것을 알고 때문에 우리가했습니다 방법 만 줌 여기서, 저장 실제로 부울 값을 가지고 그는 사실 켜져 있습니다. 우리가를 삽입 할 경우에 따라서 단어, 동물원, 우리 사전에, 우리는 그 일에 대해 어떻게 갈 것인가? 우리는 확인해야 할 일을 우리의 컴퓨터는 Z-O-O 단어는 것을 알고있다 아닌 첫 번째 단어는 Z-O-O-M은? 

청중 : [들리지] 

ANDI 펭 : 정확히, 우리 이 있는지 확인하려면 여기, 그 부울 값입니다 그게 사실 것을 체크 해제. Z-O-O는, 우리는 그것을 확인하는거야, 그래서 우리는 정확하게, 헤이, 동물원 단어 알고있다. 나는 말할거야 이 단어는 그래서 컴퓨터 때 컴퓨터를 확인하는 이 동물원은 단어임을 알고있다. 

이러한 모든 데이터를 기억하고 있기 때문에 구조, 그것은 우리에게 매우 쉽다 오, 박쥐 단어의 말을한다. 동물원 단어입니다. 줌 단어입니다. 그러나 당신이 그것을 구축 할 때, 컴퓨터가 아무 생각이 없습니다. 

그래서 당신은 정확히 말할 필요 어떤 점에서이 단어는? 어떤 시점에서이 단어가 아니다? 그리고 어느 시점에서 내가 할 물건을 검색 할 필요가있다, 어떤 점에서 나는 다음에 갈 필요합니까? 그 명확한 모두? 시원한. 

그리고 다음 온다 의 문제를 우리가 어떻게 것 뭔가를 삽입하는 방법에 대한 이동 즉,이 사실이 아니다? 그래서 그냥 우리가 삽입 할 가정 해 봅시다 우리의 트라이로 단어, 목욕,. 너희들은 현재처럼 볼 수 있듯이 우리가 지금해야하는 것은, B-A-T입니다 이 새로운 데이터 구조 파인트가 있다고 우리가 생각하기 때문에 null로 지적 오, B-A-T 후 어떤 단어가 없습니다 것을, 왜 우리는 계속해야합니까 그 T. 후 물건을 가지고 

우리는 당신을한다면 문제가 발생 다음에 오는 단어를 갖고 싶어 T의. 당신이 목욕이있는 경우있어 H의 권리를 원하는 것. 그래서 우리가 그것을 할 거 야 방법은 우리는 별도의 노드를 만들 것입니다. 우리는 어떤 금액을 충당하지 않을 이 새로운 배열의 메모리, 우리는 포인터를 재 할당 할 것입니다. 

우리는을 할당 할거야 H, 우선,이 NULL, 우리는 제거하는 것입니다. 우리는 할 겁니다 H 포인트 아래로. 우리는 H를 참조하면, 우리는 원하는 다른 곳으로 이동합니다. 

여기에서 우리는 다음 예를 꺼 확인할 수 있습니다. 우리는 T 후 H를 칠 경우, 오, 우리는이 단어 것을 알고 있습니다. 부울 true를 반환하는 것입니다. 모두 무슨 일이 있었 방법에 대한 명확한? 그래. 

그래서 본질적으로, 모든 이러한 데이터 구조 우리가 오늘을 통해 갔어요 것을, 나는했습니다 정말, 정말 빨리 그들을 사라 그리고별로에의를 세부 사항, 그리고 괜찮아요. 당신은 장난 시작하면 그것으로, 당신은 수 있습니다 위치를 추적 유지 모든 포인터이다 무슨에서 일어나는 당신의 데이터 구조, 기타 등등. 그들은 매우 유용 할 것이다 그것은 당신에게 달려 있습니다 사람은 완전히 방법을 알아낼 당신은 물건을 구현하려는. 

그래서 pset4,의 5-- 아, 그건 잘못된 것입니다. Pset5는 맞춤법 오류입니다. 내가 전에 말했듯이, 당신은 한 번에가는거야 다시, 우리의 소스 코드를 다운로드합니다. 세 가지 주요있을거야 이것은 당신이 다운로드됩니다. 당신은 사전을 다운로드 할 수 있습니다 KERS, 및 텍스트. 

모든 것들은있다 두 단어의 사전 우리는 당신이 확인하고 싶은 것을 또는 정보의 테스트 우리는 당신이 체크를 주문하려는. 그래서 사전 우리는 당신이가는 줄 당신에게 우리가 원하는 실제 단어를 제공합니다 당신의 방식으로 어떻게 든 저장하기 보다 효율적인 어레이. 그리고 텍스트는 우리가있는 무슨 될 것 묻는 것이 있는지 확인하십시오 철자 모든 단어 실제 단어들이있다. 

의 그리고 세 블록 우리는 당신이주지 프로그램 dictionary.c라고, dictionary.h 및 speller.c. 그리고 모든 dictionary.c입니다 않습니다 당신은 무엇을 구현하도록 요청하고 있습니다. 그것은 단어를로드합니다. 그것은 검사에게 그 철자, 그리고 그것을 확인한다 모든 것이 제대로 삽입됩니다. 

diction.h 그냥 라이브러리 파일입니다 그 모든 기능을 선언합니다. 그리고 speller.c, 우리는 당신을 줄 것입니다. 당신은 어떤을 수정할 필요가 없습니다. 모든 speller.c은 그 걸립니까, 로드는, 그것의 속도를 확인 방법 등의 벤치 마크 테스트 빨리 당신은 일을 할 수있어. 

그것은 철자입니다. 그냥 엉망을하지 않습니다,하지만 확인 확실히 당신은 무엇을하고 있는지 이해합니다. 우리는 기능이라고 getrusage를 사용하는 당신의 주문의 성능을 테스트 체커. 모든 그것은 기본적으로 테스트됩니다 않습니다 당신의 사전에있는 모든 시간, 그래서 당신이 그것을 알고 있어야합니다. 그것으로 엉망 않도록주의 또는 다른 일들이 제대로 실행되지 않습니다. 

그리고 이러한 문제의 대부분은입니다 너희들은 정말 dictionary.c을 수정할 수 있습니다. 우리는 당신에게 줄거야 사전에 14 만 단어. 우리는 당신에게 텍스트를 줄거야 그 단어를 가지고 파일, 우리는 당신이 구성 할 수 있도록하려면 해시 테이블 또는 트라이로 우리가 주문하도록 요구하는 경우 때문에 당신이 마법이 있다면 상상 check-- 호머의 오디세이처럼 검사합니다. 그것은이 거대한, 거대한 테스트 같다. 

매일 상상해 단어 당신을 지켜 볼 수밖에 없었습니다 140,000 값의 배열을 통해. 즉 영원히 걸릴 것 컴퓨터가 실행하는. 우리가 우리를 구성하려는 이유입니다 더 효율적인 데이터 구조로 데이터 이러한 해시 테이블 또는 트라이있다. 그리고 너희들은 종류의 수 액세스를 검색 할 때의 것을 더 쉽게 더 빨리. 

그래서 충돌을 해결하기 위해주의해야합니다. 당신은 무리를받을거야 A.와 그 시작의 단어 당신은 한 무리의 단어를받을거야 즉, 최대 B. 시작 당신이 원하는 방법 사람들은 그것을 해결하기 위해. 아마도 더있다 효율적인 해시 함수 단지 첫 글자보다 뭔가, 그래서 그것은 당신에게 달려 있습니다 사람은 종류의 당신이 원하는 무엇이든 할 수 있습니다. 

어쩌면 당신은 추가 할 함께 모든 문자. 어쩌면 당신은 이상한 일을 같이 할 문자의 수를 설명하기 위해, 도대체 무엇이. 당신이 원하는 방법들까지. 당신은 당신이 경우, 해시 테이블을 수행 할 경우 전적으로 당신에게 달려, 트라이를 시도합니다. 나는 시간 앞서 경고합니다 트라이은 일반적으로 조금 더 어렵습니다 많이있다해서 더 포인터를 추적합니다. 그러나 완전히 너희들까지. 이것은 훨씬 더 효율적 대부분의 경우에. 당신은 정말 계속 할 수 있도록하려면 당신의 포인터의 모든 트랙. 마찬가지로 같은 일을 내가 여기서 일을하였습니다. 때 삽입하려는 해시 테이블에 값 또는 삭제 당신이있어 있는지 확인 정말를 추적 모든 것이 있기 때문이다의 이 난 경우 정말 쉽게 단어, 앤디처럼 삽입하려고합니다. 그냥 그 말할하자 실제 단어, 단어, 앤디, 단어의 거대한 목록에. 

난 그냥 재 할당하는 일 경우 포인터 잘못, 죄송합니다, 전체를 간다 내 연결리스트의 나머지. 이제 유일한 단어 나 이 앤디, 그리고 지금 에있는 다른 모든 단어 사전이 손실되었다. 그래서 당신은 당신이 있는지 확인하려면 당신의 포인터의 모든 추적 그렇지 않으면 당신은받을거야 코드에서 큰 문제. 단계별로 신중하게 물건을 그립니다. 그것은 생각하기가 훨씬 쉬워집니다. 

그리고 마지막으로, 당신은 할 수 있도록하려면 프로그램의 성능을 테스트 큰 보드에. 너희들이 걸릴 경우 지금 CS50를 보면, 우리는 큰 보드라고 무슨있다. 그것은 가장 빠른의 점수 시트입니다 CS50의 모든 걸쳐 검사 시간을 철자 지금, 나는 10 등의 상단을 생각 시간 나는 그들의 여덟 직원 생각합니다. 우리가 정말 너희들이 우리를 이길 원한다. 

우리 모두는 구현하기 위해 노력하고 있었다 가능한 가장 빠른 번호. 우리는 너희들이 도전하려고 시도하는 우리와 우리 모두보다 빠르게 구현 양철통. 그리고 이것은 정말 우리가있어 처음으로 너희들을 요구하는 것은 PSET을 수행하는 그 당신은 정말 어떤 방법으로 할 수있다 당신이 원하는. 

난 항상이 더 가깝다, 말 실제 솔루션, 오른쪽? 나는 안녕하세요, 당신이해야 할 말. 나를 위해이 작업을 수행하는 프로그램을 구축 할 수 있습니다. 당신이 원하는 그러나 그것을한다. 난 그냥 빨리 할 것을 알고있다. 즉,이 주에 대한 도전입니다. 너희들은, 우리는거야 당신에게 작업을 제공합니다. 우리는 당신에게 도전을 줄 것입니다. 그리고 그것은 너희들이야 완전하게 파악하기 가장 빠르고 무엇 효율적인 방법은이를 구현합니다. 네? 

청중 : 우리는 경우에 허용 되는가 빠른 방법을 연구하고 싶었 우리가 할 수있는 온라인 해시 테이블을 할 수 그와 누군가 다른 사람의 코드를 인용? ANDI 펭 : 네, 완전히 괜찮아요. 그래서 너희들이 읽는다면 사양은, 라인있다 너희들을 말한다 사양에 해시 조회 완전히 무료입니다 어떤 일부의 기능 빠른 해시 함수 등을 통해 일을 실행 당신이 그 코드를 인용 한. 그래서 어떤 사람들은 이미 빠른 방법을 알아 냈어 신속의, 맞춤법 검사기를하고 정보를 저장하는 방법. 완전히 너희들까지 당신 경우 바로, 그냥 먹고 싶어? 당신이 인용하고 있는지 확인합니다. 도전 여기에 정말 우리는 테스트를 위해 노력하고 있음 당신이 알고 있는지 확인하고있다 당신의 방법은 주위에 대한 포인터. 지금까지 당신이 구현으로 실제 해시 함수 과 등으로 올라오고 수학은 그렇게, 너희들은 연구 할 수 무엇이든 방법은 온라인 너희들은 할 수 있습니다. 네? 

청중 : 우리는 그냥 인용 수 [들리지]를 사용하여? 

ANDI 펭 : 네. 할 수 있습니다 만, 당신의 의견에, 당신이, 오, 같은 인용 수 궁시렁에서 촬영, 궁시렁, 궁시렁, 해시 함수. 누구나 어떤 질문이? 우리는 실제로 스레 오늘 섹션을 통해. 나는 여기까지가 될 것입니다 뿐만 아니라 질문에 대한 답변. 

또한, 내가 말했듯이, 사무실 시간 오늘 밤과 내일. 이번 주에 실제로 사양 아주 쉽게 읽을 슈퍼 짧은. 난 그냥 살펴 본다 제안 그것의 전체를 읽어. 

그리고 Zamyla 사실을 안내합니다 각 기능을 통하여 당신은 구현해야하고, 그래서있어 모든 작업을 수행하는 방법에 아주, 아주 분명. 그냥 당신이있어 만들려면 포인터를 추적. 이것은 매우 어려운 PSET이다. 

그것은 좋아하기 때문에 도전 아니에요 오, 개념은 훨씬 더 있습니다 어려운, 또는 당신은 배울 필요가 그런데 너무 많은 새 구문 당신은 마지막 PSET 위해 한 것이다. 이 PSET는 어렵 기 때문에 많은 포인터가, 다음은 한 번에 아주 쉽게 당신은 할 수 코드에서 버그가 그 버그가 어디에서 찾을 수 있습니다. 

그래서 완전하고 당신의 완전한 믿음 너희들은 우리의 [들리지]을 이길 수 있도록 철자. 나는 실제로하지 서면 광산이 아직,하지만 난 내 쓰기하려고 해요. 당신이 작성하는 동안 그래서 당신은, 난 내를 작성 할 수 있습니다. 내가 만들려고하는거야 내 빠른 당신보다. 우리는 가장 빠른 하나있는 사람을 볼 수 있습니다. 

그리고 그래, 나는 모두를 볼 수 있습니다 여기에 화요일에 너희들. 나는 PSET 워크샵과 같은 종류를 실행합니다. 모든 섹션이 주, PSET 워크샵입니다 그래서 너희들은 많은 기회를 도움, 업무 시간 언제나처럼, 와 정말 기대 당신의 남자 '모든 코드를 읽고. 나는 여기 경우 퀴즈를 가지고 사람은 사람들을 데리러 싶습니다. 그게 다야.