DOUG 로이드 : 그래서 CS50, 우리는 다루었 다른 데이터 구조의 많은 권리? 우리는 배열을 볼 수, 및 연결 한 목록 및 해시 테이블, 및 시도, 스택과 큐. 우리는 또한 조금 배울 수 있습니다 나무와 힙에 대한, 하지만 정말이 모든 단지 종료 최대 테마에 변화를 주도했습니다. 정말이있다 이러한 네 가지 기본 아이디어 가지 다른 그 모든 졸이다 수 있습니다. 배열, 연결리스트, 해시 테이블 및 시도합니다. 그리고 같은 내가 거기 말했다 그들에 변화가있다, 하지만이 꽤있다 많은 요약 것 모든 것을 우리가 이야기거야 C의 관점에서이 클래스에 대한 그러나 방법이 바로, 모든 측정 최대합니까? 우리는 장점과 단점에 대해 얘기했습니다 그들에 별도의 동영상의 각의, 하지만 숫자가 많이있다 주위에 던져지고. 일반적으로 많이있다 생각은 주위에 던져지고. 의 시도하고 통합하자 그것은 단지 하나의 장소에. 의가에 대해 전문가의 무게를 보자 단점 및 고려 이는 데이터 구조 올바른 데이터 수 있습니다 특정 상황에 대한 구조, 데이터의 어떤 종류의 당신은 저장하고있다. 당신은 반드시 항상 할 필요가 없습니다 , 슈퍼 빠른 삽입, 삭제를 사용하여 트라이의 및 조회 당신이 만약 정말로 삽입과 삭제에 대한 상관 없어 너무 많은. 당신은 신속하게 임의해야하는 경우 액세스는, 어쩌면 배열이 더 좋다. 그래서 그 증류 할 수 있습니다. 의 네 개의 각각에 대해 얘기하자 데이터 구조의 주요 종류 우리는 이야기, 그리고했는지 그들이 잘 될 수있는 경우에 단지 참조 때 그들은 그렇게 좋은하지 않을 수 있습니다. 그럼 배열을 시작하자. 삽입 그래서, 그 종류의 나쁜. 

배열의 마지막에 삽입은 OK입니다 우리가 가서 우리는 배열을 구축하는 경우. 그러나 우리는 삽입해야하는 경우 중간에 요소, 삽입을 다시 생각한다 정렬 많이있다 의 거기에 요소에 맞게 이동. 그리고 우리는 삽입하는거야 그렇다면 어딘가에 그러나 어레이의 단부, 그것은 아마 그렇게 큰 아니에요. 

마찬가지로, 삭제하지 않는 한 우리는있어 어레이의 단부로부터 삭제 아마도 만약 그렇게 크지 않다 우리는 빈 틈을 떠나고 싶지 않아, 이는 일반적으로 우리가하지 않습니다. 우리는 요소를 제거 할, 그리고 다음 종류의 다시 아늑한합니다. 그래서에서 요소를 삭제 배열도 그렇게 크지 않다. 

조회는하지만, 아주 좋습니다. 우리는 랜덤 액세스 할 수 있습니다, 일정 시간 조회. 우리는 단지 일곱 말을하고, 우리가 간다 배열 재배치 일곱. 우리는로 이동하여, 20 말 배열 재배치 (20). 우리는에서 반복 할 필요가 없습니다. 그건 꽤 좋은입니다. 

배열은 정렬하기가 비교적 쉽다. 우리가 정렬에 대해 얘기 할 때마다 이러한 선택 정렬과 같은 알고리즘, 삽입 정렬, 버블 정렬, 병합 종류, 우리는 항상 그것을 할 배열을 사용, 배열은 꽤 쉽기 때문에 데이터 구조들에 대하여, 정렬 우리는 지금까지 본 것. 

또한 상대적으로 작은입니다. 여분의 공간이 많이 아니에요. 당신은 정확히만큼 따로 당신이 당신의 데이터를 보유해야하므로, 그게 꽤 많이 있습니다. 그래서 그들은 아주 작은 것 그 방법으로 효율적입니다. 그러나 또 다른 단점하지만, 그들은 크기가 고정되어 있다는 것입니다. 우리는 정확히 어떻게 선언해야 큰 우리는, 우리의 배열이 원하는 우리는 만에 하나의 기회를 얻을. 우리는 성장하고 축소 할 수 없습니다. 

우리가 성장 또는 축소해야하는 경우, 우리 완전히 새로운 배열을 선언해야합니다, 의 모든 요소를​​ 복사 두 번째 배열에 첫 번째 배열. 그리고 우리는 잘못 계산하는 경우 시간, 우리는 다시 할 필요가있다. 정말 대단하지. 그래서 배열은 우리에게 유연성을 제공하지 않습니다 요소의 변수 번호를 가지고 있습니다. 

연결리스트로, 삽입은 매우 간단합니다. 우리는 단지 전면에 압정. 삭제도 매우 간단합니다. 우리는 요소를 찾을 수있다. 즉, 약간의 검색을 포함한다. 

하지만 당신은 요소를 찾으면 당신은 당신이해야 할 모든 찾고 포인터를 변경하고, 가능성이 당신이있는 경우 이 이중 list-- 연결 연결리스트, rather-- 다음은 노드를 확보 할 수 있습니다. 당신은 이동하지 않아도 주변의 모든 것을. 당신은, 두 개의 포인터를 변경 그래서 꽤 빠르다. 

조회 바로, 그래도 나쁜? 우리를 찾는 위해서는 연결리스트의 요소, 여부를 단독으로 또는 이중으로 연결된 우리는 그것을 검색 선형해야합니다. 우리는 처음부터 시작해야하고 끝을 이동하거나 최종 이동 시작 처음으로. 우리는 더 이상 랜덤 액세스 할 수 없습니다. 우리가 일을하는 경우에 따라서 검색의 많은, 어쩌면 연결리스트는 아니다 우리에게 꽤 좋은. 

그들은 정말도있어 정렬하기 어려운, 오른쪽? 유일한 방법은 당신이 할 수있는 정말 링크 목록을 정렬 당신이 그것을 구성으로 분류하는 것입니다. 하지만 당신은 당신으로 분류하는 경우 를 구축, 당신은 더 이상 것 없다 더 이상 빠른 삽입을. 당신은 시침하지 않을 전면 위에 것들. 당신은 찾을 수있다 정확한 지점은 그것을 넣어, 다음 삽입 단지에 대한 나쁜됩니다 배열에 삽입있다. 그래서 연결리스트가 없습니다 데이터를 정렬 너무 좋아요. 

그들은 또한 아주 작은 크기 현명한입니다. 이중 약간 목록을 연결 단일 연결리스트보다 큰, 이는 약간 큰 어레이보다하지만 아니다 낭비 된 공간의 엄청난 금액. 그래서 만약 공간이 프리미엄이지만, 아니 정말 강렬한 프리미엄, 이 갈 올바른 방법 일 수 있습니다. 

해시 테이블. 해시 테이블로의 삽입 매우 간단합니다. 이것은 두 단계 프로세스이다. 처음에 우리는을 통해 우리의 데이터를 실행해야 해시 함수는 해시 코드를 얻으려면, 그리고, 우리는에 요소를 삽입 그 해시 코드의 위치에서 해시 테이블. 

연결리스트와 유사한 삭제, 당신이 요소를 발견하면 쉽다. 당신은 먼저 찾아야 하지만 당신은 그것을 삭제하면, 당신은 단지 교환 할 필요가 포인터의 부부, 경우 별도의 체인을 사용하고 있습니다. 당신이 프로빙 사용하는 경우, 또는 당신이하지 않은 경우 사용하는 모든 체인 하여 해쉬 테이블에서, 삭제는 실제로 정말 간단합니다. 당신이해야 할 모든 해시입니다 데이터는 다음 해당 위치로 이동합니다. 그리고 가정 당신은하지 않습니다 어떤 충돌이 당신은 매우 신속하게 제거 할 수 있습니다. 

자, 조회는 어디 것들 좀 더 복잡해진다. 그것은 더 평균있어 연결리스트보다. 당신이 체인을 사용하는 경우, 당신은 여전히​​ 링크 된 목록을 가지고, 이는 여전히 있음을 의미 검색은 링크 된 목록을 손해. 당신이 복용하고 있기 때문에 그러나 당신은 연결 목록 100 또는 1000에 그것을 분할 또는 n 당신의 해시 테이블의 요소, 당신이있어 연결리스트의 크기 n 번째 모두 하나입니다. 그들은 모두 실질적으로 작은입니다. 당신은 N 대신 목록을 연결 한 크기 n의 하나 연결리스트의. 

그래서이 실제 상수 일반적으로 우리 요인, 시간 복잡도에 대해 얘기하지 않는, 그것을 실제로 여기에 변화를 않습니다. 그래서 조회는 여전히 선형 당신이 체인을 사용하는 경우 검색, 하지만,리스트의 길이 당신은을 통해 검색하는 비교하면 매우 짧습니다. 다시 정렬하여 인 경우 여기에 목표, 해시 테이블의 아마 올바른 방법은 이동하지. 정렬하면 그냥 배열을 사용 당신에게 정말 중요합니다. 

그리고 그들은 크기의 영역을 실행 할 수 있습니다. 그것은 여부를 말하기 어렵다 해시 테이블은 작거나 큰 정말에 의존하기 때문에 얼마나 큰하여 해시 테이블이다. 당신은 단지 저장 될 거라면 당신의 해시 테이블의 다섯 가지 요소, 당신은 해시 테이블이 그것은 10,000 요소, 당신은 아마 많은 공간을 낭비하고 있습니다. 대조 또한 당신에게 할 수있는 매우 컴팩트 한 해시 테이블을 가지고 그러나 작은 당신의 해시 테이블 가져옵니다 그 연결리스트의 각각을 길게 가져옵니다. 그래서 정말 정의 할 수있는 방법이 없습니다 정확하게 해시 테이블의 크기, 그러나 그것은 아마 안전 그것은 일반적으로 말할 수 있습니다 링크보다 더 될 것 동일한 데이터 저장 목록 트라이보다하지만 작은. 

그리고 시도는 네 번째입니다 이러한 구조의 것을 우리는 얘기를했습니다. 트라이에 삽입하면 복잡하다. 동적 많이있다 메모리 할당, 특히 초기에, 빌드하기 시작하고있다. 그러나 일정 시간이다. 그것은 단지 요소의 인간 여기가 힘들 수있다. 널 포인터가 발생하는 데, malloc에 공간, 아마도 malloc에​​ 공간이 이동 거기에서 다시. 의 위협 요인의 종류 동적 메모리 할당에 대한 포인터 취소 할 수있는 장애물이다. 그러나 당신이 그것을 삭제 한 후에 삽입 실제로, 매우 간단 온다 그리고 그것은 확실히 일정 시간이다. 

삭제가 용이하다. 당신이 할 필요가 아래로 이동하는 포인터와 무료 노드의 커플, 그래서 꽤 좋다. 조회도 꽤 빠릅니다. 그것은 단지 기반으로 데이터의 길이. 모든 데이터가 있다면 다섯 문자열, 예를 들어, 다섯 기억하는 당신의 트라이에 문자열, 그것은 단지 다섯 단계를 수행 당신이 찾고있는 것을 찾을 수 있습니다. 다섯 때문에, 단지 일정한 요인이다 다시, 삽입, 삭제, 조회 여기에 효율적으로, 모든 일정 시간이다. 

또 다른 것은 당신의 트라이는 점이다 실제로 종류의 이미 오른쪽으로 정렬? 우리가있어 방법의 장점으로 삽입 요소, 의 문자로 편지를 이동하여 키의 숫자에 의해 키 또는 숫자, 일반적으로, 당신의 트라이가 될 수있을 테니까요 당신이 그것을 구축으로 가지 분류. 정말 수 없습니다 의미는 정렬에 대해 생각하는 같은 방식으로 우리는 생각 그것은 배열, 또는 연결리스트와, 또는 해시 테이블. 그러나 어떤 의미에서, 당신의 당신이 가서 트라이가 정렬됩니다. 

단점은 물론 있다는 트라이 빠르게 거대한된다. 모든 연결 지점에서 다음을 수행 할 수도 키는 숫자로 구성된 경우 잔 마셔요, 다른 (10)가 장소는 당신이 갈 수있는 모든 노드 것을 의미한다 정보가 포함되어 있습니다 데이터에 대해 당신이 저장할 해당 노드, 플러스 10 포인터에서. 어느, CS50의 IDE에, 80 바이트입니다. 그래서 적어도 80 바이트의 사용자가 만든 모든 노드, 그리고 심지어 데이터를 계산 아니에요. 및 노드 인 경우는 대신 숫자의 편지, 지금은 26 포인터가 모든 위치에서. 그리고 26 시간 (8)는 아마 200 바이트, 또는 그런 일. 그리고 당신은 자본이 당신에게 할 수 lowercase-- 나는이 함께 갈거야 여기서 오른쪽 볼? 귀하의 노드는 정말 얻을 수 있습니다 큰, 그래서 트라이 자체, 전체, 수 너무, 정말 큰 얻을. 공간은 높은에있는 경우 그래서 시스템에 프리미엄, 트라이의 정보는 다음의 제품에 올바른 방법으로하지 않을 수 있습니다 심지어는 다른 장점이 있지만, 이동 놀이로 제공됩니다. 나는 더그 로이드입니다. 이 CS50입니다.