1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [섹션 6 : 이하 편안한]

2
00:00:02,730 --> 00:00:05,040
[네이트 Hardison] [하버드 대학]

3
00:00:05,040 --> 00:00:07,320
[이 CS50 수 있습니다.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
괜찮아요. 제 6에 오신 것을 환영합니다.

5
00:00:11,840 --> 00:00:14,690
이번 주, 우리는 섹션에서 데이터 구조에 대해 이야기 할 수있을 것

6
00:00:14,690 --> 00:00:19,780
이번 주 문제는 spellr에 자리 잡고 주로하기 때문에

7
00:00:19,780 --> 00:00:24,410
다른 데이터 구조 탐험의 전체 무리는하지 않습니다.

8
00:00:24,410 --> 00:00:26,520
이 문제 세트 함께 갈 수있는 여러 가지 방법이 몰려있다

9
00:00:26,520 --> 00:00:31,570
그리고 당신이 알고있는 더 많은 데이터 구조, 당신이 할 수있는 더 멋진 일들.

10
00:00:31,570 --> 00:00:34,990
>> 그럼 시작하자. 먼저 우리는 스택에 대해 이야기 할거야

11
00:00:34,990 --> 00:00:37,530
우리가 얘기하는거야하는 스택과 큐 데이터 구조.

12
00:00:37,530 --> 00:00:40,560
우리가 그래프에 대해 얘기 시작할 때 스택과 큐, 정말 도움

13
00:00:40,560 --> 00:00:44,390
우리는 지금 너무 많은 일을 할거야 안된다.

14
00:00:44,390 --> 00:00:52,820
하지만 CS의 가장 큰 기본 데이터 구조 중 하나를 이해하기 정말 잘하네요.

15
00:00:52,820 --> 00:00:54,880
문제 세트 사양에 설명

16
00:00:54,880 --> 00:00:59,260
유사한으로 스택에 대한 당신이 그것을 뽑아 경우, 대화

17
00:00:59,260 --> 00:01:05,239
당신이 식당 홀에서 식당에서 가지고 식사 트레이의 더미

18
00:01:05,239 --> 00:01:09,680
식당 직원이 와서 그들이 청소 한 후, 식사 트레이를 만들어 곳 때

19
00:01:09,680 --> 00:01:12,000
그들은 그들에게 다른 상단에 하나를 쌓아.

20
00:01:12,000 --> 00:01:15,050
그리고 아이들은 음식을 사러 올 때

21
00:01:15,050 --> 00:01:19,490
그들은 먼저 상단 하나 트레이를 당겨 다음, 그 아래 한 다음, 그 아래 한.

22
00:01:19,490 --> 00:01:25,190
그래서, 효과, 식당 직원은 내려 놓고하는 첫 번째 줄 이륙됩니다 마지막 하나입니다.

23
00:01:25,190 --> 00:01:32,330
식당 직원이 입고있는 마지막 하나는 저녁 식사를 위해 이륙됩니다 첫 번째입니다.

24
00:01:32,330 --> 00:01:38,100
당신이 이미하지 않은 경우이 문제 세트의 사양에, 당신은 어떤을 다운로드 할 수 있습니다

25
00:01:38,100 --> 00:01:46,730
우리는 이런 종류의 구조체를 사용하여 스택 데이터 stucture를 모델링에 대해 이야기.

26
00:01:46,730 --> 00:01:51,070
>> 그래서 우리가 가진 게 무엇,이 강의에서 제시 한 것과 유사합니다

27
00:01:51,070 --> 00:01:58,120
강의를 제외하고 우리는 숯불 * s에 반하여 ints로이를 제시했다.

28
00:01:58,120 --> 00:02:06,250
이 그 가게 어떤 스택하실 건가요?

29
00:02:06,250 --> 00:02:09,009
다니엘? 우리는이 스택에 무엇을 저장하는거야?

30
00:02:09,009 --> 00:02:15,260
[다니엘] 문자열? >> 우리는 분명,이 스택에 문자열을 저장합니다.

31
00:02:15,260 --> 00:02:20,950
당신이 스택을 만들려면이 필요합니다 모든 배열입니다

32
00:02:20,950 --> 00:02:23,920
특정 용량의이 경우있는

33
00:02:23,920 --> 00:02:28,020
용량은 상수이기 때문에 모두 대문자로 될 것입니다.

34
00:02:28,020 --> 00:02:36,340
그리고 배열뿐만 아니라, 우리가 추적해야하는 모든 배열의 현재 크기입니다.

35
00:02:36,340 --> 00:02:38,980
하는 진짜 멋진 일이지 여기서주의해야 할 점

36
00:02:38,980 --> 00:02:47,060
우리가 다른 데이터 구조, 배열의 상단에 스택 데이터 구조를 작성하는 것입니다.

37
00:02:47,060 --> 00:02:50,110
스택을 구현하는 여러 가지 방법이 있습니다.

38
00:02:50,110 --> 00:02:54,250
우리는하지만, 희망적으로 연결된 목록 문제 일 후, 아직 그렇게하지 ​​않습니다

39
00:02:54,250 --> 00:03:00,520
당신은 쉽게뿐만 아니라 연결된 목록의 상단에 스택을 구현하는 방법을 볼 수 있습니다.

40
00:03:00,520 --> 00:03:02,640
그러나 지금, 우리는 배열에 충실합니다.

41
00:03:02,640 --> 00:03:06,350
그러니 다시 우리가 필요로하는 모든 배열이며, 우리는 배열의 크기를 추적해야합니다.

42
00:03:06,350 --> 00:03:09,850
[샘] 죄송합니다, 왜 당신이 스택 문자열 위에 말했다입니까?

43
00:03:09,850 --> 00:03:13,440
문자열은 스택 내에있는 식으로는 같습니다.

44
00:03:13,440 --> 00:03:16,790
[Hardison] 그래. 우리는 우리 어레이 데이터 구조를하고, 만드는거야 -

45
00:03:16,790 --> 00:03:22,130
정말 좋은 질문입니다. 그래서 질문은이 온라인을 감상하는 사람들을 위해, 왜

46
00:03:22,130 --> 00:03:24,140
왜 우리는, 스택 문자열의 상단에 있다는 말을

47
00:03:24,140 --> 00:03:27,990
여기에는 문자열은 스택 안에있는 것 같습니다? 때문에

48
00:03:27,990 --> 00:03:31,050
어느 완전히 경우가 있습니다.

49
00:03:31,050 --> 00:03:34,660
내가 얘길하는 것은 우리가 배열 데이터 구조를 가지고 한 것이 었습니다.

50
00:03:34,660 --> 00:03:39,290
우리는 숯불 * s의 배열, 문자열의 배열을 해

51
00:03:39,290 --> 00:03:45,300
우리는 스택 데이터 구조를 생성하기 위해 해당에 추가 할 수 있습니다.

52
00:03:45,300 --> 00:03:48,620
>> 따라서 스택은 배열보다 약간 더 복잡합니다.

53
00:03:48,620 --> 00:03:51,890
우리는 스택을 구축 할 배열을 사용할 수 있습니다.

54
00:03:51,890 --> 00:03:55,810
우리는 스택이 배열의 상단에 내장되어 말 몫이다.

55
00:03:55,810 --> 00:04:02,510
마찬가지로, 내가 전에 말했듯이, 우리는 링크 목록의 상단에 스택을 구축 할 수 있습니다.

56
00:04:02,510 --> 00:04:04,960
대신 우리의 요소를 보유 할 배열을 사용,

57
00:04:04,960 --> 00:04:10,070
우리는 우리의 요소를 개최하고 주위 스택을 구축하는 링크 목록을 사용할 수 있습니다.

58
00:04:10,070 --> 00:04:12,420
몇 가지 코드를보고, 그럼 예를 몇 통과하자,

59
00:04:12,420 --> 00:04:14,960
실제로 여기서 무슨 일이 있었는지 확인합니다.

60
00:04:14,960 --> 00:04:23,400
왼쪽에서, 그 스택 구조체가 메모리에 모습을 버려 한

61
00:04:23,400 --> 00:04:28,330
용량은 # 포워드하도록 정의 된 경우.

62
00:04:28,330 --> 00:04:33,490
우리는 우리의 네 요소 숯불 * 배열이 있어요.

63
00:04:33,490 --> 00:04:38,110
우리는 문자열 [0] 문자열 [1], 문자열 [2] 문자열 [3]이 있어요

64
00:04:38,110 --> 00:04:43,800
그런 다음 크기의 정수에 대한 마지막 공간.

65
00:04:43,800 --> 00:04:46,270
이 말이 돼? 좋아요.

66
00:04:46,270 --> 00:04:48,790
이건 내가 오른쪽에 무엇한다면 어떤 일이 일어입니다

67
00:04:48,790 --> 00:04:55,790
내 코드 할 것입니다, 그냥 구조체, S라는 스택 구조체를 선언하는 것입니다.

68
00:04:55,790 --> 00:05:01,270
이것은 우리가 얻을거야. 이 메모리에서이 발자국을 보내고.

69
00:05:01,270 --> 00:05:05,590
여기서 첫 번째 질문이 스택 구조체의 내용이 무엇입니까입니까?

70
00:05:05,590 --> 00:05:09,250
지금 그들은 아무것도 아냐,하지만 그들은 완전히 아무것도하지 않습니다.

71
00:05:09,250 --> 00:05:13,300
그들은 쓰레기 이러한 종류의하고 있습니다. 우리는 아무 생각 그 안에 뭐가 있는지이 없습니다.

72
00:05:13,300 --> 00:05:17,000
우리가 스택을 선언 할 때, 우리는 메모리의 상단에 그를 던져 요.

73
00:05:17,000 --> 00:05:19,840
이 정수 i를 선언하고 초기화하지 않은 거 가지입니다.

74
00:05:19,840 --> 00:05:21,730
거기 엔 뭐가 들어 있는지 알아하지 않습니다. 당신이 거기에 뭐가 읽을 수 있습니다

75
00:05:21,730 --> 00:05:27,690
하지만 도움이 슈퍼 영웅이 될하지 않을 수 있습니다.

76
00:05:27,690 --> 00:05:32,680
니가 항상 기억하고 싶은 한 가지가 초기화해야합니다 무엇이든 초기화합니다.

77
00:05:32,680 --> 00:05:35,820
이 경우, 우리는 제로로 크기를 초기화 할거야

78
00:05:35,820 --> 00:05:39,960
그 우리를 위해 매우 중요하다고 판명 겁니다 때문입니다.

79
00:05:39,960 --> 00:05:43,450
우리는 가서 포인터의 모든 문자 * s을, 초기화 할 수

80
00:05:43,450 --> 00:05:49,670
아마도 null이 어떤 이해 값이 있어야합니다.

81
00:05:49,670 --> 00:05:58,270
그러나 우리가 그렇게 할 수있는 완전히 필요가 없습니다.

82
00:05:58,270 --> 00:06:04,200
>> 이제 스택에있는 두 개의 주요 작업은?

83
00:06:04,200 --> 00:06:07,610
사람은 스택으로 뭘 강연에서 기억나요? 그래?

84
00:06:07,610 --> 00:06:09,700
[스텔라]는 넘기고 터지는? 정확히 >>.

85
00:06:09,700 --> 00:06:13,810
넘기고 터지는 것은 스택에있는 두 개의 주요 작업입니다.

86
00:06:13,810 --> 00:06:17,060
그리고 푸시 어떻게합니까? >>이 상단에 뭔가를두고

87
00:06:17,060 --> 00:06:19,300
스택의 후 다시 시도해가 벗겨집니다.

88
00:06:19,300 --> 00:06:23,150
[Hardison] 그렇지. 그래서 밀어은 스택의 상단에서 뭔가를 등록합니다.

89
00:06:23,150 --> 00:06:27,700
이 카운터에 식사 트레이를 내려 놓고 식사를 직원 같아.

90
00:06:27,700 --> 00:06:33,630
그리고 터지는은 스택의 식사 트레이를하고있다.

91
00:06:33,630 --> 00:06:36,460
자, 무슨 일이 일어날 지의 예 몇 통과

92
00:06:36,460 --> 00:06:39,720
우리는 스택에 물건을 밀어 때.

93
00:06:39,720 --> 00:06:45,110
우리는 스택 상에 문자열을 '안녕하세요'밀어한다면,

94
00:06:45,110 --> 00:06:49,760
이게 우리 다이어그램 현재 모습입니다.

95
00:06:49,760 --> 00:06:53,410
어떻게되는지 알아요?

96
00:06:53,410 --> 00:06:56,530
우리는 문자열 배열의 첫 번째 요소로 밀어

97
00:06:56,530 --> 00:07:01,420
우리는 1 일 우리의 크기 수를 늘어.

98
00:07:01,420 --> 00:07:05,340
우리가 두 슬라이드 사이의 차이를 볼한다면, 여기 10 살때, 여기에 누르기 전에 있습니다.

99
00:07:05,340 --> 00:07:08,690
여기에 푸시 한 후입니다.

100
00:07:08,690 --> 00:07:13,460
누르기 전에, 푸시 후.

101
00:07:13,460 --> 00:07:16,860
그리고 지금 우리는 스택에 한 요소가 있습니다.

102
00:07:16,860 --> 00:07:20,970
이 문자열 "안녕하세요"이고, 바로 그 거에요.

103
00:07:20,970 --> 00:07:24,440
배열의 다른 모든 우리의 문자열 배열에서 여전히 쓰레기입니다.

104
00:07:24,440 --> 00:07:27,070
우리가 초기화되지 않았습니다.

105
00:07:27,070 --> 00:07:29,410
자, 우리가 스택에 다른 문자열을 밀어 말한다.

106
00:07:29,410 --> 00:07:32,210
우리는이 시간에 "세계"를 강요하고 있습니다.

107
00:07:32,210 --> 00:07:35,160
그래서 당신은, "세계가 '여기'안녕하세요 '의 상단에갑니다 볼 수 있습니다

108
00:07:35,160 --> 00:07:40,040
와 크기 카운트 2까지갑니다.

109
00:07:40,040 --> 00:07:44,520
이제 우리는 "CS50", 그 다시 정상에 가서 밀어 수 있습니다.

110
00:07:44,520 --> 00:07:51,110
우리가 돌​​아 가면, 당신은 우리가 스택의 상단에 물건을 밀어하는 방법을 볼 수 있습니다.

111
00:07:51,110 --> 00:07:53,320
그리고 지금 우리는 튀어 야지.

112
00:07:53,320 --> 00:07:58,910
우리가 스택의 어떤 오프를 체포되었을 떼, 어떻게 된거야?

113
00:07:58,910 --> 00:08:01,540
사람의 차이를 볼 수? 그것은 아주 미묘한 힘이있는 거지.

114
00:08:01,540 --> 00:08:05,810
[학생] 크기입니다. >> 네,, 크기가 변경되었습니다.

115
00:08:05,810 --> 00:08:09,040
>> 다른이 변경 될 을까?

116
00:08:09,040 --> 00:08:14,280
너무 [학생] 문자열. >>이 맞아. 너무 문자열.

117
00:08:14,280 --> 00:08:17,110
그것은 판명 당신이 이런 식으로 일을 할 때,

118
00:08:17,110 --> 00:08:21,960
우리는 우리의 스택에 요소를 복사하지 않았기 때문에,

119
00:08:21,960 --> 00:08:24,670
우리는 실제로 아무것도 할 필요가 없습니다, 우리는 크기를 사용할 수 있습니다

120
00:08:24,670 --> 00:08:28,630
우리 배열에 일의 수를 추적 할

121
00:08:28,630 --> 00:08:33,780
수 있도록 우리가 다시 나타 때, 다시 우리가 1 우리의 크기를 감소.

122
00:08:33,780 --> 00:08:39,440
실제로에 가서 뭔가를 덮어 쓰게 할 필요가 없습니다.

123
00:08:39,440 --> 00:08:41,710
펑키의 종류.

124
00:08:41,710 --> 00:08:46,520
우리가해야 할 것이 더 작업이기 때문에 우리가 일반적으로 혼자 일을 유지하는 것이 밝혀졌다.

125
00:08:46,520 --> 00:08:50,060
우리가 돌​​아가서 뭔가를 덮어되어 있지 않은 경우, 왜 그렇게?

126
00:08:50,060 --> 00:08:54,150
그래서 우리는 스택의 두 배에서 튀어 때 않네요 모든 크기 몇 번을 감소 연산이다.

127
00:08:54,150 --> 00:08:59,120
그리고 다시, 우리가 우리 스택에 물건을 복사하지 수 있기 때문입니다.

128
00:08:59,120 --> 00:09:01,320
그래? 어서.

129
00:09:01,320 --> 00:09:04,460
[학생, 이해할 수없는] >> 그리고 다시 뭔가를 밀어 때 어떻게 되겠습니까?

130
00:09:04,460 --> 00:09:08,570
다시 뭔가를 밀어 때, 어디로 가야합니까?

131
00:09:08,570 --> 00:09:12,390
어디에서, 바질 요? 문자열 [1] 안으로 >>? >>이 맞아.

132
00:09:12,390 --> 00:09:14,530
왜 문자열 [3]로 이동되지 않는 이유는 무엇입니까?

133
00:09:14,530 --> 00:09:19,410
[바질]는 아무 문자열에서가 있다고 잊었 때문에 [1]과 [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] 그렇지. 우리 스택은, 본질적으로, 그것이 무엇이든에 쥐고 있었다고 "잊었"

135
00:09:24,040 --> 00:09:29,480
문자열에서 [1] 또는 문자열 [2], 우리는 "woot"를 밀어 있으므로 때,

136
00:09:29,480 --> 00:09:36,670
그냥 문자열 [1]에서 요소로 그를 게재 할 수 있습니다.

137
00:09:36,670 --> 00:09:41,590
기본 수준에서, 어떻게 작품을 거기에 질문 있습니까?

138
00:09:41,590 --> 00:09:45,160
[샘] 그래서이 금액의 측면에서, 어떠한 방식으로 동적이지

139
00:09:45,160 --> 00:09:47,620
또는 스택의 크기의 관점에서?

140
00:09:47,620 --> 00:09:56,750
[Hardison] 그렇지. 입니다 - 중요한 점은이 동적으로 growning 스택 아니라고했다.

141
00:09:56,750 --> 00:10:02,850
이것은 대부분의 네 가지로, 대부분의 네 번째 문자 * s의, 보유 할 수있는 스택입니다.

142
00:10:02,850 --> 00:10:07,580
우리는 다섯 번째의 것을 시도하고 밀어한다면, 당신은 무슨 일이라도 어떻게 생각하세요?

143
00:10:07,580 --> 00:10:11,870
[학생 이해할 수없는]

144
00:10:11,870 --> 00:10:14,600
[Hardison] 그렇지. 일어날 수있는 여러 가지가 있습니다.

145
00:10:14,600 --> 00:10:19,330
그것은 아마도 우리가 무엇에 따라 잘못을 감금 할 수 -

146
00:10:19,330 --> 00:10:22,530
정확히 어떻게 우리는 백 엔드를 구현했다.

147
00:10:22,530 --> 00:10:31,740
그것은 덮어 쓸 수 있습니다. 우리가 수업 시간에 말씀하신 그 버퍼 오버 플로우를 만들 수 있습니다.

148
00:10:31,740 --> 00:10:35,240
어떻게 덮어 쓰기 될 수 가장 눈에 띄는 일이 될 것입니다

149
00:10:35,240 --> 00:10:42,370
우리는 스택에 추가 일을 보내버 리려고한다면?

150
00:10:42,370 --> 00:10:44,550
그럼 당신은 버퍼 오버 플로우를 언급.

151
00:10:44,550 --> 00:10:47,870
에 이상 작성 또는 밟은받을 것이다 일이 될 수도 있습니다 무엇

152
00:10:47,870 --> 00:10:52,320
우리는 여분의 일을 밀어하려고하면 실수로 넘쳐? 경우

153
00:10:52,320 --> 00:10:54,730
[대니얼, 이해할 수없는] >> 가능.

154
00:10:54,730 --> 00:10:58,440
그러나 처음에, 어떻게됩니까? 우리가 사분의 일 일을 밀어하려고하면 어떨까요?

155
00:10:58,440 --> 00:11:06,220
그것은 적어도 우리가 가진 한이 메모리 다이어그램으로, 크기를 덮어 쓰기 할 수 있습니다.

156
00:11:06,220 --> 00:11:10,880
>> 문제 설정 사양에있는 우리가 오늘 구현 할 거냐

157
00:11:10,880 --> 00:11:16,030
우리가 원하는 것은 단지 false를 반환합니다.

158
00:11:16,030 --> 00:11:20,030
우리 푸시 방법은 부울 값을 반환 것입니다

159
00:11:20,030 --> 00:11:22,920
압박이 성공하면 그 부울 값 사실이 될 것입니다

160
00:11:22,920 --> 00:11:29,730
과 거짓 스택이 가득 차서 더 아무것도 누르지 할 수 있습니다.

161
00:11:29,730 --> 00:11:33,620
의 지금 그 코드를 약간의 통과 보자.

162
00:11:33,620 --> 00:11:36,400
다음은 푸시 기능입니다.

163
00:11:36,400 --> 00:11:40,380
스택에 대한 푸시 기능은 스택에 넣어 문자열에 데려 갈 수 있습니다.

164
00:11:40,380 --> 00:11:45,820
문자열이 성공적으로 밀려 된 경우는 TRUE를 반환 거예요

165
00:11:45,820 --> 00:11:51,820
스택과 거짓 그렇지 있습니다.

166
00:11:51,820 --> 00:11:59,740
무엇에 대한 모든 제안 여기서 할 수있는 좋은 제일 먼저 할 수 있을까요?

167
00:11:59,740 --> 00:12:20,630
크기는 용량을 동일 경우 [샘] 후 false를 반환?

168
00:12:20,630 --> 00:12:23,320
[Hardison] 찾았다. 잘 했어.

169
00:12:23,320 --> 00:12:26,310
크기가 용량 인 경우에는 FALSE를 반환거야.

170
00:12:26,310 --> 00:12:29,270
우리는 스택에 더 아무 것도 삽입 할 수 없습니다.

171
00:12:29,270 --> 00:12:36,900
그렇지 않으면, 우리는 스택의 상단에 뭔가를 넣어 싶습니다.

172
00:12:36,900 --> 00:12:41,670
처음에 "스택의 최상위 (top)는"무엇입니까?

173
00:12:41,670 --> 00:12:43,650
[다니엘] 크기 0? >> 크기 0.

174
00:12:43,650 --> 00:12:49,990
스택의 하나가 후 스택의 최상위 (top)은 무엇입니까? 아가씨, 넌 알지?

175
00:12:49,990 --> 00:12:52,720
[미시] 하나입니다. >> 크기가 정확히 한 것입니다. 당신은 크기에 추가 유지

176
00:12:52,720 --> 00:13:01,690
하고 배열의 인덱스 크기의 새로운 요소에 주력하고 때마다.

177
00:13:01,690 --> 00:13:05,470
그 말이 경우에, 한 - 라이너의 종류로 할 수 있습니다.

178
00:13:05,470 --> 00:13:11,910
우리는 문자열 배열이 있어요 그래서, 우리는 크기 지수에서 액세스 할거야

179
00:13:11,910 --> 00:13:14,780
우리는 그냥 우리의 숯불 *를 저장하는거야.

180
00:13:14,780 --> 00:13:19,340
더 문자열 복사 여기에가에 갈 수 없어 어떻게주의,

181
00:13:19,340 --> 00:13:29,680
메모리의 동적 할당?

182
00:13:29,680 --> 00:13:34,440
그리고 미시 우리가 지금 할 일을 올렸어

183
00:13:34,440 --> 00:13:40,570
우리가 배열의 해당 위치에 문자열을 저장 한 때문에,

184
00:13:40,570 --> 00:13:49,230
그녀는 우리가 다음 공격을 위해 준비하도록 하나의 크기를 증가해야한다고 말했다.

185
00:13:49,230 --> 00:13:53,950
그래서 우리는 s.size 랑 할 수 있습니다 + +.

186
00:13:53,950 --> 00:13:59,330
이 시점에서, 우리는 배열로 만든 것. 우리가해야 할 마지막은 무엇입니까?

187
00:13:59,330 --> 00:14:10,110
[학생] TRUE를 반환. >> 사실 돌아갑니다.

188
00:14:10,110 --> 00:14:14,690
그럼, 아주 간단한 코드 아주 간단합니다. 너무 많이.

189
00:14:14,690 --> 00:14:17,070
일단 당신이 스택의 작동 방식 중심으로 머리를 감싸 한

190
00:14:17,070 --> 00:14:21,910
이 구현하기 아주 간단합니다.

191
00:14:21,910 --> 00:14:26,390
>> 자,이의 다음 부분은 스택의 문자열에서 보여주고 있습니다.

192
00:14:26,390 --> 00:14:29,410
당신이 사람들에게 약간의 작업을 할 시간을 주겠어.

193
00:14:29,410 --> 00:14:34,320
거의 기본적으로 우리가 여기에 푸시에 무슨 짓을했는지의 역입니다.

194
00:14:34,320 --> 00:14:38,510
내가 한 것은 사실입니다 - 죄송합니다.

195
00:14:38,510 --> 00:14:48,160
I, 여기, 그리고 어플라이언스에 기기를 부팅 한

196
00:14:48,160 --> 00:14:53,600
나는 문제가 5 명세를 설정 찾았습니다.

197
00:14:53,600 --> 00:15:02,560
우리가 확대되면 내가 cdn.cs50.net/2012/fall/psets/pset5.pdf에있어 볼 수 있습니다.

198
00:15:02,560 --> 00:15:08,590
너희들이 여기 section6.zip에 위치하고있어이 코드를 다운로드하신 적이 있습니까?

199
00:15:08,590 --> 00:15:15,030
괜찮아요. 당신은 정말 신속하게 지금 그렇게, 그런 짓을하지 않은 경우.

200
00:15:15,030 --> 00:15:22,130
내 터미널 창에서 할 수 있습니다.

201
00:15:22,130 --> 00:15:25,090
사실 여기까지 했어요. 그래.

202
00:15:25,090 --> 00:15:34,730
네, 샘? >> 나는 왜 = str을 크기의 s.string의 괄호를하던가요에 대한 질문이 있으십니까?

203
00:15:34,730 --> 00:15:42,910
으로 str은 무엇입니까? 그 전에 어디 선가 정의되거나 - 오, 숯불 *의 str을에?

204
00:15:42,910 --> 00:15:47,160
[Hardison] 예, 맞아요. 그것은 인수했다. >> 아, 그래. 미안 해요.

205
00:15:47,160 --> 00:15:49,470
[Hardison]이 (가) 우리는 여기에 전달하는 문자열을 지정하는

206
00:15:49,470 --> 00:15:55,220
우리가 여기서 얘기하지 않았 음을 마련 할 수있는 다른 질문은

207
00:15:55,220 --> 00:15:58,810
우리가 S라는 변수가 있다는 당연한 우리는했습니다

208
00:15:58,810 --> 00:16:02,710
그 범위와 우리에게 접근으로했다.

209
00:16:02,710 --> 00:16:06,960
S이 스택 구조체이라고 당연한 우리는했다.

210
00:16:06,960 --> 00:16:08,930
그래서,이 푸쉬 코드를 다시보고

211
00:16:08,930 --> 00:16:13,450
당신은 우리가 통과 했어요이 문자열로 일을하고 것을 알 수 있습니다

212
00:16:13,450 --> 00:16:19,210
하지만 갑자기, 우리는 같은 s.size에 액세스, S 어디에서 왔는가?하는

213
00:16:19,210 --> 00:16:23,020
우리가 섹션 아카이브에 보는거야하는 코드

214
00:16:23,020 --> 00:16:27,100
다음 문제에서 뭘 할 거라고 물건, 세트

215
00:16:27,100 --> 00:16:32,440
우리는 우리의 스택이 전역 변수를 구조체했습니다

216
00:16:32,440 --> 00:16:36,380
우리는 모든 다른 기능에 대한 액세스 권한이 수 있도록

217
00:16:36,380 --> 00:16:40,630
수동으로 주변을 통과하고 참조하여 통과 할 필요없이,

218
00:16:40,630 --> 00:16:44,870
거기에 물건을 모든 종류의 해.

219
00:16:44,870 --> 00:16:52,280
우리는 친절 일을하기 위해, 당신이 경우, 조금 속이고하고 있습니다.

220
00:16:52,280 --> 00:16:57,430
그리고 그 얘기가 재미 있기 때문에 우리가하는 일이 뭔가, 그것은 쉬워졌습니다.

221
00:16:57,430 --> 00:17:02,800
사람들이 큰 데이터 구조가있는 경우 종종, 사람들은 이렇게 볼 수 있습니다

222
00:17:02,800 --> 00:17:07,750
그들은 프로그램 내에서 운영되고있어.

223
00:17:07,750 --> 00:17:09,560
>> 의가 어플라이언스에 다시 가자.

224
00:17:09,560 --> 00:17:15,240
모두가 성공적으로 section6.zip 받으셨어요?

225
00:17:15,240 --> 00:17:20,440
다들 지퍼 section6.zip를 사용하여 압축을 풉니 다?

226
00:17:20,440 --> 00:17:27,200
당신은 제 6 항 디렉토리에 가면 -

227
00:17:27,200 --> 00:17:29,220
아, 사방 -

228
00:17:29,220 --> 00:17:32,840
당신이 여기에 무슨리스트, 당신은 세 가지. C 파일이 있어요 것을 볼 수 있습니다.

229
00:17:32,840 --> 00:17:38,350
당신은 단독으로 연결된 목록입니다 큐, sll, 그리고 스택있어.

230
00:17:38,350 --> 00:17:44,600
당신은 stack.c을 열면,

231
00:17:44,600 --> 00:17:47,330
당신은 우리가 우리에 대해 정의이 구조체있어 것을 알 수 있습니다

232
00:17:47,330 --> 00:17:51,330
우리가 슬라이드에 대해 얘기하는 정확한 구조체.

233
00:17:51,330 --> 00:17:56,340
우리는 스택에 대한 우리의 전역 변수 있어요

234
00:17:56,340 --> 00:18:00,110
우리는 우리의 푸시 기능이있어

235
00:18:00,110 --> 00:18:04,230
그리고 우리는 우리의 팝업 기능을있어.

236
00:18:04,230 --> 00:18:08,320
여기에 슬라이드에 다시 밀어 줄은, 코드를 올려 놓을 게요

237
00:18:08,320 --> 00:18:10,660
하지만 너희들이 어떻게하고 싶은 것은 최선을 다해입니다

238
00:18:10,660 --> 00:18:13,790
가서 팝업 기능을 구현합니다.

239
00:18:13,790 --> 00:18:18,480
일단 당신이 그것을 구현 한, 당신은 스택을하여이를 컴파일 할 수

240
00:18:18,480 --> 00:18:22,540
그리고, 결과 스택 실행 파일을 실행

241
00:18:22,540 --> 00:18:28,390
그 아래가 메인에 해당이 테스트 코드를 모두 실행됩니다.

242
00:18:28,390 --> 00:18:31,060
그리고 메인은 실제로 푸시와 팝 호출을 담당한다

243
00:18:31,060 --> 00:18:33,220
모든 괜찮아지나 확인하고.

244
00:18:33,220 --> 00:18:36,820
또한 여기에 스택 크기를 초기화

245
00:18:36,820 --> 00:18:39,780
그럼 당신은 초기화에 대해 걱정할 필요가 없습니다.

246
00:18:39,780 --> 00:18:42,310
당신은 제대로 초기화 된 것으로 간주 할 수 있습니다

247
00:18:42,310 --> 00:18:48,000
당신이 팝업 함수에서 액세스하는 시간으로.

248
00:18:48,000 --> 00:18:53,530
그게 말이나 돼?

249
00:18:53,530 --> 00:19:00,100
그래서 여기에 우리가 이동합니다. 푸시 코드가 있습니다.

250
00:19:00,100 --> 00:19:13,210
난 자네들과 5 10 분을주지.

251
00:19:13,210 --> 00:19:15,690
그리고 당신이 코딩하는 동안 중간에 질문이 있으면,

252
00:19:15,690 --> 00:19:17,710
을 크게 문의 해 주시기 바랍니다.

253
00:19:17,710 --> 00:19:23,080
당신이 그걸 고정 지점에 도착하면, 그냥 물어보십시오.

254
00:19:23,080 --> 00:19:26,030
다른 사람들에게 알려, 내가 알려 주시기 바랍니다.

255
00:19:26,030 --> 00:19:28,160
도 이웃과 협력합니다.

256
00:19:28,160 --> 00:19:30,360
[다니엘] 우리는 단지 지금 팝업 구현거야? >> 그냥 팝업.

257
00:19:30,360 --> 00:19:34,200
원하는 경우이 압력의 구현을 복사 할 수 있지만

258
00:19:34,200 --> 00:19:37,780
테스트가 작동 할 수 있도록.

259
00:19:37,780 --> 00:19:41,940
그것은에 점점 물건을 테스트하는 하드 으니까 -

260
00:19:41,940 --> 00:19:49,030
아니면, 처음부터 스택에 뭔가가없는 경우 스택의 터지는 것을 테스트 어렵습니다.

261
00:19:49,030 --> 00:19:55,250
>> 반환 될 예정 팝업은 무엇입니까? 스택의 최상위 (top)에서 요소입니다.

262
00:19:55,250 --> 00:20:01,260
그것은 스택의 최상위 (top)의 요소를 하차해야하는

263
00:20:01,260 --> 00:20:05,780
그리고 스택의 크기를 감소

264
00:20:05,780 --> 00:20:07,810
그리고 지금 당신은 상단에있는 요소를 잃었습니다.

265
00:20:07,810 --> 00:20:11,420
그리고 당신은 상단에있는 요소를 반환합니다.

266
00:20:11,420 --> 00:20:20,080
[학생, 이해할 수없는]

267
00:20:20,080 --> 00:20:28,810
[Hardison] 당신이 그렇게하면 어떻게 되겠습니까? [학생, 이해할 수없는]

268
00:20:28,810 --> 00:20:34,000
어떤 일이 끝나는 것을 당신은 아마 중 하나를 액세스

269
00:20:34,000 --> 00:20:37,350
그 요소가 아직 초기화되지 않은하므로 계산

270
00:20:37,350 --> 00:20:39,990
이 마지막 요소가 꺼져 어디.

271
00:20:39,990 --> 00:20:46,260
잘 보면 그래서 여기, 푸쉬에, 우리는 s.size 요소에서 문자열에 액세스하는

272
00:20:46,260 --> 00:20:48,560
이 새 색인 때문입니다.

273
00:20:48,560 --> 00:20:51,460
그것은 스택의 새로운 최상위입니다.

274
00:20:51,460 --> 00:21:01,100
팝업에 반해, s.size는 다음 공간이 될 것입니다

275
00:21:01,100 --> 00:21:05,210
당신의 스택에있는 모든 요소 위에 공간.

276
00:21:05,210 --> 00:21:10,050
따라서 최상위 요소는 s.size에 없다

277
00:21:10,050 --> 00:21:14,930
오히려, 그것은 아래입니다.

278
00:21:14,930 --> 00:21:19,640
>> 당신이해야 할 또 다른 문제 - 팝업에서

279
00:21:19,640 --> 00:21:22,030
당신은 크기를 감소해야하나요합니다.

280
00:21:22,030 --> 00:21:28,750
당신은 여기에 우리의 작은 그림으로 기억한다면,

281
00:21:28,750 --> 00:21:30,980
정말 우리가 무슨 일이 본 유일한 우리가 팝업 호출 할 때

282
00:21:30,980 --> 00:21:36,150
이 정도 크기 후 1 먼저 2, 떨어 것이 었습니다.

283
00:21:36,150 --> 00:21:42,620
그럼 우리가에 새로운 요소를 밀 때, 그것은 적절한 자리에 계속합니다.

284
00:21:42,620 --> 00:21:49,610
[바질] s.size은 2 인 경우는 엘리먼트 (2)에 갈거야,

285
00:21:49,610 --> 00:21:54,400
그리고 그 요소를 나타 싶어 하죠?

286
00:21:54,400 --> 00:21:59,510
우리가 졌으면 - >> 그럼 다시 살펴 보자.

287
00:21:59,510 --> 00:22:07,730
이이 시점에서 우리 스택 인 경우

288
00:22:07,730 --> 00:22:12,130
우리는, 팝업 전화

289
00:22:12,130 --> 00:22:16,150
되는 인덱스는 맨 위 요소입니다?

290
00:22:16,150 --> 00:22:19,300
[바질]는 2에서는 만 3 열어거야. >>이 맞아.

291
00:22:19,300 --> 00:22:24,220
따라서 우리의 크기는 3 곳이지만, 우리는 색인을 2 요소를 나타 싶습니다.

292
00:22:24,220 --> 00:22:29,900
당신이 배열의 제로 색인을 가지고 하나에서의 전형적인 이죠.

293
00:22:29,900 --> 00:22:36,430
그래서 세 번째 요소를 나타하려는 않지만, 세 번째 요소는 인덱스 3에 없습니다.

294
00:22:36,430 --> 00:22:39,430
그리고 우리가 밀어 때 그 마이너스 1 할 필요가 없습니다 이유

295
00:22:39,430 --> 00:22:44,120
지금 있기 때문에, 당신은 발견되는 최상위 요소,

296
00:22:44,120 --> 00:22:47,600
우리가이 시점에서 스택 위에 뭔가를 강요한다면,

297
00:22:47,600 --> 00:22:50,360
우리는 인덱스 3에서 밀어 붙일 것입니다.

298
00:22:50,360 --> 00:23:03,550
그리고 그냥 당신이 추진하고 때의 크기와 인덱스가 줄 것으로 발생합니다.

299
00:23:03,550 --> 00:23:06,960
>> 누가 작동 스택 구현있어?

300
00:23:06,960 --> 00:23:09,690
당신은 작업 스택 하나가있어. 팝 아직 작업이 있습니까?

301
00:23:09,690 --> 00:23:11,890
[다니엘] 예. 그런 것 같아요.

302
00:23:11,890 --> 00:23:14,610
>> 프로그램 실행 오류있는을 감금가 아니야, 이건 출력 거죠?

303
00:23:14,610 --> 00:23:17,520
당신이 그것을 실행할 때 "성공"을 인쇄합니까?

304
00:23:17,520 --> 00:23:22,630
그래. 가 "성공"을 출력하고 붐을 이동하지 않는 경우, 스택 확인을 실행

305
00:23:22,630 --> 00:23:26,000
다음 모든 좋네요.

306
00:23:26,000 --> 00:23:34,070
괜찮아요. 진짜로 빠르게 어플라이언스의로 가자,

307
00:23:34,070 --> 00:23:46,100
우리는이를 통해 안내합니다.

308
00:23:46,100 --> 00:23:51,110
우리는 아빠 랑 여기서 뭐하는거야 만난다면

309
00:23:51,110 --> 00:23:55,220
다니엘, 당신이 한 짓 처음하는 일이 무엇 이었습니까?

310
00:23:55,220 --> 00:23:58,850
[다니엘] s.size이 0보다 큰 경우.

311
00:23:58,850 --> 00:24:03,120
[Hardison] 좋아. 그리고 왜 그런 짓을 했지?

312
00:24:03,120 --> 00:24:05,610
[다니엘] 스택 내부의 뭔가가 있는지 확인합니다.

313
00:24:05,610 --> 00:24:10,950
[Hardison] 맞아. 당신은 s.size가 0보다 큰 있는지 확인하기 위해 테스트 할;

314
00:24:10,950 --> 00:24:13,280
그렇지 않으면, 당신은 일어날 것 무엇을 원하는 겁니까?

315
00:24:13,280 --> 00:24:16,630
[다니엘] 반환 null이? >> 반환 null이, 맞아요.

316
00:24:16,630 --> 00:24:20,740
그래서, 만약 s.size은 0보다 커야합니다. 우리는 무슨 일을하는거야?

317
00:24:20,740 --> 00:24:25,890
스택이 비어 있지 않으면 우리는 어떻게해야합니까?

318
00:24:25,890 --> 00:24:31,210
[스텔라] 당신은 크기를 감소? 괜찮아, 크기를 감소 >>.

319
00:24:31,210 --> 00:24:34,440
그래서 당신은 어떻게하는거야? >> s.size ... -.

320
00:24:34,440 --> 00:24:37,030
[Hardison] 좋아요. 그리고 당신이 무슨 짓을 한거야?

321
00:24:37,030 --> 00:24:44,140
[스텔라] 그리고는 반환 s.string 말 [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] 좋아요.

323
00:24:48,560 --> 00:24:51,940
그렇지 않으면 null을 반환합니다. 네, 샘?

324
00:24:51,940 --> 00:24:55,510
[샘] 왜이 + 1 s.size 할 필요가되지 않는 이유는 무엇입니까?

325
00:24:55,510 --> 00:24:58,430
[Hardison] 플러스 1? >> 그래. >>은 알았어.

326
00:24:58,430 --> 00:25:00,980
당신이 하나를 꺼내겠다 있기 때문에 [샘] 내 생각 엔,

327
00:25:00,980 --> 00:25:04,290
그러면 안에게 그들이 요구하는 하나를 반환 할거야.

328
00:25:04,290 --> 00:25:09,400
[Hardison] 그리고 우리는 0 인덱스의이 모든 문제를 얘기를 했어요 그냥 뭐이었다.

329
00:25:09,400 --> 00:25:11,380
그래서 우리가 여기에 다시 확대합니다.

330
00:25:11,380 --> 00:25:15,650
우리가 여기에서이 남자를 보면, 당신은 우리가 나타 때 것을 알 수 있습니다

331
00:25:15,650 --> 00:25:19,340
우리는 색인을 2 요소를 보여주고하고 있습니다.

332
00:25:19,340 --> 00:25:25,200
>> 그래서 우리는 우리의 크기는 색인과 일치, 먼저 크기를 줄이십시오.

333
00:25:25,200 --> 00:25:39,650
먼저 크기를 감소하지 않는 경우, 우리는 -1 후 감소 크기를해야 해.

334
00:25:39,650 --> 00:25:45,270
좋아요. 괜찮아?

335
00:25:45,270 --> 00:25:47,530
여기에 대한 질문?

336
00:25:47,530 --> 00:25:54,050
이뿐만 아니라를 작성하는 다른 방법에는 여러가지가 있습니다.

337
00:25:54,050 --> 00:26:03,290
사실, 우리는 뭔가를 할 수 - 우리는 하나 라이너를 할 수 있습니다.

338
00:26:03,290 --> 00:26:05,770
우리는 한 줄 수익을 수행 할 수 있습니다.

339
00:26:05,770 --> 00:26:12,980
우리가 그렇게함으로써 반환하기 전에 그래서 우리가 실제로 감소 할 수 있습니다.

340
00:26:12,980 --> 00:26:18,320
그래서를 넣어 - s.size 전에.

341
00:26:18,320 --> 00:26:22,060
그 거랑은 정말 조밀합니다.

342
00:26:22,060 --> 00:26:30,940
어디의 차이 -.의 크기와 s.size .. -

343
00:26:30,940 --> 00:26:40,130
즉이 접미사 - 때문에 그들이 접미사 전화 - 제공 후 s.size .. -

344
00:26:40,130 --> 00:26:47,430
s.size은 색인을 찾는 목적으로 평가된다는 것을 의미합니다

345
00:26:47,430 --> 00:26:50,410
만약이 줄이 실행될 때 현재와 같이

346
00:26:50,410 --> 00:26:54,290
그리고이 - 줄이 실행되고 나면 발생합니다.

347
00:26:54,290 --> 00:27:00,340
인덱스 s.size의 요소에 액세스 한 후.

348
00:27:00,340 --> 00:27:07,260
우리가 감소 먼저 일이 원하기 때문에 그것은, 우리가 원하는 게 아니에요.

349
00:27:07,260 --> 00:27:10,990
Othewise, 우리는 배열을 액세스 할 수있어, 효과적으로 범위를 벗어.

350
00:27:10,990 --> 00:27:16,850
우리는 실제로 액세스 할 수있는 유일한 위의 요소에 액세스 할거야.

351
00:27:16,850 --> 00:27:23,840
그래, 샘? >> 더 빨리 또는 한 줄 여부에 있도록 적은 RAM을 사용하여입니까?

352
00:27:23,840 --> 00:27:29,620
[Hardison]는 솔직히, 정말 따라 달라집니다.

353
00:27:29,620 --> 00:27:34,220
[샘, 이해할 수없는] >> 네, 따라 달라집니다. 당신은 컴파일러 트릭을 수행 할 수

354
00:27:34,220 --> 00:27:41,580
그를 인식하도록 컴파일러를 얻을, 보통, 내가 상상.

355
00:27:41,580 --> 00:27:44,840
>> 그래서 우리는이 컴파일러 최적화 물건에 대해 조금 언급 한

356
00:27:44,840 --> 00:27:47,400
당신은 컴파일에 할 수있는

357
00:27:47,400 --> 00:27:50,580
그는 컴파일러가 알 수있을 수 있다는 것은의 종류입니다

358
00:27:50,580 --> 00:27:54,710
오처럼, 이봐, 어쩌면 내가, 하나의 작업이 모두 수행 할 수

359
00:27:54,710 --> 00:27:59,420
로 RAM에서 크기 변수를로드에 반대하는 것은

360
00:27:59,420 --> 00:28:03,770
그걸 decrementing 다시를 저장 한 다음 다시 다시로드

361
00:28:03,770 --> 00:28:08,000
이 작업의 나머지 부분을 처리 할 수​​ 있습니다.

362
00:28:08,000 --> 00:28:10,710
그러나 일반적으로, 아냐,이 것들 아냐

363
00:28:10,710 --> 00:28:20,770
그 속도가 매우 빠르고 프로그램을 만들거야.

364
00:28:20,770 --> 00:28:26,000
스택에 대한 질문 더 있습니까?

365
00:28:26,000 --> 00:28:31,360
>> 따라서 밀 들락 거리지. 당신들은 해커 버전을 시도 할 경우

366
00:28:31,360 --> 00:28:33,660
우리가 해커 판에 한 건 정말 사라 졌어요

367
00:28:33,660 --> 00:28:37,670
이 스택은 동적으로 성장했다.

368
00:28:37,670 --> 00:28:43,190
여기까지 푸시 함수에서 기본적으로이 도전,

369
00:28:43,190 --> 00:28:48,820
그 배열이 성장하는 방법을 찾아 야지

370
00:28:48,820 --> 00:28:52,450
당신은 스택에 더 많은 요소를 계속 밀고 있습니다.

371
00:28:52,450 --> 00:28:56,000
사실은 너무 많은 추가 코드 없습니다.

372
00:28:56,000 --> 00:29:00,080
제대로 거기에 malloc에​​ 전화를한다는 점을 기억해야합니다 - 도보로 전화

373
00:29:00,080 --> 00:29:03,310
당신은 realloc를 호출 할 때 다음 해결.

374
00:29:03,310 --> 00:29:06,090
당신이 관심이 있다면 그건 재미 도전입니다.

375
00:29:06,090 --> 00:29:11,550
>> 그러나 당분간, 그럼 이동하게하고, 큐에 대해 이야기합시다.

376
00:29:11,550 --> 00:29:15,680
여기까지 스크롤합니다.

377
00:29:15,680 --> 00:29:19,340
대기열이 스택의 가까운 형제입니다.

378
00:29:19,340 --> 00:29:25,380
그래서 스택에 그 일이 마지막에 넣어되었습니다

379
00:29:25,380 --> 00:29:28,810
그런 다음 검색 할 첫 번째 일이 있었다.

380
00:29:28,810 --> 00:29:33,600
우리는 주문이에서 마지막을 먼저, 또는 LIFO있어.

381
00:29:33,600 --> 00:29:38,390
대기열에 반면에, 당신이 줄에 서 때의 기대로,

382
00:29:38,390 --> 00:29:41,980
일렬로 한 최초의 사람 대기열에 갈 수있는 먼저,

383
00:29:41,980 --> 00:29:47,630
대기열에서 검색됩니다 먼저입니다.

384
00:29:47,630 --> 00:29:51,490
우리가 그래프를 처리 할 때 큐도 종종 사용됩니다

385
00:29:51,490 --> 00:29:55,560
우리는 스택을 짧게 이야기처럼

386
00:29:55,560 --> 00:30:00,260
그리고 큐는 다른 것들의 무리에도 편리합니다.

387
00:30:00,260 --> 00:30:06,180
자주 올라 오는 한 가지 예를 들어, 유지하기 위해 노력하고 있습니다

388
00:30:06,180 --> 00:30:12,310
요소의 정렬 목록입니다.

389
00:30:12,310 --> 00:30:17,650
그리고 당신은 배열이 작업을 수행 할 수 있습니다. 당신은 배열의 가지 정렬 목록을 유지 관리 할 수​​ 있습니다

390
00:30:17,650 --> 00:30:20,650
하지만 까다로운 도착 그때 어디 있는지 항상 찾아 내야

391
00:30:20,650 --> 00:30:26,160
다음 일을 삽입 할 수있는 적절한 장소.

392
00:30:26,160 --> 00:30:28,250
가 10을 통해 숫자의 배열, 1을면하는 것은,

393
00:30:28,250 --> 00:30:31,630
그리고 당신은 100를 통해 모든 숫자 1에 해당을 확장하려면

394
00:30:31,630 --> 00:30:33,670
그리고 당신은 무작위 순서로 숫자를 받고 모든 것을 유지하려는

395
00:30:33,670 --> 00:30:40,650
당신은 통과로 정렬, 당신은 변화를 많이 할 필요가 결국.

396
00:30:40,650 --> 00:30:43,910
대기열 및 기본 데이터 구조의 특정 유형의 특정 형식에,

397
00:30:43,910 --> 00:30:46,670
당신은 실제로 매우 간단하게 할 수 있습니다.

398
00:30:46,670 --> 00:30:50,640
뭔가를 추가 한 다음 모든 것을 할 때마다 개편 할 필요가 없습니다.

399
00:30:50,640 --> 00:30:56,770
또한 당신은 주변의 내부 요소의 이동을 많이해야 돼.

400
00:30:56,770 --> 00:31:02,990
우리가 큐를 볼 때, 당신은 그것을 볼 수 -도 queue.c의 섹션 코드에서 -

401
00:31:02,990 --> 00:31:10,950
우리가 제공 한 구조체는 우리가 스택에 준 구조체에 아주 비슷합니다.

402
00:31:10,950 --> 00:31:13,770
>> 이 한 예외가있어, 그 한 가지 예외

403
00:31:13,770 --> 00:31:21,700
우리가 머리라고이 추가 정수를 가지고 것은,

404
00:31:21,700 --> 00:31:28,120
여기 머리가 대기열의 머리의 트랙을 유지입니다

405
00:31:28,120 --> 00:31:32,160
대기열 또는 첫 번째 요소입니다.

406
00:31:32,160 --> 00:31:37,470
스택으로, 우리는, 우리는 검색하려고 줄 수있는 요소를 추적 할 수 있었다

407
00:31:37,470 --> 00:31:40,800
단지 크기를 사용하여 스택 또는 상단,

408
00:31:40,800 --> 00:31:44,220
대기열이있는 반면, 우리는 반대 끝을 처리 할 필요하고 있습니다.

409
00:31:44,220 --> 00:31:49,000
우리는 압정으로 고정 말에 일을하려고 노력하지만 전면에서 물건을 반환하고 있습니다.

410
00:31:49,000 --> 00:31:54,640
따라서 효과적으로 머리, 우리는 대기열의 시작의 색인을 가지고

411
00:31:54,640 --> 00:31:58,920
그리고 크기는 우리에게 큐의 끝의 색인을 제공합니다

412
00:31:58,920 --> 00:32:03,730
우리는 머리에서 물건을 검색하고 꼬리에 물건을 추가 할 수 있도록.

413
00:32:03,730 --> 00:32:06,890
스택 반면, 우리는 어느 스택의 최상위 (top) 처리했다.

414
00:32:06,890 --> 00:32:08,900
우리는 스택의 하단에 액세스 할 수 없었어요.

415
00:32:08,900 --> 00:32:12,220
우리는 상단에 물건을 추가하고 상단의 일을 벗고

416
00:32:12,220 --> 00:32:17,470
그래서 우리는 우리의 구조체 안에 여분의 필드를 필요하지 않았다.

417
00:32:17,470 --> 00:32:20,590
그는 일반적으로 이해합니까?

418
00:32:20,590 --> 00:32:27,670
괜찮아요. 네, 샬롯? [샬롯, 이해할 수없는]

419
00:32:27,670 --> 00:32:32,660
[Hardison] 그건 좋은 질문이고, 그 강의에 와서 하나였습니다.

420
00:32:32,660 --> 00:32:36,290
아마 몇 가지 예를 통해 들어가는 것은 설명 할 이유

421
00:32:36,290 --> 00:32:41,400
우리는 문자열에게 큐의 머리로 [0]를 사용하지 않습니다.

422
00:32:41,400 --> 00:32:46,770
>> 그래서 우리는 우리의 큐를 가지고 상상, 우리는 대기열에 전화거야.

423
00:32:46,770 --> 00:32:49,210
처음에, 우리는 그것을 인스턴스화되면,

424
00:32:49,210 --> 00:32:53,330
우리가 그것을 선언했을 때, 우리는 아무 것도 초기화되지 않았습니다.

425
00:32:53,330 --> 00:32:56,790
다 쓰레기입니다. 그럼 당연히 우리는 우리가 초기화되었는지 확인하려면

426
00:32:56,790 --> 00:33:00,950
크기와 머리 입력란 모두 합리적인 0, 무언가 있어야합니다.

427
00:33:00,950 --> 00:33:05,770
우리는 또한 우리를 계속 큐에 요소를 null로 수 있습니다.

428
00:33:05,770 --> 00:33:09,930
그리고이 다이어그램 적합한를 만들기 위해, 이제 큐는 세 가지 요소를 개최 할 수있는 것을,

429
00:33:09,930 --> 00:33:13,150
우리 스택 네를 개최 할 수 반면, 우리의 큐는 세 수용 할 수 있습니다.

430
00:33:13,150 --> 00:33:18,680
그리고 그 다이어그램 적합한를 만들기 위해 단지입니다.

431
00:33:18,680 --> 00:33:26,150
여기서 무슨 일이 일어날 먼저 우리는 "안녕하세요"문자열을 인큐입니다.

432
00:33:26,150 --> 00:33:30,380
그리고 마찬가지로 우리가 스택과 함께 한, 여기 정말 다른 아무것도,

433
00:33:30,380 --> 00:33:39,230
우리는 문자열에 [0] 1하여 크기를 증가에 문자열을 던져.

434
00:33:39,230 --> 00:33:42,720
우리는 "안녕"을 인큐, 그것은 입고됩니다.

435
00:33:42,720 --> 00:33:45,870
그래서이 대부분 스택 것 같습니다.

436
00:33:45,870 --> 00:33:53,230
우리는 여기에 새로운 요소, 새로운 요소를 시작 크기는 올라가고 유지합니다.

437
00:33:53,230 --> 00:33:56,330
우리가 뭔가를 dequeue 할 때 어떻게이 시점에서 어떻게됩니까?

438
00:33:56,330 --> 00:34:01,280
우리가 dequeue 할 때, 그건 우리가 dequeue 할 요소입니까?

439
00:34:01,280 --> 00:34:04,110
[바질] 문자열 [0]. >> 제로. 정확히 맞아, 바질.

440
00:34:04,110 --> 00:34:10,960
우리는 첫 번째 문자열이 한 "안녕하세요"를 제거하고 싶습니다.

441
00:34:10,960 --> 00:34:13,170
따라서 변경 다른 점은 무엇 이었습니까?

442
00:34:13,170 --> 00:34:17,010
우리가 스택의 어떤 오프를 때린 공지, 우리는 방금 크기를 변경

443
00:34:17,010 --> 00:34:22,080
하지만 여기, 우리는 변화 그 몇 가지있어.

444
00:34:22,080 --> 00:34:27,440
크기 변경하지만, 머리를 변경 않습니다 만.

445
00:34:27,440 --> 00:34:31,020
이 이전 샬롯의 지점으로 돌아 간다됩니다

446
00:34:31,020 --> 00:34:38,699
왜 우리는뿐만 아니라이 머리를해야합니까?

447
00:34:38,699 --> 00:34:42,110
그것은, 지금 샬롯을 이해합니까? 의 >> 종류.

448
00:34:42,110 --> 00:34:47,500
의 [Hardison]인가? 우리가 dequeued했을 때 무슨 일 있었나요?

449
00:34:47,500 --> 00:34:54,340
머리는 이제 재미입니다 무슨 짓을 한거야?

450
00:34:54,340 --> 00:34:56,449
그 변경 [샬롯] 오, 까 - 알았어. 알 겠어요.

451
00:34:56,449 --> 00:35:02,090
때문에 머리 - 머리는 위치의 측면에서의 변화를 가리키고있다.

452
00:35:02,090 --> 00:35:07,200
더 이상 항상 제로 인덱스의 하나. >> 네, 맞아요.

453
00:35:07,200 --> 00:35:17,660
높은 요소를 dequeueing 경우 무슨 일이 있었 냐면했습니다

454
00:35:17,660 --> 00:35:20,590
완료되었으며, 우리는이 머리 필드가 없었

455
00:35:20,590 --> 00:35:26,880
우리가 항상 0 색인에 큐의 머리에이 문자열을 호출했기 때문에,

456
00:35:26,880 --> 00:35:30,170
그러면 우리는 대기열의 나머지 부분을 아래로 이동 할 것입니다.

457
00:35:30,170 --> 00:35:36,010
우리는 문자열에서에서 "안녕"[1] 이동하기 위해 [0] 문자열이있을 것이다.

458
00:35:36,010 --> 00:35:38,760
그리고 문자열 [2] 다운 문자열 [1].

459
00:35:38,760 --> 00:35:43,050
그리고 우리는, 요소의 전체 목록을 보려면이 작업을 수행해야 할

460
00:35:43,050 --> 00:35:45,110
요소의 전체 배열입니다.

461
00:35:45,110 --> 00:35:50,490
그리고 우리가 배열이 일을 할 때, 정말 비싼옵니다.

462
00:35:50,490 --> 00:35:53,340
그래서 여기, 그것은 큰 문제가 아니에요. 우리는 우리의 배열의 세 가지 요소가 있습니다.

463
00:35:53,340 --> 00:35:57,230
하지만 우리는 천 요소의 대기열 또는 만 요소가 있다면,

464
00:35:57,230 --> 00:36:00,060
그리고 갑자기, 우리는 dequeue의 무리를 만들기 시작하면 루프의 모든 호출

465
00:36:00,060 --> 00:36:03,930
일이 진짜가 지속적으로 모든 것을 내려 주던로 천천히 것입니다.

466
00:36:03,930 --> 00:36:07,320
알다시피, 1 명 근무 시간, 1 1, 변화에 의해, 1 교대를 바꿔 주죠.

467
00:36:07,320 --> 00:36:13,650
정말 포인터 있진 않지만 대신이 머리를 사용, 우리는 "포인터"라고

468
00:36:13,650 --> 00:36:16,430
엄격한 의미에서, 그것은 포인터 취향이 아니야.

469
00:36:16,430 --> 00:36:19,410
이 정수 * 또는 문자 * 또는 그런 건 아닙니다.

470
00:36:19,410 --> 00:36:28,930
그러나 포인팅 또는 대기열의 머리를 보이고 있어요. 응?

471
00:36:28,930 --> 00:36:38,800
>> [학생]는 머리에 무엇이든 오프 팝업하는 방법 dequeue는 알 수 있습니까?

472
00:36:38,800 --> 00:36:43,620
[Hardison] 어떻게 dequeue이 머리에 있다고든지 튀어하는 방법을 알고 있습니까? >> 오른쪽, 그래.

473
00:36:43,620 --> 00:36:49,050
>> 모습이보고있어는로 설정되어있는 단지 어떤 머리 영역입니다.

474
00:36:49,050 --> 00:36:52,710
우리는 바로 여기 봐봐 첫 번째 경우에, 경우,

475
00:36:52,710 --> 00:36:55,690
우리의 머리는 0, 인덱스 0입니다. >>이 맞아.

476
00:36:55,690 --> 00:37:00,500
[Hardison]는 그냥 그래, 인덱스 0의 요소 문자열 "안녕하세요"이라고 말했다 그래서

477
00:37:00,500 --> 00:37:03,050
우리 대기열의 머리에있는 요소입니다.

478
00:37:03,050 --> 00:37:05,570
그래서 우리는 그 사람을 dequeue거야.

479
00:37:05,570 --> 00:37:09,800
그래서 호출자에게 반환됩니다 요소 될 것입니다.

480
00:37:09,800 --> 00:37:14,540
예, 사드? >> 그래서 머리는 기본적를 설정 - 당신이 색인을 생성 할 걸세 어디?

481
00:37:14,540 --> 00:37:17,750
그거의 시작이야? >> 그래. 좋아요 >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] 우리 배열의 새로운 시작되고 야.

483
00:37:22,900 --> 00:37:28,930
당신이 뭔가를 dequeue 때 당신이해야 할 모든, 색인 q.head에서 요소를 액세스가

484
00:37:28,930 --> 00:37:32,240
그리고 그 말은 당신이 dequeue 할 요소입니다.

485
00:37:32,240 --> 00:37:34,930
당신은 또한 크기를 감소해야합니다.

486
00:37:34,930 --> 00:37:39,430
일이있는 약간 까다로운 잡는 곳이 어디 우리 잠시 표시됩니다.

487
00:37:39,430 --> 00:37:46,520
우리가 다시 인큐 경우 우리는 지금 dequeue하고,

488
00:37:46,520 --> 00:37:51,300
우리가 어디를 인큐합니까?

489
00:37:51,300 --> 00:37:55,000
어디 다음 요소는 우리 대기열에 가서는 무엇입니까?

490
00:37:55,000 --> 00:37:57,980
우리는 문자열 "CS"를 인큐 싶은 말.

491
00:37:57,980 --> 00:38:02,240
그 어떤 색인에가는거야? [학생] 문자열 [2]. >> 둘.

492
00:38:02,240 --> 00:38:04,980
왜이 아니라 0?

493
00:38:04,980 --> 00:38:13,570
[바질] 이제 머리는 1이기 때문에, 목록의 시작처럼 그래?

494
00:38:13,570 --> 00:38:21,220
[Hardison] 맞아. 그리고이 목록의 끝을 나타냅니다?

495
00:38:21,220 --> 00:38:23,290
우리는 우리의 큐의 끝을 나타 내기 위해 무엇을 사용하는거야?

496
00:38:23,290 --> 00:38:25,970
머리는 우리 대기열의 머리, 우리의 큐의 시작입니다.

497
00:38:25,970 --> 00:38:29,530
우리 큐의 끝은 무엇입니까? [학생] 크기입니다. >> 크기, 맞아요.

498
00:38:29,530 --> 00:38:36,360
그래서 우리의 새로운 요소는 크기로 들어가서, 우리가 수행하는 요소는 오프 머리에서 하차 있습니다.

499
00:38:36,360 --> 00:38:45,390
우리는 다음 요소를 인큐 때, 우리는 크기에에에 무리가 올 수 있습니다.

500
00:38:45,390 --> 00:38:48,530
[학생]하기 전에 알고있는, 크기는 오른쪽, 1이라고 넣어?

501
00:38:48,530 --> 00:38:55,690
[Hardison] 맞아. 그래서별로 크기에. 크기 +,하지 +1,하지만 + 헤드.

502
00:38:55,690 --> 00:38:59,990
우리는 머리를 한 금액을 기준으로 모든 이동 때문입니다.

503
00:38:59,990 --> 00:39:14,270
그래서 여기, 이제 우리는 인덱스 1에서 시작 크기 (1)의 대기열에있어.

504
00:39:14,270 --> 00:39:20,730
꼬리 부분은 인덱스 2입니다. 그래?

505
00:39:20,730 --> 00:39:25,780
>> [학생] 어떻게됩니까 때 메모리에 당신이 dequeue 문자열 [0], 그리고 문자열 '슬롯

506
00:39:25,780 --> 00:39:29,420
단지 기본적으로 비우지하게하거나 잊어?

507
00:39:29,420 --> 00:39:34,700
[Hardison] 그래. 이런 점에서 우리가 그들을 잊고하고 있습니다.

508
00:39:34,700 --> 00:39:42,640
우리는 그들의 사본을 저장 한 경우 -

509
00:39:42,640 --> 00:39:46,310
많은 데이터 구조는 종종 요소의 자신의 사본을 저장합니다

510
00:39:46,310 --> 00:39:51,760
데이터 구조를 관리하는 사람은 걱정할 필요하지 않도록

511
00:39:51,760 --> 00:39:53,650
모든 포인터 가는지에 대해.

512
00:39:53,650 --> 00:39:56,000
데이터 구조 다에 보유, 모든 사본에 개최

513
00:39:56,000 --> 00:39:59,580
모든 적절하게 지속 있는지 확인합니다.

514
00:39:59,580 --> 00:40:03,140
그러나,이 경우, 이러한 데이터 구조, 그냥 단순 들어,

515
00:40:03,140 --> 00:40:05,580
우리가 그들에 저장 있다는 것도 사본을하지 않습니다.

516
00:40:05,580 --> 00:40:08,630
[학생] 그래서이 연속 배열 - >> 예.

517
00:40:08,630 --> 00:40:14,350
우리가 정의가이 구조 뭔지를 다시 확인하면됩니다.

518
00:40:14,350 --> 00:40:19,110
그것은 당신이 본 것 같은 단지 표준 배열

519
00:40:19,110 --> 00:40:24,280
숯불 * s의 배열입니다.

520
00:40:24,280 --> 00:40:26,340
그 있습니까 -? >> 그래, 난 그냥 궁금 해서요

521
00:40:26,340 --> 00:40:29,130
당신은 결국 어느 정도까지 메모리가 실행됩니다 경우

522
00:40:29,130 --> 00:40:32,330
귀하의 배열에 모든 빈 곳이 있다면?

523
00:40:32,330 --> 00:40:36,390
[Hardison] 그래, 그게 좋은 점입니다.

524
00:40:36,390 --> 00:40:41,530
>> 우리는이 시점에서 지금 무슨 일이 일어 났는지를 보면

525
00:40:41,530 --> 00:40:46,350
우리 대기열을 채워 한, 그것은 것 같습니다.

526
00:40:46,350 --> 00:40:50,390
그러나 우리는 정말 우리의 대기열을 작성하지 않았습니다

527
00:40:50,390 --> 00:40:57,710
우리가 사이즈 2입니다 대기열을 가지고 있지만, 인덱스 1에서 시작하기 때문에하면,

528
00:40:57,710 --> 00:41:02,160
우리 헤드 포인터가있는 곳 이니까.

529
00:41:02,160 --> 00:41:08,400
당신이 말한 것 같은, 그 문자열의 요소 [0] 인덱스 0에서 정말 없다.

530
00:41:08,400 --> 00:41:10,450
그것은 더 이상 우리 대기열에 없습니다.

531
00:41:10,450 --> 00:41:16,460
우린 그냥 가서 우리가이 일을 dequeued 때를 덮어 할 생각은하지 않았다.

532
00:41:16,460 --> 00:41:18,700
그래서 우리가 메모리가 부족 한 것 같아하더라도, 우리는 정말 없어요.

533
00:41:18,700 --> 00:41:23,270
우리가 사용하기에 그 자리를 이용하실 수 있습니다.

534
00:41:23,270 --> 00:41:29,310
적절한 행동, 우리는 dequeue 뭔가를 처음으로 할 경우

535
00:41:29,310 --> 00:41:34,420
바이 오프 나타 거라고, "안녕"좋아.

536
00:41:34,420 --> 00:41:38,460
우리의 대기열이 지수 2 시작 및 크기 일입니다.

537
00:41:38,460 --> 00:41:42,240
우리가 다시 무언가를 시도하고 인큐 경우 그리고 지금, 50 말

538
00:41:42,240 --> 00:41:47,880
50 인덱스 0에이 장소에 가야

539
00:41:47,880 --> 00:41:51,270
그것은 여전히​​ 우리 사용할 때문입니다. 예, 사드?

540
00:41:51,270 --> 00:41:53,630
[사드]는 그이 자동으로 발생합니까?

541
00:41:53,630 --> 00:41:56,150
[Hardison] 그것은 아주 자동으로되지 않습니다. 당신은 수학을해야

542
00:41:56,150 --> 00:42:00,380
작동하게하지만, 기본적으로 우리가 한 것은 우리가 감싸 한 것입니다 수 있습니다.

543
00:42:00,380 --> 00:42:04,070
이 사건의 한가운데에 구멍이있는 경우 [사드] 그리고는 괜찮아?

544
00:42:04,070 --> 00:42:08,720
[Hardison] 우리는 계산이 제대로 작동 할 수 있다면입니다.

545
00:42:08,720 --> 00:42:15,470
>> 그리고 그런 일이 실제로 모드 연산자와도 복잡하지 않아서 것을 밝혀졌다.

546
00:42:15,470 --> 00:42:20,040
그래서처럼 우리는 시저와 암호화 재료로 한

547
00:42:20,040 --> 00:42:25,190
모드를 사용, 우리는 일들이 주위에 포장을하고 계속 할 수 있습니다

548
00:42:25,190 --> 00:42:28,090
우리 대기열 주변과 주위와 주변과,

549
00:42:28,090 --> 00:42:32,180
그 헤드 포인터가 움직이는 유지.

550
00:42:32,180 --> 00:42:38,840
그 크기를 공지 사항은 항상 대기열에서 실제로 요소의 수를 존중합니다.

551
00:42:38,840 --> 00:42:43,110
그리고 이건 그냥 순환 유지 헤드 포인터입니다.

552
00:42:43,110 --> 00:42:49,660
우리는 처음으로 돌아 가야하는 경우, 여기서 무슨 일이 있었는지를 보면

553
00:42:49,660 --> 00:42:55,020
그리고 당신은 머리에 어떤 일이 일어 났는지

554
00:42:55,020 --> 00:42:58,240
우리가 뭔가를 인큐 때, 아무 머리에게 무슨 일이 있었 않습니다.

555
00:42:58,240 --> 00:43:00,970
우리가 다른 것을 enqueued 때, 아무 것도 머리에게 무슨 일이 있었 않습니다.

556
00:43:00,970 --> 00:43:04,130
우리가 뭔가를 dequeued 마자 머리 하나에 의해갑니다.

557
00:43:04,130 --> 00:43:06,600
우리가 뭔가를 enqueued 아무것도 머리에 변화가 없습니다.

558
00:43:06,600 --> 00:43:11,060
우리가 뭔가를 dequeue 때, 갑자기 모두 머리가 증가됩니다.

559
00:43:11,060 --> 00:43:14,660
우리가 뭔가를 인큐 때, 아무 것도 머리에 변화가 없습니다.

560
00:43:14,660 --> 00:43:20,240
>> 우리가 다시 무언가를 dequeue 할 경우 어떻게이 시점에서 무슨 일이 일어날?

561
00:43:20,240 --> 00:43:23,240
어떤 생각? 어떻게 머리에 무슨 일이 일어날?

562
00:43:23,240 --> 00:43:27,190
머리는 어떻게해야하나요

563
00:43:27,190 --> 00:43:32,990
우리가 다른 것을 dequeue 할 경우?

564
00:43:32,990 --> 00:43:35,400
머리는 지금, 색인 2입니다

565
00:43:35,400 --> 00:43:38,920
이는 대기열의 머리는 문자열 [2]을 의미합니다.

566
00:43:38,920 --> 00:43:44,280
[학생] 0을 반환입니까? >>이 0이되어야합니다. 그것은 정확히, 주변에 다시 포장해야합니다.

567
00:43:44,280 --> 00:43:48,440
지금까지, 우리는 dequeue라고 때마다, 우리는 머리에 한을 추가 했어요

568
00:43:48,440 --> 00:43:50,960
머리에 한 추가 머리에 한 추가 머리에 한을 추가합니다.

569
00:43:50,960 --> 00:43:58,400
그 헤드 포인터는 우리 배열의 마지막 색인에 도착, 가능한 빨리,

570
00:43:58,400 --> 00:44:05,650
그리고 우리가 처음으로 주위를 돌려 포장을해야합니다 0으로 돌아갑니다.

571
00:44:05,650 --> 00:44:09,900
[샬롯] 어떤 스택의 큐의 용량을 결정?

572
00:44:09,900 --> 00:44:13,120
[Hardison]는이 경우에, 우리는 # 정의 상수를 사용하고 있습니다. 좋아요 >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison]는 실제. C 파일에서, 당신이 약간의와 추문 갈 수

574
00:44:19,590 --> 00:44:21,710
그리고 큰 또는 원하는만큼 약간으로합니다.

575
00:44:21,710 --> 00:44:25,310
[샬롯]는 그래서 당신은 그것을 대기열을 할 때, 당신은 컴퓨터를 알고 어떻게해야합니까

576
00:44:25,310 --> 00:44:29,120
당신은 스택이되고 싶어 얼마나 큰?

577
00:44:29,120 --> 00:44:31,700
[Hardison] 그건 큰 문제입니다.

578
00:44:31,700 --> 00:44:34,800
몇 가지 방법이 있습니다. 하나가 앞을 사실을 정의하는 것입니다

579
00:44:34,800 --> 00:44:42,050
이 말을 4 요소 또는 50 요소 또는 만이 큐가 될 것입니다.

580
00:44:42,050 --> 00:44:45,430
다른 방법은 해커 판 사람들이하는 일을하는 것입니다

581
00:44:45,430 --> 00:44:52,310
더 많은 일이 인치 추가 할로 큐가 동적으로 성장해야하는 함수를 만들

582
00:44:52,310 --> 00:44:54,740
>> [샬롯]는 그래서 첫 번째 옵션으로 가서, 어떤 구문을 사용합니까

583
00:44:54,740 --> 00:44:57,830
프로그램을 알려 대기열의 크기는 무엇인가?

584
00:44:57,830 --> 00:45:04,780
[Hardison] 아. 그럼이 나가자.

585
00:45:04,780 --> 00:45:12,650
여기 stack.c 란 말이야, 그래서 그냥 위로 스크롤거야.

586
00:45:12,650 --> 00:45:17,920
이 바로이 부​​분을 볼 수 있나요? 이것은 # 용량 (10) 정의입니다.

587
00:45:17,920 --> 00:45:24,600
그리고 우리가 큐에 가지고 거의 동일한 구문입니다.

588
00:45:24,600 --> 00:45:28,390
대기열에를 제외하고, 우리는 여기에 그 여분의 구조체 필드있어.

589
00:45:28,390 --> 00:45:32,760
[샬롯] 오, 용량이 문자열에 대한 능력을 의미 알았는데.

590
00:45:32,760 --> 00:45:36,770
[Hardison] 아. 이 단어의 최대 길이 거라고 생각 >>. >>은 알았어.

591
00:45:36,770 --> 00:45:41,180
그래. 여기에 용량은 - 그 좋은 점입니다.

592
00:45:41,180 --> 00:45:44,000
그리고이 까다로운 뭔가있다

593
00:45:44,000 --> 00:45:49,480
우리가 여기에 선언 한 것은 문자 * s의 배열이기 때문이다.

594
00:45:49,480 --> 00:45:52,770
포인터의 배열입니다.

595
00:45:52,770 --> 00:45:56,690
이 문자의 배열입니다.

596
00:45:56,690 --> 00:46:01,690
이렇게하면 파일에 대한 버퍼를 선언했을 때 당신이 본 게 뭔지 아마 I / O,

597
00:46:01,690 --> 00:46:06,840
당신은 스택에 수동으로 문자열을 생성했을 때.

598
00:46:06,840 --> 00:46:09,090
그러나 우리가 여기 가진 건 숯불 * s의 배열입니다.

599
00:46:09,090 --> 00:46:13,400
그럼 포인터의 배열입니다.

600
00:46:13,400 --> 00:46:18,350
사실, 우리는 다시 축소 우리는 여기서 무슨 일이 벌어 보면

601
00:46:18,350 --> 00:46:23,140
프리젠 테이션에, 당신이 실제 요소, 문자 데이터를 볼 수

602
00:46:23,140 --> 00:46:26,180
배열 자체 내에 저장되지 않습니다.

603
00:46:26,180 --> 00:46:42,690
여기서 우리 어레이 내에 저장된 것은 문자 데이터에 대한 포인터입니다.

604
00:46:42,690 --> 00:46:52,560
좋아요. 그래서 우리는, 큐의 크기가 단지 스택과 마찬가지로하는 방법을 본 적이

605
00:46:52,560 --> 00:46:58,670
크기는 항상 대기열에 현재 요소 수를 존중합니다.

606
00:46:58,670 --> 00:47:02,720
이 enqueues을 한 후, 크기는 2입니다.

607
00:47:02,720 --> 00:47:07,110
dequeue을 한 후 크기는 현재 1입니다.

608
00:47:07,110 --> 00:47:09,330
다른 인큐을 한 후 크기는 2로 돌아합니다.

609
00:47:09,330 --> 00:47:12,340
따라서 크기는 분명히 큐에 요소 수를 존중

610
00:47:12,340 --> 00:47:15,580
그리고 머리는 자전거를 보관합니다.

611
00:47:15,580 --> 00:47:20,210
이 0-1-2, 0-1-2, 0-1-2에서갑니다.

612
00:47:20,210 --> 00:47:25,620
그리고 우리가 dequeue를 호출 때마다, 헤드 포인터는 다음 색인에 증가됩니다.

613
00:47:25,620 --> 00:47:29,930
머리를 가서하려고하​​는 경우 그리고, 그 뒤로 0 루프.

614
00:47:29,930 --> 00:47:34,870
그래서 그와 함께, 우리는 dequeue 함수를 쓸 수 있습니다.

615
00:47:34,870 --> 00:47:40,200
우리는 너희들이 대신 구현하기위한 인큐 기능을 떠날거야.

616
00:47:40,200 --> 00:47:45,880
>> 우리는 큐의 요소를 dequeue 때,

617
00:47:45,880 --> 00:47:55,490
우리가 스택에 대한 팝업 기능을 쓰기 시작한 다니엘했던 처음하는 일이 무엇 이었습니까?

618
00:47:55,490 --> 00:48:00,490
저 아직 말을하지 않은 사람의 말을 들어 봅시다.

619
00:48:00,490 --> 00:48:06,710
, 어디 한번 사드하자, 당신은 대니얼 그가 팝업 처음 쓴 것은으로 무슨 짓을했는지 기억하나요?

620
00:48:06,710 --> 00:48:08,860
[사드]가 발생했습니다되었다 - 그는 무언가에 대한 테스트 >>.

621
00:48:08,860 --> 00:48:12,140
[사드] 크기가 0보다 큰 경우. 정확히 >>.

622
00:48:12,140 --> 00:48:14,390
그리고에 대해 해당 테스트는 무엇 이었습니까?

623
00:48:14,390 --> 00:48:19,090
[사드] 배열 내부 것이 있는지 확인하는 테스트 거예요.

624
00:48:19,090 --> 00:48:23,210
[Hardison] 그래. 그렇지. 이 비어 있다면 그래서 당신은 스택의에서 아무 열어 할 수 없습니다.

625
00:48:23,210 --> 00:48:26,510
이 비어 있다면 마찬가지로, 당신은 대기열에서 아무것도 dequeue 할 수 없습니다.

626
00:48:26,510 --> 00:48:30,420
우리 마을은 우리가 dequeue 함수에서 어떻게해야 가장 먼저는 무엇입니까, 당신 생각은?

627
00:48:30,420 --> 00:48:33,860
[사드] 크기가 0보다 큰 경우? >> 그래.

628
00:48:33,860 --> 00:48:37,710
이 경우, 사실은 그냥 0 있는지 확인하기 위해 테스트되었습니다.

629
00:48:37,710 --> 00:48:42,240
가 0 인 경우는 null 반환 할 수 있습니다.

630
00:48:42,240 --> 00:48:45,280
그러나 동일한 논리.

631
00:48:45,280 --> 00:48:49,110
그리고의이을 계속 보자.

632
00:48:49,110 --> 00:48:54,600
크기가 0이 아닌 경우, 우리는 dequeue 할 요소는 어디 있죠?

633
00:48:54,600 --> 00:48:58,550
[사드] 머리에서? 정확히 >>.

634
00:48:58,550 --> 00:49:01,720
우리는 우리 대기열의 첫 번째 요소를 뺄 수

635
00:49:01,720 --> 00:49:07,040
머리에서 요소를 액세스하여.

636
00:49:07,040 --> 00:49:14,630
미친 아무것도.

637
00:49:14,630 --> 00:49:19,620
그 후, 우리는 어떻게해야합니까? 어떻게 무슨 일이 있나요?

638
00:49:19,620 --> 00:49:23,740
우리가 dequeue에 대해 이야기하는 다른 것은 무엇입니까?

639
00:49:23,740 --> 00:49:28,130
우리의 큐가 변경 되었기 때문에 두 가지가 일어날 수 있습니다.

640
00:49:28,130 --> 00:49:35,640
[다니엘]의 크기를 줄입니다. >> 우리는 크기를 줄일 수 있으며, 머리를 높일 수 있나요? 그렇지.

641
00:49:35,640 --> 00:49:40,600
머리를 높이려면, 우리는 맹목적으로 기억 머리를 늘릴 수 없습니다.

642
00:49:40,600 --> 00:49:45,080
우리는 queue.head을하지 못하는 + +.

643
00:49:45,080 --> 00:49:51,630
우리는 또한 용량으로이 모드를 포함해야합니다.

644
00:49:51,630 --> 00:49:54,740
그리고 왜 우리는 용량에 의해 스텔라 MOD 어떻게해야합니까?

645
00:49:54,740 --> 00:49:58,680
[스텔라]는 주변에 줄 바꿈하는 때문입니다. 정확히 >>.

646
00:49:58,680 --> 00:50:04,750
용량에 의해 우리는 모드가 0에 다시 포장을해야하기 때문.

647
00:50:04,750 --> 00:50:07,400
그래서 지금,이 시점에서 우리는 다니엘이 말을 할 수 있습니다.

648
00:50:07,400 --> 00:50:12,700
우리는 크기를 감소 할 수 있습니다.

649
00:50:12,700 --> 00:50:29,170
그리고 우리가 대기열의 맨 위에있는 요소를 반환 할 수 있습니다.

650
00:50:29,170 --> 00:50:34,000
처음에는 밥맛 가지 보입니다. 당신은 질문이있을 수 있습니다. 뭐라고 요?

651
00:50:34,000 --> 00:50:37,260
>> [샘] 왜 큐의 상단에 처음이다? 그 어디가는 거지?

652
00:50:37,260 --> 00:50:42,480
[Hardison] 그것은 아래에서 네 번째 라인에서 제공합니다.

653
00:50:42,480 --> 00:50:46,060
우리는 우리의 큐가 비어 있지 않도록 테스트 한 후

654
00:50:46,060 --> 00:50:54,100
우리가 처음 숯불 *를 꺼내, 우리는 머리를 색인에 앉아 요소를 뽑아

655
00:50:54,100 --> 00:50:58,680
우리의 배열, 우리의 문자열 배열, >>를 호출 첫 번째의?

656
00:50:58,680 --> 00:51:04,500
[Hardison] 우리는 처음 전화하십시오. 그래.

657
00:51:04,500 --> 00:51:09,850
그에 따라, 당신은 왜 우리가 그 일을 할 수 밖에없는 생각합니까?

658
00:51:09,850 --> 00:51:18,270
[샘] 각 처음으로 단지 q.strings를 제공하고 있습니다 [q.head]? >> 그래.

659
00:51:18,270 --> 00:51:23,830
>> 우리가 모듈로 기능을 q.head이 변화하고 있어요 때문에,

660
00:51:23,830 --> 00:51:27,810
또한 리턴 라인 내에서 해당 작업을 수행 할 수있는 방법은 없습니다.

661
00:51:27,810 --> 00:51:31,640
[Hardison] 그렇지. 당신은에 자리하고 있습니다. 샘은 완전히에 반점입니다.

662
00:51:31,640 --> 00:51:36,800
우리는 큐의 첫 번째 요소를 꺼내 변수로를 저장하는 이유는,,,

663
00:51:36,800 --> 00:51:43,030
우리가이 줄을 q.head 한 곳 때문입니다

664
00:51:43,030 --> 00:51:47,030
거기에 모듈로 연산자는 우리가 할 수있는 뭔가가, 안 그래

665
00:51:47,030 --> 00:51:51,230
그리고없이 머리에 적용했습니다 - 한 줄 인치

666
00:51:51,230 --> 00:51:54,480
우리가 실제로 첫 번째 요소를 뽑아 내야하고, 머리를 조정

667
00:51:54,480 --> 00:52:00,430
크기를 조정 한 다음 우리가 철수하는 요소를 반환합니다.

668
00:52:00,430 --> 00:52:02,680
그리고 우리는 나중에 마련 볼 수 있습니다 왔던 것입니다

669
00:52:02,680 --> 00:52:04,920
연결리스트, 우리는 그들과 주변 연주로.

670
00:52:04,920 --> 00:52:08,410
당신은 연결 목록의 해방 또는 폐기하고 종종 때

671
00:52:08,410 --> 00:52:13,500
당신은 다음 요소, 연결리스트의 다음 포인터를 기억해야

672
00:52:13,500 --> 00:52:16,330
현재 하나 폐기 처분하기 전에.

673
00:52:16,330 --> 00:52:23,580
때문에 그렇지 않으면 당신은 목록에 남아있는의 정보를 버린다.

674
00:52:23,580 --> 00:52:34,160
귀하의 어플라이언스로 가면 이제,이 중 queue.c--X를 엽니 다.

675
00:52:34,160 --> 00:52:39,390
제가 queue.c을 열고 경우, 나를 여기에 확대하게

676
00:52:39,390 --> 00:52:44,970
당신이 비슷한 파일이 것을 확인할 수 있습니다.

677
00:52:44,970 --> 00:52:49,200
우리가 stack.c과 이전에했던 일에 비슷한 파일입니다.

678
00:52:49,200 --> 00:52:54,690
우리는 슬라이드에서 본대로 방금 정의한 대기열에 대한 우리의 구조체있어.

679
00:52:54,690 --> 00:52:59,870
>> 우리는 당신 할 것입니다 우리의 인큐 기능을 갖추고 있습니다.

680
00:52:59,870 --> 00:53:04,340
그리고 우리는 여기 dequeue 함수가 있습니다.

681
00:53:04,340 --> 00:53:06,870
파일의 dequeue 함수는 unimplemented되고,

682
00:53:06,870 --> 00:53:13,230
원하는 경우에 그것을 입력 할 수 있도록하지만 파워 포인트에서 다시 올려드립니다.

683
00:53:13,230 --> 00:53:16,690
따라서 향후 5 분 정도를 들어, 너희들은 인큐에서 작동

684
00:53:16,690 --> 00:53:22,570
이는 거의 단지 dequeue의 맞은 편에 위치해 있습니다.

685
00:53:22,570 --> 00:53:29,560
당신이 enqueueing 때 머리를 조정할 필요는 없습니다,하지만 당신은 조정해야하나요?

686
00:53:29,560 --> 00:53:38,920
크기입니다. 그래서 인큐, 머리는 손길이 닿지 않은 유지하면 크기가 변경됩니다.

687
00:53:38,920 --> 00:53:46,920
그러나 약간의 시간이 걸립니까 - 그 모드들을 플레이해야합니다

688
00:53:46,920 --> 00:53:57,560
새로운 요소가에 삽입해야하는지 인덱스 것인지 알아 내려고합니다.

689
00:53:57,560 --> 00:54:03,080
그래서 너희들에게 조금주지, 슬라이드에 다시 dequeue를 넣어

690
00:54:03,080 --> 00:54:05,200
그리고 사람들이 질문을 가지고, 그래서 우리가 할 수있는 그들을 큰소리

691
00:54:05,200 --> 00:54:09,220
그룹으로 그들에 대한 모든 이야기.

692
00:54:09,220 --> 00:54:13,960
또한 하지마 크기 - 당신은 크기를 조정했을 때, 당신은 항상 할 수 -

693
00:54:13,960 --> 00:54:18,720
혹시 크기를 모드해야합니까? [다니엘] 번호 >> 당신은 크기를 MOD 오른쪽이 없습니다.

694
00:54:18,720 --> 00:54:24,260
, 당신은면의 크기는 항상 것입니다 - 가정 당신이 적절하게 물건을 관리하는

695
00:54:24,260 --> 00:54:30,840
크기는 항상 0과 3 사이 여야합니다.

696
00:54:30,840 --> 00:54:38,680
여기가 어디 인큐을 채취 할 때 MOD해야하나요?

697
00:54:38,680 --> 00:54:41,060
만 머리에 [학생]. 만 머리에 >>, 맞아요.

698
00:54:41,060 --> 00:54:44,620
그리고 왜 인큐에 전혀 MOD해야하나요?

699
00:54:44,620 --> 00:54:48,830
때 MOD하는 수 밖에 없어요있는 상황입니까?

700
00:54:48,830 --> 00:54:53,630
이 공간에 물건이 있으면 [학생], 공백 1, 2에 좋아

701
00:54:53,630 --> 00:54:55,950
다음은 0에서 뭔가를 추가 할 필요가있었습니다.

702
00:54:55,950 --> 00:55:02,570
[Hardison] 네, 맞아요. 머리 포인터가 매우 끄트머리에 위치해 자한다면,

703
00:55:02,570 --> 00:55:14,210
또는 크기 플러스 머리가 큰 경우, 또는 오히려 대기열 주위에 래핑 할 것이다.

704
00:55:14,210 --> 00:55:17,830
>> 그래서 우리는 지금 슬라이드에 여기에있어 한 상황에서,

705
00:55:17,830 --> 00:55:24,370
나는 지금 무언가를 인큐하려는 경우

706
00:55:24,370 --> 00:55:31,110
우리는 인덱스 0에서 뭔가를 인큐하고 싶습니다.

707
00:55:31,110 --> 00:55:35,450
당신은 50 어디로 가는지보고, 나는 인큐 50 전화면

708
00:55:35,450 --> 00:55:40,840
그 아래에 내려갑니다. 이 인덱스 0에갑니다.

709
00:55:40,840 --> 00:55:44,160
이미 dequeued 된 '안녕'을 대체합니다.

710
00:55:44,160 --> 00:55:46,210
[다니엘]이 (가) 당신이 이미 dequeue에 그 처리하지 마십시오?

711
00:55:46,210 --> 00:55:50,550
왜 인큐의 머리를 짓입니까?

712
00:55:50,550 --> 00:55:55,770
[Hardison] 오, 그럼, 넌 머리를 수정하지, 미안 해요.

713
00:55:55,770 --> 00:56:02,310
하지만 당신은에 액세스 할 때 모듈로 연산자를 사용해야합니다

714
00:56:02,310 --> 00:56:04,250
당신이 액세스 할 때 인큐 할 요소

715
00:56:04,250 --> 00:56:06,960
대기열의 다음 요소입니다.

716
00:56:06,960 --> 00:56:10,960
[바질] 그 짓도 안 했어, 그리고 난 거기에 "성공"을 가지고.

717
00:56:10,960 --> 00:56:13,370
[다니엘] 아, 난 당신이 무슨 말을하는지 알아.

718
00:56:13,370 --> 00:56:16,240
[Hardison]이 그래서 그냥 .. - 방금 q.size에서나요?

719
00:56:16,240 --> 00:56:20,670
[바질] 그래. 난 그냥면을 변경, 내가 머리를 아무 짓도하지 않았어요.

720
00:56:20,670 --> 00:56:24,300
[Hardison] 당신은 실제로 아무것도 할 머리를 재설정 할 필요가 없습니다

721
00:56:24,300 --> 00:56:31,650
하지만 문자열 배열로 할 때 인덱스

722
00:56:31,650 --> 00:56:39,500
당신은 실제로 가서 다음 요소가있는 곳 계산해야

723
00:56:39,500 --> 00:56:44,230
스택을 실 가지로 묶다 때문에, 당신의 스택에있는 다음 요소는 항상

724
00:56:44,230 --> 00:56:48,740
크기에 해당하는 색인​​에.

725
00:56:48,740 --> 00:56:55,850
우리가 우리의 스택 푸시 기능에서 다시 만난다면

726
00:56:55,850 --> 00:57:03,100
우리는 항상 오른쪽 인덱스 크기의 새로운 요소에 쿵하는 소리 수 있습니다.

727
00:57:03,100 --> 00:57:06,710
대기열 반면, 우리는 할 수 없어

728
00:57:06,710 --> 00:57:10,340
우리가이 상황에 있으면 때문에,

729
00:57:10,340 --> 00:57:18,130
우리가 enqueued 경우 50 새로운 문자열은 문자열 [1]에서 오른쪽으로 갈거야

730
00:57:18,130 --> 00:57:20,540
있는 우리는하고 싶지 않아요.

731
00:57:20,540 --> 00:57:41,200
우리는 새로운 문자열 인덱스 0에 가서하길 원한다.

732
00:57:41,200 --> 00:57:44,320
>> 않는 사람이 - 네? [학생] 내가 질문이 있지만 정말 관련이 없습니다.

733
00:57:44,320 --> 00:57:48,160
누군가가 단지 pred 포인터 같은 것을 호출 할 때 무엇을 의미합니까?

734
00:57:48,160 --> 00:57:51,260
그 이름이 무엇에 줄여서 그런 건가요? 나는 그냥 이름 알아.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred 포인터? 어디 봅시다. 어떤 맥락에서?

736
00:57:59,110 --> 00:58:01,790
[학생]는 삽입하는 것은이었다. 당신이 원하는 경우 나중에 요청할 수 있습니다

737
00:58:01,790 --> 00:58:03,920
정말 관련이 없습니다 만, 난 그냥 있기 때문에 -

738
00:58:03,920 --> 00:58:07,300
[Hardison] 강의에서 다윗의 삽입 코드에서?

739
00:58:07,300 --> 00:58:10,860
우리는 그를 끌어와 그 부분에 대해 이야기를 할 수 있습니다.

740
00:58:10,860 --> 00:58:15,550
우리는 다음, 일단 우리가 링크 된 목록에 도착에 대해 얘기하자.

741
00:58:15,550 --> 00:58:21,440
>> 따라서 인큐 함수가 어떻게 생겼는지 살펴 정말 빠르게 까.

742
00:58:21,440 --> 00:58:26,530
사람들이 귀하의 인큐 줄에 수행하려고하는 첫 번째 것은 무엇입니까? 이 대기열에?

743
00:58:26,530 --> 00:58:29,960
당신이 밀어 스택에 무슨 짓을했는지와 유사합니다.

744
00:58:29,960 --> 00:58:32,080
당신은 스텔라, 무슨 짓을 한거야?

745
00:58:32,080 --> 00:58:35,050
[스텔라, 이해할 수없는]

746
00:58:35,050 --> 00:58:45,700
[Hardison] 그렇지. (== 용량을 q.size) 경우 -

747
00:58:45,700 --> 00:58:54,720
내가 그럴 권리가 장소에 내 괄호를 넣어해야 할 것은 - false를 반환합니다.

748
00:58:54,720 --> 00:59:01,370
조금 확대합니다. 좋아요.

749
00:59:01,370 --> 00:59:03,800
이제 우리는 짓을 할 수 밖에 없었던 그 다음은 뭐죠?

750
00:59:03,800 --> 00:59:11,370
그냥 스택을 좋아하고, 그 장소에 삽입.

751
00:59:11,370 --> 00:59:16,010
그리고 그렇게를 삽입 할 수있는 권리 장소는 무엇 이었습니까?

752
00:59:16,010 --> 00:59:23,170
스택과는별로 그건이 일과, 색인 크기이​​었다.

753
00:59:23,170 --> 00:59:30,210
[다니엘] 내가 q.head - 또는이 - >>의 q.strings를? >> 그래.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size MOD 능력]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] 우리는 아마도이 문제를 해결 괄호를 넣었 으면 좋겠어

756
00:59:42,740 --> 00:59:48,830
우리는 모두에게 cleart 인 것 적절한 우선 순위를 받고 그래야.

757
00:59:48,830 --> 00:59:55,800
그리고 그 같은 설정? 으로 str에게 >>? 으로 str에게 >>. 좋아요.

758
00:59:55,800 --> 01:00:00,160
그리고 지금 우리가해야 할 것이 마지막이 뭐죠?

759
01:00:00,160 --> 01:00:06,780
우리는 스택에 그랬던 것처럼. >>의 크기를 증가? >>의 크기를 증가.

760
01:00:06,780 --> 01:00:13,830
붐. 그리고, 시작 코드부터, 그냥 기본적으로 false를 반환

761
01:00:13,830 --> 01:00:27,460
우리 모두는지나 모두가 잘되면 true로를 변경하고 싶습니다.

762
01:00:27,460 --> 01:00:33,050
괜찮아요. 해당 섹션에 대한 정보의 많은입니다.

763
01:00:33,050 --> 01:00:39,480
우리는 상당히 이상하지. 우리는 단독으로 연결된 목록은 정말 빠르게 얘기하고 싶어요.

764
01:00:39,480 --> 01:00:44,010
이를 놓을 게요 그래서 우리는 나중에 다시 이동할 수 있습니다.

765
01:00:44,010 --> 01:00:50,850
그러나의 더 몇 슬라이드에 우리의 프리젠 테이션으로 돌아 가자.

766
01:00:50,850 --> 01:00:53,790
따라서 인큐가 TODO이며, 이제 우리는 그것을 한 적이있어.

767
01:00:53,790 --> 01:00:57,430
>> 이번에는 단독으로 연결된 목록을 살펴 보자.

768
01:00:57,430 --> 01:01:00,040
우리는 강의에서이 조금 더 이야기.

769
01:01:00,040 --> 01:01:02,540
우리가 사람들을 한 곳에서 몇 너희들의 데모를 본

770
01:01:02,540 --> 01:01:08,220
어색 서로 홀딩 숫자를 가리키고? >> 난 그했다.

771
01:01:08,220 --> 01:01:16,620
>> 당신들은 어떻게 생각 했어? 그 짓을, 희망이 조금 demystify?

772
01:01:16,620 --> 01:01:25,990
목록으로 우리가 우리가 노드에 전화를하고있는 이러한 유형의 처리을 이용할 수 있습니다.

773
01:01:25,990 --> 01:01:32,520
대기열과 스택 반면 우리는 우리가 스택에 큐를 호출한다고 structs를했다

774
01:01:32,520 --> 01:01:34,860
우리는 스택 타입의 새 큐를 가지고

775
01:01:34,860 --> 01:01:39,240
여기에 목록이 단지 노드의 무리로 구성되어 있습니다.

776
01:01:39,240 --> 01:01:45,920
문자열이 문자들 뿐이 것을 같은 방식으로 모든 서로 옆에 줄 지어.

777
01:01:45,920 --> 01:01:50,650
연결리스트는 노드와 다른 노드와 다른 노드와 다른 노드입니다.

778
01:01:50,650 --> 01:01:55,080
그리고 오히려 함께 모든 노드를 마쳤와 contiguously를 저장하는 것보다

779
01:01:55,080 --> 01:01:58,090
메모리에 서로 바로 옆에 모두,

780
01:01:58,090 --> 01:02:04,470
이 다음 포인터를 갖는 것은 우리가 무작위로, 노드 곳을 저장할 수 있습니다.

781
01:02:04,470 --> 01:02:10,500
그리고 전선의 종류 다 함께 하나에서 다음을 가리 키도록.

782
01:02:10,500 --> 01:02:15,850
>> 그리고이 배열을 통해 있다는 큰 장점 였죠?

783
01:02:15,850 --> 01:02:21,680
저장 모든 걸 contiguously 서로 옆에 붙어?

784
01:02:21,680 --> 01:02:24,190
기억 나? 응? >> 동적 메모리 할당?

785
01:02:24,190 --> 01:02:27,220
어떤 의미에서 >> 동적 메모리 할당?

786
01:02:27,220 --> 01:02:31,780
당신이 더 당신이 전체 배열을 이동 할 필요가 없습니다 만들기 유지할 수 있다는 점에서 [학생]?

787
01:02:31,780 --> 01:02:40,940
[Hardison] 그렇지. 따라서 배열로, 당신은 그것의 중간에 새로운 요소를 넣어하려는 경우,

788
01:02:40,940 --> 01:02:45,320
당신은 공간을 만들기 위해 모든 이동해야합니다.

789
01:02:45,320 --> 01:02:47,880
그리고 같은 우리는 대기열에 대한 이야기

790
01:02:47,880 --> 01:02:50,080
우리가 헤드 포인터를 유지 거로군요

791
01:02:50,080 --> 01:02:52,050
우리는 지속적으로 물건을 이동하지 않도록.

792
01:02:52,050 --> 01:02:54,520
당신이 큰 배열이 있다면 그 돈이 정말 많이 들어 있기 때문에

793
01:02:54,520 --> 01:02:57,130
그리고 당신은 항상이 무작위로 삽입을 다하고 있습니다.

794
01:02:57,130 --> 01:03:00,820
목록 반면, 당신이해야 할 모든은 새로운 노드에 던져 is

795
01:03:00,820 --> 01:03:06,330
포인터를 조정하면됩니다.

796
01:03:06,330 --> 01:03:10,940
어떻게이 사실을 엿?

797
01:03:10,940 --> 01:03:16,830
이외에도이 배열로 작동하도록 쉬운 일이 아닙니다 사실에서? 응?

798
01:03:16,830 --> 01:03:22,980
[다니엘] 글쎄, 난이 연결리스트의 특정 요소에 액세스하기가 훨씬 더 어렵 겠죠?

799
01:03:22,980 --> 01:03:30,470
[Hardison] 당신은 당신의 연결리스트의 중간에 임의의 요소로 바로 이동할 수 없습니다.

800
01:03:30,470 --> 01:03:33,800
어떻게 대신해야합니까? 당신은 모든 게를 탐색해야합니다 >>.

801
01:03:33,800 --> 01:03:35,660
[Hardison] 그래. 당신은 한 번에 한, 한 번에 하나의 통과해야합니다.

802
01:03:35,660 --> 01:03:38,480
그것은 거대한 - 이건 고통입니다.

803
01:03:38,480 --> 01:03:41,550
다른 하나는 무엇입니까 -이 또 다른 몰락이 있어요.

804
01:03:41,550 --> 01:03:45,340
[바질] 당신은 앞으로 및 뒤로 갈 수 있습니까? 한 방향을 가야 해요?

805
01:03:45,340 --> 01:03:48,570
[Hardison] 그래. 그럼 우리는 때때로 그 해결합니까?

806
01:03:48,570 --> 01:03:53,370
[바질] 목록에게 이중 - 연결? 정확히 >>. 이중 - 링크 목록이 있습니다.

807
01:03:53,370 --> 01:03:55,540
도 있습니다 - 뭐라고 요?

808
01:03:55,540 --> 01:03:57,620
>> [샘]이 그 pred 것을 사용과 동일합니다 -

809
01:03:57,620 --> 01:04:01,090
난 그냥 기억, pred 것은 무슨 일 것을이 아닌 것은 무엇입니까?

810
01:04:01,090 --> 01:04:05,850
저 사람 이중과 단독 사이에?

811
01:04:05,850 --> 01:04:10,020
그가 무슨 짓을하는지 정확히에서 [Hardison] 가자의 모습.

812
01:04:10,020 --> 01:04:15,760
그래서 여기에 우리가 이동합니다. 다음은 그 목록 코드입니다.

813
01:04:15,760 --> 01:04:25,620
여기 우리가 여기에 predptr 있습니다. 당신이 무슨 말을하는지인가요?

814
01:04:25,620 --> 01:04:30,750
그래서이 였어요 - 그 목록을 자유롭게 있고 그가에 대한 포인터를 저장하려고합니다.

815
01:04:30,750 --> 01:04:35,000
이 이중, 단독으로 연결된 - 목록이 아닙니다.

816
01:04:35,000 --> 01:04:40,090
이 이야기이기 때문에 우리는 목록을 해방에 대해 나중에이에 대한 자세한 내용을 이야기 할 수

817
01:04:40,090 --> 01:04:42,900
그리고 처음 다른 물건을 보여주고 싶어.

818
01:04:42,900 --> 01:04:51,480
하지만 그건 단지 - 이건 PTR의 가치를 내고 있잖아

819
01:04:51,480 --> 01:04:54,170
[학생] 오, preceeding 포인터거야? >> 그래.

820
01:04:54,170 --> 01:05:04,070
우리는 predptr가 무엇인지, 우리가 무료 전에 PTR 자체를 증가시킬 수 있도록.

821
01:05:04,070 --> 01:05:09,130
우리는 무료 PTR 및 전화 PTR = PTR 다음, 그렇죠? 할 수 없으므로

822
01:05:09,130 --> 01:05:11,260
그거 나쁜 것입니다.

823
01:05:11,260 --> 01:05:20,940
그러니까이 남자에게, 어디 보자.

824
01:05:20,940 --> 01:05:23,900
>> 목록에 대한 또 다른 나쁜 것은, 배열이있는 반면

825
01:05:23,900 --> 01:05:26,520
우리는, 스스로가 서로 옆에 쌓여있는 모든 요소가

826
01:05:26,520 --> 01:05:29,050
여기에 우리는이 포인터를 도입했습니다.

827
01:05:29,050 --> 01:05:34,060
그래서 우리가 사용하는 데 메모리의 추가 덩어리가 있어요

828
01:05:34,060 --> 01:05:37,910
우리 목록에 저장중인 모든 요소.

829
01:05:37,910 --> 01:05:40,030
우리는 유연성을하지만 비용이 부과됩니다.

830
01:05:40,030 --> 01:05:42,230
그것은이 시간 비용이 있습니다

831
01:05:42,230 --> 01:05:45,270
그리고 너무이 메모리 비용이 함께 제공됩니다.

832
01:05:45,270 --> 01:05:47,800
우리가 배열의 모든 요소를​​ 통과해야하는 의미에서 시간

833
01:05:47,800 --> 01:05:58,670
색인 10시 하나 또는 그 배열에 인덱스 열 있었을 거라고을 찾으십시오.

834
01:05:58,670 --> 01:06:01,230
>> 정말 빠르게 때 그림에서이 목록을

835
01:06:01,230 --> 01:06:05,980
일반적으로 우리는 목록의 머리 나 목록의 첫 번째 포인터에 개최

836
01:06:05,980 --> 01:06:08,010
그리고이 진정한 포인터됩니다.

837
01:06:08,010 --> 01:06:11,100
단지 4 바이트입니다. 그것은 실제 노드 자체 없습니다.

838
01:06:11,100 --> 01:06:17,120
그래서 그것에 int 값, 거기에 더 옆에 포인터를가 없음을 참조하십시오.

839
01:06:17,120 --> 01:06:20,790
그것은 말 그대로 단지 포인터입니다.

840
01:06:20,790 --> 01:06:23,550
그것은 실제 노드 구조체없는 일을 가리 키도록거야.

841
01:06:23,550 --> 01:06:28,480
[샘] 노드라는 포인터? >>입니다 - 안돼. 이 유형의 노드의 무언가에 대한 포인터입니다.

842
01:06:28,480 --> 01:06:32,540
이 노드 구조체에 대한 포인터입니다. >> 아, 그래.

843
01:06:32,540 --> 01:06:36,870
오른쪽에있는 왼쪽, 코드에 다이어그램.

844
01:06:36,870 --> 01:06:42,190
우리는 시작하는 좋은 방법입니다 0,로 설정할 수 있습니다.

845
01:06:42,190 --> 01:06:49,850
때 그림을, 그런 당신도 그 널 (null)로 작성하거나 그것을 통해 라인을 넣어.

846
01:06:49,850 --> 01:06:53,910
>> 목록에서 작동 할 수있는 가장 쉬운 방법 중 하나는,

847
01:06:53,910 --> 01:06:57,430
우리는, 당신은 모두 앞에 짓을 요청하고 둘 사이의 차이를 볼 수 추가

848
01:06:57,430 --> 01:07:01,320
하지만 prepending는 확실히 쉽습니다.

849
01:07:01,320 --> 01:07:05,790
어디에 당신이 앞에 때이입니다 - 때 앞에 (7)

850
01:07:05,790 --> 01:07:10,050
당신은 노드 구조체에 가서 만들

851
01:07:10,050 --> 01:07:13,870
당신은 지금 있기 때문에 그것을 prepended 때문에, 그것을 가리 먼저 설정

852
01:07:13,870 --> 01:07:17,240
이 목록의 시작 부분에있을거야.

853
01:07:17,240 --> 01:07:22,540
우리 다른 노드를 생성 앞에 (3), 지금 3 7 전에 온다면.

854
01:07:22,540 --> 01:07:31,130
그래서 우리는 기본적으로 목록에 물건을 밀어하고 있습니다.

855
01:07:31,130 --> 01:07:34,720
지금, 당신은 앞에은, 가끔 사람들이이 밀어 전화 것을 알 수 있습니다

856
01:07:34,720 --> 01:07:39,600
때문에 귀하의 목록에 새로운 요소를 밀어하고 있습니다.

857
01:07:39,600 --> 01:07:43,270
이 목록의 앞에 삭제도 간단합니다.

858
01:07:43,270 --> 01:07:45,650
그래서 사람들은 자주 팝업을 호출합니다.

859
01:07:45,650 --> 01:07:52,200
그리고 그 방법으로, 당신은 연결리스트를 사용하여 스택을 에뮬레이션 할 수 있습니다.

860
01:07:52,200 --> 01:07:57,880
죄송합니다. 죄송합니다, 지금 우리는 추가로지고있어. 그래서 여기 우리 앞에 (3) 이제 (7) prepended.

861
01:07:57,880 --> 01:08:02,600
만약 우리가 prepended 경우 우리는 (4),이 목록에 다른 일을 prepended,

862
01:08:02,600 --> 01:08:06,540
그러면 우리는 4가 있으며 3 다음 다음 7 할.

863
01:08:06,540 --> 01:08:14,220
그럼 우리가 나타나서 제거 3, 4를 제거 할 수, 7을 제거합니다.

864
01:08:14,220 --> 01:08:16,500
종종이 생각하는보다 직관적 인 방법은 추가로 있습니다.

865
01:08:16,500 --> 01:08:20,310
그래서 여기 추가로 모습을 무엇인지 diagrammed했습니다.

866
01:08:20,310 --> 01:08:23,380
여기 추가 (7) 다를 보이지 않는다

867
01:08:23,380 --> 01:08:25,160
때문에 목록에 하나의 요소가 있습니다.

868
01:08:25,160 --> 01:08:28,620
그리고 첨부 (3) 끝을 넣습니다.

869
01:08:28,620 --> 01:08:31,020
아마 당신은 지금 추가로 트릭을 볼 수 있습니다

870
01:08:31,020 --> 01:08:36,600
즉, 목록의 시작 부분이 어디에은 알고부터입니다

871
01:08:36,600 --> 01:08:39,450
이 목록을 통해 모든 방법을 걸어서 가야 목록에 추가 할

872
01:08:39,450 --> 01:08:46,500
, 마지막까지 중지 한 다음 노드 아래로 쿵하는 소리 모든을 구축 할 수 있습니다.

873
01:08:46,500 --> 01:08:50,590
모든 물건을 다 와이어.

874
01:08:50,590 --> 01:08:55,170
그럼 앞에있는 것처럼 우리가 정말 빨리이 일을 냈 더라면

875
01:08:55,170 --> 01:08:58,170
이 목록에 덧붙이 때, 상당히 간단합니다.

876
01:08:58,170 --> 01:09:02,960
>> 당신은 새 노드를 일부 동적 메모리 할당을 포함한다.

877
01:09:02,960 --> 01:09:09,830
그래서 여기에 우리가 malloc을 사용하여 노드 구조체를 만들고 있어요.

878
01:09:09,830 --> 01:09:14,710
malloc 그래서 그 이후에 우리 메모리를 따로 설정합니다 때문에 우리는 사용

879
01:09:14,710 --> 01:09:20,350
우리가이 원하지 않기 때문에 - 우리는이 기억이 오랫동안 유지하고 싶습니다.

880
01:09:20,350 --> 01:09:25,350
그리고 우리는 우리가 할당하는 메모리 공간에 대한 포인터를 얻을.

881
01:09:25,350 --> 01:09:29,260
우리는 노드의 크기를 사용, 우리는 필드를 합계가 1이되지 않습니다.

882
01:09:29,260 --> 01:09:31,899
우리는 수동으로 바이트 수를 생성하지 않습니다

883
01:09:31,899 --> 01:09:39,750
대신에 우리는 우리가 바이트의 해당 번호를 알아내는 걸 알아요 있도록 sizeof 사용합니다.

884
01:09:39,750 --> 01:09:43,660
우리는 우리의 malloc 호출이 성공하는지 테스트해야합니다.

885
01:09:43,660 --> 01:09:47,939
이렇게하면 일반적으로하고 싶은 일입니다.

886
01:09:47,939 --> 01:09:52,590
현대적인 기계에서 메모리가 부족하면 쉽게 일이 아닙니다

887
01:09:52,590 --> 01:09:56,610
당신은 물건 톤을 할당하고 큰 목록을하지 않는,

888
01:09:56,610 --> 01:10:02,220
하지만 아이폰이나 안드로이드 같은 말에 물건을 구축하는 경우,

889
01:10:02,220 --> 01:10:05,230
당신은 강렬한 무언가를하고있는 경우 특히 당신은 제한된 메모리 자원을 가지고 있습니다.

890
01:10:05,230 --> 01:10:08,300
그래서 연습에 들어가 두는 건 좋은 일입니다.

891
01:10:08,300 --> 01:10:10,510
>> 여기 몇 다른 기능을 사용납니다

892
01:10:10,510 --> 01:10:12,880
당신은 새로운 종류의가 있다고 보았 으니까.

893
01:10:12,880 --> 01:10:15,870
따라서 fprintf 단지 printf처럼되어 있습니다

894
01:10:15,870 --> 01:10:21,320
첫 번째 인자를 제외하고 인쇄 할 수있는 스트림입니다.

895
01:10:21,320 --> 01:10:23,900
이 경우, 우리는 표준 오류 문자열로 인쇄 할

896
01:10:23,900 --> 01:10:29,410
이는 표준 outstream 다릅니다.

897
01:10:29,410 --> 01:10:31,620
기본적으로는 같은 장소에 나타납니다.

898
01:10:31,620 --> 01:10:34,600
또한 터미널 출력,하지만 당신은 할 수 -

899
01:10:34,600 --> 01:10:38,790
이러한 명령을 사용하면 약, 리디렉션 기술을 배웠습니다

900
01:10:38,790 --> 01:10:42,290
이런 문제 세트 4 토미의 동영상에 대해 배웠습니다, 당신이 직접 할 수 있습니다

901
01:10:42,290 --> 01:10:47,900
서로 다른 영역에, 다음 종료 프로그램, 여기 종료합니다.

902
01:10:47,900 --> 01:10:50,440
그것은 메인에서 돌아처럼 본질적입니다

903
01:10:50,440 --> 01:10:53,600
여기에 반환 아무 짓도 안하기 때문에 우리는 출구를 사용하는 경우를 제외하고.

904
01:10:53,600 --> 01:10:57,140
우리는 메인에없는거야, 자, 재 우리가 원하는 것처럼 프로그램을 종료하지 않습니다.

905
01:10:57,140 --> 01:11:03,020
그래서 우리는 출구 기능을 사용하고 그것을 오류 코드를 제공합니다.

906
01:11:03,020 --> 01:11:11,890
그럼 여기서 우리는 전이어야 할 새 노드의 값 필드의 전 분야를 설정하고 우리는 그걸 송금.

907
01:11:11,890 --> 01:11:15,530
우리는 먼저 가리 키도록 새 노드의 다음 포인터를 설정

908
01:11:15,530 --> 01:11:20,460
그리고 처음에 이제 새 노드를 가리 킵니다.

909
01:11:20,460 --> 01:11:25,120
코드의이 첫번째 라인은, 우리가 새 노드를 구축하고 있습니다.

910
01:11:25,120 --> 01:11:27,280
이 함수의 마지막 두 줄하지만 최초로 없습니다.

911
01:11:27,280 --> 01:11:30,290
당신은 실제로 도우미 함수로, 함수로 당겨 수 있습니다.

912
01:11:30,290 --> 01:11:32,560
자주하는 일입니다 사실, 난 함수로 뽑아

913
01:11:32,560 --> 01:11:36,040
나는 빌드 노드 같은 전화

914
01:11:36,040 --> 01:11:40,410
그리고 그 앞에 함수가 아주 작은 유지, 그것은 불과 3 선 다음입니다.

915
01:11:40,410 --> 01:11:48,710
내 빌드 노드 함수를 사용하여 전화를 걸하고 최대 I 와이어 모든.

916
01:11:48,710 --> 01:11:51,970
>> 나는 당신에게 보여주고 싶은 마지막으로 한가지,

917
01:11:51,970 --> 01:11:54,030
그리고 당신이 직접 추가 한 모든 작업을 수행 알려드립니다

918
01:11:54,030 --> 01:11:57,500
목록을 통해 반복하는 방법은 다음과 같습니다.

919
01:11:57,500 --> 01:12:00,780
목록을 통해 반복 이동하기 위해 다른 방법의 무리가 있습니다.

920
01:12:00,780 --> 01:12:03,140
이 경우, 우리는 목록의 길이를 찾을거야.

921
01:12:03,140 --> 01:12:06,570
그래서 우리는 길이 = 0로 시작합니다.

922
01:12:06,570 --> 01:12:11,580
이 문자열을 나 strlen를 작성과 매우 유사합니다.

923
01:12:11,580 --> 01:12:17,780
이것이 내가 여기에 루프이 당신을 보여 드리고자합니다.

924
01:12:17,780 --> 01:12:23,530
그것은 약간 펑키 보이는, 그것은 일반적인 아닙니다 INT I = 0, 나는 <무엇이든, 내가 + +.

925
01:12:23,530 --> 01:12:34,920
대신에이 목록의 시작 부분으로 우리 변수 n을 초기화있어.

926
01:12:34,920 --> 01:12:40,620
우리 반복자 변수가 null이되지 않습니다 동안 그리고, 우리는 계속.

927
01:12:40,620 --> 01:12:46,340
관례 상, 목록의 끝은 null 될 것 때문입니다.

928
01:12:46,340 --> 01:12:48,770
그리고, 오히려 + +을하고보다 증가

929
01:12:48,770 --> 01:12:57,010
+의 연결리스트로 이에 상응 + N = N-> 옆에 위치해 있습니다.

930
01:12:57,010 --> 01:13:00,410
>> 우리가 시간이 있기 때문에 당신이 여기 메워 알려드립니다.

931
01:13:00,410 --> 01:13:09,300
귀하의 spellr의 psets에서 작업하지만 기억해야합니다.

932
01:13:09,300 --> 01:13:11,650
링크 된 목록, 당​​신은 해시 테이블을 구현하는 경우,

933
01:13:11,650 --> 01:13:14,010
확실히 매우 유용합니다.

934
01:13:14,010 --> 01:13:21,780
그리고 일을 통해 반복이 관용구를 갖는 것은 희망, 더 쉽게 생활을 할 것입니다.

935
01:13:21,780 --> 01:13:25,910
질문 빨리?

936
01:13:25,910 --> 01:13:28,920
[샘] 당신은 완료 sll 및 SC를 보낼 수 있습니까?

937
01:13:28,920 --> 01:13:38,360
[Hardison] 그래. 나는 완료 슬라이드와 완료 sll 스택과 queue.cs을 보내드립니다.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]