JASON Hirschhorn: Chào mừng tất cả mọi người với mục Bảy. Chúng tôi đang trong tuần bảy của khóa học. Và thứ năm sắp tới Halloween là vì vậy tôi mặc quần áo lên như một quả bí ngô. Tôi không thể cúi xuống và đưa vào đôi giày của tôi, vì vậy đó là lý do tại sao tôi chỉ mang vớ. Tôi cũng không mặc bất cứ thứ gì dưới này, vì vậy tôi không thể lấy nó ra nếu nó mất tập trung cho bạn. Tôi xin lỗi trước cho điều đó. Bạn không cần phải tưởng tượng những gì đang xảy ra. Tôi đang mặc quần đùi. Vì vậy, đó là tất cả tốt. 

Tôi có một câu chuyện dài về lý do tại sao tôi ăn mặc như một quả bí ngô, nhưng tôi sẽ tiết kiệm mà cho sau trong phần này bởi vì tôi muốn bắt đầu. Chúng tôi có rất nhiều điều thú vị đi qua trong tuần này. Hầu hết trong số họ liên quan trực tiếp đến điều này bộ vấn đề của tuần, lỗi chính tả. Chúng ta sẽ được đi qua liên kết danh sách và bảng băm cho toàn bộ phần. Tôi đưa danh sách này lên mỗi tuần, một danh sách các nguồn lực cho bạn để giúp bạn với các tài liệu về khóa học này. Nếu thua lỗ hoặc nếu tìm kiếm một số thêm thông tin, kiểm tra một trong các nguồn tài nguyên. 

Một lần nữa, pset6 là lỗi chính tả, pset trong tuần này. Và nó cũng khuyến khích bạn, và tôi khuyến khích các bạn, sử dụng một số khác nguồn lực đặc biệt cho pset này. Đặc biệt, ba tôi đã được liệt kê trên màn hình - gdb, mà chúng tôi đã quen thuộc với và được sử dụng trong một thời gian bây giờ, là sẽ rất hữu ích trong tuần này. Vì vậy, tôi đặt ở đây. Nhưng bất cứ khi nào bạn đang làm việc với C, bạn nên luôn luôn sử dụng gdb để debug chương trình của bạn. Tuần này cũng valgrind. Không ai biết những gì valgrind không? 

ĐỐI TƯỢNG: Nó kiểm tra rò rỉ bộ nhớ? 

JASON Hirschhorn: Valgrind kiểm tra xem có rò rỉ bộ nhớ. Vì vậy, nếu bạn malloc một cái gì đó trong bạn chương trình, bạn đang yêu cầu bộ nhớ. Vào cuối chương trình của bạn, bạn có viết miễn phí trên tất cả mọi thứ bạn đã malloced để cung cấp cho bộ nhớ trở lại. Nếu bạn không viết tự do ở cuối và chương trình của bạn đến một kết luận, tất cả mọi thứ sẽ tự động được giải phóng. Và cho các chương trình nhỏ, đó là một thỏa thuận không phải là lớn. Nhưng nếu bạn đang viết một chạy lâu hơn chương trình mà không bỏ thuốc lá, nhất thiết, trong một vài phút hoặc một vài giây, sau đó rò rỉ bộ nhớ có thể trở thành một việc rất lớn. 

Vì vậy, cho pset6, kỳ vọng là bạn sẽ có không rò rỉ bộ nhớ với chương trình của bạn. Để kiểm tra rò rỉ bộ nhớ, chạy valgrind và nó sẽ cung cấp cho bạn một số đẹp đầu ra cho bạn biết liệu hay không tất cả mọi thứ được tự do. Chúng tôi sẽ thực hành với nó sau này hôm nay, hy vọng. 

Cuối cùng, các lệnh khác. Bạn sử dụng một cái gì đó tương tự với nó trong pset5 với công cụ peek. Cho phép bạn nhìn vào bên trong. Bạn cũng sử dụng khác cũng vậy, mỗi vấn đề đặt spec. Nhưng trong cho phép bạn so sánh hai tập tin. Bạn có thể so sánh các tập tin bitmap và tiêu đề thông tin của một giải pháp nhân viên và giải pháp của bạn trong pset5 nếu bạn đã chọn để sử dụng nó. Khác sẽ cho phép bạn làm điều đó, là tốt. Bạn có thể so sánh câu trả lời chính xác cho vấn đề của tuần này thiết lập để câu trả lời của bạn và xem nếu nó dòng lên hoặc nhìn thấy chỗ nào bị lỗi. 

Vì vậy, những người đang có ba công cụ tốt mà bạn nên sử dụng trong tuần này, và chắc chắn kiểm tra chương trình của bạn với ba công cụ trước khi chuyển nó vào Một lần nữa, như tôi đã đề cập mỗi tuần, nếu bạn có bất kỳ thông tin phản hồi cho tôi - cả hai tích cực và mang tính xây dựng - cảm thấy tự do để đi đến trang web ở dưới cùng của slide này và đầu vào nó ở đó. Tôi thực sự đánh giá cao sự và tất cả các thông tin phản hồi. Và nếu bạn cung cấp cho tôi những điều cụ thể mà Tôi có thể làm gì để cải thiện hoặc rằng tôi làm tốt mà bạn muốn tôi tiếp tục, tôi đi mà trái tim và thực sự cố gắng hết sức để lắng nghe phản hồi của bạn. Tôi không thể hứa tôi sẽ làm tất cả mọi thứ, tuy nhiên, giống như mặc một bí ngô trang phục mỗi tuần. 

Vì vậy, chúng tôi sẽ dành phần lớn phần, như tôi đã đề cập, nói về danh sách liên kết và bảng băm, mà sẽ được áp dụng trực tiếp vào vấn đề thiết lập trong tuần này. Danh sách liên kết, chúng tôi sẽ đi qua tương đối một cách nhanh chóng bởi vì chúng tôi đã dành một chút công bằng thời gian đi qua nó trong phần. Và vì vậy chúng tôi sẽ nhận được thẳng vào mã hóa vấn đề cho danh sách liên kết. Và sau đó cuối cùng chúng tôi sẽ nói về băm bảng và làm thế nào họ được áp dụng cho vấn đề tuần thiết lập. 

Bạn đã nhìn thấy mã này trước đây. Đây là một cấu trúc, và nó được xác định một cái gì đó mới được gọi là một nút. Và bên trong một nút có một số nguyên ngay tại đây và có một con trỏ đến một nút khác. Chúng tôi đã nhìn thấy điều này trước đây. Điều này đã được sắp lên cho một vài tuần nay. Nó kết hợp con trỏ, và chúng tôi luôn làm việc với, và cấu trúc, cho phép chúng ta kết hợp hai khác nhau mọi thứ vào một loại dữ liệu. 

Có rất nhiều đang xảy ra trên màn hình. Nhưng tất cả của nó cần được tương đối quen thuộc với bạn. Trên dòng đầu tiên, chúng tôi khai báo một nút mới. Và bên trong có nút mới, tôi đặt số nguyên trong nút đó để một. Chúng ta thấy trên dòng tiếp theo, tôi đang làm một printf lệnh, nhưng tôi đã chuyển sang màu xám lệnh printf vì thực sự Phần quan trọng là dòng này đây - new_node.n. Không chấm có nghĩa là gì? 

ĐỐI TƯỢNG: Đi về nút và đánh giá giá trị n cho nó. 

JASON Hirschhorn: Đó là chính xác. Chấm có nghĩa là truy cập vào phần n của nút mới này. Dòng tiếp theo này làm gì? Michael. 

ĐỐI TƯỢNG: Nó tạo ra một nút khác mà sẽ trỏ đến nút mới. 

JASON Hirschhorn: Vì vậy, nó không tạo ra một nút mới. Nó tạo ra một cái gì? 

ĐỐI TƯỢNG: Một con trỏ. 

JASON Hirschhorn: Một con trỏ tới một nút, như được chỉ ra bởi nút này * đây. Vì vậy, nó tạo ra một con trỏ tới một nút. Và đó nút là nó chỉ để, Michael? 

ĐỐI TƯỢNG: nút mới? 

JASON Hirschhorn: nút New. Và nó chỉ có bởi vì chúng tôi đã cho nó địa chỉ của nút mới. Và bây giờ trong dòng này, chúng ta thấy hai cách khác nhau thể hiện điều tương tự. Và tôi muốn chỉ ra làm thế nào những hai điều đều giống nhau. Trong dòng đầu tiên, chúng tôi tới đích con trỏ. Vì vậy, chúng tôi đi đến nút. Đó là những gì có nghĩa là ngôi sao này. Chúng tôi đã nhìn thấy rằng trước với con trỏ. Tới nút đó. Đó là trong dấu ngoặc đơn. Và sau đó truy cập thông qua các dấu chấm các yếu tố n của nút đó. 

Vì vậy, đó là tham gia các cú pháp chúng ta đã thấy ngay tại đây và bây giờ sử dụng nó với một con trỏ. Tất nhiên, nó được loại bận rộn nếu bạn đang viết những dấu ngoặc đơn - ngôi sao và dấu chấm đó. Nó được một chút bận rộn. Vì vậy, chúng tôi có một số cú pháp đường. Và dòng này ngay tại đây - ptr_node-> n. Điều đó không chính xác. Vì vậy, hai dòng mã là tương đương và sẽ làm cùng một điều chính xác. 

Nhưng tôi muốn chỉ những người ra trước chúng tôi đi thêm nữa để bạn hiểu mà thực sự điều này đúng ở đây là cú pháp đường cho dereferencing con trỏ và sau đó sẽ n một phần của cấu trúc đó. Thắc mắc về slide này? OK. 

Vì vậy, chúng ta sẽ đi qua một vài các hoạt động mà bạn có thể làm trên danh sách liên kết. Một danh sách liên kết, thu hồi, là một loạt các các nút trỏ đến nhau. Và chúng tôi thường bắt đầu với một con trỏ được gọi là người đứng đầu, nói chung, mà điểm đến điều đầu tiên trong danh sách. Vì vậy, trên dòng đầu tiên ở đây, chúng tôi có L ban đầu của chúng tôi đầu tiên. Vì vậy, điều mà bạn có thể nghĩ đến - điều này văn bản ngay tại đây bạn có thể nghĩ như chỉ con trỏ chúng tôi đã được lưu trữ ở đâu đó rằng điểm đến các yếu tố đầu tiên. Và trong danh sách liên kết này chúng tôi có bốn nút. Mỗi nút là một hộp lớn. Hộp lớn hơn bên trong lớn hộp là một phần số nguyên. Và sau đó chúng tôi có một phần con trỏ. 

Những hộp không được rút ra để quy mô lớn như thế nào bởi vì là một số nguyên trong byte? Lớn như thế nào bây giờ? Bốn. Và lớn như thế nào là một con trỏ? Bốn. Vì vậy, thực sự, nếu chúng ta rút ra này để mở rộng cả hai hộp sẽ có cùng kích thước. Trong trường hợp này, chúng tôi muốn chèn một cái gì đó vào danh sách liên kết. Vì vậy, bạn có thể thấy ở đây chúng tôi đang chèn Chúng tôi đi qua năm qua danh sách liên kết, tìm nơi mà năm đi, và sau đó chèn nó. 

Hãy phá vỡ đó và đi một chút chậm hơn. Tôi sẽ chỉ cho Ban. Vì vậy, chúng tôi có nút của chúng tôi năm đó chúng tôi đã tạo ra trong mallocs. Tại sao tất cả mọi người cười? Chỉ đùa thôi. OK. Vì vậy, chúng tôi đã malloced năm. Chúng tôi đã tạo ra nút này ở một nơi khác. Chúng tôi có nó sẵn sàng để đi. Chúng tôi bắt đầu ở phía trước danh sách của chúng tôi với hai. Và chúng tôi muốn chèn trong một thời trang được sắp xếp. 

Vì vậy, nếu chúng ta thấy hai và chúng tôi muốn đặt trong năm, chúng ta làm gì khi chúng ta thấy một cái gì đó ít hơn chúng tôi? Những gì? Chúng tôi muốn để chèn vào năm này danh sách liên kết, giữ cho nó được sắp xếp. Chúng ta thấy số hai. Vì vậy, chúng ta làm gì? Marcus? 

ĐỐI TƯỢNG: Hãy gọi cho con trỏ đến nút tiếp theo. 

JASON Hirschhorn: Và tại sao chúng tôi đi đến tiếp theo? 

ĐỐI TƯỢNG: Bởi vì đó là nút tiếp theo trong danh sách. Và chúng tôi chỉ biết rằng vị trí khác. 

JASON Hirschhorn: Và năm lớn hơn hai, đặc biệt. Bởi vì chúng tôi muốn giữ nó được sắp xếp. Vì vậy, năm lớn hơn hai. Vì vậy, chúng tôi chuyển sang kế tiếp. Và bây giờ chúng tôi đạt đến bốn. Và những gì sẽ xảy ra khi chúng ta đạt đến bốn? 

Năm lớn hơn bốn. Vì vậy, chúng tôi tiếp tục đi. Và bây giờ chúng tôi đang ở sáu. Và làm những gì chúng ta thấy ở sáu? Có, Carlos? 

ĐỐI TƯỢNG: Sáu lớn hơn năm. 

JASON Hirschhorn: Sáu là lớn hơn năm. Vì vậy, đó là nơi mà chúng ta muốn để chèn năm. Tuy nhiên, hãy nhớ rằng nếu chúng ta chỉ có một con trỏ ở đây - đây là con trỏ thêm của chúng tôi đó là đi ngang qua danh sách. Và chúng tôi chỉ đến sáu. Chúng tôi đã mất theo dõi những gì đến trước khi sáu. Vì vậy, nếu chúng ta muốn chèn một cái gì đó vào danh sách này giữ nó được sắp xếp, chúng tôi có lẽ cần phải có bao nhiêu con trỏ? 

ĐỐI TƯỢNG: Hai. 

JASON HIRSCHORN: Hai. Một để theo dõi các hiện một và một để theo dõi trước đó. Đây chỉ là một danh sách liên kết đơn lẻ. Nó chỉ đi một hướng. Nếu chúng ta có một danh sách liên kết kép, nơi tất cả mọi thứ đã được trỏ đến điều sau khi nó và điều trước đó, sau đó chúng tôi sẽ không cần phải làm điều đó. Nhưng trong trường hợp này chúng tôi không muốn để mất theo dõi những gì đi trước chúng ta trong trường hợp chúng ta cần phải chèn năm một nơi nào đó ở giữa. Nói chúng tôi đã chèn chín. Điều gì sẽ xảy ra khi chúng tôi có đến tám? 

ĐỐI TƯỢNG: Bạn sẽ phải nhận được rằng điểm null. Thay vì có điểm vô giá trị bạn muốn có để thêm một yếu tố và sau đó có nó trỏ đến chín. 

JASON HIRSCHORN: Chính xác. Vì vậy, chúng tôi nhận tám. Chúng tôi đến cuối danh sách bởi vì này được trỏ đến null. Và bây giờ, thay vì có nó trỏ đến vô giá trị, chúng tôi có nó trỏ đến nút mới của chúng tôi. Và chúng tôi đặt con trỏ trong nút mới của chúng tôi để null. Không ai có bất kỳ câu hỏi về chèn? Nếu tôi không quan tâm giữ danh sách được sắp xếp? 

ĐỐI TƯỢNG: Stick nó ở bắt đầu hoặc kết thúc. 

JASON HIRSCHORN: Stick nó tại đầu hoặc kết thúc. Mà một trong những chúng ta nên làm gì? Bobby? Tại sao kết thúc? 

ĐỐI TƯỢNG: Bởi vì đầu đã được lấp đầy. 

JASON HIRSCHORN: OK. Đầu đã được lấp đầy. Ai muốn tranh luận chống lại Bobby. Marcus. 

ĐỐI TƯỢNG: Vâng, bạn có thể muốn dính vào nó ngay từ đầu vì nếu không nếu bạn đặt nó ở kết thúc bạn phải đi qua toàn bộ danh sách. 

JASON HIRSCHORN: Chính xác. Vì vậy, nếu chúng ta đang suy nghĩ về thời gian chạy, thời gian chạy chèn ở cuối sẽ là n, kích thước này. O thời gian chạy lớn chèn là những gì ngay từ đầu? Thời gian liên tục. Vì vậy, nếu bạn không quan tâm về việc giữ gìn một cái gì đó sắp xếp, tốt hơn để chỉ chèn vào đầu danh sách này. Và có thể được thực hiện trong thời gian liên tục. 

OK. Hoạt động tiếp theo được tìm thấy, trong đó khác - chúng tôi đã diễn đạt này như tìm kiếm. Nhưng chúng ta sẽ xem xét thông qua danh sách liên kết cho một số đối tượng. Các bạn đã thấy mã cho tìm kiếm trước trong bài giảng. Nhưng chúng tôi loại chỉ cần làm nó với chèn, hoặc ít nhất là chèn một cái gì đó được sắp xếp. Bạn xem xét thông qua, sẽ nút bằng nút, cho đến khi bạn tìm thấy những con số đó bạn tìm kiếm. Điều gì xảy ra nếu bạn đạt cuối danh sách? Nói rằng tôi đang tìm chín và tôi đến cuối danh sách. Chúng ta phải làm gì? 

ĐỐI TƯỢNG: Quay trở lại sai? 

JASON HIRSCHORN: Trở về sai. Chúng tôi không tìm thấy nó. Nếu bạn đến cuối danh sách và bạn không tìm thấy số lượng bạn tìm kiếm, nó không phải ở đó. Bất kỳ câu hỏi về tìm? Nếu đây là một danh sách được sắp xếp, điều gì sẽ khác nhau để tìm kiếm của chúng tôi? Yeah. 

ĐỐI TƯỢNG: Nó sẽ tìm thấy giá trị đầu tiên đó là lớn hơn một trong những bạn đang tìm kiếm và sau đó trả về false. 

JASON HIRSCHORN: Chính xác. Vì vậy, nếu đó là một danh sách được sắp xếp, nếu chúng tôi nhận được một cái gì đó lớn hơn những gì chúng tôi đang tìm kiếm, chúng tôi không cần phải tiếp tục đi đến cuối danh sách. Chúng ta có thể tại thời điểm đó trả về false bởi vì chúng ta sẽ không tìm thấy nó. Câu hỏi là bây giờ, chúng tôi đã nói chuyện về giữ danh sách liên kết được sắp xếp, giữ cho chúng được phân loại. Đó sẽ là một cái gì đó bạn có lẽ sẽ phải suy nghĩ về khi mã hóa vấn đề thiết lập năm nếu bạn chọn một bảng băm với riêng chaining cách tiếp cận, mà chúng tôi sẽ nói về sau này. 

Nhưng nó có giá trị để giữ danh sách sắp xếp và sau đó có thể để có thể có tìm kiếm nhanh hơn? Hoặc là nó tốt hơn để nhanh chóng chèn một cái gì đó trong thời gian chạy liên tục nhưng sau đó có còn tìm kiếm? Đó là một sự cân bằng ngay đó mà bạn có thể quyết định những gì là thích hợp hơn cho vấn đề cụ thể của bạn. Và có không nhất thiết một Câu trả lời hoàn toàn đúng. Nhưng nó chắc chắn là một quyết định bạn có được để thực hiện, và có lẽ tốt để bảo vệ trong, nói rằng, một hoặc hai bình luận lý do tại sao bạn chọn một trong khác. 

Cuối cùng, xóa. Chúng tôi đã nhìn thấy xóa. Nó tương tự như tìm kiếm. Chúng tôi tìm kiếm các phần tử. Nói rằng chúng tôi đang cố gắng để xóa sáu. Vì vậy, chúng tôi tìm thấy sáu ngay tại đây. Điều mà chúng ta phải chắc chắn rằng chúng tôi làm là bất cứ điều gì chỉ để sáu - như chúng ta thấy trong bước hai xuống đây - bất cứ điều gì trỏ đến sáu nhu cầu để bỏ qua sáu giờ và được thay đổi để bất cứ điều gì sáu được trỏ đến. Chúng tôi không muốn đứa trẻ mồ côi bao giờ phần còn lại của danh sách của chúng tôi bằng cách quên đi để thiết lập mà con trỏ trước. Và đôi khi, tùy thuộc về chương trình, họ sẽ chỉ xóa nút này hoàn toàn. Đôi khi bạn sẽ muốn quay trở lại giá trị đó là trong nút này. Vì vậy, đó là cách xóa các công trình. Bất kỳ câu hỏi về xóa? 

ĐỐI TƯỢNG: Vì vậy, nếu bạn đang đi để xóa nó, bạn sẽ chỉ sử dụng miễn phí bởi vì có lẽ nó đã được malloced? 

JASON HIRSCHORN: Nếu bạn muốn giải phóng một cái gì đó hoàn toàn chính xác và bạn malloced nó. Nói rằng chúng ta muốn trở về giá trị này. Chúng tôi có thể trở lại sáu và sau đó miễn phí nút này và gọi miễn phí trên đó. Hoặc chúng tôi có lẽ muốn gọi miễn phí đầu tiên và sau đó trở về sáu. 

OK. Vì vậy, chúng ta hãy chuyển sang thực hành mã hóa. Chúng tôi đang đi vào mã ba chức năng. Người đầu tiên được gọi là insert_node. Vì vậy, bạn có mã mà tôi gửi qua email bạn, và nếu bạn đang xem cái này sau này bạn có thể truy cập vào mã trong linked.c trên trang web CS50. Nhưng trong linked.c, có một số đang bộ xương đó là đã có được viết cho bạn. Và sau đó có một vài chức năng bạn cần phải viết. 

Đầu tiên chúng ta sẽ viết insert_node. Và những gì không insert_node là chèn một số nguyên. Và bạn đang đưa ra các số nguyên vào một danh sách liên kết. Và đặc biệt, bạn cần để giữ cho các danh sách được sắp xếp từ nhỏ đến lớn. Ngoài ra, bạn không muốn chèn thêm bất kỳ bản sao. Cuối cùng, bạn có thể thấy insert_node trả về một bool. Vì vậy, bạn đang nghĩ để cho người dùng biết hay không chèn là thành công bằng cách trả lại đúng hay sai. Vào cuối của chương trình này - và cho giai đoạn này bạn không cần phải lo lắng về bất cứ điều gì giải phóng. Vì vậy, tất cả các bạn đang làm là lấy một số nguyên và chèn nó vào một danh sách. 

Đó là những gì tôi yêu cầu bạn làm bây giờ. Một lần nữa, trong linked.c, mà bạn tất cả đều có, là mã bộ xương. Và bạn sẽ thấy hướng về phía dưới khai báo hàm mẫu. Tuy nhiên, trước khi đi vào mã hóa nó trong C, tôi rất khuyến khích bạn đi thông qua các bước chúng tôi đã thực hành mỗi tuần. Chúng ta đã trải qua một bức tranh về điều này. Vì vậy, bạn cần phải có một số hiểu biết về cách làm việc này. Nhưng tôi sẽ khuyến khích bạn viết một số giả trước khi lặn in Và chúng ta sẽ đi qua giả như một nhóm. Và sau đó một khi bạn đã viết của bạn giả, và một khi chúng tôi đã viết của chúng tôi giả như một nhóm, bạn có thể đi vào mã hóa nó trong C. 

Là một người đứng đầu lên, chức năng insert_node có lẽ là khó khăn nhất trong ba chúng tôi đang đi để viết bởi vì tôi bổ sung một số hạn chế bổ sung cho lập trình của bạn, đặc biệt là bạn sẽ không chèn thêm bất kỳ bản sao và danh sách nên vẫn còn được sắp xếp. Vì vậy, đây là một chương trình không tầm thường mà bạn cần phải viết mã. Và tại sao bạn không đi 5-7 phút chỉ để làm việc trên giả và mã. Và sau đó chúng tôi sẽ bắt đầu đi theo nhóm. Một lần nữa, nếu bạn có bất kỳ câu hỏi chỉ giơ tay và tôi sẽ đi xung quanh. . 

Chúng tôi cũng thường làm những - hoặc tôi không nói một cách rõ ràng bạn có thể làm việc với mọi người. Nhưng rõ ràng, tôi rất khuyến khích các bạn, nếu bạn có thắc mắc, yêu cầu các hàng xóm ngồi bên cạnh bạn hoặc thậm chí làm việc với ai đó khác nếu bạn muốn. Điều này không phải là một cá nhân hoạt động im lặng. 

Hãy bắt đầu với một số văn bản giả trên diễn đàn. Ai có thể cho tôi những dòng đầu tiên của giả cho chương trình này? Đối với chức năng này, thay vì - insert_node. Alden? 

ĐỐI TƯỢNG: Vì vậy, điều đầu tiên tôi làm là tạo ra một con trỏ đến nút mới và tôi khởi tạo nó trỏ đến cùng điều mà danh sách được trỏ đến. 

JASON HIRSCHORN: OK. Vì vậy, bạn đang tạo ra một con trỏ mới vào danh sách, không để nút. 

ĐỐI TƯỢNG: Đúng vậy. Yeah. 

JASON HIRSCHORN: OK. Và sau đó những gì chúng ta muốn làm gì? Có gì sau đó? Những gì về các nút? Chúng tôi không có một nút. Chúng tôi chỉ có một giá trị. Nếu chúng ta muốn chèn một nút, những gì chúng tôi cần làm đầu tiên trước khi chúng tôi thậm chí có thể suy nghĩ về chèn nó? 

ĐỐI TƯỢNG: Ồ, xin lỗi. chúng ta cần phải malloc không gian cho một nút. 

JASON HIRSCHORN: Tuyệt vời. Chúng ta hãy làm - OK. Không thể đạt cao. OK. Chúng ta sẽ đi xuống, và sau đó chúng tôi đang sử dụng hai cột. Tôi không thể đi mà - OK. Tạo ra một nút mới. Bạn có thể tạo ra một con trỏ vào danh sách hoặc bạn chỉ có thể sử dụng danh sách như nó tồn tại. Bạn không thực sự cần phải làm điều đó. 

Vì vậy, chúng tôi tạo ra một nút mới. Tuyệt vời. Đó là những gì chúng tôi làm đầu tiên. Cái gì tiếp theo? 

ĐỐI TƯỢNG: Chờ. Chúng ta nên tạo một nút mới ngay bây giờ hoặc chúng ta nên chờ đợi để chắc chắn rằng không có bản sao của nút trong danh sách trước khi chúng tôi tạo ra nó? 

JASON HIRSCHORN: Câu hỏi. Chúng ta hãy giữ mà cho sau này vì phần lớn thời gian chúng ta sẽ tạo ra một nút mới. Vì vậy, chúng tôi sẽ giữ cho rằng đây. Nhưng đó là một câu hỏi hay. Nếu chúng ta tạo ra nó và chúng ta tìm thấy một bản sao, những gì nên chúng tôi làm trước khi trở về? 

ĐỐI TƯỢNG: Miễn phí nó. 

JASON HIRSCHORN: Vâng. Có thể giải phóng nó. OK. Chúng ta phải làm gì sau khi chúng tôi tạo ra một nút mới? Annie? 

ĐỐI TƯỢNG: Chúng tôi đặt số trong nút? 

JASON HIRSCHORN: Chính xác. Chúng tôi đưa số - chúng tôi malloc không gian. Tôi sẽ rời khỏi đó tất cả như một dòng. Nhưng bạn nói đúng. Chúng tôi malloc không gian, và sau đó chúng tôi đặt số lượng in Chúng tôi thậm chí có thể đặt con trỏ một phần của nó để null. Đó chính quyền. Và sau đó những gì về sau không? Chúng tôi vẽ bức tranh này trên diễn đàn. Vì vậy, chúng ta làm gì? 

ĐỐI TƯỢNG: Chúng tôi đi qua danh sách. 

JASON HIRSCHORN: Đi qua danh sách. OK. Và làm những gì chúng tôi kiểm tra tại mỗi nút. Kurt, những gì chúng tôi kiểm tra cho tại mỗi nút? 

ĐỐI TƯỢNG: Xem liệu giá trị của n nút đó là lớn hơn giá trị n của nút của chúng tôi. 

JASON HIRSCHORN: OK. Tôi sẽ làm - yeah, OK. Vì vậy, nó là n - Tôi sẽ nói rằng nếu giá trị lớn hơn nút này, sau đó chúng ta làm gì? 

ĐỐI TƯỢNG: Vâng, sau đó chúng ta chèn điều ngay trước đó. 

JASON HIRSCHORN: OK. Vì vậy, nếu nó lớn hơn này, sau đó chúng tôi muốn chèn. Nhưng chúng tôi muốn chèn nó ngay trước khi bởi vì chúng tôi cũng sẽ cần phải được theo dõi, sau đó, những gì trước đây. Vì vậy, trước khi chèn. Vì vậy, chúng ta có thể bỏ qua một cái gì đó trước đây về. Chúng tôi có lẽ cần phải được giữ theo dõi những gì đang xảy ra. Nhưng chúng tôi sẽ lấy lại ở đó. Vì vậy, những gì giá trị nhỏ hơn? Kurt, chúng ta làm gì nếu giá trị nhỏ hơn? 

ĐỐI TƯỢNG: Sau đó, bạn chỉ cần tiếp tục đi trừ khi đó là người cuối cùng. 

JASON HIRSCHORN: Tôi thích điều đó. Vì vậy, đi đến nút tiếp theo. Trừ khi đó là tác phẩm mới nhất - có lẽ chúng tôi đang kiểm tra cho rằng trong các điều khoản của một điều kiện. Nhưng yeah, nút tiếp theo. Và đó là nhận được quá thấp, vì vậy chúng tôi sẽ di chuyển qua đây. Nhưng nếu - tất cả mọi người có thể thấy điều này? Nếu chúng ta bằng những gì chúng ta làm gì? Nếu giá trị, chúng tôi đang cố gắng để chèn bằng giá trị của nút này? Yeah? 

ĐỐI TƯỢNG: [nghe được]. 

JASON HIRSCHORN: Vâng. Vì điều này - Marcus là đúng. Chúng ta có thể có thể thực hiện một cái gì đó khác nhau. Nhưng cho rằng chúng tôi đã tạo ra nó, đây chúng ta nên giải phóng và sau đó quay trở lại. Oh boy. Là tốt hơn? Làm thế nào vậy? OK. Miễn phí và sau đó làm những gì chúng tôi trở lại, [không nghe được]? OK. Chúng ta đang thiếu gì? Vì vậy, nơi được chúng tôi theo dõi của nút trước? 

ĐỐI TƯỢNG: Tôi nghĩ rằng nó sẽ đi sau khi tạo ra một nút mới. 

JASON HIRSCHORN: OK. Vì vậy, ngay từ đầu chúng ta sẽ có thể - yeah, chúng tôi có thể tạo ra một con trỏ đến một mới nút, giống như một con trỏ nút trước và một nút con trỏ hiện hành. Vì vậy, hãy chèn đó ở đây. Tạo hiện tại và trước con trỏ đến các nút. Nhưng khi chúng ta điều chỉnh những con trỏ? Nơi nào chúng ta làm điều đó trong các mã? Jeff? 

ĐỐI TƯỢNG: - Điều kiện giá trị? 

JASON HIRSCHORN: Những một đặc biệt? 

ĐỐI TƯỢNG: Tôi chỉ nhầm lẫn. Nếu giá trị lớn hơn nút này, không có nghĩa là bạn muốn đi đến nút tiếp theo? 

JASON Hirschhorn: Vì vậy, nếu giá trị của chúng tôi là lớn hơn giá trị của nút này. 

ĐỐI TƯỢNG: Vâng, sau đó bạn muốn đi xa hơn xuống dòng, phải không? 

JASON Hirschhorn: Đúng vậy. Vì vậy, chúng tôi không chèn nó ở đây. Nếu giá trị nhỏ hơn nút này, sau đó chúng tôi đi đến nút tiếp theo - hoặc sau đó chúng tôi chèn trước. 

ĐỐI TƯỢNG: Chờ đợi, đó là này nút và đó là giá trị? 

JASON Hirschhorn: Câu hỏi. Giá trị theo định nghĩa chức năng này là những gì chúng tôi đang đưa ra. Vì vậy, giá trị là số chúng ta đang đưa ra. Vì vậy, nếu giá trị nhỏ hơn này nút, chúng tôi cần thời gian để chèn. Nếu giá trị lớn hơn nút này, chúng tôi đi đến nút tiếp theo. Và quay trở lại câu hỏi ban đầu, Mặc dù vậy, nơi - 

ĐỐI TƯỢNG: Nếu giá trị lớn hơn nút này. 

JASON Hirschhorn: Và như vậy chúng ta làm gì đây? Ngọt ngào. Đó là chính xác. Tôi chỉ sẽ viết cập nhật con trỏ. Nhưng có, với hiện tại bạn sẽ cập nhật nó để trỏ đến kế tiếp. Bất cứ điều gì khác chúng ta đang thiếu? Vì vậy tôi sẽ để kiểu này mã vào gedit. Và trong khi tôi làm điều này, bạn có thể có một vài phút nữa để làm việc trên mã hóa này trong C. 

Vì vậy, tôi có nhập giả. Một lưu ý trước khi chúng ta bắt đầu. Chúng tôi có thể không có khả năng hoàn toàn hoàn thành điều này trong tất cả các ba chức năng này. Có giải pháp đúng cho họ mà tôi sẽ gửi email ra đến với bạn sau khi phần, và nó sẽ được đăng tải trên CS50.net. Vì vậy tôi không khuyến khích bạn hãy nhìn vào các phần. Tôi khuyến khích bạn hãy thử các trên của bạn sở hữu, và sau đó sử dụng các thực hành vấn đề để kiểm tra câu trả lời của bạn. Những tất cả đều được thiết kế chặt chẽ liên quan đến và tuân thủ những gì bạn phải làm trong bộ vấn đề. Vì vậy, tôi khuyến khích bạn thực hành này ngày của riêng bạn và sau đó sử dụng mã để kiểm tra câu trả lời của bạn. Bởi vì tôi muốn chuyển sang băm bảng tại một số điểm trong phần này. Vì vậy, chúng ta có thể không vượt qua được tất cả. Nhưng chúng tôi sẽ làm càng nhiều chúng tôi có thể bây giờ. 

OK. Chúng ta hãy bắt đầu. Asam, làm thế nào để chúng ta tạo ra một nút mới? 

ĐỐI TƯỢNG: Bạn struct *. 

JASON Hirschhorn: Vì vậy, chúng tôi có mà lên đây. Oh, xin lỗi. Bạn đang nói cấu trúc *. 

ĐỐI TƯỢNG: Và sau đó [? loại?] hay nút c. 

JASON Hirschhorn: OK. Tôi sẽ gọi nó là new_node vì vậy chúng tôi có thể ở lại quán. 

ĐỐI TƯỢNG: Và bạn muốn thiết lập mà đứng đầu, nút đầu tiên. 

JASON Hirschhorn: OK. Vì vậy bây giờ trỏ này - vì vậy đây đã không tạo ra một nút mới được nêu ra. Đây chỉ là chỉ tới nút đầu tiên trong danh sách. Làm thế nào để tạo ra một nút mới? Nếu tôi cần không gian để tạo ra một nút mới. Malloc. Và lớn như thế nào? 

ĐỐI TƯỢNG: Kích thước của cấu trúc. 

JASON Hirschhorn: Các kích thước của các cấu trúc. Và những gì các cấu trúc được gọi là? 

ĐỐI TƯỢNG: Node? 

JASON Hirschhorn: Node. Vì vậy, malloc (sizeof (node)); cho chúng ta không gian. Và là dòng này - có một điều không chính xác trên dòng này. Là new_node một con trỏ đến một cấu trúc? Đó là một tên chung. Nó là gì - nút, chính xác. Đó là một nút *. Và làm những gì chúng tôi làm ngay sau khi chúng tôi malloc một cái gì đó, Asan? Điều đầu tiên chúng tôi làm là những gì? Nếu nó không hoạt động? 

ĐỐI TƯỢNG: Oh, kiểm tra xem nó chỉ đến nút? 

JASON Hirschhorn: Chính xác. Vì vậy, nếu bạn new_node bằng bình đẳng null, chúng ta làm gì? Này trả về một bool, chức năng này. Chính xác. Có vẻ tốt. Bất cứ điều gì thêm không? Chúng tôi sẽ thêm những điều ở cuối. Nhưng cho đến nay có vẻ tốt. Tạo con trỏ hiện tại và trước đó. Michael, làm thế nào để làm điều này? 

ĐỐI TƯỢNG: Bạn sẽ phải để làm một nút *. Bạn phải làm cho người ta không cho new_node nhưng đối với các các nút chúng tôi đã có. 

JASON Hirschhorn: OK. Vì vậy, các nút hiện tại chúng tôi đang ở trên. Tôi sẽ gọi Curr đó. Được rồi. Chúng tôi đã quyết định chúng ta muốn giữ hai bởi vì chúng ta cần phải biết những gì trước khi nó. Những gì họ nhận được khởi tạo? 

ĐỐI TƯỢNG: giá trị của họ trong danh sách của chúng tôi. 

JASON Hirschhorn: là Vì vậy, những gì Điều đầu tiên trong danh sách của chúng tôi? Hoặc làm thế nào để chúng ta biết nơi bắt đầu của danh sách của chúng tôi là? 

ĐỐI TƯỢNG: Không phải là nó thông qua vào chức năng? 

JASON Hirschhorn: Đúng vậy. Nó đã được thông qua trong ngay tại đây. Vì vậy, nếu nó được thông qua vào chức năng, bắt đầu của danh sách, chúng tôi những gì nên thiết lập hiện tại bằng? 

ĐỐI TƯỢNG: Danh sách. 

JASON Hirschhorn: Danh sách. Đó chính quyền. Bây giờ nó có địa chỉ của khi bắt đầu danh sách của chúng tôi. Và những gì về trước? 

ĐỐI TƯỢNG: Danh sách trừ một? 

JASON Hirschhorn: Có không có gì trước khi nó. Vì vậy, những gì chúng tôi có thể làm cho sự không có gì? 

ĐỐI TƯỢNG: Null. 

JASON Hirschhorn: Vâng. Nghe có vẻ như một ý tưởng tốt. Hoàn hảo. Cảm ơn bạn. Đi qua danh sách. Constantine, chúng ta sẽ mất bao lâu đi qua danh sách? 

ĐỐI TƯỢNG: Cho đến khi chúng tôi đạt được null. 

JASON Hirschhorn: OK. Vì vậy, nếu, trong khi, cho vòng lặp. Chúng tôi đang làm những gì? 

ĐỐI TƯỢNG: Có lẽ một vòng lặp? 

JASON Hirschhorn: Hãy làm một vòng lặp. OK. 

ĐỐI TƯỢNG: Và chúng ta nói cho - cho đến khi con trỏ hiện tại không bằng null. 

JASON Hirschhorn: Vì vậy, nếu chúng ta biết điều kiện, làm thế nào chúng ta có thể viết một vòng lặp dựa tắt tình trạng đó. Loại một vòng lặp chúng ta nên sử dụng? 

ĐỐI TƯỢNG: Trong khi. 

JASON Hirschhorn: Vâng. Có ý nghĩa hơn dựa tắt của những gì bạn nói. Nếu chúng ta chỉ muốn đi vào chúng tôi nó sẽ chỉ biết điều đó, nó sẽ làm cho tinh thần để làm một vòng lặp while. Trong khi hiện tại không rỗng không bằng nhau, nếu giá trị nhỏ hơn nút này. Akshar, cho tôi dòng này. 

ĐỐI TƯỢNG: Nếu hiện tại-> n n thấp hơn giá trị. Hoặc đảo ngược. Chuyển khung đó. 

JASON Hirschhorn: Xin lỗi. 

ĐỐI TƯỢNG: Thay đổi khung. 

JASON Hirschhorn: Vì vậy, nếu nó lớn hơn giá trị. Bởi vì đó là gây nhầm lẫn với các bình luận ở trên, tôi sẽ làm điều đó. Nhưng có. Nếu giá trị của chúng tôi là ít hơn này nút, chúng ta làm gì? Oh. Tôi có nó ở đây. Chèn trước. OK. Làm thế nào để chúng tôi làm điều đó? 

ĐỐI TƯỢNG: Là nó vẫn còn tôi? 

JASON Hirschhorn: Vâng. 

ĐỐI TƯỢNG: Bạn - new_node-> tiếp theo. 

JASON Hirschhorn: Vậy điều gì mà sẽ bằng? 

ĐỐI TƯỢNG: Nó sẽ hiện bình đẳng. 

JASON Hirschhorn: Chính xác. Và do đó khác - những gì khác chúng ta cần phải cập nhật? 

ĐỐI TƯỢNG: Kiểm tra xem trong quá khứ bằng null. 

JASON Hirschhorn: Nếu prev - vì vậy nếu trước bằng null. 

ĐỐI TƯỢNG: Điều đó có nghĩa nó sẽ để trở thành người đứng đầu. 

JASON Hirschhorn: phương tiện đó nó đã trở thành người đứng đầu. Vì vậy, sau đó chúng ta làm gì? 

ĐỐI TƯỢNG: Chúng tôi đầu bằng new_node. 

JASON Hirschhorn: Head bằng new_node. Và tại sao đi đây, không liệt kê? 

ĐỐI TƯỢNG: Bởi vì đầu là một toàn cầu biến, đó là nơi bắt đầu. 

JASON Hirschhorn: Sweet. OK. Và - 

ĐỐI TƯỢNG: Sau đó, bạn khác prev-> tiếp theo bằng new_node. Và sau đó bạn trở thành sự thật. 

JASON Hirschhorn: Nơi nào chúng tôi thiết lập new_node kết thúc? 

ĐỐI TƯỢNG: Tôi sẽ - Tôi thiết lập mà lúc đầu. 

JASON Hirschhorn: Vì vậy, những gì dòng? 

ĐỐI TƯỢNG: Sau khi tuyên bố nếu kiểm tra nếu nó được biết đến. 

JASON Hirschhorn: Ngay ở đây? 

ĐỐI TƯỢNG: tôi muốn làm new_node-> n bằng giá trị. 

JASON Hirschhorn: Âm thanh tốt. Có lẽ nó có ý nghĩa - chúng ta không cần biết danh sách những gì chúng ta đang ở trên bởi vì chúng tôi chỉ giao dịch với một danh sách. Do đó, một tuyên bố chức năng tốt hơn cho này chỉ là để thoát khỏi điều này hoàn toàn và chỉ cần chèn một giá trị vào đầu. Chúng tôi thậm chí không cần biết danh sách những gì chúng tôi đang nhập Nhưng tôi sẽ giữ nó cho bây giờ và sau đó thay đổi nó khi cập nhật các slide và mã số. Vì vậy, đó có vẻ tốt cho bây giờ. Nếu giá trị - những người có thể làm dòng này? Nếu - chúng ta làm gì đây, Noah. 

ĐỐI TƯỢNG: Nếu giá trị lớn hơn curr-> n - 

JASON Hirschhorn: Làm thế nào chúng tôi đi đến nút tiếp theo? 

ĐỐI TƯỢNG: Curr-> n là bằng new_node. 

JASON Hirschhorn: Vì vậy, n là những gì một phần của cấu trúc? Các số nguyên. Và new_node là một con trỏ đến một nút. Vì vậy, những gì một phần của Curr chúng ta nên cập nhật? Nếu không n, sau đó một phần khác là gì? Noah, nhưng phần khác là những gì. 

ĐỐI TƯỢNG: Oh, tiếp theo. 

JASON Hirschhorn: Tiếp theo, chính xác. Chính xác. Tiếp theo là một trong những quyền. Và những gì khác chúng ta cần để cập nhật, Noah? 

ĐỐI TƯỢNG: Các con trỏ. 

JASON Hirschhorn: Vì vậy, chúng tôi cập nhật hiện tại. 

ĐỐI TƯỢNG: Trước-> tiếp theo. 

JASON Hirschhorn: Vâng. OK, chúng tôi sẽ tạm dừng. Ai có thể giúp chúng ta ra khỏi đây? Manu, những gì chúng ta nên làm gì? 

ĐỐI TƯỢNG: Bạn đã có để thiết lập nó bằng curr-> tiếp theo. Nhưng làm điều đó trước khi các dòng trước đó. 

JASON Hirschhorn: OK. Bất cứ điều gì khác? Akshar. 

ĐỐI TƯỢNG: Tôi không nghĩ rằng bạn đang có nghĩa là để thay đổi curr-> tiếp theo. Tôi nghĩ rằng bạn đang có nghĩa là để làm bình đẳng Curr Curr-> tiếp theo để đi đến nút tiếp theo. 

JASON Hirschhorn: Vì vậy, xin lỗi, ở đâu? Trên những dòng? Dòng này? 

ĐỐI TƯỢNG: Vâng. Làm Curr bằng Curr-> tiếp theo. 

JASON Hirschhorn: Vì vậy, đó là chính xác bởi vì hiện nay là một con trỏ đến một nút. Và chúng tôi muốn nó để trỏ đến tiếp theo nút của những gì đang nhận được hiện nay chỉ vào. Curr chính nó có một tiếp theo. Nhưng nếu chúng ta để cập nhật curr.next, chúng tôi sẽ được cập nhật ghi chú thực tế bản thân, không nơi này con trỏ đang chỉ. Những gì về dòng này, mặc dù. Avi? 

ĐỐI TƯỢNG: Trước-> tiếp theo bằng Curr. 

JASON Hirschhorn: Vì vậy, một lần nữa, nếu trước là một con trỏ tới một nút, trước-> tiếp theo là con trỏ thực tế trong nút. Vì vậy, điều này sẽ được cập nhật một con trỏ trong một nút để Curr. Chúng tôi không muốn để cập nhật một con trỏ trong một nút. Chúng tôi muốn để cập nhật trước đó. Vì vậy, làm thế nào để chúng tôi làm điều đó? 

ĐỐI TƯỢNG: Nó sẽ chỉ được prev. 

JASON Hirschhorn: Đúng vậy. Trước là một con trỏ đến một nút. Bây giờ chúng ta thay đổi nó vào một con trỏ mới đến một nút. OK Chúng ta hãy di chuyển xuống. Cuối cùng, tình trạng cuối cùng này. Jeff, chúng ta làm gì đây? 

ĐỐI TƯỢNG: Nếu giá trị bằng curr-> n. 

JASON Hirschhorn: Xin lỗi. Ôi trời. Những gì? Giá trị == curr-> n. Chúng ta phải làm gì? 

ĐỐI TƯỢNG: Bạn muốn giải phóng new_node của chúng tôi, và sau đó bạn sẽ trả về false. 

JASON Hirschhorn: Đây là những gì chúng ta đã viết cho đến nay. Không ai có bất cứ điều gì thêm trước khi chúng tôi thực hiện? OK. Hãy thử nó. Kiểm soát có thể đạt được kết thúc của một chức năng không có hiệu lực. Avi, những gì đang xảy ra? 

ĐỐI TƯỢNG: Bạn có nghĩa vụ phải đặt trở lại thật bên ngoài vòng lặp trong khi? 

JASON Hirschhorn: Tôi không biết. Bạn có muốn tôi? 

ĐỐI TƯỢNG: Đừng bận tâm. Không. 

JASON Hirschhorn: Akshar? 

ĐỐI TƯỢNG: Tôi nghĩ rằng bạn có nghĩa là để đưa trở lại sai ở cuối của vòng lặp while. 

JASON Hirschhorn: Vì vậy, nơi Bạn muốn nó đi đâu? 

ĐỐI TƯỢNG: Giống như bên ngoài vòng lặp while. Vì vậy, nếu bạn thoát khỏi vòng lặp trong khi đó phương tiện mà bạn đã đạt đến cuối cùng và không có gì đã xảy ra. 

JASON Hirschhorn: OK. Vì vậy, chúng ta làm gì ở đây? 

ĐỐI TƯỢNG: Bạn trả về false cũng có. 

JASON Hirschhorn: Oh, chúng tôi làm điều đó trong cả hai nơi? 

ĐỐI TƯỢNG: Vâng. 

JASON Hirschhorn: OK. Chúng ta nên đi đâu? Ôi trời. Tôi xin lỗi. Tôi xin lỗi vì màn hình. Nó loại freaking ra vào chúng tôi. Vì vậy, chọn một tùy chọn. Bằng không, mỗi mã, bỏ chương trình. Một cái gì đó chèn. Chúng ta hãy chèn ba. Chèn đã không thành công. Tôi sẽ in ra. Tôi không có bất cứ điều gì. OK. Có lẽ đó chỉ là một sự may mắn. Chèn một. Không thành công. OK. Chúng ta hãy chạy qua GDB thực sự nhanh chóng để kiểm tra những gì đang xảy ra. 

Ghi gdb. / Tên của bạn chương trình được chúng tôi vào GDB. Là rất nhiều để xử lý? Nhấp nháy? Có thể. Nhắm mắt lại và có một số sâu hơi thở nếu bạn cảm thấy mệt mỏi nhìn vào nó. Tôi đang trong GDB. Điều đầu tiên tôi làm trong GDB là gì? Chúng ta phải tìm ra những gì đang xảy ra ở đây. Chúng ta hãy xem. Chúng tôi có sáu phút để con số ra những gì đang xảy ra. Phá vỡ chính. Và sau đó tôi phải làm gì? Carlos? Chạy. OK. Hãy chọn một lựa chọn. Và những gì N làm gì? Tiếp theo. Yeah. 

ĐỐI TƯỢNG: Bạn đã không đề cập đến - bạn không nói rằng người đứng đầu, đó là khởi tạo null ở đầu. Nhưng tôi nghĩ bạn nói đó là OK. 

JASON Hirschhorn: Hãy đi - chúng ta hãy xem trong GDB, và sau đó chúng tôi sẽ quay trở lại. Nhưng có vẻ như bạn đã có một số ý tưởng về những gì đang xảy ra. Vì vậy, chúng tôi muốn chèn một cái gì đó. OK. Chúng tôi đã chèn. Xin vui lòng nhập một int. Chúng tôi sẽ chèn ba. Và sau đó tôi đang trên đường này. Làm thế nào để tôi đi bắt đầu gỡ lỗi chèn chức năng được biết đến? Ôi trời. Đó là rất nhiều. Được rằng freaking ra rất nhiều? 

ĐỐI TƯỢNG: Oh, nó đã chết. 

JASON Hirschhorn: Tôi chỉ kéo nó ra. OK. 

ĐỐI TƯỢNG: Có lẽ đó là đầu kia của dây. 

JASON Hirschhorn: Wow. Vì vậy, dòng dưới cùng - bạn đã nói những gì? 

ĐỐI TƯỢNG: Tôi nói sự trớ trêu của kỹ thuật khó khăn trong lớp học này. 

JASON Hirschhorn: Tôi biết. Nếu tôi có quyền kiểm soát một phần. [Nghe được] Đó là âm thanh tuyệt vời. Tại sao cậu không bắt đầu nghĩ về những gì chúng tôi có thể đã làm sai, và chúng tôi sẽ trở lại trong 90 giây. 

Avica, tôi sẽ yêu cầu bạn làm thế nào để đi insert_node bên trong để gỡ lỗi nó. Vì vậy, đây là nơi mà chúng tôi cuối cùng rời đi. Làm thế nào để đi vào bên trong insert_node, Avica, để kiểm tra những gì đang xảy ra? Lệnh gì GDB? Phá vỡ sẽ không đưa tôi vào bên trong. Không Marquise biết? 

ĐỐI TƯỢNG: Cái gì? 

JASON Hirschhorn: Lệnh gì GDB Tôi sử dụng để đi vào bên trong chức năng này? 

ĐỐI TƯỢNG: Bước? 

JASON Hirschhorn: Bước qua S. Điều đó có tôi bên trong. OK. New_node mallocing một số không gian. Rằng tất cả trông giống như đi của nó. Hãy kiểm tra new_node. Nó có một số địa chỉ bộ nhớ. Hãy kiểm tra - đó là tất cả đúng. Vì vậy, tất cả mọi thứ ở đây có vẻ được làm việc một cách chính xác. 

ĐỐI TƯỢNG: sự khác biệt là gì giữa P và màn hình hiển thị? 

JASON Hirschhorn: P là viết tắt của in ấn. Và do đó, bạn đang yêu cầu những gì là sự khác biệt giữa đó và điều này? Trong trường hợp này, không có gì. Nhưng nói chung có một số khác biệt. Và bạn nên tìm trong hướng dẫn GDB. Nhưng trong trường hợp này, không có gì. Chúng ta có xu hướng sử dụng in ấn, tuy nhiên, vì chúng tôi không cần phải làm nhiều hơn in một giá trị duy nhất. 

OK. Vì vậy, chúng tôi đang trên đường 80 của mã của chúng tôi, thiết lập node * Curr bằng danh sách. Chúng ta hãy in ra Curr. Nó tương đương với danh sách. Ngọt ngào. Chờ đợi. Nó bằng một cái gì đó. Điều đó dường như không đúng. Có chúng tôi đi. Đó là bởi vì trong GDB, phải, nếu đó là dòng bạn đang ở trên nó đã không được thực hiện được nêu ra. Vì vậy, bạn cần phải thực sự gõ bên cạnh thực thi các dòng trước khi nhìn thấy kết quả của nó. Vì vậy, ở đây chúng tôi đang có. Chúng tôi chỉ thực hiện dòng này, trước bằng null. Vì vậy, một lần nữa, nếu chúng ta in trước chúng ta sẽ không nhìn thấy bất cứ điều gì kỳ lạ. Nhưng nếu chúng ta thực sự thực hiện mà dòng, sau đó chúng ta sẽ thấy dòng mà làm việc. 

Vì vậy, chúng tôi có Curr. Đó là cả hai tốt. Phải không? Bây giờ chúng ta đang ở trên dòng này ngay tại đây. Trong khi Curr không làm vô giá trị như nhau. Vâng, những gì hiện Curr bằng nhau? Chúng tôi chỉ thấy nó tương đương null. Chúng tôi in nó ra. Tôi sẽ in ra một lần nữa. Vì vậy, là trong khi vòng lặp sẽ thực hiện? 

ĐỐI TƯỢNG: số 

JASON Hirschhorn: Vì vậy, khi tôi đánh máy mà dòng, bạn sẽ thấy chúng tôi đã tăng tất cả các cách xuống phía dưới, trả về false. Và sau đó chúng tôi sẽ trả về false và quay trở lại chương trình của chúng tôi và cuối cùng in ra, như chúng ta đã thấy, chèn đã không thành công. Vì vậy, bất cứ ai có bất kỳ ý tưởng về những gì chúng ta cần phải làm gì để sửa lỗi này? Tôi sẽ chờ đợi cho đến khi tôi nhìn thấy một vài tay đi lên. Chúng tôi đã không thực hiện điều này. Hãy nhớ, đây là lần đầu tiên điều chúng tôi đã làm. Tôi sẽ không để làm một cặp vợ chồng. Tôi sẽ làm một vài. Bởi vì một vài nghĩa là hai. Tôi sẽ chờ đợi nhiều hơn hai. 

Chèn đầu tiên, Curr, theo mặc định bằng null. Và vòng lặp này chỉ thực hiện nếu Curr không phải là null. Vì vậy, làm thế nào tôi có thể làm được việc này? Tôi thấy ba tay. Tôi sẽ chờ đợi nhiều hơn ba. Marcus, bạn nghĩ gì? 

ĐỐI TƯỢNG: Vâng, nếu bạn cần nó để thực hiện nhiều hơn một lần, bạn chỉ cần thay đổi nó vào một vòng lặp do-while. 

JASON Hirschhorn: OK. Mà sẽ giải quyết vấn đề của chúng tôi, mặc dù? 

ĐỐI TƯỢNG: Trong trường hợp này không vì thực tế là danh sách là sản phẩm nào. Vì vậy, sau đó bạn có thể chỉ cần thêm một tuyên bố rằng nếu thoát vòng lặp sau đó bạn có thể vào cuối năm danh sách, lúc này bạn chỉ có thể chèn nó. 

JASON Hirschhorn: Tôi thích điều đó. Có ý nghĩa. Nếu vòng lặp thoát - bởi vì nó sẽ trả về false đây. Vì vậy, nếu thoát vòng lặp, sau đó chúng tôi đang ở cuối danh sách, hoặc có thể bắt đầu của một danh sách nếu không có gì trong nó, mà là giống như kết thúc. Vì vậy, bây giờ chúng tôi muốn chèn cái gì ở đây. Vì vậy, làm thế nào để mã nhìn, Marcus? 

ĐỐI TƯỢNG: Nếu bạn đã có nút malloced, bạn chỉ có thể nói new_node-> tiếp theo bằng vô giá trị vì nó có phải là cuối cùng. Hoặc new_node-> tiếp theo bằng null. 

JASON Hirschhorn: OK. Xin lôi. New_node-> tiếp theo bằng vô giá trị bởi vì chúng ta ở cuối. Mà không đặt nó vào Làm thế nào để chúng tôi đặt nó trong danh sách? Đúng. Đó chỉ là đặt nó bằng với. Không làm thế nào để chúng tôi thực sự đặt nó trong danh sách? Những gì đang trỏ đến cuối danh sách? 

ĐỐI TƯỢNG: Trưởng. 

JASON Hirschhorn: Xin lỗi? 

ĐỐI TƯỢNG: Trưởng trỏ đến cuối danh sách. 

JASON Hirschhorn: Nếu không có gì trong danh sách, người đứng đầu là chỉ tới cuối danh sách. Vì vậy, mà sẽ làm việc cho chèn đầu tiên. Những gì về nếu có một vài những thứ trong danh sách? Hơn chúng tôi không muốn để thiết lập đầu bằng new_node. Những gì chúng tôi muốn làm ở đó? Yeah? Có lẽ trước đó. Mà sẽ làm việc? Nhớ lại rằng trước đó chỉ là một con trỏ tới một nút. Và trước đó là một biến địa phương. Vì vậy, dòng này sẽ thiết lập một biến địa phương, trước, bằng hoặc trỏ đến nút mới này. Điều đó sẽ không thực sự đặt nó trong danh sách của chúng tôi, mặc dù. Làm thế nào để chúng tôi đặt nó trong danh sách của chúng tôi? Akchar? 

ĐỐI TƯỢNG: Tôi nghĩ rằng bạn làm hiện tại-> tiếp theo. 

JASON Hirschhorn: OK. Curr-> tiếp theo. Vì vậy, một lần nữa, lý do duy nhất chúng tôi đang xuống ở đây là, những gì hiện tại bằng nhau? 

ĐỐI TƯỢNG: Bình đẳng null. 

JASON Hirschhorn: Và vì vậy những gì sẽ xảy ra nếu chúng ta làm null-> tiếp theo? Chúng tôi sẽ nhận được những gì? Chúng tôi sẽ nhận được một lỗi phân khúc. 

ĐỐI TƯỢNG: Do Curr bằng null. 

JASON Hirschhorn: Đó là điều tương tự như trước, tuy nhiên, bởi vì có một biến địa phương, chúng tôi đang thiết bằng nút mới này. Chúng ta hãy quay trở lại hình ảnh của chúng tôi chèn một cái gì đó. Nói rằng chúng ta đang chèn vào cuối danh sách, vì vậy ở đây. Chúng tôi có một con trỏ hiện tại đó là trỏ đến null và một điểm trước đó đó là chỉ vào 8. Vì vậy, những gì chúng ta cần phải cập nhật, Avi? 

ĐỐI TƯỢNG: Trước-> tiếp theo? 

JASON Hirschhorn: Trước-> tiếp theo là gì chúng tôi muốn cập nhật, vì đó sẽ thực sự chèn nó vào cuối danh sách. Chúng tôi vẫn còn có một lỗi, tuy nhiên, rằng chúng ta sẽ chạy vào. Lỗi đó là những gì? Yeah? 

ĐỐI TƯỢNG: Nó sẽ quay trở lại sai trong trường hợp này? 

JASON Hirschhorn: Oh, là được sẽ trả về false. Nhưng có lỗi khác. Vì vậy, chúng tôi sẽ cần phải đặt lại đúng. 

ĐỐI TƯỢNG: Liệu trước vẫn bằng null ở đầu danh sách? 

JASON Hirschhorn: vẫn còn Vì vậy, trước bằng null ở đầu. Vậy làm thế nào chúng ta có thể vượt qua được điều đó không? Yeah? 

ĐỐI TƯỢNG: Tôi nghĩ rằng bạn có thể làm một kiểm tra trước khi vòng lặp trong khi để xem nó một danh sách trống. 

JASON Hirschhorn: OK. Vì vậy, hãy đi đây. Làm một kiểm tra. Nếu - 

ĐỐI TƯỢNG: Vì vậy, nếu đầu bằng bằng null. 

JASON Hirschhorn: Nếu đầu bằng bằng null - mà sẽ cho chúng tôi biết nếu nó là một danh sách trống. 

ĐỐI TƯỢNG: Và sau đó bạn làm đầu bằng mới. 

JASON Hirschhorn: Head bằng new_node? Và những gì khác chúng ta cần phải làm gì? 

ĐỐI TƯỢNG: Và sau đó bạn trở lại đúng. 

JASON Hirschhorn: Không hẳn. Chúng ta đang thiếu một bước. 

ĐỐI TƯỢNG: New_node tiếp theo có để trỏ đến null. 

JASON Hirschhorn: Chính xác, Alden. Và sau đó chúng ta có thể trở thành sự thật. OK. Nhưng nó vẫn là một ý tưởng tốt để làm những việc ở cuối danh sách, phải không? Được rồi. Chúng tôi vẫn thực sự có thể nhận được đến cuối danh sách. Như vậy là tốt mã này nếu chúng ta đang ở kết thúc của danh sách và có một số những thứ trong danh sách? Phải không? Bởi vì chúng tôi vẫn còn có ý tưởng của Marcus. Chúng ta có thể thoát khỏi vòng lặp này vì chúng tôi đang ở cuối danh sách. Vì vậy, chúng tôi vẫn muốn này mã xuống đây? 

ĐỐI TƯỢNG: Có. 

JASON Hirschhorn: Vâng. Và làm những gì chúng ta cần phải thay đổi điều này để? Đúng. Không có âm thanh tốt để tất cả mọi người cho đến nay? Bất kỳ ai có bất kỳ - Avi, bạn có một cái gì đó để thêm? 

ĐỐI TƯỢNG: số 

JASON Hirschhorn: OK. Vì vậy, chúng tôi đã thực hiện một vài thay đổi. Chúng tôi đã thực hiện việc kiểm tra này trước khi chúng tôi đã đi vào một danh sách trống. Vì vậy, chúng tôi đã đưa về chăm sóc một danh sách trống. Và ở đây chúng tôi đã chăm sóc của chèn một cái gì đó ở cuối danh sách. Vì vậy, nó có vẻ như trong khi vòng lặp này lấy chăm sóc điều ở giữa, một nơi nào đó trong danh sách nếu có những thứ trong danh sách. 

OK. Chúng ta hãy chạy chương trình này một lần nữa. Không thành công. 

ĐỐI TƯỢNG: Bạn đã không làm cho nó. 

JASON Hirschhorn: Oh, Tôi đã không làm cho nó. Tốt điểm, Michael. Chúng ta hãy thêm một làm cho liên kết. Đường 87 có một lỗi. Dòng 87. Alden, đây là dòng bạn đã cho tôi. Chuyện gì vậy? 

ĐỐI TƯỢNG: Nó phải được để null. 

JASON Hirschhorn: Tuyệt vời. Chính xác. Nó phải là vô giá trị. Chúng ta hãy làm một lần nữa. Biên dịch. OK. Chúng ta hãy chèn ba. Chèn đã thành công. Hãy in ra. Oh, nếu chúng ta chỉ có thể kiểm tra. Nhưng chúng tôi đã không thực hiện các in chức năng được nêu ra. Hãy nhập một cái gì đó khác. Chúng ta nên nhập vào những gì? 

ĐỐI TƯỢNG: Bảy. 

JASON Hirschhorn: Bảy? 

ĐỐI TƯỢNG: Có. 

JASON Hirschhorn: Chúng tôi có một lỗi seg. Vì vậy, chúng tôi có một, nhưng chúng tôi rõ ràng không thể có được hai. Nó là 05:07. Vì vậy chúng tôi có thể gỡ lỗi này trong ba phút. Nhưng tôi sẽ để lại cho chúng tôi ở đây và chuyển sang băm bảng. Nhưng một lần nữa, câu trả lời cho các mã này Tôi sẽ gửi email cho bạn một chút. Chúng tôi rất gần với nó. Tôi rất khuyến khích bạn tìm ra những gì đang xảy ra ở đây và sửa chữa nó. Vì vậy, tôi sẽ gửi email cho bạn mã này như cũng cộng với giải pháp - có lẽ là giải pháp sau này. Đầu tiên mã này. 

Một điều khác tôi muốn làm trước khi chúng tôi kết thúc là chúng tôi đã không giải phóng bất cứ điều gì. Vì vậy, tôi muốn cho bạn thấy những gì valgrind như thế nào. Nếu chúng ta chạy ranh giới valgrind trên chương trình của chúng tôi,. / liên kết. Một lần nữa, theo slide này, chúng tôi nên chạy valgrind với một số loại lựa chọn, trong trường hợp này - Rò rỉ kiểm tra đầy đủ =. Vì vậy, hãy viết valgrind - Rò rỉ kiểm tra đầy đủ =. Vì vậy, đây sẽ chạy valgrind trên chương trình của chúng tôi. Và bây giờ là chương trình thực sự chạy. Vì vậy, chúng ta sẽ chạy nó giống như trước, đặt một cái gì đó in Tôi sẽ đưa ba. Điều đó làm việc. Tôi sẽ không cố gắng để đưa vào một cái gì đó khác vì chúng ta sẽ có được một sai seg trong trường hợp đó. Vì vậy, tôi chỉ cần đi để bỏ thuốc lá. 

Và bây giờ bạn nhìn thấy ở đây bị rò rỉ và tóm tắt đống. Đây là những điều tốt đẹp mà bạn muốn kiểm tra. Vì vậy, các bản tóm tắt đống - nó nói, trong sử dụng ở lối ra - tám byte trong một khối. Đó là một khối là nút chúng tôi malloced. Michael, bạn nói trước khi một nút là tám cắn bởi vì nó có số nguyên và con trỏ. Vì vậy, đó là nút của chúng tôi. Và sau đó nó nói chúng tôi sử dụng malloc bảy lần và chúng tôi tự do một cái gì đó sáu lần. Nhưng chúng tôi không bao giờ được gọi là miễn phí, vì vậy tôi không có ý tưởng này nói về. 

Nhưng nó đủ để nói rằng khi bạn chạy chương trình, malloc đang được gọi là ở một số nơi khác mà chúng tôi không cần phải lo lắng. Vì vậy, có lẽ gọi là malloc ở một số nơi. Chúng tôi không cần phải lo lắng đâu. Nhưng điều này thực sự là chúng tôi. Dòng đầu tiên là chúng tôi. Chúng tôi rời khối. Và bạn có thể thấy ở đây trong phần tóm tắt rò rỉ. Vẫn có thể truy cập - tám byte trong một khối. Điều đó có nghĩa bộ nhớ - chúng tôi đã bị rò rỉ bộ nhớ. Chắc chắn bị mất - một cái gì đó bị mất cho tốt. Nói chung, bạn sẽ không nhìn thấy bất cứ điều gì đó. Vẫn có thể truy cập thường là nơi bạn sẽ thấy mọi thứ, nơi mà bạn sẽ muốn để nhìn xem những gì đang bạn nên đã giải phóng nhưng bạn quên để giải phóng. 

Và sau đó nếu đây không phải là trường hợp, nếu chúng tôi đã làm tất cả mọi thứ miễn phí, chúng tôi có thể kiểm tra. Chúng ta hãy chạy chương trình không đưa vào bất cứ điều gì. Bạn sẽ thấy ở đây được sử dụng ở lối ra - byte trong khối không. Điều đó có nghĩa chúng tôi không còn gì khi chương trình này kết thúc. Vì vậy, trước khi quay trong pset6, chạy valgrind và chắc chắn rằng bạn không có bất kỳ rò rỉ bộ nhớ trong chương trình của bạn. Nếu bạn có bất kỳ câu hỏi với valgrind, cảm thấy tự do để tiếp cận. Nhưng đây là cách bạn sử dụng nó. Rất đơn giản - xem bạn có sử dụng ở lối ra - bất kỳ byte trong bất kỳ khối. 

Vì vậy, chúng tôi đã làm việc trên nút chèn. Tôi đã có hai chức năng khác ở đây - in các nút và các nút miễn phí. Một lần nữa, đây là những chức năng đó sẽ tốt cho bạn để thực hành bởi vì họ sẽ giúp bạn không chỉ với các bài tập mẫu mà còn về vấn đề thiết lập. Họ bản đồ trên khá chặt chẽ để điều bạn sẽ phải làm trong vấn đề thiết lập. Nhưng tôi muốn chắc chắn chúng ta chạm vào tất cả mọi thứ. Và bảng băm cũng rất quan trọng để những gì chúng tôi đang làm trong phần này tuần - hoặc trong bộ vấn đề. 

Vì vậy, chúng ta sẽ hoàn thành phần nói về bảng băm. Nếu bạn nhận thấy tôi đã thực hiện một ít bảng băm. Đó không phải là những gì chúng ta đang nói về, tuy nhiên. Chúng ta đang nói về một khác nhau loại bảng băm. Và cốt lõi, một bảng băm của nó là gì khác hơn một mảng cộng với một hàm băm. Chúng ta sẽ nói chuyện một chút chỉ để chắc chắn rằng tất cả mọi người hiểu được những gì một hàm băm là. Và tôi nói với bạn bây giờ mà nó là không có gì hơn hai điều - một mảng và một hàm băm. Và đây là các bước thông qua mà điều này hoạt động. 

Có mảng của chúng tôi. Có chức năng của chúng tôi. Đặc biệt, hàm băm cần làm một vài điều với điều này. Tôi sẽ nói chuyện cụ thể về vấn đề này thiết lập. Nó có thể sẽ có trong một chuỗi. Và những gì nó sẽ trở lại? Dữ liệu loại? Alden? Hàm băm của bạn trở lại? Một số nguyên. Vì vậy, đây là những gì băm bảng bao gồm - một bảng ở dạng mảng và một hàm băm. Làm thế nào nó hoạt động? Nó hoạt động trong ba bước. Chúng tôi cung cấp cho nó một phím. Trong trường hợp này, chúng tôi sẽ cung cấp cho nó một chuỗi. Chúng ta gọi là hàm băm mỗi bước một trên phím và chúng tôi có được một giá trị. 

Cụ thể, chúng tôi sẽ nói chúng tôi có một số nguyên. Số nguyên, có rất cụ thể giới hạn với những gì số nguyên có thể được. Trong ví dụ này, mảng của chúng tôi có kích thước ba. Vì vậy, những gì con số có thể là số nguyên. Phạm vi của các giá trị hợp lệ cho là những gì số nguyên, kiểu trả về của này băm chức năng? Không, một và hai. Điểm của hàm băm là tìm ra các nơi trong mảng nơi quan trọng của chúng tôi là đi. Chỉ có ba có thể nơi đây - không, một, hoặc hai. Vì vậy, chức năng này tốt hơn trở lại không, một, hoặc hai. Một số các chỉ tiêu giá trị trong mảng này. 

Và sau đó tùy thuộc vào nơi nó trả về, bạn có thể thấy mảng có mở ngoặc giá trị. Đó là nơi mà chúng tôi đưa chìa khóa. Vì vậy, chúng tôi ném trong bí ngô, chúng tôi nhận ra không. Tại khung mảng 0, chúng tôi đặt bí ngô. Chúng tôi ném vào con mèo, chúng tôi nhận ra một. Chúng tôi đặt con mèo ở một. Chúng tôi đưa con nhện. Chúng tôi nhận ra hai. Chúng tôi đặt con nhện ở mảng khung hai. Nó sẽ rất tốt đẹp nếu nó làm việc như thế. Nhưng không may, như chúng ta sẽ thấy, đó là một chút phức tạp hơn. 

Trước khi chúng tôi đến đó, bất kỳ câu hỏi về điều này cơ bản thiết lập một bảng băm? Đây là hình ảnh chính xác những gì chúng tôi đã thu hút trên diễn đàn. Nhưng vì chúng ta vẽ trên bảng, tôi tôi sẽ không đi vào chi tiết hơn. Về cơ bản các phím, hộp đen ma thuật - hoặc trong trường hợp này, teal hộp - một hàm băm đặt chúng trong xô. Và trong ví dụ này chúng tôi không đặt tên. Chúng tôi đang đặt điện thoại liên quan số tên trong xô. Nhưng bạn có thể rất tốt chỉ đặt tên trong xô. 

Đây chỉ là một hình ảnh của những gì chúng tôi đã thu hút trên diễn đàn. Chúng tôi có những cạm bẫy tiềm năng, mặc dù. Và có hai đặc biệt trình bày rằng tôi muốn đi qua. Người đầu tiên là về một hàm băm. Vì vậy, tôi hỏi những câu hỏi, những gì làm cho một hàm băm tốt? Tôi đưa ra hai câu trả lời. Đầu tiên là nó xác định. Trong bối cảnh các hàm băm, điều này có nghĩa là gì? Có? 

ĐỐI TƯỢNG: Nó có thể tìm thấy chỉ số trong thời gian liên tục? 

JASON Hirschhorn: Đó không phải là những gì nó có nghĩa. Nhưng đó là một đoán tốt. Bất cứ ai có một đoán để điều này có nghĩa? Đó là một hàm băm tốt là xác định? Annie? 

ĐỐI TƯỢNG: Đó là một chìa khóa duy nhất có thể được ánh xạ đến một nơi trong bảng băm. 

JASON Hirschhorn: Đó là chính xác. Mỗi khi bạn đưa vào bí ngô, nó luôn luôn trả về số không. Nếu bạn đặt trong bí ngô và băm của bạn chức năng trả về số không, nhưng có một xác suất trở về một cái gì đó khác lớn hơn không - như vậy có lẽ nó có thể trở lại một đôi khi hoặc hai thời điểm khác - đó không phải là một hàm băm tốt. Bạn đúng. Hàm băm của bạn nên trả lại cùng một số nguyên chính xác, trong trường hợp này, chuỗi chính xác. 

Có thể nó trả về số nguyên chính xác cho chuỗi chính xác bất kể vốn. Nhưng trong trường hợp đó nó vẫn còn xác định bởi vì nhiều điều được ánh xạ vào cùng một giá trị. Đó là tốt. Miễn là chỉ có một đầu ra cho một đầu vào nhất định. 

OK. Điều thứ hai là nó trả về chỉ số hợp lệ. Chúng tôi lớn lên mà trước đó. Chức năng này băm - oh boy - một hàm băm nên trở về chỉ số hợp lệ. Vì vậy, nói - chúng ta hãy quay trở lại ví dụ này. Hàm băm của tôi đếm lên các chữ cái trong từ. Đó là hàm băm. Và trả về số nguyên. Vì vậy, nếu tôi có từ A, đó là sẽ trở lại một. Và nó sẽ đặt một ngay tại đây. Nếu tôi đặt trong bat từ? Nó sẽ trở về ba. Trường hợp không dơi đi đâu? 

Nó không phù hợp. Nhưng nó cần phải đi đâu đó. Đây là bảng băm của tôi sau khi tất cả, và tất cả mọi thứ cần phải đi đâu đó. Vì vậy, nơi dơi nên đi đâu? Bất kỳ suy nghĩ? Đoán? Tốt đoán? 

ĐỐI TƯỢNG: Zero. 

JASON Hirschhorn: Tại sao không? 

ĐỐI TƯỢNG: Bởi vì ba modulo ba là số không? 

JASON Hirschhorn: Ba modulo ba là số không. Đó là một đoán tuyệt vời, và đó là chính xác. Vì vậy, trong trường hợp này là cần có thể đi từ số không. Vì vậy, một cách tốt để đảm bảo rằng băm này chức năng chỉ trả về chỉ số hợp lệ để modulo nó bởi kích thước của bảng. Nếu bạn modulo bất cứ điều gì trở lại này bằng cách ba, bạn sẽ luôn luôn được một cái gì đó giữa không, một và hai. Và nếu điều này luôn luôn trả về bảy, và bạn luôn modulo ba, bạn luôn luôn sẽ nhận được điều tương tự. 

Vì vậy, nó vẫn còn xác định nếu bạn modulo. Nhưng điều đó sẽ đảm bảo rằng bạn không bao giờ có được một cái gì đó - một ngành công nghiệp không hợp lệ. Nói chung, theo modulo đó nên xảy ra bên trong hàm băm của bạn. Vì vậy, bạn không cần phải lo lắng về điều này. Bạn chỉ có thể đảm bảo rằng đây là một các chỉ tiêu hợp lệ. Bất kỳ câu hỏi này cạm bẫy tiềm năng? 

OK. Và có chúng tôi đi. Tiếp cạm bẫy tiềm năng, và đây là một trong những lớn. Nếu hai phím bản đồ với giá trị giống nhau không? Vì vậy, có hai cách để xử lý này. Người đầu tiên được gọi là tuyến tính thăm dò, mà tôi không sẽ đi qua. Nhưng bạn nên quen thuộc với cách làm việc và đó là những gì. 

Điều thứ hai tôi sẽ đi qua bởi vì đó là một trong đó nhiều mọi người có thể sẽ kết thúc quyết định để sử dụng trong bộ vấn đề của họ. Tất nhiên, bạn không cần phải. Nhưng đối với các bộ vấn đề, nhiều người có xu hướng chọn để tạo ra một bảng băm với chain riêng biệt để thực hiện từ điển của họ. Vì vậy, chúng ta sẽ đi qua những gì nó có nghĩa là để tạo ra một bảng băm với chain riêng biệt. 

Vì vậy tôi đặt trong bí ngô. Nó trả về số không. Và tôi đặt bí ngô ở đây. Sau đó, tôi đưa vào - một điều Halloween với chủ đề là gì? 

ĐỐI TƯỢNG: Kẹo. 

JASON Hirschhorn: Kẹo! Đó là một tuyệt vời nhất. Tôi đặt trong bánh kẹo, và kẹo cũng mang lại cho tôi không. Tôi phải làm gì? Bất kỳ ý tưởng? Bởi vì bạn biết tất cả các loại những gì chain riêng là. Vì vậy, bất kỳ ý tưởng phải làm gì? Yeah. 

ĐỐI TƯỢNG: Đưa chuỗi thực sự trong bảng băm. 

JASON Hirschhorn: Vì vậy, chúng ta sẽ rút ra những ý tưởng tốt hơn ở đây. OK. 

ĐỐI TƯỢNG: Có hashtable [Nghe được] con trỏ trỏ đến khởi đầu của một danh sách. Và sau đó đã bí ngô có giá trị đầu tiên trong đó danh sách liên kết và kẹo được giá trị thứ hai trong danh sách liên kết mà. 

JASON Hirschhorn: OK. Marcus, đó là nổi bật. Tôi sẽ phá vỡ xuống. Marcus đang nói không ghi đè lên quả bí ngô. Đó sẽ là xấu. Không đặt kẹo ở một nơi khác. Chúng ta sẽ đặt chúng cả ở số không. Nhưng chúng ta sẽ đối phó với đặt chúng ở số không bởi tạo ra một danh sách ở số không. Và chúng ta sẽ tạo ra một danh sách các tất cả mọi thứ mà ánh xạ tới không. Và cách tốt nhất chúng tôi đã học để tạo ra một danh sách có thể phát triển và thu nhỏ động không nằm trong một mảng. Vì vậy, không phải là một mảng đa chiều. Nhưng chỉ cần tạo ra một danh sách liên kết. 

Vì vậy, những gì ông đề xuất - Tôi sẽ có được một mới - là tạo ra một mảng với con trỏ, một mảng của con trỏ. OK. Bất kỳ ý tưởng hoặc gợi ý những gì các loại của con trỏ này nên được? Marcus? 

ĐỐI TƯỢNG: Con trỏ tới - 

JASON Hirschhorn: Bởi vì bạn cho biết một danh sách liên kết, vì vậy - 

ĐỐI TƯỢNG: con trỏ Node? 

JASON Hirschhorn: con trỏ Node. Nếu những điều trong liên kết của chúng tôi danh sách là các nút sau đó họ nên con trỏ nút. Và những gì họ bằng ban đầu? 

ĐỐI TƯỢNG: Null. 

JASON Hirschhorn: Null. Do đó, có điều trống rỗng của chúng tôi. Lợi nhuận bí ngô bằng không. Chúng ta phải làm gì? Đi bộ tôi thông qua nó? Trên thực tế, Marcus đã cho tôi. Người khác đi bộ tôi thông qua nó. Những gì chúng ta làm khi chúng ta - này trông rất giống với những gì chúng tôi đã chỉ làm. Avi. 

ĐỐI TƯỢNG: Tôi sẽ có nhiều phán đoán. Vì vậy, khi bạn nhận được kẹo. 

JASON Hirschhorn: Vâng. Vâng, chúng tôi đã bí ngô. Hãy có được một đầu tiên của chúng tôi. Chúng tôi đã bí ngô. 

ĐỐI TƯỢNG: OK. Lợi nhuận bí ngô bằng không. Vì vậy, bạn đặt nó ở đó. Hoặc thực sự, bạn đặt nó trong danh sách liên kết. 

JASON Hirschhorn: Làm thế nào để chúng tôi đặt nó trong danh sách liên kết? 

ĐỐI TƯỢNG: Oh, cú pháp thực tế? 

JASON Hirschhorn: Chỉ cần đi bộ - nói thêm. Chúng ta phải làm gì? 

ĐỐI TƯỢNG: Bạn chỉ cần chèn nó như là nút đầu tiên. 

JASON Hirschhorn: OK. Vì vậy, chúng tôi có nút của chúng tôi, bí ngô. Và bây giờ làm thế nào để chèn nó? 

ĐỐI TƯỢNG: Bạn chỉ định nó cho con trỏ. 

JASON Hirschhorn: Những con trỏ? 

ĐỐI TƯỢNG: Các con trỏ ở số không. 

JASON Hirschhorn: Vì vậy, nơi không thời điểm này? 

ĐỐI TƯỢNG: Để vô giá trị ngay bây giờ. 

JASON Hirschhorn: Vâng, nó chỉ để null. Nhưng tôi đặt trong bí ngô. Vì vậy, nơi nó nên chỉ? 

ĐỐI TƯỢNG: Để bí ngô. 

JASON Hirschhorn: Để bí ngô. Chính xác. Vì vậy, điều này dẫn đến bí ngô. Và nơi nào con trỏ này tại điểm bí ngô? Để 

ĐỐI TƯỢNG: Null. 

JASON Hirschhorn: Để vô giá trị. Chính xác. Vì vậy, chúng tôi chỉ đưa vào một cái gì đó vào danh sách liên kết. Chúng tôi chỉ viết mã này để làm điều này. Hầu như chúng tôi gần như đã nhận nó hoàn toàn bị nứt. Bây giờ chúng ta chèn kẹo. Kẹo của chúng tôi cũng đi đến số không. Vì vậy, chúng ta làm gì với kẹo? 

ĐỐI TƯỢNG: Nó phụ thuộc vào có hay không chúng tôi đang cố gắng để sắp xếp nó. 

JASON Hirschhorn: Đó là chính xác. Nó phụ thuộc vào có hay không chúng tôi đang cố gắng để sắp xếp nó. Giả sử chúng ta không sẽ sắp xếp nó. 

ĐỐI TƯỢNG: Vậy thì, như chúng ta đã thảo luận trước khi, nó đơn giản nhất chỉ để đặt nó đúng ngay từ đầu để con trỏ từ không có điểm để kẹo. 

JASON Hirschhorn: OK. Giữ. Hãy để tôi tạo ra kẹo ngay tại đây. Vì vậy, con trỏ này - 

ĐỐI TƯỢNG: Vâng, nên bây giờ được trỏ đến kẹo. Sau đó có con trỏ từ điểm kẹo bí ngô. 

JASON Hirschhorn: Giống như điều đó không? Và nói rằng chúng ta đã khác điều để bản đồ không? 

ĐỐI TƯỢNG: Vâng, bạn chỉ làm điều tương tự? 

JASON Hirschhorn: Làm điều tương tự. Vì vậy, trong trường hợp này, nếu chúng ta không muốn giữ nó được sắp xếp nó âm thanh khá đơn giản. Chúng tôi có con trỏ trong các chỉ tiêu được đưa ra bởi hàm băm của chúng tôi. Chúng tôi có điểm đó đến nút mới của chúng tôi. Và sau đó bất cứ điều gì nó đã được chỉ với trước đây - trong trường hợp này vô giá trị, trong trường hợp thứ hai bí ngô - rằng, bất cứ điều gì nó trỏ đến trước đây, chúng tôi thêm vào tiếp theo của nút mới của chúng tôi. Chúng tôi đang chèn một cái gì đó trong đầu. Trong thực tế điều này là đơn giản hơn rất nhiều so với cố gắng để giữ cho các danh sách được sắp xếp. Nhưng một lần nữa, tìm kiếm sẽ được phức tạp hơn ở đây. Chúng tôi sẽ luôn luôn phải đi đến cùng. 

OK. Bất kỳ câu hỏi về xâu chuỗi riêng biệt? Làm thế nào mà làm việc? Xin vui lòng yêu cầu họ bây giờ. Tôi thực sự muốn chắc chắn rằng tất cả các bạn hiểu điều này trước khi chúng tôi đi ra ngoài. 

ĐỐI TƯỢNG: Tại sao bạn đặt bí ngô và kẹo vào cùng một phần của bảng băm? 

JASON Hirschhorn: Câu hỏi. Tại sao chúng ta đặt chúng trong cùng một một phần của bảng băm? Vâng, trong trường hợp này hàm băm của chúng tôi lợi nhuận bằng không cho cả hai người. Vì vậy, họ cần phải đi vào các chỉ tiêu không bởi vì đó là nơi mà chúng ta sẽ tìm kiếm chúng nếu chúng ta muốn xem chúng. Một lần nữa, với một cách tiếp cận tuyến tính thăm dò chúng tôi sẽ không đặt chúng cả ở số không. Nhưng trong cách tiếp cận chuỗi riêng biệt, chúng ta sẽ đặt chúng ở cả không và sau đó tạo ra một danh sách tắt của không. 

Và chúng tôi không muốn ghi đè lên bí ngô chỉ đơn giản cho rằng bởi vì sau đó chúng tôi sẽ cho rằng bí ngô là không bao giờ chèn vào. Nếu chúng ta chỉ giữ một điều trong vị trí đó sẽ là xấu. Sau đó sẽ không có cơ hội của chúng tôi bao giờ hết - nếu chúng ta từng có một bản sao, sau đó chúng tôi sẽ chỉ xóa giá trị ban đầu của chúng tôi. Vì vậy, đó là lý do tại sao chúng tôi làm phương pháp này. Hoặc đó là lý do tại sao chúng tôi chọn - nhưng một lần nữa, chúng tôi chọn phương pháp xâu chuỗi riêng biệt, trong đó có nhiều cách tiếp cận khác người ta có thể lựa chọn. Điều đó trả lời câu hỏi của bạn? 

OK. Carlos. Tuyến tính thăm dò sẽ liên quan đến - nếu chúng ta tìm thấy một vụ va chạm ở số không, chúng tôi sẽ xem xét ở vị trí tiếp theo để xem nó đã được mở và đặt nó ở đó. Và sau đó chúng ta nhìn vào các môn thể thao tiếp theo và xem đó là mở và đặt nó ở đó. Vì vậy, chúng tôi tìm thấy có sẵn tiếp theo vị trí mở và đặt nó ở đó. Bất kỳ câu hỏi nào khác không? Yeah, Avi. 

ĐỐI TƯỢNG: Là một theo dõi đó, làm những gì bạn có ý nghĩa bởi vị trí tiếp theo? Trong bảng băm hoặc trong một danh sách liên kết. 

JASON Hirschhorn: Đối với tuyến tính lập trình, không có danh sách liên kết. Vị trí tiếp theo trên bảng băm. 

ĐỐI TƯỢNG: OK. Vì vậy, các bảng băm sẽ khởi tạo kích thước - như số lượng các chuỗi mà bạn đã chèn? 

JASON Hirschhorn: Bạn sẽ muốn nó được thực sự lớn. Vâng. Đây là một hình ảnh của những gì chúng ta vừa vẽ trên bảng. Một lần nữa, chúng tôi có một vụ va chạm ở đây. 152. Và bạn sẽ thấy chúng tôi tạo ra một danh sách liên kết tắt của nó. Một lần nữa, bảng băm chain riêng cách tiếp cận không phải là một trong những bạn phải đưa cho các vấn đề thiết lập sáu nhưng là một trong những rất nhiều sinh viên có xu hướng mất. Vì vậy, trên lưu ý rằng, chúng ta hãy nói ngắn gọn trước khi chúng tôi đi ra ngoài về vấn đề sáu, và sau đó tôi sẽ chia sẻ một câu chuyện với bạn. Chúng tôi có ba phút. 

Vấn đề thiết lập sáu. Bạn có bốn chức năng - tải, kiểm tra, kích thước, và dỡ bỏ. Tải - tốt, chúng tôi đã đi quá tải ngay bây giờ. Chúng tôi đã thu hút tải trên diễn đàn. Và chúng tôi thậm chí bắt đầu mã hóa rất nhiều chèn vào một danh sách liên kết. Vì vậy, tải không phải là nhiều hơn những gì chúng tôi đã chỉ được làm. 

Kiểm tra là một lần bạn có một cái gì đó nạp. Đó là quá trình tương tự như thế này. Cùng hai phần đầu tiên mà bạn ném một cái gì đó vào hàm băm và nhận được giá trị của nó. Nhưng bây giờ chúng tôi không chèn nó. Bây giờ chúng tôi đang tìm kiếm nó. Tôi đã viết mẫu mã cho việc tìm kiếm một cái gì đó trong một danh sách liên kết. Tôi khuyến khích bạn thực hành điều đó. Nhưng trực giác tìm kiếm một cái gì đó khá tương tự như chèn một cái gì đó. Thật vậy, chúng tôi đã vẽ một bức tranh về việc tìm kiếm một cái gì đó trong một danh sách liên kết, di chuyển thông qua cho đến khi bạn đã kết thúc. Và nếu bạn đã kết thúc và không thể tìm thấy nó, sau đó nó không có ở đó. Vì vậy, đó là kiểm tra, về cơ bản. 

Tiếp theo là kích thước. Chúng ta hãy bỏ qua kích thước. Cuối cùng bạn đã dỡ bỏ. Dỡ bỏ là một trong chúng tôi đã không rút ra trên diễn đàn hoặc mã hoá được nêu ra. Nhưng tôi khuyến khích bạn thử mã hóa nó trong mẫu của chúng tôi danh sách liên kết ví dụ. Nhưng trực giác dỡ bỏ tương tự như miễn phí - hoặc tôi có nghĩa là tương tự để kiểm tra. Ngoại trừ bây giờ mỗi khi bạn đang đi thông qua, bạn không chỉ đơn giản là kiểm tra để xem nếu bạn có giá trị của bạn ở đó. Nhưng bạn đang dùng nút đó và giải phóng nó, về cơ bản. Đó là những gì dỡ bỏ yêu cầu bạn phải làm. Tất cả mọi thứ miễn phí bạn đã malloced. Vì vậy, bạn đang trải qua toàn bộ danh sách một lần nữa, đi qua toàn bộ băm bảng một lần nữa. Thời gian này không kiểm tra để xem những gì đang có. Chỉ giải phóng những gì đang có. 

Và cuối cùng kích thước. Kích thước nên được thực hiện. Nếu bạn không thực hiện kích thước - Tôi sẽ nói nó như thế này. Nếu bạn không thực hiện kích thước chính xác một dòng mã trong đó có tuyên bố quay trở lại, bạn có làm kích thước chính xác. Vì vậy, hãy chắc chắn rằng kích thước, thiết kế đầy đủ điểm, bạn đang làm nó trong một cách chính xác dòng mã, bao gồm cả các tuyên bố trở lại. 

Và không đóng gói được nêu ra, Akchar. Hải ly háo hức. Tôi muốn nói lời cảm ơn các bạn cho đến phần. Có một Halloween vui vẻ. Đây là trang phục của tôi. Tôi sẽ mặc này vào thứ năm nếu tôi nhìn thấy bạn ở giờ hành chính. Và nếu bạn đang tò mò về một số chi tiết nền để trang phục này, cảm thấy miễn phí kiểm tra 2.011 phần cho một câu chuyện về lý do tại sao tôi mặc trang phục bí ngô. Và nó là một câu chuyện buồn. Vì vậy, hãy chắc chắn rằng bạn có một số các mô lân cận. Nhưng vào đó, nếu bạn có bất kỳ câu hỏi tôi sẽ dính xung quanh bên ngoài sau khi phần. May mắn về vấn đề thiết lập sáu. Và như mọi khi, nếu bạn có bất kỳ câu hỏi, cho tôi biết.