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 נתוני מחסנית תוך שימוש בסוג זה של struct.

26
00:01:46,730 --> 00:01:51,070
>> אז מה יש לנו כאן, זה דומה למה שהוצג בהרצאה,

27
00:01:51,070 --> 00:01:58,120
למעט בהרצאה הצגנו את זה עם ints לעומת * של char.

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
יש לנו מערך של char * 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
בצד השמאל, שזרקתי את מה שstruct המחסנית היה נראה כמו בזיכרון

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
שיהיה הקוד שלי, הוא פשוט להכריז struct, struct נערם בשם זה.

68
00:04:55,790 --> 00:05:01,270
זה מה שאנחנו מקבלים. זה מקובע את טביעת רגל זה בזיכרון.

69
00:05:01,270 --> 00:05:05,590
השאלה הראשונה כאן היא מה היא התוכן של struct מחסנית זה?

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
זה כמו סוג של הכרזה אני int ולא מאתחל אותו.

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 * char,

80
00:05:43,450 --> 00:05:49,670
להיות קצת ערך מובן, כנראה ריק.

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
אז אם אנחנו מסתכלים על ההבדל בין שתי שקופיות, כאן היה 0, הנה לפני הדחיפה.

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
[Basil] כי זה שכח שיש משהו במייתרים [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
זו מחסנית שיכולה להכיל לכל היותר 4 char * 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
מה שאנחנו רוצים לעשות הוא פשוט לחזור שווא.

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
זה הולך להחזר אמיתי אם המחרוזת נדחפה בהצלחה

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
[סם] אם גודל שווה יכולת אז לחזור שווא?

168
00:12:20,630 --> 00:12:23,320
[Hardison] בינגו. עבודה יפה.

169
00:12:23,320 --> 00:12:26,310
אם הגודל הוא היכולת, אנחנו הולכים לחזור שווא.

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
מהו "ראש הערימה," בהתחלה?

173
00:12:41,670 --> 00:12:43,650
[דניאל] גודל 0? >> גודל 0.

174
00:12:43,650 --> 00:12:49,990
מהו ראש הערימה לאחר יש דבר אחד במחסנית? מסים, אתה יודע?

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
ואנחנו פשוט הולכים לאחסון * char לשם.

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
[סטודנטים] תשואה אמיתית. >> חזרה אמיתי.

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
אני כבר מאותחל מכשיר לכאן, ובמכשיר,

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
כן, סם? >> יש לי שאלה למה אתה אומר סוגריים של s.string של גודל = str?

203
00:15:34,730 --> 00:15:42,910
מהו רחוב? האם זה מוגדר איפשהו לפני, או - הו, ברחוב * char?

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
אנחנו לקחנו כמובן מאליו שזה היה struct מחסנית זו.

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
שעשינו המחסנית שלנו struct גלובלי משתנית

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 unzip?

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
ולך לרשום את כל מה שיש פה, אתה רואה שיש לך שלושה קבצים. ג שונים.

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
אתה יכול לראות שיש לנו struct זה מוגדר עבורנו,

232
00:17:47,330 --> 00:17:51,330
struct המדויק שרק דברו עליו בשקופיות.

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
>> מה הוא פופ אמור לחזור? האלמנט מהחלק העליון של הערימה.

262
00:19:55,250 --> 00:20:01,260
זה אמור לקבל את האלמנט של ראש הערימה

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, ולאחר מכן ל1.

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
[סם] למה זה לא צריך להיות s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] 1 פלוס? >> כן. >> תפס את זה.

326
00:24:58,430 --> 00:25:00,980
[סם] חשב שבגלל שאתה לוקח את 1,

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
הוא שסיומת זו - הם קוראים לזה postfix משום - מגיע לאחר 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
אז אם יש לך מערך של מספרים, 1 עד 10,

393
00:30:28,250 --> 00:30:31,630
ואז אתה רוצה להרחיב את זה לכל המספרים 1 עד 100,

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
struct שהענקנו לך הוא באמת דומה לstruct שנתנו לך לערימה.

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
ואילו עם המחסנית, שהיינו יחיד שעוסק בראש הערימה.

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
ולכן אנחנו לא צריכים ששדה נוסף בתוך struct שלנו.

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
הדבר הראשון שקורה כאן הוא שאנחנו Enqueue המחרוזת "היי".

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
אנו Enqueue "שלום", היא מקבלת לשים על.

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
זה לא * int או * או משהו כזה char.

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, ועכשיו, אם אנחנו Enqueue שוב,

488
00:37:46,520 --> 00:37:51,300
איפה אנחנו Enqueue?

489
00:37:51,300 --> 00:37:55,000
היכן האלמנט הבא ילך בתורנו?

490
00:37:55,000 --> 00:37:57,980
אומר שאנחנו רוצים Enqueue המחרוזת "CS".

491
00:37:57,980 --> 00:38:02,240
שלמדד זה הולך? [סטודנטים] מייתרים [2]. >> שתיים.

492
00:38:02,240 --> 00:38:04,980
למה 2 ולא 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
כאשר אנו Enqueue האלמנט הבא, אנחנו נכניס את זה בגודל.

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
מערך של char * 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
ההתנהגות ההולמת, אם היינו לנסות ו1 dequeue משהו

535
00:41:29,310 --> 00:41:34,420
כמו "שלום", שהיה קופץ משלום.

536
00:41:34,420 --> 00:41:38,460
עכשיו התור שלנו מתחיל בעמוד 2 והוא בגודל 1.

537
00:41:38,460 --> 00:41:42,240
ועכשיו, אם אנסה וEnqueue משהו שוב, להגיד 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
>> ומתברר שזה בעצם לא כל כך קשה לעשות עם מפעיל mod.

546
00:42:15,470 --> 00:42:20,040
אז בדיוק כמו שעשינו עם קיסר וחומר האנוסים,

547
00:42:20,040 --> 00:42:25,190
באמצעות mod, אנחנו יכולים לקבל דברים כדי לעטוף ולהמשיך

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
כאשר אנו Enqueue משהו, שום דבר לא קרה לראש.

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
כאשר אנו Enqueue משהו, שום דבר לא קורה בראש.

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 אלמנטים או 10,000.

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
למעט בתור, יש לנו שדה struct נוסף בפה.

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
כי מה שהכרזנו כאן הוא מערך של char * 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
עם זאת, מה יש לנו כאן הוא מערך של char * 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
לאחר ביצוע 2 enqueues, הגודל הוא 2.

607
00:47:02,720 --> 00:47:07,110
לאחר ביצוע dequeue הגודל הוא עכשיו 1.

608
00:47:07,110 --> 00:47:09,330
לאחר ביצוע Enqueue אחר הגודל הוא חזרה עד 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
ואנחנו הולכים לעזוב את פונקצית Enqueue בשבילכם ליישם במקום.

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, אנחנו יכולים לחזור ריקים.

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
יש לנו גם לכלול mod זה על ידי היכולת.

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
אנו mod על ידי היכולת, כי יש לעטוף בחזרה סביב 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
>> [סם] מדוע זה 1 בראש התור? איפה זה הולך?

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
אנחנו נוציא את דמות * 1, אנחנו נוציא את האלמנט שיושב בראש המדד

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
[סם] כל 1 פשוט חוזר q.strings [q.head]? >> כן.

659
00:51:18,270 --> 00:51:23,830
>> בגלל שאנחנו עושים זה משתנה מq.head עם פונקצית mod,

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
יש מפעיל mod שם הוא לא משהו שאנחנו יכולים לעשות

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
יש לנו struct לתור המוגדר בדיוק כפי שראינו בשקופיות.

679
00:52:54,690 --> 00:52:59,870
>> יש לנו תפקיד Enqueue שהוא בשבילך לעשות.

680
00:52:59,870 --> 00:53:04,340
ויש לנו את פונקצית dequeue כאן.

681
00:53:04,340 --> 00:53:06,870
פונקצית dequeue בקובץ שאינו מיושמת

682
00:53:06,870 --> 00:53:13,230
אבל אני אשים אותו בחזרה על PowerPoint, כך שתוכל להקליד אותו ב, אם תרצה.

683
00:53:13,230 --> 00:53:16,690
אז במשך 5 הדקות הבאות או כך, אתם עובדים על Enqueue

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
גודל. לכן, כאשר אתם Enqueue, הראש נשאר ללא שינוי, בגודל משתנה.

687
00:53:38,920 --> 00:53:46,920
אבל זה ייקח קצת - יהיה לך לשחק עם שmod

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
אתה צריך מוד הגודל אי פעם? [דניאל] מס >> אתה לא צריך מוד הגודל, נכון.

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
איפה אתה צריך מוד כשאתה עושה Enqueue?

697
00:54:38,680 --> 00:54:41,060
[סטודנטים] רק לראש. >> רק לראש, בדיוק.

698
00:54:41,060 --> 00:54:44,620
ולמה אתה צריך מוד בכלל בEnqueue?

699
00:54:44,620 --> 00:54:48,830
כאשר הוא מצב שבו היית צריך מוד?

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
אם אני רוצה משהו Enqueue עכשיו,

706
00:55:24,370 --> 00:55:31,110
אנחנו רוצים משהו בEnqueue המדד 0.

707
00:55:31,110 --> 00:55:35,450
אז אם אתה מסתכל בו 50 הולך, ואני קורא Enqueue 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
למה זה לעשות משהו עם הראש בEnqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] אה, אז אתה לא שינוי בראש, מצטער.

713
00:55:55,770 --> 00:56:02,310
אבל אתה צריך להשתמש באופרטור mod כשאתה ניגש

714
00:56:02,310 --> 00:56:04,250
האלמנט שברצונך Enqueue כאשר אתה ניגש

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
בגלל withe המחסנית, האלמנט הבא במחסנית שלך תמיד היה

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
אנחנו תמיד יכולים plunk באלמנט החדש שלנו נכון בגודל אינדקס.

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
>> אז בואו מהר מאוד להסתכל על מה פונקצית Enqueue נראית.

742
00:58:21,440 --> 00:58:26,530
מה היה הדבר הראשון שאנשים ניסו לעשות בקו Enqueue? לתור הזה?

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
אני צריך לשים את הפלטה שלי במקום הנכון - בתמורת שווא.

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
בום. ולאחר מכן, שכן קוד המתנע רק חזר שווא כברירת מחדל,

761
01:00:13,830 --> 01:00:27,460
אנחנו רוצים לשנות את זה לאמיתי אם כל עובר והכל ילכו כשורה.

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
אז Enqueue הוא 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
ובמקום לנפץ את כל צומת יחד ואחסונם בסמיכות

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
מעל הכל אחסון סמיכות פשוט תקוע אחד ליד שני?

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
בעוד שעם רשימה, כל מה שאתה צריך לעשות הוא לזרוק אותו על צומת חדשה,

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
[סטודנטים] הו, זה מצביע קדם? >> כן.

820
01:04:54,170 --> 01:05:04,070
כך שלאחר מכן ניתן להגדיל ptr עוצמה לפני שבחינם אז מה predptr הוא.

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, או שהיה מדד 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
זה הולך להצביע על משהו שהוא struct צומת בפועל.

841
01:06:23,550 --> 01:06:28,480
[סם] מצביע נקרא צומת? >> זה - אין. זה הוא מצביע למשהו מסוג הצומת.

842
01:06:28,480 --> 01:06:32,540
זה מצביע ל struct צומת. >> אה, בסדר.

843
01:06:32,540 --> 01:06:36,870
תרשים מהשמאל, הקוד בצד ימין.

844
01:06:36,870 --> 01:06:42,190
אנו יכולים להגדיר אותו ריק, שהוא דרך טובה להתחיל.

845
01:06:42,190 --> 01:06:49,850
כשאתה תרשים זה, או שאתה כותב את זה כריק או שאתה בקו את זה ככה.

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
אתה הולך וליצור struct הצומת

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
אופס. מצטער, עכשיו אנחנו מגיעים להוספה. אז הנה אנחנו prepended (7), עכשיו אנחנו הקדם זיהוי (3).

861
01:07:57,880 --> 01:08:02,600
אם אנחנו prepended משהו אחר על רשימה זו, אם אנחנו prepended (4),

862
01:08:02,600 --> 01:08:06,540
אז יהיה לנו 4 ו 7 ואז 3 ואז.

863
01:08:06,540 --> 01:08:14,220
אז נוכל להכניס ולהוציא 4, 3 הסירו, הסר 7.

864
01:08:14,220 --> 01:08:16,500
לעתים קרובות הדרך אינטואיטיבית יותר לחשוב על זה עם הוספה.

865
01:08:16,500 --> 01:08:20,310
אז אני כבר נתחתי את מה שהיה נראה כמו צירוף עם כאן.

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
אז הנה אנחנו עושים struct צומת באמצעות 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
אנו משתמשים בגודל של צומת, אנחנו לא מסכמים את השדות.

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
אז הנה לנו להגדיר שדה הערך של צומת החדש, התחום שאני להיות שווה ל i, ואז אנחנו נמלכד אותה.

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
אני עושה קריאה לפונקצית צומת המבנה שלי, ואז כל מה שעל חוט.

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 = 0, i <מה, אני + +.

925
01:12:23,530 --> 01:12:34,920
במקום שזה אתחול n המשתנה שלנו להיות ההתחלה של הרשימה.

926
01:12:34,920 --> 01:12:40,620
ואז בזמן משתנה איטרטור שלנו הוא לא ריק, שנמשיך.

927
01:12:40,620 --> 01:12:46,340
הסיבה לכך היא, למוסכמות, לסוף הרשימה שלנו יהיה בטל.

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
אבל לשמור את זה בחשבון כאשר אתם עובדים על psets spellr.

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]