1
00:00:00,000 --> 00:00:02,832
>> [השמעת מוסיקה]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> דאג LLOYD: אוקיי, אז ב
נקודה בקורס זה,

4
00:00:08,560 --> 00:00:15,300
אנחנו כבר כיסינו הרבה יסודות של ג
אנחנו יודעים הרבה על משתנים, מערכים,

5
00:00:15,300 --> 00:00:17,610
מצביעים, כל דברים טובים.

6
00:00:17,610 --> 00:00:21,610
אלה בנויים כל סוג של
בלראות את היסודות,

7
00:00:21,610 --> 00:00:23,880
אבל אנחנו יכולים לעשות יותר, נכון?

8
00:00:23,880 --> 00:00:27,930
אנו יכולים לשלב דברים
יחד בדרכים מעניינות.

9
00:00:27,930 --> 00:00:31,010
>> ואז בואו נעשה את זה, בואו נתחיל
להסתעף של מה C נותן לנו,

10
00:00:31,010 --> 00:00:35,270
ולהתחיל ליצור נתונים שלנו
מבנים באמצעות בנייה אלה

11
00:00:35,270 --> 00:00:40,590
בלוקים יחד כדי לעשות משהו
באמת יקר, שימושי.

12
00:00:40,590 --> 00:00:43,420
דרך אחת שאנחנו יכולים לעשות זה
לדבר על אוספים.

13
00:00:43,420 --> 00:00:48,360
כל כך כל כך הרבה שהיינו לנו סוג אחד של נתונים
מבנה לייצוג אוספים

14
00:00:48,360 --> 00:00:51,030
של רצון ערכים, ערכים דומים.

15
00:00:51,030 --> 00:00:52,350
זה יהיה מערך.

16
00:00:52,350 --> 00:00:57,020
יש לנו אוספים של מספרים שלמים, או
אוספים של דמויות וכן הלאה.

17
00:00:57,020 --> 00:01:00,890
>> מבנים גם הם סוג של נתונים
מבנה לאיסוף מידע,

18
00:01:00,890 --> 00:01:03,220
אבל זה לא לאיסוף כמו ערכים.

19
00:01:03,220 --> 00:01:08,090
זה בדרך כלל מתערבב סוגי נתונים שונים
יחד בתוך תיבה אחת.

20
00:01:08,090 --> 00:01:10,750
אבל זה לא את עצמו
משמש לשרשרת יחד

21
00:01:10,750 --> 00:01:16,920
או להתחבר יחד דומה
פריטים, כמו מערך.

22
00:01:16,920 --> 00:01:20,960
מערכים נהדרים עבור
האלמנט להסתכל למעלה, אבל זוכרים

23
00:01:20,960 --> 00:01:24,262
שזה קשה מאוד
להכניס לתוך מערך,

24
00:01:24,262 --> 00:01:26,470
אלא אם כן אנחנו מכניסים ב
הסוף מאוד של מערך זה.

25
00:01:26,470 --> 00:01:29,730
>> והדוגמא הטובה ביותר שיש לי
בשביל זה הוא מיון הכנסה.

26
00:01:29,730 --> 00:01:31,650
אם אתה זוכר וידאו שלנו
במיון הכנסה,

27
00:01:31,650 --> 00:01:34,110
היה הרבה
חשבון מעורב בכך

28
00:01:34,110 --> 00:01:37,970
להרים אלמנטים, ולהעביר אותם
מהדרך כדי שתתאים למשהו

29
00:01:37,970 --> 00:01:41,290
לאמצע המערך שלך.

30
00:01:41,290 --> 00:01:44,690
מערכים סובלים גם מאחר
בעיה, שהוא חוסר גמישות.

31
00:01:44,690 --> 00:01:47,150
כאשר אנו מצהירים מערך,
אנחנו מקבלים ירייה אחת על זה.

32
00:01:47,150 --> 00:01:49,790
אנחנו מקבלים לומר, אני רוצה
אלמנטים רבים זה.

33
00:01:49,790 --> 00:01:51,940
יכול להיות 100, אולי זה
להיות 1,000, אולי זה

34
00:01:51,940 --> 00:01:55,930
להיות x כאשר x הוא מספר שהמשתמש
נתן לנו בשורת או בשורת

35
00:01:55,930 --> 00:01:56,630
קו.

36
00:01:56,630 --> 00:01:59,905
>> אבל אנחנו מקבלים רק ירייה אחת בזה, אנחנו
לא מקבל אז לומר אה, בעצם אני

37
00:01:59,905 --> 00:02:04,360
צורך 101, או שאני צריך x בתוספת 20.

38
00:02:04,360 --> 00:02:07,910
מאוחר מדי, כבר הכריז
מערך, ואם אנחנו רוצים להגיע 101 או x

39
00:02:07,910 --> 00:02:12,050
בתוספת 20, אנחנו צריכים להכריז
מערך שונה לחלוטין,

40
00:02:12,050 --> 00:02:15,540
להעתיק את כל האלמנטים של המערך
מעל, ולאחר מכן יש לנו מספיק.

41
00:02:15,540 --> 00:02:19,880
ומה אם אנחנו טועים שוב, מה
אם אנחנו באמת צריכים 102, או בתוספת 40 x,

42
00:02:19,880 --> 00:02:21,970
אנחנו חייבים לעשות את זה שוב.

43
00:02:21,970 --> 00:02:26,250
אז הם מאוד לא גמישים
לשינוי גודל הנתונים שלנו,

44
00:02:26,250 --> 00:02:29,360
אבל אם אנו משלבים יחד כמה
של היסודות שיש לנו כבר

45
00:02:29,360 --> 00:02:33,230
למד על מצביעים ומבנים,
בפרט שימוש בזיכרון דינמי

46
00:02:33,230 --> 00:02:36,180
הקצאה עם malloc, אנחנו
יכול לשים את החתיכות הללו יחד

47
00:02:36,180 --> 00:02:40,960
כדי ליצור נתונים חדשים structure--
ביחידים קשורים רשימה שאולי say--

48
00:02:40,960 --> 00:02:45,400
המאפשר לנו לגדול ו
לכווץ אוסף של ערכים

49
00:02:45,400 --> 00:02:48,800
ולא יהיה לנו כל שטח מבוזבז.

50
00:02:48,800 --> 00:02:53,320
>> אז שוב, אנחנו קוראים לרעיון זה,
רעיון זה, רשימה מקושרת.

51
00:02:53,320 --> 00:02:56,320
בפרט, בסרט הזה שאנחנו
מדבר על רשימה מקושרת ביחידות,

52
00:02:56,320 --> 00:02:59,185
ואז עוד וידאו נדבר
רשימות על מקושרות כפליים, ש

53
00:02:59,185 --> 00:03:01,560
היא רק וריאציה על נושא כאן.

54
00:03:01,560 --> 00:03:05,200
אבל רשימה מקושרת ביחידים
מורכב מצומת,

55
00:03:05,200 --> 00:03:08,559
בלוטות פשוט להיות term-- מופשט
זה פשוט משהו שאני מתקשר

56
00:03:08,559 --> 00:03:10,350
זה סוג של
מבנה, בעצם, אני?

57
00:03:10,350 --> 00:03:16,190
רק הולך לקרוא לזה node-- וזה
יש צומת שני חברים, או שני שדות.

58
00:03:16,190 --> 00:03:20,300
יש לו נתונים, בדרך כלל
מספר שלם, לצוף אופי,

59
00:03:20,300 --> 00:03:23,790
או יכול להיות איזה סוג נתונים אחר
שהגדרת עם def סוג.

60
00:03:23,790 --> 00:03:29,290
והוא מכיל מצביע ל
צומת אחר מאותו הסוג.

61
00:03:29,290 --> 00:03:34,710
>> אז יש לנו שני דברים בתוך
צומת זו, נתונים ומצביע

62
00:03:34,710 --> 00:03:36,380
לצומת אחרת.

63
00:03:36,380 --> 00:03:39,370
ואם אתה מתחיל לדמיין
זה, אתה יכול לחשוב על זה

64
00:03:39,370 --> 00:03:42,280
כמו שרשרת של בלוטות ש
מחוברים יחד.

65
00:03:42,280 --> 00:03:45,070
יש לנו את הצומת הראשונה, זה
מכיל נתונים, ומצביע

66
00:03:45,070 --> 00:03:49,110
לצומת השנייה, המכילה
הנתונים, ומצביע לצומת השלישית.

67
00:03:49,110 --> 00:03:52,940
ואז בגלל זה אנחנו קוראים לזה
רשימה מקושרת, שהם קשורים זה לזה.

68
00:03:52,940 --> 00:03:56,070
>> מה עושה את זה מיוחד
מבנה צומת נראה?

69
00:03:56,070 --> 00:04:01,120
ובכן, אם אתה זוכר מהווידאו שלנו ב
הגדרת סוגים מותאמים אישית, עם def הסוג,

70
00:04:01,120 --> 00:04:05,400
אנו יכולים להגדיר structure-- ו
הקלד להגדיר מבנה כזה.

71
00:04:05,400 --> 00:04:11,240
tyepdef sllist struct, ולאחר מכן אני
שימוש במילה הערך כאן באופן שרירותי

72
00:04:11,240 --> 00:04:13,891
כדי לציין כל סוג נתונים באמת.

73
00:04:13,891 --> 00:04:16,890
אתה יכול לעבור על מספר שלם או לצוף,
אתה יכול להיות מה שאתה רוצה.

74
00:04:16,890 --> 00:04:19,389
זה לא מוגבל רק
מספרים שלמים, או משהו כזה.

75
00:04:19,389 --> 00:04:22,790
אז הערך הוא רק שרירותי
סוג הנתונים, ולאחר מכן מצביע

76
00:04:22,790 --> 00:04:26,310
לצומת אחרת מאותו הסוג.

77
00:04:26,310 --> 00:04:29,690
>> עכשיו, יש קצת לתפוס
כאן בהגדרת מבנה

78
00:04:29,690 --> 00:04:33,030
כאשר זה מבנה של התייחסות עצמית.

79
00:04:33,030 --> 00:04:35,340
אני צריך שאהיה לי זמני
שם למבנה שלי.

80
00:04:35,340 --> 00:04:37,640
בסוף אני היום
בבירור רוצה לקרוא לזה

81
00:04:37,640 --> 00:04:43,030
צומת SLL, זה סופו של דבר החדש
שם חלק מהגדרת הסוג שלי,

82
00:04:43,030 --> 00:04:47,450
אבל אני לא יכול להשתמש בצומת SLL
באמצע זה.

83
00:04:47,450 --> 00:04:51,430
הסיבה לכך, יש לי לא
נוצר צומת SLL סוג המכונה

84
00:04:51,430 --> 00:04:55,200
עד שפגעתי נקודה אחרונה זו כאן.

85
00:04:55,200 --> 00:04:59,720
עד לנקודה זו, אני צריך שאהיה לי
דרך נוספת להתייחס לסוג נתונים זה.

86
00:04:59,720 --> 00:05:02,440
>> וזה עצמי
סוג הנתונים רפרנציאלית.

87
00:05:02,440 --> 00:05:06,314
זה; זה סוג של נתונים
מבנה המכיל נתונים,

88
00:05:06,314 --> 00:05:08,480
ומצביע למשנהו
מבנה מאותו הסוג.

89
00:05:08,480 --> 00:05:11,750
אז אני צריך להיות מסוגל להתייחס ל
סוג נתונים זה לפחות באופן זמני,

90
00:05:11,750 --> 00:05:14,910
כך זה נותן זמני
שמו של sllist struct

91
00:05:14,910 --> 00:05:18,540
מאפשר לי אז לומר שאני רוצה
מצביע לsllist struct אחר,

92
00:05:18,540 --> 00:05:24,690
כוכב sllist struct, ולאחר מכן
אחרי שהשלמתי את ההגדרה,

93
00:05:24,690 --> 00:05:27,220
עכשיו אני יכול לקרוא לזה סוג צומת SLL.

94
00:05:27,220 --> 00:05:30,520
>> אז בגלל זה אתה רואה שיש
שם זמני כאן,

95
00:05:30,520 --> 00:05:31,879
אבל שם קבע כאן.

96
00:05:31,879 --> 00:05:33,920
לפעמים אתה עשוי לראות
הגדרות של מבנה,

97
00:05:33,920 --> 00:05:36,570
לדוגמא, שאינם
רפרנציאלית עצמי, ש

98
00:05:36,570 --> 00:05:39,390
אין לי שם מציין כאן.

99
00:05:39,390 --> 00:05:43,040
זה הייתי אומר רק struct typedef,
לפתוח סד מתולתל ולאחר מכן להגדיר את זה.

100
00:05:43,040 --> 00:05:45,620
אבל אם אתה struct הוא עצמי
רפרנציאלית, כמו זה הוא,

101
00:05:45,620 --> 00:05:49,010
אתה צריך לציין
שם סוג זמני.

102
00:05:49,010 --> 00:05:51,310
אבל סופו של דבר, עכשיו
שאנחנו כבר עשינו את זה,

103
00:05:51,310 --> 00:05:53,620
אנחנו רק יכולים להתייחס ל
בלוטות אלה, יחידות אלה,

104
00:05:53,620 --> 00:05:57,900
כצומת SLL למטרות
של שאר וידאו זה.

105
00:05:57,900 --> 00:06:00,900
>> בסדר, אז אנחנו יודעים איך
ליצור צומת רשימה מקושרת.

106
00:06:00,900 --> 00:06:03,240
אנחנו יודעים איך להגדיר
צומת רשימה מקושרת.

107
00:06:03,240 --> 00:06:06,670
עכשיו, אם אנחנו הולכים להתחיל
משתמש בהם כדי לאסוף מידע,

108
00:06:06,670 --> 00:06:10,360
יש כמה פעולות ש
צריך להבין ולעבוד איתו.

109
00:06:10,360 --> 00:06:12,860
אנחנו צריכים לדעת כיצד ליצור
רשימה מקושרת יש מאין.

110
00:06:12,860 --> 00:06:14,901
אם אין רשימה כבר,
אנחנו רוצים להתחיל אחד.

111
00:06:14,901 --> 00:06:16,960
אז אנחנו צריכים להיות מסוגלים
כדי ליצור רשימה מקושרת,

112
00:06:16,960 --> 00:06:19,130
אנחנו צריכים כנראה לחפש
ברשימת הקשר

113
00:06:19,130 --> 00:06:21,830
למצוא אלמנט שאנחנו מחפשים.

114
00:06:21,830 --> 00:06:24,430
אנחנו צריכים להיות מסוגלים להכניס
דברים חדשים לרשימה,

115
00:06:24,430 --> 00:06:25,930
אנחנו רוצים הרשימה שלנו כדי להיות מסוגלת לגדול.

116
00:06:25,930 --> 00:06:28,638
ובאופן דומה, אנחנו רוצים להיות מסוגלים
כדי למחוק את הדברים מהרשימה שלנו,

117
00:06:28,638 --> 00:06:30,250
אנחנו רוצים הרשימה שלנו כדי להיות מסוגלת לכווץ.

118
00:06:30,250 --> 00:06:32,160
ובסופו שלנו
תוכניות, במיוחד

119
00:06:32,160 --> 00:06:34,550
אם אתה זוכר שאנחנו
דינמי הקצאת זיכרון

120
00:06:34,550 --> 00:06:38,337
לבנות רשימות אלה בדרך כלל,
אנחנו רוצים לשחרר את כל זיכרון ש

121
00:06:38,337 --> 00:06:39,670
כאשר סיימנו לעבוד עם זה.

122
00:06:39,670 --> 00:06:44,627
ולכן אנחנו צריכים להיות מסוגלים למחוק
רשימה מקושרת שלמה באחד להיכשל בבת.

123
00:06:44,627 --> 00:06:46,460
אז בואו לעבור
חלק מפעולות אלה

124
00:06:46,460 --> 00:06:51,192
ואיך אנחנו יכולים לדמיין אותם,
מדבר בקוד פסאודו קוד ספציפי.

125
00:06:51,192 --> 00:06:53,150
אז אנחנו רוצים ליצור
רשימה מקושרת, אז אולי אנחנו

126
00:06:53,150 --> 00:06:56,480
רוצה להגדיר פונקציה
עם אב טיפוס זה.

127
00:06:56,480 --> 00:07:01,690
SLL כוכב צומת, ליצור, ואני מעביר
בטיעון אחד, כמה נתונים שרירותיים

128
00:07:01,690 --> 00:07:05,530
הקלד שוב, מסוג כלשהו נתונים שרירותי.

129
00:07:05,530 --> 00:07:10,482
אבל אני returning-- פונקציה זו צריכה
תחזור אליי מצביע, ליחידים

130
00:07:10,482 --> 00:07:11,190
צומת רשימה מקושרת.

131
00:07:11,190 --> 00:07:14,050
שוב, אנחנו מנסים ליצור
רשימה מקושרת יש מאין,

132
00:07:14,050 --> 00:07:17,900
אז אני צריך מצביע ל
רשימה שכשאני עושה.

133
00:07:17,900 --> 00:07:19,420
>> אז מה הם הצעדים המעורבים כאן?

134
00:07:19,420 --> 00:07:20,960
ובכן, דבר ראשון שאני
הולך לעשות הוא דינמי

135
00:07:20,960 --> 00:07:22,550
להקצות שטח לצומת חדשה.

136
00:07:22,550 --> 00:07:26,689
שוב, אנו יוצרים מתוך דקים זה
אוויר, ולכן אנחנו צריכים מרחב malloc לזה.

137
00:07:26,689 --> 00:07:28,480
וכמובן, מייד
אחרי שmalloc,

138
00:07:28,480 --> 00:07:31,692
אנחנו תמיד לבדוק כדי לוודא ש
pointer-- לא קבלתי אפס בחזרה.

139
00:07:31,692 --> 00:07:33,650
כי אם אנחנו מנסים ו
התרפסות מצביע null,

140
00:07:33,650 --> 00:07:36,190
אנחנו הולכים לסבול
segfault ואנחנו לא רוצים את זה.

141
00:07:36,190 --> 00:07:39,510
>> אז אנחנו רוצים למלא את השדה,
אנחנו רוצים לאתחל את שדה הערך

142
00:07:39,510 --> 00:07:41,690
ולאתחל את השדה הבא.

143
00:07:41,690 --> 00:07:45,450
ואז אנחנו רוצים צריכה-- סופו של דבר כ
אב טיפוס הפונקציה indicates-- אנחנו רוצים

144
00:07:45,450 --> 00:07:49,940
לחזור מצביע לצומת SLL.

145
00:07:49,940 --> 00:07:51,710
אז מה לעשות זה נראה כמו חזותי?

146
00:07:51,710 --> 00:07:55,230
ובכן, קודם אנחנו הולכים באופן דינמי
להקצות שטח לצומת SLL חדש,

147
00:07:55,230 --> 00:07:58,320
כדי שmalloc-- זה
ייצוג חזותי

148
00:07:58,320 --> 00:08:00,020
של הצומת אנחנו פשוט נוצרו.

149
00:08:00,020 --> 00:08:02,757
ואנחנו בודקים לוודא
זה לא null-- במקרה זה,

150
00:08:02,757 --> 00:08:04,840
התמונה לא הייתה
הופיע אם זה היה ריק,

151
00:08:04,840 --> 00:08:07,298
היינו נגמרים של זיכרון,
כך אנחנו טובים ללכת לשם.

152
00:08:07,298 --> 00:08:10,200
אז עכשיו אנחנו בלשלב C,
לאתחל את שדה ערך צמתים.

153
00:08:10,200 --> 00:08:12,280
ובכן, המבוסס על פונקציה זו
קורא אני משתמש כאן,

154
00:08:12,280 --> 00:08:16,700
נראה כמו שאני רוצה לעבור ב6,
אז אני 6 בשדה הערך.

155
00:08:16,700 --> 00:08:18,865
עכשיו, לאתחל את השדה הבא.

156
00:08:18,865 --> 00:08:21,640
ובכן, מה אני הולך לעשות שם,
אין שום דבר הבא, נכון,

157
00:08:21,640 --> 00:08:23,600
זה הדבר היחיד ברשימה.

158
00:08:23,600 --> 00:08:27,206
אז מה הדבר הבא ברשימה?

159
00:08:27,206 --> 00:08:29,660
>> זה לא צריך להצביע על כל דבר, נכון.

160
00:08:29,660 --> 00:08:33,600
אין שום דבר אחר שיש, אז מה הוא
המושג שאנחנו יודעים על זה nothing--

161
00:08:33,600 --> 00:08:35,638
מצביעים לשום דבר?

162
00:08:35,638 --> 00:08:37,929
זה צריך להיות אולי אנחנו רוצים
לשים מצביע null שם,

163
00:08:37,929 --> 00:08:40,178
ואני מייצג את null
מצביע כפשוט תיבה אדומה,

164
00:08:40,178 --> 00:08:41,559
אנחנו לא יכולים ללכת יותר.

165
00:08:41,559 --> 00:08:44,430
כפי שנראה קצת מאוחר יותר,
תהיה לנו בסופו השרשרות

166
00:08:44,430 --> 00:08:46,330
חיצים חיבור
בלוטות אלה יחד,

167
00:08:46,330 --> 00:08:48,480
אבל כאשר אתה מכה
תיבה אדומה, זה null,

168
00:08:48,480 --> 00:08:51,150
אנחנו לא יכולים ללכת יותר,
זה סוף הרשימה.

169
00:08:51,150 --> 00:08:53,960
>> ולבסוף, אנחנו רק רוצים
לחזור מצביע לצומת זו.

170
00:08:53,960 --> 00:08:56,160
אז אנחנו קוראים לזה חדש,
ויחזור חדש

171
00:08:56,160 --> 00:08:59,370
כך שהוא יכול לשמש ב
מה פונקציה יצר אותו.

172
00:08:59,370 --> 00:09:03,100
אז יש לנו ללכת, יצרנו ביחידים
צומת רשימה מקושרת יש מאין,

173
00:09:03,100 --> 00:09:05,920
ועכשיו יש לנו רשימה שאנחנו יכולים לעבוד איתו.

174
00:09:05,920 --> 00:09:08,260
>> עכשיו, נניח שאנחנו כבר
יש שרשרת גדולה,

175
00:09:08,260 --> 00:09:09,800
ואנחנו רוצים למצוא משהו בזה.

176
00:09:09,800 --> 00:09:12,716
ואנחנו רוצים פונקציה שקורה
לחזור אמת או שקר, בהתאם

177
00:09:12,716 --> 00:09:15,840
על אם ערך קיים ברשימה.

178
00:09:15,840 --> 00:09:18,160
אב טיפוס פונקציה, או
הכרזה לפונקציה ש,

179
00:09:18,160 --> 00:09:23,320
עשוי להיראות כמו זה-- בול למצוא, ו
אז אנחנו רוצים לעבור בשתי טענות.

180
00:09:23,320 --> 00:09:26,996
>> הראשון, הוא מצביע ל
האלמנט הראשון של הרשימה המקושרת.

181
00:09:26,996 --> 00:09:29,620
זהו למעשה משהו שאתה
תמיד רוצה לעקוב אחר,

182
00:09:29,620 --> 00:09:33,110
ובעצם יכול להיות משהו ש
אתה אפילו להכניס למשתנה גלובלית.

183
00:09:33,110 --> 00:09:35,360
ברגע שאתה יוצר רשימה,
אתה תמיד, תמיד

184
00:09:35,360 --> 00:09:38,990
רוצה לעקוב אחר מאוד
האלמנט הראשון של הרשימה.

185
00:09:38,990 --> 00:09:43,690
ככה אתה יכול להתייחס לכל אחר
אלמנטים רק על ידי הבא בשרשרת,

186
00:09:43,690 --> 00:09:47,300
מבלי לשמור מצביעים
שלם לכל אלמנט.

187
00:09:47,300 --> 00:09:50,920
אתה רק צריך לעקוב אחר ראשון
אחד אם הם כל כבול יחד.

188
00:09:50,920 --> 00:09:52,460
>> ואז דבר השני
אנחנו עוברים שוב

189
00:09:52,460 --> 00:09:54,376
הוא שרירותי some--
כל סוג נתונים אנחנו

190
00:09:54,376 --> 00:09:59,640
מחפש יש בתוך
אני מקווה אחד הצמתים ברשימה.

191
00:09:59,640 --> 00:10:00,980
אז מה הם השלבים?

192
00:10:00,980 --> 00:10:04,250
ובכן, הדבר הראשון שאנחנו עושים הוא
אנו יוצרים מצביע רוחבי

193
00:10:04,250 --> 00:10:06,015
מצביע על ראש הרשימות.

194
00:10:06,015 --> 00:10:08,890
ובכן, למה אנחנו עושים את זה, אנחנו כבר
יש מצביע בראש הרשימות,

195
00:10:08,890 --> 00:10:10,974
למה אנחנו לא רק לעבור שאחד מסביב?

196
00:10:10,974 --> 00:10:13,140
ובכן, כמו שאמרתי,
זה באמת חשוב לנו

197
00:10:13,140 --> 00:10:17,580
תמיד לעקוב אחר
האלמנט הראשון ברשימה.

198
00:10:17,580 --> 00:10:21,270
וכך זה בעצם טוב יותר
כדי ליצור עותק של זה,

199
00:10:21,270 --> 00:10:25,350
ולהשתמש בו כדי לנוע, כדי שאף פעם לא
לעבור בטעות משם, או שאנחנו תמיד

200
00:10:25,350 --> 00:10:30,430
יש מצביע בשלב מסוים שהוא
ממש על האלמנט הראשון של הרשימה.

201
00:10:30,430 --> 00:10:33,290
אז זה טוב יותר כדי ליצור
שנייה אחת שאנו משתמשים כדי לעבור.

202
00:10:33,290 --> 00:10:35,877
>> אז אנחנו פשוט להשוות בין
שדה הערך בצומת ש

203
00:10:35,877 --> 00:10:38,960
זה מה שאנחנו מחפשים, ואם זה
לא, אנחנו פשוט לעבור לצומת הבאה.

204
00:10:38,960 --> 00:10:41,040
ואנחנו ממשיכים לעשות את זה
מעל, ושוב, ושוב,

205
00:10:41,040 --> 00:10:44,811
עד שגם למצוא
האלמנט, או שפגענו

206
00:10:44,811 --> 00:10:47,310
null-- אנחנו כבר הגענו לסוף
של הרשימה והוא לא שם.

207
00:10:47,310 --> 00:10:50,540
זה צריך לקוות לצלצל בפעמון
לך כמו סתם חיפוש ליניארי,

208
00:10:50,540 --> 00:10:54,430
אנחנו רק משכפלים אותו ב
מבנה רשימה מקושר ביחידים

209
00:10:54,430 --> 00:10:56,280
במקום להשתמש במערך לעשות את זה.

210
00:10:56,280 --> 00:10:58,210
>> אז הנה דוגמא ל
רשימה מקושרת ביחידים.

211
00:10:58,210 --> 00:11:00,043
אחד זה מורכב מ
חמישה צמתים, ויש לנו

212
00:11:00,043 --> 00:11:04,330
מצביע לראש
רשימה, הנקראת רשימה.

213
00:11:04,330 --> 00:11:07,385
הדבר הראשון שאנחנו רוצים לעשות הוא
שוב, ליצור שמצביע חציה.

214
00:11:07,385 --> 00:11:09,760
אז יש לנו עכשיו שני מצביעים
נקודה שלאותו הדבר.

215
00:11:09,760 --> 00:11:15,025
>> עכשיו, שים לב גם כאן, אני לא
צריך malloc חלל כל לטראב.

216
00:11:15,025 --> 00:11:18,970
אני לא אומר טראב שווה malloc
משהו, צומת שכבר קיימת,

217
00:11:18,970 --> 00:11:21,160
החלל שבזיכרון כבר קיים.

218
00:11:21,160 --> 00:11:24,290
אז כל מה שאני בעצם אני עושה הוא
יצירת מצביע אחר לזה.

219
00:11:24,290 --> 00:11:28,210
אני לא mallocing נוסף
חלל, רק צריכים עכשיו שני מצביעים

220
00:11:28,210 --> 00:11:31,370
מצביע על אותו הדבר.

221
00:11:31,370 --> 00:11:33,710
>> אז הוא 2 מה אני מחפש?

222
00:11:33,710 --> 00:11:37,220
ובכן, לא, אז במקום אני
הולך לעבור אל השלב הבא.

223
00:11:37,220 --> 00:11:41,740
אז בעצם הייתי אומר,
טראב שווה טראב הבא.

224
00:11:41,740 --> 00:11:43,630
האם 3 מה אני מחפש, לא.

225
00:11:43,630 --> 00:11:45,780
אז אני ממשיך ללכת
דרך, עד שסופו של דבר

226
00:11:45,780 --> 00:11:48,690
לקבל עד 6 וזה מה שאני מחפש
למבוסס על הקריאה לפונקציה

227
00:11:48,690 --> 00:11:51,600
יש לי בראש
שם, ואז אני עושה.

228
00:11:51,600 --> 00:11:54,150
>> עכשיו, מה אם האלמנט אני
מחפש אינו ברשימה,

229
00:11:54,150 --> 00:11:55,510
האם זה עדיין הולך לעבודה?

230
00:11:55,510 --> 00:11:57,120
ובכן, שים לב כי הרשימה
כאן הוא שונה בעדינות,

231
00:11:57,120 --> 00:11:59,410
וזה עוד דבר זה
חשוב עם רשימות מקושרות,

232
00:11:59,410 --> 00:12:01,780
אתה לא צריך לשמור על
שלהם בסדר מסוים.

233
00:12:01,780 --> 00:12:05,390
אתה יכול אם אתה רוצה, אבל
ייתכן שיש לך כבר שמת לב

234
00:12:05,390 --> 00:12:09,310
כי אנחנו לא עוקבים אחר
מה מספר אלמנט אנחנו ב.

235
00:12:09,310 --> 00:12:13,150
>> וזה סוג של סחר אחד ש
יש לי עם רשימה מקושרת פסוקים מערכים,

236
00:12:13,150 --> 00:12:15,300
הוא זה שאין לנו
גישה אקראית יותר.

237
00:12:15,300 --> 00:12:18,150
אנחנו לא יכולים פשוט לומר, אני רוצה
ללכת לאלמנט ה 0,

238
00:12:18,150 --> 00:12:21,410
או אלמנט ה -6 של מערכי,
שאני יכול לעשות במערך.

239
00:12:21,410 --> 00:12:25,080
אני לא יכול להגיד שאני רוצה ללכת ל
אלמנט ה 0, או האלמנט 6,

240
00:12:25,080 --> 00:12:30,360
או אלמנט ה -25 של הרשימה המקושרת שלי,
אין מדד הקשורים בם.

241
00:12:30,360 --> 00:12:33,660
ואז זה לא ממש משנה
אם אנחנו שומרים הרשימה שלנו כדי.

242
00:12:33,660 --> 00:12:36,080
אם אתה רוצה אתה
בהחלט יכול, אבל יש

243
00:12:36,080 --> 00:12:38,567
אין סיבה שהם צריכים
יישמר בכל סדר.

244
00:12:38,567 --> 00:12:40,400
אז שוב, בואו ננסה ו
למצוא 6 ברשימה זו.

245
00:12:40,400 --> 00:12:43,200
ובכן, אנחנו מתחילים ב
מתחיל, אנחנו לא מוצאים 6,

246
00:12:43,200 --> 00:12:47,690
ואז אנחנו ממשיכים לא מציאת
6, עד שסופו של דבר להגיע לכאן.

247
00:12:47,690 --> 00:12:52,790
נקודות עכשיו טראב אז זכות הצומת
המכיל 8, ושש הוא לא שם.

248
00:12:52,790 --> 00:12:55,250
>> אז הצעד הבא יהיה
ללכת למצביע הבא,

249
00:12:55,250 --> 00:12:57,440
כך אומר טראב שווה טראב הבא.

250
00:12:57,440 --> 00:13:00,750
ובכן, טראב הבא, שצוין על ידי
התיבה האדומה שם, היא null.

251
00:13:00,750 --> 00:13:03,020
אז יש מקום אחר
ללכת, ולכן בשלב זה

252
00:13:03,020 --> 00:13:06,120
אנו יכולים להסיק כי אנחנו כבר הגענו
סוף הרשימה המקושרת,

253
00:13:06,120 --> 00:13:07,190
ו -6 לא נמצא שם.

254
00:13:07,190 --> 00:13:10,980
וזה יוחזר
שקר במקרה הזה.

255
00:13:10,980 --> 00:13:14,540
>> אישור, איך אנחנו מכניסים חדשים
צומת לרשימה המקושרת?

256
00:13:14,540 --> 00:13:17,310
אז אנחנו כבר יכולים ליצור
רשימה מקושרת משום מקום,

257
00:13:17,310 --> 00:13:19,370
אבל אנחנו כנראה רוצים
לבנות שרשרת ולא

258
00:13:19,370 --> 00:13:22,620
ליצור חבורה של רשימות שונות.

259
00:13:22,620 --> 00:13:25,700
אנחנו רוצים שנהיה לי רשימה אחת ש
יש חבורה של צמתים בזה,

260
00:13:25,700 --> 00:13:28,040
לא חבורה של רשימות עם צומת אחת.

261
00:13:28,040 --> 00:13:31,260
אז אנחנו לא יכולים פשוט להמשיך להשתמש ביצירה
פונקציה שהגדרנו קודם לכן, עכשיו אנחנו

262
00:13:31,260 --> 00:13:33,860
רוצה להכניס לתוך
רשימה שכבר קיימת.

263
00:13:33,860 --> 00:13:36,499
>> אז המקרה הזה, אנחנו הולכים
לעבור בשתי טענות,

264
00:13:36,499 --> 00:13:39,290
מצביע לראש ש
רשימה מקושרת שאנחנו רוצים להוסיף ל.

265
00:13:39,290 --> 00:13:40,910
שוב, זה למה זה כל כך
חשוב שתמיד

266
00:13:40,910 --> 00:13:43,400
לעקוב אחר זה, כי
זה הדרך היחידה שאנחנו באמת

267
00:13:43,400 --> 00:13:46,690
יש להתייחס לכל הרשימה היא
רק על ידי מצביע לאלמנט הראשון.

268
00:13:46,690 --> 00:13:49,360
אז אנחנו רוצים לעבור ב
מצביע שלאלמנט הראשון,

269
00:13:49,360 --> 00:13:52,226
ומה ערך ש
רוצה להוסיף לרשימה.

270
00:13:52,226 --> 00:13:54,600
וסופו של דבר בפונקציה זו
הוא הולך לחזור מצביע

271
00:13:54,600 --> 00:13:57,980
לראש החדש של רשימה מקושרת.

272
00:13:57,980 --> 00:13:59,700
>> מהם השלבים המעורבים כאן?

273
00:13:59,700 --> 00:14:02,249
ובכן, בדיוק כמו עם יצירה,
אנחנו צריכים להקצות באופן דינמי

274
00:14:02,249 --> 00:14:05,540
מרחב לצומת חדשה, ולבדוק לעשות
בטוח שלא נגמרו זיכרון, שוב,

275
00:14:05,540 --> 00:14:07,150
בגלל שאנחנו משתמשים בmalloc.

276
00:14:07,150 --> 00:14:09,080
אז אנחנו רוצים לאכלס
ולהכניס את הצומת,

277
00:14:09,080 --> 00:14:12,730
כך לשים את המספר, מה ש
val הוא, לצומת.

278
00:14:12,730 --> 00:14:17,310
אנחנו רוצים להכניס את הצומת ב
תחילת הרשימה המקושרת.

279
00:14:17,310 --> 00:14:19,619
>> יש סיבה שאני
רוצה לעשות את זה, וזה

280
00:14:19,619 --> 00:14:21,910
יכול להיות שווה לקחת שני
כדי להשהות את הווידאו כאן,

281
00:14:21,910 --> 00:14:25,860
ולחשוב למה שהייתי רוצה
הכנס בתחילת קשורה

282
00:14:25,860 --> 00:14:26,589
רשימה.

283
00:14:26,589 --> 00:14:28,630
שוב, שציינתי קודם לכן
כי זה לא ממש

284
00:14:28,630 --> 00:14:33,020
משנה אם אנחנו לשמר אותו בכל
כדי, אז אולי זה רמז.

285
00:14:33,020 --> 00:14:36,040
ואתה ראית מה היה קורה אם הייתי
רציתי צריכה-- או מרק שני

286
00:14:36,040 --> 00:14:37,360
לפני כאשר אנחנו הולכים
באמצעות חיפוש ש

287
00:14:37,360 --> 00:14:39,235
יכולתי לראות את מה שאולי
יקרה אם אנחנו מנסים

288
00:14:39,235 --> 00:14:41,330
להכניס בסוף הרשימה.

289
00:14:41,330 --> 00:14:44,750
מכיוון שאין לנו
מצביע לסוף הרשימה.

290
00:14:44,750 --> 00:14:47,490
>> אז הסיבה שאני היה רוצה
להכניס בתחילת,

291
00:14:47,490 --> 00:14:49,380
כי אני יכול לעשות את זה באופן מיידי.

292
00:14:49,380 --> 00:14:52,730
יש לי מצביע בתחילת, ו
אנחנו אראה את זה בראייה בשנייה.

293
00:14:52,730 --> 00:14:55,605
אבל אם אני רוצה להכניס בסוף,
אני צריך להתחיל בהתחלה,

294
00:14:55,605 --> 00:14:58,760
לעבור את כל הדרך ל
סוף, ואז טקטיקה על זה.

295
00:14:58,760 --> 00:15:01,420
אז זה אומר ש
הכנסה בסוף הרשימה

296
00:15:01,420 --> 00:15:04,140
יהפוך o של n
מבצע, חוזר

297
00:15:04,140 --> 00:15:06,720
לדיון שלנו
מורכבות חישובית.

298
00:15:06,720 --> 00:15:10,140
זה הייתי הופך o פעולת n, בי
כרשימה יש יותר גדולה, וגדולה יותר,

299
00:15:10,140 --> 00:15:13,310
ו, זה יהפוך גדול יותר יותר ו
קשה יותר לטקטיקת משהו

300
00:15:13,310 --> 00:15:14,661
בסוף.

301
00:15:14,661 --> 00:15:17,410
אבל זה תמיד ממש קל
טקטיקה משהו על בהתחלה,

302
00:15:17,410 --> 00:15:19,060
אתה תמיד בהתחלה.

303
00:15:19,060 --> 00:15:21,620
>> ואנו רואים חזותיים של זה שוב.

304
00:15:21,620 --> 00:15:24,100
ואז ברגע שנסיים, פעם אחת
אנחנו כבר הכנסנו את הצומת החדשה,

305
00:15:24,100 --> 00:15:26,880
אנחנו רוצים לחזור המצביע שלנו ל
הראש החדש של רשימה מקושרת, ש

306
00:15:26,880 --> 00:15:29,213
מאז שאנחנו מכניסים ב
מתחיל, יהיה למעשה

307
00:15:29,213 --> 00:15:31,060
מצביע לצומת רק יצרנו.

308
00:15:31,060 --> 00:15:33,280
בואו לחזות את זה,
כי אני חושב שזה יעזור.

309
00:15:33,280 --> 00:15:36,661
>> אז הנה הרשימה שלנו, זה מורכב מ
ארבעה יסודות, צומת המכילות 15,

310
00:15:36,661 --> 00:15:38,410
המצביע על צומת
המכיל 9, ש

311
00:15:38,410 --> 00:15:41,370
מצביע על צומת המכילה 13,
המצביע על צומת המכילה

312
00:15:41,370 --> 00:15:44,840
10, שבו יש null
מצביע כמצביע הבא שלה

313
00:15:44,840 --> 00:15:47,010
אז זה סוף הרשימה.

314
00:15:47,010 --> 00:15:50,200
אז אנחנו רוצים להכניס
צומת חדשה עם הערך 12

315
00:15:50,200 --> 00:15:52,720
בתחילת זה
רשימה, מה עושים?

316
00:15:52,720 --> 00:15:58,770
ובכן, קודם אנחנו malloc מקום ל
צומת, ואז אנחנו שמים 12 שם.

317
00:15:58,770 --> 00:16:02,211
>> אז עכשיו אנחנו כבר הגענו
נקודת החלטה, נכון?

318
00:16:02,211 --> 00:16:03,960
יש לנו כמה
מצביעים שאנחנו יכולים

319
00:16:03,960 --> 00:16:06,770
להעביר, שיש לנו לעבור ראשון?

320
00:16:06,770 --> 00:16:09,250
האם עלינו לעשות 12 נקודות ל
הראש החדש של list--

321
00:16:09,250 --> 00:16:13,020
או תסלחו לי, אנחנו צריכים לעשות 12
מצביע לראש הרשימה הישן?

322
00:16:13,020 --> 00:16:15,319
או שאנחנו צריכים לומר ש
רשימה מתחילה עכשיו בגיל 12.

323
00:16:15,319 --> 00:16:17,110
יש הבחנה
שם, ואנחנו נראים

324
00:16:17,110 --> 00:16:19,870
מה קורה עם שני בשני.

325
00:16:19,870 --> 00:16:23,350
>> אבל זה מוביל ל
נושא נהדר לסרגל צדדי,

326
00:16:23,350 --> 00:16:26,280
אשר הוא שאחד מ
הדברים מסובכים ביותר עם רשימות מקושרות

327
00:16:26,280 --> 00:16:30,980
להוא לארגן את המצביעים
בסדר הנכון.

328
00:16:30,980 --> 00:16:34,520
אם תעביר את הדברים מקולקלים,
אתה יכול בסופו של טעות

329
00:16:34,520 --> 00:16:36,050
יִתוּם שאר הרשימה.

330
00:16:36,050 --> 00:16:37,300
והנה דוגמה לכך.

331
00:16:37,300 --> 00:16:40,540
אז בואו נלך עם הרעיון של--
גם, שיצרנו 12 רק.

332
00:16:40,540 --> 00:16:43,180
אנחנו יודעים 12 הולכים להיות
הראש החדש של הרשימה,

333
00:16:43,180 --> 00:16:47,660
ואז למה אנחנו לא פשוט לעבור
מצביע הרשימה להצביע שם.

334
00:16:47,660 --> 00:16:49,070
>> אוקיי, אז זה טוב.

335
00:16:49,070 --> 00:16:51,560
אז עכשיו שבו עושה 12 הנקודה הבאה?

336
00:16:51,560 --> 00:16:54,580
אני מתכוון, מבחינה ויזואלית ניתן לראות
שיצביע על 15,

337
00:16:54,580 --> 00:16:57,250
כמו בני אדם זה ממש ברור לנו.

338
00:16:57,250 --> 00:17:00,300
איך המחשב יודע?

339
00:17:00,300 --> 00:17:02,720
אין לנו שום דבר
מצביע על 15 יותר, נכון?

340
00:17:02,720 --> 00:17:05,869
>> איבדנו כל יכולת להתייחס ל -15.

341
00:17:05,869 --> 00:17:11,460
אנחנו לא יכולים לומר שווים הבאים חץ החדש
משהו, אין שם כלום.

342
00:17:11,460 --> 00:17:13,510
למעשה, אנחנו כבר מיותמים
שאר הרשימה

343
00:17:13,510 --> 00:17:16,465
על ידי כך, יש לנו
נשבר בטעות השרשרת.

344
00:17:16,465 --> 00:17:18,089
ואנחנו בהחלט לא רוצים לעשות את זה.

345
00:17:18,089 --> 00:17:20,000
>> אז בואו לחזור ולנסות את זה שוב.

346
00:17:20,000 --> 00:17:24,060
אולי הדבר הנכון לעשות
הוא לקבוע של 12 מצביע הבא

347
00:17:24,060 --> 00:17:28,290
לראש הישן של הרשימה הראשונה,
אז אנחנו יכולים להעביר את הרשימה על.

348
00:17:28,290 --> 00:17:30,420
ולמעשה, כי הוא
סדר נכון שאנחנו

349
00:17:30,420 --> 00:17:32,836
צריך לעקוב אחרי כשאנחנו
עבודה עם רשימה מקושרת ביחידים.

350
00:17:32,836 --> 00:17:36,460
אנחנו תמיד רוצים להתחבר
אלמנט חדש לרשימה,

351
00:17:36,460 --> 00:17:41,010
לפני שאנחנו לוקחים את זה סוג של
צעד חשוב של שינוי

352
00:17:41,010 --> 00:17:43,360
שבו ראש הרשימה המקושרת הוא.

353
00:17:43,360 --> 00:17:46,740
שוב, זה דבר כזה בסיסי,
אנו לא רוצים לאבד אותו.

354
00:17:46,740 --> 00:17:49,310
>> אז אנחנו רוצים לוודא ש
כל מה שהוא כבול יחד,

355
00:17:49,310 --> 00:17:52,040
לפני שנעבור מצביע ש.

356
00:17:52,040 --> 00:17:55,300
ואז זה יהיה בסדר הנכון,
אשר הוא לחבר 12 לרשימה,

357
00:17:55,300 --> 00:17:57,630
אז לומר שהרשימה מתחילה 12.

358
00:17:57,630 --> 00:18:00,860
אם אמר הרשימה מתחילה ב 12 ו
לאחר מכן ניסיתי להתחבר 12 לרשימה,

359
00:18:00,860 --> 00:18:02,193
כבר ראינו מה קורה.

360
00:18:02,193 --> 00:18:04,920
אנחנו מאבדים את הרשימה בטעות.

361
00:18:04,920 --> 00:18:06,740
>> אוקיי, אז עוד דבר אחד לדבר עליו.

362
00:18:06,740 --> 00:18:09,750
מה אם אנחנו רוצים להיפטר מ
כל מקושר רשימה בבת אחת?

363
00:18:09,750 --> 00:18:11,750
שוב, אנחנו mallocing
כל המרחב הזה, ולכן אנחנו

364
00:18:11,750 --> 00:18:13,351
צריך לשחרר אותו לאחר שנסיים.

365
00:18:13,351 --> 00:18:15,350
אז עכשיו אנחנו רוצים למחוק
הרשימה כל מדד.

366
00:18:15,350 --> 00:18:16,850
ובכן, מה אנחנו רוצים לעשות?

367
00:18:16,850 --> 00:18:20,460
>> אם הגענו למצביע null, ש
רוצה להפסיק, אחרת, פשוט למחוק

368
00:18:20,460 --> 00:18:23,420
שאר הרשימה ולאחר מכן לשחרר אותי.

369
00:18:23,420 --> 00:18:28,890
מחק את שאר הרשימה,
ולאחר מכן לשחרר את הצומת הנוכחית.

370
00:18:28,890 --> 00:18:32,850
מה זה נשמע כמו,
מה טכניקה יש לנו דיברנו

371
00:18:32,850 --> 00:18:35,440
עושה על העבר זה נשמע כמו?

372
00:18:35,440 --> 00:18:39,560
מחק את כולם, אז
לחזור ולמחוק אותי.

373
00:18:39,560 --> 00:18:42,380
>> זה רקורסיה, שעשינו
בעיה קצת יותר קטנה,

374
00:18:42,380 --> 00:18:46,910
אנחנו אומרים למחוק את כולם
אחר, אז אתה יכול למחוק אותי.

375
00:18:46,910 --> 00:18:50,940
ועוד יותר בהמשך הדרך, צומת ש
יגיד, למחוק את כולם.

376
00:18:50,940 --> 00:18:53,940
אבל סופו של דבר נגיע ל
נקודה שבה הרשימה היא ריקה,

377
00:18:53,940 --> 00:18:55,310
וזה מקרה הבסיס שלנו.

378
00:18:55,310 --> 00:18:57,010
>> אז בואו נסתכל על זה,
ואיך זה יכול לעבוד.

379
00:18:57,010 --> 00:18:59,759
אז הנה הרשימה שלנו, זה אותו הדבר
רשימה אנחנו רק מדברים,

380
00:18:59,759 --> 00:19:00,980
ויש שלבים.

381
00:19:00,980 --> 00:19:04,200
יש הרבה טקסט כאן, אבל
אני מקווה ההדמיה תעזור.

382
00:19:04,200 --> 00:19:08,557
>> אז אנחנו נו-- ואני גם משכתי
עד איור מסגרות ערימה שלנו

383
00:19:08,557 --> 00:19:10,890
מהווידאו שלנו בשיחת ערימות,
ואני מקווה שכל זה

384
00:19:10,890 --> 00:19:13,260
יחד אראה לך מה קורה.

385
00:19:13,260 --> 00:19:14,510
אז הנה הקוד פסאודו הקוד שלנו.

386
00:19:14,510 --> 00:19:17,830
אם נגיע לnull
מצביע, לעצור, אחרת,

387
00:19:17,830 --> 00:19:21,320
מחק את שאר הרשימה,
לאחר מכן לשחרר את הצומת הנוכחית.

388
00:19:21,320 --> 00:19:25,700
אז עכשיו, list--
המצביע שאנחנו

389
00:19:25,700 --> 00:19:28,410
עובר בלהרוס נקודות ל -12.

390
00:19:28,410 --> 00:19:33,340
12 הוא לא מצביע null, כך שאנחנו
הולך למחוק את שאר הרשימה.

391
00:19:33,340 --> 00:19:35,450
>> מה הוא מחיקה
כולנו מעורב?

392
00:19:35,450 --> 00:19:37,950
ובכן, זה אומר מה שהופך את
קורא להרוס, אמר

393
00:19:37,950 --> 00:19:42,060
כי 15 היא תחילת
שאר הרשימה שאנחנו רוצים להרוס.

394
00:19:42,060 --> 00:19:47,480
וכך השיחה להרוס
12 הוא סוג של בהמתנה.

395
00:19:47,480 --> 00:19:52,690
זה קפוא שם, מחכה לי
קורא להרוס 15, כדי לסיים את עבודתה.

396
00:19:52,690 --> 00:19:56,280
>> ובכן, 15 הוא לא מצביע null, ו
כך זה הולך לומר, בסדר,

397
00:19:56,280 --> 00:19:58,450
טוב, למחוק את שאר הרשימה.

398
00:19:58,450 --> 00:20:00,760
שאר הרשימה מתחילה
בשעת 9, ולכן אנחנו פשוט

399
00:20:00,760 --> 00:20:04,514
לחכות עד שתמחק את כל מה ש
דברים, ואז לחזור ולמחוק אותי.

400
00:20:04,514 --> 00:20:06,680
ובכן 9 הולך להגיד, טוב,
אני לא מצביע null,

401
00:20:06,680 --> 00:20:09,020
כך למחוק את שאר הרשימה מכאן.

402
00:20:09,020 --> 00:20:11,805
וכך לנסות ולהרוס 13.

403
00:20:11,805 --> 00:20:15,550
13 אומר, אני לא מצביע null,
אותו דבר, הוא עובר באק.

404
00:20:15,550 --> 00:20:17,930
10 הוא לא מצביע null, 10
מכיל מצביע null,

405
00:20:17,930 --> 00:20:20,200
אבל 10 הוא לא את עצמו
null מצביע עכשיו,

406
00:20:20,200 --> 00:20:22,470
ואז זה עובר באק מדי.

407
00:20:22,470 --> 00:20:25,560
>> עכשיו ורשימת נקודות שם, זה
באמת היה מצביע לsome--

408
00:20:25,560 --> 00:20:28,710
אם היה לי יותר מקום בתמונה,
זה מצביע על כמה מרחב אקראי

409
00:20:28,710 --> 00:20:29,960
כי אנחנו לא יודעים מה זה.

410
00:20:29,960 --> 00:20:34,680
למרות שזה מצביע null, הרשימה
הוא ממש עכשיו להגדיר את זה של ערכי null.

411
00:20:34,680 --> 00:20:36,820
זה מצביע ממש בתוך הקופסה אדומה.

412
00:20:36,820 --> 00:20:39,960
הגענו מצביע null, כך
אנחנו יכולים להפסיק, ואנחנו נעשו.

413
00:20:39,960 --> 00:20:46,230
>> וכדי שהמסגרת הסגולה היא now-- ב
ראש stack-- זה המסגרת הפעילה,

414
00:20:46,230 --> 00:20:47,017
אבל זה נעשה.

415
00:20:47,017 --> 00:20:48,600
אם אנחנו כבר הגענו למצביע null, לעצור.

416
00:20:48,600 --> 00:20:51,290
אנחנו לא עושים שום דבר, אנחנו
לא יכול לשחרר את מצביע null,

417
00:20:51,290 --> 00:20:55,070
לא malloc כל
מרחב, ולכן אנחנו עושים.

418
00:20:55,070 --> 00:20:57,590
כך שמסגרת הפונקציה
הוא נהרס, ואנחנו

419
00:20:57,590 --> 00:21:00,930
resume-- להרים שבו השאירו
את עם אחד הגבוה ביותר הבא, ש

420
00:21:00,930 --> 00:21:02,807
היא מסגרת בצבע כחולה כהה כאן זה.

421
00:21:02,807 --> 00:21:04,390
אז אנחנו מרימים תקין שבו הפסקנו.

422
00:21:04,390 --> 00:21:06,598
אנו נמחקו שאר
רשימה כבר, אז עכשיו אנחנו

423
00:21:06,598 --> 00:21:08,000
הולך לשחרר את בלוטות הנוכחיות.

424
00:21:08,000 --> 00:21:12,920
אז עכשיו אנחנו יכולים לשחרר את הצומת הזה, ועכשיו
אנחנו כבר הגענו לסוף הפונקציה.

425
00:21:12,920 --> 00:21:16,810
וכדי שמסגרת התפקיד נהרסה,
ואנחנו להרים בכחול אחד האור.

426
00:21:16,810 --> 00:21:20,650
>> אז זה says-- אני כבר done--
מחיקה שאר הרשימה, כך

427
00:21:20,650 --> 00:21:23,140
לשחרר את הצומת הנוכחית.

428
00:21:23,140 --> 00:21:26,520
ועכשיו את המסגרת הצהובה היא
חזרה על ראש הערימה.

429
00:21:26,520 --> 00:21:29,655
וכך כפי שאתה רואה, אנחנו עכשיו
להרוס את הרשימה מימין לשמאל.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> מה היה כאילו קרה,,
אם היינו עושה דברים בצורה לא נכונה?

432
00:21:37,280 --> 00:21:39,410
בדיוק כמו כשניסינו
כדי להוסיף אלמנט.

433
00:21:39,410 --> 00:21:41,909
אם פישל השרשרת, אם
לא לחבר את המצביעים

434
00:21:41,909 --> 00:21:44,690
בסדר הנכון, אם אנחנו
רק שחררתי את האלמנט הראשון,

435
00:21:44,690 --> 00:21:47,420
אם רק השתחררתי
ראש הרשימה, עכשיו אנחנו

436
00:21:47,420 --> 00:21:49,642
אין דרך להתייחס ל
שאר הרשימה.

437
00:21:49,642 --> 00:21:51,350
וכך תהיה לנו
כל מה שהתייתם,

438
00:21:51,350 --> 00:21:53,880
היו לנו מה
נקרא דליפת זיכרון.

439
00:21:53,880 --> 00:21:56,800
אם אתה זוכר מהווידאו שלנו
על הקצאת זיכרון דינמית,

440
00:21:56,800 --> 00:21:58,650
זה לא דבר טוב מאוד.

441
00:21:58,650 --> 00:22:00,810
>> אז כמו שאמרתי, יש
כמה פעולות

442
00:22:00,810 --> 00:22:04,010
שאנחנו צריכים להשתמש בו כדי לעבוד
עם מקושר רשימת יעילות.

443
00:22:04,010 --> 00:22:08,430
וודאי שמתם לב שאני הושמט אחד,
מחיקת אלמנט יחיד ממקושר

444
00:22:08,430 --> 00:22:09,064
רשימה.

445
00:22:09,064 --> 00:22:10,980
הסיבה שעשיתי את זה
זה בעצם סוג של

446
00:22:10,980 --> 00:22:14,360
מסובך לחשוב על איך למחוק
אלמנט יחיד מיחידים

447
00:22:14,360 --> 00:22:15,600
רשימה מקושרת.

448
00:22:15,600 --> 00:22:19,950
אנחנו צריכים להיות מסוגלים לדלג על
משהו ברשימה, ש

449
00:22:19,950 --> 00:22:22,975
אומר שאנחנו מקבלים אנחנו point--
רוצה למחוק node-- זה

450
00:22:22,975 --> 00:22:25,350
אבל כדי לעשות את זה כדי ש
לא לאבד את כל מידע,

451
00:22:25,350 --> 00:22:30,530
אנחנו צריכים להתחבר זה
צומת כאן, כאן.

452
00:22:30,530 --> 00:22:33,390
>> אז אני כנראה עשיתי את זה לא נכון
מנקודת מבט חזותית.

453
00:22:33,390 --> 00:22:36,830
אז אנחנו בתחילתו שלנו
רשימה, אנחנו ממשיכים דרך,

454
00:22:36,830 --> 00:22:40,510
אנחנו רוצים למחוק את הצומת הזה.

455
00:22:40,510 --> 00:22:43,440
אם אנחנו רק למחוק אותו,
אנחנו כבר נשברו השרשרת.

456
00:22:43,440 --> 00:22:45,950
צומת זה ממש כאן
מתייחס לכל דבר אחר,

457
00:22:45,950 --> 00:22:48,260
הוא מכיל את השרשרת מכאן והלאה.

458
00:22:48,260 --> 00:22:51,190
>> אז מה שאנחנו צריכים לעשות בפועל
לאחר שנגיע לנקודה זו,

459
00:22:51,190 --> 00:22:56,670
הוא שאנחנו צריכים לקחת צעד אחורה אחת, ו
להתחבר צומת זה מעל לצומת זה,

460
00:22:56,670 --> 00:22:58,590
כדי שלאחר מכן תוכל למחוק
אחד באמצע.

461
00:22:58,590 --> 00:23:02,120
אבל רשימות מקושרות ביחידות לא
לספק לנו דרך ללכת אחורה.

462
00:23:02,120 --> 00:23:05,160
אז אנחנו צריכים גם לשמור
שני מצביעים, ולהעביר אותם

463
00:23:05,160 --> 00:23:09,527
סוג של צעד מ, אחד מאחורי
אחר כמו שאנחנו הולכים, או להגיע לנקודה

464
00:23:09,527 --> 00:23:11,110
ולאחר מכן לשלוח את מצביע אחר דרך.

465
00:23:11,110 --> 00:23:13,150
וכמו שאתה יכול לראות, זה
יכול לקבל קצת מבולגן.

466
00:23:13,150 --> 00:23:15,360
למרבה המזל, יש לנו
דרך אחרת כדי לפתור את זה,

467
00:23:15,360 --> 00:23:17,810
כאשר אנו מדברים על רשימות מקושרות כפליים.

468
00:23:17,810 --> 00:23:20,720
>> אני דאג לויד, זה CS50.

469
00:23:20,720 --> 00:23:22,298