>> [MUSIC CHƠI]
>> DOUG LLOYD: OK, vậy tại thời điểm này trong khóa học,
chúng tôi đã bao phủ được rất nhiều các vấn đề cơ bản của C. Chúng tôi biết rất nhiều về các biến, mảng,
con trỏ, tất cả những thứ tốt.
Những người được tất cả các loại xây dựng để xem như là nguyên tắc cơ bản,
nhưng chúng ta có thể làm nhiều hơn nữa, phải không?
Chúng tôi có thể kết hợp những thứ với nhau theo những cách thú vị.
>> Và như vậy chúng ta hãy làm điều đó, hãy bắt đầu chi nhánh ra những gì C cho chúng ta,
và bắt đầu để tạo ra dữ liệu của chúng tôi cơ cấu sử dụng các tòa nhà
khối với nhau để làm một cái gì đó thực sự có giá trị, hữu ích.
Một trong những cách chúng ta có thể làm điều này là để nói về bộ sưu tập.
Vì vậy, cho đến nay chúng ta đã có một loại dữ liệu cấu trúc cho bộ sưu tập đại diện cho
các giá trị thích, giá trị tương tự.
Đó sẽ là một mảng.
Chúng tôi có bộ sưu tập các số nguyên, hoặc bộ sưu tập của các nhân vật và như vậy.
>> Cấu trúc cũng được sắp xếp của một dữ liệu cấu trúc để thu thập thông tin,
nhưng nó không phải là để thu thập như các giá trị.
Nó thường được pha trộn các loại dữ liệu khác nhau với nhau bên trong một hộp duy nhất.
Nhưng nó không phải là bản thân sử dụng để chuỗi lại với nhau
hoặc kết nối với nhau tương tự mặt hàng, như một mảng.
Mảng là tuyệt vời cho yếu tố nhìn lên, nhưng thu hồi
rằng nó rất khó khăn để chèn vào một mảng,
trừ khi chúng tôi đang chèn vào cuối của mảng đó.
>> Và ví dụ tốt nhất mà tôi có cho đó là sắp xếp chèn.
Nếu bạn nhớ lại video của chúng tôi về sắp xếp chèn,
đã có rất nhiều chi phí liên quan đến việc có
để nhận các yếu tố, và chuyển chúng ra khỏi con đường để phù hợp với một cái gì đó
vào giữa mảng của bạn.
Mảng cũng bị khác vấn đề, đó là sự thiếu linh hoạt.
Khi chúng ta khai báo một mảng, chúng ta có được một bắn vào nó.
Chúng tôi nhận được để nói, tôi muốn này có nhiều yếu tố.
Có thể là 100, nó có thể là 1.000, nó có thể
là x trong đó x là một số mà người sử dụng đã cho chúng tôi một dấu nhắc hoặc theo lệnh
dòng.
>> Nhưng chúng tôi chỉ nhận được một bắn vào nó, chúng tôi không nhận được để sau đó nói oh, thực sự tôi
cần 101, hay tôi cần x cộng với 20.
Quá trễ, chúng tôi đã tuyên bố mảng, và nếu chúng ta muốn có được 101 hoặc x
cộng với 20, chúng ta phải khai báo một mảng hoàn toàn khác nhau,
sao chép tất cả các phần tử của mảng hơn, và sau đó chúng ta có đủ.
Và những gì nếu chúng ta sai một lần nữa, những gì nếu chúng ta thực sự cần 102, hoặc x cộng với 40,
chúng ta phải làm điều này một lần nữa.
Vì vậy, họ rất linh hoạt cho thay đổi kích thước dữ liệu của chúng tôi,
nhưng nếu chúng ta kết hợp với nhau một số của những điều cơ bản mà chúng tôi đã đã
học về con trỏ và cấu trúc, đặc biệt là sử dụng bộ nhớ động
phân bổ với malloc, chúng tôi có thể đặt những miếng lại với nhau
để tạo ra một dữ liệu mới structure-- một danh sách liên kết đơn lẻ, chúng tôi có thể say--
cho phép chúng ta phát triển và thu nhỏ một tập hợp các giá trị
và chúng ta sẽ không có bất kỳ không gian lãng phí.
>> Vì vậy, một lần nữa, chúng ta gọi là ý tưởng này, khái niệm này, một danh sách liên kết.
Đặc biệt, trong video này chúng tôi nói về danh sách đơn lẻ liên kết,
và sau đó một video khác, chúng tôi sẽ nói chuyện danh sách khoảng gấp đôi liên kết, trong đó
chỉ là một biến thể của một chủ đề ở đây.
Tuy nhiên, một danh sách liên kết đơn lẻ bao gồm các nút,
nút chỉ là một term-- trừu tượng nó chỉ là cái gì tôi gọi điện thoại
đó là một loại cấu trúc, về cơ bản, tôi?
Chỉ cần đi để gọi nó là một node-- và điều này node có hai thành viên, hoặc hai lĩnh vực.
Nó có dữ liệu, thường là một số nguyên, một nhân vật nổi,
hoặc có thể là một số loại dữ liệu khác mà bạn đã xác định với một loại def.
Và nó có chứa một con trỏ đến một nút khác cùng loại.
>> Vì vậy, chúng ta có hai thứ bên trong của nút này, dữ liệu và một con trỏ
đến một nút khác.
Và nếu bạn bắt đầu để hình dung này, bạn có thể nghĩ về nó
giống như một chuỗi các nút đó được kết nối với nhau.
Chúng tôi có các nút đầu tiên, nó chứa dữ liệu, và một con trỏ
đến nút thứ hai, trong đó có chứa dữ liệu, và một con trỏ đến nút thứ ba.
Và đó là lý do tại sao chúng tôi gọi nó là một danh sách liên kết, họ đang liên kết với nhau.
>> Những gì hiện này đặc biệt cấu trúc nút như thế nào?
Vâng, nếu bạn nhớ lại từ video của chúng tôi trên xác định các loại tùy chỉnh, với loại def,
chúng ta có thể xác định một structure-- và gõ xác định một cấu trúc như thế này.
tyepdef struct sllist, và sau đó tôi sử dụng giá trị từ đây tùy tiện
để chỉ bất kỳ loại dữ liệu thực sự.
Bạn có thể vượt qua trên một số nguyên hoặc float, bạn có thể có bất cứ điều gì bạn muốn.
Nó không bị giới hạn chỉ số nguyên, hoặc bất cứ điều gì như thế.
Vì vậy, giá trị chỉ là một tùy ý kiểu dữ liệu, và sau đó một con trỏ
đến một nút khác cùng loại.
>> Bây giờ, có một chút bắt ở đây với việc xác định một cấu trúc
khi nó là một cấu trúc tự tham chiếu.
Tôi phải có một tạm thời đặt tên cho cấu trúc của tôi.
Vào cuối ngày tôi rõ ràng muốn gọi nó
nút sll, đó là cuối cùng mới đặt tên một phần của định nghĩa kiểu của tôi,
nhưng tôi không thể sử dụng nút sll ở giữa này.
Lý do là, tôi đã không tạo ra một loại gọi là nút sll
cho đến khi tôi đạt điểm cuối cùng này ở đây.
Cho đến thời điểm đó, tôi cần phải có một cách khác để tham khảo kiểu dữ liệu này.
>> Và đây là một tự kiểu dữ liệu tham chiếu.
Nó; s một kiểu dữ liệu của một cấu trúc có chứa một dữ liệu,
và một con trỏ đến một cấu trúc cùng loại.
Vì vậy, tôi cần để có thể tham khảo kiểu dữ liệu này ít nhất là tạm thời,
để cho nó một tạm thời Tên của struct sllist
cho phép tôi để sau đó nói rằng tôi muốn có một con trỏ đến một cấu trúc sllist,
một ngôi sao struct sllist, và sau đó sau khi tôi đã hoàn thành việc xác định,
Tôi bây giờ có thể gọi đây là loại một nút sll.
>> Vì vậy, đó là lý do tại sao bạn nhìn thấy ở đây một cái tên tạm thời ở đây,
nhưng một cái tên thường trực ở đây.
Đôi khi bạn có thể nhìn thấy định nghĩa của cấu trúc,
ví dụ, mà không phải là tự tham chiếu, mà
không có một cái tên đặc tả ở đây.
Nó sẽ chỉ nói typedef struct, mở ngoặc móc và sau đó xác định nó.
Nhưng nếu bạn là struct là tự tham chiếu, như này là,
bạn cần phải xác định một Loại tên tạm thời.
Nhưng cuối cùng, bây giờ rằng chúng tôi đã làm điều này,
chúng ta chỉ có thể tham khảo các nút này, các đơn vị,
như các nút sll cho các mục đích của phần còn lại của video này.
>> Được rồi, vì vậy chúng tôi biết làm thế nào để tạo ra một nút danh sách liên kết.
Chúng tôi biết làm thế nào để xác định một danh sách nút liên kết.
Bây giờ, nếu chúng ta sẽ bắt đầu sử dụng chúng để thu thập thông tin,
có một vài hoạt động, chúng tôi cần phải hiểu và làm việc với.
Chúng tôi cần phải biết làm thế nào để tạo ra một danh sách liên kết trong không khí mỏng.
Nếu không có danh sách đã có, chúng tôi muốn bắt đầu một.
Vì vậy, chúng tôi cần để có thể để tạo ra một danh sách liên kết,
chúng ta cần phải có lẽ tìm thông qua danh sách liên kết
để tìm một phần tử, chúng tôi đang tìm kiếm.
Chúng tôi cần để có thể chèn những điều mới vào danh sách,
chúng ta muốn danh sách của chúng tôi để có thể phát triển.
Và tương tự, chúng tôi muốn có thể để xóa những thứ trong danh sách của chúng tôi,
chúng ta muốn danh sách của chúng tôi để có thể thu nhỏ.
Và vào cuối của chúng tôi các chương trình, đặc biệt là
nếu bạn nhớ lại rằng chúng tôi tự động phân bổ bộ nhớ
để xây dựng các danh sách thông thường, chúng ta muốn giải phóng tất cả các bộ nhớ
khi chúng tôi đang làm việc với nó.
Và vì vậy chúng tôi cần để có thể xóa một toàn bộ danh sách liên kết trong một không swoop.
Vì vậy, hãy đi qua một số các hoạt động này
và làm thế nào chúng ta có thể hình dung họ, nói trong mã giả cụ thể.
Vì vậy, chúng tôi muốn tạo ra một danh sách liên kết, như vậy có lẽ chúng tôi
muốn xác định một chức năng với mẫu thử nghiệm này.
sll sao node, tạo ra, và tôi đang đi qua trong một đối số, một số dữ liệu tùy ý
gõ một lần nữa, một số loại dữ liệu tùy ý.
Nhưng tôi returning-- chức năng này nên trả lại cho tôi một con trỏ, để một đơn lẻ
danh sách liên kết nút.
Một lần nữa, chúng tôi đang cố gắng để tạo ra một danh sách liên kết trong không khí mỏng,
vì vậy tôi cần một con trỏ đến danh sách đó khi tôi đang làm.
>> Vì vậy, các bước liên quan ở đây là gì?
Vâng, điều đầu tiên tôi sẽ làm là tự động
phân bổ không gian cho một nút mới.
Một lần nữa, chúng tôi đang tạo ra nó mỏng không khí, vì vậy chúng tôi cần không gian malloc cho nó.
Và tất nhiên, ngay lập tức sau khi chúng tôi malloc,
chúng tôi luôn kiểm tra để chắc chắn rằng chúng tôi pointer-- chúng tôi đã không nhận được trở lại null.
Bởi vì nếu chúng ta cố gắng và tôn kính một con trỏ null,
chúng ta sẽ phải chịu một segfault và chúng tôi không muốn điều đó.
>> Sau đó, chúng tôi muốn để điền vào trong lĩnh vực này, chúng ta muốn khởi trường giá trị
và khởi tạo các lĩnh vực tiếp theo.
Và sau đó chúng tôi muốn đối với: cuối cùng là prototype indicates-- chúng ta muốn
để trả về một con trỏ tới một nút sll.
Vì vậy, những gì làm cho điều này trông giống như thị giác?
Vâng, đầu tiên chúng ta sẽ phải tự động phân bổ không gian cho một nút sll mới,
vì vậy chúng tôi malloc-- đó một đại diện trực quan
của nút chúng ta vừa tạo.
Và chúng tôi kiểm tra để đảm bảo nó không null-- trong trường hợp này,
hình ảnh sẽ không có hiện lên nếu nó là null,
chúng tôi đã có thể chạy ra khỏi bộ nhớ, vì vậy chúng tôi đang tốt để đi đến đó.
Vì vậy, bây giờ chúng tôi đang ở trên bước C, khởi tạo các lĩnh vực các nút giá trị.
Vâng, dựa trên chức năng này gọi tôi đang sử dụng ở đây,
Dường như tôi muốn vượt qua trong 6, vì vậy tôi sẽ thấy 6 trong trường giá trị.
Bây giờ, khởi tạo các lĩnh vực tiếp theo.
Vâng, những gì tôi sẽ làm gì ở đó, không có gì là tiếp theo, phải,
đây là điều duy nhất trong danh sách.
Vì vậy, điều tiếp theo trong danh sách là những gì?
>> Nó không phải trỏ đến bất cứ điều gì, phải.
Không có gì khác ở đó, như vậy là gì khái niệm mà chúng ta biết đó là nothing--
con trỏ để không có gì?
Nó sẽ được có lẽ chúng ta muốn để đặt một con trỏ null có,
và tôi sẽ đại diện cho các null con trỏ như chỉ là một hộp màu đỏ,
chúng ta không thể đi xa hơn.
Như chúng ta sẽ thấy một chút sau, chúng tôi sẽ có chuỗi cuối cùng
các mũi tên kết nối các nút này lại với nhau,
nhưng khi bạn nhấn hộp màu đỏ, đó là null,
chúng ta không thể đi xa hơn, đó là sự kết thúc của danh sách.
>> Và cuối cùng, chúng tôi chỉ muốn trả về một con trỏ đến nút này.
Vì vậy, chúng tôi sẽ gọi nó là mới, và sẽ trở lại mới
do đó, nó có thể được sử dụng trong chức năng bất cứ điều gì tạo ra nó.
Vì vậy, có chúng tôi đi, chúng tôi đã tạo ra một đơn lẻ liên kết với nút danh sách ra khỏi không khí mỏng,
và bây giờ chúng tôi có một danh sách chúng ta có thể làm việc với.
>> Bây giờ, chúng ta hãy nói rằng chúng ta đã có một chuỗi lớn,
và chúng tôi muốn tìm một cái gì đó trong nó.
Và chúng tôi muốn có một chức năng đó sẽ để trở về đúng hay sai, tùy thuộc
về việc có một giá trị tồn tại trong danh sách đó.
Một nguyên mẫu hàm, hoặc khai cho chức năng đó,
có thể trông giống như this-- Bool tìm, và sau đó chúng tôi muốn vượt qua trong hai đối số.
>> Việc đầu tiên, là một con trỏ trỏ tới Yếu tố đầu tiên của danh sách liên kết.
Đây thực sự là một cái gì đó bạn sẽ luôn muốn theo dõi,
và thực sự có thể là một cái gì đó bạn thậm chí còn đặt trong một biến toàn cầu.
Khi bạn tạo ra một danh sách, bạn luôn luôn, luôn luôn
muốn theo dõi của rất Yếu tố đầu tiên của danh sách.
Bằng cách đó bạn có thể tham khảo tất cả các khác phần tử bằng cách chỉ làm theo chuỗi,
mà không cần phải giữ con trỏ còn nguyên vẹn đến từng yếu tố duy nhất.
Bạn chỉ cần để theo dõi những người đầu tiên một nếu tất cả họ đang xích lại với nhau.
>> Và sau đó là điều thứ hai chúng ta đang đi trong một lần nữa
là tùy tiện some-- bất cứ loại dữ liệu chúng tôi
tìm kiếm có bên trong hy vọng một trong các nút trong danh sách.
Vì vậy, các bước là gì?
Vâng, điều đầu tiên chúng tôi làm là chúng ta tạo ra một con trỏ ngang
trỏ đến đầu danh sách.
Vâng, tại sao chúng ta làm điều đó, chúng tôi đã có một con trỏ ở đầu danh sách,
tại sao chúng ta không chỉ di chuyển một mà xung quanh?
Vâng, như tôi vừa nói, nó thực sự quan trọng đối với chúng tôi
để luôn theo dõi các Yếu tố đầu tiên trong danh sách.
Và do đó, nó thực sự tốt hơn để tạo ra một bản sao của rằng,
và sử dụng để di chuyển xung quanh vì vậy chúng tôi không bao giờ vô tình di chuyển đi, hoặc chúng tôi luôn
có một con trỏ tại một số điểm đó là phải vào phần tử đầu tiên của danh sách.
Vì vậy, nó là tốt hơn để tạo ra một thứ hai mà chúng tôi sử dụng để di chuyển.
>> Sau đó, chúng ta chỉ cần so sánh xem trường giá trị tại nút đó
là những gì chúng tôi đang tìm kiếm, và nếu nó không, chúng ta chỉ cần di chuyển đến nút tiếp theo.
Và chúng tôi tiếp tục làm điều đó hơn, và hơn và hơn,
cho đến khi chúng tôi có thể tìm thấy phần tử, hoặc chúng ta nhấn
null-- chúng tôi đã đạt đến cuối cùng của danh sách và nó là không có.
Điều này hy vọng sẽ rung chuông với bạn như chỉ tìm kiếm tuyến tính,
chúng tôi chỉ là bản sao của nó trong một cấu trúc danh sách liên kết đơn lẻ
thay vì sử dụng một mảng để làm điều đó.
>> Vì vậy, đây là một ví dụ của một danh sách đơn lẻ liên kết.
Điều này bao gồm năm nút, và chúng tôi có
một con trỏ đến đầu của danh sách, được gọi là danh sách.
Điều đầu tiên chúng tôi muốn làm là một lần nữa, tạo ra rằng con trỏ traversal.
Vì vậy, chúng tôi có bây giờ hai con trỏ điểm đó đến cùng một điều.
>> Bây giờ, nhận thấy đây cũng có, tôi đã không phải malloc bất kỳ không gian cho trav.
Tôi đã không nói trav bằng malloc một cái gì đó, nút đó đã tồn tại,
rằng không gian trong bộ nhớ đã tồn tại.
Vì vậy, tất cả những gì đang thực sự làm là việc tạo ra một con trỏ đến nó.
Tôi không mallocing thêm không gian, chỉ có bây giờ hai con trỏ
trỏ đến cùng một điều.
>> Vậy là 2 những gì tôi đang tìm kiếm?
Vâng, không có, vì vậy thay vì tôi sẽ di chuyển đến kế tiếp.
Vì vậy, về cơ bản tôi sẽ nói, trav bằng trav tiếp theo.
Là 3 những gì tôi đang tìm kiếm, không có.
Vì vậy, tôi tiếp tục đi thông qua, cho đến khi cuối cùng
có đến 6 đó là những gì tôi đang tìm kiếm cho dựa trên các cuộc gọi chức năng
Tôi có ở đầu ở đó, và vì vậy tôi thực hiện.
>> Bây giờ, nếu các yếu tố tôi những gì tìm đã không có trong danh sách,
là nó vẫn đi làm à?
Vâng, chú ý rằng danh sách đây là tinh tế khác nhau,
và đây là một điều đó là quan trọng với danh sách liên kết,
bạn không có để bảo tồn chúng trong bất kỳ thứ tự cụ thể.
Bạn có thể nếu bạn muốn, nhưng bạn có thể đã nhận thấy
rằng chúng tôi không theo dõi các những gì số lượng phần tử chúng ta đang ở.
>> Và đó là sắp xếp của một thương mại mà chúng ta có với danh sách liên kết câu mảng,
được nó, chúng ta không có truy cập ngẫu nhiên nữa.
Chúng ta không thể chỉ nói, tôi muốn để đi tới phần tử 0,
hoặc các yếu tố thứ 6 của mảng của tôi, mà tôi có thể làm trong một mảng.
Tôi không thể nói tôi muốn đi đến 0 tố, hoặc các yếu tố thứ 6,
hoặc các yếu tố thứ 25 của danh sách liên kết của tôi, không có chỉ số liên quan đến họ.
Và vì vậy nó không thực sự quan trọng nếu chúng ta giữ gìn danh sách theo thứ tự.
Nếu bạn muốn cho bạn chắc chắn có thể, nhưng có
không có lý do tại sao họ cần phải được bảo quản trong bất kỳ thứ tự.
Vì vậy, một lần nữa, chúng ta hãy cố gắng và tìm 6 trong danh sách này.
Vâng, chúng ta bắt đầu ở bắt đầu, chúng tôi không tìm thấy 6,
và sau đó chúng tôi tiếp tục không tìm thấy 6, cho đến khi chúng tôi cuối cùng nhận được để ở đây.
Vì vậy, ngay điểm bây giờ trav đến nút có chứa 8, và sáu không có trong đó.
>> Vì vậy, bước tiếp theo sẽ là để đi đến con trỏ tới,
do đó, nói trav bằng trav tiếp theo.
Vâng, trav tiếp theo, chỉ định bởi hộp màu đỏ ở đó, là null.
Vì vậy, không có chỗ nào khác để đi, và vào thời điểm này
chúng ta có thể kết luận rằng chúng tôi đã đạt sự kết thúc của danh sách liên kết,
và 6 không phải là ở đó.
Và nó sẽ được trả lại sai trong trường hợp này.
>> OK, làm thế nào để chúng ta chèn một mới nút vào danh sách liên kết?
Vì vậy, chúng tôi đã có thể tạo ra một danh sách liên kết ra khỏi hư không,
nhưng có lẽ chúng ta muốn xây dựng một chuỗi và không
tạo ra một loạt các danh sách riêng biệt.
Chúng tôi muốn có một danh sách đó có một loạt các nút trong nó,
không phải là một loạt các danh sách với một nút duy nhất.
Vì vậy, chúng ta không thể tiếp tục sử dụng Tạo chức năng, chúng tôi xác định trước đó, bây giờ chúng tôi
muốn chèn vào một danh sách đó đã tồn tại.
>> Vì vậy, trường hợp này, chúng ta sẽ để vượt qua trong hai tham số,
con trỏ đến đầu của đó danh sách mà chúng tôi muốn thêm vào liên kết.
Một lần nữa, đó là lý do tại sao nó là như vậy quan trọng là chúng tôi luôn luôn
theo dõi của nó, bởi vì đó là cách duy nhất chúng ta thực sự
phải tham khảo cho toàn bộ danh là chỉ bởi một con trỏ tới phần tử đầu tiên.
Vì vậy, chúng tôi muốn vượt qua trong một con trỏ tới phần tử đầu tiên,
và bất cứ điều gì giá trị chúng tôi muốn thêm vào danh sách.
Và cuối cùng chức năng này sẽ trả về một con trỏ
cho người đứng đầu mới của một danh sách liên kết.
>> Các bước liên quan ở đây là gì?
Vâng, giống như với tạo, chúng ta cần phải tự động phân bổ
không gian cho một nút mới, và kiểm tra để chắc chắc chắn chúng tôi không chạy ra khỏi bộ nhớ, một lần nữa,
bởi vì chúng ta đang sử dụng malloc.
Sau đó, chúng tôi muốn cư và chèn các nút,
do đó, đặt số lượng, bất cứ điều gì val là, vào các nút.
Chúng tôi muốn chèn nút tại đầu của danh sách liên kết.
>> Có một lý do mà tôi muốn làm điều này, và nó
có thể là giá trị tham gia một giây tạm dừng video ở đây,
và suy nghĩ về lý do tại sao tôi muốn chèn vào đầu của một liên kết
danh sách.
Một lần nữa, tôi đã đề cập trước đó rằng nó không thực sự
quan trọng nếu chúng ta giữ gìn nó trong bất kỳ trật tự, như vậy có lẽ đó là một đầu mối.
Và bạn đã thấy những gì sẽ xảy ra nếu chúng tôi muốn đối với: hoặc từ chỉ một giây
trước khi chúng tôi đã đi thông qua tìm kiếm bạn
có thể nhìn thấy những gì có thể xảy ra nếu chúng tôi đã cố gắng
để chèn vào cuối danh sách.
Bởi vì chúng ta không có một con trỏ đến cuối danh sách.
>> Vì vậy, lý do mà tôi muốn để chèn vào đầu,
là bởi vì tôi có thể làm điều đó ngay lập tức.
Tôi có một con trỏ ở đầu, và chúng ta sẽ thấy điều này trong một hình ảnh trong một giây.
Nhưng nếu tôi muốn chèn ở cuối, Tôi phải bắt đầu ngay từ đầu,
đi qua tất cả các cách để các kết thúc, và sau đó sẽ dán nó vào.
Vì vậy, điều đó có nghĩa rằng chèn vào cuối danh sách
sẽ trở thành một o của n hoạt động, đi lại
để thảo luận về tính toán phức tạp.
Nó muốn trở thành một o n hoạt động, nơi như danh sách đã lớn hơn, và lớn hơn,
và lớn hơn, nó sẽ trở thành nhiều hơn và khó khăn hơn để tack một cái gì đó
vào lúc kết thúc.
Nhưng nó luôn luôn thực sự dễ dàng để tack một cái gì đó vào lúc đầu,
bạn luôn ở đầu.
>> Và chúng ta sẽ thấy một hình ảnh này một lần nữa.
Và sau đó một khi chúng ta đã thực hiện xong, một lần chúng tôi đã chèn node mới,
chúng tôi muốn trở lại con trỏ của chúng tôi để người đứng đầu mới của một danh sách liên kết, trong đó
vì chúng ta đang chèn vào bắt đầu, thực sự sẽ là
một con trỏ đến nút chúng ta vừa tạo.
Hãy hình dung này, bởi vì tôi nghĩ rằng nó sẽ giúp đỡ.
>> Vì vậy, đây là danh sách của chúng tôi, nó bao gồm bốn yếu tố, một nút chứa 15,
mà chỉ vào một nút chứa 9,
chỉ với một nút chứa 13, mà điểm đến một nút có chứa
10, trong đó có null con trỏ như con trỏ tiếp theo
vì vậy đó là sự kết thúc của danh sách.
Vì vậy, chúng tôi muốn chèn một nút mới với giá trị 12
vào đầu này danh sách, chúng ta làm gì?
Vâng, đầu tiên chúng ta malloc không gian cho các nút, và sau đó chúng tôi đặt 12 trong đó.
>> Vì vậy, bây giờ chúng tôi đã đạt đến một điểm quyết định, phải không?
Chúng tôi có một vài gợi ý rằng chúng ta có thể
di chuyển, mà một trong chúng ta nên di chuyển đầu tiên?
Chúng ta nên làm cho 12 điểm đến người đứng đầu mới của list--
hay tha thứ cho tôi, chúng ta nên làm cho 12 trỏ đến đầu cũ của danh sách?
Hoặc chúng ta nên nói rằng danh sách doanh nghiệp bắt đầu vào lúc 12.
Có một sự khác biệt ở đó, và chúng tôi sẽ xem xét
những gì xảy ra với cả hai trong một giây.
>> Nhưng điều này dẫn đến một chủ đề lớn cho sidebar,
đó là một trong những điều khó khăn nhất với danh sách liên kết
là để sắp xếp các con trỏ theo thứ tự đúng.
Nếu bạn di chuyển mọi thứ trong trật tự, bạn có thể kết thúc vô tình
orphaning phần còn lại của danh sách.
Và đây là một ví dụ về điều đó.
Vì vậy, chúng ta hãy đi với ý tưởng of-- tốt, chúng tôi đã chỉ ra 12.
Chúng ta biết 12 là có được người đứng đầu mới của danh sách,
và như vậy tại sao chúng ta không chỉ cần di chuyển con trỏ danh sách chỉ có.
>> OK, vậy thì tốt.
Vì vậy, bây giờ nơi nào 12 điểm tiếp theo?
Tôi có nghĩa là, chúng ta có thể nhìn thấy bằng mắt rằng nó sẽ trỏ đến 15,
như con người nó thực sự rõ ràng cho chúng tôi.
Làm thế nào để máy tính biết?
Chúng tôi không có bất cứ điều gì trỏ đến 15 nữa, đúng không?
>> Chúng tôi đã bị mất bất kỳ khả năng tham khảo 15.
Chúng tôi không thể nói mũi tên mới equals tiếp theo một cái gì đó, không có gì có.
Trong thực tế, chúng tôi đã mồ côi phần còn lại của danh sách
bởi làm như vậy, chúng tôi đã vô tình phá vỡ dây chuyền.
Và chúng tôi chắc chắn không muốn làm điều đó.
>> Vì vậy, chúng ta hãy quay trở lại và thử lại.
Có lẽ những điều phải làm là để thiết lập con trỏ tới 12 của
cho người đứng đầu cũ của danh sách đầu tiên, sau đó chúng ta có thể di chuyển trong danh sách trong.
Và trên thực tế, đó là đúng thứ tự mà chúng ta
phải tuân theo khi chúng tôi làm việc với các danh sách đơn lẻ liên kết.
Chúng tôi luôn luôn muốn kết nối các nguyên tố mới vào danh sách,
trước khi chúng tôi mất rằng loại bước quan trọng của việc thay đổi
nơi người đứng đầu của danh sách liên kết là.
Một lần nữa, đó là một điều cơ bản như vậy, chúng tôi không muốn để mất theo dõi của nó.
>> Vì vậy, chúng tôi muốn chắc chắn rằng mọi thứ được xích lại với nhau,
trước khi chúng tôi di chuyển con trỏ đó.
Và vì vậy đây sẽ là thứ tự đúng, mà là để kết nối 12 vào danh sách,
sau đó nói rằng danh sách này bắt đầu một 12.
Nếu chúng ta biết danh sách bắt đầu lúc 12 và sau đó đã cố gắng để kết nối 12 vào danh sách,
chúng tôi đã nhìn thấy những gì xảy ra.
Chúng ta mất danh sách bằng cách sai lầm.
>> OK, vì vậy một điều nữa để nói về.
Điều gì nếu chúng ta muốn thoát khỏi một toàn bộ danh sách liên kết cùng một lúc?
Một lần nữa, chúng tôi đang mallocing tất cả các không gian này, và vì vậy chúng tôi
cần phải giải phóng nó khi chúng ta đang thực hiện.
Vì vậy, bây giờ chúng tôi muốn xóa toàn bộ danh sách liên kết.
Vâng, những gì chúng ta muốn làm gì?
>> Nếu chúng tôi đã đạt đến con trỏ null, chúng tôi muốn dừng lại, nếu không, chỉ cần xóa
phần còn lại của danh sách và sau đó thoát tôi.
Xóa phần còn lại của danh sách, và sau đó giải phóng các nút hiện hành.
Âm thanh gì như thế, những gì kỹ thuật có chúng tôi nói chuyện
về trước mà âm thanh như thế nào?
Xóa tất cả mọi người khác, sau đó trở lại và xóa tôi.
>> Đó là đệ quy, chúng tôi đã thực hiện các vấn đề một chút nhỏ hơn,
chúng ta đang nói xóa tất cả mọi người khác, sau đó bạn có thể xóa tôi.
Và tiếp tục xuống đường, nút đó sẽ nói, xóa tất cả mọi người khác.
Nhưng cuối cùng chúng tôi sẽ nhận được vào điểm mà danh sách là null,
và đó là trường hợp cơ sở của chúng tôi.
>> Vì vậy, chúng ta hãy nhìn vào điều này, và làm thế nào điều này có thể làm việc.
Vì vậy, đây là danh sách của chúng tôi, đó là cùng liệt kê chúng tôi chỉ nói về,
và có các bước.
Có rất nhiều các văn bản ở đây, nhưng hy vọng những hình dung được sẽ giúp.
>> Vì vậy, chúng tôi have-- và tôi cũng kéo lên khung stack minh họa của chúng tôi
từ video của chúng tôi trên ngăn xếp cuộc gọi, và hy vọng tất cả điều này
với nhau sẽ cho bạn thấy những gì đang xảy ra.
Vì vậy, đây là mã giả của chúng tôi.
Nếu chúng ta đạt đến một null con trỏ, dừng lại, nếu không,
xóa phần còn lại của danh sách, sau đó giải phóng các nút hiện hành.
Vì vậy, ngay bây giờ, list-- các con trỏ mà chúng tôi
đi qua trong để tiêu diệt điểm đến 12.
12 không phải là một con trỏ null, vì vậy chúng tôi sẽ xóa phần còn lại của danh sách.
>> Những gì được xóa phần còn lại của chúng tôi tham gia?
Vâng, nó có nghĩa là làm một gọi để tiêu diệt, nói
rằng 15 là sự khởi đầu của phần còn lại của danh sách, chúng tôi muốn tiêu diệt.
Và do đó, các cuộc gọi đến phá hủy 12 là loại giữ.
Nó đóng băng ở đó, chờ đợi gọi để tiêu diệt 15, để kết thúc công việc của mình.
>> Vâng, 15 không phải là một con trỏ null, và do đó, nó sẽ nói, tất cả các quyền,
tốt, xóa phần còn lại của danh sách.
Phần còn lại của danh sách bắt đầu tại 9, và vì vậy chúng tôi sẽ chỉ
chờ đợi cho đến khi bạn xóa tất cả những gì công cụ, sau đó trở lại và xóa tôi.
Vâng 9 sẽ nói, tốt, Tôi không phải là một con trỏ null,
để xóa phần còn lại trong danh sách tại đây.
Và vì vậy hãy thử và phá hủy 13.
13 nói, tôi không phải là con trỏ null, cùng một điều, nó vượt qua buck.
10 không phải là con trỏ null, 10 chứa một con trỏ null,
nhưng 10 không phải là bản thân một rỗng trỏ ngay bây giờ,
và để nó vượt qua buck quá.
>> Và bây giờ liệt kê điểm đó, nó thực sự sẽ trỏ đến some--
nếu tôi đã có nhiều không gian hơn trong hình ảnh, nó sẽ trỏ đến một số không gian ngẫu nhiên
rằng chúng ta không biết nó là gì.
Đó là con trỏ null, mặc dù danh sách là nghĩa đen bây giờ thiết lập nó là giá trị null.
Nó chỉ ngay bên trong cái hộp màu đỏ.
Chúng tôi đi đến một con trỏ null, vì vậy chúng ta có thể dừng lại, và chúng tôi đang thực hiện.
>> Và vì vậy mà khung màu tím là now-- tại đầu stack-- đó là khung hoạt động,
nhưng nó được thực hiện.
Nếu chúng tôi đã đạt đến một con trỏ null, dừng lại.
Chúng tôi không làm bất cứ điều gì, chúng tôi không thể giải phóng một con trỏ null,
chúng tôi đã không malloc bất kỳ không gian, và vì vậy chúng tôi đang thực hiện.
Vì vậy mà khung chức năng bị phá hủy, và chúng tôi
resume-- chúng tôi nhận ra nơi chúng tôi rời off với mức cao nhất trong những kế tiếp, mà
là màu xanh khung tối này ở đây.
Vì vậy, chúng tôi tiếp tục ngay tại nơi chúng tôi rời đi.
Chúng tôi đã xóa phần còn lại của danh sách đã có, vì vậy bây giờ chúng tôi
đi để giải phóng các nút hiện hành.
Vì vậy, bây giờ chúng tôi có thể giải phóng nút này, và bây giờ chúng tôi đã đạt đến kết thúc của hàm.
Và vì vậy mà khung chức năng bị phá hủy, và chúng tôi đón tại một ánh sáng màu xanh.
>> Vì vậy, nó says-- Tôi đã done-- xóa phần còn lại của danh sách, vì
giải phóng các nút hiện hành.
Và bây giờ khung màu vàng là trở lại trên cùng của ngăn xếp.
Và như vậy, bạn thấy, chúng tôi bây giờ phá hủy danh sách các từ phải sang trái.
>> Điều gì sẽ xảy ra, mặc dù, nếu chúng tôi đã làm điều sai cách?
Cũng giống như khi chúng ta cố gắng để thêm một yếu tố.
Nếu chúng ta sai lầm của chuỗi, nếu chúng tôi đã không kết nối các con trỏ
theo đúng thứ tự, nếu chúng tôi chỉ giải phóng các yếu tố đầu tiên,
nếu chúng ta chỉ giải phóng đứng đầu danh sách, bây giờ chúng tôi
không có cách nào để tham khảo phần còn lại của danh sách.
Và như vậy chúng ta sẽ có tất cả mọi thứ mồ côi,
chúng tôi sẽ có những gì được gọi là một rò rỉ bộ nhớ.
Nếu bạn nhớ lại từ video của chúng tôi về cấp phát bộ nhớ động,
đó không phải là điều rất tốt.
>> Vì vậy, như tôi đã nói, có một số hoạt động
rằng chúng ta cần phải sử dụng để làm việc với danh sách liên kết có hiệu quả.
Và bạn có thể đã nhận thấy tôi bỏ qua một, xóa một yếu tố duy nhất từ ​​một liên kết
danh sách.
Lý do tôi đã làm điều đó là nó thực sự loại
khó khăn để suy nghĩ về làm thế nào để xóa một yếu tố duy nhất từ ​​một đơn lẻ
danh sách liên kết.
Chúng tôi cần để có thể bỏ qua một cái gì đó trong danh sách, trong đó
có nghĩa là chúng ta có được một chúng point-- muốn xóa node-- này
nhưng để làm cho nó vì vậy chúng tôi không bị mất bất kỳ thông tin,
chúng ta cần phải kết nối này nút ở đây, ở đây.
>> Vì vậy, có lẽ tôi đã làm điều đó sai từ góc độ thị giác.
Vì vậy, chúng tôi đang ở đầu của chúng tôi danh sách, chúng tôi đang tiến hành thông qua,
chúng ta muốn xóa nốt này.
Nếu chúng ta chỉ cần xóa nó, chúng tôi đã phá vỡ chuỗi.
Nút này ngay tại đây đề cập đến tất cả mọi thứ khác,
nó có chứa các chuỗi từ đây trên ra ngoài.
>> Vì vậy, những gì chúng ta cần làm thực sự sau khi chúng tôi có được đến thời điểm này,
là chúng ta cần phải bước trở lại một, và kết nối nút này sang nút này,
vì vậy chúng ta có thể xóa một trong những khu trung lộ.
Nhưng danh sách đơn lẻ liên kết không cung cấp cho chúng ta một con đường để đi về phía sau.
Vì vậy, chúng ta cần phải hoặc là giữ hai con trỏ, và di chuyển chúng
loại bước ra, một ở phía sau khác như chúng tôi đi, hoặc có một điểm
và sau đó gửi một con trỏ qua.
Và như bạn thấy, nó có thể có được một chút lộn xộn.
May mắn thay, chúng tôi có một cách khác để giải quyết đó,
khi chúng ta nói về danh sách liên kết kép.
>> Tôi Doug Lloyd, đây là CS50.