1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [주 6 일 계속]

2
00:00:02,520 --> 00:00:04,160
[데이비드 J. Malan] [하버드 대학]

3
00:00:04,160 --> 00:00:08,720
[이 CS50 수 있습니다.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
이 CS50이며,이 주 6의 끝입니다.

5
00:00:12,970 --> 00:00:17,970
따라서 CS50x, edX 이니셔티브에 참여 하버드 최초의 코스 중 하나

6
00:00:17,970 --> 00:00:20,590
실제로 지난 월요일 데뷔했다.

7
00:00:20,590 --> 00:00:23,460
당신은 인터넷에서 어떤 다른 사람의 모습을하고 싶으 시다면

8
00:00:23,460 --> 00:00:27,180
지금와 함께 다음 아르, 당신은 x.cs50.net에 참가할 수 있습니다.

9
00:00:27,180 --> 00:00:30,350
즉, edx.org에 적절한 장소로 리디렉션합니다

10
00:00:30,350 --> 00:00:34,160
이것과 MIT와 버클리에서 다른 코스가 지금 살고있는 곳이었다.

11
00:00:34,160 --> 00:00:38,140
당신은 계정에 서명을해야합니다, 당신은 물질이 대부분 동일 찾을 수 있습니다

12
00:00:38,140 --> 00:00:42,170
당신은 우리가 모든 준비로 지연 몇 주이라도, 이번​​ 학기에했다. 한로

13
00:00:42,170 --> 00:00:46,930
그런데 CS50x의 학생들이 지금은 볼 수는 상당히 이와 같은 인터페이스입니다.

14
00:00:46,930 --> 00:00:50,040
이 예를 들어, 문제 세트 0 튜토리얼을 주도 Zamyla입니다.

15
00:00:50,040 --> 00:00:54,230
edx.org에 로그인 후, CS50x 학생은 일의 종류를 볼 수

16
00:00:54,230 --> 00:00:57,170
당신은 과정에 보여야하는데 : 월요일 강의를

17
00:00:57,170 --> 00:01:01,650
수요일, 다양한 반바지, 문제 세트, 연습, PDF 파일에 대한 강의.

18
00:01:01,650 --> 00:01:04,459
또한, 당신이 여기서 보는 것처럼, 기계 번역

19
00:01:04,459 --> 00:01:08,390
, 이탈리아어, 스페인어, 일본어, 중국어로 영어 성적

20
00:01:08,390 --> 00:01:12,810
확실하게 불완전한 것입니다 다른 언어와 전체 무리

21
00:01:12,810 --> 00:01:15,840
우리는 API라는 걸를 사용하여 프로그램을 출시로

22
00:01:15,840 --> 00:01:18,360
Google에서 또는 응용 프로그램 프로그래밍 인터페이스,

23
00:01:18,360 --> 00:01:21,360
그것은 우리가 이러한 다른 언어 영어로 변환 할 수 있습니다.

24
00:01:21,360 --> 00:01:24,100
하지만 일부 100 플러스 자원 봉사자들의 아름다운 정신 덕분에,

25
00:01:24,100 --> 00:01:26,940
친절 참여 제의 인터넷에서 무작위 명

26
00:01:26,940 --> 00:01:30,180
이 프로젝트에, 우리는 서서히 그 번역의 질을 향상됩니다

27
00:01:30,180 --> 00:01:35,790
인간이 우리의 컴퓨터가 만든 한 실수를 수정하지로.

28
00:01:35,790 --> 00:01:42,330
>> 우리가 몇 학생들은 우리가 처음 예상했던 것보다 월요일에 표시 한 아웃 그게집니다.

29
00:01:42,330 --> 00:01:48,980
사실, 지금 CS50x 집에서 함께 따라 십만명이 있습니다.

30
00:01:48,980 --> 00:01:54,430
따라서 컴퓨터 과학에서이 과정을이 창립 클래스의 일부입니다 실현

31
00:01:54,430 --> 00:01:57,370
더 일반적으로 교육, 더 넓게, 액세스 할 수 있습니다.

32
00:01:57,370 --> 00:02:00,130
그리고 현실은 이러한 대규모 온라인 코스의 일부와 함께 지금

33
00:02:00,130 --> 00:02:04,070
그들은 모두 우리가 한 것 같은이 매우 높은 숫자로 시작합니다.

34
00:02:04,070 --> 00:02:08,759
그러나 목표는 궁극적으로 CS50x에 대해 가능한 한 마무리 라인에 많은 사람들을 얻을 정말입니다.

35
00:02:08,759 --> 00:02:12,000
디자인으로 CS50x는 지난 월요일부터 제공 될 것입니다

36
00:02:12,000 --> 00:02:17,430
다른 학교 약속이 사람들 있도록 2013년 4월 15일부터 끝까지,

37
00:02:17,430 --> 00:02:20,990
일, 가족, 다른 갈등과 같은이 좀 더 유연성을 가지고

38
00:02:20,990 --> 00:02:23,640
이 과정에 뛰어들되는, 그, 그것은 말 충분

39
00:02:23,640 --> 00:02:30,540
상당히 ambitiously 완료 일반적인 학기 동안 단 3 개월 과정 동안 경우에만.

40
00:02:30,540 --> 00:02:34,190
그러나 이러한 학생들은 같은 콘텐츠를 볼 같은 문제 세트를 예방합니다

41
00:02:34,190 --> 00:02:36,350
같은 반바지와 같은에 대한 액세스 권한을 갖는다.

42
00:02:36,350 --> 00:02:38,990
그래서 우리는 모두 여기 정말있는 것으로 알고 있습니다.

43
00:02:38,990 --> 00:02:42,360
그리고 CS50x의 끝 목표 중 하나는 많은 사람들을 얻을 수 없습니다

44
00:02:42,360 --> 00:02:45,720
결승점와 그들에게 컴퓨터 과학의 현저한 이해를 제공

45
00:02:45,720 --> 00:02:49,000
프로그래밍뿐만 아니라 그들에게이 공유 경험이 있습니다합니다.

46
00:02:49,000 --> 00:02:52,010
캠퍼스에 50 정의 특성 중 하나는, 우리는 희망,

47
00:02:52,010 --> 00:02:56,260
가끔, 더 나은 또는 더 나쁜위한 공동의 경험을 이런 종류있다

48
00:02:56,260 --> 00:02:59,480
하지만이 사람들이에 왼쪽과 오른쪽으로 회전 할 필요가,

49
00:02:59,480 --> 00:03:01,830
그리고 근무 시간과 hackathon 및 공정.

50
00:03:01,830 --> 00:03:04,560
그것은 온라인으로 사람들과 본인이 그렇게되고 조금 어렵네

51
00:03:04,560 --> 00:03:10,580
하지만 CS50x는 최초로 CS50 박람회와 4 월에 종료됩니다

52
00:03:10,580 --> 00:03:13,630
공정한 우리의 아이디어의 온라인 적응 할 것입니다

53
00:03:13,630 --> 00:03:18,250
2 분 동영상으로 - 어디 학생들이 수천은 모두 1 제출에 초대합니다

54
00:03:18,250 --> 00:03:22,480
그 자신의 최종 프로젝트 또는 동영상의 스크린은 인사 손을 흔들 중

55
00:03:22,480 --> 00:03:24,490
그리고 자신의 프로젝트에 대해 얘기하고 demoing,

56
00:03:24,490 --> 00:03:27,610
많은 전임자처럼은 공정에 캠퍼스에 끝났습니다

57
00:03:27,610 --> 00:03:31,400
학기 말까지, 희망은 글로벌 전시회가 될 수 있도록

58
00:03:31,400 --> 00:03:37,080
CS50x 학생들의 최종 프로젝트의 많은 그런 식으로 어느 캠퍼스에 여기 너에게이 12 월 기다리고 있습니다.

59
00:03:37,080 --> 00:03:39,680
앞으로 몇 개월은 그 말에 따라서 더.

60
00:03:39,680 --> 00:03:43,640
>> 100,000 학생들과 함께하지만, 몇 가지 더 인증 기관 (CA)에 대한 필요성을 제공합니다.

61
00:03:43,640 --> 00:03:47,590
당신들이 여기에 오솔길을 가로과 CS50을 복용하는 감안할 때

62
00:03:47,590 --> 00:03:51,630
몇 주 edX에있는 사람들이 물질의 석방을 사전에

63
00:03:51,630 --> 00:03:55,330
우리가이 계획에 가능한 한 자신의 학생들의 많은 참여 싶지만 알고 있습니다

64
00:03:55,330 --> 00:03:58,720
학기뿐만 아니라이 겨울이 오는 봄을 모두.

65
00:03:58,720 --> 00:04:01,620
따라서 CS50x에 참여하고 싶으 시다면,

66
00:04:01,620 --> 00:04:07,450
특히 CS50x 토론, CS50 토론의 edX 버전에에 참여

67
00:04:07,450 --> 00:04:10,140
당신의 많은 캠퍼스에서 사용 된있는 온라인 게시판,

68
00:04:10,140 --> 00:04:13,040
해당 URL에 머리를 해 주시기 바랍니다, 우리는 당신이 누군지 알려

69
00:04:13,040 --> 00:04:16,450
우리는 모두 학생 및 직원 팀과 교수진을 구성 좋아 테니까요

70
00:04:16,450 --> 00:04:19,630
캠퍼스에서 누가 단순히 함께 연주하고 돕고 있습니다.

71
00:04:19,630 --> 00:04:21,720
그리고 그들에게 익숙한 질문을 볼 때,

72
00:04:21,720 --> 00:04:25,320
당신은 인터넷에서 어떤 나라 어딘가 쯤에 몇 가지 버그를보고 학생을 듣고

73
00:04:25,320 --> 00:04:27,450
당신도 같은 문제를 그 반지 종을했기 때문에

74
00:04:27,450 --> 00:04:32,620
얼마 전에 귀하의 D-홀에서, 희망 그리고 당신은에 차임과 자신의 경험을 공유 할 수 있습니다.

75
00:04:32,620 --> 00:04:37,300
당신이 원한다면 참여 바랍니다.

76
00:04:37,300 --> 00:04:39,360
>> 하버드에서 컴퓨터 과학 코스는 전통의 비트가

77
00:04:39,360 --> 00:04:44,730
당신은 자랑스럽게 입을 수있는 의류, 옷을 갖는 그 중 CS50,

78
00:04:44,730 --> 00:04:49,090
학기 말에, 당신은 CS50을 완료하는 것은 자랑스럽게 말하는

79
00:04:49,090 --> 00:04:51,830
그리고 CS50과 같은했다, 우리는 항상 학생들을 포함 해

80
00:04:51,830 --> 00:04:54,540
이 과정을 최대한, 우리는 초대된다에

81
00:04:54,540 --> 00:04:56,900
학기의시기에, 학생들은 디자인을 제출하는

82
00:04:56,900 --> 00:04:59,330
당신은 사용하고자하는 선택의 포토샵을 사용하거나, 어떤 도구

83
00:04:59,330 --> 00:05:02,330
당신은 T-셔츠와 스웨터에 디자인을 제출, 디자이너 인 경우

84
00:05:02,330 --> 00:05:06,100
와 개에 대한 파라솔과 작은 두건 우리는 지금이 있고 좋아요.

85
00:05:06,100 --> 00:05:09,370
그리고 모든 일이겠군요 - 수상자는 매년 그 다음 전시되어 있습니다

86
00:05:09,370 --> 00:05:12,700
store.cs50.net에서 코스의 웹 사이트에.

87
00:05:12,700 --> 00:05:15,790
모든이 비용으로 판매하지만, 웹 사이트 자체를 실행하고 있습니다

88
00:05:15,790 --> 00:05:18,330
그리고 사람들이 좋아하는 색상과 디자인을 선택할 수 있습니다.

89
00:05:18,330 --> 00:05:20,420
그래서 우리가 작년 디자인의 일부를 공유 할 거라고 생각

90
00:05:20,420 --> 00:05:25,130
그 연례 전통, 여기에 이​​것 외에 웹 사이트에 있었다.

91
00:05:25,130 --> 00:05:29,410
"나는 Faultn을 감금있어 매일은"지난해 제출 중 하나

92
00:05:29,410 --> 00:05:32,290
이는 졸업생 위해 계속 사용할 수 있습니다.

93
00:05:32,290 --> 00:05:35,820
우리가이 한 것 "CS50는 1989 년 설립."

94
00:05:35,820 --> 00:05:39,010
우리 Bowdens 중 하나 인 롭 지난해 인기이었습니다.

95
00:05:39,010 --> 00:05:43,480
"팀 보덴"은 태어났다,이 디자인은 탑 셀러 중, 제출되었습니다.

96
00:05:43,480 --> 00:05:49,040
으로 여기있는 건이었다. 많은 사람들이 영업 로그에 따라 "보덴의 열기 '를했다.

97
00:05:49,040 --> 00:05:52,650
그 것은 지금 인터넷에서, 거기에 디자인 될 수 있다고 알고 있습니다.

98
00:05:52,650 --> 00:05:57,510
다음 문제가이에 대한 자세한 내용은 오는 설정합니다.

99
00:05:57,510 --> 00:06:00,330
>> 하나 더 도구 : 지금 희망 몇 가지 노출을했고 한

100
00:06:00,330 --> 00:06:02,350
GDB 몇 가지 체험,

101
00:06:02,350 --> 00:06:04,570
이는 물론, 디버거이며 조작 할 수 있습니다

102
00:06:04,570 --> 00:06:09,500
상당히 낮은 수준에서 프로그램은 어떤 것들 뭐하는거야?

103
00:06:09,500 --> 00:06:13,030
GDB는 당신이 무엇을하게됩니까?

104
00:06:13,030 --> 00:06:15,030
응? 나에게 무언가를 제공합니다. [학생 답 이해할 수없는]

105
00:06:15,030 --> 00:06:18,120
좋아. 함수에 단계, 그래서 당신은 실행을 입력 할 필요가 없습니다

106
00:06:18,120 --> 00:06:22,310
표준 출력에 물건을 인쇄 전체를 통해 프로그램 타격을 갖추고 있습니다.

107
00:06:22,310 --> 00:06:25,190
오히려, 여러분은 다음 입력, 라인하여 라인을 통해 단계를 수

108
00:06:25,190 --> 00:06:30,300
선 또는 쓴 한 가지 일반적으로, 함수 안으로 잠수 할 단계로 라인으로 라인을 이동합니다.

109
00:06:30,300 --> 00:06:35,240
GDB는 당신이 다른 무엇을하게됩니까? 응? [학생 답 이해할 수없는]

110
00:06:35,240 --> 00:06:38,100
변수를 인쇄 할 수 있습니다. 당신은 프로그램의 내부에 약간의 반성을하고 싶다면

111
00:06:38,100 --> 00:06:41,500
사방에 printf 문장을 쓰기에 의존 할 필요없이,

112
00:06:41,500 --> 00:06:44,600
당신은 변수를 인쇄하거나 변수를 표시 할 수 있습니다.

113
00:06:44,600 --> 00:06:46,710
당신은 GDB 같은 디버거로 또 무엇을 할 수 있습니까?

114
00:06:46,710 --> 00:06:49,170
[학생 답 이해할 수없는]

115
00:06:49,170 --> 00:06:52,080
그렇지. 당신은 중단 점을 설정할 수 있습니다, 당신은 휴식 실행을 말할 수

116
00:06:52,080 --> 00:06:54,020
main () 함수 또는 foo는 기능에서.

117
00:06:54,020 --> 00:06:56,800
한 줄에 123 휴식 실행을 말할 수있다.

118
00:06:56,800 --> 00:06:58,950
그리고 중단 점은 정말 강력한 기술 아르

119
00:06:58,950 --> 00:07:01,110
때문에 어디 문제에 대한 일반적인 감각이있는 경우

120
00:07:01,110 --> 00:07:05,360
아마, 당신은 프로그램의 전체를 통해 스테핑 시간을 낭비 할 필요가 없습니다 않습니다.

121
00:07:05,360 --> 00:07:08,250
당신은 본질적으로 바로 이동 한 후 입력을 시작할 수 있습니다 -

122
00:07:08,250 --> 00:07:10,970
단계 또는 다음 또는 같은과를 통해 스테핑.

123
00:07:10,970 --> 00:07:14,340
그러나 GDB 같은과 캐치, 그건 인간이 도움이 있다는 것입니다

124
00:07:14,340 --> 00:07:16,940
문제를 발견하고 버그를 찾으십시오.

125
00:07:16,940 --> 00:07:19,470
그것은 반드시 당신에게 그렇게 많이 찾지 않습니다.

126
00:07:19,470 --> 00:07:23,070
>> 그래서 우리는 짧은 명령 줄 도구입니다, 다른 일 style50을 도입

127
00:07:23,070 --> 00:07:27,500
그 조금 더 깔끔하게 당신보다 코드를 어떤 양식에 일치시키다하려고 인간이 수행 할 수 있습니다.

128
00:07:27,500 --> 00:07:29,530
그러나 역시, 정말 미학 것입니다.

129
00:07:29,530 --> 00:07:34,110
사용하기 좀 더 마법 is Valgrind이라는 다른 도구가 밝혀.

130
00:07:34,110 --> 00:07:36,860
의 출력 먼저 눈에 atrociously 암호입니다.

131
00:07:36,860 --> 00:07:39,420
그러나 특히 지금 우리가 용어의 부분에 있다고, 놀라 울 정도 유용

132
00:07:39,420 --> 00:07:43,080
어디 malloc 및 동적 메모리 할당을 사용하기 시작하고 있습니다.

133
00:07:43,080 --> 00:07:45,420
상황은 빠르게, 정말로 잘못 할 수 있습니다.

134
00:07:45,420 --> 00:07:49,320
때문에 귀하의 메모리를 확보하는 것을 잊지 당신이 NULL 포인터를 역 참조하는 경우

135
00:07:49,320 --> 00:07:55,770
또는 일부 쓰레기 포인터를 역 참조, 일반적으로 결과가 증상 무엇인가?

136
00:07:55,770 --> 00:07:59,470
잘못을 감금. 그리고 당신은 킬로바이트 또는 메가 바이트 어떤 수의 코어 파일을

137
00:07:59,470 --> 00:08:02,990
추락 할 때 즉, 프로그램의 메모리의 상태를 나타냅니다

138
00:08:02,990 --> 00:08:05,730
하지만이 프로그램은 궁극적으로, 세분화 오류를 오류를 감금

139
00:08:05,730 --> 00:08:08,450
어떤 뭔가 나쁜 일을 거의 관련이 있었 단 뜻

140
00:08:08,450 --> 00:08:11,750
당신이 여기 어딘가에 만든 메모리 관련 실수 있습니다.

141
00:08:11,750 --> 00:08:14,100
그래서 Valgrind이 같은 것을 찾을 수 있도록 도와줍니다.

142
00:08:14,100 --> 00:08:17,720
당신이 프로그램을 컴파일 한 후 그 말은, GDB처럼, 당신이 실행하는 도구입니다

143
00:08:17,720 --> 00:08:20,330
하지만 직접 프로그램을 실행보다는, 당신은 Valgrind 실행

144
00:08:20,330 --> 00:08:23,960
그리고 당신이 GDB와 마찬가지로, 여기에 프로그램을 전달합니다.

145
00:08:23,960 --> 00:08:26,220
이제 사용은, 가장 좋은 종류의 출력을 받아

146
00:08:26,220 --> 00:08:30,410
그래서 바로 화면의 상단에 당신은 Valgrind-v를 조금 오래 볼 수 있습니다.

147
00:08:30,410 --> 00:08:35,350
당신이 리눅스 컴퓨터에 프로그램을 사용할 때 "V"는 거의 보편적 자세한을 의미합니다.

148
00:08:35,350 --> 00:08:38,770
그래서 당신이 기본적으로하는 것보다 더 많은 데이터를 뱉어 의미합니다.

149
00:08:38,770 --> 00:08:45,510
"- = 전체를 누설 확인하십시오." 이 단지 가능한 모든 메모리 누수에 대한 검사를 말하고있는

150
00:08:45,510 --> 00:08:49,430
제가 한 수 실수. 이 역시 리눅스 프로그램과 일반적인 패러다임입니다.

151
00:08:49,430 --> 00:08:52,710
당신은 명령 줄 인수가있는 경우 일반적으로 즉, "스위치"입니다

152
00:08:52,710 --> 00:08:55,830
그는 프로그램의 동작을 변경해야하며, 하나의 편지있어

153
00:08:55,830 --> 00:09:00,310
그렇죠-V하지만이었던 그 경우, 그냥 프로그래머의 설계에 의해,

154
00:09:00,310 --> 00:09:05,150
, 명령 줄 인수는과 단어의 전체 단어 나 시리즈를 시작합니다 -.

155
00:09:05,150 --> 00:09:08,190
이것들은 인간의 컨벤션 있지만, 당신은 점점을 볼 수 있습니다.

156
00:09:08,190 --> 00:09:12,410
그리고, 마지막으로, "a.out"이 특정 예제에서 프로그램의 임의의 이름입니다.

157
00:09:12,410 --> 00:09:14,640
여기 몇 가지 대표적인 출력입니다.

158
00:09:14,640 --> 00:09:22,890
>> 우리가 말은 무엇인지 살펴 전에, 제가 여기에 코드 스 니펫 (snippet)로 가자.

159
00:09:22,890 --> 00:09:26,390
그리고 곧, 제가하는 방식이 일을 준비합시다

160
00:09:26,390 --> 00:09:32,120
과의 여기이 짧은 예입니다 memory.c, 살펴 보자.

161
00:09:32,120 --> 00:09:36,290
따라서이 프로그램에, 나를 기능과 질문에 확대 보자.

162
00:09:36,290 --> 00:09:39,430
우리는 함수를 호출 주요 기능, F를 가지고

163
00:09:39,430 --> 00:09:45,590
그리고 다음에 어떻게 F가 약간 기술 영어로, 할을 수행합니까?

164
00:09:45,590 --> 00:09:49,760
F는 무엇을 수행합니까?

165
00:09:49,760 --> 00:09:53,680
방법에 대한 I 줄 20로 시작되고, 별의 위치는 중요하지 않습니다,

166
00:09:53,680 --> 00:09:56,720
하지만 지난 강의 함께 일관성을 수 있습니다.

167
00:09:56,720 --> 00:09:59,910
우리 라인 (20)가 무슨 일을하는데? 왼쪽에. 우리는 더 이상 그것을 파괴합니다.

168
00:09:59,910 --> 00:10:02,410
INT * X : 그게 무슨 일을할까요?

169
00:10:02,410 --> 00:10:04,940
좋아요. 이 포인터를 선언, 그리고 지금의 더 많은 기술적 인하자.

170
00:10:04,940 --> 00:10:10,230
이 포인터를 선언하는 매우 구체적으로, 무엇을 의미합니까? 다른 사람?

171
00:10:10,230 --> 00:10:15,050
응? [학생 답 이해할 수없는] 너무 멀리.

172
00:10:15,050 --> 00:10:17,060
그래서 당신은 등호의 오른쪽에 읽고.

173
00:10:17,060 --> 00:10:20,290
단지 INT * X에 그냥 왼쪽에가 초점을 보자.

174
00:10:20,290 --> 00:10:24,700
이 포인터 "를 선언"않지만, 지금 가자는 정의에 깊이에 잠수.

175
00:10:24,700 --> 00:10:28,330
그 구체적, 기술적으로 무엇을 의미합니까? 응?

176
00:10:28,330 --> 00:10:31,940
[학생 답 이해할 수없는]

177
00:10:31,940 --> 00:10:35,090
좋아요. 그것은 메모리에 주소를 저장 할 준비를하고있어.

178
00:10:35,090 --> 00:10:40,680
좋아. 그리고의 더이 한 걸음을 가져 가게, 그것은 32 비트 변수, X를 선언있어.

179
00:10:40,680 --> 00:10:44,440
그리고 내가 그 때문에 32 비트 알아 -?

180
00:10:44,440 --> 00:10:47,390
는이 경우 포인터 때문에 그런, 정수이기 때문에이 없습니다.

181
00:10:47,390 --> 00:10:49,650
는 정수로 하나 같은, 그건 우연의 일치

182
00:10:49,650 --> 00:10:51,970
그 별이 있다는 사실은이 포인터가 의미

183
00:10:51,970 --> 00:10:57,300
와 어플라이언스에 여러 컴퓨터와 마찬가지로, 전부는 아니지만, 포인터는 32 비트입니다.

184
00:10:57,300 --> 00:11:01,850
최신 맥, 최신 PC를 같은 더 현대적인 하드웨어에, 당신은 64 비트 포인터를 가지고 있습니다

185
00:11:01,850 --> 00:11:04,160
하지만 어플라이언스에, 이것들은 32 비트입니다.

186
00:11:04,160 --> 00:11:08,380
그래서 우리는 거기에 표준화됩니다. 더 구체적으로, 그 이야기는 다음과 같이 간다 :

187
00:11:08,380 --> 00:11:10,820
우리는 포인터 "를 선언"; 그게 무슨 뜻 이죠?

188
00:11:10,820 --> 00:11:12,810
우리는 메모리 주소를 저장하는 준비합니다.

189
00:11:12,810 --> 00:11:15,530
그게 무슨 뜻 이죠?

190
00:11:15,530 --> 00:11:19,810
우리는 32 비트를 차지라는 변수 x를 만들

191
00:11:19,810 --> 00:11:23,810
그건 곧 정수의 주소를 저장합니다.

192
00:11:23,810 --> 00:11:26,470
그리고 아마도 우리가 얻을 수 최대한 정확한입니다.

193
00:11:26,470 --> 00:11:31,810
세상을 단순화하고 단지 X라는 포인터를 선언 말을 전진 괜찮아요.

194
00:11:31,810 --> 00:11:35,380
포인터를 선언하지만, 실현과 실제로 무슨 일이야 이해

195
00:11:35,380 --> 00:11:38,490
그저 그 몇 글자 인치

196
00:11:38,490 --> 00:11:42,040
>> 자,이 사람은 그 이상 표현이지만, 마치 작은 쉬워졌습니다.

197
00:11:42,040 --> 00:11:48,160
그래서 지금 강조 것은, 무엇을하고있다 : "malloc (10 * sizeof (int는));"응?

198
00:11:48,160 --> 00:11:52,350
[학생 답 이해할 수없는]

199
00:11:52,350 --> 00:11:58,250
좋아. 그리고 거기에 걸릴 수 있습니다. 그것은 십 정수에 대한 메모리 덩어리를 할당있어.

200
00:11:58,250 --> 00:12:02,190
그리고 지금의 약간 깊이에 잠수 해, 그것은 십 정수 메모리 덩어리를 할당있어.

201
00:12:02,190 --> 00:12:05,390
malloc는 무엇 반환입니까?

202
00:12:05,390 --> 00:12:10,390
더 구체적으로 그 청크의 주소 또는, 그 덩어리의 첫번째 바이트의 주소입니다.

203
00:12:10,390 --> 00:12:14,080
제가 그럼 어떻게 오전, 프로그래머가 알 수있는 메모리 끝의 덩어리?

204
00:12:14,080 --> 00:12:18,340
나는 연속 된 거에요. Malloc은 정의에 의해 당신에게 메모리의 연속 된 덩어리를 제공합니다.

205
00:12:18,340 --> 00:12:21,240
거기에 어떤 차이 없습니다. 당신은 그 덩어리의 모든 바이트에 액세스 할 수 있습니다

206
00:12:21,240 --> 00:12:26,760
다시 백업 할 백업 할 수 있지만, 메모리의 청크의 끝이 어디에 어떻게 알 수 있습니까?

207
00:12:26,760 --> 00:12:28,850
당신은 malloc를 사용하는 경우? [학생 답 이해할 수없는 잘 됐네.

208
00:12:28,850 --> 00:12:30,670
당신은하지 않습니다. 당신은 기억해야합니다.

209
00:12:30,670 --> 00:12:35,960
나는 값 10을 사용하여 기억해야하고, 난 그 끝났하지 못하는 것 같습니다.

210
00:12:35,960 --> 00:12:41,000
그러나 무거운 짐이 나를 전적으로입니다. 우리가 문자열에 약간 의존이 될 나 strlen,

211
00:12:41,000 --> 00:12:45,860
때문에 \ 0을 갖는이 협약에서만 작동합니다

212
00:12:45,860 --> 00:12:48,840
또는 문자열의 끝에서이 특별한 빵점 문자 빵점.

213
00:12:48,840 --> 00:12:51,740
그 메모리 중 임의의 덩어리에 보유하지 않습니다.

214
00:12:51,740 --> 00:12:58,590
그것은 당신에게 달려 있습니다. 라인 20 그럼, 메모리 덩어리를 할당

215
00:12:58,590 --> 00:13:02,590
그 십 정수를 저장할 수 있으며, 첫 번째 바이트의 주소를 저장

216
00:13:02,590 --> 00:13:05,610
라는 변수 X의 메모리의 청크의.

217
00:13:05,610 --> 00:13:11,140
포인터입니다 따라서. 라인 21 그래서, 불행히도 실수였다.

218
00:13:11,140 --> 00:13:16,110
그러나 먼저, 무엇을하는 거지? 그것은, 위치 10, 인덱스 0에서 상점을 말하는거야

219
00:13:16,110 --> 00:13:19,480
X 값 0이라는 메모리의 청크의.

220
00:13:19,480 --> 00:13:21,510
>> 따라서 몇 가지가가는납니다.

221
00:13:21,510 --> 00:13:25,420
x는 포인터이지만, 몇 주 전부터 기억

222
00:13:25,420 --> 00:13:29,440
당신은 여전히​​ 배열 스타일의 대괄호 표기법을 사용할 수 있습니다.

223
00:13:29,440 --> 00:13:36,180
그 사실은 더 이상한 모양의 포인터 연산에 대한 짧은 손 표기법니까.

224
00:13:36,180 --> 00:13:40,320
우리가이 같은 짓을 했을까 곳 : 주소 X를 타고, 지난 10 장소를 이동

225
00:13:40,320 --> 00:13:44,550
해당 위치에 저장되어있는 어떤 주소로도 이동합니다.

226
00:13:44,550 --> 00:13:48,090
솔직히,이 읽고있는 편안한 받게하기 위해서 심한 것입니다.

227
00:13:48,090 --> 00:13:52,900
그래서 세상이 일반적으로 훨씬 더 인간 친화적 읽을 수있는 단지 때문에 대괄호를 사용합니다.

228
00:13:52,900 --> 00:13:55,140
하지만 그게 정말 후드 아래에 무슨 일입니다;

229
00:13:55,140 --> 00:13:58,190
x는 주소가 아닌 배열 이라기보다는이다.

230
00:13:58,190 --> 00:14:02,410
그래서이 X의 위치 10 0 저장합니다.

231
00:14:02,410 --> 00:14:06,120
왜이 안 좋은가요? 응?

232
00:14:06,120 --> 00:14:17,370
[학생 답 이해할 수없는] 그렇지.

233
00:14:17,370 --> 00:14:21,100
, 우리는 겨우 10 ints를 할당하지만, C에서 프로그래밍 할 때 0을 기준으로

234
00:14:21,100 --> 00:14:25,690
그래서 당신은 0 1 2 3 4 5 6 7 8 9하지만, 10에 액세스 할 수 있습니다.

235
00:14:25,690 --> 00:14:30,270
따라서 두 프로그램은 감금 결함에 갈거나 없습니다.

236
00:14:30,270 --> 00:14:32,900
하지만 우리는 정말 모르겠어,이 nondeterministic 행동의 일종입니다.

237
00:14:32,900 --> 00:14:35,600
정말 우리가 운이 있는지 여부에 따라 달라집니다.

238
00:14:35,600 --> 00:14:40,650
그 여분의 바이트를 사용하는 경우는 운영 체제가 신경 쓰지 않는 밝혀지면

239
00:14:40,650 --> 00:14:43,360
나에게 주어지지 않았다 하더라도, 내 프로그램이 충돌하지 않을 수도 있습니다.

240
00:14:43,360 --> 00:14:46,780
는, 노골적이지는 버그이지만, 그 증상을 볼 수 있습니다

241
00:14:46,780 --> 00:14:48,960
또는 한 번만 한동안 볼 수 있습니다.

242
00:14:48,960 --> 00:14:51,230
하지만 현실은 버그가 사실이라는 것입니다.

243
00:14:51,230 --> 00:14:54,320
당신이 올바른하고자하는 프로그램을 작성 한 경우 그리고 정말 문제입니다

244
00:14:54,320 --> 00:14:58,840
당신은 사람들이 매번 가끔은 충돌하는 사용하는 프로그램을 판매 한

245
00:14:58,840 --> 00:15:02,450
때문에 물론, 상황이 안 좋은데. 사실, 당신은 Android 휴대 전화 나 아이폰이있는 경우

246
00:15:02,450 --> 00:15:05,550
그리고, 당신은 요즘 앱을 다운로드 네가 가졌던 한 경우 응용 프로그램은 종료

247
00:15:05,550 --> 00:15:10,040
가 사라 갑자기, 그, 거의 항상 일부 메모리 관련 문제의 결과입니다

248
00:15:10,040 --> 00:15:12,830
프로그래머는 포인터를 망쳐 및 역 참조된다

249
00:15:12,830 --> 00:15:18,670
그 또는 그녀가 있어서는 안됩니다,와 iOS 또는 Android의 결과는 모두 프로그램을 죽입니다

250
00:15:18,670 --> 00:15:23,080
오히려 위험 정의되지 않은 동작 또는 보안 타협의 일부 종류보다.

251
00:15:23,080 --> 00:15:25,950
>> 이것 외에이 프로그램에 다른 버그가 있습니다.

252
00:15:25,950 --> 00:15:30,180
이 프로그램에 또 무슨 일을 망쳐 버린거야?

253
00:15:30,180 --> 00:15:32,740
내가 설교 한 일을 연습했습니다. 응?

254
00:15:32,740 --> 00:15:34,760
[학생 답 이해할 수없는 잘 됐네.

255
00:15:34,760 --> 00:15:36,880
나는 메모리를 해제하지 않았습니다. 그래서 지금 엄지 손가락의 규칙

256
00:15:36,880 --> 00:15:43,150
당신이 malloc를 호출 때마다 작업을 완료하면 해당 메모리를 사용하여 무료로 전화해야 할 수 있습니다.

257
00:15:43,150 --> 00:15:45,610
자,이 메모리를 해방할까요?

258
00:15:45,610 --> 00:15:49,780
아마,이 첫 번째 줄은 올바른이었다고 가정하면, 여기서하고 싶어합니다.

259
00:15:49,780 --> 00:15:55,710
내 말은, 예를 들어, 여기를 할 수 없습니다 때문입니다. 이유는 무엇입니까?

260
00:15:55,710 --> 00:15:57,860
그냥 범위. 그래서 우리는, 포인터에 대해 얘기하고 있어도

261
00:15:57,860 --> 00:16:04,830
이 주 2 X 만이 선언 된 중괄호 내부 범위에 세 문제입니다.

262
00:16:04,830 --> 00:16:11,000
그럼 당신은 확실히 거기 확보 할 수 없습니다. 을 확보 할 수있는 유일한 기회 대략 21 라인 이후입니다.

263
00:16:11,000 --> 00:16:15,170
이 매우 간단한 프로그램입니다, 당신은 가지 마음을 감싸 일단 매우 간단

264
00:16:15,170 --> 00:16:17,870
실수가 어디를 중심으로 프로그램은하고 있어요.

265
00:16:17,870 --> 00:16:20,500
그리고 당신이 먼저 그것을 보지 못했다하더라도, 희망 지금 너무 눈에 띄어서

266
00:16:20,500 --> 00:16:23,870
이러한 실수는 아주 쉽게 해결하고 쉽게 만들어진 것을.

267
00:16:23,870 --> 00:16:28,720
그러나 프로그램이 12 개 이상의 노선 긴 경우는, 100 줄 길이, 50 라인의 길이

268
00:16:28,720 --> 00:16:31,150
논리적으로 생각, 선에 의해 코드 라인을 통해 걷기,

269
00:16:31,150 --> 00:16:35,110
지속적으로, 버그를 찾고, 가능하지만 할 특히 재미 없어

270
00:16:35,110 --> 00:16:38,340
그리고 그렇게하는 것도 어려운 일이고, Valgrind 같은 도구가 존재하는 이유입니다.

271
00:16:38,340 --> 00:16:40,900
내가 가서이 일을하게 놔두지 : 내 터미널 창을 열어,

272
00:16:40,900 --> 00:16:45,400
그리고 메모리는 괜찮을 것 같습니다 때문에 날 그냥 메모리를 실행하지 맙시다.

273
00:16:45,400 --> 00:16:49,180
운이 나타납니다. 배열의 끝 부분에 해당 추가 바이트로 이동

274
00:16:49,180 --> 00:16:51,060
너무 문제가 될 것 같습니다하지 않습니다.

275
00:16:51,060 --> 00:16:56,370
그러나 그냥 확인하고 의미 정신 검사를,도, 그럼에도 불구하고, 내가 할게

276
00:16:56,370 --> 00:16:58,320
이 사실은 정확 여부.

277
00:16:58,320 --> 00:17:04,690
>> 따라서 valgrind-V를 두자 - = 전체를 누설 확인

278
00:17:04,690 --> 00:17:07,520
그리고이 경우에 프로그램의 이름은 메모리,하지 a.out입니다.

279
00:17:07,520 --> 00:17:10,760
그럼 내가 가서이 해주세요. Enter 키를 누르십시오.

280
00:17:10,760 --> 00:17:14,109
이런. 이번 행사는 출력,이 내가 이전에 언급거야.

281
00:17:14,109 --> 00:17:17,550
그러나, 여기에 말도 안되는 모든을 읽어 배울 경우,

282
00:17:17,550 --> 00:17:20,760
이 대부분은 재미없는 단지 진단 결과입니다.

283
00:17:20,760 --> 00:17:24,829
당신의 눈이 정말 찾고 싶은 것은 오류 또는 무효의 언급입니다.

284
00:17:24,829 --> 00:17:26,800
문제를 제안 단어입니다.

285
00:17:26,800 --> 00:17:29,340
그리고 실제로, 거기에 잘못 무슨 일이야 보자.

286
00:17:29,340 --> 00:17:35,230
나는 일종의 요약,이 "출구에서 사용. 1 블록에 40 바이트를"

287
00:17:35,230 --> 00:17:38,750
아직 정말 블록이 무엇인지 잘 모르겠어요,하지만 40 바이트

288
00:17:38,750 --> 00:17:41,260
그 어디에서 제가 이해할 수있는 것처럼 실제로 느낀다.

289
00:17:41,260 --> 00:17:45,030
40 바이트. 왜 출구에서 사용 40 바이트 무엇입니까?

290
00:17:45,030 --> 00:17:48,780
그리고 더 구체적으로 우리가 여기에 아래로 스크롤하면

291
00:17:48,780 --> 00:17:54,520
이유는 확실히 40 바이트를 잃어? 응?

292
00:17:54,520 --> 00:17:59,520
[학생 답 이해할 수없는] 좋아요. 네, 맞아요.

293
00:17:59,520 --> 00:18:03,540
,이 열 정수가 있었고, 그 각각 4, 또는 32 비트의 크기

294
00:18:03,540 --> 00:18:08,300
당신이 제안대로, 나는 무료 전화를 안 한니까 내가 정확하게 40 바이트를 잃었습니다.

295
00:18:08,300 --> 00:18:13,460
즉, 벌레, 그리고 지금은 더 조금을 살펴 보자이 옆에 표시

296
00:18:13,460 --> 00:18:16,900
"잘못된 크기 4 써주세요." 이제이는 무엇인가?

297
00:18:16,900 --> 00:18:21,150
이 주소는 겉보기에, 어떻게 기본 표기법을 표현입니까?

298
00:18:21,150 --> 00:18:23,640
이 16 진수이며, 언제든지 당신은 0x로 시작하는 번호가 표시

299
00:18:23,640 --> 00:18:29,410
그것은 우리가 다시 질문, 내가 생각 pset 0의 섹션에서 방법을했는지, 16 진수 의미

300
00:18:29,410 --> 00:18:34,090
이는 바이너리 진수 진수로 변환하는 등등, 워밍업 운동을 할 만했다.

301
00:18:34,090 --> 00:18:39,220
진수, 단지 인간의 컨벤션으로, 보통 포인터를 나타내는 데 사용됩니다

302
00:18:39,220 --> 00:18:41,570
또는 더 일반적으로 해결할 수 있습니다. 그건 그냥 대회의

303
00:18:41,570 --> 00:18:45,340
가 읽기 조금 더 쉽기 때문입니다, 그것은, 소수점과 같은보다 좀 더 콤팩트입니다

304
00:18:45,340 --> 00:18:47,720
대부분의 인간이 사용하기에 진 쓸모가 있습니다.

305
00:18:47,720 --> 00:18:50,840
이제이 무엇을 의미합니까? 잘못된 쓰기가 같은 음, 보이는

306
00:18:50,840 --> 00:18:54,480
memory.c의 라인 21 사이즈 4.

307
00:18:54,480 --> 00:18:59,180
그럼 줄 21 돌아 가자, 그리고 실제로, 여기에 잘못 기록입니다.

308
00:18:59,180 --> 00:19:02,640
그래서 Valgrind는 완전히 내 손을 잡아과 수정이 말하려고하지 않습니다

309
00:19:02,640 --> 00:19:05,520
하지만 내가 잘못된 쓰기를하고있는 것으로 감지된다.

310
00:19:05,520 --> 00:19:08,800
내가하지 말라고 4 바이트를 터치하고 있는데 분명히이 있기 때문입니다

311
00:19:08,800 --> 00:19:13,960
당신이 지적으로, 나는 대신에 [9]의 [10]을하고 있어요 maximally

312
00:19:13,960 --> 00:19:16,660
또는 [0] 나 사이에 뭔가.

313
00:19:16,660 --> 00:19:19,690
Valgrind를 사용하면 이제 프로그램을 작성 할 때마다 실현

314
00:19:19,690 --> 00:19:24,190
포인터를 사용하여 메모리를 사용하고, malloc 더 구체적으로, 그

315
00:19:24,190 --> 00:19:27,080
확실히이 오래 실행 습관에 들어가

316
00:19:27,080 --> 00:19:30,890
하지만 아주 쉽게 Valgrind의 명령을 복사하고 붙여 넣기

317
00:19:30,890 --> 00:19:32,650
거기에 몇 가지 오류가 있는지 확인합니다.

318
00:19:32,650 --> 00:19:34,820
그리고, 당신이 출력을 볼 때마다 압도적 있습니다

319
00:19:34,820 --> 00:19:39,430
하지만 단지 시각적으로 모든 출력을 구문 분석하고 표시되는지 확인하면 오류를 언급

320
00:19:39,430 --> 00:19:43,190
또는 경고 또는 무효 또는 잃었다.

321
00:19:43,190 --> 00:19:46,200
당신과 같은 소리가 어디 선가 실수를하는 모든 단어입니다.

322
00:19:46,200 --> 00:19:48,580
귀하의 툴킷의 새로운 도구 인 것 알고 있습니다.

323
00:19:48,580 --> 00:19:51,270
>> 지금 월요일에, 우리는 사람들을 아주 많이 가지고하는 것은 여기에 와서

324
00:19:51,270 --> 00:19:53,150
과 연결리스트의 개념을 나타냅니다.

325
00:19:53,150 --> 00:20:00,970
그리고 우리는 어떤 문제에 대한 솔루션으로 연결리스트를 소개?

326
00:20:00,970 --> 00:20:04,590
응? [학생 답 이해할 수없는 잘 됐네.

327
00:20:04,590 --> 00:20:06,530
배열은 메모리가 그들에게 추가 할 수 없습니다.

328
00:20:06,530 --> 00:20:09,440
당신은 10 사이즈의 배열, 당신이 얻을 전부를 할당합니다.

329
00:20:09,440 --> 00:20:13,690
당신이 처음에 malloc을 호출하면, realloc 같은 함수를 호출 할 수 있습니다

330
00:20:13,690 --> 00:20:17,580
공간이 그 끝을 향해있는 경우와 그 배열을 성장 시도 할 수 있습니다

331
00:20:17,580 --> 00:20:21,610
다른 사람이 사용하지 있으며,이 아니라면, 그냥 다른 곳에서 당신에게 더 큰 덩어리를 찾을 것.

332
00:20:21,610 --> 00:20:25,040
그런데 그게 새로운 배열에있는 바이트의 모든 복사합니다.

333
00:20:25,040 --> 00:20:28,310
이 매우 올바른 솔루션처럼 들린다.

334
00:20:28,310 --> 00:20:34,790
왜 이런 매력이?

335
00:20:34,790 --> 00:20:36,940
난 그게 작동 그러니까, 인간은이 문제를 해결했습니다.

336
00:20:36,940 --> 00:20:40,710
왜 우리는 연결 목록과 월요일에이를 해결하기 위해 필요 했을까? 응?

337
00:20:40,710 --> 00:20:44,060
[학생 대답은 이해할 수없는]은 시간이 오래 걸릴 수 있습니다.

338
00:20:44,060 --> 00:20:49,260
사실, 당신이 malloc이나 realloc 또는 또 다른 하나입니다 calloc을 호출 할 때마다,

339
00:20:49,260 --> 00:20:52,470
언제든지 당신, 프로그램, 운영 체제에 말을하는거야,

340
00:20:52,470 --> 00:20:54,310
당신은 프로그램을 느리게하는 경향이 있습니다.

341
00:20:54,310 --> 00:20:57,470
당신은 루프에 가지 이러한 종류의 일을하는 경우, 당신은 정말 물건 속도가 느려지하고 있습니다.

342
00:20:57,470 --> 00:21:00,740
당신은 "여러분, 안녕하세요!"형 프로그램의 간단한이를 발견 할 수 없어

343
00:21:00,740 --> 00:21:04,300
하지만 훨씬 더 큰 프로그램에서, 메모리에 다시 다시 운영 체제를 묻는

344
00:21:04,300 --> 00:21:07,520
하거나 다시하고 다시 돌려주는 것은 좋은 일이되지 경향이있다.

345
00:21:07,520 --> 00:21:11,210
또한, 그냥 지적의 일종 - 이건 완전히 시간 낭비입니다.

346
00:21:11,210 --> 00:21:16,490
새 배열로 모든 것을 복사 점점 더 많은 메모리를 할당 왜, 위험,

347
00:21:16,490 --> 00:21:21,980
당신이 실제로 필요로 만 많은 메모리를 할당 할 수있는 대안이 있다면 요?

348
00:21:21,980 --> 00:21:24,130
그래서 여기에서 더하기 부호와 minuses가 있습니다.

349
00:21:24,130 --> 00:21:26,730
더하기 부호 중 하나는 우리가 역 동성을 가지고 있다는 것입니다.

350
00:21:26,730 --> 00:21:29,100
메모리의 덩어리는 무료입니다 어디에 있는지 중요하지 않습니다,

351
00:21:29,100 --> 00:21:32,070
난 그냥 포인터를 통해 만들에이 빵 부스러기를 정렬 할 수 있습니다

352
00:21:32,070 --> 00:21:34,470
함께 내 전체 링크 목록을 문자열로.

353
00:21:34,470 --> 00:21:36,470
하지만 적어도 하나의 가격을 지불합니다.

354
00:21:36,470 --> 00:21:40,060
>> 내가 뭘 연결된 목록을 얻기에 포기해야합니까?

355
00:21:40,060 --> 00:21:42,470
응? [학생 답 이해할 수없는 잘 됐네.

356
00:21:42,470 --> 00:21:45,650
당신은 더 많은 메모리가 필요합니다. 지금은,이 포인터위한 공간이 필요합니다

357
00:21:45,650 --> 00:21:47,900
이 슈퍼 간단한 연결리스트의 경우

358
00:21:47,900 --> 00:21:51,410
만 4 바이트 아르 정수를 저장하려고 즉, 우리는 말을 계속

359
00:21:51,410 --> 00:21:54,240
잘, 포인터는 4 바이트이기 때문에 지금은 그대로 두 배로 한

360
00:21:54,240 --> 00:21:57,290
메모리의 양 난 그냥이 목록을 저장해야합니다.

361
00:21:57,290 --> 00:21:59,680
다시 한 번,이 컴퓨터 과학의 일정한 효율이 줄어입니다

362
00:21:59,680 --> 00:22:03,440
시간과 공간과 개발 노력 및 기타 리소스 사이에 있습니다.

363
00:22:03,440 --> 00:22:06,630
연결리스트를 사용하는 다른 단점은 무엇입니까? 응?

364
00:22:06,630 --> 00:22:10,150
[학생 답 이해할 수없는]

365
00:22:10,150 --> 00:22:12,600
좋아. 에 액세스 할 쉽게 수 없습니다. 우리는 활용이 더 이상 수

366
00:22:12,600 --> 00:22:15,530
같은 주 0 원칙은 분열과 정복.

367
00:22:15,530 --> 00:22:18,220
그리고 더 구체적 이진 검색 할 수 있습니다. 때문에 비록 우리 인간이

368
00:22:18,220 --> 00:22:20,400
이 목록의 중간이 어디에 대략 볼 수 있습니다,

369
00:22:20,400 --> 00:22:25,840
컴퓨터는이 연결 목록이 먼저라는 주소에서 시작하는 알고 있습니다.

370
00:22:25,840 --> 00:22:28,250
그래서 0x123 또는 그런 일입니다.

371
00:22:28,250 --> 00:22:30,990
그리고 프로그램을 수있는 유일한 방법은 중간 요소를 찾을 수 있습니다

372
00:22:30,990 --> 00:22:33,350
실제로 전체 목록을 검색하는 것입니다.

373
00:22:33,350 --> 00:22:35,500
그리고 나서, 말 그대로 전체 목록을 검색 할 수 있기 때문에

374
00:22:35,500 --> 00:22:38,950
도 일단은 포인터를 따라 중간 요소에 도달

375
00:22:38,950 --> 00:22:42,380
너, 프로그램은 잠재적으로이 목록이 얼마나 오래 몰라

376
00:22:42,380 --> 00:22:45,250
당신은 그것의 끝을 눌러, 당신은 어떻게 프로그래밍 방식으로 알고 때까지

377
00:22:45,250 --> 00:22:48,600
당신은 연결리스트의 끝에 있다고?

378
00:22:48,600 --> 00:22:51,120
특별한 NULL 포인터, 그래서, 컨벤션가 있습니다.

379
00:22:51,120 --> 00:22:53,870
이 포인터를 사용하기보다는, 우리는 확실히 어떤 쓰레기 값이되고 싶지 않아

380
00:22:53,870 --> 00:22:57,750
어디 선가 무대를 가리키고, 우리는 그것을 손으로 NULL을 원하는,

381
00:22:57,750 --> 00:23:01,530
결말 곳을 우리가 알 수 있도록 우리는이 데이터 구조에서이 터미널이 있도록.

382
00:23:01,530 --> 00:23:03,410
>> 우리가이 조작하고 싶다면?

383
00:23:03,410 --> 00:23:05,980
우리는이 시각의 대부분을 했어, 인간과

384
00:23:05,980 --> 00:23:07,630
하지만 우리가 삽입을하려면?

385
00:23:07,630 --> 00:23:12,360
따라서 원본 목록 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
우리는 55 번, 뭐 노드에 대한 malloc 공간을 원하는 경우

387
00:23:16,730 --> 00:23:20,730
그리고 우리는 월요일에했던 것처럼 목록에 55 삽입하고 싶어?

388
00:23:20,730 --> 00:23:23,690
우리가 어떻게이 작업을 수행합니까? 음, 아니타가 와서 그녀는 본질적으로 목록을 걸었다.

389
00:23:23,690 --> 00:23:27,500
그녀는 다음, 다음, 다음, 다음, 다음 다음 첫 번째 요소에서 시작했다.

390
00:23:27,500 --> 00:23:29,500
마지막으로 왼쪽 모든 방법을 아래로 누르

391
00:23:29,500 --> 00:23:34,480
그리고 오 실현이 NULL입니다. 그래서 포인터 조작이 필요해서 했어요?

392
00:23:34,480 --> 00:23:37,980
마지막에 있던 사람, 번호 34, 왼쪽 손이 제기 필요

393
00:23:37,980 --> 00:23:46,220
55에 가리, 55는 새로운 NULL 종료 될 때까지 아래로 가리키고 자신의 왼쪽 팔을 필요했습니다. 완료.

394
00:23:46,220 --> 00:23:49,540
예쁜 쉽게 정렬 목록에 55을 삽입 할 수도 있습니다.

395
00:23:49,540 --> 00:23:51,800
그리고 어떻게이 볼 수 있을까요?

396
00:23:51,800 --> 00:23:55,690
>> 내가 가서 여기 몇 가지 코드 예제를 열어 보자.

397
00:23:55,690 --> 00:23:58,120
나는 gedit를 열고 내가 먼저 두 개의 파일을 열어 드리겠습니다.

398
00:23:58,120 --> 00:24:02,050
하나는 list1.h이며,이 코드의 덩어리라고 난 그냥 생각 나게 해

399
00:24:02,050 --> 00:24:04,920
우리는 노드를 나타내는 데 사용되는.

400
00:24:04,920 --> 00:24:13,040
노드 목록에서 그 다음 일은 바로 포인트 그 다음이라는 N이라는 정수와 포인터를 모두 갖추고 있습니다.

401
00:24:13,040 --> 00:24:15,450
그건. H 파일에 지금있다. 이유는 무엇입니까?

402
00:24:15,450 --> 00:24:19,090
있는데,이 대회는, 그리고 우리는이 엄청난 양의 자신을 이용 복용하지 못 했어

403
00:24:19,090 --> 00:24:22,220
printf 및 기타 기능을 작성하지만, 사람

404
00:24:22,220 --> 00:24:27,150
stdio.h라는 파일을 작성하여 세계에 선물로 그 모든 기능을했다.

405
00:24:27,150 --> 00:24:30,950
그리고 string.h가하고 map.h이있어, 모든 이들 h 파일이있어

406
00:24:30,950 --> 00:24:34,410
당신은 본이나 다른 사람이 작성한 기간 동안 사용했을 가능성이 있다고.

407
00:24:34,410 --> 00:24:38,470
일반적으로 이러한 인치 H 파일 typedefs 같은 유일한 사항은 다음과 같습니다

408
00:24:38,470 --> 00:24:42,310
또는 사용자 정의 유형 또는 상수 선언의 선언.

409
00:24:42,310 --> 00:24:47,890
당신은 헤더 파일의 기능 '구현을 넣어하지 않습니다.

410
00:24:47,890 --> 00:24:50,570
당신은 대신, 단지 자신의 프로토 타입을 넣어.

411
00:24:50,570 --> 00:24:53,050
당신은 그들이 원하는 세계와 공유 할 뭔가를 넣어

412
00:24:53,050 --> 00:24:55,640
자신의 코드를 컴파일하는 순서를 유지해야합니다. 그러니 이번 만 습관에 가려면하면,

413
00:24:55,640 --> 00:24:59,110
우리는 같은 일을하기로 결정했습니다. 많은이 list1.h에 없 거든

414
00:24:59,110 --> 00:25:02,070
그러나 우리는 세계의 사람들에게 관심이 될만한 걸 넣어 한

415
00:25:02,070 --> 00:25:05,030
누가 우리의 연결리스트 구현을 사용하고 싶습니다.

416
00:25:05,030 --> 00:25:08,040
이제 list1.c에,이 일을 통과하지 않습니다

417
00:25:08,040 --> 00:25:11,390
이 좀 긴이기 때문에,이 프로그램도 있지만, 그 프롬프트에 빠르게 실제 실행할 수 있습니다.

418
00:25:11,390 --> 00:25:15,720
나, 목록 1를 컴파일 내게 한 다음 목록 1을 실행하게, 그리고 당신은 볼 수 있습니다 봅시다

419
00:25:15,720 --> 00:25:18,070
여기 시뮬레이션 간단한 작은 프로그램이있어

420
00:25:18,070 --> 00:25:20,990
그 때문에 목록에 번호를 추가하고 제거 할 수 있도록거야.

421
00:25:20,990 --> 00:25:24,310
그럼 내가 가서 메뉴 옵션 3 3 입력 보자.

422
00:25:24,310 --> 00:25:27,880
전 그 번호를 삽입하려면 - 가자의 9 살 첫 번째 숫자는, 어떻게

423
00:25:27,880 --> 00:25:30,550
그런데 지금은 내가 목록 지금 9는 말거야.

424
00:25:30,550 --> 00:25:33,760
내가 가서 다른 삽입을하자, 그래서 메뉴 옵션 3를 누르십시오.

425
00:25:33,760 --> 00:25:36,760
어떤 번호가 내가 삽입하고 싶어? 17.

426
00:25:36,760 --> 00:25:39,220
입력합니다. 그리고 한번 더 할게요.

427
00:25:39,220 --> 00:25:41,720
제가 22 번을 삽입 보자.

428
00:25:41,720 --> 00:25:45,850
그래서 우리는 우리가 잠시 전에 슬라이드 형태로 가지고있는 연결리스트의 처음 부분을 수 있습니다.

429
00:25:45,850 --> 00:25:48,740
이 삽입 실제로 어떻게 된 일 이죠?

430
00:25:48,740 --> 00:25:52,000
사실, 22 목록의 끝에 지금이다.

431
00:25:52,000 --> 00:25:55,050
이야기 그래서 우리는 월요일에 무대에서 했더니 지금 recapped

432
00:25:55,050 --> 00:25:57,460
실제로 코드에서 일어나는해야합니다.

433
00:25:57,460 --> 00:25:59,700
가 살펴 보자. 저이 파일에 아래로 스크롤 보자.

434
00:25:59,700 --> 00:26:01,720
우리는 기능의 일부를 넘는 광택됩니다

435
00:26:01,720 --> 00:26:05,630
우리는,에 내려 가서 말, 삽입 기능을합니다.

436
00:26:05,630 --> 00:26:11,720
>> 우리가이 연결 목록에 새 노드를 삽입하는 방식 보자.

437
00:26:11,720 --> 00:26:14,550
목록은 어디에 선언입니까? 음, 우선은, 상단에있는 모든 방법을 스크롤

438
00:26:14,550 --> 00:26:19,970
내 링크 목록이 기본적으로 처음에 NULL입니다 하나의 포인터로 선언되고 있다는 사실을 알 수.

439
00:26:19,970 --> 00:26:23,180
그래서 일반적으로 우리가 상대하고 전파 한, 여기에 전역 변수를 사용

440
00:26:23,180 --> 00:26:25,280
그것은 유지하기 위해 코드 좀 어질러 놨하게 있기 때문

441
00:26:25,280 --> 00:26:29,080
그 게으른, 보통의 일종 이죠하지만 게으른 아니고 잘못 것도 아니고 나쁘지 않아

442
00:26:29,080 --> 00:26:33,660
생활에 프로그램의 목적은 한 링크 목록을 시뮬레이션하는 것이다.

443
00:26:33,660 --> 00:26:35,460
그게 바로 우리가하고있는 일입니다.

444
00:26:35,460 --> 00:26:39,100
모든 기능에 통과해야 다음 주에이를 선언하고 자보다는

445
00:26:39,100 --> 00:26:42,640
우리가이 프로그램에 서면으로 작성했습니다, 우리는 대신 오 실현, 그냥이 글로벌하게 해 줍시다!

446
00:26:42,640 --> 00:26:47,060
이 프로그램의 전체 목적은 하나 하나의 연결된 목록을 입증 할 수 때문입니다.

447
00:26:47,060 --> 00:26:50,700
그럼 괜찮아요 느낀다. 여기 내 프로토 타입은, 우리는 이러한 모든 통과하지 않습니다

448
00:26:50,700 --> 00:26:55,800
하지만 삭제 기능을 찾을 기능, 삽입 기능 및 이송 기능을 썼습니다.

449
00:26:55,800 --> 00:26:59,080
그러나의 지금 삽입 함수에 내려 놔

450
00:26:59,080 --> 00:27:01,490
이 하나가 작동 방법을 참조하십시오.

451
00:27:01,490 --> 00:27:09,940
삽입 줄에 - 여기 우리는 간다.

452
00:27:09,940 --> 00:27:12,850
삽입합니다. 우리가 물을거야 때문에 그게 어떤 인수를 고려하지 않습니다

453
00:27:12,850 --> 00:27:15,930
그들은 삽입 할 수는이 기능의 사용자 내부.

454
00:27:15,930 --> 00:27:19,410
하지만 먼저, 우리는 그들에게 공간을 제공하기 위해 준비하고 있습니다.

455
00:27:19,410 --> 00:27:22,050
이것은 다른 예제 복사 및 붙여 넣기의 일종입니다.

456
00:27:22,050 --> 00:27:25,110
이 경우, 우리는 정수를 할당했다,이 시간 우리는 노드를 할당하고 있습니다.

457
00:27:25,110 --> 00:27:27,910
정말 노드가 얼마나 많은 바이트를 기억하지 않는,하지만 그건 괜찮아.

458
00:27:27,910 --> 00:27:30,460
Sizeof 나를 위해 그 방법을 찾아 내야 할 수 있습니다.

459
00:27:30,460 --> 00:27:33,340
그리고 왜 라인 120에 NULL을 확인 이유는 무엇입니까?

460
00:27:33,340 --> 00:27:37,530
라인 119에 잘못이 있겠 어? 응?

461
00:27:37,530 --> 00:27:40,530
[학생 답 이해할 수없는]

462
00:27:40,530 --> 00:27:43,440
좋아. 그냥 내가 너무 많은 메모리를 요구 한 경우 될 수

463
00:27:43,440 --> 00:27:47,020
또는 뭔가 잘못된 운영 체제, 내 말을 돌려주기에 충분한 바이트가 없습니다

464
00:27:47,020 --> 00:27:50,640
그래서 NULL을 반환하여 많은 신호를, 나는 그것에 대해 확인하지 않는 경우

465
00:27:50,640 --> 00:27:54,710
그냥 난 맹목적으로 주소가 반환 사용하는 수행은 NULL이 될 수 있습니다.

466
00:27:54,710 --> 00:27:58,400
그것은 알 수없는 값이 될 수 있습니다,하지 좋은 일하지 않는 I -

467
00:27:58,400 --> 00:28:00,590
실제로 알 수없는 값이 없습니다. 그것은 NULL 될 수, 제가 원하는 않도록

468
00:28:00,590 --> 00:28:02,550
그것을 악용하고 dereferencing 위험합니다.

469
00:28:02,550 --> 00:28:07,410
그렇게되면, 그냥 돌아 내가 전혀 기억이 돌아 오면 않은 것처럼 우리는 척 할거야.

470
00:28:07,410 --> 00:28:12,270
>> 그렇지 않으면, 사용자가 나에게 삽입 할 수있는 전화 번호를 알려 말해, 난 우리의 옛 친구 GetInt 전화

471
00:28:12,270 --> 00:28:15,530
그리고 이건 우리가 월요일에 도입 된 새로운 구문했다.

472
00:28:15,530 --> 00:28:20,320
'newptr -> N'당신이 malloc에​​ 의해 주어진있는 주소를 의미

473
00:28:20,320 --> 00:28:23,490
이는, 새로운 노드 객체의 첫 번째 바이트를 나타냅니다

474
00:28:23,490 --> 00:28:26,860
그리고 다음에 n이라는 필드로 이동합니다.

475
00:28:26,860 --> 00:28:35,270
작은 사소한 질문 :이 코드의 어떤 더 이상한 선에 동일합니다?

476
00:28:35,270 --> 00:28:38,110
어떻게 다른이를 쓸 수 있었 을까? 자상을 원하십니까?

477
00:28:38,110 --> 00:28:41,480
[학생 답 이해할 수없는]

478
00:28:41,480 --> 00:28:44,870
좋아. . n을 사용하지만이 같은 매우 간단한 게 아냐.

479
00:28:44,870 --> 00:28:47,090
처음 무엇을해야합니까? [학생 답 이해할 수없는]

480
00:28:47,090 --> 00:28:52,730
좋아. 나는 * newptr.n을 수행해야합니다.

481
00:28:52,730 --> 00:28:55,610
그래서이 새로운 포인터가 분명 주소 말하는 것입니다. 이유는 무엇입니까?

482
00:28:55,610 --> 00:28:59,520
이것은 malloc에​​ 의해 반환 된 때문입니다. 말을 *의 newptr은 "거기 갈"

483
00:28:59,520 --> 00:29:02,970
거기지면 그 다음에 당신이 더 친숙. n을 사용할 수 있습니다

484
00:29:02,970 --> 00:29:05,730
하지만이 우리 인간에 갈 특히, 조금 추해 보이

485
00:29:05,730 --> 00:29:10,360
화살표가있는 포인터 모든 시간을 그려, 세상이 화살표 표기법을 표준화 있으며,

486
00:29:10,360 --> 00:29:12,320
이는 정확히 같은 일을하지 않습니다.

487
00:29:12,320 --> 00:29:16,070
왼쪽에있는 것은 포인터 인 경우> 표기법 - 그래서 당신은 단지을 사용합니다.

488
00:29:16,070 --> 00:29:18,790
는 실제 구조체 있다면 그렇지 않으면,. n을 사용합니다.

489
00:29:18,790 --> 00:29:25,800
그리고이 : 왜 newptr -> 다음 초기화 말고 NULL 하는가?

490
00:29:25,800 --> 00:29:28,610
우리는 무대의 끝 매달려 왼쪽에서 필요하지 않습니다.

491
00:29:28,610 --> 00:29:31,630
우리는 바로 아래 가리켜되는데,이 목록의 끝을 의미

492
00:29:31,630 --> 00:29:34,980
가능성이 노드에있을 수 있습니다, 그래서 우리는 더이 NULL인지 확인하십시오.

493
00:29:34,980 --> 00:29:38,460
그리고 일반적으로 귀하의 변수 또는 데이터 멤버와 structs를 초기화

494
00:29:38,460 --> 00:29:40,470
뭔가 그냥 좋은 연습입니다.

495
00:29:40,470 --> 00:29:45,170
그냥 쓰레기가 존재하고 일반적으로 존재하는 계속 내버려 두는 게 문제에서 당신을 도착

496
00:29:45,170 --> 00:29:48,650
당신은 나중에 뭔가를 잊어 버린 경우.

497
00:29:48,650 --> 00:29:51,590
>> 여기 몇 가지 경우입니다. 이, 다시, 삽입 기능입니다

498
00:29:51,590 --> 00:29:54,930
변수가 먼저 전화하면 내가 확인 우선이다

499
00:29:54,930 --> 00:29:58,240
그 전역 변수가 NULL이며, 그 어떤 연결리스트가 없음을 의미합니다.

500
00:29:58,240 --> 00:30:02,460
우리는 어떤 번호를 삽입하지 않은 때문에이 현재의 번호를 삽입 할 수 하찮은입니다

501
00:30:02,460 --> 00:30:05,240
목록으로, 때문에 그냥 목록의 시작 부분에 포함되어 있습니다.

502
00:30:05,240 --> 00:30:08,100
아니타 그냥 그런 척, 혼자 여기 서 있을때 있도록였다

503
00:30:08,100 --> 00:30:11,390
우리가 노드를 할당 할 때까지 다른 사람은 무대에 여기 없었습니다

504
00:30:11,390 --> 00:30:13,940
그리고 그녀는 처음으로 손을 길렀다

505
00:30:13,940 --> 00:30:17,420
다른 사람들은 월요일에 그녀를 무대에 온다면.

506
00:30:17,420 --> 00:30:22,900
지금 여기,이 내가 말을 좀 확인이 경우 N의 새로운 노드의 값

507
00:30:22,900 --> 00:30:27,370
, 현재 첫 번째 노드에서 N의 값을 <입니다

508
00:30:27,370 --> 00:30:29,930
그 시작되었습니다 연결된 목록이있는 것을 의미합니다.

509
00:30:29,930 --> 00:30:32,330
이 목록에서 하나 이상의 노드는하지만이 새로운 사람

510
00:30:32,330 --> 00:30:37,230
그 때문에 우리가 주변에 물건을 이동해야하기 전에 속한다.

511
00:30:37,230 --> 00:30:43,450
목록, 그냥 시작하는 경우 즉,,, 말의하자

512
00:30:43,450 --> 00:30:48,100
단지 숫자 17 - 사실, 우리는 더 명확하게이 작업을 수행 할 수 있습니다.

513
00:30:48,100 --> 00:30:56,010
우리가 처음 불리는 포인터와 함께 우리의 이야기를 시작하면은,

514
00:30:56,010 --> 00:30:59,870
그리고 처음에는 NULL이고, 우리는 9 번을 삽입

515
00:30:59,870 --> 00:31:02,510
9 번 분명 목록의 시작 부분에 포함되어 있습니다.

516
00:31:02,510 --> 00:31:07,400
그래서 우리는 그냥 주소 또는 9 번을 malloced 여기 넣어가 가정합시다.

517
00:31:07,400 --> 00:31:13,170
먼저 기본적으로 구 경우, 우리가 논의 첫 번째 시나리오는 여기서 가자 지점이 사람을 의미합니다

518
00:31:13,170 --> 00:31:15,790
이 같은 NULL 떠나, 지금 우리는 9 번을 갖추고 있습니다.

519
00:31:15,790 --> 00:31:18,280
우리가 삽입 할 다음 숫자는 17입니다.

520
00:31:18,280 --> 00:31:22,420
17 여기에 속한다, 우리는이를 통해 몇 가지 논리적 인 스텝을해야 할거야.

521
00:31:22,420 --> 00:31:26,060
우리가의 우리가 숫자 8을 삽입하고 싶다고 가정하자 그런 짓을하기 전에 그래서 대신하자.

522
00:31:26,060 --> 00:31:28,650
>> 그러므로 편의의 위해, 여기 그리는거야.

523
00:31:28,650 --> 00:31:30,760
하지만 잊지마, malloc은 대부분 어느 곳을 넣을 수 있습니다.

524
00:31:30,760 --> 00:31:33,460
그러나 그림, 제발 여기를 넣어드립니다.

525
00:31:33,460 --> 00:31:38,440
그래서 난 숫자 8에 대한 노드를 할당 한 척,이는 기본적으로 NULL입니다.

526
00:31:38,440 --> 00:31:42,800
이제 무슨 일이 있어요? 가지 정도.

527
00:31:42,800 --> 00:31:47,090
우리가이 같은 포인터를 업데이트 곳 우리는 월요일에 무대에서이 실수를 한

528
00:31:47,090 --> 00:31:51,890
그런 다음이 이런 짓을하고 나서 우리는 주장 - 우리는 무대에서 다른 사람들을 고아.

529
00:31:51,890 --> 00:31:54,350
넌 할 수 없어 때문에 - 여기 작업의 순서는 중요합니다

530
00:31:54,350 --> 00:31:58,760
지금 있기 때문에 우리는 공간에 떠 일종의 경우이 노드 9 잃었습니다.

531
00:31:58,760 --> 00:32:01,150
그래서 월요일에 바로 접근 아니 었습니다.

532
00:32:01,150 --> 00:32:03,330
우리가 처음 다른 뭔가를해야합니다.

533
00:32:03,330 --> 00:32:06,280
세계의 상태는 다음과 같이 표시됩니다. 처음, 8가 할당되었습니다.

534
00:32:06,280 --> 00:32:10,550
어떻게 8 삽입 더 나은 방법이 될 것입니다?

535
00:32:10,550 --> 00:32:14,720
대신 먼저이 포인터를 업데이트 때문에, 대신에 그냥 여기에 하나를 업데이트합니다.

536
00:32:14,720 --> 00:32:17,720
그래서 우리는이 NULL 문자를 설정하는거야 코드의 라인이 필요합니다

537
00:32:17,720 --> 00:32:22,020
노드 9시 눈치 실제 포인터로,

538
00:32:22,020 --> 00:32:27,970
그리고 우리는 안전하게 여기에서이 남자를 가리 먼저 변경할 수 있습니다.

539
00:32:27,970 --> 00:32:31,330
이제 우리는 두 가지 요소의 목록을 연결리스트를 갖추고 있습니다.

540
00:32:31,330 --> 00:32:33,580
그리고이 사실은 여기 어떻게 생겼나요?

541
00:32:33,580 --> 00:32:36,900
우리가 코드를 보면, 나는 정확히 한 것을 확인할 수 있습니다.

542
00:32:36,900 --> 00:32:41,970
나는 newptr 말했듯이,이 이야기, newptr이 사람을 지목했다.

543
00:32:41,970 --> 00:32:45,520
>> 그럼 내가 한 가지가 더 그리하게, 나는 이것에 대한 좀 더 방을 떠난 거군요.

544
00:32:45,520 --> 00:32:48,540
그래서 작은 그림을 용서 하소서.

545
00:32:48,540 --> 00:32:52,140
이 사람 newptr라고합니다.

546
00:32:52,140 --> 00:32:57,940
우리가 라인에 몇 줄 이전에 선언 된 변수 - 25 위.

547
00:32:57,940 --> 00:33:03,430
그리고 8을 가리키고있어. 그래서 newptr -> 다음 말을 할 때, 구조체로 이동 의미

548
00:33:03,430 --> 00:33:07,910
newptr에 의해에서 지적하는 것은, 그래서 여기 우리가 거​​기로 가봐.

549
00:33:07,910 --> 00:33:13,990
그런 다음 화살표는 다음 필드를 말하는 있으며, 다음 =가 어떤 값을 넣어 있겠죠?

550
00:33:13,990 --> 00:33:17,280
어떤 값은 먼저입니다;? 먼저 된 값

551
00:33:17,280 --> 00:33:21,930
먼저이 이제이 노드에서 가리켜 의미하므로,이 노드에서 지적되었다.

552
00:33:21,930 --> 00:33:25,660
즉, 어떻게, 내 필적이있는 우스꽝 엉망이라도 보인다

553
00:33:25,660 --> 00:33:28,620
단지 주변에 화살표를 이동하는 간단한 뭐지

554
00:33:28,620 --> 00:33:31,560
이 한번의 라이너로 코드 변환합니다.

555
00:33:31,560 --> 00:33:38,110
다음 필드에 먼저 무엇 저장 한 후 처음으로 실제로 무엇 업데이트 할 수 있습니다.

556
00:33:38,110 --> 00:33:40,900
의이 중 일부를 미리와 빨리 감기 가자,

557
00:33:40,900 --> 00:33:44,220
지금이 꼬리 삽입에서만 봐.

558
00:33:44,220 --> 00:33:51,210
내가 어떤 노드의 다음 필드가 NULL이라는 것을 알게 요점 가정 해 보겠습니다.

559
00:33:51,210 --> 00:33:53,410
그리고 이야기, 자세히이 시점에서 난 다시 glossing 건

560
00:33:53,410 --> 00:33:58,170
I 줄 142, 전신 포인터에서 다른 포인터를 도입 한 것입니다.

561
00:33:58,170 --> 00:34:01,320
기본적으로 이야기의 시점에서 한 번 목록이 긴 나와서,

562
00:34:01,320 --> 00:34:04,800
난 가지 두 손가락으로 걸어야겠다 너무 멀리 가면 때문에,

563
00:34:04,800 --> 00:34:08,219
단일 길이 목록에서 기억, 당신은 거꾸로 갈 수 없어.

564
00:34:08,219 --> 00:34:13,659
따라서 predptr의 생각이 내 왼쪽 손가락이고, newptr -하지 newptr.

565
00:34:13,659 --> 00:34:17,199
여기에 또 다른 포인터가 내 다른 손가락이, 그리고 목록을 도보로 불과 했거든요.

566
00:34:17,199 --> 00:34:22,179
그 존재 이유입니다. 그러나의는 여기에 간단한 사례 중 하나를 고려 보자.

567
00:34:22,179 --> 00:34:26,620
그 포인터의 다음 필드가 NULL 인 경우, 논리적 함축 된 의미는 뭐죠?

568
00:34:26,620 --> 00:34:30,840
이 목록을 가로 지르는하고하는 경우에는 NULL 포인터를 친거야?

569
00:34:30,840 --> 00:34:35,780
당신은 목록의 끝 부분에 있어요, 코드는 다음이 하나의 추가 요소를 추가 할 수

570
00:34:35,780 --> 00:34:41,230
직관적 일종의은 그의 다음 포인터 NULL입니다 노드를 취할 것입니다

571
00:34:41,230 --> 00:34:46,120
그래서 현재 NULL이며, 새 노드의 주소로하지만, 그것을 변경합니다.

572
00:34:46,120 --> 00:34:52,260
그래서 우리는 우리가 다른 사람의 왼손을 마련하여 무대에 그린 코드에있는 화살표를 그리기하고 있습니다.

573
00:34:52,260 --> 00:34:54,070
>> 그리고 지금의 내 손을 흔들고하겠다고 경우,

574
00:34:54,070 --> 00:34:58,020
난 우리가 환경의 이러한 종류의에 할 때 길을 쉽게 생각해서,

575
00:34:58,020 --> 00:35:00,600
목록의 중간에 삽입을 확인합니다.

576
00:35:00,600 --> 00:35:03,220
알아내는하려는 경우 그러나 단지 직관적으로, 무슨 일이 일어 났을 할 필요가

577
00:35:03,220 --> 00:35:06,600
일부 번호는 중간에 속하는 곳은 걸어서해야하나요

578
00:35:06,600 --> 00:35:09,510
하나 이상의 손가락으로 하나 이상의 포인터

579
00:35:09,510 --> 00:35:12,920
이 검사에 의해 속한 곳을 파악하는 것은 요소 <현재 하나

580
00:35:12,920 --> 00:35:15,450
> 현재 하나 한 번 당신은 그 곳을 찾아

581
00:35:15,450 --> 00:35:20,400
그리고 당신은 매우 신중하게 주위 포인터를 이동 위치를 쉘 게임의 이러한 종류의 작업을 수행해야합니다.

582
00:35:20,400 --> 00:35:23,850
그리고 그 대답은, 자신의 집에서이 일을 이유로하려는 경우

583
00:35:23,850 --> 00:35:28,340
다운 단지 코드의 두 라인에 종기, 그러나 그 라인의 순서는 슈퍼 것이 중요합니다.

584
00:35:28,340 --> 00:35:31,390
당신이 누군가의 손에 내려 제기하는 경우 다른 사람이 잘못된 순서로하고 있기 때문

585
00:35:31,390 --> 00:35:34,580
다시, 당신은 목록을 orphaning 결국 수 있습니다.

586
00:35:34,580 --> 00:35:39,500
더 많은 개념적으로 요약하자면, 꼬리의 삽입은 비교적 간단합니다.

587
00:35:39,500 --> 00:35:42,940
머리의 삽입도 비교적 간단합니다

588
00:35:42,940 --> 00:35:45,580
하지만 추가 포인터에게이 시간을 업데이트해야합니다

589
00:35:45,580 --> 00:35:47,930
여기 목록에 5 번을 쥐어 짜기로,

590
00:35:47,930 --> 00:35:51,560
다음 중간에 삽입 더 많은 노력을 포함하여,

591
00:35:51,560 --> 00:35:56,130
매우 신중의 올바른 위치에 숫자 20를 삽입하려면,

592
00:35:56,130 --> 00:35:58,350
어느 17 22 사이입니다.

593
00:35:58,350 --> 00:36:02,700
당신은 22에 새 노드 20 점을 가지고있는 것처럼 일을해야하므로

594
00:36:02,700 --> 00:36:08,470
다음, 노드의 포인터가 마지막으로 업데이트해야합니다?

595
00:36:08,470 --> 00:36:10,630
그것은 실제로 삽입, 17 살이야.

596
00:36:10,630 --> 00:36:14,080
그러니 다시 특정 구현에 대한 실제 코드를 연기합니다.

597
00:36:14,080 --> 00:36:17,280
>> 언뜻보기에, 조금 압도적이지만, 그건 정말 무한 루프입니다

598
00:36:17,280 --> 00:36:21,770
즉,, 루프 루프, 루프, 루프, 그리고 NULL 포인터를 누르 자마자 소멸

599
00:36:21,770 --> 00:36:24,590
어떤 시점에서 당신이 필요한 삽입 할 수 있습니다.

600
00:36:24,590 --> 00:36:30,960
이 후, 담당자 연결리스트 삽입 코드입니다.

601
00:36:30,960 --> 00:36:34,590
, 그 많은 사람 이었어요, 우리는 한 가지 문제를 해결 한 것 같은데

602
00:36:34,590 --> 00:36:36,940
하지만 우리는 전혀 다른 하나를 도입했습니다. 솔직히, 우리는이 모든 시간을 보냈어요

603
00:36:36,940 --> 00:36:40,540
큰 O와 Ω에 더 신속하게 문제를 해결하기 위해 노력하고, 시간을 실행,

604
00:36:40,540 --> 00:36:43,270
여기 우리는 거꾸로, 기분 큰 단계를 취하고있다.

605
00:36:43,270 --> 00:36:45,380
그리고 아직 목표에 데이터를 저장하는 경우는,

606
00:36:45,380 --> 00:36:48,010
우리가 월요일에 말했다대로, 성배 같은 느낌, 정말로 것

607
00:36:48,010 --> 00:36:50,470
즉시 물건을 저장할 수 있습니다.

608
00:36:50,470 --> 00:36:53,930
>> 사실, 우리는 잠시 동안 넣어 따로 연결리스트 짓을했다고 가정

609
00:36:53,930 --> 00:36:56,000
우리는 대신 테이블의 개념을 도입했습니다.

610
00:36:56,000 --> 00:36:59,110
그리고 배열로 잠시 그​​냥 테이블을 생각 보자.

611
00:36:59,110 --> 00:37:03,790
이 배열이 사건은 여기서 몇 가지 요소 26, 25을 통해 0을 가지고

612
00:37:03,790 --> 00:37:07,940
당신이 이름을 저장의 일부 덩어리를 필요로하는 가정

613
00:37:07,940 --> 00:37:10,350
앨리스와 밥, 찰리,처럼.

614
00:37:10,350 --> 00:37:12,880
그리고 당신은 그 이름을 저장하기 위해 일부 데이터 구조가 필요합니다.

615
00:37:12,880 --> 00:37:15,000
글쎄, 당신은 연결리스트 같은 것을 사용할 수 있습니다

616
00:37:15,000 --> 00:37:20,260
당신은 등등 밥 한 후 밥과 찰리 전에 앨리스를 삽입 목록을 걸어 수 있습니다.

617
00:37:20,260 --> 00:37:23,850
그리고 사실, 당신은 옆으로 그런 식으로 코드를 보려면,

618
00:37:23,850 --> 00:37:27,230
list2.h, 우리는 정확히 어떻게 알고.

619
00:37:27,230 --> 00:37:30,610
우리는이 코드를 가지 않지만, 이번은 첫 번째 예제의 변형입니다

620
00:37:30,610 --> 00:37:34,640
우리가 소위 학생을 본 적이 다른 구조체를 소개합니다

621
00:37:34,640 --> 00:37:40,330
그리고 그런 일이 실제로 링크 된 목록에 저장하면 학생 구조에 대한 포인터입니다

622
00:37:40,330 --> 00:37:44,520
보다 간단한 약간의 정수, N.

623
00:37:44,520 --> 00:37:46,900
, 코드가 실제 문자열을 포함 저기 있군요 실현

624
00:37:46,900 --> 00:37:49,940
하지만 손에있는 목표는 이제 정말로 효율성 문제를 해결하는 것입니다 경우,

625
00:37:49,940 --> 00:37:53,380
우리가 앨리스라는 객체를 제공하는 경우가 좋지 않을까,

626
00:37:53,380 --> 00:37:56,020
우리는 데이터 구조의 정확한 위치에 그녀를 넣고 싶어요

627
00:37:56,020 --> 00:37:58,860
그냥 앨리스 넣어 정말 좋은 거라고 기분이,

628
00:37:58,860 --> 00:38:01,180
그의 이름은 첫 번째 위치에, A로 시작합니다.

629
00:38:01,180 --> 00:38:05,270
그리고 그의 이름은 두 번째 위치에, B로 시작 밥.

630
00:38:05,270 --> 00:38:09,580
배열로, 또는 그것을 테이블, 그에서 해시 테이블을 호출 시작하자

631
00:38:09,580 --> 00:38:13,650
우리는 정확히 할 수 있습니다. 우리가 앨리스와 같은 이름을 부여하는 경우는,

632
00:38:13,650 --> 00:38:16,700
앨리스 같은 문자열, 당신은 A-L-I-C-e를 어디에 배치해야합니까?

633
00:38:16,700 --> 00:38:20,540
우리는 hueristic가 필요합니다. 우리는 앨리스 같은 입력을하는 함수가 필요

634
00:38:20,540 --> 00:38:24,610
와 답변을 반환, "이 위치에서 앨리스 놔."

635
00:38:24,610 --> 00:38:28,720
그리고이 기능이 블랙 박스는 해쉬 함수 호출 할 것이다.

636
00:38:28,720 --> 00:38:32,330
>> 해쉬 함수는 "앨리스"와 같이 입력을 필요 것이지

637
00:38:32,330 --> 00:38:38,080
그리고 사용자에 대한 반환은 일반적으로 일부 데이터 구조의 숫자 위치는 앨리스가 있어야 할 곳.

638
00:38:38,080 --> 00:38:40,830
이 경우, 우리의 해쉬 함수는 상대적으로 간단합니다.

639
00:38:40,830 --> 00:38:47,510
우리 해쉬 함수는 당신이 문자 나에 대해 관심을 가져야 "앨리스"를 제공하는 경우라고해야하나요?

640
00:38:47,510 --> 00:38:55,660
첫 번째. 그래서 [0]보​​고, 그리고 나서 [0] 문자가있는 경우, 숫자 0을 반환 말한다.

641
00:38:55,660 --> 00:39:01,130
이 B면 1을 반환합니다. 그건 C 경우, 등등 2를 반환합니다.

642
00:39:01,130 --> 00:39:05,940
모든 공 색인, 그 등등 저 앨리스하고 밥하고 찰리를 삽입 할 수 있으며 것

643
00:39:05,940 --> 00:39:10,960
이 데이터 구조로. 하지만 문제가 있습니다.

644
00:39:10,960 --> 00:39:13,060
어떤 아니타가 다시 나타나서? 경우

645
00:39:13,060 --> 00:39:17,510
우리는 아니타 어디를 어떻게 삽입합니까? 그녀의 이름은도, A 문자로 시작

646
00:39:17,510 --> 00:39:20,330
우리가이 문제의 더 큰 혼란을 변경 한 것과 같아.

647
00:39:20,330 --> 00:39:24,380
우리는 지금 데이터 구조로 즉시 삽입, 일정 시간 삽입을 가지고

648
00:39:24,380 --> 00:39:27,100
오히려 악화의 경우보다 선형,

649
00:39:27,100 --> 00:39:29,510
그러나 우리는이 경우에 아니타와 함께 무엇을 할 수 있습니까?

650
00:39:29,510 --> 00:39:34,110
두 가지 옵션이 정말 무엇입니까? 응?

651
00:39:34,110 --> 00:39:37,410
[학생 답 이해할 수없는] 그래, 이제 또 다른 차원을 만들 수 있습니다.

652
00:39:37,410 --> 00:39:42,320
좋아. 그래서 우리는 우리가 월요일에 구두로 얘기했던 것처럼 3D로 사물을 구축 할 수 있습니다.

653
00:39:42,320 --> 00:39:46,700
우리는 여기에서 다른 액세스를 추가,하지만 난이 간단하게하려고했다고 가정 없었다.

654
00:39:46,700 --> 00:39:50,160
여기에 전체 목표는 즉시 일정한 시간 액세스 할 수 있어야합니다

655
00:39:50,160 --> 00:39:52,170
그래서 너무 많은 복잡성을 추가있어.

656
00:39:52,170 --> 00:39:55,970
이 데이터 구조로 아니타를 삽입하는 다른 옵션은 무엇입니까? 응?

657
00:39:55,970 --> 00:39:58,610
[학생 답 이해할 수없는 잘 됐네. 그래서 우리는 아래로 다른 사람을 움직일 수있다

658
00:39:58,610 --> 00:40:03,040
그녀가 정말되고 싶은 곳에서 찰리 밥과 앨리스, 아래 nudges과 같은 우리 아니타 넣어.

659
00:40:03,040 --> 00:40:05,660
>> 물론, 지금이 부작용이 있어요.

660
00:40:05,660 --> 00:40:09,000
이 데이터 구조는 우리가 사람들을 한 번 삽입하고 싶지 때문에 아마도 유용합니다

661
00:40:09,000 --> 00:40:11,250
하지만 우리는 그들이 나중에 거기가 있는지 확인하고 싶어서

662
00:40:11,250 --> 00:40:13,600
우리가 데이터 구조의 이름을 모두 인쇄하려는 경우.

663
00:40:13,600 --> 00:40:15,850
우리는 결국이 데이터에 뭔가 의미있는 일을 할 겁니다.

664
00:40:15,850 --> 00:40:20,810
이제 우리는 그녀가 있어야 할 곳은 더 이상없는 앨리스를 통해 망의 종류가 있어요.

665
00:40:20,810 --> 00:40:23,880
또한 밥이나 찰리 있습니다.

666
00:40:23,880 --> 00:40:26,060
아마 이건 좋은 생각이 아닙니다.

667
00:40:26,060 --> 00:40:28,830
그러나 실제로이 하나의 옵션입니다. 우리는 모두 아래로 이동 수

668
00:40:28,830 --> 00:40:32,240
또는 대체, 아니타는 게임에 늦게, 우리가 아니타를 안 넣을거야

669
00:40:32,240 --> 00:40:35,870
여긴 아니라고 여기, 여기, 그냥 목록에서 약간 낮은 그녀를 넣어 보자.

670
00:40:35,870 --> 00:40:38,680
하지만이 문제는 다시 바뀔하기 시작한다.

671
00:40:38,680 --> 00:40:41,630
당신은 그녀 이름에 따라 즉시 앨리스를 찾을 수 있습니다.

672
00:40:41,630 --> 00:40:44,320
그리고 즉시 밥, 그리고 찰리. 하지만 당신은 아니타을 찾아

673
00:40:44,320 --> 00:40:46,360
그리고 음,보고, 앨리스는 방법입니다.

674
00:40:46,360 --> 00:40:48,770
음, 내 이름은 앨리스 아래 확인하자. 밥은 아니타하지 않습니다.

675
00:40:48,770 --> 00:40:51,850
찰리는 아니타하지 않습니다. 아, 아니타이 있습니다.

676
00:40:51,850 --> 00:40:54,720
그리고 당신은 논리의 열차 모든 방법을 계속하는 경우

677
00:40:54,720 --> 00:41:00,690
이 새로운 데이터 구조로 찾거​​나 아니타를 삽입의 최악의 실행 시간은?

678
00:41:00,690 --> 00:41:03,280
그것은 바로, O (n)이있어?

679
00:41:03,280 --> 00:41:06,280
최악의 경우에 속하기 때문 앨리스, 밥, 찰리가 있습니다. . .

680
00:41:06,280 --> 00:41:10,150
모든 "Y"라는 사람에게 내려, 그래서 하나의 자리가 남았습니다.

681
00:41:10,150 --> 00:41:13,950
다행히, 우리는 "Z"라는 사람도없고, 그래서 우리가 맨 아래에 아니타 넣어.

682
00:41:13,950 --> 00:41:16,040
>> 우리가 정말이 문제를 해결하지 않았습니다.

683
00:41:16,040 --> 00:41:19,890
따라서 우리는이 3 차원을 도입 할 필요는 없어.

684
00:41:19,890 --> 00:41:22,230
우리가이 3 차원을 도입 않는 경우 그리고, 밝혀

685
00:41:22,230 --> 00:41:25,240
우리는 완벽하게이 작업을 수행 할 수 없지만, 성배가별로 될 것입니다

686
00:41:25,240 --> 00:41:28,370
일정한 시간 삽입 및 동적 삽입이 있으므로

687
00:41:28,370 --> 00:41:30,960
우리는 크기 26 하드 코드 배열 할 필요가 없습니다.

688
00:41:30,960 --> 00:41:34,400
우리가 원하는 우리는 많은 이름으로 삽입 할 수 있지만, 우선은 여기 5 분 휴식을

689
00:41:34,400 --> 00:41:38,790
그리고 제대로 해.

690
00:41:38,790 --> 00:41:46,020
괜찮아요. 난 정말 인위적가 이야기를 설정

691
00:41:46,020 --> 00:41:48,670
앨리스하고 밥하고 찰리 후 아니타를 선택하여

692
00:41:48,670 --> 00:41:51,000
그의 이름은 분명 앨리스과 충돌하려고 했어요.

693
00:41:51,000 --> 00:41:54,120
그러나 우리가 월요일에 종료 문제는 단지 얼마나 가능성이

694
00:41:54,120 --> 00:41:56,370
당신이 가지 충돌을 것이라고? 즉,

695
00:41:56,370 --> 00:42:00,490
우리가이 표 구조를 사용하기 시작하면되는데,이, 정말 배열입니다

696
00:42:00,490 --> 00:42:02,460
26 지역의 경우,

697
00:42:02,460 --> 00:42:05,740
우리의 입력 대신 균일하게 배포하는 경우 무엇입니까?

698
00:42:05,740 --> 00:42:09,620
그것은 인위적으로 앨리스와 밥, 찰리, 데이비드 아닙니다 등등 순으로,

699
00:42:09,620 --> 00:42:12,380
그것은 균일 Z.을 통해 통해 배포 있어요

700
00:42:12,380 --> 00:42:15,220
>> 어쩌면 우리는 운 좋으면 우리는 두의 또는 두 개의 B의를 할 수 없어

701
00:42:15,220 --> 00:42:17,640
누군가가 지적, 매우 높은 확률로하지만,로

702
00:42:17,640 --> 00:42:20,730
우리 일반화이 문제가 아니라 그렇게하면 0-25

703
00:42:20,730 --> 00:42:26,060
하지만, 말, 0 364이나 65, 전형적인 년의 일 종종 수,

704
00:42:26,060 --> 00:42:31,170
그리고 질문을 "이 방에있는 우리 둘은 같은 생일을 가지고있는 확률은 무엇입니까?"

705
00:42:31,170 --> 00:42:34,600
또 다른 방법을 넣어, 확률 우리 둘은로 시작하는 이름을 가지고 뭐​​죠?

706
00:42:34,600 --> 00:42:37,190
질문의 종류는 동일하지만,이 주소 공간

707
00:42:37,190 --> 00:42:39,940
이 검색 공간, 생일의 경우 더 큰

708
00:42:39,940 --> 00:42:42,820
우리는 알파벳의 문자보다 년에 너무 많은 일이 있기 때문.

709
00:42:42,820 --> 00:42:44,910
충돌의 확률은 무엇입니까?

710
00:42:44,910 --> 00:42:48,410
음, 우리는 수학에게 반대 방법을 계산하여 생각할 수 있습니다.

711
00:42:48,410 --> 00:42:50,580
노 충돌의 확률은 무엇입니까?

712
00:42:50,580 --> 00:42:53,970
자, 여기이 표현은 어떤 확률 래요

713
00:42:53,970 --> 00:42:58,770
그들은 독특한 생일이 방에 한 사람은이 있다면?이

714
00:42:58,770 --> 00:43:01,190
그것은 100 %입니다. 때문에 방에 한 사람이 있다면,

715
00:43:01,190 --> 00:43:03,940
자신의 생일 년에 365 일의 모든 수 있습니다.

716
00:43:03,940 --> 00:43:08,650
따라서 365분의 365 옵션은 나에게 하나의 값을 제공합니다.

717
00:43:08,650 --> 00:43:11,250
따라서 현재 문제의 확률은 1입니다.

718
00:43:11,250 --> 00:43:13,270
그러나 방에 두 사람이있을 경우,

719
00:43:13,270 --> 00:43:16,490
자신의 생일과는 다른 것입니다 확률은?

720
00:43:16,490 --> 00:43:20,680
단 364 수 일, 무시 도약 년가 있어요

721
00:43:20,680 --> 00:43:23,580
자신의 생일에 다른 사람과 충돌 할 수 없습니다.

722
00:43:23,580 --> 00:43:31,920
따라서 365분의 364. 다른 사람을 와서는 경우, 등등 365분의 363 야합니다.

723
00:43:31,920 --> 00:43:35,790
그래서 우리는 작아지고있는이 분수를 함께 곱한 유지

724
00:43:35,790 --> 00:43:40,720
알아내는 우리 모두가 독특한 생일을 가지고있는 확률은 무엇입니까?

725
00:43:40,720 --> 00:43:43,570
하지만 우리는 물론, 그 대답을하고 주변을 뒤집어

726
00:43:43,570 --> 00:43:47,210
그 1 마이너스 모두, 우리는 결국 얻을 것 표현식을

727
00:43:47,210 --> 00:43:51,250
귀하의 수학 책의 뒷면을 기억 경우,이 같은 뭔가를 조금 보입니다

728
00:43:51,250 --> 00:43:54,590
어떤이 훨씬 더 쉽게 그래픽으로 해석됩니다.

729
00:43:54,590 --> 00:43:57,820
그리고 여기이 그림은 X 축에 생일의 수를 가지고

730
00:43:57,820 --> 00:44:02,030
이나 생일 파티를 가진 사람들과 Y 축의의 번호와 일치의 확률입니다.

731
00:44:02,030 --> 00:44:06,060
그리고이 말하는 건, 당신이 경우에도, 보자 것입니다

732
00:44:06,060 --> 00:44:10,860
의 22, 23과 같은 무언가를 선택할 수 있습니다.

733
00:44:10,860 --> 00:44:13,160
방에있는 22 또는 23 명이이 있다면

734
00:44:13,160 --> 00:44:17,100
이 매우 소수의 사람들 만 두가 같은 생일을 가야하는 확률

735
00:44:17,100 --> 00:44:19,560
combinatorially, 실제로 슈퍼 높습니다.

736
00:44:19,560 --> 00:44:23,450
50 % 확률이 거의 이제 22 명 세미나의 수업에

737
00:44:23,450 --> 00:44:25,790
사람들 2 같은 생일을 가지고 갈 수 있습니다.

738
00:44:25,790 --> 00:44:28,520
때문에 같은 생일을 가질 수있는 많은 방법이 있습니다.

739
00:44:28,520 --> 00:44:31,110
더 나쁜 것은, 당신이 차트의 오른쪽 보면,

740
00:44:31,110 --> 00:44:34,040
시간에 당신은 거기에 58 학생들과 함께 수업을

741
00:44:34,040 --> 00:44:39,270
생일을 갖는 2 인 확률은 슈퍼, 슈퍼 높이 거의 100 %입니다.

742
00:44:39,270 --> 00:44:41,880
자, 실제 생활에 대한 재미있는 사실의 일종 이죠.

743
00:44:41,880 --> 00:44:45,850
>> 그러나 의미는, 이제, 데이터 구조 및 저장 정보

744
00:44:45,850 --> 00:44:51,100
당신의 데이터 멋진, 깨끗하고 균일 한 분포를 가정 있다는 것을 의미

745
00:44:51,100 --> 00:44:53,650
당신은 사물의 무리에 맞는 충분히 큰 배열을 가지고

746
00:44:53,650 --> 00:44:59,360
당신은 고유 한 위치에있는 사람을 만나게 될 거예요 의미하지 않는다.

747
00:44:59,360 --> 00:45:03,810
당신은 충돌을 할 겁니다. 때 이름으로, 해시의 개념 그래서

748
00:45:03,810 --> 00:45:07,450
"앨리스"와 같은 입력을 복용하고 어떤 방법에 마사지

749
00:45:07,450 --> 00:45:10,190
그리고 0 또는 1 또는 2와 같은 답변을 다시 받고.

750
00:45:10,190 --> 00:45:17,500
그 기능의 일부 출력을 다시 얻기 것은 충돌의 확률에 감염되어 있습니다.

751
00:45:17,500 --> 00:45:19,530
그럼 우리는 그 충돌을 처리 할 수​​ 있습니까?

752
00:45:19,530 --> 00:45:21,940
음, 한 사건에, 우리는 제안 된 아이디어를 취할 수 있습니다.

753
00:45:21,940 --> 00:45:25,100
우리는 좀 더 간단하게, 어쩌면 모든 사람을 이동하거나, 수

754
00:45:25,100 --> 00:45:29,870
차라리 다른 이동 사람들보다, 그냥 사용할 수있는 곳의 맨 아래에 아니타를 이동 보자.

755
00:45:29,870 --> 00:45:32,810
앨리스가 0에하면, 밥은 1이며, 찰리는 2에

756
00:45:32,810 --> 00:45:35,260
우리는 위치 3시 아니타을 올려 놓을 게요.

757
00:45:35,260 --> 00:45:38,860
그리고이 프로빙 선형이라는 데이터 구조의 기술입니다.

758
00:45:38,860 --> 00:45:41,310
당신은이 줄을 걸어, 당신은 프로빙의 일종이야 선형 때문에

759
00:45:41,310 --> 00:45:43,640
데이터 구조에서 사용할 수있는 장소에.

760
00:45:43,640 --> 00:45:46,210
물론,이 O (N)에 devolves.

761
00:45:46,210 --> 00:45:49,590
데이터 구조가 정말 가득 경우, 25 사람들은 이미이

762
00:45:49,590 --> 00:45:54,120
그리고 아니타이 클 그녀는 위치 Z는 무엇입니까 쳐다 끝내고, 괜찮아요.

763
00:45:54,120 --> 00:45:56,540
그녀는 여전히 맞는, 우리는 나중에 그녀를 찾을 수 있습니다.

764
00:45:56,540 --> 00:46:00,100
>> 하지만이 일을 속도의 목표에 반하는했다.

765
00:46:00,100 --> 00:46:02,530
우리가 대신이 3 차원을 도입 어쩌죠?

766
00:46:02,530 --> 00:46:06,400
그 기술은 일반적으로 별도의 체인이라고, 또는 체인을 가지고 있습니다.

767
00:46:06,400 --> 00:46:10,030
그리고 해시 테이블은 이제이 표 구조하는 일

768
00:46:10,030 --> 00:46:13,450
테이블은 포인터의 배열입니다.

769
00:46:13,450 --> 00:46:18,230
그런데 그 포인터가 가리키는 것은 추측 무엇입니까?

770
00:46:18,230 --> 00:46:21,970
연결 목록입니다. 우리는이 세계의 모두의 가장을 어쩌죠?

771
00:46:21,970 --> 00:46:26,500
우리는 초기 인덱스에 배열을 사용하여

772
00:46:26,500 --> 00:46:32,070
데이터 구조로 그래서 우리는 즉시, [1], [30] 또는 등등 [0]로 이동할 수 있습니다

773
00:46:32,070 --> 00:46:36,480
하지만, 우리는 유연성을 가지고 우리는 아니타와 앨리스와 아담에 맞게 수

774
00:46:36,480 --> 00:46:38,630
및 기타 이름,

775
00:46:38,630 --> 00:46:43,470
우리는 대신 다른 축이 임의의 성장 보자.

776
00:46:43,470 --> 00:46:47,340
그리고 우리는 결국 월요일로 연결된 목록과 그 표현 기능이 있습니다.

777
00:46:47,340 --> 00:46:49,530
우리는 임의로 데이터 구조를 증가 할 수 있습니다.

778
00:46:49,530 --> 00:46:52,450
또한, 우리는, 큰 2 차원 배열을 만들 수

779
00:46:52,450 --> 00:46:57,190
하지만 그 경우 끔찍한 상황이 될거에요 2 차원 배열의 행 중 하나

780
00:46:57,190 --> 00:47:01,280
그의 이름은 A.으로 시작하는 일이 추가 사람만큼 큰되지 않습니다

781
00:47:01,280 --> 00:47:04,200
맙소사 우리는 거대한 2 차원 구조를 할당해야

782
00:47:04,200 --> 00:47:06,600
라는 많은 사람들이있어해서

783
00:47:06,600 --> 00:47:09,480
Z 뭔가라는 이름 때문에 몇 사람이 특히.

784
00:47:09,480 --> 00:47:12,170
이건 그냥 아주 희박한 데이터 구조 될거야.

785
00:47:12,170 --> 00:47:15,400
그럼 어떤 방법으로, 완벽 하진 않지만 이제 우리는 적어도 수 있습니다

786
00:47:15,400 --> 00:47:19,090
앨리스 나 아니타가 있어야 할 곳 바로 찾으려면

787
00:47:19,090 --> 00:47:21,090
적어도 수직 축 측면에서,

788
00:47:21,090 --> 00:47:25,850
그리고 우리는이 연결 목록에서 아니타 또는 앨리스 넣어 위치를 결정해야합니다.

789
00:47:25,850 --> 00:47:32,480
우리가 일을 분류 상관하지 않는 경우, 얼마나 빨리 우리는이 같은 구조로 앨리스를 삽입 할 수?

790
00:47:32,480 --> 00:47:35,370
이 상수 시간이다. [0]에 우리는 색인, 아무도 거기에,

791
00:47:35,370 --> 00:47:37,550
앨리스는 연결리스트의 시작 부분에갑니다.

792
00:47:37,550 --> 00:47:40,000
하지만 그건 큰 문제가 아니에요. 아니타는 함께 온다면 때문에

793
00:47:40,000 --> 00:47:42,160
몇 가지 단계 수 후 아니타는 어디에 속해 있습니까?

794
00:47:42,160 --> 00:47:45,140
음, [0]. OOP. 앨리스는 그 링크는 이미 목록에 있습니다.

795
00:47:45,140 --> 00:47:47,760
>> 그러나 우리는이 이름을 정렬인지를 신경 쓰지 않을 때는,

796
00:47:47,760 --> 00:47:53,580
우리는 앨리스 이상, 삽입 아니타을 이동할 수 있지만 심지어는 일정 시간입니다.

797
00:47:53,580 --> 00:47:57,010
앨리스와 아담과 전혀 다른 이름,이 경우에도

798
00:47:57,010 --> 00:47:59,410
정말 물리적으로 이동 않아. 이유는 무엇입니까?

799
00:47:59,410 --> 00:48:04,090
우리가 알고있는 연결 목록과 함께했기 때문이 노드 근데거야?

800
00:48:04,090 --> 00:48:06,550
당신이해야 할 모든 빵 부스러기를 이동합니다.

801
00:48:06,550 --> 00:48:10,930
주위에 화살표를 이동, 당신은 실제로 주위에 데이터를 이동할 필요가 없습니다.

802
00:48:10,930 --> 00:48:14,610
그래서 우리는 즉시 그 경우, 아니타를 삽입 할 수 있습니다. 상수 시간.

803
00:48:14,610 --> 00:48:20,250
그래서 우리는 일정 시간 조회 및 아니타 같은 사람의 일정한 시간 삽입되어 있습니다.

804
00:48:20,250 --> 00:48:22,740
그러나 세계를 지나치게 단순화 종류의.

805
00:48:22,740 --> 00:48:28,510
우리가 나중에 앨리스를 찾으려면?

806
00:48:28,510 --> 00:48:31,050
우리가 나중에 앨리스를 찾으려면?

807
00:48:31,050 --> 00:48:35,690
얼마나 많은 단계 그건 걸릴까요?

808
00:48:35,690 --> 00:48:37,850
[학생 답 이해할 수없는]

809
00:48:37,850 --> 00:48:40,950
그렇지. 연결리스트의 앨리스하기 전에 사람들의 수.

810
00:48:40,950 --> 00:48:45,420
우리의 데이터 구조, 다시이 수직 액세스 할 수 있기 때문에 그래서 아주 완벽 하진

811
00:48:45,420 --> 00:48:50,240
다음은 교수형이 연결된 목록을 가지고 - 사실, 그렇게 배열을 그려하지 맙시다.

812
00:48:50,240 --> 00:48:56,020
그것은이 연결 목록과 같은 작은 선물을 보이는 그것을 매달려있다.

813
00:48:56,020 --> 00:48:59,110
하지만 문제는 경우 Alice와 아담과 모든 다른 이름

814
00:48:59,110 --> 00:49:01,720
거기 더 살게

815
00:49:01,720 --> 00:49:04,810
누군가가 단계 많이 복용 결국 수 찾기,

816
00:49:04,810 --> 00:49:06,670
당신이 연결된 목록을 통과해야 bcause

817
00:49:06,670 --> 00:49:08,090
이는 선형 작업입니다.

818
00:49:08,090 --> 00:49:14,270
그래서 정말 다음, 삽입 시간은 궁극적으로 n은 목록에있는 요소의 개수입니다 O (n은)입니다.

819
00:49:14,270 --> 00:49:21,780
으로 나눈 값, 어디 임의로 그 m은 링크 된 목록의 번호입니다 m, 전화 할게

820
00:49:21,780 --> 00:49:24,500
우리는이 수직 축에 있다고.

821
00:49:24,500 --> 00:49:27,180
즉, 우리가 진정으로 이름의 균일 한 분포를 가정하면,

822
00:49:27,180 --> 00:49:30,150
완전히 비현실적인. 다른 사람보다 몇 글자 분명 더있어.

823
00:49:30,150 --> 00:49:32,580
>> 하지만 우리는 지금 균일 분포에 대한 가정하면,

824
00:49:32,580 --> 00:49:37,350
우리는 총 사람, m 총 체인 습니했습니다

825
00:49:37,350 --> 00:49:40,630
이러한 체인 각각의 우리에게 다음 길이

826
00:49:40,630 --> 00:49:44,380
공정 단순히 총 N 체인 수로 나눈 될 것입니다.

827
00:49:44,380 --> 00:49:48,900
따라서 N / m. 우리 모두가 수학적으로 영리 할 수​​있는 그러나 여기입니다.

828
00:49:48,900 --> 00:49:53,030
이들의 고정 된 번호가 있기 때문에 m은 상수입니다.

829
00:49:53,030 --> 00:49:54,620
당신은 시작에서 배열을 선언 할거야

830
00:49:54,620 --> 00:49:58,450
우리는 크기 조정 세로 축을 아니에요. 정의함으로써, 고정 유지됩니다 그.

831
00:49:58,450 --> 00:50:01,220
정말 변경 것은, 이야기 만 가로 축입니다.

832
00:50:01,220 --> 00:50:04,760
따라서 엄밀히 말해서,이 상수입니다. 그래서 지금, 삽입 시간

833
00:50:04,760 --> 00:50:09,700
거의 O (n)이됩니다.

834
00:50:09,700 --> 00:50:12,410
그럼이 모든 것을 훨씬 더 기분이되지 않습니다.

835
00:50:12,410 --> 00:50:14,940
그러나 진실은 뭐죠? 음,이 시간, 주,

836
00:50:14,940 --> 00:50:20,640
우리는 말한 적 O (N ²). O (N), 2 X N ², - N, 2로 나눈 값입니다. . . 르샤.

837
00:50:20,640 --> 00:50:23,580
단지 N ²입니다. 하지만 지금은 학기의이 부분에

838
00:50:23,580 --> 00:50:25,560
우리는 다시 현실 세계에 대해 얘기를 시작할 수 있습니다.

839
00:50:25,560 --> 00:50:31,520
그리고 N / m 혼자 습니보다 절대적으로 빠릅니다.

840
00:50:31,520 --> 00:50:35,170
당신은 이름이 수 천 개를 가지고 있고, 여러 개의 버킷으로 올려 어기면

841
00:50:35,170 --> 00:50:37,820
당신은 이러한 체인의 각 단 10 이름이 있도록

842
00:50:37,820 --> 00:50:41,670
절대적으로 열 가지를 검색하면 수천 가지보다 더 빨리 될 것입니다.

843
00:50:41,670 --> 00:50:43,740
그리고 다가오는 문제 세트 중 하나에 도전 것입니다

844
00:50:43,740 --> 00:50:46,100
정확히 그것에 대해 생각해하더라도, 그래,

845
00:50:46,100 --> 00:50:49,520
점근 적 및 수학적으로이 아직도 선형이며,

846
00:50:49,520 --> 00:50:51,700
것을 발견 할 때 이는 일반적으로됐다.

847
00:50:51,700 --> 00:50:54,530
현실에서, 그보다 더 빨리 될거야

848
00:50:54,530 --> 00:50:56,520
이 때문에 제수의.

849
00:50:56,520 --> 00:50:58,310
그리고 다시 트레이드 오프가 되려고하고 있어요

850
00:50:58,310 --> 00:51:01,390
그리고 이론과 현실 간의 갈등,

851
00:51:01,390 --> 00:51:03,550
그리고 손잡이 중 하나는 학기에이 시점에서 회전을 시작합니다

852
00:51:03,550 --> 00:51:07,510
우리가 약간 semster의 최종 준비로 현실 하나의 이상이며,

853
00:51:07,510 --> 00:51:09,280
우리는 웹 프로그래밍의 세계를 소개로

854
00:51:09,280 --> 00:51:11,530
사용자가로 갈거야 왜냐면, 정말로 성능이 셀 것입니다

855
00:51:11,530 --> 00:51:14,880
가난한 디자인 결정을 느끼고 감사하기 시작한다.

856
00:51:14,880 --> 00:51:19,950
>> 당신은 링크를 구현하는 일은 정말 어떻게해야할까요 - 해시 테이블을 31 요소와?

857
00:51:19,950 --> 00:51:22,600
그리고 앞의 예는 생일에 대해 임의로이었다.

858
00:51:22,600 --> 00:51:26,190
사람이 1 월 1 2월 1일의 생일이있는 경우, 우리는이 양동이에 넣어드립니다.

859
00:51:26,190 --> 00:51:28,960
가 1 월 2 년 2 월 2 일 3월 2일면, 우리는이 양동이에 넣어드립니다.

860
00:51:28,960 --> 00:51:32,220
가 31 살 이유입니다. 어떻게 해시 테이블을 선언합니까?

861
00:51:32,220 --> 00:51:37,480
그것은 꽤 간단 될 수 노드 * 표는 그것을 위해 내 임의의 이름, [31]입니다.

862
00:51:37,480 --> 00:51:42,400
이것은 노드에 저에게 31 포인터를 제공합니다

863
00:51:42,400 --> 00:51:45,370
이 날 링크 목록 31 포인터를 할 수 있도록

864
00:51:45,370 --> 00:51:48,800
그 사슬에서 처음 NULL 경우에도.

865
00:51:48,800 --> 00:51:54,860
제가 저장하려는 경우 "밥", "찰리" "앨리스"를 넣어 원하는 게 뭐야?

866
00:51:54,860 --> 00:51:57,010
음, 우리는 구조에서 그 물건을 포장 할 필요가

867
00:51:57,010 --> 00:52:00,530
우리는 앨리스, 밥을 가리 키도록 찰리을 가리 키도록, 등등. 필요 하거든요

868
00:52:00,530 --> 00:52:04,940
우리는 단지 혼자의 이름을 가질 수 없습니다, 그래서 여기 노드라는 새로운 구조를 만들 수 있습니다.

869
00:52:04,940 --> 00:52:08,310
>> 실제 노드는 무엇입니까? 이 새로운 연결 목록에서 노드는 무엇입니까?

870
00:52:08,310 --> 00:52:11,840
단어라고 첫 번째 문제는, 그 사람의 이름입니다.

871
00:52:11,840 --> 00:52:14,340
길이는, 아마, 인간의 이름의 최대 길이에 관한

872
00:52:14,340 --> 00:52:18,210
그게 무엇이든, 20, 미친 코너의 경우 30, 40 문자

873
00:52:18,210 --> 00:52:22,680
그리고 한 무엇입니다? 그것은 단지 여분의 NULL 문자, \ 0입니다.

874
00:52:22,680 --> 00:52:27,410
그래서이 노드는 내부 자체의 "무언가"를 배치하고 있습니다

875
00:52:27,410 --> 00:52:29,640
뿐만 아니라 옆에라는 포인터를 선언

876
00:52:29,640 --> 00:52:32,580
우리가 찰리 밥 체인 앨리스 수 등등 그.

877
00:52:32,580 --> 00:52:36,700
NULL이 될 수 있지만 반드시 할 필요는 없습니다.

878
00:52:36,700 --> 00:52:40,110
이 해시 테이블에서 질문? 응?

879
00:52:40,110 --> 00:52:46,190
[학생 이해할 수없는, 질문을] 배열 - 좋은 질문입니다.

880
00:52:46,190 --> 00:52:50,120
왜 배열보다는 숯불 *이 숯불 단어는?

881
00:52:50,120 --> 00:52:53,830
이 다소 임의의 예에서, 나는 의지하고 싶지 않았어

882
00:52:53,830 --> 00:52:56,190
원래 이름의 각 malloc합니다.

883
00:52:56,190 --> 00:52:59,530
나는 문자열 메모리의 최대 양을 선언하고 싶어

884
00:52:59,530 --> 00:53:06,020
난 앨리스 \ 0이 아닌이 malloc과 무료 등 처리해야하는 구조로 복사 할 수 있도록.

885
00:53:06,020 --> 00:53:11,710
나는 공간 사용을 더 의식되고 싶어한다면 난 할 수있어. 좋은 질문입니다.

886
00:53:11,710 --> 00:53:14,780
그래서 멀리 일반화하려고 두자

887
00:53:14,780 --> 00:53:18,350
더 일반적으로 데이터 구조에서 오늘의 나머지 부분에 초점을

888
00:53:18,350 --> 00:53:21,170
우리는 같은 기본을 사용하여 해결할 수있는 다른 문제

889
00:53:21,170 --> 00:53:24,590
심지어 데이터 구조 불구하고 자신은 세부 사항에 다를 수 있습니다.

890
00:53:24,590 --> 00:53:27,910
>> 따라서 컴퓨터 과학에서 밝혀, 나무는 매우 일반적이다.

891
00:53:27,910 --> 00:53:29,760
그리고 당신은 가족 나무처럼의 나무 종류 생각할 수

892
00:53:29,760 --> 00:53:31,830
일부 뿌리, 일부 암컷 대장 또는 가장이있는 곳

893
00:53:31,830 --> 00:53:34,540
할머니 나 할아버지 또는 이전 버전으로 돌아

894
00:53:34,540 --> 00:53:38,880
어떤 아래에 엄마, 아빠 또는 여러 형제 자매 또는 마음입니다.

895
00:53:38,880 --> 00:53:42,500
따라서 트리 구조 노드를 가지고 있으며 아이들이

896
00:53:42,500 --> 00:53:45,260
각 노드에 대해 일반적으로 0 또는 더 많은 아이들.

897
00:53:45,260 --> 00:53:47,320
그리고 전문 용어의 일부가 여기이 그림에 표시되는

898
00:53:47,320 --> 00:53:50,630
이 가장자리에있는 작은 아이들이나 손자들의

899
00:53:50,630 --> 00:53:52,330
누가 그들에서 냄새가 나는데도 화살표가 없습니다

900
00:53:52,330 --> 00:53:55,070
그는 소위 잎, 그리고 내부에있는 사람 아르

901
00:53:55,070 --> 00:53:58,790
내부 노드입니다, 당신은 그것을 그 라인을 따라 뭔가를 호출 할 수 있습니다.

902
00:53:58,790 --> 00:54:01,430
그러나이 구조는 매우 일반적입니다. 이 녀석은 좀 임의입니다.

903
00:54:01,430 --> 00:54:04,930
우리는 우리가 오른쪽에 세 명의 아이가, 왼쪽에서 한 아이가

904
00:54:04,930 --> 00:54:06,830
아래에 두 아이들은 떠났다.

905
00:54:06,830 --> 00:54:10,740
그래서 우리는, 우리가 일을 표준화하기 시작하면 다른 크기의 나무가 있지만, 수

906
00:54:10,740 --> 00:54:15,330
그리고 당신은 이전 짧은에서 이진 검색 패트릭의 동영상에서이 기억 수도 있습니다

907
00:54:15,330 --> 00:54:19,490
온라인 이진 검색 배열 구현하실 필요가 없습니다

908
00:54:19,490 --> 00:54:21,410
칠판에 종이 또는 조각.

909
00:54:21,410 --> 00:54:25,490
당신은보다 정교한 데이터 구조에 번호를 저장하고 싶어하고 있다고 가정합시다.

910
00:54:25,490 --> 00:54:27,680
이 같은 나무를 만들 수 있습니다.

911
00:54:27,680 --> 00:54:35,290
당신은 C에 선언 노드를 가질 수 있으며, 해당 노드 안에 그것의 적어도 두 개의 요소를 가질 수 있습니다.

912
00:54:35,290 --> 00:54:39,470
하나는 당신이 저장할 수 있으며, 다른 하나는 - 글쎄, 우리는 하나가 더 필요합니다.

913
00:54:39,470 --> 00:54:41,540
다른 하나는 그 자식입니다.

914
00:54:41,540 --> 00:54:45,150
그래서 여기가 다른 데이터 구조입니다. 이 시간은, 노드는 N 번호를 저장로 정의됩니다

915
00:54:45,150 --> 00:54:49,060
그리고 후 두 포인터, 왼쪽 자녀 및 오른쪽 아이.

916
00:54:49,060 --> 00:54:52,100
그리고 임의 아니에요. 어떻게이 나무에 대한 재미있는이야?

917
00:54:52,100 --> 00:55:00,550
>> 우리가 패트릭가 비디오에 배치하는 방법이 배치하거나 한 방법에 패턴은 무엇입니까?

918
00:55:00,550 --> 00:55:02,790
그것은 이곳에서 몇 가지 분류가 그런 종류의 확실

919
00:55:02,790 --> 00:55:04,460
하지만 간단한 규칙이 뭐지? 응?

920
00:55:04,460 --> 00:55:08,350
[학생 답 이해할 수없는]

921
00:55:08,350 --> 00:55:12,040
좋아요. 이 흘끗 경우, 당신은 왼쪽에있는 작은 숫자를 참조하십시오

922
00:55:12,040 --> 00:55:14,690
큰 왼쪽에있는 숫자,하지만 모든 노드에 대한 사실입니다.

923
00:55:14,690 --> 00:55:20,370
각 노드를 들어,보다는 자사의 왼쪽 아이가 덜하고,보다 권리의 자녀가 더.

924
00:55:20,370 --> 00:55:25,210
전 그 번호 44, 말,이 데이터 구조를 검색하려면이게 지금 의미하는 것은,

925
00:55:25,210 --> 00:55:29,320
나는 왜냐하면 지금이 더 복잡한 데이터 구조의 모든과 마찬가지로, 루트에서 시작해야

926
00:55:29,320 --> 00:55:31,910
우리는 처음, 한 가지에 대한 포인터가 있습니다.

927
00:55:31,910 --> 00:55:35,010
이 경우에는 처음의 루트입니다. 그것은, 왼쪽 끝이 아니야

928
00:55:35,010 --> 00:55:39,530
만약이 구조의 루트입니다. 그래서 여기 55입니다보고 싶어하지만 난 44 찾고 있어요.

929
00:55:39,530 --> 00:55:41,430
어떤 방향으로 가야할까요?

930
00:55:41,430 --> 00:55:45,680
분명, 오른쪽으로 너무 좋을 것 때문에 음, 왼쪽으로 가고 싶어요.

931
00:55:45,680 --> 00:55:49,050
그래서 여기 발견, 당신은 개념적 반으로 나무를 자르고의 일종이야

932
00:55:49,050 --> 00:55:51,700
당신은 오른쪽 아래로 못하실 거예요 때문입니다.

933
00:55:51,700 --> 00:55:55,410
그래서 지금은 55에서 33로 이동합니다. 이 숫자의 너무 작아.

934
00:55:55,410 --> 00:56:01,590
나는 44을 찾고 있는데, 지금은 44이 나무에있는 경우, 오른쪽에 분명 갈 수있어.

935
00:56:01,590 --> 00:56:04,460
그러니 다시 치기 절반으로 나무입니다.

936
00:56:04,460 --> 00:56:06,780
이 전화 번호부에 개념적으로 거의 동일입니다.

937
00:56:06,780 --> 00:56:09,510
그것은 우리가 칠판에 종이로 무슨 짓을하고 똑같아요

938
00:56:09,510 --> 00:56:13,940
하지만 우리가 실제로 할 수있는보다 정교한 구조 네요

939
00:56:13,940 --> 00:56:16,880
이, 나눠서 알고리즘의 설계에 의해 정복

940
00:56:16,880 --> 00:56:19,420
그리고 사실, 이와 같은 구조를 가로 지르는 - 아하하.

941
00:56:19,420 --> 00:56:22,870
이와 같은 구조를 가로 지르는 것은, 그 밖에 어디 "이 길을 갈거나 길을 갈"

942
00:56:22,870 --> 00:56:26,870
섹션에서 구현할 때 처음에는 마음을 굽어 모든 코드를 의미

943
00:56:26,870 --> 00:56:31,270
또는 재귀 또는 반복을 사용하여, 이진 검색, 집에서 그것을 통해 도보

944
00:56:31,270 --> 00:56:35,060
그것은 목에 통증이 있습니다. 중간 요소를 찾기 다음 라운딩 위로 또는 아래로 해.

945
00:56:35,060 --> 00:56:39,230
>> 우리가 다시 재귀를 사용할 수 있기 때문에 아름다움이 할 필요가

946
00:56:39,230 --> 00:56:43,760
하지만 훨씬 더 깔끔하게. 사실, 당신이 55 번에이고 44를 찾으려면,

947
00:56:43,760 --> 00:56:48,450
이 경우 왼쪽으로가는 다음 어떻게해야하나요? 당신은 동일한 알고리즘을 실행합니다.

948
00:56:48,450 --> 00:56:51,560
당신은 노드의 값을 확인 한 다음 왼쪽 또는 오른쪽으로 이동합니다.

949
00:56:51,560 --> 00:56:53,670
그런 다음 왼쪽 또는 오른쪽으로 이동하여 노드의 값을 확인하십시오.

950
00:56:53,670 --> 00:56:56,710
이것은 완벽하게 재귀에 적합합니다.

951
00:56:56,710 --> 00:57:00,920
그래서,하지만 과거에 우리는 재귀를 포함한 몇 가지 매우 임의의 예제를 했어요

952
00:57:00,920 --> 00:57:03,430
즉, 데이터 stuctures과 재귀 할 필요가 없었다

953
00:57:03,430 --> 00:57:07,820
특히 나무, 이건 문제가 복용의 아이디어의 완벽한 응용 프로그램입니다

954
00:57:07,820 --> 00:57:12,920
를 축소 한 다음, 같은 종류의,하지만 작은 프로그램을 해결.

955
00:57:12,920 --> 00:57:14,590
>> 그래서 우리가 도입 할 수있는 다른 데이터 구조가 있습니다.

956
00:57:14,590 --> 00:57:18,760
이 하나는 암호화 살펴 한눈에 설계,이 하나는 놀라워하고 있습니다.

957
00:57:18,760 --> 00:57:25,090
그래서이는 단어 검색에서 상속 trie, trie라는 데이터 구조입니다

958
00:57:25,090 --> 00:57:30,210
이는 다시 시도 - 발을 발음,하지만 그건 세상은 이런 것들을 부르는되지 않습니다. 시도합니다. T-R-I-5.

959
00:57:30,210 --> 00:57:35,190
그것은 일종의 트리 구조이지만, trie의 각 노드

960
00:57:35,190 --> 00:57:41,280
모습을? 이 축약 종류이기 때문에이 조금 잘못된 것입니다.

961
00:57:41,280 --> 00:57:45,960
그러나이 trie의 각 노드가 실제로 배열입니다 것 같습니다.

962
00:57:45,960 --> 00:57:48,840
그리고 비록이 그림의 저자를 표시하지 않았습니다

963
00:57:48,840 --> 00:57:54,130
이 경우,이 trie는 그 목적 생활에 단어를 저장하는 것입니다 데이터 구조입니다

964
00:57:54,130 --> 00:57:57,330
A-L-I-C-E 또는 B-O-B처럼.

965
00:57:57,330 --> 00:58:02,480
그리고 그 길을 어떤에서 등등이 데이터 저장 앨리스와 밥, 찰리, 아니타와

966
00:58:02,480 --> 00:58:06,970
그것은 trie의 앨리스를 저장하는 상기 배열을 사용합니다

967
00:58:06,970 --> 00:58:09,820
우리는 배열처럼 보이는 루트 노드에서 시작

968
00:58:09,820 --> 00:58:12,080
그리고 그것은 속기 표기법으로 기록되어있어.

969
00:58:12,080 --> 00:58:15,070
그게 더 이름이 없었 때문에 저자는 abcdefg 생략.

970
00:58:15,070 --> 00:58:19,150
그들은 단지 M과 P와 T를 갖게했지만이 경우

971
00:58:19,150 --> 00:58:22,780
의는 여기에 일부 이름에 떨어진 앨리스와 밥과 찰리 이동하세요.

972
00:58:22,780 --> 00:58:25,670
맥스웰이 다이어그램에서 실제로 있습니다.

973
00:58:25,670 --> 00:58:29,570
그럼 저자 저장소를 한 M--X-w-E-L-리터?에게

974
00:58:29,570 --> 00:58:36,990
그 또는 그녀는 루트 노드에서 시작, 그리고에 가서 [M], 그래서 대략 13, 배열의 13 위치.

975
00:58:36,990 --> 00:58:40,750
그런 다음 거기에서, 포인터가 있습니다.

976
00:58:40,750 --> 00:58:42,760
다른 배열로 이어지는 포인터.

977
00:58:42,760 --> 00:58:47,880
그곳에서 저자는, 왼쪽 상단이 묘사로, 위치에 그 배열로 인덱스

978
00:58:47,880 --> 00:58:52,250
그리고 그 또는 그녀가 다른 배열에 해당 포인터를 따라

979
00:58:52,250 --> 00:58:55,460
및 위치 X.에서 포인터에 가서

980
00:58:55,460 --> 00:58:59,840
그런 다음 등등 다음 배열 위치 W, E, L, L, 및에

981
00:58:59,840 --> 00:59:03,090
마지막으로,의 사실이에 사진을 넣어 봅시다.

982
00:59:03,090 --> 00:59:05,380
코드에서 같은 노드 모습은 무엇입니까?

983
00:59:05,380 --> 00:59:11,820
trie에있는 노드가 더 많은 노드에 대한 포인터의 배열을 포함하고 있습니다.

984
00:59:11,820 --> 00:59:16,090
뿐만 아니라 적어도 구현에서, 부울 값 어떤 종류의이있어.

985
00:59:16,090 --> 00:59:18,770
나는 is_word 전화 발생합니다. 이유는 무엇입니까?

986
00:59:18,770 --> 00:59:22,670
당신은 맥스웰를 삽입 할 때, 당신은 삽입하지 않으니까

987
00:59:22,670 --> 00:59:25,300
이 데이터 구조에 무엇이든.

988
00:59:25,300 --> 00:59:27,480
귀하는 X를 작성하지 M.를 작성하지

989
00:59:27,480 --> 00:59:30,240
당신이하고있는 모든 포인터 다음과 같은 것입니다.

990
00:59:30,240 --> 00:59:33,360
다음 M, A를 나타내는 포인터를 나타냅니다 포인터

991
00:59:33,360 --> 00:59:36,310
다음엔 X, W, E, L, L을 나타냅니다 포인터

992
00:59:36,310 --> 00:59:41,950
하지만 니가 마지막에 할 필요 체크인, 가지의 종류이며,이 위치에 도달했습니다.

993
00:59:41,950 --> 00:59:45,560
데이터 구조에 여기에 끝나는 단어가 발생했습니다.

994
00:59:45,560 --> 00:59:48,190
>> 그래서 trie에 정말 가득하고 저자는 대표 선택합니다

995
00:59:48,190 --> 00:59:51,880
작은 삼각형을 통해 이러한 terminuses.

996
00:59:51,880 --> 00:59:56,470
사실이 그저 사실은이 삼각형 여기 있다는 것을 의미,이 부울 값

997
00:59:56,470 --> 00:59:59,200
이 트리에서 뒤로 이동하면,

998
00:59:59,200 --> 01:00:02,420
그 맥스웰이에라는 단어를 의미합니다.

999
01:00:02,420 --> 01:00:04,870
예를 들어,하지만 단어 foo는,

1000
01:00:04,870 --> 01:00:07,970
, 트리에없는 제가 맨 위에 여기에 루트 노드에서 시작하면,

1001
01:00:07,970 --> 01:00:14,030
더 F 포인터, 아니 오 포인터, 아니 오 포인터가 없습니다. foo는이 사전의 이름이 아닙니다.

1002
01:00:14,030 --> 01:00:22,460
그러나 반대로, 튜링, t-U-R-I-N-g. 다시, 나는 t 또는 u 또는 R 또는 I 또는 n 또는 g를 저장하지 못했습니다.

1003
01:00:22,460 --> 01:00:29,820
하지만 여기이 노드의 진정한 방법의 값이 데이터 구조에 저장 짓을 - 트리에서

1004
01:00:29,820 --> 01:00:33,030
true로 is_word이 Boolean 값을 설정하여.

1005
01:00:33,030 --> 01:00:35,740
그래서 trie이 매우 흥미로운 메타 구조의 종류입니다

1006
01:00:35,740 --> 01:00:39,810
당신은 정말 사전 이런 종류의 단어 스스로를 저장하지 곳.

1007
01:00:39,810 --> 01:00:45,100
명확하게하려면, 당신은 단지 예, 아니오로 저장하지 마, 여기에 끝나는 단어가 있습니다.

1008
01:00:45,100 --> 01:00:46,430
>> 이제 의미가 뭐야?

1009
01:00:46,430 --> 01:00:51,120
당신은 메모리에 저장하기 위해 노력하는 사전 150,000 단어가있는 경우

1010
01:00:51,120 --> 01:00:53,400
연결리스트 같은 것을 사용하여

1011
01:00:53,400 --> 01:00:56,870
귀하의 링크 목록에서 150,000 노드를 갖게 돼있다.

1012
01:00:56,870 --> 01:01:00,250
그리고 알파벳 순으로 단어 중 하나를 찾는 것은 O (n)이 시간이 걸릴 수 있습니다.

1013
01:01:00,250 --> 01:01:04,370
선형 시간. 그러나 trie의 여기 경우에,

1014
01:01:04,370 --> 01:01:09,210
단어를 찾는 실행 시간은?

1015
01:01:09,210 --> 01:01:17,390
여기의 아름다움을 밝혀 즉 당신은 이미 사전에 149,999 단어를 경우에도

1016
01:01:17,390 --> 01:01:20,170
본 데이터 구조를 구현,

1017
01:01:20,170 --> 01:01:25,560
에 앨리스 같은 앨리스 한 사람을 찾거나 삽입 할 시간이 얼마나 걸립니까?

1018
01:01:25,560 --> 01:01:30,640
음, 뒤에 캐릭터 어쩌면 6 단계, 5입니다.

1019
01:01:30,640 --> 01:01:32,880
때문에 구조에있는 다른 이름의 presense

1020
01:01:32,880 --> 01:01:35,340
앨리스를 삽입의 방법으로하지 않습니다.

1021
01:01:35,340 --> 01:01:39,640
또한, 앨리스를 찾는 것이이 사전의 150,000 단어가 있습니다되면

1022
01:01:39,640 --> 01:01:41,960
모든의 앨리스를 찾는 당신의 방식으로하지 않습니다

1023
01:01:41,960 --> 01:01:46,880
앨리스는 때문입니다. . . . . 여기 때문에 Boolean 값을 발견했습니다.

1024
01:01:46,880 --> 01:01:50,920
그리고 더 부울 사실, 그리고 앨리스가없는 경우 단어의 데이터 구조에 포함되어 있지 않습니다.

1025
01:01:50,920 --> 01:01:56,220
즉,이 새에 물건을 물건을 발견하고 삽입의 실행 시간

1026
01:01:56,220 --> 01:02:01,920
trie의 데이터 구조의 O입니다 - 그것은 습니 않아.

1027
01:02:01,920 --> 01:02:05,730
150,000명의 presense 앨리스에 아무런 영향을 미치지 않기 때문에, 그것은 보인다.

1028
01:02:05,730 --> 01:02:11,560
의는 K 영어 단어의 최대 길이입니다 K, 전화 놔

1029
01:02:11,560 --> 01:02:14,050
이는 일반적으로 더 이상 20 일 문자보다 수 없습니다.

1030
01:02:14,050 --> 01:02:17,940
따라서 k는 상수입니다. 성배 그래서 우리가 지금 발견 한 것 같습니다

1031
01:02:17,940 --> 01:02:26,000
삽입물에 대한 trie, 일정한 시간이 그 삭제에 대해 조회를 들어, 수 있습니다.

1032
01:02:26,000 --> 01:02:29,170
때문에 이미 구조의 가지 수,

1033
01:02:29,170 --> 01:02:32,600
이는 물리적으로도이 없습니다. 다시 말하지만, 그들은 단지 확인란의 선택이 해제되어 분류하고 예, 아니오

1034
01:02:32,600 --> 01:02:35,050
미래 실행 시간에 아무런 영향을 미치지 않습니다.

1035
01:02:35,050 --> 01:02:37,940
>> 그러나 캐치있을거야, 그렇지 않으면 우리는 많은 시간을 낭비하지 않았을

1036
01:02:37,940 --> 01:02:41,460
모든 다른 데이터 구조에 불과 드디어 놀라운 비밀 하나를 얻을 수 있습니다.

1037
01:02:41,460 --> 01:02:46,410
그래서 가격이 우리가 여기이 위대함을 달성하기 위해 지불? 공간.

1038
01:02:46,410 --> 01:02:49,010
이 것은 엄청난 것입니다. 그리고 그 이유 그 저자

1039
01:02:49,010 --> 01:02:52,400
여기에 제시되지 않았 눈치 배열과 같이이 모든 일 즉,

1040
01:02:52,400 --> 01:02:55,400
그는 나무의 나머지 trie의 나머지를 그린 적 없어요

1041
01:02:55,400 --> 01:02:58,060
그냥 이야기와 관련이없는니까.

1042
01:02:58,060 --> 01:03:01,870
하지만이 노드의 모든 다양한 슈퍼 있으며, 트리의 모든 노드가 걸립니다

1043
01:03:01,870 --> 01:03:07,780
26 사실,이 경우에는 나는 아포스트로피를위한 공간을 포함했기 때문에 27 문자 일 수도

1044
01:03:07,780 --> 01:03:09,980
그래야 우리가 apostrophized 단어가있을 수 있습니다.

1045
01:03:09,980 --> 01:03:14,450
이 경우, 이것들은 다양한 배열입니다. 그들은 picutured되지 않도록하더라도,

1046
01:03:14,450 --> 01:03:18,190
이 RAM의 거대한 양을 차지한다.

1047
01:03:18,190 --> 01:03:20,670
어떤 현대적인 하드웨어에서 especilly, 괜찮아 질 거라고

1048
01:03:20,670 --> 01:03:25,650
하지만 그게 거래 때문이에요. 우리는 더 많은 공간을 소비하여 짧은 시간을.

1049
01:03:25,650 --> 01:03:28,580
어디이 모든거야?

1050
01:03:28,580 --> 01:03:32,640
그럼, 한번 해보자 구 - 여기 보자.

1051
01:03:32,640 --> 01:03:39,510
여기이 남자 점프를하자.

1052
01:03:39,510 --> 01:03:43,450
>> 믿거 나 말거나, C, 지금 약간의 시간에 대한왔다만큼 재미 있고,

1053
01:03:43,450 --> 01:03:48,130
우리는 더 많은 현대적인 것들로 전환 할 시간이 다예요 학기의 지점에 도달하고 있습니다.

1054
01:03:48,130 --> 01:03:50,950
높은 수준의 것들. 그리고 앞으로 수주에 대한하지만

1055
01:03:50,950 --> 01:03:54,580
우리는 여전히 포인터와 메모리 관리의 세계에 자신을 빠져 계속해서

1056
01:03:54,580 --> 01:03:57,210
우리가 다음에 구축 할 수있는 그 편안함을 얻으려면,

1057
01:03:57,210 --> 01:04:01,270
최종 게임이 언어, 아이러니하게도, 아니 소개하는 궁극적입니다.

1058
01:04:01,270 --> 01:04:03,330
우리는 HTML에 대해 얘기 10 분 거리, 지출됩니다.

1059
01:04:03,330 --> 01:04:05,950
HTML이 모든 마크 업 언어입니다, 그리고 마크 업 언어입니다

1060
01:04:05,950 --> 01:04:10,220
'이 일이 굵게'라고 오픈 브래킷과 닫힌 괄호 이러한 일련의

1061
01:04:10,220 --> 01:04:12,000
'이 중심을'이 기울임 꼴 만들기 '.'

1062
01:04:12,000 --> 01:04:14,250
이 모든 지적 재미있는 건 아니지만, 유용 됐네요.

1063
01:04:14,250 --> 01:04:16,650
그리고 확실히 요즘 편재입니다.

1064
01:04:16,650 --> 01:04:19,450
하지만 어떻게 HTML의 세계에 대한 강력한, 그리고 웹 프로그래밍 더 일반적으로,

1065
01:04:19,450 --> 01:04:25,910
동적 물건을 구축하고있다, PHP 나 파이썬이나 루비 또는 Java 또는 C #과 같은 언어로 코드를 작성.

1066
01:04:25,910 --> 01:04:30,360
정말, 무슨 일이든 선택의 당신의 언어가 있으며, 동적 HTML 생성.

1067
01:04:30,360 --> 01:04:32,960
동적으로 CSS라는 것을 생성.

1068
01:04:32,960 --> 01:04:35,810
캐스 케이 딩 스타일 시트, 미학에 관한 것입니다.

1069
01:04:35,810 --> 01:04:41,360
그리고 심지어, 오늘, 나는 알고 Google.com 같은 웹 사이트로 이동하는 경우

1070
01:04:41,360 --> 01:04:46,100
그래서, 아마도 당신은 전에했던 개발자, 소스보기,보기로 이동

1071
01:04:46,100 --> 01:04:49,800
하지만 소스를 볼 것,이 물건은 아마도 꽤 이상한 보입니다.

1072
01:04:49,800 --> 01:04:55,320
그러나 이것은 Google.com을 구현하는 기본 코드입니다.

1073
01:04:55,320 --> 01:04:57,940
프런트 엔드에서. 그리고 실제로이 모든 상황이 보송 보송 한 미학의 콘텐츠입니다.

1074
01:04:57,940 --> 01:05:01,740
이 여기에 CSS 달려 있습니다. 난 스크롤을 유지하는 경우 몇 가지 색으로 구분되는 물건을받을 수 있습니다.

1075
01:05:01,740 --> 01:05:06,890
이 HTML입니다. Google의 코드는 엉망처럼 보이지만 사실은 다른 창을 열면

1076
01:05:06,890 --> 01:05:09,380
우리는이에 몇 가지 구조를 볼 수 있습니다.

1077
01:05:09,380 --> 01:05:12,640
제가이 일을 열 경우 여기를 발견, 좀 더 읽기입니다.

1078
01:05:12,640 --> 01:05:16,850
우리는 오래 전부터이 태그를 만나러가는 중이 야, [단어] 태그입니다,

1079
01:05:16,850 --> 01:05:23,520
HTML, 머리, 몸, 사업부, 스크립트, 텍스트 영역, 기간, 중심 사업부.

1080
01:05:23,520 --> 01:05:26,770
그리고이 또한 한눈에 알 수없는 수준의 정렬되어 있습니다

1081
01:05:26,770 --> 01:05:30,890
하지만이 난장판 모든 특정 패턴 및 반복 패턴을 다음과

1082
01:05:30,890 --> 01:05:33,850
일단 기본을 내려 있도록이 같은 코드를 작성 할 수 있습니다

1083
01:05:33,850 --> 01:05:37,550
그리고 자바 스크립트라는 또 다른 언어를 사용하여이 같은 코드를 조작.

1084
01:05:37,550 --> 01:05:40,440
그리고 자바 스크립트는 브라우저의 내부 실행 언어입니다

1085
01:05:40,440 --> 01:05:44,380
Google은 Google지도에서 사용하는 코스 쇼핑 도구에 하버드 과정에 사용하는 오늘날

1086
01:05:44,380 --> 01:05:48,660
당신에게 동성의 전체 무리를 제공하기 위해 페이스 북은 인스턴트 상태 업데이트를 표시 할 수 있습니다

1087
01:05:48,660 --> 01:05:51,430
트위터는 즉시 당신에게 트윗을 보여을 사용합니다.

1088
01:05:51,430 --> 01:05:53,820
이 모든 우리는 우리 자신을 인치 빠져을 시작합니다

1089
01:05:53,820 --> 01:05:57,190
그러나 거기에 도착하기 위해 인터넷에 대해 좀 이해할 필요가있다.

1090
01:05:57,190 --> 01:06:01,130
여기에 클립이 그저 분 거리에 있습니다, 지금이은, 사실 가정합시다하면,

1091
01:06:01,130 --> 01:06:08,380
인터넷 올 관한 일에 대한 티저로 작동하는 방식. 당신에게 "인터넷의 전사를."제공

1092
01:06:08,380 --> 01:06:14,720
>> [♫ 느린 합창 음악 ♫]

1093
01:06:14,720 --> 01:06:20,450
[남성 나레이터] 그는 메시지와 함께.

1094
01:06:20,450 --> 01:06:23,770
프로토콜 모두 자신이 있습니다.

1095
01:06:23,770 --> 01:06:37,270
[♫ 빠른 전자 음악 ♫]

1096
01:06:37,270 --> 01:06:41,330
그는 라우터 무관심한, 멋진 방화벽의 세계에 온

1097
01:06:41,330 --> 01:06:45,690
죽음보다 훨씬 더 위험.

1098
01:06:45,690 --> 01:06:55,400
그는 빨라요. 그는 강한입니다. 그는 TCP / IP이고, 그는 주소를 있어요.

1099
01:06:55,400 --> 01:06:59,250
인터넷의 전사.

1100
01:06:59,250 --> 01:07:05,290
[Malan] 다음 주, 그럼. 인터넷. 웹 프로그래밍. 이 CS50입니다.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]