[Powered by Google Translate] [주 6 일 계속]
[데이비드 J. Malan] [하버드 대학]
[이 CS50 수 있습니다.] [CS50.TV]
이 CS50이며,이 주 6의 끝입니다.
따라서 CS50x, edX 이니셔티브에 참여 하버드 최초의 코스 중 하나
실제로 지난 월요일 데뷔했다.
당신은 인터넷에서 어떤 다른 사람의 모습을하고 싶으 시다면
지금와 함께 다음 아르, 당신은 x.cs50.net에 참가할 수 있습니다.
즉, edx.org에 적절한 장소로 리디렉션합니다
이것과 MIT와 버클리에서 다른 코스가 지금 살고있는 곳이었다.
당신은 계정에 서명을해야합니다, 당신은 물질이 대부분 동일 찾을 수 있습니다
당신은 우리가 모든 준비로 지연 몇 주이라도, 이번​​ 학기에했다. 한로
그런데 CS50x의 학생들이 지금은 볼 수는 상당히 이와 같은 인터페이스입니다.
이 예를 들어, 문제 세트 0 튜토리얼을 주도 Zamyla입니다.
edx.org에 로그인 후, CS50x 학생은 일의 종류를 볼 수
당신은 과정에 보여야하는데 : 월요일 강의를
수요일, 다양한 반바지, 문제 세트, 연습, PDF 파일에 대한 강의.
또한, 당신이 여기서 보는 것처럼, 기계 번역
, 이탈리아어, 스페인어, 일본어, 중국어로 영어 성적
확실하게 불완전한 것입니다 다른 언어와 전체 무리
우리는 API라는 걸를 사용하여 프로그램을 출시로
Google에서 또는 응용 프로그램 프로그래밍 인터페이스,
그것은 우리가 이러한 다른 언어 영어로 변환 할 수 있습니다.
하지만 일부 100 플러스 자원 봉사자들의 아름다운 정신 덕분에,
친절 참여 제의 인터넷에서 무작위 명
이 프로젝트에, 우리는 서서히 그 번역의 질을 향상됩니다
인간이 우리의 컴퓨터가 만든 한 실수를 수정하지로.
>> 우리가 몇 학생들은 우리가 처음 예상했던 것보다 월요일에 표시 한 아웃 그게집니다.
사실, 지금 CS50x 집에서 함께 따라 십만명이 있습니다.
따라서 컴퓨터 과학에서이 과정을이 창립 클래스의 일부입니다 실현
더 일반적으로 교육, 더 넓게, 액세스 할 수 있습니다.
그리고 현실은 이러한 대규모 온라인 코스의 일부와 함께 지금
그들은 모두 우리가 한 것 같은이 매우 높은 숫자로 시작합니다.
그러나 목표는 궁극적으로 CS50x에 대해 가능한 한 마무리 라인에 많은 사람들을 얻을 정말입니다.
디자인으로 CS50x는 지난 월요일부터 제공 될 것입니다
다른 학교 약속이 사람들 있도록 2013년 4월 15일부터 끝까지,
일, 가족, 다른 갈등과 같은이 좀 더 유연성을 가지고
이 과정에 뛰어들되는, 그, 그것은 말 충분
상당히 ambitiously 완료 일반적인 학기 동안 단 3 개월 과정 동안 경우에만.
그러나 이러한 학생들은 같은 콘텐츠를 볼 같은 문제 세트를 예방합니다
같은 반바지와 같은에 대한 액세스 권한을 갖는다.
그래서 우리는 모두 여기 정말있는 것으로 알고 있습니다.
그리고 CS50x의 끝 목표 중 하나는 많은 사람들을 얻을 수 없습니다
결승점와 그들에게 컴퓨터 과학의 현저한 이해를 제공
프로그래밍뿐만 아니라 그들에게이 공유 경험이 있습니다합니다.
캠퍼스에 50 정의 특성 중 하나는, 우리는 희망,
가끔, 더 나은 또는 더 나쁜위한 공동의 경험을 이런 종류있다
하지만이 사람들이에 왼쪽과 오른쪽으로 회전 할 필요가,
그리고 근무 시간과 hackathon 및 공정.
그것은 온라인으로 사람들과 본인이 그렇게되고 조금 어렵네
하지만 CS50x는 최초로 CS50 박람회와 4 월에 종료됩니다
공정한 우리의 아이디어의 온라인 적응 할 것입니다
2 분 동영상으로 - 어디 학생들이 수천은 모두 1 제출에 초대합니다
그 자신의 최종 프로젝트 또는 동영상의 스크린은 인사 손을 흔들 중
그리고 자신의 프로젝트에 대해 얘기하고 demoing,
많은 전임자처럼은 공정에 캠퍼스에 끝났습니다
학기 말까지, 희망은 글로벌 전시회가 될 수 있도록
CS50x 학생들의 최종 프로젝트의 많은 그런 식으로 어느 캠퍼스에 여기 너에게이 12 월 기다리고 있습니다.
앞으로 몇 개월은 그 말에 따라서 더.
>> 100,000 학생들과 함께하지만, 몇 가지 더 인증 기관 (CA)에 대한 필요성을 제공합니다.
당신들이 여기에 오솔길을 가로과 CS50을 복용하는 감안할 때
몇 주 edX에있는 사람들이 물질의 석방을 사전에
우리가이 계획에 가능한 한 자신의 학생들의 많은 참여 싶지만 알고 있습니다
학기뿐만 아니라이 겨울이 오는 봄을 모두.
따라서 CS50x에 참여하고 싶으 시다면,
특히 CS50x 토론, CS50 토론의 edX 버전에에 참여
당신의 많은 캠퍼스에서 사용 된있는 온라인 게시판,
해당 URL에 머리를 해 주시기 바랍니다, 우리는 당신이 누군지 알려
우리는 모두 학생 및 직원 팀과 교수진을 구성 좋아 테니까요
캠퍼스에서 누가 단순히 함께 연주하고 돕고 있습니다.
그리고 그들에게 익숙한 질문을 볼 때,
당신은 인터넷에서 어떤 나라 어딘가 쯤에 몇 가지 버그를보고 학생을 듣고
당신도 같은 문제를 그 반지 종을했기 때문에
얼마 전에 귀하의 D-홀에서, 희망 그리고 당신은에 차임과 자신의 경험을 공유 할 수 있습니다.
당신이 원한다면 참여 바랍니다.
>> 하버드에서 컴퓨터 과학 코스는 전통의 비트가
당신은 자랑스럽게 입을 수있는 의류, 옷을 갖는 그 중 CS50,
학기 말에, 당신은 CS50을 완료하는 것은 자랑스럽게 말하는
그리고 CS50과 같은했다, 우리는 항상 학생들을 포함 해
이 과정을 최대한, 우리는 초대된다에
학기의시기에, 학생들은 디자인을 제출하는
당신은 사용하고자하는 선택의 포토샵을 사용하거나, 어떤 도구
당신은 T-셔츠와 스웨터에 디자인을 제출, 디자이너 인 경우
와 개에 대한 파라솔과 작은 두건 우리는 지금이 있고 좋아요.
그리고 모든 일이겠군요 - 수상자는 매년 그 다음 전시되어 있습니다
store.cs50.net에서 코스의 웹 사이트에.
모든이 비용으로 판매하지만, 웹 사이트 자체를 실행하고 있습니다
그리고 사람들이 좋아하는 색상과 디자인을 선택할 수 있습니다.
그래서 우리가 작년 디자인의 일부를 공유 할 거라고 생각
그 연례 전통, 여기에 이​​것 외에 웹 사이트에 있었다.
"나는 Faultn을 감금있어 매일은"지난해 제출 중 하나
이는 졸업생 위해 계속 사용할 수 있습니다.
우리가이 한 것 "CS50는 1989 년 설립."
우리 Bowdens 중 하나 인 롭 지난해 인기이었습니다.
"팀 보덴"은 태어났다,이 디자인은 탑 셀러 중, 제출되었습니다.
으로 여기있는 건이었다. 많은 사람들이 영업 로그에 따라 "보덴의 열기 '를했다.
그 것은 지금 인터넷에서, 거기에 디자인 될 수 있다고 알고 있습니다.
다음 문제가이에 대한 자세한 내용은 오는 설정합니다.
>> 하나 더 도구 : 지금 희망 몇 가지 노출을했고 한
GDB 몇 가지 체험,
이는 물론, 디버거이며 조작 할 수 있습니다
상당히 낮은 수준에서 프로그램은 어떤 것들 뭐하는거야?
GDB는 당신이 무엇을하게됩니까?
응? 나에게 무언가를 제공합니다. [학생 답 이해할 수없는]
좋아. 함수에 단계, 그래서 당신은 실행을 입력 할 필요가 없습니다
표준 출력에 물건을 인쇄 전체를 통해 프로그램 타격을 갖추고 있습니다.
오히려, 여러분은 다음 입력, 라인하여 라인을 통해 단계를 수
선 또는 쓴 한 가지 일반적으로, 함수 안으로 잠수 할 단계로 라인으로 라인을 이동합니다.
GDB는 당신이 다른 무엇을하게됩니까? 응? [학생 답 이해할 수없는]
변수를 인쇄 할 수 있습니다. 당신은 프로그램의 내부에 약간의 반성을하고 싶다면
사방에 printf 문장을 쓰기에 의존 할 필요없이,
당신은 변수를 인쇄하거나 변수를 표시 할 수 있습니다.
당신은 GDB 같은 디버거로 또 무엇을 할 수 있습니까?
[학생 답 이해할 수없는]
그렇지. 당신은 중단 점을 설정할 수 있습니다, 당신은 휴식 실행을 말할 수
main () 함수 또는 foo는 기능에서.
한 줄에 123 휴식 실행을 말할 수있다.
그리고 중단 점은 정말 강력한 기술 아르
때문에 어디 문제에 대한 일반적인 감각이있는 경우
아마, 당신은 프로그램의 전체를 통해 스테핑 시간을 낭비 할 필요가 없습니다 않습니다.
당신은 본질적으로 바로 이동 한 후 입력을 시작할 수 있습니다 -
단계 또는 다음 또는 같은과를 통해 스테핑.
그러나 GDB 같은과 캐치, 그건 인간이 도움이 있다는 것입니다
문제를 발견하고 버그를 찾으십시오.
그것은 반드시 당신에게 그렇게 많이 찾지 않습니다.
>> 그래서 우리는 짧은 명령 줄 도구입니다, 다른 일 style50을 도입
그 조금 더 깔끔하게 당신보다 코드를 어떤 양식에 일치시키다하려고 인간이 수행 할 수 있습니다.
그러나 역시, 정말 미학 것입니다.
사용하기 좀 더 마법 is Valgrind이라는 다른 도구가 밝혀.
의 출력 먼저 눈에 atrociously 암호입니다.
그러나 특히 지금 우리가 용어의 부분에 있다고, 놀라 울 정도 유용
어디 malloc 및 동적 메모리 할당을 사용하기 시작하고 있습니다.
상황은 빠르게, 정말로 잘못 할 수 있습니다.
때문에 귀하의 메모리를 확보하는 것을 잊지 당신이 NULL 포인터를 역 참조하는 경우
또는 일부 쓰레기 포인터를 역 참조, 일반적으로 결과가 증상 무엇인가?
잘못을 감금. 그리고 당신은 킬로바이트 또는 메가 바이트 어떤 수의 코어 파일을
추락 할 때 즉, 프로그램의 메모리의 상태를 나타냅니다
하지만이 프로그램은 궁극적으로, 세분화 오류를 오류를 감금
어떤 뭔가 나쁜 일을 거의 관련이 있었 단 뜻
당신이 여기 어딘가에 만든 메모리 관련 실수 있습니다.
그래서 Valgrind이 같은 것을 찾을 수 있도록 도와줍니다.
당신이 프로그램을 컴파일 한 후 그 말은, GDB처럼, 당신이 실행하는 도구입니다
하지만 직접 프로그램을 실행보다는, 당신은 Valgrind 실행
그리고 당신이 GDB와 마찬가지로, 여기에 프로그램을 전달합니다.
이제 사용은, 가장 좋은 종류의 출력을 받아
그래서 바로 화면의 상단에 당신은 Valgrind-v를 조금 오래 볼 수 있습니다.
당신이 리눅스 컴퓨터에 프로그램을 사용할 때 "V"는 거의 보편적 자세한을 의미합니다.
그래서 당신이 기본적으로하는 것보다 더 많은 데이터를 뱉어 의미합니다.
"- = 전체를 누설 확인하십시오." 이 단지 가능한 모든 메모리 누수에 대한 검사를 말하고있는
제가 한 수 실수. 이 역시 리눅스 프로그램과 일반적인 패러다임입니다.
당신은 명령 줄 인수가있는 경우 일반적으로 즉, "스위치"입니다
그는 프로그램의 동작을 변경해야하며, 하나의 편지있어
그렇죠-V하지만이었던 그 경우, 그냥 프로그래머의 설계에 의해,
, 명령 줄 인수는과 단어의 전체 단어 나 시리즈를 시작합니다 -.
이것들은 인간의 컨벤션 있지만, 당신은 점점을 볼 수 있습니다.
그리고, 마지막으로, "a.out"이 특정 예제에서 프로그램의 임의의 이름입니다.
여기 몇 가지 대표적인 출력입니다.
>> 우리가 말은 무엇인지 살펴 전에, 제가 여기에 코드 스 니펫 (snippet)로 가자.
그리고 곧, 제가하는 방식이 일을 준비합시다
과의 여기이 짧은 예입니다 memory.c, 살펴 보자.
따라서이 프로그램에, 나를 기능과 질문에 확대 보자.
우리는 함수를 호출 주요 기능, F를 가지고
그리고 다음에 어떻게 F가 약간 기술 영어로, 할을 수행합니까?
F는 무엇을 수행합니까?
방법에 대한 I 줄 20로 시작되고, 별의 위치는 중요하지 않습니다,
하지만 지난 강의 함께 일관성을 수 있습니다.
우리 라인 (20)가 무슨 일을하는데? 왼쪽에. 우리는 더 이상 그것을 파괴합니다.
INT * X : 그게 무슨 일을할까요?
좋아요. 이 포인터를 선언, 그리고 지금의 더 많은 기술적 인하자.
이 포인터를 선언하는 매우 구체적으로, 무엇을 의미합니까? 다른 사람?
응? [학생 답 이해할 수없는] 너무 멀리.
그래서 당신은 등호의 오른쪽에 읽고.
단지 INT * X에 그냥 왼쪽에가 초점을 보자.
이 포인터 "를 선언"않지만, 지금 가자는 정의에 깊이에 잠수.
그 구체적, 기술적으로 무엇을 의미합니까? 응?
[학생 답 이해할 수없는]
좋아요. 그것은 메모리에 주소를 저장 할 준비를하고있어.
좋아. 그리고의 더이 한 걸음을 가져 가게, 그것은 32 비트 변수, X를 선언있어.
그리고 내가 그 때문에 32 비트 알아 -?
는이 경우 포인터 때문에 그런, 정수이기 때문에이 없습니다.
는 정수로 하나 같은, 그건 우연의 일치
그 별이 있다는 사실은이 포인터가 의미
와 어플라이언스에 여러 컴퓨터와 마찬가지로, 전부는 아니지만, 포인터는 32 비트입니다.
최신 맥, 최신 PC를 같은 더 현대적인 하드웨어에, 당신은 64 비트 포인터를 가지고 있습니다
하지만 어플라이언스에, 이것들은 32 비트입니다.
그래서 우리는 거기에 표준화됩니다. 더 구체적으로, 그 이야기는 다음과 같이 간다 :
우리는 포인터 "를 선언"; 그게 무슨 뜻 이죠?
우리는 메모리 주소를 저장하는 준비합니다.
그게 무슨 뜻 이죠?
우리는 32 비트를 차지라는 변수 x를 만들
그건 곧 정수의 주소를 저장합니다.
그리고 아마도 우리가 얻을 수 최대한 정확한입니다.
세상을 단순화하고 단지 X라는 포인터를 선언 말을 전진 괜찮아요.
포인터를 선언하지만, 실현과 실제로 무슨 일이야 이해
그저 그 몇 글자 인치
>> 자,이 사람은 그 이상 표현이지만, 마치 작은 쉬워졌습니다.
그래서 지금 강조 것은, 무엇을하고있다 : "malloc (10 * sizeof (int는));"응?
[학생 답 이해할 수없는]
좋아. 그리고 거기에 걸릴 수 있습니다. 그것은 십 정수에 대한 메모리 덩어리를 할당있어.
그리고 지금의 약간 깊이에 잠수 해, 그것은 십 정수 메모리 덩어리를 할당있어.
malloc는 무엇 반환입니까?
더 구체적으로 그 청크의 주소 또는, 그 덩어리의 첫번째 바이트의 주소입니다.
제가 그럼 어떻게 오전, 프로그래머가 알 수있는 메모리 끝의 덩어리?
나는 연속 된 거에요. Malloc은 정의에 의해 당신에게 메모리의 연속 된 덩어리를 제공합니다.
거기에 어떤 차이 없습니다. 당신은 그 덩어리의 모든 바이트에 액세스 할 수 있습니다
다시 백업 할 백업 할 수 있지만, 메모리의 청크의 끝이 어디에 어떻게 알 수 있습니까?
당신은 malloc를 사용하는 경우? [학생 답 이해할 수없는 잘 됐네.
당신은하지 않습니다. 당신은 기억해야합니다.
나는 값 10을 사용하여 기억해야하고, 난 그 끝났하지 못하는 것 같습니다.
그러나 무거운 짐이 나를 전적으로입니다. 우리가 문자열에 약간 의존이 될 나 strlen,
때문에 \ 0을 갖는이 협약에서만 작동합니다
또는 문자열의 끝에서이 특별한 빵점 문자 빵점.
그 메모리 중 임의의 덩어리에 보유하지 않습니다.
그것은 당신에게 달려 있습니다. 라인 20 그럼, 메모리 덩어리를 할당
그 십 정수를 저장할 수 있으며, 첫 번째 바이트의 주소를 저장
라는 변수 X의 메모리의 청크의.
포인터입니다 따라서. 라인 21 그래서, 불행히도 실수였다.
그러나 먼저, 무엇을하는 거지? 그것은, 위치 10, 인덱스 0에서 상점을 말하는거야
X 값 0이라는 메모리의 청크의.
>> 따라서 몇 가지가가는납니다.
x는 포인터이지만, 몇 주 전부터 기억
당신은 여전히​​ 배열 스타일의 대괄호 표기법을 사용할 수 있습니다.
그 사실은 더 이상한 모양의 포인터 연산에 대한 짧은 손 표기법니까.
우리가이 같은 짓을 했을까 곳 : 주소 X를 타고, 지난 10 장소를 이동
해당 위치에 저장되어있는 어떤 주소로도 이동합니다.
솔직히,이 읽고있는 편안한 받게하기 위해서 심한 것입니다.
그래서 세상이 일반적으로 훨씬 더 인간 친화적 읽을 수있는 단지 때문에 대괄호를 사용합니다.
하지만 그게 정말 후드 아래에 무슨 일입니다;
x는 주소가 아닌 배열 이라기보다는이다.
그래서이 X의 위치 10 0 저장합니다.
왜이 안 좋은가요? 응?
[학생 답 이해할 수없는] 그렇지.
, 우리는 겨우 10 ints를 할당하지만, C에서 프로그래밍 할 때 0을 기준으로
그래서 당신은 0 1 2 3 4 5 6 7 8 9하지만, 10에 액세스 할 수 있습니다.
따라서 두 프로그램은 감금 결함에 갈거나 없습니다.
하지만 우리는 정말 모르겠어,이 nondeterministic 행동의 일종입니다.
정말 우리가 운이 있는지 여부에 따라 달라집니다.
그 여분의 바이트를 사용하는 경우는 운영 체제가 신경 쓰지 않는 밝혀지면
나에게 주어지지 않았다 하더라도, 내 프로그램이 충돌하지 않을 수도 있습니다.
는, 노골적이지는 버그이지만, 그 증상을 볼 수 있습니다
또는 한 번만 한동안 볼 수 있습니다.
하지만 현실은 버그가 사실이라는 것입니다.
당신이 올바른하고자하는 프로그램을 작성 한 경우 그리고 정말 문제입니다
당신은 사람들이 매번 가끔은 충돌하는 사용하는 프로그램을 판매 한
때문에 물론, 상황이 안 좋은데. 사실, 당신은 Android 휴대 전화 나 아이폰이있는 경우
그리고, 당신은 요즘 앱을 다운로드 네가 가졌던 한 경우 응용 프로그램은 종료
가 사라 갑자기, 그, 거의 항상 일부 메모리 관련 문제의 결과입니다
프로그래머는 포인터를 망쳐 및 역 참조된다
그 또는 그녀가 있어서는 안됩니다,와 iOS 또는 Android의 결과는 모두 프로그램을 죽입니다
오히려 위험 정의되지 않은 동작 또는 보안 타협의 일부 종류보다.
>> 이것 외에이 프로그램에 다른 버그가 있습니다.
이 프로그램에 또 무슨 일을 망쳐 버린거야?
내가 설교 한 일을 연습했습니다. 응?
[학생 답 이해할 수없는 잘 됐네.
나는 메모리를 해제하지 않았습니다. 그래서 지금 엄지 손가락의 규칙
당신이 malloc를 호출 때마다 작업을 완료하면 해당 메모리를 사용하여 무료로 전화해야 할 수 있습니다.
자,이 메모리를 해방할까요?
아마,이 첫 번째 줄은 올바른이었다고 가정하면, 여기서하고 싶어합니다.
내 말은, 예를 들어, 여기를 할 수 없습니다 때문입니다. 이유는 무엇입니까?
그냥 범위. 그래서 우리는, 포인터에 대해 얘기하고 있어도
이 주 2 X 만이 선언 된 중괄호 내부 범위에 세 문제입니다.
그럼 당신은 확실히 거기 확보 할 수 없습니다. 을 확보 할 수있는 유일한 기회 대략 21 라인 이후입니다.
이 매우 간단한 프로그램입니다, 당신은 가지 마음을 감싸 일단 매우 간단
실수가 어디를 중심으로 프로그램은하고 있어요.
그리고 당신이 먼저 그것을 보지 못했다하더라도, 희망 지금 너무 눈에 띄어서
이러한 실수는 아주 쉽게 해결하고 쉽게 만들어진 것을.
그러나 프로그램이 12 개 이상의 노선 긴 경우는, 100 줄 길이, 50 라인의 길이
논리적으로 생각, 선에 의해 코드 라인을 통해 걷기,
지속적으로, 버그를 찾고, 가능하지만 할 특히 재미 없어
그리고 그렇게하는 것도 어려운 일이고, Valgrind 같은 도구가 존재하는 이유입니다.
내가 가서이 일을하게 놔두지 : 내 터미널 창을 열어,
그리고 메모리는 괜찮을 것 같습니다 때문에 날 그냥 메모리를 실행하지 맙시다.
운이 나타납니다. 배열의 끝 부분에 해당 추가 바이트로 이동
너무 문제가 될 것 같습니다하지 않습니다.
그러나 그냥 확인하고 의미 정신 검사를,도, 그럼에도 불구하고, 내가 할게
이 사실은 정확 여부.
>> 따라서 valgrind-V를 두자 - = 전체를 누설 확인
그리고이 경우에 프로그램의 이름은 메모리,하지 a.out입니다.
그럼 내가 가서이 해주세요. Enter 키를 누르십시오.
이런. 이번 행사는 출력,이 내가 이전에 언급거야.
그러나, 여기에 말도 안되는 모든을 읽어 배울 경우,
이 대부분은 재미없는 단지 진단 결과입니다.
당신의 눈이 정말 찾고 싶은 것은 오류 또는 무효의 언급입니다.
문제를 제안 단어입니다.
그리고 실제로, 거기에 잘못 무슨 일이야 보자.
나는 일종의 요약,이 "출구에서 사용. 1 블록에 40 바이트를"
아직 정말 블록이 무엇인지 잘 모르겠어요,하지만 40 바이트
그 어디에서 제가 이해할 수있는 것처럼 실제로 느낀다.
40 바이트. 왜 출구에서 사용 40 바이트 무엇입니까?
그리고 더 구체적으로 우리가 여기에 아래로 스크롤하면
이유는 확실히 40 바이트를 잃어? 응?
[학생 답 이해할 수없는] 좋아요. 네, 맞아요.
,이 열 정수가 있었고, 그 각각 4, 또는 32 비트의 크기
당신이 제안대로, 나는 무료 전화를 안 한니까 내가 정확하게 40 바이트를 잃었습니다.
즉, 벌레, 그리고 지금은 더 조금을 살펴 보자이 옆에 표시
"잘못된 크기 4 써주세요." 이제이는 무엇인가?
이 주소는 겉보기에, 어떻게 기본 표기법을 표현입니까?
이 16 진수이며, 언제든지 당신은 0x로 시작하는 번호가 표시
그것은 우리가 다시 질문, 내가 생각 pset 0의 섹션에서 방법을했는지, 16 진수 의미
이는 바이너리 진수 진수로 변환하는 등등, 워밍업 운동을 할 만했다.
진수, 단지 인간의 컨벤션으로, 보통 포인터를 나타내는 데 사용됩니다
또는 더 일반적으로 해결할 수 있습니다. 그건 그냥 대회의
가 읽기 조금 더 쉽기 때문입니다, 그것은, 소수점과 같은보다 좀 더 콤팩트입니다
대부분의 인간이 사용하기에 진 쓸모가 있습니다.
이제이 무엇을 의미합니까? 잘못된 쓰기가 같은 음, 보이는
memory.c의 라인 21 사이즈 4.
그럼 줄 21 돌아 가자, 그리고 실제로, 여기에 잘못 기록입니다.
그래서 Valgrind는 완전히 내 손을 잡아과 수정이 말하려고하지 않습니다
하지만 내가 잘못된 쓰기를하고있는 것으로 감지된다.
내가하지 말라고 4 바이트를 터치하고 있는데 분명히이 있기 때문입니다
당신이 지적으로, 나는 대신에 [9]의 [10]을하고 있어요 maximally
또는 [0] 나 사이에 뭔가.
Valgrind를 사용하면 이제 프로그램을 작성 할 때마다 실현
포인터를 사용하여 메모리를 사용하고, malloc 더 구체적으로, 그
확실히이 오래 실행 습관에 들어가
하지만 아주 쉽게 Valgrind의 명령을 복사하고 붙여 넣기
거기에 몇 가지 오류가 있는지 확인합니다.
그리고, 당신이 출력을 볼 때마다 압도적 있습니다
하지만 단지 시각적으로 모든 출력을 구문 분석하고 표시되는지 확인하면 오류를 언급
또는 경고 또는 무효 또는 잃었다.
당신과 같은 소리가 어디 선가 실수를하는 모든 단어입니다.
귀하의 툴킷의 새로운 도구 인 것 알고 있습니다.
>> 지금 월요일에, 우리는 사람들을 아주 많이 가지고하는 것은 여기에 와서
과 연결리스트의 개념을 나타냅니다.
그리고 우리는 어떤 문제에 대한 솔루션으로 연결리스트를 소개?
응? [학생 답 이해할 수없는 잘 됐네.
배열은 메모리가 그들에게 추가 할 수 없습니다.
당신은 10 사이즈의 배열, 당신이 얻을 전부를 할당합니다.
당신이 처음에 malloc을 호출하면, realloc 같은 함수를 호출 할 수 있습니다
공간이 그 끝을 향해있는 경우와 그 배열을 성장 시도 할 수 있습니다
다른 사람이 사용하지 있으며,이 아니라면, 그냥 다른 곳에서 당신에게 더 큰 덩어리를 찾을 것.
그런데 그게 새로운 배열에있는 바이트의 모든 복사합니다.
이 매우 올바른 솔루션처럼 들린다.
왜 이런 매력이?
난 그게 작동 그러니까, 인간은이 문제를 해결했습니다.
왜 우리는 연결 목록과 월요일에이를 해결하기 위해 필요 했을까? 응?
[학생 대답은 이해할 수없는]은 시간이 오래 걸릴 수 있습니다.
사실, 당신이 malloc이나 realloc 또는 또 다른 하나입니다 calloc을 호출 할 때마다,
언제든지 당신, 프로그램, 운영 체제에 말을하는거야,
당신은 프로그램을 느리게하는 경향이 있습니다.
당신은 루프에 가지 이러한 종류의 일을하는 경우, 당신은 정말 물건 속도가 느려지하고 있습니다.
당신은 "여러분, 안녕하세요!"형 프로그램의 간단한이를 발견 할 수 없어
하지만 훨씬 더 큰 프로그램에서, 메모리에 다시 다시 운영 체제를 묻는
하거나 다시하고 다시 돌려주는 것은 좋은 일이되지 경향이있다.
또한, 그냥 지적의 일종 - 이건 완전히 시간 낭비입니다.
새 배열로 모든 것을 복사 점점 더 많은 메모리를 할당 왜, 위험,
당신이 실제로 필요로 만 많은 메모리를 할당 할 수있는 대안이 있다면 요?
그래서 여기에서 더하기 부호와 minuses가 있습니다.
더하기 부호 중 하나는 우리가 역 동성을 가지고 있다는 것입니다.
메모리의 덩어리는 무료입니다 어디에 있는지 중요하지 않습니다,
난 그냥 포인터를 통해 만들에이 빵 부스러기를 정렬 할 수 있습니다
함께 내 전체 링크 목록을 문자열로.
하지만 적어도 하나의 가격을 지불합니다.
>> 내가 뭘 연결된 목록을 얻기에 포기해야합니까?
응? [학생 답 이해할 수없는 잘 됐네.
당신은 더 많은 메모리가 필요합니다. 지금은,이 포인터위한 공간이 필요합니다
이 슈퍼 간단한 연결리스트의 경우
만 4 바이트 아르 정수를 저장하려고 즉, 우리는 말을 계속
잘, 포인터는 4 바이트이기 때문에 지금은 그대로 두 배로 한
메모리의 양 난 그냥이 목록을 저장해야합니다.
다시 한 번,이 컴퓨터 과학의 일정한 효율이 줄어입니다
시간과 공간과 개발 노력 및 기타 리소스 사이에 있습니다.
연결리스트를 사용하는 다른 단점은 무엇입니까? 응?
[학생 답 이해할 수없는]
좋아. 에 액세스 할 쉽게 수 없습니다. 우리는 활용이 더 이상 수
같은 주 0 원칙은 분열과 정복.
그리고 더 구체적 이진 검색 할 수 있습니다. 때문에 비록 우리 인간이
이 목록의 중간이 어디에 대략 볼 수 있습니다,
컴퓨터는이 연결 목록이 먼저라는 주소에서 시작하는 알고 있습니다.
그래서 0x123 또는 그런 일입니다.
그리고 프로그램을 수있는 유일한 방법은 중간 요소를 찾을 수 있습니다
실제로 전체 목록을 검색하는 것입니다.
그리고 나서, 말 그대로 전체 목록을 검색 할 수 있기 때문에
도 일단은 포인터를 따라 중간 요소에 도달
너, 프로그램은 잠재적으로이 목록이 얼마나 오래 몰라
당신은 그것의 끝을 눌러, 당신은 어떻게 프로그래밍 방식으로 알고 때까지
당신은 연결리스트의 끝에 있다고?
특별한 NULL 포인터, 그래서, 컨벤션가 있습니다.
이 포인터를 사용하기보다는, 우리는 확실히 어떤 쓰레기 값이되고 싶지 않아
어디 선가 무대를 가리키고, 우리는 그것을 손으로 NULL을 원하는,
결말 곳을 우리가 알 수 있도록 우리는이 데이터 구조에서이 터미널이 있도록.
>> 우리가이 조작하고 싶다면?
우리는이 시각의 대부분을 했어, 인간과
하지만 우리가 삽입을하려면?
따라서 원본 목록 9, 17, 20, 22, 29, 34.
우리는 55 번, 뭐 노드에 대한 malloc 공간을 원하는 경우
그리고 우리는 월요일에했던 것처럼 목록에 55 삽입하고 싶어?
우리가 어떻게이 작업을 수행합니까? 음, 아니타가 와서 그녀는 본질적으로 목록을 걸었다.
그녀는 다음, 다음, 다음, 다음, 다음 다음 첫 번째 요소에서 시작했다.
마지막으로 왼쪽 모든 방법을 아래로 누르
그리고 오 실현이 NULL입니다. 그래서 포인터 조작이 필요해서 했어요?
마지막에 있던 사람, 번호 34, 왼쪽 손이 제기 필요
55에 가리, 55는 새로운 NULL 종료 될 때까지 아래로 가리키고 자신의 왼쪽 팔을 필요했습니다. 완료.
예쁜 쉽게 정렬 목록에 55을 삽입 할 수도 있습니다.
그리고 어떻게이 볼 수 있을까요?
>> 내가 가서 여기 몇 가지 코드 예제를 열어 보자.
나는 gedit를 열고 내가 먼저 두 개의 파일을 열어 드리겠습니다.
하나는 list1.h이며,이 코드의 덩어리라고 난 그냥 생각 나게 해
우리는 노드를 나타내는 데 사용되는.
노드 목록에서 그 다음 일은 바로 포인트 그 다음이라는 N이라는 정수와 포인터를 모두 갖추고 있습니다.
그건. H 파일에 지금있다. 이유는 무엇입니까?
있는데,이 대회는, 그리고 우리는이 엄청난 양의 자신을 이용 복용하지 못 했어
printf 및 기타 기능을 작성하지만, 사람
stdio.h라는 파일을 작성하여 세계에 선물로 그 모든 기능을했다.
그리고 string.h가하고 map.h이있어, 모든 이들 h 파일이있어
당신은 본이나 다른 사람이 작성한 기간 동안 사용했을 가능성이 있다고.
일반적으로 이러한 인치 H 파일 typedefs 같은 유일한 사항은 다음과 같습니다
또는 사용자 정의 유형 또는 상수 선언의 선언.
당신은 헤더 파일의 기능 '구현을 넣어하지 않습니다.
당신은 대신, 단지 자신의 프로토 타입을 넣어.
당신은 그들이 원하는 세계와 공유 할 뭔가를 넣어
자신의 코드를 컴파일하는 순서를 유지해야합니다. 그러니 이번 만 습관에 가려면하면,
우리는 같은 일을하기로 결정했습니다. 많은이 list1.h에 없 거든
그러나 우리는 세계의 사람들에게 관심이 될만한 걸 넣어 한
누가 우리의 연결리스트 구현을 사용하고 싶습니다.
이제 list1.c에,이 일을 통과하지 않습니다
이 좀 긴이기 때문에,이 프로그램도 있지만, 그 프롬프트에 빠르게 실제 실행할 수 있습니다.
나, 목록 1를 컴파일 내게 한 다음 목록 1을 실행하게, 그리고 당신은 볼 수 있습니다 봅시다
여기 시뮬레이션 간단한 작은 프로그램이있어
그 때문에 목록에 번호를 추가하고 제거 할 수 있도록거야.
그럼 내가 가서 메뉴 옵션 3 3 입력 보자.
전 그 번호를 삽입하려면 - 가자의 9 살 첫 번째 숫자는, 어떻게
그런데 지금은 내가 목록 지금 9는 말거야.
내가 가서 다른 삽입을하자, 그래서 메뉴 옵션 3를 누르십시오.
어떤 번호가 내가 삽입하고 싶어? 17.
입력합니다. 그리고 한번 더 할게요.
제가 22 번을 삽입 보자.
그래서 우리는 우리가 잠시 전에 슬라이드 형태로 가지고있는 연결리스트의 처음 부분을 수 있습니다.
이 삽입 실제로 어떻게 된 일 이죠?
사실, 22 목록의 끝에 지금이다.
이야기 그래서 우리는 월요일에 무대에서 했더니 지금 recapped
실제로 코드에서 일어나는해야합니다.
가 살펴 보자. 저이 파일에 아래로 스크롤 보자.
우리는 기능의 일부를 넘는 광택됩니다
우리는,에 내려 가서 말, 삽입 기능을합니다.
>> 우리가이 연결 목록에 새 노드를 삽입하는 방식 보자.
목록은 어디에 선언입니까? 음, 우선은, 상단에있는 모든 방법을 스크롤
내 링크 목록이 기본적으로 처음에 NULL입니다 하나의 포인터로 선언되고 있다는 사실을 알 수.
그래서 일반적으로 우리가 상대하고 전파 한, 여기에 전역 변수를 사용
그것은 유지하기 위해 코드 좀 어질러 놨하게 있기 때문
그 게으른, 보통의 일종 이죠하지만 게으른 아니고 잘못 것도 아니고 나쁘지 않아
생활에 프로그램의 목적은 한 링크 목록을 시뮬레이션하는 것이다.
그게 바로 우리가하고있는 일입니다.
모든 기능에 통과해야 다음 주에이를 선언하고 자보다는
우리가이 프로그램에 서면으로 작성했습니다, 우리는 대신 오 실현, 그냥이 글로벌하게 해 줍시다!
이 프로그램의 전체 목적은 하나 하나의 연결된 목록을 입증 할 수 때문입니다.
그럼 괜찮아요 느낀다. 여기 내 프로토 타입은, 우리는 이러한 모든 통과하지 않습니다
하지만 삭제 기능을 찾을 기능, 삽입 기능 및 이송 기능을 썼습니다.
그러나의 지금 삽입 함수에 내려 놔
이 하나가 작동 방법을 참조하십시오.
삽입 줄에 - 여기 우리는 간다.
삽입합니다. 우리가 물을거야 때문에 그게 어떤 인수를 고려하지 않습니다
그들은 삽입 할 수는이 기능의 사용자 내부.
하지만 먼저, 우리는 그들에게 공간을 제공하기 위해 준비하고 있습니다.
이것은 다른 예제 복사 및 붙여 넣기의 일종입니다.
이 경우, 우리는 정수를 할당했다,이 시간 우리는 노드를 할당하고 있습니다.
정말 노드가 얼마나 많은 바이트를 기억하지 않는,하지만 그건 괜찮아.
Sizeof 나를 위해 그 방법을 찾아 내야 할 수 있습니다.
그리고 왜 라인 120에 NULL을 확인 이유는 무엇입니까?
라인 119에 잘못이 있겠 어? 응?
[학생 답 이해할 수없는]
좋아. 그냥 내가 너무 많은 메모리를 요구 한 경우 될 수
또는 뭔가 잘못된 운영 체제, 내 말을 돌려주기에 충분한 바이트가 없습니다
그래서 NULL을 반환하여 많은 신호를, 나는 그것에 대해 확인하지 않는 경우
그냥 난 맹목적으로 주소가 반환 사용하는 수행은 NULL이 될 수 있습니다.
그것은 알 수없는 값이 될 수 있습니다,하지 좋은 일하지 않는 I -
실제로 알 수없는 값이 없습니다. 그것은 NULL 될 수, 제가 원하는 않도록
그것을 악용하고 dereferencing 위험합니다.
그렇게되면, 그냥 돌아 내가 전혀 기억이 돌아 오면 않은 것처럼 우리는 척 할거야.
>> 그렇지 않으면, 사용자가 나에게 삽입 할 수있는 전화 번호를 알려 말해, 난 우리의 옛 친구 GetInt 전화
그리고 이건 우리가 월요일에 도입 된 새로운 구문했다.
'newptr -> N'당신이 malloc에​​ 의해 주어진있는 주소를 의미
이는, 새로운 노드 객체의 첫 번째 바이트를 나타냅니다
그리고 다음에 n이라는 필드로 이동합니다.
작은 사소한 질문 :이 코드의 어떤 더 이상한 선에 동일합니다?
어떻게 다른이를 쓸 수 있었 을까? 자상을 원하십니까?
[학생 답 이해할 수없는]
좋아. . n을 사용하지만이 같은 매우 간단한 게 아냐.
처음 무엇을해야합니까? [학생 답 이해할 수없는]
좋아. 나는 * newptr.n을 수행해야합니다.
그래서이 새로운 포인터가 분명 주소 말하는 것입니다. 이유는 무엇입니까?
이것은 malloc에​​ 의해 반환 된 때문입니다. 말을 *의 newptr은 "거기 갈"
거기지면 그 다음에 당신이 더 친숙. n을 사용할 수 있습니다
하지만이 우리 인간에 갈 특히, 조금 추해 보이
화살표가있는 포인터 모든 시간을 그려, 세상이 화살표 표기법을 표준화 있으며,
이는 정확히 같은 일을하지 않습니다.
왼쪽에있는 것은 포인터 인 경우> 표기법 - 그래서 당신은 단지을 사용합니다.
는 실제 구조체 있다면 그렇지 않으면,. n을 사용합니다.
그리고이 : 왜 newptr -> 다음 초기화 말고 NULL 하는가?
우리는 무대의 끝 매달려 왼쪽에서 필요하지 않습니다.
우리는 바로 아래 가리켜되는데,이 목록의 끝을 의미
가능성이 노드에있을 수 있습니다, 그래서 우리는 더이 NULL인지 확인하십시오.
그리고 일반적으로 귀하의 변수 또는 데이터 멤버와 structs를 초기화
뭔가 그냥 좋은 연습입니다.
그냥 쓰레기가 존재하고 일반적으로 존재하는 계속 내버려 두는 게 문제에서 당신을 도착
당신은 나중에 뭔가를 잊어 버린 경우.
>> 여기 몇 가지 경우입니다. 이, 다시, 삽입 기능입니다
변수가 먼저 전화하면 내가 확인 우선이다
그 전역 변수가 NULL이며, 그 어떤 연결리스트가 없음을 의미합니다.
우리는 어떤 번호를 삽입하지 않은 때문에이 현재의 번호를 삽입 할 수 하찮은입니다
목록으로, 때문에 그냥 목록의 시작 부분에 포함되어 있습니다.
아니타 그냥 그런 척, 혼자 여기 서 있을때 있도록였다
우리가 노드를 할당 할 때까지 다른 사람은 무대에 여기 없었습니다
그리고 그녀는 처음으로 손을 길렀다
다른 사람들은 월요일에 그녀를 무대에 온다면.
지금 여기,이 내가 말을 좀 확인이 경우 N의 새로운 노드의 값
, 현재 첫 번째 노드에서 N의 값을 <입니다
그 시작되었습니다 연결된 목록이있는 것을 의미합니다.
이 목록에서 하나 이상의 노드는하지만이 새로운 사람
그 때문에 우리가 주변에 물건을 이동해야하기 전에 속한다.
목록, 그냥 시작하는 경우 즉,,, 말의하자
단지 숫자 17 - 사실, 우리는 더 명확하게이 작업을 수행 할 수 있습니다.
우리가 처음 불리는 포인터와 함께 우리의 이야기를 시작하면은,
그리고 처음에는 NULL이고, 우리는 9 번을 삽입
9 번 분명 목록의 시작 부분에 포함되어 있습니다.
그래서 우리는 그냥 주소 또는 9 번을 malloced 여기 넣어가 가정합시다.
먼저 기본적으로 구 경우, 우리가 논의 첫 번째 시나리오는 여기서 가자 지점이 사람을 의미합니다
이 같은 NULL 떠나, 지금 우리는 9 번을 갖추고 있습니다.
우리가 삽입 할 다음 숫자는 17입니다.
17 여기에 속한다, 우리는이를 통해 몇 가지 논리적 인 스텝을해야 할거야.
우리가의 우리가 숫자 8을 삽입하고 싶다고 가정하자 그런 짓을하기 전에 그래서 대신하자.
>> 그러므로 편의의 위해, 여기 그리는거야.
하지만 잊지마, malloc은 대부분 어느 곳을 넣을 수 있습니다.
그러나 그림, 제발 여기를 넣어드립니다.
그래서 난 숫자 8에 대한 노드를 할당 한 척,이는 기본적으로 NULL입니다.
이제 무슨 일이 있어요? 가지 정도.
우리가이 같은 포인터를 업데이트 곳 우리는 월요일에 무대에서이 실수를 한
그런 다음이 이런 짓을하고 나서 우리는 주장 - 우리는 무대에서 다른 사람들을 고아.
넌 할 수 없어 때문에 - 여기 작업의 순서는 중요합니다
지금 있기 때문에 우리는 공간에 떠 일종의 경우이 노드 9 잃었습니다.
그래서 월요일에 바로 접근 아니 었습니다.
우리가 처음 다른 뭔가를해야합니다.
세계의 상태는 다음과 같이 표시됩니다. 처음, 8가 할당되었습니다.
어떻게 8 삽입 더 나은 방법이 될 것입니다?
대신 먼저이 포인터를 업데이트 때문에, 대신에 그냥 여기에 하나를 업데이트합니다.
그래서 우리는이 NULL 문자를 설정하는거야 코드의 라인이 필요합니다
노드 9시 눈치 실제 포인터로,
그리고 우리는 안전하게 여기에서이 남자를 가리 먼저 변경할 수 있습니다.
이제 우리는 두 가지 요소의 목록을 연결리스트를 갖추고 있습니다.
그리고이 사실은 여기 어떻게 생겼나요?
우리가 코드를 보면, 나는 정확히 한 것을 확인할 수 있습니다.
나는 newptr 말했듯이,이 이야기, newptr이 사람을 지목했다.
>> 그럼 내가 한 가지가 더 그리하게, 나는 이것에 대한 좀 더 방을 떠난 거군요.
그래서 작은 그림을 용서 하소서.
이 사람 newptr라고합니다.
우리가 라인에 몇 줄 이전에 선언 된 변수 - 25 위.
그리고 8을 가리키고있어. 그래서 newptr -> 다음 말을 할 때, 구조체로 이동 의미
newptr에 의해에서 지적하는 것은, 그래서 여기 우리가 거​​기로 가봐.
그런 다음 화살표는 다음 필드를 말하는 있으며, 다음 =가 어떤 값을 넣어 있겠죠?
어떤 값은 먼저입니다;? 먼저 된 값
먼저이 이제이 노드에서 가리켜 의미하므로,이 노드에서 지적되었다.
즉, 어떻게, 내 필적이있는 우스꽝 엉망이라도 보인다
단지 주변에 화살표를 이동하는 간단한 뭐지
이 한번의 라이너로 코드 변환합니다.
다음 필드에 먼저 무엇 저장 한 후 처음으로 실제로 무엇 업데이트 할 수 있습니다.
의이 중 일부를 미리와 빨리 감기 가자,
지금이 꼬리 삽입에서만 봐.
내가 어떤 노드의 다음 필드가 NULL이라는 것을 알게 요점 가정 해 보겠습니다.
그리고 이야기, 자세히이 시점에서 난 다시 glossing 건
I 줄 142, 전신 포인터에서 다른 포인터를 도입 한 것입니다.
기본적으로 이야기의 시점에서 한 번 목록이 긴 나와서,
난 가지 두 손가락으로 걸어야겠다 너무 멀리 가면 때문에,
단일 길이 목록에서 기억, 당신은 거꾸로 갈 수 없어.
따라서 predptr의 생각이 내 왼쪽 손가락이고, newptr -하지 newptr.
여기에 또 다른 포인터가 내 다른 손가락이, 그리고 목록을 도보로 불과 했거든요.
그 존재 이유입니다. 그러나의는 여기에 간단한 사례 중 하나를 고려 보자.
그 포인터의 다음 필드가 NULL 인 경우, 논리적 함축 된 의미는 뭐죠?
이 목록을 가로 지르는하고하는 경우에는 NULL 포인터를 친거야?
당신은 목록의 끝 부분에 있어요, 코드는 다음이 하나의 추가 요소를 추가 할 수
직관적 일종의은 그의 다음 포인터 NULL입니다 노드를 취할 것입니다
그래서 현재 NULL이며, 새 노드의 주소로하지만, 그것을 변경합니다.
그래서 우리는 우리가 다른 사람의 왼손을 마련하여 무대에 그린 코드에있는 화살표를 그리기하고 있습니다.
>> 그리고 지금의 내 손을 흔들고하겠다고 경우,
난 우리가 환경의 이러한 종류의에 할 때 길을 쉽게 생각해서,
목록의 중간에 삽입을 확인합니다.
알아내는하려는 경우 그러나 단지 직관적으로, 무슨 일이 일어 났을 할 필요가
일부 번호는 중간에 속하는 곳은 걸어서해야하나요
하나 이상의 손가락으로 하나 이상의 포인터
이 검사에 의해 속한 곳을 파악하는 것은 요소 <현재 하나
> 현재 하나 한 번 당신은 그 곳을 찾아
그리고 당신은 매우 신중하게 주위 포인터를 이동 위치를 쉘 게임의 이러한 종류의 작업을 수행해야합니다.
그리고 그 대답은, 자신의 집에서이 일을 이유로하려는 경우
다운 단지 코드의 두 라인에 종기, 그러나 그 라인의 순서는 슈퍼 것이 중요합니다.
당신이 누군가의 손에 내려 제기하는 경우 다른 사람이 잘못된 순서로하고 있기 때문
다시, 당신은 목록을 orphaning 결국 수 있습니다.
더 많은 개념적으로 요약하자면, 꼬리의 삽입은 비교적 간단합니다.
머리의 삽입도 비교적 간단합니다
하지만 추가 포인터에게이 시간을 업데이트해야합니다
여기 목록에 5 번을 쥐어 짜기로,
다음 중간에 삽입 더 많은 노력을 포함하여,
매우 신중의 올바른 위치에 숫자 20를 삽입하려면,
어느 17 22 사이입니다.
당신은 22에 새 노드 20 점을 가지고있는 것처럼 일을해야하므로
다음, 노드의 포인터가 마지막으로 업데이트해야합니다?
그것은 실제로 삽입, 17 살이야.
그러니 다시 특정 구현에 대한 실제 코드를 연기합니다.
>> 언뜻보기에, 조금 압도적이지만, 그건 정말 무한 루프입니다
즉,, 루프 루프, 루프, 루프, 그리고 NULL 포인터를 누르 자마자 소멸
어떤 시점에서 당신이 필요한 삽입 할 수 있습니다.
이 후, 담당자 연결리스트 삽입 코드입니다.
, 그 많은 사람 이었어요, 우리는 한 가지 문제를 해결 한 것 같은데
하지만 우리는 전혀 다른 하나를 도입했습니다. 솔직히, 우리는이 모든 시간을 보냈어요
큰 O와 Ω에 더 신속하게 문제를 해결하기 위해 노력하고, 시간을 실행,
여기 우리는 거꾸로, 기분 큰 단계를 취하고있다.
그리고 아직 목표에 데이터를 저장하는 경우는,
우리가 월요일에 말했다대로, 성배 같은 느낌, 정말로 것
즉시 물건을 저장할 수 있습니다.
>> 사실, 우리는 잠시 동안 넣어 따로 연결리스트 짓을했다고 가정
우리는 대신 테이블의 개념을 도입했습니다.
그리고 배열로 잠시 그​​냥 테이블을 생각 보자.
이 배열이 사건은 여기서 몇 가지 요소 26, 25을 통해 0을 가지고
당신이 이름을 저장의 일부 덩어리를 필요로하는 가정
앨리스와 밥, 찰리,처럼.
그리고 당신은 그 이름을 저장하기 위해 일부 데이터 구조가 필요합니다.
글쎄, 당신은 연결리스트 같은 것을 사용할 수 있습니다
당신은 등등 밥 한 후 밥과 찰리 전에 앨리스를 삽입 목록을 걸어 수 있습니다.
그리고 사실, 당신은 옆으로 그런 식으로 코드를 보려면,
list2.h, 우리는 정확히 어떻게 알고.
우리는이 코드를 가지 않지만, 이번은 첫 번째 예제의 변형입니다
우리가 소위 학생을 본 적이 다른 구조체를 소개합니다
그리고 그런 일이 실제로 링크 된 목록에 저장하면 학생 구조에 대한 포인터입니다
보다 간단한 약간의 정수, N.
, 코드가 실제 문자열을 포함 저기 있군요 실현
하지만 손에있는 목표는 이제 정말로 효율성 문제를 해결하는 것입니다 경우,
우리가 앨리스라는 객체를 제공하는 경우가 좋지 않을까,
우리는 데이터 구조의 정확한 위치에 그녀를 넣고 싶어요
그냥 앨리스 넣어 정말 좋은 거라고 기분이,
그의 이름은 첫 번째 위치에, A로 시작합니다.
그리고 그의 이름은 두 번째 위치에, B로 시작 밥.
배열로, 또는 그것을 테이블, 그에서 해시 테이블을 호출 시작하자
우리는 정확히 할 수 있습니다. 우리가 앨리스와 같은 이름을 부여하는 경우는,
앨리스 같은 문자열, 당신은 A-L-I-C-e를 어디에 배치해야합니까?
우리는 hueristic가 필요합니다. 우리는 앨리스 같은 입력을하는 함수가 필요
와 답변을 반환, "이 위치에서 앨리스 놔."
그리고이 기능이 블랙 박스는 해쉬 함수 호출 할 것이다.
>> 해쉬 함수는 "앨리스"와 같이 입력을 필요 것이지
그리고 사용자에 대한 반환은 일반적으로 일부 데이터 구조의 숫자 위치는 앨리스가 있어야 할 곳.
이 경우, 우리의 해쉬 함수는 상대적으로 간단합니다.
우리 해쉬 함수는 당신이 문자 나에 대해 관심을 가져야 "앨리스"를 제공하는 경우라고해야하나요?
첫 번째. 그래서 [0]보​​고, 그리고 나서 [0] 문자가있는 경우, 숫자 0을 반환 말한다.
이 B면 1을 반환합니다. 그건 C 경우, 등등 2를 반환합니다.
모든 공 색인, 그 등등 저 앨리스하고 밥하고 찰리를 삽입 할 수 있으며 것
이 데이터 구조로. 하지만 문제가 있습니다.
어떤 아니타가 다시 나타나서? 경우
우리는 아니타 어디를 어떻게 삽입합니까? 그녀의 이름은도, A 문자로 시작
우리가이 문제의 더 큰 혼란을 변경 한 것과 같아.
우리는 지금 데이터 구조로 즉시 삽입, 일정 시간 삽입을 가지고
오히려 악화의 경우보다 선형,
그러나 우리는이 경우에 아니타와 함께 무엇을 할 수 있습니까?
두 가지 옵션이 정말 무엇입니까? 응?
[학생 답 이해할 수없는] 그래, 이제 또 다른 차원을 만들 수 있습니다.
좋아. 그래서 우리는 우리가 월요일에 구두로 얘기했던 것처럼 3D로 사물을 구축 할 수 있습니다.
우리는 여기에서 다른 액세스를 추가,하지만 난이 간단하게하려고했다고 가정 없었다.
여기에 전체 목표는 즉시 일정한 시간 액세스 할 수 있어야합니다
그래서 너무 많은 복잡성을 추가있어.
이 데이터 구조로 아니타를 삽입하는 다른 옵션은 무엇입니까? 응?
[학생 답 이해할 수없는 잘 됐네. 그래서 우리는 아래로 다른 사람을 움직일 수있다
그녀가 정말되고 싶은 곳에서 찰리 밥과 앨리스, 아래 nudges과 같은 우리 아니타 넣어.
>> 물론, 지금이 부작용이 있어요.
이 데이터 구조는 우리가 사람들을 한 번 삽입하고 싶지 때문에 아마도 유용합니다
하지만 우리는 그들이 나중에 거기가 있는지 확인하고 싶어서
우리가 데이터 구조의 이름을 모두 인쇄하려는 경우.
우리는 결국이 데이터에 뭔가 의미있는 일을 할 겁니다.
이제 우리는 그녀가 있어야 할 곳은 더 이상없는 앨리스를 통해 망의 종류가 있어요.
또한 밥이나 찰리 있습니다.
아마 이건 좋은 생각이 아닙니다.
그러나 실제로이 하나의 옵션입니다. 우리는 모두 아래로 이동 수
또는 대체, 아니타는 게임에 늦게, 우리가 아니타를 안 넣을거야
여긴 아니라고 여기, 여기, 그냥 목록에서 약간 낮은 그녀를 넣어 보자.
하지만이 문제는 다시 바뀔하기 시작한다.
당신은 그녀 이름에 따라 즉시 앨리스를 찾을 수 있습니다.
그리고 즉시 밥, 그리고 찰리. 하지만 당신은 아니타을 찾아
그리고 음,보고, 앨리스는 방법입니다.
음, 내 이름은 앨리스 아래 확인하자. 밥은 아니타하지 않습니다.
찰리는 아니타하지 않습니다. 아, 아니타이 있습니다.
그리고 당신은 논리의 열차 모든 방법을 계속하는 경우
이 새로운 데이터 구조로 찾거​​나 아니타를 삽입의 최악의 실행 시간은?
그것은 바로, O (n)이있어?
최악의 경우에 속하기 때문 앨리스, 밥, 찰리가 있습니다. . .
모든 "Y"라는 사람에게 내려, 그래서 하나의 자리가 남았습니다.
다행히, 우리는 "Z"라는 사람도없고, 그래서 우리가 맨 아래에 아니타 넣어.
>> 우리가 정말이 문제를 해결하지 않았습니다.
따라서 우리는이 3 차원을 도입 할 필요는 없어.
우리가이 3 차원을 도입 않는 경우 그리고, 밝혀
우리는 완벽하게이 작업을 수행 할 수 없지만, 성배가별로 될 것입니다
일정한 시간 삽입 및 동적 삽입이 있으므로
우리는 크기 26 하드 코드 배열 할 필요가 없습니다.
우리가 원하는 우리는 많은 이름으로 삽입 할 수 있지만, 우선은 여기 5 분 휴식을
그리고 제대로 해.
괜찮아요. 난 정말 인위적가 이야기를 설정
앨리스하고 밥하고 찰리 후 아니타를 선택하여
그의 이름은 분명 앨리스과 충돌하려고 했어요.
그러나 우리가 월요일에 종료 문제는 단지 얼마나 가능성이
당신이 가지 충돌을 것이라고? 즉,
우리가이 표 구조를 사용하기 시작하면되는데,이, 정말 배열입니다
26 지역의 경우,
우리의 입력 대신 균일하게 배포하는 경우 무엇입니까?
그것은 인위적으로 앨리스와 밥, 찰리, 데이비드 아닙니다 등등 순으로,
그것은 균일 Z.을 통해 통해 배포 있어요
>> 어쩌면 우리는 운 좋으면 우리는 두의 또는 두 개의 B의를 할 수 없어
누군가가 지적, 매우 높은 확률로하지만,로
우리 일반화이 문제가 아니라 그렇게하면 0-25
하지만, 말, 0 364이나 65, 전형적인 년의 일 종종 수,
그리고 질문을 "이 방에있는 우리 둘은 같은 생일을 가지고있는 확률은 무엇입니까?"
또 다른 방법을 넣어, 확률 우리 둘은로 시작하는 이름을 가지고 뭐​​죠?
질문의 종류는 동일하지만,이 주소 공간
이 검색 공간, 생일의 경우 더 큰
우리는 알파벳의 문자보다 년에 너무 많은 일이 있기 때문.
충돌의 확률은 무엇입니까?
음, 우리는 수학에게 반대 방법을 계산하여 생각할 수 있습니다.
노 충돌의 확률은 무엇입니까?
자, 여기이 표현은 어떤 확률 래요
그들은 독특한 생일이 방에 한 사람은이 있다면?이
그것은 100 %입니다. 때문에 방에 한 사람이 있다면,
자신의 생일 년에 365 일의 모든 수 있습니다.
따라서 365분의 365 옵션은 나에게 하나의 값을 제공합니다.
따라서 현재 문제의 확률은 1입니다.
그러나 방에 두 사람이있을 경우,
자신의 생일과는 다른 것입니다 확률은?
단 364 수 일, 무시 도약 년가 있어요
자신의 생일에 다른 사람과 충돌 할 수 없습니다.
따라서 365분의 364. 다른 사람을 와서는 경우, 등등 365분의 363 야합니다.
그래서 우리는 작아지고있는이 분수를 함께 곱한 유지
알아내는 우리 모두가 독특한 생일을 가지고있는 확률은 무엇입니까?
하지만 우리는 물론, 그 대답을하고 주변을 뒤집어
그 1 마이너스 모두, 우리는 결국 얻을 것 표현식을
귀하의 수학 책의 뒷면을 기억 경우,이 같은 뭔가를 조금 보입니다
어떤이 훨씬 더 쉽게 그래픽으로 해석됩니다.
그리고 여기이 그림은 X 축에 생일의 수를 가지고
이나 생일 파티를 가진 사람들과 Y 축의의 번호와 일치의 확률입니다.
그리고이 말하는 건, 당신이 경우에도, 보자 것입니다
의 22, 23과 같은 무언가를 선택할 수 있습니다.
방에있는 22 또는 23 명이이 있다면
이 매우 소수의 사람들 만 두가 같은 생일을 가야하는 확률
combinatorially, 실제로 슈퍼 높습니다.
50 % 확률이 거의 이제 22 명 세미나의 수업에
사람들 2 같은 생일을 가지고 갈 수 있습니다.
때문에 같은 생일을 가질 수있는 많은 방법이 있습니다.
더 나쁜 것은, 당신이 차트의 오른쪽 보면,
시간에 당신은 거기에 58 학생들과 함께 수업을
생일을 갖는 2 인 확률은 슈퍼, 슈퍼 높이 거의 100 %입니다.
자, 실제 생활에 대한 재미있는 사실의 일종 이죠.
>> 그러나 의미는, 이제, 데이터 구조 및 저장 정보
당신의 데이터 멋진, 깨끗하고 균일 한 분포를 가정 있다는 것을 의미
당신은 사물의 무리에 맞는 충분히 큰 배열을 가지고
당신은 고유 한 위치에있는 사람을 만나게 될 거예요 의미하지 않는다.
당신은 충돌을 할 겁니다. 때 이름으로, 해시의 개념 그래서
"앨리스"와 같은 입력을 복용하고 어떤 방법에 마사지
그리고 0 또는 1 또는 2와 같은 답변을 다시 받고.
그 기능의 일부 출력을 다시 얻기 것은 충돌의 확률에 감염되어 있습니다.
그럼 우리는 그 충돌을 처리 할 수​​ 있습니까?
음, 한 사건에, 우리는 제안 된 아이디어를 취할 수 있습니다.
우리는 좀 더 간단하게, 어쩌면 모든 사람을 이동하거나, 수
차라리 다른 이동 사람들보다, 그냥 사용할 수있는 곳의 맨 아래에 아니타를 이동 보자.
앨리스가 0에하면, 밥은 1이며, 찰리는 2에
우리는 위치 3시 아니타을 올려 놓을 게요.
그리고이 프로빙 선형이라는 데이터 구조의 기술입니다.
당신은이 줄을 걸어, 당신은 프로빙의 일종이야 선형 때문에
데이터 구조에서 사용할 수있는 장소에.
물론,이 O (N)에 devolves.
데이터 구조가 정말 가득 경우, 25 사람들은 이미이
그리고 아니타이 클 그녀는 위치 Z는 무엇입니까 쳐다 끝내고, 괜찮아요.
그녀는 여전히 맞는, 우리는 나중에 그녀를 찾을 수 있습니다.
>> 하지만이 일을 속도의 목표에 반하는했다.
우리가 대신이 3 차원을 도입 어쩌죠?
그 기술은 일반적으로 별도의 체인이라고, 또는 체인을 가지고 있습니다.
그리고 해시 테이블은 이제이 표 구조하는 일
테이블은 포인터의 배열입니다.
그런데 그 포인터가 가리키는 것은 추측 무엇입니까?
연결 목록입니다. 우리는이 세계의 모두의 가장을 어쩌죠?
우리는 초기 인덱스에 배열을 사용하여
데이터 구조로 그래서 우리는 즉시, [1], [30] 또는 등등 [0]로 이동할 수 있습니다
하지만, 우리는 유연성을 가지고 우리는 아니타와 앨리스와 아담에 맞게 수
및 기타 이름,
우리는 대신 다른 축이 임의의 성장 보자.
그리고 우리는 결국 월요일로 연결된 목록과 그 표현 기능이 있습니다.
우리는 임의로 데이터 구조를 증가 할 수 있습니다.
또한, 우리는, 큰 2 차원 배열을 만들 수
하지만 그 경우 끔찍한 상황이 될거에요 2 차원 배열의 행 중 하나
그의 이름은 A.으로 시작하는 일이 추가 사람만큼 큰되지 않습니다
맙소사 우리는 거대한 2 차원 구조를 할당해야
라는 많은 사람들이있어해서
Z 뭔가라는 이름 때문에 몇 사람이 특히.
이건 그냥 아주 희박한 데이터 구조 될거야.
그럼 어떤 방법으로, 완벽 하진 않지만 이제 우리는 적어도 수 있습니다
앨리스 나 아니타가 있어야 할 곳 바로 찾으려면
적어도 수직 축 측면에서,
그리고 우리는이 연결 목록에서 아니타 또는 앨리스 넣어 위치를 결정해야합니다.
우리가 일을 분류 상관하지 않는 경우, 얼마나 빨리 우리는이 같은 구조로 앨리스를 삽입 할 수?
이 상수 시간이다. [0]에 우리는 색인, 아무도 거기에,
앨리스는 연결리스트의 시작 부분에갑니다.
하지만 그건 큰 문제가 아니에요. 아니타는 함께 온다면 때문에
몇 가지 단계 수 후 아니타는 어디에 속해 있습니까?
음, [0]. OOP. 앨리스는 그 링크는 이미 목록에 있습니다.
>> 그러나 우리는이 이름을 정렬인지를 신경 쓰지 않을 때는,
우리는 앨리스 이상, 삽입 아니타을 이동할 수 있지만 심지어는 일정 시간입니다.
앨리스와 아담과 전혀 다른 이름,이 경우에도
정말 물리적으로 이동 않아. 이유는 무엇입니까?
우리가 알고있는 연결 목록과 함께했기 때문이 노드 근데거야?
당신이해야 할 모든 빵 부스러기를 이동합니다.
주위에 화살표를 이동, 당신은 실제로 주위에 데이터를 이동할 필요가 없습니다.
그래서 우리는 즉시 그 경우, 아니타를 삽입 할 수 있습니다. 상수 시간.
그래서 우리는 일정 시간 조회 및 아니타 같은 사람의 일정한 시간 삽입되어 있습니다.
그러나 세계를 지나치게 단순화 종류의.
우리가 나중에 앨리스를 찾으려면?
얼마나 많은 단계 그건 걸릴까요?
[학생 답 이해할 수없는]
그렇지. 연결리스트의 앨리스하기 전에 사람들의 수.
우리의 데이터 구조, 다시이 수직 액세스 할 수 있기 때문에 그래서 아주 완벽 하진
다음은 교수형이 연결된 목록을 가지고 - 사실, 그렇게 배열을 그려하지 맙시다.
그것은이 연결 목록과 같은 작은 선물을 보이는 그것을 매달려있다.
하지만 문제는 경우 Alice와 아담과 모든 다른 이름
거기 더 살게
누군가가 단계 많이 복용 결국 수 찾기,
당신이 연결된 목록을 통과해야 bcause
이는 선형 작업입니다.
그래서 정말 다음, 삽입 시간은 궁극적으로 n은 목록에있는 요소의 개수입니다 O (n은)입니다.
으로 나눈 값, 어디 임의로 그 m은 링크 된 목록의 번호입니다 m, 전화 할게
우리는이 수직 축에 있다고.
즉, 우리가 진정으로 이름의 균일 한 분포를 가정하면,
완전히 비현실적인. 다른 사람보다 몇 글자 분명 더있어.
>> 하지만 우리는 지금 균일 분포에 대한 가정하면,
우리는 총 사람, m 총 체인 습니했습니다
이러한 체인 각각의 우리에게 다음 길이
공정 단순히 총 N 체인 수로 나눈 될 것입니다.
따라서 N / m. 우리 모두가 수학적으로 영리 할 수​​있는 그러나 여기입니다.
이들의 고정 된 번호가 있기 때문에 m은 상수입니다.
당신은 시작에서 배열을 선언 할거야
우리는 크기 조정 세로 축을 아니에요. 정의함으로써, 고정 유지됩니다 그.
정말 변경 것은, 이야기 만 가로 축입니다.
따라서 엄밀히 말해서,이 상수입니다. 그래서 지금, 삽입 시간
거의 O (n)이됩니다.
그럼이 모든 것을 훨씬 더 기분이되지 않습니다.
그러나 진실은 뭐죠? 음,이 시간, 주,
우리는 말한 적 O (N ²). O (N), 2 X N ², - N, 2로 나눈 값입니다. . . 르샤.
단지 N ²입니다. 하지만 지금은 학기의이 부분에
우리는 다시 현실 세계에 대해 얘기를 시작할 수 있습니다.
그리고 N / m 혼자 습니보다 절대적으로 빠릅니다.
당신은 이름이 수 천 개를 가지고 있고, 여러 개의 버킷으로 올려 어기면
당신은 이러한 체인의 각 단 10 이름이 있도록
절대적으로 열 가지를 검색하면 수천 가지보다 더 빨리 될 것입니다.
그리고 다가오는 문제 세트 중 하나에 도전 것입니다
정확히 그것에 대해 생각해하더라도, 그래,
점근 적 및 수학적으로이 아직도 선형이며,
것을 발견 할 때 이는 일반적으로됐다.
현실에서, 그보다 더 빨리 될거야
이 때문에 제수의.
그리고 다시 트레이드 오프가 되려고하고 있어요
그리고 이론과 현실 간의 갈등,
그리고 손잡이 중 하나는 학기에이 시점에서 회전을 시작합니다
우리가 약간 semster의 최종 준비로 현실 하나의 이상이며,
우리는 웹 프로그래밍의 세계를 소개로
사용자가로 갈거야 왜냐면, 정말로 성능이 셀 것입니다
가난한 디자인 결정을 느끼고 감사하기 시작한다.
>> 당신은 링크를 구현하는 일은 정말 어떻게해야할까요 - 해시 테이블을 31 요소와?
그리고 앞의 예는 생일에 대해 임의로이었다.
사람이 1 월 1 2월 1일의 생일이있는 경우, 우리는이 양동이에 넣어드립니다.
가 1 월 2 년 2 월 2 일 3월 2일면, 우리는이 양동이에 넣어드립니다.
가 31 살 이유입니다. 어떻게 해시 테이블을 선언합니까?
그것은 꽤 간단 될 수 노드 * 표는 그것을 위해 내 임의의 이름, [31]입니다.
이것은 노드에 저에게 31 포인터를 제공합니다
이 날 링크 목록 31 포인터를 할 수 있도록
그 사슬에서 처음 NULL 경우에도.
제가 저장하려는 경우 "밥", "찰리" "앨리스"를 넣어 원하는 게 뭐야?
음, 우리는 구조에서 그 물건을 포장 할 필요가
우리는 앨리스, 밥을 가리 키도록 찰리을 가리 키도록, 등등. 필요 하거든요
우리는 단지 혼자의 이름을 가질 수 없습니다, 그래서 여기 노드라는 새로운 구조를 만들 수 있습니다.
>> 실제 노드는 무엇입니까? 이 새로운 연결 목록에서 노드는 무엇입니까?
단어라고 첫 번째 문제는, 그 사람의 이름입니다.
길이는, 아마, 인간의 이름의 최대 길이에 관한
그게 무엇이든, 20, 미친 코너의 경우 30, 40 문자
그리고 한 무엇입니다? 그것은 단지 여분의 NULL 문자, \ 0입니다.
그래서이 노드는 내부 자체의 "무언가"를 배치하고 있습니다
뿐만 아니라 옆에라는 포인터를 선언
우리가 찰리 밥 체인 앨리스 수 등등 그.
NULL이 될 수 있지만 반드시 할 필요는 없습니다.
이 해시 테이블에서 질문? 응?
[학생 이해할 수없는, 질문을] 배열 - 좋은 질문입니다.
왜 배열보다는 숯불 *이 숯불 단어는?
이 다소 임의의 예에서, 나는 의지하고 싶지 않았어
원래 이름의 각 malloc합니다.
나는 문자열 메모리의 최대 양을 선언하고 싶어
난 앨리스 \ 0이 아닌이 malloc과 무료 등 처리해야하는 구조로 복사 할 수 있도록.
나는 공간 사용을 더 의식되고 싶어한다면 난 할 수있어. 좋은 질문입니다.
그래서 멀리 일반화하려고 두자
더 일반적으로 데이터 구조에서 오늘의 나머지 부분에 초점을
우리는 같은 기본을 사용하여 해결할 수있는 다른 문제
심지어 데이터 구조 불구하고 자신은 세부 사항에 다를 수 있습니다.
>> 따라서 컴퓨터 과학에서 밝혀, 나무는 매우 일반적이다.
그리고 당신은 가족 나무처럼의 나무 종류 생각할 수
일부 뿌리, 일부 암컷 대장 또는 가장이있는 곳
할머니 나 할아버지 또는 이전 버전으로 돌아
어떤 아래에 엄마, 아빠 또는 여러 형제 자매 또는 마음입니다.
따라서 트리 구조 노드를 가지고 있으며 아이들이
각 노드에 대해 일반적으로 0 또는 더 많은 아이들.
그리고 전문 용어의 일부가 여기이 그림에 표시되는
이 가장자리에있는 작은 아이들이나 손자들의
누가 그들에서 냄새가 나는데도 화살표가 없습니다
그는 소위 잎, 그리고 내부에있는 사람 아르
내부 노드입니다, 당신은 그것을 그 라인을 따라 뭔가를 호출 할 수 있습니다.
그러나이 구조는 매우 일반적입니다. 이 녀석은 좀 임의입니다.
우리는 우리가 오른쪽에 세 명의 아이가, 왼쪽에서 한 아이가
아래에 두 아이들은 떠났다.
그래서 우리는, 우리가 일을 표준화하기 시작하면 다른 크기의 나무가 있지만, 수
그리고 당신은 이전 짧은에서 이진 검색 패트릭의 동영상에서이 기억 수도 있습니다
온라인 이진 검색 배열 구현하실 필요가 없습니다
칠판에 종이 또는 조각.
당신은보다 정교한 데이터 구조에 번호를 저장하고 싶어하고 있다고 가정합시다.
이 같은 나무를 만들 수 있습니다.
당신은 C에 선언 노드를 가질 수 있으며, 해당 노드 안에 그것의 적어도 두 개의 요소를 가질 수 있습니다.
하나는 당신이 저장할 수 있으며, 다른 하나는 - 글쎄, 우리는 하나가 더 필요합니다.
다른 하나는 그 자식입니다.
그래서 여기가 다른 데이터 구조입니다. 이 시간은, 노드는 N 번호를 저장로 정의됩니다
그리고 후 두 포인터, 왼쪽 자녀 및 오른쪽 아이.
그리고 임의 아니에요. 어떻게이 나무에 대한 재미있는이야?
>> 우리가 패트릭가 비디오에 배치하는 방법이 배치하거나 한 방법에 패턴은 무엇입니까?
그것은 이곳에서 몇 가지 분류가 그런 종류의 확실
하지만 간단한 규칙이 뭐지? 응?
[학생 답 이해할 수없는]
좋아요. 이 흘끗 경우, 당신은 왼쪽에있는 작은 숫자를 참조하십시오
큰 왼쪽에있는 숫자,하지만 모든 노드에 대한 사실입니다.
각 노드를 들어,보다는 자사의 왼쪽 아이가 덜하고,보다 권리의 자녀가 더.
전 그 번호 44, 말,이 데이터 구조를 검색하려면이게 지금 의미하는 것은,
나는 왜냐하면 지금이 더 복잡한 데이터 구조의 모든과 마찬가지로, 루트에서 시작해야
우리는 처음, 한 가지에 대한 포인터가 있습니다.
이 경우에는 처음의 루트입니다. 그것은, 왼쪽 끝이 아니야
만약이 구조의 루트입니다. 그래서 여기 55입니다보고 싶어하지만 난 44 찾고 있어요.
어떤 방향으로 가야할까요?
분명, 오른쪽으로 너무 좋을 것 때문에 음, 왼쪽으로 가고 싶어요.
그래서 여기 발견, 당신은 개념적 반으로 나무를 자르고의 일종이야
당신은 오른쪽 아래로 못하실 거예요 때문입니다.
그래서 지금은 55에서 33로 이동합니다. 이 숫자의 너무 작아.
나는 44을 찾고 있는데, 지금은 44이 나무에있는 경우, 오른쪽에 분명 갈 수있어.
그러니 다시 치기 절반으로 나무입니다.
이 전화 번호부에 개념적으로 거의 동일입니다.
그것은 우리가 칠판에 종이로 무슨 짓을하고 똑같아요
하지만 우리가 실제로 할 수있는보다 정교한 구조 네요
이, 나눠서 알고리즘의 설계에 의해 정복
그리고 사실, 이와 같은 구조를 가로 지르는 - 아하하.
이와 같은 구조를 가로 지르는 것은, 그 밖에 어디 "이 길을 갈거나 길을 갈"
섹션에서 구현할 때 처음에는 마음을 굽어 모든 코드를 의미
또는 재귀 또는 반복을 사용하여, 이진 검색, 집에서 그것을 통해 도보
그것은 목에 통증이 있습니다. 중간 요소를 찾기 다음 라운딩 위로 또는 아래로 해.
>> 우리가 다시 재귀를 사용할 수 있기 때문에 아름다움이 할 필요가
하지만 훨씬 더 깔끔하게. 사실, 당신이 55 번에이고 44를 찾으려면,
이 경우 왼쪽으로가는 다음 어떻게해야하나요? 당신은 동일한 알고리즘을 실행합니다.
당신은 노드의 값을 확인 한 다음 왼쪽 또는 오른쪽으로 이동합니다.
그런 다음 왼쪽 또는 오른쪽으로 이동하여 노드의 값을 확인하십시오.
이것은 완벽하게 재귀에 적합합니다.
그래서,하지만 과거에 우리는 재귀를 포함한 몇 가지 매우 임의의 예제를 했어요
즉, 데이터 stuctures과 재귀 할 필요가 없었다
특히 나무, 이건 문제가 복용의 아이디어의 완벽한 응용 프로그램입니다
를 축소 한 다음, 같은 종류의,하지만 작은 프로그램을 해결.
>> 그래서 우리가 도입 할 수있는 다른 데이터 구조가 있습니다.
이 하나는 암호화 살펴 한눈에 설계,이 하나는 놀라워하고 있습니다.
그래서이는 단어 검색에서 상속 trie, trie라는 데이터 구조입니다
이는 다시 시도 - 발을 발음,하지만 그건 세상은 이런 것들을 부르는되지 않습니다. 시도합니다. T-R-I-5.
그것은 일종의 트리 구조이지만, trie의 각 노드
모습을? 이 축약 종류이기 때문에이 조금 잘못된 것입니다.
그러나이 trie의 각 노드가 실제로 배열입니다 것 같습니다.
그리고 비록이 그림의 저자를 표시하지 않았습니다
이 경우,이 trie는 그 목적 생활에 단어를 저장하는 것입니다 데이터 구조입니다
A-L-I-C-E 또는 B-O-B처럼.
그리고 그 길을 어떤에서 등등이 데이터 저장 앨리스와 밥, 찰리, 아니타와
그것은 trie의 앨리스를 저장하는 상기 배열을 사용합니다
우리는 배열처럼 보이는 루트 노드에서 시작
그리고 그것은 속기 표기법으로 기록되어있어.
그게 더 이름이 없었 때문에 저자는 abcdefg 생략.
그들은 단지 M과 P와 T를 갖게했지만이 경우
의는 여기에 일부 이름에 떨어진 앨리스와 밥과 찰리 이동하세요.
맥스웰이 다이어그램에서 실제로 있습니다.
그럼 저자 저장소를 한 M--X-w-E-L-리터?에게
그 또는 그녀는 루트 노드에서 시작, 그리고에 가서 [M], 그래서 대략 13, 배열의 13 위치.
그런 다음 거기에서, 포인터가 있습니다.
다른 배열로 이어지는 포인터.
그곳에서 저자는, 왼쪽 상단이 묘사로, 위치에 그 배열로 인덱스
그리고 그 또는 그녀가 다른 배열에 해당 포인터를 따라
및 위치 X.에서 포인터에 가서
그런 다음 등등 다음 배열 위치 W, E, L, L, 및에
마지막으로,의 사실이에 사진을 넣어 봅시다.
코드에서 같은 노드 모습은 무엇입니까?
trie에있는 노드가 더 많은 노드에 대한 포인터의 배열을 포함하고 있습니다.
뿐만 아니라 적어도 구현에서, 부울 값 어떤 종류의이있어.
나는 is_word 전화 발생합니다. 이유는 무엇입니까?
당신은 맥스웰를 삽입 할 때, 당신은 삽입하지 않으니까
이 데이터 구조에 무엇이든.
귀하는 X를 작성하지 M.를 작성하지
당신이하고있는 모든 포인터 다음과 같은 것입니다.
다음 M, A를 나타내는 포인터를 나타냅니다 포인터
다음엔 X, W, E, L, L을 나타냅니다 포인터
하지만 니가 마지막에 할 필요 체크인, 가지의 종류이며,이 위치에 도달했습니다.
데이터 구조에 여기에 끝나는 단어가 발생했습니다.
>> 그래서 trie에 정말 가득하고 저자는 대표 선택합니다
작은 삼각형을 통해 이러한 terminuses.
사실이 그저 사실은이 삼각형 여기 있다는 것을 의미,이 부울 값
이 트리에서 뒤로 이동하면,
그 맥스웰이에라는 단어를 의미합니다.
예를 들어,하지만 단어 foo는,
, 트리에없는 제가 맨 위에 여기에 루트 노드에서 시작하면,
더 F 포인터, 아니 오 포인터, 아니 오 포인터가 없습니다. foo는이 사전의 이름이 아닙니다.
그러나 반대로, 튜링, t-U-R-I-N-g. 다시, 나는 t 또는 u 또는 R 또는 I 또는 n 또는 g를 저장하지 못했습니다.
하지만 여기이 노드의 진정한 방법의 값이 데이터 구조에 저장 짓을 - 트리에서
true로 is_word이 Boolean 값을 설정하여.
그래서 trie이 매우 흥미로운 메타 구조의 종류입니다
당신은 정말 사전 이런 종류의 단어 스스로를 저장하지 곳.
명확하게하려면, 당신은 단지 예, 아니오로 저장하지 마, 여기에 끝나는 단어가 있습니다.
>> 이제 의미가 뭐야?
당신은 메모리에 저장하기 위해 노력하는 사전 150,000 단어가있는 경우
연결리스트 같은 것을 사용하여
귀하의 링크 목록에서 150,000 노드를 갖게 돼있다.
그리고 알파벳 순으로 단어 중 하나를 찾는 것은 O (n)이 시간이 걸릴 수 있습니다.
선형 시간. 그러나 trie의 여기 경우에,
단어를 찾는 실행 시간은?
여기의 아름다움을 밝혀 즉 당신은 이미 사전에 149,999 단어를 경우에도
본 데이터 구조를 구현,
에 앨리스 같은 앨리스 한 사람을 찾거나 삽입 할 시간이 얼마나 걸립니까?
음, 뒤에 캐릭터 어쩌면 6 단계, 5입니다.
때문에 구조에있는 다른 이름의 presense
앨리스를 삽입의 방법으로하지 않습니다.
또한, 앨리스를 찾는 것이이 사전의 150,000 단어가 있습니다되면
모든의 앨리스를 찾는 당신의 방식으로하지 않습니다
앨리스는 때문입니다. . . . . 여기 때문에 Boolean 값을 발견했습니다.
그리고 더 부울 사실, 그리고 앨리스가없는 경우 단어의 데이터 구조에 포함되어 있지 않습니다.
즉,이 새에 물건을 물건을 발견하고 삽입의 실행 시간
trie의 데이터 구조의 O입니다 - 그것은 습니 않아.
150,000명의 presense 앨리스에 아무런 영향을 미치지 않기 때문에, 그것은 보인다.
의는 K 영어 단어의 최대 길이입니다 K, 전화 놔
이는 일반적으로 더 이상 20 일 문자보다 수 없습니다.
따라서 k는 상수입니다. 성배 그래서 우리가 지금 발견 한 것 같습니다
삽입물에 대한 trie, 일정한 시간이 그 삭제에 대해 조회를 들어, 수 있습니다.
때문에 이미 구조의 가지 수,
이는 물리적으로도이 없습니다. 다시 말하지만, 그들은 단지 확인란의 선택이 해제되어 분류하고 예, 아니오
미래 실행 시간에 아무런 영향을 미치지 않습니다.
>> 그러나 캐치있을거야, 그렇지 않으면 우리는 많은 시간을 낭비하지 않았을
모든 다른 데이터 구조에 불과 드디어 놀라운 비밀 하나를 얻을 수 있습니다.
그래서 가격이 우리가 여기이 위대함을 달성하기 위해 지불? 공간.
이 것은 엄청난 것입니다. 그리고 그 이유 그 저자
여기에 제시되지 않았 눈치 배열과 같이이 모든 일 즉,
그는 나무의 나머지 trie의 나머지를 그린 적 없어요
그냥 이야기와 관련이없는니까.
하지만이 노드의 모든 다양한 슈퍼 있으며, 트리의 모든 노드가 걸립니다
26 사실,이 경우에는 나는 아포스트로피를위한 공간을 포함했기 때문에 27 문자 일 수도
그래야 우리가 apostrophized 단어가있을 수 있습니다.
이 경우, 이것들은 다양한 배열입니다. 그들은 picutured되지 않도록하더라도,
이 RAM의 거대한 양을 차지한다.
어떤 현대적인 하드웨어에서 especilly, 괜찮아 질 거라고
하지만 그게 거래 때문이에요. 우리는 더 많은 공간을 소비하여 짧은 시간을.
어디이 모든거야?
그럼, 한번 해보자 구 - 여기 보자.
여기이 남자 점프를하자.
>> 믿거 나 말거나, C, 지금 약간의 시간에 대한왔다만큼 재미 있고,
우리는 더 많은 현대적인 것들로 전환 할 시간이 다예요 학기의 지점에 도달하고 있습니다.
높은 수준의 것들. 그리고 앞으로 수주에 대한하지만
우리는 여전히 포인터와 메모리 관리의 세계에 자신을 빠져 계속해서
우리가 다음에 구축 할 수있는 그 편안함을 얻으려면,
최종 게임이 언어, 아이러니하게도, 아니 소개하는 궁극적입니다.
우리는 HTML에 대해 얘기 10 분 거리, 지출됩니다.
HTML이 모든 마크 업 언어입니다, 그리고 마크 업 언어입니다
'이 일이 굵게'라고 오픈 브래킷과 닫힌 괄호 이러한 일련의
'이 중심을'이 기울임 꼴 만들기 '.'
이 모든 지적 재미있는 건 아니지만, 유용 됐네요.
그리고 확실히 요즘 편재입니다.
하지만 어떻게 HTML의 세계에 대한 강력한, 그리고 웹 프로그래밍 더 일반적으로,
동적 물건을 구축하고있다, PHP 나 파이썬이나 루비 또는 Java 또는 C #과 같은 언어로 코드를 작성.
정말, 무슨 일이든 선택의 당신의 언어가 있으며, 동적 HTML 생성.
동적으로 CSS라는 것을 생성.
캐스 케이 딩 스타일 시트, 미학에 관한 것입니다.
그리고 심지어, 오늘, 나는 알고 Google.com 같은 웹 사이트로 이동하는 경우
그래서, 아마도 당신은 전에했던 개발자, 소스보기,보기로 이동
하지만 소스를 볼 것,이 물건은 아마도 꽤 이상한 보입니다.
그러나 이것은 Google.com을 구현하는 기본 코드입니다.
프런트 엔드에서. 그리고 실제로이 모든 상황이 보송 보송 한 미학의 콘텐츠입니다.
이 여기에 CSS 달려 있습니다. 난 스크롤을 유지하는 경우 몇 가지 색으로 구분되는 물건을받을 수 있습니다.
이 HTML입니다. Google의 코드는 엉망처럼 보이지만 사실은 다른 창을 열면
우리는이에 몇 가지 구조를 볼 수 있습니다.
제가이 일을 열 경우 여기를 발견, 좀 더 읽기입니다.
우리는 오래 전부터이 태그를 만나러가는 중이 야, [단어] 태그입니다,
HTML, 머리, 몸, 사업부, 스크립트, 텍스트 영역, 기간, 중심 사업부.
그리고이 또한 한눈에 알 수없는 수준의 정렬되어 있습니다
하지만이 난장판 모든 특정 패턴 및 반복 패턴을 다음과
일단 기본을 내려 있도록이 같은 코드를 작성 할 수 있습니다
그리고 자바 스크립트라는 또 다른 언어를 사용하여이 같은 코드를 조작.
그리고 자바 스크립트는 브라우저의 내부 실행 언어입니다
Google은 Google지도에서 사용하는 코스 쇼핑 도구에 하버드 과정에 사용하는 오늘날
당신에게 동성의 전체 무리를 제공하기 위해 페이스 북은 인스턴트 상태 업데이트를 표시 할 수 있습니다
트위터는 즉시 당신에게 트윗을 보여을 사용합니다.
이 모든 우리는 우리 자신을 인치 빠져을 시작합니다
그러나 거기에 도착하기 위해 인터넷에 대해 좀 이해할 필요가있다.
여기에 클립이 그저 분 거리에 있습니다, 지금이은, 사실 가정합시다하면,
인터넷 올 관한 일에 대한 티저로 작동하는 방식. 당신에게 "인터넷의 전사를."제공
>> [♫ 느린 합창 음악 ♫]
[남성 나레이터] 그는 메시지와 함께.
프로토콜 모두 자신이 있습니다.
[♫ 빠른 전자 음악 ♫]
그는 라우터 무관심한, 멋진 방화벽의 세계에 온
죽음보다 훨씬 더 위험.
그는 빨라요. 그는 강한입니다. 그는 TCP / IP이고, 그는 주소를 있어요.
인터넷의 전사.
[Malan] 다음 주, 그럼. 인터넷. 웹 프로그래밍. 이 CS50입니다.
[CS50.TV]