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 Chan - Πανεπιστήμιο του Χάρβαρντ]

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 Puff.

5
00:00:12,180 --> 00:00:17,440
Σε Σφολιάτα Huff'n τι κάνουμε πρόκειται να κάνουμε με ένα αρχείο συμπιεσμένο Huffman

6
00:00:17,440 --> 00:00:20,740
και στη συνέχεια, ξεφυσώντας το back up, αποσυμπίεση έτσι,

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
και στη συνέχεια, μετά από αυτό είμαστε για να web προγραμματισμό.

15
00:00:56,480 --> 00:01:02,310
Έτσι, τον εαυτό σας συγχαρώ για να πάρει πάνω από την καμπούρα πιο δύσκολες σε CS50.

16
00:01:03,630 --> 00:01:09,760
>> Προχωρώντας για Puff Huff'n, εργαλειοθήκη μας για αυτό το PSET πρόκειται να Huffman δέντρα,

17
00:01:09,760 --> 00:01:14,700
έτσι η κατανόηση όχι μόνο πώς δυαδική εργασία δέντρα, αλλά και συγκεκριμένα δέντρα Huffman,

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
και έτσι αυτά θα είναι τα αρχεία. γ, αλλά στη συνέχεια τα συνοδευτικά. 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
αλλά και κατά τη διάρκεια του debugging.

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
>> Πρώτα ας ρίξουμε μια ματιά σε Huffman δέντρα.

35
00:02:13,720 --> 00:02:19,600
Huffman δέντρα είναι δυαδικά δέντρα, πράγμα που σημαίνει ότι κάθε κόμβος έχει μόνο 2 παιδιά.

36
00:02:19,600 --> 00:02:24,870
Στην Huffman δέντρα το χαρακτηριστικό στοιχείο είναι ότι οι συχνότερες τιμές

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
είστε μετάφραση ότι συχνά, έτσι ώστε αντί να χρειάζεται να χρησιμοποιήσει το σύνολο των bits

41
00:02:43,940 --> 00:02:48,640
διατεθεί για το συνηθισμένο τύπο δεδομένων, μπορείτε να συμπιέσετε τα κάτω σε λιγότερους,

42
00:02:48,640 --> 00:02:53,730
και τότε τα γράμματα που εκπροσωπούνται λιγότερο συχνά εκπροσωπούνται πλέον με bits

43
00:02:53,730 --> 00:02:59,840
επειδή μπορείτε να αντέξετε οικονομικά ότι όταν ζυγίζουν από τις συχνότητες που εμφανίζονται αυτά τα γράμματα.

44
00:02:59,840 --> 00:03:03,020
Έχουμε την ίδια ιδέα εδώ στην Huffman δέντρα

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
πρόκειται να εκπροσωπείται με τις λιγότερες bits.

48
00:03:17,940 --> 00:03:22,020
>> Ο τρόπος που θα κατασκευάσει ένα δέντρο Huffman

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
Όπως είδαμε σε κώδικα Μορς, ο ένας gotcha ήταν ότι αν είχε μόνο ένα ηχητικό σήμα και το μπιπ

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
Και έτσι τι κάνει Huffman δέντρα είναι επειδή από τη φύση των χαρακτήρων

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
σύμφωνα με την οποία επιστολή που προσπαθείτε να κωδικοποιούν με τη σειρά των bits

66
00:04:45,160 --> 00:04:50,670
γιατί πουθενά κατά μήκος των bits που αντιπροσωπεύουν το 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
>> Ας δούμε ένα απλό παράδειγμα ενός δέντρου Huffman.

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
Β εμφανίζεται 6 φορές, και C εμφανίζεται 2 φορές.

76
00:05:25,060 --> 00:05:28,970
Φυσικά, θα πάω να πω ότι είμαι με τη χρήση Β πιο συχνά,

77
00:05:28,970 --> 00:05:35,970
έτσι θέλω να εκπροσωπώ Β με το μικρότερο αριθμό bits, ο μικρότερος αριθμός από 0 και 1.

78
00:05:35,970 --> 00:05:42,600
Και τότε είμαι επίσης πρόκειται να περιμένουμε C να απαιτήσει το πιο ποσό των 0 και 1, καθώς και.

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
Έτσι, εδώ έχουμε Huffman δέντρο μας

92
00:06:36,300 --> 00:06:40,020
όπου για να πάρει στο Β, η οποία θα ήταν απλά το bit 1

93
00:06:40,020 --> 00:06:45,430
και στη συνέχεια να πάρει στο Α θα είχαμε 01 και στη συνέχεια με C 00.

94
00:06:45,430 --> 00:06:51,300
Έτσι, εδώ βλέπουμε ότι βασικά είμαστε εκπροσωπούν αυτές χαρακτήρες είτε με 1 ή 2 bits

95
00:06:51,300 --> 00:06:55,160
όπου το Β, όπως προβλέπεται, έχει το λιγότερο.

96
00:06:55,160 --> 00:07:01,730
Και τότε είχαμε C αναμένεται να έχουν τη μεγαλύτερη, αλλά δεδομένου ότι είναι ένα τόσο μικρό δέντρο Huffman,

97
00:07:01,730 --> 00:07:06,020
τότε το Α αντιπροσωπεύεται επίσης από 2 δυαδικά ψηφία, σε αντίθεση με κάπου στη μέση.

98
00:07:07,820 --> 00:07:11,070
>> Ακριβώς για να πάει πάνω από ένα άλλο απλό παράδειγμα του δέντρου Huffman,

99
00:07:11,070 --> 00:07:19,570
υποθέσουμε ότι έχετε τη συμβολοσειρά "Hello".

100
00:07:19,570 --> 00:07:25,360
Αυτό που κάνετε είναι η πρώτη που θα πω πόσες φορές έχει εμφανιστεί H σε αυτό;

101
00:07:25,360 --> 00:07:34,200
Η εμφανίζεται μία φορά και στη συνέχεια e εμφανίζεται μία φορά και στη συνέχεια έχουμε l εμφανίζεται δύο φορές

102
00:07:34,200 --> 00:07:36,580
και o εμφανίζονται μία φορά.

103
00:07:36,580 --> 00:07:44,310
Και έτσι στη συνέχεια, περιμένουμε ποιο γράμμα πρέπει να εκπροσωπείται από τον ελάχιστο αριθμό bit;

104
00:07:44,310 --> 00:07:47,450
[Φοιτητής] l. >> L. Ναι. l είναι δεξιά.

105
00:07:47,450 --> 00:07:50,730
Περιμένουμε l που αντιπροσωπεύεται από τον ελάχιστο αριθμό bit

106
00:07:50,730 --> 00:07:55,890
l επειδή χρησιμοποιείται πλέον στη συμβολοσειρά "Hello".

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, το οποίο είναι l.

110
00:08:23,410 --> 00:08:32,799
Τότε λέω ότι ο τρόπος μπορώ να οικοδομήσουμε ένα δέντρο Huffman είναι να βρείτε τις 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 και το e.

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
Στη συνέχεια, έχουμε l εκπροσωπείται από μόλις 1 bit και στη συνέχεια το κατά 2 o

124
00:09:45,880 --> 00:09:52,360
και στη συνέχεια το e από 2 και έπειτα το H πέφτει στο 3 bits.

125
00:09:52,360 --> 00:09:59,750
Έτσι, μπορείτε να μεταδώσετε αυτό το μήνυμα "Hello" αντί του πραγματικά με τους χαρακτήρες

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
Θα μπορούσαμε να είχαμε ενταχθεί είτε το Υ και το πρώτο ίσως o.

129
00:10:11,900 --> 00:10:15,730
Ή τότε αργότερα, όταν είχαμε την l εκπροσωπείται από 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
Έτσι, όταν έχουμε να κάνουμε με συμπίεση Huffman,

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
αλλά μερικές φορές μπορείτε επίσης να έχετε ένα δέντρο Huffman

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
Έτσι, αν ήταν να σκεφτούμε έναν κόμβο Huffman, αν κοιτάξουμε πίσω στη δομή εδώ,

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," τότε μετράνε πόσες φορές έχει αναφερθεί Τ,

175
00:13:34,200 --> 00:13:38,420
h αναφέρθηκε, ί, s, γ, 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, καθώς και.

186
00:14:26,100 --> 00:14:31,570
Τώρα ξέρω ότι το επόμενο βήμα μου θα πρέπει να ενώνει το μικρότερο αριθμό,

187
00:14:31,570 --> 00:14:41,380
το οποίο είναι το Τ, το 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
Τι ο κώδικας και ο κώδικας της διανομής σας πρόκειται να κάνει θα ήταν να ενταχθούν στην 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
όπως αναμενόταν, το i και το s, οι οποίες εμφανίζονται πιο συχνά

205
00:15:56,580 --> 00:16:01,350
αντιπροσωπεύονται από το μικρότερο αριθμό από bits.

206
00:16:03,660 --> 00:16:05,660
>> Να είστε προσεκτικοί εδώ.

207
00:16:05,660 --> 00:16:09,780
Στην Huffman δέντρα η υπόθεση έχει σημασία στην πραγματικότητα.

208
00:16:09,780 --> 00:16:13,670
Ένα κεφαλαίο γράμμα S είναι διαφορετική από ό, τι ένα πεζό s.

209
00:16:13,670 --> 00:16:21,260
Αν είχαμε "Αυτό είναι CS50" με κεφαλαία γράμματα, τότε η s πεζά θα εμφανίζονται μόνο δύο φορές,

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
>> Τώρα που έχουμε καλύπτονται Huffman δέντρα, μπορούμε να βουτήξει Puff 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
αντλώντας κόμβους, δημιουργώντας τη δική σας typedef struct για έναν κόμβο,

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
Αυτή η γνώση είναι σίγουρα πρόκειται να σας βοηθήσει όταν βουτιά στο τμήμα Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
του PSET.

223
00:17:19,150 --> 00:17:26,329
Στη βασική έκδοση του PSET, καθήκον σας είναι να εφαρμόσει Puff,

224
00:17:26,329 --> 00:17:30,240
και στην έκδοση χάκερ καθήκον σας είναι να εφαρμόσει Huff.

225
00:17:30,240 --> 00:17:38,490
Τι Huff που κάνει είναι να παίρνει το κείμενο και στη συνέχεια να μεταφράζεται σε 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
Τ αντιπροσωπεύεται από 100, τα πράγματα όπως ότι,

229
00:17:54,840 --> 00:17:58,860
και στη συνέχεια θα λάβει Huff το κείμενο και στη συνέχεια έξοδος ότι δυαδικό.

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
Στη συνέχεια, με Puff μας δίνεται ένα δυαδικό αρχείο του 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
έτσι είμαστε αποσυμπίεση αυτό.

236
00:18:29,350 --> 00:18:36,450
Αν κάνεις το πρότυπο έκδοση, δεν χρειάζεται να εφαρμόσει Huff,

237
00:18:36,450 --> 00:18:39,290
έτσι, τότε μπορείτε να χρησιμοποιήσετε μόνο την υλοποίηση του προσωπικού του Huff.

238
00:18:39,290 --> 00:18:42,080
Υπάρχουν οδηγίες στο spec για το πώς να το κάνουμε αυτό.

239
00:18:42,080 --> 00:18:48,780
Μπορείτε να εκτελέσετε την εφαρμογή προσωπικό του Huff πάνω σε ένα συγκεκριμένο αρχείο κειμένου

240
00:18:48,780 --> 00:18:53,270
και στη συνέχεια να χρησιμοποιήσετε αυτό το έξοδο ως συμβολή σας για να Puff.

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
επειδή τα αρχεία. γ, επειδή έχουμε την. ώρα

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
Αν δεν καταλαβαίνετε τι συμβαίνει στα αρχεία. Γ, τότε μην ανησυχείτε πάρα πολύ,

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, στα σχόλια που δηλώνει ένα στρώμα αφαίρεσης Huffman για κωδικοποιημένα αρχεία.

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
Στη συνέχεια, εδώ έχουμε έναν μαγικό αριθμό που προσδιορίζει ένα Huffman-κωδικοποιημένο αρχείο.

255
00:20:11,930 --> 00:20:15,890
Μέσα σε ένα κώδικα Huffman θα πάμε να έχουν ένα συγκεκριμένο αριθμό μαγεία

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, τότε ξόρκια πραγματικά έξω Huff.

259
00:20:27,160 --> 00:20:34,290
Εδώ έχουμε ένα struct για Huffman-κωδικοποιημένο αρχείο.

260
00:20:34,290 --> 00:20:39,670
Δεν υπάρχει όλα αυτά τα χαρακτηριστικά που σχετίζονται με ένα αρχείο Huff.

261
00:20:39,670 --> 00:20:47,080
Στη συνέχεια, εδώ κάτω έχουμε την κεφαλίδα για ένα αρχείο Huff, έτσι το λέμε 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
Αν είναι ένα πραγματικό αρχείο Huff, πρόκειται να είναι ο αριθμός ψηλά, αυτό το μαγικό ένα.

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
πρόκειται να λίστα ό, τι η συχνότητα αυτών των συμβόλων είναι μέσα στο αρχείο Huff.

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
Στη συνέχεια, έχουμε κάποιες λειτουργίες που επιστρέφουν το επόμενο κομμάτι στο αρχείο Huff

273
00:21:44,600 --> 00:21:52,580
καθώς και γράφει ένα κομμάτι στο αρχείο Huff, και στη συνέχεια, η λειτουργία αυτή εδώ, hfclose,

274
00:21:52,580 --> 00:21:54,650
που κλείνει πραγματικά το αρχείο Huff.

275
00:21:54,650 --> 00:21:57,290
Πριν, είχαμε να κάνουμε με ευθεία ακριβώς fclose,

276
00:21:57,290 --> 00:22:01,190
αλλά όταν έχετε ένα αρχείο Huff, αντί να fclosing

277
00:22:01,190 --> 00:22:06,080
τι είστε πραγματικά πρόκειται να κάνουμε είναι να hfclose και hfopen αυτό.

278
00:22:06,080 --> 00:22:13,220
Αυτές είναι συγκεκριμένες λειτουργίες στα αρχεία Huff ότι θα πάμε να κάνουμε.

279
00:22:13,220 --> 00:22:19,230
Στη συνέχεια, εδώ διαβάζουμε στην κεφαλίδα και στη συνέχεια να γράψει την κεφαλίδα.

280
00:22:19,230 --> 00:22:25,700
>> Ακριβώς με την ανάγνωση του. Αρχείο h μπορούμε να το είδος του να πάρει μια αίσθηση για το τι ένα αρχείο Huff θα μπορούσε να είναι,

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
Έχει όλα τα I / O αρχείο εδώ ασχολούνται με δείκτες.

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
μέσα στο αρχείο Huff αντί να κάνει όλα από μόνοι μας.

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 σε διαφάνειες είπαμε ότι περιμένουμε ένα Huffman κόμβο

291
00:23:30,210 --> 00:23:32,960
και κάναμε ένα typedef struct node.

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
Back to Ορθογράφος, όταν έκαναν ένα νέο κόμβο

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
Δάσος είναι όπου μπορείτε να τοποθετήσετε όλα τα δέντρα Huffman σας.

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, θα περιμένουμε να δούμε τουλάχιστον 1 rmtree εντολή εκεί,

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
Dump από σχόλιο του εδώ παίρνει ένα Huffman-συμπιεσμένο αρχείο

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
για ένα αρχείο bitmap.

379
00:31:33,580 --> 00:31:38,000
Αυτό που κάνουμε εδώ είναι ο έλεγχος για να δούμε αν οι πληροφορίες κεφαλίδας

380
00:31:38,000 --> 00:31:44,330
περιέχει τον σωστό αριθμό μαγεία που δείχνει ότι πρόκειται για ένα πραγματικό αρχείο Huff,

381
00:31:44,330 --> 00:31:53,610
τότε όλα αυτά τα ελέγχους για να βεβαιωθείτε ότι το αρχείο που είναι ανοιχτό ένα πραγματικό huffed αρχείο ή όχι.

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 χωματερή, η οποία είναι το αποτέλεσμα της huffing ένα αρχείο

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
Τ και στη συνέχεια, η οποία εμφανίζεται μία φορά.

391
00:32:54,820 --> 00:33:07,860
Και τότε εδώ έχουμε το πραγματικό μήνυμα σε 0s και 1s.

392
00:33:07,860 --> 00:33:15,450
Αν κοιτάξουμε hth.txt, η οποία είναι κατά πάσα πιθανότητα το αρχικό μήνυμα που huffed,

393
00:33:15,450 --> 00:33:22,490
περιμένουμε να δούμε κάποια Hs και Ts εκεί.

394
00:33:22,490 --> 00:33:28,720
Συγκεκριμένα, περιμένουμε να δούμε μόνο 1 και 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 Huff είναι κωδικοποιούν επίσης το χαρακτήρα νέας γραμμής, καθώς και.

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
και στη συνέχεια το Τ είναι πιθανώς 01 και στη συνέχεια το επόμενο H είναι 1, καθώς

401
00:34:17,120 --> 00:34:21,139
και στη συνέχεια, έχουμε μια νέα γραμμή υποδεικνύεται από δύο 0s.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> Και τελικά, επειδή έχουμε να κάνουμε με πολλαπλά. Και γ. Αρχεία h,

404
00:34:31,600 --> 00:34:36,350
θα πάμε να έχουν ένα αρκετά πολύπλοκο επιχείρημα για τον compiler,

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
καθώς και να πάει μακριά από αυτό το σημείο για να δείτε πώς μπορείτε να είναι σε θέση να κάνει το αρχείο σας Puff

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
για το πώς θα πάμε να ασχολούνται με τους κόμβους Huffman.

416
00:35:30,980 --> 00:35:35,400
Εμείς δεν πρόκειται να καλώντας τους κόμβους πια? Θα πάμε να τους καλεί τα δέντρα

417
00:35:35,400 --> 00:35:39,260
όπου θα πάμε για να εκπροσωπεί τους σύμβολο με μια χαρα,

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
Τελικά, όταν είμαστε δημιουργία Huff αρχείο μας,

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
Νωρίτερα, όταν κάναμε ακριβώς Huffman δέντρα μας,

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
Και τελικά, το τελευταίο βήμα μας με την παραγωγή μας παράδειγμα με την As, Β, και 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; Εντάξει. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Τι πρέπει να κάνουμε για Puff;

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
θέλουμε να εξασφαλίσουμε ότι η είσοδος είναι ένα αρχείο Huff ή όχι.

446
00:38:05,820 --> 00:38:10,420
Και στη συνέχεια, όταν εγγυόμαστε ότι είναι ένα αρχείο Huff, τότε θέλουμε να οικοδομήσουμε δέντρο μας,

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
Αυτό είναι χρήση. Και τώρα θέλουμε να εξασφαλίσουμε ότι η είσοδος huffed ή όχι.

459
00:39:08,820 --> 00:39:16,420
Σκεπτόμενος πίσω, υπήρχε κάτι στον κώδικα της διανομής που θα μπορούσε να μας βοηθήσει

460
00:39:16,420 --> 00:39:21,570
με την κατανόηση εάν ένα αρχείο huffed ή όχι;

461
00:39:21,570 --> 00:39:26,910
Υπήρχε πληροφορίες σχετικά με την huffile.c Huffeader.

462
00:39:26,910 --> 00:39:33,430
Γνωρίζουμε ότι κάθε αρχείο έχει ένα Huff 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
στην οποία είχε την ανάγνωση σε ένα αρχείο Huff.

467
00:39:49,120 --> 00:39:53,990
Και έτσι για να το κάνουμε αυτό, θα έπρεπε να ελέγξει αν όντως ήταν huffed ή όχι.

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
και θα ερμηνεύεται ότι για Whodunit και μεγέθους,

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
σχετικά με τον τρόπο εξασφαλίζεται ότι η είσοδος είναι στην πραγματικότητα ή όχι huffed

477
00:40:40,540 --> 00:40:43,240
καθώς και μερικά άλλα πράγματα.

478
00:40:45,930 --> 00:40:50,250
Έχουμε εξασφαλίσει την ορθή χρήση και εξασφαλίζεται ότι η είσοδος huffed.

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
Υπάρχει η Boolean λειτουργία φυτό ότι τα φυτά μη-0 δέντρο μέσα στο δάσος συχνότητα μας.

485
00:41:23,870 --> 00:41:29,250
Και έτσι εκεί θα περάσει σε ένα δείκτη σε ένα δάσος και ένα δείκτη σε ένα δέντρο.

486
00:41:32,530 --> 00:41:40,340
Γρήγορη ερώτηση: Πόσα δάση θα έχετε όταν είστε οικοδόμηση ενός δέντρου Huffman;

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
είστε picking 2 δέντρα και στη συνέχεια ένα άλλο δέντρο φύτευση

500
00:42:48,840 --> 00:42:54,060
που έχει αυτά τα 2 δέντρα που πήρε ως παιδιά.

501
00:42:57,950 --> 00:43:05,280
Για να οικοδομήσουμε δέντρο Huffman, μπορείτε να διαβάσετε τα σύμβολα και τις συχνότητες, προκειμένου

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
και στο spec λέει να τα χειριστεί με χάρη,

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
ορισμένες από αυτές είναι Boolean λειτουργίες.

538
00:45:42,260 --> 00:45:48,480
Στην αφηρημένη περίπτωση που έχουμε μια Boolean συνάρτηση που ονομάζεται foo,

539
00:45:48,480 --> 00:45:54,580
βασικά, μπορούμε να υποθέσουμε ότι εκτός από να κάνει ό, τι κάνει foo,

540
00:45:54,580 --> 00:45:57,210
δεδομένου ότι είναι μια Boolean λειτουργία, επιστρέφει αληθής ή ψευδής -

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
Έτσι, τότε αυτό είναι το πώς μπορείτε να κάνετε κάτι, αν η συνάρτηση επιστρέφει true και είναι επιτυχής.

555
00:47:06,500 --> 00:47:11,800
Αλλά όταν είσαι έλεγχο σφαλμάτων, το μόνο που θέλουν να σταματήσουν το κάπνισμα, εάν η λειτουργία σας επιστρέφει false.

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 επιστρέφει true.

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
Γι 'αυτό είναι χρήσιμο να χρησιμοποιήσετε Boolean λειτουργίες όπως η κατάσταση

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
Όταν χτίζουμε το δέντρο Huffman, στη συνέχεια, γράφοντας το μήνυμα στο αρχείο είναι αρκετά απλή.

572
00:48:33,070 --> 00:48:39,260
Είναι αρκετά εύκολο τώρα να ακολουθήσει ακριβώς την 0s και 1s.

573
00:48:39,260 --> 00:48:45,480
Και έτσι, κατά συνθήκη, γνωρίζουμε ότι σε ένα δέντρο Huffman δείχνουν τα αριστερά 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
Μπορούμε να πούμε αν έχουμε χτυπήσει ένα φύλλο, εάν οι δείκτες τόσο για το αριστερό και το δεξί δέντρα είναι NULL.

584
00:49:32,220 --> 00:49:34,110
Τέλεια.

585
00:49:34,110 --> 00:49:40,320
Ξέρουμε ότι θέλουμε να διαβάζονται σιγά-σιγά σε Huff αρχείο μας.

586
00:49:43,870 --> 00:49:51,220
Όπως είδαμε πριν σε dump.c, τι έκαναν είναι να διαβάσετε σε λίγο-λίγο στο αρχείο Huff

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
Αυτό φροντίζει για την επανάληψη όλων των bits στο αρχείο μέχρι να χτυπήσει το τέλος του αρχείου.

592
00:50:15,520 --> 00:50:21,270
Με βάση αυτό, τότε θα πάμε να θέλουν να έχουν κάποιο είδος του iterator

593
00:50:21,270 --> 00:50:26,760
να διασχίσει το δέντρο σας.

594
00:50:26,760 --> 00:50:31,460
Και στη συνέχεια με βάση το αν το bit είναι 0 ή 1,

595
00:50:31,460 --> 00:50:36,920
θα πάμε να θέλουν να μετακινηθούν είτε ότι iterator προς τα αριστερά ή να το μετακινήσετε προς τα δεξιά

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
Γιατί μπορούμε να το κάνουμε αυτό με ένα αρχείο αλλά δεν Huffman κώδικα Μορς;

599
00:50:54,300 --> 00:50:56,610
Επειδή σε κώδικα Μορς υπάρχει ένα κομμάτι της ασάφειας.

600
00:50:56,610 --> 00:51:04,440
Θα μπορούσε να είναι όπως, OH περιμένει, έχουμε χτυπήσει ένα γράμμα στο δρόμο, οπότε ίσως αυτό είναι η επιστολή μας,

601
00:51:04,440 --> 00:51:08,150
ενώ αν συνεχιστεί μόλις λίγο περισσότερο, τότε θα είχαμε χτυπήσει ένα άλλο γράμμα.

602
00:51:08,150 --> 00:51:13,110
Αλλά αυτό δεν πρόκειται να συμβεί στην κωδικοποίηση Huffman,

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
Θέλουμε τόσο κοντά το αρχείο Huff ότι έχουμε ήδη ασχολούνται με

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 για Puff και στη συνέχεια θα πρέπει να περάσει επίσης

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
έτσι τρέχει στη συνέχεια με λίγες περισσότερες σημαίες, όπως η διαρροή-check = πλήρης,

642
00:54:26,450 --> 00:54:32,040
που πιθανότατα θα μας δώσει λίγο περισσότερο χρήσιμες για έξοδο Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Στη συνέχεια, μια άλλη χρήσιμη συμβουλή όταν debugging είναι η εντολή diff.

644
00:54:39,040 --> 00:54:48,520
Μπορείτε να αποκτήσετε πρόσβαση υλοποίηση του προσωπικού του Huff, ότι τρέχει σε ένα αρχείο κειμένου,

645
00:54:48,520 --> 00:54:55,400
και στη συνέχεια εξάγει σε ένα δυαδικό αρχείο, ένα δυαδικό αρχείο Huff, να είναι συγκεκριμένα.

646
00:54:55,400 --> 00:54:59,440
Στη συνέχεια, αν έχετε δικό σας φούσκα σε αυτό το δυαδικό αρχείο,

647
00:54:59,440 --> 00:55:03,950
στη συνέχεια, στην ιδανική περίπτωση, εξερχόμενο αρχείο κειμένου σας πρόκειται να είναι πανομοιότυπα

648
00:55:03,950 --> 00:55:08,200
με το αρχικό που έχετε περάσει μέσα

649
00:55:08,200 --> 00:55:15,150
Εδώ είμαι με τη χρήση hth.txt ως παράδειγμα, και αυτό είναι το ένα μίλησε για το spec σας.

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
>> Μπορείτε να πάρετε ακόμη και έναν πυροβολισμό στο ίσως συμπίεση και αποσυμπίεση, στη συνέχεια

654
00:55:38,110 --> 00:55:41,600
μερικά από τα αρχεία που χρησιμοποιούνται σε Ορθογράφος, όπως Πόλεμος και Ειρήνη

655
00:55:41,600 --> 00:55:46,710
ή Jane Austen ή κάτι τέτοιο - που θα είναι είδος δροσερό - ή Austin Powers,

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
Αν πάτε μέσω του spec PSET, αυτό που πραγματικά περπατά μέσω της δημιουργίας το δυαδικό αρχείο,

661
00:56:12,690 --> 00:56:16,590
του huffing αυτό, και θα δείτε ότι για πολύ μικρά αρχεία

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
>> Έχουμε απορίες σχετικά με Huff δέντρα ή τη διαδικασία ίσως καταστεί τα δέντρα

669
00:56:55,320 --> 00:56:58,590
ή οποιεσδήποτε άλλες ερωτήσεις σχετικά με Puff 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]