1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Walkthrough - סט בעיה 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla צ'אן - אוניברסיטת הרווארד]

3
00:00:04,810 --> 00:00:07,240
[זה CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> שלום לכולם, וברוך הבאים לWalkthrough 6: פאף Huff'n.

5
00:00:12,180 --> 00:00:17,440
בפאף Huff'n מה שאנחנו עושים הוא הולך להיות התמודדות עם קובץ דחוס האפמן

6
00:00:17,440 --> 00:00:20,740
ולאחר מכן מנפח אותו בחזרה למעלה, ולכן decompressing,

7
00:00:20,740 --> 00:00:25,810
כדי שנוכל לתרגם מ0s ו 1s שהמשתמש שולח לנו

8
00:00:25,810 --> 00:00:30,660
ולהמיר אותו בחזרה לטקסט המקורי.

9
00:00:30,660 --> 00:00:34,360
Pset 6 הולכים להיות די מגניב כי אתה הולך לראות כמה מהכלים

10
00:00:34,360 --> 00:00:41,730
שבו השתמש בpset 4 ו 5 וpset סוג של שילובם בקונספט די מגניב 1

11
00:00:41,730 --> 00:00:43,830
כשאתה בא לחשוב על זה.

12
00:00:43,830 --> 00:00:50,110
>> כמו כן, ניתן לטעון, pset 4 ו 5 היה psets המאתגר ביותר שהיו לנו להציע.

13
00:00:50,110 --> 00:00:53,950
אז מעכשיו, יש לנו 1 יותר pset זה ב-C,

14
00:00:53,950 --> 00:00:56,480
ואז אחרי שאנחנו בתכנות אינטרנט.

15
00:00:56,480 --> 00:01:02,310
אז לברך את עצמכם להשגה על הדבשת הקשה ביותר בCS50.

16
00:01:03,630 --> 00:01:09,760
>> העברה ב לפאף Huff'n, ארגז הכלים שלנו לpset זה הולך להיות עצי האפמן,

17
00:01:09,760 --> 00:01:14,700
לכן הבנה לא רק במיוחד עצי האפמן אופן עבודה של עצים בינארי אלא גם,

18
00:01:14,700 --> 00:01:16,240
איך הם בנויים.

19
00:01:16,240 --> 00:01:20,210
ואז אנחנו הולכים להיות הרבה קוד הפצה בpset זה,

20
00:01:20,210 --> 00:01:22,480
ואנחנו נבוא לראות שבעצם חלק מהקוד

21
00:01:22,480 --> 00:01:24,670
אנחנו אולי לא יכולים להבין באופן מלא עדיין,

22
00:01:24,670 --> 00:01:30,080
ולכן אלה יהיו. את קבצי C, אבל אז. הקבצים המצורפים h

23
00:01:30,080 --> 00:01:34,300
ייתן לנו מספיק הבנה שאנו זקוקים לכך שאנחנו יודעים איך פונקציות אלו עובדות

24
00:01:34,300 --> 00:01:38,100
או לפחות את מה שהם אמורים לעשות - התשומות והתפוקות שלהם -

25
00:01:38,100 --> 00:01:40,760
גם אם אנחנו לא יודעים מה קורים בקופסה השחורה

26
00:01:40,760 --> 00:01:44,090
או שאינך מבין מה קורה בקופסה השחורה שבפנים.

27
00:01:44,090 --> 00:01:49,400
ולבסוף, כרגיל, אנו עוסקים במבני נתונים חדשים,

28
00:01:49,400 --> 00:01:51,840
סוגים מסוימים של צומת המצביעים על דברים מסוימים,

29
00:01:51,840 --> 00:01:56,080
וכן כאן יש עט ונייר לא רק לתהליך העיצוב

30
00:01:56,080 --> 00:01:58,470
וכשאתה מנסה להבין איך pset צריכה לעבוד

31
00:01:58,470 --> 00:02:00,520
אלא גם בניפוי.

32
00:02:00,520 --> 00:02:06,140
אתה יכול לקבל GDB צד העט והנייר שלך בזמן שאתה לוקח את מה שהערכים הם,

33
00:02:06,140 --> 00:02:09,320
שם החיצים שלך מצביעים, ודברים כאלה.

34
00:02:09,320 --> 00:02:13,720
>> ראשית בואו נסתכל על עצי האפמן.

35
00:02:13,720 --> 00:02:19,600
עצי האפמן הם עצים בינאריים, כלומר כל צומת יש 2 ילדים בלבד.

36
00:02:19,600 --> 00:02:24,870
בעצי האפמן האופייני הוא שהערכים השכיחים ביותר

37
00:02:24,870 --> 00:02:27,140
מיוצגים על ידי את הביטים הכי מעט.

38
00:02:27,140 --> 00:02:32,690
ראינו בדוגמאות הרצאה של קוד מורס, סוג של מאוחד שכמה מכתבים.

39
00:02:32,690 --> 00:02:38,030
אם אתה מנסה לתרגם או דואר, למשל,

40
00:02:38,030 --> 00:02:43,940
אתה מתרגם את זה לעתים קרובות, כך שבמקום שיצטרך להשתמש בסט המלא של ביטים

41
00:02:43,940 --> 00:02:48,640
הוקצה עבור אותו סוג הנתונים רגיל, אתם דוחסים אותו למעט יותר,

42
00:02:48,640 --> 00:02:53,730
ואז אותיות אלה המיוצגים בתדירות נמוכה יותר מיוצגות עם חתיכות ארוכות יותר

43
00:02:53,730 --> 00:02:59,840
כי אתה יכול להרשות לעצמך שכשאתה שוקל את התדרים שהמכתבים האלה מופיעים.

44
00:02:59,840 --> 00:03:03,020
יש לנו את אותו רעיון כאן בעצי האפמן

45
00:03:03,020 --> 00:03:12,360
שבו אנו עושים את שרשרת, סוג של הדרך להגיע לתווים המסוימים.

46
00:03:12,360 --> 00:03:14,470
ולאחר מכן את הדמויות שיש להם רוב בתדר

47
00:03:14,470 --> 00:03:17,940
הולכים להיות מיוצגים עם חתיכות הקטנות ביותר.

48
00:03:17,940 --> 00:03:22,020
>> אופן שבו אתה לבנות עץ האפמן

49
00:03:22,020 --> 00:03:27,430
היא על ידי נחת את כל הדמויות המופיעות בטקסט

50
00:03:27,430 --> 00:03:30,630
וחישוב התדר שלהם, באיזו תדירות הם מופיעים.

51
00:03:30,630 --> 00:03:33,880
זה יכול להיות או לספור כמה פעמים מופיעות אותיות אלה

52
00:03:33,880 --> 00:03:40,270
או אולי אחוז מתוך כל הדמויות כמה כל אחד מהם מופיע.

53
00:03:40,270 --> 00:03:44,270
ואז מה שאתה עושה הוא ברגע שאתה צריך את כל זה החוצה מיפה,

54
00:03:44,270 --> 00:03:49,060
אז אתה מחפש את 2 תדרים הנמוכים ולאחר מכן תצטרף אליהם כאחים

55
00:03:49,060 --> 00:03:55,660
אז שבו צומת האב יש תדר שהוא הסכום של 2 ילדיה.

56
00:03:55,660 --> 00:04:00,870
ואז אתה אומר שעל ידי כינוס הצומת השמאלית,

57
00:04:00,870 --> 00:04:03,770
אתה מבין שעל ידי ביצוע 0 הסניף,

58
00:04:03,770 --> 00:04:08,140
ולאחר מכן את הצומת הימנית ביותר היא הענף 1.

59
00:04:08,140 --> 00:04:16,040
כפי שראינו בקוד מורס, האחד תפס אותך היה שאם היה לך רק צפצוף והצפצוף

60
00:04:16,040 --> 00:04:18,120
זה היה מעורפל.

61
00:04:18,120 --> 00:04:22,430
זה יכול גם להיות מכתב 1 או שזה יכול להיות רצף של 2 אותיות.

62
00:04:22,430 --> 00:04:27,790
אז מה עושה עצי האפמן הוא, כי על ידי אופיין של הדמויות

63
00:04:27,790 --> 00:04:34,140
או הדמויות שלנו סופיות בפועל מהווים את צומת האחרונים בענף -

64
00:04:34,140 --> 00:04:39,300
אנו מתייחסים לאלו כעלים - מכוח שיש לא יכול להיות כל עמימות

65
00:04:39,300 --> 00:04:45,160
במונחים של מכתב שאתה מנסה לקודד עם הסדרה של ביטים

66
00:04:45,160 --> 00:04:50,670
כי בשום מקום לאורך הביטים המייצגים את מכתב 1

67
00:04:50,670 --> 00:04:55,960
יהיה לך להיתקל במכתב אחר שלם, ולא יהיה כל בלבול ש.

68
00:04:55,960 --> 00:04:58,430
אבל תלכו לדוגמאות שאתם ממש יכולים לראות כי

69
00:04:58,430 --> 00:05:02,120
במקומנו רק אומר לך שזה נכון.

70
00:05:02,120 --> 00:05:06,390
>> בואו נסתכל על דוגמה פשוטה לעץ האפמן.

71
00:05:06,390 --> 00:05:09,380
יש לי כאן שהיא מחרוזת ארוכה 12 תווים.

72
00:05:09,380 --> 00:05:14,010
יש לי 4 כ, 6 ארוחת בוקר, ו 2 Cs.

73
00:05:14,010 --> 00:05:17,270
הצעד הראשון שלי יהיה לספור.

74
00:05:17,270 --> 00:05:20,760
כמה פעמים לא מופיע? נראה 4 פעמים במחרוזת.

75
00:05:20,760 --> 00:05:25,060
B מופיע 6 פעמים, ו-C מופיע 2 פעמים.

76
00:05:25,060 --> 00:05:28,970
באופן טבעי, אני הולך להגיד אני משתמש ב 'לרוב,

77
00:05:28,970 --> 00:05:35,970
אז אני רוצה לייצג B עם המספר הנמוך ביותר של ביטים, מספר הנמוך ביותר של 0s ו 1s.

78
00:05:35,970 --> 00:05:42,600
ואז אני גם הולך לצפות C לדרוש את הכמות הגדולה ביותר של 0s ו 1s גם כן.

79
00:05:42,600 --> 00:05:48,550
ראשית מה שעשיתי כאן הוא שהנחתי אותן בסדר עולה מבחינת תדירות.

80
00:05:48,550 --> 00:05:52,710
אנו רואים שC ו, אלה הם 2 התדרים הנמוכים ביותר שלנו.

81
00:05:52,710 --> 00:06:00,290
אנו יוצרים צומת אב, וכי צומת ההורה לא צריך מכתב הקשור אליו,

82
00:06:00,290 --> 00:06:05,070
אבל יש תדר, שהוא הסכום.

83
00:06:05,070 --> 00:06:08,780
הסכום הופך 2 + 4, שעומדים על 6.

84
00:06:08,780 --> 00:06:10,800
אז אנחנו עוקבים אחרי הענף השמאלי.

85
00:06:10,800 --> 00:06:14,970
אם אנחנו נמצאים בצומת 6, אז הייתי לעקוב 0 להגיע לג

86
00:06:14,970 --> 00:06:17,450
ואז 1 להגיע לא

87
00:06:17,450 --> 00:06:20,300
אז עכשיו יש לנו 2 צמתים.

88
00:06:20,300 --> 00:06:23,920
יש לנו את הערך 6 ואז יש לנו גם צומת אחר עם הערך 6.

89
00:06:23,920 --> 00:06:28,550
ולכן אלה 2 הם לא רק 2 הנמוכים ביותר, אלא גם בדיוק 2 שעזבו,

90
00:06:28,550 --> 00:06:33,820
אז אנחנו מצטרפים לאלה של הורה אחר, עם הסכום להיות 12.

91
00:06:33,820 --> 00:06:36,300
אז הנה יש לנו עץ האפמן

92
00:06:36,300 --> 00:06:40,020
איפה ניתן לקבל ל-B, שהיה אמור להיות רק 1 הביט

93
00:06:40,020 --> 00:06:45,430
ולאחר מכן להגיע ליהיה לנו 01 ולאחר מכן יש C 00.

94
00:06:45,430 --> 00:06:51,300
אז הנה אנו רואים שבעצם אנחנו מייצגים את התווים האלה עם 1 או 2 ביטים

95
00:06:51,300 --> 00:06:55,160
בי B, כצפוי, יש לפחות.

96
00:06:55,160 --> 00:07:01,730
ואז ציפינו C יש רוב, אך מכיוון שזה עץ האפמן קטן כזה,

97
00:07:01,730 --> 00:07:06,020
אז גם הוא מיוצג על ידי 2 ביטים בניגוד לאי שם באמצע.

98
00:07:07,820 --> 00:07:11,070
>> רק לעבור על דוגמה פשוטה אחרת של עץ האפמן,

99
00:07:11,070 --> 00:07:19,570
אומר שיש לך את המחרוזת "שלום".

100
00:07:19,570 --> 00:07:25,360
מה שאתה עושה הוא ראשון שהייתי אומר כמה פעמים אין H מופיע בזה?

101
00:07:25,360 --> 00:07:34,200
H מופיע פעם אחת ולאחר מכן דואר מופיע פעם אחת ולאחר מכן יש לנו אני מופיע פעמים

102
00:07:34,200 --> 00:07:36,580
o ומופיעה פעם אחת.

103
00:07:36,580 --> 00:07:44,310
ואם כך אנו מצפים שמכתב להיות מיוצגים על ידי המספר המינימאלי של ביטים?

104
00:07:44,310 --> 00:07:47,450
[תלמיד] l. אני. >> Yeah. l הוא נכון.

105
00:07:47,450 --> 00:07:50,730
אנו מצפים l להיות מיוצגים על ידי המספר המינימאלי של ביטים

106
00:07:50,730 --> 00:07:55,890
כי אני משמש ביותר במחרוזת "שלום".

107
00:07:55,890 --> 00:08:04,280
מה שאני הולך לעשות עכשיו הוא למשוך את ההקשרים האלה.

108
00:08:04,280 --> 00:08:15,580
יש לי 1, שהוא גובה, ולאחר מכן עוד 1, שהוא הדואר, ולאחר מכן 1, אשר הוא O -

109
00:08:15,580 --> 00:08:23,410
עכשיו אני מכניס אותם במטרה - ולאחר מכן 2, שהוא אני.

110
00:08:23,410 --> 00:08:32,799
אז אני אומר שהדרך שאני לבנות עץ האפמן היא למצוא את 2 צומת עם התדרים הפחות

111
00:08:32,799 --> 00:08:38,010
ולהפוך אותם לאחים על ידי יצירת צומת אב.

112
00:08:38,010 --> 00:08:41,850
כאן יש לנו 3 צומת עם התדירות הנמוכה ביותר. הם כולם 1.

113
00:08:41,850 --> 00:08:50,620
אז הנה אנחנו בוחרים בו אנחנו הולכים קישור הראשון.

114
00:08:50,620 --> 00:08:54,850
נניח שאני בוחר H והדואר.

115
00:08:54,850 --> 00:09:01,150
הסכום של 1 + 1 הוא 2, אבל הצומת הזה אין מכתב המשויך אליו.

116
00:09:01,150 --> 00:09:04,440
זה פשוט מחזיק את הערך.

117
00:09:04,440 --> 00:09:10,950
עכשיו אנחנו מסתכלים על 2 תדרים הקרובים הנמוכים ביותר.

118
00:09:10,950 --> 00:09:15,590
זה 2 ו 1. זה יכול להיות אחד מאלה 2, אבל אני הולך לבחור אחד זה.

119
00:09:15,590 --> 00:09:18,800
הסכום הוא 3.

120
00:09:18,800 --> 00:09:26,410
ולבסוף, יש לי רק 2 שמאל, אז זה הופך להיות 5.

121
00:09:26,410 --> 00:09:32,010
אז הנה, כצפוי, אם אני ממלא בקידוד בשביל זה,

122
00:09:32,010 --> 00:09:37,480
1s תמיד הסניף ו0s ימין הוא השמאל.

123
00:09:37,480 --> 00:09:45,880
אז יש לנו אני מיוצג על ידי רק קצת 1 ולאחר מכן o על ידי 2

124
00:09:45,880 --> 00:09:52,360
ולאחר מכן על ידי הדואר 2 ולאחר מכן H נופל ל3 חתיכות.

125
00:09:52,360 --> 00:09:59,750
אז אתה יכול להעביר את המסר הזה "שלום" במקום באמת משתמש בתווים

126
00:09:59,750 --> 00:10:02,760
רק על ידי 0s ו 1s.

127
00:10:02,760 --> 00:10:07,910
עם זאת, זכור כי בכמה מקרים שהיו לנו קשרים עם התדר שלנו.

128
00:10:07,910 --> 00:10:11,900
יכולנו הצטרפנו גם H וo 1 אולי.

129
00:10:11,900 --> 00:10:15,730
או אז בשלב מאוחר יותר, כאשר היו לנו אני מיוצג על ידי 2

130
00:10:15,730 --> 00:10:19,410
כמו גם הצטרפתי לאחד מיוצג על ידי 2, היינו יכול קשור אחת מהן.

131
00:10:19,410 --> 00:10:23,630
>> וכך, כאשר אתה שולח 0s ו 1s, שלמעשה אינו מבטיח

132
00:10:23,630 --> 00:10:27,090
שהנמען יכול לקרוא את ההודעה שלך במלואו מייד את הבת

133
00:10:27,090 --> 00:10:30,490
משום שהם אולי לא יודעים שהחלטה שקבלת.

134
00:10:30,490 --> 00:10:34,920
לכן, כאשר יש לנו עסק עם דחיסת האפמן,

135
00:10:34,920 --> 00:10:40,090
איכשהו יש לנו לספר לנמען ההודעה שלנו איך אנחנו החלטנו -

136
00:10:40,090 --> 00:10:43,470
הם צריכים לדעת איזה מידע נוסף

137
00:10:43,470 --> 00:10:46,580
בנוסף להודעה הדחוסה.

138
00:10:46,580 --> 00:10:51,490
הם צריכים להבין מה באמת נראה כמו העץ,

139
00:10:51,490 --> 00:10:55,450
איך אנחנו בעצם קבלנו את ההחלטות האלה.

140
00:10:55,450 --> 00:10:59,100
>> כאן פשוט עשו דוגמאות המבוססות על הספירה בפועל,

141
00:10:59,100 --> 00:11:01,550
אבל לפעמים אתה יכול להיות גם עץ האפמן

142
00:11:01,550 --> 00:11:05,760
בהתבסס על התדירות שבה מופיעות אותיות, וזה אותו התהליך המדויק.

143
00:11:05,760 --> 00:11:09,090
כאן אני מביע אותה במונחים של אחוז או שברים,

144
00:11:09,090 --> 00:11:11,290
וכן כאן בדיוק את אותו דבר.

145
00:11:11,290 --> 00:11:15,300
אני מוצא את 2 נמוך ביותר, תסכם אותם, 2 הבאים הנמוכים, תסכמו אותם,

146
00:11:15,300 --> 00:11:19,390
עד שיש לי עץ מלא.

147
00:11:19,390 --> 00:11:23,610
למרות שאנחנו יכולים לעשות את זה כך או כך, כאשר יש לנו עסק עם אחוזים,

148
00:11:23,610 --> 00:11:27,760
זה אומר שאנחנו מחלקים דברים והתמודדות עם נקודות עשרוניות או לייתר דיוק צף

149
00:11:27,760 --> 00:11:30,900
אם אנחנו חושבים על מבני נתונים של ראש.

150
00:11:30,900 --> 00:11:32,540
מה אנחנו יודעים על צף?

151
00:11:32,540 --> 00:11:35,180
מה בעיה נפוצה כאשר יש לנו עסק עם מצופים?

152
00:11:35,180 --> 00:11:38,600
[תלמיד] חשבון לא מדויק. >> כן. חוסר דיוק.

153
00:11:38,600 --> 00:11:43,760
בגלל חוסר דיוק נקודה צפה, לpset זה כך שאנו מוודאים

154
00:11:43,760 --> 00:11:49,450
כי אנחנו לא לאבד את כל ערכים, אז אנחנו למעשה הולכים להיות התמודדות עם הספירה.

155
00:11:49,450 --> 00:11:54,880
אז אם הייתם חושב על צומת האפמן, אם אתה מסתכל אחורה למבנה כאן,

156
00:11:54,880 --> 00:12:01,740
אם אתה מסתכל בירוקים יש תדר הקשור אליו

157
00:12:01,740 --> 00:12:08,760
כמו גם שהוא מצביע לצומת לשמאלו, כמו גם צומת לזכותה.

158
00:12:08,760 --> 00:12:13,970
ולאחר מכן את אלה האדומים יש גם דמות שקשורה אליהן.

159
00:12:13,970 --> 00:12:18,900
אנחנו לא הולכים לעשות פרחים נפרדים להורים ואז הבלוטות הסופיות,

160
00:12:18,900 --> 00:12:23,680
בו אנו מתייחסים אליו כעלים, אלא אלה יהיו רק צריכים ערכי NULL.

161
00:12:23,680 --> 00:12:31,050
לכל צומת שנהיה לנו אופי, שסמל שמייצגת צומת,

162
00:12:31,050 --> 00:12:40,490
אז תדירות כמו גם מצביע לילד השמאלי שלו, כמו גם זכותה הילד.

163
00:12:40,490 --> 00:12:45,680
העלים, שהם בתחתית, היה צריכים גם מצביעי צומת

164
00:12:45,680 --> 00:12:49,550
לשמאלם ומימינם, אבל מכיוון שערכים אלה אינם מצביעים על בלוטות בפועל,

165
00:12:49,550 --> 00:12:53,970
מה הערך שלהם יהיה? >> [תלמיד] NULL. NULL. >> בדיוק.

166
00:12:53,970 --> 00:12:58,430
הנה דוגמה לאופן שעשוי לייצג את התדירות בצפים,

167
00:12:58,430 --> 00:13:02,130
אבל אנחנו הולכים להיות התמודדות עימו עם שלמים,

168
00:13:02,130 --> 00:13:06,780
אז כל מה שעשיתי הוא לשנות את סוג הנתונים שיש.

169
00:13:06,780 --> 00:13:09,700
>> בואו נלך על קצת יותר מדוגמה מורכבת.

170
00:13:09,700 --> 00:13:13,360
אבל עכשיו שעשינו את אלה פשוטים, זה רק את אותו התהליך.

171
00:13:13,360 --> 00:13:20,290
אתה מוצא את 2 תדרים הנמוכים, לסכם את התדרים

172
00:13:20,290 --> 00:13:22,450
וזה התדר החדש של צומת אביך,

173
00:13:22,450 --> 00:13:29,310
אשר לאחר מכן מצביע לשמאלו עם 0 סניף והנכון עם הסניף 1.

174
00:13:29,310 --> 00:13:34,200
אם יש לנו את המחרוזת "זה cs50," אז אנחנו לספור כמה פעמים מוזכרים T,

175
00:13:34,200 --> 00:13:38,420
ח ציין, אני, ס, צ, 5, 0.

176
00:13:38,420 --> 00:13:42,010
אז מה שעשיתי כאן הוא עם הבלוטות האדומות אני רק ניטעתי,

177
00:13:42,010 --> 00:13:48,530
אני אמרתי שאני הולך לעשות בתווים אלה סופו של דבר בתחתית העץ שלי.

178
00:13:48,530 --> 00:13:51,740
מי הולך להיות כל העלים.

179
00:13:51,740 --> 00:13:58,200
אז מה שעשיתי הוא שמיינתי אותם לפי תדירות בסדר עולה,

180
00:13:58,200 --> 00:14:02,950
וזה בעצם אופן שבו קוד pset עושה את זה

181
00:14:02,950 --> 00:14:07,550
הוא הוא ממיין אותו על ידי תדר ואז לפי סדר אלפביתי.

182
00:14:07,550 --> 00:14:13,870
אז יש לו את המספרים ראשונים ולאחר מכן לפי סדר אלפביתי של התדר.

183
00:14:13,870 --> 00:14:18,520
ואז מה הייתי עושה הוא הייתי מוצא 2 הנמוך ביותר. זה 0 ו 5.

184
00:14:18,520 --> 00:14:22,390
אני היית מסכם אותם, וזה 2. ואז הייתי ממשיך, למצוא 2 הבאים הנמוך יותר.

185
00:14:22,390 --> 00:14:26,100
אלה הם 1s 2, ולאחר מכן אלו הפכו 2 גם כן.

186
00:14:26,100 --> 00:14:31,570
עכשיו אני יודע שהשלב הבא שלי הולך להיות שהצטרף המספר הנמוך ביותר,

187
00:14:31,570 --> 00:14:41,380
שהוא T, 1, ולאחר מכן בחירה באחת מהבלוטות שיש 2 כתדר.

188
00:14:41,380 --> 00:14:44,560
אז הנה יש לנו 3 אפשרויות.

189
00:14:44,560 --> 00:14:47,980
מה שאני הולך לעשות לשקופית רק בראייתו לארגן מחדש אותם בשבילך

190
00:14:47,980 --> 00:14:51,790
כך שאתה יכול לראות איך אני בונה אותו.

191
00:14:51,790 --> 00:14:59,040
מה הקוד וקוד ההפצה שלך הולך לעשות יהיה להצטרף 1 T

192
00:14:59,040 --> 00:15:01,410
בצומת 0 ו 5.

193
00:15:01,410 --> 00:15:05,060
אז שסכומים עד 3, ולאחר מכן אנו ממשיכים בתהליך.

194
00:15:05,060 --> 00:15:08,660
2 ו 2 עכשיו הם הנמוכים ביותר, אז אלה הסכום עד 4.

195
00:15:08,660 --> 00:15:12,560
כולם לאחר כל כך הרבה? אוקיי.

196
00:15:12,560 --> 00:15:16,410
ואז אחרי שיש לנו 3 ו 3 שיש להוסיף עד,

197
00:15:16,410 --> 00:15:21,650
אז שוב אני רק מיתוג זה, כך שאתה יכול לראות חזותי, כך שהוא לא מקבל יותר מדי מבולגן.

198
00:15:21,650 --> 00:15:25,740
אז יש לנו 6, ולאחר מכן הצעד הסופי שלנו הוא שעכשיו יש לנו רק 2 צמתים

199
00:15:25,740 --> 00:15:30,440
נסכם אלה כדי להפוך את השורש של העץ שלנו, שהוא 10.

200
00:15:30,440 --> 00:15:34,100
והמספר 10 הגיוני כי כל צומת מיוצג,

201
00:15:34,100 --> 00:15:40,750
ערכם, מספר התדר שלהם, היה כמה פעמים הם הופיעו במחרוזת,

202
00:15:40,750 --> 00:15:46,350
ולאחר מכן יש לנו 5 תווים במחרוזת שלנו, כך שזה הגיוני.

203
00:15:48,060 --> 00:15:52,320
אם אנחנו מסתכלים על איך הייתי לקודד אותו ממש,

204
00:15:52,320 --> 00:15:56,580
כצפוי, אני והים, המופיע בתדירות הגבוהה ביותר

205
00:15:56,580 --> 00:16:01,350
מיוצגים על ידי המספר הנמוך ביותר של ביטים.

206
00:16:03,660 --> 00:16:05,660
>> היזהר כאן.

207
00:16:05,660 --> 00:16:09,780
בעצי האפמן המקרה ממש חשוב.

208
00:16:09,780 --> 00:16:13,670
אותיות רישיות S הוא שונה משל אותיות קטנות.

209
00:16:13,670 --> 00:16:21,260
אם היו לנו "זה CS50" עם אותיות גדולות, ולאחר מכן של האותיות הקטנות היה מופיע רק פעמים,

210
00:16:21,260 --> 00:16:27,120
יהיה צומת עם 2 כערכו, ולאחר מכן אותיות רישיות S תהיינה רק פעם אחת.

211
00:16:27,120 --> 00:16:33,440
אז העץ שלך ישנה את מבנים, כי אתה באמת צריך עלה נוסף כאן.

212
00:16:33,440 --> 00:16:36,900
אבל הסכום עדיין יהיה 10.

213
00:16:36,900 --> 00:16:39,570
זה מה שאנחנו באמת הולכים להתקשר אל הבדיקה,

214
00:16:39,570 --> 00:16:44,060
בנוסף לכל סעיפים.

215
00:16:46,010 --> 00:16:50,990
>> עכשיו שאנחנו כבר מכוסים עצי האפמן, אנחנו יכולים לצלול לתוך פאף Huff'n, pset.

216
00:16:50,990 --> 00:16:52,900
אנחנו עומדים להתחיל עם קטע של שאלות,

217
00:16:52,900 --> 00:16:57,990
וזה הולך להביא לך רגיל עם עצים בינאריים וכיצד פועל סביב זה:

218
00:16:57,990 --> 00:17:03,230
בלוטות לציור, יצירת struct typedef שלך לצומת,

219
00:17:03,230 --> 00:17:07,230
ולראות איך אתה יכול להכניס לתוך עץ בינארי, שסדר,

220
00:17:07,230 --> 00:17:09,050
חוצה אותו, ודברים כאלה.

221
00:17:09,050 --> 00:17:14,560
ידע שבהחלט הולך לעזור לך כאשר אתה צולל לתוך חלק פאף Huff'n

222
00:17:14,560 --> 00:17:17,089
של pset.

223
00:17:19,150 --> 00:17:26,329
במהדורה הסטנדרטית של pset, המשימה שלך היא ליישם פאף,

224
00:17:26,329 --> 00:17:30,240
ובגרסת האקר המשימה שלך היא ליישם הף.

225
00:17:30,240 --> 00:17:38,490
מה הף עושה זה לוקח טקסט ואז זה מתרגם אותו ל0s ו 1s,

226
00:17:38,490 --> 00:17:41,990
לכן התהליך שעשינו לעיל שבו אנו סופרים את התדרים

227
00:17:41,990 --> 00:17:50,970
ואז עשה את העץ ואז אמר, "איך אני מקבל T?"

228
00:17:50,970 --> 00:17:54,840
T מיוצג על ידי 100, דברים כאלה,

229
00:17:54,840 --> 00:17:58,860
ואז הף ייקח את הטקסט ואז הפלט שבינארי.

230
00:17:58,860 --> 00:18:04,920
אבל גם בגלל שאנחנו יודעים שאנחנו רוצים לאפשר לנמען ההודעה שלנו

231
00:18:04,920 --> 00:18:11,790
כדי לשחזר את אותו עץ בדיוק, זה כולל גם מידע על ספירת השכיחות.

232
00:18:11,790 --> 00:18:17,980
אז עם פאף אנו מקבלים קובץ בינארי של 0s ו 1s

233
00:18:17,980 --> 00:18:21,740
ונתן גם מידע על התדרים.

234
00:18:21,740 --> 00:18:26,740
אנו מתרגמים את כל אלו שיחזרו 0s ו 1s להודעה המקורית שהייתה,

235
00:18:26,740 --> 00:18:29,350
לכן אנחנו decompressing ש.

236
00:18:29,350 --> 00:18:36,450
אם אתה עושה את המהדורה הרגילה, אתה לא צריך ליישם הף,

237
00:18:36,450 --> 00:18:39,290
ואז אתה יכול פשוט להשתמש ביישום צוות של הף.

238
00:18:39,290 --> 00:18:42,080
יש הוראות במפרט על איך לעשות את זה.

239
00:18:42,080 --> 00:18:48,780
אתה יכול להפעיל את יישום צוות של הף על קובץ טקסט מסוים

240
00:18:48,780 --> 00:18:53,270
ולאחר מכן להשתמש בפלט שכקלט לפאף.

241
00:18:53,270 --> 00:18:59,330
>> כפי שציינתי קודם, יש לנו הרבה קוד חלוקה לזה.

242
00:18:59,330 --> 00:19:01,810
אני מתכוון להתחיל ללכת דרכו.

243
00:19:01,810 --> 00:19:04,400
אני הולך לבלות את רוב הזמן ב. קבצי h

244
00:19:04,400 --> 00:19:07,660
כי ב. את קבצי C, כי יש לנו. h

245
00:19:07,660 --> 00:19:11,650
ושמספק לנו את אבות הטיפוס של הפונקציות,

246
00:19:11,650 --> 00:19:15,520
אנחנו לא צריכים באופן מלא כדי להבין בדיוק -

247
00:19:15,520 --> 00:19:20,280
אם אתה לא מבין מה קורה ב. את קבצי C, אז אל תדאגו יותר מדי,

248
00:19:20,280 --> 00:19:23,600
אבל בהחלט תנסה להעיף מבט, כי זה עלול לתת כמה רמזים

249
00:19:23,600 --> 00:19:29,220
וזה שימושי להתרגל לקריאת הקוד של אנשים אחרים.

250
00:19:38,940 --> 00:19:48,270
>> כאשר מסתכלים על huffile.h, בהערותיו מצהירות שכבת ההפשטה לקבצי האפמן מקודדים.

251
00:19:48,270 --> 00:20:01,660
אם אנחנו הולכים למטה, אנחנו רואים שיש מקסימום של 256 סמלים שאולי צריך קודים ל.

252
00:20:01,660 --> 00:20:05,480
זה כולל את כל האותיות אלף - הגדולות וקטנות -

253
00:20:05,480 --> 00:20:08,250
ואז סמלים ומספרים, וכו '

254
00:20:08,250 --> 00:20:11,930
אז כאן יש לנו מספר קסם זיהוי קובץ האפמן מקודד.

255
00:20:11,930 --> 00:20:15,890
בתוך קוד האפמן שהם הולכים להיות מספר קסם מסוים

256
00:20:15,890 --> 00:20:18,560
קשור עם הכותרת.

257
00:20:18,560 --> 00:20:21,110
זה אולי נראה כמו סתם מספר קסם אקראי,

258
00:20:21,110 --> 00:20:27,160
אבל אם אתה באמת לתרגם אותה לASCII, אז זה בעצם מפרט את הף.

259
00:20:27,160 --> 00:20:34,290
כאן יש לנו struct לקובץ האפמן בקידוד.

260
00:20:34,290 --> 00:20:39,670
יש כל המאפיינים הללו קשורים קובץ הף.

261
00:20:39,670 --> 00:20:47,080
אז כאן יש לנו את הכותרת לקובץ הף, ולכן אנחנו קוראים לזה Huffeader

262
00:20:47,080 --> 00:20:50,810
במקום להוסיף שעות נוספות בגלל שזה נשמע אותו דבר בכל מקרה.

263
00:20:50,810 --> 00:20:52,720
חמוד.

264
00:20:52,720 --> 00:20:57,790
יש לנו מספר קסם המשויך אליו.

265
00:20:57,790 --> 00:21:09,040
אם זה קובץ הף בפועל, זה הולך להיות המספר למעלה, זה קסם.

266
00:21:09,040 --> 00:21:14,720
ואז זה יהיה מערך.

267
00:21:14,720 --> 00:21:18,750
אז לכל סמל, שבה יש 256,

268
00:21:18,750 --> 00:21:24,760
זה הולך לרשום את כל מה התדירות של הסמלים האלה הן בתוך קובץ הף.

269
00:21:24,760 --> 00:21:28,090
ולבסוף, יש לנו את בדיקה עבור התדרים,

270
00:21:28,090 --> 00:21:32,160
שאמור להיות בסכום של תדרים אלה.

271
00:21:32,160 --> 00:21:36,520
אז זה מה שHuffeader הוא.

272
00:21:36,520 --> 00:21:44,600
אז יש לנו כמה פונקציות שמחזירות את הקטע הבא בקובץ הף

273
00:21:44,600 --> 00:21:52,580
כמו גם כותב קצת לקובץ הף, ואז זה פונקציה כאן, hfclose,

274
00:21:52,580 --> 00:21:54,650
שבעצם סוגר את קובץ הף.

275
00:21:54,650 --> 00:21:57,290
לפני כן, היינו לנו עסק עם ישר פשוט fclose,

276
00:21:57,290 --> 00:22:01,190
אבל כאשר יש לך קובץ הף, במקום fclosing זה

277
00:22:01,190 --> 00:22:06,080
מה אתה בעצם הולך לעשות הוא hfclose וhfopen.

278
00:22:06,080 --> 00:22:13,220
אלה הם פונקציות ספציפיות לקבצי הף שאנחנו הולכים להיות התמודדות עם.

279
00:22:13,220 --> 00:22:19,230
אז הנה אנחנו קוראים בכותרת ואז לכתוב את הכותרת.

280
00:22:19,230 --> 00:22:25,700
>> רק על ידי קריאה. קובץ h שאנחנו יכולים לקבל סוג של תחושה של מה קובץ הף יכול להיות,

281
00:22:25,700 --> 00:22:32,480
מה מאפיינים יש לו, מבלי להיכנס ממש לתוך huffile.c,

282
00:22:32,480 --> 00:22:36,750
אשר, אם לקפוץ למים, הולך להיות קצת יותר מורכב.

283
00:22:36,750 --> 00:22:41,270
יש לו כל קובץ הקלט / פלט כאן התמודדות עם מצביעים.

284
00:22:41,270 --> 00:22:48,010
כאן אנו רואים שכאשר אנו קוראים hfread, למשל, הוא עדיין מתמודד עם fread.

285
00:22:48,010 --> 00:22:53,050
אנחנו לא להיפטר מהפונקציות הללו לחלוטין, אבל אנחנו שולחים את אלה שטופלו

286
00:22:53,050 --> 00:22:59,760
בתוך קובץ הף במקום לעשות את כל זה בעצמנו.

287
00:22:59,760 --> 00:23:02,300
אתה יכול להרגיש חופשי לסריקה דרך זה אם אתה סקרן

288
00:23:02,300 --> 00:23:08,410
ותלך, ולקלף את השכבה קצת לאחור.

289
00:23:20,650 --> 00:23:24,060
>> הקובץ הבא שאנחנו הולכים להסתכל הוא tree.h.

290
00:23:24,060 --> 00:23:30,210
לפני בWalkthrough מחליק אמרנו שאנחנו מצפים האפמן צומת

291
00:23:30,210 --> 00:23:32,960
ועשינו צומת struct typedef.

292
00:23:32,960 --> 00:23:38,360
אנו מצפים שנהיה לו סמל, תדירות, ואז 2 כוכבי צומת.

293
00:23:38,360 --> 00:23:41,870
במקרה זה מה שאנחנו עושים הוא שזה בעצם אותו הדבר

294
00:23:41,870 --> 00:23:46,880
אלא שבמקום צומת אנחנו הולכים לקרוא להם עצים.

295
00:23:48,790 --> 00:23:56,760
יש לנו פונקציה שכאשר אתה קורא להפוך עץ זה מחזיר אותך מצביע עץ.

296
00:23:56,760 --> 00:24:03,450
בחזרה למאית, כשאתה היה עושה צומת חדש

297
00:24:03,450 --> 00:24:11,410
אתה אמרת צומת * מילה חדשה = malloc (sizeof) ודברים כאלה.

298
00:24:11,410 --> 00:24:17,510
בעיקרון, mktree הולך להיות התמודדות עם זה בשבילך.

299
00:24:17,510 --> 00:24:20,990
בדומה לכך, כאשר ברצונך להסיר את עץ,

300
00:24:20,990 --> 00:24:24,810
כך שבעצם הוא משחרר את העץ כשתסיים עם זה,

301
00:24:24,810 --> 00:24:33,790
במקום לקרוא במפורש חופשי על זה, אתם למעשה רק הולכים להשתמש בפונקצית rmtree

302
00:24:33,790 --> 00:24:40,360
שבו אתה עובר במצביע כדי שעץ ולאחר מכן tree.c יטפל בזה בשבילך.

303
00:24:40,360 --> 00:24:42,490
>> אנו מצפים לtree.c.

304
00:24:42,490 --> 00:24:47,240
אנו מצפים את אותן פונקציות חוץ מאשר לראות את היישום גם כן.

305
00:24:47,240 --> 00:24:57,720
כפי שציפינו, כאשר אתה קורא את זה mktree mallocs גודלו של עץ למצביע,

306
00:24:57,720 --> 00:25:03,190
מאתחל את כל הערכים לערך NULL, כך 0s או ערכי null,

307
00:25:03,190 --> 00:25:08,280
ולאחר מכן מחזיר את המצביע לעץ הזה שיש לך רק malloc'd אליך.

308
00:25:08,280 --> 00:25:13,340
הנה כאשר אתה קורא להסיר עץ זה גורם תחילה ודא כי אתה לא משחרר כפול.

309
00:25:13,340 --> 00:25:18,320
היא מוודא כי למעשה יש לכם עץ שברצונך להסיר.

310
00:25:18,320 --> 00:25:23,330
הנה כי עץ כולל גם את ילדיה,

311
00:25:23,330 --> 00:25:29,560
מה זה עושה זה רקורסיבי קורא להסיר עץ בצומת השמאלית של העץ

312
00:25:29,560 --> 00:25:31,650
כמו גם את הצומת הנכונה.

313
00:25:31,650 --> 00:25:37,790
לפני שהוא משחרר את ההורה, הוא צריך לשחרר את הילדים גם כן.

314
00:25:37,790 --> 00:25:42,770
ההורה הוא גם החלפה עם שורש.

315
00:25:42,770 --> 00:25:46,500
ההורה הראשון אי פעם, כל כך כמו---סב הסב גדול גדול

316
00:25:46,500 --> 00:25:52,130
או עץ סבתא, ראשון שאנחנו צריכים לשחרר את הרמות ראשונות.

317
00:25:52,130 --> 00:25:58,490
אז לעבור לתחתית, ללא אלה, ולאחר מכן יחזור למעלה, ללא אלה, וכו '

318
00:26:00,400 --> 00:26:02,210
אז זה עץ.

319
00:26:02,210 --> 00:26:04,240
>> עכשיו אנחנו מסתכלים על יער.

320
00:26:04,240 --> 00:26:09,860
יער שבו אתה מניח את כל עצי האפמן.

321
00:26:09,860 --> 00:26:12,910
זה אומר שאנחנו הולכים יש משהו שנקרא עלילה

322
00:26:12,910 --> 00:26:22,320
המכיל מצביע לעץ, כמו גם מצביע לעלילה נקראת הבא.

323
00:26:22,320 --> 00:26:28,480
מה עושה מבנה מסוג זה נראה לך?

324
00:26:29,870 --> 00:26:32,490
זה סוג של אומר שזה שם.

325
00:26:34,640 --> 00:26:36,700
בדיוק כאן.

326
00:26:37,340 --> 00:26:39,170
רשימה מקושרת.

327
00:26:39,170 --> 00:26:44,590
אנו רואים שכאשר יש לנו עלילה זה כמו רשימה מקושרת של עלילות.

328
00:26:44,590 --> 00:26:53,020
יער מוגדר כרשימה מקושרת של מגרשים,

329
00:26:53,020 --> 00:26:58,100
וכך המבנה של יער הוא שאנחנו פשוט הולכים להיות מצביע לחלקה הראשונה שלנו

330
00:26:58,100 --> 00:27:02,740
ועלילה שיש עץ בתוכה או יותר נכון מצביעה על עץ

331
00:27:02,740 --> 00:27:06,190
ולאחר מכן מצביע על המזימה הבאה, וכך הלאה וכך הלאה.

332
00:27:06,190 --> 00:27:11,100
כדי להפוך את יער שאנו מכנים mkforest.

333
00:27:11,100 --> 00:27:14,930
אז יש לנו כמה פונקציות די שימושיות כאן.

334
00:27:14,930 --> 00:27:23,240
יש לנו לבחור בו אתה עובר ביער ולאחר מכן ערך ההחזרה הוא * עץ,

335
00:27:23,240 --> 00:27:25,210
מצביע לעץ.

336
00:27:25,210 --> 00:27:29,370
מה תעשה בחירה הוא שזה ילך אל היער שאתה מצביע על

337
00:27:29,370 --> 00:27:35,240
לאחר מכן להסיר את עץ בתדירות הנמוכה ביותר מזה יער

338
00:27:35,240 --> 00:27:38,330
ולאחר מכן לתת לך מצביע לעץ הזה.

339
00:27:38,330 --> 00:27:43,030
ברגע שאתה קורא לבחור, העץ לא קיים ביער יותר,

340
00:27:43,030 --> 00:27:48,550
אבל ערך ההחזרה הוא הסמן לעץ.

341
00:27:48,550 --> 00:27:50,730
אז יש לך מפעל.

342
00:27:50,730 --> 00:27:57,420
בתנאי שאתה עובר במצביע לעץ שיש תדר שאינו-0,

343
00:27:57,420 --> 00:28:04,040
מה יעשה הוא צמח זה ייקח יער, לקחת את העץ, וצמח שבתוך עץ של היער.

344
00:28:04,040 --> 00:28:06,370
כאן יש לנו rmforest.

345
00:28:06,370 --> 00:28:11,480
דומה כדי להסיר את העץ, שבעצם שחרר את כל העצים שלנו עבורנו,

346
00:28:11,480 --> 00:28:16,600
להסיר יער חינם הכל הכלול באותו יער.

347
00:28:16,600 --> 00:28:24,890
>> אם תסתכלו לתוך forest.c, אנו מצפים לראות את פקודת rmtree לפחות 1 לשם,

348
00:28:24,890 --> 00:28:30,090
כי כדי לפנות זיכרון ביער אם יש עצי יער בזה,

349
00:28:30,090 --> 00:28:32,930
אז סופו של דבר אתה הולך לעשות כדי להסיר את העצים האלה יותר מדי.

350
00:28:32,930 --> 00:28:41,020
אם נסתכל לתוך forest.c, יש לנו mkforest, שכפי שאנו מצפים.

351
00:28:41,020 --> 00:28:42,890
אנו malloc דברים.

352
00:28:42,890 --> 00:28:51,740
נאתחל את העלילה הראשונה ביער כNULL משום שהוא ריק מלכתחילה,

353
00:28:51,740 --> 00:29:05,940
אז אנחנו רואים את בחירה, שמחזירה את העץ עם המשקל הנמוך ביותר, תדר הנמוך ביותר,

354
00:29:05,940 --> 00:29:13,560
ולאחר מכן נפטר שמצומת מסוימת שמצביע על העץ הזה והבא,

355
00:29:13,560 --> 00:29:16,760
אז זה לוקח כי מתוך הרשימה המקושרת של היער.

356
00:29:16,760 --> 00:29:24,510
והנה יש לנו מפעל, אשר מוסיף עץ לרשימה המקושרת.

357
00:29:24,510 --> 00:29:29,960
מה יער עושה זה שומר את זה יפה מסודר עבורנו.

358
00:29:29,960 --> 00:29:37,910
ולבסוף, יש לנו rmforest, וכצפוי, יש לנו מכונה במקום rmtree.

359
00:29:46,650 --> 00:29:55,440
>> כאשר מסתכלים על קוד ההפצה עד כה, huffile.c היה כנראה בהרבה הכי הקשה להבין,

360
00:29:55,440 --> 00:29:59,990
בעוד שאר קבצים עצמם היו די פשוט לעקוב אחריו.

361
00:29:59,990 --> 00:30:03,090
עם הידע של מצביעים ורשימות מקושרות וכאלה שלנו,

362
00:30:03,090 --> 00:30:04,860
היינו מסוגל לעקוב די טוב.

363
00:30:04,860 --> 00:30:10,500
אבל כל מה שאנחנו צריכים באמת לוודא כי אנו מבינים היטב הוא את הקבצים. H

364
00:30:10,500 --> 00:30:15,840
בגלל שאתה צריך להיות קורא פונקציות אלה, העוסק בערכים לחזור האלה,

365
00:30:15,840 --> 00:30:20,590
כדי לוודא שאתה מבין לגמרי איזו פעולה הוא הולך להתבצע

366
00:30:20,590 --> 00:30:24,290
כל פעם שאתה קורא על אחת מהפעולות אלה.

367
00:30:24,290 --> 00:30:33,020
אבל בעצם ההבנה הפנימית שלו היא לא ממש נחוצה, כי יש לנו אלה. קבצי h.

368
00:30:35,170 --> 00:30:39,490
יש לנו עוד 2 קבצים שנותרו בקוד ההפצה שלנו.

369
00:30:39,490 --> 00:30:41,640
>> הבה יתבונן במזבלה.

370
00:30:41,640 --> 00:30:47,230
תזרוק אותו מההערה כאן לוקח קובץ דחוס האפמן

371
00:30:47,230 --> 00:30:55,580
ואז מתרגם ומזבלות כל התוכן שלה החוצה.

372
00:31:01,010 --> 00:31:04,260
כאן אנו רואים שזה קורא hfopen.

373
00:31:04,260 --> 00:31:10,770
זה סוג של שיקוף לקובץ * קלט = fopen,

374
00:31:10,770 --> 00:31:13,500
ואז אתה עובר במידע.

375
00:31:13,500 --> 00:31:18,240
זה כמעט זהה רק שבמקום * קובץ שאתה עובר בHuffile;

376
00:31:18,240 --> 00:31:22,030
במקום fopen אתה עובר בhfopen.

377
00:31:22,030 --> 00:31:29,280
כאן אנו קוראים בכותרת ראשונה, שהוא די דומה לאופן בו אנו קוראים בכותרת

378
00:31:29,280 --> 00:31:33,580
לקובץ מפה סיבי.

379
00:31:33,580 --> 00:31:38,000
מה שאנחנו עושים כאן זה לבדוק אם פרטי הכותרת

380
00:31:38,000 --> 00:31:44,330
מכיל את מספר הקסם הנכון שמצביע על כך שזה קובץ הף בפועל,

381
00:31:44,330 --> 00:31:53,610
אז כל הבדיקות האלה כדי לוודא שהקובץ שפתוח הוא קובץ נשף בפועל או לא.

382
00:31:53,610 --> 00:32:05,330
מה שזה עושה זה מוציא את התדרים של כל הסמלים שאנחנו יכולים לראות

383
00:32:05,330 --> 00:32:09,790
בתוך הטרמינל לתוך טבלה גרפית.

384
00:32:09,790 --> 00:32:15,240
חלק זה הולך להיות שימושי.

385
00:32:15,240 --> 00:32:24,680
יש לו קצת וקורא לאט לאט לתוך סיבי משתנה ולאחר מכן מדפיס אותו.

386
00:32:28,220 --> 00:32:35,430
אז אם אני היה קורא על hth.bin מזבלה, שהוא התוצאה של מתנשם קובץ

387
00:32:35,430 --> 00:32:39,490
באמצעות פתרון צוות, הייתי מקבל את זה.

388
00:32:39,490 --> 00:32:46,000
זה פלט כל הדמויות האלה ואז לשים את התדר שבו הם מופיעים.

389
00:32:46,000 --> 00:32:51,180
אם נסתכל, רובם 0s פרט לזה: H, המופיע פעמים,

390
00:32:51,180 --> 00:32:54,820
ואז T, שמופיע פעם אחת.

391
00:32:54,820 --> 00:33:07,860
והנה יש לנו את המסר האמיתי ב0s ו 1s.

392
00:33:07,860 --> 00:33:15,450
אם נסתכל על hth.txt, שהוא ככל הנראה ההודעה המקורית שנשפה,

393
00:33:15,450 --> 00:33:22,490
אנו מצפים לראות כמה Hs וTs לשם.

394
00:33:22,490 --> 00:33:28,720
באופן ספציפי, אנחנו מצפים לראות רק 1 T ו 2 HS.

395
00:33:32,510 --> 00:33:37,440
הנה אנחנו בhth.txt. זה אכן יש HTH.

396
00:33:37,440 --> 00:33:41,270
כלול בשם, למרות שאנחנו לא יכולים לראות אותו, היא דמות שורה חדשה.

397
00:33:41,270 --> 00:33:53,190
Hth.bin קובץ הף גם קידוד תו השורה החדש גם כן.

398
00:33:55,680 --> 00:34:01,330
הנה כי אנחנו יודעים שהצו HTH שורה חדשה ולאחר מכן,

399
00:34:01,330 --> 00:34:07,340
אנו יכולים לראות כי כנראה H מיוצג רק על ידי אחת 1

400
00:34:07,340 --> 00:34:17,120
ואז T הוא כנראה 01 ולאחר מכן H הבא הוא 1, כמו גם

401
00:34:17,120 --> 00:34:21,139
ואז יש לנו שורה חדשה סומנה בשני 0s.

402
00:34:22,420 --> 00:34:24,280
מגניב.

403
00:34:26,530 --> 00:34:31,600
>> ולבסוף, מכיוון שאנחנו עוסקים במספר. ג ו. קבצי h,

404
00:34:31,600 --> 00:34:36,350
אנחנו הולכים להיות טיעון מורכב למדי למהדר,

405
00:34:36,350 --> 00:34:40,460
אז הנה יש לנו Makefile שעושה מזבלה בשבילך.

406
00:34:40,460 --> 00:34:47,070
אבל בעצם, יש לך ללכת על מה שהופך קובץ puff.c שלך.

407
00:34:47,070 --> 00:34:54,330
Makefile למעשה אינו עוסק בביצוע puff.c בשבילך.

408
00:34:54,330 --> 00:34:59,310
אנחנו עוזבים כי עד לערוך את Makefile.

409
00:34:59,310 --> 00:35:05,930
כאשר אתה נכנסת לפקודה כמו כל לעשות, למשל, זה יעשה את כולם בשבילך.

410
00:35:05,930 --> 00:35:10,760
תרגיש חופשי להסתכל על הדוגמות של Makefile מpset העבר

411
00:35:10,760 --> 00:35:17,400
כמו גם נוסע מזה כדי לראות איך אתה יכול להיות מסוגל לעשות את קובץ פאף

412
00:35:17,400 --> 00:35:20,260
על ידי עריכת Makefile זה.

413
00:35:20,260 --> 00:35:22,730
זה בערך אותו לקוד ההפצה שלנו.

414
00:35:22,730 --> 00:35:28,380
>> ברגע שאנחנו מקבלים דרך את זה, אז הנה רק תזכורת נוספת

415
00:35:28,380 --> 00:35:30,980
של איך שאנחנו הולכים להיות התמודדות עם בלוטות האפמן.

416
00:35:30,980 --> 00:35:35,400
אנחנו לא הולכים להתקשר אליהם צומת יותר; אנחנו הולכים להתקשר אליהם עצים

417
00:35:35,400 --> 00:35:39,260
לאן אנחנו הולכים לייצג את סמלם עם char,

418
00:35:39,260 --> 00:35:43,340
התדר שלהם, את מספר המופעים, עם שלם.

419
00:35:43,340 --> 00:35:47,370
אנחנו משתמשים בזה כי זה יותר מדויק מאשר ציפה.

420
00:35:47,370 --> 00:35:52,980
ואז יש לנו מצביע נוסף לילד משמאל, כמו גם את הילד הנכון.

421
00:35:52,980 --> 00:35:59,630
יער, כפי שראינו, הוא פשוט רשימה מקושרת של עצים.

422
00:35:59,630 --> 00:36:04,670
סופו של דבר, כאשר אנו בונים את קובץ הף,

423
00:36:04,670 --> 00:36:07,580
אנחנו רוצים היער שלנו להכיל רק עץ 1 -

424
00:36:07,580 --> 00:36:12,420
עץ 1, 1 שורש עם ילדים מרובים.

425
00:36:12,420 --> 00:36:20,840
מוקדם יותר, כאשר אנחנו רק עושים עצי האפמן,

426
00:36:20,840 --> 00:36:25,360
יצא לדרכנו על ידי הצבה של כל צומת על המסך שלנו

427
00:36:25,360 --> 00:36:27,790
ואומר שאנחנו הולכים להיות לי צומת אלה,

428
00:36:27,790 --> 00:36:32,920
סופו של דבר הם הולכים להיות העלים, וזה הסמל שלהם, זה התדר שלהם.

429
00:36:32,920 --> 00:36:42,070
ביער שלנו אם אנחנו צריכים רק 3 אותיות, זה יער של 3 עצים.

430
00:36:42,070 --> 00:36:45,150
ואז כמו שאנחנו הולכים על, כאשר הוספנו את ההורה הראשון,

431
00:36:45,150 --> 00:36:48,080
עשינו יער של עצים 2.

432
00:36:48,080 --> 00:36:54,930
הסרנו 2 הילדים האלה מהיער שלנו ולאחר מכן החלפנו אותו בצומת אב

433
00:36:54,930 --> 00:36:58,820
שהיו 2 צומת אלה כילדים.

434
00:36:58,820 --> 00:37:05,600
ולבסוף, בשלב האחרון שלנו עם קבלת הדוגמא שלנו עם כ, ארוחת הבוקר, וCs

435
00:37:05,600 --> 00:37:08,030
יהיה להפוך את ההורה הסופי,

436
00:37:08,030 --> 00:37:13,190
וכן אז שיביא את הסך הכולל שלנו של עצים ביער ל1.

437
00:37:13,190 --> 00:37:18,140
האם כולם רואים איך אתה מתחיל לצאת עם עצים רבים ביער

438
00:37:18,140 --> 00:37:22,520
וסופו של דבר עם 1? אוקיי. מגניב.

439
00:37:25,530 --> 00:37:28,110
>> מה אנחנו צריכים לעשות לפאף?

440
00:37:28,110 --> 00:37:37,110
מה שאנחנו צריכים לעשות הוא להבטיח כי, כמו תמיד, הם נותנים לנו את הסוג הנכון של קלט

441
00:37:37,110 --> 00:37:39,090
כך שאנחנו יכולים למעשה להפעיל את התכנית.

442
00:37:39,090 --> 00:37:43,130
במקרה זה הם הולכים לתת לנו אחרי הוויכוח הראשון שלהם שורת פקודה

443
00:37:43,130 --> 00:37:53,440
עוד 2: את הקובץ שאנחנו רוצים לשחרר את לחץ ואת הפלט של קובץ הדחיסה.

444
00:37:53,440 --> 00:38:00,410
אבל ברגע שאנחנו מוודאים שהם עוברים אותנו בכמות הנכונה של ערכים,

445
00:38:00,410 --> 00:38:05,820
אנחנו רוצים להבטיח שהקלט הוא קובץ הף או לא.

446
00:38:05,820 --> 00:38:10,420
ואז ברגע שאנחנו מבטיחים שזה קובץ הף, אז אנחנו רוצים לבנות את העץ שלנו,

447
00:38:10,420 --> 00:38:20,940
לבנות עץ כזה שיתאים לעץ שהאדם ששלח הודעה שנבנה.

448
00:38:20,940 --> 00:38:25,840
ואז אחרי שאנחנו בונים את העץ, אז אנחנו יכולים להתמודד עם 0s ו 1s שהם העבירו ב,

449
00:38:25,840 --> 00:38:29,590
בעקבות אלה יחד העץ שלנו כי זה זהה,

450
00:38:29,590 --> 00:38:33,510
ואז לכתוב את ההודעה שיצאה, לפרש את הקטעים חזרה לתווים.

451
00:38:33,510 --> 00:38:35,880
ואז, בסוף, כי יש לנו עסק עם מצביעים כאן,

452
00:38:35,880 --> 00:38:38,110
אנחנו רוצים לוודא שאין לנו שום דליפות זיכרון

453
00:38:38,110 --> 00:38:41,330
וכל מה שאנחנו חופשיים.

454
00:38:42,820 --> 00:38:46,430
>> הבטחת שימוש נכון היא כובע ישן לנו עד עכשיו.

455
00:38:46,430 --> 00:38:51,980
אנחנו לוקחים בקלט, שהוא הולך להיות השם של הקובץ כדי לנפח,

456
00:38:51,980 --> 00:38:56,010
ואז אנחנו לציין פלט,

457
00:38:56,010 --> 00:39:01,580
כך שמו של הקובץ לפלט התפוח, אשר יהיה קובץ הטקסט.

458
00:39:03,680 --> 00:39:08,820
זה שימוש. ועכשיו אנחנו רוצים להבטיח שהקלט נשף או לא.

459
00:39:08,820 --> 00:39:16,420
במחשבה לאחור, האם יש משהו בקוד ההפצה שעשויה לעזור לנו

460
00:39:16,420 --> 00:39:21,570
עם ההבנה האם קובץ נשף או לא?

461
00:39:21,570 --> 00:39:26,910
היה מידע בhuffile.c על Huffeader.

462
00:39:26,910 --> 00:39:33,430
אנו יודעים כי כל קובץ הף יש Huffeader משויך אליו עם מספר קסם

463
00:39:33,430 --> 00:39:37,240
כמו גם מערך של התדרים לכל סמל

464
00:39:37,240 --> 00:39:39,570
כמו גם בדיקה.

465
00:39:39,570 --> 00:39:43,180
אנחנו יודעים את זה, אבל אנחנו גם לקחנו להציץ בdump.c,

466
00:39:43,180 --> 00:39:49,120
שבו קרא לקובץ הף.

467
00:39:49,120 --> 00:39:53,990
ואז לעשות את זה, זה היה צריך לבדוק אם זה באמת היה או לא התנשף.

468
00:39:53,990 --> 00:40:03,380
אז אולי תוכל להשתמש dump.c כמבנה לpuff.c.

469
00:40:03,380 --> 00:40:12,680
חזור לpset 4 כאשר היו לנו copy.c הקובץ שהועתק במשולשי RGB

470
00:40:12,680 --> 00:40:14,860
ופרשנו כי להאשמות ושינוי גודל,

471
00:40:14,860 --> 00:40:20,390
באופן דומה, מה שאתה יכול לעשות זה פשוט להפעיל את הפקודה כמו cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
ולהשתמש בחלק מהקוד שם.

473
00:40:23,600 --> 00:40:28,210
עם זאת, זה לא הולך להיות פשוט כמו של תהליך

474
00:40:28,210 --> 00:40:33,010
לתרגום dump.c לתוך puff.c,

475
00:40:33,010 --> 00:40:36,160
אבל לפחות זה נותן לך נקודת ההתחלה

476
00:40:36,160 --> 00:40:40,540
כיצד להבטיח שהקלט נשף בפועל או לא

477
00:40:40,540 --> 00:40:43,240
כמו גם כמה דברים אחרים.

478
00:40:45,930 --> 00:40:50,250
יש לנו הבטחתי שימוש נכון והבטיחו כי הקלט התנשף.

479
00:40:50,250 --> 00:40:53,570
בכל פעם שעשינו מה שעשינו בדיקת השגיאות הנכונה שלנו,

480
00:40:53,570 --> 00:41:01,520
כך חזר והפסקת התפקוד אם חלק הכישלון מתרחש, אם יש בעיה.

481
00:41:01,520 --> 00:41:07,170
>> עכשיו מה שאנחנו רוצים לעשות הוא לבנות את העץ עצמו.

482
00:41:08,840 --> 00:41:12,640
אם נסתכל ביער, יש 2 פונקציות עיקריות

483
00:41:12,640 --> 00:41:15,800
שאנחנו הולכים לרוצים להיות מכירים היטב.

484
00:41:15,800 --> 00:41:23,870
יש מפעל הפונקציה בוליאנית שצמחי עץ תדירות הלא-0 בתוך היער שלנו.

485
00:41:23,870 --> 00:41:29,250
ואז יש לך לעבור במצביע ליער ומצביע לעץ.

486
00:41:32,530 --> 00:41:40,340
שאלה מהירה: כמה יערות יש לך כאשר אתה בונה עץ האפמן?

487
00:41:44,210 --> 00:41:46,650
היער שלנו הוא כמו הבד שלנו, נכון?

488
00:41:46,650 --> 00:41:50,800
אז אנחנו רק נצטרך יער 1, אבל אנחנו הולכים ליש עצים מרובים.

489
00:41:50,800 --> 00:41:57,590
אז לפני שאתה קורא למפעל, אתה כנראה הולך לרוצה לעשות יערך.

490
00:41:57,590 --> 00:42:04,430
יש פקודה שלאם אתה מסתכל לתוך forest.h על איך אתה יכול להפוך את יער.

491
00:42:04,430 --> 00:42:09,270
אתה יכול לטוע עץ. אנחנו יודעים איך לעשות את זה.

492
00:42:09,270 --> 00:42:11,590
ואז אתה יכול גם להרים עץ מהיער,

493
00:42:11,590 --> 00:42:17,540
הסרת עץ עם המשקל הנמוך ביותר ונותן לך את המצביע לזה.

494
00:42:17,540 --> 00:42:23,090
מחשבה לאחור לכאשר אנחנו עושים את עצמנו דוגמאות,

495
00:42:23,090 --> 00:42:27,980
כאשר אנחנו מציירים אותו, אנחנו פשוט רק הוספנו את הקישורים.

496
00:42:27,980 --> 00:42:31,680
אבל כאן לא רק הוספת הקישורים,

497
00:42:31,680 --> 00:42:40,630
חושב על זה יותר כמו שאתה מסיר 2 מתוך צומת אלה ולאחר מכן החלפת אותו באחד אחר.

498
00:42:40,630 --> 00:42:44,200
כדי להביע את זה במונחים של בחירה ושתילה,

499
00:42:44,200 --> 00:42:48,840
אתה מתחיל לתפוס 2 עצים ולאחר מכן נטיעת עץ אחר

500
00:42:48,840 --> 00:42:54,060
כי יש 2 העצים האלה שהיו צריכים לאסוף את הילדים.

501
00:42:57,950 --> 00:43:05,280
כדי לבנות את העץ של האפמן, אתה יכול לקרוא את הסמלים והתדרים במטרה

502
00:43:05,280 --> 00:43:10,790
בגלל Huffeader נותן לך את זה,

503
00:43:10,790 --> 00:43:14,250
נותן לך מערך של התדרים.

504
00:43:14,250 --> 00:43:19,660
אז אתה יכול להמשיך ולהתעלם מכל דבר רק עם 0 בזה

505
00:43:19,660 --> 00:43:23,760
כי אנחנו לא רוצים 256 עלים בקצה שלו.

506
00:43:23,760 --> 00:43:27,960
אנחנו רוצים את המספר של עלים שתווים בלבד

507
00:43:27,960 --> 00:43:31,600
כי למעשה משמש בקובץ.

508
00:43:31,600 --> 00:43:37,590
אתה יכול לקרוא בסמלים האלה, וכל אחד מהסמלים האלה שיש להם תדרים שאינם-0,

509
00:43:37,590 --> 00:43:40,440
אלה הולכים להיות עצים.

510
00:43:40,440 --> 00:43:45,990
מה אתה יכול לעשות הוא בכל פעם שאתם קוראים בתדירות שאינו סמל-0,

511
00:43:45,990 --> 00:43:50,660
אתה יכול לשתול עץ שביער.

512
00:43:50,660 --> 00:43:56,620
ברגע שאתה שותל את העצים ביער, אתה יכול להצטרף העצים האלה כאחים,

513
00:43:56,620 --> 00:44:01,130
כך חוזר לנטיעה וקטיף שבו בוחר 2 ולאחר מכן צמח 1,

514
00:44:01,130 --> 00:44:05,820
איפה זה שמפעל 1 הוא האב של 2 הילדים שהיו צריך לאסוף.

515
00:44:05,820 --> 00:44:11,160
אז התוצאה הסופית שלך הולכת להיות עץ בודד ביער.

516
00:44:16,180 --> 00:44:18,170
ככה אתה בונה את העץ שלך.

517
00:44:18,170 --> 00:44:21,850
>> ישנם מספר דברים שיכולים להשתבש כאן

518
00:44:21,850 --> 00:44:26,580
מכיוון שאנחנו עוסקים ביצירת עצים חדשים והתמודדות עם מצביעים ודברים כאלה.

519
00:44:26,580 --> 00:44:30,450
לפני שנים, כאשר היינו לנו עסק עם מצביעים,

520
00:44:30,450 --> 00:44:36,580
כל פעם שאנו malloc'd אנחנו רוצים לוודא שזה לא יחזור אלינו ערך מצביע NULL.

521
00:44:36,580 --> 00:44:42,770
אז בכמה שלבים בתהליך זה יש הולך להיות כמה מקרים

522
00:44:42,770 --> 00:44:45,920
שם התכנית שלך עלולה להיכשל.

523
00:44:45,920 --> 00:44:51,310
מה שאתה רוצה לעשות הוא שאתה רוצה לוודא שאתה לטפל הטעויות האלה,

524
00:44:51,310 --> 00:44:54,580
ובמפרט זה אומר לטפל בם בחינניות,

525
00:44:54,580 --> 00:45:00,280
כל כך אוהב להדפיס הודעה למשתמש אומר להם מדוע התכנית יש להפסיק

526
00:45:00,280 --> 00:45:03,050
ומייד עזב אותו.

527
00:45:03,050 --> 00:45:09,490
לשם הטיפול בשגיאות הזה, זכור כי אתה רוצה לבדוק את זה

528
00:45:09,490 --> 00:45:12,160
בכל פעם שיכולה להיות כישלון.

529
00:45:12,160 --> 00:45:14,660
בכל פעם שאתה עושה מצביע חדש

530
00:45:14,660 --> 00:45:17,040
אתה רוצה לוודא שזה מצליח.

531
00:45:17,040 --> 00:45:20,320
לפני מה שנהגנו לעשות הוא להפוך את המצביע וmalloc חדש,

532
00:45:20,320 --> 00:45:22,380
ואז הייתי בודקים אם מצביע שהוא NULL.

533
00:45:22,380 --> 00:45:25,670
אז יש הולך להיות כמה מקרים שבם אתה פשוט יכול לעשות את זה,

534
00:45:25,670 --> 00:45:28,610
אבל לפעמים אתה בעצם קורא לפונקציה

535
00:45:28,610 --> 00:45:33,100
ובתוך פונקציה, זה אחד שעושה mallocing.

536
00:45:33,100 --> 00:45:39,110
במקרה זה, אם אנחנו מסתכלים אחורה לחלק מהפונקציות בקוד,

537
00:45:39,110 --> 00:45:42,260
חלקם פונקציות בוליאניים.

538
00:45:42,260 --> 00:45:48,480
במקרה המופשט אם יש לנו פונקציה בוליאנית נקראת foo,

539
00:45:48,480 --> 00:45:54,580
בעצם, אנחנו יכולים להניח שבנוסף לכל מה foo עושה,

540
00:45:54,580 --> 00:45:57,210
מאז זה פונקציה בוליאנית, היא מחזירה אמת או שקר -

541
00:45:57,210 --> 00:46:01,300
אמיתי אם תצליח, אם לא שקרי.

542
00:46:01,300 --> 00:46:06,270
אז אנחנו רוצים לבדוק אם ערך ההחזרה של foo הוא אמת או שקר.

543
00:46:06,270 --> 00:46:10,400
אם זה נכון, זה אומר שאנחנו הולכים ברצונך להדפיס מסר כלשהו

544
00:46:10,400 --> 00:46:14,390
ולאחר מכן לצאת מהתכנית.

545
00:46:14,390 --> 00:46:18,530
מה שאנחנו רוצים לעשות הוא לבדוק את ערך ההחזרה של foo.

546
00:46:18,530 --> 00:46:23,310
אם foo מחזיר שקר, אז אנחנו יודעים שנתקלנו בסוג כלשהו של שגיאה

547
00:46:23,310 --> 00:46:25,110
ואנחנו צריכים להפסיק את התכנית שלנו.

548
00:46:25,110 --> 00:46:35,600
דרך לעשות זאת היא מצב שבו יש הפונקציה בפועל עצמו במצב שלך.

549
00:46:35,600 --> 00:46:39,320
אומר foo לוקח בx.

550
00:46:39,320 --> 00:46:43,390
אנחנו יכולים לקבל כתנאים אם (foo (x)).

551
00:46:43,390 --> 00:46:50,900
בעיקרון, זה אומר שאם בסופו של ביצוע foo היא מחזירה אמיתית,

552
00:46:50,900 --> 00:46:57,390
אז אנחנו יכולים לעשות את זה כי יש לו הפונקציה להעריך foo

553
00:46:57,390 --> 00:47:00,500
על מנת להעריך את המצב כולו.

554
00:47:00,500 --> 00:47:06,500
אז ככה אתה יכול לעשות משהו אם הפונקציה מחזירה אמיתית ומוצלחת.

555
00:47:06,500 --> 00:47:11,800
אבל כשאתה בדיקת שגיאות, אתה רק רוצה לפרוש אם הפונקציה שלך מחזירה שקר.

556
00:47:11,800 --> 00:47:16,090
מה אתה יכול לעשות הוא פשוט להוסיף == כוזב או פשוט להוסיף מפץ לפניו

557
00:47:16,090 --> 00:47:21,010
ואז יש לך אם (! foo).

558
00:47:21,010 --> 00:47:29,540
בתוך גופו של המצב שהיית לו כל הטיפול בשגיאות,

559
00:47:29,540 --> 00:47:36,940
כל כך אוהב, "לא ניתן ליצור העץ הזה" ולאחר מכן להחזיר 1 או משהו כזה.

560
00:47:36,940 --> 00:47:43,340
מה שעושה, אם כי, הוא שלמרות שחזר foo שווא -

561
00:47:43,340 --> 00:47:46,980
אומר foo מחזירת אמת.

562
00:47:46,980 --> 00:47:51,060
אז אתה לא צריך להתקשר לfoo שוב. זה טעות נפוצה.

563
00:47:51,060 --> 00:47:54,730
בגלל שזה היה במצב שלך, זה כבר העריך,

564
00:47:54,730 --> 00:47:59,430
אז יש לך כבר את התוצאה, אם אתה משתמש לעשות עץ או משהו כזה

565
00:47:59,430 --> 00:48:01,840
או צמח או בחירה או משהו.

566
00:48:01,840 --> 00:48:07,460
זה כבר יש ערך. זה כבר הוצא להורג.

567
00:48:07,460 --> 00:48:10,730
אז זה מועיל כדי להשתמש בפונקציות וליאניים כתנאי

568
00:48:10,730 --> 00:48:13,890
משום שאם לא אתה בעצם לבצע את גוף הלולאה,

569
00:48:13,890 --> 00:48:18,030
היא מבצעת את הפונקציה בכל מקרה.

570
00:48:22,070 --> 00:48:27,330
>> השני שלנו לצעד האחרון הוא כותב את ההודעה לקובץ.

571
00:48:27,330 --> 00:48:33,070
ברגע שאנו לבנות עץ האפמן, אז כותב את ההודעה לקובץ הוא די פשוט.

572
00:48:33,070 --> 00:48:39,260
זה די פשוט עכשיו פשוט לעקוב 0s ו 1s.

573
00:48:39,260 --> 00:48:45,480
וזאת על ידי אמנה אנו יודעים שבעץ האפמן את 0s מעיד עזב

574
00:48:45,480 --> 00:48:48,360
ו1s מצביע ימין.

575
00:48:48,360 --> 00:48:53,540
אז אם אתם קוראים בטיפי טיפין, בכל פעם שאתה מקבל 0

576
00:48:53,540 --> 00:48:59,100
אתה עוקב אחרי ענף השמאל, ולאחר מכן בכל פעם שאתם קוראים ב1

577
00:48:59,100 --> 00:49:02,100
אתה הולך לבצע את הסניף הנכון.

578
00:49:02,100 --> 00:49:07,570
ואז אתה הולך להמשיך עד שתגיע לעלה

579
00:49:07,570 --> 00:49:11,550
כי העלים הולכים להיות בסופו של הענפים.

580
00:49:11,550 --> 00:49:16,870
איך אנחנו יכולים לדעת אם אנחנו כבר פגענו עלינו או לא?

581
00:49:19,800 --> 00:49:21,690
אנחנו אמרנו את זה לפני.

582
00:49:21,690 --> 00:49:24,040
[תלמיד] אם המצביעים הם NULL. >> כן.

583
00:49:24,040 --> 00:49:32,220
אנחנו יכולים לדעת אם יש לנו להכות עלה אם המצביעים לעצים ימניים ושמאליים שניהם בטלים.

584
00:49:32,220 --> 00:49:34,110
מושלם.

585
00:49:34,110 --> 00:49:40,320
אנחנו יודעים שאנחנו רוצים לקרוא בטיפי טיפין לתוך קובץ הף.

586
00:49:43,870 --> 00:49:51,220
כפי שראינו קודם לכן בdump.c, מה שהם עשו זה שהם קוראים בטיפי טיפין לתוך קובץ הף

587
00:49:51,220 --> 00:49:54,560
ופשוט הדפיס מה החתיכות האלה היו.

588
00:49:54,560 --> 00:49:58,430
אנחנו לא הולכים לעשות את זה. אנחנו הולכים לעשות משהו שהוא קצת יותר מורכב.

589
00:49:58,430 --> 00:50:03,620
אבל מה שאנחנו יכולים לעשות הוא שאנחנו יכולים לקחת את הקטע הזה של קוד שנכתב בקצת.

590
00:50:03,620 --> 00:50:10,250
כאן יש לנו קצת השלמים המייצגים את הקטע הנוכחי שאנו נמצאים בו.

591
00:50:10,250 --> 00:50:15,520
זה דואג iterating כל הביטים בקובץ עד שתגיע לסוף הקובץ.

592
00:50:15,520 --> 00:50:21,270
בהתבסס על כך, ואז אתה הולך לרוצה לקבל קצת סוג של איטרטור

593
00:50:21,270 --> 00:50:26,760
לחצות את העץ שלך.

594
00:50:26,760 --> 00:50:31,460
ולאחר מכן על בסיס אם הסיבי הוא 0 או 1,

595
00:50:31,460 --> 00:50:36,920
אתה הולך רוצה או להזיז את זה איטרטור לשמאל או להזיז אותו ימינה

596
00:50:36,920 --> 00:50:44,080
כל הדרך עד שתגיע לעלה, ולכן כל הדרך עד שהצומת שאתה על

597
00:50:44,080 --> 00:50:48,260
זה אינו מעיד על בלוטות כל עוד.

598
00:50:48,260 --> 00:50:54,300
למה אנחנו יכולים לעשות את זה עם קובץ האפמן אבל לא קוד מורס?

599
00:50:54,300 --> 00:50:56,610
כי בקוד מורס יש קצת אי בהיר.

600
00:50:56,610 --> 00:51:04,440
אנחנו יכולים להיות כמו, אה רגע, שפגענו מכתב בדרך, אז אולי זה הוא המכתב שלנו,

601
00:51:04,440 --> 00:51:08,150
ואילו אם תמשיך רק עוד קצת, ואז הייתי מכה את מכתב נוסף.

602
00:51:08,150 --> 00:51:13,110
אבל זה לא הולך לקרות בקידוד האפמן,

603
00:51:13,110 --> 00:51:17,540
כך אנחנו יכולים להיות סמוכים ובטוחים שהדרך היחידה שאנחנו הולכים להכות אופי

604
00:51:17,540 --> 00:51:23,480
הוא אם ילדי ימין ועל שמאל שהם הצומת של NULL.

605
00:51:28,280 --> 00:51:32,350
>> לבסוף, אנו רוצים לשחרר את כל הזיכרון שלנו.

606
00:51:32,350 --> 00:51:37,420
אנחנו רוצים גם לסגור את תיק הף כי אנחנו כבר עוסקים ב

607
00:51:37,420 --> 00:51:41,940
כמו גם להסיר את כל העצים ביער שלנו.

608
00:51:41,940 --> 00:51:46,470
בהתבסס על היישום שלך, אתה כנראה הולך רוצה לקרוא להסרת יער

609
00:51:46,470 --> 00:51:49,780
במקום באמת עובר את כל העצים בעצמך.

610
00:51:49,780 --> 00:51:53,430
אבל אם עשית את כל עצים זמניים, אתה רוצה לשחרר את זה.

611
00:51:53,430 --> 00:51:59,060
אתה יודע את הקוד שלך טוב ביותר, כך שאתה יודע לאן אתה הקצאת זיכרון.

612
00:51:59,060 --> 00:52:04,330
ואז אם אתה הולך ב, להתחיל אפילו בקרת F'ing לmalloc,

613
00:52:04,330 --> 00:52:08,330
כל פעם שאתה רואה malloc ולוודא שתשחרר את כל זה

614
00:52:08,330 --> 00:52:10,190
אבל אז פשוט עובר את הקוד שלך,

615
00:52:10,190 --> 00:52:14,260
הבנה שבו אתה יכול להיות מוקצה זיכרון.

616
00:52:14,260 --> 00:52:21,340
בדרך כלל אתה יכול פשוט לומר, "בסופו של קובץ אני רק הולך להסרת יער ביער שלי",

617
00:52:21,340 --> 00:52:23,850
אז בעצם לנקות זיכרון ש, חופשי ש,

618
00:52:23,850 --> 00:52:28,310
"ואז אני גם הולך לסגור את התיק, ואז התכנית שלי הולכת להפסיק."

619
00:52:28,310 --> 00:52:33,810
אבל האם זה הזמן היחיד שהתכנית שלך נסגרה?

620
00:52:33,810 --> 00:52:37,880
לא, כי לפעמים יכול להיות שהיה טעות שקרתה.

621
00:52:37,880 --> 00:52:42,080
אולי אנחנו לא יכולים לפתוח את הקובץ או לא יכל לעשות עם עץ אחר

622
00:52:42,080 --> 00:52:49,340
או איזה סוג של שגיאה שקרה בתהליך הקצאת הזיכרון ואז זה חזר NULL.

623
00:52:49,340 --> 00:52:56,710
שגיאה שקרתה ולאחר מכן חזרנו ולהתפטר.

624
00:52:56,710 --> 00:53:02,040
אז אתה רוצה לוודא שכל זמן אפשרי שהתכנית שלך יכולה להפסיק,

625
00:53:02,040 --> 00:53:06,980
אתה רוצה לשחרר את כל הזיכרון שלך שם.

626
00:53:06,980 --> 00:53:13,370
זה לא רק הולך להיות ממש בסוף של הפונקציה העיקרית שאתה יוצא מהקוד שלך.

627
00:53:13,370 --> 00:53:20,780
אתה רוצה להסתכל אחורה לכל מקרה שהקוד שלך קיים פוטנציאל לחזור בטרם עת

628
00:53:20,780 --> 00:53:25,070
ולאחר מכן זיכרון פנוי מה הגיוני.

629
00:53:25,070 --> 00:53:30,830
תגיד אתה קראת להפוך את יער ושחזר שווא.

630
00:53:30,830 --> 00:53:34,230
אז אתה כנראה לא יהיה צורך להסיר יערך

631
00:53:34,230 --> 00:53:37,080
כי אין לך עדיין יער.

632
00:53:37,080 --> 00:53:42,130
אבל בכל נקודה בקוד שבו אתה יכול לחזור בטרם העת

633
00:53:42,130 --> 00:53:46,160
אתה רוצה לוודא שאתה לשחרר את כל זיכרון אפשרי.

634
00:53:46,160 --> 00:53:50,020
>> לכן, כאשר יש לנו עסק עם שחרור זיכרון ויש דליפות פוטנציאליות,

635
00:53:50,020 --> 00:53:55,440
אנחנו רוצים להשתמש בשיקול הדעת שלנו וההיגיון שלנו לא רק

636
00:53:55,440 --> 00:54:01,850
אלא גם להשתמש בValgrind כדי לקבוע אם יש לנו לשחרר את כל הזיכרון שלנו כמו שצריך או לא.

637
00:54:01,850 --> 00:54:09,460
אתה יכול גם להפעיל Valgrind על פאף ואז יש לך גם להעביר את זה

638
00:54:09,460 --> 00:54:14,020
המספר הנכון של טיעוני שורת פקודה כדי Valgrind.

639
00:54:14,020 --> 00:54:18,100
אתה יכול להפעיל את זה, אבל הפלט הוא קצת מסתורי.

640
00:54:18,100 --> 00:54:21,630
אנחנו קבלנו קצת להתרגל לזה עם מאית, אבל אנחנו עדיין צריכות עוד קצת עזרה,

641
00:54:21,630 --> 00:54:26,450
כך אז מפעיל אותו עם כמה דגלים יותר כמו דליפה לבדוק מלא =,

642
00:54:26,450 --> 00:54:32,040
כנראה שייתן לנו קצת יותר על תפוקה מועילה Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> אז עוד טיפ שימושי כאשר אתה ניפוי הוא פקודת ההבדל.

644
00:54:39,040 --> 00:54:48,520
אתה יכול לגשת ליישומו של צוות של הף, להפעיל שעל קובץ טקסט,

645
00:54:48,520 --> 00:54:55,400
ואז פלטת אותו לקובץ בינארי, קובץ בינארי הף, להיות ספציפי.

646
00:54:55,400 --> 00:54:59,440
אז אם אתה מפעיל הנשיפה שלך על אותו הקובץ בינארי,

647
00:54:59,440 --> 00:55:03,950
אז באופן אידיאלי, קובץ טקסט outputted שלך הולך להיות זהה

648
00:55:03,950 --> 00:55:08,200
לזה המקורי שעבר פנימה

649
00:55:08,200 --> 00:55:15,150
כאן אני משתמש hth.txt כדוגמה, וזה אחד לא דבר עליו במפרט שלך.

650
00:55:15,150 --> 00:55:21,040
זה ממש פשוט HTH ואז שורה חדשה.

651
00:55:21,040 --> 00:55:30,970
אבל בהחלט מרגיש חופשי ואתה בהחלט מוזמן להשתמש בדוגמאות ארוכות יותר

652
00:55:30,970 --> 00:55:32,620
לקובץ הטקסט שלך.

653
00:55:32,620 --> 00:55:38,110
>> אתה אפילו יכול לקחת זריקה בדחיסה ולאחר מכן אולי decompressing

654
00:55:38,110 --> 00:55:41,600
חלק מהקבצים שנמצאים בשימוש במאית כמו המלחמה ושלום

655
00:55:41,600 --> 00:55:46,710
או ג'יין אוסטן או משהו כזה - זה יהיה די מגניב - או אוסטין פאוורס,

656
00:55:46,710 --> 00:55:51,880
סוג של התמודדות עם קבצים גדולים יותר, כי אנחנו לא חושבים על זה

657
00:55:51,880 --> 00:55:55,590
אם השתמשנו בכלי הבא כאן, ls-l.

658
00:55:55,590 --> 00:56:01,150
אנחנו רגילים לls, אשר בעצם מפרט את כל התוכן בספרייה הנוכחית שלנו.

659
00:56:01,150 --> 00:56:07,860
עובר בדגל-l בעצם מציג את הגודל של קבצים אלה.

660
00:56:07,860 --> 00:56:12,690
אם אתה עובר את מפרט pset, זה בעצם מנחה אותך דרך יצירת הקובץ בינארי,

661
00:56:12,690 --> 00:56:16,590
של מתנשם זה, ואתה רואה את זה בקבצים קטנים מאוד

662
00:56:16,590 --> 00:56:23,910
עלות השטח של לדחוס אותו ולתרגם את כל המידע הזה

663
00:56:23,910 --> 00:56:26,980
של כל תדרים והדברים כאלה עולה על התועלת הממשית

664
00:56:26,980 --> 00:56:30,000
דחיסה של הקובץ במקום הראשון.

665
00:56:30,000 --> 00:56:37,450
אבל אם אתה מפעיל אותו על איזה קבצי טקסט ארוכים יותר, אז אתה יכול לראות שאתה מתחיל לקבל כמה תועלת

666
00:56:37,450 --> 00:56:40,930
בדחיסה של קבצים אלה.

667
00:56:40,930 --> 00:56:46,210
>> ולבסוף, יש לנו GDB הידידים הוותיק, שבהחלט הולך להיות שימושי מדי.

668
00:56:48,360 --> 00:56:55,320
>> האם יש לנו שאלות על עצי הף או את התהליך של הפיכה אולי העצים

669
00:56:55,320 --> 00:56:58,590
או כל שאלה אחרת בפאף Huff'n?

670
00:57:00,680 --> 00:57:02,570
אוקיי. אני אשאר קצת סיבובים.

671
00:57:02,570 --> 00:57:06,570
>> תודה לכולם. זה היה Walkthrough 6. ומזל טוב.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]