1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [שבוע 6, המשך]

2
00:00:02,520 --> 00:00:04,160
[הדוד י מלאן] [אוניברסיטת הרווארד]

3
00:00:04,160 --> 00:00:08,720
[זה CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
זה CS50 וזה סוף השבוע 6.

5
00:00:12,970 --> 00:00:17,970
אז CS50x, אחד הקורסים הראשונים של הרווארד המעורבים ביוזמת edx

6
00:00:17,970 --> 00:00:20,590
אכן זו לראשונה שלשום.

7
00:00:20,590 --> 00:00:23,460
אם אתם רוצים לקבל צצה לאחרים מה באינטרנט

8
00:00:23,460 --> 00:00:27,180
כעת עוקבים יחד עם, אתם יכולים לגשת לx.cs50.net.

9
00:00:27,180 --> 00:00:30,350
שיפנה אותך למקום המתאים בedx.org,

10
00:00:30,350 --> 00:00:34,160
שהיה שם זה וקורסים נוספים מ-MIT וברקלי חי כיום.

11
00:00:34,160 --> 00:00:38,140
תצטרך להירשם לחשבון, תמצאו שהחומר הוא במידה רבה באותה

12
00:00:38,140 --> 00:00:42,170
כפי שהיה לך בסמסטר הזה, אם כי כמה שבועות עוכבו, כפי שאנו מקבלים הכל מוכן.

13
00:00:42,170 --> 00:00:46,930
אבל מה תלמידים בCS50x כעת לראות הוא ממשק ממש כמו זה.

14
00:00:46,930 --> 00:00:50,040
זו, למשל, היא Zamyla מוביל את ההדרכה לקבוצת הבעיה 0.

15
00:00:50,040 --> 00:00:54,230
עם כניסתך לedx.org, סטודנט CS50x רואה את מיני דברים

16
00:00:54,230 --> 00:00:57,170
שהיית מצפה לראות בקורס: ההרצאה ליום שני,

17
00:00:57,170 --> 00:01:01,650
הרצאה ליום רביעי, מכנסים שונים, סט הבעיה, ליין, קבצי PDF.

18
00:01:01,650 --> 00:01:04,459
בנוסף לכך, כפי שאתה רואה כאן, תרגומי מכונית

19
00:01:04,459 --> 00:01:08,390
מתעתיקים האנגלים לסיני, יפני, ספרדית, איטלקי,

20
00:01:08,390 --> 00:01:12,810
וכל חבורה של שפות אחרות שבהחלט תהיה מושלם

21
00:01:12,810 --> 00:01:15,840
כפי שאנו לגלגל אותם החוצה תכנותיים באמצעות משהו שנקרא API,

22
00:01:15,840 --> 00:01:18,360
או ממשק תכנות יישומים, מ-Google

23
00:01:18,360 --> 00:01:21,360
שמאפשר לנו להמיר אנגלית לשפות אחרות אלה.

24
00:01:21,360 --> 00:01:24,100
אך הודות לרוח הנפלאה של חלק ממתנדבים 100 ויותר,

25
00:01:24,100 --> 00:01:26,940
אנשים אקראיים באינטרנט שמוצעים בחביבות להסתבך

26
00:01:26,940 --> 00:01:30,180
בפרויקט זה, אנחנו בהדרגה להיות שיפור האיכות של התרגומים האלה

27
00:01:30,180 --> 00:01:35,790
על ידי כך בני אדם לתקן את הטעויות שהמחשבים שלנו עשו.

28
00:01:35,790 --> 00:01:42,330
>> אז מתברר שיש לנו עוד כמה סטודנטים יגיעו ביום שני ממה שציפינו בתחילה.

29
00:01:42,330 --> 00:01:48,980
למעשה, עכשיו CS50x יש 100.000 אנשים הבאים יחד בבית.

30
00:01:48,980 --> 00:01:54,430
אז מבין שהם החלק ממעמד ההשבעה הזה של עשיית קורס זה במדע המחשב

31
00:01:54,430 --> 00:01:57,370
חינוך באופן כללי יותר, באופן רחב יותר, נגיש.

32
00:01:57,370 --> 00:02:00,130
והמציאות היא עכשיו, עם חלק מהקורסים מקוונים המסיביים אלה,

33
00:02:00,130 --> 00:02:04,070
כולם מתחילים עם מספרים אלה גבוהים מאוד, כפי שנראה שנעשה כאן.

34
00:02:04,070 --> 00:02:08,759
אבל המטרה, בסופו, לCS50x היא באמת להגיע כמה שיותר אנשים אל קו הסיום כמה שאפשר.

35
00:02:08,759 --> 00:02:12,000
על פי תכנון, CS50x הולך להיות מוצע מיום שני האחרון

36
00:02:12,000 --> 00:02:17,430
לאורך כל הדרך 15 אפריל 2013, כך שאנשים שיש להם מחויבויות לבית הספר במקום אחר,

37
00:02:17,430 --> 00:02:20,990
עבודה, משפחה, סכסוכים אחרים וכדומה, יש קצת יותר גמישות

38
00:02:20,990 --> 00:02:23,640
עם שלצלול לקורס זה, ש, די אם נאמר,

39
00:02:23,640 --> 00:02:30,540
נעשה די שאפתן ולו רק במשך שלושה חודשים בלבד במהלך סמסטר רגיל.

40
00:02:30,540 --> 00:02:34,190
אבל תלמידים אלה יהיו התמודדות עם סטיה הבעיה, צפייה באותו התוכן,

41
00:02:34,190 --> 00:02:36,350
יש גישה לאותם מכנסיים קצרים וכדומה.

42
00:02:36,350 --> 00:02:38,990
אז הבין שכולנו בעצם בזה ביחד.

43
00:02:38,990 --> 00:02:42,360
ואחת מהמטרות הסופיות של CS50x הוא לא רק כדי לקבל כמה שיותר אנשים

44
00:02:42,360 --> 00:02:45,720
אל קו הסיום ולתת להם הבנה חדשה זו של מדעי מחשב

45
00:02:45,720 --> 00:02:49,000
ותכנות, אבל גם שיש להם הניסיון המשותף הזה.

46
00:02:49,000 --> 00:02:52,010
אחד המאפיינים המגדירים של 50 בקמפוס, ואנו מקווים,

47
00:02:52,010 --> 00:02:56,260
היה זה סוג של חוויה קהילתית, לטוב או לרע, לפעמים,

48
00:02:56,260 --> 00:02:59,480
אבל יש את האנשים האלה לפנות לשמאל ולימין,

49
00:02:59,480 --> 00:03:01,830
ושעתי העבודה וhackathon והוגן.

50
00:03:01,830 --> 00:03:04,560
זה קצת קשה לעשות את זה באופן אישי עם אנשים באינטרנט,

51
00:03:04,560 --> 00:03:10,580
אבל CS50x יסתיים באפריל עם אי CS50 אקספו הראשון,

52
00:03:10,580 --> 00:03:13,630
שתהיה הסתגלות מקוונת של הרעיון ההוגן

53
00:03:13,630 --> 00:03:18,250
איפה אלו אלף תלמידים וכולם מוזמנים להגיש 1 - לוידאו 2-דקה,

54
00:03:18,250 --> 00:03:22,480
גם screencast של הפרויקט שלהם הסופי או וידאו שלהם מנופף לשלום

55
00:03:22,480 --> 00:03:24,490
ומדבר על הפרויקט שלהם וdemoing,

56
00:03:24,490 --> 00:03:27,610
בדומה לקודמים שעשו כאן בקמפוס ביריד,

57
00:03:27,610 --> 00:03:31,400
כך שבסופו של הסמסטר, התקווה היא שתהיה לי תערוכה עולמית

58
00:03:31,400 --> 00:03:37,080
של פרויקטי הגמר של סטודנטי CS50x, ממש כמו זה שמחכה לך בדצמבר הקרוב כאן בקמפוס.

59
00:03:37,080 --> 00:03:39,680
נוסף על כך, כי בחודשים הבאים.

60
00:03:39,680 --> 00:03:43,640
>> עם 100.000 תלמידים, אם כי, מגיע צורך בכמה רשויות אישורים נוספות.

61
00:03:43,640 --> 00:03:47,590
בהתחשב בכך שנתן לוהט שביל כאן ולוקח CS50

62
00:03:47,590 --> 00:03:51,630
כמה שבועות מראש לשחרורו של חומר זה לחברים, edx,

63
00:03:51,630 --> 00:03:55,330
מבין שהיינו רוצה לערב כמה שיותר מהתלמידים שלנו ככל האפשר ביוזמה זו,

64
00:03:55,330 --> 00:03:58,720
הן במהלך הסמסטר וגם בחורף ובאביב קרוב.

65
00:03:58,720 --> 00:04:01,620
אז אם אתה רוצה להיות מעורב בCS50x,

66
00:04:01,620 --> 00:04:07,450
במיוחד הצטרף בCS50x לדון, גרסת edx של CS50 לדון,

67
00:04:07,450 --> 00:04:10,140
שרבים מכם כבר משתמשים בקמפוס, לוח המודעות המקוון,

68
00:04:10,140 --> 00:04:13,040
אנא עשה את הראש לאותה כתובת, תן לנו לדעת מי אתה,

69
00:04:13,040 --> 00:04:16,450
כי נשמח לבנות את צוות של סטודנטים וסגל כאחד וסגל

70
00:04:16,450 --> 00:04:19,630
בקמפוס, שפשוט משחקים יחד ולעזור.

71
00:04:19,630 --> 00:04:21,720
כשהם רואים שאלה שמוכרת להם ו,

72
00:04:21,720 --> 00:04:25,320
אתה שומע סטודנט דיווח כמה באגים אי שם במדינה כלשהי באינטרנט,

73
00:04:25,320 --> 00:04:27,450
ושמצלצל לי מוכר מדי, כי אתה היה באותו נושא

74
00:04:27,450 --> 00:04:32,620
בd-האולם לפני כמה זמן, בתקווה שאז אתה יכול לצלצל ולחלוק את החוויה שלך.

75
00:04:32,620 --> 00:04:37,300
אז בבקשה אל להשתתף אם אתה רוצה.

76
00:04:37,300 --> 00:04:39,360
>> קורסים למדעי מחשב באוניברסיטת הרווארד יש קצת מסורת,

77
00:04:39,360 --> 00:04:44,730
CS50 ביניהם, שיש כמה בגדים, קצת בגדים, שאתה יכול ללבוש בגאווה

78
00:04:44,730 --> 00:04:49,090
בסוף הסמסטר, ואמר די בגאווה שסיימת CS50

79
00:04:49,090 --> 00:04:51,830
ולקחתי CS50 וכיוצא בזה, ואנחנו תמיד מנסים לערב את התלמידים

80
00:04:51,830 --> 00:04:54,540
בתהליך זה עד כמה שניתן, לפיה אנחנו מזמינים,

81
00:04:54,540 --> 00:04:56,900
בערך בתקופה זו של הסמסטר, סטודנטים להגיש עיצובים

82
00:04:56,900 --> 00:04:59,330
באמצעות פוטושופ, או מה שכלי של בחירה שברצונך להשתמש

83
00:04:59,330 --> 00:05:02,330
אם אתה מעצב, להגיש עיצובים לחולצות וסווטשירטים

84
00:05:02,330 --> 00:05:06,100
ומטריות ובנדנות הקטנה לכלבים יש לנו עכשיו וכדומה.

85
00:05:06,100 --> 00:05:09,370
והכל אז - את הזוכים בכל שנה לאחר מכן, הציגו

86
00:05:09,370 --> 00:05:12,700
באתר האינטרנט של הקורס בstore.cs50.net.

87
00:05:12,700 --> 00:05:15,790
הכל נמכר במחיר שם, אבל האתר פשוט מתנהל מעצמו

88
00:05:15,790 --> 00:05:18,330
ומאפשר לאנשים לבחור את הצבעים והעיצובים שהם אוהבים.

89
00:05:18,330 --> 00:05:20,420
אז חשבנו שאנחנו רק רוצים לחלוק כמה מהעיצובים של השנה שעברה

90
00:05:20,420 --> 00:05:25,130
שהיו באתר מלבד זה שלפנינו, שהנה מסורת שנתית.

91
00:05:25,130 --> 00:05:29,410
"כל היום אני SEG Faultn" היה אחת מההגשות בשנה שעברה,

92
00:05:29,410 --> 00:05:32,290
שהוא עדיין זמין יש לבוגרים.

93
00:05:32,290 --> 00:05:35,820
אנחנו ראינו את זה, "CS50, נוסד 1989."

94
00:05:35,820 --> 00:05:39,010
אחד Bowdens, רוב, היה פופולרי מאוד בשנה שעברה.

95
00:05:39,010 --> 00:05:43,480
"צוות אודן" נולד, עיצוב זו הוגש, בין מוכרי הדף.

96
00:05:43,480 --> 00:05:49,040
כפי שהיה זה כאן. אנשים רבים הייתה "קדחת אודן" על פי יומני מכירות.

97
00:05:49,040 --> 00:05:52,650
מבין שזה עכשיו יכול להיות העיצוב שלך שם, עד באינטרנט.

98
00:05:52,650 --> 00:05:57,510
פרטים נוספים על זה בבעיה הבאה קובעים לבוא.

99
00:05:57,510 --> 00:06:00,330
>> כלי אחד נוסף: שתהיה לך קצת חשיפה ובתקווה עכשיו

100
00:06:00,330 --> 00:06:02,350
קצת ניסיון על ידות עם GDB,

101
00:06:02,350 --> 00:06:04,570
וזה, כמובן, הבאגים ומאפשר לך לשנות

102
00:06:04,570 --> 00:06:09,500
התכנית שלך ברמה נמוכה למדי, מה שעושה סוגים של דברים?

103
00:06:09,500 --> 00:06:13,030
מה GDB לא ייתן לך לעשות?

104
00:06:13,030 --> 00:06:15,030
כן? תן לי משהו. [תשובת סטודנט, לא מובן]

105
00:06:15,030 --> 00:06:18,120
טוב. צעד לתוך פונקציה, אז אתה לא רק צריך להקליד לרוץ

106
00:06:18,120 --> 00:06:22,310
ויש לי את המכה באמצעות תכנית שלמותו, להדפיס את הדברים לפלט סטנדרטי.

107
00:06:22,310 --> 00:06:25,190
במקום זאת, אתה יכול לעבור דרך הקו אותו על ידי קו, או להקליד הבא

108
00:06:25,190 --> 00:06:30,300
ללכת שורה אחרת שורה אחרת שורה או צעד לצלול לתוך פונקציה, בדרך כלל אחד שאתה כתבת.

109
00:06:30,300 --> 00:06:35,240
מה עוד אין GDB ייתן לך לעשות? כן? [תשובת סטודנט, לא מובן]

110
00:06:35,240 --> 00:06:38,100
דפס משתנים. אז אם אתה רוצה לעשות את חשבון נפש קטן בתוך התכנית שלך

111
00:06:38,100 --> 00:06:41,500
מבלי להזדקק לכתיבת דוחות printf בכל המקום,

112
00:06:41,500 --> 00:06:44,600
אתה יכול פשוט להדפיס משתנה או להציג משתנה.

113
00:06:44,600 --> 00:06:46,710
מה עוד אפשר לעשות עם הבאגים כמו GDB?

114
00:06:46,710 --> 00:06:49,170
[תשובת סטודנט, לא מובן]

115
00:06:49,170 --> 00:06:52,080
בדיוק. באפשרותך להגדיר נקודתי עצירה, אתה יכול לומר ביצוע הפסקה

116
00:06:52,080 --> 00:06:54,020
בתפקיד הראשי או פונקצית foo.

117
00:06:54,020 --> 00:06:56,800
אתה יכול להגיד ביצוע הפסקה בקו 123.

118
00:06:56,800 --> 00:06:58,950
ונקודתי עצירה הן טכניקה חזקה באמת

119
00:06:58,950 --> 00:07:01,110
כי אם יש לך תחושה כללית של איפה הבעיה שלך

120
00:07:01,110 --> 00:07:05,360
כנראה, אתה לא צריך לבזבז זמן דריכה דרך השלמות של התכנית.

121
00:07:05,360 --> 00:07:08,250
אתה בעצם יכול לקפוץ ישר לשם ולאחר מכן להתחיל להקליד -

122
00:07:08,250 --> 00:07:10,970
דריכה דרכו בצעד או הבא או כמו.

123
00:07:10,970 --> 00:07:14,340
אבל לתפוס עם משהו כמו GDB הוא שזה עוזר לך, אדם,

124
00:07:14,340 --> 00:07:16,940
למצוא את הבעיות שלך ותמצא הבאגים שלכם.

125
00:07:16,940 --> 00:07:19,470
זה לא בהכרח מוצא אותם כל כך הרבה בשבילך.

126
00:07:19,470 --> 00:07:23,070
>> אז הציג style50 היום השני, שהוא כלי שורת פקודה קצר

127
00:07:23,070 --> 00:07:27,500
שמנסה לסגנן את הקוד שלך קצת יותר נקי ממה שאתה, אנושי, עשוי לעשות.

128
00:07:27,500 --> 00:07:29,530
אבל גם את זה, הוא באמת רק עניין אסתטי.

129
00:07:29,530 --> 00:07:34,110
אבל מתברר שיש בכלי זה אחר בשם Valgrind שהוא קצת יותר מסתורי לשימוש.

130
00:07:34,110 --> 00:07:36,860
הפלט שלו הוא אכזרי סתום במבט הראשון.

131
00:07:36,860 --> 00:07:39,420
אבל זה שימושי להפליא, במיוחד עכשיו שאנחנו בחלק מהטווח

132
00:07:39,420 --> 00:07:43,080
איפה אתה מתחיל להשתמש malloc והקצאת זיכרון דינמית.

133
00:07:43,080 --> 00:07:45,420
דברים יכולים ללכת ממש ממש לא בסדר במהירות.

134
00:07:45,420 --> 00:07:49,320
כי אם אתה שוכח לשחרר את הזיכרון שלך, או שאתה חלק dereference מצביע NULL,

135
00:07:49,320 --> 00:07:55,770
או שאתה חלק dereference מצביע אשפה, מה שהוא בדרך כלל הסימפטום שתוצאות?

136
00:07:55,770 --> 00:07:59,470
SEG אשמה. ואתה מקבל קובץ הגרעין הזה של מספר מסוים של ק"ג או מגה

137
00:07:59,470 --> 00:08:02,990
המייצג את המצב של הזיכרון של התכנית שלך כאשר הוא התרסק,

138
00:08:02,990 --> 00:08:05,730
אבל התכנית שלך בסופו צינוק פגמים, תקלות פילוח,

139
00:08:05,730 --> 00:08:08,450
מה שאומר שמשהו רע קרה כמעט תמיד קשור

140
00:08:08,450 --> 00:08:11,750
לטעות בזיכרון שעשית במקום.

141
00:08:11,750 --> 00:08:14,100
אז Valgrind עוזר לך למצוא דברים כאלה.

142
00:08:14,100 --> 00:08:17,720
זה כלי שאתה מפעיל, כמו GDB, לאחר שצרפת את התכנית שלך,

143
00:08:17,720 --> 00:08:20,330
אבל במקום להריץ את התכנית שלך באופן ישיר, אתה מפעיל Valgrind

144
00:08:20,330 --> 00:08:23,960
ואתה עובר אליו התכנית שלך, בדיוק כמו שאתה עושה עם GDB.

145
00:08:23,960 --> 00:08:26,220
כעת, השימוש, כדי לקבל הסוג של פלט הטוב ביותר,

146
00:08:26,220 --> 00:08:30,410
הוא קצת ארוך, אז ממש שם על גבי המסך תראה Valgrind-V.

147
00:08:30,410 --> 00:08:35,350
"-V" כמעט אוניברסלי פירוש מפורט כאשר אתה משתמש בתוכניות במחשב לינוקס.

148
00:08:35,350 --> 00:08:38,770
אז זה אומר לירוק יותר נתונים ממה שהיית כברירת מחדל.

149
00:08:38,770 --> 00:08:45,510
"- דליפה לבדוק = מלא". זה רק אומר סימון עבור כל דליפות הזיכרון האפשריות,

150
00:08:45,510 --> 00:08:49,430
טעויות שאולי עשיתי. גם זה, הוא פרדיגמה משותפת עם תוכניות לינוקס.

151
00:08:49,430 --> 00:08:52,710
באופן כללי, אם יש לך טיעון שורת פקודה זה "בורר",

152
00:08:52,710 --> 00:08:55,830
זה אמור לשנות את ההתנהגות של התכנית, וזה אות אחת,

153
00:08:55,830 --> 00:09:00,310
זה-V, אבל אם זה יעבור, רק על ידי עיצוב של המתכנת,

154
00:09:00,310 --> 00:09:05,150
הוא מילה או סדרה מלאה של מילים, ויכוח שורת הפקודה מתחיל עם -.

155
00:09:05,150 --> 00:09:08,190
אלה הם רק מוסכמות אדם, אבל אתה רואה אותם יותר ויותר.

156
00:09:08,190 --> 00:09:12,410
ואז, סוף סוף, "a.out" הוא שם השרירותי לתכנית בדוגמה זו בפרט.

157
00:09:12,410 --> 00:09:14,640
והנה כמה פלט נציג.

158
00:09:14,640 --> 00:09:22,890
>> לפני שאנחנו מסתכלים על מה שאולי אומרים, בואו נעבור עליי לקטע של קוד כאן.

159
00:09:22,890 --> 00:09:26,390
ולתת לי לזוז מזה של הדרך, בקרוב,

160
00:09:26,390 --> 00:09:32,120
ובואו נסתכל memory.c, שהוא דוגמה קצרה זה כאן.

161
00:09:32,120 --> 00:09:36,290
אז בתכנית זו, תן לי להתקרב בפונקציות ובשאלות.

162
00:09:36,290 --> 00:09:39,430
יש לנו פונקציה עיקרית שקוראה לפונקציה, f,

163
00:09:39,430 --> 00:09:45,590
ואז מה f אין להמשיך לעשות, באנגלית הטכנית במקצת?

164
00:09:45,590 --> 00:09:49,760
מה f אין להמשיך לעשות?

165
00:09:49,760 --> 00:09:53,680
מה דעתך על אני אתחיל עם קו 20, ואת מיקומו של הכוכב לא משנה,

166
00:09:53,680 --> 00:09:56,720
אבל אני פשוט אהיה עקבי כאן עם ההרצאה אחרונה.

167
00:09:56,720 --> 00:09:59,910
מה אין קו 20 בשבילנו? בצד השמאל. אנחנו נשבור אותו עוד יותר למטה.

168
00:09:59,910 --> 00:10:02,410
Int * x: מה זה עושה?

169
00:10:02,410 --> 00:10:04,940
אוקיי. זה הכרזת מצביע, ועכשיו בואו אהיה גם יותר טכני.

170
00:10:04,940 --> 00:10:10,230
מה זה אומר, מאוד קונקרטי, להכריז על מצביע? מישהו אחר?

171
00:10:10,230 --> 00:10:15,050
כן? [תשובת סטודנט, לא מובן] יותר מדי רחוק.

172
00:10:15,050 --> 00:10:17,060
אז אתה קורא לצד הימני של סימן השוויון.

173
00:10:17,060 --> 00:10:20,290
בואו נתמקד רק בצד השמאל, רק על int x *.

174
00:10:20,290 --> 00:10:24,700
זה "להצהיר" מצביע, אבל עכשיו בואו לצלול עמוק יותר להגדרה הזאת.

175
00:10:24,700 --> 00:10:28,330
מה זה קונקרטי, מבחינה טכנית אומר? כן?

176
00:10:28,330 --> 00:10:31,940
[תשובת סטודנט, לא מובן]

177
00:10:31,940 --> 00:10:35,090
אוקיי. זה הכנה לשמירת כתובת בזיכרון.

178
00:10:35,090 --> 00:10:40,680
טוב. ובואו ניקח את זה צעד אחד קדימה; הוא מכריז על משתנה, x, זה 32 סיביים.

179
00:10:40,680 --> 00:10:44,440
ואני יודע שזה 32 סיבי בגלל -?

180
00:10:44,440 --> 00:10:47,390
זה לא בגלל שזה int, כי זה מצביע במקרה זה.

181
00:10:47,390 --> 00:10:49,650
צירוף מקרים שזה אחד ואותו הדבר עם int,

182
00:10:49,650 --> 00:10:51,970
אבל העובדה שיש שם פירושו כוכב זה הוא מצביע

183
00:10:51,970 --> 00:10:57,300
ובמכשיר, כמו במחשבים רבים, אך לא כולם, מצביעים הם 32 סיביים.

184
00:10:57,300 --> 00:11:01,850
על חומרה מודרנית יותר כמו מקינטוש האחרון, את המחשבים החדישים ביותר, שאולי יש לי מצביעים 64-bit,

185
00:11:01,850 --> 00:11:04,160
אבל במכשיר, הדברים האלה הם 32 סיביים.

186
00:11:04,160 --> 00:11:08,380
כך יהיו לנו סטנדרטיזציה על זה. באופן קונקרטי יותר, הסיפור הולך כך:

187
00:11:08,380 --> 00:11:10,820
אנחנו "להכריז" מצביע, מה זה אומר?

188
00:11:10,820 --> 00:11:12,810
אנחנו מכינים לאחסון כתובת זיכרון.

189
00:11:12,810 --> 00:11:15,530
מה זה אומר?

190
00:11:15,530 --> 00:11:19,810
אנו יוצרים משתנים בשם x שתופס 32 סיביים

191
00:11:19,810 --> 00:11:23,810
כי בקרוב יהיה לאחסן את הכתובת של מספר שלם.

192
00:11:23,810 --> 00:11:26,470
וזהו ככל הנראה על מדויקים כמו שאנחנו יכולים לקבל.

193
00:11:26,470 --> 00:11:31,810
זה בסדר נע קדימה על מנת לפשט את העולם, ורק אומרים להכריז מצביע נקרא x.

194
00:11:31,810 --> 00:11:35,380
להכריז מצביע, אך מבין ולהבין מה באמת קורה

195
00:11:35,380 --> 00:11:38,490
אפילו במרחק של רק כמה תווים אלה.

196
00:11:38,490 --> 00:11:42,040
>> עכשיו, זה כמעט קצת יותר קל, למרות שזה ביטוי ארוך יותר.

197
00:11:42,040 --> 00:11:48,160
אז מה זה עושה, שמודגש עכשיו: "malloc (10 * sizeof (int));" כן?

198
00:11:48,160 --> 00:11:52,350
[תשובת סטודנט, לא מובן]

199
00:11:52,350 --> 00:11:58,250
טוב. ואני אקח אותה לשם. זה הקצאת נתח הזיכרון עבור 10 מספרים שלמים.

200
00:11:58,250 --> 00:12:02,190
ועכשיו בואו לצלול קצת יותר עמוק; זה הקצאת נתח הזיכרון עבור 10 מספרים שלמים.

201
00:12:02,190 --> 00:12:05,390
מה malloc אז חוזר?

202
00:12:05,390 --> 00:12:10,390
הכתובת של נתח, או, באופן קונקרטי יותר, את הכתובת של הבית הראשון של שהנתח.

203
00:12:10,390 --> 00:12:14,080
אז איך אני, המתכנת, לדעת היכן שמסתיים נתח של הזיכרון?

204
00:12:14,080 --> 00:12:18,340
אני יודע שזה רציף. Malloc, מעצם הגדרתו, ייתן לך נתח רציף של זיכרון.

205
00:12:18,340 --> 00:12:21,240
אין פערים בזה. יש לך גישה לכל בתים שבגוש,

206
00:12:21,240 --> 00:12:26,760
גב אל גב אל גב, אבל איך אני יודע איפה סוף הנתח זה של זיכרון הוא?

207
00:12:26,760 --> 00:12:28,850
כאשר אתה משתמש malloc? [תשובת סטודנט, לא מובן] טוב.

208
00:12:28,850 --> 00:12:30,670
אתה לא יודע. צריכים לזכור.

209
00:12:30,670 --> 00:12:35,960
אני צריך לזכור שהייתי הערך 10, ואני אפילו לא נראה לי שעשיתי כאן.

210
00:12:35,960 --> 00:12:41,000
אבל את האחריות היא כולה עליי. Strlen, שנהיינו קצת סומך על למייתרים,

211
00:12:41,000 --> 00:12:45,860
עובד רק בגלל מוסכמות זה שיש \ 0

212
00:12:45,860 --> 00:12:48,840
או התו המיוחד הזה NUL, NUL, בסוף המחרוזת.

213
00:12:48,840 --> 00:12:51,740
שאינו מחזיק בנתחים שרירותיים רק של זיכרון.

214
00:12:51,740 --> 00:12:58,590
זה תלוי בך. אז קו 20, ולאחר מכן, מקצה נתח של זיכרון

215
00:12:58,590 --> 00:13:02,590
שיכול לאחסן 10 מספרים שלמים, והוא מאחסן את הכתובת של הבית הראשון

216
00:13:02,590 --> 00:13:05,610
שהנתח של הזיכרון בx משתנה בשם.

217
00:13:05,610 --> 00:13:11,140
מכאן, שהוא מצביע. אז 21 קו, למרבה הצער, הייתה טעות.

218
00:13:11,140 --> 00:13:16,110
אבל קודם, מה הוא עושה? זה אומר חנות במיקום 10, 0 אינדקס,

219
00:13:16,110 --> 00:13:19,480
מגוש הזיכרון נקרא x הערך 0.

220
00:13:19,480 --> 00:13:21,510
>> אז שם לב כמה דברים קורים.

221
00:13:21,510 --> 00:13:25,420
למרות x הוא מצביע, זוכר מלפני שבועות

222
00:13:25,420 --> 00:13:29,440
שאתה עדיין יכול להשתמש בסימון סוגר מרובע מערך בסגנון.

223
00:13:29,440 --> 00:13:36,180
כי זה בעצם סימון קצר יד לפעולות אריתמטיות על המצביעים מסתוריים למראה יותר.

224
00:13:36,180 --> 00:13:40,320
שבו אנחנו היו עושים משהו כזה: קח x הכתובת, העבר את 10 מקומות מעל,

225
00:13:40,320 --> 00:13:44,550
אז הולך לשם כדי שינה את הכתובה מאוחסנת באותו מקום.

226
00:13:44,550 --> 00:13:48,090
אבל בכנות, זה פשוט זוועה לקרוא ולהרגיש בנוח עם.

227
00:13:48,090 --> 00:13:52,900
אז העולם בדרך כלל משתמש בסוגריים המרובעים רק בגלל שזה כל כך הרבה יותר ידידותי לאדם לקריאה.

228
00:13:52,900 --> 00:13:55,140
אבל זה מה שבאמת קורה מתחת למכסת המנוע;

229
00:13:55,140 --> 00:13:58,190
x הוא כתובת, לא מערך, כשלעצמה.

230
00:13:58,190 --> 00:14:02,410
אז זה אחסון 0 במיקום 10 בx.

231
00:14:02,410 --> 00:14:06,120
למה זה רע? כן?

232
00:14:06,120 --> 00:14:17,370
[תשובת סטודנט, לא מובן] בדיוק.

233
00:14:17,370 --> 00:14:21,100
אנו הוקצינו רק 10 ints, אבל אנחנו סופרים מ0 כאשר תכנות ב-C,

234
00:14:21,100 --> 00:14:25,690
אז יש לך גישה ל0 1 2 3 4 5 6 7 8 9, אבל לא 10.

235
00:14:25,690 --> 00:14:30,270
אז או שהתכנית הולכת אשמת צינוק או שזה לא.

236
00:14:30,270 --> 00:14:32,900
אבל אנחנו לא ממש יודעים, זה סוג של התנהגות לא דטרמיניסטית.

237
00:14:32,900 --> 00:14:35,600
זה באמת תלוי בשאלות אם נהיה לנו מזל.

238
00:14:35,600 --> 00:14:40,650
אם אתברר שמערכת ההפעלה לא אכפת לי אם אני משתמש שבבתים נוספים,

239
00:14:40,650 --> 00:14:43,360
למרות שזה לא נתן לי את זה, התכנית שלי לא יכולה לקרוס.

240
00:14:43,360 --> 00:14:46,780
זה גולמי, זה עגלה, אבל ייתכן שלא תראו שסימפטום,

241
00:14:46,780 --> 00:14:48,960
או שאתה יכול לראות את זה רק פעם אחת בכמה זמן.

242
00:14:48,960 --> 00:14:51,230
אבל המציאות היא שהבאג הוא, למעשה, יש.

243
00:14:51,230 --> 00:14:54,320
וזה באמת בעייתי אם אתה כתבת תכנית שאתה רוצה להיות נכון,

244
00:14:54,320 --> 00:14:58,840
שמכרת את התכנית שהאנשים משתמשים שבכל פעם מתרסקת

245
00:14:58,840 --> 00:15:02,450
כי, כמובן, זה לא טוב. למעשה, אם יש לך טלפון אנדרואיד או iPhone

246
00:15:02,450 --> 00:15:05,550
ואתה מוריד אפליקציות בימים אלה, אם אי פעם היה לי אפליקציה פשוט להפסיק,

247
00:15:05,550 --> 00:15:10,040
פתאום הוא נעלם, זה כמעט תמיד נבע מהסיבה הקשורה לנושא זיכרון,

248
00:15:10,040 --> 00:15:12,830
לפי המתכנת דפוק וdereferenced מצביע

249
00:15:12,830 --> 00:15:18,670
שהוא או היא לא הייתה צריכה, והתוצאה של iOS או אנדרואיד הוא רק כדי להרוג את התכנית לגמרי

250
00:15:18,670 --> 00:15:23,080
ולא התנהגות בלתי מוגדרת סיכון או איזה סוג של פשרת אבטחה.

251
00:15:23,080 --> 00:15:25,950
>> יש באג אחד אחר בתכנית זו מלבד זה.

252
00:15:25,950 --> 00:15:30,180
מה עוד יש לי דפוק בתכנית זו?

253
00:15:30,180 --> 00:15:32,740
אני כבר לא התאמנתי מה שהטפתי לו. כן?

254
00:15:32,740 --> 00:15:34,760
[תשובת סטודנט, לא מובן] טוב.

255
00:15:34,760 --> 00:15:36,880
אני עדיין לא שחררתי את הזיכרון. אז כלל האצבע עכשיו

256
00:15:36,880 --> 00:15:43,150
צריך להיות בכל העת שאתה קורא malloc, עליך להתקשר חינם כאשר אתה עשית שימוש בזיכרון זה.

257
00:15:43,150 --> 00:15:45,610
עכשיו, כשאני הייתי רוצה לשחרר את הזיכרון הזה?

258
00:15:45,610 --> 00:15:49,780
כנראה, בהנחת הקו הראשון זה היה נכון, לא הייתי רוצה לעשות את זה כאן.

259
00:15:49,780 --> 00:15:55,710
כי אני לא יכול, למשל, לעשות את זה כאן. למה?

260
00:15:55,710 --> 00:15:57,860
רק מחוץ לתחום. אז למרות שאנחנו מדברים על מצביעים,

261
00:15:57,860 --> 00:16:04,830
זה שבוע 2 או 3 בעיה, כאשר x הוא רק בהיקפה הפנימי של הסוגריים המסולסלים שבו הוכרז.

262
00:16:04,830 --> 00:16:11,000
אז אתה בהחלט לא יכול לשחרר אותו שם. הסיכוי היחיד שלי כדי לשחרר אותו הוא בערך אחרי 21 שורות.

263
00:16:11,000 --> 00:16:15,170
זוהי תכנית פשוטה למדי, זה היה די קל ברגע שאתה סוג של עטף את דעתך

264
00:16:15,170 --> 00:16:17,870
סביב מה התכנית עושה, שבו היו טעויות.

265
00:16:17,870 --> 00:16:20,500
וגם אם אתה לא רואה את זה בהתחלה, אני מקווה שזה קצת ברור עכשיו

266
00:16:20,500 --> 00:16:23,870
שהטעויות האלה נפתרות די בקלות ועשויה בקלות.

267
00:16:23,870 --> 00:16:28,720
אך כאשר תכנית היא ארוך יותר מ 12 קווים, זה עוד 50 קווים, 100 קווים ארוך,

268
00:16:28,720 --> 00:16:31,150
הליכה בקו הקוד שלך על ידי קו מחשבה המעמיקה על כל זה בהיגיון,

269
00:16:31,150 --> 00:16:35,110
אפשרי אבל לא במיוחד כיף לעשות, כל זמן מחפש באגים,

270
00:16:35,110 --> 00:16:38,340
וזה גם קשה לעשות, וזו הסיבה שכלי כמו Valgrind קיים.

271
00:16:38,340 --> 00:16:40,900
תן לי ללכת קדימה ולעשות את זה: תן לי לפתוח את חלון המסוף שלי,

272
00:16:40,900 --> 00:16:45,400
והרשו לי לא פשוט להפעיל זיכרון, כי זיכרון נראה בסדר.

273
00:16:45,400 --> 00:16:49,180
אני מקבל מזל. הולכים לבתים נוספים בסוף המערך

274
00:16:49,180 --> 00:16:51,060
לא נראה לי בעייתי מדי.

275
00:16:51,060 --> 00:16:56,370
אבל תרשה לי, בכל זאת, לעשות בדיקת שפיות, שרק אומר שכדי לבדוק

276
00:16:56,370 --> 00:16:58,320
אם זה הוא למעשה נכון.

277
00:16:58,320 --> 00:17:04,690
>> אז בואו נעשיתי valgrind-v - דליפה לבדוק = מלא,

278
00:17:04,690 --> 00:17:07,520
ולאחר מכן את שמה של התכנית במקרה זה הוא זיכרון, לא a.out.

279
00:17:07,520 --> 00:17:10,760
אז תן לי ללכת קדימה ולעשות את זה. על Enter.

280
00:17:10,760 --> 00:17:14,109
אלוהים יקר. זה הפלט שלה, וזה מה שנאמרתי קודם לכן.

281
00:17:14,109 --> 00:17:17,550
אבל, אם אתה לומד לקרוא בדרך את כל השטויות כאן,

282
00:17:17,550 --> 00:17:20,760
ביותר לכך הוא פשוט פלט אבחון זה לא כל כך מעניין.

283
00:17:20,760 --> 00:17:24,829
מה העיניים שלך באמת רוצות להיות מחפשות הוא כל אזכור של טעות או לא חוקי.

284
00:17:24,829 --> 00:17:26,800
מילים המרמזות על בעיות.

285
00:17:26,800 --> 00:17:29,340
ואכן, בואו לראות מה השתבש כאן למטה.

286
00:17:29,340 --> 00:17:35,230
יש לי סיכום כלשהו, ​​"בשימוש ביציאה:. 40 בתים ב1 רחובות"

287
00:17:35,230 --> 00:17:38,750
אני לא ממש בטוח מה הוא בלוק, אבל 40 בתים

288
00:17:38,750 --> 00:17:41,260
ממש מרגיש כאילו אני יכול להבין מהאיפה זה מגיע.

289
00:17:41,260 --> 00:17:45,030
40 בתים. למה הם 40 בתים בשימוש ביציאה?

290
00:17:45,030 --> 00:17:48,780
ולייתר דיוק, אם אנחנו לגלול למטה כאן,

291
00:17:48,780 --> 00:17:54,520
לכן אני בהחלט אבדתי 40 בתים? כן?

292
00:17:54,520 --> 00:17:59,520
[תשובת סטודנט, לא מובן] מושלם. כן, בדיוק.

293
00:17:59,520 --> 00:18:03,540
היו עשרה מספרים שלמים, וכל אחד מאלה הם גודל של 4, או 32 סיביים,

294
00:18:03,540 --> 00:18:08,300
כך אבדתי בדיוק 40 בתים, כי, כפי שההצעה, לא נקרא חופשי.

295
00:18:08,300 --> 00:18:13,460
זה באג אחד, ועכשיו בואו נסתכל למטה עוד קצת ולראות לצד זה,

296
00:18:13,460 --> 00:18:16,900
"לא חוקי לכתוב בגודל 4". מה קורה פה?

297
00:18:16,900 --> 00:18:21,150
כתובת זו בטאה את מה שתיווי בסיס, כנראה?

298
00:18:21,150 --> 00:18:23,640
זה הקסדצימלי, וכל פעם שאתה רואה את מספר התחלה עם 0x,

299
00:18:23,640 --> 00:18:29,410
זה אומר ההקסדצימלי, כפי שאכן עשה בדרך חזרה, אני חושב, קטע של 0 pset של שאלות,

300
00:18:29,410 --> 00:18:34,090
שהיה רק ​​כדי לעשות את תרגיל חימום, המרה עשרונית לקסדצימלי לינארי וכך הלאה.

301
00:18:34,090 --> 00:18:39,220
הקסדצימלי, פשוט על ידי כינוס אנושי, משמש בדרך כלל כדי לייצג את המצביעים

302
00:18:39,220 --> 00:18:41,570
או, באופן כללי יותר, מתייחס. זה פשוט כנס,

303
00:18:41,570 --> 00:18:45,340
כי זה קצת יותר קל לקריאה, זה קצת יותר קומפקטי מאשר משהו כמו עשרוני,

304
00:18:45,340 --> 00:18:47,720
ובינארי הוא חסר תועלת עבור רוב בני האדם לשימוש.

305
00:18:47,720 --> 00:18:50,840
אז עכשיו מה זה אומר? ובכן, זה נראה כאילו יש כתיבה לא חוקית

306
00:18:50,840 --> 00:18:54,480
בגודל 4 על 21 קו memory.c.

307
00:18:54,480 --> 00:18:59,180
אז בואו נחזור לקו 21, ואכן, כאן היא שכתיבה לא חוקית.

308
00:18:59,180 --> 00:19:02,640
אז Valgrind לא הולך להחזיק לחלוטין ידי ואומר לי מה הוא התיקון,

309
00:19:02,640 --> 00:19:05,520
אבל זה הוא גילוי שאני עושה לכתוב חוקי.

310
00:19:05,520 --> 00:19:08,800
אני נוגע בי 4 בתים שאני לא צריך להיות, וכנראה שזה בגלל,

311
00:19:08,800 --> 00:19:13,960
כפי שציינת, אני עושה [10] במקום [9] מקסימאלי

312
00:19:13,960 --> 00:19:16,660
או [0] או משהו באמצע.

313
00:19:16,660 --> 00:19:19,690
עם Valgrind, מבין כל זמן עכשיו אתה כותב תכנית

314
00:19:19,690 --> 00:19:24,190
המשתמש במצביעים ומשתמש בזיכרון, וmalloc לייתר דיוק,

315
00:19:24,190 --> 00:19:27,080
בהחלט להיכנס להרגל של ריצה ארוכה זה

316
00:19:27,080 --> 00:19:30,890
אך יועתק בקלות ולהדביק פיקוד Valgrind

317
00:19:30,890 --> 00:19:32,650
כדי לראות אם יש כמה טעויות שהיו שם.

318
00:19:32,650 --> 00:19:34,820
וזה יהיה מכריע בכל פעם שאתה רואה את הפלט,

319
00:19:34,820 --> 00:19:39,430
אלא רק לנתח דרך ויזואלית את כל התפוקה ולראות אם אתה רואה אזכורים של טעויות

320
00:19:39,430 --> 00:19:43,190
או אזהרות או לא חוקי או שאבד.

321
00:19:43,190 --> 00:19:46,200
כל אחת ממילים שנשמעים כמו פשלת איפשהו.

322
00:19:46,200 --> 00:19:48,580
אז מבין שזה כלי חדש בארגז הכלים שלך.

323
00:19:48,580 --> 00:19:51,270
>> עכשיו ביום שני, היו לנו חבורה שלמה של אנשים לבוא לכאן

324
00:19:51,270 --> 00:19:53,150
ומייצג את הרעיון של רשימה מקושרת.

325
00:19:53,150 --> 00:20:00,970
והצגנו את הרשימה המקושרת כפתרון למה בעיה?

326
00:20:00,970 --> 00:20:04,590
כן? [תשובת סטודנט, לא מובן] טוב.

327
00:20:04,590 --> 00:20:06,530
מערכים לא יכולים להיות זיכרון הוסיף להם.

328
00:20:06,530 --> 00:20:09,440
אם אתה מקצה מערך בגודל 10, זה כל מה שאתה מקבל.

329
00:20:09,440 --> 00:20:13,690
אתה יכול לקרוא לפונקציה כמו realloc אם נקרא בתחילה malloc,

330
00:20:13,690 --> 00:20:17,580
וכי ניתן לנסות לגדול מערך אם יש מקום לקראת הסוף זה

331
00:20:17,580 --> 00:20:21,610
שאף אחד אחר לא משתמש, ואם אין, זה יהיה פשוט למצוא לך נתח גדול יותר במקום אחר.

332
00:20:21,610 --> 00:20:25,040
אבל אז זה יהיה להעתיק את כל הבתים האלה למערך החדש.

333
00:20:25,040 --> 00:20:28,310
זה נשמע כמו פתרון מאוד נכון.

334
00:20:28,310 --> 00:20:34,790
למה זה לא מושך?

335
00:20:34,790 --> 00:20:36,940
אני מתכוון שזה עובד, בני האדם פתרו בעיה זו.

336
00:20:36,940 --> 00:20:40,710
למה אנחנו לא צריכים לפתור אותה ביום שני עם רשימות מקושרות? כן?

337
00:20:40,710 --> 00:20:44,060
[תשובת סטודנט, לא מובן] זה יכול לקחת זמן רב.

338
00:20:44,060 --> 00:20:49,260
למעשה, בכל פעם שאתה קורא malloc או realloc או calloc, שהוא עוד אחד,

339
00:20:49,260 --> 00:20:52,470
כל פעם שאתה, תכנית, מדברים על מערכת ההפעלה,

340
00:20:52,470 --> 00:20:54,310
אתם נוטים להאט את התכנית.

341
00:20:54,310 --> 00:20:57,470
ואם אתה עושה דברים כאלה בלולאות, אתה באמת האטה.

342
00:20:57,470 --> 00:21:00,740
אתה לא הולך לשים לב לזה הפשוט ביותר של "שלום עולם" תוכניות מסוג,

343
00:21:00,740 --> 00:21:04,300
אבל בתוכניות הרבה יותר גדולות, ובקש את מערכת ההפעלה שוב ושוב לזיכרון

344
00:21:04,300 --> 00:21:07,520
או להחזיר אותו שוב ושוב נוטה שלא להיות דבר טוב.

345
00:21:07,520 --> 00:21:11,210
בנוסף, זה פשוט סוג של בחינה אינטלקטואלית - זה בזבוז זמן מוחלט.

346
00:21:11,210 --> 00:21:16,490
למה להקצות יותר ויותר זיכרון, סיכון מעתיק הכל לתוך המערך החדש,

347
00:21:16,490 --> 00:21:21,980
אם יש לך חלופה שמאפשרת לך להקצות רק כמות זיכרון שאתה בעצם צריך?

348
00:21:21,980 --> 00:21:24,130
אז יש יתרונות וחסרונות בפה.

349
00:21:24,130 --> 00:21:26,730
האחד הפלוסים כרגע הוא שיש לנו דינמי.

350
00:21:26,730 --> 00:21:29,100
לא משנה איפה הגושים של זיכרון הם שהם בחינם,

351
00:21:29,100 --> 00:21:32,070
אני רק יכול כאילו ליצור פירורי לחם אלה באמצעות מצביעים

352
00:21:32,070 --> 00:21:34,470
כדי לקשור את כל הרשימה המקושרת שלי ביחד.

353
00:21:34,470 --> 00:21:36,470
אבל אני משלם מחיר אחד לפחות.

354
00:21:36,470 --> 00:21:40,060
>> מה יש לי לוותר בצובר רשימות מקושרות?

355
00:21:40,060 --> 00:21:42,470
כן? [תשובת סטודנט, לא מובן] טוב.

356
00:21:42,470 --> 00:21:45,650
אתה צריך יותר זיכרון. עכשיו אני צריך מקום למצביעים אלו,

357
00:21:45,650 --> 00:21:47,900
ובמקרה של רשימה מקושרת פשוטה סופר

358
00:21:47,900 --> 00:21:51,410
כי הוא מנסה רק כדי לאחסן מספרים שלמים, שהם 4 בתים, אנחנו כל זמן אומרים

359
00:21:51,410 --> 00:21:54,240
כן, מצביע הוא 4 בתים, אז עכשיו אני ממש הכפלתי

360
00:21:54,240 --> 00:21:57,290
כמות הזיכרון שאני צריך רק כדי לאחסן רשימה זו.

361
00:21:57,290 --> 00:21:59,680
אבל שוב, זה תחלופה מתמדת במדעי מחשב

362
00:21:59,680 --> 00:22:03,440
בין הזמן ומרחב ופיתוח, מאמץ ומשאבים אחרים.

363
00:22:03,440 --> 00:22:06,630
מה חסרון נוסף של שימוש ברשימה מקושרת? כן?

364
00:22:06,630 --> 00:22:10,150
[תשובת סטודנט, לא מובן]

365
00:22:10,150 --> 00:22:12,600
טוב. לא קל לגישה. אנחנו כבר לא יכולים למנף

366
00:22:12,600 --> 00:22:15,530
שבוע 0 עקרונות כמו פרד ומשול.

367
00:22:15,530 --> 00:22:18,220
ולייתר דיוק, חיפוש בינארי. כי למרות שאנו, בני אדם

368
00:22:18,220 --> 00:22:20,400
תוכל לראות היכן בערך באמצע הרשימה זו הוא,

369
00:22:20,400 --> 00:22:25,840
המחשב רק יודע שרשימה מקושרת זה מתחילה בכתובת בשם הראשון.

370
00:22:25,840 --> 00:22:28,250
וזה 0x123 או משהו כזה.

371
00:22:28,250 --> 00:22:30,990
והדרך היחידה התכנית יכולה למצוא את אלמנט האמצע

372
00:22:30,990 --> 00:22:33,350
הוא למעשה לחפש את הרשימה כולה.

373
00:22:33,350 --> 00:22:35,500
וגם אז, זה פשוטו כמשמעו, יש לחפש את הרשימה כולה, כי

374
00:22:35,500 --> 00:22:38,950
אפילו ברגע שאתה מגיע לאלמנט האמצע ידי ביצוע המצביעים,

375
00:22:38,950 --> 00:22:42,380
, את התכנית, אין לי מושג כמה זמן רשימה זו היא, באופן פוטנציאלי,

376
00:22:42,380 --> 00:22:45,250
עד שתגיע לקצה שלו, ואיך אתה יודע תכנותי

377
00:22:45,250 --> 00:22:48,600
כי אתה בסוף הרשימה מקושרת?

378
00:22:48,600 --> 00:22:51,120
יש מצביע NULL מיוחד, אז שוב, אמנה.

379
00:22:51,120 --> 00:22:53,870
במקום להשתמש מצביע זה, אנחנו בהחלט לא רוצים שזה יהיה קצת ערך זבל

380
00:22:53,870 --> 00:22:57,750
מצביע מבמה אי שם, אנחנו רוצים שזה יהיה יד למטה, NULL,

381
00:22:57,750 --> 00:23:01,530
כך שיש לנו תחנה סופית זה במבנה נתונים זה כדי שנדע איפה זה ייגמר.

382
00:23:01,530 --> 00:23:03,410
>> מה אם אנחנו רוצים לטפל בזה?

383
00:23:03,410 --> 00:23:05,980
אנחנו עשינו את רוב החזותיים הזה, ועם בני אדם,

384
00:23:05,980 --> 00:23:07,630
אבל מה אם אנחנו רוצים לעשות כניסה?

385
00:23:07,630 --> 00:23:12,360
אז ברשימה המקורית הייתה 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
מה אם אז רציתי חלל malloc למספר 55, צומת עבורו,

387
00:23:16,730 --> 00:23:20,730
ואז אנחנו רוצים להכניס 55 לרשימה בדיוק כפי שעשינו ביום שני?

388
00:23:20,730 --> 00:23:23,690
איך עושים את זה? ובכן, אניטה עלתה והיא בעצם נכנסה לרשימה.

389
00:23:23,690 --> 00:23:27,500
היא החלה במרכיב הראשון, אז הבאה, הבא, הבא, הבא, הבא.

390
00:23:27,500 --> 00:23:29,500
לבסוף פגע בכל הדרך השמאלית למטה

391
00:23:29,500 --> 00:23:34,480
והבנתי אה, זה הוא ריק. אז מניפולצית מצביע מה שהיה צריכה לעשות?

392
00:23:34,480 --> 00:23:37,980
האדם שהיה בסופו של דבר, המספר 34, צריך ידו השמאלית מורמת

393
00:23:37,980 --> 00:23:46,220
כדי להצביע על 55, 55 נזקקו הזרוע השמאלית שלהם כלפי מטה כדי להיות NULL השליחות הקטלנית החדשה. עשה.

394
00:23:46,220 --> 00:23:49,540
די קל להכניס 55 לרשימה ממוינת.

395
00:23:49,540 --> 00:23:51,800
ואיך ייתכן שזה נראה?

396
00:23:51,800 --> 00:23:55,690
>> תן לי ללכת קדימה, לפתוח את חלק קוד דוגמה כאן.

397
00:23:55,690 --> 00:23:58,120
אני אפתח את gedit, ותן לי לפתוח את שני קבצים ראשונים.

398
00:23:58,120 --> 00:24:02,050
אחת הוא list1.h, ותן לי רק להזכיר שזה היה הנתח של קוד

399
00:24:02,050 --> 00:24:04,920
שאנו משמשים כדי לייצג צומת.

400
00:24:04,920 --> 00:24:13,040
צומת יש גם int בשם n ומצביע בשם הבא שרק נקודות לדבר הבא ברשימה.

401
00:24:13,040 --> 00:24:15,450
זה עכשיו ב. קובץ h. למה?

402
00:24:15,450 --> 00:24:19,090
יש אמנה זו, ואנחנו לא נצלנו את זה כמות עצם ענקיות,

403
00:24:19,090 --> 00:24:22,220
אבל מי שכתב את פונקציות printf ואחרות

404
00:24:22,220 --> 00:24:27,150
נתן במתנה לעולם כל הפונקציות הללו על ידי כתיבת קובץ בשם stdio.h.

405
00:24:27,150 --> 00:24:30,950
ואז יש string.h, ואז יש map.h, ויש את כל הקבצים האלה h

406
00:24:30,950 --> 00:24:34,410
שאולי ראה או השתמשתי במונח נכתב על ידי אנשים אחרים.

407
00:24:34,410 --> 00:24:38,470
בדרך כלל באלה. קבצי h דברים בלבד כמו typedefs

408
00:24:38,470 --> 00:24:42,310
או הצהרות של סוגים או הצהרות של קבועים מותאמים אישית.

409
00:24:42,310 --> 00:24:47,890
אתה לא שמת את ההטמעות 'פונקציות בקבצי כותרת.

410
00:24:47,890 --> 00:24:50,570
אתה שם, במקום, רק אב הטיפוס שלהם.

411
00:24:50,570 --> 00:24:53,050
אתה שם את הדברים שאתה רוצה לחלוק עם העולם את מה שהם צריכים

412
00:24:53,050 --> 00:24:55,640
כדי לקמפל את הקוד שלהם. אז רק כדי להיכנס להרגל הזה,

413
00:24:55,640 --> 00:24:59,110
החלטנו לעשות את אותו דבר. אין הרבה בlist1.h,

414
00:24:59,110 --> 00:25:02,070
אבל אנחנו שמנו משהו שעשוי לעניין את האנשים בעולם

415
00:25:02,070 --> 00:25:05,030
שרוצה להשתמש ביישום הרשימה המקושר שלנו.

416
00:25:05,030 --> 00:25:08,040
עכשיו, בlist1.c, אני לא עובר את כל העניין הזה

417
00:25:08,040 --> 00:25:11,390
כי זה קצת ארוך, זה תכנית, אבל בואו להפעיל אותו במהירות אמיתית בשורת הפקודה.

418
00:25:11,390 --> 00:25:15,720
בואו לאסוף אותי List1, תן לי לאחר מכן להפעיל List1, ומה שתראה הוא

419
00:25:15,720 --> 00:25:18,070
יש לנו מדומה תכנית קטנה ופשוט כאן

420
00:25:18,070 --> 00:25:20,990
זה הולך כדי לאפשר לי להוסיף ולהסיר מספרים לרשימה.

421
00:25:20,990 --> 00:25:24,310
אז תן לי ללכת קדימה וסוג 3 ל3 אפשרות התפריט.

422
00:25:24,310 --> 00:25:27,880
אני רוצה להכניס את המספר - בואו נעשה את המספר הראשון, שהיה 9,

423
00:25:27,880 --> 00:25:30,550
ועכשיו אומר לי שהרשימה היא עכשיו 9.

424
00:25:30,550 --> 00:25:33,760
תן לי ללכת קדימה ולעשות הכנסה נוספת, ולכן אני מכה אפשרות תפריט 3.

425
00:25:33,760 --> 00:25:36,760
מה מספר אני רוצה להוסיף? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. ואני אעשה רק עוד אחד.

427
00:25:39,220 --> 00:25:41,720
בואו יכניסו לי את המספר 22.

428
00:25:41,720 --> 00:25:45,850
אז יש לנו את ראשיתה של הרשימה המקושרת שהיו לנו בצורת שקופית לפני רגע.

429
00:25:45,850 --> 00:25:48,740
איך הכנסה זו אכן קורית?

430
00:25:48,740 --> 00:25:52,000
ואכן, 22 הם עכשיו בסוף הרשימה.

431
00:25:52,000 --> 00:25:55,050
אז הסיפור שספרנו על במה ביום שני ורק עכשיו recapped

432
00:25:55,050 --> 00:25:57,460
חייב להיות ממש קורה בקוד.

433
00:25:57,460 --> 00:25:59,700
בואו נעיף מבט. בואו לגלול למטה בקובץ זה.

434
00:25:59,700 --> 00:26:01,720
אנחנו לחפות על חלק מהפונקציות,

435
00:26:01,720 --> 00:26:05,630
אבל אנחנו ניסע, נניח, להוספת הפונקציה.

436
00:26:05,630 --> 00:26:11,720
>> בואו לראות איך אנחנו הולכים על החדרת צומת חדש לרשימה מקושרת זה.

437
00:26:11,720 --> 00:26:14,550
איפה הרשימה מוכרזת? ובכן, בואו לגלול את כל הדרך למעלה בחלק העליון,

438
00:26:14,550 --> 00:26:19,970
ושימו לב שהרשימה המקושרת שלי הכריזה למעשה כמצביע יחיד שתחילה NULL.

439
00:26:19,970 --> 00:26:23,180
אז אני משתמש במשתנה הגלובלית כאן, שבאופן כללי יש לנו הטפתי נגד

440
00:26:23,180 --> 00:26:25,280
כי זה עושה את הקוד שלך קצת מבולגן לשמור,

441
00:26:25,280 --> 00:26:29,080
זה סוג של עצלן, בדרך כלל, אבל זה לא עצלן וזה לא בסדר וזה לא רע

442
00:26:29,080 --> 00:26:33,660
אם כל המטרה של התכנית שלך בחיים היא לדמות רשימה מקושרת אחד.

443
00:26:33,660 --> 00:26:35,460
וזה בדיוק מה שאנחנו עושים.

444
00:26:35,460 --> 00:26:39,100
אז במקום להכריז בזה ראשי ולאחר מכן יש להעביר אותו לכל פונקציה

445
00:26:39,100 --> 00:26:42,640
אנחנו כתבנו בתכנית זו, אנו מבינים במקום הו, בואו פשוט לעשות את זה גלובלי

446
00:26:42,640 --> 00:26:47,060
כי כל המטרה של תכנית זו היא להדגים רשימה אחת ורק אחת קשורה.

447
00:26:47,060 --> 00:26:50,700
אז זה מרגיש בסדר. הנה אבות הטיפוס שלי, ואנחנו לא נעבור על כל אלה,

448
00:26:50,700 --> 00:26:55,800
אבל כתבתי פונקצית מחיקה, פונקציה מוצאת, הוספת פונקציה, ופונקציה חוצה.

449
00:26:55,800 --> 00:26:59,080
אבל בואו עכשיו יורדים חזרה לפונקציית ההוספה

450
00:26:59,080 --> 00:27:01,490
ולראות איך זה עובד כאן.

451
00:27:01,490 --> 00:27:09,940
הוספה היא על קו - הנה זה בא.

452
00:27:09,940 --> 00:27:12,850
הוסף. אז זה לא לוקח כל טיעונים, כי אנחנו הולכים לשאול

453
00:27:12,850 --> 00:27:15,930
בתוך המשתמש של פונקציה זו למספר שהם רוצים להוסיף.

454
00:27:15,930 --> 00:27:19,410
אבל קודם, אנחנו מכינים כדי לתת להם קצת מרחב.

455
00:27:19,410 --> 00:27:22,050
זה סוג של העתקה והדבקה מהדוגמא הקודמת.

456
00:27:22,050 --> 00:27:25,110
במקרה זה, הייתי הקצאת int, הפעם אנחנו הקצאת צומת.

457
00:27:25,110 --> 00:27:27,910
אני לא ממש זוכר כמה בתי צומת היא, אבל זה בסדר.

458
00:27:27,910 --> 00:27:30,460
Sizeof יכול להבין את זה בשבילי.

459
00:27:30,460 --> 00:27:33,340
ולמה אני בודק NULL בקו 120?

460
00:27:33,340 --> 00:27:37,530
מה יכול להיות רע בקו 119? כן?

461
00:27:37,530 --> 00:27:40,530
[תשובת סטודנט, לא מובן]

462
00:27:40,530 --> 00:27:43,440
טוב. פשוט יכול להיות מקרה שאני מבקש יותר מדי זיכרון

463
00:27:43,440 --> 00:27:47,020
או משהו במערכת ההפעלה של ורע אין מספיק בתים כדי לתת לי,

464
00:27:47,020 --> 00:27:50,640
כך הוא מאותת באותה מידה על ידי חזרת NULL, ואם אני לא בודק של

465
00:27:50,640 --> 00:27:54,710
ואני פשוט עיוור להמשיך להשתמש בכתובה חזרה, זה יכול להיות NULL.

466
00:27:54,710 --> 00:27:58,400
זה יכול להיות ערך כלשהו לא ידוע, לא דבר טוב, אלא אם כן אני -

467
00:27:58,400 --> 00:28:00,590
למעשה לא יהיה ערך לא ידוע. זה יכול להיות NULL, ולכן אני לא רוצה

468
00:28:00,590 --> 00:28:02,550
להתעלל בו ולהסתכן בביטול הפניה זה.

469
00:28:02,550 --> 00:28:07,410
אם זה יקר, אני רק אחזור ונעמיד פנים כאילו אני לא אחזור כל זיכרון בכלל.

470
00:28:07,410 --> 00:28:12,270
>> אחרת, אני אומר לי המשתמש נתן לי מספר להוסיף, אני קורא GetInt הידיד הוותיק שלנו,

471
00:28:12,270 --> 00:28:15,530
ואז זה היה התחביר החדש שהצגנו ביום שני.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' הפירוש תיקח את הכתובת שניתנה לך על ידי malloc

473
00:28:20,320 --> 00:28:23,490
המייצג את הבית הראשון של אובייקט צומת חדש,

474
00:28:23,490 --> 00:28:26,860
ואז ללכת לשדה בשם n.

475
00:28:26,860 --> 00:28:35,270
שאלת טריוויה קטנה: זה שווה את מה שהשורה סתומה עוד יותר של קוד?

476
00:28:35,270 --> 00:28:38,110
אחרת איך יכולתי לכתוב את זה? רוצה לקחת דקירה?

477
00:28:38,110 --> 00:28:41,480
[תשובת סטודנט, לא מובן]

478
00:28:41,480 --> 00:28:44,870
טוב. שימוש. N, אבל זה לא ממש פשוט כמו זה.

479
00:28:44,870 --> 00:28:47,090
מה אני קודם צריך לעשות? [תשובת סטודנט, לא מובן]

480
00:28:47,090 --> 00:28:52,730
טוב. אני צריך לעשות * newptr.n.

481
00:28:52,730 --> 00:28:55,610
אז זה אומר מצביע חדש ברור כתובת. למה?

482
00:28:55,610 --> 00:28:59,520
כי זה הוחזר על ידי malloc. Newptr * אומר "ללכת לשם"

483
00:28:59,520 --> 00:29:02,970
ואז ברגע שאתה שם, אז אתה יכול להשתמש בהרבה יותר מוכר. n,

484
00:29:02,970 --> 00:29:05,730
אבל זה רק נראה קטן ומכוער, במיוחד אם אנו בני האדם הולכים

485
00:29:05,730 --> 00:29:10,360
לצייר עם חצי מצביעים כל הזמן; העולם יש טופל על סימון החץ הזה,

486
00:29:10,360 --> 00:29:12,320
שעושה בדיוק את אותו הדבר.

487
00:29:12,320 --> 00:29:16,070
אז אתה משתמש רק -> סימון כאשר הדבר בצד השמאל הוא מצביע.

488
00:29:16,070 --> 00:29:18,790
אחרת, אם זה struct בפועל, השתמש. N.

489
00:29:18,790 --> 00:29:25,800
ואז זה: מדוע אני לאתחל newptr-> ליד NULL?

490
00:29:25,800 --> 00:29:28,610
אנחנו לא רוצים שיד שמאל שלו משתלשלת מסיום השלב.

491
00:29:28,610 --> 00:29:31,630
אנחנו רוצים שהוא מצביע ישר למטה, מה שאומר בסוף הרשימה זו

492
00:29:31,630 --> 00:29:34,980
עלול להיות בצומת הזו, כך שעדיף שלוודא שהוא NULL.

493
00:29:34,980 --> 00:29:38,460
וגם, באופן כללי, אתחול המשתנים שלך או החברים שלך ונתוני structs

494
00:29:38,460 --> 00:29:40,470
למשהו הוא פשוט תרגול טוב.

495
00:29:40,470 --> 00:29:45,170
פשוט לתת לאשפה קיימת ותמשיך להתקיים, בדרך כלל מקבלת אותך בצרות

496
00:29:45,170 --> 00:29:48,650
אם שכחת לעשות משהו בהמשך.

497
00:29:48,650 --> 00:29:51,590
>> הנה כמה מקרים. זה, שוב, הוא הוספת הפונקציה,

498
00:29:51,590 --> 00:29:54,930
והדבר הראשון שאני בודק הוא אם למשתנה בשם הראשון,

499
00:29:54,930 --> 00:29:58,240
שמשתנים הגלובלי הוא NULL, זה אומר שאין רשימה מקושרת.

500
00:29:58,240 --> 00:30:02,460
אנחנו לא הכנסנו את כל מספרים, כך שזה טריוויאלי להכניס מספר הנוכחי

501
00:30:02,460 --> 00:30:05,240
לרשימה, מכיוון שזה שייך בתחילת הרשימה.

502
00:30:05,240 --> 00:30:08,100
אז זה היה כאשר אניטה פשוט עמדה לכאן לבד, מעמיד פן

503
00:30:08,100 --> 00:30:11,390
אף אחד אחר לא היה כאן על במה עד שהוקצינו צומת,

504
00:30:11,390 --> 00:30:13,940
אז היא יכולה להרים את ידה בפעם הראשונה,

505
00:30:13,940 --> 00:30:17,420
אם כל אחד אחר היה לעלות על הבמה אחריה ביום שני.

506
00:30:17,420 --> 00:30:22,900
עכשיו הוא כאן, זו בדיקה קטנה שבו אני חייב לומר שאם הערך של צומת החדש של n

507
00:30:22,900 --> 00:30:27,370
הוא <הערך של n בצומת הראשונה הנוכחית,

508
00:30:27,370 --> 00:30:29,930
זה אומר שיש רשימה מקושרת שהחלה.

509
00:30:29,930 --> 00:30:32,330
יש צומת אחת לפחות ברשימה, אבל הבחור החדש

510
00:30:32,330 --> 00:30:37,230
שייך לפניו, כך שאנחנו צריכים להעביר דברים.

511
00:30:37,230 --> 00:30:43,450
במילים אחרות, אם ברשימה החלה רק עם, יניח,

512
00:30:43,450 --> 00:30:48,100
רק מספר 17, זה - למעשה, אנחנו יכולים לעשות את זה בצורה ברורה יותר.

513
00:30:48,100 --> 00:30:56,010
אם תתחילו את הסיפור שלנו עם מצביע כאן התקשר בפעם הראשונה

514
00:30:56,010 --> 00:30:59,870
ותחילה זה NULL, ואנו מוסיפים את המספר 9,

515
00:30:59,870 --> 00:31:02,510
המספר 9 שייך בבירור בתחילת הרשימה.

516
00:31:02,510 --> 00:31:07,400
אז בואו נעמיד פן שאנחנו רק malloced כתובת או המספר 9 והכנסנו אותו לכאן.

517
00:31:07,400 --> 00:31:13,170
אם הראשון הוא 9 כברירת מחדל, התרחיש הראשון דנו רק אומר ששלב זה בחור בואו לכאן,

518
00:31:13,170 --> 00:31:15,790
תשאיר את זה כNULL; עכשיו יש לנו את המספר 9.

519
00:31:15,790 --> 00:31:18,280
המספר הבא אנחנו רוצים להכניס הוא 17.

520
00:31:18,280 --> 00:31:22,420
17 שייכים לכאן, ולכן אנחנו הולכים לעשות קצת קפיצה לוגית בזה.

521
00:31:22,420 --> 00:31:26,060
אז בואו במקום, לפני שאנחנו עושים את זה, בואו נעמיד פן שאנחנו רוצים להכניס את המספר 8.

522
00:31:26,060 --> 00:31:28,650
>> אז רק לצורך הנוחות, אני הולך לצייר כאן.

523
00:31:28,650 --> 00:31:30,760
אבל זכור, malloc יכול לשים אותו ביותר בכל מקום.

524
00:31:30,760 --> 00:31:33,460
אבל למען השם, הציור, אני אשים את זה כאן.

525
00:31:33,460 --> 00:31:38,440
אז להעמיד פן שזה עתה הוקצה צומת עבור המספר 8; זה הוא NULL כברירת מחדל.

526
00:31:38,440 --> 00:31:42,800
מה עכשיו צריך לקרות? כמה דברים.

527
00:31:42,800 --> 00:31:47,090
אנחנו עשינו את הטעות הזאת על במה ביום שני שבו אנחנו מתעדכנים מצביע כזה,

528
00:31:47,090 --> 00:31:51,890
אז עשה את זה, ואז אנחנו טוענים - אנחנו מיותמים כולם על במה.

529
00:31:51,890 --> 00:31:54,350
מכיוון שאתה לא יכול - סדר פעולות כאן הוא חשוב,

530
00:31:54,350 --> 00:31:58,760
כי עכשיו אנחנו כבר אבדנו 9 צומת זה שהוא פשוט סוג של מרחף בחלל.

531
00:31:58,760 --> 00:32:01,150
אז זו לא הייתה הגישה הנכונה ביום שני.

532
00:32:01,150 --> 00:32:03,330
תחילה עלינו לעשות משהו אחר.

533
00:32:03,330 --> 00:32:06,280
מצבו של העולם נראה כך. בתחילה, 8 הוקצו.

534
00:32:06,280 --> 00:32:10,550
מה יהיה דרך טובה יותר להכניס 8?

535
00:32:10,550 --> 00:32:14,720
במקום לעדכן את המצביע זה ראשון, רק לעדכן את זה כאן במקום.

536
00:32:14,720 --> 00:32:17,720
אז אנחנו צריכים שורת הקוד שהולכת להפוך את דמות NULL זה

537
00:32:17,720 --> 00:32:22,020
למצביע שבפועל מצביע בשעת 9 בצומת,

538
00:32:22,020 --> 00:32:27,970
ואז אנו יכולים בבטחה לשנות תחילה להצביע על הבחור הזה כאן.

539
00:32:27,970 --> 00:32:31,330
עכשיו יש לנו רשימה, רשימה מקושרת, משני אלמנטים.

540
00:32:31,330 --> 00:32:33,580
ומה זה באמת נראה כמו כאן?

541
00:32:33,580 --> 00:32:36,900
אם נסתכל על הקוד, שים לב שעשיתי בדיוק את זה.

542
00:32:36,900 --> 00:32:41,970
אני כבר אמרתי newptr, ובסיפור הזה, newptr מצביע על הבחור הזה.

543
00:32:41,970 --> 00:32:45,520
>> אז נתת לי לצייר עוד דבר אחד, ואני צריך להשאיר קצת יותר מקום לזה.

544
00:32:45,520 --> 00:32:48,540
אז תסלח הציור הקטנטן.

545
00:32:48,540 --> 00:32:52,140
הבחור הזה נקרא newptr.

546
00:32:52,140 --> 00:32:57,940
זה משתנה הכרזנו כמה שורות קודם לכן, בקו - מעל 25.

547
00:32:57,940 --> 00:33:03,430
וזה מצביע על 8. לכן, כאשר אני אומר newptr-> הבא, זה אומר ללכת לstruct

548
00:33:03,430 --> 00:33:07,910
שמכוונים אליי על ידי newptr, אז הנה אנחנו, נלך לשם.

549
00:33:07,910 --> 00:33:13,990
ואז הוא אומר לי חץ השדה הבא, ולאחר מכן = אומר לשים איזה ערך יש?

550
00:33:13,990 --> 00:33:17,280
הערך שהיה במקום הראשון, מה ערך היה בראשון?

551
00:33:17,280 --> 00:33:21,930
קודם הצביע בצומת הזו, אז זה אומר שזה צריך עכשיו להצביע בצומת זה.

552
00:33:21,930 --> 00:33:25,660
במילים אחרות, מה שנראה אמנם בלגן מגוחך עם כתב היד שלי,

553
00:33:25,660 --> 00:33:28,620
מה זה רעיון פשוט של הזזת החיצים האלה מסביב

554
00:33:28,620 --> 00:33:31,560
מתרגם ל קוד רק עם התוחם הזה.

555
00:33:31,560 --> 00:33:38,110
לאחסן את מה שהוא בראשון בשדה הבא ולאחר מכן לעדכן מה קודם למעשה.

556
00:33:38,110 --> 00:33:40,900
בואו נלך קדימה ולהריץ קדימה דרך החלק הזה,

557
00:33:40,900 --> 00:33:44,220
ולהסתכל רק על הכנסת זנב זה לעת עתה.

558
00:33:44,220 --> 00:33:51,210
אניח שאני מגיע לנקודה שבה אני מוצא שהשדה הבא של צומת מסוימת הוא NULL.

559
00:33:51,210 --> 00:33:53,410
ובנקודה הזאת בסיפור, פרט שאני פסחתי על

560
00:33:53,410 --> 00:33:58,170
הוא שאני כבר הצגתי מצביע אחר כאן בקו 142, מצביע קודם.

561
00:33:58,170 --> 00:34:01,320
בעיקרו של דבר, בשלב זה בסיפור, ברגע שמקבלת הרשימה ארוכה,

562
00:34:01,320 --> 00:34:04,800
אני סוג של צריך ללכת אותו עם שתי אצבעות, כי אם אני הולך רחוק מדי,

563
00:34:04,800 --> 00:34:08,219
זוכר ברשימה אחת באורך, אתה לא יכול ללכת אחורה.

564
00:34:08,219 --> 00:34:13,659
אז הרעיון הזה של predptr הוא האצבע השמאלית שלי, וnewptr - לא newptr.

565
00:34:13,659 --> 00:34:17,199
מצביע נוסף שיש כאן זה את האצבע שלי אחרת, ואני פשוט סוג של הליכה ברשימה.

566
00:34:17,199 --> 00:34:22,179
זו הסיבה שקיימת. אבל הבה נבחן אחד מהמקרים הפשוטים יותר כאן בלבד.

567
00:34:22,179 --> 00:34:26,620
אם השדה הבא ששל המצביע הוא NULL, מה המשמעות ההגיונית?

568
00:34:26,620 --> 00:34:30,840
אם אתה חוצה את הרשימה הזאת ואתה מכה מצביע NULL?

569
00:34:30,840 --> 00:34:35,780
אתה בסוף הרשימה, וכן את הקוד לאז לצרף מרכיב נוסף זה

570
00:34:35,780 --> 00:34:41,230
הוא סוג של אינטואיטיבית ייקח צומת שלידו מצביע הוא NULL,

571
00:34:41,230 --> 00:34:46,120
אז זה כרגע ריק, ולשנות אותו, אם כי, כדי להיות הכתובת של הצומת החדשה.

572
00:34:46,120 --> 00:34:52,260
אז אנחנו רק ציור בקוד על החץ שציירנו על במה על ידי הרמת יד השמאל של מישהו.

573
00:34:52,260 --> 00:34:54,070
>> ומקרה שאני אניף את הידות שלי בעכשיו,

574
00:34:54,070 --> 00:34:58,020
רק בגלל שאני חושב שזה קל ללכת לאיבוד כאשר אנחנו עושים את זה בסוג כזה של הסביבה,

575
00:34:58,020 --> 00:35:00,600
בודק לכניסה באמצע של הרשימה.

576
00:35:00,600 --> 00:35:03,220
אבל רק באופן אינטואיטיבי, מה צריך לקרות אם אתה רוצה להבין

577
00:35:03,220 --> 00:35:06,600
שבו חלק מספר שייך באמצע הוא שאתה צריך ללכת ברגלו

578
00:35:06,600 --> 00:35:09,510
עם יותר מאצבע אחת, מצביע יותר מפעם אחת,

579
00:35:09,510 --> 00:35:12,920
להבין לאן הוא שייך על ידי בדיקה הוא המרכיב <1 הנוכחי,

580
00:35:12,920 --> 00:35:15,450
> הנוכחי אחד, וברגע שאתה מוצא את המקום,

581
00:35:15,450 --> 00:35:20,400
אז אתה צריך לעשות את זה סוג של משחק פגז שבו אתה מזיז את המצביעים סביב מאוד בזהירות.

582
00:35:20,400 --> 00:35:23,850
ותשובה, אם תרצו למצוא היגיון בתוך זה בבית בעצמך,

583
00:35:23,850 --> 00:35:28,340
מסתכם רק בשתי השורות האלה של קוד, אבל כדי של הקווים האלה הוא סופר חשוב.

584
00:35:28,340 --> 00:35:31,390
כי אם אתה טיפה היד של מישהו ולהעלות מישהו אחר שלא בסדר הנכון,

585
00:35:31,390 --> 00:35:34,580
שוב, אתה יכול בסוף יתום הרשימה.

586
00:35:34,580 --> 00:35:39,500
לסיכום יותר מושגית, הכניסה בזנב היא פשוטה יחסית.

587
00:35:39,500 --> 00:35:42,940
הכניסה בראש היא גם פשוטה יחסית,

588
00:35:42,940 --> 00:35:45,580
אבל אתה צריך לעדכן את מצביע נוסף הפעם

589
00:35:45,580 --> 00:35:47,930
לסחוט מספר 5 ברשימה כאן,

590
00:35:47,930 --> 00:35:51,560
ולאחר מכן כניסה באמצע כרוך אפילו יותר מאמץ,

591
00:35:51,560 --> 00:35:56,130
כדי להוסיף את המספר 20 מאוד בזהירות במיקום הנכון שלו,

592
00:35:56,130 --> 00:35:58,350
שבין 17 ו 22.

593
00:35:58,350 --> 00:36:02,700
אז אתה צריך לעשות משהו כמו 20 יש נקודת הצומת החדשה עד 22,

594
00:36:02,700 --> 00:36:08,470
ולאחר מכן, המצביע של הצומת שבו צריך להיות מעודכן אחרון?

595
00:36:08,470 --> 00:36:10,630
זה 17, כדי באמת להכניס אותו.

596
00:36:10,630 --> 00:36:14,080
אז שוב, אני לדחות את הקוד בפועל שליישום מסוים.

597
00:36:14,080 --> 00:36:17,280
>> במבט הראשון, זה קצת מוחץ, אבל זה באמת רק ללולאה אינסופית

598
00:36:17,280 --> 00:36:21,770
זה לופים, לופים, לופים, לופים, ולשבור ברגע שאתה מכה את מצביע NULL,

599
00:36:21,770 --> 00:36:24,590
ובנקודה שאתה יכול לעשות הכנסה הנדרשת.

600
00:36:24,590 --> 00:36:30,960
זהו, אם כן, הוא קוד הכנסת נציג מקושר רשימה.

601
00:36:30,960 --> 00:36:34,590
זה היה סוג של הרבה, וזה מרגיש כאילו אנחנו כבר פתרנו בעיה אחת,

602
00:36:34,590 --> 00:36:36,940
אבל אנחנו כבר הצגנו כל אחד אחר. בכנות, אנחנו מבלים כל כך הרבה זמן

603
00:36:36,940 --> 00:36:40,540
על הגדול O וΩ וזמן ריצה, מנסה לפתור בעיות במהירות רבה יותר,

604
00:36:40,540 --> 00:36:43,270
וכאן אנחנו לוקחים צעד גדול אחורה, זה מרגיש.

605
00:36:43,270 --> 00:36:45,380
ובכל זאת, אם המטרה היא לאחסון נתונים,

606
00:36:45,380 --> 00:36:48,010
זה מרגיש כמו הגביע הקדוש, כפי שאמרנו ביום שני, יהיה באמת

607
00:36:48,010 --> 00:36:50,470
כדי לאחסן את הדברים באופן מיידי.

608
00:36:50,470 --> 00:36:53,930
>> למעשה, יניח שעשינו רשימה מקושרת בצד לשים לרגע

609
00:36:53,930 --> 00:36:56,000
ואנחנו במקום הצגנו את הרעיון של שולחן.

610
00:36:56,000 --> 00:36:59,110
ובואו נחשוב על שולחן לרגע, כמו מערך.

611
00:36:59,110 --> 00:37:03,790
מערך זה והמקרה הזה כאן יש כמה אלמנטים 26, 0 עד 25,

612
00:37:03,790 --> 00:37:07,940
ותניח שאתה זקוק לקצת נתח של אחסון לשמות:

613
00:37:07,940 --> 00:37:10,350
אליס ובוב וצ'רלי וכדומה.

614
00:37:10,350 --> 00:37:12,880
ואתה צריך קצת מבנה נתונים כדי לאחסן את השמות האלה.

615
00:37:12,880 --> 00:37:15,000
ובכן, אתה יכול להשתמש במשהו כמו רשימה מקושרת

616
00:37:15,000 --> 00:37:20,260
ואתה יכול ללכת ברשימת ההכנסה אליס לפני בוב וצ'רלי לאחר שבוב וכן הלאה.

617
00:37:20,260 --> 00:37:23,850
ואכן, אם אתה רוצה לראות את קוד כמו שכהערת אגב,

618
00:37:23,850 --> 00:37:27,230
יודע שבlist2.h, אנו עושים בדיוק את זה.

619
00:37:27,230 --> 00:37:30,610
אנחנו לא נעבור על הקוד הזה, אבל זה הנו נגזר של הדוגמא הראשונה

620
00:37:30,610 --> 00:37:34,640
שמציג struct אחד אחר שראינו לפני הסטודנט שנקרא,

621
00:37:34,640 --> 00:37:40,330
ואז מה זה בעצם מאחסן ברשימה המקושרת הוא מצביע למבנה סטודנט

622
00:37:40,330 --> 00:37:44,520
במקום מספר שלם קטן ופשוט, n.

623
00:37:44,520 --> 00:37:46,900
אז מבין שיש קוד שיש כרוך מחרוזות בפועל,

624
00:37:46,900 --> 00:37:49,940
אם המטרה בהישג יד ממש כרגע היא לטפל בבעיה, אבל היעילות,

625
00:37:49,940 --> 00:37:53,380
האם זה לא יהיה נחמד אם אנו מקבלים אובייקט בשם אליס,

626
00:37:53,380 --> 00:37:56,020
אנחנו רוצים להביא אותה למיקום הנכון במבנה נתונים,

627
00:37:56,020 --> 00:37:58,860
זה מרגיש כאילו זה הייתי ממש נחמד, רק כדי לשים את אליס,

628
00:37:58,860 --> 00:38:01,180
מי ששם מתחיל ב, במיקום הראשון.

629
00:38:01,180 --> 00:38:05,270
ובוב, ששמה מתחיל ב-B, במיקום השני.

630
00:38:05,270 --> 00:38:09,580
עם מערך, או בואו נתחיל קוראים לזה שולחן, שולחן חשיש בזה,

631
00:38:09,580 --> 00:38:13,650
אנחנו יכולים לעשות בדיוק את זה. אם אנו מקבלים שם כמו אליס,

632
00:38:13,650 --> 00:38:16,700
מחרוזת כמו אליס, שבו אתה מכניס-l-i-c-דואר?

633
00:38:16,700 --> 00:38:20,540
אנחנו צריכים hueristic. אנחנו צריכים פונקציה לקחת קצת קלט כמו אליס

634
00:38:20,540 --> 00:38:24,610
ולהחזיר תשובה, "שים את אליס במיקום זה."

635
00:38:24,610 --> 00:38:28,720
ופונקציה זו, הקופסה השחורה הזו, הוא הולך להיות שם פונקציית hash.

636
00:38:28,720 --> 00:38:32,330
>> פונקציית hash היא משהו שלוקח קלט, כמו "אליס",

637
00:38:32,330 --> 00:38:38,080
וחוזר אליך, בדרך כלל, את המיקום המספרי בחלק מבנה נתונים בי אליס שייכת.

638
00:38:38,080 --> 00:38:40,830
במקרה זה, פונקציית hash שלנו צריכה להיות פשוט יחסית.

639
00:38:40,830 --> 00:38:47,510
פונקציית hash שלנו צריכה לומר, אם אתה מקבל את "אליס", שדמות צריכה שאכפת לי?

640
00:38:47,510 --> 00:38:55,660
ראשון. אז אני מסתכל על [0], ואז אני אומר אם [0] דמות היא, להחזיר את המספר 0.

641
00:38:55,660 --> 00:39:01,130
אם זה ב ', לחזור 1. אם C זה, לחזור 2, וכן הלאה.

642
00:39:01,130 --> 00:39:05,940
הכל 0 המדד, ושיאפשר לי להכניס את אליס, ואז בוב וצ'רלי וכן הלאה

643
00:39:05,940 --> 00:39:10,960
למבנה נתונים זה. אבל יש בעיה.

644
00:39:10,960 --> 00:39:13,060
מה אם אניטה מגיעה שוב?

645
00:39:13,060 --> 00:39:17,510
איפה שם את אניטה? את שמה, גם מתחיל באות,

646
00:39:17,510 --> 00:39:20,330
וזה מרגיש כמו שעשינו בלגן גדול עוד יותר לבעיה זו.

647
00:39:20,330 --> 00:39:24,380
עכשיו יש לנו החדרה מיידית, החדרת זמן קבועה, למבנה נתונים

648
00:39:24,380 --> 00:39:27,100
ולא במקרה הגרוע יותר ליניארי,

649
00:39:27,100 --> 00:39:29,510
אבל מה אנחנו יכולים לעשות עם אניטה במקרה זה?

650
00:39:29,510 --> 00:39:34,110
מה הן שתי אפשרויות, באמת? כן?

651
00:39:34,110 --> 00:39:37,410
[תשובת סטודנט, לא מובן] אוקיי, אז נהיה לנו ממד אחר.

652
00:39:37,410 --> 00:39:42,320
זה טוב. אז אנחנו יכולים לבנות דברים ב3D כמו שדברנו עליה מילולי ביום שני.

653
00:39:42,320 --> 00:39:46,700
אנחנו יכולים להוסיף גישה אחרת כאן, אבל נניח שלא, מה שאני מנסה לומר את זה פשוט.

654
00:39:46,700 --> 00:39:50,160
כל המטרה כאן היא כדי לקבל גישה מיידית בזמן קבוע,

655
00:39:50,160 --> 00:39:52,170
כך שזה חיבור יותר מדי מורכב.

656
00:39:52,170 --> 00:39:55,970
מה הן אפשרויות אחרות, כשמנסה להכניס את אניטה למבנה נתונים זה? כן?

657
00:39:55,970 --> 00:39:58,610
[תשובת סטודנט, לא מובן] טוב. כדי שנוכל לעבור את כולם למטה,

658
00:39:58,610 --> 00:40:03,040
כמו צ'רלי דחיפות את בוב ואליס, ואז אנחנו שמים את אניטה שבו היא לא באמת רוצה להיות.

659
00:40:03,040 --> 00:40:05,660
>> כמובן, עכשיו, יש תופעת לוואי של זה.

660
00:40:05,660 --> 00:40:09,000
מבנה נתונים זה כנראה לא שימושי בגלל שאנחנו רוצים להכניס אנשים שפעם

661
00:40:09,000 --> 00:40:11,250
אלא בגלל שאנחנו רוצים לבדוק אם הם שם מאוחר יותר

662
00:40:11,250 --> 00:40:13,600
אם אנחנו רוצים להדפיס את כל השמות במבנה הנתונים.

663
00:40:13,600 --> 00:40:15,850
אנחנו הולכים לעשות משהו עם הנתונים הללו סופו של דבר.

664
00:40:15,850 --> 00:40:20,810
אז עכשיו יש לנו סוג של דפק את אליס, שכבר לא שם היא אמורה להיות.

665
00:40:20,810 --> 00:40:23,880
גם הוא בוב, וגם לא את צ'רלי.

666
00:40:23,880 --> 00:40:26,060
אז אולי זה לא רעיון כל כך טוב.

667
00:40:26,060 --> 00:40:28,830
אבל אכן, זו אפשרות אחת. נוכל להסיט את כולם,

668
00:40:28,830 --> 00:40:32,240
או לעזאזל, אניטה הגיעה מאוחר למשחק, למה אנחנו לא פשוט לשים את אניטה

669
00:40:32,240 --> 00:40:35,870
לא כאן, לא כאן, לא כאן, בואו פשוט לשים אותה קצת נמוך יותר ברשימה.

670
00:40:35,870 --> 00:40:38,680
אבל אז הבעיה מתחילה לרדת ברמה שוב.

671
00:40:38,680 --> 00:40:41,630
ייתכן שתוכל למצוא את אליס באופן מיידי, המבוסס על שמה הפרטי.

672
00:40:41,630 --> 00:40:44,320
ובוב באופן מיידי, וצ'רלי. אבל כשאתה מסתכל על אניטה,

673
00:40:44,320 --> 00:40:46,360
ואתה רואה, הממ, אליס היא בדרך.

674
00:40:46,360 --> 00:40:48,770
ובכן, תן לי לבדוק מתחת לאליס. בוב הוא לא אניטה.

675
00:40:48,770 --> 00:40:51,850
צ'רלי הוא לא אניטה. אה, יש אניטה.

676
00:40:51,850 --> 00:40:54,720
אם תמשיך רכבת שההיגיון של כל הדרך ו,

677
00:40:54,720 --> 00:41:00,690
מה זמן הריצה הגרועה ביותר של מציאה או החדרת אניטה למבנה הנתונים החדש הזה?

678
00:41:00,690 --> 00:41:03,280
זה O (n), נכון?

679
00:41:03,280 --> 00:41:06,280
כי במקרה הגרוע ביותר, יש אליס, בוב, צ'רלי. . .

680
00:41:06,280 --> 00:41:10,150
כל הדרך למטה למישהו בשם "Y", ולכן יש רק מקום אחד שמאלה.

681
00:41:10,150 --> 00:41:13,950
למרבה המזל, יש לנו אף אחד לא קרא "Z", ולכן אנחנו שמים אניטה במאוד בתחתית.

682
00:41:13,950 --> 00:41:16,040
>> אנחנו לא באמת פתרנו את הבעיה.

683
00:41:16,040 --> 00:41:19,890
אז אולי אנחנו צריכים להציג את הממד שלישי.

684
00:41:19,890 --> 00:41:22,230
ומתברר, אם אנחנו מציגים את הממד שלישי,

685
00:41:22,230 --> 00:41:25,240
אנחנו לא יכולים לעשות את זה בצורה מושלמת, אבל הגביע הקדוש הולך להיות מקבל

686
00:41:25,240 --> 00:41:28,370
החדרה מתמדת בזמן והוספות דינמיות כך ש

687
00:41:28,370 --> 00:41:30,960
אין לנו לקשה קוד מערך בגודל 26.

688
00:41:30,960 --> 00:41:34,400
אנחנו יכולים להוסיף כשמות רבים כפי שאנו רוצים, אבל בואו ניקח ההפסקה שלנו 5-הדקה כאן

689
00:41:34,400 --> 00:41:38,790
ואז לעשות את זה כמו שצריך.

690
00:41:38,790 --> 00:41:46,020
בסדר. אני להגדיר את הסיפור די באופן מלאכותי יש

691
00:41:46,020 --> 00:41:48,670
על ידי בחירת אליס ובוב וצ'רלי ולאחר מכן אניטה,

692
00:41:48,670 --> 00:41:51,000
שמו היה ברור שמתנגש עם אליס.

693
00:41:51,000 --> 00:41:54,120
אבל השאלה שנסתיימו ביום שני עם רק כמה סביר הוא זה

694
00:41:54,120 --> 00:41:56,370
שהיית מקבל סוגים אלה של התנגשויות? במילים אחרות,

695
00:41:56,370 --> 00:42:00,490
אם תתחילו להשתמש במבנה הטבלאי הזה, שהוא באמת רק מערך,

696
00:42:00,490 --> 00:42:02,460
במקרה זה של 26 מקומות,

697
00:42:02,460 --> 00:42:05,740
מה אם התשומות שלנו במקומו מפוזרות באופן אחיד?

698
00:42:05,740 --> 00:42:09,620
זה לא באופן מלאכותי אליס ובוב וצ'רלי ודוד וכן הלאה לפי סדר אלפביתי,

699
00:42:09,620 --> 00:42:12,380
הוא מפוזר באופן אחיד על פני דרך צ

700
00:42:12,380 --> 00:42:15,220
>> אולי אנחנו פשוט נהיה לך מזל ואנחנו לא הולכים להיות לך שתיים או שניים של B של

701
00:42:15,220 --> 00:42:17,640
בהסתברות מאוד גבוהה, אבל כמו שמישהו ציין,

702
00:42:17,640 --> 00:42:20,730
אם להכליל את הבעיה הזו ולא לעשות 0-25

703
00:42:20,730 --> 00:42:26,060
אבל, אומר, 0 עד 364, או 65, לעתים קרובות מספר ימים בשנה טיפוסית,

704
00:42:26,060 --> 00:42:31,170
ושאל את השאלה, "מה ההסתברות ששנינו בחדר הזה יש לו יום הולדת?"

705
00:42:31,170 --> 00:42:34,600
שים את זה בדרך אחרת, מה ההסתברות ששנינו יש שם החל?

706
00:42:34,600 --> 00:42:37,190
הסוג של שאלה הוא אותו הדבר, אבל מרחב הכתובות הזה,

707
00:42:37,190 --> 00:42:39,940
מרחב חיפוש זה, הוא יותר גדול במקרה של ימי הולדת,

708
00:42:39,940 --> 00:42:42,820
כי יש לנו כל כך הרבה יותר ימים בשנה מאותיות באלפבית.

709
00:42:42,820 --> 00:42:44,910
מה ההסתברות להתנגשות?

710
00:42:44,910 --> 00:42:48,410
ובכן, אנחנו יכולים לחשוב על זה על ידי חישוב המתמטי בכיוון ההפוך.

711
00:42:48,410 --> 00:42:50,580
מה ההסתברות להתנגשויות לא?

712
00:42:50,580 --> 00:42:53,970
ובכן, הביטוי הזה כאן אומר שמה ההסתברות

713
00:42:53,970 --> 00:42:58,770
אם יש רק אדם אחד בחדר הזה, שיש להם יום הולדת ייחודית?

714
00:42:58,770 --> 00:43:01,190
זה 100%. כי אם יש רק אדם אחד בחדר,

715
00:43:01,190 --> 00:43:03,940
או יום ההולדת שלה יכול להיות כל אחד מתוך 365 ימים מתוך השנה.

716
00:43:03,940 --> 00:43:08,650
אז אפשרויות 365/365 נותנות לי ערך של 1.

717
00:43:08,650 --> 00:43:11,250
אז ההסתברות בשאלה כרגע היא רק 1.

718
00:43:11,250 --> 00:43:13,270
אבל אם יש אדם נוסף בחדר,

719
00:43:13,270 --> 00:43:16,490
מה ההסתברות שיום ההולדת שלהם הוא שונה?

720
00:43:16,490 --> 00:43:20,680
יש 364 ימים בלבד אפשריים, שנים מעוברות, תוך התעלמות

721
00:43:20,680 --> 00:43:23,580
ליום ההולדת שלהם לא אתנגש עם האנשים האחרים.

722
00:43:23,580 --> 00:43:31,920
אז 364/365. אם אדם שלישי מגיע, זה 363/365, וכן הלאה.

723
00:43:31,920 --> 00:43:35,790
אז אנחנו ממשיכים יחד הכפלת השברים האלה, שמקבלים יותר ויותר קטנים,

724
00:43:35,790 --> 00:43:40,720
כדי להבין מה היא ההסתברות שכולנו יש ימי הולדת ייחודיים?

725
00:43:40,720 --> 00:43:43,570
אבל אז אנחנו יכולים, כמובן, פשוט לקחת את התשובה הזאת ולהעיף סביבו

726
00:43:43,570 --> 00:43:47,210
ולעשות 1 מינוס כל זה, ביטוי שסופו של דבר יקבל

727
00:43:47,210 --> 00:43:51,250
אם אתה זוכר את החלק האחורי של ספרי המתמטיקה שלך, זה נראה משהו קטן כזה,

728
00:43:51,250 --> 00:43:54,590
אשר מתפרש הרבה יותר בקלות בצורה גרפית.

729
00:43:54,590 --> 00:43:57,820
וגרפיקה זה כאן יש מספר ימי ההולדת על ציר x,

730
00:43:57,820 --> 00:44:02,030
או מספר אנשים עם ימי הולדת, ועל ציר y הוא ההסתברות להתאמה.

731
00:44:02,030 --> 00:44:06,060
ומה שזה אומר הוא שאם יש לך, יניח, אפילו,

732
00:44:06,060 --> 00:44:10,860
בואו לבחור משהו כמו 22, 23.

733
00:44:10,860 --> 00:44:13,160
אם יש 22 או 23 אנשים בחדר,

734
00:44:13,160 --> 00:44:17,100
ההסתברות כי שניים מאותם מעט מאוד אנשים הולכים להיות באותו יום ההולדה

735
00:44:17,100 --> 00:44:19,560
הוא למעשה גבוה נפלא, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% סיכויים כי בכיתה של רק 22 אנשים, סמינר, כמעט,

737
00:44:23,450 --> 00:44:25,790
2 האנשים האלה הולכים להיות אותו יום ההולדת.

738
00:44:25,790 --> 00:44:28,520
בגלל שיש כל כך הרבה דרכים שבם אתה יכול לקבל אותו יום ההולדת.

739
00:44:28,520 --> 00:44:31,110
גרוע מכך, אם אתה מסתכל על הצד הימני של התרשים,

740
00:44:31,110 --> 00:44:34,040
בזמן שיש לך בכיתה עם 58 תלמידים בזה,

741
00:44:34,040 --> 00:44:39,270
ההסתברות של 2 אנשים שיש להם יום הולדת היא גבוהה נפלא, סופר, כמעט 100%.

742
00:44:39,270 --> 00:44:41,880
עכשיו, זה סוג של עובדה משעשעת על חיים אמיתיים.

743
00:44:41,880 --> 00:44:45,850
>> אבל השלכות, עכשיו, למבני נתונים ואחסון מידע

744
00:44:45,850 --> 00:44:51,100
משמעות הדבר הוא כי רק בהנחה שיש לך הפצה נחמדה, נקיה ואחידה של נתונים

745
00:44:51,100 --> 00:44:53,650
ויש לך מספיק גדול כדי להתאים מערך חבורה של דברים

746
00:44:53,650 --> 00:44:59,360
זה לא אומר שאתה הולך לגרום לאנשים במיקומים ייחודיים.

747
00:44:59,360 --> 00:45:03,810
אתה הולך להיות התנגשויות. אז הרעיון הזה של hashing, כפי שהוא נקרא,

748
00:45:03,810 --> 00:45:07,450
לוקח קלט כמו "אליס" ומעסה אותו בדרך כלשהי

749
00:45:07,450 --> 00:45:10,190
ולאחר מכן מקבל בחזרה תשובה כמו 0 או 1 או 2.

750
00:45:10,190 --> 00:45:17,500
מקבל בחזרה חלק מהתפוקה שהוא הוטרד על ידי פונקצית ההסתברות של התנגשות.

751
00:45:17,500 --> 00:45:19,530
אז איך אנחנו יכולים להתמודד עם ההתנגשויות האלה?

752
00:45:19,530 --> 00:45:21,940
ובכן, במקרה אחד, אנחנו יכולים לקחת את הרעיון שהוצע.

753
00:45:21,940 --> 00:45:25,100
אנחנו רק יכולים להעביר את כולם, או אולי, קצת יותר פשוט,

754
00:45:25,100 --> 00:45:29,870
ולא כל מהלך אחר, בואו פשוט לעבור אניטה לתחתית במקום הזמין.

755
00:45:29,870 --> 00:45:32,810
אז אם אליס היא ב0, בוב הוא ב1, צ'רלי הוא ב2,

756
00:45:32,810 --> 00:45:35,260
אנחנו פשוט נשים את אניטה בשעת 3 מיקום.

757
00:45:35,260 --> 00:45:38,860
וזו טכניקה במבני נתונים הנקראת ליניארי חיטוט.

758
00:45:38,860 --> 00:45:41,310
בשכבות בגלל שאתה סתם הליכת הקו הזה, ואתה סוג של חיטוט

759
00:45:41,310 --> 00:45:43,640
למקומות פנויים במבנה הנתונים.

760
00:45:43,640 --> 00:45:46,210
כמובן, זה יתפורר אל O (n).

761
00:45:46,210 --> 00:45:49,590
אם מבנה הנתונים ממש מלא, יש 25 אנשים בזה כבר,

762
00:45:49,590 --> 00:45:54,120
ואז מגיעה יחד אניטה, היא מסתיימת במה יהיה המיקום Z, וזה בסדר גמור.

763
00:45:54,120 --> 00:45:56,540
היא עדיין מתאימה, ואנחנו יכולים למצוא אותה מאוחר יותר.

764
00:45:56,540 --> 00:46:00,100
>> אבל זה היה בניגוד למטרה של זירוז דברים.

765
00:46:00,100 --> 00:46:02,530
אז מה אם אנחנו במקום הצגנו הממד השלישי הזה?

766
00:46:02,530 --> 00:46:06,400
טכניקה שנקרא בדרך שרשור נפרד, או שיש רשתות.

767
00:46:06,400 --> 00:46:10,030
ומה שולחן חשיש כרגע הוא, מבנה טבלאי זו,

768
00:46:10,030 --> 00:46:13,450
השולחן שלך הוא רק מערך של מצביעים.

769
00:46:13,450 --> 00:46:18,230
אבל מה המצביעים האלה מצביעים הוא נחש מה?

770
00:46:18,230 --> 00:46:21,970
רשימה מקושרת. אז מה אם אנחנו לוקחים את הטוב שבשני העולמים הללו?

771
00:46:21,970 --> 00:46:26,500
אנו משתמשים במערכים למדדים הראשוניים

772
00:46:26,500 --> 00:46:32,070
למבנה הנתונים ולכן אנחנו יכולים מייד ללכת ל[ 0] [1], [30] או כן הלאה,

773
00:46:32,070 --> 00:46:36,480
אבל כך יש לנו גמישות מסוימת ואנחנו יכולים להתאים אניטה ואליס ואדם

774
00:46:36,480 --> 00:46:38,630
וכל האחרים שם,

775
00:46:38,630 --> 00:46:43,470
במקום לתת לנו את הציר השני לגדול באופן שרירותי.

776
00:46:43,470 --> 00:46:47,340
ולבסוף, כמו ביום שני, יש לי שיכולת הבעה ברשימה מקושרת.

777
00:46:47,340 --> 00:46:49,530
אנחנו יכולים לצמוח במבנה נתונים באופן שרירותי.

778
00:46:49,530 --> 00:46:52,450
לחלופין, אנו יכולים רק להפוך את מערך 2-ממדים ענקים,

779
00:46:52,450 --> 00:46:57,190
אבל זה הולך להיות מצב נורא אם אחת מהשורות במערך 2-ממדי

780
00:46:57,190 --> 00:47:01,280
אינה גדול מספיק לאדם הנוסף ששם קורה להתחיל עם א '

781
00:47:01,280 --> 00:47:04,200
חס ושלום שיש לנו כדי להקצות מחדש מבנה 2-ממדי ענק

782
00:47:04,200 --> 00:47:06,600
רק בגלל שיש כל כך הרבה אנשים בשם,

783
00:47:06,600 --> 00:47:09,480
במיוחד כאשר יש כל כך מעט אנשים בשם Z משהו.

784
00:47:09,480 --> 00:47:12,170
זה פשוט הולך להיות מבנה נתונים מאוד דליל.

785
00:47:12,170 --> 00:47:15,400
אז זה לא מושלם ובכל אמצעי, אבל עכשיו אנחנו לפחות יש את היכולת

786
00:47:15,400 --> 00:47:19,090
מייד למצוא בי אליס או אניטה שייכת,

787
00:47:19,090 --> 00:47:21,090
לפחות במונחים של הציר האנכי,

788
00:47:21,090 --> 00:47:25,850
ואז אנחנו רק צריכים להחליט איפה לשים את אניטה או אליס ברשימה מקושרת זה.

789
00:47:25,850 --> 00:47:32,480
אם לא אכפת לנו אודות מיון דברים, כמה מהר אנחנו יכולים להכניס את אליס למבנה כזה?

790
00:47:32,480 --> 00:47:35,370
זה זמן קבוע. אנו אינדקס לתוך [0], ואם יש אף אחד,

791
00:47:35,370 --> 00:47:37,550
אליס יוצאת בתחילת שהרשימה מקושרת.

792
00:47:37,550 --> 00:47:40,000
אבל זה לא עניין כזה גדול. כי אם אניטה אז מגיעה

793
00:47:40,000 --> 00:47:42,160
חלק מספר השלבים מאוחר יותר, שבו אין אניטה שייכת?

794
00:47:42,160 --> 00:47:45,140
ובכן, [0]. OOP. אליס כבר שברשימה מקושרת.

795
00:47:45,140 --> 00:47:47,760
>> אם לא אכפת לנו אודות מיון השמות האלה אבל,

796
00:47:47,760 --> 00:47:53,580
אנחנו יכולים פשוט לעבור על אליס, ההוספה אניטה, אבל אפילו זה לא זמן קבוע.

797
00:47:53,580 --> 00:47:57,010
גם אם יש אליס ואדם וכל שניית השמות האלה,

798
00:47:57,010 --> 00:47:59,410
זה לא באמת עובר אותם פיזי. למה?

799
00:47:59,410 --> 00:48:04,090
מכיוון שבדיוק עשו כאן עם רשימה מקושרת, מי יודע היו צומת האלה הם בכלל?

800
00:48:04,090 --> 00:48:06,550
כל מה שאתה צריך לעשות הוא להעביר את פירורי הלחם.

801
00:48:06,550 --> 00:48:10,930
הזז את החצים סביב; אין לך פיזי להעביר את כל נתונים מסביב.

802
00:48:10,930 --> 00:48:14,610
אז אנחנו יכולים להוסיף אניטה, במקרה זה, באופן מיידי. זמן קבוע.

803
00:48:14,610 --> 00:48:20,250
אז יש לנו בדיקה מתמדת בזמן, והחדרה מתמדת בזמן של מישהו כמו אניטה.

804
00:48:20,250 --> 00:48:22,740
אבל זה סוג של פשטני מדי העולם.

805
00:48:22,740 --> 00:48:28,510
מה אם מאוחר יותר אנחנו רוצים למצוא את אליס?

806
00:48:28,510 --> 00:48:31,050
מה אם מאוחר יותר אנחנו רוצים למצוא את אליס?

807
00:48:31,050 --> 00:48:35,690
כמה צעדים שהוא הולך לקחת?

808
00:48:35,690 --> 00:48:37,850
[תשובת סטודנט, לא מובן]

809
00:48:37,850 --> 00:48:40,950
בדיוק. מספר אנשים לפני שאליס ברשימה המקושרת.

810
00:48:40,950 --> 00:48:45,420
אז זה לא ממש מושלם, כי מבנה הנתונים שלנו, שוב, יש לו גישה אנכית זו

811
00:48:45,420 --> 00:48:50,240
ואז יש לו רשימות מקושרות אלה תלויים - בעצם, בואו לא לצייר אותו מערך.

812
00:48:50,240 --> 00:48:56,020
זה רשימות מקושרות אלה נתלו עליו זה נראה משהו קטן כזה.

813
00:48:56,020 --> 00:48:59,110
אבל הבעיה היא אם אליס ואדם וכל שניית שמות אלה

814
00:48:59,110 --> 00:49:01,720
בסופו של עוד ועוד שם,

815
00:49:01,720 --> 00:49:04,810
למצוא מישהו יכול בסופו של דבר לוקח חבורה של צעדים,

816
00:49:04,810 --> 00:49:06,670
bcause יש לך לחצות את הרשימה המקושרת,

817
00:49:06,670 --> 00:49:08,090
אשר היא פעולה ליניארית.

818
00:49:08,090 --> 00:49:14,270
אז באמת, אם כן, זמן החדרת סופו של דבר הוא O (n), כאשר n הוא מספר האיברים ברשימה.

819
00:49:14,270 --> 00:49:21,780
מחולק ב, בואו נקרא לזה באופן שרירותי מ ', מ' שבו מספר הרשימות מקושרות

820
00:49:21,780 --> 00:49:24,500
שיש לנו בציר אנכי זה.

821
00:49:24,500 --> 00:49:27,180
במילים אחרות, אם נניח שאנחנו באמת התפלגות אחידה של שמות,

822
00:49:27,180 --> 00:49:30,150
לחלוטין לא ריאלית. ברור שיש יותר של אותיות מסוימות יותר מאחרים.

823
00:49:30,150 --> 00:49:32,580
>> אבל אם תניחו לרגע שהתפלגות אחידה,

824
00:49:32,580 --> 00:49:37,350
ויש לנו n אנשי סך הכל, ושרשרות כלל מ '

825
00:49:37,350 --> 00:49:40,630
עומד לרשותנו, ולאחר מכן את האורך של כל אחת מרשתות אלה

826
00:49:40,630 --> 00:49:44,380
די פשוט הולך להיות כולל, n מתחלק במספר הרשתות.

827
00:49:44,380 --> 00:49:48,900
אז n / m. אבל כאן בדיוק אנחנו יכולים להיות כל מתמטיים מתוחכמים.

828
00:49:48,900 --> 00:49:53,030
מ 'הוא תמידי, כי יש מספר קבוע של אלה.

829
00:49:53,030 --> 00:49:54,620
אתה הולך להכריז על המערך שלך בהתחלה,

830
00:49:54,620 --> 00:49:58,450
ואנחנו לא שינוי גודל הציר האנכי. על פי הגדרה, שנשאר קבוע.

831
00:49:58,450 --> 00:50:01,220
זה רק הציר האופקי, כביכול, שהוא משתנה.

832
00:50:01,220 --> 00:50:04,760
אז מבחינה טכנית, זה קבוע. אז עכשיו, בפעם ההכנסה

833
00:50:04,760 --> 00:50:09,700
הוא פחות או יותר O (n).

834
00:50:09,700 --> 00:50:12,410
כך שלא מרגיש כל כך הרבה יותר טוב.

835
00:50:12,410 --> 00:50:14,940
אבל מה האמת כאן? ובכן, כל הזמן הזה, במשך שבועות,

836
00:50:14,940 --> 00:50:20,640
אנחנו אומרים O (n ²). O (n), 2 x n ², - n, מחולק על ידי 2. . . איכס.

837
00:50:20,640 --> 00:50:23,580
זה פשוט ² n. אבל עכשיו, בחלק זה של הסמסטר,

838
00:50:23,580 --> 00:50:25,560
אנחנו יכולים להתחיל לדבר על לחזור לעולם האמיתי.

839
00:50:25,560 --> 00:50:31,520
וn / מ 'הוא בהחלט מהיר יותר מאשר רק n לבד.

840
00:50:31,520 --> 00:50:35,170
אם יש לך אלף שמות, ואתה שובר אותם לסלים מרובים

841
00:50:35,170 --> 00:50:37,820
כך יש לך רק עשרה שמות בכל אחת מרשתות אלה,

842
00:50:37,820 --> 00:50:41,670
בהחלט מחפש עשרה דברים הולך להיות מהיר יותר מאלף דברים.

843
00:50:41,670 --> 00:50:43,740
וכך באחת קבוצות הבעיה הקרובות הוא הולך לאתגר אותך

844
00:50:43,740 --> 00:50:46,100
לחשוב בדיוק על זה למרות, כן,

845
00:50:46,100 --> 00:50:49,520
asymptotically ומתמטי, זה עדיין רק ליניארית,

846
00:50:49,520 --> 00:50:51,700
שמבאס באופן כללי, כאשר מנסים למצוא דברים.

847
00:50:51,700 --> 00:50:54,530
במציאות, זה הולך להיות מהיר יותר מזה

848
00:50:54,530 --> 00:50:56,520
בגלל המחלק הזה.

849
00:50:56,520 --> 00:50:58,310
ואז יש שוב הולך להיות תחלופה זו

850
00:50:58,310 --> 00:51:01,390
וזה קונפליקט בין התאוריה למציאות,

851
00:51:01,390 --> 00:51:03,550
ואת אחד הכפתורים יהיה להתחיל להסתובב בנקודה זו בסמסטר

852
00:51:03,550 --> 00:51:07,510
הוא יותר של מציאות אחת כמו שאנחנו סוג של להתכונן לסוף semster,

853
00:51:07,510 --> 00:51:09,280
כפי שאנו מציגים את העולם של תכנות אינטרנט,

854
00:51:09,280 --> 00:51:11,530
שם באמת, ביצועים הולכים לספור כי המשתמשים שלך הולכים

855
00:51:11,530 --> 00:51:14,880
מתחיל להרגיש ולהעריך את החלטות עיצוב עניות.

856
00:51:14,880 --> 00:51:19,950
>> אז איך אתה הולך על יישום מקושר - שולחן חשיש עם 31 אלמנטים?

857
00:51:19,950 --> 00:51:22,600
והדוגמא הקודמת הייתה באופן שרירותי על ימי הולדת.

858
00:51:22,600 --> 00:51:26,190
אם למישהו יש יום הולדה 1 בינואר או פברואר 1, שנכניס אותם בדלי הזה.

859
00:51:26,190 --> 00:51:28,960
אם זה 2 בינואר 2 בפברואר, 2 במרץ, שנכניס אותם בדלי הזה.

860
00:51:28,960 --> 00:51:32,220
זו סיבה שזה היה 31. איך אתה מצהיר שולחן חשיש?

861
00:51:32,220 --> 00:51:37,480
זה יכול להיות די פשוט, שולחן * צומת הוא שמי השרירותי לזה, [31].

862
00:51:37,480 --> 00:51:42,400
זה נותן לי 31 מצביעים לבלוטות,

863
00:51:42,400 --> 00:51:45,370
וזה מאפשר לי יש 31 מצביעים לרשימות המקושרים

864
00:51:45,370 --> 00:51:48,800
גם אם רשתות אלה תחילה NULL.

865
00:51:48,800 --> 00:51:54,860
מה שאני כן רוצה לשים אם אני רוצה לאחסן את "אליס", "בוב", "צ'ארלי"?

866
00:51:54,860 --> 00:51:57,010
ובכן, אנחנו צריכים לסיים את הדברים האלה במבנה

867
00:51:57,010 --> 00:52:00,530
כי אנחנו צריכים את אליס להצביע לבוב, כדי להצביע על צ'רלי, וכן הלאה.

868
00:52:00,530 --> 00:52:04,940
אנחנו לא יכולים רק צריכים את השמות לבד, אז אני יכול ליצור מבנה חדש בשם צומת כאן.

869
00:52:04,940 --> 00:52:08,310
>> מהו צומת בפועל? מה היא צומת ברשימה המקושרת החדשה הזה?

870
00:52:08,310 --> 00:52:11,840
הדבר הראשון, שנקרא מילה, הוא לשמו של האדם.

871
00:52:11,840 --> 00:52:14,340
האורך, ככל הנראה, מתייחס לאורך המרבי של שמו של אדם,

872
00:52:14,340 --> 00:52:18,210
מה שזה, 20, 30, 40 תווים במקרים פינתיים מטורפים,

873
00:52:18,210 --> 00:52:22,680
ו+1 הוא בשביל מה? זה פשוט אופי NULL הנוסף, \ 0.

874
00:52:22,680 --> 00:52:27,410
אז צומת זו עטיפה "משהו" בתוך עצמו,

875
00:52:27,410 --> 00:52:29,640
אבל זה גם מצהיר מצביע נקרא הבא

876
00:52:29,640 --> 00:52:32,580
כך שאנחנו יכולים שרשרת אליס לבוב לצ'ארלי וכן הלאה.

877
00:52:32,580 --> 00:52:36,700
יכול להיות אפס, אך לא בהכרח צריך להיות.

878
00:52:36,700 --> 00:52:40,110
כל שאלה על שולחנות החשיש האלה? כן?

879
00:52:40,110 --> 00:52:46,190
[סטודנט ששאל את השאלה, לא מובן] מערך - שאלה טובה.

880
00:52:46,190 --> 00:52:50,120
מדוע מילת char זה במערך ולא רק * char?

881
00:52:50,120 --> 00:52:53,830
בדוגמא השרירותית הזה, אני לא רוצה שיהיה לי להיזקק

882
00:52:53,830 --> 00:52:56,190
לmalloc עבור כל אחד מהשמות המקוריים.

883
00:52:56,190 --> 00:52:59,530
אני רוצה להכריז על סכום מקסימאלי של זיכרון עבור המחרוזת

884
00:52:59,530 --> 00:53:06,020
כדי שאוכל להעתיק את מבנה אליס \ 0 ולא אצטרך להתמודד עם malloc וחופשי וכדומה.

885
00:53:06,020 --> 00:53:11,710
אבל אני יכול לעשות את זה אם אני רוצה להיות מודע יותר לשימוש בחלל. שאלה טובה.

886
00:53:11,710 --> 00:53:14,780
אז בואו ננסה לעשות הכללות מזה

887
00:53:14,780 --> 00:53:18,350
ולמקד את השארית היום במבני נתונים באופן כללי יותר

888
00:53:18,350 --> 00:53:21,170
ובעיות אחרות שאנחנו יכולים לפתור תוך שימוש באותם יסודות

889
00:53:21,170 --> 00:53:24,590
למרות שמבני הנתונים עצמם עשויים להיות שונים בפרטים שלהם.

890
00:53:24,590 --> 00:53:27,910
>> אז מתברר במדעי מחשב, עצים נפוצים מאוד.

891
00:53:27,910 --> 00:53:29,760
ואתה יכול לחשוב על סוג של עץ כמו עץ ​​משפחה,

892
00:53:29,760 --> 00:53:31,830
שבו יש כמה שורשים, כמה אמן או הפטריארך,

893
00:53:31,830 --> 00:53:34,540
סבתא או סבא או קודם לכן בחזרה,

894
00:53:34,540 --> 00:53:38,880
שמתחתיו הן אמא ואבא או אחים שונים וכדומה.

895
00:53:38,880 --> 00:53:42,500
אז מבנה עץ יש צומת ויש לה ילדים,

896
00:53:42,500 --> 00:53:45,260
בדרך כלל 0 ילדים או יותר עבור כל צומת.

897
00:53:45,260 --> 00:53:47,320
וחלק מהז'רגון שאתה רואה בתמונה כאן

898
00:53:47,320 --> 00:53:50,630
הוא כל אחד מהילדים הקטנים או הנכדים על הקצוות

899
00:53:50,630 --> 00:53:52,330
שאין לי חצים הנובעים מהם,

900
00:53:52,330 --> 00:53:55,070
אלה הם עלים כביכול, וכל מי שבפנים

901
00:53:55,070 --> 00:53:58,790
הוא צומת פנימית, אתה יכול לקרוא לזה משהו בכיוון הזה.

902
00:53:58,790 --> 00:54:01,430
אבל המבנה הזה הוא די נפוץ. זה קצת שרירותי.

903
00:54:01,430 --> 00:54:04,930
יש לנו ילד אחד בצד השמאל, יש לנו שלושה ילדים בצד ימין,

904
00:54:04,930 --> 00:54:06,830
שני ילדים בפינה שמאלית התחתונה.

905
00:54:06,830 --> 00:54:10,740
אז יכול להיות לנו עצים בגדלים שונים, אבל אם תתחילו לתקנן דברים,

906
00:54:10,740 --> 00:54:15,330
ואתם אולי זוכרים את זה מהווידאו של פטריק בחיפוש בינארי מקצר קודם

907
00:54:15,330 --> 00:54:19,490
חיפוש באינטרנט, בינארי לא צריך להיות מיושם במערך

908
00:54:19,490 --> 00:54:21,410
או פיסות נייר על לוח.

909
00:54:21,410 --> 00:54:25,490
תניח שאתה רוצה לאחסן המספרים שלך במבנה נתונים מתוחכמים יותר.

910
00:54:25,490 --> 00:54:27,680
אתה יכול ליצור עץ כזה.

911
00:54:27,680 --> 00:54:35,290
אתה יכול להיות צומת הכריזה ב-C, וצומת שיכולה להיות לפחות שני אלמנטים בתוכו.

912
00:54:35,290 --> 00:54:39,470
אחת הוא המספר שאתה רוצה לאחסן, והשני הוא - טוב, אנחנו צריכים עוד אחד.

913
00:54:39,470 --> 00:54:41,540
השני הוא הילדים שלה.

914
00:54:41,540 --> 00:54:45,150
אז הנה עוד מבנה נתונים. הפעם, צומת מוגדרת כאחסון מספר n

915
00:54:45,150 --> 00:54:49,060
ואז שני מצביעים, ילד שמאלי וילד נכון.

916
00:54:49,060 --> 00:54:52,100
והם לא שרירותיים. מה שמעניין בעץ הזה?

917
00:54:52,100 --> 00:55:00,550
>> מה הדפוס באופן בו אנו כבר הנחנו את זה או איך פטריק הניח אותו בווידאו שלו?

918
00:55:00,550 --> 00:55:02,790
זה סוג של מובן מאליו שיש איזה מיון קורה כאן,

919
00:55:02,790 --> 00:55:04,460
אבל מה את הכלל הפשוט? כן?

920
00:55:04,460 --> 00:55:08,350
[תשובת סטודנט, לא מובן]

921
00:55:08,350 --> 00:55:12,040
מושלם. אם תציץ בזה, אתה רואה את המספרים הקטנים בצד השמאל,

922
00:55:12,040 --> 00:55:14,690
מספרים גדולים בצד השמאל, אבל זה נכון עבור כל צומת.

923
00:55:14,690 --> 00:55:20,370
לכל צומת, הילד השמאלי שלה פחות ממה שהוא, והילד את זכותו גדול מזה.

924
00:55:20,370 --> 00:55:25,210
מה זה אומר כרגע הוא אם אני רוצה לחפש מבנה נתונים זה, יניח, את המספר 44,

925
00:55:25,210 --> 00:55:29,320
אני חייב להתחיל בשורש, כי כמו בכל המבנים של נתונים מורכבים יותר האלה עכשיו,

926
00:55:29,320 --> 00:55:31,910
יש לנו רק מצביע על דבר אחד, ההתחלה.

927
00:55:31,910 --> 00:55:35,010
ובמקרה הזה, ההתחלה היא בשורש. זה לא הקצה השמאלי,

928
00:55:35,010 --> 00:55:39,530
שהוא שורש של מבנה זה. אז אני רואה כאן הוא 55, ואני מחפש 44.

929
00:55:39,530 --> 00:55:41,430
לאיזה כיוון אני רוצה ללכת?

930
00:55:41,430 --> 00:55:45,680
ובכן, אני רוצה ללכת לשמאל, כי ברור לימין הוא הולך להיות גדול מדי.

931
00:55:45,680 --> 00:55:49,050
אז מבחין כאן, אתה סוג של קיצוץ בחצי העץ מושגית

932
00:55:49,050 --> 00:55:51,700
כי אתה אף פעם לא יורד לצד ימין.

933
00:55:51,700 --> 00:55:55,410
אז עכשיו אני עובר מ55 עד 33. זה קטן מדי של מספר.

934
00:55:55,410 --> 00:56:01,590
אני מחפש 44, אבל עכשיו אני יודע שאם 44 הם בעץ הזה, אני יכול ללכת כמובן לצד ימין.

935
00:56:01,590 --> 00:56:04,460
אז שוב, אני גיזום העץ בחצי.

936
00:56:04,460 --> 00:56:06,780
זה פחות או יותר זהה רעיוני לספר טלפונים.

937
00:56:06,780 --> 00:56:09,510
זה זהה למה שעשינו בניירות שעל הלוח,

938
00:56:09,510 --> 00:56:13,940
אבל זה מבנה מתוחכם יותר המאפשר לנו בעצם לעשות

939
00:56:13,940 --> 00:56:16,880
זה פרד ומשול ידי עיצוב של האלגוריתם,

940
00:56:16,880 --> 00:56:19,420
ולמעשה, חוצה מבנה כזה - אופס.

941
00:56:19,420 --> 00:56:22,870
חוצה מבנה כמו זה, שבו רק "ללכת בדרך זו או ללכת בדרך הזאת",

942
00:56:22,870 --> 00:56:26,870
פירושו כל הקוד שכופף את דעתך בהתחלה בעת יישומו בסעיף

943
00:56:26,870 --> 00:56:31,270
או עובר אותו בבית, לחיפוש בינארי, באמצעות רקורסיה או איטרציה,

944
00:56:31,270 --> 00:56:35,060
זה כאב בצוואר. מצא אלמנט האמצע, ואז לעשות עיגול שלך למעלה או למטה.

945
00:56:35,060 --> 00:56:39,230
>> יש יופי לזה כי עכשיו אנחנו יכולים להשתמש ברקורסיה שוב,

946
00:56:39,230 --> 00:56:43,760
אבל הרבה יותר נקי. ואכן, אם אתה נמצא בבית המספר 55 ואתה רוצה למצוא 44,

947
00:56:43,760 --> 00:56:48,450
אתה הולך השארת במקרה זה, ואז מה אתה עושה? אתה מפעיל אותו האלגוריתם המדויק.

948
00:56:48,450 --> 00:56:51,560
אתה לבדוק את הערך של הצומת, אז אתה הולך ימינה או שמאלה.

949
00:56:51,560 --> 00:56:53,670
אז אתה לבדוק את הערך של הצומת, ללכת ימינה או שמאלה.

950
00:56:53,670 --> 00:56:56,710
זה מתאים בצורה מושלמת לרקורסיה.

951
00:56:56,710 --> 00:57:00,920
אז למרות שבעבר עשה כמה דוגמאות די שרירותיות המעורבות רקורסיה

952
00:57:00,920 --> 00:57:03,430
זה לא צריך להיות רקורסיבית, עם stuctures נתונים,

953
00:57:03,430 --> 00:57:07,820
במיוחד עצים, זה יישום מושלם של הרעיון הזה של לקיחת בעיה,

954
00:57:07,820 --> 00:57:12,920
התכווצותו, ולאחר מכן לפתור את אותו סוג של, אבל, תכנית קטנה יותר.

955
00:57:12,920 --> 00:57:14,590
>> אז יש מבנה נתונים אחר שאנחנו יכולים להציג.

956
00:57:14,590 --> 00:57:18,760
1 זה נועד במבט הראשון נראה מסתורי, אבל זה אחד מדהים.

957
00:57:18,760 --> 00:57:25,090
אז זה הוא מבנה נתונים בשם איירי, איירי, שהתקבל בירושה ממילת האחזור,

958
00:57:25,090 --> 00:57:30,210
שלא מבוטא מחדש לנסות-val, אבל זה מה שהעולם קורא את הדברים האלה. מנסה. T-r-i-דואר.

959
00:57:30,210 --> 00:57:35,190
זהו מבנה עץ מסוג כלשהו, ​​אבל כל אחד מצומת באיירי

960
00:57:35,190 --> 00:57:41,280
נראה כי מה? וזה קצת מטעה, כי זה סוג של מקוצר.

961
00:57:41,280 --> 00:57:45,960
אבל זה נראה כמו כל צומת באיירי זה היא למעשה מערך.

962
00:57:45,960 --> 00:57:48,840
ולמרות שמחבר תרשים זה לא הראה את זה,

963
00:57:48,840 --> 00:57:54,130
במקרה זה, איירי זה היא מבנה נתונים שמטרתו בחיים הוא לאחסן מילים

964
00:57:54,130 --> 00:57:57,330
כמו-l-i-c-דואר או B-O-B.

965
00:57:57,330 --> 00:58:02,480
ואופן שבו נתוני החנויות אליס ובוב וצ'ארלי ואניטה וכן הלאה

966
00:58:02,480 --> 00:58:06,970
הוא משתמש במערך לפי לאחסן אליס בארץ איירי,

967
00:58:06,970 --> 00:58:09,820
אנחנו מתחילים בצומת השורש שנראה כמו מערך,

968
00:58:09,820 --> 00:58:12,080
וזה כתוב בסימון מקוצר.

969
00:58:12,080 --> 00:58:15,070
המחבר השמיט אבגדהוז כי לא היו שמות עם זה.

970
00:58:15,070 --> 00:58:19,150
הם הראו M ו-P ו-T בלבד, אבל במקרה הזה,

971
00:58:19,150 --> 00:58:22,780
בואו נתרחק מאליס ובוב וצ'רלי לכמה שמות שנמצאים כאן.

972
00:58:22,780 --> 00:58:25,670
מקסוול הוא למעשה בשרטוט זה.

973
00:58:25,670 --> 00:58:29,570
אז איך עשה את חנות מחבר M--x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
הוא או היא התחיל בצומת השורש, והלך ל[ ז], כך שבערך 13, מיקום ה -13 במערך.

975
00:58:36,990 --> 00:58:40,750
אז משם, יש מצביע.

976
00:58:40,750 --> 00:58:42,760
מצביע שמוביל למערך אחר.

977
00:58:42,760 --> 00:58:47,880
משם המחבר צמוד שלמערך במיקום, כפי שמוצג שם בפינה שמאלית עליונה,

978
00:58:47,880 --> 00:58:52,250
ואז הוא או היא אחרי שהמצביע למערך אחר,

979
00:58:52,250 --> 00:58:55,460
והלך למצביע במיקום X.

980
00:58:55,460 --> 00:58:59,840
ואז במערך המיקום W הבא, E, L, L, וכן הלאה,

981
00:58:59,840 --> 00:59:03,090
ולבסוף, בואו באמת מנסה לשים תמונה לזה.

982
00:59:03,090 --> 00:59:05,380
איך נראה צומת כמו בקוד?

983
00:59:05,380 --> 00:59:11,820
בצומת איירי מכילה מערך של מצביעים לצומת נוספים.

984
00:59:11,820 --> 00:59:16,090
אבל יש גם חייב להיות איזשהו הערך בוליאני, לפחות ביישום זה.

985
00:59:16,090 --> 00:59:18,770
אני במקרה קורא לזה is_word. למה?

986
00:59:18,770 --> 00:59:22,670
כי כשאתה מכניס מקסוול, אתה לא מכניס

987
00:59:22,670 --> 00:59:25,300
משהו לתוך מבנה נתונים זה.

988
00:59:25,300 --> 00:59:27,480
אתה לא כותב מ 'אתה לא כותב X.

989
00:59:27,480 --> 00:59:30,240
כל מה שאתה עושה הוא בעקבות מצביעים.

990
00:59:30,240 --> 00:59:33,360
המצביע המייצג M, אז המצביע המייצג,

991
00:59:33,360 --> 00:59:36,310
אז המצביע המייצג X, אז W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
אבל מה שאתה צריך לעשות בסוף הוא סוג של ללכת, בדוק, שהגעתי מיקום זה.

993
00:59:41,950 --> 00:59:45,560
הייתה מילה שמסתיימת כאן במבנה הנתונים.

994
00:59:45,560 --> 00:59:48,190
>> אז מה היא באמת איירי מלאה והמחבר בחר לייצג

995
00:59:48,190 --> 00:59:51,880
terminuses אלה עם משולשים קטנים.

996
00:59:51,880 --> 00:59:56,470
זה רק אומר שעובדת המשולש הזה כאן, ערך בוליאני זה של אמיתי

997
00:59:56,470 --> 00:59:59,200
משמעות היא שאם אתה הולך אחורה בעץ,

998
00:59:59,200 --> 01:00:02,420
זה אומר מילה בשם מקסוול הוא בזה.

999
01:00:02,420 --> 01:00:04,870
אבל המילה foo, למשל,

1000
01:00:04,870 --> 01:00:07,970
לא בעץ, משום שאם אני מתחיל לעבוד בצומת השורש לכאן בראש,

1001
01:00:07,970 --> 01:00:14,030
אין מצביע f, אין מצביע o, אין מצביע o. Foo אינו שם במילון זה.

1002
01:00:14,030 --> 01:00:22,460
אבל לעומת זאת, טיורינג, t-u-r-i-n-g. שוב, אני לא לאחסן t או u או r או אני או n או g.

1003
01:00:22,460 --> 01:00:29,820
אבל עשיתי את החנות במבנה נתונים זה ערך של דרך האמיתית כאן בצומת הזה - בעץ

1004
01:00:29,820 --> 01:00:33,030
על ידי הגדרת הערך בוליאני זה של is_word לנכון.

1005
01:00:33,030 --> 01:00:35,740
אז איירי היא סוג של המבנה מטה מאוד המעניין הזה,

1006
01:00:35,740 --> 01:00:39,810
איפה שאתה לא באמת אחסון הדברים עצמם לסוג זה של מילון.

1007
01:00:39,810 --> 01:00:45,100
כדי להיות ברור, אתה רק אחסון כן או לא, יש מילה שמסתיימת כאן.

1008
01:00:45,100 --> 01:00:46,430
>> עכשיו, מה המשמעות?

1009
01:00:46,430 --> 01:00:51,120
אם יש לך 150.000 מילים במילון שאתה מנסה לאחסן בזיכרון

1010
01:00:51,120 --> 01:00:53,400
באמצעות משהו כמו רשימה מקושרת,

1011
01:00:53,400 --> 01:00:56,870
אתה הולך לי 150.000 צומת ברשימה המקושרת שלך.

1012
01:00:56,870 --> 01:01:00,250
ולמצוא אחת את המילים האלה בסדר אלפביתי יכול לקחת זמן O (n).

1013
01:01:00,250 --> 01:01:04,370
הזמן ליניארי. אבל במקרה כאן של איירי,

1014
01:01:04,370 --> 01:01:09,210
מה זמן הריצה של מציאת מילה?

1015
01:01:09,210 --> 01:01:17,390
מתברר היופי כאן הוא שגם אם יש לך 149,999 מילים כבר במילון זה,

1016
01:01:17,390 --> 01:01:20,170
כפי שיושם במבנה נתונים זה,

1017
01:01:20,170 --> 01:01:25,560
כמה זמן לוקח למצוא או להכניס אדם נוסף לזה, כמו אליס, אליס?

1018
01:01:25,560 --> 01:01:30,640
טוב, זה רק 5, אולי 6 שלבים לתו הנגרר.

1019
01:01:30,640 --> 01:01:32,880
בגלל הנוכחות בשמות אחרים במבנה

1020
01:01:32,880 --> 01:01:35,340
לא מקבל בדרך של החדרת אליס.

1021
01:01:35,340 --> 01:01:39,640
יתר על כן, מציאת אליס פעם יש 150.000 מילים במילון זה

1022
01:01:39,640 --> 01:01:41,960
לא מקבל בדרך של מציאת אליס כלל,

1023
01:01:41,960 --> 01:01:46,880
כי אליס היא. . . . . כאן, בגלל שמצאתי ערך בוליאני.

1024
01:01:46,880 --> 01:01:50,920
ואם אין בוליאני הנכונה, אז אליס היא לא במבנה הנתונים הזה של מילים.

1025
01:01:50,920 --> 01:01:56,220
במילים אחרות, הזמן פועל למציאת דברים והחדרת דברים לזה חדש

1026
01:01:56,220 --> 01:02:01,920
מבנה נתונים של איירי הוא הו - זה לא N.

1027
01:02:01,920 --> 01:02:05,730
בגלל הנוכחות בשל 150.000 אנשים אין כל השפעה על אליס, שזה נראה.

1028
01:02:05,730 --> 01:02:11,560
אז בואו נקראים לזה k, כאשר k הוא האורך המקסימאלי של מילה באנגלית

1029
01:02:11,560 --> 01:02:14,050
שהוא בדרך כלל לא יותר מתווים 20-משהו.

1030
01:02:14,050 --> 01:02:17,940
אז k הוא קבוע. אז את הגביע הקדוש נראים שאנו נמצאים כעת

1031
01:02:17,940 --> 01:02:26,000
הוא זו של זמן איירי, קבוע למוסיף, לחיפושים, למחיקות.

1032
01:02:26,000 --> 01:02:29,170
בגלל מספר הדברים שכבר קיים במבנה,

1033
01:02:29,170 --> 01:02:32,600
שהם אפילו לא שם פיסיים. שוב, הם פשוט למיין של מסומן, כן או לא,

1034
01:02:32,600 --> 01:02:35,050
אין השפעה על זמן הריצה שלו בעתיד.

1035
01:02:35,050 --> 01:02:37,940
>> אבל בוודאי יש להיות מלכוד, אחרת לא היה מבזבז כל כך הרבה זמן

1036
01:02:37,940 --> 01:02:41,460
בכל מבני נתונים אחרים אלה רק לבסוף להגיע לאחד הסוד שזה מדהים.

1037
01:02:41,460 --> 01:02:46,410
אז מה מחיר אנחנו משלמים כדי להגיע לגדולה זה כאן? חלל.

1038
01:02:46,410 --> 01:02:49,010
דבר זה הוא מסיבי. והסיבה לכך שהמחבר

1039
01:02:49,010 --> 01:02:52,400
לא הציג את זה כאן, שים לב שכל הדברים האלה שנראים כמו מערכים,

1040
01:02:52,400 --> 01:02:55,400
הוא לא משך את שאר העץ, שאר איירי,

1041
01:02:55,400 --> 01:02:58,060
כי הם פשוט לא רלוונטיים לסיפור.

1042
01:02:58,060 --> 01:03:01,870
אבל כל צומת האלה הם רחבים במיוחד, ובכל צומת בעץ תופסת

1043
01:03:01,870 --> 01:03:07,780
26 או בעצם, יכול להיות 27 תווים, כי במקרה זה הייתי בכלל מקום לגרש

1044
01:03:07,780 --> 01:03:09,980
כך שיכול להיות לנו מילות apostrophized.

1045
01:03:09,980 --> 01:03:14,450
במקרה זה, מדובר במערכים רחבים. אז למרות שהם לא picutured,

1046
01:03:14,450 --> 01:03:18,190
זה לוקח כמות מסיבית של זכרון RAM.

1047
01:03:18,190 --> 01:03:20,670
אשר עשוי להיות בסדר, especilly בחומרה מודרנית,

1048
01:03:20,670 --> 01:03:25,650
אבל זה האיזון. אנחנו מקבלים פחות זמן על ידי ההוצאה יותר מקום.

1049
01:03:25,650 --> 01:03:28,580
אז איפה הוא כל זה הולך?

1050
01:03:28,580 --> 01:03:32,640
ובכן, בואו נעשה - בואו לראות כאן.

1051
01:03:32,640 --> 01:03:39,510
בואו נעשה קפיצה לבחור הזה כאן.

1052
01:03:39,510 --> 01:03:43,450
>> תאמינו או לא, כיף כמו C כבר כמה זמן,

1053
01:03:43,450 --> 01:03:48,130
אנחנו מגיעים לנקודה בסמסטר שבו הגיע זמן למעבר לדברים יותר מודרניים.

1054
01:03:48,130 --> 01:03:50,950
דברים ברמה גבוהה יותר. ואף על פי לשבועות הקרובים

1055
01:03:50,950 --> 01:03:54,580
אנחנו עדיין נמשיך לטבול את עצם בעולם של מצביעים וניהול זיכרון

1056
01:03:54,580 --> 01:03:57,210
כדי לקבל נחמה זו שאיתה אז יכולה לבנות עליו,

1057
01:03:57,210 --> 01:04:01,270
סוף המשחק הוא בסופו להציג, באופן אירוני, לא זו שפה.

1058
01:04:01,270 --> 01:04:03,330
נבלנו, כמו 10 דקות בדיבורים על ה-HTML.

1059
01:04:03,330 --> 01:04:05,950
כל HTML הוא הוא שפת סימון, ומה היא שפת סימון

1060
01:04:05,950 --> 01:04:10,220
אלה הוא סדרה של סוגריים פתוחים וסגורים סוגריים שאומרים 'תעשה את זה מודגש'

1061
01:04:10,220 --> 01:04:12,000
"לעשות את זה" הנטוי "לעשות מרכז זה '.

1062
01:04:12,000 --> 01:04:14,250
זה לא כל כך מעניין מבחינה אינטלקטואלית, אבל זה סופר שימושי.

1063
01:04:14,250 --> 01:04:16,650
וזה בהחלט נוכח בכל מקום בימים אלה.

1064
01:04:16,650 --> 01:04:19,450
אבל מה רב עצמה על העולם של ה-HTML, ותכנות אינטרנט באופן כללי יותר,

1065
01:04:19,450 --> 01:04:25,910
בונה דברים דינמיים; כתיבת קוד בשפות כמו PHP או Python או Ruby או Java או C #.

1066
01:04:25,910 --> 01:04:30,360
באמת, כל השפה של בחירה שלך, ויצירת HTML באופן דינמי.

1067
01:04:30,360 --> 01:04:32,960
יצירת משהו שנקרא CSS באופן דינמי.

1068
01:04:32,960 --> 01:04:35,810
גיליונות סגנון מדורג, שהיא גם באסתטיקה.

1069
01:04:35,810 --> 01:04:41,360
וכך למרות שהיום, אם אני הולך לאתר מסוים כמו Google.com המוכר,

1070
01:04:41,360 --> 01:04:46,100
ואני הולכת להצגה, ליזם, הצגת מקור, שאולי כבר עשה קודם,

1071
01:04:46,100 --> 01:04:49,800
אבל הולך להציג מקור, החומר הזה כנראה נראה די תמוה.

1072
01:04:49,800 --> 01:04:55,320
אבל זה הקוד הבסיסי שמיישם Google.com.

1073
01:04:55,320 --> 01:04:57,940
על הקצה הקדמי. ובעצם כל זה הוא דברי אסתטיקה אווריריות.

1074
01:04:57,940 --> 01:05:01,740
זה CSS עד כאן. אם אני שומר את הגלילה למטה נקבל כמה דברים בצבעים.

1075
01:05:01,740 --> 01:05:06,890
זה HTML. הקוד של גוגל נראה כמו בלגן, אבל אם אני באמת לפתוח את חלון אחר,

1076
01:05:06,890 --> 01:05:09,380
אנו יכולים לראות כמה מבנה לזה.

1077
01:05:09,380 --> 01:05:12,640
אם אני פותח את זה, שים לב כאן, זה קצת יותר קריא.

1078
01:05:12,640 --> 01:05:16,850
אנחנו הולכים לראות תג זה לפני זמן רב, [מילה] הוא תג,

1079
01:05:16,850 --> 01:05:23,520
HTML, ראש, גוף, div, תסריט, אזור טקסט, תוחלת, ממוקד, div.

1080
01:05:23,520 --> 01:05:26,770
וזה גם למיין נסתר למראה במבט הראשון,

1081
01:05:26,770 --> 01:05:30,890
אבל כל הבלגן הזה כדלקמן דפוסים מסוימים, ודפוסי דיר,

1082
01:05:30,890 --> 01:05:33,850
כך שברגע שיקבל את היסודות למטה, תוכל לכתוב קוד כזה

1083
01:05:33,850 --> 01:05:37,550
ולאחר מכן לתפעל קוד כזה עדיין משתמש בשפה אחרת, בשם-JavaScript.

1084
01:05:37,550 --> 01:05:40,440
וJavaScript היא שפה שפועלת בתוך דפדפן

1085
01:05:40,440 --> 01:05:44,380
היום שאנו משתמשים בקורסי הרווארד, לכלי הקניות כמובן שגוגל מפות משתמשות

1086
01:05:44,380 --> 01:05:48,660
כדי לתת לך חבורה שלמה של דינמי, פייסבוק נותן לך להציג עדכוני סטטוס מיידיים,

1087
01:05:48,660 --> 01:05:51,430
טוויטר משתמש בו כדי להראות לך טוויטים באופן מיידי.

1088
01:05:51,430 --> 01:05:53,820
כל זה יתחיל לשקוע פנימה את עצמנו

1089
01:05:53,820 --> 01:05:57,190
אבל כדי להגיע לשם, אנחנו צריכים להבין משהו קטן על האינטרנט.

1090
01:05:57,190 --> 01:06:01,130
הקליפ הזה כאן הוא רק דקה ארוכה, ובואו נניח לזה עכשיו, למעשה,

1091
01:06:01,130 --> 01:06:08,380
איך האינטרנט עובד כמו טיזר למה שעומד לבוא. אני נותן לך "לוחמים של הרשת."

1092
01:06:08,380 --> 01:06:14,720
>> [מוסיקת ♫ מקהלה איטית ♫]

1093
01:06:14,720 --> 01:06:20,450
[מספרת זכר] הוא הגיע עם הודעה.

1094
01:06:20,450 --> 01:06:23,770
בפרוטוקול כולו.

1095
01:06:23,770 --> 01:06:37,270
[♫ מוסיקה אלקטרונית מהירים יותר ♫]

1096
01:06:37,270 --> 01:06:41,330
הוא הגיע לעולם של חומות אש הקרירות, אדיש נתבים,

1097
01:06:41,330 --> 01:06:45,690
וסכנות הרבה יותר גרועות ממוות.

1098
01:06:45,690 --> 01:06:55,400
הוא מהיר מאוד. הוא חזק. הוא TCP / IP, ויש לו את הכתובת שלך.

1099
01:06:55,400 --> 01:06:59,250
לוחמים של הרשת.

1100
01:06:59,250 --> 01:07:05,290
[מלאן] בשבוע הבא, ולאחר מכן. האינטרנט. תכנות אינטרנט. זה CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]