DAVID 마란 : 좋아요. CS50에 다시 오신 것을 환영합니다. 이 주 (8)의 시작이다. 그리고 그 문제 5 세트가 종료 되 도전의 작은 비트. 그래서 당신은 당신의 모든 복구 가​​정 교육 휄로우 CA의 사진 card.raw 파일에서, 당신은 자격이 지금 그 사람들을 모두 찾아하는 하나의 행운의 당첨자는 하나의 집으로 안내합니다 이러한 것들, 도약 운동 당신이 마지막에 사용할 수있는 장치 예를 들어 프로젝트. 이것은 매년 리드 creepiness의 비트. 그래서 내가 내가 할 거라고 생각하는 것은 공유입니다 당신과 함께있을 노트의 일부 앞뒤로 사라 후반의 직원 목록입니다. 예, 바로 지난 밤, 견적 직원 중 하나에서, 맺다 회원은, "난 그냥 학생 노크를했다 내 문을 나와 함께 사진을 촬영합니다. 스토커가 당신을 말해. "시작했다 우리가 이동 한 후 공정 설명 및 에 한 시간 정도 후, "나는했다 학생이 섹션 뒤에 나를 기다리고 그는 우리의 이름과 사진을 모두 가지고 몇 장의 용지에. "좋아. 그래서 조직,하지만 아직 모든 오싹. 그런 다음, "나는 이번 주말, 외출했다가 내가 돌아 왔을 때, 하나 있었다 나의 침실. "[웃음] DAVID 마란 : 직원 다음 인용 회원 "학생에 집에 와서 4에서 서머 빌이 아침에 오전. "다음 직원은, "나는 산에있는 나의 호텔에 도착 시스코와 학생이 기다리고 있었다 세 DSLR 카메라와 로비 나. " 카메라의 종류. "나는 직원이 이번 학기에도 아니에요 하지만 학생이 내 집에이 파산 모든 것은 아침과 기록 . 구글 유리 "그리고 마지막으로, "적어도 12 명이 열심히했다 내가 밖으로 왔을 때 나를 위해 기다리고 리무진, 그리고 I 일어났다. "좋아. 그래서 사진 가운데로 당신은 할 수있다 기억이 동료는 누가 여기에있다 살고 마일로 바나나로 알고 있습니다 로렌 카르발류, 우리의 머리 연구원 교수. 마일로 마일로, 이리와. 밀로. 밀로. 당신을 마음, 그는 그래서 구글 유리를 입고 우리는 당신이 모든 후 보여 드리죠. 당신이 좋아하면 것인지 그래서 이것은 마일로 이후 그와 함께 사진을 찍고. 당신은 밖으로보고 싶으면 거기에 관객. 확인을 클릭합니다. 그 좋은 영상입니다. 음, 마일로 바나나. 아,하지 않습니다. [웃음] 확인을 클릭합니다. 앞에 무슨 일이 있을지에 다음 단어 때문에, 우리가 변화하기 시작하기 때문에, 이번 주 특히,에 C에서 명령 줄 PHP로 환경과 자바 스크립트와 SQL 및 HTML과 CSS에 웹 기반 환경에서, 우리는 할 수 있습니다 모든 당신을 장착 에 대한 더 많은 지식 잠재적 인 최종 프로젝트. 이를 위해 코스를 가지고 세미나 개최의 전통있는 접선 주제에있다 코스. 매우 프로그래밍과에 관련 앱 개발 등등하지만, 필요에 의해 탐구하지 물론 자신의 강의. 하나에 관심이있을 수 있습니다 그래서 만약 올해의 세미나 이상 cs50.net/seminar에 등록. 이전 세미나가 있습니다 cs50.net/seminars에서. 그리고 올해 지금까지 명단에 루비와 놀라운 웹 애플 리케이션에있다 대안 레일, PHP로 언어입니다. 전산 언어학. 이다 IOS에 소개 그리고 아이폰 사용되는 플랫폼 아이 패드 개발. 자바 스크립트는 웹 애플 리케이션을 위해, 우리는 다룰 것이다 즉, 본 세미나에서, 당신은 갈 것이다 더 자세히. 모션 도약, ​​그래서 우리는 실제로 몇 가지가 있습니다 도약 동작에서 우리의 친구, 회사 자체는 우리를 가입 할 수 있습니다. 내일, 사실, 제공하는 실습 세미나 경우 여러분의 관심. Meteor.js에 대한 대체 기술 하지 않는 브라우저에서 자바 스크립트를 사용하여 하지만 서버. 아주 많이 Node.js, 그 정맥뿐만 아니라. 매끄러운 안드로이드 디자인. 안드로이드는 매우 인기있는 대안이되고 IOS 및 Windows 전화에 다른 모바일 플랫폼. 웹 보안 적극적인 방어. 그래서 사실, 당신이 좋아하면 것인지 이에 종사하는, 나를 보자 이주의합니다. 우리는 그 말을 아주 행복 도약에서 우리의 친구 시작이 모션 - 이 장치는 정말 그냥 왔어요 몇 달 전 중 1 - 우아 30 같은 장치를 기부했다 많은 학생들과의 수업, 경우에 당신은 하드웨어를 빌려 싶습니다 학기의 끝 부분에 대해 사용 실제 최종 프로젝트. 그들은 여러 언어를 지원합니다. 그들 중 아무도 그렇게 C, 그들 중 누구도 PHP, 실현이 세미나 중 하나 이상 관심 증명할 수 있습니다. 그리고 그들 모두는에서 촬영 될 것입니다 당신이 수 없습니다하는 경우 사람에 참석한다. 일정을 통해 발표 우리가 방을 응고로 이메일을 보내십시오. 그리고 마지막으로, 당신은에 가면 projects.cs.50.net,이 웹 사이트입니다 우리는 우리가 초대 매년 것이라고 주장 사회, 교직원의 여러분 부서, 직원, 두 CS50에의 외부에있는 프로젝트 아이디어를 제안한다. 학생 그룹에 관심 있어요. 부서의 관심 있어요. 당신이 어려움을 겪고 있다면 그래서이 켜 않습니다 무엇에 대한 불확실성과 스스로 해결하고 싶습니다. 그래서 지난 번에 우리는 틀림없이 소개 더 복잡한 데이터 구조를 우리는 것보다 지난 주에 본. 우리는 꽤 배열을 사용하고 것 만약 행복으로 유용한 단순한 데이터 구조. 그럼 우리는이를 소개하는 물론 목록을 연결되어 있습니다. 과에 대한 동기 중 하나 것이었다 이 데이터 구조를 도입? 그래? 그게 뭐야? 대상 : 동적 크기입니다. DAVID 마란 : 동적 크기입니다. 배열에있는 반면에, 그래서 당신은한다 사전에 그 크기 때를 알아야 당신은 그것을 할당합니다. 연결 목록에서, 당신은하지 않습니다 것을 알고있다. 당신이 더 일반적으로 그냥 malloc에​​, 또는 수 추가를 할당 노드 말하자면, 언제나 당신 더 많은 데이터를 삽입 할. 그리고 노드는 아무런 의미를 미리 없다. 그냥 설명하는 일반적인 용어입니다 우리가 걸 컨테이너의 일종 저장하기 위해 데이터 구조에 사용 이에 대한 관심의 일부 항목하는 경우 정수가 될 일. 그러나 단점은 항상있다. 그래서 우리는 데이터를 동적으로 크기를 얻을 구조, 그러나 우리가 어떤 가격을 지불합니까? 연결리스트의 단점은 무엇입니까? 그래? 관객은 : 더 많은 메모리가 필요합니다. DAVID 마란 : 그것은 더 필요 메모리, 정확히 어떻게? 대상 : [들림]. DAVID 마란 : 그렇습니다. 그래서 지금 우리는 포인터를 차지했다 메모리를 추가 우리가 이전에 해당 필요하지 않았다 때문에 장점 배열 물론, 그 모든 연속 된 뒤의 뒷면에 백업하려면 어떤 당신에게 무작위 액세스를 제공합니다. 때문에 단지 대괄호를 사용하여 표기법, 또는 좀 더 기술적으로 포인터 산술, 매우 간단뿐만 아니라, 당신은에 액세스 할 수 있습니다 일정 시간의 요소. 그리고 사실, 그 암시하는 일종의 우리와 함께 지불하는 또 다른 가격 연결리스트. 무엇의 실행 시간에 발생 검색과 같은, 내가하고 싶은 경우 어떤 가치와 내부를 찾을 수 연결리스트의? 내 실행 시간은 어떻게되고 있습니까? N의 큰 O. 그것은으로 분류 있다면 요? 어떤 데이터 구조가 정렬 있다면 요? 나는 큰 것보다 더 잘할 수 검색을위한 N의 O? 아니, 있기 때문에 최악의 경우는 수도 잘 정렬 만 할 수 당신은 큰 수 있습니다 찾고 있습니다. 그것은 어떤 숫자 100이 될 수도 모든 할 일이 있습니다 끝에 방법입니다. 당신은 단지 링크에 액세스 할 수 있으므로 하여이 구현 목록 첫 번째 노드의 방법, 당신은거야 운이 여전히 종류. 당신은 모든 일을 통과해야합니다 먼저 찾기 위해 지속하는 100처럼 그렇게 큰 값입니다. 그건 경우 또는 결정 거기 있지도. 그래서 우리는 데이터에 어떤 알고리즘을 수행 할 수 없습니다 구조를 다음과 같이 보인다? 우리는 이진 검색을 할 수 있기 때문에 이진 검색은 우리가 가진 것을 필요 무작위 액세스 할 수 있습니다. 우리는 단지 위치로 도약 할 수 따라하지 않고 위치 양식이 빵 부스러기 이러한 모든 포인터. 이제 우리는 어떻게이를 구현 했습니까? 글쎄, 우리가 여기 화면으로 이동 한 경우에, 우리는 신속하게이 데이터를 다시 구현할 수 있습니다 구조 - 내 글씨는 모두 아닙니다 여기에 좋은,하지만 우리가하려고합니다. 그래서 typedef는 구조체, 그리고 무엇을했다 I 이 일을 여기 호출 할? 노드입니다. 그래서 우리가 시작 얻을 것이다. 그리고 지금, 무엇의 내부에 있어야합니다 그 단독의 데이터 구조 연결리스트? 얼마나 많은 필드? 두 그럼. 하나는 매우 쉽습니다. N 그렇게 INT. 그리고 우리는 우리가 원하는 N 아무것도 호출 할 수 있습니다 우리가 있다면하지만 INT해야한다 정수에 대한 연결리스트를 구현. 지금 무슨 일이 두 번째 작업을 수행 필드 수 있나요? 구조체 노드는 *. 나는 구조체 노드 * 그리고 난 그렇게 생각하지 경우 또한 내가 원하는대로이 호출 할 수 있습니다, 하지만 그냥 내가 전화 할게 명확하게 그 다음, 우리가 해왔으로. 그리고 나는 중괄호를 닫 있습니다. 그리고 지금, 마지막으로, 여기 노드를 내려 놔. 하지만이 선언 거라면 같이이다 노드는, 왜 그렇게되는 귀찮게 않았다 여기에 구조체 선언의 자세한 노드 * 다음과 같은 반대 다음 단지 노드 *에? 그래? 대상 : [들림]. DAVID 마란 : 그렇습니다. 정확히. C는 정말 당신을 그대로 소요하기 때문에 전용 노드의 정의를 본다 여기까지하면, 당신은 할 수 없습니다 여기까지 참조하십시오. 그래서 우리는 선제이 종류가 틀림없이 여기에 선언 더 자세한. 구조체 노드는 것을 의미 우리는 지금 액세스 할 수 있습니다 데이터 구조의 내부. 그리고 옆으로,이 때문에 이제 좀 더 주관적인되고 별이 기술적으로 여기에 갈 수 있습니다, 그것은 여기 갈 수는 있습니다 심지어 중간에 이동합니다. 우리는 당신을위한 스타일 가이드를 채용 한 물론, 퍼팅 대회 데이터 바로 옆에 스타 유형,이 경우 어느 구조체 노드가 될 것입니다. 그러나 교과​​서를 많이 실현 온라인 참조, 당신은 참으로 수도 다른 쪽을 참조하십시오. 하지만 단지 그 사실 것 모두 실현 일을하고 당신은 단순히해야한다 일관성. 좋아. 따라서 우리의 선언이었습니다 구조체 노드의. 하지만 우리는 더 많은 일을하기 시작 정교한 확인해보세요. 예를 들어, 우리는 도입하기로 결정 해시 테이블 같은. 그래서 여기에 크기가 n의 해시 테이블입니다 n으로 왼쪽 상단에 0부터 인덱스 마이너스 바닥에 1 떠났다. 이 해시 될 수 아무것도 테이블. 그러나 우리는 일의 종류를 이야기 했는가 의 해시 테이블을 사용하는 방법에 대한? 무엇을 저장? 이름. 우리는 같은 이름을 할 수 우리는 지난 시간에했다. 정말, 당신은 아무것도를 저장할 수 있습니다. 그리고 우리는 다시이 표시됩니다 PHP와 자바 스크립트합니다. 해시 테이블은 스위스의 좋은 일종이다 당신이 저장할 수있는 군용 칼 거의 당신이 내부에 원하는대로 값으로 키를 연결하여 그것. 값이 키를 사용합니다. 이제이 간단한 경우에, 우리의 키는 단지 숫자입니다. 우리는 해시를 구현하고 배열 표. 그리고 키 0이고, 1, 2, 등등. 그래서 우리는, 인간으로, 마지막 결정 당신은 우리가 있다면 무엇을 알고 주하는 저장소 이름에 가고,하자 그냥 임의로하지만, 꽤 합리적으로, 한다고 가정 앨리스, 이름, 그냥 0으로 인덱스됩니다. 와 밥, B 이름은 색인화 할 1에, 등등. 그래서 우리는, 입력 간의 매핑을했다 이는 문자열이며, 해시 숫자 위치. 그래서 그 과정은 일반적으로 알려져 있습니다 해쉬 함수, 당신은 진정 수 그 코드를 구현합니다. 내가 해시 함수를 구현하려는 경우 그것은 정확히 우리가한다 바로 지난 시간부터 설명, 나는 수도 로받는 함수를 선언 예를 들어 입력 - 및하자이에이 작업을 수행 여기에 화면을 표시합니다. 내가 해시를 구현하려는 경우 기능은 내가 말할 수 있습니다 이런 식으로 뭔가. 그것은 int를 반환하는거야. 그것은 해시 호출 할 것, 그리고의 인수로 받아 들일 것 문자열, 또는 우리는 이제 더 적절한 수 있습니다 와 char *로 말을, 우리는 그것의 전화 할께. 그리고이 모든 기능은 할 수있다 궁극적으로, int를 반환합니다. 지금, 그것은 어떻게합니까 그 수도 그렇게 분명하지. 어떤없이 구현하는거야 지금은 오류 검사의 형태. 그냥 맹목적으로 말할거야 반환 의 브라켓 0에서 무엇을 뺀, 하자 자본 세미콜론을 말한다. 완전히 깨진. 그것은 완벽 하진 때문에 하나의 null이 무슨 경우? 나쁜 일이 일어날 것입니다. 두, 어떤 경우에는 이것의 첫 번째 문자 이름은 대문자 아닌가요? 설정하지 않을 걸 밖으로 잘 하나. 그것은 소문자 수 있습니다 또는 전혀 문자. 여기에 개선 그래서 완전히 방 그러나 이것은 기본적인 생각이다. 우리는 구두로 지난 주에 설명한 것을 앨리스 매핑 단지 과정 1-0와 밥이 표현 될 수있다 확실히 더 많은 공식을 통해 (formulaically) C로 여기에 작동합니다. 다시 해시 호출로 문자열을 입력 한 다음 어떻게 든 무언가를 출력을 생성하기 위해 해당 입력으로. 아닌 우리의 블랙 박스 설명과는 달리 우리는 오랫동안 수행했는지. 나는이있을 수 있습니다 방법을 몰라 후드 아래 작업. 문제 세트 6 문제 중 하나 당신이 결정하는 무엇 귀하의 해시 함수가 될 것인가? 그 블랙의 안쪽에 할 무슨 상자, ​​그리고 아마도, 그것은있을거야 좀 더 이것보다 흥미와 오류 확실히 더 많은 경향이 이 특별한 이상 검사 구현. 그러나 문제는 바로 발생할 수 있습니다? 우리는 이와 같은 데이터 구조가있는 경우 하나 문제 중 하나가 무엇입니까 당신은 삽입 할 경우 시간이 지남에 실행할 수 있습니다 에 더 많은 이름 해시 테이블? 당신이 바로 충돌을 얻는가? 당신은 무엇을 앨리스와 아론을 가지고있는 경우 이름이 일어난 이명 로 시작하는? 그건 어디 당신은 질문을 구걸 두 번째 같은 이름을 넣어? 글쎄, 당신은 순진 그냥 둘 수 밥이 속한 곳,하지만 밥은 당신이하려고하면 종류의 나사 다음에 자신​​의 이름을 삽입하고 그의 여지가 없습니다. 그래서 당신은 찰리가 밥을 넣어 수 있습니다 그리고 당신이 매우 빠르게 상상할 수 혼란의 비트에 이양. 결국 선형 일 경우 단지 전체를 검색해야 앨리스 나 밥을 찾고 나 아론이나 찰리. 그래서 그 대신 우리는 대신에, 제안 선형 열린 공간 프로빙 그리고 우리는 거기에 이름을 쿵쾅 거리고 애호가 방법을 제안 하였다. 아직도 구현 된 해시 테이블 인덱스 배열,하지만 데이터 유형 이러한 지표는 이제 포인터되었습니다. 어떤 포인터? 연결리스트에 대한 포인터. 때문에 연결리스트는 그 리콜 정말 그냥 노드에 대한 포인터, 그리고 노드는 다음 필드 및 해당 노드가 다음 필드를 가지고, 등등. 그래서 지금에이 배열을 생각할 수 해시 테이블로의 왼쪽 연결리스트로 이어지는. 당신이 얻을 경우의 장점은 앨리스와 아론 사이의 충돌, 당신은 무엇을해야합니까 두 번째 같은 사람? 당신은 그를 연결하거나 그녀 끝 또는 시작 그 연결리스트의. 실제로 통해 단지 국수하자 그 잠깐합니다. 여기서 가장 적합한을 만들 것? 나는 앨리스를 삽입하고 그녀가 바라 끝나는 경우 첫 번째 위치는, 나는 시도 아론의 이름을 삽입하고있다 분명 충돌이 나는 넣어야한다 그 시작 부분에 연결리스트의? 즉, 첫 위치에서의 또는 끝? 대상 : [들림]. DAVID 마란 : OK. 나는 처음 들었다. 왜 처음에? 대상 : [들림]. DAVID 마란 : OK. 그것은 알파벳의, 좋은 데요 있도록. 그 좋은 재산입니다. 그것은 나에게 잠재적으로 시간을 절약 할 수 있습니다. 그것은 나를 이진 검색을 수행하자,하지만하지 않습니다 I 적어도 탈출 할 수있을 것 내가 알게되면 루프, 음, 내가 길이야 지난이었다 아론이 될 것입니다 연결된 목록을 정렬. 내가 찾고 내 시간을 낭비 할 필요가 없습니다 끝까지. 그래서 합리적이다. 왜 다른 당신은 삽입 할 수 있습니다 에서 충돌하는 이름 목록의 시작? 그게 뭐야? 대상 : [들림]. DAVID 마란 : 그것은 시간이 오래 걸릴 수 있습니다 목록의 끝에 얻을 수 있습니다. 그리고 사실, 더 길고 더. 당신이 삽입 이상의 이름이 , 더 이상 그와 함께 시작 체인을 얻을 것입니다. 더 이상 연결하는 리스트 얻을 것입니다. 그래서 당신은 정말 그냥있어 당신의 시간을 낭비. 어쩌면 당신은 유지하는 게 좋겠어 상수 삽입 시간, 1 큰 O, 항상 충돌하는 이름으로 바꾸어 연결리스트의 시작, 그리고 많이 걱정하지 정렬에 대해. 가장 좋은 대답은 무엇입니까? 그것은 명확하지 않다. 그것은 종류에 따라 다릅니다 어떤 분포 패턴이 무엇이며, 이름을 당신이 삽입됩니다. 그것은 반드시이 아니다 확실한 대답. 그러나 여기에 또있다 디자인 기회를 제공합니다. 그래서 우리는이 일에보고하는 정말 다른 큰 기회입니다 P 세트 6. 그리고 당신이 이미하지 않은 경우, 실현 해시 이들 모두에 Zamyla 다이빙, 테이블과 더 자세히 시도. 그리고 비디오 연습은 P 세트 사양에 포함. 이 트라이이었다 - T-R-I-E. 과에 대한 흥미 것이었다 이것은 실행 시간이었다 맥스웰 같은 이름을 검색 중 마지막으로, 무슨 큰 O인가? 그게 뭐야? 대상 : 문자의 수입니다. DAVID 마란 : 문자의 수. 나는 두 가지를 들었다. 문자와 일정 시간의 수. 그럼 그 첫 번째로 가자. 문자의 수입니다. 음,이 데이터 구조, 리콜이며, 나무, 가족 나무의 각을 좋아 그 노드는 배열로 구성되어 있습니다. 그리고 그 배열에 대한 포인터 같은 다른 노드 또는 다른 트리에서 배열. 우리는 확인하고 싶었 그래서 경우 맥스웰이 여기에 있는지, 내가 갈 수도 있습니다 의 맨 위에있는 첫 번째 배열에 나무, 소위 루트의 상단 다음 트라이, 및 M 포인터를 따라 그 다음, 포인터, X, W, E, L, L. 그리고 나서, 일부 특수 기호를 볼 때 삼각형 여기에 표시된. 코드에서 당신은 우리가 제안 볼 거 야 당신 그냥 예라고, BOOL로 구현 또는 아니, 단어는 여기에서 멈 춥니 다. 음, 일단 우리가 M--X-W-E-L-L에 갔어요, 아마 일곱 느낌 여덟 우리는 지난 1, 여덟 가면 맥스웰를 찾는 단계. 나의이 K. 부르게하지만, 마지막을 기억 시간은, 내가 만약 거기에 있다고 주장 에 현실적으로 최대 길이 단어, 40 일부 - 이상한 문자처럼, 최대 길이는 의미 상수 값. 그래서 정말, 그래, 그것은 기술적으로 큰 O의 하지만, 8, 7, 또는 K. 정말 큰 O의 무엇에 유한 캡이 있다면 K가 될 수는 상수이다. 그리고 그것은 1 큰 O는시의 하루의 끝. 아니 현실 세계합니다. 당신은 실제로 시청을 시작하지 않는 경우 프로그램의 실행으로 당신의 시계. 그것은 절대적으로 조금 될 것 정말 일정보다 느리게 한 단계와 시간입니다. 그것은 7 ~ 8 단계가 될 것 하지만 여전히 훨씬, 훨씬 더의 그 N의 큰 O와 같은 알고리즘보다 에 무엇이의 크기에 따라 달라집니다 데이터 구조. 여기에 거꾸로 우리가 삽입 할 수 있습니다 알 이에 백만 이상의 이름 데이터 구조,하지만 어떻게 더 많은 단계 그것을 찾기 위해 우리를 걸릴 것입니다 이 경우 맥스웰? 없음. 그가 영향을받지 있습니다. 그리고 지금까지, 우리가 본 적이 생각하지 않는다 데이터 구조 또는의 예 완전히이었다 알고리즘 외부의 영향을받지 그런 행동. 하지만이 놀라운 할 수 없습니다. 이 유일한 해결책이 될 수 없습니다 P-세트에 대한 그리고 그것은 아니에요. 이 데이터를 필요는 없습니다 구조는 당신이 몰리는한다 때문에 해시 테이블 같은 단점. 여기에 지불하는 가격은 무엇입니까? 메모리. 내 말은,이 끔찍 메모리의 양입니다. 그리고 당신은 확실히 여기에서 볼 수 없기 때문에 이 그림의 저자 물론, 배열을 모두 절단 우리는의를 많이 시청하지 않는 B의와 C의와 Q의와 Y의 와 Z의 이러한 배열합니다. 하지만 그들은있어. 이러한 노드 각각은 전체 배열 일부 26 바이트 이상, 각각의 이는 문자를 나타냅니다. 우리가 지원할 수 있도록 우리의 경우 27 일 문제 세트 아포스트로피. 이 데이터 구조는 정말 그래서, 정말 밀도와 넓은. 그리고 혼자 둔화 끝날 수도 물건은 아래로, 또는 적어도 당신을 비용 더 많은 공간. 그러나 다시, 우리는 그릴 수 있습니다 여기에 비교. 다시 잠시 기억, 우리는 많은 것을 달성 정렬에 더 많은 흥미로운 상영 시간 우리는 정렬 병합,하지만 가격을 사용하는 경우 우리는 병합 n을 달성 N 로그온 할 때 지불 종류는 우리가 지출해야 무엇보다 자원? 더 많은 공간. 우리는에 보조 배열을 필요로 처럼 사람들을 복사 우리는 무대에서 여기 않았다. 그래서 다시, 명확한 승자, 하지만 단지 주관적 디자인 결정을 할 수 있습니다. 좋아. 어떻게 이것에 대해? 누구나하는 D-홀을 인식? 확인을 클릭합니다. 그래서 우리 셋 않습니다. 메이 하우스. 그래서 이것은 메이의 식사입니다. 나는 모든 식당 홀 가지고있을거야 이와 같은 트레이의 스택. 그리고 실제로 대표 우리가했습니다 뭔가 분명히 이미 본. 우리는 문자 그대로 스택을했다. 귀하의 측면에서 그리고 스택, 데이터가 어디로가는 컴퓨터의 메모리이며, 함수가 호출되는 동안. 예를 들어, 사물의 어떤 종류의 이동 에 대하여 스택에 우리가 토론 한 메모리 레이아웃 지난 주에? 그게 뭐야? 대상 : 함수 호출. DAVID 마란 : 미안 해요. 대상 : 함수 호출. DAVID 마란 : 함수를 호출하지만, 특히, 각각의 안쪽은 무엇입니까 그 프레임? 사물의 어떤 종류의? 그래. 지역 변수 때문에. 언제든지 우리는 몇 가지 로컬 스토리지가 필요 인수와 같은, 또는 INT I, 또는 INT 온도, 또는 어떤 지역 변수는, 우리는 있었어요된다 스택에 그 퍼팅. 그리고 우리는 그것을 호출 스택 때문에 그 레이어 아이디어. 현실과 일치, 그냥 업 그 개념. 그러나 그것은 밝혀 스택도 할 수있는 데이터 구조로 볼 수, 배열에 대안 대안 링크 된 목록에 추가합니다. 개념적으로 더 흥미로운 여전히 수 그 중 하나를 사용하여 구현 것들,하지만 다른 종류의의 데이터 구조는 정말 지원 두 작업. 하지만 당신은 애호가에 추가 할 수 있습니다 이보다 기능을 제공합니다. 그러나 이러한 기본이다 - 누르고 팝업. 그리고 스택 아이디어는 그 경우 I 이나 애넌 버그없이 여기있다 바로 옆에서 트레이를 알고 거기에 번호 9. 그래서 그냥 INT. 그리고 데이터에이를 밀어하려면 현재 비어있는 구조. 이에게 스택의 하단을 고려하십시오. 나는에이 숫자 9를 밀어 것 스택, 지금 바로있다. 그러나 스택에 대한 흥미로운 것은 지금 밀어 원하는 경우에, 그것은이다 다른 값처럼 17, 나는 밀어 스택에이, 내가 할거야 난 그냥려고 만 직관적 인 것 바로 그것을 넣어 어디 인간 상단에 넣어하는 경향이 될 것이다. 그러나 지금은 흥미 , 내가 어떻게 9시 어떻게해야합니까 무엇입니까? 당신이 알고, 내가 어떤 노력없이하지 않습니다. 그래서에 대한 흥미 스택, 그 디자인입니다 그것은 LIFO 데이터 구조입니다. 기술의 어리석은 방법 마지막, 첫 번째가 부족합니다. 그래서 마지막 숫자 이 시간에 17이었다. 내가 뭔가를 나타 싶은 경우 스택, 그것은 단지 17가 될 수 있습니다. 정도의 필수 순서가있다 여기에 작업 위치를 마지막 항목 에서가 처음으로 나온 수있다. 따라서 약어, LIFO. 그럼 왜이 유용 할 수 있습니다? 자신의 상황입니다 당신은 거라고하는 이 같은 데이터 구조를 원하는? 음, 확실히 도움이되었습니다 컴퓨터의 내부. 따라서 운영 체제는 명확하게이 기능을 사용 스택 데이터 구조의 일종. 우리는 또한 같은 생각을 볼 수 있습니다 웹 페이지에 관해서. 이번 주 다음 주에 따라서 그리고 저쪽에, 그리고 당신은 웹을 구현하기 시작할 때 언어 페이지는 HTML, 당신이 할 수있는 전화 실제로 같은 데이터 구조를 사용하여 이 결정하면 페이지 올바르게 포맷됩니다. 우리가 볼 수 있기 때문에 모든 웹 페이지는 다음과 계층 구조의 정렬, 들여 쓰기 , 하루의 끝에, 될 것 후드 아래 트리 구조. 단지 약간의 해당에 이렇게 더. 하지만 지금의이에 대한 제안하자 순간, 우리는에 대해 어떻게 갈 수 스택이 무엇입니까? 대표 우리가 구현하는 나 제안하자 다음과 같은 코드로 스택입니다. 그래서 스택은 내부에해야 할 것입니다 두 가지, 배열, 전화 트레이, 단지 데모와 일치해야합니다. 그리고 그 배열의 각 항목 int 형이 될 것입니다. 그리고 용량은 아마도 무엇인가? 내가 작성하지했기 때문에 여기에 전체 정의. 아마 최대의 배열의 크기입니다. 그리고 그것은 아마 샤프로 선언 된 일부 파일의 맨 위에 정의 상수의 종류는 암시 단순한 대문자. 그래서 어딘가에 용량이 정의되어 가능한 최대 크기. 한편, 내부 데이터 구조의 스택으로 알려진이됩니다 단지 알려진 정수 단순히 크​​기. 지금이 나타내는 있었다면 그림으로,의를 가정하자 그이 전체 블랙 박스 내 스택을 나타냅니다. 그것의 내부는 두 변수이다. 그래서 난을 그릴거야 크기 첫 번째. 그리고 난거야 두 번째 배열로 그립니다. 그러나 다만 상황이 질서 유지 일반적으로 내가 좋아하는 배열을 그릴 것 좋은이 있지만, 그것의 종류 우리는 현실을 일치하는 경우, 또는 정신 모델을 일치합니다. 그럼 내가 대신 배열을 그려 보자 수직, 이는 그냥 또 다시, 작가의 연주. 정말 무엇이 중요하지 않습니다 후드 아래에있다. 그리고 우리는 기본적으로 그렇게 말할 것 용량은 세 가지가 될 것입니다. 그래서이 위치를 0이 될 것입니다 위치 1이 될 것입니다 위치 2가됩니다. 나는 스트레스 공을 매수하는 경우 것 누군가가 와서 실행하려면 잠시 여기를 탑승? OK, 먼저 손을 보았다. 올라 와요. 좋아. 그래서 나는 스티븐 믿습니다. 올라 와요. 좋아. 하지만 지금 우리는 초기에 감아한다고 가정 세계의 상태를 어디에 그냥 스택을 선언하고의이 용량이 세 가지가 될 것. 그러나 크기는 아직 결정되지 않았습니다. 트레이는 아직 결정되지 않았습니다. 먼저 몇 가지 질문 때문에. 그리고 내가 당신에게 마이크를 줄 수 있도록 당신이 할 수 있도록 이 더 적극적으로 참여. 그래서 크기의 내부는이 순간 무엇인가 시간에 내가했던 모든 경우 와 스택을 선언 한 줄의 코드? STEVEN : 많이하지 않습니다. DAVID 마란 : OK,별로. 우리는 크기 안에 무엇이 알고 우리는 안에 무엇이 알고 여기에이 배​​열의? STEVEN : 그냥 임의의 코드를, 오른쪽? 그냥 - DAVID 마란은 : 네, 갈거야 그 코드를 호출하지만 임의 - STEVEN : 확인해보세요. DAVID 마란 : 무작위 같은 것들 STEVEN : 비트. DAVID 마란 : 비트, 오른쪽? 쓰레기 값이 그래서, 오른쪽? 따라서 0과 1의 순열. 이전 용도의 잔존물 이 메모리의. 그리고 우리는 정말 모르겠어요 무슨 값 그래서 우리는 일반적으로 그들을 잡아되어 물음표. 우리는 아마도거야 그래서 우선 여기에서 할 것 - 나 내부에이 필드를주게 트레이 -이 이름의. 우리는 아마도 무엇을 초기화한다 크기가 우리가 원하는 경우에 이 스택을 사용하기 시작? STEVEN : 트레이 하위 3입니다. DAVID 마란 : 그래서, 확인을 클릭합니다. 명확하게, 용량은 선언 다른 세 개. 그리고 그게 내가 사용한 적이 무엇을 배열을 할당합니다. 크기는 참조하는 것입니다 얼마나 많은 트레이 스택에 현재. STEVEN : 제로. DAVID 마란 : 그래서 0이되어야합니다. 그래서 가서, 어떤 손가락, 크기 0을 그립니다. 좋아. 그래서 지금이 내부 무엇 여기, 우리는 모르겠어요. 이들은 정말 그냥 쓰레기 값입니다. 그래서 우리는 물음표를 그릴 수도 있지만 지금 보드를 청결하게 유지하자 그것은 중요하지 않기 때문에 이거야. 우리는 배열을 초기화 할 필요가 없습니다 아무것도 우리가 알고있는 경우 때문에 스택의 크기가 0이고, 잘, 우리 에서 아무것도보고하지 않아야 어쨌든에서이 배열 이 시점 시간이있다. 그래서 지금 밀어한다고 가정 스택에 번호 9. 우리가 어떻게 데이터 구조를 업데이트해야합니다 이 블랙 박스 내부에? 어떤 값을 변경해야합니까? STEVEN : 내 - 사이즈는? DAVID 마란 : OK. 크기는 얼마가되어야? STEVEN : 크기는 하나가 될 것입니다. DAVID 마란 : OK. 그래서 크기는 하나가된다. 그래서 당신은 몇 가지 방법으로이 작업을 수행 할 수 있습니다. 이제, 내가 당신을 줄 수 있도록하여 손가락 지우개입니다. 좋아. 그런 다음 이제 손가락 브러쉬입니다. 좋아. 그리고 이제 또 무엇을 변경해야 분명히, 데이터 구조? STEVEN : 우리는에서거야 9 아래에서 위로. DAVID 마란 : 9. OK, 좋아. 그래서 여전히에서 무엇을 중요하지 않습니다 위치 하나 또는 두 개의 그들이이기 때문에 쓰레기 값은, 그러나 우리는 걱정하지한다 사이즈이므로이보고 우리에게 말하고 만 첫 번째 요소 실제로 합법적이다. 그래서 지금은 목록에 17을 누릅니다. 어떤이 사진은 어떻게됩니까? STEVEN : 그래서 크기는 두 가지로 갈 것입니다. DAVID 마란 : OK. 당신은 지우개입니다 - 죄송합니다. 당신은 지우개입니다. STEVEN : 지우개. DAVID 마란 : 당신은 브러쉬입니다. STEVEN : 브러쉬. DAVID 마란 : OK. 그리고 또 뭐가? 다음 그리고 우리 - : STEVEN DAVID 마란 : 우리는 17 밀었다. STEVEN : 우리는, 그래서 정상에 17 스틱 - DAVID 마란 : OK, 좋아. STEVEN : - 내려 놓습니다. DAVID 마란 : 좋아요. 그것은 간단지고있어. 나는 당신에게이 시간을 도움이 될 것 아니에요. 22을 누릅니다. STEVEN : 완료. 지우개되고. 나는 브러쉬가되고 있어요. 그리고 나서 22을 가하고 있습니다. DAVID 마란 : 22. 우수. 그래서 한 번 더. 지금 밀어거야 스택에 26 위에. STEVEN : 오. 세상에 오. 당신은 정말 방심 저를 붙 잡았다. DAVID 마란 : 당신은하지 않았다 이 예견? STEVEN :이오고 보지 않았다. 우리는 다시 초기 용량 있을까요? DAVID 마란 : 그건 좋은 질문이다. 그래서 우리는 종류의 자신을 그린 것 여기에 모서리합니다. 정말 스티븐 좋은 밖으로 없다 우리는이 배열을 할당했기 때문에 정적, 그래서 내부 이야기하기 데이터 구조. 그리고 우리는 본질적으로 하드 코딩했습니다 그것의 크기는 세 가지가 될 수 있습니다. 그래서 우리는 정말 재 할당 할 수 없습니다. 우리는 우리가 다시 가서 수 있다면 트레이가 해당 포인터로 재정의 우리는 다음에 손 메모리에 malloc을 사용합니다. 때문에 우리는에서 메모리를 얻은 경우 malloc을 통해 힙, 우리 다음을 해제 할 수 있습니다. 그러나 그것을 해제하기 전에, 우리는 수 메모리의 큰 덩어리를 재 할당 포인터를 업데이트하고, 등등. 하지만 지금이 정말 가장 우리가 할 수 있습니다. 푸시와 팝 아마 가고있다 약간의 오차 신호를받습니다. 그래서 예를 들면, 우리가 구현 푸시는 BOOL을 반환 할 수 있습니다 어느 이전 사실, 사실, 사실 반환됩니다. 그러나 네 번째, 그것은이 것 예를 들어, false를 반환합니다. 좋아. 아주 잘 했어. 축하합니다. 당신은 오늘 스트레스 공을 얻었습니다. [박수] STEVEN : 감사합니다. DAVID 마란 : 감사합니다. 좋아, 그럼이 많이없는 것 같다 앞으로 단계, 오른쪽? 우리는이 데이터 구조를 설명했다. 그것은 바로, 강제적이었다? 운영 체제는 그것을 좋아한다. 분명히 웹이 사용 할 수 있습니다 아직 다른 응용 프로그램. 그러나 우리가 걸 바보 제한 정렬 일주일에 두 제한을 맞댄 여기서 우리는 크기의 배열을 해결했습니다. 그래서 몇 가지가 실제로있다 방법 우리는이 문제를 해결 할 수 있습니다. 우리는 동적 배열을 할당 할 수 내가했듯이으로 어려운 코딩하지 여기에 수행하지만, 대신에 다시 선언 이것은 단지로, 명확하게 이런 식으로 뭔가. INT * 트레이는 결정되지 아직 용량에 대한. 하지만 다른 스택을 선언 할 때 내 코드에서, 나는 다음 malloc을 호출 할 수 있습니다 덩어리의 주소를 얻기 메모리 및 I는 할당 할 수 트레이에 해당 주소를 입력합니다. 그리고 때문에 그냥 덩어리의 메모리, I 사각형 계속 사용할 수 있습니다 일반적인 방법으로 대괄호 표기법. 다시 말하지만, 이것은 일종의 거기 때문에 기능 배열과 동일하지만 올 메모리의 덩어리 다시 malloc에​​에서. 우리는 다른 사람과 같은 사람을 치료할 수 포인터 연산을 사용하거나 대괄호 표기법. 그래서 한 가지 방법이다. 하지만 어떻게 다른 우리는 이것을 구현할 수 있습니다 같은 데이터 구조에 잠재적으로? 오른쪽? 우리가이 문제를 해결할 것 같은 느낌 일주일 전에 같은 문제. 이 문제에 대한 해결책은 무엇인가 스티븐로 실행 한? 따라서 연결리스트, 맞아. 문제는 우리가 그림을 걸 경우 할당에 의해 코너에 자신 사전에 너무 적은 메모리가 우리 어떻게 든, 잘 처리해야 왜 그냥을 피할 수 모두 실행? 왜 그냥 트레이로 선언하지 노드, 인체 공학적 연결리스트에 대한 포인터 그리고 단순히 새로운 노드를 할당 스티븐 맞게 필요한 때마다 데이터 구조에 번호입니다. 그래서 사진을 변경해야합니다. 그것은 깨끗하고 아닐 거예요 세 정수의 단지 배열로 간단하다. 지금은에 대한 포인터가 될 것 구조체, 그 구조체가는 INT와 다음 포인터가 있습니다. 그것은 그 포인터를 통해 이어질 것 같은 또 다른 구조체에 같은 또 다른 구조체. 그래서 사진은 실제로 것 조금 지저분를 얻을. 그리고 우리는 화살표를 매기을 것이다 모든 것을 함께. 하지만 그 때문에, 오른쪽, 괜찮아요 우리는이 작업을 수행하는 방법을 살펴 보았다. 그리고 일단 당신이 편안하게 링크처럼 구현하는 것이 당신이해야 할 것이다 목록, 만약 당신 와 해시 테이블을 구현하도록 선택할 P 세트 6에 대해 별도의 체인을 수행 할 수 있습니다 빌딩 블록, 또는로 사용 성분, 또는 스크래치, 말 절차, 당신은, 당신을 넣어 뭔가 자신의 퍼즐 조각을 만들어 그런 다음 다시 사용할 수있는. 그래서 트레이드 오프,하지만 잠재적 인 솔루션 우리는 실제로 전에 본 적이. 그래서 매우 자주, 당신은이에게 매를 참조하십시오 이년 때 애플 출시 새로운, 모든 미친 사람인가 애플의 외부 회선에 최대 자신의 한계를 구입할 저장 하드웨어 업그레이드합니다. 나는이 말을, 그 이유는, OK의 나는 그 사람 중 하나입니다. 그래서 어떤 종류의 데이터 구조 이 현실을 나타낼 수 있습니다? 음,이 큐, 회선 통화 할 수 있습니다. 그래서 영국은 일반적으로 부를 것이다 큐 어쨌든, 그래서 좋은 이름이다. 그리고 큐 두 가지 작업 우리가 대기열에 전화 할게 지원해야한다 작업 및 대기열에서 제외 작동, 이는이 비슷 밀어 팝업하는 정신. 그것은 다른 단지 일종의 협약 우리가 이것들을 호출하고 있습니다. 하지만 뭔가를 큐에 저장하는 추가의 의미 또는 데이터 구조에 삽입합니다. 대기열에서 제외하는 것은 그것을 제거하는 것을 의미합니다. 그러나 스택은 LIFO 데이터이었다 반면 구조는, 큐가 먼저입니다 데이터 구조 중 첫번째로 올려주세요. 당신은 선에있는 첫번째 사람이 있다면 당신이 얻을 수있는 첫 번째 사람이 될 것입니다 라인 밖으로 새 장치를 구입할 수 있습니다. 이 사람들이 얼마나 화가 될 것 상상 애플은 대신 스택을 사용하는 경우에 대한 예, 피킹을 구현하는 새 장난감까지. 그래서 큐를 확실히 이해하고, 우리는 모든 종류의 생각할 수 응용 프로그램, 아마도, 큐, 당신이 공정성을 할 때 특히. 그래서 우리는 어떻게 이러한 구현할 수 있습니다 데이터 구조로? 물론, 그 우리가 수도 제안 이 방법을 수행해야합니다. 그래서 지금은 숫자를 가지고거야. 그래서 우리는 단순하고 있지하겠습니다 반드시 트레이의 관점에서 이야기. 의 사람들이받은 숫자에 불과합니다. 용량이 다시가는, 문제를 해결 될 수있는 사람의 총 수 이 라인 등 세 다른 어떤 값입니다. 하지만 난 트랙을 유지하는 데 필요한 제안 의 크기뿐만 아니라 큐, 그것은 얼마나 많은 것들입니다. 그래서 크기는 현재 크기, 용량은 최대 크기입니다. 그냥 다시 명명법 대회 있습니다. 이유는 추가 INT 내부를해야합니까 에 누구를 추적 할 큐의 라인 셨나요? 왜이 경우 그렇게해야합니까? 음,이 사진 어떻게 변경하려는? 아마 대부분 재사용 할 수 있습니다 이 그림. 내가 가서 여기에 무엇을 지울 수 있습니다. 우리는이에게 약간을 줄 것이다 여기에 다른 이름으로 백업합​​니다. 17의 제거하자,하자 제거 9,의는 3 없애 보자. 과의이 한 가지를 추가 할 수 있습니다. 나는 추적하는 데 필요한 제안 목록의 앞, 이는 단지 뿐만 아니라 INT 될 것. 그리고 우리는 그것을 간단하게 할 겁니다. 지금은 정보 없음 연결리스트가 없습니다. 우리는 우리가가는거야 인정합니다 이 제한에 반대 부딪. 그러나 나는 무엇을 보려고 싶어 이 시간을 어떻게? 내가 가서 처음으로 이렇게 가정 사람 줄에 제공하고, 그 번호 9이다. 우리는 스트레스 공을 가지고 않습니다. 나는 말, 두 개 또는 세 사람이 도용 할 수 있습니까? 하나, 둘, 셋? 올라 와요. 오른쪽 전면에서, 때문에 우리는이 사람이 신속하게됩니다. 당신의 각각은 지금이 될 것입니다 애플 라인 팬 소년. 당신이 애플의 하드웨어를받을 수 없습니다 이 생각의 끝에. 좋아. 당신은 9 번입니다, 그래서 당신이있어 17 번, 22 번. 이처럼, 임의의 숫자 학생 ID 나 이것 저것. 그냥 순간에, 시작하자 물건을 추가 시작합니다. 그리고 여기이 시간에 보드를 실행합니다. 따라서이 경우는 초기화 한 전면 수 - 사실 정말 상관 없어 무슨 크기가 0이기 때문에 앞입니다. 그래서 이것은 단지뿐만 아니라 수도 물음표합니다. 이들은 모두 물음표입니다. 그래서 지금 우리가 실제로 보려면 시작합니다 사람들은 가게에 서서. 그래서 9 번하면, 당신은 처음이야 이 AM 5시에, 가서 줄 또는 전날 밤. 확인을 클릭합니다. 이제 9 여기에있다. 따라서 9는 목록의 앞에 있습니다. 그래서 내가 가서 업데이트 할거야 이 전류 데이터의 크기 구조는 더 이상 0이하지 않으려면 그러나 1로. 나는에서 9를 넣어거야 목록의 앞. 내가 가서 화면을 전환하자 그래서 우리는 여기에 우리 과거 볼 수 있습니다. 그리고 지금 나는 무엇을 원하는가 앞에 넣어? 내가 추적 할 거라는 지금 큐의 앞 위치 0에 있습니다. 무엇이 다음에 일어날 것 때문에? 글쎄, 난 큐에 이제 가정 17뿐만 아니라. 그래서 거기에 줄을 뛰어. 그리고 또, 도어의 종류는에 가게는 여기에 것입니다. 그래서 지금은 17 추가했습니다. 그리고이 녀석이 차단 되더라도 OK의 화면, 우리는 여기에서 그것을 볼 수 있기 때문이다. 미안 해요. 대상 : 우리는 이동할 수 있습니다 - DAVID 마란 : 아니, 괜찮아. 그것은 거기 거대한이다. 그래서 17 내부 큐에서 지금이다. 어느를 업데이트해야합니다 필드 지금 생각? OK, 확실히 크기입니다. 그리고 어떻게 전면 어떻습니까? OK, 아니. 전면 변경되지해야하기 때문에 스택과는 달리, 우리는 공정성을 유지하려고합니다. 9이 먼저 온 경우에, 우리는 9 할 라인의 첫 번째 아웃 할 수 그리고 저장소에. 사실,의​​는 것을 볼 수 있습니다. 우리는 22를 삽입하기 전에하자 가서 대기열에서 제외 9. 이름이 뭐였더라? 대상 : 제이크. DAVID 마란 : 제이크 것입니다 현재 대기열 수 있습니다. 그래서 당신은 가게에 걸어 얻는다. 그리고 척하는 가게 거기입니다. 그래서 지금 필요한 사항 - DIT-DIT-DIT! 이제 어떻게 일어날 필요가 있겠습니까? 디자인 결정. 그래서 나쁜 본능 만 - 이름이 뭐였더라? 대상 : 데이비드. DAVID 마란 : 데이비드. 그래서 다윗은 어떻게 했습니까? 그 데이터를 수정 정렬하려고했다 자신의 위치에서 구조 및 이동 제이크의 이전 위치로. 우리가하고자하는 경우 그 괜찮습니다 로 그를 받아들이 구현 세부 사항입니다. 하지만 먼저,의 데이터를 업데이트 할 수 있도록 우리는 구조를 그것을하기 전에. 나는 모든 아이디어를 좋아하지 않는니까 사람들이 줄을 이동. 다윗은 그것을 수행하는 경우 그것은 더 큰 문제 없다 한 번, 그러나 다시, 다시 생각한다 우리에 8 자원 봉사자를했다했을 때 무대와 우리는 삽입과 같이 했어 우리가 시작했던 정렬 주위 사람을 이동. 맞아, 비싸있어? 그 큰 O 나에 대해 싫증이 나다 만드는 N으로, n은 큰 O를 다시 제곱. 그것은 같은 느낌이 아니에요 이상적인 결과. 그럼 그냥이 업데이트 할 수 있습니다. 그래서 큐의 크기 더 이상이 없습니다. 이제 단순히 하나입니다. 하지만 지금 뭔가를 업데이트 할 수 있습니다 나는 전에 업데이트되지 않았습니다 목록의 앞. 난 그냥 말할 수, 그 위치는 1입니다? 그래서 지금 우리가 여기에 쓰레기 값이 쓰레기는 여기에 값 및 데이비드 이 쓰레기의 중간. 그러나 데이터 구조 그대로이다. 그리고 사실, 난 할 필요가 없습니다 제이크의 이전 번호를 변경 9, 대숩 때문이다. 지금에 충분한 정보를 가지고 나는 거기에 한 사람 알고있는 사이즈 이 큐. 그리고 내가 아는 그 사람 위치 1이 아니라 0이다. 내가 계산 아니에요. 뿐만 아니라 1 그래서. 따라서 데이터 구조는 여전히 OK입니다. 그럼, 다음에 어떻게됩니까? 하자 대기열 - 당신의 이름은 무엇입니까? 대상 : 캘런. DAVID 마란 : 캘런. 의는 캘런를 큐에있게하고, 22 대기열에 지금이다. 그래서 지금 여기에 변화가 무엇인가? 프런트에 갈되지 않습니다 분명히 변경할 수 있습니다. 크기는 다시 2로 변경하는 것입니다. 22 여기서 끝, 9, 여전히 존재 그러나 그것은 효과적으로의 지금은 쓰레기 값입니다. 그냥 제이크 과거의 잔재이다. 그래서 지금 일어나는 경우 어떻게 나는 데이비드 큐에서 제거? 마지막으로 작업 대기열에서 제외 데이비드. 우리는 변화 할 수 있습니다,하지만하자를 제안 가능한 약간의 작업으로 수행. 이제 내 데이터 구조 간다 2에서 1로 크기가 백업하십시오. 그러나 큐의 앞 지금은 2가됩니다. 나는이 번호를 변경할 필요가 없습니다 그들이있어 아직 있기 때문에 그냥 쓰레기 값. 하지만 지금은 어떻게됩니까? 나는 26 자신을 큐에 가정? 여기에 속하는 것 같은 느낌. 그래서 나는 대기열에 넣는거야. 그래서 나는 어떤 종류의 여기에 속한다. 그리고 당신은 확실히 않더라도 무대에서 시각이 주셔서 감사합니다, 우리는 충분한 공간을 가지고 있기 때문에, 내가해야 여기에 서하지, 왜? 대상 : 당신이 범위를 벗어입니다. DAVID 마란 : 오른쪽. 나는 범위를 벗어 해요. 내가 넘어 색인 것 이 배열의 경계입니다. 정말 중 하나에 있어야합니다 세 가지 위치. 이제 어디로 가야하는 가장 자연스러운입니까? 나는 우리가 활용 제안 일주일에 한 트릭. Mod 연산자, 비율입니다. 나는 기술적으로 서니까 위치 3,하지만 난 3 모드 용량을 그래서 3 퍼센트 기호 3 - 용량은 3이다. 그게 뭐야? 나머지는 언제 무엇입니까 당신은 3으로 3 분할? 0. 저를두고 그래서 제이크이었다 이것은 실제로 좋은 것입니다. 그래서 지금 구현 이 물건은 것의 두통의 비트 수. 그것은 정말로 단지 한 줄의 두통의 코드. 하지만 적어도 지금은 쓰레기가있다 값이 여기에 있지만, 두 가지가있다 여기에 합법적 인 정수. 그리고 지금 우리가 할 것을 주장 우리는 너무 오래 같이 할 필요가 정확히 우리는 무엇 제이크의 변경 값은 26이 될 것이었다. 우리는 지금도 충분한 정보를 가지고 무결성을 유지하기 위해 이 데이터 구조. 우리는 여전히 어떤 운으로있을 때 우리 네 개 이상의 총을 삽입 할 요소,하지만 난 적어도 만들 꽤 있습니다 이 상수의 효율적인 사용 시간이 실제로있다. 나는 변화에 대해 걱정할 필요가 없습니다 다윗의 경사와 같은 사람이 있었다. 스택에 대한 질문 또는이 큐? 관객은 : 이유입니다 당신이 알고 있도록 크기를 필요로 사람을 가지고 어디? DAVID 마란 : 그렇습니다. 나는 배열의 크기를 알 필요가 내가 정확히 알 필요가 있기 때문에 이러한 값의 대부분은 합법적이며, 배치 할 위치를 그래서 내가 찾을 수있는 다음 사람. 정확히. 크기는 - 실제로, 우리는 아직이 업데이트되지 못했습니다. 나는 26에 자신을 추가했습니다. 크기, 지금은 1 만, 2. 그래서 지금이 참으로 저를 찾을 수 목록의 머리, 이는 0이 아닌 1 만 2입니다. 목록의 앞 실제로 22 번이다. 그는 먼저 와서, 그래서 그는해야하기 때문에 내 앞에 가게에 허용, 비록 시각적으로 내가 서있어 가까이 저장할 수 있습니다. 모든 권리? 이 녀석 갈채 그리고 우리는 그들을 거기서 드리겠습니다. [박수] DAVID 마란 : 나는하도록 할 수 당신은 트레이를 유지합니다. 우리는 경우 어떻게되는지 볼 수 당신이 원하는,하지만 어쩌면 아닙니다. 좋아. 그래서 지금이 우리를 떠나지 않습니다? 음, 거기에있는 나에게 제안하자 우리가 할 수 몇 가지 다른 데이터 구조 것입니다 우리의 도구 키트에 추가 시작 사실은 꽤, 상당히 관련 등의 수 우리는 웹 물건에 뛰어들. 또, 어떤 연결이있는 의 형태로 나무에 DOM, 문서라는 것을 개체 모델. 그러나 우리는 더 볼 수 있습니다 그렇게 오래 전에. 내가 definitionally 제안하게하는 우리 지금 당신이로 알고 있습니다 어떤 나무를 호출 가족 나무, 당신보다 에서 약간의 조상이 나무의 뿌리. 에서 족장이나 여자 가장 트리의 맨. 배우자가없는,이 경우합니다. 그러나 우리는 지금 우리가 전화 할게 뭔지 걸어 노드입니다 아이들, 왼쪽의 자녀 또는 오른쪽 자식 오프 여기에 묘사 된대로 화살표. 트리 데이터 구조 즉,에 컴퓨터, 트리 제로가 이상의 노드. 그것은 적어도 하나의 노드가있는 경우, 그는 루트라고. 그것은 시각적으로 그 물건의 우리는 정상에 그립니다. 그리고 해당 노드가 다른 노드 버리면 할 수 있습니다 , 0, 1 또는 2 또는 3이 또는 그러나 많은 아이들 데이터 구조를 지원합니다. 이 경우, 루트, 저장 값을 하나, 두 아이, 2, 3을 가지고 그래서 우리는 일반적으로 2 왼쪽 호출 어린이 및 3 오른쪽 아이. 그리고 우리는 5-6를 얻을 때 7, 6 중간 아이라고 할 수 있습니다. 당신은 4 명의 아이들이있는 경우 그것은 혼란을 가져옵니다. 그래서 우리는 그런 종류의 사용을 중지 구두 바로 가기. 하지만 정말 그냥 가족 나무입니다. 그리고 여기 단풍은 해당 노드입니다 자신은 아이가 없습니다. 그들은 나무의 바닥을 건다. 그래서 우리가 어떻게 나무가를 구현할 수 있습니다 최대한 단 두 아이가? 우리는 이진 트리 전화 할께. BI는 다시, 두 개의 의미 바이너리와 같은 경우. 그리고 그것은, 0, 1을 가질 수 있습니다 극대 또는 두 아이. 나는 우리가 노드를 구현할 것을 제안합니다 INT N과 그 구조, 그리고 두 개의 포인터는 하나라는 왼쪽, 하나는 오른쪽했다. 하지만 그 그냥 좋은 위치 임의의 규칙. 그리고 당신은 지금 특히 좋은 무엇을의 의 종류와 개념 고투 재귀하거나하지라고 생각 아무것도 정말 솔루션 특히 수 있다면 메모리가 부족. 우리는 데이터에 대해 얘기하고 이제는 구조 및 허용 알고리즘 우리는 통과하고 조작 할 수 재귀가 다시 온다 밝혀 훨씬 더 강력한 아름다운 방법이 아니라면. 내가 제안이 구현되도록 검색 기능. 두 개의 입력을 감안할 때 - 그래서 블랙 박스로 생각. 두 개의 입력, N, INT, 그리고 주어진 나무 포인터에 대한 포인터 트리의 노드 또는 정말 루트 I 이 함수가 리턴 할 수있는 주장 true 또는 false, 그 값 N 이 나무의 내부입니다. 이 블랙 박스 안에 무엇입니까? 음, 네 가지. 첫 번째 그냥 확인합니다. 나무가 null의 경우는, false를 반환합니다. 어떤 노드가없는 경우, 아무 N이 없습니다 어떤 번호가 없다, 다만 false를 반환합니다. 당신이 찾고 있지만, N, 값이있는 경우 를 들어, 나무 화살표 n보다 적은이고, 단지 명확하게, 그것은 때 무슨 뜻 이죠 나는 그 나무와 화살표 쓰기 표기법, N? 정확히. 그것은 역 참조를 의미 포인터가 나무를했다. 그 안에 들어간 다음 거기에 가서, 노드와 N 라 불리는 필드를 얻는다. 그리고 한 실제 N을 비교 반대 검색에 전달. n은 N 값보다 작 그렇다면 트리 노드 자체가, 잘, 그게 무슨 뜻 이죠? 그것은 첫눈에 아무런 의미가 없습니다. 오른쪽? 당신의 배열이있을 때 그냥 좋아 값은 2 진을 적용 추천 분할의 형태로 검색 정복. 그러나 우리는 할 것을 가정해야 않았다 이진 검색이 전혀 작동 할 전화 번호부과 이전 예? 정렬 방법. 그러니 트리의 정의를 수정하자 여기에서 할 수있는 단지 나무 수없는 아이들의 번호가 있습니다. 다만 이진 트리,하는 수 최대한 0, 1 또는 2가있다. 하지만 이진 검색 트리 또는 BST와 같은 이는 단지를 말하는 멋진 방법입니다 같은 이진 트리가 모든 노드의 왼쪽 아이가있는 경우이며, 노드보다. 그리고 모든 노드의 오른쪽 자식, 존재하는 경우, 클 노드 자체보다. 그래서 다른 말로하면, 경우에 당신은 그릴 수 있었다 나무 밖으로는 모든 숫자는 신중하게 다음과 같이 균형되도록 경우 당신이 루트로 55이, 33 갈 수 있습니다 그 왼쪽으로 55 이하이기 때문에. 77 권리 때문에 갈 수 그것은 55보다 큰 있습니다. 하지만 지금은, 동일한 정의를 알 그것은 구두로 재귀 적 정의의 33를 신청합니다. 33의 왼쪽 자식, 그것보다 작아야합니다 33의 오른쪽 아이, 44이어야합니다 그것보다 큰. 그래서 이것은 이진 검색 나무이며, 나는 약간의를 사용하여 제안 재귀, 우리는 이제 N을 찾을 수 있습니다. 여기서 n은의 값이 n보다 작 그렇다면 현재 노드, 내가 갈거야 앞서 펀트 말하자면, 그냥하기 대답은의 무엇이든 반환 에 N을 검색 트리의 왼쪽 자식입니다. 다시 주목,이 기능을 단지 노드 스타를 기대 노드에 대한 포인터. 그래서 확실히 나는 나무 마찬가지로 수 이끌 왼쪽 화살표, 나 다른 노드로. 그러나 노드는 무엇입니까? 음,이 선언에 따라, 왼쪽 그래서 그냥 그냥 포인터 내가 검색 기능을 전달하고있어 의미 다른 포인터, 즉 나타내는 하나의 내 왼쪽 아이의 나무. 따라서이 경우 포인터가있는 경우, 33 이 샘플의 입력 사이에, 경우입니다 n은의 값이 n보다 큰 트리에서 현재 노드 다음, 난 기타에 앞서 펀트 갈 방향과 방금 뭐라고, 내가하지 이 값을 n은 트리에 있는지 알고, 그러나 그것은 경우 나도 알아, 그것은 아래의 내 오른쪽 분기 말하자면. 그래서 나는 재귀 적으로 검색하고 부르 자, 다시 N을 전달하지만 전달 내 오른쪽 자식에 대한 포인터. 즉, 나는 현재하고 있어요 경우 55 내가 99을 찾고 있어요, 내가 아는 99 내가 찢어 그래서 그냥 같이 55보다 큰 경우 전화 번호부 주 전 우리 오른쪽으로 가서 마찬가지로 우리는 여기 갈. 그것은 내 오른쪽에 그리고 만약 모르겠어요 아이, 그리고 그게 아니라, 77이 있습니다 만, 나는 그 방향으로 알고. 그래서, 내 오른쪽 자식 검색 전화 77, 및에서 검색 그림을 보자 이 경우이 임의의 99 예를 들어이 사실이다. 또, 마지막 사건은 무엇인가? 나무의 경우는 null를 한 경우입니다. n은 현재 노드의보다 적은 경우 값이 다른 경우가 있습니다. n은 현재보다 큰 경우 노드의 값은 세 번째 경우이다. 네 번째이자 마지막 사건은 무엇입니까? 금방, 우리는 케이스에서 생각해? 그것은 n은에 있음을해야합니다 지금 제가하는 현재 노드. 나는이 시점에서 55을 찾고 있어요 그래서 만약 의 이야기에서, 해당 분기 나무는 true를 반환합니다. 그래서 여기에 흥미로운 것은 그 우리 실제로, 주와 달리 과거의 우리 종류 의 두 가지 기본 경우가 있습니다. 그리고 그들은 필요가 없습니다 위쪽에있는 모두합니다. 상단은 기본 케이스 때문에 경우 나무가 NULL 할 수있는 아무것도 없습니다. 그냥 하드 코드를 반환 거짓의 값입니다. 하단 분기의 일종이다 기본적으로는, 그것에 우리가 검사 한 경우 그것이 있어야 경우는 null, 우리는 확인했다 왼쪽,하지만하지 않아야, 우리는했습니다 그것은 바로해야하는 경우 확인하지만, 안된다, 명확하게는되어야합니다 바로 여기서 우리는. 기본 케이스 그건. 그래서 두 개의 재귀 경우가있다 중간에 거기에 끼워. 하지만 쓸 수 이 임의의 순서로한다. 난 그냥 어떤 종류의 자연의 느낌 생각 첫 번째 가능한 오류를 확인하려면, 그런 다음 왼쪽 확인한 다음 다음 바로 확인 당신이 노드한다고 가정 당신은 실제로 찾고 있습니다. 그럼 왜이 유용 할 수 있습니다? 그래서 밝혀 - 나이 맛보기로 이동하자 여기에 그 웹에서이다. 우리는하지를 사용하여 시작하는거야 프로그래밍 처음에는 언어 만 마크 업 언어입니다. 의 하나되는 마크 업 언어 프로그래밍과 정신은 비슷할 언어,하지만 당신에게 제공하지 않습니다 능력은 논리적으로 자신을 표현한다. 그것은 단지 당신에게 능력을 제공 구조적으로 자신을 표현한다. 당신은 어디에서 무언가를 넣고 싶어 페이지에서 웹 페이지? 무슨 색깔 당신이 그것을 할 싶어? 어떤 글꼴 크기 당신은 그것을 할 싶어? 어떤 단어는 실제로 당신을 웹 페이지에서 원하는? 그래서 그 마크 업 언어이다. 하지만 우리는 매우 신속하게 소개합니다 본격적인입니다 자바 스크립트, 프로그래밍 언어. 구문 외관과 매우 유사 C에,하지만 몇 가지가 있습니다 좋은, 더 강력한, 더 많은 사용자 친화적 인 기능을 제공합니다. 이에 좌절 한 학기 요점은 우리가 거​​ 야입니다 곧 훨씬 적은에서 맞춤법 검사기를 구현 다른 언어를 사용하여 코드 라인 C 자체가 허용하는 것보다,하지만 이유에 대한 우리는 곧 이해하게 될 것입니다. 이 최초의 웹 페이지가됩니다. 그것은 완전히 실망 할 것 우리가 만드는 첫 번째. 그것은 단순히 안녕하세요 세계, 말할 것이다. 하지만 당신은 그것을 본 적이 없다면 전에, 이것은 HTML이다 하이퍼 텍스트 마크 업 언어. 당신은에서 특정 메뉴 옵션에 가면 에 대한 웹 페이지의 대부분은 어떤 브라​​우저 인터넷, 당신은 HTML을 볼 수 있습니다 어떤 사람들은에 쓴 해당 웹 페이지를 만들 수 있습니다. 그리고 그것은 아마로 보지 않는다 간단한 또​​는만큼 깔끔한. 그러나 이들의 패턴을 따를 것 열린 괄호와 슬래시와 문자와 잠재적 숫자입니다. 나는 당신에게 맛보기를 줘야 할 것 같아서 당신이 할 수있을 것이다 무엇 CS50 복용 후. 저 cs.harvard.edu / 약탈에 가자, 우리 자신의 롭 보덴의 홈페이지. 그분은 우리를 위해 이것을했다. 그래서 당신은 곧 일을 할 수있을 것이다. 또한, 당신은 무엇을 들었어요 오늘 아침 - 이 아침에 듣고 무엇을 - [햄스터 댄스 음악] - 내려가이 만들 수있을 것이다. 즉, 수요일에 우리를 기다리고 있습니다. 우리는 당신에게 다음을 볼 수 있습니다. [햄스터 댄스 음악] DAVID 마란 : 다음 CS50에서 -