[Powered by Google Translate] [Walkthrough - Vấn đề Set 6] [Zamyla Chan - Đại học Harvard] [Đây là CS50. - CS50.TV] 

Xin chào, tất cả mọi người, và chào đón để Walkthrough 6: Huff'n Puff. Trong Huff'n Puff những gì chúng tôi đang làm là có thể đối phó với một tập tin nén Huffman và sau đó puffing nó lại lên, do đó, giải nén nó, để chúng tôi có thể dịch từ 0 và 1 mà người dùng gửi cho chúng tôi và chuyển đổi nó trở lại vào văn bản gốc. Pset 6 là có được khá mát mẻ bởi vì bạn sẽ thấy một số trong những công cụ mà bạn sử dụng trong pset 4 và pset 5 và các loại kết hợp chúng thành khái niệm khá gọn gàng 1 khi bạn đến để suy nghĩ về nó. 

Ngoài ra, có thể là, pset 4 và 5 là psets thách thức mà chúng tôi đã cung cấp. Vì vậy, từ bây giờ, chúng tôi có pset thêm 1 trong C, và sau đó sau đó chúng tôi đang lập trình web. Vì vậy, chúc mừng mình nhận được trên cái bướu khó khăn nhất trong CS50. 

Chuyển Huff'n Puff, hộp công cụ của chúng tôi cho pset này sẽ là Huffman cây, do đó, sự hiểu biết không chỉ làm thế nào cây nhị phân công việc mà còn đặc biệt Huffman cây, làm thế nào họ đang xây dựng. Và sau đó chúng ta sẽ có rất nhiều mã phân phối pset này, và chúng tôi sẽ đến xem mà thực sự một số mã chúng tôi có thể có thể không hoàn toàn hiểu, và do đó, những sẽ là c tập tin., nhưng sau đó đi kèm của họ. h file sẽ cho chúng ta đủ hiểu biết mà chúng ta cần để chúng tôi biết những chức năng làm việc như thế nào hoặc ít nhất là những gì họ có nghĩa vụ phải làm đầu vào và đầu ra của họ - thậm chí nếu chúng ta không biết những gì đang xảy ra trong hộp đen hoặc không hiểu những gì đang xảy ra trong các hộp đen trong vòng. Và cuối cùng, như thường lệ, chúng tôi đang đối phó với các cấu trúc dữ liệu mới, loại cụ thể của các nút trỏ đến những điều nào đó, và vì vậy ở đây có một cây bút và giấy không chỉ cho quá trình thiết kế và khi bạn đang cố gắng để tìm ra cách pset bạn nên làm việc mà còn trong quá trình gỡ lỗi. Bạn có thể có GDB cùng với bút và giấy của bạn trong khi bạn đi xuống các giá trị là gì, mũi tên của bạn đang trỏ, và những thứ như thế. 

Trước tiên chúng ta hãy nhìn vào cây Huffman. Huffman cây là cây nhị phân, nghĩa là mỗi node chỉ có 2 con. Trong cây Huffman đặc trưng là các giá trị thường xuyên nhất được đại diện bởi các bit ít nhất. Chúng ta đã thấy trong các ví dụ bài giảng của mã Morse, mà loại của hợp nhất một số chữ cái. Nếu bạn đang cố gắng để dịch một A hoặc E, ví dụ, bạn đang dịch thường xuyên, do đó, thay vì phải sử dụng toàn bộ các bit được phân bổ cho loại dữ liệu thông thường, bạn nén nó xuống ít hơn, và sau đó những chữ cái được đại diện ít thường xuyên hơn được đại diện với bit dài hơn vì bạn có thể đủ khả năng đó khi bạn cân nhắc các tần số mà những chữ cái xuất hiện. Chúng tôi có ý tưởng tương tự ở cây Huffman nơi mà chúng tôi đang làm cho một chuỗi, một loại đường dẫn để có được một số ký tự. Và sau đó các nhân vật có tần số nhất sẽ được đại diện với các bit ít nhất. 

Cách mà bạn xây dựng một cây Huffman bằng cách đặt tất cả các nhân vật xuất hiện trong văn bản và tính toán tần số của họ, làm thế nào chúng xuất hiện. Điều này có thể là một số của những chữ cái xuất hiện bao nhiêu lần hoặc có lẽ là một tỷ lệ phần trăm trong số tất cả các nhân vật từng xuất hiện nhiều như thế nào. Và vì vậy những gì bạn làm là một khi bạn có tất cả các rằng trong ánh xạ, sau đó bạn nhìn cho 2 tần số thấp nhất và sau đó tham gia cùng họ là anh chị em ruột mà sau đó là nút cha có tần số là tổng của 2 con của nó. Và sau đó bạn theo quy ước nói rằng các nút trái, bạn làm theo bằng cách làm theo các chi nhánh 0, và sau đó nút ngoài cùng bên phải là chi nhánh 1. Như chúng ta đã thấy trong mã Morse, Ghi chú là nếu bạn đã có một tiếng bíp và tiếng bíp đó là mơ hồ. Nó hoặc có thể là 1 lá thư hoặc nó có thể là một chuỗi 2 chữ cái. Và vì vậy những gì Huffman cây là bởi vì bản chất của các nhân vật hoặc ký tự cuối cùng của chúng tôi thực tế là các nút cuối cùng trên chi nhánh - chúng tôi tham khảo những người như lá - do đó không thể có bất kỳ sự mơ hồ trong điều kiện của thư mà bạn đang cố gắng để mã hóa với một loạt các bit bởi vì hư không cùng các bit đại diện cho 1 ký tự bạn sẽ gặp phải một lá thư khác, và sẽ không có bất kỳ sự nhầm lẫn đó. Nhưng chúng ta sẽ đi vào các ví dụ mà bạn thực sự có thể nhìn thấy thay vì chúng ta chỉ nói với bạn rằng đó là sự thật. 

Hãy xem xét một ví dụ đơn giản của một cây Huffman. Tôi có một chuỗi dài 12 ký tự. Tôi có 4 As, 6 Bs, và 2 Cs. Bước đầu tiên của tôi sẽ được đếm. Bao nhiêu lần A xuất hiện? Nó xuất hiện 4 lần trong chuỗi. B xuất hiện 6 lần, và C xuất hiện 2 lần. Đương nhiên, tôi sẽ nói tôi đang sử dụng B thường xuyên nhất, vì vậy tôi muốn đại diện cho B với số lượng ít nhất của các bit, số lượng ít nhất trong số 0 và 1. Và sau đó tôi cũng sẽ mong đợi C yêu cầu số tiền nhất của 0 và 1. Đầu tiên những gì tôi đã làm ở đây được chúng tôi đặt thứ tự tăng dần về tần số. Chúng tôi thấy rằng C và A, những người đang có 2 của chúng tôi tần số thấp nhất. Chúng tôi tạo ra một nút cha, và rằng nút phụ huynh không có một bức thư liên kết với nó, nhưng nó có một tần số, là tổng. Tổng hợp trở thành 2 + 4, trong đó là 6. Sau đó, chúng tôi thực hiện theo các nhánh trái. Nếu chúng ta rằng nút 6, sau đó chúng tôi sẽ làm theo 0 C và sau đó 1 A. Vì vậy, bây giờ chúng tôi có 2 nút. Chúng tôi có giá trị 6 và sau đó chúng tôi cũng có một nút khác với giá trị 6. Và như vậy những 2 không chỉ là mức thấp nhất 2 nhưng cũng chỉ là 2 còn sót lại, do đó, chúng tôi tham gia của phụ huynh khác, với số tiền là 12. Vì vậy, ở đây chúng tôi có cây Huffman của chúng tôi nơi nhận được B, đó sẽ chỉ là bit 1 và sau đó để có được đến A, chúng tôi sẽ có 01 và sau đó C có 00. Vì vậy, ở đây chúng tôi thấy rằng về cơ bản chúng tôi đang đại diện cho các ký tự này với 1 hoặc 2 bit B, như dự đoán, có ít nhất. Và sau đó chúng tôi đã mong đợi C có nhiều nhất, nhưng kể từ khi nó như một cây nhỏ Huffman, thì A cũng được đại diện bởi 2 bit như trái ngược với một nơi nào đó ở giữa. 

Chỉ cần đi qua một ví dụ đơn giản khác của cây Huffman, nói rằng bạn có chuỗi "Hello". Những gì bạn làm là lần đầu tiên bạn sẽ nói bao nhiêu lần H xuất hiện trong? H xuất hiện một lần và sau đó e xuất hiện một lần và sau đó chúng tôi có l xuất hiện hai lần và o xuất hiện một lần. Và như vậy thì chúng tôi hy vọng bức thư cho được đại diện bởi số lượng ít nhất của các bit? [Sinh viên] l. >> L. Yeah. l là đúng. Chúng tôi hy vọng l được đại diện bởi số lượng ít nhất của các bit vì l được sử dụng nhiều nhất trong chuỗi "Hello." Những gì tôi đang làm bây giờ là vẽ ra các nút này. Tôi có 1, đó là H, và sau đó khác 1, đó là e, và sau đó một 1, mà là o - ngay bây giờ tôi đang đặt chúng theo thứ tự và sau đó 2, đó là l. Sau đó, tôi nói theo cách mà tôi xây dựng một cây Huffman là tìm thấy 2 nút với tần số ít nhất và làm cho họ anh chị em bằng cách tạo ra một nút cha. Ở đây chúng tôi có 3 nút với tần số thấp nhất. Họ tất cả 1. Vì vậy, ở đây chúng tôi chọn một trong chúng ta sẽ liên kết đầu tiên. Hãy nói rằng tôi chọn H và điện tử. Tổng của 1 + 1 là 2, nhưng nút này không có một bức thư liên kết với nó. Nó chỉ giữ giá trị. Bây giờ chúng ta nhìn vào 2 tần số thấp nhất tiếp theo. Đó là 2 và 1. Đó có thể là một trong những người 2, nhưng tôi sẽ chọn một trong những điều này. Tổng là 3. Và cuối cùng, tôi chỉ có 2 bên trái, sau đó trở thành 5. Sau đó, ở đây, như mong đợi, nếu tôi điền vào trong mã hóa cho rằng, 1s luôn luôn chi nhánh phải và số 0 là một trong những bên trái. Sau đó, chúng tôi có l đại diện bởi chỉ bit 1 và sau đó o 2 và sau đó e 2 và sau đó H rơi xuống 3 bit. Vì vậy, bạn có thể truyền tải thông điệp này "Hello" thay vì thực sự sử dụng các ký tự bằng cách chỉ 0 và 1. Tuy nhiên, hãy nhớ rằng trong nhiều trường hợp, chúng tôi đã có quan hệ với tần số của chúng tôi. Chúng ta có thể có hoặc tham gia vào H và o đầu tiên có thể. Hoặc sau đó sau này khi chúng tôi đã có l đại diện bởi 2 cũng như tham gia một trong những đại diện bởi 2, chúng ta có thể liên kết với một trong hai. 

Và như vậy khi bạn gửi 0 và 1, mà thực sự không đảm bảo mà người nhận có thể đọc đầy đủ thông điệp của bạn phải off the bat bởi vì họ có thể không biết được quyết định bạn đã thực hiện. Vì vậy, khi chúng ta đang đối phó với nén Huffman, bằng cách nào đó, chúng ta phải nói với người nhận thông điệp của chúng tôi chúng tôi quyết định như thế nào - Họ cần phải biết một số loại thông tin thêm trong Ngoài thông điệp nén. Họ cần phải hiểu những gì cây thực sự trông giống như, làm thế nào chúng ta thực sự thực hiện các quyết định đó. 

Ở đây chúng ta chỉ cần làm ví dụ dựa trên số lượng thực tế, nhưng đôi khi bạn cũng có thể có một cây Huffman dựa trên tần số mà tại đó các chữ cái xuất hiện, và đó là quá trình tương tự chính xác. Ở đây tôi đang thể hiện về tỷ lệ phần trăm hoặc một phần nhỏ, và do đó, đây chính xác cùng một điều. Tôi tìm thấy trong 2 thấp nhất, tổng hợp, tiếp theo 2 thấp nhất, tổng hợp, cho đến khi tôi có một cây đầy đủ. Mặc dù chúng tôi có thể làm điều đó trong hai cách, khi chúng tôi đang đối phó với tỷ lệ phần trăm, điều đó có nghĩa là chúng tôi đang phân chia thứ và đối phó với số thập phân hay đúng hơn là nổi nếu chúng ta đang suy nghĩ về cấu trúc dữ liệu của một cái đầu. Chúng ta biết gì về nổi? Một vấn đề thường gặp khi chúng ta đang đối phó với phao là gì? [Sinh viên] không chính xác số học. >> Yeah. Không rõ ràng. Bởi vì sự thiếu chính xác dấu chấm động, pset này để chúng tôi đảm bảo rằng chúng ta không mất bất kỳ giá trị, sau đó chúng tôi đang thực sự sẽ được giao dịch với đếm. Vì vậy, nếu bạn là suy nghĩ của một nút Huffman, nếu bạn nhìn lại cấu trúc ở đây, nếu bạn nhìn vào những người màu xanh lá cây nó có một tần số liên kết với nó cũng như nó chỉ đến một nút bên trái của nó cũng như một nút bên phải của nó. Và sau đó là màu đỏ đó cũng có một nhân vật liên kết với chúng. Chúng tôi sẽ không làm cho những người riêng biệt cho cha mẹ và sau đó các nút cuối cùng, mà chúng tôi đề cập như lá, mà là những người sẽ chỉ có giá trị NULL. Đối với mỗi nút, chúng tôi sẽ có một nhân vật, biểu tượng nút đó đại diện cho, sau đó một tần số cũng như một con trỏ đến con trái của nó cũng như con phải của nó. Lá, đó là ở dưới cùng rất, cũng sẽ có con trỏ nút bên trái và bên phải của họ, nhưng kể từ khi những giá trị không chỉ đến các hạch thực tế, giá trị của họ sẽ là gì? >> [Sinh viên] NULL. >> NULL. Chính xác. Dưới đây là một ví dụ về làm thế nào bạn có thể đại diện cho các tần số trong các phao nổi, nhưng chúng ta sẽ phải đối phó với nó với số nguyên, do đó, tất cả những gì tôi đã làm là thay đổi các kiểu dữ liệu đó. 

Chúng ta hãy đi hơn một chút của một ví dụ phức tạp. Nhưng bây giờ mà chúng tôi đã thực hiện những cái đơn giản, nó chỉ là quá trình tương tự. Bạn tìm thấy 2 tần số thấp nhất, tổng hợp các tần số và đó là tần số mới của nút cha mẹ của bạn, sau đó chỉ vào bên trái của nó với các chi nhánh 0 và quyền với các chi nhánh 1. Nếu chúng ta có chuỗi "Đây là CS50," sau đó chúng tôi đếm bao nhiêu lần là T được đề cập, h đã đề cập, i, s, c, 5, 0. Sau đó, những gì tôi đã làm ở đây là với các nút màu đỏ tôi mới trồng, Tôi nói rằng tôi sẽ có những nhân vật cuối cùng ở dưới cùng của cây của tôi. Những người sẽ được tất cả lá. Sau đó, những gì tôi đã làm là chúng tôi được sắp xếp theo số thứ tự tăng dần, và điều này thực sự là cách mã pset không là nó loại theo tần số và sau đó theo thứ tự bảng chữ cái. Vì vậy, nó có những con số đầu tiên và sau đó theo thứ tự bảng chữ cái tần số. Sau đó, những gì tôi sẽ làm là tôi sẽ tìm thấy thấp nhất 2. Đó là 0 và 5. Tôi sẽ tổng hợp, và đó là 2. Sau đó, tôi sẽ tiếp tục tìm thấy 2 thấp nhất tiếp theo. Đó là 1s hai, và sau đó những người trở thành 2 là tốt. Bây giờ tôi biết rằng bước tiếp theo của tôi là sẽ được tham gia số lượng thấp nhất, đó là T, 1, và sau đó chọn một trong các nút có 2 như tần số. Vì vậy, ở đây chúng tôi có 3 lựa chọn. Những gì tôi sẽ làm cho slide chỉ là trực quan sắp xếp lại chúng cho bạn để bạn có thể xem như thế nào Tôi đang xây dựng nó lên. Mã và mã phân phối của bạn sẽ làm được sẽ gia nhập T với các nút 0 và 5. Vì vậy, sau đó số tiền đến 3, và sau đó chúng tôi tiếp tục quá trình. The 2 và 2 tại là thấp nhất, sau đó những khoản tiền 4. Tất cả mọi người sau cho đến nay? Okay. Sau đó, sau đó chúng tôi có 3 và 3 cần được bổ sung, vì vậy một lần nữa, tôi chỉ cần chuyển đổi nó để bạn có thể nhìn thấy bằng mắt để nó không nhận được quá lộn xộn. Sau đó, chúng tôi có một 6, và sau đó bước cuối cùng của chúng tôi bây giờ là rằng chúng tôi chỉ có 2 nút chúng tôi tổng hợp những để làm cho gốc rễ của cây của chúng tôi, mà là 10. Và số 10 có ý nghĩa bởi vì mỗi nút đại diện, giá trị của họ, số tần số của họ là bao nhiêu lần họ xuất hiện trong chuỗi, và sau đó chúng tôi có 5 ký tự trong chuỗi ký tự của chúng tôi, do đó, có ý nghĩa. Nếu chúng ta nhìn lên làm thế nào chúng ta thực sự sẽ mã hóa nó, như mong đợi, i và s, xuất hiện thường xuyên nhất được đại diện bởi số lượng ít nhất của các bit. 

Hãy cẩn thận ở đây. Trong trường hợp cây Huffman thực sự quan trọng. An S chữ hoa là khác nhau hơn một s chữ thường. Nếu chúng tôi đã có "Đây là CS50" với chữ in hoa, sau đó s chữ thường chỉ xuất hiện hai lần, sẽ là một nút với 2 như giá trị của nó, và sau đó chữ hoa S sẽ chỉ được một lần. Vì vậy, sau đó cây của bạn sẽ thay đổi cấu trúc bởi vì bạn thực sự có một lá thêm ở đây. Tuy nhiên, số tiền vẫn sẽ là 10. Đó là những gì chúng tôi đang thực sự sẽ được gọi tổng kiểm tra, việc bổ sung của tất cả các số đếm. 

Bây giờ chúng tôi đã được bảo hiểm cây Huffman, chúng ta có thể nhảy vào Huff'n Puff, pset. Chúng ta sẽ bắt đầu với một phần của câu hỏi, và điều này sẽ giúp bạn có được quen với cây nhị phân và làm thế nào để hoạt động xung quanh đó: vẽ các nút, tạo struct typedef của bạn cho một nút, và nhìn thấy cách bạn có thể chèn vào một cây nhị phân, một trong đó là sắp xếp, vượt qua nó, và những thứ như thế. Kiến thức đó chắc chắn sẽ giúp bạn khi bạn đi sâu vào phần Puff Huff'n của pset. Trong phiên bản tiêu chuẩn của pset, nhiệm vụ của bạn là thực hiện Puff, và trong phiên bản hacker nhiệm vụ của bạn là để thực hiện Huff. Huff không là phải mất văn bản và sau đó nó chuyển nó thành 0 và 1, vì vậy quá trình mà chúng ta đã làm ở trên, nơi chúng tôi đếm tần số và sau đó thực hiện các cây và sau đó nói, "Làm thế nào để có được T?" T được đại diện bởi 100, những điều như thế, và sau đó Huff sẽ có văn bản và sau đó sản lượng mà nhị phân. Nhưng cũng bởi vì chúng ta biết rằng chúng ta muốn cho phép người nhận của tin nhắn để tái tạo chính xác cùng một cây, nó cũng bao gồm thông tin về tính tần số. Sau đó, với Puff chúng tôi đang đưa ra một tập tin nhị phân 0 và 1 và đưa ra các thông tin về các tần số. Chúng tôi dịch tất cả những người trở lại 0 và 1 thành thông điệp ban đầu đó là, vì vậy chúng tôi đang giải nén. Nếu bạn đang làm phiên bản tiêu chuẩn, bạn không cần phải thực hiện Huff, do đó, sau đó bạn chỉ có thể sử dụng cán bộ thực hiện Huff. Có hướng dẫn trong spec về làm thế nào để làm điều đó. Bạn có thể chạy các cán bộ thực hiện của Huff khi một tập tin văn bản nhất định và sau đó sử dụng đầu ra như là đầu vào của bạn Puff. 

Như tôi đã đề cập trước đây, chúng tôi có rất nhiều mã phân phối cho một này. Tôi sẽ bắt đầu đi qua nó. Tôi sẽ dành hầu hết thời gian vào các tập tin h bởi vì trong các tập tin c., bởi vì chúng ta có h. và cung cấp cho chúng tôi với các nguyên mẫu của các chức năng, chúng ta không hoàn toàn cần phải hiểu chính xác - Nếu bạn không hiểu những gì đang xảy ra trong các tập tin c., Sau đó không lo lắng quá nhiều, nhưng chắc chắn cố gắng để có một cái nhìn bởi vì nó có thể cung cấp cho một số gợi ý và nó rất hữu ích để có được sử dụng để đọc mã của người khác. 

Nhìn vào huffile.h, trong các ý kiến ​​tuyên bố một lớp trừu tượng cho các tập tin mã hóa Huffman. Nếu chúng tôi đi xuống, chúng ta thấy rằng có một tối đa là 256 ký hiệu mà chúng ta có thể cần mã số. Điều này bao gồm tất cả các chữ của bảng chữ cái chữ hoa và chữ thường - và sau đó ký hiệu, số, vv Sau đó, ở đây chúng tôi có một số phép thuật xác định một tập tin mã hóa Huffman. Trong vòng một mã Huffman họ đang đi để có một con số kỳ diệu nhất định liên kết với tiêu đề. Điều này có thể trông giống như chỉ là một con số kỳ diệu ngẫu nhiên, nhưng nếu bạn thực sự dịch nó thành ASCII, sau đó nó thực sự rõ hết sức giận dữ. Ở đây chúng tôi có một cấu trúc cho một tập tin mã hóa Huffman. Có tất cả các đặc tính liên kết với một tập tin Huff. Sau đó xuống đây chúng tôi có tiêu đề cho một tập tin Huff, vì vậy chúng tôi gọi nó Huffeader thay vì thêm h thêm bởi vì nó nghe như vậy anyway. Cute. Chúng tôi có một con số kỳ diệu liên kết với nó. Nếu nó là một tập tin thực tế Huff, nó sẽ là số lượng lên trên, ma thuật này. Và sau đó nó sẽ có một mảng. Vì vậy, cho mỗi biểu tượng, trong đó có 256, nó sẽ liệt kê những gì tần số của những biểu tượng trong các tập tin Huff. Và cuối cùng, chúng tôi có một tổng kiểm tra cho các tần số, mà phải là tổng của những tần số. Vì vậy, đó những gì Huffeader một. Sau đó, chúng tôi có một số chức năng trả lại các bit tiếp theo trong tập tin Huff cũng như viết một chút để các tập tin Huff, và sau đó chức năng này ở đây, hfclose, mà thực sự đóng file Huff. Trước đây, chúng tôi đã giao dịch với thẳng chỉ fclose, nhưng khi bạn có một tập tin Huff, thay vì fclosing nó những gì bạn đang thực sự sẽ làm hfclose và hfopen nó. Đó là những chức năng cụ thể để các tập tin Huff rằng chúng ta sẽ được giao dịch với. Sau đó, ở đây chúng tôi đọc trong tiêu đề và sau đó viết các tiêu đề. 

Chỉ bằng cách đọc file. H, chúng ta có thể loại được một cảm giác của những gì một tập tin Huff có thể là, những đặc điểm nào nó có, mà không thực sự đi sâu vào các huffile.c, đó, nếu chúng ta đi sâu vào, là có được một chút phức tạp hơn. Nó có tất cả các tập tin I / O ở đây đối phó với con trỏ. Ở đây chúng ta thấy rằng khi chúng ta gọi hfread, ví dụ, nó vẫn còn đối phó với fread. Chúng tôi không nhận được thoát khỏi những chức năng hoàn toàn, nhưng chúng tôi đang gửi những người được chăm sóc bên trong các tập tin Huff thay vì làm tất cả nó chính mình. Bạn có thể cảm thấy tự do để quét qua này nếu bạn đang tò mò và đi và bóc lớp lại một chút. 

Các tập tin tiếp theo mà chúng ta sẽ xem xét là tree.h. Trước đây trong Walkthrough các trang trình bày, chúng tôi nói rằng chúng tôi mong đợi một nút Huffman và chúng tôi đã thực hiện một nút typedef struct. Chúng tôi mong đợi nó để có một biểu tượng, một tần số, và sau đó 2 sao nút. Trong trường hợp này, những gì chúng tôi đang làm điều này về cơ bản là giống nhau ngoại trừ thay vì nút, chúng ta sẽ gọi cho họ cây. Chúng tôi có một chức năng mà khi bạn gọi làm cho cây nó sẽ trả về cho bạn một con trỏ cây. Sao Speller, khi bạn đã làm cho một nút mới bạn nói nút * mới từ = malloc (sizeof) và vật như thế. Về cơ bản, mktree sẽ được giao dịch với điều đó cho bạn. Tương tự như vậy, khi bạn muốn loại bỏ một cây, do đó về cơ bản giải phóng cây khi bạn đang thực hiện với nó, thay vì rõ ràng gọi miễn phí trên đó, bạn đang thực sự chỉ sẽ sử dụng chức năng rmtree nơi bạn vượt qua trong con trỏ cây đó và sau đó tree.c sẽ chăm sóc việc đó cho bạn. 

Chúng tôi nhìn vào tree.c. Chúng tôi hy vọng các chức năng tương tự, ngoại trừ thực hiện như. Như chúng ta mong đợi, khi bạn gọi mktree mallocs các kích thước của một cái cây vào một con trỏ, khởi tạo tất cả các giá trị với giá trị NULL, do đó, số 0 hoặc NULLs, và sau đó trả về con trỏ cây mà bạn vừa malloc'd cho bạn. Khi bạn gọi loại bỏ cây đầu tiên nó làm cho chắc chắn rằng bạn không tăng gấp đôi giải phóng. Nó làm cho chắc chắn rằng bạn thực sự có một cây mà bạn muốn loại bỏ. Ở đây vì một cái cây cũng bao gồm trẻ em, điều này không có gì nó đệ quy gọi loại bỏ cây vào nút bên trái của cây cũng như các nút bên phải. Trước khi giải phóng phụ huynh, nó cần để giải thoát cho trẻ em là tốt. Cha mẹ cũng là hoán đổi cho nhau với gốc. Lần đầu tiên cha mẹ, như vậy giống như great-great-great-great-ông nội hoặc bà cây, đầu tiên chúng ta để giải phóng các cấp độ đầu tiên. Vì vậy, đi qua phía dưới, miễn phí đó, và sau đó quay lại, miễn phí những người, vv Vì vậy, đó là cây. 

Bây giờ chúng ta nhìn vào rừng. Rừng là nơi mà bạn đặt tất cả các cây của bạn Huffman. Nó nói rằng chúng ta sẽ có một cái gì đó được gọi là một âm mưu có chứa một con trỏ đến một cái cây cũng như một con trỏ đến một âm mưu tiếp theo. Được cấu trúc thực hiện điều này loại trông giống như? Nó loại nói nó ở đó. Ngay trên đây. Một danh sách liên kết. Chúng ta thấy rằng khi chúng ta có một âm mưu nó giống như một danh sách liên kết của các lô. Rừng được định nghĩa như là một danh sách liên kết của các lô, và do đó, cấu trúc rừng là chúng ta chỉ có một con trỏ đến âm mưu đầu tiên của chúng tôi và cốt truyện mà có một cây bên trong nó hay đúng hơn là chỉ vào một cái cây và sau đó chỉ đến cốt truyện tiếp theo, vv và vv. Để làm cho một khu rừng, chúng tôi gọi mkforest. Sau đó, chúng tôi có một số chức năng khá hữu ích ở đây. Chúng tôi có chọn nơi bạn vượt qua trong một khu rừng và sau đó giá trị trả về là một * Tree, một con trỏ vào một cái cây. Chọn sẽ làm là nó sẽ đi vào rừng mà bạn đang trỏ đến sau đó loại bỏ một cây với tần số thấp nhất từ ​​rừng và sau đó cung cấp cho bạn con trỏ đến cây đó. Một khi bạn gọi chọn, cây sẽ không tồn tại trong rừng nữa, nhưng giá trị trả lại là con trỏ đến cây đó. Sau đó, bạn có nhà máy. Với điều kiện là bạn vượt qua trong một con trỏ đến một cây có một tần số không-0, những gì nhà máy sẽ làm là nó sẽ mất rừng, cây, và trồng cây bên trong rừng. Ở đây chúng tôi có rmforest. Tương tự như loại bỏ cây, mà cơ bản đã giải phóng tất cả các cây của chúng tôi cho chúng tôi, loại bỏ rừng sẽ miễn phí tất cả mọi thứ có trong rừng. 

Nếu chúng ta nhìn vào forest.c, chúng tôi sẽ mong đợi để xem ít nhất 1 lệnh rmtree trong đó, bởi vì bộ nhớ miễn phí trong rừng nếu một khu rừng có cây ở trong đó, sau đó cuối cùng bạn sẽ phải để loại bỏ những cây quá. Nếu chúng ta nhìn vào forest.c, chúng tôi có mkforest của chúng tôi, như chúng ta mong đợi. Chúng tôi điều malloc. Chúng tôi khởi tạo các âm mưu đầu tiên trong rừng như NULL bởi vì đó là sản phẩm nào để bắt đầu với, sau đó chúng ta thấy lựa chọn, mà trả về cây với trọng lượng thấp nhất, tần số thấp nhất, và sau đó được loại bỏ nút cụ thể đó là điểm đến cây đó và là một trong những tiếp theo, do đó, nó mất rằng danh sách liên kết của rừng. Và sau đó ở đây chúng tôi có nhà máy, chèn một cây vào danh sách liên kết. Rừng không là nó độc đáo giúp nó được sắp xếp cho chúng tôi. Và cuối cùng, chúng tôi có rmforest, và như mong đợi, chúng tôi có rmtree gọi là có. 

Nhìn vào mã phân phối cho đến nay, huffile.c có lẽ đến nay là khó khăn nhất để hiểu, trong khi các tập tin khác tự khá đơn giản để làm theo. Với kiến ​​thức của chúng ta về con trỏ và danh sách liên kết và như vậy, chúng tôi đã có thể theo dõi khá tốt. Nhưng tất cả chúng ta cần phải thực sự chắc chắn rằng chúng tôi hoàn toàn hiểu là H tập tin. bởi vì bạn cần phải được kêu gọi những chức năng, đối phó với những giá trị trở lại, do đó hãy chắc chắn rằng bạn hoàn toàn hiểu những hành động sẽ được thực hiện bất cứ khi nào bạn gọi một trong những chức năng. Nhưng trên thực tế sự hiểu biết bên trong của nó không phải là khá cần thiết bởi vì chúng tôi có những tập tin h. Chúng tôi có thêm 2 tập tin còn lại trong mã phân phối của chúng tôi. 

Chúng ta hãy nhìn vào bãi. Đổ bởi bình luận của mình ở đây có một tập tin Huffman nén và sau đó dịch và bãi tất cả các nội dung của nó. Ở đây chúng ta thấy rằng nó gọi hfopen. Đây là loại phản ánh nộp * input = fopen, và sau đó bạn vượt qua trong thông tin. Nó gần như giống hệt nhau ngoại trừ thay vì một tập tin * bạn đang đi trong một Huffile; thay vì fopen bạn đang đi qua hfopen. Ở đây chúng ta đọc trong tiêu đề đầu tiên, là loại tương tự như làm thế nào chúng ta đọc trong tiêu đề cho một tập tin bitmap. Những gì chúng tôi đang làm ở đây là kiểm tra để xem liệu thông tin tiêu đề chứa con số kỳ diệu bên phải chỉ ra rằng nó là một tập tin thực tế Huff, sau đó tất cả các kiểm tra để đảm bảo rằng các tập tin mà chúng ta mở cửa là một tập tin huffed thực tế hay không. Điều này không có kết quả đầu ra các tần số của tất cả các biểu tượng mà chúng ta có thể nhìn thấy trong một thiết bị đầu cuối vào một bảng đồ họa. Điều này một phần là sẽ có ích. Nó có một chút và đọc bit by bit vào bit biến và sau đó in nó ra. Vì vậy, nếu tôi được là để gọi bãi chứa trên hth.bin, đó là kết quả của huffing một file bằng cách sử dụng các giải pháp nhân viên, tôi sẽ nhận được điều này. Nó xuất ra tất cả các ký tự và sau đó đặt tần số mà chúng xuất hiện. Nếu chúng ta nhìn, hầu hết trong số họ là 0 trừ trường hợp này: H, xuất hiện hai lần, và sau đó T, xuất hiện một lần. Và sau đó ở đây chúng tôi có tin nhắn thực tế trong 0 và 1. Nếu chúng ta nhìn tại hth.txt, mà có lẽ là thông điệp ban đầu đã được gắt gỏng, chúng tôi mong đợi để xem một số Hs và Ts trong đó. Cụ thể, chúng tôi mong đợi để xem chỉ 1 T và Hs 2. Ở đây chúng tôi đang trong hth.txt. Nó thực sự có HTH. Bao gồm trong đó, mặc dù chúng tôi không thể nhìn thấy nó, là một ký tự xuống dòng. Huff tập tin hth.bin cũng được mã hóa các ký tự xuống dòng là tốt. Ở đây bởi vì chúng ta biết rằng bộ này là HTH và sau đó xuống dòng, chúng ta có thể thấy rằng có lẽ H được đại diện bởi chỉ duy nhất 1 và sau đó T có lẽ là 01 và sau đó H tiếp theo là 1 cũng và sau đó chúng tôi có một dòng mới được chỉ định bởi hai 0s. Cool. 

Và cuối cùng, bởi vì chúng ta đang đối phó với nhiều c và h tập tin, chúng ta sẽ có một cuộc tranh luận khá phức tạp để trình biên dịch, và do đó, ở đây chúng tôi có một Makefile mà làm cho đổ cho bạn. Nhưng trên thực tế, bạn có để đi về làm tập tin riêng puff.c của bạn. Makefile thực sự không đối phó với việc puff.c cho bạn. Chúng tôi rời khỏi đó vào bạn để chỉnh sửa các Makefile. Khi bạn nhập một lệnh như thế làm cho tất cả, ví dụ, nó sẽ làm cho tất cả chúng cho bạn. Hãy nhìn vào các ví dụ về Makefile từ pset qua cũng như đi tắt của một trong những điều này để xem làm thế nào bạn có thể có thể làm cho tập tin Puff của bạn bằng cách chỉnh sửa Makefile. Đó là về nó cho các mã phân phối của chúng tôi. 

Một khi chúng tôi đã nhận được thông qua đó, thì đây chỉ là một lời nhắc nhở làm thế nào chúng ta sẽ đối phó với các nút Huffman. Chúng tôi sẽ không gọi họ là các nút nữa, chúng ta sẽ gọi họ là cây nơi mà chúng tôi đang đi để được đại diện cho biểu tượng của họ với một char, tần số của họ, số lần xuất hiện, với một số nguyên. Chúng tôi đang sử dụng mà bởi vì nó chính xác hơn một phao. Và sau đó chúng tôi có một con trỏ trỏ tới con trái cũng như đứa trẻ phải. Rừng A, như chúng ta đã thấy, chỉ là một danh sách liên kết của cây. Cuối cùng, khi chúng tôi đang xây dựng của chúng tôi tập tin Huff, chúng tôi muốn rừng của chúng tôi có chứa chỉ có 1 cây - 1 cây, 1 root với nhiều con. Trước đó chúng tôi đã chỉ làm cho cây Huffman của chúng tôi, chúng tôi bắt đầu bằng cách đặt tất cả các nút trên màn hình của chúng tôi và nói rằng chúng ta sẽ có các nút này, cuối cùng chúng ta sẽ là những chiếc lá, và điều này là biểu tượng của họ, đây là tần số của họ. Trong rừng của chúng ta nếu chúng ta chỉ có 3 chữ cái, đó là một khu rừng của 3 cây. Và sau đó khi chúng tôi đi, khi chúng ta thêm phụ huynh đầu tiên, chúng tôi đã thực hiện một rừng cây xanh 2 bên. Chúng tôi loại bỏ 2 trong số những trẻ em từ rừng của chúng tôi và sau đó thay thế nó bằng một nút cha có những 2 nút như trẻ em. Và cuối cùng, bước cuối cùng của chúng tôi với ví dụ của chúng ta với As, Bs, và Cs sẽ làm cho cha mẹ cuối cùng, và như vậy thì đó sẽ mang lại tổng số cây trong rừng 1. Tất cả mọi người xem như thế nào bạn bắt đầu với nhiều cây trong rừng của bạn và kết thúc với 1? Okay. Cool. 

Những gì chúng tôi cần phải làm cho Puff? Những gì chúng ta cần làm là đảm bảo rằng, như mọi khi, họ cung cấp cho chúng tôi đúng loại đầu vào để chúng tôi thực sự có thể chạy chương trình. Trong trường hợp này chúng ta sẽ được cho chúng tôi sau khi lập luận của họ dòng lệnh đầu tiên Thêm 2 tập tin mà chúng tôi muốn để giải nén và sản lượng của các tập tin giải nén. Nhưng một khi chúng tôi chắc chắn rằng họ vượt qua chúng ta trong số tiền phải của giá trị, chúng tôi muốn đảm bảo rằng đầu vào là một tập tin Huff hay không. Và sau đó một khi chúng tôi đảm bảo rằng đó là một tập tin Huff, sau đó chúng tôi muốn xây dựng cây của chúng tôi, xây dựng cây như vậy mà nó phù hợp với cây mà người gửi tin nhắn được xây dựng. Sau đó, sau khi chúng tôi xây dựng cây, sau đó chúng tôi có thể đối phó với 0 và 1 mà họ đi qua theo những người dọc theo cây của chúng tôi bởi vì nó giống hệt nhau, và sau đó viết tin nhắn đó ra, giải thích các bit trở lại ký tự. Và sau đó ở cuối bởi vì chúng tôi đang làm việc với con trỏ ở đây, chúng tôi muốn đảm bảo rằng chúng tôi không có bất kỳ rò rỉ bộ nhớ và rằng chúng tôi tất cả mọi thứ miễn phí. 

Đảm bảo sử dụng thích hợp là chiếc mũ cũ cho chúng ta bây giờ. Chúng tôi có một đầu vào, mà là có được tên của tập tin để hơi, phùng, và sau đó chúng tôi chỉ định một đầu ra, do đó, tên của các tập tin cho đầu ra bỏng, mà sẽ được các tập tin văn bản. Đó là cách sử dụng. Và bây giờ chúng tôi muốn đảm bảo rằng đầu vào là gắt gỏng hay không. Nghĩ lại, đã có bất cứ điều gì trong mã phân phối có thể giúp chúng ta với sự hiểu biết cho dù một tập tin được gắt gỏng hay không? Có thông tin tại huffile.c về các Huffeader. Chúng ta biết rằng tất cả các tập tin Huff có một Huffeader liên kết với nó với một con số kỳ diệu cũng như một mảng của các tần số cho mỗi biểu tượng cũng như một tổng kiểm tra. Chúng ta biết rằng, nhưng chúng tôi cũng đã một peek tại dump.c, trong đó nó đã được đọc vào một tập tin Huff. Và để làm điều đó, phải kiểm tra xem liệu nó có thực sự gắt gỏng hay không. Vì vậy, có lẽ chúng ta có thể sử dụng dump.c như một cấu trúc cho puff.c. của chúng tôi Trở lại pset 4 khi chúng tôi đã có copy.c tập tin sao chép trong ba RGB và chúng tôi giải thích rằng cho Whodunit và Thay đổi kích thước, tương tự như vậy, những gì bạn có thể làm là chỉ cần chạy lệnh như cp dump.c puff.c và sử dụng một số mã có. Tuy nhiên, nó sẽ không phải là đơn giản của một quá trình để dịch dump.c của bạn vào puff.c, nhưng ít nhất nó cung cấp cho bạn một nơi nào đó để bắt đầu làm thế nào để đảm bảo rằng đầu vào là thực sự gắt gỏng hay không cũng như một số những thứ khác. Chúng tôi đã đảm bảo sử dụng đúng cách và đảm bảo rằng đầu vào là gắt gỏng. Mỗi thời gian mà chúng tôi đã thực hiện mà chúng tôi đã thực hiện kiểm tra lỗi thích hợp của chúng tôi, để quay trở lại và bỏ chức năng nếu thất bại một số xảy ra, nếu có một vấn đề. 

Bây giờ những gì chúng tôi muốn làm là xây dựng cây thực tế. Nếu chúng ta nhìn trong rừng, có 2 chức năng chính rằng chúng ta sẽ muốn trở nên rất quen thuộc với. Có nhà máy chức năng Boolean rằng thực vật không-0 tần số cây trong rừng của chúng tôi. Và do đó bạn vượt qua trong một con trỏ đến một khu rừng và một con trỏ vào một cái cây. Nhanh câu hỏi: Làm thế nào có nhiều rừng bạn sẽ có khi bạn đang xây dựng một cây Huffman Rừng của chúng tôi cũng giống như vải của chúng tôi, phải không? Vì vậy, chúng ta sẽ chỉ có 1 rừng, nhưng chúng tôi sẽ có nhiều cây. Vì vậy, trước khi bạn gọi thực vật, bạn có lẽ sẽ muốn làm cho hệ thống của mình. Có một lệnh cho rằng nếu bạn nhìn vào forest.h vào cách bạn có thể làm cho một khu rừng. Bạn có thể trồng một cây. Chúng tôi biết làm thế nào để làm điều đó. Và sau đó bạn cũng có thể chọn một cây từ rừng, loại bỏ một cây với trọng lượng thấp nhất và tạo cho bạn một con trỏ vào đó. Suy nghĩ lại khi chúng tôi đã làm ví dụ bản thân, khi chúng tôi đã vẽ nó ra, chúng tôi chỉ đơn giản là chỉ cần thêm các liên kết. Nhưng ở đây thay vì chỉ cần thêm các liên kết, nghĩ về nó hơn như bạn đang loại bỏ 2 của các nút và sau đó thay thế nó bằng một số khác. Để diễn tả về chọn và trồng, bạn chọn 2 cây và sau đó trồng một cây khác có những 2 cây mà bạn chọn như trẻ em. Để xây dựng cây Huffman, bạn có thể đọc trong các ký hiệu và tần số theo thứ tự vì Huffeader cho rằng đối với bạn, cung cấp cho bạn một loạt các tần số. Vì vậy, bạn có thể đi trước và chỉ cần bỏ qua bất cứ điều gì với 0 bởi vì chúng tôi không muốn 256 lá ở phần cuối của nó. Chúng tôi chỉ muốn số lượng lá là các ký tự đang thực sự được sử dụng trong tập tin. Bạn có thể đọc trong những biểu tượng, và mỗi của những biểu tượng có tần số không-0, những người sẽ là cây. Những gì bạn có thể làm là mỗi khi bạn đọc một ký hiệu tần số không-0, bạn có thể trồng cây trong rừng. Khi bạn trồng cây trong rừng, bạn có thể tham gia những cây là anh chị em ruột, như vậy sẽ trở lại để trồng và chọn nơi bạn chọn 2 và sau đó cây trồng 1, 1 mà bạn thực vật là mẹ của 2 con mà bạn chọn. Vì vậy, sau đó kết quả cuối cùng của bạn là có được một cây duy nhất trong forest của bạn. Đó là cách bạn xây dựng cây của bạn. 

Có một vài điều mà có thể đi sai ở đây bởi vì chúng tôi đang làm việc với cây mới và đối phó với con trỏ và vật như thế. Trước khi khi chúng tôi đang đối phó với con trỏ, bất cứ khi nào chúng ta malloc'd chúng tôi muốn để đảm bảo rằng nó đã không quay trở lại cho chúng ta một giá trị con trỏ NULL. Vì vậy, tại một vài bước trong quá trình này sẽ được một số trường hợp chương trình của bạn có thể thất bại. Những gì bạn muốn làm là bạn muốn làm cho chắc chắn rằng bạn xử lý những sai sót, và trong spec nó nói để xử lý chúng một cách duyên dáng, in ra một thông báo cho người sử dụng nói cho họ lý do tại sao chương trình để bỏ thuốc lá và sau đó nhanh chóng bỏ nó. Để làm điều này xử lý lỗi, hãy nhớ rằng bạn muốn kiểm tra xem nó mỗi lần duy nhất có thể là một thất bại. Mỗi lần duy nhất mà bạn đang thực hiện một con trỏ mới bạn muốn chắc chắn rằng đó là thành công. Trước những gì chúng tôi được sử dụng để làm là làm cho một con trỏ mới và malloc nó, và sau đó chúng tôi sẽ kiểm tra xem con trỏ đó là NULL. Vì vậy, sẽ có một số trường hợp mà bạn chỉ có thể làm điều đó, nhưng đôi khi bạn đang thực sự gọi một chức năng và trong phạm vi chức năng rằng, đó là một trong đó là làm mallocing. Trong trường hợp đó, nếu chúng ta nhìn lại một số chức năng trong các mã, một số người trong số họ là những chức năng Boolean. Trong trường hợp trừu tượng nếu chúng ta có một chức năng Boolean gọi là foo, về cơ bản, chúng ta có thể giả định rằng ngoài để làm bất cứ điều gì foo không, vì nó là một chức năng Boolean, nó trả về đúng hay sai - true nếu thành công, false nếu không. Vì vậy, chúng tôi muốn kiểm tra xem giá trị trả về của foo là đúng hay sai. Nếu nó sai, điều đó có nghĩa là chúng ta sẽ muốn in một số loại tin nhắn và sau đó thoát khỏi chương trình. Những gì chúng tôi muốn làm là kiểm tra giá trị trả về của foo. Nếu foo trả về false, sau đó chúng tôi biết rằng chúng tôi gặp phải một số loại lỗi và chúng ta cần phải từ bỏ chương trình của chúng tôi. Một cách để làm điều này là có một điều kiện mà chức năng thực tế bản thân là điều kiện của bạn. Nói foo mất trong x. Chúng tôi có thể có như là một điều kiện nếu (foo (x)). Về cơ bản, điều đó có nghĩa là nếu ở cuối thực hiện foo nó trả về true, sau đó chúng ta có thể làm điều này bởi vì chức năng đã đánh giá foo để đánh giá tình trạng toàn bộ. Vì vậy, sau đó đó là cách bạn có thể làm một cái gì đó nếu hàm trả về đúng sự thật và là thành công. Nhưng khi bạn kiểm tra lỗi, bạn chỉ muốn bỏ thuốc lá nếu chức năng của bạn trả về false. Những gì bạn có thể làm được chỉ cần thêm một == false hoặc chỉ cần thêm một tiếng nổ ở phía trước của nó và sau đó bạn có (foo). Trong cơ thể của tình trạng đó, bạn sẽ có tất cả các xử lý lỗi, thích, "Không thể tạo ra cây này" và sau đó trở lại 1 hoặc một cái gì đó như thế. Điều đó không có gì, mặc dù, là mặc dù foo trở lại sai - Nói foo trả về true. Sau đó, bạn không cần phải gọi foo một lần nữa. Đó là một quan niệm sai lầm phổ biến. Bởi vì nó là ở trong tình trạng của bạn, nó đã được đánh giá, vì vậy bạn đã có kết quả, nếu bạn đang sử dụng làm cho cây hoặc một cái gì đó như thế hoặc thực vật hoặc chọn một cái gì đó hoặc. Nó đã có giá trị đó. Nó đã được thực hiện. Vì vậy, nó rất hữu ích để sử dụng các chức năng Boolean là điều kiện vì hay không, bạn thực sự thực hiện cơ thể của vòng lặp, thực hiện chức năng anyway. 

Thứ hai bước cuối cùng là viết tin nhắn vào tập tin. Một khi chúng ta xây dựng cây Huffman, sau đó có văn bản thông báo đến tập tin khá đơn giản. Nó khá đơn giản, chỉ cần làm theo các số 0 và 1. Và do đó, theo quy ước chúng ta biết rằng trong một cây Huffman số 0 chỉ ra trái và 1s cho thấy đúng. Vì vậy, sau đó nếu bạn đọc trong từng chút một, mỗi khi bạn nhận được một 0 bạn sẽ làm theo các chi nhánh bên trái, và sau đó mỗi khi bạn đọc một 1 bạn sẽ thực hiện theo các chi nhánh phải. Và sau đó bạn sẽ tiếp tục cho đến khi bạn nhấn một chiếc lá bởi vì lá sẽ được vào cuối của các ngành. Làm thế nào chúng ta có thể nói cho dù chúng tôi đã đạt một chiếc lá hay không? Chúng tôi đã nói trước đây. [Sinh viên] Nếu các con trỏ NULL. >> Yeah. Chúng tôi có thể cho biết nếu chúng tôi đã trúng một lá nếu các con trỏ đến cây cả hai bên trái và phải là NULL. Hoàn hảo. Chúng ta biết rằng chúng ta muốn đọc trong từng chút một vào tập tin Huff của chúng tôi. Như chúng ta đã thấy trước đây trong dump.c, những gì họ đã làm là họ đọc trong từng chút một vào tập tin Huff và chỉ in ra những bit. Chúng tôi sẽ không được làm điều đó. Chúng tôi sẽ làm một cái gì đó là một chút phức tạp hơn. Nhưng những gì chúng ta có thể làm là chúng ta có thể đi mà chút mã mà đọc vào các bit. Ở đây chúng tôi có các bit số nguyên đại diện cho bit hiện tại mà chúng ta đang ở trên. Này sẽ chăm sóc của iterating tất cả các bit trong tập tin cho đến khi bạn nhấn vào cuối của tập tin. Dựa vào đó, sau đó bạn sẽ muốn có một số loại iterator đi qua cây của bạn. Và sau đó dựa trên bit là 0 hoặc 1, bạn sẽ muốn hoặc di chuyển mà iterator bên trái hoặc di chuyển nó sang bên phải tất cả các cách cho đến khi bạn nhấn một chiếc lá, do đó, tất cả các cách cho đến khi mà nút mà bạn đang ở trên không trỏ đến các nút nữa. Tại sao chúng ta có thể làm điều này với một tập tin Huffman nhưng không mã Morse? Bởi vì trong mã Morse có một chút mơ hồ. Chúng tôi có thể được như thế, oh chờ đợi, chúng tôi đã trúng một lá thư trên đường đi, như vậy có lẽ đây là bức thư của chúng tôi, trong khi đó nếu chúng tôi tiếp tục lâu hơn một chút, sau đó chúng tôi đã đánh trúng một lá thư khác. Nhưng điều đó sẽ không xảy ra trong mã hóa Huffman, vì vậy chúng tôi có thể yên tâm rằng cách duy nhất mà chúng tôi đang đi để đạt đến một nhân vật là nếu trẻ em trái và bên phải của nút đó là NULL. 

Cuối cùng, chúng tôi muốn giải phóng tất cả các bộ nhớ của chúng tôi. Chúng tôi muốn cho cả hai gần các tập tin Huff mà chúng tôi đã được giao dịch với cũng như loại bỏ tất cả các cây trong rừng của chúng tôi. Dựa trên việc thực hiện của bạn, bạn có thể sẽ muốn gọi loại bỏ rừng thay vì thực sự đi qua tất cả các cây chính mình. Nhưng nếu bạn thực hiện bất kỳ cây tạm thời, bạn sẽ muốn giải phóng đó. Bạn biết mã của bạn tốt nhất, để bạn biết nơi bạn đang cấp phát bộ nhớ. Và vì vậy nếu bạn đi vào, bắt đầu bằng thậm chí kiểm soát f'ing cho malloc, nhìn thấy bất cứ khi nào bạn malloc và đảm bảo rằng bạn giải phóng tất cả những điều đó nhưng sau đó chỉ cần đi qua mã của bạn, sự hiểu biết nơi bạn có thể cấp phát bộ nhớ. Thông thường, bạn chỉ có thể nói, "Vào cuối của một tập tin tôi chỉ cần đi để loại bỏ rừng về rừng của tôi," do đó, về cơ bản rõ ràng rằng bộ nhớ, miễn phí mà "Và sau đó tôi cũng sẽ phải đóng tập tin và sau đó chương trình của tôi sẽ bỏ thuốc lá." Nhưng là thời gian duy nhất mà chương trình của bạn bỏ? Không, bởi vì đôi khi có thể có được một lỗi đã xảy ra. Có lẽ chúng ta không có thể mở một tập tin hoặc chúng tôi không thể thực hiện một cây hoặc một số loại lỗi xảy ra trong quá trình cấp phát bộ nhớ và vì vậy nó trở về NULL. Một lỗi đã xảy ra và sau đó chúng tôi trở về và bỏ thuốc lá. Vì vậy, sau đó bạn muốn để đảm bảo rằng bất cứ lúc nào có thể là chương trình của bạn có thể bỏ thuốc lá, bạn muốn giải phóng tất cả bộ nhớ của bạn có. Nó không chỉ là ở cuối của các chức năng chính mà bạn bỏ mã của bạn. Bạn muốn nhìn lại mọi trường hợp rằng mã của bạn có khả năng có thể trở lại sớm và sau đó bộ nhớ bất cứ điều gì miễn phí có ý nghĩa. Nói rằng bạn đã được gọi là rừng và trở lại sai. Sau đó, bạn có thể sẽ không cần phải loại bỏ rừng của bạn bởi vì bạn không có một khu rừng. Tuy nhiên, ở mỗi điểm trong mã nơi bạn có thể trở lại sớm bạn muốn làm cho chắc chắn rằng bạn tự do bất kỳ bộ nhớ có thể. 

Vì vậy, khi chúng tôi đang làm việc với giải phóng bộ nhớ và có tiềm năng rò rỉ, chúng tôi muốn không chỉ sử dụng bản án của chúng tôi và logic của chúng tôi mà còn sử dụng Valgrind để xác định liệu chúng tôi đã giải phóng tất cả các bộ nhớ của chúng tôi đúng hay không. Bạn có thể chạy Valgrind trên Puff và sau đó bạn cũng phải vượt qua nó số bên phải của đối số dòng lệnh để Valgrind. Bạn có thể chạy, nhưng đầu ra là một chút khó hiểu. Chúng tôi đã nhận được một bit được sử dụng nó với Speller, nhưng chúng tôi vẫn cần sự giúp đỡ nhiều hơn một chút, vì vậy sau đó chạy nó với một vài lá cờ như rò rỉ kiểm tra = đầy đủ, mà có lẽ sẽ cung cấp cho chúng tôi một số đầu ra hữu ích hơn trên Valgrind. 

Sau đó, một mẹo hữu ích khi bạn gỡ lỗi là lệnh khác. Bạn có thể truy cập thực hiện của đội ngũ nhân viên Huff, chạy vào một tập tin văn bản, và sau đó đầu ra nó vào một tập tin nhị phân, một tập tin nhị phân Huff, được cụ thể. Sau đó, nếu bạn chạy phun của riêng bạn trên đó tập tin nhị phân, sau đó lý tưởng, outputted tập tin văn bản của bạn là có được giống hệt nhau một trong những ban đầu mà bạn đã thông qua. Ở đây tôi đang sử dụng hth.txt làm ví dụ, và đó là một trong những nói đến trong spec của bạn. Đó là nghĩa đen chỉ HTH và sau đó một dòng mới. Nhưng chắc chắn cảm thấy miễn phí và bạn có chắc chắn khuyến khích sử dụng các ví dụ dài hơn cho các tập tin văn bản của bạn. 

Bạn thậm chí có thể mất một shot tại có thể nén và sau đó giải nén một số các tập tin mà bạn đã sử dụng trong Speller như Chiến tranh và Hòa bình Jane Austen hoặc một cái gì đó như thế - đó sẽ là loại mát hoặc Austin Powers, loại đối phó với các tập tin lớn hơn bởi vì chúng tôi sẽ không đi xuống đến nó nếu chúng ta sử dụng các công cụ tiếp theo đây, ls-l. Chúng tôi đang sử dụng để ls, mà về cơ bản liệt kê tất cả các nội dung trong thư mục hiện tại của chúng tôi. Đi qua trong l-cờ thực sự hiển thị kích thước của các tập tin. Nếu bạn đi qua spec pset, nó thực sự bạn đi qua việc tạo ra các tập tin nhị phân, huffing nó, và bạn thấy rằng đối với các tập tin rất nhỏ chi phí không gian của nén và dịch tất cả các thông tin đó của tất cả các tần số và vật như thế có giá trị hơn lợi ích thực tế nén các tập tin ở nơi đầu tiên. Nhưng nếu bạn chạy nó trên một số tập tin văn bản dài hơn, sau đó bạn có thể thấy rằng bạn bắt đầu để có được một số lợi ích trong quá trình nén các tập tin. 

Và cuối cùng, chúng tôi có GDB cũ của bạn thân của chúng tôi, chắc chắn sẽ có ích quá. 

Chúng ta có bất kỳ câu hỏi trên Huff cây hoặc quá trình có thể làm cho cây hoặc bất kỳ câu hỏi về Huff'n Puff? Okay. Tôi sẽ ở lại xung quanh một chút. 

Cảm ơn, tất cả mọi người. Walkthrough 6. Và chúc may mắn. 

[CS50.TV]