스피커 1 : 모든 오른쪽, 그래서 우리는 다시 수 있습니다. CS50에 오신 것을 환영합니다. 이것은 일주일 내내의 끝입니다. 그래서 지난 시간을 기억, 우리는 시작 조금 더 정교한보고 데이터 구조. 지금까지 있기 때문에, 모두 우리가 정말 있었다 우리의 처분이, 배열했다. 그러나 우리는 배열을 무시하지 않기 전에 모든 흥미있는 참으로 사실 중 일부는 무엇입니까합니다 이 간단한 데이터 플러스 구조 지금까지? 그것은 잘은 무엇입니까? 지금까지 우리가 본 것처럼? 당신은 무엇을 가지고 있습니까? 아무것도. 학생 : [들림]. 스피커 1 : 저게 뭐죠? 학생 : [들림]. 스피커 1 : 고정 크기입니다. 자, 그럼 왜 크기가 고정 그래도 좋은가? 학생 : [들림]. 스피커 1 : OK, 그래서에 효율적 당신을 할당 할 수 있다는 의미 공간의 고정 된 양, 희망 정확하게으로 많이 공간을 당신이 원하는대로. 그래서 절대적으로 플러스가 될 수 있습니다. 또 다른 배열해서 측면은 무엇입니까? 그래? 학생 : [들림]. 스피커 1 : 모든 - 네? 학생 : [들림]. 스피커 1 : 메모리에있는 모든 상자 또는 서로 옆에. 그리고 그 도움이된다 - 왜? 그것은 매우 사실입니다. 하지만 어떻게 우리가 진실을 악용 할 수 있습니까? 학생 : [들림]. 스피커 1 : 맞아요, 우리가 추적 할 수의 모든 것이 알아서 곳 하나, 즉 주소의 주소 메모리의 청크의 첫 번째 바이트. 또는 문자열의 경우, 첫 번째의 주소 해당 문자열에있는 문자. 거기에서, 우리는 찾을 수 있습니다 문자열의 끝. 우리는 두 번째 요소를 찾을 수 있습니다 세 번째 요소, 등등. 그리고 그 설명이 너무 멋진 방법 기능은 배열이 우리에게주는 것입니다 무작위 액세스 할 수 있습니다. 그냥 대괄호를 사용하여 표기법과 숫자, 당신은로 이동할 수 있습니다 배열의 특정 요소 일정 시간, 큰 O에 하나 말하자면. 하지만 몇 가지 단점이있었습니다. 배열은 매우 쉽게 무엇을하지? 그것은 잘 게 아니에요? 학생 : [들림]. 스피커 1 : 저게 뭐죠? 학생 : [들림]. 스피커 1 : 크기에 확장. 배열의 단점이 될 수 있도록 무엇의 정확히 반대 그나입니다. 그래서 단점 중 하나는 그것은 고정 된 크기의합니다. 그래서 당신은 정말 성장을 할 수 없습니다. 당신의 큰 덩어리를 재 할당 할 수 기억하고 이전 요소를 이동 새 배열. 에 대해 다음 무료 이전 배열, 예, malloc을 또는 유사한을 사용하여 realloc을 호출 기능을하는 재 할당 메모리. realloc과는 옆으로, 당신을 제공하기 위해 시도 배열에 다음의 메모리 당신은 이미이 있는지 확인하십시오. 그러나 물건을 움직일 수 있습니다 모두 주위에. 그러나 짧은, 맞아, 비싸? 때문에 당신의 메모리 청크가있는 경우 이 크기는하지만, 당신은 정말 하나를 원하는 이 크기의, 당신은 유지하려는 원래의 요소는, 당신이 대략 선형 시간 복사 프로세스 그에서 일어날 필요 새로운 구 배열입니다. 그리고 현실은 운영 체제를 요구하고있다 또 다시 시스템 다시 메모리의 큰 덩어리를 시작할 수 있습니다에 대한 뿐만 아니라 당신에게 약간의 시간을 요할 수 있습니다. 그래서 축복과 저주의 , 사실을 위장하는 이러한 배열 고정 된 크기입니다. 그러나 우리는 대신에 무언가를 소개하는 경우 이런 식으로, 어떤 우리가 링크라는 목록, 우리는 몇 가지 그나를 얻을 몇 여기서 단점뿐만 아니라. 연결리스트는 단순히 데이터 그래서 구조는 다음에 C 구조체의 구성 구조체, 리콜, 단지 경우, 하나 이상의 특정의 컨테이너 변수의 종류. 이 경우, 어떻게 데이터 유형을 구조체의 내부로 나타나는 마지막으로 우리는 노드라고? 이 사각형의 각 노드입니다. 그리고 작은 사각형의 각 그것의 내부 데이터 형식입니다. 우리는 어떤 종류의 말 했는가 그들은 월요일에 있었다? 그래? 학생 : [들림]. 스피커 1 : 변수의 포인터, 또는 더 구체적으로, 중간, n에, 그리고 하단의 포인터. 이들의 모두에서 32 비트 될 일이 이 CS50 같은 컴퓨터에서 최소 기구, 그리고 그들이있어 너무 크기가 똑같이 그려. 그래서 포인터를 사용하는 분명히에 대한 생각? 배열이있을 때 왜 지금이 화살표를 추가 너무 친절하고 깨끗하고 간단하게? 포인터가 무엇을하고있다 우리 다음 각 노드에서? 학생 : [들림]. SPEAKER 1 : 맞아요. 여기서 당신을 말하고 다음 중 하나입니다. 그래서 일종의의 비유를 사용 일종의 스레드를 사용하여 함께 이러한 노드에 실을 꿰다. 그리고 그것은 우리가하고있는 정확하게 무엇을 포인터 때문에 이러한 각 메모리 덩어리가 될 수도 있고 그렇지 않을 수도 있습니다 또는 연속 다시 다시 다시하기 RAM의 내부에 있기 때문에 때마다 malloc에​​ 말을 전화 나에게 충분히 제공 새 노드에 대한 바이트, 그것은 수도 여기 아니면 여기에있을 수도 있습니다. 그것은 여기에있을 수 있습니다. 그것은 여기에있을 수 있습니다. 당신은 모르겠어요. 하지만의 주소에 포인터를 사용 이러한 노드, 당신은 스티치 그 수 함께 시각적으로 보이는 방법 이러한 일들이 경우에도 목록처럼 모든 하나를 통해 확산 당신의 두 RAM 당신의 사기가바이트 자신의 컴퓨터의 내부입니다. , 그 후에, 단점은 너무 연결리스트는 무엇입니까? 우리가있어 가격은 무엇입니까 분명히 지불? 학생 : [들림]. 스피커 1 : 더 많은 공간, 오른쪽? 우리는이 경우에, 양을 두 배로 한 공간을 우리는 사라했기 때문에 각 각 노드에 대한 32 비트에서 INT, 이제 우리는 64 비트를 가지고 있기 때문에 뿐만 아니라 포인터 주변을 유지합니다. 당신은 더 많은 효율성을 얻을 귀하의 구조체 경우 이 간단한 것보다 크다. 당신은 실제로 내부에 학생이있는 경우 어느 문자열의 부부입니다 이름과 집, 어쩌면 ID 번호, 모두 어쩌면 다른 분야. 당신은 충분히 큰 구조체 나있는 경우에는, 그리고 아마 포인터의 비용​​은 아니 그렇게 큰 거래. 이것은에서 코너 케이스의 비트 우리는 간단한 원시를 저장하는 연결리스트의 내부입니다. 그러나 중요한 점은 동일합니다. 당신은 확실히 더 지출하고 메모리,하지만 당신은 있어요 유연성을 제공합니다. 지금은 요소를 추가하려는 경우 때문에, 이 목록의 시작 부분에, 나는 새로운 노드를 할당해야합니다. 난 그냥 사람들을 업데이트해야합니다 바로 이동하여 어떻게 든 화살 주변에 몇몇 포인터. 나는에 무언가를 삽입하려면 목록의 중간에, 나는 필요 없어 우리가 그랬던 것처럼 옆 사람을 밀어 자원 봉사자와 함께 주 '지난 사람 배열을 나타낸다. 난 그냥 새로운 노드를 할당 할 수 있습니다 다음 그냥 화살표를 가리 다른 방향은하지 않기 때문에 실제에 남아있다 내가 그린 것 같은 기억은 진정한 선 여기에 화면에. 그리고 마지막으로, 당신은 삽입 할 경우 목록의 끝에 뭔가가, 그것의 더 쉽게. 이것은 임의의 표기법의 일종이다 하지만 34의 포인터는 추측을. 대부분의 포인터의 값은 무엇인가 옛날처럼의 가능성이 그려진 종류 이 학교 안테나? 학생 : [들림]. 스피커 1 : 그것은 아마 널 (null)입니다. 그리고 실제로 그 하나 저자의 널의 표현입니다. 당신 때문에 절대적으로 그리고 널의 알 필요가 어디에 링크의 끝 목록은 다음 보관하지 않도록하고 이 화살표를 수행하고 다음과 같은 어떤 쓰레기 값. 그래서 널 (null)이 더 있다는 걸 의미하지 않습니다 숫자 34의 오른쪽에 더 많은 노드, 이 경우합니다. 그래서 우리는 우리가 구현할 수있는 제안 코드에서이 노드입니다. 그리고 우리는 이런 종류 봤어요 구문 전. typedef는 단지의 새로운 유형을 정의 우리는 같은 우리 동의어를 제공합니다 문자열은 char *로를 위해이다. 이 경우, 우리에게주는 것 속기 표기법 있도록 구조체 노드 대신 같이 쓸 수있다 많은 청소기 노드. 그것은 덜 자세한 많아요. 노드의 내부에 분명히 int이며 라는 N, 다음 구조체 노드 * 이는 우리가 원하는 정확히 무엇을 의미 화살표는 다른, 포인터를 의미하는 동일한 데이터 형식의 노드입니다. 그리고 나는 우리가 구현할 수있는 제안 이 같은 검색 기능에서 언뜻 보일 수 있습니다 조금 복잡. 그러나 맥락에서 살펴 보자. 내가 여기서 기기에 갈 수 있습니다. 저라는 파일을 열어 보자 목록 제로 점 H. 그리고는 정의를 우리를 포함 그냥이 데이터에 순간 전보고 형식은 노드를했다. 그래서 우리는 그 점 h 파일에 넣었습니다. 그리고 옆으로도이 생각으로 당신은 볼 것입니다이 프로그램은 모든 것을 복잡, 그것은 참으로입니다 로 프로그램을 작성 규칙 당겨, 데이터 유형 같은 것들을 넣어 때로는 안에서의 상수 헤더 파일과 반드시​​있는 귀하의 C 파일 확실 할 때 프로그램은 크고 큰 얻을 수 있도록 모두에 보이도록 위치를 알고 어떤 경우에는 문서 또는 다음과 같은 기본 사항에 대한 어떤 종류의 정의. 지금은 목록 제로 점을 열면 C는 몇 가지를 알 수 있습니다. 그것은 대부분의 몇 가지 헤더 파일을 포함 그 중 우리가 전에 본 적이. 그것은 자신의 헤더 파일이 포함되어 있습니다. 그리고 옆으로, 그 이유는 두 배의 여기에 따옴표로 각도에 반대 라인에 괄호가 거기 강조했다? 학생 : [들림]. 스피커 1 : 네, 그래서 로컬 파일입니다. 그것은 여기에 자신의 로컬 파일 그래서 경우 15 행에서, 예를 들어, 사용 큰 따옴표 대신 꺾쇠 괄호의. 지금이 흥미로운 종류입니다. 내가 지구를 선언 한 것을 알 수 라인 18이 프로그램에서 변수 먼저 호출이되는 아이디어는 첫 번째에 대한 포인터가 될 것 내 연결된 목록에서 노드, 난했습니다 내가했습니다 있기 때문에 null로 초기화 어떤 실제를 할당되지 그러나 단지 노드. 그래서 이것은 우리가 그림으로 나타냅니다 그림으로의 순간 전보고 지금까지의 해당 포인터 손으로면을 떠났다. 그래서 지금 그 포인터 화살표를 가지고 있지 않습니다. 그 대신 null입니다. 그러나 그것은 있다는 것을 나타냅니다 첫 번째 실제의 주소 이 목록의 노드입니다. 그래서 나는 그것이 글로벌 구현했습니다 이 모든, 당신이 볼 수로 인해 이 프로그램은 생활에서 구현합니다 않습니다 나를 위해 연결리스트. 지금은 여기에 몇 가지 프로토 타입을 가지고있다. 나는 같은 기능을 구현하기로 결정 삭제, 삽입, 검색 및 통과 - 를 통해 마지막 단지 인 거리 목록 요소를 인쇄. 그리고 지금 여기 내 메인 루틴이다. 그리고 우리는에 너무 많은 시간을 할애하지 않습니다 이 이후 이러한 희망, 정렬입니다 지금 쯤은 오래된 모자입니다. 나는 다음과 같은 작업을 수행 할거야 사용자가 협력하면서. 하나 그래서, 인쇄 할거야 이 메뉴 중. 그리고 난 같은 포맷 한 완전히 내가 할 수있는 것처럼. 의미 하나 사용자 유형이있는 경우 그들은 뭔가를 삭제합니다. 의미 두 가지의 사용자 유형에 해당하는 경우 그들은 무언가를 삽입하려고합니다. 등등. 그런 다음 메시지를 표시 할거야 다음 명령. 그리고 나서 getInt를 사용하려고 해요. 그래서 이것은 정말 간단한 menuing입니다 당신이 입력 할 필요가 어디 인터페이스 하나 번호 매핑 이러한 명령. 지금은 좋은 깨끗한 스위치가 에 전환하는거야 문 사용자가 들어 입력 한 어떤 그들은 하나를 입력 한 경우, 나는거야 삭제 전화 및 휴식. 그들은 두 입력 한 경우에, 나는거야 삽입 호출 휴식. 지금은 각각 넣었습니다 인식 한 같은 줄에 이러한. 이것은 단지 문체의 결정이다. 일반적으로 우리는 무언가를 보았다 이런. 하지만 난 그냥 솔직히, 내 프로그램 결정 더 읽기 보였기 때문에 그것은 만 사가지 경우였다 다만 다음과 같이 기재. 스타일을 완전히 합법적 인 사용. 그리고 등이 너무 오래 할거야 사용자가 0 입력하지 않은, 어느 I 결정은 종료 할 의미합니다. 그래서 지금 난 무엇을 알 여기서 뭘. 나는 분명히 목록을 확보 할거야. 잠시 후에 그것에 대한하지만 더. 의에 앞서이 프로그램을 실행하자. 그래서 나는 더 큰 터미널을 만들어 보자 창, 도트 슬래시 목록 0. 나는로 가서 삽입 할거야 입력 두, 지금 50와 같은 수, 당신은 목록이 이제 50입니다 볼 수 있습니다. 그리고 내 텍스트 다만 조금 위로 스크롤. 이제 목록에 포함 된 알 번호 50. 두 가지를 복용하여 다른 삽입을하자. 의이 같은 숫자를 입력 할 수 있습니다. 목록은 현재 50 다음 하나입니다. 이것은 단지 텍스트 표현입니다 그래서 목록. 과의 같은 하나 이상의 숫자를 삽입하자 희망 번호 인 42, 때문에 중간에 종료 예정 특정 종류의이 프로그램은 그 그것은 삽입을 같은 요소. 그래서 거기에 우리가 있습니다. 수 초 간단한 프로그램 절대적으로 내가 배열을 사용했지만 연결리스트를 사용하는 일이 그냥 내가 동적으로 수 성장과 수축. 그래서, 만약의 검색에 대해 살펴 보겠습니다 I 명령 세 가지를 실행, 내가 검색 할 번호 43, 말합니다. 아무것도 분명히 찾을 수 없습니다, 나는 어떤 응답을 가지고하지 않기 때문에. 그래서 다시이 작업을 수행하자. 검색 할 수 있습니다. 50, 또는 오히려 검색하자 검색 42, 이는 좋은가 약간 미묘한 의미. 그리고 거기에 삶의 의미를 발견했다. 당신이 모르는 경우, 번호 42, 참조, 구글 그것. 좋아. 그래서 나를 위해이 프로그램을 수행하고있다? 그것은 다만 저를 따라서 삽입 할 수있어 요소까지 및 검색 할 수 있습니다. 에, 그럼, 빨리 감기하자 우리는 흘끗 그 함수 월요일에 맛보기로. 이 기능 그래서, 난에 대해 검색을 주장 처음으로 목록의 요소 한, 사용자에게 메시지를 표시 한 후 호출 실제 INT를 얻을 수 getInt를 당신이 검색하고자하는. 그런 다음이를 확인할 수 있습니다. 나는 임시 변수를 만들거야 라인 188에 포인터라고 - PTR - 그것을 무엇이라고 수 있었다. 그리고 노드에 대한 포인터이다 나는 거기에 노드 * 말했기 때문에. 그리고 나는 그것이 동일하게 초기화 해요 처음 그래서 효과적으로 것을 내 손가락, 그래서 매우에 이야기하기 목록의 첫 번째 요소입니다. 여기 내 오른손 PTR 난 그래서 경우 같은 것을 가리키는 첫 가리키는입니다. 그래서 지금 다시 코드, 무엇이 다음에 일어날 일 - 반복 할 때이 일반적인 패러다임 같은 구조에 연결리스트. 나는 동안 다음을 수행 할거야 포인터 그래서 null로 같지 않은 동안 내 손가락은 널 문자를 가리키는되지 않습니다 값, 포인터 화살표 n은 N과 동일합니다. 우리는 여기서 n은 것을 처음으로 알 수 있습니다 무엇 당 GetInts에 입력 한 사용자는 여기를 호출합니다. 그리고 포인터 화살표 없음은 무엇을 의미? 우리는 여기 사진에 돌아가 잘 경우, 나는에서 가리키는 손가락이있는 경우 아홉을 포함하는 첫 번째 노드 화살표는 본질적으로 이동을 의미합니다 노드, 위치 N의 값을 잡아 이 경우, 데이터 필드에 N을했다. 옆으로 - 우리는이 부부를 보았다 주 전 누군가가 물었을 때 - 이 구문은 새로운이지만, 그것은하지 않습니다 우리에게 능력을 제공하는 우리 이미하지 않았다. 사용하는 것과이 구절은 무엇인가 점 표기법과 스타 커플 주 전 우리는 다시 벗겨 때 이 비트 중간 계층? 학생 : [들림]. 스피커 1 : 맞아요, 그것은 스타이고, 그런 다음에, 스타 점 N 있었다 여기서 괄호, 이는 보인다 솔직히, 나는 많게 생각 읽기 더 이상한. 그러나 별 포인터, 언제나, 수단이 이동합니다. 그리고 일단 당신이 어떤 데이터가 왔어 필드가 액세스 할 수 있습니까? 그럼 당신은에 액세스 할 점 표기법을 사용 구조체 데이터 필드, 그리고 특히 n을합니다. 솔직히, 나는이 주장 읽는 것만으로 어렵습니다. 어디 기억하기 힘들어 괄호, 가야합니까 스타와 그 모든. 그래서 세계는 몇 가지 문법을 채택 설탕, 말하자면. 말의 단지 섹시한 방법 이 동일하며 아마도 더 직관적. 포인터가 실제로 포인터라면, 화살표 표기 수단이 가서 찾아 이 경우 필드에 N을했다. 나는 그것을 발견 그래서 만약, 내가 뭘 알 수 있습니다. 나는 단순히 인쇄, 나는 퍼센트 나는 발견 그 INT의 값에 연결. 나는 종류의 단지 1 초 동안 잠을 호출 로 화면에 일시 정지 관광 사용자에게 흡수 할 두 번째 줄 방금 무슨 일이. 그리고 나서 휴식. 그렇지 않으면, 나는 무엇을해야합니까? 나는 동일한 포인터를 업데이트 다음 포인터 화살표. 그래서 그냥 명확하게,이 이동 수단 내 구식 표기법도 사용. 이것은 단지 어떤 이동하는 것을 의미하므로 당신은 매우에서하는 가리키고 첫 번째 경우는 내가 가리키는있어입니다 그것에서 9와 구조체. 그래서 거기에 갔어요. 그리고 점 표기법의 의미, 다음에서 값을 가져옵니다. 그러나이 값은, 그것은 그려에도 불구하고 좁은으로, 단지 숫자입니다. 그것은 숫자 주소입니다. 여부,이 코드 한 줄은 이렇게 이 같은 기록보다 비밀 방법, 또는 다음과 같이, 조금 더 직관적 인 방법은, 그냥 내 손을 이동 의미 다음 단계로 첫 번째 노드에서 그 후, 다음 하나는 한 다음, 등등. 그래서 우리는 다른에 연연하지 않습니다 삽입 및 삭제의 구현 및 탐색의 처음 두 이는 매우 관여하고 있습니다. 그리고 나는 그것을 얻기 위해 아주 쉽게 생각 구두를 수행 할 때 잃었다. 그러나 우리가 할 수있는 것은 결정하기 위해 시도하는 방법 가장 시각적으로이 작업을 수행 할 수 있습니다. 내가 제안 것이기 때문에 그 경우 우리 이에 요소를 삽입 할 기존 목록, 어떤 다섯 가지 요소를 가지고 - 9, 17, 22, 26, 33 - 나는이 구현하려고 한 경우 코드는, 내가 이동하는 방법을 고려할 필요가 이 일에 대해. 그리고 아기 단계를 수행 제안 할 이 경우 내 말은 그것에, 무엇입니까 가능한 시나리오가 우리 일반적으로 발생할 수있는? 링크에 대해 삽입을 구현할 때 목록이 그냥 일어나는 크기 다섯 구체적인 예. 당신은 번호를 삽입 할 경우에 잘 번호를 하나의 말을 좋아하고, 여기서, 정렬 된 순서를 유지 분명히 하나의 필요 개수는 않습니다 이 특정 예제에서 이동? 처음에 좋아한다. 그러나 흥미로운 무슨이있다 당신은이에 하나를 삽입 할 경우 목록, 어떤 특별한 포인터가 필요 분명히 업데이트 할? 첫번째로 올려주세요. 그래서 난이 첫 번째 경우입니다 주장 우리는, 고려할 수있는 에서 삽입을 포함하는 시나리오 목록의 시작입니다. 의도 쉽게 또는 어쩌면 오프 뽑아 보자 쉽게 경우, 상대적으로 말하기. 내가 삽입한다고 가정 정렬 된 순서에서 번호 35. 그것은 분명 거기에 속한다. 그래서 포인터가 분명히가는 이 시나리오에서 업데이트 할 수 있습니까? 34의 포인터가 널 (NULL)이되고 그러나 구조체의 주소 숫자 35을 포함. 그래서이 경우는 두 가지이다. 아직, 나는 양자화의 종류 해요 내가 여기서 할 필요가 얼마나 작동합니다. 그리고 마지막으로, 명백한 중간 케이스입니다 참, 중간에 있으면 내가 원하는 가는 말 23과 같이 삽입 23 26 사이지만, 지금은 상황이 조금 더 얻을 참여하기 때문에 어떤 포인터를 변경해야합니까? 22 분명히 변경해야하므로 그는 더 이상 26 가리킬 수 있기 때문이다. 그는 새 노드를 가리 키도록해야하는 나는 호출하여 할당해야합니다 malloc에​​ 또는 어떤 해당합니다. 하지만 나는 또한 새로운 노드 23이 필요합니다 이 경우, 그 포인터를 가지고 누구를 가리키는? 26. 하고있을거야 여기에 작업 순서입니다. 때문에 미련이 작업을 수행, 그리고 경우 의 시작 부분에 인스턴스 시작을위한 목록 내 목표는 23를 삽입하는 것입니다. 그리고 나는 속합니까 확인 여기에, 구에 가까운? 아니오. 그것은 17 다음 여기에 속한다합니까? 아니오. 그것은 22 다음 여기에 속한다합니까? 예. 지금 여기 바보 야하는 경우, 그리고 이를 통해 생각 나는 수도 23 나의 새로운 노드를 할당합니다. 나는의 포인터를 업데이트 할 수 있습니다 노드를 가리키는 22라는 그것은 새로운 노드. 그리고 나서 업데이트 무엇을해야합니까 새 노드의 포인터이어야 하는가? 학생 : [들림]. 스피커 1 : 맞아요. 26에 가리키는. 난 이미 업데이트되지 않은 경우에 젠장 22의 포인터가이 사람에서 가리킨하기 지금은 고아, 나머지를 가지고 목록으로 말하자면. 여기에 작업 때문에 순서 중요 할 것입니다. 이렇게하려면 내가 훔칠 수 여섯 자원 봉사자를 말한다. 그리고 우리는이 작업을 수행 할 수없는 경우 보자 시각 대신 코드 현명한. 그리고 우리는 몇 가지 아름다운 스트레스를가 오늘 당신을 위해 공. 확인하는 방법에 대한 하나, 둘,에 다시 -가 끝. 너희 둘 셋, 넷, 끝에 사람. 다섯, 여섯. 있는지 확인하십시오. 다섯 여섯. 모든 권리와 갈 게요 너희들 옆에있는 시간입니다. 좋아, 어서. 좋아, 여기에 먼저있어 이후 당신은 어색 하나 싶습니다 여기에 구글 유리에? 좋아, 그래서 OK, 유리, 영상을 기록합니다. OK, 당신은 갈 수 있어요. 좋아요, 당신들이 와서 할 수있는 경우 여기, 내가 사전에 준비했습니다 몇 가지 숫자. 그래, 어서와. 그리고 왜 당신이 조금 가지 않는다 추가하는 방법입니다. 그리고 보자, 당신의 이름은 무엇입니까, 구글 유리가 있나요? 학생 : 벤. 스피커 1 : 벤? OK, 벤, 당신은 말 그대로 먼저 될 것입니다. 그래서 우리는 당신을 보낼거야 무대의 끝. 좋아, 당신의 이름은? 학생 : 제이슨. 스피커 1 : 제이슨, OK 당신은거야 아홉합니다. 당신은 벤이 길을 따라 싶은 경우에. 학생 : 질. 스피커 1 : 질, 당신이 될 것입니다 17 이는 내가이 더 많은 일을하려는 경우 지능적으로 나는 것 다른 쪽 끝에서 시작했다. 당신은 그 길을 이동합니다. 22. 그리고 당신은? 학생 : 메리. 스피커 1 : 메리, 당신은 22있을 것이다. 그리고 당신의 이름은? 학생 : 크리스. 스피커 1 : 크리스, 당신은 26있을 것이다. 그리고 마지막으로. 학생 : 다이아나. 스피커 1 : 다이아나, 당신은 34있을 것이다. 그래서 당신은 어서와. 좋아, 이렇게 분류 완벽 이미 주문한다. 과의이 가서 이렇게하자 그래서 우리가 정말 할 수 있습니다 - 벤 당신이 찾고있는 단지 종류입니다 난데없이 거기에. 자, 그럼 가서이를 묘사하자 I이었다 많은처럼 팔을 사용하여, 정확하게, 무슨 일이야. 그래서 가서 자신에게 줄 발 또는 자신 사이에는 두 가지. 한 손으로 가서 포인트 당신은에서 누구를 가리키는해야한다 이에 따라. 당신이 null이라면 그냥 포인트 똑바로 바닥에. OK, 너무 좋아. 그래서 지금 우리는 연결리스트를 가지고 있고, 나를 보자 나는의 역할을합니다 것을 제안 PTR, 그래서 나는 걱정하지 않습니다 주변이 들고입니다. 그리고 - 사람 바보 대회 - 당신이 당신이 원하는 무엇이든을 호출 할 수 있습니다 - 이전 포인터, PRED 포인터 - 그냥 우리가 준 별명이다 내 왼쪽 손에 우리의 샘플 코드입니다. 유지 될 것하는 반면 누구에 누구의 추적 시나리오에 따라. 그래서 첫째, 오프 뽑아하려는 가정 삽입의 첫 번째 예는 말 20,리스트에. 그래서 누군가가 필요 해요 우리를 위해 숫자 20을 구현. 그래서 malloc에​​ 누군가 필요 관객. 올라 와요. 당신의 이름은 무엇입니까? 학생 : 브라이언. 스피커 1 : 브라이언, 모든 권리, 그래서 당신 20를 포함하는 노드가되어야한다. 그래, 어서와. 그리고 확실히, 여기서 브라이언 속합니까? 그래서 중간에 - 사실, 분을 기다립니다. 우리는 주문의를하고 있어요. 우리는 더 어렵게이 만들고있어 처음에는 필요 이상으로. OK, 우리는 자유 브라이언에 갈거야 그리고 다섯 realloc을 브라이언. OK, 이제 우리는 삽입 할 다섯 브라이언. 그래서 옆 어서와 단지 순간을 위해 벤. 그리고 당신은 아마 알 수 있습니다 이 이야기는 것입니다. 그러나하자에 대해 신중하게 생각 작업의 순서입니다. 그리고 그것은 정확하게이 영상의 줄 것이 이 샘플 코드. 그래서 나는 여기있는 PTR 처음에 가리키는있다 아니 본질적으로 벤,에, 그러나 어떤에 그는이 포함되어 가치있는이 경우 이다 - 당신의 이름을 다시 무엇인가? 학생 : 제이슨. 스피커 1 : 제이슨 벤과 나는 둘은 그렇게 이 순간 제이슨 가리키는. 그래서 지금 결정해야합니다, 브라이언은 어디에 속합니까? 유일한 그래서 난에 액세스 할 수 있습니다 지금 자신의 n 개의 데이터 항목입니다. 그래서, 확인하는 것입니다거야 제이슨보다 브라이언 적은? 대답은 사실이다. 그래서 지금 어떻게해야 올바른 순서로? 나는 얼마나 많은 포인터를 업데이트 할 필요가 이 이야기에 맞추어? 내 손은 여전히​​ 가리키는 위치 제이슨, 당신의 손 - 만약 당신이 원한다면 일종의처럼 손을 넣어 I , 물음표 모르겠어요. OK, 좋아. 좋아, 당신이 너무 몇 가지 후보. 벤 또는 I 또는 브라이언이나 제이슨 하나 아니면 다른 사람, 그 포인터를 변경해야합니까? 어떻게 전체의 많은? 좋아, 그럼 두. 내 포인터가 정말 더 이상 문제가되지 않습니다 난 그냥 임시 해요 때문이다. 그래서, 아마도이 두 사람의 벤과 브라이언 모두. 그래서 우리는 업데이트하는 날 제안하자 벤은, 이후 그가 처음이다. 이 목록의 첫 번째 요소 지금 브라이언 될 것입니다. 브라이언에 따라서 벤 점. 자, 이제 어떻게? 누가 누구에서 지적되는? 학생 : [들림]. 스피커 1 : OK 그래서 브라이언이 제이슨 가리킬 수 있습니다. 하지만 난 그 포인터 추적을 잃었습니까? 제이슨이 어디 있는지 아세요? 학생 : [들림]. 스피커 1 : 난 이후로 내가 할 임시 포인터. 그리고 아마도, 내가 변경되지 않은 새 노드를 가리키게한다. 그래서 우리는 단순히 브라이언 포인트를 가질 수 있습니다 누구에 나는 가리키는거야. 그리고 우리는 끝났어. 그래서 케이스 하나에 삽입 목록의 시작. 두 가지 주요 단계가 있었다. 하나, 우리는 벤를 업데이트해야하고 우리는 또한 브라이언를 업데이트해야합니다. 그리고 나서 걱정 할 필요가 없습니다 의 나머지 부분을 통해 터벅 터벅 우리는 이미 발견 목록, 때문에 그의 그는에 속한 위치하기 때문에 첫 번째 요소의 왼쪽. 좋아, 그래서 매우 간단합니다. 우리는 거의 것처럼 사실, 느낌 이 너무 복잡하고. 그럼 이제 끝을 뽑아 보자 목록, 그리고 위치를 확인 복잡성이 시작됩니다. 청중 그래서 지금, 나 할당. 사람은 55를 재생하려면? 좋아, 내가 먼저 손을 보았다. 올라 와요. 그래. 당신의 이름은 무엇입니까? 학생 : [들림]. 스피커 1 : Habata. OK, 올라옵니다. 당신은 55 번있을 것이다. 그래서 당신은 물론, 속 목록의 끝에. 그럼 저와 시뮬레이션을 재생하자 단지 순간을 위해 PTR되고있다. 그래서 나는 처음에 가리 키도록거야 벤에서 가리키는 뭐든간에. 우리는 지금 브라이언을 가리키는거야 모두. 그래서 55 개 미만이 아닙니다. 그래서 난으로 자신을 업데이트 할거야 브라이언의 다음 포인터로 가리키는 사람 지금은 물론 제이슨입니다. 55 그래서보다 아홉 없습니다 나는 PTR를 업데이트하는거야. 나는 PTR를 업데이트하는거야. 나는 PTR를 업데이트하는거야 나는 PTR을 업데이트 할 것. 그리고 나는 갈거야 - 음, 무엇을 당신의 이름을 다시? 학생 : 다이아나. 스피커 1 : 다이아나 가리키는 물론, 그녀의 왼쪽 손으로 널에서. 어디 Habata 실제로 수행 분명히 속해? 왼쪽으로, 여기. 어떻게 내가 여기에 그녀를 넣어 알고 내가 망쳐 버린 것 같아요. 무엇 PTR 예술이기 때문에 시간이 순간? NULL입니다. 그래서 비록 시각적으로, 우리는 할 수있다 분명이 모든 참조 여기에 무대에 사람. 나는 이전의 트랙을 유지 적이 없다 목록에있는 사람. 나는 밖으로 가리키는 손가락을 가지고 있지 않습니다 이 경우, 노드 번호 34. 그럼 실제로이 이상을 시작할 수 있습니다. 그래서 지금은 사실 필요 두 번째 지역 변수입니다. 그리고 이것은 당신이 볼 수 것입니다 실제 예제 C 코드로 내가가는 곳, 나는 가리 내 오른손을 업데이트 할 때 제이슨, 따라서 I, 뒤에 브라이언를 떠나 더 나은 내 왼쪽 손을 사용하여 시작 내가 어디에 있었는지 내가 가서되도록 업데이트 이 목록을 통해 - 더 어색 나는 예정보다 지금 여기 시각 - 내가 얻을거야 목록의 끝. 이 손은 사랑이다 아직도 널 표시하는 것보다 다른 쓸모없는 나는 목록의 끝에 분명 해요 하지만 지금은 적어도이있다 이전 포인터 그래서, 여기를 가리키는 지금 무엇을 건네고 어떤 포인터가 필요 업데이트 할? 그의 손 당신이 원하는 첫 번째 재구성? 학생 : [들림]. 스피커 1 : OK, 다이애나의 때문에. 어디 가리 싶어 에서 다이애나의 왼쪽 포인터? 55, 아마도 그 때문에 우리가 삽입 한. 어디 55 포인터가 가야하나요? 아래는, null를 나타내는. 그리고 내 손이 시점에서,하지 그들은 단지했기 때문에 문제가 임시 변수. 이제 우리는 끝났어. 그래서 추가가 복잡 -와 그것은 구현하기가 어렵지 않다 그러나 우리는 만들 수있는 보조 변수를 필요로 확인이 내 권리를 이동하기 전에 손, 내 왼쪽의 값을 업데이트 한편, PRED이 경우 포인터 때문에, 나는 뒤에 포인터를 가지고 내가 어디에 있었는지를 추적한다. 지금은 옆으로, 당신이 생각하는 경우 이처럼 통해,이 느낌 유지해야하는 약간 성가신 이 왼손의 추적 할 수 있습니다. 어떤 다른 해결책은 것 이 문제에 다녀 오 셨나요? 당신은 데이터를 재 설계 할 수있어 경우 우리가 얘기 구조 지금까지? 이 단지 종류의 조금을 느끼는 경우 좋아, 두 개의 포인터를 가지고 고민 누가이 목록을 수 것 , 이상적인 세계에서, 유지하고있다 우리가 필요로하는 정보를? 그래? 학생 : [들림]. 스피커 1 : 맞아요. 오른쪽 너무 흥미로운 사실​​은있다 아이디어의 세균. 그리고 이전 포인터의 생각, 이전 요소를 가리키는. 내가 그냥 구현하는 경우 그 목록 자체의 내부? 그리고 시각화하기 어려울 것 이 모든 종이없는 바닥에 떨어지는. 그러나이 사람들을 모두 사용한다고 가정 그들의 손의 이전을 가지고 따라서 포인터, 그리고 다음 포인터 우리는 이중 전화 할게 무엇을 구현 연결리스트. 즉, 나 되감기 정렬 할 수 있습니다 것입니다 훨씬 더 쉽게 나없이, 프로그래머, 유지하기 위해 필요 수동 추적 - 진정한 수동 - 나는 이전에 있었던 곳의 리스트합니다. 그래서 우리는 그렇게 할 수 없습니다. 그 때문에 우리는 간단하게합니다 두 배, 가격에 올 것 포인터 공간, 두 번째 개를 원하는 경우. 그러나 실제로 일반적이다 데이터 구조로 알려져 이중 연결리스트. 여기에 마지막 예제를 수행하고 넣어 보자 자신의 불행 중이 녀석. malloc에​​ 20 그래서. 이 통로에서 올라와. 좋아, 당신의 이름은 무엇입니까? 학생 : [들림]. 스피커 1 : 미안 해요? 학생 : [들림]. 스피커 1 : Demeron? OK 올라옵니다. 당신은 20이어야한다. 당신은 분명 가고있다 17 22 사이에 속한다. 그래서 내 교훈을 배울 수 있습니다. 내가 포인터를 시작하는거야 브라이언 가리키는. 그리고 내 왼쪽 손을 가지고거야 내가 이동에만 브라이언로 업데이트 제이슨 검사는 아홉 20 이하합니까? 아니오. 17 이상 20 미만입니까? 아니오. 22 이상 20 미만입니까? 예. 그래서 포인터 또는 손 변경해야 여기서 그들은 지금 가리키는거야? 그래서 우리는 20를 가리키는 17을 수행 할 수 있습니다. 그래서 괜찮아요. 우리는 어디 가리 싶어 포인터 지금? 22시. 22 여기서 우리는 다시 한번 감사를 알고 내 임시 포인터. 그래서 우리는 OK있어. 그래서 때문에이 임시 저장 나는 모두가 어디에 추적을 유지했다. 그리고 지금 당신은 시각적 곳으로 갈 수 있습니다 당신이 속하고 지금 우리는 1, 2, 3이 필요 4, 5, 6, 7, 8, 9, 긴장 공, 와 갈채를 이 녀석, 우리가 할 수있는 경우. 잘 했어. [박수] 스피커 1 : 좋아요. 그리고 당신은 조각을 유지할 수 있습니다 기념품으로 종이. 좋아, 그래서, 많은의 날 믿어 더 쉽게하는을 걷는 그것은 실제 코드보다 인간. 하지만 당신은 단지 순간에 찾을 수 있습니다 지금 같은 것입니다 - 아, 감사합니다. 감사합니다 - 당신이 동일한 데이터를 찾을 것입니다 구조, 연결리스트, 사실 수 있습니다 더에 빌딩 블록으로 사용될 수 복잡한 데이터 구조. 그리고 여기 너무 테마를 실현은 그 우리는 절대적으로 더 소개했다 구현에 복잡성 이 알고리즘. 삽입, 우리는 그것을 통해 간 경우, 삭제 및 검색은 조금 그것보다 더 복잡 배열했다. 그러나 우리는 어떤 활력을 얻을 수 있습니다. 우리는 적응 데이터 구조를 얻을. 그러나 다시, 우리는 몇 가지를 갖는 가격을 지불 추가적인 복잡성의 두 그것을 구현. 그리고 우리는 무작위 액세스를 제공하고 있습니다. 그리고 솔직히, 멋진이 아니다 슬라이드를 청소 난 당신을 줄 수있는 여기에서 말하는 이유는 연결 목록입니다 배열보다 낫다. 그리고에 그것을 두십시오. 테마도, 지금은 재발하기 때문에 더 그렇게 앞으로 몇 주 안에있다 반드시이 아니라고 정답. 우리는 별도의 축이 이유입니다 문제 세트 디자인. 그것은 매우 문맥에 맞는 것입니다 이 데이터를 사용할지 여부 구조 나 하나, 그것은 것입니다 측면에서 당신에게 중요한 무엇에 따라 달라집니다 자원과 복잡성. 하지만 내가 제안하자 그 이상 데이터 구조 성배는 것 시간 상수 뭔가, 에 관계없이 많은 재료가되는 방법 그 안에, 그것은 놀라운되지 않을 것 경우 데이터 구조는 답을 반환 일정 시간입니다. 예. 이 단어는 큰 사전입니다. 또는 아니,이 단어는 없습니다. 아니면 그러한 문제. 잘 보자 우리가 적어도 수 있다면 그 방향으로 조치를 취할. 내가 새 데이터 구조를 제안하게하는 다른 것들을 사용할 수 있습니다, 이 경우 해시 테이블이라고. 그래서 우리는이기는 다시 사실입니다 이 경우 배열과의 임으로,이 그려진 것 의 종류와 배열로 해시 테이블 2 차원 배열 - 또는 오히려이 두 여기에 묘사 된 것 차원 배열 - 그러나 이것은 단지 같은 크기 26의 배열, 그 경우 우리 배열 테이블, 테​​이블 받침대를 호출 제로 상단에 사각형입니다. 테이블 브라켓 25 사각형이다 아래에. 그리고 내가 데이터를 그릴 수있는 방법입니다 내가 저장할 구조 사람의 이름. 그래서 예를 들어, 난을 그릴 수 없습니다 여기에 오버 헤드에 모든 것을, 만약 내가 내가 지금 갈거야이 배열을했다 해시 테이블을 호출하고,이 또 다시 위치 제로. 이것은 여기에 위치입니다 하나 등등. 나는이 데이터를 사용하려는 주장 구조, 토론을 위해, 사람의 이름을 저장하기 위해, Alice와 Bob 찰리와 같은 다른 이름. 그래서 시작으로 지금의 생각 사전, 말의 단어의 제비를 가진. 그들은 이름이 될 일이 여기에 우리의 예제합니다. 그리고 이것은에, 아마도 너무나 밀접한입니다 우리와 같이 맞춤법 검사기를 구현 문제에 대한 여섯 설정할 수 있습니다. 우리는 전체 크기 26의 배열이있는 경우에는 이 25 일 위치되도록 하단에, 나는 앨리스이라고 주장 사전의 첫 번째 단어 내가 RAM에 삽입 할 이름, 이 데이터 구조로, 어디 말하고 본능이 앨리스의 이름이 배열에 가야하나요? 우리는 26 옵션이 있습니다. 우리는 그녀를두고 싶은? 우리는 브라켓 제로에서 그녀를 원하는 맞죠? 앨리스에 대한이의 그 제로를 호출 할 수 있습니다. 그리고 B는 하나가 될 것입니다, 그리고 C는 두 가지가됩니다. 그래서 우리는 쓸거야 여기에 앨리스의 이름을 백업합니다. 우리는 밥, 자신을 삽입 할 경우 이름이 여기에 갈 것이다. 찰리는 여기에 갈 것이다. 등등 다운을 통해 이 데이터 구조입니다. 이 멋진 데이터 구조입니다. 왜? 잘 실행 시간은 무엇인가 이것으로 사람의 이름을 삽입 지금은 데이터 구조를? 이 테이블이 구현되는 것을 감안할 때, 진정, 배열. 잘 일정한 시간이다. 그것은 하나의 명령이다. 왜? 그럼 당신은 어떻게 결정합니까 앨리스는 어디에 속해? 당신은 그녀의 이름의 한 편지를 보여? 첫번째로 올려주세요. 이 문자열 인 경우 그리고 당신은 거기에 얻을 수 있습니다 단지 문자열을 확인하여 브라켓 제로. 문자열의 0 번째 문자 때문에. 그것은 간단합니다. 우리는 암호에 해당했다 할당 주 전. 그리고 일단 당신이 앨리스의 알 편지를 수도, 우리는 뺄 수 있습니다 65 자본 자체 할인 그것은 우리에게 영을 준다. 그래서 우리는 이제 앨리스가 속한 것을 알고 위치 제로. 그리고이 데이터에 대한 포인터를 제공 구조는 일종의, 얼마나합니까 그것은 위치를 찾으려면 데려가 배열의 제로? 한 단계는, 바로 그것은 일정한 시간 랜덤 액세스 때문에 우리 제안은 배열의 특징이었다. 그래서 짧은, 알아내는 무슨 색인 앨리스의 이름에,이다,이다 이 경우는, 또는하자 그냥 해결 제로 여기서, B는 하나이며, C는 그 두 그렇게 파악 일정 시간입니다. 난 그냥 그녀의 첫 글자를보고해야 제로 곳 알아 냈어 배열은 일정 시간입니다. 그래서 기술적으로 그건 지금은 두 단계처럼. 그러나 여전히 상수이다. 그래서 우리는 하나의 큰 O를 호출, 그래서 우리는했습니다 이 테이블에 앨리스를 삽입 일정 시간입니다. 물론, 내가되고있어 여기에 순진, 맞죠? 어떤 클래스의 아론이 있다면? 또는 알리시아? 또는 다른 이름으로 시작 A. 우리가 어디 넣어 가고있다 그 사람 맞죠? 내 말은, 지금은 세 개만있다 테이블에 사람들이, 어쩌면 우리 위치 아론을 넣어야한다 제로 하나 둘 셋. 오른쪽, 여기를 넣을 수 있습니다. 하지만, 우리는에 다윗을 삽입하려고하면 이 목록은 다윗이 어디로 가야합니까? 지금 우리의 시스템은 침입 시작 아래 오른쪽? 이제 다윗은 여기서 끝납니다 아론은 실제로 여기됩니다. 를 갖는 그리고 지금은이 모든 아이디어 우리를주는 깨끗한 데이터 구조 일정 시간 삽입이 더 이상 내가해야하기 때문에 시간 상수, 확인, 오, 제기랄, 누군가가 벌써 앨리스의 위치. 날이 데이터의 나머지 부분을 조사하자 구조 넣는 장소를 찾고 아론의 이름이 같은 사람. 그리고도 시작됩니다 선형 시간이 걸릴 수 있습니다. 또한, 당신은 지금을 찾으려면 이 데이터 구조 아론, 그리고 확인하고, 아론의 이름은 여기에 없습니다. 이상적으로, 당신은 아론의 말 것 없는 데이터 구조합니다. 그러나 당신이 경우에 공간을 만들기 시작 아론은 여기서 D가 있었어야 또는 E, 당신은, 최악의 경우, 확인해야합니다 에서 전체 데이터 구조, 무언가에 양도한다이 경우 테이블의 크기에 선형. 모든 권리 그래서,이 문제를 해결할 수 있습니다. 여기서 문제는 내가했다는 것입니다 이 배열의 26 요소입니다. 내가 그것을 변경할 수 있습니다. 으악. 대신의 존재하므로 내가 그것을 변경할 수 총 크기 26, 바닥을 알 수 인덱스 n은 마이너스 1로 바꿀 것입니다. 26 인간 '에 대해 명확하게 너무 작은 경우 이름 때문에 수천있다 세계의 이름은은 그냥 만들어 보자 100 1,000 1만인치 의 단지 더 많은 공간을 할당 할 수 있습니다. 잘 반드시 감소하지 않는 우리는 두 가지 문제가 발생하지 않습니다 가능성 이름으로 사람들로 시작하고, 그래서, 당신은 넣어 시도하려고했다 아직 위치 제로에 이름. 그들은 여전히​​ 충돌려고하는 우리는 아직도 넣어 솔루션을 필요 의미 Alice와 아론과 알리시아 및 기타 다른로 시작하는 이름. 하지만이 얼마나 문제인가? 확률은 그게 당신 데이터 충돌이 이런 구조? 음, 저를 보자 - 우리는 돌아올거야 여기 그 질문에. 그리고 어떻게 우리가 수도보고 먼저 해결. 내가 여기서이 제안을 당겨 보자. 우리가 방금 설명한 것은 알고리즘 선형이라는 추론 를 삽입하려고하면, 그것에 프로빙 이 데이터에 뭔가 해시 테이블이라고 구조, 그리고 여지 당신은 거기에 없다 진정한 데이터 구조를 조사 점검이 사용할 수 있습니까? 이 가능한이 사용할 수 있습니다? 이 사용할 수 있습니까? 그리고 마침내 때, 당신은 삽입 당신이 원래 의도 한 이름 다른 그 위치에서. 그러나 최악의 경우, 만 자리 데이터의 맨 아래있을 수 있습니다 구조, 배열의 끝. 그래서 선형 최악의 경우, 프로빙, 선형 알고리즘에 양도한다 여기서 아론, 그가 마지막으로 삽입 할 수 일어나는 경우 이 데이터 구조에, 그는 수도 이 첫 번째 위치에 충돌하지만, 다음 맨 마지막에 나쁜 행운으로 끝납니다. 그래서이 일정하지 않다 저희를위한 시간 성배. 삽입이 요소 접근 방식에 데이터 구조 해시라고 테이블은 일정 시간이 될 것 같지 않습니다 적어도 일반적인 경우합니다. 그것은 선형 무언가로 바뀔 수 있습니다. 우리는 충돌을 해결 그래서 경우 다소 다르게? 그래서 여기가 더 정교의 아직도 무엇을 접근 해시 테이블이라고. 및 해시, 옆으로, 무엇으로 그 인덱스를 의미 아까 언급. 에 해시 뭔가 할 수 있습니다 동사로 생각했다. 당신 해시 앨리스는 이름의 경우에, 해시 함수 말하자면, 숫자를 반환해야합니다. 그녀는에 속하는 경우이 경우 제로 그녀는에 속하는 경우 위치 0 개 위치 하나, 등등. 그래서 내 해시 함수는 지금까지왔다 간단한 초 만보고 사람의 이름 첫 글자. 하지만 해시 함수로 간다 입력 데이터의 일부 조각 문자열 중간, 뭐든간에. 그리고 그것은 일반적으로 숫자를 뱉어. 그리고 그 번호는 어디에 해당 데이터 요소는 데이터 구조에 속하는 해시 테이블로 여기 알려져 있습니다. 그래서 그냥 직관적으로, 이것이다 약간 다른 상황. 이것은 실제로 예제를 참조합니다 관련 생일, 여기서 만큼이있을 수 있습니다 월 31 일. 하지만이 사람에게 무엇을 결정 했 충돌의 경우에합니까? 컨텍스트는 현재의 충돌되지 것 이름 만 생일의 충돌, 두 사람의 같은 생일이있는 경우 예를 들어 10 월 2 일. 학생 : [들림]. 스피커 1 : 그래, 그래서 여기에 우리가 연결리스트의 활용. 그래서 조금 다르게 보인다 우리는 그것을 먼저 그려보다. 그러나 우리는 배열을 가지고있는 것 같습니다 왼쪽에. 즉 더를 위해, 하나의 인덱스 없다 특별한 이유. 하지만 여전히 배열입니다. 그것은 포인터의 배열입니다. 각각의 이러한 요소 각각 이러한 원이나 슬래시 - 슬래시 나타내는 널 (null) -이 각각의 포인터는 분명히 가리키고 어떤 데이터 구조를? 링크 된 목록입니다. 그래서 지금 우리가 할 수있는 능력을 가지고 우리의 프로그램에 하드 코드 테이블의 크기입니다. 이 경우, 우리가 결코 알 한달에 31 개 이상의 일. 열심히 31과 같은 값입니다 코딩 그 상황에서 합리적. 이름의 맥락에서, 하드 코딩 26 무리없는 그 사람들의 이름은, 예를 들어,로 시작 Z까지를 포함하는 알파벳 우리는 데이터로 그들 모두를 벼락 공부를 할 수 있습니다 구조 그렇게 오랫동안 우리가 얻을 때, 등 충돌, 우리는 여기에 이​​름을 넣지 않고, 우리는 대신에 이들 세포의 생각 문자열이 아닌 자체 만만큼 예를 들어, 앨리스에 대한 포인터. 그리고 앨리스는 또 다른 포인터를 가질 수 있습니다 로 시작하는 다른 이름 A. 그리고 밥은 실제로 여기에 간다. 그리고 시작 다른 이름이 있다면 B로, 그는 여기에 끝납니다. 그리고 이것의 각 요소 우리가 설계하는 경우 테이블 두 개, 조금 더 영리 - 어서 - 우리는이 조금 더 디자인하는 경우 영리, 지금은 적응 데이터가됩니다 아무 하드 제한은 없습니다 구조 당신은 삽입 할 수 있습니다 얼마나 많은 요소 그것으로 당신이 할 경우가 있기 때문에 충돌, 그 괜찮습니다. 그냥 가서 그것을에 추가 우리는이었다 조금 전 보았던 연결리스트로 알려져 있습니다. 그럼 그냥 잠시 동안의 일시 정지를 할 수 있습니다. 충돌 확률은 얼마인가 첫 번째 장소에서? 그래, 어쩌면 내가 이상, 어쩌면 생각 해요 나는이 문제를 설계 할 이상 해요 당신은 무엇을 알고 있기 때문에? 네, 임의 가지고 올 수 처럼 내 머리의 맨 오프 예 앨리슨와 아론하지만, 현실에서, 의 균일 한 분포 부여 어떤 임의의 삽입이다 입력, 데이터 구조로 정말로 무엇인가 충돌 확률은? 잘 밝혀, 사실의 초고. 이 날 일반화하자 문제는 이것과 같습니다. 따라서 N의 방에 CS50 학생, 무엇을 확률이 적어도 방에 두 학생 같은 생일이? 그래서이있다. 몇 훈트 - 여기 몇 가지 200, 3백명 오늘 집에서 백명. 당신은 무엇을 스스로에게 물어보고 싶은게 너무 경우 두 사람의 확률 같은 생일을 가진이 방에, 우리는이 알아낼 수 있습니다. 그리고 두 께가 실제로 주장 같은 생일을 가진 사람. 예를 들어, 사람이하지 오늘 생일이? 어제? 내일? 내가 갈거야처럼 좋아, 그래서 느낌 더보기이 363 정도를해야합니다 시간은 실제로 알아낼 우리가 할 경우에 충돌이 있습니다. 아니면 우리가 수학적으로이 작업을 수행 할 수 오히려 지루하고 이상 이 작업을 수행. 다음을 제안한다. 그래서 우리가 모델링 할 수있는 제안 을 가진 두 사람의 확률 1의 확률 같은 생일 필요없이 하나의 마이너스 확률 같은 생일. 그래서를 얻으려면,이 단지입니다 이를 작성하는 멋진 방법 객실 내 첫 번째 사람이, 그 또는 그녀 수 중 하나를 가질 수 있습니다 생일은 일년 365 일 가정 가진 사람에게 사과를 2월 29일 생일. 그래서이 방에있는 첫 번째 사람은 무료입니다 생일의 수를 가지고 밖으로 365의 가능성이 있으므로 우리는 365 365 나눈 할 것이다 이는 하나입니다. 방에있는 다음 사람, 만약 목표 충돌을 방지하는 것입니다, 수 만 방법에 대한 자신의 생일을이 여러 가지 가능한 일? 364. 따라서이 식의 두 번째 항은 기본적으로 우리가 수학을하고 한 가지 일을 뺀 있습니다. 그리고 다음 날, 그 다음 날, 아래의 총 개수로 다음날 방에있는 사람들의. 그리고 우리는 고려하면, 그 무엇 의 유무 사람의 확률 독특한 생일, 그러나 다시 1을 뺀 즉, 우리가 얻을 것은 표현 그것은 매우 기발 할 수 있습니다 다음과 같습니다. 그러나 더 흥미로운 시각적으로 볼 수 있습니다. 이 x 축에 차트입니다 방에있는 사람의 수, 생일의 수. y 축에 대한 확률은 충돌의 두 사람 같은 생일 데. 그리고이 곡선에서 테이크 아웃입니다 즉 당신이 40 좋아하는 받자 마자 학생, 당신은 90 %의 확률로 최대있어 combinatorically 두 명 이상 필요 같은 생일. 그리고 일단 당신이 그것을의 58명을 좋아 얻을 기회 두의 거의 100 % 방에있는 사람들을 위하여려고하고있다 같은 생일,있다하더라도 365 또는 366 가능한 물통 및 방에있는 유일한 58명. 다만 통계적으로 당신은 가능성이있어 , 충돌을하는 짧은 이 토론을 동기를 부여. 우리는 여기에서 멋진 얻고, 경우에도 그 이러한 체인을 가지고 시작, 우리는 아직도 충돌을해야 할 것. 질문을 구걸 그래서, 무엇입니까 삽입과 삭제를 수행 비용 이 같은 데이터 구조에? 그럼 내가 제안하자 - 그리고 나를 통해 화면으로 돌아 가자 여기에 - 우리의 요소를 n을 한 경우 목록, 그래서 우리는 삽입하려는 경우 n 개의 요소, 그리고 우리는이 얼마나 많은 총 버킷? 하자 총 31 버킷 말 생일의 경우합니다. 하나의 최대 길이는 무엇입니까 잠재적으로 이러한 체인? 다시 가능 31이 있다면 해당 월의 생일. 그리고 우리가 모두 응집거야 - 실제로는 바보 같은 예입니다. 대신 26을 봅시다. 실제로 이름이 사람이있는 경우에는 따라서 포기, A에서 Z까지로 시작 우리는 26 가능성. 그리고 우리는 같은 데이터 구조를 사용하는 우리가 그것에 우리가 보았던 하나, 포인터의 배열 된 각 연결리스트를 가리키는 첫 번째 목록은 모든 사람입니다 이름을 앨리스. 두 번째 목록은 모든 첨부 시작,로 시작하는 이름을 B와, 등등. 각각의 가능성 길이는 무엇입니까 해당 목록 우리는 좋은 깨끗한 가정하면 Z까지 이름의 분포 전체 데이터 구조를 통해? 데이터 구조의 N 사람들이있다 그들이 잘한다면, 26로 나눈 전체에 퍼져 데이터 구조. 따라서 이들 각각의 길이 체인은 26로 나눈 n입니다. 그러나 큰 O 표기법, 즉 무엇인가? 정말 그렇게 무엇입니까? 그래서 오른쪽, 정말 그냥 N입니까? 우리는 과거에 말한 때문에, 우 당신은 26로 나누어합니다. 예, 실제로는 더 빠르다. 그러나 이론적으로, 그것은 근본적 아니다 모든 것을 빨리. 그래서 우리는 모두 그 정도되지 않는 것 같습니다 가까이이 성배. 사실,이 단지 선형 시간입니다. 도대체이 시점에서, 왜 우리는하지 않습니다 하나의 거대한 연결 목록을 사용합니까? 왜 우리는 하나의 거대한을 사용하지 않는 의 이름을 저장하는 배열 방에있는 사람? 음, 뭔가가 남아 있습니다 해시 테이블에 대한 강력한? 강력한 뭔가가 남아 있습니다 데이터 구조에 대한 즉, 다음과 같습니다? 이. 학생 : [들림]. 스피커 1 : 그것은 단지 오른쪽, 다시 경우 선형 시간 알고리즘 및 선형 시간 데이터 구조, 왜하지 단지 큰 모든 사람의 이름을 저장 배열 또는 큰 연결리스트에서? 그리고 훨씬 더 CS을 중단 그것은 필요 이상? 심지어 이것에 대해 강력한 무엇입니까 나는 그것을 긁어하지만? 학생 : [들림]. 스피커 1 : 삽입의이되지 않습니다? 더 이상 비싼. 그래서 삽입은 잠재적 여전히 수 일정한 시간이 될 경우에도 데이터 구조는 다음과 같이 배열을 보이는 포인터가 가리키는 각각의 잠재적으로 연결된 목록입니다. 당신은 어떻게 일정하게 달성 할 수 이름 시간 삽입? 바로 앞에 붙여? 우리의 디자인 목표를 희생하는 경우 이전에, 우리는 계속 싶었던 사람의 이름은, 예를 들어, 정렬 또는 무대에서 모든 숫자는 분류 우리가이 있다고 가정 분류되지 않은 연결리스트. 그것은 단지 우리에게 하나 또는 두 단계를 비용 벤과 브라이언의 경우처럼 이전에 요소를 삽입하는 방법 목록의 시작입니다. 우리 모두 정렬 걱정하지 않도록하는 경우 로 시작하는 이름의 일부 또는 전부 B로 시작하는 이름을 우리는 아직 할 수 일정 시간 삽입을 얻을 수 있습니다. 이제 앨리스 나 밥 또는 이름을 찾고 더 일반적으로 아직 무엇인가? 그것은 26로 나눈 N의 큰 O,의 모두가 균일의 이상적인 경우 분산, 많은의가 어디 Z의, 아마도 이는이 있기 때문에 비현실적인. 그러나 여전히 직선입니다. 그러나 여기에서, 우리는 점에 다시 올 인 점근 표기법 이론적으로 사실. 하지만 현실 세계에서, 경우 내가 주장하는 내 프로그램은 26 번 뭔가를 할 수 그 프로그램이 당신보다 더 빠르게 당신이 사용하고 선호하는 건가요? 당신이나 광산, 어떤 26 배 빠른? 현실적으로, 그 사람은 26입니다 배 빠르게, 심지어 이론적 경우 우리의 알고리즘은 동일한에서 실행 실행 시간 점근. 내가 다른을 제안하자 모두 솔루션입니다. 이것은 당신의 마음을 날려하지 않는 경우, 우리는 데이터 구조 나간다. 그래서 그것은 트라이입니다 - 바보 같은 이름의 종류. 그것은 단어에게 번의 검색에서 제공하고, 때문에 트라이, T-R-I-e를 철자 물론 검색은 트라이 같은데. 하지만 그 역사의 단어 트라이의. 그래서 트라이는 실제로 나무의 일종 그리고 그것은 또한 그 단어에 놀이이다. 그리고 당신은 확실히 그것을 볼 수 없지만 이 시각화, 트라이은 나무와 함께 가족 나무처럼, 구조 상단 및 평가 한 조상 손자와 증손 으로는 바닥에 나뭇잎. 그러나 트라이에있는 각 노드는 배열입니다. 그리고 배열에 - 그리고하자 잠시 지나치게 단순화 - 그것은의이 배열이 경우, 크기 26, 여기서 각 노드는 다시 크기의 배열 26 곳의 0 번째 요소 배열을 나타내며, 마지막 이러한 각의 요소 배열 Z.을 나타냅니다 그래서, 다음, 제안하는이 데이터 트라이로 알려진 구조 일 수있다 단어를 저장하는 데에도 사용됩니다. 우리는 우리가 저장할 수있는 방법 순간 전보고 단어, 또는이 경우 이름에, 우리 우리는 번호를 저장할 수있는 방법을 보았던 그러나 우리는 이름이나 문자열에 초점을 맞출 경우 여기에 흥미로운 것을 알 수 있습니다. 그 이름 맥스웰이라고 주장 이 데이터 구조의 내부. 당신은 어디에서 맥스웰을 볼 수 있습니까? 학생 : [들림]. 스피커 1 : 왼쪽에. 따라서이 데이터 흥미로운 무엇 구조는 오히려 매장보다 문자열 M--X-W-E-L-L 백 슬래시 제로, 모든 인접, 대신 무엇을 할 따르고있다. 이 데이터 구조와 같은 트라이 경우, 그 각각의 노드는 다시 배열 그리고 당신은 맥스웰을 저장하려는 경우 먼저 인덱스 등등 때문에 루트의 노드, , 최상위 노드를 이야기하기 오른쪽, 그래서 위치 M,에서 대략 중간에. 그리고 거기에서, 당신을 따라 자식 노드에 대한 포인터는, 말하자면. 따라서 가계도 의미에서, 당신은 아래로를 따르십시오. 그리고 그 다른 노드로 당신을 이끌 거기 왼쪽에 또 다른 배열입니다. 그리고 당신은 맥스웰을 저장하려는 경우 당신이 나타내는 포인터를 찾을 수 A, 이는 여기입니다. 그런 다음 노드로 이동합니다. 그리고주의 - 이것은 왜 그림의 약간의 눈속임 - 이 노드는 작은 슈퍼보세요. 하지만이 오른쪽에 Y 및 Z를합니다 그것은 바로 저자가 절단되었습니다있어 사진 있도록 실제 일을 참조하십시오. 그렇지 않으면이 그림 상당히 넓은 것입니다. 다음 위치 X로 이제 당신은 색인, 그런 다음 그 W, 그리고 E, L, L. 무엇 이 호기심? 음, 우리는 새로운 이런 종류의를 사용하는 경우 에 문자열을 저장하는 방법에 걸릴 데이터 구조, 당신은 여전히​​ 필요 기본적으로 데이터에 체크 표시 단어는 여기에 끝나는 구조. 즉,이 노드의 각 어떻게 든 기억을 가지고 우리 실제로 다음이 포인터의 그리고 약간의를 떠나 이것의 여기 하단에 빵 부스러기 M--X-W-E-L-L을 나타내는 구조입니다 실제로이 데이터 구조가있다. 그래서 우리는 다음과 같이이 작업을 수행 할 수 있습니다. 우리가 그림에서 각 노드 톱 하나, 크기 27의 배열을 가지고 있습니다. P에 여섯 설정 때문에 그것은 지금 27의 우리가 실제로 당신에게 아포스트로피를 줄 것이다 그래서 우리는 오라일리 같은 이름을 가질 수 있습니다 아포스트로피 및 다른 사람. 그러나 같은 생각. 에서 이러한 요소 각각의 구조체 배열을 포인트 노드, 그래서 그냥 노드입니다. 그래서 이것은 매우 연상 우리의 링크 목록. 그리고, 나는 부울을 가지고있는 나는거야 단어를 호출하는 단지가 될 것입니다 단어이 종료 true의 경우 트리 노드입니다. 그것은 효과적으로 약간을 나타냅니다 삼각형 우리는 잠시 전에 보았다. 단어의 해당 노드에서 종료 그렇다면 나무, 그 단어 필드는 true가됩니다 이는 개념적으로 해제 확인되거나, 우리는 예가,이 삼각형을 그리는거야 여기에 단어입니다. 그래서 이것은 트라이이다. 이제 질문은, 무엇 그 시간을 실행? 그것은 N의 큰 O인가? 다른 것입니까? 글쎄, 당신은이 데이터에 이름을 n을 한 경우 구조, 맥스웰의 하나 인 그들의 실행 시간 것입니다 삽입 또는 맥스웰를 찾는? 실행 시간은 무엇입니까 맥스웰 삽입? N 다른 이름이있는 경우 이미 테이블에있는? 그래? 학생 : [들림]. 스피커 1 : 그래, 길이의 이름, 오른쪽? M--X-W-E-L-L 있도록이 같은 느낌 그래서 알고리즘은 일곱 큰 O입니다. 지금은 물론, 이름 길이가 달라집니다. 아마 짧은 이름입니다. 아마 긴 이름이다. 그러나 여기에서 중요한 것은이다 그것은 상수이다. 그리고 어쩌면 그것이 정말 일정하지의 하나님 현실적으로 경우에 사전에 몇 가지 제한이 거기에 아마 에있는 문자의 수 특정 국가에있는 사람의 이름을 입력합니다. 그래서 우리는 가정 할 수 값은 상수입니다. 나는 그것이 무엇인지 모르겠어요. 그것은 아마보다 큰 우리는 생각합니다. 일부 코너는 항상 거기 때문에 미친 긴 이름을 가진 케이스. 그럼이 K 호출하게,하지만 여전히의 상수 아마도 모든 때문에 이상에서 세계에 이름을 특정 국가, 그 길이 또는이다 짧은, 그래서 상수이다. 그러나 우리는 말했다했을 때 뭔가 큰 상수 값의 O, 무엇을하는 에 정말 상응하는? 그건 정말 같은 것 일정한 시간을 말하는 등. 지금 우리는 부정 행위의 종류 맞아요? 우리는 몇 가지 이론을 활용하는 종류입니다 여기에 잘, K의 순서가 있다고합니다 정말 그냥 하나의 주문 그리고 일정 시간입니다. 하지만 정말이다. 여기서 중요한 통찰력이기 때문 우리는이 이미 이름을 n을 한 경우 데이터 구조, 우리 삽입 맥스웰, 그것은 우리를 걸리는 시간의 양을 영향을받는 모든에서 맥스웰를 삽입 얼마나 많은 다른 사람들 데이터 구조에? 될 것 같지 않습니다. 나는 이것에 억 이상의 요소를 가지고 있다면 다음 트라이하고, 맥스웰되어 삽입 그는 전혀 영향? 아니오. 그리고 그 날 데이터의 달리의 우리는 여기서 지금까지 본 적이 구조 귀하의 알고리즘의 실행 시간은 얼마나 완전히 독립적으로 물건은 나 있지 않은 해당 데이터 구조에있다. 이 가르치시로 그리고 당신은 지금이다 P 세트 여섯, 기회있는 것 다시 자신의 구현을 포함 15에 읽기 맞춤법 검사기, 즉, 최선의 방법이를 저장 반드시 명확하지 않다. 내가 찾을 열망했다지만 성배, 나는하지 트라이는 주장한다. 사실, 해시 테이블은 아주 잘 할 수있다 훨씬 더 효율적인 것으로 증명한다. 하지만 그 단지입니다 - 그것은 단지 디자인 결정 중 하나 당신은 확인해야합니다. 그러나 닫는의가 보자 50 정도 초 무슨 일이 있을지에 들여다 봐도 앞서 다음 주 우리 전환 이후 이 명령 줄에서 것들을 웹에 세계의 C 프로그램 경우 기반 PHP 같은 언어와 자바 스크립트와 인터넷 자체 당신은했습니다 HTTP 같은 프로토콜, 년 동안 당연한 모든 지금 가장하고, 입력 하루는, 아마도, 또는 본. 그리고 우리는 다시 껍질을 시작합니다 어떤 레이어는 인터넷이다. 그리고 코드는 무엇입니다 기초는 오늘날의 도구를 제공합니다. 여기 맛보기 너무 50초. 나는 당신에게 그물의 전사를 제공합니다. [동영상 재생] - 그는 메시지와 함께. 프로토콜을 모두 자신과 함께. 그는 잔인한 방화벽의 세계에 온 무관 심한 라우터 및 위험까지 죽음보다 더. 그는 빠르다. 그는 강한. 그는 TCPIP입니다. 그는 당신의 주소를 가지고있다. 넷의 전사. [END 동영상 재생] 스피커 1 : 그것은 얼마나 인터넷 다음주로 작동된다.