1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
דאג LLOYD: בסדר,
זאת על ידי נקודה שאתה זה

3
00:00:05,990 --> 00:00:09,020
כנראה די מוכר
עם מערכים ורשימות מקושרות

4
00:00:09,020 --> 00:00:10,950
אשר הוא שני העיקרי
מבני נתונים יש לנו

5
00:00:10,950 --> 00:00:16,810
דיברתי על לשמירת סטים של
נתונים של סוגים דומים הנתונים מאורגנים.

6
00:00:16,810 --> 00:00:19,080
>> עכשיו אנחנו הולכים לדבר
על כמה וריאציות

7
00:00:19,080 --> 00:00:20,330
על מערכים ורשימות מקושרות.

8
00:00:20,330 --> 00:00:22,362
בסרטון הזה אנחנו הולכים
לדבר על ערימות.

9
00:00:22,362 --> 00:00:25,320
במיוחד שאנחנו הולכים לדבר
על מבנה נתונים הנקרא ערימה.

10
00:00:25,320 --> 00:00:28,510
כזכור מדיונים קודמים
על מצביעים וזיכרון,

11
00:00:28,510 --> 00:00:32,060
שהערימה היא גם
שם לקטע של זיכרון

12
00:00:32,060 --> 00:00:34,980
שבו הכריז באופן סטטי
זיכרון memory-- ש

13
00:00:34,980 --> 00:00:38,730
שם, משתנים שאתה שם, et
מסגרות וכו ופונקציה שאנחנו גם

14
00:00:38,730 --> 00:00:41,000
מסגרות ערימת שיחה קיימות.

15
00:00:41,000 --> 00:00:45,421
אז זה הוא מבנה נתונים מחסנית
לא קטע ערימה של זיכרון.

16
00:00:45,421 --> 00:00:45,920
אוקיי.

17
00:00:45,920 --> 00:00:46,890
>> אבל מה היא ערימה?

18
00:00:46,890 --> 00:00:49,220
אז זה פחות או יותר רק
סוג מיוחד של מבנה

19
00:00:49,220 --> 00:00:51,190
השומר על הנתונים באופן מסודר.

20
00:00:51,190 --> 00:00:53,760
ויש שתי מאוד
דרכים נפוצות ליישום

21
00:00:53,760 --> 00:00:57,380
ערימות באמצעות שני מבני נתונים
שאנחנו כבר מכירים,

22
00:00:57,380 --> 00:01:00,340
מערכים ורשימות מקושרות.

23
00:01:00,340 --> 00:01:04,430
מה הופך מיוחד ערימה היא
אופן שבו אנחנו שמים מידע

24
00:01:04,430 --> 00:01:08,200
לערימה, והדרך בה אנו
להסיר את המידע מהערימה.

25
00:01:08,200 --> 00:01:11,600
בפרט עם ערימות
הכלל הוא רק ביותר

26
00:01:11,600 --> 00:01:15,830
לאחרונה אלמנט נוסף ניתן להסיר.

27
00:01:15,830 --> 00:01:17,660
>> אז תחשוב על זה כאילו זה ערימה.

28
00:01:17,660 --> 00:01:21,170
אנחנו גדיש מידע
על גבי עצמו,

29
00:01:21,170 --> 00:01:24,271
והדבר היחיד בראש
הערימה ניתן להסיר.

30
00:01:24,271 --> 00:01:27,020
אנחנו לא יכולים להסיר את הדבר מתחת
כי היית כל דבר אחר

31
00:01:27,020 --> 00:01:28,020
תתמוטט ותיפול.

32
00:01:28,020 --> 00:01:32,580
אז אנחנו באמת בונים ערימה ש
אז אנחנו צריכים להסיר חתיכה אחרי חתיכה.

33
00:01:32,580 --> 00:01:36,590
בגלל זה אנחנו בדרך כלל מתייחסים
לערימה כמבנה LIFO,

34
00:01:36,590 --> 00:01:38,940
תימשך ב, יוצא ראשון.

35
00:01:38,940 --> 00:01:42,290
LIFO, יימשך ב, ראשון החוצה.

36
00:01:42,290 --> 00:01:45,635
>> אז בגלל מגבלה זו על
איך מידע ניתן להוסיף ל

37
00:01:45,635 --> 00:01:49,080
והוסר ממחסנית, יש באמת
רק שני דברים שאנחנו יכולים לעשות עם ערימה.

38
00:01:49,080 --> 00:01:52,010
אנחנו יכולים לדחוף, המהווה את
טווח אנו משתמשים להוספה

39
00:01:52,010 --> 00:01:55,130
אלמנט חדש לראש
מחסנית, או אם המחסנית אינה קיימת

40
00:01:55,130 --> 00:01:58,550
ואנחנו יוצרים אותו מאפס,
יצירת המחסנית במקום הראשון

41
00:01:58,550 --> 00:02:00,110
יהיה דחיפה.

42
00:02:00,110 --> 00:02:04,990
ולאחר מכן פופ, זה הסוג של CS
טווח אנו משתמשים כדי להסיר את רוב לאחרונה

43
00:02:04,990 --> 00:02:08,330
הוסיף אלמנט מהחלק העליון של המחסנית.

44
00:02:08,330 --> 00:02:11,130
>> אז אנחנו הולכים להסתכל על שני
יישומים, המבוסס הן המערך

45
00:02:11,130 --> 00:02:13,120
ורשימה מקושרת מבוסס.

46
00:02:13,120 --> 00:02:14,870
ואנחנו הולכים ל
תתחיל עם המערך מבוסס.

47
00:02:14,870 --> 00:02:19,990
אז הנה הרעיון הבסיסי של מה ש
מבנה נתונים מחסנית המערך מבוסס

48
00:02:19,990 --> 00:02:21,140
ייראה.

49
00:02:21,140 --> 00:02:23,740
יש לנו הגדרה מוקלד כאן.

50
00:02:23,740 --> 00:02:27,790
בתוך שיש לנו שני חברים
או שדות של המבנה.

51
00:02:27,790 --> 00:02:29,880
יש לנו מערך.

52
00:02:29,880 --> 00:02:32,400
ושוב אני משתמש
ערך סוג נתונים שרירותי.

53
00:02:32,400 --> 00:02:35,180
>> אז זה יכול להיות כל סוג נתונים,
char int או נתונים אחרים

54
00:02:35,180 --> 00:02:37,080
הקלד יצרת בעבר.

55
00:02:37,080 --> 00:02:39,861
אז יש לנו מערך של קיבולת גודל.

56
00:02:39,861 --> 00:02:44,010
היכולת להיות לירה מוגדרת קבועה,
אולי במקום אחר בקובץ שלנו.

57
00:02:44,010 --> 00:02:47,550
אז שם לב כבר עם זה בפרט
יישום אנחנו מדלג

58
00:02:47,550 --> 00:02:49,800
את עצמנו כמו היו בדרך כלל
במקרה של מערכים,

59
00:02:49,800 --> 00:02:53,170
שאנחנו לא יכולים לשנות את הגודל באופן דינמי,
שבו יש מספר מסוים

60
00:02:53,170 --> 00:02:55,450
של מקסימום אלמנטים ש
אנחנו יכולים לשים בערימה שלנו.

61
00:02:55,450 --> 00:02:57,930
במקרה זה זה אלמנטי קיבולת.

62
00:02:57,930 --> 00:03:00,310
>> אנחנו גם לעקוב אחר
ראש הערימה.

63
00:03:00,310 --> 00:03:04,350
מה אלמנט הוא ביותר
לאחרונה נוסף לערימה?

64
00:03:04,350 --> 00:03:07,470
וכך אנו לעקוב אחר ש
בראש משתנה בשם.

65
00:03:07,470 --> 00:03:11,692
וכל זה מקבל עטוף יחד
לסוג הנתונים חדש בשם ערימה.

66
00:03:11,692 --> 00:03:13,400
וברגע שאנחנו נוצרו
סוג נתונים חדש

67
00:03:13,400 --> 00:03:15,410
אנו יכולים להתייחס אליו כמו
כל סוג נתונים אחר.

68
00:03:15,410 --> 00:03:20,970
אנחנו יכולים להכריז על ערימה של, בדיוק כמו
אנחנו יכולים לעשות X int, או y char.

69
00:03:20,970 --> 00:03:22,990
וכאשר אנו אומרים מחסנית
ים, גם מה שקורה

70
00:03:22,990 --> 00:03:26,420
הוא שאנו מקבלים סט של
הזיכרון להפריש עבורנו.

71
00:03:26,420 --> 00:03:28,770
>> במקרה זה קיבולת
אני כבר החלטתי, ככל הנראה,

72
00:03:28,770 --> 00:03:33,470
הוא 10 כי יש לי
משתנה אחד של ערימת הסוג

73
00:03:33,470 --> 00:03:35,320
המכיל שני שדות זוכרים.

74
00:03:35,320 --> 00:03:38,330
מערך, במקרה זה הולך
להיות מערך של מספרים שלמים

75
00:03:38,330 --> 00:03:40,440
כמו במקרה ברוב דוגמאות שלי.

76
00:03:40,440 --> 00:03:43,996
ומשתנה שלם אחרת
מסוגל לאחסן העליון,

77
00:03:43,996 --> 00:03:45,870
הוסיף לאחרונה
אלמנט לערימה.

78
00:03:45,870 --> 00:03:50,290
אז אחת ערימה אחת של מה שאנחנו
רק הגדרה נראית כך.

79
00:03:50,290 --> 00:03:53,190
זה תיבה המכילה
מערך של 10 מה

80
00:03:53,190 --> 00:03:57,280
יהיו מספרים שלמים במקרה זה ו
משתנה שלם אחרת יש בירוק

81
00:03:57,280 --> 00:04:00,010
כדי לציין את ראש הערימה.

82
00:04:00,010 --> 00:04:02,600
>> כדי להגדיר את החלק העליון של
ערימה אנחנו רק אומרים s.top.

83
00:04:02,600 --> 00:04:04,890
ככה אנחנו לגשת
תחום זוכר מבנה.

84
00:04:04,890 --> 00:04:10,460
s.top שווה 0 ביעילות
עושה את זה לערימה שלנו.

85
00:04:10,460 --> 00:04:12,960
אז שוב יש לנו שתי פעולות
שאנחנו יכולים לבצע כעת.

86
00:04:12,960 --> 00:04:14,270
אנחנו יכולים לדחוף ואנחנו יכולים לקפוץ.

87
00:04:14,270 --> 00:04:15,635
בואו נתחיל עם דחיפה.

88
00:04:15,635 --> 00:04:18,260
שוב, דוחף מוסיף חדש
אלמנט לראש הערימה.

89
00:04:18,260 --> 00:04:21,460
>> אז מה לעשות שאנחנו צריכים לעשות ב
מערך זה מבוסס יישום?

90
00:04:21,460 --> 00:04:23,210
ובכן בכללי
פונקצית דחיפה הולכת

91
00:04:23,210 --> 00:04:26,160
צריך לקבל
מצביע לערימה.

92
00:04:26,160 --> 00:04:28,610
עכשיו קח שני ותחשוב על זה.

93
00:04:28,610 --> 00:04:32,840
למה שנרצה לקבל
מצביע למחסנית?

94
00:04:32,840 --> 00:04:36,830
כזכור מסרטונים קודמים ב
היקף משתנה ומצביעים,

95
00:04:36,830 --> 00:04:42,350
מה היה קורה אם אנחנו פשוט שלחו
ערימה, זה לא כבפרמטר?

96
00:04:42,350 --> 00:04:45,770
מה היית למעשה עבר שם?

97
00:04:45,770 --> 00:04:49,430
זכור שאנו יוצרים עותק
כאשר אנו עוברים אותו לפונקציה

98
00:04:49,430 --> 00:04:51,160
אלא אם כן אנו משתמשים במצביעים.

99
00:04:51,160 --> 00:04:55,380
וכך בפונקציה זו לדחוף צרכי
לקבל מצביע למחסנית

100
00:04:55,380 --> 00:04:59,160
כך שאנחנו בעצם משנים
הערימה בכוונתנו לשנות.

101
00:04:59,160 --> 00:05:03,060
>> דחיפת הדבר אחרת כנראה רוצה
קיבלתי הוא אלמנט נתונים של ערך סוג.

102
00:05:03,060 --> 00:05:06,970
במקרה זה, שוב, מספר שלם ש
אנחנו הולכים להוסיף לחלק העליון של מחסנית.

103
00:05:06,970 --> 00:05:08,680
אז יש לנו שני הפרמטרים שלנו.

104
00:05:08,680 --> 00:05:11,310
מה אנחנו הולכים
עכשיו לעשות בתוך הדחיפה?

105
00:05:11,310 --> 00:05:14,860
ובכן, פשוט, אנחנו פשוט הולכים להוסיף
אלמנט שלראש הערימה

106
00:05:14,860 --> 00:05:22,860
ולאחר מכן לשנות את שם ראש
הערימה היא, שזה נקודה ערך עליון.

107
00:05:22,860 --> 00:05:25,639
אז זה מה שפונקציה
הכרזה לדחיפה

108
00:05:25,639 --> 00:05:27,680
עשוי להיראות כמו ב
מבוסס מערך יישום.

109
00:05:27,680 --> 00:05:30,967
>> שוב זה לא שלטון חזק ומהר
שאתה יכול לשנות את זה ויש לי

110
00:05:30,967 --> 00:05:32,050
זה משתנה בדרכים שונות.

111
00:05:32,050 --> 00:05:33,840
אולי זה הוכרז ברחבי העולם.

112
00:05:33,840 --> 00:05:36,180
ואז אתה אפילו לא צריך
להעביר את זה הוא כפרמטר.

113
00:05:36,180 --> 00:05:39,125
זה שוב רק
מקרה כללי לדחיפה.

114
00:05:39,125 --> 00:05:41,000
ויש שונים
דרכים ליישומו.

115
00:05:41,000 --> 00:05:42,810
אבל במקרה הזה שלנו
דחיפה הולכת לקחת

116
00:05:42,810 --> 00:05:48,540
שני טיעונים, מצביע למחסנית ו
אלמנט נתונים של ערך סוג, מספר שלם

117
00:05:48,540 --> 00:05:49,840
במקרה הזה.

118
00:05:49,840 --> 00:05:52,100
>> אז אנחנו הכריזו ים, אנחנו
אמר s.top שווה 0.

119
00:05:52,100 --> 00:05:55,969
עכשיו בואו לדחוף
מספר 28 על הערימה.

120
00:05:55,969 --> 00:05:57,010
ובכן מה זה אומר?

121
00:05:57,010 --> 00:05:59,600
ובכן כרגע
ראש הערימה הוא 0.

122
00:05:59,600 --> 00:06:01,350
ואז מה בעצם
הולך לקרות הוא

123
00:06:01,350 --> 00:06:05,820
אנחנו הולכים להישאר במספר
28 למיקום מערך 0.

124
00:06:05,820 --> 00:06:09,540
די פשוט, נכון, ש
היה העליון, ועכשיו אנחנו טובים ללכת.

125
00:06:09,540 --> 00:06:12,910
ואז אנחנו צריכים לשנות את מה ש
ראש הערימה יהיה.

126
00:06:12,910 --> 00:06:15,130
כך שבפעם הבאה
אנחנו דוחפים אלמנט ב,

127
00:06:15,130 --> 00:06:18,017
אנחנו הולכים לאחסן אותו ב
מיקום מערך, כנראה לא 0.

128
00:06:18,017 --> 00:06:20,100
אנחנו לא רוצים להחליף
מה שאנחנו פשוט לשים שם.

129
00:06:20,100 --> 00:06:23,510
וכך אנחנו פשוט להזיז את הראש ל1.

130
00:06:23,510 --> 00:06:24,890
זה כנראה הגיוני.

131
00:06:24,890 --> 00:06:28,940
>> עכשיו, אם אנחנו רוצים לשים את אלמנט נוסף
על הערימה, אומר שאנחנו רוצים לדחוף 33,

132
00:06:28,940 --> 00:06:33,190
גם עכשיו אנחנו רק הולכים לקחת 33
ולשים אותו במספר מיקום מערך

133
00:06:33,190 --> 00:06:37,580
1, ולאחר מכן לשנות את חלקו העליון שלנו
מחסנית להיות מספר מיקום מערך דו.

134
00:06:37,580 --> 00:06:40,650
אז אם בפעם הבאה שאנחנו רוצים
לדחוף אלמנט על הערימה,

135
00:06:40,650 --> 00:06:43,087
זה תהיה לשים במערך מיקום 2.

136
00:06:43,087 --> 00:06:44,420
ובואו לעשות את זה עוד פעם אחת.

137
00:06:44,420 --> 00:06:45,753
אנחנו לדחוף 19 מעל הערימות.

138
00:06:45,753 --> 00:06:48,940
אנחנו נשים 19 במערך מיקום 2
ולשנות את החלק העליון של המחסנית שלנו

139
00:06:48,940 --> 00:06:51,220
להיות מערך מיקום 3
כך שאם אנו הפעם הבאה

140
00:06:51,220 --> 00:06:54,780
צריך לעשות שכיבות אנחנו טובים ללכת.

141
00:06:54,780 --> 00:06:56,980
>> אוקיי, אז שדוחף בקליפת אגוז.

142
00:06:56,980 --> 00:06:57,830
מה לגבי פקיעה?

143
00:06:57,830 --> 00:07:00,240
אז נפץ מהסוג
עמית לדוחף.

144
00:07:00,240 --> 00:07:02,720
זה איך אנחנו להסיר נתונים מהערימה.

145
00:07:02,720 --> 00:07:04,610
ובצרכי פופ הכלליים
לעשות את הדברים הבאים.

146
00:07:04,610 --> 00:07:07,600
הוא צריך לקבל את מצביע ל
מחסנית, שוב במקרה הכללי.

147
00:07:07,600 --> 00:07:10,480
במקרים מסוימים אחרים עלולים
הכריז הערימה גלובלית,

148
00:07:10,480 --> 00:07:13,910
בכל מקרה אתה לא צריך לעבור את זה
בכי יש לו כבר את הגישה אליו

149
00:07:13,910 --> 00:07:15,541
כמשתנה גלובלית.

150
00:07:15,541 --> 00:07:17,040
אבל אז מה עוד אנחנו צריכים לעשות?

151
00:07:17,040 --> 00:07:21,000
ובכן אנחנו הגדלה
ראש הערימה בדחיפה,

152
00:07:21,000 --> 00:07:24,050
אז אנחנו כנראה הולכים רוצים
להפחתת ראש הערימה

153
00:07:24,050 --> 00:07:25,009
בפופ, נכון?

154
00:07:25,009 --> 00:07:26,800
ואז כמובן
אנחנו גם הולכים רוצים

155
00:07:26,800 --> 00:07:29,240
כדי להחזיר את הערך שאנו מסירים.

156
00:07:29,240 --> 00:07:32,125
אם אנחנו מוסיפים אלמנטים, אנחנו רוצים
לצאת אלמנטים בהמשך,

157
00:07:32,125 --> 00:07:34,000
אנחנו כנראה באמת
רוצה לאחסן אותם כדי ש

158
00:07:34,000 --> 00:07:36,490
לא רק למחוק אותם מ
מחסנית ולאחר מכן לעשות שום דבר איתם.

159
00:07:36,490 --> 00:07:38,500
בדרך כלל אם אנחנו
דוחף וצץ כאן

160
00:07:38,500 --> 00:07:41,250
אנחנו רוצים לאחסן את זה
מידע בצורה משמעותית

161
00:07:41,250 --> 00:07:43,250
ואז זה לא עושה
תחושה רק כדי למחוק אותו.

162
00:07:43,250 --> 00:07:46,380
אז פונקציה זו צריכה
כנראה להחזיר ערך לנו.

163
00:07:46,380 --> 00:07:51,040
>> אז זה מה שהצהרה לפופ
עשוי להיראות כאילו יש בפינה השמאלית העליונה.

164
00:07:51,040 --> 00:07:53,870
פונקציה זו מחזירה
נתונים של ערך סוג.

165
00:07:53,870 --> 00:07:56,320
שוב אנחנו כבר משתמשים
מספרים שלמים בכל.

166
00:07:56,320 --> 00:08:01,916
והיא מקבלת מצביע למחסנית כ
טענתה היחידה או פרמטר יחיד.

167
00:08:01,916 --> 00:08:03,040
אז מה הוא פופ הולך לעשות?

168
00:08:03,040 --> 00:08:07,990
נניח שאנחנו רוצים עכשיו
פופ אלמנט משל ים.

169
00:08:07,990 --> 00:08:14,000
אז זוכר שאמרתי שהערימות הן האחרונות
ב, ראשון החוצה, מבני נתונים LIFO.

170
00:08:14,000 --> 00:08:17,855
איזה אלמנט הולך
יוסר מהמחסנית?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
האם אתה מניח 19?

173
00:08:24,150 --> 00:08:25,290
בגלל אתה רוצה להיות צודק.

174
00:08:25,290 --> 00:08:28,836
19 היו האלמנט האחרון שנוספנו ל
מחסנית כאשר אנו דוחפים אלמנטים ב,

175
00:08:28,836 --> 00:08:31,210
וכך זה הולך הראשון
אלמנט שמקבל הוסר.

176
00:08:31,210 --> 00:08:34,780
זה כאילו שאמרנו 28, ו
אז אנחנו שמים 33 על גבי זה,

177
00:08:34,780 --> 00:08:36,659
ואנחנו שמים 19 על גבי זה.

178
00:08:36,659 --> 00:08:40,650
האלמנט היחיד שאנחנו יכולים לקחת אותו 19.

179
00:08:40,650 --> 00:08:45,019
>> עכשיו בתרשים כאן מה שעשיתי
נמחק סוג של 19 מהמערך.

180
00:08:45,019 --> 00:08:46,810
זה לא ממש
מה שאנחנו הולכים לעשות.

181
00:08:46,810 --> 00:08:48,934
אנחנו רק הולכים סוג
של להעמיד פנים שזה לא שם.

182
00:08:48,934 --> 00:08:51,441
הוא עדיין שם ב
שמיקום הזיכרון,

183
00:08:51,441 --> 00:08:54,190
אבל אנחנו פשוט הולכים להתעלם ממנו
על ידי שינוי החלק העליון של המחסנית שלנו

184
00:08:54,190 --> 00:08:56,080
מלהיות 3-2.

185
00:08:56,080 --> 00:08:58,720
אז אם היינו עכשיו לדחוף
אלמנט נוסף על הערימה,

186
00:08:58,720 --> 00:09:00,720
זה היה מעל 19 לכתוב.

187
00:09:00,720 --> 00:09:03,990
>> אבל בואו לא לעבור את הטרחה
של מחיקת 19 מהערימה.

188
00:09:03,990 --> 00:09:05,830
אנחנו רק יכולים להעמיד פנים שהוא לא שם.

189
00:09:05,830 --> 00:09:11,107
למטרות של המחסנית זה נעלם אם
נשנינו את הראש כדי להיות 2 במקום 3.

190
00:09:11,107 --> 00:09:12,690
בסדר, אז זה היה פחות או יותר אותו.

191
00:09:12,690 --> 00:09:15,080
זה כל מה שאנחנו צריכים לעשות
פופ אלמנט מ.

192
00:09:15,080 --> 00:09:16,090
בואו נעשה את זה שוב.

193
00:09:16,090 --> 00:09:18,610
אז אני כבר הדגיש אותו באדום כאן ל
מצביע אנחנו עושים שיחה אחרת.

194
00:09:18,610 --> 00:09:19,720
אנחנו הולכים לעשות את אותו הדבר.

195
00:09:19,720 --> 00:09:20,803
>> אז מה הולך לקרות?

196
00:09:20,803 --> 00:09:23,670
ובכן, אנחנו הולכים לאחסון
33 בx ואנחנו הולכים

197
00:09:23,670 --> 00:09:26,217
כדי לשנות את ראש הערימה עד 1.

198
00:09:26,217 --> 00:09:29,050
כך שאם היינו עכשיו לדחוף
אלמנט לתוך הערימה שאנחנו

199
00:09:29,050 --> 00:09:31,610
הולך לעשות עכשיו,
מה הולך לקרות

200
00:09:31,610 --> 00:09:36,367
הוא שאנחנו הולכים לדרוס
מספר מיקום מערך 1.

201
00:09:36,367 --> 00:09:38,950
אז כי 33 שסוג של שמאל
מאחורי שרק העמיד פנים

202
00:09:38,950 --> 00:09:44,390
הוא כבר לא שם, אנחנו פשוט הולכים
להרביץ בו ולשים 40 יש במקום.

203
00:09:44,390 --> 00:09:46,290
ואז כמובן,
מאז שעשינו דחיפה,

204
00:09:46,290 --> 00:09:48,780
אנחנו הולכים להגדיל
ראש הערימה 1-2

205
00:09:48,780 --> 00:09:50,950
כך שאם אנחנו עכשיו להוסיף
אלמנט נוסף אותו ימצא

206
00:09:50,950 --> 00:09:54,700
ללכת למספר מיקום מערך דו.

207
00:09:54,700 --> 00:09:57,590
>> עכשיו רשימות מקושרים אחרת
דרך ליישם ערימות.

208
00:09:57,590 --> 00:10:01,210
ואם הגדרה זו על
מסך כאן נראה לכם מוכר,

209
00:10:01,210 --> 00:10:04,260
זה בגלל שזה נראה כמעט
בדיוק אותו דבר, למעשה,

210
00:10:04,260 --> 00:10:07,790
זה פחות או יותר בדיוק
כמו רשימה מקושרת ביחידות,

211
00:10:07,790 --> 00:10:11,990
אם אתה זוכר מהדיון שלנו
ביחידים רשימות מקושרים בוידאו אחר.

212
00:10:11,990 --> 00:10:15,510
ההגבלה היחידה כאן
הוא לנו כמתכנתים,

213
00:10:15,510 --> 00:10:17,900
אסור לנו ל
להוסיף או למחוק באופן אקראי

214
00:10:17,900 --> 00:10:20,620
מהרשימה המקושרת ביחידים
שאנחנו יכולים לעשות בעבר.

215
00:10:20,620 --> 00:10:25,820
אנחנו יכולים רק עכשיו להוסיף ולמחוק מ
הקדמי או העליון של מקושר

216
00:10:25,820 --> 00:10:26,320
רשימה.

217
00:10:26,320 --> 00:10:28,028
זה באמת רק
הבדל למרות ש.

218
00:10:28,028 --> 00:10:29,700
זה אחרת רשימה מקושרת ביחידים.

219
00:10:29,700 --> 00:10:32,060
זה רק ההגבלה
החלפה על עצמנו

220
00:10:32,060 --> 00:10:35,770
כמתכנתים ש
משנה אותו לערימה.

221
00:10:35,770 --> 00:10:39,280
>> הכלל כאן הוא תמיד לשמור
מצביע לראש רשימה מקושרת.

222
00:10:39,280 --> 00:10:41,520
זה כמובן כלל
כלל חשוב ראשון.

223
00:10:41,520 --> 00:10:44,260
לרשימה מקושרת ביחידים בכל מקרה אתה
רק צריך מצביע לראש

224
00:10:44,260 --> 00:10:46,160
כדי שיהיה לי ש
שרשרת תוכל להפנות

225
00:10:46,160 --> 00:10:48,596
לכל אלמנט אחר
ברשימה המקושרת.

226
00:10:48,596 --> 00:10:50,470
אבל זה במיוחד
חשוב עם ערימה.

227
00:10:50,470 --> 00:10:52,386
וכך, בדרך כלל, אתה
הולך באמת רוצה

228
00:10:52,386 --> 00:10:54,090
מצביע זה להיות משתנה גלובלי.

229
00:10:54,090 --> 00:10:56,574
זה כנראה הולך ל
להיות אפילו יותר קל ככה.

230
00:10:56,574 --> 00:10:58,240
אז מה הם אנלוגים של דחיפה ופופ?

231
00:10:58,240 --> 00:10:58,740
תקין.

232
00:10:58,740 --> 00:11:01,812
אז דוחף שוב מוסיף
אלמנט חדש לערימה.

233
00:11:01,812 --> 00:11:03,770
ברשימה מקושרת ש
אומר שאנחנו הולכים להיות

234
00:11:03,770 --> 00:11:07,770
כדי ליצור צומת חדש שאנחנו
הולך להוסיף לרשימה המקושרת,

235
00:11:07,770 --> 00:11:10,500
ולאחר מכן בצע את הצעדים זהירים
שאנחנו כבר שתוארו קודם לכן

236
00:11:10,500 --> 00:11:16,050
ברשימות מקושרות ביחידות כדי להוסיף אותו ל
השרשרת בלי לשבור את השרשרת

237
00:11:16,050 --> 00:11:18,900
ולאבד או יִתוּם כל
אלמנטים של הרשימה המקושרת.

238
00:11:18,900 --> 00:11:21,820
וזה בעצם מה ש
בועה קטנה של טקסט יש מסכמת.

239
00:11:21,820 --> 00:11:23,740
ובואו נסתכל
על זה כתרשים.

240
00:11:23,740 --> 00:11:24,823
>> אז הנה הרשימה המקושרת שלנו.

241
00:11:24,823 --> 00:11:26,620
זה במקביל מכיל ארבעה יסודות.

242
00:11:26,620 --> 00:11:30,420
ועוד בצורה מושלמת הנה
מחסנית המכילה ארבעה מרכיבים.

243
00:11:30,420 --> 00:11:36,030
ונניח שעכשיו אנחנו רוצים
לדחוף פריט חדש על ערימה זו.

244
00:11:36,030 --> 00:11:39,792
ואנחנו רוצים לדחוף חדשים
פריט המידע שהערך הוא 12.

245
00:11:39,792 --> 00:11:41,000
ובכן מה שאנחנו הולכים לעשות?

246
00:11:41,000 --> 00:11:43,420
ובכן ראשון שאנחנו הולכים
חלל malloc, דינמי

247
00:11:43,420 --> 00:11:45,411
להקצות שטח לצומת חדשה.

248
00:11:45,411 --> 00:11:48,160
וכמובן מייד לאחר
אנחנו עושים שיחה לmalloc אנחנו תמיד

249
00:11:48,160 --> 00:11:52,989
הקפד לבדוק null,
כי אם יש לנו אפס בחזרה

250
00:11:52,989 --> 00:11:54,280
יש איזה סוג של בעיה.

251
00:11:54,280 --> 00:11:57,570
אנחנו לא רוצים dereference null ש
מצביע או שאתה תסבול אשמת SEG.

252
00:11:57,570 --> 00:11:58,510
זה לא טוב.

253
00:11:58,510 --> 00:11:59,760
אז אנחנו כבר malloced של הצומת.

254
00:11:59,760 --> 00:12:01,260
אנחנו נניח שהיינו לנו הצלחה כאן.

255
00:12:01,260 --> 00:12:06,090
אנחנו הולכים לשים 12 ל
שדה הנתונים של הצומת.

256
00:12:06,090 --> 00:12:11,570
עכשיו אתה זוכר שהמצביעים שלנו
המהלכים הבאים ולכן אנחנו לא לשבור את השרשרת?

257
00:12:11,570 --> 00:12:15,100
יש לנו כמה אפשרויות כאן, אבל
רק אחד שהולך להיות בטוח

258
00:12:15,100 --> 00:12:19,330
הוא להגדיר חדשות הבאות מצביע ל
נקודה לראש הרשימה הישנה

259
00:12:19,330 --> 00:12:21,360
או מה יהיה בקרוב
ראש ישן של הרשימה.

260
00:12:21,360 --> 00:12:23,610
ועכשיו שכולנו
אלמנטים משורשרים יחד,

261
00:12:23,610 --> 00:12:27,370
אנחנו רק יכולים להעביר את הרשימה להצביע
לאותו המקום שעושה חדשים.

262
00:12:27,370 --> 00:12:33,550
ויש לנו עכשיו ביעילות דחף
אלמנט חדש על החלק הקדמי של המחסנית.

263
00:12:33,550 --> 00:12:36,420
>> פופ אנחנו רק רוצים
להסיר שהאלמנט הראשון.

264
00:12:36,420 --> 00:12:38,150
ואז בעצם מה ש
אנחנו צריכים לעשות כאן,

265
00:12:38,150 --> 00:12:40,050
גם אנחנו צריכים למצוא את המרכיב השני.

266
00:12:40,050 --> 00:12:43,540
סופו של דבר שיהפוך חדש
ראש אחרי שנמחק את הראשון.

267
00:12:43,540 --> 00:12:47,300
אז אנחנו פשוט צריכים להתחיל מ
ההתחלה, להתקדם אחד.

268
00:12:47,300 --> 00:12:50,340
ברגע שיש לנו אחיזה באחד
קדימה של איפה אנחנו כיום

269
00:12:50,340 --> 00:12:53,850
אנחנו יכולים למחוק את הראשון בשלום
ואז אנחנו יכולים רק להזיז את הראש

270
00:12:53,850 --> 00:12:57,150
כדי להצביע על מה שהיה
שני טווח ולאחר מכן החברה

271
00:12:57,150 --> 00:12:59,170
הוא הראשון לאחר ש
צומת נמחקה.

272
00:12:59,170 --> 00:13:01,160
>> אז שוב, לקחת מבט
על זה כתרשימנו

273
00:13:01,160 --> 00:13:05,022
רוצה פופ עכשיו
אלמנט משל ערימה זה.

274
00:13:05,022 --> 00:13:05,730
אז מה אנחנו עושים?

275
00:13:05,730 --> 00:13:08,188
ובכן אנחנו הולכים ראשון כדי ליצור
מצביע חדש שהולך

276
00:13:08,188 --> 00:13:10,940
כדי להצביע על אותה הנקודה כראש.

277
00:13:10,940 --> 00:13:13,790
אנחנו הולכים להעביר אותה במקום אחד
קדימה באומר שווים טראב

278
00:13:13,790 --> 00:13:17,510
יומרות תרמילאיות הבאות לדוגמא, ש
תקדם את אחד מצביע טראב

279
00:13:17,510 --> 00:13:19,324
עמדה קדימה.

280
00:13:19,324 --> 00:13:21,240
עכשיו שיש לנו
להחזיק במרכיב הראשון

281
00:13:21,240 --> 00:13:24,573
ברשימת המצביע נקרא, ו
אלמנט שני באמצעות מצביע נקרא

282
00:13:24,573 --> 00:13:28,692
טראב, אנו יכולים למחוק באופן בטוח ש
אלמנט ראשון מהערימה

283
00:13:28,692 --> 00:13:30,650
מבלי לאבד את השאר
של השרשרת כי אנחנו

284
00:13:30,650 --> 00:13:32,358
יש דרך להתייחס
לאלמנט השני

285
00:13:32,358 --> 00:13:34,780
קדימה בדרך של
מצביע נקרא טראב.

286
00:13:34,780 --> 00:13:37,100
>> אז עכשיו אנחנו יכולים לשחרר את הצומת.

287
00:13:37,100 --> 00:13:38,404
אנחנו יכולים לשחרר את הרשימה.

288
00:13:38,404 --> 00:13:41,320
ואז כל מה שאנחנו צריכים לעשות עכשיו הוא
להעביר את הרשימה לנקודה לאותו המקום

289
00:13:41,320 --> 00:13:44,482
טראב שעושה, ואנחנו סוג של חזרה
שבו התחלנו לפני שדחפנו 12

290
00:13:44,482 --> 00:13:45,690
במקום הראשון, נכון.

291
00:13:45,690 --> 00:13:46,940
זה בדיוק איפה שהיינו.

292
00:13:46,940 --> 00:13:48,840
היו לנו ערימת ארבעה רכיב זה.

293
00:13:48,840 --> 00:13:49,690
הוספנו חמישי.

294
00:13:49,690 --> 00:13:51,910
אנחנו דחפתי חמישית
אלמנט ב, ואז אנחנו

295
00:13:51,910 --> 00:13:55,980
צץ שלאחרונה
הוסיף אלמנט אחורה.

296
00:13:55,980 --> 00:13:58,816
>> זה באמת די הרבה
כל מה שיש לערימות.

297
00:13:58,816 --> 00:14:00,190
אתה יכול ליישם אותם כמערכים.

298
00:14:00,190 --> 00:14:01,815
אתה יכול ליישם אותם כרשימות מקושרות.

299
00:14:01,815 --> 00:14:04,810
יש, כמובן, אחר
דרכים ליישומם גם כן.

300
00:14:04,810 --> 00:14:09,060
בעיקרון הסיבה היינו להשתמש
ערימות היא לשמור נתונים בצורה כזאת

301
00:14:09,060 --> 00:14:12,090
שהוסיף לאחרונה
אלמנט הוא הדבר הראשון שאנחנו

302
00:14:12,090 --> 00:14:14,980
הולך רוצה לחזור.

303
00:14:14,980 --> 00:14:17,900
אני דאג לויד, זה cs50.

304
00:14:17,900 --> 00:14:19,926