[음악 연주] 스피커 1 : 좋습니다. 모든 사람은 다시 섹션에 오신 것을 환영합니다. 여러분 모두가 성공적으로 희망 퀴즈에서 회복 지난 주. 나는 항상 조금 미친 짓이야 알고있다. 당신이 있다면 내가 전에 말했듯 표준 편차 이내 정말 특히, 그것에 대해 걱정하지 마십시오 덜 편안한 섹션을 참조하십시오. 그것은 당신이 있어야 할 곳에 대해입니다. 당신은 멋진, 훌륭한 한 경우. 당신에게 명예. 그리고 당신이 느끼는 경우에 당신이 필요로 좋아 조금 더 도와주세요 도달 주시기 바랍니다 TF가 어떤 밖으로. 우리는 여기에 도움이한다. 우리가 가르치는 이유입니다. 내가 당신을 위해 여기에 매주 월요일 해요 이유 목요일에 남자와 사무실에서 시간. 그래서 알려 주시기 바랍니다 당신은 아무것도에 대한 걱정이된다면 또는 퀴즈에 아무것도 경우 거기 것을 정말 해결하고 싶습니다. 그래서 오늘의 의제는 모든 데이터 구조에 대한. 이들 중 일부는 그냥있을거야 이러한 익숙하게 얻을 수 있습니다. 당신은 지금까지 구현하지 않을 수 있습니다 이 클래스의 그들. 당신 것입니다 그들 중 일부, 당신의 철자의 PSET에있다. 당신은 선택을해야합니다 해시 테이블과 시도 사이. 그래서 우리는 확실히 그 이상 갈 것. 그것은 종류의 확실히 더 될 것 높은 수준의 섹션의 오늘, 그러나, 때문에 거기에 그들 중 많은, 그리고 경우 우리는 구현 세부 사항에 갔다 이 모든, 우리는 않을 것 심지어 연결리스트를 통해 얻을 아마 해시 테이블의 약간. 그래서 나와 함께 곰. 우리는 일을하지 않을거야 많은이 시간을 코딩. 당신은 그것에 대해 질문이있는 경우 또는 당신은 그것을 구현보고 싶어 나 자신을 위해 그것을 시도, 나는 확실히 추천 , study.cs50.net하려고하는 이 모든 예제를 가지고있다. 내 파워 포인트를 할 것이다 메모와 함께 그 우리 일부 프로그래밍뿐만 아니라 사용하는 경향 운동, 특히 것들에 대한 연결리스트와 이진 등 나무 스택과 큐. 그래서 좀 더 높은 수준의, 어떤 너희들을위한 좋은 수 있습니다. 그와 그래서, 우리는 시작합니다. 또한, 그럼요 퀴즈. 나는에있는 당신의 대부분의 생각 내 부분은, 당신의 퀴즈가 하지만 사람 또는 어떤 이유에서 오는 당신 하지, 그들은 바로 여기 앞에있어. 그래서 연결리스트. 이동의 나는이 종류를 알고 퀴즈 전에 백업합니다. 그 전에 주이었다 우리는 이것에 대해 배웠다. 그러나이 경우에, 우리는 정액 깊이에서 조금 더 이동합니다. 그럼 왜 우리는을 선택할 수 있습니다 배열을 통해 목록을 연결? 그들은 무엇 구별? 네? 청중 : 당신은 확장 할 수 있습니다 링크 배열의 크기가 고정 대 나열합니다. 스피커 1 : 맞아요. 배열은 반면 크기를 고정하고있다 연결리스트는 가변 크기를 갖는다. 우리가 모르는 경우 어떻게 많은 우리가 저장하고자, 연결리스트는 우리에게 훌륭한을 제공합니다 방법은해야 할 일이 우리가 할 수 있기 때문에 다른 노드에 추가에 추가 다른 노드와 다른 노드에 추가합니다. 그러나이 트레이드 - 오프 (trade-off) 될 수 있을까요? 사람은 트레이드 오프를 기억 하는가 배열과 연결리스트 사이? 음 .....? 청중 : 당신은에있다 모든 방법을 통해 이동 링크 된 목록을 목록의 요소를 찾을 수 있습니다. 배열, 당신은 할 수 단지 요소를 찾을 수 있습니다. 스피커 1 : 맞아요. 그래서 arrays--와 청중 : [들리지]. 스피커 1 : 배열, 우리가 어떤 것은 랜덤 액세스라고합니다. 우리가 원하는 경우에 무슨 일이 있음을 의미 목록의 사상 다섯 번째 포인트 또는 다섯 번째 지점 우리 배열, 우리는 단지 그것을 잡아 수 있습니다. 이 연결리스트가 있다면, 우리가 오른쪽을 반복하는? 그래서 요소에 액세스 배열은, 일정 시간 이 것 링크 된 목록 반면, 가장 가능성이 있기 때문에 어쩌면 선형 시간이 우리의 요소는 마지막에 모든 방법입니다. 우리는 모두를 검색 할 수 있습니다. 이러한 모든 데이터 그래서 우리가 가고있는 구조 에 좀 더 많은 시간을 소비하기 위해, 흑자 및 네거티브은 무엇인가. 우리는 할 수 있습니다 때 다른 통해 하나를 사용? 그리고 그 가지의 더 큰 일이 빼앗아. 그래서 우리는 여기에있다 노드의 정의. 그것은 하나의 요소처럼 우리의 연결리스트, 오른쪽? 그래서 우리는 모두 잘 알고 우리의 형식 정의 구조체와, 우리는 지난 번 리뷰에 갔다한다. 그냥 만들면 기본적했다 우리가 사용할 수있는 다른 데이터 유형입니다. 그리고이 경우에는, 어떤 노드의 즉, 약간의 정수를 개최한다. 그리고 두 번째 부분은 여기에 무엇입니까? 누구? 청중 : [들리지]. 스피커 1 : 그래. 그것은 다음 노드에 대한 포인터이다. 그래서이 사실은 여기에 있어야한다. 이 유형의 포인터 다음 일에 노드입니다. 그리고 그것은 무엇을의 그들 우리의 노드를 포함한다. 쿨. 검색 좋아, 그래서, 우리가 있었던 것처럼 당신이 있다면 그냥 손 전에 말 를 검색 할 것, 실제로 반복해야 링크 된 목록을. 우리는 숫자를 찾고 있다면 그래서 9, 우리는 우리의 머리에 시작할 것 그리고 그 시작 부분에 우리 포인트 우리의 연결리스트의 오른쪽? 그리고 우리는 OK,이 작업을 수행, 말 노드 번호 (9)를 포함? 아니? 좋아, 다음 단계로 이동합니다. 그것을 따르십시오. 그것은 수 (9)이 포함되어 있습니까? 아니오. 다음 중 하나를 수행하십시오. 그래서 우리는 실제로 반복해야 우리의 링크 목록을. 우리는 단지 9 곳으로 바로 이동 할 수 없습니다. 그리고 너희들은 실제로 원하는 경우 몇 가지 의사 코드까지를 참조하십시오. 우리는 여기에 몇 가지 검색 기능을 즉,에 걸릴 무엇을 받한다? 당신은 어떻게 생각하세요? 그래서 쉬운. 이 무엇입니까? 청중 : [들리지]. 스피커 1 : 우리가 찾고있는 수. 오른쪽? 어떤이는에 해당하는 것? 그것은 포인터입니까? 청중 : 노드. 스피커 1 : 목록에 노드 우리는 오른쪽에서 찾고 있다는 것을? 그래서 우리는 일부 노드가 여기에 포인터입니다 있습니다. 이 문서의 정보는 다음의 제품에 무슨 점입니다 실제로 우리의 목록을 반복. 우리는 목록에이 동일하게 설정 그건 그냥 왜냐하면 에이 동일한 설정 우리의 연결리스트의 시작. 그리고 그것은 NULL이있는 동안, 동안 우리는 여전히 우리의 목록에있는 물건을 가지고 해당 노드가 있는지 확인 우리가 찾고있는 번호입니다. true를 돌려줍니다. 그렇지 않으면, 오른쪽을 업데이트? null의 경우, 우리는 우리의 종료 While 루프와 false를 반환 그 의미하기 때문에 우리는 그것을 발견하지 않았습니다. 모두가 그 작동 방법을 얻을 수 있습니까? 확인을 클릭합니다. 당신은 삽입에 따라서 세 가지 방법이있다. 당신은 당신이 추가 할 수 있습니다, 앞에 추가 할 수 있습니다 모듬으로 당신은 삽입 할 수 있습니다. 이 경우, 우리는 야 앞에 추가 할 것. 사람이 어떻게 사람들을 알고 있나요 삼가지 경우는 다를 수 있습니다? 그래서 앞에 추가하면 넣어 것을 의미한다 그 목록의 앞에. 그래서 의미에 상관없이 그 노드는 상관없이 어떤 값이 무엇인지, 당신은거야 OK, 바로 앞에 여기를 넣어? 그것은 첫 번째가 될 것 목록의 요소입니다. 당신이 그것을 추가하면 돼가 목록의 맨 위로 이동합니다. 그리고 모듬 당신이있어 의미에 삽입 장소에 실제로 넣어 것 이 유지 어디에 연결리스트 정렬. 다시 말하지만, 당신은 어떻게 사용 그 때 사용 그들은 경우에 따라 달라질 수 있습니다. 그것은 필요하지 않는 경우 정렬, 앞에 붙는 경향이있다 무슨 대부분의 사람들이어야합니다 당신이하지 않기 때문에 사용 전체 목록을 이동해야 오른쪽을에 추가 할 수있는 끝을 찾는 방법은? 당신은 바로 그것을 찌를 수있다. 그래서 우리는 통과합니다 삽입 한 지금. 내가 갈거야 그래서 한 가지 높은이 PSET에 추천 언제나처럼, 물건을 그릴 것입니다. 당신이 업데이트하는 것이 매우 중요합니다 올바른 순서대로 포인터 당신이 그들을 업데이트 할 경우 때문에 약간 순서가, 당신은 끝날거야 목록의 일부를 잃는. 그래서 예를 들어,이 경우, 우리는 야 1 단지 지점에 머리를 말하고. 우리는 그렇게한다면 이 일을 저장하지 않고, 우리는 아무 생각이 무엇인지 1 이제 가리켜 야 우리는 분실했기 때문에 무엇 머리는 지적했다. 그래서 한 가지 기억해야 할 때 앞에 추가하고있어 무엇을 저장하는 것입니다 처음에 머리 포인트, 다음를 재 할당 한 다음 업데이트 어떤 새로운 노드를 표시해야한다. 그 경우는 그것을 하나의 방법이다. 우리는이 방법을 수행했다 그래서 만약 여기서 우리는, 머리를 재 할당 우리는 기본적으로 우리가 손실 전체 목록, 오른쪽? 이를 수행하는 한가지 방법은 한 점에있을 것이다 다음, 다음 (1) 머리 점을 가지고있다. 또는 당신은 같은 종류의 할 수 내가 얘기 임시 저장. 하지만 당신의 재 할당 올바른 순서로 포인터 매우, 매우 될 것입니다 이 PSET 중요합니다. 그렇지 않으면, 당신은 해시를 할 겁니다 테이블 또는 단지 될 것 시도 단어의 일부만 당신 혹시 교수님은 음 ..... 그런 다음 원하는? 청중 : 임시 무엇 스토리지 것은 당신에 대해 얘기했다? 스피커 1 : 임시 저장. 그래서 기본적으로 다른 당신이 할 수있는 방법 처럼, 뭔가의 머리를 저장한다 그것을 임시 변수를 저장합니다. 1로 지정하고 다음 가리 키도록 한 업데이트 어떤 머리가 가리키는 데 사용. 이 방법은 명백하게 더 우아한 당신 때문에 임시 값을 필요로하지 않지만 단지 그것을 할 수있는 또 다른 방법을 제공. 그리고 우리가 실제로해야합니까 이에 대한 몇 가지 코드. 연결리스트에 대한 그래서 우리 실제로 몇 가지 코드가있다. 그래서이 앞에 추가되어, 여기에 삽입합니다. 그래서이 머리를 들어갑니다. 그래서 일단, 당신은 필요 물론, 새로운 노드를 작성, NULL을 확인합니다. 항상 좋은. 그리고 당신은 값을 할당해야합니다. 때마다 당신은 당신을 새로운 노드를 생성 그것은 다음을 가리키는 무슨 모른다, 그래서 당신은 NULL로 초기화 할. 그것은 무언가를 가리키는 끝날 경우 다른, 그것은 재 할당 및 괜찮아요됩니다. 그 첫 번째 일이있는 경우 목록에서, 그것은 필요 때문에 NULL을 가리 키도록 즉,리스트의 마지막이다. 그럼 삽입, 우리는 우리가 여기 참조 우리의 노드의 다음 값을 할당하는 머리는 무엇이든 될, 이는 우리가 여기에 있었다 것입니다. 즉 우리가 무슨 짓을했는지. 그리고 우리는 지점에 머리를 할당하고 우리의 새로운 노드에 대한 기억 때문에, 새로운는 노드에 몇 가지 포인터입니다 그리고 정확히 머리가 무엇인지입니다. 그게 바로 우리가 왜이다 이 화살표 접근이있다. 쿨? 음 .....? 청중 : 우리가해야합니까 첫 번째 NULL로 새로운 다음을 초기화, 또는 우리는 머리를 초기화 할 수 있습니다? 스피커 1 : 다음 새로운 시작 NULL이어야합니다 당신이 모르는 때문에 그것은 어디있을거야. 또한,이 종류의 것입니다 단지 패러다임을 좋아한다. 당신은 NULL 동일 단지 수 있도록 설정 반드시 모든 기지가 다루어진다는 것을 해당하므로, 어떠한 재 할당을하기 전에 당신은 항상 것을 보장하고 특정 값을 가리키는 수 쓰레기 값 같은 대. 그래, 우리가 할당 때문에 자동으로 다음 새, 하지만 그것은 단지 같은 더 많은 것은 인 좋은 습관을 초기화 그 방법으로 다음 재 할당. 좋아, 그럼 이중으로 지금 연결리스트. 우리는 무엇을 생각 하는가? 무엇과 다르다 이중 연결리스트? 그래서 우리의 연결리스트에서, 우리는 할 수 하나 지 방향으로 이동? 우리는 다음이있다. 우리는 앞으로 갈 수 있습니다. 이중 연결리스트, 우리는 또한 뒤로 이동할 수 있습니다. 그래서 우리는뿐만 아니라이 우리가 저장할 수, 그것은 다음을 가리키는 곳에 우리는이 우리는 어디에서 왔는지. 그래서이 가능 더 좋은 통과. 그래서 이중 연결 노드, 매우 유사, 맞죠? 유일한 차이는 우리는 지금 다음 및 이전을해야합니다. 그것은 유일한 차이점이다. 우리가 있었던 경우에 따라서 앞에 추가 또는 append-- 우리합니다 이곳에이에 대한 코드를 가지고 있지 않습니다 하지만 당신이 시도했다 경우 , 중요한 것은 삽입 당신이 할 필요가있다 확실히 당신은 할당하고 모두 이전하고 올바르게 다음 포인터. 이 경우, 당신은 것 만 다음 초기화하지, 당신은 이전 초기화합니다. 우리는리스트의 선두에 있다면, 우리 머리와 동일한 새로운 만들 것뿐만 아니라, 하지만 우리의 새로운 이전은해야 오른쪽 머리를 가리? 즉, 유일한 차이점이다. 그리고 당신은 더 많은 연습을 원하는 경우 삽입과 연결리스트, 이러한, 인서트, 삭제와 모듬 목록으로, study.cs50.net을 확인하시기 바랍니다. 큰 운동의 무리가있다. 내가보기 엔 그들을 권장합니다. 나는 우리가 그들을 통해 갈 시간이 있었으면 좋겠다 그러나 데이터 구조들이 많이있어 를 통해 얻을 수 있습니다. OK, 해시 테이블 그렇게. 이것은 아마도 가장입니다 당신의 pset에 유용 비트 여기에 당신이있을거야 때문에 이들 중 하나, 또는 시도를 구현. 정말 해시 테이블을 좋아한다. 그들은 꽤 멋지다. 그래서 기본적으로 무엇을 발생은 해시 테이블 우리가 정말 빠른해야 할 때입니다 삽입, 삭제, 조회. 사람들은 우리가하고있는 일입니다 해시 테이블에 우선 순위. 그들은 꽤 큰 얻을 수 있습니다 하지만 우리는 시도로 볼 수 있습니다로, 훨씬 더 큰 일이있다. 그러나 기본적으로, 모든 해시 테이블은 해시 함수 즉, 각을 넣어하는 버킷을 알려줍니다 데이터의, 당신의 각 요소. 간단한 방법은 해시 테이블 생각 사물의 단지 버킷 점이다, 맞죠? 당신은에 의해 일을 정렬되도록 할 때 그들의 이름 첫 글자 등, 그 종류의 해시 테이블처럼. 나는이 그룹에 있다면 그래서 너희들은 이름이 시작 누구든 그룹으로 여기에, 또는 생일은 누구든 , 1 월, 2 월, 3 월에 무엇이든, 그것은 효율적입니다 해시 테이블을 생성. 그냥 버킷을 만드는 것 그 당신은에 당신의 요소를 정렬 당신이 그들을 쉽게 찾을 수 있도록. 내가 필요로하는이 방법 그래서 둘 중 하나를 찾으려면, 내가 검색하지 않아도 당신의 이름의 각각을 통해. 나는 오, 같이 할 수있다, 나는 알고 다니엘의 생일은 말야 ...이다 청중 : --April. 스피커 1 : 2011 년 4 월. 그래서 난 내 4 월에보고 양동이, 및 운, 그녀가 하나가 될 것입니다 및 내 시간은, 그런 의미에서 일정이었다 내가보고있는 경우 반면, 사람들의 전체 무리를 통해, 그것은 훨씬 더 오래 걸릴 거예요. 그래서 해시 테이블 정말 그냥 버킷입니다. 쉬운 방법은 그들을 생각합니다. 그래서 매우 중요한 일에 대한 해시 테이블은 해시 함수이다. 그래서 일이 나는 것처럼 이야기 당신의 이름의 첫 번째 편지 또는 당신의 생일 달, 이러한 아이디어가 정말로 해시 함수에 연관. 그것은 결정의 단지 방법있는 당신이 확인하고 요소로 전환 식당? 그래서이 PSET를 들어, 당신은 찾아 볼 수 있습니다 원하는 해시 함수 꽤 많이. 자신의 할 필요가 없습니다. 정말 괜찮은 사람은 밖으로있다 미친 수학의 모든 종류가있다 할 수있다. 그리고 당신은 당신을하려는 경우 슈퍼 빠른 맞춤법 검사기, 나는 확실히 것 그 중 하나에 보인다. 그러나 또한있다 계산 같은 간단한 것들, 단어의 합과 같은 각 문자는 번호가 있습니다. 합을 계산한다. 즉, 버킷을 결정합니다. 또한 쉽게 것들 갖도록 단지의 여기의 모든처럼, B 모두 여기에 있습니다. 그 중 어느 하나. 기본적으로, 당신을 알려줍니다 배열 인덱스로 가야 당신의 요소입니다. 그냥 bucket-- 결정 모든 해시 함수는이다. 그래서 여기에 우리는 예를 문자열의 첫 글자 만 써도 제가 단지에 대해 얘기했다. 그래서 당신은 단지의 일부 해시가 당신의 문자열 마이너스의 첫 글자, 몇 가지를 줄 것이다 0에서 25 사이의 숫자입니다. 하고 싶은 것은 이 나타내는 확인 당신의 해시의 크기 table-- 얼마나 많은 버킷있다. 이들의 많은으로 해시 함수들은 야 가는 그 수도 값을 반환한다 지금까지 버킷 수 이상이어야 당신은 실제로 가지고 하여 해시 테이블, 그래서 당신은 할 필요가 확인 및 사람들에 의해 모드 (mod). 그렇지 않으면, 말하는 것, 아, 버킷 5000에 있어야합니다 하지만 당신은 30가 당신의 해시 테이블의 버킷. 그리고 물론, 우리 모두가 그 알고 어떤 미친 오류가 발생할 것이다. 그럼으로이 mod 확인 당신의 해시 테이블의 크기입니다. 쿨. 충돌 그래서. 모두가 지금까지 좋은가요? 음 .....? 청중 : 왜 것 이러한 대규모의 값을 반환? 스피커 1 : 알고리즘에 따라 하여 해시 함수 사용. 그들 중 일부는 할 것 미친 곱셈. 그리고 방법에 대해 전부 균일 한 분포, 그래서 그들은 정말 어떤 작업을 수행 때로는 미친 것들. 그게 다야. 다른 건? 확인을 클릭합니다. 충돌 그래서. 기본적으로, 앞서 말했듯이, 최상의 시나리오에서, 내가 들여다 어떤 버킷입니다 한 가지를해야 할 것, 그래서 오른쪽, 전혀 볼 필요가 없습니다? 나는 하나가 거기 알고 또는이다 아니, 그건 우리가 정말 원하는거야. 하지만 수만 수천이있는 경우 데이터 포인트와 그 수보다 작 양동이, 우리는 할 겁니다 충돌 경우 결국 무엇인가 에서 생을 마감해야 할 것입니다 이미 요소가 버킷. 그래서 질문은, 무엇을 우리는 그 경우에해야합니까? 우리는 무엇을해야합니까? 우리는 이미 뭔가가? 우리는 단지 그것을 밖으로 던져합니까? 아니오. 우리는 그들 모두를 유지해야합니다. 그래서 방법이 우리 일반적으로 그 무엇을하면된다? 데이터 구조는 무엇인가 우리는에 대해 이야기? 청중 : 링크 된 목록입니다. 스피커 1 : 연결리스트. 그래서 지금, 대신 이들 각각의 버킷은 단지 하나의 요소를 가진 그것의 링크 된 목록을 포함 것 그것에 해시 하였다 소자. OK, 모든 종류의 아이디어를 얻을 수 있습니까? 우리는 배열을 가질 수 없기 때문에 우리는 얼마나 많은 것들을 알 수 없기 때문에 거기에있을 것입니다. 연결리스트는 우리를 수 단지 정확한 숫자를 가지고 그 바로, 그 양동이에 해시? 프로빙은 그래서 선형 기본적으로이 idea-- 이 충돌에 대처하는 한 방법입니다. 당신이 할 수있는 것은이에, 경우입니다 경우는, 베리 1로 해쉬 된 우리는 이미 무언가가, 방금 될 때까지 계속 당신은 빈 슬롯을 찾을 수 있습니다. 즉, 처리 할 수​​있는 한 가지 방법입니다. 처리 할 수​​있는 다른 방법 그것은 함께 우리 단지 링크를 그 이름은 목록 체인이라고합니다. 그래서이 아이디어는 경우 작동 당신이 생각하는 당신의 해시 테이블 보다 훨씬 크다 데이터 설정하거나 경우 시도하고 체인 최소화하려면 그것은 절대적으로 필요한 때까지. 그래서 한 가지 선형이다 분명히 의미 프로빙 당신의 해시 함수 그 그다지 유용하지 않다 당신이 사용하게하려고하고 있기 때문에 당신의 해시 함수, 포인트에 도착, 당신은 아래로 조사 선형 사용할 수 있습니다 어떤 장소. 하지만 지금은, 물론, 아무것도 거기에 끝이 다른 당신이해야 돼요 더욱 아래로 검색 할 수 있습니다. 그리고 더 많은있다 검색 비용이 요소를 입력 들어가는 이제 해시 테이블, 맞죠? 그리고 지금 당신이 가서 시도하고 발견 할 때 베리는 다시, 당신은 그것을 해시거야, 그것은 말할 것 오, 버킷 1에 보면, 그것은 수 없을거야 버킷 1에, 그래서 당신은있어 통과해야 할 것 이들의 나머지 부분을 통해. 그래서, 때때로 유용 그러나 대부분의 경우, 우리는 그런 말을하는거야 체인은 당신이 원하는 것입니다. 그래서 우리는이 이전에 대해 이야기했다. 나는 나 자신의 조금 앞서있어. 그러나 체인은 기본적으로 즉 하여 해쉬 테이블에서 각 버킷 그냥 링크 목록입니다. 그래서 다른 방법으로, 또는 그 이상의 기술 방법, 해시 테이블 생각 그냥 배열 점이다 연결리스트, 어떤 때 당신이 당신의 사전을 작성하고 그리고 당신은 그것을로드하려고하고, 로 생각 연결리스트의 배열 훨씬 더 쉽게 만들 것 당신이 초기화 될 때까지. 청중 : 그래서 해시 테이블 소정의 크기를 갖는, 버킷의 [들림] 같은? 스피커 1 : 맞아요. 그래서 한 세트의 번호를 가지고 당신이 determine-- 버킷 이는 너희들해야 플레이 주시기 바랍니다. 그것은 정말 멋진 일 수있다 무슨 일이 있었 을까 당신은 버킷의 전화 번호를 변경할 수있다. 하지만 그래,가 버킷의 설정 번호. 어떻게 당신이로 적합 할 수 있습니다 당신이 필요로하는 많은 요소 이 별도의 체인 어디입니까 각 버킷리스트를 연결했다. 그게 당신의 해시 테이블을 의미 정확히 크기가됩니다 당신은 잘 될하는 데 필요? 즉, 연결리스트의 요점이다. 쿨. 이 그래서 모두 OK? 좋아. 아. 방금 무슨 일이? 정말 지금. 누군가가 나를 죽이고 같아요. OK 우리는에 갈거야 조금 미친 시도. 나는 해시 테이블을 좋아한다. 나는 그들이 정말 멋진 것 같아요. 시도는 너무 시원하다. 그래서 누군가는 시도가 무엇인지 기억 하는가? 당신은 이상 갔었어야 이를 간략하게 강의에? 당신은 그것이 작동하는 방법의 종류를 기억하십니까? 청중 : 난 그냥 고개를 끄덕 해요 우리는 가서 않았다. 스피커 1 : 우리는 그것을 통해 가야합니까. OK, 우리가 정말 갈거야 현재 상황을 통해 우리는 무슨 말을하는지. 청중 : 즉, 검색 트리입니다. 스피커 1 : 그래. 그것은 검색 트리입니다. 신난다. 그래서 여기에 주목해야 할 한 가지가 있다는 것입니다 우리 개별 문자를 찾고 있습니다 여기, 바로? 그래서 우리의 해시 함수와 이전에, 우리 전체 단어를보고 있었다, 이제 우리는 더 찾고 문자에서, 맞죠? 그래서 우리는 여기 멘델을 통해 맥스웰 있습니다. 그래서 기본적으로 try-- 방법이 생각하는 이것에 대해 그 모든 수준은 여기 문자의 배열이다. 그래서이 루트 노드는 바로 여기에있다? 이는 모든 문자가 모든 단어의 시작을위한 알파벳입니다. 하고 싶은 것은 말하자면, OK, 우리는 몇 가지 M 단어가 있습니다. 우리는 맥스웰을 찾아 가고, 그래서있어 우리는 전체에 M. 그리고 M 포인트로 이동 다른 배열 곳마다 만큼이 단어, 이있는 단어입니다 두 번째 문자로, 한 단어가있다로 두 번째 문자로 B가, 그것은 포인터를해야합니다 일부 다음 배열로 이동. 아마이 아니다 단어 MP 뭔가, 이의 P 위치에 따라서 배열, 그냥 NULL이 될 것이다. 그것은 어떤 단어가 없다, 확인을 말할 것 즉 M은 OK, P 다음에있다? 그래서 우리는, 각각에 대해 생각하는 경우 이러한 작은 것들 중 하나 실제로 이들 중 하나입니다 Z까지에서 큰 배열 그래서 것들 중 하나 무엇을 수 있습니다 그 시도의 단점 가지입니까? 청중 : 메모리의 많은. 스피커 1 : 그것은 바로, 메모리의 톤입니까? 여기에 이​​러한 블록의 각 하나 26 대, 26 요소 배열을 나타냅니다. 그래서 시도는 공간 무거운 믿을 수 없을만큼 얻을. 하지만 그들은 매우 빠르다. 그래서 매우 빠르지 만 정말 공간이 비효율적. 종류의 파악해야 어느 밖으로 당신이 원하는. 다음은, 당신의 pset 정말 멋진 하지만 메모리를 많이 차지하지, 그래서 당신은 트레이드 오프 (trade off). 그래? 청중 :이 수 있을까 다음 시도를 설정하고 당신은 일단 모든 당신이 need-- 그것이 데이터 그 의미가하면 나도 몰라. 내가 치우는 모든 NULL 문자,하지만 당신은 인덱스 데모 테잎을 할 수 없을 것입니다 스피커 1 : 당신은 여전히​​ 필요합니다. 청중 : - 같은 방법으로 각각의 시간. 스피커 1 : 그래. 당신은 수 있도록 NULL 문자가 필요합니다 이 단어가 아니라면 당신은 알고있다. 당신은 당신이 원하는 무언가가 벤습니까? 확인을 클릭합니다. 좋아, 그래서 우리는거야 조금 더 갈 뒤에 기술적 인 세부 사항으로 시도하고 예를 통해 작동합니다. 좋아, 그럼이 같은 일이다. 연결리스트에서, 우리의 주요 반면 ? 종류의 집게 리아 내가 원하는 말은 무엇인가 - 빌딩 블록 같은 노드이었다. 시도에서, 우리는 또한 노드가 그러나 그것은 다르게 정의입니다. 그래서 우리는 몇 가지 부울이 그 단어 여부 사실을 나타냅니다 이 위치에 존재하고 우리는 이곳에 또는 오히려 약간의 배열을 이에 대한 포인터입니다 27 문자의 배열입니다. 그리고 이것은이,이 경우에 대한 것이다 27-- 나는 여러분 모두가 같은 확신 해요, 대기 알파벳 26 글자가있다. 왜 우리는 27해야합니까? 그래서에 따라 이 구현 방법, 이 PSET에서입니다 아포스트로피 허용. 그래서 왜 여분의 하나입니다. 또한 일부있을 것이다 경우 널 (NULL) 종료 중 하나로 포함되어 있습니다 가 될 수있어 문자, 그것은 그들이에 확인 방법 이 단어의 끝이 어떤지를 확인합니다. 당신이 관심이 있다면, 체크 아웃 study.cs50에 케빈의 비디오, 뿐만 아니라 위키 백과가로 이 좋은 자원. 그러나 우리는 종류를 통해 갈거야 당신이 시도를 통해 작업하는 방법의 당신이 하나를 쓰게. 그래서 우리는 여기에 슈퍼 간단한 하나가 그 (것)들에있는 단어 "박쥐"와 "줌"을 가지고있다. 그리고 우리가 여기서 보는 바와 같이, 여기이 작은 공간 우리 부울를 나타내는 예,이 단어 말했다. 그리고 이것은 우리가 문자의 배열, 오른쪽? 그래서 우리는 통과 예정 이 시도에 "박쥐"를 발견. 그래서 오른쪽 상단에서 시작? 그리고 우리는 B가에 해당하는 것을 알고 두 번째 인덱스, 두 번째 요소 이 배열에서, 및 b 때문에. 그래서 대략 번째. 그리고 OK,로 그 멋진 따르 말한다 다음 배열, 우리가 기억한다면 때문에, 이들의 각 아니다 실제로 요소가 포함되어 있습니다. 이러한 배열의 각각 오른쪽 포인터를 포함? 그것은 만들 수있는 중요한 차이점이다. 나는이 시도는 나중에 ... 것입니다 알고 처음에 얻을 정말 열심히, 그래서이 경우에도 두 번째 또는 세 번째 시간 그것은 종류 아직 어려운 겉으로의, 당신이 시계를 가면 약속 짧은 내일 다시, 아마 훨씬 더 많은 의미가 있습니다. 그것은 소화 많이 걸립니다. 나는 아직도 가끔 생각 같은 잠깐, 시도는 무엇인가? 이걸 어떻게 사용합니까? 그래서 우리는이 경우 B 조, 이는 두 번째 인덱스입니다. 우리가 있던 경우에, 말하자면, C 또는 d 또는 다른 편지, 우리는 색인이 다시 매핑 할 필요가 우리의 배열의 정보는 다음의 제품에 해당하는지. 그래서 우리는 rchar처럼 걸릴 단지 우리 이 0-25로 매핑하는 오프 뺍니다. 좋은 모두 어떻게 우리를 우리의 문자를이란? 확인을 클릭합니다. 그래서 우리는 두 번째 우리로 이동 그 참조, 예, NULL로하지 않습니다. 우리는이 다음 배열에 이동할 수 있습니다. 그래서 우리는 여기이 다음 배열로 이동합니다. 그리고 우리는 지금, OK,라고 우리 여기에 있는지 확인해야합니다. 이 null의 경우, 또는 그것을 않습니다 실제로 앞으로 이동? 그래서 실제로 이동 이 배열에 전달합니다. 그리고 우리는 OK, t는 우리의 마지막 문자, 말한다. 그래서 우리는 인덱스에있는 T로 이동합니다. 그리고 우리는 앞으로 이동 때문에 또 하나있다. 그리고이 사람은, 네, 기본적으로 그 말한다 이 단어가 있다고 말한다와 ... 당신이 따르는 경우에 그 경로, 당신은 도착했습니다 단어에서, 우리가 알고있는 "박쥐"입니다. 네? 청중 : 그 가지고하는 것이 표준이다 다음 인덱스 0으로 1의 종류가 또는 끝 부분에있는가? 스피커 1 호 우리가 다시 본다면 우리의 여기에 선언, 그것은 부울이다, 그래서 노드에서 자신의 요소입니다. 그래서 배열의 일부가 아니다. 쿨. 우리가 우리의 말을 마치고 그래서 우리는있어 이 배열에서, 우리는 무엇을 할 이 단어에 대한 검사를 할 수 있습니다. 그리고이 경우에는, 예 반환. 그래서 그 주에, 우리는 "동물원"을 알고 - "동물원"는 말씀입니다 인간으로 우리는 알고있다 맞죠? 그러나 여기 것이다 시도된다 아니, 아니다,라고. 그리고 그 말을 우리 때문에 여기 단어로 지정하지 않았습니다. 심지어 우리가 통과 할 수 있지만 이 배열에 이르기까지, 이 시도는, 아니, 그런 말을 동물원은 사전에없는 우리는하지 않았기 때문에 등을 지정. 그래서 한 가지 방법은 거저해야 할 일 아, 죄송합니다,이. 그래서이 경우, "동물원"아니다 단어지만 우리 시도이다. 하지만이 하나, 우리가하고 싶은 말은 "목욕은,"무슨 일이 단어를 소개합니다 우리가 through-- B, A, T를 수행합니다. 우리는이 배열에있어, 그리고 우리는 시간을 검색으로 이동합니다. 이 경우, 언제 시간에 포인터를 보면, 그것은 OK, NULL을 가리키는거야? 명시 적으로 않는 한 그래서 다른 배열을 가리키는, 당신은 가정의 모든 포인터 그 이 배열에 null로 가리키고있다. 이 경우 그래서, 시간이 가리키는 우리는 아무것도 할 수 없습니다 그래서 null로, 그래서 그것은 또한 반환 거짓, "목욕은"여기에 있지 않습니다. 그래서 지금 우리는 실제로있어 를 통해 갈 어떻게 우리가 실제로 말을 그게 "동물원"우리의 시도입니다. 우리는 어떻게 우리의 시도에 "동물원"을 삽입합니까? 우리가 시작 동일한 방법으로 그래서 우리의 연결리스트, 우리는 루트에서 시작합니다. 의심에서 시작하면 이러한 것들의 루트. 그리고 우리는, 확인, Z를 말할 것이다. Z이 존재하고,이하지. 그래서 당신로 이동하고 다음 배열, OK? 그리고 다음 하나에, 우리는 OK, O는 존재라고? 그것은 않습니다. 이 다시. 그리고 우리의 다음 하나, 우리는 말한 OK, "동물원"여기에 이​​미 존재합니다. 우리가해야 할 일은이 동일하게 설정되어 참으로,이 단어가있다. 당신은 모든 것을 따랐다 경우 그 시점 이전까지, 이 단어의 그래서 그냥 등로는 동일하게 설정. 네? 청중 : 그래서 그 수행 "바"는 단어는 것을 의미? 스피커 1 호 그래서이 경우, "바"우리는 얻을 것 여기에, 우리는이 단어를 말할 것이다 그것은 여전히​​가 없을 것이다. OK? 음 .....? 청중 : 당신이 한 번 그래서 단어 당신은 그 다음, 네 말 m로 이동이 포함됩니다? 스피커 1 : 그래서이 관련이있다 너의 ... 당신은이를로드하고 있습니다. 당신은 "동물원"이 단어 말한다. 당신은 check--에 갈 때 같은, 당신이 말하고 싶은 말, "동물원"이 사전에 존재 하는가? 당신은 "동물원"을 검색 할거야 다음은 단어인지 확인합니다. 당신은 절대 이동하지 못해 그 아니기 때문에 m에 이르기까지 당신은 무엇을 찾고 있습니다. 그래서 우리는 실제로 원한다면 이 시도에 "목욕"를 추가, 우리는 같은 일을 할 것입니다 우리가했던 것처럼 "동물원" 때 우리는 그것을 볼 것 제외 시도하고 시간에 도착, 그것은 존재하지 않습니다. 시도 그래서 당신이 생각할 수있는 연결리스트에 새로운 노드를 추가, 그래서 우리는 서로를 추가해야 그래서 같은 이러한 배열 중 하나. 그리고 우리는 단지 시간을 설정 우리가하는 일 이 가리키는이 배열의 요소입니다. 그리고 우리는 여기서 뭘할까요? true로이 같은 추가 때문에 단어입니다. 쿨. 나는 알고있다. 시도는하지 가장 흥미로운입니다. 날 믿어, 내가 알고있다. 그래서 한 가지 시도와 실현, 나는 그들이 매우 효율적이야 말했다. 그래서 우리는 그들이 본 적이 공간의 톤을 차지합니다. 그들은 종류의 혼동하고 있습니다. 그럼 왜 우리는 이제까지이를 사용해야합니까? 그들이이기 때문에 우리는이를 사용 매우 효율적입니다. 만약 당신이 찾는 경우에 따라서 단어까지 만입니다 단어의 길이에 의해 제한. 그래서 만약 당신이 찾고있는 길이 다섯이다 단어, 당신이 오직해야 할거야 OK, 대부분의 다섯 비교에서 사진을? 그래서 그것은 기본적으로 일정하게 만든다. 삽입 및 조회처럼 기본적으로 일정 시간이다. 만약 당신이 얻을 수 있다면 그래서 일정 시간에 뭔가, 즉 이보다 더 좋을 순 없다입니다. 당신은보다 더 얻을 수 없다 이러한 것들에 대한 일정 시간. 그래서 그 중 하나입니다 시도의 거대한 흑자. 그러나 많은 공간이다. 그래서 당신은 가지를 결정해야 무슨 일이 더 중요합니다. 그리고 오늘날의 컴퓨터에, 공간 시도가 걸릴 수 어쩌면 영향을주지 않습니다 당신이 그 많은,하지만 어쩌면 당신이 뭔가를 처리하고 즉, 훨씬, 훨씬 더 많은 일을 가지고 과 시도는 합리적이 아니다. 네? 청중 : 잠깐, 그래서 당신은 (26)가 하나 하나의 문자? 스피커 1 : 음 ...... 그래, 당신은 (26)이있다. 당신은 일부는 다음 단어 마커이며이 당신은 모든 일에서 26 포인터를 가지고있다. 그리고 그들은 가실 수 없습니다 .--있어 청중 : 모든 26 그들은 각각 26해야합니까? 스피커 1 : 네. 당신이 할 수 그리고는 이유 그것은 아주 빠른 속도로 확장을 참조하십시오. 좋아. 그래서 우리는 나무로받을거야하는 내가 좋아 쉽게 느낄 아마 것 좋은 작은 집행 유예 수 이 시도에서. 그래서 희망이 당신의 가장 전에 나무를 보았다. 꽤 마음에 들지 외부 사람, 어떤 I 누구나 알고하지 않습니다 최근 야외 갔다. 나는 애플이 이번 주말을 따기 갔다, 그리고 맙소사, 그것은 아름다웠다. 나는 잎을 몰랐다 그 꽤 볼 수 있었다. 그래서 그냥 나무, 오른쪽인가? 그것은 단지 일부 노드, 그리고 그것을 다른 노드의 무리를 가리 킵니다. 당신이 여기에서 보는 바와 같이,이입니다 반복되는 테마 가지. 노드 노드 가리키는 가지입니다 많은 데이터 구조의 본질. 그것은 단지 우리 방법에 따라 달라집니다 그들이 서로 가리 우리가 어떻게 통과 그들을 통해 어떻게 우리 그 결정 것들을 삽입 서로 다른 특성. 그래서 그냥 몇 가지 용어, 이는 내가 전에 사용했습니다. 그래서 루트는 맨 위에 무엇이든이다. 우리는 항상 시작하는 곳이다. 또한 머리로 생각할 수 있습니다. 그러나 나무를 위해, 우리는 경향이 루트로 참조. 하단들을 이곳에서 아무것도 아주, 아주 심연에서 고려 잎입니다. 그래서 함께 간다 전체 트리 일, 맞죠? 잎은 나무의 가장자리에있다. 그리고 우리는 또한 몇가 용어는 관계의 노드에 대해 이야기 서로. 그래서 우리는 부모가 자녀, 형제. 그래서이 경우,도 3은 5, 6 및 7의 부모. 그래서 부모는 무엇이든입니다 당신이있어 어떤 위에서 한 단계 그래서 그냥, 참조 가족 나무처럼. 바라 건데,이 모든 조금이다 비트 시도보다 더 직관적 인. 형제 자매가 그 어떤 있습니다 바로 같은 부모,? 그들은 여기에 같은 수준에있어. 그리고 나는이었다로 말, 어린이는있다 아래의 한 단계는 무엇입니다 문제가되는 노드에, OK? 쿨. 그래서 이진 트리. 누구든지 중 하나를 짐작 할 수 이진 트리의 특성? 청중 : 최대 두 잎. 스피커 1 : 맞아요. 그래서 두 잎의 최대. 그래서 전에이 하나, 우리는이 하나 있었다 즉, 세 있었지만 이진 트리 두 가지의 최대이 부모 당 어린이, 맞죠? 다른있다 흥미로운 특징. 사람은 알고 있습니까? 이진 트리. 그래서 이진 트리가 모든 것 엥에이 하나 sorted-- 아니다 하지만 정렬 된 이진 트리에, 오른쪽에있는 모든 부모보다 큰 왼쪽에있는 모든 부모보다 작습니다. 그리고 그 퀴즈왔다 질문하기 전에, 그래서 좋은 알고. 그래서 우리는이를 정의하는 방법, 다시, 우리는 다른 노드가 있습니다. 이것은 것과 매우 비슷합니다? 두 곱으로 청중 : 연결리스트 스피커 1 : 이중 연결리스트, 오른쪽? 그래서 우리는 이것을 대체 할 경우 이전 및 다음으로, 이 이중 연결리스트가 될 것입니다. 그러나이 경우에, 우리는 실제로 좌 · 우 및 그것 뿐이다 있습니다. 그렇지 않으면, 똑같은이다. 우리는 여전히 요소가 당신이 찾고있는 당신은 단지 두 개의 포인터를 가지고 무엇에가는 것은 다음입니다. 그래, 그래서 이진 검색 트리. 우리는에, 모든 것을 통지하는 경우 바로 여기에 큰 than--입니다 즉시 또는 모든 여기에서 오른쪽 모든 것이보다 크다 여기보다 작습니다. 그래서 우리는을 통해 검색 할 수 있다면, 그것을 이진 검색에 매우 가깝게 보일 것 여기, 바로? 대신 찾고 제외 반 배열에서, 우리는 단지 하나 왼쪽에서 찾고 있습니다 사이드 또는 트리의 오른쪽. 조금 간단하게 얻을 수 있도록, 나는 생각한다. 루트가 NULL 인 경우에 따라서, 분명히 그냥 거짓이다. 그것은이 있다면 그리고, 분명히 그것은 사실입니다. 그 이하의 경우에, 우리는 왼쪽을 검색 할 수 있습니다. 그것보다 더 있다면, 우리는 권리를 검색 할 수 있습니다. 그것은 정확히 이진 검색처럼 다만 서로 다른 데이터 구조 것을 우리가 사용하고 있습니다. 배열 대신, 그냥 이진 트리입니다. OK, 스택. 또한, 우리처럼 보인다 약간의 시간을 가질 수 있습니다. 우리가 할 경우에, 나는 갈 행복 해요 이 중 다시. 좋아, 그럼 스택. 사람은 무엇을 기억 하는가 stacks-- 스택의 특성? OK, 우리의 대부분, 그래서 나는 생각한다, 식당에서 식사를 halls-- 우리가 좋아하지 않을 수만큼. 그러나 분명히, 당신은 스택 생각할 수 말 그대로 그냥 트레이의 스택으로 또는 사물의 스택. 그리고 어떤 일이 중요합니다 실현하기 위해 그것의 것입니다 특성을 탔던 우리가 고요 지나가는 부르는 LIFO이다. 사람은 무엇의 약자인지 알고 있나요? 음 .....? 관객 : 첫째, 아웃 지속됩니다. 스피커 1 : 오른쪽, 첫 번째, 아웃 지속됩니다. 우리가 알고있는 경우에 따라서, 우리는 물건을 적재하는 경우 최대, 가장 쉬운 일이 마지막으로 .. 잡아합니다 어쩌면 유일한 것은 우리가 잡을 수 있습니다 우리의 스택이 큰 enough-- 경우 해제 그 위에 요소이다. 그래서 어떤이에 넣어 우리가 여기에 참조로 last--, 어떤 밀렸다 대부분에 recently--입니다 첫 번째가 될 것 우리가 떨어져 팝업 것은, OK? 그래서 우리가 여기에있는 것은 다른 형식 정의 구조체. 이것은 정말 그냥 좋아한다 데이터 구조 과정을 충돌, 그래서 너희들 던져 많이있다. 나는 알고있다. 그래서 또 다른 구조체. 구조에 대한 야호. 그리고이 경우에는, 포인터의 일부 어떤 능력을 가지고 배열. 그래서 이것은 우리의 스택을 나타냅니다 여기에, 우리의 실제 배열과 같은 즉, 우리의 요소를 잡고있다. 그리고 여기에 우리는 몇 가지 크기가있다. 그리고 일반적으로, 당신은 유지하려는 당신의 스택이 얼마나 큰 추적 그것은 수 있도록 무슨 일 때문에 당신이 크기를 알고있는 경우에 할 일은, 당신이 말을 할 수 있습니다, 좋아, 내가 용량 무엇입니까? 나는 더 많은 것을 추가 할 수 있습니까? 그리고 그것은 또한 당신을 알려줍니다 어디 스택의 상단 그래서 당신은 무엇을 알고 실제로 이륙 할 수 있습니다. 그리고 그 사실에 무슨 여기에 좀 더 명확하게. 그래서 푸시, 한 가지를 들어, 경우 푸시를 구현하기 위해 이제까지했다, 그러니까 내 말대로, 당신을 스택은 권리, 제한된 크기가? 우리의 배열은 어떤 능력을 가지고 있었다. 그것은 배열입니다. 그것은 고정 된 크기, 그래서 우리는 필요 우리는 더 참을​​ 수 없어하고 있는지 확인 우리보다 우리의 배열에 실제로위한 공간이있다. 그래서 때 푸시를 만드는 기능, 확인, 말입니다 할 첫 번째 일은, 내 스택의 공간을해야합니까? 내가하지 않으면, 미안 때문에 나는 당신의 요소를 저장할 수 없습니다. 내가 할 경우에, 당신은 저장할 그것은 스택의 상단 오른쪽? 그리고 이것은 우리가 가지고있는 이유 우리의 크기를 추적합니다. 우리는 우리의 크기를 추적하지 않는 경우, 우리는 그것을 어디에 둘지 모른다. 우리는 얼마나 많은 일을 모르는 이미 우리의 배열에 있습니다. 분명히 같이 가지 방법이 있습니다 어쩌면 당신은 그것을 할 수 있습니다. 당신은 NULL로 모든 것을 초기화 할 수 다음 최신 NULL을 확인, 하지만 훨씬 쉽게 일이 그냥 OK, 크기를 추적, 대답. 내가 알고있는 것처럼 네 개의 요소가 내 배열, 다음 일은 그렇게 우리에 넣어, 우리는있어 인덱스 4에 저장하는 것이다. 그리고, 물론, 이것은을 의미 당신은 성공적으로 일을 추진했습니다 당신의 스택 위에, 당신 크기를 늘리려면 당신이 알 수 있도록 그렇게 어디에 당신은 더 많은 일을 밀어 수 있습니다. 우리가 팝업하려고한다면 스택에서 뭔가, 첫 번째 일이 될 수 있습니다 무엇 우리는 확인하려는? 당신은 걸릴려고 당신의 스택에서 뭔가. 당신은 반드시 거기에 있습니까 당신의 스택에 뭔가? 아니오. 그래서 우리는 확인 할 수 있습니다? 청중 : [들리지]. 스피커 1 : 크기를 확인? 크기. 그래서 우리가 있는지 확인하려면 우리의 크기는 OK, 0보다 크다? 그것이 경우에, 우리는 감소 할 0에 의해 우리의 크기와 그를 돌려줍니다. 왜? 처음에 우리는 있었다 밀어, 우리는 그것을 밀어 크기와 다음 업데이트 크기 위에. 이 경우, 우리는 크기를 감소시키는 것 다음을 뽑고, 그것을 이륙 우리의 배열. 왜 우리는 그렇게 할 수 있습니까? 그래서 난 내 스택에 한 가지가 있다면, 그 시점에서 나의 크기 있을까요? 1. 어디 요소 1은 저장됩니까? 무엇 인덱스에? 청중 : 0. 스피커 1 : 0. 이 경우 그래서, 우리 항상 싶은건 대신 반환 크기 - 1, 우리 때문에 우리의 요소가 있음을 알 1 이하로 저장 될 것 우리의 크기가 무엇이든,이 그냥 처리한다. 그것은 약간 더 우아한 방법입니다. 그리고 우리는 단지 우리를 감소 다음 크기와 크기를 반환합니다. 음 .....? 청중 : 나는, 단지 일반적으로 추측 이유는이 데이터 구조는 것 도움이 될? 스피커 1 : 그것은 당신의 상황에 따라 달라집니다. 이론의 일부 그래서, 확인을 먹게됐다 작업하는 경우, 유익한 존재하는 경우 나 보자 그 밖에보다 더 유리하다 CS의. 스택, 어떤 시간이 필요 뭔가를 추적하는 그 가장 최근에 추가 된 경우입니다 당신은 스택을 사용할 것입니다. 그리고 나는 좋은 생각할 수 없다 지금 그 예. 그러나 때마다 가장 최근의를 일이 가장 중요하다 그 때 스택의 유용 할 것입니다. 나는 경우에 생각하려고 해요 이것에 대한 좋은 일이있다. 나는 다음에 좋은 예를 생각한다면 20 분, 나는 확실히 당신에게 말할 것이다. 그러나 전반적으로, 거기에 아무것도 경우, 같은 나는 대부분의 경우 가장 최근에 말했다 즉, 가장 중요한 것입니다 여기서 스택은 놀이로 제공됩니다. 큐 반면 반대 가지입니다. 그리고 모든 작은 개. 바로이 위대한 아닌가요? 나는 내가해야 같은 느낌 단지 토끼 영상이 권리의 중간에 너희들 섹션 이 강렬한 부분이기 때문이다. 그래서 큐. 기본적으로 큐는 라인과 같다. 너희들 내가이 매일 확인 사용 해요, 우리의 식당에서 좋아한다. 그래서 우리는에 갈 필요가 그리고 난, 우리의 트레이를 얻을 수 반드시이 줄을 기다려야 슬쩍 또는 음식을 얻을 수 있습니다. 여기 차분 그래서 이 FIFO 것입니다. 그래서 LIFO 먼저, 마지막 인 경우 아웃, FIFO는 먼저 서비스에있다. 그래서 이것은 당신이 어디에 넣어 뭐든 처음에 가장 중요하다. 당신이 기다리는 경우에 따라서 한테 들었 냐에서 당신을 수 당신이 가면 상상 새로운 아이폰을 가서 그리고 스택은 어디에 라인의 마지막 사람이 먼저있어 사람들은 서로를 죽일 것입니다. 그래서 FIFO, 우리 모두 아주 잘 알고 여기에 현실 세계와, 그리고 모든 사실과 관련이있다 종류의이 모든 라인을 다시 과 구조를 대기. 스택 반면 그래서, 우리는 푸시와 팝을 가지고있다. 큐, 우리는이 대기열 및 대기열에서 제외. 그래서 대기열은 기본적으로 의미 뒷면에 넣어, 및 대기열에서 제외 수단을 가지고 전면에서 끕니다. 그래서 우리의 데이타 구조는 조금 더 복잡합니다. 우리는 추적 할 두 번째 문제가있다. 이, 머리가없는 그래서 오른쪽 정확하게 스택입니까? 이는 스택과 동일한 구조이다. 다른 유일한 것은 지금 우리입니다 당신이 어떻게 생각이 머리를 가지고 를 추적 할거야? 청중 : 첫 번째. 스피커 1 : 오른쪽, 우리는에 넣어 먼저. 우리의 큐의 선두. 누구든지 첫 줄에 있습니다. 좋아, 그래서 우리는 대기열을합니다. 다시, 임의의와 이러한 데이터 구조, 우리가 배열을 취급하고 있기 때문에, 우리는 우리가 공간이 있는지 확인해야합니다. 이 날 이야기 같은 종류의 것입니다 너희들, 당신이 파일을 열 경우, 당신은 널 (null)를 확인해야합니다. 이 스택에 상관 그리고 큐, 당신은 필요 우리가이기 때문에 공간이 있는지 확인합니다 고정 된 크기의 배열을 다루는, 우리는 5까지 이곳에 0, 1을 참조로. 그래서 우리는이 경우에 무엇을 체크입니다 우리는 여전히 공간이 있는지 확인합니다. 우리의 크기는 용량보다 적은 있습니까? 그렇다면, 우리는 그것을 저장해야 우리는 우리의 크기를 업데이트하고 꼬리. 그래서 꼬리는이 경우에 무엇을 할 수 있는가? 그것은 명시 적으로 기입 아니에요. 우리는 어떻게 그것을 저장할 것인가? 꼬리는 어떤 것입니까? 그래서이 예제를 걸어 보자. 그래서이 6 사이즈의 배열이 오른쪽인가? 그리고 우리는 지금, 우리의 크기가 5있다. 우리가 그것을 넣어 때, 돼가 오른쪽 다섯 번째 인덱스로 이동합니다? 그래서 꼬리에 저장합니다. 꼬리를 작성하는 또 다른 방법은가 .. 크기의 인덱스에서 우리의 배열은, 잘 될? 이 크기는 5입니다. 다음 것은 5로 갈 것입니다. 쿨? 확인을 클릭합니다. 이것은 약간 더 복잡해진다 우리는 머리를 엉망으로 시작할 때. 네? 청중 : 그 뜻이 우리 배열을 선언 한 것이라고 다섯 가지 요소 긴 및 우리는에 추가하고? 스피커 1 호 그래서이 경우에는,이 스택이다. 이 선언 될 것이다 6 사이즈의 배열로서. 그리고이 경우에, 우리 하나의 공간 왼쪽에 있습니다. 좋아, 그럼 한 가지이에 경우, 우리의 머리가 0 인 경우, 우리는 단지 크기에 추가 할 수 있습니다. 그러나 조금 까다를 가져옵니다 실제로 때문에, 그들은 슬라이드가없는 이를 위해, 그래서 나는거야 이 아니기 때문에 하나를 그립니다 아주 간단 당신이 한 번 물건들을 치우는 시작합니다. 스택 반면, 그래서 당신은 오직이 크기가 무엇인지에 대해 걱정 시에 무언가를 추가하고, 큐와 함께 당신은 또한 확인해야 머리가 차지되어 있는지, 때문에 큐에 대한 좋은 점 입니다 당신이 용량으로하지 않으면, 당신은 실제로는 줄 바꿈 할 수 있습니다. 좋아, 그럼 한 건 말인데 ... 오, 이 끔찍한 분필입니다. 고려해야 할 한 가지 경우입니다. 우리는 단지 다섯을 다하겠습니다. OK, 그래서 우리는에 갈거야 머리가 여기에있다 말한다. 이는 0, 1, 2, 3, 4이다. 머리가, 그리고 그들의 일을하시기 바랍니다. 그리고 우리는 오른쪽에 뭔가를 추가하려면? 그래서 일이 우리가 할 필요가 알은 헤드가 항상 있다는 이 방법을 이동 가서 다음 루프 다시 주위에, OK? 그래서이 큐는 오른쪽 공간이? 그것은 처음에 공간이 이것의 대향 가지. 그래서 우리가해야 할 일을 우리는 꼬리를 계산해야합니다. 당신은 알고 경우 머리를 이동하지 않은, 꼬리 에서 당신의 배열 크기의 인덱스입니다. 그러나 현실에서, 당신은 큐를 사용하는 경우, 당신의 머리는 아마 업데이트 중입니다. 그래서 당신이해야 할 것입니다 실제로 꼬리를 계산합니다. 그래서 우리가 할 것은이 공식은 여기, 당신을 할거야하는 들에 대해 생각하고, 우리는 그것에 대해 이야기 할 것입니다. 따라서이 용량이다. 그래서이 실제로 것 당신이 그것을 할 수있는 방법을 제공합니다. 이 때문에 경우에, 무엇을? 우리의 머리는 1, 우리의 크기는 4입니다. 우리는 5 그 모드 (mod) 경우, 우리는 0을 얻을, 이는 어디 우리가 입력해야합니다. 그럼 다음의 경우에, 우리는이 작업을 수행하는 경우, 우리는 좋아, 뭔가를 큐에서 제거하자 말한다. 우리는이를 큐에서 제거. 우리는 바로이 요소를 꺼내? 그리고 지금 우리의 머리는, 여기 가리키는 우리는 다른 일에 추가 할. 이것은 기본적이며 다시 우리 라인의 오른쪽? 큐는 배열 감싸는 할 수 있습니다. 즉, 주된 차이점 중 하나입니다. 스택, 당신은이 작업을 수행 할 수 없습니다. 큐, 당신은 할 수 모든 문제 때문에 당신이 알고있는 것이 무엇인지 가장 최근에 추가되었습니다. 모든 추가 될 것입니다 때문에 이 좌측 방향,이 경우, 다음 줄 바꿈을 수행 할 수 있습니다 새로운 요소에 넣어 계속 배열의 전면에 정말 아니기 때문에 이상 배열 전면. 당신의 시작을 생각할 수 당신의 머리가 실제로 어디에 배열입니다. 그래서이 공식은 어떻게 당신은 당신의 꼬리를 계산합니다. 그 의미가 있습니까? 확인을 클릭합니다. OK, 대기열에서 제외하고 너희들은 10 분을 나에게 명확히 질문을합니다 내가 미친 알고 있기 때문에 당신은 할 수 있습니다. 같은 전부다 ... 너무 좋아요 너희들이 발견 있을지 몰라 하지만 CS는 모든 패턴에 관한 것입니다. 상황이 꽤 많이입니다 단지 작은 비틀기와, 같은. 여기 그래서 같은 일. 우리는 만약 우리가 실제로 볼 수 확인해야 바로 우리 큐에 뭔가를 가지고? OK, 0보다 우리의 크기가 큰 경우, 말? 쿨. 우리가 할 경우, 우리는 우리의 머리를 이동하는 난 그냥 여기에 입증하는 것입니다. 우리는 하나의 이상으로 우리의 머리를 업데이트합니다. 그리고 우리는 우리의 감소 크기와 요소를 반환합니다. 더 많은 콘크리트가 study.cs50.net에 코드, 나는 매우가는 것이 좋습니다 당신이 시간이 있다면 그것을 통해, 심지어 그냥 의사 코드의 경우. 그리고 당신들을 통해 이야기하려는 경우 나 하나 하나에 함께하겠습니다하시기 바랍니다 알고있다. 나는 행복 할 것입니다. 데이터 구조, 만약 당신이 CS (124)을, 당신은거야 데이터 구조가 매우 얻을 알고 재미 있고 이것은 단지 시작했다. 그래서 나는 그것이 어려운 알고있다. 괜찮아요. 우리는 투쟁. 나는 아직도. 그래서 그것에 대해 너무 많이 걱정하지 마십시오. 그러나 그것은 기본적으로 당신입니다 데이터 구조 과정을 충돌. 나는 많이 알고있다. 거기에 아무것도 그 우리 또 다시 가고 싶은? 우리는을 통해 얘기하고 싶지 없나? 네? 청중 : 그 예를 들어, 그래서 새 꼬리는 그 이상 0에? 스피커 1 : 네. 청중 : OK. 그래서 그 다음을 통해 진행 당신이 1 더하기 4에 올이 것 스피커 1 : 그래서 당신은 말을했다 우리가 가고 싶어 할 때 다시이 작업을 수행? 청중 : 네. 당신 내밀면 파악되면 이에 어디 있는지 그의에서 꼬리를 계산? 스피커 1 : 그래서 꼬리 나는이 변경 받이었다. 그래서 여기에이 예에서,이이었다 우리가 확인,보고있는 배열? 그래서 우리는 1, 2, 3, 4 가지가있다. 그래서 우리는 우리의 머리에서 1과 동일해야 이 점은, 우리의 크기는 4와 동일 이 시점에서, 맞죠? 여러분 모두가 그런 경우 동의? 그래서 우리는 머리 플러스 크기를 수행하는 우리에게 5를 제공하고, 우리는 5 모드 (mod). 우리는 0 인 것을 우리에게 알려줍니다, 0을 얻을 여기서 우리가 공간이 우리의 꼬리이다. 청중 : 모자는 무엇입니까? 스피커 1 : 용량. 미안 해요. 그래서 배열의 크기입니다. 네? 청중 : [들리지] 전 우리는 요소를 반환? 스피커 1 : 그래서 우리는 이동 머리 또는 순간을 반환? 우리가 하나를 이동한다면, 크기를 감소? 기다려. 나는 확실히 다른를 잊어 버렸습니다. 신경 쓰지 마. 또 다른 공식은 없습니다. 그래, 당신은 반환 할 것 머리 한 다음 다시 이동합니다. 청중 : OK,이 때문에시 점, 머리는, 0에 있었다 그리고 당신은 반환 할 인덱스 0 다음 머리 1 - 1? 스피커 1 : 맞아요. 나는 다른 있다고 생각 이 같은의 공식 종류. I는 다음과 같이 상단에 내 머리를 가지고 있지 않습니다 나는 당신에게 잘못을주고 싶지 않습니다. 하지만 그것은 완벽하게 유효한 것 같아요 말하자면, OK,이 element--를 저장하는 어떤 머리의 요소는 감소는 ... 당신의 크기는 당신의 머리를 통해 이동 및 반환 즉 어떤 요소이다. 즉 완벽하게 유효합니다. 확인을 클릭합니다. 이가 아닌 것 같아 그게 ...처럼 당신은 아니에요 여기서 걸어 갈 같은, 그래, 내가 시도를 알고있다. 나는 모든 것을 얻었다. 그건 괜찮아요. 나는 약속드립니다. 그러나 데이터 구조는 무엇인가됩니다 그것은 많은 시간에 익숙해 걸립니다. 가장 어려운 아마 하나 일, 나는 과정에서, 생각합니다. 그래서 확실히한다 반복과 먹어 본 난을 찾고 정말 연결리스트를 몰랐다 나는 그들과 함께 너무 많이했다 때까지, 그 같은 방식으로 나는하지 않았다 정말 포인터를 이해 내가 먹어 본 때까지 두 그것을 가르 칠 년은 내 자신의 Pset을한다. 그것은 반복하고 시간이 많이 걸린다. 그리고 결국, 그것은 종류의를 클릭합니다. 그러나 그 사이에, 당신은 어떤이있는 경우 높은 수준의 이해의 어떤 이들은 자신의 장점을 수행 무엇을 어떤 cons-- 우리가 정말 강조하는 경향이있다, 특히 인트로 과정에서. 마찬가지로, 우리는 왜 사용합니다 배열을 시도? 마찬가지로, 긍정적 인은 무엇인가 그 각각의 네거티브? 그리고 트레이드 오프를 이해 이들 구조들 각각 사이 지금은 훨씬 더 중요한 것입니다. 미친있을 수 있습니다 의 질문 또는 두 개의 푸시를 구현하도록 요구하는 것 또는 팝업 또는 대기열 및 대기열에서 제외를 구현한다. 그러나 대부분의 경우, 그 데 높은 수준의 이해와 더 직관적 인 이해는된다 사실보다 더 중요 이를 구현할 수있는. 정말 멋진 것 당신의 모든 경우 나가서 시도를 구현 갈 수있다, 하지만 우리는 반드시이 아니다 이해 지금 가장 합리적인 것. 그러나 당신은 당신이 원하는 경우에, 당신의 pset에서 할 수 있습니다 에, 다음 연습을 얻을 것이다, 그리고 아마 당신은거야 정말 이해합니다. 네? 청중 : 사람이 확인되는 있도록 우리는 PSET에서 사용하는 의미? 나는 그들 중 하나를 사용해야합니까? 스피커 1 : 네. 그럼 당신은 선택의 여지가. 내가, 우리가 할 수있는이 경우 추측 PSET 조금 이야기 나는이 통과했기 때문이다. 당신의 PSET에 그래서, 당신은 당신이 시도 또는 해시 테이블의 선택. 어떤 사람들은 시도 할 것이다 와, 꽃 필터를 사용하여 하지만 사람들은 기술적으로 정확하지 않습니다. 때문에 확률 적 성격의, 그들은 때로는 잘못된 반응을 제공합니다. 그들은 비록에 근사하고 있습니다. 고보고 추천 그들에 적어도. 그러나 당신은 당신의 선택의 여지가 해시 테이블과 시도 사이. 그리고 그 곳이 될 것 당신은 당신의 사전에로드합니다. 그리고 당신은 선택해야합니다 하여 해시 함수 당신은 얼마나 많은 선택해야합니다 당신이 양동이, 그것은 다릅니다. 당신이 더 많은 버킷이있는 경우처럼, 어쩌면 더 빨리 실행됩니다. 하지만 어쩌면 당신은 낭비하는거야 공간을 많이하지만 그런 식으로. 당신은 그것을 파악해야합니다. 음 .....? 청중 : 당신은 그 전에 말했다 우리는 다른 해시 함수를 사용하여, 우리는 할 필요가 없습니다 해시 함수를 생성? 스피커 1 : 오른쪽, 예. 그래서 말 그대로 해시 함수, 구글과 같은 "해시 함수" 그리고 멋진 사람을 찾습니다. 당신은 구축 할 것으로 예상되지 않습니다 자신의 해시 함수. 사람들은 자신의 지출 이러한 것들에 대한 논문. 그래서 자신의 건물에 대해 걱정하지 마십시오. 시작하는 하나의 온라인을 찾습니다. 그들 중 일부는 당신에있다 약간의 조작 수 있도록해야합니다 반환 형식이 일치 그리고 이것 저것, 처음에 그렇게, 내가 뭔가를 사용하는 것이 좋습니다 것입니다 정말 쉽게 어쩌면 단지 첫 글자에 해시. 그리고 그 작업이 있으면, 냉각기 해시 함수를 통합. 음 .....? 청중 : 노력할 것이라고하는 일 또는 효율적인하지만,이었다고 나할까요 그냥 열심히 스피커 1 : 그래서 시도, 나는 생각 구현하기가 직관적으로 어렵다 하지만 매우 빠릅니다. 그러나, 더 많은 공간을 차지합니다. 다시 말하지만, 당신은 이들 모두를 최적화 할 수 있습니다 다른 방법과 방법이 있습니다 난 ... 청중 : 우리는 어떻게이에 등급을 매긴다? 그것은 문제가 .. 않습니다 스피커 1 : 그래서 당신은 정상적인 방법으로 등급 화하고 있습니다. 당신은 디자인에 등급이 될 것입니다. 그렇다면 당신이 방법, 당신이 원하는 그것이 될 수있는이 같은 우아 확인 및 효율적인 것이 될 수있다. 하지만 당신은 시도 또는 해시를 선택하는 경우 테이블, 한 작동으로, 우리는 그와 행복. 당신이 뭔가를 사용하는 경우 그리고 그 해시 첫 글자, 즉, 괜찮아요 같은 어쩌면 디자인이 많다는있다. 우리는 또한 도달하고 이 semester-- 포인트 나도 몰라 당신 경우 당신이 있다면 noticed--들 PSET 등급은 약간 감소 때문에 디자인과 이것 저것의, 그것은 완벽하게 괜찮아요. 이 점에 점점 어디를 프로그램은 더 복잡지고있다. 더 많은 장소가있다 당신은에 향상시킬 수 있습니다. 그래서 완벽하게 정상입니다. 그것은 당신이 걸 아니다 당신의 pset에 나쁜 일을. 그것은 단지 우리는 지금 당신을 더 열심히 당하고있다. 그래서 모든 사람이 그것을 느끼고. 난 그냥 모든 psets를 등급 화. 나는 모두가 그것을 느끼고 알고있다. 그래서 그것에 대해 걱정하지 마십시오. 그리고 당신은에 대한 질문이있는 경우 이전의 Pset 또는 개선 할 수있는 방법, 나는 시도하고 특정 주석 장소,하지만 때로는 늦었 나는 피곤. 다른 일이있다 약 데이터 구조? 난 너희들이 정말하지 않습니다 확신 해요 더 이상 그들에 대해 얘기하고 싶어, 가있는 경우에, 나는 행복 해요 아무것도뿐만 아니라, 그들을 이동 강연이 과거 주 또는 마지막 주. 나는 그래서, 지난 주 모든 리뷰 있었는지 우리는 몇 가지 검토를 건너 뛸 수도 있습니다 강의에서. 내가 대답 할 수있는 다른 질문? 좋아, 좋아. 그럼, 너희들은 15 분 일찍 나가. 나는이 적어도 반 도움이되었습니다 바랍니다 나는 다음 주에 너희들을 볼 수 있습니다, 또는 목요일 근무 시간. 간식이 요청입니다 다음 주, 그것은 것입니다? 오늘 사탕을 잊었 때문입니다. 그리고 마지막 사탕을 가져 주이지만, 콜럼버스의 날이었다 그래서 육명 같이 있었다 사람 자신에게 사탕의 네 개의 가방을 가지고 있었다. 나는 육각형을 가져올 수 당신이 좋아 다시합니다. 육각형? OK, 좋은 소리. , 좋은 하루들 되세요.