스피커 1 : 좋아, 그래서 이것은이다 CS50이 주 다섯의 끝입니다. 그리고 그 마지막 시간을 기억 우리 시작 애호가 데이터보고 해결하기 위해 시작 구조 소개하기 시작 문제, 새로운 문제가 있지만,이 열쇠 나사의 종류였습니다 우리 노드에서 노드로 수행하기 시작했다. 그래서 물론이다 단일 연결리스트. 그리고에 의해 단독으로 연결된 난 그냥 거기에 하나의 의미 그 각 노드 사이에 스레드. 당신은 애호가 수행 할 수 있습니다 밝혀 이중 연결리스트 같은 것들 당신은 화살표가된다 양방향으로 가고있는 특정 효율성에 도움이 될 수 있습니다. 그러나 이것은 문제를 해결? 이 무슨 문제를 해결하는 데 도움이 되었습니까? 우리는 월요일에 왜 관심을 했습니까? 왜, 이론적으로, 우리는 월요일에 관심을 했습니까? 그것은 무엇을합니까? 

청중 : 우리는 동적으로 크기를 조정할 수 있습니다. 

스피커 1 : OK, 우리가 할 수있는 그렇게 동적으로 크기를 조정합니다. 그럼 당신의 모두를 수행. 그래서 당신은 동적으로 크기를 조정할 수 있습니다 데이터 구조, 배열, 반면 리콜, 당신은 알고있다 선험적 공간이 얼마나 당신이 원하는 당신은 조금 더 필요로하는 경우 공간, 당신은 운이 가지입니다. 당신은 완전히 새로운 배열을 생성해야합니다. 당신은 모든 이동해야 당신의 다른 하나의 데이터, 결국 기존의 배열을 해제 당신이 할 수있는 한 후 진행하면. 어떤 단지 매우 비용이 많이 드는 느낌이 매우 비효율적, 실제로 그것을 할 수 있습니다. 그러나이 모두 좋지 않다. 우리는 가격을 지불 한 것이었다 더 확실한 가격의 우리 링크 된 목록을 사용하여 지불? 

청중 : 우리는 사용할 필요가 각각에 대해 두 공간. 스피커 1 : 그래, 그래서 우리가 필요로하는 두 배 이상 많은 공간이있다. 사실, 난 실현이 그림의 조금이라도 오해의 소지를, 때문에 현대의 많은에 CS50의 IDE에 컴퓨터, 포인터 또는 주소 사실 4 바이트에 있지 않습니다. 그것은 매우 자주이있어 일 8 바이트, 어떤 바닥 수단 가장 실제로이 직사각형 의 두 배 종류의 내가 그린 한 것과 큰, 이는 당신이 3 배를 사용하는 것을 의미 우리가 달리있을 수 있습니다 많은 공간. 지금 동시에, 우리는 야 여전히 바이트를 말하는 거죠? 우리는 반드시 이야기하지 않을 메가 바이트 또는 기가 바이트, 이러한 데이터하지 않는 구조는 큰 얻을. 

그래서 오늘 우리는 생각하기 시작 우리는 데이터를 탐색하는 방법 보다 효율적의 경우 사실은 데이터가 더 큰 가져옵니다. 그러나 이제 정규화 해보자 먼저 작업 당신은이에 할 수있는 데이터 구조 가지. 링크 같은 뭔가 목록은 일반적으로 지원 작업은 삭제 좋아, 삽입하고 검색 할 수 있습니다. 그리고 그 무엇을 의미합니까? 그건 그냥, 그 일반적 의미 사람들이 연결리스트를 사용하는 경우, 그들은 또는 다른 사람이 구현했습니다 삭제, 삽입 등의 기능, 및 검색, 당신은 할 수 있습니다 실제로 뭔가를 데이터 구조에 유용하다. 그럼 잠깐 살펴 보자 우리가 구현하는 방법에 연결리스트에 대한 몇 가지 코드는 다음과 같이 다음과 같습니다. 

그래서이 그냥 C 코드입니다, 심지어 완전한 프로그램 정말 빠르게 휘저어있다. 그것은 분포 온라인 아니다 코드, 실제로 실행되지 않습니다 때문이다. 하지만 난 그냥했습니다 통지 코멘트는 말했다와 함께, 점 점 점, 거기에 뭔가 가,가, 뭔가를 점 점 점. 그리고 그냥 살펴 보자 수분이 많은 부분은 무엇인지. 그래서 라인 세에, 이 지금 리콜 우리는 마지막 노드를 선언 제안 된 시간, 그 직사각형 개체 중 하나. 그것은, 우리가 N 전화 할게 int를 가지고 그러나 우리는 무엇을 호출 할 수 있습니다, 다음 구조체 노드 별은 다음했다. 그리고 바로, 그 두 번째 분명합니다 라인, 라인 여섯에, 그것은 무엇인가? 그것은 우리를 위해 무엇을하고 있는가? 그것은 확실히 더 보이기 때문에 우리 보통의 변수보다 더 애매. 

청중 : 그것은 하나를 통해 이동합니다. 

스피커 1 : 그것은 하나를 통해 이동합니다. 그리고, 더 정확하게하기 이는 주소를 저장할 될 운명이야 노드의 의미 옆에, 오른쪽? 그래서에 없을거야 반드시 아무것도 이동합니다. 그냥 것 인 값을 저장 주소 될 것 다른 노드, 우리가 구조체 말한 이유입니다 노드 스타, 스타 나타내는 포인터 또는 주소입니다. 좋아, 그럼 지금 당신은 우리가 있다고 가정하면 우리에게 사용할 수있는이 N 및하자 다른 사람이 있다고 가정 정수의 전체 무리를 삽입 연결리스트로. 그리고 링크 된 목록입니다 어떤 점 가리키는 의 변수라는 목록 매개 변수로 여기에 전달, 어떻게 라인 가야합니까 (14) 검색을 구현​​? 즉, 내가 구현하고있는 경우 그 목적은 인생의 기능 다음 INT와을하는 것입니다 연결리스트의 시작, 즉, 연결리스트에 대한 포인터입니다. 처음처럼, 나는 다윗을 누가 생각 우리의 자원 봉사는, 월요일에 있었다 그는 가리키는했다 전체 연결리스트, 우리가 통과하는 것처럼입니다 데이비드 여기에 우리의 인수로. 어떻게 우리는이 목록을 통과 가야합니까? 글쎄, 그것은 밝혀 그 비록 포인터는, 우리에게 지금 비교적 새로운 우리는 상대적으로이 작업을 수행 할 수 있습니다 노골적. 

나는 앞서 갈거야 및 임시 변수를 선언하는 규칙에 의해 단지 것입니다 에가, PTR 포인터라고, 또는 하지만 당신은 당신이 원하는 무엇이든을 호출 할 수 있습니다. 그리고 초기화거야 그 목록의 시작. 그래서 당신은 종류의이 생각할 수 내가 교사로서 다른 날, 종류의 사람을 가리키는 자원 봉사자로서의 인간 사이. 그래서의 임시 변수를 해요 단지 같은 것을 가리키는 우리는 우연히라는 것을 자원 봉사 다윗은 또한 지적했다. 이제 포인터가있는 동안 null이 아닌, 때문에 리콜 그 null가 특별한 감시 값 이리스트의 단부를 획정 내가 가리키는 아니에요 동안 그렇게 우리의 마지막 자원 봉사 등의 접지 이고,의 앞서 가자 그리고 다음을 수행하십시오. pointer-- 경우 지금은 종류의 원하는 우리는 학생했던 일을 structure-- 포인터 점 옆 경우 equals-- 포인터 점 N은, 동일 오히려 경우 이 변수 N은 같 에 통과의 주장, 나는 앞서 가고 싶어 그리고 true를 돌려 말한다. 나는 내부 수 없음을 발견했다 내 연결리스트의 노드 중 하나. 그러나 점 더 이상 이러한 맥락에서 작동, 포인터, PTR은, 때문에 실제로 포인터, 주소, 우리는 실제로 놀라 울 수 구문의 마지막 조각을 사용 차종의 종류 직관적 인 감각과 실제로 에서 이동 즉, 여기에 화살표를 사용하여 거기에 정수에 해당 주소. 그래서 매우 유사 도트 연산자에 정신 하지만, 포인터는 포인터 없기 때문에 아닌 실제 구조체 자체, 우리는 단지에있는 화살표를 사용합니다. 

경우에 따라서 현재 노드가 나는, 임시 변수가 가리키는입니다 N, 내가 무엇을 하시겠습니까되지 않는 이유는 무엇입니까? 글쎄, 내 인간 자원 봉사자 우리가 다른 날 여기 있다고, 내 첫 인간은 하나의 내가 아닌 경우 원하고, 어쩌면 두 번째 사람은 아니다 내가 원하는 한, 세 번째, 내가 이동 물리적으로 유지해야합니다. 마찬가지로 내가 어떻게 목록을 단계별로합니까? 우리가 배열이있을 때, 당신을 그냥 플러스 플러스 좋아했다. 그러나이 경우에 충분 다음, 포인터, 도착, 포인터를 않습니다. 즉, 다음 필드 왼쪽 손의 모든처럼 월요일에 우리의 인간 자원 봉사자 다른 노드를 가리 키도록 사용했다. 사람들은 자신의 다음 이웃이었다. 

나는이 목록을 통해 단계 싶다면, 난 그냥, 더 이상 내가 할 플러스 플러스 없습니다 내가 대신 말을해야 나는, 포인터는 것입니다 다음 필드는 어떤 같음, 다음 필드는 다음 필드가 있습니다 그 왼쪽 손 모두 다음 우리는 무대 가리키는 것으로 일부 이후의 값. 그리고 통과하는 경우 그 전체 반복, 그리고 마지막으로, 내가 가진 NOT NULL 히트 발견 N 아직, 난 그냥 false를 돌려줍니다. 그래서 다시, 우리가 여기서하고있는 모든 것을, 잠시 전에 그림에 따라, 가리키는 의해 시작 아마도 목록의 시작. 그리고 내가 확인 값입니다 나는 아홉 동일한 찾고 있어요? 그렇다면, 나는 true를 돌려 나는 끝났어요. 그렇지 않은 경우, 나는 내 손을 업데이트, 일명 포인터를 가리 키도록 다음 화살표의 위치에서, 그리고 그 다음 화살표의 위치, 그리고 다음. 간단히 말해서 나는 당신이 배열을 통해 걷고 있어요. 

그래서 다시, 누가 무슨 상관이 야? 마찬가지로이에 대한 성분 무엇인가? 글쎄, 우리가 도입 리콜 스택의 개념, 어느 그것의 같은 추상적 인 데이터가있는 한 유형입니다 하지 C 것은,이 CS50 일이 아니다, 그것은 추상적 인 아이디어의 생각 위에 다른 물건을 적재 즉 구현 될 수있다 다른 방법의 무리가. 그리고 우리가 제시 한 방법으로했다 배열, 또는 링크 된 목록. 그리고는 그 canonically 밝혀 스택은 두 개 이상의 작업을 지원합니다. 그리고 버즈 단어에, 푸시 있습니다 스택에 뭔가를 밀어 새로운 트레이 등 식당, 또는 팝업, 이는 최상위을 제거하는 것을 의미한다 식당에서 스택에서 트레이 홀, 그리고 어쩌면 일부 다른 작업뿐만 아니라. 그래서 우리가 어떻게 구조를 정의 할 수 있습니다 우리는 지금 스택을 호출하고 있는지? 

음, 우리는 필요한 모든이 내가 말할 C로 우리의 처분에 구문, 나에게의 타입 정의를 제공 스택의 내부 구조체, 나는의 배열은 말할거야 정수의 무리하고 크기. 그래서 다른 말로하면, 내가 원하는 경우 이 코드를 구현하기 위해, 내가 가서 그냥 가지하자 이 무슨 말을 그립니다. 이 말을 그래서, 나에게 줄 배열을 가지고 구조, 나는, 용량이 무엇인지 모른다 그것은 내가했는지 분명히 몇 가지 상수이다 다른 곳에서 정의하고, 그 괜찮아요. 그러나, 그것은 단지 하나의 가정 둘, 셋, 넷, 다섯. 그래서 용량은 5입니다. 내부에이 요소 내 구조 번호를 호출됩니다. 그리고 나에게도 필요 다른 변수 분명히 처음에 내가 갈거야라는 크기 0으로 초기화되는 규정합니다. 아무것도에 존재하지 않는 경우 스택, 크기는 제로 그것은 숫자에 쓰레기 값을합니다. 나는 아직 거기에 무슨 생각이 없다. 

내가 밀어 싶다면 스택에 뭔가, 내가 함수 푸시를 호출한다고 가정하고, 나는, 숫자 50과 같은 50를 밀어 말 어디 제안 것이다 나는이 배열에 그립니다? 다섯 가지 가능한 대답이있다. 당신은 어디에서 수 (50)를 밀어 하시겠습니까? 여기에 목표 경우, 다시 전화 기능 푸시는, 인수 전달 50, 나는 그것을 어디에 배치해야합니까? 다섯 possible-- 20 %의 확률로 의 제대로 추측. 네? 

청중 : 오른쪽. 

스피커 1 : 오른쪽. 25 %의 확률로 지금있다 의 제대로 추측. 그래서 사실은 잘 될 것입니다. 규칙에 따라, 나는 배열을 말할 것이다, 우리는 일반적으로, 왼쪽에서 시작할 것 그러나 우리는 확실히 할 수 오른쪽에서 시작합니다. 그래서 여기에 스포일러가 난 것 아마 왼쪽에 그리는 것, 다만 정상적인 배열 경우처럼 나는 왼쪽에서 오른쪽으로가는 시작합니다. 하지만 당신은 전환 할 수있는 경우 산술, 괜찮아요. 그냥 기존 아니다. 좋아, 내가 하나를 만들 필요가 하지만 더 변화. 지금은 뭔가를 밀어했는지 스택에, 다음은 뭐지? 

좋아, 내가 크기를 증가해야합니다. 그래서 내가 앞으로 그냥 가자 제로이었다이를 업데이트합니다. 그리고 대신에 지금은 갈거야 값 하나에 넣어. 그리고 지금은 서로를 밀어 가정 스택에 수 (51) 등을들 수있다. 글쎄, 난 하나 더 확인해야 크기 두 가지에 달려 변화. 그리고 내가 한 번 더 밀어 가정 (61)와 같은 스택에 수, 지금은 크기를 업데이트해야 하나 시간, 크기와 값 3을 얻는다. 그리고 지금은 팝업을 호출한다고 가정합니다. 지금 관례, 팝, 인수를하지 않습니다. 스택 전체 트레이 은유의 포인트 당신이 재량권을하지 않아도됩니다 용지함을 가서, 모든 당신은 할 수있다 에서 최상위를 팝업됩니다 스택, 단지 때문이다. 즉,이 데이터 구조가하는 일입니다. 

만약 그 논리에 의해 그래서 팝, 무엇을 벗기라고? 그래서 61. 그래서 정말 컴퓨터는 무엇인가 메모리에 할 건가요? 어떻게 내 코드는 무엇을해야합니까? 당신은 무엇을 제안 할 것이다 우리는 화면 변경? 무엇을 변경해야합니까? 죄송합니다? 그래서 우리는 (61)을 제거. 그래서 나는 확실히 그렇게 할 수 있습니다. 그리고 (61)을 제거 할 수 있습니다. 그리고 다른 무엇 변화가 일어날 필요가 있겠습니까? 크기는 아마 두로 돌아 가야한다. 그리고 그 괜찮아요. 그러나 분, 크기를 기다립니다 잠시 전 세였다. 그냥 빠른 전성 검사를 해 보자. 우리는 어떻게 우리가 알고 않았다 (61)을 제거하고 싶어? 우리가 보여주고 있기 때문에. 그래서 나는이 두 번째 공간이 있습니다. 

난, 잠깐 일주일에 두 다시 생각 우리는 얘기를 시작했을 때 이 위치 제로였다 배열, 이 위치 하나,이 위치했다 두,이 위치 셋, 넷입니다, 이처럼 보인다 크기 사이의 관계 내가 원하는 요소를 제거합니다 배열에서 바로 무엇을 것 같습니다? 크기 - 하나. 그리고 그 방법으로 인간의 우리는 (61)이 먼저 알고있다. 어떻게 컴퓨터가 알고있는거야? 때 코드, 어디를 아마 크기 마이너스 하나를 수행 할, 그래서 세 뺀 두하고 있다는 것입니다 우리는 (61)를 제거하는 것을 의미합니다. 그리고 우리는 참으로 업데이트 할 수 있습니다 그 크기가 너무 크기 지금 두 세에서 이동합니다. 그냥 학자로, 내가 갈거야 내가 바로, 끝났어요 것을 제안 하는가? 당신은 직관적 제안 제대로 나는 (61)을 제거한다. 그러나이없는 내가 가지 종류의 (61)을 제거이라도? 나는 효과적으로 잊어 버린 그것이 사실이있다. 당신이 읽은 경우에, 다시 PSET4에 대한 생각 법의학에 대한 문서, PDF 우리가 가진 것을 너희들은 읽기, 또는 PSET4이 주 읽습니다. 이 실제로 밀접한 관계가 있음을 기억하라 컴퓨터 법의학의 모든 생각. 어떤 컴퓨터가 일반적으로 수행하는 것입니다 뭔가가 어디 그냥 잊어 하지만 가서 좋아하지 않는다 그것을 또는 재정의 스크래치하려고 0과 1에 그 비트 또는 어떤 다른 임의의 패턴 당신이하지 않으면 자신은 그렇게 의도적으로 않습니다. 그래서 당신의 직관이었다 오른쪽의이 (61)을 제거 할 수 있습니다. 그러나 현실에서, 우리는 귀찮게 할 필요가 없습니다. 우리는 잊지 필요 그것은 우리의 크기를 변경하여이있다. 

지금이 스택에 문제가있다. 나는 일을 계속 밀고 경우 스택에, 무슨 일이야 분명히 일어날 것 단지 잠시 시간? 우리는 공간이 부족 될 것입니다. 그리고 우리는 무엇을해야합니까? 우리는 종류의 나사하고 있습니다. 이 구현은 할 수 없습니다 사용하기 때문에 우리는, 배열의 크기를 조정 이 구문, 당신의 경우 일주일에 두 다시 생각한다 당신은 선언 한 후 어레이의 크기, 우리는 아직 어디에 메커니즘을 보지 못했다 배열의 크기를 변경할 수있다. 그리고 실제로 C는 해당 기능이 없습니다. 당신이 말한다면 나에게 다섯 줄 Nths, 그들에게 전화 번호, 즉, 당신이 그것을받을거야 모두이다. 그래서 우리는 월요일로 지금,이 용액을 표현하는 능력 하지만, 우리는 단지 조정할 필요 우리 스택의 정의 일부 하드 코딩 배열하지 않으려면, 하지만 그냥 주소를 저장합니다. 

이제 그 이유가 무엇입니까? 이제 우리는 편안해야 사실 내 프로그램이 실행될 때, 나는 아마 갈거야 인간에게 물어, 얼마나 많은 숫자 당신은 저장 하시겠습니까? 그래서 입력 어딘가에서 온있다. 하지만 알고 나면 번호, 다음, 난 그냥 수 제공하는 기능을 어떻게 사용 나 메모리의 덩어리? 나는 malloc에​​ 사용할 수 있습니다. 그리고 임의의 수를 말할 수있다 바이트 내가 다시이 Nths에 대한합니다. 그리고 모든 나는 숫자에 저장해야 이 구조체의 내부 여기에 변수 무엇을해야 하는가? 무엇 실제로로 전환 이 시나리오의 숫자? 네, 첫 번째 포인터 메모리의 청크의 바이트, 또는보다 구체적으로는, 어드레스 그 바이트의 제. 이 하나 있다면 상관 없어 바이트 또는 억 바이트, 난 그냥 먼저 걱정해야합니다. 때문에 무엇 malloc을 보장하고 내 운영체제 보장 입니다 메모리 I의 덩어리 얻을, 그것은 인접 할 것입니다. 간격이있을 것 아니에요. 나는 50를 요구 한 경우에 따라서 바이트 또는 1,000 바이트, 그들은 모두가 될거야 다시 다시 다시합니다. 그리고 너무 오래 내가 어떻게 얼마나 큰 기억으로 많은 내가 알아야 할 모든 요구 최초의 주소입니다. 

그래서 지금 우리는 코드의 기능이 있습니다. 이기는하지만, 그것은 우리를 취할 것 더 많은 시간이를 쓰기 우리는 지금 그 메모리를 재 할당 할 수 그냥 거기에 다른 주소를 저장 우리는 심지어 더 큰 이상을 원하는 경우 메모리의 작은 덩어​​리. 그래서 여기에 무역 오프에. 이제 우리는 활력을 얻을. 우리는 여전히이 인접에 나는 주장하고있다. malloc을 우리에게 줄 것 때문에 메모리의 연속 된 덩어리. 하지만이에 통증이 될 것입니다 우리의 목, 프로그래머, 실제로 최대 코드. 그것은 단지 더 많은 작업입니다. 우리는 내가 무엇 유사 코드가 필요합니다 잠시 전 닌가. 아주 행할 수 있지만, 복잡성을 추가합니다. 그래서 개발자 시간, 프로그래머 시간은 또 다른 자원이다 우리가 지출해야 할 수도 있음 약간의 시간이 새로운 기능을 얻을 수 있습니다. 그리고 물론 큐가있다. 우리는이에 가지 않을 것이다 많은 세부 사항 하나. 하지만 정신에 매우 유사하다. 나는 큐를 구현하고 수 그 대응 작업, 대기열 또는 대기열에서 제외, 추가 또는 제거 등, 그것은, 그것을 말하는 단지 애호가 방법 인큐 또는 디큐로는 다음과 같다. 난 그냥 내 자신에게 구조체를 제공 할 수 있습니다 그 다시 숫자의 배열을 가지고, 또 그 크기를 갖는, 하지만 왜 지금해야합니까 큐의 앞을 추적하기 위해? 내가 알 필요하지 않았다 내 스택의 앞. 글쎄, 만약 내가 다시에 대한 queue-- 그냥 열심히하자 다섯 같이 갖는으로 코딩 여기에 잠재적으로의 정수. 그래서 이것은 제로, 하나, 둘, 셋, 넷이다. 이 될 것입니다 다시 호출 번호. 그리고이 크기라고한다. 

왜이 충분하지 단지 크기가 있습니까? 음,에 그 같은 번호를 눌러 보자. 그래서 나는 큐에, 또는 밀어 pushed--. 지금은 50을 대기열에, 그리고 것 51, 후 61, 도트는 도트와 도트. 그래서 대기열입니다. 나는 그 (61), 다음 (50), (51)의 대기열. 그리고 그와 동일하게 나타남 지금까지 스택, 를 제외하고 내가 한 변경을 할 필요가있다. 나는이 크기를 업데이트해야합니다, 그래서 이동 이제 2-3 to 하나 0에서. 어떻게 대기열에서 제외합니까? 무엇 디큐으로됩니까? 누가 먼저이 목록을 제공한다 그것은 애플 스토어에서 줄이 있다면? 그래서 50. 그래서 종류의 난이도가이 시간이다. 마지막 반면 수퍼했다 쉽게 그냥 크기 마이너스 하나를 수행합니다 나는 효과적으로 나의 배열의 끝에 도착 숫자가있는 곳, 그것은 61을 제거합니다. 그러나 나는 61를 제거하지 않습니다. 나는, (50)을 원하는 사람 오전 5시 00 분이 있었다 위해 줄을 새로운 아이폰 또는 이것 저것. 그래서 나는, 50 없애 바로,이 작업을 수행 할 수없는 이유는 무엇입니까? 나는 (50)을 통과 할 수 있습니다. 그러나 우리는 단지 우리를 말했다 그래서 항문 될 필요가 없습니다 로 밖으로 긁거나 데이터를 숨 깁니다. 그게 어디 우리는 잊을 수있다. 

그러나 나는 지금 나의 크기를 변경하는 경우 두 사람은이 충분한 정보입니다 내 큐에 무슨 일이 일어나고 있는지 알고? 정말. 내 크기가 두처럼하지만, 큐는 어디서부터 시작 않습니다, 특히 나는 아직도이있는 경우 메모리에 그 같은 숫자. 50, 51, 61. 그래서 기억해야 이제 앞입니다. 그래서 나는까지 제안 된 거기에, 우리는 단지라는거야 그의 초기 N 번째 앞, 값은 무엇을 했어야? 제로,리스트의 시작에 불과합니다. 하지만 지금은 추가로 감소시키는합니다 크기는, 우리는 단지 전면을 증가. 이제 여기에 또 다른 문제입니다. 그래서 계속 한 번. 이의 수를 가정 같은 121, 124, 다음, 젠, 나는 공간이 부족 해요. 하지만 난 아니에요, 분을 기다립니다. 이야기를이 시점에서 그래서, 크기가 하나, 둘 것을 가정, 셋, 넷, 그렇게한다고 가정 크기는, 전면이 하나이고, 4 개이고 그래서 51 앞에있다. 나는 여기에 다른 번호를 데려 가고 싶다는, 하지만, 젠장, 나는 공간이 부족 해요. 하지만 난 지금, 정말 아니에요? 좀 어디 넣을 수 (171)과 같은 부가 가치? 그래, 내가 할 수있는 단지 종류의 바로, 다시 거기 가서? 그리고 50을 교차, 또는 그냥 171으로 덮어. 그리고 당신은 왜 궁금해하는 경우 우리의 숫자는, 그래서 무작위있어 이들은 일반적으로 컴퓨터를 가져옵니다 CS50 후 하버드 대학 과학 교육 과정. 하지만 좋은 최적화이었다, 지금 때문에 공간을 낭비하고 있지 않다. 나는 아직도 기억해야 얼마나 큰이 일 총입니다. 그것은 다섯 총입니다. 에 내가 원하는하지 않기 때문에 (51)을 덮어 쓰기 시작합니다. 그래서 지금은 아직 공간이 부족입니다, 그래서 같은 문제 이전. 하지만 당신은 어떻게 지금 볼 수 있습니다 코드에서, 당신 아마 더 조금 작성해야 복잡성은 그렇게 할 수 있습니다. 그리고 사실, 어떤 연산자 C 아마 수 있습니다 당신은 마술이 원형합니까? 네 모듈로 연산자 퍼센트 기호. 그래서 큐에 대한 종류의 멋진 무엇을, 우리는 드로잉 배열을 유지하더라도 이와 같은 직선으로, 당신의 경우 종류의 커브 등이 생각 주위에 원으로, 그럼 그냥 직관적으로는 가지 정신적으로 작동 좀 더 명확하게 조금 생각합니다. 당신은 여전히​​ 구현해야 할 것이다 코드에서 그 정신 모델. 그래서없는 어려운, 궁극적으로, 구현 하지만 우리는 여전히 오히려 size--을 잃게 우리는이 작업을 수행하지 않는 기능, 크기를 조정합니다. 

우리는 배열을 제거해야 우리 하나의 포인터로 교체, 다음 어딘가에 내 코드에 내가있어 실제로 생성하는 기능을 무엇 전화 배열이라는 숫자? malloc에​​, 또는 이와 유사한 기능, 정확하게. 스택 또는 큐에 대한 질문. 그래? 좋은 질문. 무엇을 모듈로 여기에 사용합니다. 그래서 일반적으로, 사용시 모드는, 당신은 그것을 할 것 의 크기 전체 데이터 구조. 그래서 뭔가 5 용량, 경우 같은 이 상수의, 아마 참여하고있다. 그러나 단지 모듈로 다섯을하고 아마도 불충분 우리가 알 필요가 있기 때문에 우리가 할 여기 또는 여기 또는 여기에 랩 어라운드. 그래서 당신은 아마도있어 포함 할 것 물건의 크기, 뿐만 아니라 전면 변수입니다. 그래서 그냥이 상대적으로있어 간단한 산술 식, 그러나 모듈은 핵심 요소가 될 것입니다. 

그래서 단편 영화가됩니다. 애니메이션 그 일부 다른 대학에서 사람 우리가했습니다 것을 함께 넣어 이 토론에 적합. 그것은 잭 학습 포함 큐와 통계에 대한 사실. 

영화 : 옛적에 한 번, 잭이라는 사람이 있었다. 이 친구 만들기에 왔을 때, 잭은 숙련 된 기술을 가지고 있지 않았다. 그래서 잭은 얘기했다 가장 인기있는 남자 그는 알고 있었다. 그는 루에 가서 어떻게해야합니까 물어? 루는 그의 친구 것을보고 정말 고민했다. 글쎄, 그는 단지, 시작 당신이 옷을 입고있는 방법을 찾습니다. 당신은 어떤 옷이 없으십니까 다른 모습? 네, 잭 말했다. 나는 확실하지. 우리 집에 와서 나는 당신에게 보여줄 것이다. 그래서 그들은 잭에 떨어져 갔다. 그리고 잭 루​​에게 상자를 보여 주었다 여기서 그는, 그의 셔츠를 유지 자신의 바지와 양말. 루는 내가 당신이 참조 말했다 더미에서 모든 옷. 왜 일부를 착용하지 않는다 잠시 한번 다른 사람? 

잭이 말했다 잘 때 , 옷과 양말을 제거 나는 그들을 씻어 넣어 그들을 멀리 상자에. 그런 다음 온다 아침, 최대 나는 홉. 나는 상자에 가서 얻을 상단 떨어져 내 옷. 루 빨리 실현 잭의 문제. 그는, 옷, CD를 보관 스택 책. 그는 위해 도착했을 때 뭔가를 읽거나 착용, 그는 최고 책이나 속옷을 선택 것입니다. 그리고 그는이 완료되었을 때, 그는 바로 다시 넣어 것입니다. 다시는 스택의 상단에, 갈 것입니다. 나는 해결책을 알고있다, 승리의 큰 소리로 말했다. 당신은 배울 필요 큐를 사용하기 시작. 루 잭의 옷을 가져다가 옷장에서 그들을 걸려. 그리고 그는 비워했을 때 상자, ​​그는 단지 그것을 던졌다. 

그리고 그는 잭의 말에, 지금은 말했다 하루, 왼쪽에 옷을 넣어 당신이 그들을 멀리 둘 때. 그럼 내일 아침에 때를 당신의 옷을 입고, 햇빛을 볼 수 라인의 끝에서 오른쪽에. 당신은 표시되지 않는 이유는 무엇입니까? 루는 말했다. 너무 좋은 것입니다. 당신은 한 번에 모든 것을 착용합니다 전에 두 번 뭔가를 착용하십시오. 그리고 큐의 모든과 그의 옷장 선반에, 잭 느끼기 시작 자신의 확신. 루에 대한 모든 감사와 그의 멋진 큐. 스피커 1 : 좋아, 그것은 사랑스러운입니다. 그래서 정말 가고 무슨 지금은 후드 아래에? 우리가 포인터를 가지고, 우리의 malloc을 가지고, 우리가 만들 수있는 능력을 가지고 있다는 자신의 메모리의 덩어리 동적. 그래서이 사진 우리는 그냥 다른 하루 엿볼. 우리는 정말 연연하지 않았다 거기에,하지만이 사진 아래에있다가 계속되고 지금 주 후드. 그리고 이것은 단지, 대표 우리가 그린 한 사각형, 컴퓨터의 메모리. 그리고 어쩌면 당신의 컴퓨터 또는 CS50 ID는, 메모리 또는 RAM의 기가 바이트를 가지고 두 기가 바이트 네. 정말 중요하지 않습니다. 운영 체제 Windows 또는 Mac OS 또는 Linux, 기본적으로 프로그램을 할 수 있습니다 이 액세스 할 수 있는지 생각하는 전체에 컴퓨터의 메모리, 심지어 당신이 실행 될 수 있지만 한 번에 여러 프로그램. 그래서 현실에서, 그건 정말 작동하지 않습니다. 그러나 그것은 환상 종류의 모든 프로그램에 주어진. 그래서 만약 당신이이 RAM의 두 기가 있었다 컴퓨터가 생각할 수있는 방법이다. 

지금 우연히, 이들 중 하나 것들, 이들의 메모리 세그먼트들 중 하나, 스택이라고합니다. 그리고 실제로 모든 시간 지금까지 코드를 작성에서 당신이라는 것을 인스턴스 주에 대한 기능,. 언제든지 내가했는지 기억 그린 컴퓨터 메모리, 난 항상 종류의 그릴 여기에 사각형의 절반 얘기 귀찮게하지 않습니다 위의 무엇에 대해. 주를 호출 할 때, 내가 주장 때문에 당신은 메모리의 은색를 얻을 즉, 여기에 내려갑니다. 주요 만약 함수 호출 스왑처럼 잘 스왑 간다. 그리고 그건, 밝혀 어디가 끝입니다. 스택라는 뭔가 컴퓨터의 메모리의 내부. 지금의 일 단부에, 이것은 단지 주소입니다. 그것은 바이트 제로처럼 바이트 한 바이트 20 억. 하지만 당신은 그것에 대해 생각하는 경우 이 직사각형의 객체로서, 모든 우리는 모든 일을하고 시간 우리는 함수가 호출 메모리의 새 슬라이스를 레이어링. 우리는 슬라이스 해당 기능을 제공하고 있습니다 자신의 메모리와 함께 작동합니다. 

그리고이 중요하다는 것을 지금 기억합니다. 우리가 가지고있는 경우 때문에 스왑과 같은 A와 B와 같은 두 개의 지역 변수 우리는 하나, 둘에서 그 값을 변경 둘, 하나, 리콜 스왑 반환 때, 그것은이 슬라이스 것처럼있어 메모리 다만 사라 졌어요. 사실상, 그것은 여전히 이 포렌식. 그리고 무언가가 실제로 아직 거기입니다. 그러나 개념적으로, 그것은으로의 하지만 완전히 사라 졌어요. 그리고 주요 작품의 어떤을 알 수 없습니다 즉, 그 스왑 기능에 이루어졌다 그것은 실제로 그 전달 경우 제외 포인터 또는 참조를 기준으로 인수. 이제, 근본적인 해결책 스왑과 그 문제 주소로 물건을 전달합니다. 하지만 너무 무엇이다, 밝혀 그 부분 이상 계속되고 구형의 모든 시간이다 아직 더 많은 메모리 업이있다. 그리고 때 동적 메모리를 할당, 그것은하여 GetString, 내부 여부하는 우리는 CS50에 당신을 위해 해왔습니다 라이브러리 또는 너희들 경우 malloc에​​ 전화해서 물어 덩어리의 운영 체제 메모리, 그것은 스택에서 오지 않는다. 또 다른 곳에서 유래 컴퓨터의 메모리에 그는 힙이라고. 그리고 그 어떤 다른 아니다. 이 같은 RAM입니다. 동일한 메모리이다. 그것은까지 그냥 RAM의 이 대신에 여기까지. 

그래서 그게 무슨 뜻 이죠? 글쎄, 당신의 컴퓨터가있는 경우 메모리 한정된 양 스택은 그렇게 성장하고있다 말을하고, 힙, 따라하기 이 화살표로, 아래로 성장하고있다. 즉, 모든 시간 당신이 malloc을 호출, 당신은 조각을 주어지고있어 메모리의 위, 조금 후, 낮은 어쩌면 조금 낮은, 당신이 malloc을 호출 할 때마다, 힙, 그것은 사용이다, 종류의 성장, 무엇에 점점 더 가까이 성장? 스택입니다. 그래서 이것은 좋은 생각처럼 보인다? 정말 확실하지 않다 어디 말은, 당신은 다른 무엇을 당신이하는 경우에만 할 수있다 메모리의 유한 한 양이있다. 그러나 이것은 확실히 나쁘다. 그 두 개의 화살표가 있습니다 서로에 대한 과정을 충돌. 

그리고 그 나쁜 사람, 사람들 밝혀 프로그래밍 특히 좋다 와 컴퓨터에 해킹을 시도, 이 현실을 악용 할 수 있습니다. 사실, 이제 생각 해보자 작은 조각. 그래서 당신이 읽을 수있는 예입니다 대한 위키 백과에 대한 상세. 우리는 당신을 가리키는 것 기사의 경우 호기심. 그러나 공격은 일반적으로있다 버퍼 오버 플로우로 알려진 그 인간만큼 오랫동안 존재했다 조작 할 수 있었다 특히 C에서 컴퓨터의 메모리, 그래서이 매우 임의적 프로그램은, 하지만 이제 바닥부터 읽어 보자. ARGC의 문자 스타 ARGV에 주. 그래서 걸리는 프로그램입니다 명령 줄 인수. 그리고 모든 주요 분명히 전화는 않습니다 기능은 단순화를 위해 F를 호출합니다. 그리고 그것은 무엇에 통과? 하나의 ARGV. 그래서 F로 통과 어떤 단어는 사용자가 입력 한 것입니다 후 프롬프트에서 프로그램의 이름에서 모든. 그래서 많은 시저 또는 Vigenere, 같은있는 당신은 ARGV와 함께 일을 불러올 수 있습니다. 

그래서 F는 무엇인가? F는 문자열에 소요 단독 인수로, 일명 숯 스타, 같은 일, 문자열로. 그리고 임의로라고 이 예에서 바. 그리고 숯불 C (12), 그냥 쉽게 설명하자면, 우리를 위해 일을 숯불 C 브라켓 (12)은 무엇인가? 그것은 무엇을 할거야? 구체적으로는, 메모리를 할당 12 문자 12 바이트. 정확히. 그리고 마지막 줄, 저어 사본, 당신은 아마 본 적이 없다. 이 문자열의 복사본입니다 그 목적은 인생의 기능 두 번째 인수를 복사하는 것입니다 첫 번째 인자로, 하지만 최대 바이트의 특정 번호. 그래서 세 번째 인수는 말한다 당신은 얼마나 많은 바이트를 복사해야합니까? 막대의 길이, 무엇이든에 입력 한 사용자. 및 내용 이며, 그 문자열을 바 메모리에 복사 ℃에서 지적했다 

그래서이 종류의 바보 같은 것, 그리고 그것입니다. 그것은 인위적인 예입니다, 그러나 대표자 공격 경로의 클래스, 프로그램을 공격 방법. 모든 고급 사용자가있는 경우 좋은 11 문자의 단어 유형 적은, 플러스 백 슬래시 제로 나. 무엇보다도 사용자의 유형을 더 있다면 11, 12, 20 또는 50 자? 할 일이 프로그램은 무엇입니까? 잠재적 SEG 오류. 그것은거야 맹목적으로 최대 표시 줄에 모든 것을 복사 자사의 길이에 문자 그대로 표시 줄에 모든 것을, 주소로 C. 그러나 C에서 지적 단지 선제 12 바이트로 부여하고있다. 그러나 추가 검사가 없습니다. 조건없는 경우가있다. 여기에 검사 오류가 없습니다. 

그리고이 프로그램은 무엇인가 할 거 그냥 맹목적이다 다른 한 가지를 복사합니다. 그래서 우리는이를 그릴 경우 그림으로, 여기에 메모리 공간의 단지 슬리버. 그래서 우리는 바닥에 알 지역 변수 바있다. store-- 것 그 포인터 그래서 사용자들은 로컬 인수 오히려 문자열 줄을 저장하는 것. 그리고 바로 알 위에 스택, 때문에 당신이 물어 때마다 스택에 메모리, 그것은 조금 간다 그림으로 위, 우리가 12 바이트를 가지고 통지. 왼쪽 상단 하나는 C 브라켓 제로입니다 오른쪽 아래 하나는 C 브래킷 (11)이다. 즉 얼마나 컴퓨터의 를 배치하는 것. 그래서 그냥 직관적으로, 줄이 더있는 경우 를 포함하여 총 12 자보다 인 백 슬래시 제로, 12 C 브라켓 (12)은 갈? 또는 오히려 여기서 12입니다 문자 또는 13 문자, 가는 백 문자 사진에서 생을 마감하는 방법? 위 또는 아래에? 

마우스 오른쪽 단추로, 비록 때문에 스택 자체가 상방으로 성장 당신은에 물건을 넣어 일단 그것은, 그 설계 이유로 위에서 아래로 메모리를 저장합니다. 당신은 12 개 이상의 바이트를 가지고 있다면, 당신은 줄을 덮어 쓰기 시작하는 것입니다. 이제 버그는,하지만 그건 정말 큰 문제. 이 때문에 그러나 그것은 큰 문제이며, 메모리에 계속 더 많은 물건. 그래서 여기에 우리가 어떻게 힘이다 명확하게하기 위해, 안녕하세요했습니다. 나는 프롬프트에서 인사에 입력합니다. H-E-L-L-O 백 슬래시 제로, 내 끝 그 12 바이트는, 우리는 매우 안전 해요. 모두가 잘됩니다. 하지만 뭔가를 입력하면 이상, 잠재적입니다 바 공간으로 크리프 것. 그러나 더 나쁜 아직, 그것은집니다 이 모든 시간 초과, 우리는 얘기 적이없는 경우에도 그것은 스택은 다른 재료에 사용됩니다. 그것은 단지 지역 변수 아니다. 

C는 매우 낮은 수준의 언어이다. 그리고 그것은 일종의 비밀 또한 스택을 사용 때 기억 기능은 무엇이라고 어드레스는 이전의 함수이며 그래서 다시 그 기능에 이동할 수 있습니다. 그래서 주요 통화 중 교체 할 때 일이 스택으로 푸시 있습니다 단지, 지역 변수를 스왑하지 또는 인수, 또한 비밀리에 추진 스택에 나타낸 바와 같이 여기에 빨간색 조각에 의해, 메인의 주소는 물리적으로 컴퓨터의 메모리에, 그래서 스왑이 완료, 컴퓨터 나는 주에 다시 갈 필요가 알고 및 주요 기능을 실행 완료. 그래서, 지금은 위험한 경우 때문에 안녕하세요보다 잘 이상에서 사용자 유형, 사용자의 입력이되도록 쳤을 또는, 그 빨간 부분을 덮어 만약 논리적 컴퓨터 그냥 맹목적으로 가정 할 것 그 붉은 조각의 바이트는 것을 이 반환해야되는 주소, 상대가 어떤 경우 충분히 스마트 또는 바이트의 순서를 넣어 충분히 운 이 주소처럼 보이는, 하지만 코드의 주소이다 그 또는 그녀가 컴퓨터를 원한다고 대신에 메인으로 실행하는 방법? 

즉, 어떤 경우를 사용자는 프롬프트에 입력됩니다 다만 일이 아니다 안녕하세요 무해한 같은 하지만 상당의 코드는 실제로이다 이 모든 사용자의 파일을 삭제하려면? 아니면 나에게 자신의 암호를 이메일을 보내? 또는 로깅을 시작 그들의 키, 오른쪽? 방법이있다,,의 오늘 규정하자 그들은 안녕하세요 단지를 입력 할 수 있음 세계 또는 이름, 그들은 본질적으로 수 코드, 제로에 전달하고 사람, 그 컴퓨터 코드와 주소를 모두 실수. 이기는하지만 그래서 다소 추상적으로, 경우 충분히 적대적 코드에서 사용자 유형 우리가 여기로 일반화거야 A. 공격 또는 적이다. 그러니 그냥 나쁜 물건. 우리는 걱정하지 않는다 숫자 또는 제로 또는 사람 오늘, 당신은 결국 있음 그 빨간 부분을 덮어 쓰기, 바이트의 순서를 알 수 있습니다. O 835 C 제로 여덟 제로. 그리고 지금 여기에 위키 백과의 문서로 당신이 지금 실제로 시작하는 경우, 제안했다 컴퓨터의에서 바이트를 라벨 메모리는 Wikipedia 기사는 무엇인가 제안하는이며, 그 어떤 주소의 경우 그 왼쪽 상단 바이트의 80 ℃ 0 3508입니다. 

즉, 나쁜 사람이면 자신의 코드로 똑똑 실제로 여기에 숫자를 넣어 그 코드 어드레스에 대응 그 또는 그녀는 주입 컴퓨터에, 당신 컴퓨터를 속일 수 있습니다 아무것도에. 파일을 제거 이메일 일, 트래픽 스니핑, 말 그대로 아무것도 될 수있다 컴퓨터에 주입. 그리고 버퍼 오버 플로우 그것의 핵심 공격 그냥 바보, 바보 배열의 최우선 그 그 경계를 확인하지 않았다. 그리고 이것은 매우 위험한 것입니다 동시에 슈퍼 강력한 C에서 우리가 참으로이 없다는 것입니다 메모리 어디서나 액세스 할 수 있습니다. 그것은 우리에게 달려, 프로그래머, 사람은 원래의 코드를 작성 어떤의 이놈의 길이를 확인하는 우리가 조작하고 배열. 그래서 명확하게하기 위해, 수정은 무엇인가? 우리는이 롤백 경우 코드, 내가하지 말아야 단지 막대의 길이를 변경, 무엇 다른 내가 확인해야합니까? 다른 내가에 일을해야 전적 공격을 방지? 난 그냥 맹목적으로 말하고 싶지 않습니다 당신은 많은 바이트를 복사해야 로 바의 길이입니다. 나는로 복사하고 싶은 말 많은 바이트 줄에 할당 된 최대 메모리 또는 최대로 (12). 그래서 조건의 경우 어떤 종류의 필요 그 줄의 길이를 확인하지 않습니다, 그러나 12, 우리 단지 하드 코드를 넘으면 최대 가능한 거리로 12. 그렇지 않으면 소위 버퍼 오버 플로우 공격이 발생할 수 있습니다. 그 슬라이드의 맨 아래에서, 당신은 자세한 내용을 궁금하다면 실제 원본 기사입니다 당신을 살펴보고하려는 경우. 

하지만 지금은 가격 중 비 효율성이 여기에 있었다 지불했다. 그래서 빠른이었다 에서 낮은 수준의 모양 무엇 문제는 우리가 지금이 발생할 수 있습니다 컴퓨터의 메모리에 액세스 할 수 있습니다. 그러나 또 다른 문제 우리 이미 월요일에 발견 바로 비 효율성이었다 연결리스트의. 우리는 다시 선형 시간입니다. 우리는 더 이상 연속 배열이 없습니다. 우리는 랜덤 액세스 할 수 없습니다. 우리는 대괄호 표기법을 사용할 수 없습니다. 우리는 문자 그대로 while 루프를 사용해야합니다 처럼 나는 잠시 전에 썼다. 그러나 월요일에, 우리는 우리가 할 수있는 주장 효율성의 영역으로 다시 크리프 뭔가를 달성 로그 어쩌면, 또는 가장 아직, 어쩌면 심지어 뭔가 일정 시간 소위. 그래서 우리는 이러한 새로운를 사용하는 것이 어떻게 할 수 도구,이 주소,이 포인터, 우리 자신의 일을 스레딩? 글쎄, 있다고 가정 여기에, 이러한 무리입니다 우리는에 저장할 수의 효율적으로 데이터 구조 및 검색. 우리는 절대적으로 일주일에 되감기 할 수 있습니다 두 사람은, 배열에이 던져 이진 검색을 사용하여 검색. 분할하고 정복. 그리고 사실 당신이 쓴 PSET3에서 이진 검색, 위치를 찾기 프로그램을 구현했습니다. 하지만 당신은 무엇을하는 것은 알고있다. 더 많은 종류가있다 이렇게 영리한 방법. 그것은 조금 더있어 정교하고 그것을 아마 우리는 왜 바이너리 볼 수 있습니다 검색은 훨씬 더 빨리 그렇게입니다. 먼저, 소개하자 나무의 개념. 어느도에 불구하고 현실 나무 가지 컴퓨터의 세계에서,이 같은 성장 그들이 종류의 하향 성장 과학 당신이 가족 나무처럼 당신의 조부모 또는 증조부모 또는 이것 저것 상단 족장에서와 가족의 족장, 한 루트 노드 아래 소위 그 아이들이있는이다, 그 이하의 어린이, 또는 그 자손 더 일반적. 그리고 사람이 걸려 가족의 바닥 나무,되고 게다가 가족의 막내, 또한 단지 일반적으로 할 수있다 나무의 잎했다. 

그래서 그냥 무리입니다 단어와 정의 뭔가 컴퓨터에있는 나무라고 과학, 가족 나무처럼 많이. 그러나 애호가 화신을 거기에 나무, 하나의 이진 검색 트리라고합니다. 그리고 당신은 할 수 있습니다 애타게 가지 이 일을 수행 떨어져 무엇. 글쎄, 그것은 어떤 의미에서 진입니까? 어디 이진 여기에서 오는가? 죄송합니다? 너무 많은 중 하나 또는 아니에요. 이것은 각 노드가 더 있는지를 더 이상의 두 아이, 우리는 여기에서 볼 수있다. 일반적으로, tree--에서와 당신의 부모와 조부모 많은 아이를 가질 수 있습니다 또는 손자가 실제로 원하는대로, 그래서 예를 들어 거기에서 우리는 세 가지가 그 오른쪽 노드 오프 어린이, 하지만 이진 트리에서 노드 갖는다 최대로 0, 1, 또는 두 아이. 그리고는, 좋은 숙박 시설의 이 두 가지로 덮인 거라면 때문에, 우리는 할 수있을거야 작은 로그 기반을 얻을 두 작업은 여기에 궁극적으로 진행. 그래서 우리는 로그 뭔가가있다. 그러나 잠시 그​​에 대한 자세한. 탐색 트리 수 있다는 의미 배치되도록 왼쪽 아이의 루트 값보다 크다. 그리고 오른쪽 아이는 루트보다 크다. 즉, 당신이 중 하나를 사용할 수있는 경우 노드,이 그림의 원, 그 왼쪽에 보이는 자녀와 오른쪽 아이, 첫 번째는,보다 작아야합니다 두 번째는보다 커야합니다. 그래서 정신은 (55)을 선택합니다. 그것은 아이를 남아 (33)이다. 그것은 이하이다. 55, 오른쪽 아이는 77입니다. 이는보다 큰이다. 그리고 그 재귀 적 정의이다. 우리는 그 하나 하나 확인할 수 있습니다 노드 및 보유하는 것과 동일한 패턴입니다. 

그래서에서 좋은거야 이진 검색 트리이고, 그 하나는, 우리는이를 구현할 수 구조체로, 그냥이를 좋아한다. 그리고 우리는 던지고있어 비록 당신의 구조를 많이, 그들은 다소있어 직관적 인 지금 희망. 구문은, 아직 확실히 비밀입니다 그러나,이 노드에서의 내용 context-- 우리는 계속 단어 노드를 사용하여, 그것은 사각형의 여부 화면 또는 원에, 그것은, 그냥 일반 컨테이너의 같은 나무의이 경우, 우리는 우리가 정수를 필요로했다 각 노드에서 그리고, 나는 두 개의 포인터를 가리키는 필요 왼쪽 자식, 오른쪽 아이에게, 각각. 그건 어떻게 우리가 수도 구조체에 그를 구현한다. 그리고 내가 어떻게 코드를 구현할 수? 음, 빠른 보자 이 작은 예를 살펴 보자. 그것은 작동하지 않습니다,하지만 난했습니다 복사 및 그 구조를 붙여. 그리고 만약 바이너리 내 기능 검색 트리, 검색이라고합니다 이 두 인수를, 정수 N과 포인터 트리 노드, 그래서 포인터 또는 트리의 루트에 대한 포인터, 어떻게 N을 찾고 가야합니까? 음, 첫 번째, 내가이기 때문에 포인터를 처리, 나는 정신 검사를 할거야. 트리 등호가 null 같다면, N은 이 나무의 여부를이 나무에? 그것은 바로,이 될 수없는 이유는 무엇입니까? 내가 널 과거입니다 경우, 거기에 아무것도 없다. 나는 수도뿐만 아니라 단지 맹목적으로 false를 돌려 말한다. 당신은 내게 아무것도주지 않으면, 내가 확실히 할 수 없습니다 숫자 N을 찾을 수 밖에 그래서 나는 수도 지금 확인하세요? 내가 아니라 다른 N 인 경우는 말할거야 트리 노드에서 무엇이든 이하 나는 N 값을 넘겨 봤는데. 즉, 숫자 I는 요한다면 N, 찾고, 노드보다 작 내가 찾고 있어요 그. 그리고 노드는 내가 찾고 있어요 트리라고에, 그리고 앞의 예에서 리콜 포인터의 값에 얻을 수 있습니다, 나는 화살표 표기법을 사용합니다. N은 나무 화살표보다 작다면 N, 나는 개념적으로 왼쪽으로 가고 싶어. 나는 어떻게 왼쪽들을 검색 명시합니까? 이 경우, 명확하게하려면 문제의 사진, 나는 통과 한 최상위 그 그 아래로 가리키는 화살. 그건 내 나무 포인터입니다. 나는 트리의 루트를 가리키는거야. 내가 들어 말을 찾고 있어요 임의 수 (44). 보다 44 작거나 분명히 55보다 큰? 그래서 미만이다. 그리고이 경우 조건이 적용됩니다. 그래서 개념적으로, 내가 무엇을 하시겠습니까? 나는 44을 찾고 있다면 다음 검색? 그래? 

정확히 내가 원하는 왼쪽 아이를 검색, 또는이 사진의 왼쪽 서브 트리. 그리고 사실, 저를 통해 할 수 아래로 여기 사진 단지 잠시, 이후 나는이를 긁지 수 있습니다. 나는 55에 여기에 시작하고, 경우 내가 알고있는 값 (44) 이다 위해 내가 찾고 있어요 왼쪽, 그것은 종류의 에서의 전화 번호부 등에 찢어 절반 또는 절반에 나무를 찢어. 나는 더 이상 걱정 할 필요가 없습니다 나무의이 전체의 절반입니다. 그럼에도 불구하고, 호기심의 관점에서 구조, 여기에 이​​상이 일 33로 시작하는 자체, 그 이진 검색 트리입니다. 때문에 나는 전에 단어가 재귀 말했다 실제로 이것은 데이터 구조는 그 정의에 의해 재귀입니다. 당신이있어 나무가있을 수 있습니다 큰,하지만 그 아이의 모든 하나 작은 조금 트리를 나타냅니다. 대신의 할아버지 인 또는 할머니, 지금은 엄마의 or-- 나는 엄마하지 say-- 수 없습니다 또는 아빠, 그 이상이 될 것이다. 이 대신에 두 아이 형제와 형제처럼 될 것입니다. 가계도의 새로운 세대. 그러나 구조적으로, 같은 생각입니다. 그리고 내가 기능이 밝혀 있는 나는 이진 검색을 검색 할 수 있습니다 트리. 그것은 검색이라고합니다. 나는 나무 화살표 왼쪽에 N 검색 N이 값보다 큰 경우에 다른 것을 나는 현재에있어. 조금 전에 이야기 (55). 나는라는 기능을 가지고 검색이 난 그냥 수 N이를 통과하고 반복적으로 검색 서브 트리 그냥 반환 무엇이든 그 대답. 그렇지 나는 여기에 몇 가지 최종 기본 케이스를 가지고있다. 

마지막 경우는 무엇인가? 나무 중 하나 nul​​l입니다. 나도 찾고 있어요 값은 그것보다보다 작거나 큰 또는 동일. 그리고 나는 동일을 말할 수 동일하지만, 논리적이다 여기 다른 말을하는 것과 같습니다. 그래서 사실은 내가 뭔가를 찾을 방법이다. 그래서 희망이있다 더욱 강력한 예 바보 시그마 기능 이상 우리는 다시 몇 강의를했다 어디 루프를 사용하는만큼 쉬웠다 하나에서 모든 숫자를 계산하는 데이터 구조와 여기에 N. 그 자체가 재귀 적입니다 우리는 지금, 정의 반복적으로 그려 자신을 표현하는 능력을 가지고 코드 자체는 재귀입니다. 그래서 여기에 동일한 코드입니다. 

그래서 우리는 다른 어떤 문제를 해결할 수 있습니까? 멀리 그래서 빠른 단계 단지 잠시 나무. 여기에, 독일 국기를 말한다. 그리고 분명히있다 이 플래그 패턴. 그리고 많이있다 세계 플래그 그 측면에서이만큼 간단합니다 자신의 색상과 패턴의. 그러나 이것은 저장된다고 가정 .GIF 또는 JPEG 또는 비트 맵 또는 핑, 어떤 그래픽 파일 포맷 있는 당신이 잘 알고 우리가있어 그 중 일부 PSET4에서 함께 연주. 이 저장하는 가치가하지 않는 것 검은 픽셀, 검은 픽셀, 검은 픽셀, 점, 점, 점,의 모두 첫 번째 주사선 검은 픽셀, 또는 행, 다음 왕창 같은, 다음 왕창 다음 같은, 그리고 빨간색 픽셀의 전체 무리, 적색 픽셀, 적색 픽셀, 다음 전체 노랑 픽셀의 무리, 오른쪽? 

이러한 비 효율성은 여기에있다. 어떻게 직관적으로 당신 것 독일 국기를 압축 파일로 구현하는 경우? 어떤 정보처럼 우리를 할 수 없습니다 위해 디스크에 저장 귀찮게 등으로부터 우리의 파일 크기를 줄일 수 있습니다 킬로바이트, 뭔가 메가 바이트 작은? 상기 리던던시 놓여 여기에 명확하게하는 방법? 당신은 무엇을 할 수 있습니까? 그래? 정확히. 왜보다는 기억 모든 이놈 픽셀의 색상 당신이 PSET4에서하고있는 등 비트 맵 파일 형식으로, 왜 당신은 단지를 대변하지 않습니다 예를 들어 픽셀의 왼쪽 열, 검은 픽셀의 무리, 무리 빨간색과 노란색의 무리, 다음 그냥 어떻게 든를 인코딩 반복의 생각이 100 배 또는이 1,000 번 반복? 경우 100 또는 1000입니다 그냥 정수, 당신 때문에 단지 하나의 번호로 멀리 얻을 수 있습니다 대신 수백 또는 수천의 추가 픽셀. 그리고 실제로, 그것은 어떻게 우리를이다 독일 국기를 압축 할 수있다. 과 프랑스 국기에 대한 지금 무엇? 어떤 종류의 그리고 조금 정신 운동하는 플래그 디스크에 더 압축 할 수 있습니까? 독일 국기 또는 프랑스 플래그, 우리는 그 접근 방식을 경우? 독일 국기, 거기 때문에 더 수평 중복. 그리고 디자인으로, 많은 그래픽 파일 형식은 참으로 스캔 라인을 작동합니까 수평. 그들은 일할 수있는 수직, 단지 인류 결정 년전 우리는거야 일반적으로 일 행의 생각 열을 기준으로 행 대신 열을 기준으로. 그래서 실제로 당신이 인 경우에 파일을 보시려면, 독일 국기와 프랑스의 크기 플래그, 너무 오래 해상도 그대로 같은, 동일한 폭 높이, 이것 여기가 더 될 것입니다 당신 때문에 자신에게 세 번을 반복해야합니다. 당신은 파란색, 반복을 지정해야 자신을, 흰색, 빨간색, 자신을 반복 자신을 반복합니다. 당신은 모든 갈 수 없어 오른쪽 방법. 그리고 옆으로, 만들려면 압축을 취소 이러한 경우, 어디에나 video--에서 4 개의 프레임 당신 영화 리콜 있습니다 또는 비디오는 일반적으로 초당 29 또는 30 프레임 등을들 수있다. 그것은 작은 플립 북처럼 어디를 단지 이미지, 이미지, 이미지, 이미지 참조 이미지는 슈퍼 빠른 그래서 그것은처럼 보인다 화면의 배우가 이동하고있다. 다음은 꿀벌에이다 꽃의 무리의 상단. 그리고 그것은 종류의 수 있습니다하지만 첫 눈에 보이지, 이동 유일한 이 영화는 꿀벌입니다. 

어떤 것은 저장에 대한 바보 비디오 압축 해제? 이는 비디오를 저장하는 폐기물의 종류의 네 개의 거의 동일한 이미지로 그 만하는 한 벌입니다으로 다르​​다. 당신은 멀리 던질 수있는 가장 정보의 만 기억, 예를 들면, 제 프레임과 최종 프레임, 당신이했습니다 경우 키 프레임 지금, 말씀을 듣고 단지에 저장 꿀벌은 중간. 그리고 당신은 필요 없어 , 핑크 모두 저장할 파랑 및 및 녹색 값뿐만 아니라. 그래서 이것은 단지라고하는 것입니다 압축은 어디 에나있다. 우리가 자주 사용하는 기술이다 요즘 부여이나 걸릴. 

그러나 당신은 어떻게 텍스트를 압축합니까? 당신은 어떻게 텍스트를 압축 가야합니까? 음, 문자의 각 ASCII는 한 바이트, 또는 8 비트이다. 그리고 그 종류의 바보, 맞아? 당신은 아마를 입력하기 때문에 그리고 E와 I와 O 및 U 많은 더 자주 W 또는 Q 또는 Z와 같은보다, 언어에 따라하는 당신은 확실히 쓰고있어. 그리고 왜 우리가 사용하는 모든 문자에 8 비트, 적어도 포함 인기있는 문자, 오른쪽? 왜에 대한 적은 비트를 사용하지 슈퍼 인기있는 편지, E와 같은 일들이 당신이 생각 첫 번째 행운의 휠에, 그리고 더 많은 비트를 사용 덜 인기있는 편지? 왜? 우리가 갈거야 때문에 자주 사용할. 

음, 거기가 밝혀 이 작업을 수행하려고 시도되었습니다. 그리고 당신은 학년에서 기억 경우 학교 또는 고등학교, 모스 부호. 모스 부호는 점이 대시는 할 수 와이어로 함께 전송 소리 또는 어떤 종류의 신호. 하지만 모스 부호는 슈퍼 깨끗합니다. 이 글은 이진 시스템의 종류의 것을 당신은 점 또는 대시가 있습니다. 하지만 당신은, 예를 들어, 두 개의 점을 볼 경우. 아니면 운영자에 다시 생각하는 경우 누가, 삐, 삐, 삐 같이 간다 음, 약간의 트리거 타격 즉, 신호를 송신하고, 당신이 경우,받는 사람, 두를 수신 점은, 어떤 메시지가 수신 한? 완전히 임의의. 

내가? 내가? 또는 무엇 비슷해 또는 I? 아마 두 전자의 권리인가? 그래서이 문제가있다 모스와 decodability의 코드, 이에 않는 당신에게 메시지를 보내는 사람 실제로 그래서 당신의 정렬 할 수 있습니다 일시 정지 참조 또는 문자 사이의 간격을 듣고, 그것은 단지에 충분한 아니다 0과 1의 스트림을 전송, 또는 점과 대시, 모호함이 존재하기 때문이다. E는 하나의 점, 그래서 당신 경우 두 개의 점을 참조하거나 두 개의 점을 듣고, 아마 두 개의 전자의 나 어쩌면 하나 I.의 그래서 우리는 A의 시스템이 필요 보다 더 영리한. 그래서 사람의 이름 허프만 년 전 바로이 함께했다. 그래서 우리는 단지거야 빠른 눈을 촬영합니다 방법에 나무이 밀접한 있습니다. 이 몇 가지 있음을 가정 보내려는 바보 메시지, 다만 A, B로 구성, C의 D의와 E의, 하지만 중복이 많이 여기에있다. 그것은 영어로 의미가 아니에요. 그것은 암호화 아니에요. 그냥 바보 메시지이다 반복이 많은. 당신은 실제로 아웃 카운트 그래서 만약 모든 의, B의, C의, D의 및 E 년대는 여기 주파수. 편지의 20 %는 의, 편지의 45 % 전자의, 3 다른 주파수이다. 우리는 수동으로이 카운트 업 그냥 수학을했다. 

그래서 밝혀 허프만, 얼마 전에, 당신이 알고있는, 실현 무엇을, 나는 건물을 시작하는 경우 나무, 또는 나무의 숲, 만약에 당신, 다음과 같이, 나는 다음과 같은 작업을 수행 할 수 있습니다. 나는 각 노드를 줄거야 내가 걱정하는 편지 내가 저장거야 해당 노드의 내부 부동 소수점과 같은 주파수 값은, 또는 당신은, 너무, N을 사용할 수 있습니다 그러나 우리는 여기 float를 사용합니다. 그리고 알고리즘이 그는 당신 즉 제안 단일 노드의 숲을 나무, 그래서 슈퍼 짧은 나무, 당신은 그들을 연결 시작 새 그룹, 새 부모가됩니다. 그리고 당신은을 선택하여이 작업을 수행 한 번에 두 개의 작은 주파수. 그래서 10 %와 10 %를했다. 나는 새로운 노드를 만들 수 있습니다. 그리고 새로운 노드에게 20 %를 호출합니다. 

어떤 두 개의 노드 내가 다음 결합? 그것은 조금 모호하다. 그래서 일부 코너 케이스를있다 고려하지만, 꽤 물건을 유지하기 위해, 나는 20 %를 선택하는거야 - 지금은 아이들을 무시합니다. 내가 20 %를 선택하는거야와 15 %는 두 개의 새로운 가장자리를 그립니다. 그리고 지금하는 두 개의 노드 나는 논리적으로 결합합니까? 모든 아이들, 모든 무시 손자, 그냥 뿌리를 보면 지금. 어떤 두 개의 노드 나는 함께 묶어합니까? 지점이 0.35. 그래서 내가 두 개의 새로운 가장자리를 그릴 수 있습니다. 그리고 나는 단 하나의 왼쪽을 가지고있다. 그래서 여기에 나무입니다. 그리고 의도적으로 그려져있어 종류의 예쁜보고, 그러나 가장자리가 알 또한 0과 1로 표시되었습니다. 그래서 좌변 모두 제로이다 임의로하지만, 지속적으로. 모든 오른쪽 가장자리가 그들이다. 

그리고 호프만,이 제안 무엇 당신이 B를 표현하려면, 로 숫자 66을 나타냅니다보다는 팔 전체 비트 아스키, 당신은 무슨, 그냥 가게를 알고 패턴 제로, 제로, 제로, 제로는 경로의 때문에 내 나무에서 씨 허프만의 나무, 루트에서 잎에. 당신을 저장하려면 E 대조적으로,하지 E.를 나타내는 8 비트를 전송 대신 비트 어떤 패턴을 보내? 하나. 그리고이 약 좋은거야 그 E는 가장 인기있는 문자입니다, 당신은을 사용하는 그것에 대한 짧은 코드입니다. 다음으로 가장 인기있는 편지는 같다 A.이었다 그리고 얼마나 많은 비트 그는 그것을 위해 사용 제안 했는가? 0 개, 1 개. 

그리고 그것은 구현 있기 때문에 이 나무로, 지금은 내가 거기에 규정하자 모스와 같이 모호성 없습니다 코드의 모든 때문에 당신이 걱정 편지 이들 에지들의 단부에있다. 그래서 그냥 하나 나무의 응용 프로그램입니다. 이은 ... - 나는 파도합니다 이에 내 손 방법을 C 구조로이를 구현 할 수 있습니다. 우리는 결합해야 기호, 문자 등, 및 주파수에 좌우. 그러나의 두 가지를 살펴 보자 마지막 예는거야 후 꽤 익숙해 문제의 퀴즈 제로 다섯을 설정합니다. 

따라서 데이터 구조가 해시 테이블로 알려진. 그리고 해시 테이블의 종류입니다 이 버킷을 갖는 것을 냉각. 그리고 네 개의 버킷이 겠 여기에, 단지 4 개의 빈 공간. 여기에 여기에 한 벌의 카드는, 그리고 클럽, 스페이드, 클럽, 다이아몬드, 클럽, 다이아몬드, 클럽, 다이아몬드, clubs-- 그래서 이것은 랜덤입니다. 하트, hearts-- 그래서 해요 여기에 모든 입력을 bucketizing. 그리고 해시 테이블 요구 귀하의 의견을보고, 다음 일정에 넣어 당신이 보는 무엇을 기준으로 배치합니다. 이 알고리즘입니다. 그리고 슈퍼를 사용했다 단순한 시각적 알고리즘. 의 가장 어려운 부분이었다 그림이 무엇인지 기억. 그리고 네 총 것들을있다. 

이제 스택, 성장 된 여기에 의도적 인 디자인 일이다. 그러나 나는 다른 무엇을 할 수 있는가? 그래서 실제로 여기에 우리가 오래된 학교 시험 책의 무리. 한 무리한다고 가정 학생 이름은 여기에 있습니다. 여기에 더 큰 해시 테이블입니다. 대신 네 개의 버킷, 나는의 26 가정 해 봅시다했다. 그리고 우리는 (26)을 빌려 가고 싶지 않았다 외부 [에서 물건? 애넌 버그?], 그래서 여기를 대표하는 다섯이다 Z까지 그리고 만약 내가 누구의 이름으로 시작하는 학생을 볼 나는 거기에 자신의 퀴즈를 넣어거야. 누군가가 C로 시작하면, 저기, 그럼하지 머 실제로 그렇게하고 싶지 않았다. B는 여기에 간다. 그래서있어 A와 B와 C 그리고 지금 여기에 또 다른 학생입니다. 그러나 해시 테이블이면 배열로 구현, 나는 종류의 나사 해요 이 시점에서, 오른쪽? 나는 종류의이 곳을 넣을 필요가있다. 

그래서이 문제를 해결할 수있는 한 가지 방법은 모든입니다 오른쪽은 C가 통화, B가 통화 중, 통화 중입니다. 나는에 그래서 D에 집어 넣어거야 첫째, 임의 즉시 액세스 할 수 있습니다 학생들을위한 버킷의 각. 그러나 지금은 종류의 양도 것 뭔가 선형으로, 내가 사람을 검색 할 경우 때문에 누구의 이름으로 시작, 나는 여기에서 확인. 하지만이 아닌 경우 내가 찾고 학생, 나는 종류의 검사를 시작해야 양동이, 내가 무슨 짓을했는지 때문에 의 선형 종류이었다 데이터 구조 프로브. 보고있는 것만 말하는 바보 방법 첫 번째 사용 가능한 개방, 그리고, 말하자면, 플랜 B로두고 또는이 경우 계획 D, 값 해당 위치에. 이 것을이 당신이했습니다 경우 바로 그래서이다 26 곳과없는 학생들을 얻었다 이름 Q 또는 Z, 또는 무엇인가 등으로 것을, 적어도 당신은 공간을 사용하고 있습니다. 

그러나 우리는 이미 더 봤어요 여기에 영리 솔루션, 오른쪽? 대신 무엇을 할 것입니다 당신은 충돌이있는 경우? 두 사람이있는 경우 이름, 무슨 일이 것 스마트 이상이었다 단지보다 직관적 인 솔루션 D가 있어야하는데 퍼팅? 왜 그냥 가지 마세요 외부 [? 애넌 버그?], malloc에​​, 다른 노드처럼 넣어 여기에 다음 여기에 학생 것을 넣어. 나는 본질적으로 가질 수 있도록 배열의 일종, 또는 우리가있는 한 아마도 더 우아하게 연결리스트를보기 시작. 

그래서 해시 테이블 구조 즉, 그냥 다음과 같을 수 있습니다 하지만 더 영리하게, 당신은 무엇인가라는 별도의 체인, 이에 해시 테이블 간단히 배열의 각이고, 요소가 숫자가 아닌, 연결리스트는 자체입니다. 당신은 슈퍼 빠른 액세스를 얻을 수 있도록 경우에 값을 해시를 결정할. 많은 카드의 예와 같이, 나는 슈퍼 빠른 결정을했다. 하트 다이아몬드는 간다, 간다. 여기에 같은, 여기 간다, D는 B가 간다, 간다. 그래서 슈퍼 빠른 조회를 한 경우 당신은 경우에 실행하는 일이 당신이있어 충돌, 두 같은 이름을 가진 사람, 그럼 당신은 이들과 결합하고 시작합니다. 그리고 어쩌면 당신은 그들을 정렬 유지 알파벳, 어쩌면 당신은하지 않습니다. 그러나 적어도 지금 우리는 역 동성을 가지고있다. 그래서 한편으로 우리는 슈퍼 빠른 있습니다 일정 시간, 그리고 선형 시간 가지 이러한 연결리스트 경우 참여 조금 긴 얻을 시작합니다. 

그래서 바보 같은 이런 종류의, 전 괴짜 농담 년. CS50 해킹 - 마라톤에서, 학생들이 체크인 할 때, 일부 TF 또는 CA 매년 생각이 올려 재미 이 같은 기호, 어디 그냥 이름이로 시작하면 의미, 이 길을 갈. 이름이 시작되는 경우 B로,이 항아리 확인을 이동 그것은 아마 나중에 학기 재미있다. 그러나 다른있다 또한,이 일의 방법입니다. 다시 그에게 가자. 

그래서이 구조가있다. 그리고 이것은 우리의 마지막 오늘 구조, 이는 트라이라고 무언가이다. 어떤 이유로 짧은 T-R-I-E, 검색을 위해,하지만 트라이라고. 그래서 트라이는 또 다른 재미 이 아이디어의 많은 아말감. 그것은 우리가 전에 본 적이 트리입니다. 그것은 이진 검색 트리 아니다. 그것은 아이들의 수와 나무의 하지만 트라이의 아이들의 각 배열입니다. 크기의 배열, 26 아니면 27 말 당신은 하이픈 이름을 지원하려는 경우 또는 사람의 이름에 아포스트로피. 

그리고이 데이터 구조이다. 그리고 당신은 정상에서 보면 아래로,이 마음 , 거기 최상위 노드, M 봐 이 왼쪽 일을 가리키는 이는 다음, X, W, E, L은, L. 이것은이다 다만 데이터 구조 임의로 그 사람의 이름을 저장합니다. 그리고 맥스웰은 다음에 의해 저장된다 배열 배열 배열의 경로입니다. 트라이는 약하지만 놀라운 무엇 그 연결리스트 반면, 심지어 배열은, 우리가 이제까지받은 것 중에 최고입니다 선형 시간 또는 로그 시간을 찾고 사람입니다. 트라이의 데이터 구조, 경우에 내 데이터 구조는 하나의 이름을 가지고 나는 맥스웰을 찾고 있어요, 내가 해요 꽤 빨리 그를 찾을 것. 난 그냥 M-A-X-W-E-L-L을 찾습니다. 만약 이 데이터 구조에 대조적으로, 가 있다면 N은, 만 인 경우 이 데이터 구조 만 이름 맥스웰은 계속 될 것입니다 검색 가능 단지 M-A-X-W-E-L-L 후 단계. 그리고 David-- D-A-V-I-D 단계. 즉, 구축하여 의 데이터 구조 있어 이러한 배열의 모든, 모두의 자체는, 랜덤 액세스를 지원 나는 사람들의를 찾고 시작할 수 있습니다 시간의 양을 사용하여 이름 하지 수에 비례 데이터 구조의 것들, 같은 만 존재하는 이름. 그것을 찾기 위해 나를 걸리는 시간 M-A-X-W-L-E-L 데이터 구조로되어 비례하지 않음 데이터 구조의 크기, 그러나 이름의 길이. 그리고 현실적으로 이름은 우리가 찾고있어 결코 긴 미친 될 것 없습니다. 아마 누군가가 10 문자가 20 문자의 이름입니다. 그것은 바로, 확실히 유한입니까? 지구에 인간이 누구 가장 긴 이름을 가진, 하지만 그 이름은 상수 값 길이, 오른쪽? 그것은 어떤 의미에서 변화하지 않습니다. 그래서이 방법으로, 우리는했습니다 데이터 구조를 달성 즉 일정 시간 룩업입니다. 이것은 다수의 단계를 거쳐야 입력의 길이에 따라, 이름이 아닌 번호 데이터 구조. 우리는 이름들의 수를 두 배로한다면 억 이십억로부터 다음 해, 발견 맥스웰은 걸릴 것입니다 일곱 단계의 동일한 번호 그를 찾을 수 있습니다. 그래서 우리는 달성 한 것 같다 실행 시간의 우리의 성배. 

너무 빨리 발표의 커플. 퀴즈 제로 올라오고있다. 코스의 웹 사이트에 그에 대한 자세한 앞으로 며칠 동안. 월요일은 휴일이다 lecture-- 여기 하버드 월요일에. 또한, 뉴 헤이븐에없는 그래서 우리는 수업을하고 월요일에 강의를위한 뉴 헤이븐에. 모든 것이 촬영한다 그리고, 평소와 같이 라이브 스트리밍 하지만의 오늘 종료하자 30 초 클립 소위 "깊은 생각" Daven 판햄에 의해하는 토요일 지난해 영감을했다 밤 라이브의 "깊은 생각" 잭 핸디으로하는 지금은 이해합니다. 

영화 : 그리고 지금, "깊은 Daven 판햄으로 생각 ". 해시 테이블. 

스피커 1 : 좋아, 그건 지금은 그것 뿐이다. 우리는 다음 주에 볼 수 있습니다. 

더그 : 행동을 참조하십시오. 그래서 지금 그 살펴 보자. 그래서 여기, 우리는 정렬되지 않은 배열을 가지고있다. 

이안 : 더그, 당신은 앞으로 다시 시작 갈 수 한 초이, 제발. 좋아, 카메라는 그래서, 압연된다 행동이 더그, 준비가 될 때마다 확인을? DOUG : 좋아, 그래서 우리 여기에있는 것은 정렬되지 않은 배열입니다. 그리고 모든 요소를​​ 색깔했습니다 이 사실을 나타 내기 위해 빨간색, 정렬되지 않은. 그래서 먼저 우리가 리콜 우리는 어레이의 왼쪽 절반을 정렬한다. 그 다음 우리는 오른쪽으로 정렬 배열의 절반입니다. 그리고 나중에 - 다, 아 -​​ 다, 아 -​​ 다, 우리는 함께 병합. 그리고 우리는 완전히 정렬 된 배열을 가지고있다. 그래서 작동 일종의 병합 방법입니다. 

IAN : 워, 워, 워, 컷, 컷, 컷, 컷. 더그, 그냥 나중에 - 다 할 수없는, 아 -​​ 다, 아 - 다, 병합 정렬을 통해 당신의 방법. 

더그 : 난 그냥했다. 괜찮아. 우리는 갈 수 있어요. 그냥 롤링을 유지하자. 어쨌든, 

이안 : 당신은 설명 할 필요 그것을 더 완벽하게보다. 그건 그냥 충분하지 않습니다. DOUG : 이안, 우리는하지 않습니다 하나로 돌아갈 필요가있다. 괜찮아. 어쨌든, 우리는 merge--를 계속하는 경우 이안, 우리는 촬영 중간에있어. 

이안 : 알아. 그리고 우리가 나중에 - 다 할 수없는, 아 -​​ 다, 전체 과정을 통해 아 - 다. 당신은 어떻게 설명 할 필요 양측이 함께 병합 얻는다. 

DOUG :하지만 우리는 이미했습니다 설명 방법이 sides-- 

이안 : 당신은 그냥 보여 주었다 그들을 병합 배열입니다. 더그 : 그들은이 과정을 알고있다. 그들은 괜찮아요. 우리는 그 위에 열 번 갔어요. 

이안 : 당신은 바로 그 위에 생략. 우리는 하나 다시거야, 당신 그 위에 당신이 나중에 - 다, 아 -​​ 다 할 수 없습니다. 다시 한에 대한 모든 권리,. 

DOUG : 나는 돌아 가야한다 모든 슬라이드를 통해? 나의 하나님. 그것은 여섯 번째 시간, 이안 같다. 괜찮아. 

이안 : 좋아. 당신 준비? 좋아요. 액션.