1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [סעיף 6] [יותר נוח]

2
00:00:01,000 --> 00:00:04,000
[רוב אודן] [אוניברסיטת הרווארד]

3
00:00:04,000 --> 00:00:09,000
[זה CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> אנחנו יכולים ראש לקטע של שאלות שלנו.

5
00:00:11,000 --> 00:00:17,000
אני שלחתי את כתובת האתר למקום קודם לכן.

6
00:00:17,000 --> 00:00:22,000
תחילת הקטע של השאלות אומרות-

7
00:00:22,000 --> 00:00:26,000
כנראה אני לא לגמרי unsick-הוא שאלה מאוד קלה

8
00:00:26,000 --> 00:00:28,000
ולא רק את מה שvalgrind?

9
00:00:28,000 --> 00:00:30,000
מה valgrind עושה?

10
00:00:30,000 --> 00:00:34,000
כל מי שרוצה להגיד מה valgrind עושה?

11
00:00:34,000 --> 00:00:36,000
[סטודנטים] צקי זכרון הדלפות.

12
00:00:36,000 --> 00:00:41,000
כן, valgrind הוא בודק זיכרון כללי.

13
00:00:41,000 --> 00:00:44,000
זה, בסופו של דבר, אומר לך אם יש לך דליפות זיכרון,

14
00:00:44,000 --> 00:00:49,000
וזה בעיקר מה שאנחנו משתמשים בו לכי אם אתה רוצה

15
00:00:49,000 --> 00:00:54,000
טוב תעשה בקבוצת הבעיה או אם אתה רוצה

16
00:00:54,000 --> 00:00:59,000
לעלות על הלוח הגדול, אתה צריך אין לי דליפות זיכרון שהיא,

17
00:00:59,000 --> 00:01:01,000
ובמקרה שיש לך דליפת זיכרון שאתה לא יכול למצוא,

18
00:01:01,000 --> 00:01:04,000
גם לזכור כי בכל פעם שאתה פותח קובץ

19
00:01:04,000 --> 00:01:07,000
ואם אתה לא סוגר אותו, זה דליפת זיכרון.

20
00:01:07,000 --> 00:01:10,000
>> הרבה אנשים מחפשים צומת מסוימת שהם לא משחררים

21
00:01:10,000 --> 00:01:15,000
כאשר באמת, הם לא סגרו את המילון בצעד הראשון.

22
00:01:15,000 --> 00:01:19,000
זה גם אומר לך אם יש לך לא חוקי קורא או כותב,

23
00:01:19,000 --> 00:01:22,000
מה שאומר שאם אתה מנסה להגדיר ערך

24
00:01:22,000 --> 00:01:26,000
זה מעבר לתום הגל וזה לא קורה לאשמת seg

25
00:01:26,000 --> 00:01:30,000
אבל valgrind תופס אותו, כמו שאתה לא צריך להיות ממש כותב שם,

26
00:01:30,000 --> 00:01:33,000
ואז אתה בהחלט לא צריך את כל אלה גם.

27
00:01:33,000 --> 00:01:38,000
כיצד אתם משתמשים valgrind?

28
00:01:38,000 --> 00:01:42,000
כיצד אתם משתמשים valgrind?

29
00:01:42,000 --> 00:01:45,000
>> זו שאלה כללית של

30
00:01:45,000 --> 00:01:49,000
סוג של להריץ אותו ולהסתכל על הפלט.

31
00:01:49,000 --> 00:01:51,000
הפלט מציף הרבה פעמים.

32
00:01:51,000 --> 00:01:54,000
יש גם שגיאות כיף שבו אם יש לך משהו מאוד לא בסדר

33
00:01:54,000 --> 00:01:59,000
קורה בלולאה, ואז זה יהיה הסוף של דבר אומר, "הרבה יותר מדי טעויות.

34
00:01:59,000 --> 00:02:03,000
אני הולך להפסיק לספור עכשיו. "

35
00:02:03,000 --> 00:02:08,000
זה בעצם פלט טקסטואלי שיש לך לנתח.

36
00:02:08,000 --> 00:02:13,000
בסוף, זה יגיד לך כל דליפות זיכרון שיש לך,

37
00:02:13,000 --> 00:02:16,000
כמה רחובות משם, מה שיכול להיות שימושי כי

38
00:02:16,000 --> 00:02:20,000
אם זה unfreed בלוק אחד, אז זה בדרך כלל קל יותר למצוא

39
00:02:20,000 --> 00:02:23,000
מ -1,000 קוביות unfreed.

40
00:02:23,000 --> 00:02:26,000
1000 לוקים unfreed כנראה אומרים שאתה לא משחרר

41
00:02:26,000 --> 00:02:30,000
הרשימות המקושרות שלך כראוי או משהו.

42
00:02:30,000 --> 00:02:32,000
זה valgrind.

43
00:02:32,000 --> 00:02:35,000
>> עכשיו יש לנו הקטע מהשאלות שלנו,

44
00:02:35,000 --> 00:02:38,000
שאתה לא צריך להוריד.

45
00:02:38,000 --> 00:02:41,000
אתה יכול ללחוץ על השם שלי ומושך אותם בחלל.

46
00:02:41,000 --> 00:02:44,000
כעת לחץ עליי.

47
00:02:44,000 --> 00:02:46,000
גרסה 1 תהיה ערימה, שאנחנו עושים ראשונים.

48
00:02:46,000 --> 00:02:55,000
הגרסה 2 תהיה התור, והגרסה 3 תהיה הרשימה המקושרת ביחידים.

49
00:02:55,000 --> 00:02:58,000
להתחיל עם המחסנית שלנו.

50
00:02:58,000 --> 00:03:02,000
כמו שנאמר כאן, מחסנית היא אחד הבסיסי ביותר,

51
00:03:02,000 --> 00:03:07,000
מבני נתונים בסיסיים של מדעי מחשב.

52
00:03:07,000 --> 00:03:11,000
הדוגמא הטיפוסית היא מאוד

53
00:03:11,000 --> 00:03:13,000
את ערימת המגשים בחדר האוכל.

54
00:03:13,000 --> 00:03:16,000
זה בעצם כל פעם שהם מונהגים על ערימה,

55
00:03:16,000 --> 00:03:20,000
מישהו הולך לומר, "אה, כמו ערימה של מגשים."

56
00:03:20,000 --> 00:03:22,000
אתה מחסנית את המגשים.

57
00:03:22,000 --> 00:03:24,000
ואז כשאתה הולך למשוך את מגש,

58
00:03:24,000 --> 00:03:31,000
המגש הראשון המקבל משך הוא האחרון שהונח על הערימה.

59
00:03:31,000 --> 00:03:34,000
המחסנית גם כמו שהוא אומר, כאן

60
00:03:34,000 --> 00:03:37,000
יש לנו את הקטע של זיכרון נקרא המחסנית.

61
00:03:37,000 --> 00:03:40,000
ולמה זה נקרא המחסנית?

62
00:03:40,000 --> 00:03:42,000
>> כי כמו מבנה נתוני מחסנית,

63
00:03:42,000 --> 00:03:46,000
הוא דוחף וקופץ מסגרות מחסנית במחסנית,

64
00:03:46,000 --> 00:03:53,000
בי מסגרות מחסנית הן כמו שיחה ספציפית של תפקוד.

65
00:03:53,000 --> 00:03:57,000
וכמו ערימה, אתה תמיד צריך לחזור

66
00:03:57,000 --> 00:04:03,000
מקריאה לפונקציה לפני שתוכל לרדת לתוך מסגרות מחסנית נמוכות שוב.

67
00:04:03,000 --> 00:04:08,000
אתה לא יכול להיות בר מרכזי שיחת foo שיחה ולחזור לבר ישירות ראשי.

68
00:04:08,000 --> 00:04:14,000
זה תמיד יש לעקוב אחרי הערימה הנכונה דוחפת ומכניסה.

69
00:04:14,000 --> 00:04:18,000
שתי הפעולות, כמו שאמרתי, הן דחיפה ופופ.

70
00:04:18,000 --> 00:04:20,000
אלה מושגים אוניברסליים.

71
00:04:20,000 --> 00:04:26,000
אתה צריך לדעת לדחוף ופופ במונחים של ערימות לא משנים מה.

72
00:04:26,000 --> 00:04:28,000
נצטרך לראות תורים הם קצת שונה.

73
00:04:28,000 --> 00:04:32,000
זה לא ממש יש מושג בינלאומי, אבל הדחיפה ופופ הם אוניברסליות לערימות.

74
00:04:32,000 --> 00:04:34,000
דחיפה פשוט לשים בערימה.

75
00:04:34,000 --> 00:04:37,000
פופ הוא לקחת את הערימה.

76
00:04:37,000 --> 00:04:43,000
ואנחנו רואים כאן שיש לנו מחסנית struct typedef שלנו,

77
00:04:43,000 --> 00:04:46,000
לכן יש לנו מחרוזות char **.

78
00:04:46,000 --> 00:04:51,000
אל תיבהל על ידי כל. **

79
00:04:51,000 --> 00:04:54,000
זה הולך להיות בסופו מערך של מחרוזות

80
00:04:54,000 --> 00:04:58,000
או מערך של מצביעים לתווים, שבי

81
00:04:58,000 --> 00:05:00,000
מצביעים לדמויות נוטים להיות מחרוזות.

82
00:05:00,000 --> 00:05:05,000
זה לא חייב להיות מחרוזות, אבל הנה, הם הולכים עליו מגבלות.

83
00:05:05,000 --> 00:05:08,000
>> יש לנו מערך של מחרוזות.

84
00:05:08,000 --> 00:05:14,000
יש לנו גודל, המייצג כמה אלמנטים כרגע על הערימה,

85
00:05:14,000 --> 00:05:19,000
ולאחר מכן יש לנו את היכולת, שהוא כמה אלמנטים יכול להיות במחסנית.

86
00:05:19,000 --> 00:05:22,000
הקיבולת צריכה להתחיל כמשהו גדול מ 1,

87
00:05:22,000 --> 00:05:27,000
אבל את הגודל עומד להתחיל את דרכו כ0.

88
00:05:27,000 --> 00:05:36,000
עכשיו, יש בעצם שלוש דרכים שונות אתה יכול לחשוב עליו מחסנית.

89
00:05:36,000 --> 00:05:39,000
ובכן, יש כנראה יותר, אבל שתי הדרכים העיקריות הן

90
00:05:39,000 --> 00:05:43,000
אתה יכול ליישם אותו באמצעות מערך, או שאתה יכול ליישם אותו באמצעות רשימה מקושרת.

91
00:05:43,000 --> 00:05:48,000
רשימות מקושרות הן סוג של מה בכך כדי להפוך את ערימות מ.

92
00:05:48,000 --> 00:05:51,000
זה מאוד קל לעשות את מחסנית תוך שימוש ברשימות מקושרות,

93
00:05:51,000 --> 00:05:55,000
אז הנה, אנחנו הולכים להפוך את ערימה באמצעות מערכים,

94
00:05:55,000 --> 00:05:59,000
ולאחר מכן שימוש במערכים, יש גם שתי דרכים שאתה יכול לחשוב על זה.

95
00:05:59,000 --> 00:06:01,000
קודם, כשאמרתי שיש לנו יכולת לערימה,

96
00:06:01,000 --> 00:06:04,000
כדי שנוכל להתאים את רכיב במחסנית.

97
00:06:04,000 --> 00:06:09,000
>> הדרך אחת היא שזה יכול לקרות ברגע שאתה מכה 10 אלמנטים, אז תסיים.

98
00:06:09,000 --> 00:06:13,000
אתה אולי יודע שיש גבול עליון של 10 דברים בעולם

99
00:06:13,000 --> 00:06:16,000
שלעולם לא יצטרכו יותר מ 10 דברים על הערימה שלך,

100
00:06:16,000 --> 00:06:20,000
בכל מקרה אתה יכול להיות חסם עליון על גודל הערימה שלך.

101
00:06:20,000 --> 00:06:23,000
או שאתה יכול להיות יש לך ערימה בלתי מוגבלת,

102
00:06:23,000 --> 00:06:27,000
אבל אם אתה עושה מערך, זה אומר שכל פעם שאתה מכה 10 אלמנטים,

103
00:06:27,000 --> 00:06:29,000
ואז אתה הולך לצריך לגדול ל 20 אלמנטים, וכאשר אתה מכה 20 אלמנטים,

104
00:06:29,000 --> 00:06:33,000
אתה הולך צריך לגדול מערכך עד 30 או 40 אלמנטי אלמנטים.

105
00:06:33,000 --> 00:06:37,000
אתה הולך צריך להגדיל את הקיבולת, וזה מה שאנחנו הולכים לעשות כאן.

106
00:06:37,000 --> 00:06:40,000
בכל פעם שאנחנו מגיעים לגודל המרבי של המחסנית שלנו,

107
00:06:40,000 --> 00:06:46,000
כאשר אנחנו דוחפים משהו אחר, אנחנו הולכים לצורך להגדיל את הקיבולת.

108
00:06:46,000 --> 00:06:50,000
הנה, יש לנו דחיפה הכריז כדחיפת bool (char * str).

109
00:06:50,000 --> 00:06:54,000
* char str הוא המחרוזת שאנחנו דוחפים על המחסנית,

110
00:06:54,000 --> 00:06:58,000
וbool פשוט אומר אם הצלחנו או נכשלנו.

111
00:06:58,000 --> 00:07:00,000
>> איך אפשר להיכשל?

112
00:07:00,000 --> 00:07:04,000
מה הן הנסיבות היחידות שאתה יכול לחשוב על

113
00:07:04,000 --> 00:07:07,000
שבו היינו צריך לחזור שווא?

114
00:07:07,000 --> 00:07:09,000
כן.

115
00:07:09,000 --> 00:07:12,000
[סטודנטים] אם זה מלא ואנחנו משתמשים ביישום מתוחם.

116
00:07:12,000 --> 00:07:17,000
כן, אז איך אנחנו מגדירים-ענינו

117
00:07:17,000 --> 00:07:23,000
אם הוא יהיה מלא ואנחנו משתמשים ביישום מוגבל.

118
00:07:23,000 --> 00:07:26,000
אז אנחנו בהחלט נחזור שווא.

119
00:07:26,000 --> 00:07:31,000
ברגע שפגענו 10 דברים במערך, אנחנו לא יכולים להתאים 11, ואנחנו חוזרים שווא.

120
00:07:31,000 --> 00:07:32,000
מה אם זה בלתי מוגבל? כן.

121
00:07:32,000 --> 00:07:38,000
אם אתה לא יכול להרחיב את המערך מסיבה כלשהי.

122
00:07:38,000 --> 00:07:43,000
כן, אז זיכרון הוא משאב מוגבל,

123
00:07:43,000 --> 00:07:51,000
וסופו של דבר, אם אנו שומרים על דברים שדוחפים על המחסנית שוב ושוב,

124
00:07:51,000 --> 00:07:54,000
אנחנו הולכים לנסות ולהקצות מערך גדול יותר שיתאימו

125
00:07:54,000 --> 00:07:59,000
הקיבולת הגדולה יותר, וmalloc או מה שאנו משתמשים הולכים לחזור שווא.

126
00:07:59,000 --> 00:08:02,000
ובכן, malloc תחזיר null.

127
00:08:02,000 --> 00:08:05,000
>> זכור, בכל פעם שהתקשרת פעם malloc, אתה צריך להיות בדיקה כדי לראות אם הוא

128
00:08:05,000 --> 00:08:12,000
חוזרים ריק או אחר שנמצא תקינות ניכוי.

129
00:08:12,000 --> 00:08:17,000
מכיוון שאנחנו רוצים שנהיה לי ערימה חסרת גבולות,

130
00:08:17,000 --> 00:08:21,000
המקרה היחיד שאנחנו הולכים נחזור שווא הוא אם ננסה

131
00:08:21,000 --> 00:08:26,000
להגדיל את הקיבולת וmalloc או מה שמחזיר שקר.

132
00:08:26,000 --> 00:08:30,000
אז פופ לוקח בלי ויכוחים,

133
00:08:30,000 --> 00:08:37,000
וזה מחזיר את המחרוזת שנמצאה בראש הערימה.

134
00:08:37,000 --> 00:08:41,000
מה לאחרונה נדחף על המחסנית היא מה אבא חוזר,

135
00:08:41,000 --> 00:08:44,000
וזה גם מסיר אותו מהערימה.

136
00:08:44,000 --> 00:08:50,000
ושים לב שהיא מחזירה null אם אין שום דבר בערימה.

137
00:08:50,000 --> 00:08:53,000
תמיד אפשר שהמחסנית ריקה.

138
00:08:53,000 --> 00:08:55,000
ב-Java, אם אתה כבר רגיל לזה, או בשפות אחרות,

139
00:08:55,000 --> 00:09:01,000
מנסה לקפוץ ממחסנית ריקה עלול לגרום לחריגה או משהו.

140
00:09:01,000 --> 00:09:09,000
>> אבל ב-C, null הוא סוג של הרבה מהמקרים כיצד אנו מטפלים בבעיות אלה.

141
00:09:09,000 --> 00:09:13,000
חוזר null הוא איך אנחנו הולכים כדי לסמן שהמחסנית הייתה ריקה.

142
00:09:13,000 --> 00:09:16,000
אנו מספקים קוד שיהיה מבחן הפונקציונלי של הערימה שלך,

143
00:09:16,000 --> 00:09:19,000
ליישם לדחוף ופופ.

144
00:09:19,000 --> 00:09:23,000
זה לא יהיה הרבה קוד.

145
00:09:23,000 --> 00:09:40,000
כך יקר, למעשה, לפני שאנחנו עושים את זה, רמז, רמז,

146
00:09:40,000 --> 00:09:44,000
אם לא ראה את זה, malloc אינו הפונקציה רק

147
00:09:44,000 --> 00:09:47,000
שמקצה זיכרון על הערימה בשבילך.

148
00:09:47,000 --> 00:09:51,000
יש משפחה של פונקציות alloc.

149
00:09:51,000 --> 00:09:53,000
הראשון הוא malloc, שאתה רגיל.

150
00:09:53,000 --> 00:09:56,000
אז יש calloc, שעושה את אותו דבר כמו malloc,

151
00:09:56,000 --> 00:09:59,000
אבל זה יהיה לאפס את הכל בשבילך.

152
00:09:59,000 --> 00:10:04,000
אם אי פעם רצית להגדיר הכל כדי null לאחר mallocing משהו

153
00:10:04,000 --> 00:10:06,000
אתה צריך רק להשתמש calloc במקום הראשון במקום לכתוב

154
00:10:06,000 --> 00:10:09,000
עבור לולאה כדי לאפס את כל הבלוק של זיכרון.

155
00:10:09,000 --> 00:10:15,000
>> Realloc הוא כמו malloc ויש הרבה מקרים מיוחדים,

156
00:10:15,000 --> 00:10:19,000
אבל בעצם מה שעושה הוא realloc

157
00:10:19,000 --> 00:10:24,000
זה לוקח מצביע שכבר הוקצה.

158
00:10:24,000 --> 00:10:27,000
Realloc היא הפונקציה שאתה רוצה לשים לב לכאן.

159
00:10:27,000 --> 00:10:31,000
זה לוקח מצביע שכבר חזר מmalloc.

160
00:10:31,000 --> 00:10:35,000
בואו נגיד שאתה מבקש מmalloc מצביע של 10 בתים.

161
00:10:35,000 --> 00:10:38,000
ואז מאוחר יותר אתה מבין שאתה רוצה 20 בתים,

162
00:10:38,000 --> 00:10:42,000
כך שאתה קורא על realloc שמצביע עם 20 בתים,

163
00:10:42,000 --> 00:10:47,000
וrealloc יעתיק אוטומטית מעל הכל בשבילך.

164
00:10:47,000 --> 00:10:51,000
אם אתה רק בשם malloc שוב, כאילו יש לי גוש של 10 בתים.

165
00:10:51,000 --> 00:10:53,000
עכשיו אני צריך בלוק של 20 בתים,

166
00:10:53,000 --> 00:10:58,000
כך שאם אני malloc 20 בתים, אז יש לי לשם העתקה ידנית על פני 10 בתים מהדבר הראשון

167
00:10:58,000 --> 00:11:01,000
לדבר השני ולאחר מכן חופשי הדבר הראשון.

168
00:11:01,000 --> 00:11:04,000
Realloc יהיה להתמודד עם זה בשבילך.

169
00:11:04,000 --> 00:11:11,000
>> שים לב לחתימה הולכת להיות * מבוטל,

170
00:11:11,000 --> 00:11:15,000
שרק חוזר מצביע לבלוק של זיכרון,

171
00:11:15,000 --> 00:11:17,000
אז void * ptr.

172
00:11:17,000 --> 00:11:22,000
אתה יכול לחשוב על החלל * כמצביע גנרי.

173
00:11:22,000 --> 00:11:27,000
באופן כללי, אתה אף פעם לא להתמודד עם החלל *,

174
00:11:27,000 --> 00:11:30,000
אבל malloc חוזר * מבוטל, ואז זה בדיוק כמו בשימוש

175
00:11:30,000 --> 00:11:34,000
זה בעצם הולך להיות * char.

176
00:11:34,000 --> 00:11:37,000
* החלל הקודם, שהוחזרו על ידי malloc

177
00:11:37,000 --> 00:11:41,000
עכשיו הוא הולך להיות מועבר לrealloc, ולאחר מכן גודל

178
00:11:41,000 --> 00:11:49,000
הוא המספר החדש של בתים שאתה רוצה להקצות, כך היכולת החדשה שלך.

179
00:11:49,000 --> 00:11:57,000
אני אתן לך כמה דקות, ולעשות את זה בשטח שלנו.

180
00:11:57,000 --> 00:12:02,000
התחל עם 1 גרסות.

181
00:12:16,000 --> 00:12:21,000
אני אפסיק אותך אחרי בתקווה על מספיק זמן כדי ליישם את הדחיפה,

182
00:12:21,000 --> 00:12:24,000
ואז אני אתן לך עוד הפסקה לעשות פופ.

183
00:12:24,000 --> 00:12:27,000
אבל זה באמת לא כל כך הרבה קוד בכלל.

184
00:12:27,000 --> 00:12:35,000
רוב הקוד הוא כנראה חומר מתרחב, הרחבת הכושר.

185
00:12:35,000 --> 00:12:39,000
אוקיי, אין לחץ לעשות לחלוטין,

186
00:12:39,000 --> 00:12:47,000
אבל כל עוד אתה מרגיש שאתה בדרך הנכונה, זה טוב.

187
00:12:47,000 --> 00:12:53,000
>> יש למישהו איזה קוד הם מרגישים בנוח איתי מושכים את?

188
00:12:53,000 --> 00:12:59,000
כן, אני אעשה את זה, אבל למישהו יש קוד שאני יכול לרוץ?

189
00:12:59,000 --> 00:13:05,000
אוקיי, אתה יכול להתחיל, לשמור אותו, מה שזה לא?

190
00:13:05,000 --> 00:13:09,000
אני תמיד שוכח צעד זה.

191
00:13:09,000 --> 00:13:15,000
אוקיי, מביט בדחיפה,

192
00:13:15,000 --> 00:13:18,000
אתה רוצה להסביר את הקוד שלך?

193
00:13:18,000 --> 00:13:24,000
[סטודנטים] קודם כל, אני הגדלתי את הגודל.

194
00:13:24,000 --> 00:13:28,000
אני מניח שאולי כדאי לי בכל אופן, אני הגדלתי את הגודל,

195
00:13:28,000 --> 00:13:31,000
ואני רואה אם ​​זה פחות מהיכולת.

196
00:13:31,000 --> 00:13:36,000
ואם זה פחות מהיכולת, אני מוסיף למערך שכבר יש לנו.

197
00:13:36,000 --> 00:13:42,000
ואם זה לא, אני מכפיל את הקיבולת של 2,

198
00:13:42,000 --> 00:13:50,000
ואני להקצות מחדש את מערך מחרוזות למשהו עם גודל קיבולת גדולה יותר כעת.

199
00:13:50,000 --> 00:13:55,000
ואז, אם זה לא יצליח, אני אומר לי המשתמש ותמורת שווא,

200
00:13:55,000 --> 00:14:04,000
ואם זה בסדר, ואז אני מחזיר את המחרוזת במקום החדש.

201
00:14:04,000 --> 00:14:07,000
>> [רוב ב] גם שמנו לב שהייתי מפעיל סיבי האופרטור נחמד כאן

202
00:14:07,000 --> 00:14:09,000
להכפיל אותו ב 2.

203
00:14:09,000 --> 00:14:11,000
זכור, משמרת השמאל תמיד הולכת להיות מוכפלת ב 2.

204
00:14:11,000 --> 00:14:15,000
Shift הימני מחולק על ידי 2, כל עוד אתה זוכר שזה אומר

205
00:14:15,000 --> 00:14:18,000
חלק 2 כמו במספר שלם חלק 2.

206
00:14:18,000 --> 00:14:20,000
זה יכול לחתוך 1 כאן או לשם.

207
00:14:20,000 --> 00:14:26,000
אבל השינוי שהשאיר 1 תמיד הולך להיות מוכפל ב 2,

208
00:14:26,000 --> 00:14:32,000
אלא אם כן אתה הצפת הגבולות השלמים, ואז זה לא יהיה.

209
00:14:32,000 --> 00:14:34,000
הערת צד.

210
00:14:34,000 --> 00:14:39,000
אני אוהב לעשות, זה לא הולך לשנות את הקידוד כל דרך שהיא,

211
00:14:39,000 --> 00:14:48,000
אבל אני רוצה לעשות משהו כזה.

212
00:14:48,000 --> 00:14:51,000
זה באמת הולך לעשות את זה קצת יותר ארוך.

213
00:15:04,000 --> 00:15:08,000
אולי זה לא מקרה המושלם כדי להראות את זה,

214
00:15:08,000 --> 00:15:14,000
אבל אני אוהב אותו הקטע לגושים האלה של

215
00:15:14,000 --> 00:15:17,000
אוקיי, אם זה אם קורה, אז אני הולך לעשות משהו,

216
00:15:17,000 --> 00:15:19,000
ואז הפונקציה נעשתה.

217
00:15:19,000 --> 00:15:22,000
אני לא צריך אז כדי לגלול את עיניי כל הדרך למטה הפונקציה

218
00:15:22,000 --> 00:15:25,000
כדי לראות מה קורה לאחר אחר.

219
00:15:25,000 --> 00:15:27,000
זה אם זה אם קורה, אז אני פשוט אחזור.

220
00:15:27,000 --> 00:15:30,000
יש לו גם הערך המוסף הנחמד של כל דבר מעבר לזה

221
00:15:30,000 --> 00:15:33,000
כעת העביר עזב פעם אחת.

222
00:15:33,000 --> 00:15:40,000
אני כבר לא צריך, אם אי פעם ליד גיחוך התורים ארוכים,

223
00:15:40,000 --> 00:15:45,000
אז 4 הבתים האלה יכולים לעזור, וגם משהו השמאלי יותר הוא,

224
00:15:45,000 --> 00:15:48,000
פחות רגש אותך, אם תרצה להרגיש-בסדר, אני צריך לזכור

225
00:15:48,000 --> 00:15:53,000
אני כרגע בלולאה בתוך בפנים אחר של ללולאה.

226
00:15:53,000 --> 00:15:58,000
בכל מקום שאתה יכול לעשות זה לחזור באופן מיידי, אני די אוהב.

227
00:15:58,000 --> 00:16:05,000
זה לגמרי לא חובה ולא צפוי בכל דרך.

228
00:16:05,000 --> 00:16:12,000
>> [סטודנטים] האם צריך להיות בגודל - במצב להיכשל?

229
00:16:12,000 --> 00:16:19,000
המצב להיכשל כאן הוא שלא הצליח realloc, אז כן.

230
00:16:19,000 --> 00:16:22,000
שים לב איך במצב להיכשל, ככל הנראה,

231
00:16:22,000 --> 00:16:26,000
אלא אם כן דברים בחינם מאוחר יותר, אנחנו תמיד הולכים להיכשל

232
00:16:26,000 --> 00:16:29,000
לא משנה כמה פעמים אנחנו מנסים לדחוף משהו.

233
00:16:29,000 --> 00:16:32,000
אם תמשיכו לדחוף, אנחנו שומרים על גודל הגדלה,

234
00:16:32,000 --> 00:16:36,000
למרות שאנחנו לא לשים שום דבר על המחסנית.

235
00:16:36,000 --> 00:16:39,000
בדרך כלל אנחנו לא להגדיל את הגודל עד

236
00:16:39,000 --> 00:16:43,000
אחרי שהכנסנו אותו בהצלחה במחסנית.

237
00:16:43,000 --> 00:16:50,000
אנחנו נעשה את זה, למשל, או כאן וכאן.

238
00:16:50,000 --> 00:16:56,000
ואז במקום לומר s.size ≤ קיבולת, זה פחות מיכולת,

239
00:16:56,000 --> 00:17:01,000
רק בגלל שאנחנו עברנו בה הכול.

240
00:17:01,000 --> 00:17:07,000
>> ואזכור, המקום היחיד שאנחנו יכולים אולי בתמורת שווא

241
00:17:07,000 --> 00:17:14,000
הוא כאן, שם realloc חזר ריק,

242
00:17:14,000 --> 00:17:19,000
אם אתה זוכר במקרה שגיאה סטנדרטית ו,

243
00:17:19,000 --> 00:17:22,000
אולי אתם יכולים לשקול מקרה זה שבו אתה רוצה להדפיס שגיאה סטנדרטית,

244
00:17:22,000 --> 00:17:26,000
stderr כך fprintf במקום רק להדפיס ישירות לפלט סטנדרטי.

245
00:17:26,000 --> 00:17:31,000
שוב, זה לא ציפייה, אבל אם זה טעות,

246
00:17:31,000 --> 00:17:41,000
הקלד printf, אז אולי כדאי לך לעשות את זה כדי להדפיס שגיאה סטנדרטית במקום פלט סטנדרטי.

247
00:17:41,000 --> 00:17:44,000
>> למישהו יש משהו אחר לשים לב? כן.

248
00:17:44,000 --> 00:17:47,000
[סטודנטים] האם אתה יכול לעבור על [לא ברור]?

249
00:17:47,000 --> 00:17:55,000
[רוב ב '] כן, binariness הממשי שלו או מה זה בדיוק?

250
00:17:55,000 --> 00:17:57,000
[סטודנטים] אז אתה מכפיל אותו ב 2?

251
00:17:57,000 --> 00:17:59,000
[רוב ב '] כן, בעצם.

252
00:17:59,000 --> 00:18:11,000
בארץ בינארי, תמיד יש לנו הסדרה של ספרות שלנו.

253
00:18:11,000 --> 00:18:22,000
הסטה שמאלית זו עד ליום 1 בעצם מוסיפה אותו כאן על צד ימין.

254
00:18:22,000 --> 00:18:25,000
חזור לזה, רק לזכור שכל הדבר בינארי

255
00:18:25,000 --> 00:18:28,000
הוא כוח של 2, כך שזה מייצג 2 ל 0,

256
00:18:28,000 --> 00:18:30,000
זה 2 ל1, 2 לזה 2.

257
00:18:30,000 --> 00:18:33,000
על ידי הוספת 0 לצד ימין עכשיו, אנחנו פשוט לעבור על הכול.

258
00:18:33,000 --> 00:18:38,000
מה הייתה אמור להיות 2 ל 0 הוא עכשיו 2 ל 1, הוא 2 עד 2.

259
00:18:38,000 --> 00:18:41,000
בצד ימין שהוכנסנו

260
00:18:41,000 --> 00:18:44,000
בהכרח הולך להיות 0,

261
00:18:44,000 --> 00:18:46,000
וזה הגיוני.

262
00:18:46,000 --> 00:18:49,000
אם אי פעם להכפיל מספר ב 2, זה לא הולך בסופו מוזר,

263
00:18:49,000 --> 00:18:54,000
כך 2 עד 0 המקום צריכים להיות 0,

264
00:18:54,000 --> 00:18:59,000
וזה מה שאני חצי הזהרתי לפני הוא אם קורה להסיט

265
00:18:59,000 --> 00:19:01,000
מעבר למספר הביטים במספר שלם,

266
00:19:01,000 --> 00:19:04,000
אז 1 זה הולך בסופו נוסע.

267
00:19:04,000 --> 00:19:10,000
זה דאגה רק אם קורה לך להיות התמודדות עם קיבולות גדולות באמת.

268
00:19:10,000 --> 00:19:15,000
אבל בנקודה הזאת, אז יש לך עסק עם מערך של מליארד דברים,

269
00:19:15,000 --> 00:19:25,000
אשר עשוי שלא להתאים לזיכרון בכל מקרה.

270
00:19:25,000 --> 00:19:31,000
>> עכשיו אנחנו יכולים להגיע לפופ, וזה אפילו יותר קל.

271
00:19:31,000 --> 00:19:36,000
אתה יכול לעשות את זה כמו שאם קורה לך לקפוץ כל חבורה,

272
00:19:36,000 --> 00:19:38,000
ועכשיו אתה במחצית הקיבולת שוב.

273
00:19:38,000 --> 00:19:42,000
אתה יכול realloc לכווץ את כמות הזיכרון שיש לך,

274
00:19:42,000 --> 00:19:47,000
אבל אתה לא צריך לדאוג בקשר לזה, ולכן במקרה realloc רק הולך להיות

275
00:19:47,000 --> 00:19:50,000
גדל זיכרון, לא מתכווץ זיכרון,

276
00:19:50,000 --> 00:19:59,000
שהוא הולך לעשות סופר פופ קל.

277
00:19:59,000 --> 00:20:02,000
עכשיו תורים, שהם הולכים להיות כמו ערימות,

278
00:20:02,000 --> 00:20:06,000
אבל כדי שאתה מוציא את הדברים החוצה הוא הפוך.

279
00:20:06,000 --> 00:20:10,000
הדוגמא הטיפוסית של תור היא קו,

280
00:20:10,000 --> 00:20:12,000
אז אני מניח שאם היית אנגלי, הייתי אומר

281
00:20:12,000 --> 00:20:17,000
דוגמה טיפוסית של תור היא תור.

282
00:20:17,000 --> 00:20:22,000
אז כמו קו, אם אתה האדם הראשון בשורה,

283
00:20:22,000 --> 00:20:24,000
אתה מצפה להיות האדם הראשון מחוץ לקו.

284
00:20:24,000 --> 00:20:31,000
אם אתה האדם האחרון בשורה, אתה הולך להיות האדם האחרון לתיקון.

285
00:20:31,000 --> 00:20:35,000
אנו קוראים כי דפוס FIFO, בעוד שמחסנית הייתה דפוס LIFO.

286
00:20:35,000 --> 00:20:40,000
המילים האלה הן די אוניברסליות.

287
00:20:40,000 --> 00:20:46,000
>> כמו ערימות ולא כמו מערכים, תורים אינם מאפשרים בדרך כלל גישה לאלמנטים באמצע.

288
00:20:46,000 --> 00:20:50,000
כאן, מחסנית, יש לנו דחיפה ופופ.

289
00:20:50,000 --> 00:20:54,000
כאן, אנו קורים שקראנו להם וEnqueue dequeue.

290
00:20:54,000 --> 00:20:58,000
שמעתי גם קראו משמרת וunshift.

291
00:20:58,000 --> 00:21:02,000
שמעתי אנשים אומרים דחיפה ופופ לחלים גם על תורים.

292
00:21:02,000 --> 00:21:05,000
שמעתי להוסיף, להסיר,

293
00:21:05,000 --> 00:21:11,000
אז דחף ופופ, אם אתה מדבר על ערימות, אתה דוחף ומכניס.

294
00:21:11,000 --> 00:21:16,000
אם אתה מדבר על תורים, אתה יכול לבחור את המילים שברצונך להשתמש

295
00:21:16,000 --> 00:21:23,000
להכנסה והוצאה, ואין הסכמה על מה שהיא צריכה להיקרא.

296
00:21:23,000 --> 00:21:27,000
אבל הנה, יש לנו Enqueue וdequeue.

297
00:21:27,000 --> 00:21:37,000
עכשיו, struct נראה כמעט זהה לstruct המחסנית.

298
00:21:37,000 --> 00:21:40,000
אבל אנחנו צריכים לעקוב אחר הראש.

299
00:21:40,000 --> 00:21:44,000
אני מניח שזה אומר כאן, אבל למה אנחנו צריכים את הראש?

300
00:21:53,000 --> 00:21:57,000
אבות הטיפוס הוא בעצם זהה ללדחוף ופופ.

301
00:21:57,000 --> 00:21:59,000
אתה יכול לחשוב על זה כעל דחיפה ופופ.

302
00:21:59,000 --> 00:22:08,000
ההבדל היחיד הוא הפופ חוזר-במקום שעבר הוא חזרה הראשונה.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, או משהו.

304
00:22:12,000 --> 00:22:14,000
והנה ההתחלה.

305
00:22:14,000 --> 00:22:17,000
התור שלנו הוא מלא לחלוטין, כך שיש ארבעה יסודות שבו.

306
00:22:17,000 --> 00:22:21,000
סוף התור שלנו הוא כרגע 2,

307
00:22:21,000 --> 00:22:24,000
ועכשיו אנחנו הולכים להכניס משהו אחר.

308
00:22:24,000 --> 00:22:29,000
>> כאשר אנו רוצים להוסיף משהו אחר, מה שעשינו לגרסת המחסנית

309
00:22:29,000 --> 00:22:36,000
הוא הרחבנו את הבלוק של זיכרון שלנו.

310
00:22:36,000 --> 00:22:40,000
מה הבעיה עם זה?

311
00:22:40,000 --> 00:22:45,000
[סטודנטים] אתה מעביר את 2.

312
00:22:45,000 --> 00:22:51,000
מה שאמרתי קודם על סוף התור,

313
00:22:51,000 --> 00:22:57,000
זה לא הגיוני שאנחנו מתחילים ב1,

314
00:22:57,000 --> 00:23:01,000
אז אנחנו רוצים dequeue 1, אז dequeue 3, אז dequeue 4,

315
00:23:01,000 --> 00:23:05,000
אז dequeue 2, אז dequeue זה.

316
00:23:05,000 --> 00:23:08,000
אנחנו לא יכולים להשתמש realloc עכשיו,

317
00:23:08,000 --> 00:23:11,000
או לכל הפחות, יש לך להשתמש realloc בדרך אחרת.

318
00:23:11,000 --> 00:23:15,000
אבל כנראה שאתה לא צריך רק להשתמש realloc.

319
00:23:15,000 --> 00:23:18,000
אתה הולך באופן ידני להעתיק את הזיכרון שלך.

320
00:23:18,000 --> 00:23:21,000
>> ישנן שתי פונקציות להעתקת זיכרון.

321
00:23:21,000 --> 00:23:25,000
יש memcopy וmemmove.

322
00:23:25,000 --> 00:23:29,000
אני כרגע קורא את הדפים כדי לראות איזה מהם אתה הולך רוצה להשתמש.

323
00:23:29,000 --> 00:23:35,000
אוקיי, memcopy, ההבדל הוא

324
00:23:35,000 --> 00:23:38,000
שmemcopy וmemmove, אחד מטפל במקרה בצורה נכונה

325
00:23:38,000 --> 00:23:41,000
לאן אתה מעתיק לתוך אזור שקורה לחפיפת האזור

326
00:23:41,000 --> 00:23:46,000
אתה מעתיק מ.

327
00:23:46,000 --> 00:23:50,000
Memcopy לא להתמודד עם זה. Memmove עושה.

328
00:23:50,000 --> 00:23:59,000
אתה יכול לחשוב על הבעיה כ-

329
00:23:59,000 --> 00:24:09,000
נניח שאני רוצה להעתיק את הבחור הזה,

330
00:24:09,000 --> 00:24:13,000
אלה ארבעה לבחור הזה.

331
00:24:13,000 --> 00:24:16,000
בסוף, מה המערך צריך להיראות

332
00:24:16,000 --> 00:24:26,000
לאחר ההעתקה היא 2, 1, 2, 1, 3, 4, ולאחר מכן כמה דברים בסוף.

333
00:24:26,000 --> 00:24:29,000
אבל זה תלוי בהסדר שבו אנחנו בעצם להעתיק,

334
00:24:29,000 --> 00:24:32,000
שהרים אם אנחנו לא מחשיבים את העובדה שהאזור שאנו מעתיקים אל

335
00:24:32,000 --> 00:24:35,000
חופף אחד אנחנו מעתיקים מ,

336
00:24:35,000 --> 00:24:46,000
אז אנחנו יכולים לעשות כמו התחלה כאן, להעתיק את 2 למקום שאנחנו רוצים ללכת,

337
00:24:46,000 --> 00:24:52,000
לאחר מכן להעביר את המצביעים שלנו קדימה.

338
00:24:52,000 --> 00:24:56,000
>> עכשיו אנחנו הולכים להיות כאן וכאן, ועכשיו אנחנו רוצים להעתיק

339
00:24:56,000 --> 00:25:04,000
הבחור הזה על הבחור הזה ולהעביר את המצביעים שלנו קדימה.

340
00:25:04,000 --> 00:25:07,000
מה שאנחנו הולכים בסופו של דבר מקבלים הוא 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
במקום 2 המתאימים, 1, 2, 1, 3, 4, כי

342
00:25:10,000 --> 00:25:15,000
2, 1 הגיע לקיצת 3 המקוריים, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove ידיות בצורה נכונה.

344
00:25:19,000 --> 00:25:23,000
במקרה זה, בעצם רק משתמש תמיד memmove

345
00:25:23,000 --> 00:25:26,000
משום שהוא מטפל בזה בצורה נכונה.

346
00:25:26,000 --> 00:25:29,000
זה בדרך כלל לא לבצע כל רע.

347
00:25:29,000 --> 00:25:32,000
הרעיון הוא במקום להתחיל מההתחלה וההעתקה בדרך זו

348
00:25:32,000 --> 00:25:35,000
כמו שאנחנו כאן, זה מתחיל מהסוף ומעתיק ב,

349
00:25:35,000 --> 00:25:38,000
ובמקרה כזה, אתה לא יכול יש לי בעיה.

350
00:25:38,000 --> 00:25:40,000
לא ביצועים יש לאיבוד.

351
00:25:40,000 --> 00:25:47,000
השתמש תמיד memmove. לא לדאוג memcopy.

352
00:25:47,000 --> 00:25:51,000
וזה מקום שאתה הולך להיות בנפרד לmemmove

353
00:25:51,000 --> 00:26:01,000
עטוף סביב חלק מהתור שלך.

354
00:26:01,000 --> 00:26:04,000
אל דאגה, אם לא נעשתה לחלוטין.

355
00:26:04,000 --> 00:26:10,000
זה קשה יותר ממחסנית, לדחוף, ופופ.

356
00:26:10,000 --> 00:26:15,000
>> מישהו יש לך קוד שנוכל לעבוד איתו?

357
00:26:15,000 --> 00:26:21,000
גם אם לחלוטין לא שלם?

358
00:26:21,000 --> 00:26:23,000
[סטודנטים] כן, זה לחלוטין לא מושלם, אם כי.

359
00:26:23,000 --> 00:26:27,000
לחלוטין לא שלם הוא בסדר, כל עוד אנחנו יכולים, שתשמרו את העדכון?

360
00:26:27,000 --> 00:26:32,000
אני שוכח שכל פעם אחת.

361
00:26:32,000 --> 00:26:39,000
אוקיי, מתעלם ממה שקורה כאשר אנחנו צריכים לשנות את גודל דברים.

362
00:26:39,000 --> 00:26:42,000
לחלוטין להתעלם מגודל.

363
00:26:42,000 --> 00:26:49,000
הסבר את הקוד הזה.

364
00:26:49,000 --> 00:26:54,000
אני בודק קודם כל אם הגודל הוא פחות מהעותק הראשון של כל

365
00:26:54,000 --> 00:27:01,000
ואז אחרי זה, אני מכניס, אני לוקח את הראש + גודל,

366
00:27:01,000 --> 00:27:05,000
ואני מקפיד שעוטף את הקיבולת של המערך,

367
00:27:05,000 --> 00:27:08,000
ואני מכניס את המחרוזת החדשה במיקום זה.

368
00:27:08,000 --> 00:27:12,000
ואז אני מגדיל את הגודל והחזר אמיתי.

369
00:27:12,000 --> 00:27:22,000
>> [רוב ב] זה בהחלט אחד מאותם מקרים שבו אתה הולך רוצה להיות באמצעות משרד ביטחון.

370
00:27:22,000 --> 00:27:25,000
כל סוג של מקרה שבו יש לך עוטף מסביב, אם אתה חושב שעוטף מסביב,

371
00:27:25,000 --> 00:27:29,000
המחשבה המיידית צריכה להיות אופנתית.

372
00:27:29,000 --> 00:27:36,000
כאופטימיזציה מהירה / להפוך את שורת הקוד האחת שלך קצרה יותר,

373
00:27:36,000 --> 00:27:42,000
אתה שם לב שהשורה הבאה זה אחד מייד

374
00:27:42,000 --> 00:27:53,000
הוא בדיוק גודל + +, אז לך למזג את זה לתוך הקו הזה, גודל + +.

375
00:27:53,000 --> 00:27:58,000
עכשיו כאן למטה, יש לנו מקרה

376
00:27:58,000 --> 00:28:01,000
שם אין לנו מספיק זיכרון,

377
00:28:01,000 --> 00:28:05,000
כך אנו מגדילים את היכולת שלנו על ידי 2.

378
00:28:05,000 --> 00:28:09,000
אני מניח שאפשר לה בעיה כאן, אבל אנחנו יכולים להתעלם מזה עכשיו,

379
00:28:09,000 --> 00:28:13,000
בו אם אתה לא להגדיל את הקיבולת שלך,

380
00:28:13,000 --> 00:28:18,000
ואז אתה הולך לרוצה להפחית את היכולת שלך על ידי 2 שוב.

381
00:28:18,000 --> 00:28:24,000
הערה קצרה נוספת היא בדיוק כמו שאתה יכול לעשות + =,

382
00:28:24,000 --> 00:28:30,000
אתה יכול גם לעשות << =.

383
00:28:30,000 --> 00:28:43,000
כמעט כל דבר יכול לעבור לפני שווים, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * החדש הוא הבלוק החדש שלנו בזיכרון.

385
00:28:52,000 --> 00:28:55,000
הו, כאן.

386
00:28:55,000 --> 00:29:02,000
>> מה אנשים חושבים על הסוג של הבלוק החדש שלנו בזיכרון?

387
00:29:02,000 --> 00:29:06,000
[סטודנטים] זה צריך להיות char **.

388
00:29:06,000 --> 00:29:12,000
מחשבה לאחור לstruct שלנו כאן,

389
00:29:12,000 --> 00:29:14,000
מייתרים הם מה שאנחנו הקצאה מחדש.

390
00:29:14,000 --> 00:29:21,000
אנחנו עושים אחסון דינמי חדש לחלוטין עבור האלמנטים בתור.

391
00:29:21,000 --> 00:29:25,000
מה שאנחנו הולכים להיות הקצאה למייתרים שלך הוא מה שאנחנו mallocing עכשיו,

392
00:29:25,000 --> 00:29:30,000
וכל כך חדש היא הולך להיות char **.

393
00:29:30,000 --> 00:29:34,000
זה הולך להיות מערך של מחרוזות.

394
00:29:34,000 --> 00:29:38,000
אז מה שקורה תחתו אנחנו הולכים בתמורת שווא?

395
00:29:38,000 --> 00:29:41,000
[סטודנטים] האם עלינו לעשות * char?

396
00:29:41,000 --> 00:29:44,000
[רוב ב '] כן, שיחה טובה.

397
00:29:44,000 --> 00:29:46,000
[סטודנטים] מה זה היה?

398
00:29:46,000 --> 00:29:49,000
[רוב ב '] רצינו לעשות גודל של * char בגלל שאנחנו כבר לא,

399
00:29:49,000 --> 00:29:53,000
זה הייתי למעשה להיות בעיה גדולה מאוד, כי sizeof (char) יהיה 1.

400
00:29:53,000 --> 00:29:55,000
* Char sizeof הולך להיות 4,

401
00:29:55,000 --> 00:29:58,000
כל כך הרבה פעמים כשאתה עוסק בints,

402
00:29:58,000 --> 00:30:01,000
אתם נוטים לצאת מזה בגלל גודל של int וגודל של int *

403
00:30:01,000 --> 00:30:04,000
על מערכה 32-bit הולכים להיות אותו הדבר.

404
00:30:04,000 --> 00:30:09,000
אבל כאן, sizeof (char) וsizeof (char *) עכשיו הולכים להיות אותו הדבר.

405
00:30:09,000 --> 00:30:15,000
>> מה הן הנסיבות שבו אנחנו בתמורת שווא?

406
00:30:15,000 --> 00:30:17,000
[סטודנטים] חדש הוא ריק.

407
00:30:17,000 --> 00:30:23,000
כן, אם חדש הוא ריק, אנחנו חוזרים שקר,

408
00:30:23,000 --> 00:30:34,000
ואני הולך לזרוק כאן למטה-

409
00:30:34,000 --> 00:30:37,000
[סטודנטים] [לא ברור]

410
00:30:37,000 --> 00:30:39,000
[רוב ב '] כן, זה בסדר.

411
00:30:39,000 --> 00:30:46,000
אתה יכול גם לעשות 2 פעמים קיבולת או שינוי קיבולת 1 ואז רק הניח אותו כאן או משהו כזה.

412
00:30:46,000 --> 00:30:52,000
אנחנו נעשה את זה כמו שהיינו לנו את זה.

413
00:30:52,000 --> 00:30:56,000
קיבולת >> = 1.

414
00:30:56,000 --> 00:31:08,000
ואתה לעולם לא צריך לדאוג לאבד את מקומו של 1

415
00:31:08,000 --> 00:31:12,000
בגלל שעזבת מוזז על ידי 1, כך המקום של 1 הוא בהכרח 0,

416
00:31:12,000 --> 00:31:16,000
כל כך נכון הסטה של ​​1, אתה עדיין הולך להיות בסדר.

417
00:31:16,000 --> 00:31:19,000
[סטודנטים] האם אתה צריך לעשות את זה לפני התמורה?

418
00:31:19,000 --> 00:31:29,000
[רוב ב '] כן, זה כבר ממש לא הגיוני.

419
00:31:29,000 --> 00:31:36,000
>> כעת אניח שאנחנו הולכים בסופו חוזר אמיתי עד הסוף.

420
00:31:36,000 --> 00:31:39,000
הדרך שאנחנו הולכים לעשות memmoves אלה,

421
00:31:39,000 --> 00:31:45,000
אנחנו צריכים להיות זהירים עם איך אנחנו עושים אותם.

422
00:31:45,000 --> 00:31:50,000
למישהו יש הצעות לאופן בו אנו עושים אותם?

423
00:32:17,000 --> 00:32:21,000
הנה ההתחלה שלנו.

424
00:32:21,000 --> 00:32:28,000
באופן בלתי נמנע, אנחנו רוצים להתחיל בתחילה שוב

425
00:32:28,000 --> 00:32:35,000
ודברים בהעתקה משם, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
איך אתה עושה את זה?

427
00:32:41,000 --> 00:32:52,000
ראשית, יש לי להסתכל על דף האדם לmemmove שוב.

428
00:32:52,000 --> 00:32:57,000
Memmove, סדר של טענות הוא תמיד חשוב.

429
00:32:57,000 --> 00:33:01,000
אנחנו רוצים לייעדנו ראשונים, שניים מקור שלישי בגודל.

430
00:33:01,000 --> 00:33:06,000
יש הרבה פונקציות שאשיבנו מקור ויעד.

431
00:33:06,000 --> 00:33:11,000
יעד, מקור נוטה להיות עקבי במידה מה.

432
00:33:17,000 --> 00:33:21,000
מהלך, מה שהוא חוזר?

433
00:33:21,000 --> 00:33:27,000
זה מחזיר את מצביע ליעד, מכל סיבה שייתכן שתרצה את זה.

434
00:33:27,000 --> 00:33:32,000
אני יכול לקרוא אותו תמונה, אבל אנחנו רוצים לעבור ליעד שלנו.

435
00:33:32,000 --> 00:33:35,000
>> מה היעד שלנו הולך להיות?

436
00:33:35,000 --> 00:33:37,000
[סטודנטים] חדש.

437
00:33:37,000 --> 00:33:39,000
[רוב ב '] כן, ושבו אנחנו מעתיקים?

438
00:33:39,000 --> 00:33:43,000
הדבר הראשון שאנחנו מעתיקים זה 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
מה זה, 1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
מה הכתובת של זה 1?

441
00:33:55,000 --> 00:33:58,000
מה הכתובת של 1?

442
00:33:58,000 --> 00:34:01,000
[סטודנטים] [לא ברור]

443
00:34:01,000 --> 00:34:03,000
[רוב ב] ראש + הכתובת של האלמנט הראשון.

444
00:34:03,000 --> 00:34:05,000
איך אנחנו מגיעים לאלמנט הראשון במערך?

445
00:34:05,000 --> 00:34:10,000
[סטודנטים] תור.

446
00:34:10,000 --> 00:34:15,000
[רוב ב '] כן, q.strings.

447
00:34:15,000 --> 00:34:20,000
זכור, כאן, הראש שלנו הוא 1.

448
00:34:20,000 --> 00:34:24,000
לעזאזל. אני פשוט חושב שזה קסם,

449
00:34:24,000 --> 00:34:29,000
הנה, הראש שלנו הוא 1. אני הולך לשנות את הצבע שלי יותר מדי.

450
00:34:29,000 --> 00:34:36,000
וכאן הוא מחרוזות.

451
00:34:36,000 --> 00:34:41,000
זה, אנחנו יכולים גם לכתוב אותו כמו שעשינו כאן

452
00:34:41,000 --> 00:34:43,000
עם ראשים + q.strings.

453
00:34:43,000 --> 00:34:51,000
הרבה אנשים גם לכתוב את זה וq.strings [ראש].

454
00:34:51,000 --> 00:34:55,000
זה לא באמת פחות יעיל.

455
00:34:55,000 --> 00:34:58,000
אתה יכול לחשוב על זה כאתם ביטול ההפניה ולאחר מכן מקבלים את הכתובת של,

456
00:34:58,000 --> 00:35:04,000
אבל המהדר הולך לתרגם את זה למה שהיינו לפני מקרה, q.strings + ראש.

457
00:35:04,000 --> 00:35:06,000
כך או כך אתה רוצה לחשוב על זה.

458
00:35:06,000 --> 00:35:11,000
>> וכמה בתים שאנחנו רוצים להעתיק?

459
00:35:11,000 --> 00:35:15,000
[סטודנטים] קיבולת - ראש.

460
00:35:15,000 --> 00:35:18,000
קיבולת - ראש.

461
00:35:18,000 --> 00:35:21,000
ואז אתה תמיד יכול לכתוב את דוגמה

462
00:35:21,000 --> 00:35:23,000
כדי להבין אם זה נכון.

463
00:35:23,000 --> 00:35:26,000
זה [סטודנטים] צריכים להיות מחולקים על ידי 2 אז.

464
00:35:26,000 --> 00:35:30,000
כן, אז אני מניח שאנחנו יכולים להשתמש בגודל.

465
00:35:30,000 --> 00:35:35,000
עדיין יש לנו גודל רווחת

466
00:35:35,000 --> 00:35:39,000
באמצעות גודל, יש לנו גודל שווה ל 4.

467
00:35:39,000 --> 00:35:42,000
הגודל שלנו הוא 4. הראש שלנו הוא 1.

468
00:35:42,000 --> 00:35:46,000
אנחנו רוצים להעתיק 3 האלמנטים הללו.

469
00:35:46,000 --> 00:35:54,000
זה השפיות לבדוק גודל ש-- הראש הוא נכון 3.

470
00:35:54,000 --> 00:35:58,000
ואחזור לכאן, כמו שאמרנו קודם,

471
00:35:58,000 --> 00:36:00,000
אם אשתמש בקיבולת, אז הייתי צריך לחלק ב 2

472
00:36:00,000 --> 00:36:04,000
כי אנחנו כבר גדלנו היכולת שלנו, אז במקום זה, אנחנו הולכים להשתמש בגודל.

473
00:36:11,000 --> 00:36:13,000
כי עותקים שמנה.

474
00:36:13,000 --> 00:36:18,000
עכשיו, אנחנו צריכים להעתיק את החלק השני, החלק שנותר מההתחלה.

475
00:36:18,000 --> 00:36:28,000
>> זה הולך memmove לאיזה תפקיד?

476
00:36:28,000 --> 00:36:32,000
[סטודנטים] גודל פלוס - ראש.

477
00:36:32,000 --> 00:36:38,000
כן, אז יש לנו כבר העתיקו בגודל - בתי ראש,

478
00:36:38,000 --> 00:36:43,000
ואז שבו אנחנו רוצים להעתיק את הבתים שנותרו הוא חדש

479
00:36:43,000 --> 00:36:48,000
ולאחר מכן גודל מינוס היטב, את מספר הבתים שכבר להעתיק פנימה

480
00:36:48,000 --> 00:36:52,000
ואז שבו אנחנו מעתיקים?

481
00:36:52,000 --> 00:36:54,000
[סטודנטים] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[רוב ב '] כן, q.strings.

483
00:36:56,000 --> 00:37:02,000
אנחנו יכולים גם לעשות וq.strings [0].

484
00:37:02,000 --> 00:37:05,000
זה הרבה פחות נפוץ מאשר זה.

485
00:37:05,000 --> 00:37:14,000
אם זה רק הולך להיות 0, אז אתה נוטה לראות q.strings.

486
00:37:14,000 --> 00:37:16,000
זה המקום שבי אנו מעתיקים מ.

487
00:37:16,000 --> 00:37:18,000
כמה בתים נשארו לנו להעתיק? >> [סטודנטים] 10.

488
00:37:18,000 --> 00:37:20,000
נכון.

489
00:37:20,000 --> 00:37:25,000
[סטודנטים] האם יש לנו להכפיל 5-10 פעמים את הגודל של הבתים או משהו?

490
00:37:25,000 --> 00:37:30,000
כן, אז זה המקום שבי-מה בדיוק אנחנו מעתיקים?

491
00:37:30,000 --> 00:37:32,000
[סטודנטים] [לא ברור]

492
00:37:32,000 --> 00:37:34,000
מהו הסוג של הדבר שאנו מעתיקים?

493
00:37:34,000 --> 00:37:36,000
[סטודנטים] [לא ברור]

494
00:37:36,000 --> 00:37:41,000
כן, אז * של char שאנו מעתיקים, אנחנו לא יודעים איפה אלה מגיעים.

495
00:37:41,000 --> 00:37:47,000
ובכן, שבו הם מצביעים, כמו מייתרים, אנחנו בסופו מעלה אותה על התור

496
00:37:47,000 --> 00:37:49,000
או enqueuing על התור.

497
00:37:49,000 --> 00:37:51,000
איפה אלה שבאים, אין לנו מושג.

498
00:37:51,000 --> 00:37:56,000
אנחנו פשוט צריכים לעקוב אחר * char של עצמם.

499
00:37:56,000 --> 00:38:00,000
אנחנו לא רוצים להעתיק גודל - בתי ראש.

500
00:38:00,000 --> 00:38:03,000
אנחנו רוצים להעתיק גודל - ראש char * s,

501
00:38:03,000 --> 00:38:11,000
כך אנחנו הולכים להכפיל את זה על ידי sizeof (char *).

502
00:38:11,000 --> 00:38:17,000
כאן למטה, ראש * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [סטודנטים] מה [לא ברור]?

504
00:38:24,000 --> 00:38:26,000
זה ממש כאן?

505
00:38:26,000 --> 00:38:28,000
[סטודנטים] לא, מתחת לזה, גודל - ראש.

506
00:38:28,000 --> 00:38:30,000
[רוב ב] זכות זו כאן?

507
00:38:30,000 --> 00:38:32,000
פעולות אריתמטיות על מצביעים.

508
00:38:32,000 --> 00:38:35,000
איך פעולות אריתמטיות על מצביעים הולכות לעבוד הוא

509
00:38:35,000 --> 00:38:40,000
זה באופן אוטומטי על ידי מכפיל את הגודל מהסוג שיש לנו עסק איתו.

510
00:38:40,000 --> 00:38:46,000
בדיוק כמו כאן, חדש + (גודל - ראש)

511
00:38:46,000 --> 00:38:56,000
זה בדיוק שווה ערך ל [גודל - הראש] וחדש

512
00:38:56,000 --> 00:39:00,000
עד שאנחנו מצפים שנפעל כהלכה,

513
00:39:00,000 --> 00:39:04,000
שכן אם יש לנו עסק עם מערך int, אז אנחנו לא אינדקס על ידי-int

514
00:39:04,000 --> 00:39:07,000
או אם זה בגודל של 5 ואתה רוצה אלמנט 4, אז אנחנו אינדקס לתוך

515
00:39:07,000 --> 00:39:10,000
מערך int [4].

516
00:39:10,000 --> 00:39:14,000
אתה אל, [4] * גודל של int.

517
00:39:14,000 --> 00:39:21,000
שמטפל בו באופן אוטומטי, ומקרה זה

518
00:39:21,000 --> 00:39:29,000
פשוטו כמשמעו, הוא שווה ערך, כך תחביר הסוגר

519
00:39:29,000 --> 00:39:34,000
פשוט הולך להיות מומר לזה ברגע שאתה לקמפל.

520
00:39:34,000 --> 00:39:38,000
זה משהו שאתה צריך להיות זהיר של

521
00:39:38,000 --> 00:39:42,000
כשאתה מוסיף גודל - ראש

522
00:39:42,000 --> 00:39:45,000
אתה מוסיף לא בייט אחד.

523
00:39:45,000 --> 00:39:53,000
אתה מוסיף * char אחד, שיכול להיות אחד בתים או משהו כזה.

524
00:39:53,000 --> 00:39:56,000
>> שאלות אחרות?

525
00:39:56,000 --> 00:40:04,000
אוקיי, dequeue הולך להיות קל יותר.

526
00:40:04,000 --> 00:40:11,000
אני אתן לך דקה ליישום.

527
00:40:11,000 --> 00:40:18,000
אה, ואני מניח שזה אותו המצב שבו

528
00:40:18,000 --> 00:40:21,000
מה מקרה Enqueue, אם אנחנו enqueuing ריק,

529
00:40:21,000 --> 00:40:24,000
אולי אנחנו רוצים לטפל בזה, אולי לא.

530
00:40:24,000 --> 00:40:27,000
אנחנו לא נעשינו את זה שוב כאן, אבל כמו מקרה המחסנית שלנו.

531
00:40:27,000 --> 00:40:34,000
אם אנחנו Enqueue ריק, יתכן שעלינו להתעלם ממנו.

532
00:40:34,000 --> 00:40:40,000
למישהו יש איזה קוד שאני יכול לרוץ?

533
00:40:40,000 --> 00:40:45,000
[סטודנטים] יש לי רק dequeue.

534
00:40:45,000 --> 00:40:56,000
גרסה 2 היא ש- בסדר.

535
00:40:56,000 --> 00:40:59,000
אתה רוצה להסביר?

536
00:40:59,000 --> 00:41:01,000
[סטודנטים] ראשית, לך לוודא שיש משהו בתור

537
00:41:01,000 --> 00:41:07,000
ושהגודל הוא יורד ב 1.

538
00:41:07,000 --> 00:41:11,000
אתה צריך לעשות את זה, ואז אתה מחזיר את הראש

539
00:41:11,000 --> 00:41:13,000
ואז להזיז את הראש למעלה 1.

540
00:41:13,000 --> 00:41:19,000
אוקיי, אז יש פינת מקרה אנחנו צריכים לשקול. כן.

541
00:41:19,000 --> 00:41:24,000
[סטודנטים] אם הראש שלך הוא באלמנט האחרון,

542
00:41:24,000 --> 00:41:26,000
אז אתה לא רוצה את הראש להצביע מחוץ למערך.

543
00:41:26,000 --> 00:41:29,000
>> כן, אז ברגע שראש פוגע בסופו של המערך שלנו,

544
00:41:29,000 --> 00:41:35,000
כאשר אנו dequeue, הראש שלנו צריך להיות חזרה לmodded 0.

545
00:41:35,000 --> 00:41:40,000
למרבה הצער, אנחנו לא יכולים לעשות את זה בצעד אחד.

546
00:41:40,000 --> 00:41:44,000
אני מניח שהייתי כנראה הדרך לתקן את זה הוא

547
00:41:44,000 --> 00:41:52,000
זה הולך להיות * char, מה שאנחנו חוזרים,

548
00:41:52,000 --> 00:41:55,000
מה השם המשתנה שלך רוצה להיות.

549
00:41:55,000 --> 00:42:02,000
אז אנחנו רוצים mod הראש ביכולת שלנו

550
00:42:02,000 --> 00:42:10,000
ואז לחזור להשרות.

551
00:42:10,000 --> 00:42:14,000
הרבה אנשים כאן שהם עלולים לעשות-

552
00:42:14,000 --> 00:42:19,000
זה מקרה של את תראה שאנשים עושים אם ראש

553
00:42:19,000 --> 00:42:29,000
גדול מקיבולת, לעשות את הראש - קיבולת.

554
00:42:29,000 --> 00:42:36,000
וזה פשוט עובד סביב מה mod הוא.

555
00:42:36,000 --> 00:42:41,000
ראש mod = קיבולת היא הרבה יותר נקיה

556
00:42:41,000 --> 00:42:51,000
מעטיפה סביב מאשר אם הראש גדול יותר מראש הקיבולת - קיבולת.

557
00:42:51,000 --> 00:42:56,000
>> שאלות?

558
00:42:56,000 --> 00:43:02,000
אוקיי, הדבר האחרון שנשארנו לנו הוא הרשימה המקושרת שלנו.

559
00:43:02,000 --> 00:43:07,000
אתה עשוי לשמש לחלק מהתנהגות הרשימה המקושרת אם עשה

560
00:43:07,000 --> 00:43:11,000
רשימות מקושרות בטבלאות hash שלך, אם אתה עשית שולחן חשיש.

561
00:43:11,000 --> 00:43:15,000
אני ממליץ בחום לעשות שולחן חשיש.

562
00:43:15,000 --> 00:43:17,000
ייתכן שכבר עשה trie,

563
00:43:17,000 --> 00:43:23,000
אבל ניסיונות קשים יותר.

564
00:43:23,000 --> 00:43:27,000
בתאוריה, הם asymptotically טובים יותר.

565
00:43:27,000 --> 00:43:30,000
אבל רק להסתכל על הלוח הגדול,

566
00:43:30,000 --> 00:43:35,000
ומנסה לא לעשות יותר טוב, והם תופסים יותר זיכרון.

567
00:43:35,000 --> 00:43:43,000
הכל על מנסה סופו להיות יותר גרוע ליותר עבודה.

568
00:43:43,000 --> 00:43:49,000
זה מה שהפתרון של דוד מלאן תמיד הוא

569
00:43:49,000 --> 00:43:56,000
האם הוא תמיד פתרון trie הודעות שלו, ובואו נראים שם הוא משמש כיום.

570
00:43:56,000 --> 00:44:00,000
מה הוא היה תחת, הדוד J?

571
00:44:00,000 --> 00:44:06,000
הוא # 18, ככה שזה לא נורא רע,

572
00:44:06,000 --> 00:44:09,000
וזה הולך להיות אחד מהטובים מנסה אתה יכול לחשוב על

573
00:44:09,000 --> 00:44:17,000
או אחד מהטובים מנסה של trie.

574
00:44:17,000 --> 00:44:23,000
האם זה גם לא הפתרון המקורי שלו?

575
00:44:23,000 --> 00:44:29,000
אני מרגיש כמו פתרוני trie נוטים להיות יותר בטווח זה של שימוש בזכרון RAM.

576
00:44:29,000 --> 00:44:33,000
>> לרדת אל חלקו העליון, ושימוש בזכרון RAM הוא בחד הספרתיה.

577
00:44:33,000 --> 00:44:36,000
יורדים לכיוון התחתי, ואז אתה מתחיל לראות מנסה

578
00:44:36,000 --> 00:44:41,000
איפה אתה מקבל את השימוש בזכרון RAM בהחלט מסיבי,

579
00:44:41,000 --> 00:44:45,000
והניסיונות קשים יותר.

580
00:44:45,000 --> 00:44:53,000
לא לגמרי שווה את זה, אבל חוויה חינוכית אם עשה את אחד.

581
00:44:53,000 --> 00:44:56,000
הדבר האחרון הוא הרשימה המקושרת שלנו,

582
00:44:56,000 --> 00:45:04,000
ושלושת הדברים האלה, מחסניות, התורים, ורשימות מקושרות,

583
00:45:04,000 --> 00:45:09,000
כל דבר שאי פעם בעתיד לעשות במדעי מחשב

584
00:45:09,000 --> 00:45:12,000
יניח שיש לך היכרות עם הדברים האלה.

585
00:45:12,000 --> 00:45:19,000
הם פשוט כל כך בסיסיים לכל דבר.

586
00:45:19,000 --> 00:45:25,000
>> מקושרי רשימות, והנה יש לנו רשימה מקושרת ביחידים הולכת להיות היישום שלנו.

587
00:45:25,000 --> 00:45:34,000
מה קשור singly אומרים כניגוד למקושר doubly? כן.

588
00:45:34,000 --> 00:45:37,000
[סטודנטים] זה רק מצביע למצביע הבא ולאו דווקא למצביעים,

589
00:45:37,000 --> 00:45:39,000
כמו זו שקדם לה וזה שאחריו.

590
00:45:39,000 --> 00:45:44,000
כן, אז בפורמט תמונה, מה אני בדיוק עושה?

591
00:45:44,000 --> 00:45:48,000
יש לי שני דברים. יש לי תמונה ותמונה.

592
00:45:48,000 --> 00:45:51,000
בפורמט תמונה, הרשימות שלנו ביחידות המקושרות,

593
00:45:51,000 --> 00:45:57,000
בהכרח, יש לנו סוג של מצביע לראש הרשימה שלנו,

594
00:45:57,000 --> 00:46:02,000
ולאחר מכן ברשימה שלנו, אנחנו רק צריכים מצביעים,

595
00:46:02,000 --> 00:46:05,000
ואולי זה נקודות לnull.

596
00:46:05,000 --> 00:46:08,000
זה הולך להיות הציור הטיפוסי שלך מרשימה מקושרת ביחידים.

597
00:46:08,000 --> 00:46:14,000
רשימה מקושרת כפול, אתה יכול ללכת אחורה.

598
00:46:14,000 --> 00:46:19,000
אם אני אתן לך בכל צומת ברשימה, אז אתה יכול להגיע לבהכרח

599
00:46:19,000 --> 00:46:23,000
כל צומת אחר ברשימה, אם זה רשימה מקושרת כפליים.

600
00:46:23,000 --> 00:46:27,000
אבל אם אני מקבל אותך בצומת השלישית ברשימה וזה רשימה מקושרת ביחידים,

601
00:46:27,000 --> 00:46:30,000
אין דרך שאתה אי פעם הולך לקבל לבלוטות הראשונות ושניות.

602
00:46:30,000 --> 00:46:34,000
ויש יתרונות וdetriments, ואחד אחד ברור

603
00:46:34,000 --> 00:46:42,000
אתה תופס יותר גודל, ויש לך לעקוב אחר שבו הדברים האלה מצביעים עכשיו.

604
00:46:42,000 --> 00:46:49,000
אבל אנחנו רק אכפת קשורי ביחידים.

605
00:46:49,000 --> 00:46:53,000
>> כמה דברים שאנחנו הולכים יש ליישם.

606
00:46:53,000 --> 00:47:00,000
node typedef struct, אני int: struct node * הבא; הצומת.

607
00:47:00,000 --> 00:47:09,000
That typedef צריך ייצרב מוחכם.

608
00:47:09,000 --> 00:47:14,000
1 חידון צריך להיות כמו לתת typedef של צומת רשימה מקושרת,

609
00:47:14,000 --> 00:47:18,000
ואתה צריך להיות מסוגל לשרבט מייד שלמטה

610
00:47:18,000 --> 00:47:22,000
אפילו בלי לחשוב על זה.

611
00:47:22,000 --> 00:47:27,000
אני מניח שכמה שאלות, למה אנחנו צריכים את struct כאן?

612
00:47:27,000 --> 00:47:32,000
למה לא יכולים להגיד * node?

613
00:47:32,000 --> 00:47:35,000
[סטודנטים] [לא ברור]

614
00:47:35,000 --> 00:47:38,000
כן.

615
00:47:38,000 --> 00:47:44,000
הדבר היחיד שמגדיר את צומת כדבר

616
00:47:44,000 --> 00:47:47,000
הוא typedef עצמו.

617
00:47:47,000 --> 00:47:55,000
אבל כמו בנקודה זו, כאשר אנחנו סוג של ניתוח באמצעות הגדרת node struct זה,

618
00:47:55,000 --> 00:48:01,000
אנחנו עדיין לא סיימנו typedef עדיין, מה גם שtypedef לא סיים,

619
00:48:01,000 --> 00:48:05,000
node לא קיים.

620
00:48:05,000 --> 00:48:12,000
אבל struct node עושה, ואת הצומת הזה בפה,

621
00:48:12,000 --> 00:48:14,000
זה גם יכול להיות משהו אחר.

622
00:48:14,000 --> 00:48:16,000
זה יכול להיקרא n.

623
00:48:16,000 --> 00:48:19,000
אפשר לקרוא node רשימה מקושרת.

624
00:48:19,000 --> 00:48:21,000
אפשר לקרוא שום דבר.

625
00:48:21,000 --> 00:48:26,000
אבל node struct הזה צריך להיקרא אותו הדבר כמו node struct זה.

626
00:48:26,000 --> 00:48:29,000
מה אתה קורא לזה יש גם כדי להיות כאן,

627
00:48:29,000 --> 00:48:32,000
וכדי שגם עונה על הנקודה השנייה של השאלה

628
00:48:32,000 --> 00:48:37,000
ולכן, הרבה פעמים כשאתה רואה structs וtypedefs של structs,

629
00:48:37,000 --> 00:48:42,000
תראה structs אנונימיים שבו אתה פשוט רואה struct typedef,

630
00:48:42,000 --> 00:48:47,000
יישום של struct, מילון, או משהו כזה.

631
00:48:47,000 --> 00:48:51,000
>> למה כאן אנחנו צריכים לומר node?

632
00:48:51,000 --> 00:48:54,000
למה זה לא יכול להיות struct אנונימי?

633
00:48:54,000 --> 00:48:56,000
זה כמעט את אותה התשובה.

634
00:48:56,000 --> 00:48:58,000
[סטודנטים] אתה צריך להתייחס אליו בתוך struct.

635
00:48:58,000 --> 00:49:04,000
כן, בתוך struct, אתה צריך להפנות לstruct עצמו.

636
00:49:04,000 --> 00:49:10,000
אם אתה לא נותן struct שם, אם זה struct בעילום שם, אתה לא יכול להתייחס לזה.

637
00:49:10,000 --> 00:49:17,000
ואחרון אך לא פחות חשוב, אלה צריכים להיות במידה מסוימת כל פשוט,

638
00:49:17,000 --> 00:49:20,000
והם צריכים לעזור לך לממש אם אתה רושם את זה

639
00:49:20,000 --> 00:49:24,000
שאתה עושה משהו לא בסדר אם הדברים כאלה לא הגיוניים.

640
00:49:24,000 --> 00:49:28,000
אחרון חביב, למה זה צריך להיות * struct node?

641
00:49:28,000 --> 00:49:34,000
למה זה לא יכול פשוט להיות struct node הבא?

642
00:49:34,000 --> 00:49:37,000
[סטודנטים] מצביעים לstruct הבא.

643
00:49:37,000 --> 00:49:39,000
זה בהכרח מה שאנחנו רוצים.

644
00:49:39,000 --> 00:49:42,000
למה זה יכול להיות לא node struct הבא?

645
00:49:42,000 --> 00:49:50,000
למה זה צריך להיות struct node * הבא? כן.

646
00:49:50,000 --> 00:49:53,000
[סטודנטים] זה כמו לולאה אינסופית.

647
00:49:53,000 --> 00:49:55,000
כן.

648
00:49:55,000 --> 00:49:57,000
[סטודנטים] הכול היה יכול להיות באחד.

649
00:49:57,000 --> 00:50:02,000
כן, רק לחשוב על איך אנחנו נעשה גודל או משהו.

650
00:50:02,000 --> 00:50:08,000
גודל של struct הוא בעצם + או - איזה דפוס כאן או שם.

651
00:50:08,000 --> 00:50:15,000
זה בעצם הולך להיות סכום הגדלים של הדברים בstruct.

652
00:50:15,000 --> 00:50:18,000
זכות זו כאן, מבלי לשנות שום דבר, את הגודל הולכת להיות קל.

653
00:50:18,000 --> 00:50:24,000
גודלו של צומת struct הולך להיות גודל של אני + הגודל הבא.

654
00:50:24,000 --> 00:50:27,000
הגודל שלי הולך להיות 4. הגודל הבא הולך להיות 4.

655
00:50:27,000 --> 00:50:30,000
הגודל של צומת struct הולך להיות 8.

656
00:50:30,000 --> 00:50:34,000
אם אין לך את *, וחשב על sizeof,

657
00:50:34,000 --> 00:50:37,000
אז sizeof (אני) הולך להיות 4.

658
00:50:37,000 --> 00:50:43,000
גודלו של צומת struct הבא הולך להיות בגודל של i + גודל של צומת struct הבאה

659
00:50:43,000 --> 00:50:46,000
+ גודל אני + הגודל של struct צומת הבאה.

660
00:50:46,000 --> 00:50:55,000
זה יהיה רקורסיה אינסופית של צמתים.

661
00:50:55,000 --> 00:51:00,000
זו הסיבה מדוע זה איך דברים צריכים להיות.

662
00:51:00,000 --> 00:51:03,000
>> שוב, בהחלט לשנן את זה,

663
00:51:03,000 --> 00:51:06,000
או לפחות מבין את זה מספיק כדי שתוכל להיות מסוגל

664
00:51:06,000 --> 00:51:12,000
סיבה דרך מה זה אמור להיראות.

665
00:51:12,000 --> 00:51:14,000
הדברים שאנחנו הולכים רוצים ליישם.

666
00:51:14,000 --> 00:51:18,000
אם אורכה של הרשימה

667
00:51:18,000 --> 00:51:21,000
אתה יכול לרמות ולשמור על הסביבה

668
00:51:21,000 --> 00:51:24,000
אורך גלובלי או משהו, אבל אנחנו לא הולכים לעשות את זה.

669
00:51:24,000 --> 00:51:28,000
אנחנו הולכים לספור את אורכה של הרשימה.

670
00:51:28,000 --> 00:51:34,000
יש לנו מכיל, כך שבעצם כמו חיפוש,

671
00:51:34,000 --> 00:51:41,000
אז יש לנו רשימה מקושרת של מספרים שלמים כדי לראות אם מספר שלם זה ברשימה המקושרת.

672
00:51:41,000 --> 00:51:44,000
הקדם זיהוי הולך להכניס בתחילת הרשימה.

673
00:51:44,000 --> 00:51:46,000
הצרף הולך להכניס בסוף.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted הולך להכניס לתוך העמדה מסודרת ברשימה.

675
00:51:53,000 --> 00:52:01,000
סוג של Insert_sorted מניח שאתה מעולם לא השתמשת בהקדם זיהוי או לצרף בדרכים רעות.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted כשאתה מיישם insert_sorted-

677
00:52:09,000 --> 00:52:13,000
נניח שיש לנו הרשימה המקושרת שלנו.

678
00:52:13,000 --> 00:52:18,000
זה מה שהוא כרגע נראה, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
אני רוצה להכניס 3, ולכן כל עוד הרשימה עצם כבר ממוינת,

680
00:52:24,000 --> 00:52:27,000
זה קל למצוא בו 3 שייכים.

681
00:52:27,000 --> 00:52:29,000
אני מתחיל בשעת 2.

682
00:52:29,000 --> 00:52:32,000
אוקיי, 3 גדולים מ 2, אז אני רוצה להמשיך.

683
00:52:32,000 --> 00:52:35,000
אה, 4 הם גדולים מדי, ולכן אני יודע 3 הוא הולכים להיכנס בו בין 2 ל 4,

684
00:52:35,000 --> 00:52:39,000
ואני חייב לתקן את מצביעים וכל הדברים האלה.

685
00:52:39,000 --> 00:52:43,000
אבל אם אנחנו לא בהחלט להשתמש insert_sorted,

686
00:52:43,000 --> 00:52:50,000
אוהבים בואו רק נאמרתי שאני הקדם זיהוי 6,

687
00:52:50,000 --> 00:52:55,000
אז הרשימה המקושרת שלי הולכת להיות זה.

688
00:52:55,000 --> 00:53:01,000
עכשיו זה לא הגיוני, ולכן לinsert_sorted, אתה יכול פשוט להניח

689
00:53:01,000 --> 00:53:04,000
שהרשימה ממוינת, למרות שקיימות פעולות

690
00:53:04,000 --> 00:53:09,000
מה שיכול לגרום לו לא להיות מסודר, וזהו זה.

691
00:53:09,000 --> 00:53:20,000
מצא מועיל להוסיף כל כך אלה הם הדברים העיקריים שאתה הולך צריך ליישם.

692
00:53:20,000 --> 00:53:24,000
>> לעת עתה, לקחת רגע כדי לעשות אורך ומכיל,

693
00:53:24,000 --> 00:53:30,000
ואלה צריכים להיות מהירים יחסית.

694
00:53:41,000 --> 00:53:48,000
מתקרב לשעת סגירה, כך שכל אחד יש משהו לאורכו או מכיל?

695
00:53:48,000 --> 00:53:50,000
הם הולכים להיות כמעט זהים.

696
00:53:50,000 --> 00:53:57,000
[סטודנטים] זמן.

697
00:53:57,000 --> 00:54:01,000
בואו נראים, מהדורה.

698
00:54:01,000 --> 00:54:04,000
אוקיי.

699
00:54:12,000 --> 00:54:15,000
אתה רוצה להסביר?

700
00:54:15,000 --> 00:54:21,000
[סטודנטים] אני פשוט ליצור צומת מצביע ולאתחל אותו לראשון, שהוא משתנה הגלובלי שלנו,

701
00:54:21,000 --> 00:54:27,000
ואז אני בודק אם זה null אז אני לא אקבל אשמת בידוד, ולהחזיר 0 אם זה המקרה.

702
00:54:27,000 --> 00:54:34,000
אחרת, אני לולאה דרך, תוך שמירה על מסלול של מספר שלם

703
00:54:34,000 --> 00:54:38,000
כמה פעמים אני קבלתי גישה לאלמנט הבא ברשימה

704
00:54:38,000 --> 00:54:43,000
ובאותה הפעולה גם לגשת תוספת אלמנט שבפועל,

705
00:54:43,000 --> 00:54:47,000
ואז אני עושה ברציפות הבדיקה כדי לראות אם זה ריק,

706
00:54:47,000 --> 00:54:56,000
ואם זה אפס, אז זה מבטל ופשוט מחזיר את מספר האלמנטים שגישה.

707
00:54:56,000 --> 00:55:01,000
>> [רוב ב '] למישהו יש הערות על כל דבר?

708
00:55:01,000 --> 00:55:06,000
זה נראה בסדר תקינות חכמה.

709
00:55:06,000 --> 00:55:10,000
[סטודנטים] אני לא חושב שאתה צריך את צומת == null.

710
00:55:10,000 --> 00:55:13,000
כן, כך שאם צומת == 0 החזר null.

711
00:55:13,000 --> 00:55:18,000
אבל אם == null צומת אז זה-הו, יש בעית תקינות.

712
00:55:18,000 --> 00:55:23,000
זה היה רק ​​אתה חוזר אני, אבל זה לא בהיקפה ברגע זה.

713
00:55:23,000 --> 00:55:30,000
אתה פשוט צריך int i, אז אני = 0.

714
00:55:30,000 --> 00:55:34,000
אבל אם הצומת היא ריקה, אז אני עדיין הולך להיות 0,

715
00:55:34,000 --> 00:55:39,000
ואנחנו הולכים להחזיר 0, ולכן מקרה זה הוא זהה.

716
00:55:39,000 --> 00:55:48,000
דבר משותף נוסף הוא לשמור על ההצהרה

717
00:55:48,000 --> 00:55:51,000
בבתוך צומת של ללולאה.

718
00:55:51,000 --> 00:55:54,000
אפשר לומר, הו, לא.

719
00:55:54,000 --> 00:55:56,000
בואו נשאיר את זה כמו זה.

720
00:55:56,000 --> 00:55:59,000
אני כנראה יהיה שם אני int = 0 כאן,

721
00:55:59,000 --> 00:56:05,000
אז צומת * צומת = 1 כאן.

722
00:56:05,000 --> 00:56:11,000
וזה, מן הסתם, מקבל-להיפטר מזה עכשיו.

723
00:56:11,000 --> 00:56:14,000
זה כנראה מה שאני הייתי כותב את זה.

724
00:56:14,000 --> 00:56:21,000
אתה יכול גם להסתכל על זה, כמו זה.

725
00:56:21,000 --> 00:56:25,000
זה למבנה לולאה כאן

726
00:56:25,000 --> 00:56:30,000
צריך להיות כמעט טבעי לך כפי שלint i = 0

727
00:56:30,000 --> 00:56:33,000
אני הוא פחות מאורכו של מערך i + +.

728
00:56:33,000 --> 00:56:38,000
אם זה מה שאתה לחזר על מערך, זה איך אתה לחזר על רשימה מקושרת.

729
00:56:38,000 --> 00:56:45,000
>> זה צריך להיות טבע שני בשלב מסוים.

730
00:56:45,000 --> 00:56:50,000
עם זה בחשבון, זה הולך להיות כמעט אותו הדבר.

731
00:56:50,000 --> 00:56:57,000
אתה הולך רוצה לחזר על רשימה מקושרת.

732
00:56:57,000 --> 00:57:02,000
אם צומת אין לי מושג מה ערכו נקרא.

733
00:57:02,000 --> 00:57:04,000
צומת i.

734
00:57:04,000 --> 00:57:15,000
אם הערך שבצומת = אני חוזר נכון, וזהו.

735
00:57:15,000 --> 00:57:18,000
שים לב שהדרך היחידה שבה בתמורת שווא

736
00:57:18,000 --> 00:57:23,000
הוא אם לחזר על הרשימה המקושרת כולו ולא לחזור לנכון,

737
00:57:23,000 --> 00:57:29,000
אז זה מה שזה עושה.

738
00:57:29,000 --> 00:57:36,000
כצד הערות שסביר להניח שלא יגיעו לצירוף או הקדם זיהוי.

739
00:57:36,000 --> 00:57:39,000
>> הפתק אחרון מהיר.

740
00:57:39,000 --> 00:57:52,000
אם אתה רואה את מילת מפתח סטטי, אז נגיד שint ספירת סטטי = 0,

741
00:57:52,000 --> 00:57:56,000
אז אנחנו עושים ספירה + +, אתה יכול בעצם לחשוב על זה כמשתנה גלובלי,

742
00:57:56,000 --> 00:58:00,000
למרות שאני רק אמרתי שזה לא איך אנחנו מתכוונים ליישם את האורך.

743
00:58:00,000 --> 00:58:06,000
אני עושה את זה כאן, ואז לספור + +.

744
00:58:06,000 --> 00:58:11,000
יש לנו אפשרות להיכנס לתוך צומת הרשימה המקושרת שלנו אנחנו הגדלת הספירה שלנו.

745
00:58:11,000 --> 00:58:15,000
הנקודה זו היא מה משמעות מילת מפתח סטטי.

746
00:58:15,000 --> 00:58:20,000
אם רק הייתי ספירת int = 0 שיהיו משתנים גלובלי ישן רגיל.

747
00:58:20,000 --> 00:58:25,000
מה זה אומר הספירה int סטטי הוא שזה משתנה גלובלי עבור קובץ זה.

748
00:58:25,000 --> 00:58:28,000
זה בלתי אפשרי עבור קובץ אחר,

749
00:58:28,000 --> 00:58:34,000
אוהבים לחשוב על pset 5, אם יש לך החל.

750
00:58:34,000 --> 00:58:39,000
יש לך גם speller.c, ויש לך dictionary.c,

751
00:58:39,000 --> 00:58:42,000
ואם אתה רק מצהיר דבר עולמי, אז הכל בspeller.c

752
00:58:42,000 --> 00:58:45,000
ניתן לגשת בdictionary.c ולהיפך.

753
00:58:45,000 --> 00:58:48,000
משתנים גלובליים נגישים על ידי. כל קובץ c,

754
00:58:48,000 --> 00:58:54,000
אבל משתנה סטטיים נגישים רק מתוך הקובץ עצמו,

755
00:58:54,000 --> 00:59:01,000
כך פנימי של בודקת איות או בתוך dictionary.c,

756
00:59:01,000 --> 00:59:06,000
זה סוג של איך הייתי להכריז משתנה לגודל של מערכי

757
00:59:06,000 --> 00:59:10,000
או בגודל של מספר המילים במילון שלי.

758
00:59:10,000 --> 00:59:15,000
מאז אני לא רוצה להכריז על משתנה גלובלי שכל אחד יש גישה ל,

759
00:59:15,000 --> 00:59:18,000
אכפת לי באמת על זה רק למטרות שלי.

760
00:59:18,000 --> 00:59:21,000
>> דבר טוב בזה גם דברי התנגשות השם השלמים.

761
00:59:21,000 --> 00:59:27,000
אם קובץ אחר מנסה להשתמש במשתנה גלובלית הנקראת ספירה, דברים הולכים מאוד מאוד לא בסדר,

762
00:59:27,000 --> 00:59:33,000
אז זה יפה שומר על דברים בטוחים, ורק אתה יכול לגשת אליו,

763
00:59:33,000 --> 00:59:38,000
ואף אחד אחר לא יכול, ואם מישהו אחר מצהיר משתנה גלובלי הנקרא ספירה,

764
00:59:38,000 --> 00:59:43,000
אז זה לא מפריע למשתנת סטטי נקראת ספירה.

765
00:59:43,000 --> 00:59:47,000
זה מה שהוא סטטי. זה משתנה קובץ גלובלי.

766
00:59:47,000 --> 00:59:52,000
>> שאלות על כל דבר?

767
00:59:52,000 --> 00:59:59,000
כל הקבוצה. ביי.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]