1 00:00:00,000 --> 00:00:02,832 >> [MUSIC CHƠI] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, vậy tại thời điểm này trong khóa học, 4 00:00:08,560 --> 00:00:15,300 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, 5 00:00:15,300 --> 00:00:17,610 con trỏ, tất cả những thứ tốt. 6 00:00:17,610 --> 00:00:21,610 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, 7 00:00:21,610 --> 00:00:23,880 nhưng chúng ta có thể làm nhiều hơn nữa, phải không? 8 00:00:23,880 --> 00:00:27,930 Chúng tôi có thể kết hợp những thứ với nhau theo những cách thú vị. 9 00:00:27,930 --> 00:00:31,010 >> 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, 10 00:00:31,010 --> 00:00:35,270 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à 11 00:00:35,270 --> 00:00:40,590 khối với nhau để làm một cái gì đó thực sự có giá trị, hữu ích. 12 00:00:40,590 --> 00:00:43,420 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. 13 00:00:43,420 --> 00:00:48,360 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 14 00:00:48,360 --> 00:00:51,030 các giá trị thích, giá trị tương tự. 15 00:00:51,030 --> 00:00:52,350 Đó sẽ là một mảng. 16 00:00:52,350 --> 00:00:57,020 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. 17 00:00:57,020 --> 00:01:00,890 >> 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, 18 00:01:00,890 --> 00:01:03,220 nhưng nó không phải là để thu thập như các giá trị. 19 00:01:03,220 --> 00:01:08,090 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. 20 00:01:08,090 --> 00:01:10,750 Nhưng nó không phải là bản thân sử dụng để chuỗi lại với nhau 21 00:01:10,750 --> 00:01:16,920 hoặc kết nối với nhau tương tự mặt hàng, như một mảng. 22 00:01:16,920 --> 00:01:20,960 Mảng là tuyệt vời cho yếu tố nhìn lên, nhưng thu hồi 23 00:01:20,960 --> 00:01:24,262 rằng nó rất khó khăn để chèn vào một mảng, 24 00:01:24,262 --> 00:01:26,470 trừ khi chúng tôi đang chèn vào cuối của mảng đó. 25 00:01:26,470 --> 00:01:29,730 >> Và ví dụ tốt nhất mà tôi có cho đó là sắp xếp chèn. 26 00:01:29,730 --> 00:01:31,650 Nếu bạn nhớ lại video của chúng tôi về sắp xếp chèn, 27 00:01:31,650 --> 00:01:34,110 đã có rất nhiều chi phí liên quan đến việc có 28 00:01:34,110 --> 00:01:37,970 để 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ì đó 29 00:01:37,970 --> 00:01:41,290 vào giữa mảng của bạn. 30 00:01:41,290 --> 00:01:44,690 Mảng cũng bị khác vấn đề, đó là sự thiếu linh hoạt. 31 00:01:44,690 --> 00:01:47,150 Khi chúng ta khai báo một mảng, chúng ta có được một bắn vào nó. 32 00:01:47,150 --> 00:01:49,790 Chúng tôi nhận được để nói, tôi muốn này có nhiều yếu tố. 33 00:01:49,790 --> 00:01:51,940 Có thể là 100, nó có thể là 1.000, nó có thể 34 00:01:51,940 --> 00:01:55,930 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 35 00:01:55,930 --> 00:01:56,630 dòng. 36 00:01:56,630 --> 00:01:59,905 >> 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 37 00:01:59,905 --> 00:02:04,360 cần 101, hay tôi cần x cộng với 20. 38 00:02:04,360 --> 00:02:07,910 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 39 00:02:07,910 --> 00:02:12,050 cộng với 20, chúng ta phải khai báo một mảng hoàn toàn khác nhau, 40 00:02:12,050 --> 00:02:15,540 sao chép tất cả các phần tử của mảng hơn, và sau đó chúng ta có đủ. 41 00:02:15,540 --> 00:02:19,880 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, 42 00:02:19,880 --> 00:02:21,970 chúng ta phải làm điều này một lần nữa. 43 00:02:21,970 --> 00:02:26,250 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, 44 00:02:26,250 --> 00:02:29,360 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 đã đã 45 00:02:29,360 --> 00:02:33,230 học về con trỏ và cấu trúc, đặc biệt là sử dụng bộ nhớ động 46 00:02:33,230 --> 00:02:36,180 phân bổ với malloc, chúng tôi có thể đặt những miếng lại với nhau 47 00:02:36,180 --> 00:02:40,960 để 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-- 48 00:02:40,960 --> 00:02:45,400 cho phép chúng ta phát triển và thu nhỏ một tập hợp các giá trị 49 00:02:45,400 --> 00:02:48,800 và chúng ta sẽ không có bất kỳ không gian lãng phí. 50 00:02:48,800 --> 00:02:53,320 >> 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. 51 00:02:53,320 --> 00:02:56,320 Đặc biệt, trong video này chúng tôi nói về danh sách đơn lẻ liên kết, 52 00:02:56,320 --> 00:02:59,185 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 đó 53 00:02:59,185 --> 00:03:01,560 chỉ là một biến thể của một chủ đề ở đây. 54 00:03:01,560 --> 00:03:05,200 Tuy nhiên, một danh sách liên kết đơn lẻ bao gồm các nút, 55 00:03:05,200 --> 00:03:08,559 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 56 00:03:08,559 --> 00:03:10,350 đó là một loại cấu trúc, về cơ bản, tôi? 57 00:03:10,350 --> 00:03:16,190 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. 58 00:03:16,190 --> 00:03:20,300 Nó có dữ liệu, thường là một số nguyên, một nhân vật nổi, 59 00:03:20,300 --> 00:03:23,790 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. 60 00:03:23,790 --> 00:03:29,290 Và nó có chứa một con trỏ đến một nút khác cùng loại. 61 00:03:29,290 --> 00:03:34,710 >> 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ỏ 62 00:03:34,710 --> 00:03:36,380 đến một nút khác. 63 00:03:36,380 --> 00:03:39,370 Và nếu bạn bắt đầu để hình dung này, bạn có thể nghĩ về nó 64 00:03:39,370 --> 00:03:42,280 giống như một chuỗi các nút đó được kết nối với nhau. 65 00:03:42,280 --> 00:03:45,070 Chúng tôi có các nút đầu tiên, nó chứa dữ liệu, và một con trỏ 66 00:03:45,070 --> 00:03:49,110 đến nút thứ hai, trong đó có chứa dữ liệu, và một con trỏ đến nút thứ ba. 67 00:03:49,110 --> 00:03:52,940 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. 68 00:03:52,940 --> 00:03:56,070 >> Những gì hiện này đặc biệt cấu trúc nút như thế nào? 69 00:03:56,070 --> 00:04:01,120 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, 70 00:04:01,120 --> 00:04:05,400 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. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, và sau đó tôi sử dụng giá trị từ đây tùy tiện 72 00:04:11,240 --> 00:04:13,891 để chỉ bất kỳ loại dữ liệu thực sự. 73 00:04:13,891 --> 00:04:16,890 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. 74 00:04:16,890 --> 00:04:19,389 Nó không bị giới hạn chỉ số nguyên, hoặc bất cứ điều gì như thế. 75 00:04:19,389 --> 00:04:22,790 Vì vậy, giá trị chỉ là một tùy ý kiểu dữ liệu, và sau đó một con trỏ 76 00:04:22,790 --> 00:04:26,310 đến một nút khác cùng loại. 77 00:04:26,310 --> 00:04:29,690 >> Bây giờ, có một chút bắt ở đây với việc xác định một cấu trúc 78 00:04:29,690 --> 00:04:33,030 khi nó là một cấu trúc tự tham chiếu. 79 00:04:33,030 --> 00:04:35,340 Tôi phải có một tạm thời đặt tên cho cấu trúc của tôi. 80 00:04:35,340 --> 00:04:37,640 Vào cuối ngày tôi rõ ràng muốn gọi nó 81 00:04:37,640 --> 00:04:43,030 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, 82 00:04:43,030 --> 00:04:47,450 nhưng tôi không thể sử dụng nút sll ở giữa này. 83 00:04:47,450 --> 00:04:51,430 Lý do là, tôi đã không tạo ra một loại gọi là nút sll 84 00:04:51,430 --> 00:04:55,200 cho đến khi tôi đạt điểm cuối cùng này ở đây. 85 00:04:55,200 --> 00:04:59,720 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. 86 00:04:59,720 --> 00:05:02,440 >> Và đây là một tự kiểu dữ liệu tham chiếu. 87 00:05:02,440 --> 00:05:06,314 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, 88 00:05:06,314 --> 00:05:08,480 và một con trỏ đến một cấu trúc cùng loại. 89 00:05:08,480 --> 00:05:11,750 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, 90 00:05:11,750 --> 00:05:14,910 để cho nó một tạm thời Tên của struct sllist 91 00:05:14,910 --> 00:05:18,540 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, 92 00:05:18,540 --> 00:05:24,690 một ngôi sao struct sllist, và sau đó sau khi tôi đã hoàn thành việc xác định, 93 00:05:24,690 --> 00:05:27,220 Tôi bây giờ có thể gọi đây là loại một nút sll. 94 00:05:27,220 --> 00:05:30,520 >> 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, 95 00:05:30,520 --> 00:05:31,879 nhưng một cái tên thường trực ở đây. 96 00:05:31,879 --> 00:05:33,920 Đôi khi bạn có thể nhìn thấy định nghĩa của cấu trúc, 97 00:05:33,920 --> 00:05:36,570 ví dụ, mà không phải là tự tham chiếu, mà 98 00:05:36,570 --> 00:05:39,390 không có một cái tên đặc tả ở đây. 99 00:05:39,390 --> 00:05:43,040 Nó sẽ chỉ nói typedef struct, mở ngoặc móc và sau đó xác định nó. 100 00:05:43,040 --> 00:05:45,620 Nhưng nếu bạn là struct là tự tham chiếu, như này là, 101 00:05:45,620 --> 00:05:49,010 bạn cần phải xác định một Loại tên tạm thời. 102 00:05:49,010 --> 00:05:51,310 Nhưng cuối cùng, bây giờ rằng chúng tôi đã làm điều này, 103 00:05:51,310 --> 00:05:53,620 chúng ta chỉ có thể tham khảo các nút này, các đơn vị, 104 00:05:53,620 --> 00:05:57,900 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. 105 00:05:57,900 --> 00:06:00,900 >> Đượ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. 106 00:06:00,900 --> 00:06:03,240 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. 107 00:06:03,240 --> 00:06:06,670 Bây giờ, nếu chúng ta sẽ bắt đầu sử dụng chúng để thu thập thông tin, 108 00:06:06,670 --> 00:06:10,360 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. 109 00:06:10,360 --> 00:06:12,860 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. 110 00:06:12,860 --> 00:06:14,901 Nếu không có danh sách đã có, chúng tôi muốn bắt đầu một. 111 00:06:14,901 --> 00:06:16,960 Vì vậy, chúng tôi cần để có thể để tạo ra một danh sách liên kết, 112 00:06:16,960 --> 00:06:19,130 chúng ta cần phải có lẽ tìm thông qua danh sách liên kết 113 00:06:19,130 --> 00:06:21,830 để tìm một phần tử, chúng tôi đang tìm kiếm. 114 00:06:21,830 --> 00:06:24,430 Chúng tôi cần để có thể chèn những điều mới vào danh sách, 115 00:06:24,430 --> 00:06:25,930 chúng ta muốn danh sách của chúng tôi để có thể phát triển. 116 00:06:25,930 --> 00:06:28,638 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, 117 00:06:28,638 --> 00:06:30,250 chúng ta muốn danh sách của chúng tôi để có thể thu nhỏ. 118 00:06:30,250 --> 00:06:32,160 Và vào cuối của chúng tôi các chương trình, đặc biệt là 119 00:06:32,160 --> 00:06:34,550 nếu bạn nhớ lại rằng chúng tôi tự động phân bổ bộ nhớ 120 00:06:34,550 --> 00:06:38,337 để 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ớ 121 00:06:38,337 --> 00:06:39,670 khi chúng tôi đang làm việc với nó. 122 00:06:39,670 --> 00:06:44,627 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. 123 00:06:44,627 --> 00:06:46,460 Vì vậy, hãy đi qua một số các hoạt động này 124 00:06:46,460 --> 00:06:51,192 và làm thế nào chúng ta có thể hình dung họ, nói trong mã giả cụ thể. 125 00:06:51,192 --> 00:06:53,150 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 126 00:06:53,150 --> 00:06:56,480 muốn xác định một chức năng với mẫu thử nghiệm này. 127 00:06:56,480 --> 00:07:01,690 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 ý 128 00:07:01,690 --> 00:07:05,530 gõ một lần nữa, một số loại dữ liệu tùy ý. 129 00:07:05,530 --> 00:07:10,482 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ẻ 130 00:07:10,482 --> 00:07:11,190 danh sách liên kết nút. 131 00:07:11,190 --> 00:07:14,050 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, 132 00:07:14,050 --> 00:07:17,900 vì vậy tôi cần một con trỏ đến danh sách đó khi tôi đang làm. 133 00:07:17,900 --> 00:07:19,420 >> Vì vậy, các bước liên quan ở đây là gì? 134 00:07:19,420 --> 00:07:20,960 Vâng, điều đầu tiên tôi sẽ làm là tự động 135 00:07:20,960 --> 00:07:22,550 phân bổ không gian cho một nút mới. 136 00:07:22,550 --> 00:07:26,689 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ó. 137 00:07:26,689 --> 00:07:28,480 Và tất nhiên, ngay lập tức sau khi chúng tôi malloc, 138 00:07:28,480 --> 00:07:31,692 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. 139 00:07:31,692 --> 00:07:33,650 Bởi vì nếu chúng ta cố gắng và tôn kính một con trỏ null, 140 00:07:33,650 --> 00:07:36,190 chúng ta sẽ phải chịu một segfault và chúng tôi không muốn điều đó. 141 00:07:36,190 --> 00:07:39,510 >> 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ị 142 00:07:39,510 --> 00:07:41,690 và khởi tạo các lĩnh vực tiếp theo. 143 00:07:41,690 --> 00:07:45,450 Và sau đó chúng tôi muốn đối với: cuối cùng là prototype indicates-- chúng ta muốn 144 00:07:45,450 --> 00:07:49,940 để trả về một con trỏ tới một nút sll. 145 00:07:49,940 --> 00:07:51,710 Vì vậy, những gì làm cho điều này trông giống như thị giác? 146 00:07:51,710 --> 00:07:55,230 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, 147 00:07:55,230 --> 00:07:58,320 vì vậy chúng tôi malloc-- đó một đại diện trực quan 148 00:07:58,320 --> 00:08:00,020 của nút chúng ta vừa tạo. 149 00:08:00,020 --> 00:08:02,757 Và chúng tôi kiểm tra để đảm bảo nó không null-- trong trường hợp này, 150 00:08:02,757 --> 00:08:04,840 hình ảnh sẽ không có hiện lên nếu nó là null, 151 00:08:04,840 --> 00:08:07,298 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 đó. 152 00:08:07,298 --> 00:08:10,200 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ị. 153 00:08:10,200 --> 00:08:12,280 Vâng, dựa trên chức năng này gọi tôi đang sử dụng ở đây, 154 00:08:12,280 --> 00:08:16,700 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ị. 155 00:08:16,700 --> 00:08:18,865 Bây giờ, khởi tạo các lĩnh vực tiếp theo. 156 00:08:18,865 --> 00:08:21,640 Vâng, những gì tôi sẽ làm gì ở đó, không có gì là tiếp theo, phải, 157 00:08:21,640 --> 00:08:23,600 đây là điều duy nhất trong danh sách. 158 00:08:23,600 --> 00:08:27,206 Vì vậy, điều tiếp theo trong danh sách là những gì? 159 00:08:27,206 --> 00:08:29,660 >> Nó không phải trỏ đến bất cứ điều gì, phải. 160 00:08:29,660 --> 00:08:33,600 Không có gì khác ở đó, như vậy là gì khái niệm mà chúng ta biết đó là nothing-- 161 00:08:33,600 --> 00:08:35,638 con trỏ để không có gì? 162 00:08:35,638 --> 00:08:37,929 Nó sẽ được có lẽ chúng ta muốn để đặt một con trỏ null có, 163 00:08:37,929 --> 00:08:40,178 và tôi sẽ đại diện cho các null con trỏ như chỉ là một hộp màu đỏ, 164 00:08:40,178 --> 00:08:41,559 chúng ta không thể đi xa hơn. 165 00:08:41,559 --> 00:08:44,430 Như chúng ta sẽ thấy một chút sau, chúng tôi sẽ có chuỗi cuối cùng 166 00:08:44,430 --> 00:08:46,330 các mũi tên kết nối các nút này lại với nhau, 167 00:08:46,330 --> 00:08:48,480 nhưng khi bạn nhấn hộp màu đỏ, đó là null, 168 00:08:48,480 --> 00:08:51,150 chúng ta không thể đi xa hơn, đó là sự kết thúc của danh sách. 169 00:08:51,150 --> 00:08:53,960 >> Và cuối cùng, chúng tôi chỉ muốn trả về một con trỏ đến nút này. 170 00:08:53,960 --> 00:08:56,160 Vì vậy, chúng tôi sẽ gọi nó là mới, và sẽ trở lại mới 171 00:08:56,160 --> 00:08:59,370 do đó, nó có thể được sử dụng trong chức năng bất cứ điều gì tạo ra nó. 172 00:08:59,370 --> 00:09:03,100 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, 173 00:09:03,100 --> 00:09:05,920 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. 174 00:09:05,920 --> 00:09:08,260 >> Bây giờ, chúng ta hãy nói rằng chúng ta đã có một chuỗi lớn, 175 00:09:08,260 --> 00:09:09,800 và chúng tôi muốn tìm một cái gì đó trong nó. 176 00:09:09,800 --> 00:09:12,716 Và chúng tôi muốn có một chức năng đó sẽ để trở về đúng hay sai, tùy thuộc 177 00:09:12,716 --> 00:09:15,840 về việc có một giá trị tồn tại trong danh sách đó. 178 00:09:15,840 --> 00:09:18,160 Một nguyên mẫu hàm, hoặc khai cho chức năng đó, 179 00:09:18,160 --> 00:09:23,320 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ố. 180 00:09:23,320 --> 00:09:26,996 >> 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. 181 00:09:26,996 --> 00:09:29,620 Đây thực sự là một cái gì đó bạn sẽ luôn muốn theo dõi, 182 00:09:29,620 --> 00:09:33,110 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. 183 00:09:33,110 --> 00:09:35,360 Khi bạn tạo ra một danh sách, bạn luôn luôn, luôn luôn 184 00:09:35,360 --> 00:09:38,990 muốn theo dõi của rất Yếu tố đầu tiên của danh sách. 185 00:09:38,990 --> 00:09:43,690 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, 186 00:09:43,690 --> 00:09:47,300 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. 187 00:09:47,300 --> 00:09:50,920 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. 188 00:09:50,920 --> 00:09:52,460 >> Và sau đó là điều thứ hai chúng ta đang đi trong một lần nữa 189 00:09:52,460 --> 00:09:54,376 là tùy tiện some-- bất cứ loại dữ liệu chúng tôi 190 00:09:54,376 --> 00:09:59,640 tìm kiếm có bên trong hy vọng một trong các nút trong danh sách. 191 00:09:59,640 --> 00:10:00,980 Vì vậy, các bước là gì? 192 00:10:00,980 --> 00:10:04,250 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 193 00:10:04,250 --> 00:10:06,015 trỏ đến đầu danh sách. 194 00:10:06,015 --> 00:10:08,890 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, 195 00:10:08,890 --> 00:10:10,974 tại sao chúng ta không chỉ di chuyển một mà xung quanh? 196 00:10:10,974 --> 00:10:13,140 Vâng, như tôi vừa nói, nó thực sự quan trọng đối với chúng tôi 197 00:10:13,140 --> 00:10:17,580 để luôn theo dõi các Yếu tố đầu tiên trong danh sách. 198 00:10:17,580 --> 00:10:21,270 Và do đó, nó thực sự tốt hơn để tạo ra một bản sao của rằng, 199 00:10:21,270 --> 00:10:25,350 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 200 00:10:25,350 --> 00:10:30,430 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. 201 00:10:30,430 --> 00:10:33,290 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. 202 00:10:33,290 --> 00:10:35,877 >> Sau đó, chúng ta chỉ cần so sánh xem trường giá trị tại nút đó 203 00:10:35,877 --> 00:10:38,960 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. 204 00:10:38,960 --> 00:10:41,040 Và chúng tôi tiếp tục làm điều đó hơn, và hơn và hơn, 205 00:10:41,040 --> 00:10:44,811 cho đến khi chúng tôi có thể tìm thấy phần tử, hoặc chúng ta nhấn 206 00:10:44,811 --> 00:10:47,310 null-- chúng tôi đã đạt đến cuối cùng của danh sách và nó là không có. 207 00:10:47,310 --> 00:10:50,540 Đ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, 208 00:10:50,540 --> 00:10:54,430 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ẻ 209 00:10:54,430 --> 00:10:56,280 thay vì sử dụng một mảng để làm điều đó. 210 00:10:56,280 --> 00:10:58,210 >> Vì vậy, đây là một ví dụ của một danh sách đơn lẻ liên kết. 211 00:10:58,210 --> 00:11:00,043 Điều này bao gồm năm nút, và chúng tôi có 212 00:11:00,043 --> 00:11:04,330 một con trỏ đến đầu của danh sách, được gọi là danh sách. 213 00:11:04,330 --> 00:11:07,385 Đ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. 214 00:11:07,385 --> 00:11:09,760 Vì vậy, chúng tôi có bây giờ hai con trỏ điểm đó đến cùng một điều. 215 00:11:09,760 --> 00:11:15,025 >> 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. 216 00:11:15,025 --> 00:11:18,970 Tôi đã không nói trav bằng malloc một cái gì đó, nút đó đã tồn tại, 217 00:11:18,970 --> 00:11:21,160 rằng không gian trong bộ nhớ đã tồn tại. 218 00:11:21,160 --> 00:11:24,290 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ó. 219 00:11:24,290 --> 00:11:28,210 Tôi không mallocing thêm không gian, chỉ có bây giờ hai con trỏ 220 00:11:28,210 --> 00:11:31,370 trỏ đến cùng một điều. 221 00:11:31,370 --> 00:11:33,710 >> Vậy là 2 những gì tôi đang tìm kiếm? 222 00:11:33,710 --> 00:11:37,220 Vâng, không có, vì vậy thay vì tôi sẽ di chuyển đến kế tiếp. 223 00:11:37,220 --> 00:11:41,740 Vì vậy, về cơ bản tôi sẽ nói, trav bằng trav tiếp theo. 224 00:11:41,740 --> 00:11:43,630 Là 3 những gì tôi đang tìm kiếm, không có. 225 00:11:43,630 --> 00:11:45,780 Vì vậy, tôi tiếp tục đi thông qua, cho đến khi cuối cùng 226 00:11:45,780 --> 00:11:48,690 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 227 00:11:48,690 --> 00:11:51,600 Tôi có ở đầu ở đó, và vì vậy tôi thực hiện. 228 00:11:51,600 --> 00:11:54,150 >> Bây giờ, nếu các yếu tố tôi những gì tìm đã không có trong danh sách, 229 00:11:54,150 --> 00:11:55,510 là nó vẫn đi làm à? 230 00:11:55,510 --> 00:11:57,120 Vâng, chú ý rằng danh sách đây là tinh tế khác nhau, 231 00:11:57,120 --> 00:11:59,410 và đây là một điều đó là quan trọng với danh sách liên kết, 232 00:11:59,410 --> 00:12:01,780 bạn không có để bảo tồn chúng trong bất kỳ thứ tự cụ thể. 233 00:12:01,780 --> 00:12:05,390 Bạn có thể nếu bạn muốn, nhưng bạn có thể đã nhận thấy 234 00:12:05,390 --> 00:12:09,310 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 ở. 235 00:12:09,310 --> 00:12:13,150 >> 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, 236 00:12:13,150 --> 00:12:15,300 được nó, chúng ta không có truy cập ngẫu nhiên nữa. 237 00:12:15,300 --> 00:12:18,150 Chúng ta không thể chỉ nói, tôi muốn để đi tới phần tử 0, 238 00:12:18,150 --> 00:12:21,410 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. 239 00:12:21,410 --> 00:12:25,080 Tôi không thể nói tôi muốn đi đến 0 tố, hoặc các yếu tố thứ 6, 240 00:12:25,080 --> 00:12:30,360 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ọ. 241 00:12:30,360 --> 00:12:33,660 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ự. 242 00:12:33,660 --> 00:12:36,080 Nếu bạn muốn cho bạn chắc chắn có thể, nhưng có 243 00:12:36,080 --> 00:12:38,567 không có lý do tại sao họ cần phải được bảo quản trong bất kỳ thứ tự. 244 00:12:38,567 --> 00:12:40,400 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. 245 00:12:40,400 --> 00:12:43,200 Vâng, chúng ta bắt đầu ở bắt đầu, chúng tôi không tìm thấy 6, 246 00:12:43,200 --> 00:12:47,690 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. 247 00:12:47,690 --> 00:12:52,790 Vì vậy, ngay điểm bây giờ trav đến nút có chứa 8, và sáu không có trong đó. 248 00:12:52,790 --> 00:12:55,250 >> Vì vậy, bước tiếp theo sẽ là để đi đến con trỏ tới, 249 00:12:55,250 --> 00:12:57,440 do đó, nói trav bằng trav tiếp theo. 250 00:12:57,440 --> 00:13:00,750 Vâng, trav tiếp theo, chỉ định bởi hộp màu đỏ ở đó, là null. 251 00:13:00,750 --> 00:13:03,020 Vì vậy, không có chỗ nào khác để đi, và vào thời điểm này 252 00:13:03,020 --> 00:13:06,120 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, 253 00:13:06,120 --> 00:13:07,190 và 6 không phải là ở đó. 254 00:13:07,190 --> 00:13:10,980 Và nó sẽ được trả lại sai trong trường hợp này. 255 00:13:10,980 --> 00:13:14,540 >> 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? 256 00:13:14,540 --> 00:13:17,310 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, 257 00:13:17,310 --> 00:13:19,370 nhưng có lẽ chúng ta muốn xây dựng một chuỗi và không 258 00:13:19,370 --> 00:13:22,620 tạo ra một loạt các danh sách riêng biệt. 259 00:13:22,620 --> 00:13:25,700 Chúng tôi muốn có một danh sách đó có một loạt các nút trong nó, 260 00:13:25,700 --> 00:13:28,040 không phải là một loạt các danh sách với một nút duy nhất. 261 00:13:28,040 --> 00:13:31,260 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 262 00:13:31,260 --> 00:13:33,860 muốn chèn vào một danh sách đó đã tồn tại. 263 00:13:33,860 --> 00:13:36,499 >> Vì vậy, trường hợp này, chúng ta sẽ để vượt qua trong hai tham số, 264 00:13:36,499 --> 00:13:39,290 con trỏ đến đầu của đó danh sách mà chúng tôi muốn thêm vào liên kết. 265 00:13:39,290 --> 00:13:40,910 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 266 00:13:40,910 --> 00:13:43,400 theo dõi của nó, bởi vì đó là cách duy nhất chúng ta thực sự 267 00:13:43,400 --> 00:13:46,690 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. 268 00:13:46,690 --> 00:13:49,360 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, 269 00:13:49,360 --> 00:13:52,226 và bất cứ điều gì giá trị chúng tôi muốn thêm vào danh sách. 270 00:13:52,226 --> 00:13:54,600 Và cuối cùng chức năng này sẽ trả về một con trỏ 271 00:13:54,600 --> 00:13:57,980 cho người đứng đầu mới của một danh sách liên kết. 272 00:13:57,980 --> 00:13:59,700 >> Các bước liên quan ở đây là gì? 273 00:13:59,700 --> 00:14:02,249 Vâng, giống như với tạo, chúng ta cần phải tự động phân bổ 274 00:14:02,249 --> 00:14:05,540 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, 275 00:14:05,540 --> 00:14:07,150 bởi vì chúng ta đang sử dụng malloc. 276 00:14:07,150 --> 00:14:09,080 Sau đó, chúng tôi muốn cư và chèn các nút, 277 00:14:09,080 --> 00:14:12,730 do đó, đặt số lượng, bất cứ điều gì val là, vào các nút. 278 00:14:12,730 --> 00:14:17,310 Chúng tôi muốn chèn nút tại đầu của danh sách liên kết. 279 00:14:17,310 --> 00:14:19,619 >> Có một lý do mà tôi muốn làm điều này, và nó 280 00:14:19,619 --> 00:14:21,910 có thể là giá trị tham gia một giây tạm dừng video ở đây, 281 00:14:21,910 --> 00:14:25,860 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 282 00:14:25,860 --> 00:14:26,589 danh sách. 283 00:14:26,589 --> 00:14:28,630 Một lần nữa, tôi đã đề cập trước đó rằng nó không thực sự 284 00:14:28,630 --> 00:14:33,020 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. 285 00:14:33,020 --> 00:14:36,040 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 286 00:14:36,040 --> 00:14:37,360 trước khi chúng tôi đã đi thông qua tìm kiếm bạn 287 00:14:37,360 --> 00:14:39,235 có thể nhìn thấy những gì có thể xảy ra nếu chúng tôi đã cố gắng 288 00:14:39,235 --> 00:14:41,330 để chèn vào cuối danh sách. 289 00:14:41,330 --> 00:14:44,750 Bởi vì chúng ta không có một con trỏ đến cuối danh sách. 290 00:14:44,750 --> 00:14:47,490 >> Vì vậy, lý do mà tôi muốn để chèn vào đầu, 291 00:14:47,490 --> 00:14:49,380 là bởi vì tôi có thể làm điều đó ngay lập tức. 292 00:14:49,380 --> 00:14:52,730 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. 293 00:14:52,730 --> 00:14:55,605 Nhưng nếu tôi muốn chèn ở cuối, Tôi phải bắt đầu ngay từ đầu, 294 00:14:55,605 --> 00:14:58,760 đi qua tất cả các cách để các kết thúc, và sau đó sẽ dán nó vào. 295 00:14:58,760 --> 00:15:01,420 Vì vậy, điều đó có nghĩa rằng chèn vào cuối danh sách 296 00:15:01,420 --> 00:15:04,140 sẽ trở thành một o của n hoạt động, đi lại 297 00:15:04,140 --> 00:15:06,720 để thảo luận về tính toán phức tạp. 298 00:15:06,720 --> 00:15:10,140 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, 299 00:15:10,140 --> 00:15:13,310 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ì đó 300 00:15:13,310 --> 00:15:14,661 vào lúc kết thúc. 301 00:15:14,661 --> 00:15:17,410 Nhưng nó luôn luôn thực sự dễ dàng để tack một cái gì đó vào lúc đầu, 302 00:15:17,410 --> 00:15:19,060 bạn luôn ở đầu. 303 00:15:19,060 --> 00:15:21,620 >> Và chúng ta sẽ thấy một hình ảnh này một lần nữa. 304 00:15:21,620 --> 00:15:24,100 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, 305 00:15:24,100 --> 00:15:26,880 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 đó 306 00:15:26,880 --> 00:15:29,213 vì chúng ta đang chèn vào bắt đầu, thực sự sẽ là 307 00:15:29,213 --> 00:15:31,060 một con trỏ đến nút chúng ta vừa tạo. 308 00:15:31,060 --> 00:15:33,280 Hãy hình dung này, bởi vì tôi nghĩ rằng nó sẽ giúp đỡ. 309 00:15:33,280 --> 00:15:36,661 >> 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, 310 00:15:36,661 --> 00:15:38,410 mà chỉ vào một nút chứa 9, 311 00:15:38,410 --> 00:15:41,370 chỉ với một nút chứa 13, mà điểm đến một nút có chứa 312 00:15:41,370 --> 00:15:44,840 10, trong đó có null con trỏ như con trỏ tiếp theo 313 00:15:44,840 --> 00:15:47,010 vì vậy đó là sự kết thúc của danh sách. 314 00:15:47,010 --> 00:15:50,200 Vì vậy, chúng tôi muốn chèn một nút mới với giá trị 12 315 00:15:50,200 --> 00:15:52,720 vào đầu này danh sách, chúng ta làm gì? 316 00:15:52,720 --> 00:15:58,770 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 đó. 317 00:15:58,770 --> 00:16:02,211 >> Vì vậy, bây giờ chúng tôi đã đạt đến một điểm quyết định, phải không? 318 00:16:02,211 --> 00:16:03,960 Chúng tôi có một vài gợi ý rằng chúng ta có thể 319 00:16:03,960 --> 00:16:06,770 di chuyển, mà một trong chúng ta nên di chuyển đầu tiên? 320 00:16:06,770 --> 00:16:09,250 Chúng ta nên làm cho 12 điểm đến người đứng đầu mới của list-- 321 00:16:09,250 --> 00:16:13,020 hay tha thứ cho tôi, chúng ta nên làm cho 12 trỏ đến đầu cũ của danh sách? 322 00:16:13,020 --> 00:16:15,319 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. 323 00:16:15,319 --> 00:16:17,110 Có một sự khác biệt ở đó, và chúng tôi sẽ xem xét 324 00:16:17,110 --> 00:16:19,870 những gì xảy ra với cả hai trong một giây. 325 00:16:19,870 --> 00:16:23,350 >> Nhưng điều này dẫn đến một chủ đề lớn cho sidebar, 326 00:16:23,350 --> 00:16:26,280 đó là một trong những điều khó khăn nhất với danh sách liên kết 327 00:16:26,280 --> 00:16:30,980 là để sắp xếp các con trỏ theo thứ tự đúng. 328 00:16:30,980 --> 00:16:34,520 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 329 00:16:34,520 --> 00:16:36,050 orphaning phần còn lại của danh sách. 330 00:16:36,050 --> 00:16:37,300 Và đây là một ví dụ về điều đó. 331 00:16:37,300 --> 00:16:40,540 Vì vậy, chúng ta hãy đi với ý tưởng of-- tốt, chúng tôi đã chỉ ra 12. 332 00:16:40,540 --> 00:16:43,180 Chúng ta biết 12 là có được người đứng đầu mới của danh sách, 333 00:16:43,180 --> 00:16:47,660 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ó. 334 00:16:47,660 --> 00:16:49,070 >> OK, vậy thì tốt. 335 00:16:49,070 --> 00:16:51,560 Vì vậy, bây giờ nơi nào 12 điểm tiếp theo? 336 00:16:51,560 --> 00:16:54,580 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, 337 00:16:54,580 --> 00:16:57,250 như con người nó thực sự rõ ràng cho chúng tôi. 338 00:16:57,250 --> 00:17:00,300 Làm thế nào để máy tính biết? 339 00:17:00,300 --> 00:17:02,720 Chúng tôi không có bất cứ điều gì trỏ đến 15 nữa, đúng không? 340 00:17:02,720 --> 00:17:05,869 >> Chúng tôi đã bị mất bất kỳ khả năng tham khảo 15. 341 00:17:05,869 --> 00:17:11,460 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ó. 342 00:17:11,460 --> 00:17:13,510 Trong thực tế, chúng tôi đã mồ côi phần còn lại của danh sách 343 00:17:13,510 --> 00:17:16,465 bởi làm như vậy, chúng tôi đã vô tình phá vỡ dây chuyền. 344 00:17:16,465 --> 00:17:18,089 Và chúng tôi chắc chắn không muốn làm điều đó. 345 00:17:18,089 --> 00:17:20,000 >> Vì vậy, chúng ta hãy quay trở lại và thử lại. 346 00:17:20,000 --> 00:17:24,060 Có lẽ những điều phải làm là để thiết lập con trỏ tới 12 của 347 00:17:24,060 --> 00:17:28,290 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. 348 00:17:28,290 --> 00:17:30,420 Và trên thực tế, đó là đúng thứ tự mà chúng ta 349 00:17:30,420 --> 00:17:32,836 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. 350 00:17:32,836 --> 00:17:36,460 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, 351 00:17:36,460 --> 00:17:41,010 trước khi chúng tôi mất rằng loại bước quan trọng của việc thay đổi 352 00:17:41,010 --> 00:17:43,360 nơi người đứng đầu của danh sách liên kết là. 353 00:17:43,360 --> 00:17:46,740 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ó. 354 00:17:46,740 --> 00:17:49,310 >> 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, 355 00:17:49,310 --> 00:17:52,040 trước khi chúng tôi di chuyển con trỏ đó. 356 00:17:52,040 --> 00:17:55,300 Và vì vậy đây sẽ là thứ tự đúng, mà là để kết nối 12 vào danh sách, 357 00:17:55,300 --> 00:17:57,630 sau đó nói rằng danh sách này bắt đầu một 12. 358 00:17:57,630 --> 00:18:00,860 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, 359 00:18:00,860 --> 00:18:02,193 chúng tôi đã nhìn thấy những gì xảy ra. 360 00:18:02,193 --> 00:18:04,920 Chúng ta mất danh sách bằng cách sai lầm. 361 00:18:04,920 --> 00:18:06,740 >> OK, vì vậy một điều nữa để nói về. 362 00:18:06,740 --> 00:18:09,750 Đ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? 363 00:18:09,750 --> 00:18:11,750 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 364 00:18:11,750 --> 00:18:13,351 cần phải giải phóng nó khi chúng ta đang thực hiện. 365 00:18:13,351 --> 00:18:15,350 Vì vậy, bây giờ chúng tôi muốn xóa toàn bộ danh sách liên kết. 366 00:18:15,350 --> 00:18:16,850 Vâng, những gì chúng ta muốn làm gì? 367 00:18:16,850 --> 00:18:20,460 >> 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 368 00:18:20,460 --> 00:18:23,420 phần còn lại của danh sách và sau đó thoát tôi. 369 00:18:23,420 --> 00:18:28,890 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. 370 00:18:28,890 --> 00:18:32,850 Âm thanh gì như thế, những gì kỹ thuật có chúng tôi nói chuyện 371 00:18:32,850 --> 00:18:35,440 về trước mà âm thanh như thế nào? 372 00:18:35,440 --> 00:18:39,560 Xóa tất cả mọi người khác, sau đó trở lại và xóa tôi. 373 00:18:39,560 --> 00:18:42,380 >> Đó là đệ quy, chúng tôi đã thực hiện các vấn đề một chút nhỏ hơn, 374 00:18:42,380 --> 00:18:46,910 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. 375 00:18:46,910 --> 00:18:50,940 Và tiếp tục xuống đường, nút đó sẽ nói, xóa tất cả mọi người khác. 376 00:18:50,940 --> 00:18:53,940 Nhưng cuối cùng chúng tôi sẽ nhận được vào điểm mà danh sách là null, 377 00:18:53,940 --> 00:18:55,310 và đó là trường hợp cơ sở của chúng tôi. 378 00:18:55,310 --> 00:18:57,010 >> 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. 379 00:18:57,010 --> 00:18:59,759 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ề, 380 00:18:59,759 --> 00:19:00,980 và có các bước. 381 00:19:00,980 --> 00:19:04,200 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. 382 00:19:04,200 --> 00:19:08,557 >> 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 383 00:19:08,557 --> 00:19:10,890 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 384 00:19:10,890 --> 00:19:13,260 với nhau sẽ cho bạn thấy những gì đang xảy ra. 385 00:19:13,260 --> 00:19:14,510 Vì vậy, đây là mã giả của chúng tôi. 386 00:19:14,510 --> 00:19:17,830 Nếu chúng ta đạt đến một null con trỏ, dừng lại, nếu không, 387 00:19:17,830 --> 00:19:21,320 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. 388 00:19:21,320 --> 00:19:25,700 Vì vậy, ngay bây giờ, list-- các con trỏ mà chúng tôi 389 00:19:25,700 --> 00:19:28,410 đi qua trong để tiêu diệt điểm đến 12. 390 00:19:28,410 --> 00:19:33,340 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. 391 00:19:33,340 --> 00:19:35,450 >> Những gì được xóa phần còn lại của chúng tôi tham gia? 392 00:19:35,450 --> 00:19:37,950 Vâng, nó có nghĩa là làm một gọi để tiêu diệt, nói 393 00:19:37,950 --> 00:19:42,060 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. 394 00:19:42,060 --> 00:19:47,480 Và do đó, các cuộc gọi đến phá hủy 12 là loại giữ. 395 00:19:47,480 --> 00:19:52,690 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. 396 00:19:52,690 --> 00:19:56,280 >> 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, 397 00:19:56,280 --> 00:19:58,450 tốt, xóa phần còn lại của danh sách. 398 00:19:58,450 --> 00:20:00,760 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ỉ 399 00:20:00,760 --> 00:20:04,514 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. 400 00:20:04,514 --> 00:20:06,680 Vâng 9 sẽ nói, tốt, Tôi không phải là một con trỏ null, 401 00:20:06,680 --> 00:20:09,020 để xóa phần còn lại trong danh sách tại đây. 402 00:20:09,020 --> 00:20:11,805 Và vì vậy hãy thử và phá hủy 13. 403 00:20:11,805 --> 00:20:15,550 13 nói, tôi không phải là con trỏ null, cùng một điều, nó vượt qua buck. 404 00:20:15,550 --> 00:20:17,930 10 không phải là con trỏ null, 10 chứa một con trỏ null, 405 00:20:17,930 --> 00:20:20,200 nhưng 10 không phải là bản thân một rỗng trỏ ngay bây giờ, 406 00:20:20,200 --> 00:20:22,470 và để nó vượt qua buck quá. 407 00:20:22,470 --> 00:20:25,560 >> Và bây giờ liệt kê điểm đó, nó thực sự sẽ trỏ đến some-- 408 00:20:25,560 --> 00:20:28,710 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 409 00:20:28,710 --> 00:20:29,960 rằng chúng ta không biết nó là gì. 410 00:20:29,960 --> 00:20:34,680 Đó 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. 411 00:20:34,680 --> 00:20:36,820 Nó chỉ ngay bên trong cái hộp màu đỏ. 412 00:20:36,820 --> 00:20:39,960 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. 413 00:20:39,960 --> 00:20:46,230 >> Và vì vậy mà khung màu tím là now-- tại đầu stack-- đó là khung hoạt động, 414 00:20:46,230 --> 00:20:47,017 nhưng nó được thực hiện. 415 00:20:47,017 --> 00:20:48,600 Nếu chúng tôi đã đạt đến một con trỏ null, dừng lại. 416 00:20:48,600 --> 00:20:51,290 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, 417 00:20:51,290 --> 00:20:55,070 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. 418 00:20:55,070 --> 00:20:57,590 Vì vậy mà khung chức năng bị phá hủy, và chúng tôi 419 00:20:57,590 --> 00:21:00,930 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à 420 00:21:00,930 --> 00:21:02,807 là màu xanh khung tối này ở đây. 421 00:21:02,807 --> 00:21:04,390 Vì vậy, chúng tôi tiếp tục ngay tại nơi chúng tôi rời đi. 422 00:21:04,390 --> 00:21:06,598 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 423 00:21:06,598 --> 00:21:08,000 đi để giải phóng các nút hiện hành. 424 00:21:08,000 --> 00:21:12,920 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. 425 00:21:12,920 --> 00:21:16,810 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. 426 00:21:16,810 --> 00:21:20,650 >> Vì vậy, nó says-- Tôi đã done-- xóa phần còn lại của danh sách, vì 427 00:21:20,650 --> 00:21:23,140 giải phóng các nút hiện hành. 428 00:21:23,140 --> 00:21:26,520 Và bây giờ khung màu vàng là trở lại trên cùng của ngăn xếp. 429 00:21:26,520 --> 00:21:29,655 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. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Điều gì sẽ xảy ra, mặc dù, nếu chúng tôi đã làm điều sai cách? 432 00:21:37,280 --> 00:21:39,410 Cũng giống như khi chúng ta cố gắng để thêm một yếu tố. 433 00:21:39,410 --> 00:21:41,909 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ỏ 434 00:21:41,909 --> 00:21:44,690 theo đúng thứ tự, nếu chúng tôi chỉ giải phóng các yếu tố đầu tiên, 435 00:21:44,690 --> 00:21:47,420 nếu chúng ta chỉ giải phóng đứng đầu danh sách, bây giờ chúng tôi 436 00:21:47,420 --> 00:21:49,642 không có cách nào để tham khảo phần còn lại của danh sách. 437 00:21:49,642 --> 00:21:51,350 Và như vậy chúng ta sẽ có tất cả mọi thứ mồ côi, 438 00:21:51,350 --> 00:21:53,880 chúng tôi sẽ có những gì được gọi là một rò rỉ bộ nhớ. 439 00:21:53,880 --> 00:21:56,800 Nếu bạn nhớ lại từ video của chúng tôi về cấp phát bộ nhớ động, 440 00:21:56,800 --> 00:21:58,650 đó không phải là điều rất tốt. 441 00:21:58,650 --> 00:22:00,810 >> Vì vậy, như tôi đã nói, có một số hoạt động 442 00:22:00,810 --> 00:22:04,010 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ả. 443 00:22:04,010 --> 00:22:08,430 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 444 00:22:08,430 --> 00:22:09,064 danh sách. 445 00:22:09,064 --> 00:22:10,980 Lý do tôi đã làm điều đó là nó thực sự loại 446 00:22:10,980 --> 00:22:14,360 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ẻ 447 00:22:14,360 --> 00:22:15,600 danh sách liên kết. 448 00:22:15,600 --> 00:22:19,950 Chúng tôi cần để có thể bỏ qua một cái gì đó trong danh sách, trong đó 449 00:22:19,950 --> 00:22:22,975 có nghĩa là chúng ta có được một chúng point-- muốn xóa node-- này 450 00:22:22,975 --> 00:22:25,350 nhưng để làm cho nó vì vậy chúng tôi không bị mất bất kỳ thông tin, 451 00:22:25,350 --> 00:22:30,530 chúng ta cần phải kết nối này nút ở đây, ở đây. 452 00:22:30,530 --> 00:22:33,390 >> Vì vậy, có lẽ tôi đã làm điều đó sai từ góc độ thị giác. 453 00:22:33,390 --> 00:22:36,830 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, 454 00:22:36,830 --> 00:22:40,510 chúng ta muốn xóa nốt này. 455 00:22:40,510 --> 00:22:43,440 Nếu chúng ta chỉ cần xóa nó, chúng tôi đã phá vỡ chuỗi. 456 00:22:43,440 --> 00:22:45,950 Nút này ngay tại đây đề cập đến tất cả mọi thứ khác, 457 00:22:45,950 --> 00:22:48,260 nó có chứa các chuỗi từ đây trên ra ngoài. 458 00:22:48,260 --> 00:22:51,190 >> 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, 459 00:22:51,190 --> 00:22:56,670 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, 460 00:22:56,670 --> 00:22:58,590 vì vậy chúng ta có thể xóa một trong những khu trung lộ. 461 00:22:58,590 --> 00:23:02,120 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. 462 00:23:02,120 --> 00:23:05,160 Vì vậy, chúng ta cần phải hoặc là giữ hai con trỏ, và di chuyển chúng 463 00:23:05,160 --> 00:23:09,527 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 464 00:23:09,527 --> 00:23:11,110 và sau đó gửi một con trỏ qua. 465 00:23:11,110 --> 00:23:13,150 Và như bạn thấy, nó có thể có được một chút lộn xộn. 466 00:23:13,150 --> 00:23:15,360 May mắn thay, chúng tôi có một cách khác để giải quyết đó, 467 00:23:15,360 --> 00:23:17,810 khi chúng ta nói về danh sách liên kết kép. 468 00:23:17,810 --> 00:23:20,720 >> Tôi Doug Lloyd, đây là CS50. 469 00:23:20,720 --> 00:23:22,298