1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [MUSIC CHƠI] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Tất cả các bên phải. 5 00:00:12,900 --> 00:00:14,600 Tất cả mọi người chào đón trở lại phần. 6 00:00:14,600 --> 00:00:18,660 Tôi hy vọng tất cả các bạn thành công thu hồi từ bài kiểm tra của bạn 7 00:00:18,660 --> 00:00:19,510 từ tuần trước. 8 00:00:19,510 --> 00:00:22,564 Tôi biết đó là một chút điên ở lần. 9 00:00:22,564 --> 00:00:25,230 Như tôi đã nói trước đây, nếu bạn trong độ lệch chuẩn, 10 00:00:25,230 --> 00:00:28,188 không thực sự lo lắng về nó, đặc biệt là cho một phần không thoải mái. 11 00:00:28,188 --> 00:00:30,230 Đó là về nơi mà bạn nên có. 12 00:00:30,230 --> 00:00:32,850 >> Nếu bạn đã làm rất tốt, sau đó tuyệt vời. 13 00:00:32,850 --> 00:00:33,650 Thanh danh cho bạn. 14 00:00:33,650 --> 00:00:36,149 Và nếu bạn cảm thấy như bạn cần một chút giúp đỡ thêm, xin vui lòng 15 00:00:36,149 --> 00:00:38,140 cảm thấy tự do để đạt được ra bất kỳ của TF. 16 00:00:38,140 --> 00:00:40,030 Chúng tôi là tất cả ở đây để giúp đỡ. 17 00:00:40,030 --> 00:00:40,960 >> Đó là lý do tại sao chúng tôi dạy. 18 00:00:40,960 --> 00:00:44,550 Đó là lý do tại sao tôi ở đây mỗi thứ Hai cho bạn guys và tại văn phòng giờ ngày thứ năm. 19 00:00:44,550 --> 00:00:48,130 Vì vậy, xin vui lòng cho tôi biết nếu bạn đang lo lắng về bất cứ điều gì 20 00:00:48,130 --> 00:00:52,450 hoặc nếu có bất cứ điều gì về các bài kiểm tra mà bạn thực sự muốn giải quyết. 21 00:00:52,450 --> 00:00:56,940 >> Vì vậy, chương trình nghị sự cho ngày hôm nay là tất cả về cấu trúc dữ liệu. 22 00:00:56,940 --> 00:01:01,520 Một số được chỉ có được chỉ để giúp bạn làm quen với các. 23 00:01:01,520 --> 00:01:04,870 Bạn có thể không bao giờ thực hiện họ trong lớp học này. 24 00:01:04,870 --> 00:01:08,690 Một số người bạn sẽ, như cho pset Speller của bạn. 25 00:01:08,690 --> 00:01:11,380 >> Bạn sẽ có sự lựa chọn của bạn giữa các bảng băm và cố gắng. 26 00:01:11,380 --> 00:01:13,680 Vì vậy, chúng tôi chắc chắn sẽ được đi trên những người. 27 00:01:13,680 --> 00:01:18,690 Nó sẽ là chắc chắn hơn các loại của một bộ phận cao cấp hiện nay, mặc dù, 28 00:01:18,690 --> 00:01:22,630 bởi vì có rất nhiều trong số họ, và nếu chúng tôi đã đi vào các chi tiết thực hiện 29 00:01:22,630 --> 00:01:26,490 trên tất cả trong số này, chúng ta sẽ không thậm chí có được thông qua danh sách liên kết 30 00:01:26,490 --> 00:01:28,520 và có lẽ một chút của bảng băm. 31 00:01:28,520 --> 00:01:31,200 >> Vì vậy, chịu với tôi. 32 00:01:31,200 --> 00:01:33,530 Chúng tôi sẽ không được làm càng nhiều mã hóa thời gian này. 33 00:01:33,530 --> 00:01:36,870 Nếu bạn có bất kỳ câu hỏi về nó hoặc bạn muốn nhìn thấy nó thực hiện 34 00:01:36,870 --> 00:01:39,260 hoặc thử nó cho chính mình, Tôi chắc chắn khuyên 35 00:01:39,260 --> 00:01:44,250 sẽ study.cs50.net, mà có các ví dụ của tất cả các. 36 00:01:44,250 --> 00:01:46,400 Nó sẽ có PowerPoints của tôi với các ghi chú mà chúng tôi 37 00:01:46,400 --> 00:01:50,860 xu hướng sử dụng cũng như một số chương trình bài tập, đặc biệt là cho những thứ 38 00:01:50,860 --> 00:01:55,250 như danh sách liên kết và nhị phân cây ngăn xếp và tín hiệu. 39 00:01:55,250 --> 00:01:59,590 Vì vậy, ít mức độ cao hơn, có thể được tốt đẹp cho các bạn. 40 00:01:59,590 --> 00:02:01,320 >> Vì vậy, với điều đó, chúng tôi sẽ bắt đầu. 41 00:02:01,320 --> 00:02:03,060 Và cũng có thể, câu đố yes--. 42 00:02:03,060 --> 00:02:06,550 Tôi nghĩ rằng hầu hết bạn của những người trong phần của tôi có câu đố của bạn, 43 00:02:06,550 --> 00:02:12,060 nhưng có ai đến ở hoặc một số lý do bạn không làm, họ đang phải ở đây ở phía trước. 44 00:02:12,060 --> 00:02:12,740 >> Vì vậy, danh sách liên kết. 45 00:02:12,740 --> 00:02:15,650 Tôi biết điều này loại đi để sao lưu trước khi bài kiểm tra của bạn. 46 00:02:15,650 --> 00:02:17,940 Đó là tuần trước rằng chúng ta học về việc này. 47 00:02:17,940 --> 00:02:21,040 Nhưng trong trường hợp này, chúng tôi sẽ chỉ đi thêm một chút chiều sâu. 48 00:02:21,040 --> 00:02:25,900 >> Vì vậy, tại sao chúng ta có thể chọn một danh sách liên kết trên một mảng? 49 00:02:25,900 --> 00:02:27,130 Điều gì phân biệt chúng? 50 00:02:27,130 --> 00:02:27,630 Có? 51 00:02:27,630 --> 00:02:30,464 >> Đung Bạn có thể mở rộng một liên kết liệt kê so với kích thước cố định của một mảng. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Đúng vậy. 53 00:02:31,171 --> 00:02:33,970 Một mảng có kích thước cố định trong khi một danh sách liên kết có kích thước biến. 54 00:02:33,970 --> 00:02:36,970 Vì vậy, nếu chúng ta không biết làm thế nào nhiều chúng tôi muốn lưu trữ, 55 00:02:36,970 --> 00:02:39,880 một danh sách liên kết cho chúng ta một lớn cách để làm điều đó bởi vì chúng ta có thể chỉ 56 00:02:39,880 --> 00:02:43,730 thêm vào một nút khác và thêm vào một nút và thêm vào một nút khác. 57 00:02:43,730 --> 00:02:45,750 Nhưng những gì có thể là một thương mại-off? 58 00:02:45,750 --> 00:02:49,521 Có ai nhớ thương mại-off giữa các mảng và danh sách liên kết? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Đung Bạn phải đi qua tất cả các cách 61 00:02:51,460 --> 00:02:53,738 thông qua danh sách liên kết tìm một phần tử trong một danh sách. 62 00:02:53,738 --> 00:02:55,570 Trong một mảng, bạn có thể chỉ cần tìm một phần tử. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Đúng vậy. 64 00:02:56,278 --> 00:02:57,120 Vì vậy, với arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Đung [không nghe được]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Với mảng, chúng ta có những gì được gọi là truy cập ngẫu nhiên. 67 00:03:01,090 --> 00:03:04,820 Có nghĩa là nếu chúng ta muốn là những gì từng điểm thứ năm của một danh sách 68 00:03:04,820 --> 00:03:07,230 hoặc điểm thứ năm của chúng tôi mảng, chúng ta chỉ có thể lấy nó. 69 00:03:07,230 --> 00:03:10,440 Nếu đó là một danh sách liên kết, chúng tôi có để lặp qua, phải không? 70 00:03:10,440 --> 00:03:14,020 Vì vậy, truy cập vào một yếu tố trong một mảng là hằng số thời gian, 71 00:03:14,020 --> 00:03:19,530 trong khi với một danh sách liên kết nó sẽ rất có thể là thời gian tuyến tính bởi vì có lẽ 72 00:03:19,530 --> 00:03:21,370 yếu tố của chúng tôi là tất cả các cách ở cuối. 73 00:03:21,370 --> 00:03:23,446 Chúng ta phải tìm kiếm thông qua tất cả mọi thứ. 74 00:03:23,446 --> 00:03:25,320 Vì vậy, với tất cả những dữ liệu này cấu trúc chúng ta sẽ 75 00:03:25,320 --> 00:03:29,330 được chi tiêu một ít thời gian hơn vào, những ưu điểm và khuyết điểm là gì. 76 00:03:29,330 --> 00:03:31,480 Khi chúng ta có thể muốn sử dụng một trong khác không? 77 00:03:31,480 --> 00:03:34,970 Và đó là loại của điều lớn hơn để lấy đi. 78 00:03:34,970 --> 00:03:40,140 >> Vì vậy, chúng tôi có ở đây định nghĩa của một nút. 79 00:03:40,140 --> 00:03:43,040 Nó giống như một phần tử trong danh sách liên kết của chúng tôi, phải không? 80 00:03:43,040 --> 00:03:46,180 Vì vậy, chúng ta đều quen thuộc với cấu trúc typedef của chúng tôi, 81 00:03:46,180 --> 00:03:47,980 mà chúng tôi đã đi qua trong việc xem xét thời gian qua. 82 00:03:47,980 --> 00:03:53,180 Đó là về cơ bản chỉ tạo một loại dữ liệu mà chúng ta có thể sử dụng. 83 00:03:53,180 --> 00:03:57,930 >> Và trong trường hợp này, đó là một số nút rằng sẽ tổ chức một số nguyên trong. 84 00:03:57,930 --> 00:04:00,210 Và sau đó phần thứ hai là những gì ở đây? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Bất cứ ai? 87 00:04:05,677 --> 00:04:06,680 >> Đung [không nghe được]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Yeah. 89 00:04:07,020 --> 00:04:08,400 Đó là một con trỏ đến nút tiếp theo. 90 00:04:08,400 --> 00:04:12,610 Vì vậy, đây thực sự cần được lên đây. 91 00:04:12,610 --> 00:04:18,790 Đây là một con trỏ kiểu nút để điều tiếp theo. 92 00:04:18,790 --> 00:04:22,410 Và đó là những gì họ bao gồm các nút của chúng tôi. 93 00:04:22,410 --> 00:04:24,060 Cool. 94 00:04:24,060 --> 00:04:29,390 >> Tất cả các bên phải, như vậy với tìm kiếm, như chúng tôi đã chỉ cần nói trước mặt, nếu bạn 95 00:04:29,390 --> 00:04:31,840 sẽ tìm kiếm thông qua, bạn phải thực sự lặp đi lặp lại 96 00:04:31,840 --> 00:04:33,660 thông qua danh sách liên kết của bạn. 97 00:04:33,660 --> 00:04:38,530 Vì vậy, nếu chúng tôi đang tìm kiếm các số 9, chúng tôi sẽ bắt đầu vào đầu của chúng tôi 98 00:04:38,530 --> 00:04:41,520 và chỉ cho chúng ta ngay từ đầu của danh sách liên kết của chúng tôi, phải không? 99 00:04:41,520 --> 00:04:44,600 Và chúng ta nói, OK, thực hiện điều này nút chứa số 9? 100 00:04:44,600 --> 00:04:45,690 Không có? 101 00:04:45,690 --> 00:04:47,500 >> Tất cả các bên phải, đi đến kế tiếp. 102 00:04:47,500 --> 00:04:48,312 Thực hiện theo nó. 103 00:04:48,312 --> 00:04:49,520 Liệu nó có chứa số 9? 104 00:04:49,520 --> 00:04:50,570 Không. 105 00:04:50,570 --> 00:04:51,550 Thực hiện theo các kế tiếp. 106 00:04:51,550 --> 00:04:55,490 >> Vì vậy, chúng ta phải thực sự lặp đi lặp lại thông qua danh sách liên kết của chúng tôi. 107 00:04:55,490 --> 00:05:00,070 Chúng ta không thể đi trực tiếp vào nơi 9 là. 108 00:05:00,070 --> 00:05:05,860 Và nếu các bạn thực sự muốn thấy một số mã giả trên đó. 109 00:05:05,860 --> 00:05:10,420 Chúng tôi có một số chức năng tìm kiếm ở đây mà có in-- những gì nó có trong? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Bạn nghĩ gì? 112 00:05:14,320 --> 00:05:15,960 Vì vậy, dễ dàng một. 113 00:05:15,960 --> 00:05:17,784 Này là gì? 114 00:05:17,784 --> 00:05:18,700 Đung [không nghe được]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Số lượng chúng tôi đang tìm kiếm. 116 00:05:20,366 --> 00:05:20,980 Phải không? 117 00:05:20,980 --> 00:05:22,875 Và điều này sẽ tương ứng với? 118 00:05:22,875 --> 00:05:25,020 Đó là một con trỏ đến? 119 00:05:25,020 --> 00:05:26,000 >> Đung A node. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: Một nút vào danh sách mà chúng ta đang nhìn vào, phải không? 121 00:05:28,980 --> 00:05:33,700 Vì vậy, chúng tôi có một số nút là con trỏ ở đây. 122 00:05:33,700 --> 00:05:37,240 Đây là một điểm đó là sẽ thực sự lặp thông qua danh sách của chúng tôi. 123 00:05:37,240 --> 00:05:39,630 Chúng tôi thiết lập nó bằng danh sách bởi vì đó chỉ 124 00:05:39,630 --> 00:05:44,380 thiết lập nó bằng với bắt đầu của danh sách liên kết của chúng tôi. 125 00:05:44,380 --> 00:05:50,660 >> Và trong khi nó không phải là NULL, trong khi chúng tôi vẫn có những thứ trong danh sách của chúng tôi, 126 00:05:50,660 --> 00:05:55,580 kiểm tra xem nút đó có số lượng chúng tôi đang tìm kiếm. 127 00:05:55,580 --> 00:05:57,740 Return true. 128 00:05:57,740 --> 00:06:01,070 Nếu không, cập nhật nó, phải không? 129 00:06:01,070 --> 00:06:04,870 >> Nếu nó là NULL, chúng ta thoát khỏi chúng tôi trong khi vòng lặp và trả về false 130 00:06:04,870 --> 00:06:08,340 bởi vì đó có nghĩa là chúng tôi đã không tìm thấy nó. 131 00:06:08,340 --> 00:06:11,048 Có tất cả mọi người có được như thế nào mà làm việc? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Vì vậy, với chèn, bạn có ba cách khác nhau. 135 00:06:20,260 --> 00:06:25,250 Bạn có thể thêm vào trước, bạn có thể thêm và bạn có thể chèn vào cả mọi loại. 136 00:06:25,250 --> 00:06:28,215 Trong trường hợp này, chúng tôi sẽ làm một thêm vào trước. 137 00:06:28,215 --> 00:06:33,380 Có ai biết làm thế nào những ba trường hợp có thể khác nhau? 138 00:06:33,380 --> 00:06:36,920 >> Vì vậy, thêm vào trước có nghĩa là bạn đặt nó ở phía trước của danh sách của bạn. 139 00:06:36,920 --> 00:06:39,770 Vì vậy, điều đó có nghĩa rằng không có vấn đề những gì nút của bạn, không có vấn đề 140 00:06:39,770 --> 00:06:43,160 những gì giá trị là, bạn sẽ để đặt nó ở đây ở phía trước, OK? 141 00:06:43,160 --> 00:06:45,160 Nó sẽ là người đầu tiên phần tử trong danh sách của bạn. 142 00:06:45,160 --> 00:06:49,510 >> Nếu bạn thêm nó, nó sẽ để đi đến trở lại danh sách của bạn. 143 00:06:49,510 --> 00:06:54,010 Và chèn vào cả mọi loại có nghĩa là bạn sẽ đặt thực sự vào nơi 144 00:06:54,010 --> 00:06:57,700 nơi nó giữ danh sách liên kết của bạn được sắp xếp. 145 00:06:57,700 --> 00:07:00,810 Một lần nữa, làm thế nào bạn sử dụng những người và khi bạn sử dụng 146 00:07:00,810 --> 00:07:02,530 họ sẽ thay đổi tùy thuộc vào trường hợp của bạn. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Nếu nó không cần phải được sắp xếp, thêm vào trước có xu hướng 149 00:07:07,750 --> 00:07:10,460 là những gì hầu hết mọi người sử dụng bởi vì bạn không 150 00:07:10,460 --> 00:07:15,680 phải đi qua toàn bộ danh sách để tìm kết thúc để thêm nó vào, đúng không? 151 00:07:15,680 --> 00:07:17,720 Bạn chỉ có thể dính nó ngay. 152 00:07:17,720 --> 00:07:21,930 >> Vì vậy, chúng ta sẽ đi qua một chèn 1 ngay bây giờ. 153 00:07:21,930 --> 00:07:26,360 Vì vậy, có một điều mà tôi sẽ khuyên trên pset này 154 00:07:26,360 --> 00:07:29,820 là để rút ra những điều trên, như mọi khi. 155 00:07:29,820 --> 00:07:35,130 Nó rất quan trọng là bạn cập nhật con trỏ của bạn theo thứ tự đúng 156 00:07:35,130 --> 00:07:38,620 bởi vì nếu bạn cập nhật chúng hơi trong trật tự, 157 00:07:38,620 --> 00:07:42,210 bạn sẽ kết thúc mất phần danh sách của bạn. 158 00:07:42,210 --> 00:07:49,680 >> Vì vậy, ví dụ, trong trường hợp này, chúng tôi nói với người đứng đầu để chỉ điểm cho 1. 159 00:07:49,680 --> 00:07:56,070 Nếu chúng ta chỉ làm điều đó mà không cần tiết kiệm 1 này, 160 00:07:56,070 --> 00:07:58,570 chúng tôi không có ý tưởng gì 1 nên chỉ đến nay 161 00:07:58,570 --> 00:08:02,490 bởi vì chúng ta đã mất những gì người đứng đầu chỉ ra. 162 00:08:02,490 --> 00:08:05,530 Vì vậy, một điều cần nhớ khi bạn đang làm một thêm vào trước 163 00:08:05,530 --> 00:08:09,630 là để tiết kiệm những gì điểm đầu đến đầu tiên, 164 00:08:09,630 --> 00:08:15,210 sau đó gán lại nó, và sau đó cập nhật những nút mới của bạn sẽ trỏ đến. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Trong trường hợp này, đây là một cách để làm điều đó. 167 00:08:22,560 --> 00:08:25,440 >> Vì vậy, nếu chúng tôi đã thực hiện nó theo cách này nơi chúng tôi chỉ bố trí đầu, 168 00:08:25,440 --> 00:08:30,320 chúng ta mất đi cơ bản của chúng tôi toàn bộ danh sách, phải không? 169 00:08:30,320 --> 00:08:38,000 Một cách để làm điều đó là có 1 điểm tiếp theo, và sau đó có điểm đầu đến 1. 170 00:08:38,000 --> 00:08:42,650 Hoặc bạn có thể làm giống như các lưu trữ tạm thời, mà tôi nói chuyện về. 171 00:08:42,650 --> 00:08:45,670 >> Nhưng chuyển nhượng của bạn con trỏ theo thứ tự đúng 172 00:08:45,670 --> 00:08:48,750 sẽ là rất, rất quan trọng đối với pset này. 173 00:08:48,750 --> 00:08:53,140 Nếu không, bạn sẽ có một băm bảng hoặc một thử đó là chỉ cần đi để được 174 00:08:53,140 --> 00:08:56,014 chỉ là một phần của những từ mà bạn muốn và sau đó mmhmm you're--? 175 00:08:56,014 --> 00:08:58,930 Đung gì là tạm thời điều lưu trữ mà bạn đã nói về? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: lưu trữ tạm thời. 177 00:09:00,305 --> 00:09:02,760 Vì vậy, về cơ bản khác cách bạn có thể làm điều này 178 00:09:02,760 --> 00:09:07,650 được lưu trữ đầu của một cái gì đó, như lưu trữ nó biến tạm thời. 179 00:09:07,650 --> 00:09:11,250 Gán cho nó 1 và sau đó cập nhật 1 điểm 180 00:09:11,250 --> 00:09:13,830 để bất cứ điều gì đầu sử dụng để trỏ đến. 181 00:09:13,830 --> 00:09:16,920 Bằng cách này là rõ ràng thanh lịch hơn bởi vì bạn 182 00:09:16,920 --> 00:09:20,770 không cần phải có giá trị tạm thời, nhưng chỉ cần cung cấp một cách khác để làm điều đó. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Và chúng tôi thực sự không có một số mã cho việc này. 185 00:09:25,790 --> 00:09:28,080 Vì vậy, danh sách liên kết, chúng tôi thực sự có một số mã. 186 00:09:28,080 --> 00:09:31,930 Vì vậy, chèn ở đây, điều này được thêm vào trước. 187 00:09:31,930 --> 00:09:34,290 Vì vậy, đây vào nó ở đầu. 188 00:09:34,290 --> 00:09:38,820 >> Vì vậy, điều đầu tiên, bạn cần phải tạo nút mới của bạn, tất nhiên, 189 00:09:38,820 --> 00:09:40,790 và kiểm tra NULL. 190 00:09:40,790 --> 00:09:43,250 Luôn luôn tốt. 191 00:09:43,250 --> 00:09:47,840 Và sau đó bạn cần phải gán các giá trị. 192 00:09:47,840 --> 00:09:51,260 Bất cứ khi nào bạn tạo một nút mới, bạn không biết những gì nó đang trỏ đến tiếp theo, 193 00:09:51,260 --> 00:09:54,560 do đó bạn muốn khởi tạo nó để NULL. 194 00:09:54,560 --> 00:09:58,760 Nếu nó kết thúc chỉ vào một cái gì đó khác, nó được bố trí và điều đó là tốt. 195 00:09:58,760 --> 00:10:00,740 Nếu đó là điều đầu tiên trong danh sách, nó cần 196 00:10:00,740 --> 00:10:04,270 để trỏ đến NULL vì đó là cuối danh sách. 197 00:10:04,270 --> 00:10:12,410 >> Vì vậy, sau đó chèn nó, chúng ta thấy ở đây chúng tôi được gán giá trị tiếp theo của nút của chúng tôi 198 00:10:12,410 --> 00:10:17,380 là bất cứ điều gì đầu là, đó là những gì chúng tôi có ở đây. 199 00:10:17,380 --> 00:10:19,930 Đó là những gì chúng ta đã làm. 200 00:10:19,930 --> 00:10:25,820 Và sau đó chúng ta đang gán đầu đến điểm đến nút mới của chúng tôi, vì nhớ, 201 00:10:25,820 --> 00:10:31,090 mới là một con trỏ tới một nút, và đó chính xác là những gì đầu. 202 00:10:31,090 --> 00:10:34,370 Đó chính là lý do tại sao chúng tôi có mũi tên này accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Mát mẻ? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Đung Chúng ta phải khởi tạo mới tiếp theo để NULL đầu tiên, 207 00:10:41,100 --> 00:10:44,240 hoặc có thể chúng ta chỉ cần khởi tạo nó để đi? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New tiếp theo cần phải được NULL để bắt đầu 209 00:10:48,210 --> 00:10:53,760 bởi vì bạn không biết nơi mà nó có được. 210 00:10:53,760 --> 00:10:56,100 Ngoài ra, đây là loại giống như một mô hình. 211 00:10:56,100 --> 00:10:59,900 Bạn đặt nó bằng NULL chỉ để làm cho chắc chắn rằng tất cả các căn cứ của bạn được bảo hiểm 212 00:10:59,900 --> 00:11:04,070 trước khi bạn làm bất cứ giao lại để bạn luôn được đảm bảo rằng nó sẽ 213 00:11:04,070 --> 00:11:08,880 được trỏ đến một giá trị cụ thể so với giống như một giá trị rác. 214 00:11:08,880 --> 00:11:12,210 Bởi vì, yeah, chúng ta gán mới tiếp theo tự động, 215 00:11:12,210 --> 00:11:15,420 nhưng đó là giống như một thực hành tốt để khởi tạo nó 216 00:11:15,420 --> 00:11:19,270 theo cách đó và sau đó phân công lại. 217 00:11:19,270 --> 00:11:23,420 >> OK, vì vậy gấp đôi danh sách liên kết bây giờ. 218 00:11:23,420 --> 00:11:24,601 Chúng ta nghĩ gì? 219 00:11:24,601 --> 00:11:26,350 Có gì khác nhau với gấp đôi danh sách liên kết? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Vì vậy, trong danh sách liên kết của chúng tôi, chúng tôi có thể chỉ di chuyển theo một hướng, phải không? 222 00:11:34,300 --> 00:11:35,270 Chúng tôi chỉ có tiếp theo. 223 00:11:35,270 --> 00:11:36,760 Chúng tôi chỉ có thể đi tiếp. 224 00:11:36,760 --> 00:11:40,300 >> Với một danh sách gấp đôi liên kết, chúng tôi cũng có thể di chuyển về phía sau. 225 00:11:40,300 --> 00:11:44,810 Vì vậy, chúng tôi không chỉ có những số mà chúng ta muốn lưu trữ, 226 00:11:44,810 --> 00:11:50,110 chúng tôi có nơi nó trỏ tới tiếp theo và chúng ta chỉ đến từ. 227 00:11:50,110 --> 00:11:52,865 Vì vậy, điều này cho phép một số traversal tốt hơn. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Vì vậy, gấp đôi các nút liên kết, rất giống nhau, phải không? 230 00:12:01,240 --> 00:12:05,000 Chỉ có khác biệt bây giờ là chúng tôi có một kế tiếp và trước đó. 231 00:12:05,000 --> 00:12:06,235 Đó là khác biệt duy nhất. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Vì vậy, nếu chúng ta thêm vào trước hoặc append-- chúng tôi không có bất kỳ mã này lên here-- 234 00:12:14,790 --> 00:12:17,830 nhưng nếu bạn đã cố gắng và chèn nó, điều quan trọng 235 00:12:17,830 --> 00:12:19,980 là bạn cần phải thực hiện chắc chắn rằng bạn đang gán 236 00:12:19,980 --> 00:12:23,360 cả hai trước đó của bạn và của bạn con trỏ tới một cách chính xác. 237 00:12:23,360 --> 00:12:29,010 Vì vậy, trong trường hợp này, bạn sẽ không chỉ khởi tạo tiếp theo, 238 00:12:29,010 --> 00:12:31,820 bạn khởi tạo trước đó. 239 00:12:31,820 --> 00:12:36,960 Nếu chúng ta đang ở đầu của danh sách, chúng tôi sẽ không chỉ làm đầu bằng mới, 240 00:12:36,960 --> 00:12:41,750 nhưng nên trước mới của chúng tôi chỉ vào đầu, phải không? 241 00:12:41,750 --> 00:12:43,380 >> Đó là khác biệt duy nhất. 242 00:12:43,380 --> 00:12:47,200 Và nếu bạn muốn thực hành nhiều hơn với những việc này với danh sách liên kết, với chèn, 243 00:12:47,200 --> 00:12:49,900 với xóa, với chèn vào một danh sách các loại, 244 00:12:49,900 --> 00:12:52,670 xin vui lòng kiểm tra study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Có một loạt các bài tập tuyệt vời. 246 00:12:54,870 --> 00:12:55,870 Tôi khuyên họ. 247 00:12:55,870 --> 00:12:59,210 Tôi muốn chúng tôi có thời gian để đi qua chúng nhưng có rất nhiều cấu trúc dữ liệu 248 00:12:59,210 --> 00:13:01,530 để có được thông qua. 249 00:13:01,530 --> 00:13:02,650 >> OK, vì vậy các bảng băm. 250 00:13:02,650 --> 00:13:07,070 Đây có lẽ là nhất bit hữu ích cho pset của bạn 251 00:13:07,070 --> 00:13:11,090 ở đây bởi vì bạn sẽ được thực hiện một trong những, hoặc một thử. 252 00:13:11,090 --> 00:13:12,200 Tôi thực sự thích các bảng băm. 253 00:13:12,200 --> 00:13:13,110 Họ đang khá mát mẻ. 254 00:13:13,110 --> 00:13:17,080 >> Vì vậy, về cơ bản những gì xảy ra là một bảng băm 255 00:13:17,080 --> 00:13:22,050 là khi chúng ta thực sự cần nhanh chóng chèn, xóa, và tra cứu. 256 00:13:22,050 --> 00:13:25,010 Đó là những điều mà chúng tôi ưu tiên trong một bảng băm. 257 00:13:25,010 --> 00:13:29,500 Họ có thể nhận được khá lớn, nhưng như chúng ta sẽ thấy có cố gắng, 258 00:13:29,500 --> 00:13:33,040 có những điều lớn hơn nhiều. 259 00:13:33,040 --> 00:13:38,330 >> Nhưng về cơ bản, tất cả băm bảng là một hàm băm 260 00:13:38,330 --> 00:13:47,215 mà nói với bạn mà xô để đưa từng dữ liệu của bạn, mỗi yếu tố của bạn trong. 261 00:13:47,215 --> 00:13:51,140 Một cách đơn giản để nghĩ về một bảng băm là nó chỉ là xô của sự vật, 262 00:13:51,140 --> 00:13:51,770 phải không? 263 00:13:51,770 --> 00:13:59,720 Vì vậy, khi bạn đang sắp xếp mọi thứ bằng như chữ cái đầu tiên của tên của họ, 264 00:13:59,720 --> 00:14:01,820 đó là loại giống như một bảng băm. 265 00:14:01,820 --> 00:14:06,180 >> Vì vậy, nếu tôi được nhóm các bạn là thành các nhóm của bất cứ ai tên bắt đầu 266 00:14:06,180 --> 00:14:11,670 với A trên đây, hoặc bất cứ ai sinh nhật là là vào tháng Giêng, tháng Hai, tháng Ba, 267 00:14:11,670 --> 00:14:15,220 bất cứ điều gì, đó là hiệu quả tạo ra một bảng băm. 268 00:14:15,220 --> 00:14:18,120 Nó chỉ tạo ra xô đó bạn sắp xếp các yếu tố của bạn thành 269 00:14:18,120 --> 00:14:19,520 để bạn có thể tìm thấy chúng dễ dàng hơn. 270 00:14:19,520 --> 00:14:22,300 Vì vậy, cách này khi tôi cần để tìm một trong các bạn, 271 00:14:22,300 --> 00:14:24,680 Tôi không phải tìm kiếm qua từng tên của bạn. 272 00:14:24,680 --> 00:14:29,490 Tôi có thể được như thế, oh, tôi biết rằng Sinh nhật của Danielle là in-- 273 00:14:29,490 --> 00:14:30,240 Đung --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: Tháng Tư. 275 00:14:30,948 --> 00:14:33,120 Vì vậy, tôi tìm vào tháng Tư của tôi xô, và với bất kỳ may mắn, 276 00:14:33,120 --> 00:14:38,270 cô ấy sẽ là người duy nhất trong đó và thời gian của tôi là không đổi trong ý nghĩa đó, 277 00:14:38,270 --> 00:14:41,230 trong khi đó nếu tôi phải nhìn thông qua một bó toàn bộ người dân, 278 00:14:41,230 --> 00:14:43,090 nó sẽ mất nhiều thời gian hơn nhiều. 279 00:14:43,090 --> 00:14:45,830 Vì vậy, bảng băm thực sự chỉ là xô. 280 00:14:45,830 --> 00:14:48,630 Cách dễ dàng để nghĩ về họ. 281 00:14:48,630 --> 00:14:52,930 >> Vì vậy, một điều rất quan trọng về một bảng băm là một hàm băm. 282 00:14:52,930 --> 00:14:58,140 Vì vậy, những điều tôi vừa nói đến, như chữ cái đầu tiên của tên đầu tiên của bạn 283 00:14:58,140 --> 00:15:01,450 hoặc tháng sinh nhật của bạn, đây là những ý tưởng mà 284 00:15:01,450 --> 00:15:03,070 thực sự tương quan đến một hàm băm. 285 00:15:03,070 --> 00:15:08,900 Nó chỉ là một cách để quyết định xô bạn yếu tố đang đi vào, OK? 286 00:15:08,900 --> 00:15:14,850 Vì vậy, cho pset này, bạn có thể tìm kiếm khá nhiều bất kỳ chức năng hash bạn muốn. 287 00:15:14,850 --> 00:15:16,030 >> Không phải là của riêng bạn. 288 00:15:16,030 --> 00:15:21,140 Có một số những người thực sự mát mẻ có mà làm tất cả các loại của toán học điên. 289 00:15:21,140 --> 00:15:25,170 Và nếu bạn muốn làm cho bạn kiểm tra chính tả siêu nhanh, 290 00:15:25,170 --> 00:15:27,620 Tôi sẽ chắc chắn nhìn vào một trong những. 291 00:15:27,620 --> 00:15:32,390 >> Nhưng đó cũng là những cái đơn giản, giống như tính toán 292 00:15:32,390 --> 00:15:39,010 tổng của các từ, như mỗi chữ cái có một số. 293 00:15:39,010 --> 00:15:39,940 Tính toán tổng. 294 00:15:39,940 --> 00:15:42,230 Xác định xô. 295 00:15:42,230 --> 00:15:45,430 Họ cũng có những người dễ dàng mà cũng giống như tất cả các của A ở đây, 296 00:15:45,430 --> 00:15:47,050 tất cả các B ở đây. 297 00:15:47,050 --> 00:15:48,920 Bất kỳ một trong những người. 298 00:15:48,920 --> 00:15:55,770 >> Về cơ bản, nó chỉ cho bạn biết mảng chỉ số phần tử của bạn nên đi vào. 299 00:15:55,770 --> 00:15:58,690 Chỉ cần quyết định bucket-- đó là tất cả một hàm băm là. 300 00:15:58,690 --> 00:16:04,180 Vì vậy, ở đây chúng ta có một ví dụ đó là chỉ là chữ cái đầu tiên của chuỗi 301 00:16:04,180 --> 00:16:05,900 rằng tôi đã chỉ nói về. 302 00:16:05,900 --> 00:16:11,900 >> Vì vậy, bạn có một số hash đó chỉ là chữ cái đầu tiên của chuỗi trừ của bạn A, 303 00:16:11,900 --> 00:16:16,090 mà sẽ cung cấp cho bạn một số số giữa 0 và 25. 304 00:16:16,090 --> 00:16:20,790 Và những gì bạn muốn làm là chắc chắn rằng điều này thể hiện 305 00:16:20,790 --> 00:16:24,110 kích thước của hash của bạn table-- bao nhiêu xô có. 306 00:16:24,110 --> 00:16:25,860 Với rất nhiều các hàm băm, họ 307 00:16:25,860 --> 00:16:31,630 sẽ được trả về giá trị mà có thể được xa trên số xô 308 00:16:31,630 --> 00:16:33,610 mà bạn thực sự có trong bảng băm của bạn, 309 00:16:33,610 --> 00:16:37,240 vì vậy bạn cần phải thực hiện chắc chắn và mod bởi những người. 310 00:16:37,240 --> 00:16:42,190 Nếu không, nó sẽ nói, oh, nó phải ở trong thùng 5000 311 00:16:42,190 --> 00:16:46,040 nhưng bạn chỉ có 30 xô trong bảng băm của bạn. 312 00:16:46,040 --> 00:16:49,360 Và tất nhiên, chúng ta đều biết đó là sẽ dẫn đến một số lỗi điên. 313 00:16:49,360 --> 00:16:52,870 Vì vậy, hãy chắc chắn để mod bởi các Kích thước của bảng băm của bạn. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Cool. 316 00:16:58,930 --> 00:17:00,506 Vì vậy, va chạm. 317 00:17:00,506 --> 00:17:02,620 Là tất cả mọi người tốt cho đến nay? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Đung Tại sao nó trả lại một giá trị lớn như vậy? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Tùy thuộc vào các thuật toán rằng hàm băm của bạn sử dụng. 321 00:17:09,210 --> 00:17:12,270 Một số trong số họ sẽ làm nhân điên. 322 00:17:12,270 --> 00:17:16,270 Và đó là tất cả về nhận một phân bố, 323 00:17:16,270 --> 00:17:18,490 do đó, họ làm một số thực sự đôi khi những điều điên rồ. 324 00:17:18,490 --> 00:17:20,960 Đó là tất cả. 325 00:17:20,960 --> 00:17:22,140 Bất cứ điều gì khác? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Vì vậy, va chạm. 328 00:17:24,480 --> 00:17:29,270 Về cơ bản, như tôi đã nói trước đó, trong trường hợp kịch bản tốt nhất, 329 00:17:29,270 --> 00:17:32,040 bất kỳ xô tôi nhìn vào là sẽ có một điều, 330 00:17:32,040 --> 00:17:34,160 vì vậy tôi không cần phải xem xét tất cả, phải không? 331 00:17:34,160 --> 00:17:37,040 Tôi có thể biết nó có hay nó không, và đó là những gì chúng ta thực sự muốn. 332 00:17:37,040 --> 00:17:43,960 Nhưng nếu chúng ta có hàng chục ngàn điểm dữ liệu và ít hơn con số đó 333 00:17:43,960 --> 00:17:48,700 xô, chúng ta sẽ có va chạm nơi cuối cùng một cái gì đó 334 00:17:48,700 --> 00:17:54,210 là sẽ phải kết thúc trong một thùng đó đã có một phần tử. 335 00:17:54,210 --> 00:17:57,390 >> Vì vậy, câu hỏi là, những gì Chúng ta phải làm trong trường hợp đó? 336 00:17:57,390 --> 00:17:58,480 Chúng tôi làm gì? 337 00:17:58,480 --> 00:17:59,300 Chúng tôi đã có một cái gì đó? 338 00:17:59,300 --> 00:18:00,060 Chúng ta chỉ cần ném nó ra? 339 00:18:00,060 --> 00:18:00,700 >> Không. 340 00:18:00,700 --> 00:18:01,980 Chúng tôi phải giữ cả hai. 341 00:18:01,980 --> 00:18:06,400 Vì vậy, cách mà chúng ta thường làm điều đó là gì? 342 00:18:06,400 --> 00:18:08,400 Cấu trúc dữ liệu là gì chúng tôi chỉ nói chuyện về? 343 00:18:08,400 --> 00:18:09,316 Đung danh sách liên kết. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: Một danh sách liên kết. 345 00:18:10,500 --> 00:18:16,640 Vì vậy, bây giờ, thay vì mỗi người trong các xô chỉ có một yếu tố, 346 00:18:16,640 --> 00:18:24,020 nó sẽ chứa một danh sách liên kết các yếu tố đó đã băm vào nó. 347 00:18:24,020 --> 00:18:27,588 OK, tất cả mọi người không loại có được ý tưởng đó? 348 00:18:27,588 --> 00:18:30,546 Bởi vì chúng ta không thể có một mảng bởi vì chúng ta không biết bao nhiêu điều 349 00:18:30,546 --> 00:18:31,730 đang có được trong đó. 350 00:18:31,730 --> 00:18:36,540 Một danh sách liên kết cho phép chúng tôi có chỉ số chính xác mà 351 00:18:36,540 --> 00:18:38,465 được băm vào thùng đó, phải không? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Vì vậy, tuyến tính thăm dò là về cơ bản idea-- này 354 00:18:50,500 --> 00:18:52,300 nó là một cách để đối phó với một vụ va chạm. 355 00:18:52,300 --> 00:18:58,010 Những gì bạn có thể làm là nếu, trong này trường hợp, berry được băm vào 1 356 00:18:58,010 --> 00:19:01,130 và chúng tôi đã có một cái gì đó, bạn chỉ cần 357 00:19:01,130 --> 00:19:04,840 tiếp tục đi xuống cho đến khi bạn tìm thấy một khe trống. 358 00:19:04,840 --> 00:19:06,370 Đó là một cách để xử lý nó. 359 00:19:06,370 --> 00:19:09,020 Một cách khác để xử lý đó là với những gì chúng ta chỉ 360 00:19:09,020 --> 00:19:12,280 called-- các liên kết danh sách được gọi là loạt. 361 00:19:12,280 --> 00:19:20,510 >> Vì vậy, ý tưởng này hoạt động nếu bảng băm của bạn, bạn nghĩ 362 00:19:20,510 --> 00:19:24,150 là lớn hơn nhiều so với dữ liệu của bạn thiết lập hoặc nếu bạn 363 00:19:24,150 --> 00:19:28,870 muốn thử và giảm thiểu chaining cho đến khi nó hoàn toàn cần thiết. 364 00:19:28,870 --> 00:19:34,050 Vì vậy, có một điều tuyến tính thăm dò rõ ràng có nghĩa 365 00:19:34,050 --> 00:19:37,290 rằng hàm băm của bạn không phải là khá hữu ích 366 00:19:37,290 --> 00:19:42,200 bởi vì bạn sẽ kết thúc bằng cách sử dụng hàm băm của bạn, nhận được đến một điểm, 367 00:19:42,200 --> 00:19:46,400 bạn tuyến tính thăm dò xuống một số nơi có sẵn. 368 00:19:46,400 --> 00:19:49,670 Nhưng bây giờ, tất nhiên, bất cứ điều gì khác mà kết thúc ở đó, 369 00:19:49,670 --> 00:19:52,050 bạn sẽ phải tìm kiếm thậm chí còn tiếp tục xuống. 370 00:19:52,050 --> 00:19:55,650 >> Và có rất nhiều chi phí tìm kiếm 371 00:19:55,650 --> 00:19:59,820 đi vào nhập vào một yếu tố trong bảng băm của bạn bây giờ, phải không? 372 00:19:59,820 --> 00:20:05,640 Và bây giờ khi bạn đi và cố gắng và tìm thấy berry một lần nữa, bạn sẽ băm nó, 373 00:20:05,640 --> 00:20:07,742 và nó sẽ nói, oh, nhìn trong thùng 1, 374 00:20:07,742 --> 00:20:09,700 và nó sẽ không được trong thùng 1, vì vậy bạn 375 00:20:09,700 --> 00:20:11,970 sẽ phải đi qua thông qua phần còn lại của các. 376 00:20:11,970 --> 00:20:17,720 Vì vậy, nó là đôi khi hữu ích, nhưng trong nhiều trường hợp, 377 00:20:17,720 --> 00:20:22,660 chúng ta sẽ nói rằng chaining là những gì bạn muốn làm. 378 00:20:22,660 --> 00:20:25,520 >> Vì vậy, chúng ta đã nói về điều này trước đó. 379 00:20:25,520 --> 00:20:27,812 Tôi có một chút trước của bản thân mình. 380 00:20:27,812 --> 00:20:33,560 Nhưng xâu chuỗi là cơ bản mà mỗi thùng trong bảng băm của bạn 381 00:20:33,560 --> 00:20:36,120 chỉ là một danh sách liên kết. 382 00:20:36,120 --> 00:20:39,660 >> Vì vậy, một cách khác, hoặc kỹ thuật hơn cách, suy nghĩ của một bảng băm 383 00:20:39,660 --> 00:20:44,490 là nó chỉ là một mảng của danh sách liên kết, mà 384 00:20:44,490 --> 00:20:49,330 khi bạn đang viết từ điển của bạn và bạn đang cố gắng để tải nó, 385 00:20:49,330 --> 00:20:52,070 suy nghĩ về nó như một mảng các danh sách liên kết 386 00:20:52,070 --> 00:20:54,390 sẽ làm cho nó dễ dàng hơn nhiều để bạn có thể khởi tạo. 387 00:20:54,390 --> 00:20:57,680 >> Đung Vì vậy, bảng băm có kích thước định trước, 388 00:20:57,680 --> 00:20:58,980 giống như một [không nghe được] xô? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Đúng vậy. 390 00:20:59,220 --> 00:21:01,655 Vì vậy, nó có một số thiết lập của nhóm bạn determine-- 391 00:21:01,655 --> 00:21:03,530 mà các bạn nên cảm thấy tự do để chơi với. 392 00:21:03,530 --> 00:21:05,269 Nó có thể là khá mát mẻ để xem những gì sẽ xảy ra 393 00:21:05,269 --> 00:21:06,810 khi bạn thay đổi số của bạn xô. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Nhưng yeah, nó có một thiết lập số xô. 396 00:21:11,510 --> 00:21:15,360 Những gì cho phép bạn để phù hợp như nhiều yếu tố như bạn cần 397 00:21:15,360 --> 00:21:19,350 là xâu chuỗi riêng biệt này, nơi bạn có danh sách liên kết trong mỗi nhóm. 398 00:21:19,350 --> 00:21:22,850 Điều đó có nghĩa bảng băm của bạn sẽ được chính xác kích thước 399 00:21:22,850 --> 00:21:25,440 mà bạn cần nó được, phải không? 400 00:21:25,440 --> 00:21:27,358 Đó là toàn bộ điểm của danh sách liên kết. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Cool. 403 00:21:32,480 --> 00:21:38,780 >> Vì vậy, tất cả mọi người có OK? 404 00:21:38,780 --> 00:21:39,801 Được rồi. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Chuyện gì vừa xảy ra? 407 00:21:41,860 --> 00:21:42,960 Thực sự bây giờ. 408 00:21:42,960 --> 00:21:45,250 Đoán ai đó giết chết tôi. 409 00:21:45,250 --> 00:21:52,060 >> OK chúng ta sẽ đi vào cố gắng, đó là một chút điên rồ. 410 00:21:52,060 --> 00:21:53,140 Tôi thích các bảng băm. 411 00:21:53,140 --> 00:21:54,460 Tôi nghĩ rằng họ đang thực sự mát mẻ. 412 00:21:54,460 --> 00:21:56,710 Cố gắng là mát mẻ, quá. 413 00:21:56,710 --> 00:21:59,590 >> Vì vậy, không ai nhớ những gì một thử là? 414 00:21:59,590 --> 00:22:01,740 Bạn nên đã đi qua nó ngắn gọn trong bài giảng? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Bạn có nhớ loại làm thế nào nó hoạt động? 417 00:22:06,377 --> 00:22:08,460 Đung Tôi chỉ gật đầu rằng chúng tôi đã đi qua nó. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Chúng tôi đi qua nó. 419 00:22:09,626 --> 00:22:13,100 OK, chúng tôi đang thực sự sẽ đi hơn nó bây giờ là những gì chúng ta đang nói. 420 00:22:13,100 --> 00:22:14,860 >> Đung Đó là một cây hồi. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Yeah. 422 00:22:15,280 --> 00:22:16,196 Đó là một cây hồi. 423 00:22:16,196 --> 00:22:16,960 Tuyệt vời. 424 00:22:16,960 --> 00:22:23,610 Vì vậy, một điều cần chú ý ở đây là chúng tôi đang xem xét đặc điểm cá nhân 425 00:22:23,610 --> 00:22:24,480 ở đây, phải không? 426 00:22:24,480 --> 00:22:29,710 >> Vì vậy, trước khi với hàm băm của chúng tôi, chúng tôi đang tìm kiếm tại các từ như một toàn thể, 427 00:22:29,710 --> 00:22:32,270 và bây giờ chúng tôi đang tìm kiếm nhiều hơn tại các nhân vật, phải không? 428 00:22:32,270 --> 00:22:38,380 Vì vậy, chúng tôi có Maxwell trên đây và Mendel. 429 00:22:38,380 --> 00:22:47,840 Vì vậy, về cơ bản một try-- một cách để suy nghĩ về việc này là tất cả các cấp ở đây 430 00:22:47,840 --> 00:22:49,000 là một mảng của các chữ cái. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Vì vậy, đây là nút gốc của bạn ở đây, phải không? 433 00:22:55,790 --> 00:23:01,980 Điều này có tất cả các ký tự của bảng chữ cái cho sự bắt đầu của mỗi từ. 434 00:23:01,980 --> 00:23:06,480 >> Và những gì bạn muốn làm là nói, OK, chúng tôi có một số M từ. 435 00:23:06,480 --> 00:23:10,590 Chúng tôi sẽ tìm kiếm Maxwell, vì vậy chúng tôi đi đến M. Và M điểm để toàn bộ 436 00:23:10,590 --> 00:23:14,800 một mảng khác, nơi mọi từ, miễn là có 437 00:23:14,800 --> 00:23:17,044 là một từ có A là lá thư thứ hai, 438 00:23:17,044 --> 00:23:19,460 miễn là có là một từ mà có B là lá thư thứ hai, 439 00:23:19,460 --> 00:23:24,630 nó sẽ có một con trỏ đi đến một số mảng tới. 440 00:23:24,630 --> 00:23:29,290 >> Có lẽ không phải là một từ đó MP một cái gì đó, 441 00:23:29,290 --> 00:23:32,980 để ở vị trí P trong này mảng, nó sẽ chỉ được NULL. 442 00:23:32,980 --> 00:23:38,840 Nó sẽ nói, OK, không có từ M đã theo sau là một P, OK? 443 00:23:38,840 --> 00:23:43,100 Vì vậy, nếu chúng ta nghĩ về nó, mỗi một trong những điều nhỏ 444 00:23:43,100 --> 00:23:47,990 thực sự là một trong những mảng lớn từ A đến Z. 445 00:23:47,990 --> 00:23:55,064 Vì vậy, những gì có thể là một trong những điều đó là loại một nhược điểm của một thử? 446 00:23:55,064 --> 00:23:56,500 >> Đung A rất nhiều bộ nhớ. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Đó là một tấn của bộ nhớ, phải không? 448 00:23:59,940 --> 00:24:08,750 Mỗi một trong những khối ở đây đại diện cho 26 không gian, 26 mảng yếu tố. 449 00:24:08,750 --> 00:24:13,680 Vì vậy, cố gắng có được không gian vô cùng nặng nề. 450 00:24:13,680 --> 00:24:17,100 >> Nhưng họ rất nhanh. 451 00:24:17,100 --> 00:24:22,540 Vì vậy, cực kỳ nhanh chóng nhưng không gian thực sự không hiệu quả. 452 00:24:22,540 --> 00:24:24,810 Loại phải tìm ra cái nào bạn muốn. 453 00:24:24,810 --> 00:24:29,470 Đây là thực sự mát mẻ cho pset của bạn, nhưng họ làm mất rất nhiều bộ nhớ, 454 00:24:29,470 --> 00:24:30,290 vì vậy bạn đánh đổi. 455 00:24:30,290 --> 00:24:31,480 Yeah? 456 00:24:31,480 --> 00:24:34,300 >> Đung Nó sẽ có thể để thiết lập một thử và sau đó 457 00:24:34,300 --> 00:24:37,967 một khi bạn có tất cả các dữ liệu trong nó mà bạn need-- 458 00:24:37,967 --> 00:24:39,550 Tôi không biết nếu điều đó sẽ có ý nghĩa. 459 00:24:39,550 --> 00:24:42,200 Tôi đã nhận được thoát khỏi tất cả các NULL ký tự, nhưng sau đó 460 00:24:42,200 --> 00:24:42,910 bạn sẽ không có khả năng chỉ số them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Bạn vẫn cần họ. 462 00:24:43,275 --> 00:24:44,854 >> Đung - theo cùng một cách mỗi lần. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Yeah. 464 00:24:45,520 --> 00:24:50,460 Bạn cần các nhân vật NULL để cho Bạn có biết nếu không có một từ đó. 465 00:24:50,460 --> 00:24:52,040 Bạn Ben đã có một cái gì đó bạn muốn? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Tất cả các bên phải, vì vậy chúng ta sẽ đi hơn một chút 468 00:24:54,581 --> 00:24:58,920 vào chi tiết kỹ thuật đằng sau một cố gắng và làm việc thông qua một ví dụ. 469 00:24:58,920 --> 00:25:01,490 >> OK, vì vậy đây là điều tương tự. 470 00:25:01,490 --> 00:25:06,290 Trong khi đó, trong một danh sách liên kết, chính chúng tôi loại of-- từ tôi muốn là những gì? - 471 00:25:06,290 --> 00:25:08,350 như xây dựng khối là một nút. 472 00:25:08,350 --> 00:25:12,280 Trong một cố gắng, chúng tôi cũng có một nút, nhưng nó được định nghĩa khác nhau. 473 00:25:12,280 --> 00:25:17,000 >> Vì vậy, chúng tôi có một số bool mà đại diện cho dù một từ thực sự 474 00:25:17,000 --> 00:25:23,530 tồn tại ở vị trí này, và sau đó chúng tôi có một số mảng here-- hay đúng hơn, 475 00:25:23,530 --> 00:25:27,840 đây là một con trỏ đến một mảng 27 ký tự. 476 00:25:27,840 --> 00:25:33,339 Và đây là cho, trong trường hợp này, điều này 27-- tôi chắc chắn rằng tất cả các bạn là như thế, chờ đợi, 477 00:25:33,339 --> 00:25:34,880 có 26 chữ cái trong bảng chữ cái. 478 00:25:34,880 --> 00:25:36,010 Tại sao chúng ta có 27? 479 00:25:36,010 --> 00:25:37,870 >> Vì vậy, tùy thuộc vào cách bạn thực hiện điều này, 480 00:25:37,870 --> 00:25:43,240 này là từ một pset đó cho phép dấu nháy. 481 00:25:43,240 --> 00:25:46,010 Vì vậy, đó là lý do tại sao một trong những phụ. 482 00:25:46,010 --> 00:25:50,500 Bạn cũng sẽ có trong một số trường hợp terminator rỗng 483 00:25:50,500 --> 00:25:53,230 được bao gồm như là một trong những các ký tự mà nó được phép có, 484 00:25:53,230 --> 00:25:56,120 và đó là cách họ kiểm tra xem nếu nó là sự kết thúc của từ này. 485 00:25:56,120 --> 00:26:01,340 Nếu bạn quan tâm, hãy kiểm tra Video Kevin trên study.cs50, 486 00:26:01,340 --> 00:26:04,790 cũng như Wikipedia có một số nguồn tài nguyên tốt ở đó. 487 00:26:04,790 --> 00:26:09,000 >> Nhưng chúng ta sẽ đi qua chỉ loại làm thế nào bạn có thể làm việc thông qua một thử 488 00:26:09,000 --> 00:26:11,010 nếu bạn đang đưa ra một. 489 00:26:11,010 --> 00:26:16,230 Vì vậy, chúng tôi có một siêu đơn giản ở đây mà có các từ "dơi" và "zoom" trong đó. 490 00:26:16,230 --> 00:26:18,920 Và như chúng ta thấy ở đây, không gian nhỏ bé này ở đây 491 00:26:18,920 --> 00:26:22,560 đại diện bool của chúng tôi nói, vâng, đây là một từ. 492 00:26:22,560 --> 00:26:27,060 Và sau đó điều này có của chúng tôi mảng của các nhân vật, phải không? 493 00:26:27,060 --> 00:26:33,480 >> Vì vậy, chúng ta sẽ đi qua tìm kiếm "bat" trong thử này. 494 00:26:33,480 --> 00:26:38,340 Vì vậy, bắt đầu ở đầu, phải không? 495 00:26:38,340 --> 00:26:46,290 Và chúng ta biết rằng b tương ứng với chỉ số thứ hai, yếu tố thứ hai 496 00:26:46,290 --> 00:26:47,840 trong mảng này, bởi vì a và b. 497 00:26:47,840 --> 00:26:51,340 Vì vậy, khoảng thứ hai. 498 00:26:51,340 --> 00:26:58,820 >> Và nó nói, OK, mát mẻ, theo đó vào mảng tiếp theo, bởi vì nếu chúng ta nhớ, 499 00:26:58,820 --> 00:27:02,160 nó không phải là mỗi một trong các thực sự có chứa nguyên tố này. 500 00:27:02,160 --> 00:27:07,110 Mỗi một trong những mảng chứa một con trỏ, phải không? 501 00:27:07,110 --> 00:27:10,030 Đây là một khác biệt quan trọng để thực hiện. 502 00:27:10,030 --> 00:27:13,450 >> Tôi biết điều này sẽ cố gắng là be-- thực sự khó khăn để có được vào thời gian đầu tiên, 503 00:27:13,450 --> 00:27:15,241 vì vậy ngay cả nếu điều này là lần thứ hai hoặc thứ ba 504 00:27:15,241 --> 00:27:18,370 và nó vẫn còn loại của vẻ khó khăn, 505 00:27:18,370 --> 00:27:21,199 Tôi hứa nếu bạn đi xem ngày mai ngắn một lần nữa, 506 00:27:21,199 --> 00:27:22,740 nó có thể sẽ có ý nghĩa hơn rất nhiều. 507 00:27:22,740 --> 00:27:23,890 Phải mất rất nhiều để tiêu hóa. 508 00:27:23,890 --> 00:27:27,800 Tôi vẫn còn đôi khi là như thế, chờ đợi, một thử là gì? 509 00:27:27,800 --> 00:27:29,080 Làm thế nào để sử dụng này? 510 00:27:29,080 --> 00:27:33,880 >> Vì vậy, chúng tôi có b trong trường hợp này, đó là chỉ số thứ hai của chúng tôi. 511 00:27:33,880 --> 00:27:40,240 Nếu chúng ta có, nói, c hoặc d hoặc bất kỳ thư khác, 512 00:27:40,240 --> 00:27:45,810 chúng ta cần phải bản đồ lại cho rằng chỉ số của mảng của chúng tôi rằng tương ứng với. 513 00:27:45,810 --> 00:27:56,930 Vì vậy, chúng tôi sẽ có như rchar và chúng tôi chỉ trừ ra một bản đồ nó vào 0-25. 514 00:27:56,930 --> 00:27:58,728 Mọi người đều tốt như thế nào chúng tôi bản đồ nhân vật của chúng tôi? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Vì vậy, chúng tôi đi đến thứ hai và chúng tôi thấy rằng, có, nó không phải là để NULL. 517 00:28:05,980 --> 00:28:07,780 Chúng tôi có thể chuyển sang mảng tiếp theo này. 518 00:28:07,780 --> 00:28:12,300 Vì vậy, chúng tôi đi vào mảng tiếp theo này ở đây. 519 00:28:12,300 --> 00:28:15,500 >> Và chúng ta nói, OK, bây giờ chúng tôi cần phải xem một là ở đây. 520 00:28:15,500 --> 00:28:18,590 Một là null hay không nó thực sự di chuyển về phía trước? 521 00:28:18,590 --> 00:28:21,880 Vì vậy, một thực sự di chuyển chuyển tiếp trong mảng này. 522 00:28:21,880 --> 00:28:24,570 Và chúng ta nói, OK, t là lá thư cuối cùng của chúng tôi. 523 00:28:24,570 --> 00:28:27,580 Vì vậy, chúng tôi đi đến t ở các chỉ số. 524 00:28:27,580 --> 00:28:30,120 Và sau đó chúng tôi di chuyển về phía trước bởi vì có một số khác. 525 00:28:30,120 --> 00:28:38,340 Và điều này về cơ bản nói rằng, có, nó nói rằng đó là một từ here-- 526 00:28:38,340 --> 00:28:41,750 rằng nếu bạn làm theo điều này đường dẫn, bạn đã đến 527 00:28:41,750 --> 00:28:43,210 tại một từ, mà chúng ta biết là "con dơi". 528 00:28:43,210 --> 00:28:43,800 Có? 529 00:28:43,800 --> 00:28:46,770 >> ĐỐI TƯỢNG: Có tiêu chuẩn để có mà như chỉ số 0 và sau đó có một loại 1 530 00:28:46,770 --> 00:28:47,660 hoặc có ở cuối? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: No. 532 00:28:48,243 --> 00:28:55,360 Vì vậy, nếu chúng ta nhìn lại chúng tôi khai ở đây, đó là một bool, 533 00:28:55,360 --> 00:28:59,490 do đó, nó là yếu tố riêng của mình trong nút của bạn. 534 00:28:59,490 --> 00:29:03,331 Vì vậy, nó không phải là một phần của mảng. 535 00:29:03,331 --> 00:29:03,830 Cool. 536 00:29:03,830 --> 00:29:08,370 Vì vậy, khi chúng tôi kết thúc từ của chúng tôi và chúng tôi ở mảng này, những gì chúng tôi muốn làm 537 00:29:08,370 --> 00:29:12,807 là làm một kiểm tra cho là này một từ. 538 00:29:12,807 --> 00:29:14,390 Và trong trường hợp này, nó sẽ trở lại có. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Vì vậy, trên lưu ý rằng, chúng ta biết rằng "sở thú" - chúng ta biết rằng con người là "sở thú" là một từ, 541 00:29:24,090 --> 00:29:24,820 phải không? 542 00:29:24,820 --> 00:29:28,990 Nhưng được thử ở đây sẽ nói, không, nó không phải. 543 00:29:28,990 --> 00:29:33,980 Và nó sẽ nói rằng bởi vì chúng tôi đã không được chỉ định nó như là một lời ở đây. 544 00:29:33,980 --> 00:29:40,440 Mặc dù chúng tôi có thể đi qua thông qua vào mảng này, 545 00:29:40,440 --> 00:29:43,890 thử này có thể nói rằng, không có, vườn thú không phải là trong từ điển của bạn 546 00:29:43,890 --> 00:29:47,070 bởi vì chúng tôi đã không được chỉ định nó như vậy. 547 00:29:47,070 --> 00:29:52,870 >> Vì vậy, một cách để làm that-- oh, xin lỗi, cái này. 548 00:29:52,870 --> 00:29:59,450 Vì vậy, trong trường hợp này, "sở thú" không phải là một từ, nhưng nó là trong thử của chúng tôi. 549 00:29:59,450 --> 00:30:05,690 Nhưng trong vụ việc này, nói rằng chúng ta muốn nó giới thiệu từ "tắm", những gì xảy ra 550 00:30:05,690 --> 00:30:08,260 là chúng tôi làm theo through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 Chúng tôi đang ở trong mảng này, và chúng tôi đi để tìm kiếm h. 552 00:30:11,820 --> 00:30:15,220 >> Trong trường hợp này, khi chúng ta nhìn vào con trỏ tại h, 553 00:30:15,220 --> 00:30:17,890 nó trỏ đến NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Vì vậy, trừ khi đó là một cách rõ ràng trỏ đến mảng khác, 555 00:30:20,780 --> 00:30:25,000 bạn cho rằng tất cả các con trỏ trong mảng này được trỏ đến null. 556 00:30:25,000 --> 00:30:28,270 Vì vậy, trong trường hợp này, h đang trỏ null vì vậy chúng tôi không thể làm bất cứ điều gì, 557 00:30:28,270 --> 00:30:31,540 vì vậy nó cũng sẽ quay trở lại sai lầm, "tắm" không phải là ở đây. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Vì vậy, bây giờ chúng tôi đang thực sự sẽ đi qua 560 00:30:35,810 --> 00:30:39,790 làm sao chúng ta thực sự nói rằng "sở thú" là trong thử của chúng tôi. 561 00:30:39,790 --> 00:30:42,920 Làm thế nào để chúng ta chèn "sở thú" thành thử chúng tôi? 562 00:30:42,920 --> 00:30:47,810 Vì vậy, trong cùng một cách mà chúng tôi bắt đầu với danh sách liên kết của chúng tôi, chúng tôi bắt đầu từ gốc rễ. 563 00:30:47,810 --> 00:30:50,600 Khi nghi ngờ, bắt đầu từ gốc rễ của những điều này. 564 00:30:50,600 --> 00:30:53,330 >> Và chúng ta sẽ nói, OK, z. 565 00:30:53,330 --> 00:30:55,650 z tồn tại trong này, và nó. 566 00:30:55,650 --> 00:30:58,370 Vì vậy, bạn đang di chuyển trên để mảng tiếp theo của bạn, OK? 567 00:30:58,370 --> 00:31:01,482 Và sau đó vào tiếp theo, chúng ta nói, OK, không o tồn tại? 568 00:31:01,482 --> 00:31:03,000 Nó thực hiện. 569 00:31:03,000 --> 00:31:04,330 Điều này một lần nữa. 570 00:31:04,330 --> 00:31:08,670 >> Và như vậy tiếp theo của chúng tôi, chúng tôi đã nói, OK, "sở thú" đã tồn tại ở đây. 571 00:31:08,670 --> 00:31:12,440 Tất cả chúng ta cần làm là thiết lập bằng này đúng sự thật, rằng có một từ đó. 572 00:31:12,440 --> 00:31:15,260 Nếu bạn đã theo dõi tất cả mọi thứ đến trước thời điểm đó, 573 00:31:15,260 --> 00:31:17,030 đó là một từ, vì vậy chỉ cần thiết lập nó bằng như vậy. 574 00:31:17,030 --> 00:31:17,530 Có? 575 00:31:17,530 --> 00:31:22,550 >> Đung Vì vậy, sau đó thực hiện điều đó có nghĩa là "ba" là một từ cũng? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: No. 577 00:31:24,120 --> 00:31:28,870 Vì vậy, trong trường hợp này, "ba", chúng tôi sẽ nhận được ở đây, chúng ta sẽ nói nó là một từ, 578 00:31:28,870 --> 00:31:31,590 và nó vẫn sẽ không có. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Đung Vì vậy, một khi bạn nó là một từ và bạn nói có, sau đó nó 582 00:31:36,360 --> 00:31:38,380 sẽ chứa để đi đến m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Vì vậy, điều này đã làm with-- bạn đang tải này. 584 00:31:42,260 --> 00:31:43,640 Bạn nói "sở thú" là một từ. 585 00:31:43,640 --> 00:31:47,020 Khi bạn đi đến check-- như thế, nói rằng bạn muốn nói, 586 00:31:47,020 --> 00:31:49,400 không "sở thú" tồn tại trong từ điển này? 587 00:31:49,400 --> 00:31:54,200 Bạn sẽ chỉ tìm kiếm cho "vườn thú" và sau đó kiểm tra để xem nếu nó là một từ. 588 00:31:54,200 --> 00:31:57,291 Bạn sẽ không bao giờ để di chuyển thông qua để m bởi vì đó không phải là 589 00:31:57,291 --> 00:31:58,290 những gì bạn đang tìm kiếm. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Vì vậy, nếu chúng ta thực sự muốn thêm "tắm" vào thử này, 592 00:32:08,070 --> 00:32:11,390 chúng tôi sẽ làm điều tương tự như chúng ta đã làm với "sở thú" 593 00:32:11,390 --> 00:32:15,380 ngoại trừ chúng ta sẽ thấy rằng khi chúng ta thử và nhận được đến h, nó không tồn tại. 594 00:32:15,380 --> 00:32:20,090 Vì vậy, bạn có thể nghĩ về điều này như cố gắng để thêm một nút mới vào một danh sách liên kết, 595 00:32:20,090 --> 00:32:27,210 vì vậy chúng tôi sẽ cần phải thêm một một trong những mảng, như vậy. 596 00:32:27,210 --> 00:32:35,670 Và sau đó những gì chúng tôi làm là chúng ta chỉ cần thiết lập h phần tử của mảng này chỉ vào này. 597 00:32:35,670 --> 00:32:39,430 >> Và sau đó những gì chúng tôi muốn làm ở đây? 598 00:32:39,430 --> 00:32:43,110 Thêm nó bằng đúng sự thật bởi vì nó là một từ. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Cool. 601 00:32:48,150 --> 00:32:48,700 Tôi biết. 602 00:32:48,700 --> 00:32:51,170 Cố gắng không phải là thú vị nhất. 603 00:32:51,170 --> 00:32:54,250 Hãy tin tôi, tôi biết. 604 00:32:54,250 --> 00:32:58,040 >> Vì vậy, một điều nhận ra có cố gắng, Tôi đã nói, họ đang rất hiệu quả. 605 00:32:58,040 --> 00:33:00,080 Vì vậy, chúng tôi đã nhìn thấy họ mất một tấn của không gian. 606 00:33:00,080 --> 00:33:01,370 Họ đang loại khó hiểu. 607 00:33:01,370 --> 00:33:03,367 Vì vậy, tại sao chúng ta không bao giờ sử dụng những? 608 00:33:03,367 --> 00:33:05,450 Chúng tôi sử dụng những vì họ vô cùng hiệu quả. 609 00:33:05,450 --> 00:33:08,130 >> Vì vậy, nếu bạn đã bao giờ tìm kiếm lên một từ, bạn chỉ 610 00:33:08,130 --> 00:33:10,450 giới hạn bởi chiều dài của từ này. 611 00:33:10,450 --> 00:33:15,210 Vì vậy, nếu bạn đang tìm kiếm một từ đó là chiều dài của năm, 612 00:33:15,210 --> 00:33:20,940 bạn chỉ bao giờ sẽ phải làm cho ít nhất năm so sánh, OK? 613 00:33:20,940 --> 00:33:25,780 Vì vậy, nó làm cho nó về cơ bản là một hằng số. 614 00:33:25,780 --> 00:33:29,150 Giống như chèn và tra cứu về cơ bản là hằng số thời gian. 615 00:33:29,150 --> 00:33:33,750 >> Vì vậy, nếu bạn đã bao giờ có thể nhận được một cái gì đó trong thời gian liên tục, 616 00:33:33,750 --> 00:33:35,150 đó là tốt như nó được. 617 00:33:35,150 --> 00:33:37,990 Bạn không thể có được tốt hơn hằng số thời gian cho những việc này. 618 00:33:37,990 --> 00:33:43,150 Vì vậy, đó là một trong những ưu điểm rất lớn của cố gắng. 619 00:33:43,150 --> 00:33:46,780 >> Nhưng đó là rất nhiều không gian. 620 00:33:46,780 --> 00:33:50,380 Vì vậy, bạn hẳn sẽ có những quyết định những gì quan trọng với bạn hơn. 621 00:33:50,380 --> 00:33:54,700 Và trên các máy tính ngày nay, không gian mà một thử có thể mất 622 00:33:54,700 --> 00:33:57,740 có lẽ không ảnh hưởng đến bạn rằng nhiều, nhưng có lẽ 623 00:33:57,740 --> 00:34:01,350 bạn đang làm việc với một cái gì đó có những thứ xa, xa hơn, 624 00:34:01,350 --> 00:34:02,810 và một thử chỉ là không hợp lý. 625 00:34:02,810 --> 00:34:03,000 Có? 626 00:34:03,000 --> 00:34:05,610 >> ĐỐI TƯỢNG: Chờ đợi, vì vậy bạn có 26 chữ cái trong mỗi một đơn? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Yeah, bạn có 26. 629 00:34:08,570 --> 00:34:16,984 Bạn có một số là đánh dấu từ và sau đó bạn có 26 con trỏ trong mỗi một. 630 00:34:16,984 --> 00:34:17,775 Và họ đang point-- 631 00:34:17,775 --> 00:34:20,280 >> Đung Và mỗi 26, Họ từng có 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Có. 633 00:34:21,500 --> 00:34:27,460 Và đó là lý do tại sao, như bạn có thể thấy, nó mở rộng khá nhanh chóng. 634 00:34:27,460 --> 00:34:28,130 Được rồi. 635 00:34:28,130 --> 00:34:32,524 Vì vậy, chúng ta sẽ nhận được vào cây, Tôi cảm thấy thích được dễ dàng hơn và có thể sẽ 636 00:34:32,524 --> 00:34:36,150 được hoãn thi hành án ít tốt đẹp từ cố gắng đó. 637 00:34:36,150 --> 00:34:39,620 Vì vậy, hy vọng nhất của bạn đã thấy một cái cây trước. 638 00:34:39,620 --> 00:34:41,820 Không giống như khá những người bên ngoài, mà tôi 639 00:34:41,820 --> 00:34:44,340 không biết nếu bất cứ ai đi ngoài trời gần đây. 640 00:34:44,340 --> 00:34:49,230 Tôi đi táo chọn cuối tuần này, và oh chúa ơi, nó thật đẹp. 641 00:34:49,230 --> 00:34:52,250 Tôi không biết lá có thể nhìn thấy khá. 642 00:34:52,250 --> 00:34:53,610 >> Vì vậy, đây chỉ là một cây, phải không? 643 00:34:53,610 --> 00:34:56,790 Nó chỉ là một số nút, và nó chỉ ra một loạt các nút khác. 644 00:34:56,790 --> 00:34:59,570 Như bạn thấy ở đây, đây là loại một chủ đề định kỳ. 645 00:34:59,570 --> 00:35:03,720 Các nút trỏ đến nút là loại bản chất của nhiều cấu trúc dữ liệu. 646 00:35:03,720 --> 00:35:06,670 Nó chỉ phụ thuộc vào cách chúng ta có chúng trỏ đến nhau 647 00:35:06,670 --> 00:35:08,600 và làm thế nào chúng tôi đi qua thông qua họ và làm thế nào chúng ta 648 00:35:08,600 --> 00:35:14,500 chèn những điều mà xác định đặc điểm khác nhau của họ. 649 00:35:14,500 --> 00:35:17,600 >> Vì vậy, chỉ một số thuật ngữ, mà tôi đã sử dụng trước. 650 00:35:17,600 --> 00:35:20,010 Vì vậy, gốc rễ là bất cứ điều gì là ở đầu. 651 00:35:20,010 --> 00:35:21,200 đó là nơi chúng tôi luôn luôn bắt đầu. 652 00:35:21,200 --> 00:35:23,610 Bạn có thể nghĩ về nó như người đứng đầu cũng. 653 00:35:23,610 --> 00:35:28,750 Nhưng đối với cây cối, chúng ta có xu hướng đề cập đến nó như là gốc. 654 00:35:28,750 --> 00:35:32,820 >> Bất cứ điều gì ở phía dưới here-- ở rất, rất bottom-- 655 00:35:32,820 --> 00:35:34,500 là lá xem xét. 656 00:35:34,500 --> 00:35:37,210 Vì vậy, nó đi cùng với các toàn bộ điều cây, phải không? 657 00:35:37,210 --> 00:35:39,860 Lá ở các cạnh của cây. 658 00:35:39,860 --> 00:35:45,820 >> Và sau đó chúng tôi cũng có một vài điều kiện để nói chuyện về các nút liên quan 659 00:35:45,820 --> 00:35:46,680 với nhau. 660 00:35:46,680 --> 00:35:49,700 Vì vậy, chúng tôi có cha mẹ, trẻ em, và anh chị em. 661 00:35:49,700 --> 00:35:56,260 Vì vậy, trong trường hợp này, 3 là mẹ của 5, 6, và 7. 662 00:35:56,260 --> 00:36:00,370 Vì vậy, cha mẹ là bất cứ điều gì một bước trên bất cứ điều gì bạn 663 00:36:00,370 --> 00:36:02,940 đề cập đến, vì vậy chỉ cần giống như một cây gia đình. 664 00:36:02,940 --> 00:36:07,090 Hy vọng rằng, đây là tất cả một chút bit trực quan hơn so với cố gắng. 665 00:36:07,090 --> 00:36:10,970 >> Anh chị em là bất kỳ có cùng cha mẹ, phải không? 666 00:36:10,970 --> 00:36:13,470 Họ đang ở trên cùng cấp ở đây. 667 00:36:13,470 --> 00:36:16,960 Và sau đó, như tôi đã nói rằng, trẻ em chỉ là 668 00:36:16,960 --> 00:36:22,630 bất cứ điều gì là một trong những bước dưới đây nút trong câu hỏi, OK? 669 00:36:22,630 --> 00:36:23,470 Cool. 670 00:36:23,470 --> 00:36:25,610 Vì vậy, một cây nhị phân. 671 00:36:25,610 --> 00:36:31,450 Ai cũng có thể gây nguy hiểm đoán về một trong các đặc tính của cây nhị phân? 672 00:36:31,450 --> 00:36:32,770 >> Đung Max hai lá. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Đúng vậy. 674 00:36:33,478 --> 00:36:34,640 Vì vậy, tối đa của hai lá. 675 00:36:34,640 --> 00:36:39,730 Vì vậy, trong một này trước đây, chúng tôi đã có một này rằng có ba, nhưng trong một cây nhị phân, 676 00:36:39,730 --> 00:36:45,000 bạn có một tối đa của hai trẻ em mỗi phụ huynh, phải không? 677 00:36:45,000 --> 00:36:46,970 Có một đặc điểm thú vị. 678 00:36:46,970 --> 00:36:51,550 Có ai biết không? 679 00:36:51,550 --> 00:36:52,620 Cây nhị phân. 680 00:36:52,620 --> 00:37:00,350 >> Vì vậy, một cây nhị phân sẽ có tất cả mọi thứ trên the-- này là không sorted-- 681 00:37:00,350 --> 00:37:05,320 nhưng trong một cây nhị phân được sắp xếp, tất cả mọi thứ ở bên phải 682 00:37:05,320 --> 00:37:08,530 lớn hơn cha mẹ, và tất cả mọi thứ trên trái 683 00:37:08,530 --> 00:37:10,035 là ít hơn so với cha mẹ. 684 00:37:10,035 --> 00:37:15,690 Và đó là một bài kiểm tra câu hỏi trước, vì vậy tốt để biết. 685 00:37:15,690 --> 00:37:19,500 Vì vậy, cách chúng ta định nghĩa này, một lần nữa, chúng tôi có một nút khác. 686 00:37:19,500 --> 00:37:21,880 Điều này trông rất giống với những gì? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Gấp đôi 689 00:37:28,836 --> 00:37:29,320 >> Danh sách liên kết: TƯỢNG 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Một danh sách liên kết đôi, phải không? 691 00:37:31,100 --> 00:37:33,690 Vì vậy, nếu chúng ta thay thế này với trước và sau, 692 00:37:33,690 --> 00:37:35,670 đây sẽ là một danh sách gấp đôi liên kết. 693 00:37:35,670 --> 00:37:40,125 Nhưng trong trường hợp này, chúng tôi thực sự có trái và bên phải và đó là nó. 694 00:37:40,125 --> 00:37:41,500 Nếu không, nó giống hệt nhau. 695 00:37:41,500 --> 00:37:43,374 Chúng tôi vẫn còn có các yếu tố bạn đang tìm kiếm, 696 00:37:43,374 --> 00:37:45,988 và bạn chỉ có hai con trỏ đi bất cứ điều gì tiếp theo. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Yeah, cây tìm kiếm nhị phân như vậy. 699 00:37:51,870 --> 00:37:57,665 Nếu chúng tôi nhận thấy, tất cả mọi thứ trên ngay ở đây là than-- lớn hơn 700 00:37:57,665 --> 00:37:59,850 hoặc tất cả mọi thứ ngay lập tức bên phải ở đây 701 00:37:59,850 --> 00:38:02,840 là lớn hơn, tất cả mọi thứ ở đây là ít hơn. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Vì vậy, nếu chúng ta tìm kiếm thông qua, nó nên nhìn rất gần với tìm kiếm nhị phân 704 00:38:14,000 --> 00:38:14,910 ở đây, phải không? 705 00:38:14,910 --> 00:38:17,640 Ngoại trừ thay vì tìm kiếm một nửa mảng, 706 00:38:17,640 --> 00:38:21,720 chúng ta chỉ nhìn vào một trong hai bên trái phía này hay phía bên phải của cây. 707 00:38:21,720 --> 00:38:24,850 Vì vậy, nó được một chút đơn giản, tôi nghĩ. 708 00:38:24,850 --> 00:38:29,300 >> Vì vậy, nếu gốc của bạn là NULL, rõ ràng là nó chỉ là sai. 709 00:38:29,300 --> 00:38:33,470 Và nếu nó có, rõ ràng đó là sự thật. 710 00:38:33,470 --> 00:38:35,320 Nếu nó ít hơn, chúng ta tìm kiếm bên trái. 711 00:38:35,320 --> 00:38:37,070 Nếu nó lớn hơn, chúng ta tìm kiếm bên phải. 712 00:38:37,070 --> 00:38:39,890 Đó là chính xác như tìm kiếm nhị phân, chỉ là một cấu trúc dữ liệu khác nhau 713 00:38:39,890 --> 00:38:40,600 mà chúng ta đang sử dụng. 714 00:38:40,600 --> 00:38:42,790 Thay vì một mảng, nó chỉ là một cây nhị phân. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, ngăn xếp. 717 00:38:48,090 --> 00:38:51,550 Và cũng có thể, nó trông giống như chúng tôi có thể có một chút thời gian. 718 00:38:51,550 --> 00:38:54,460 Nếu chúng ta làm, tôi đang hạnh phúc để đi hơn bất kỳ này một lần nữa. 719 00:38:54,460 --> 00:38:56,856 OK, vì vậy ngăn xếp. 720 00:38:56,856 --> 00:39:02,695 Có ai nhớ những gì stacks-- bất kỳ đặc điểm của một chồng? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, vì vậy hầu hết chúng ta, tôi nghĩ rằng, ăn trong ăn uống halls-- 723 00:39:10,400 --> 00:39:13,100 nhiều như chúng tôi có thể không thích. 724 00:39:13,100 --> 00:39:16,900 Nhưng rõ ràng, bạn có thể nghĩ một chồng nghĩa đen chỉ là một chồng khay 725 00:39:16,900 --> 00:39:18,460 hoặc một chồng của sự vật. 726 00:39:18,460 --> 00:39:21,820 Và điều quan trọng để nhận ra là nó 727 00:39:21,820 --> 00:39:26,850 something-- đặc tính mà chúng ta gọi nó là by-- LIFO. 728 00:39:26,850 --> 00:39:28,450 Có ai biết những gì mà là viết tắt của? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Đung cuối cùng trong, đầu tiên ra. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Phải, kéo dài, ra trước. 732 00:39:32,250 --> 00:39:36,585 Vì vậy, nếu chúng ta biết, nếu chúng ta đang xếp thứ lên, điều dễ nhất để lấy off-- 733 00:39:36,585 --> 00:39:39,570 và có lẽ điều duy nhất chúng ta có thể lấy off nếu chồng của chúng tôi là enough-- lớn 734 00:39:39,570 --> 00:39:40,850 là yếu tố hàng đầu. 735 00:39:40,850 --> 00:39:43,460 Vì vậy, bất cứ điều gì đã được đưa vào last-- như chúng ta thấy ở đây, 736 00:39:43,460 --> 00:39:46,370 bất cứ điều gì đã được đẩy trên hầu hết các recently-- là 737 00:39:46,370 --> 00:39:51,160 sẽ là người đầu tiên điều mà chúng tôi bật ra, OK? 738 00:39:51,160 --> 00:39:56,324 >> Vì vậy, những gì chúng tôi có ở đây là một cấu trúc typedef. 739 00:39:56,324 --> 00:39:58,740 Điều này thực sự giống như một sụp đổ khóa học trong cấu trúc dữ liệu, 740 00:39:58,740 --> 00:40:01,650 do đó, có rất nhiều ném vào bạn guys. 741 00:40:01,650 --> 00:40:02,540 Tôi biết. 742 00:40:02,540 --> 00:40:04,970 Vì vậy, thêm một cấu trúc. 743 00:40:04,970 --> 00:40:06,740 Yay cho các cấu trúc. 744 00:40:06,740 --> 00:40:16,660 >> Và trong trường hợp này, đó là một số con trỏ để một mảng có một số năng lực. 745 00:40:16,660 --> 00:40:20,830 Vì vậy, đây đại diện cho chồng của chúng tôi ở đây, giống như mảng thực tế của chúng tôi 746 00:40:20,830 --> 00:40:22,520 đó là tổ chức các yếu tố của chúng tôi. 747 00:40:22,520 --> 00:40:24,850 Và sau đó ở đây chúng tôi có một số kích thước. 748 00:40:24,850 --> 00:40:31,170 >> Và thông thường, bạn muốn giữ lại theo dõi lớn như thế nào ngăn xếp của bạn là 749 00:40:31,170 --> 00:40:36,180 bởi vì những gì nó sẽ cho phép bạn phải làm là nếu bạn biết kích thước, 750 00:40:36,180 --> 00:40:39,170 nó cho phép bạn nói, OK, tôi hết công suất? 751 00:40:39,170 --> 00:40:40,570 Tôi có thể thêm bất cứ điều gì nhiều hơn? 752 00:40:40,570 --> 00:40:44,650 Và nó cũng cho bạn nơi đầu chồng của bạn 753 00:40:44,650 --> 00:40:48,180 là để bạn biết những gì bạn có thể thực sự cất cánh. 754 00:40:48,180 --> 00:40:51,760 Và điều đó thực sự sẽ được rõ ràng hơn một chút ở đây. 755 00:40:51,760 --> 00:40:57,350 >> Vì vậy, để thúc đẩy, có một điều, nếu bạn đã bao giờ thực hiện đẩy, 756 00:40:57,350 --> 00:41:01,330 như tôi đã chỉ nói, của bạn stack có một kích thước giới hạn, phải không? 757 00:41:01,330 --> 00:41:03,990 Mảng của chúng tôi đã có một số năng lực. 758 00:41:03,990 --> 00:41:04,910 Đây là một mảng. 759 00:41:04,910 --> 00:41:08,930 Đó là một kích thước cố định, vì vậy chúng ta cần phải đảm bảo rằng chúng tôi không đưa thêm 760 00:41:08,930 --> 00:41:11,950 vào mảng của chúng ta hơn chúng ta thực sự có không gian cho. 761 00:41:11,950 --> 00:41:16,900 >> Vì vậy, khi bạn đang tạo ra một sự thúc đẩy chức năng, điều đầu tiên bạn làm là nói, OK, 762 00:41:16,900 --> 00:41:18,570 Tôi có không gian trong ngăn xếp của tôi? 763 00:41:18,570 --> 00:41:23,330 Bởi vì nếu tôi không, xin lỗi, Tôi không thể lưu trữ phần tử của bạn. 764 00:41:23,330 --> 00:41:28,980 Nếu tôi làm, sau đó bạn muốn để lưu trữ nó ở trên cùng của ngăn xếp, phải không? 765 00:41:28,980 --> 00:41:31,325 >> Và đây là lý do tại sao chúng tôi có để theo dõi kích thước của chúng tôi. 766 00:41:31,325 --> 00:41:35,290 Nếu chúng ta không theo dõi kích thước của chúng tôi, chúng tôi không biết được nơi để đặt nó. 767 00:41:35,290 --> 00:41:39,035 Chúng tôi không biết bao nhiêu điều là trong mảng của chúng tôi rồi. 768 00:41:39,035 --> 00:41:41,410 Giống như rõ ràng là có nhiều cách rằng có lẽ bạn có thể làm điều đó. 769 00:41:41,410 --> 00:41:44,610 Bạn có thể khởi tạo tất cả mọi thứ để NULL và sau đó kiểm tra cho NULL mới nhất, 770 00:41:44,610 --> 00:41:47,950 nhưng một điều dễ dàng hơn nhiều chỉ là để nói, OK, theo dõi các kích thước. 771 00:41:47,950 --> 00:41:51,840 Giống như tôi biết tôi có bốn yếu tố trong mảng của tôi, do đó, điều tiếp theo 772 00:41:51,840 --> 00:41:55,930 mà chúng tôi đưa vào, chúng tôi đi để lưu trữ tại chỉ số 4. 773 00:41:55,930 --> 00:42:00,940 Và sau đó, tất nhiên, điều này có nghĩa là bạn đã đẩy thành công một cái gì đó 774 00:42:00,940 --> 00:42:03,320 vào ngăn xếp của bạn, bạn muốn tăng kích thước 775 00:42:03,320 --> 00:42:08,880 để bạn biết bạn đang ở đâu vậy mà bạn có thể đẩy mọi thứ thêm về. 776 00:42:08,880 --> 00:42:12,730 >> Vì vậy, nếu chúng tôi đang cố gắng để bật một cái gì đó ra khỏi stack, 777 00:42:12,730 --> 00:42:16,072 những gì có thể là điều đầu tiên mà chúng tôi muốn kiểm tra? 778 00:42:16,072 --> 00:42:18,030 Bạn đang cố gắng để có một cái gì đó ra khỏi ngăn xếp của bạn. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Bạn có chắc chắn có một cái gì đó trong ngăn xếp của bạn? 781 00:42:24,781 --> 00:42:25,280 Không. 782 00:42:25,280 --> 00:42:26,894 Vì vậy, những gì chúng ta có thể muốn kiểm tra? 783 00:42:26,894 --> 00:42:27,810 >> Đung [không nghe được]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Kiểm tra kích thước? 785 00:42:29,880 --> 00:42:31,840 Kích thước. 786 00:42:31,840 --> 00:42:38,520 Vì vậy, chúng tôi muốn kiểm tra xem kích thước của chúng tôi là lớn hơn 0, OK? 787 00:42:38,520 --> 00:42:44,970 Và nếu có, sau đó chúng tôi muốn giảm kích thước của chúng tôi bằng 0 và quay trở lại đó. 788 00:42:44,970 --> 00:42:45,840 Tại sao? 789 00:42:45,840 --> 00:42:49,950 >> Trong giai đoạn đầu chúng tôi đẩy, chúng ta đã đẩy nó 790 00:42:49,950 --> 00:42:52,460 vào kích thước và kích thước sau đó cập nhật. 791 00:42:52,460 --> 00:42:57,850 Trong trường hợp này, chúng tôi đang giảm các kích thước và sau đó dùng nó đi, nó tuốt 792 00:42:57,850 --> 00:42:58,952 từ mảng của chúng tôi. 793 00:42:58,952 --> 00:42:59,826 Tại sao chúng ta có thể làm điều đó? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Vì vậy, nếu tôi có một điều về chồng của tôi, những gì sẽ là kích thước của tôi tại thời điểm đó? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Và đâu là 1 phần tử được lưu trữ? 798 00:43:15,180 --> 00:43:17,621 Tại những gì chỉ số? 799 00:43:17,621 --> 00:43:18,120 Đung 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Vì vậy, trong trường hợp này, chúng tôi luôn luôn cần phải thực hiện sure-- 802 00:43:22,800 --> 00:43:27,630 thay vì trả lại kích thước trừ đi 1, bởi vì chúng tôi 803 00:43:27,630 --> 00:43:31,730 biết rằng yếu tố của chúng tôi là sẽ được lưu trữ ở 1 ít 804 00:43:31,730 --> 00:43:34,705 bất cứ kích thước của chúng tôi là, điều này chỉ chăm sóc của nó. 805 00:43:34,705 --> 00:43:36,080 Đó là một cách hơi thanh lịch hơn. 806 00:43:36,080 --> 00:43:41,220 Và chúng tôi chỉ giảm giá trị của chúng tôi kích thước và sau đó trở về kích thước. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Đung tôi đoán chỉ nói chung, tại sao cấu trúc dữ liệu này 809 00:43:45,300 --> 00:43:47,800 có lợi? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Nó phụ thuộc vào ngữ cảnh của bạn. 811 00:43:50,660 --> 00:43:57,420 Vì vậy, đối với một số lý thuyết, nếu bạn đang làm việc with-- OK, 812 00:43:57,420 --> 00:44:02,750 cho tôi xem nếu có một lợi đó là mang lại lợi ích cho hơn bên ngoài 813 00:44:02,750 --> 00:44:05,420 của CS. 814 00:44:05,420 --> 00:44:15,780 Với ngăn xếp, bất cứ lúc nào bạn cần để theo dõi một cái gì đó 815 00:44:15,780 --> 00:44:20,456 là gần đây nhất được thêm vào là khi bạn sẽ muốn sử dụng một chồng. 816 00:44:20,456 --> 00:44:24,770 >> Và tôi không thể nghĩ ra một tốt ví dụ đó ngay bây giờ. 817 00:44:24,770 --> 00:44:29,955 Nhưng bất cứ khi nào gần đây nhất điều quan trọng nhất đối với bạn, 818 00:44:29,955 --> 00:44:31,705 đó là khi một chồng sẽ là hữu ích. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Tôi đang cố gắng để nghĩ rằng nếu có một tốt nhất cho việc này. 821 00:44:39,330 --> 00:44:43,720 Nếu tôi nghĩ về một ví dụ tốt trong tiếp theo 20 phút, tôi chắc chắn sẽ cho bạn biết. 822 00:44:43,720 --> 00:44:49,455 >> Nhưng nhìn chung, nếu có bất cứ điều gì, như tôi đã nói hầu hết, gần đây, nơi nhất 823 00:44:49,455 --> 00:44:52,470 là quan trọng nhất, đó là nơi một chồng đến chơi. 824 00:44:52,470 --> 00:44:58,860 Trong khi đó, hàng đợi là loại ngược lại. 825 00:44:58,860 --> 00:44:59,870 Và tất cả những con chó nhỏ. 826 00:44:59,870 --> 00:45:00,890 Đó không phải là tuyệt vời, phải không? 827 00:45:00,890 --> 00:45:03,299 Tôi cảm thấy như tôi nên chỉ có một video bunny 828 00:45:03,299 --> 00:45:05,090 ngay ở giữa phần cho các bạn 829 00:45:05,090 --> 00:45:08,870 bởi vì đây là một phần dữ dội. 830 00:45:08,870 --> 00:45:10,480 >> Vì vậy, một hàng đợi. 831 00:45:10,480 --> 00:45:12,710 Về cơ bản một danh sách giống như một dòng. 832 00:45:12,710 --> 00:45:15,780 Các bạn tôi chắc chắn rằng sử dụng hàng ngày này, giống như trong nhà ăn của chúng tôi. 833 00:45:15,780 --> 00:45:18,160 Vì vậy, chúng tôi phải đi ở và nhận được khay của chúng tôi, tôi 834 00:45:18,160 --> 00:45:21,260 chắc chắn bạn phải chờ đợi trong dòng swipe hoặc nhận được thức ăn của bạn. 835 00:45:21,260 --> 00:45:24,650 >> Vì vậy, sự khác biệt ở đây là đây là FIFO. 836 00:45:24,650 --> 00:45:30,090 Vì vậy, nếu LIFO lần cuối trong, đầu tiên ra, FIFO là lần đầu tiên trong, ra đầu tiên. 837 00:45:30,090 --> 00:45:33,400 Vì vậy, đây là nơi mà bất cứ điều gì bạn đặt về đầu tiên là quan trọng nhất của bạn. 838 00:45:33,400 --> 00:45:35,540 Vì vậy, nếu bạn đã chờ đợi trong một line-- có thể bạn 839 00:45:35,540 --> 00:45:39,130 hãy tưởng tượng nếu bạn đã đi đến đi lấy iPhone mới 840 00:45:39,130 --> 00:45:42,800 và đó là một ngăn xếp nơi người cuối cùng trong dòng nhận nó đầu tiên, 841 00:45:42,800 --> 00:45:44,160 mọi người sẽ giết lẫn nhau. 842 00:45:44,160 --> 00:45:49,800 >> Vì vậy, FIFO, chúng tôi tất cả đều rất quen thuộc với trong thế giới thực sự ở đây, 843 00:45:49,800 --> 00:45:54,930 và tất cả đã làm với thực tế loại tái tạo toàn bộ dòng này 844 00:45:54,930 --> 00:45:56,900 xếp hàng và cấu trúc. 845 00:45:56,900 --> 00:46:02,390 Vì vậy, trong khi với chồng, chúng tôi có push và pop. 846 00:46:02,390 --> 00:46:06,440 Với một hàng đợi, chúng tôi có enqueue và dequeue. 847 00:46:06,440 --> 00:46:10,910 Vì vậy, về cơ bản có nghĩa là enqueue đặt nó lên lưng, 848 00:46:10,910 --> 00:46:13,680 và các phương tiện dequeue mất ra từ phía trước. 849 00:46:13,680 --> 00:46:18,680 Vì vậy, cấu trúc dữ liệu của chúng tôi là một một chút phức tạp hơn. 850 00:46:18,680 --> 00:46:21,060 Chúng tôi có một điều thứ hai để theo dõi. 851 00:46:21,060 --> 00:46:25,950 >> Vì vậy, không có người đứng đầu, điều này là chính xác một chồng, phải không? 852 00:46:25,950 --> 00:46:27,900 Đây là cấu trúc giống như một chồng. 853 00:46:27,900 --> 00:46:32,480 Điều duy nhất khác nhau bây giờ là chúng tôi có đầu này, mà làm những gì bạn nghĩ 854 00:46:32,480 --> 00:46:34,272 sẽ theo dõi? 855 00:46:34,272 --> 00:46:35,510 >> Đung Người đầu tiên. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Đúng, các Điều đầu tiên mà chúng tôi đưa vào. 857 00:46:38,685 --> 00:46:41,130 Người đứng đầu hàng đợi của chúng tôi. 858 00:46:41,130 --> 00:46:42,240 Ai là lần đầu tiên trong dòng. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Tất cả các bên phải, vì vậy nếu chúng ta làm enqueue. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Một lần nữa, với bất kỳ các cấu trúc dữ liệu, 863 00:46:55,920 --> 00:46:59,760 kể từ khi chúng tôi đang làm việc với một mảng, chúng ta cần phải kiểm tra xem chúng tôi có không gian. 864 00:46:59,760 --> 00:47:03,290 >> Đây là loại giống như tôi nói các bạn, nếu bạn mở một tập tin, 865 00:47:03,290 --> 00:47:04,760 bạn cần phải kiểm tra null. 866 00:47:04,760 --> 00:47:08,330 Với bất kỳ các ngăn xếp và hàng đợi, bạn cần 867 00:47:08,330 --> 00:47:13,420 để xem nếu có không gian bởi vì chúng tôi đối phó với một mảng kích thước cố định, 868 00:47:13,420 --> 00:47:16,030 như chúng ta thấy here-- 0, 1 tất cả lên đến 5. 869 00:47:16,030 --> 00:47:20,690 Vì vậy, những gì chúng tôi làm trong trường hợp đó là kiểm tra để xem nếu chúng ta vẫn còn có không gian. 870 00:47:20,690 --> 00:47:23,110 Là kích thước của chúng tôi ít hơn năng lực? 871 00:47:23,110 --> 00:47:28,480 >> Nếu vậy, chúng ta cần phải lưu trữ nó ở đuôi và chúng tôi cập nhật kích thước của chúng tôi. 872 00:47:28,480 --> 00:47:30,250 Vì vậy, những gì có thể đuôi được trong trường hợp này? 873 00:47:30,250 --> 00:47:32,360 Nó không phải một cách rõ ràng bằng văn bản ra. 874 00:47:32,360 --> 00:47:33,380 Làm thế nào chúng ta có thể lưu trữ nó? 875 00:47:33,380 --> 00:47:34,928 Điều gì sẽ đuôi được? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Vì vậy, hãy đi bộ qua ví dụ này. 878 00:47:40,190 --> 00:47:44,590 Vì vậy, đây là một mảng có kích thước 6, phải không? 879 00:47:44,590 --> 00:47:49,220 Và chúng tôi có ngay bây giờ, kích thước của chúng tôi là 5. 880 00:47:49,220 --> 00:47:55,240 Và khi chúng ta đặt nó trong, nó sẽ để đi vào chỉ số thứ năm, phải không? 881 00:47:55,240 --> 00:47:57,030 Vì vậy, lưu trữ ở đuôi. 882 00:47:57,030 --> 00:48:05,600 >> Một cách khác để viết đuôi sẽ chỉ là mảng của chúng tôi ở chỉ số kích thước, phải không? 883 00:48:05,600 --> 00:48:07,560 Đây là kích thước 5. 884 00:48:07,560 --> 00:48:11,490 Điều tiếp theo là sẽ đi vào 5. 885 00:48:11,490 --> 00:48:12,296 Mát mẻ? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Nó trở nên phức tạp hơn một chút khi chúng tôi bắt đầu rối tung với người đứng đầu. 888 00:48:16,350 --> 00:48:17,060 Có? 889 00:48:17,060 --> 00:48:20,090 >> Đung Điều đó có nghĩa rằng chúng ta đã có thể tuyên bố một mảng 890 00:48:20,090 --> 00:48:23,880 đã lâu năm yếu tố và sau đó chúng tôi đang thêm vào nó? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: No. 892 00:48:24,730 --> 00:48:27,560 Vì vậy, trong trường hợp này, đây là một chồng. 893 00:48:27,560 --> 00:48:31,760 Điều này sẽ được công bố như một mảng có kích thước 6. 894 00:48:31,760 --> 00:48:37,120 Và trong trường hợp này, chúng tôi chỉ có một không gian trống. 895 00:48:37,120 --> 00:48:42,720 >> OK, vì vậy có một điều trong này trường hợp, nếu người đứng đầu của chúng tôi là ở 0, 896 00:48:42,720 --> 00:48:45,270 sau đó chúng tôi chỉ có thể thêm nó ở kích thước. 897 00:48:45,270 --> 00:48:51,020 Nhưng nó được một chút phức tạp hơn bởi vì trên thực tế, họ 898 00:48:51,020 --> 00:48:52,840 không có một slide cho điều này, vì vậy tôi sẽ 899 00:48:52,840 --> 00:48:56,670 để vẽ một bởi vì nó không khá đơn giản khi bạn 900 00:48:56,670 --> 00:48:59,230 bắt đầu nhận được thoát khỏi điều này. 901 00:48:59,230 --> 00:49:03,920 Vì vậy, trong khi với một chồng bạn chỉ bao giờ có 902 00:49:03,920 --> 00:49:08,920 phải lo lắng về những gì kích thước là khi bạn đang thêm một cái gì đó trên, 903 00:49:08,920 --> 00:49:15,710 với một hàng đợi bạn cũng cần phải thực hiện chắc chắn rằng đầu của bạn được hạch toán, 904 00:49:15,710 --> 00:49:20,760 bởi vì một điều thú vị về hàng đợi là nếu bạn không hết công suất, 905 00:49:20,760 --> 00:49:23,040 bạn thực sự có thể làm cho nó quấn quanh. 906 00:49:23,040 --> 00:49:28,810 >> OK, vì vậy một thing-- oh, này là phấn khủng khiếp. 907 00:49:28,810 --> 00:49:31,815 Một điều cần xem xét là trường hợp. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Chúng tôi sẽ chỉ làm năm. 910 00:49:37,140 --> 00:49:41,810 OK, vì vậy chúng ta sẽ nói người đứng đầu ở đây. 911 00:49:41,810 --> 00:49:46,140 Đây là 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Người đứng đầu là có, và xin vui lòng có những thứ trong đó. 913 00:49:54,210 --> 00:49:58,340 Và chúng tôi muốn thêm một cái gì đó trong, phải không? 914 00:49:58,340 --> 00:50:01,170 Vì vậy, điều mà chúng ta cần biết là người đứng đầu luôn luôn là 915 00:50:01,170 --> 00:50:05,620 sẽ di chuyển theo cách này và sau đó lặp lại xung quanh, OK? 916 00:50:05,620 --> 00:50:10,190 >> Vì vậy, hàng đợi này có không gian, phải không? 917 00:50:10,190 --> 00:50:13,950 Nó có không gian trong đầu, loại đối lập này. 918 00:50:13,950 --> 00:50:17,920 Vì vậy, những gì chúng ta cần làm là chúng tôi cần phải tính toán đuôi. 919 00:50:17,920 --> 00:50:20,530 Nếu bạn biết rằng bạn đầu đã không di chuyển, đuôi 920 00:50:20,530 --> 00:50:24,630 chỉ là mảng của bạn tại chỉ số của kích thước. 921 00:50:24,630 --> 00:50:30,000 >> Nhưng trong thực tế, nếu bạn đang sử dụng một hàng đợi, đầu của bạn có thể được cập nhật. 922 00:50:30,000 --> 00:50:33,890 Vì vậy, những gì bạn cần làm là thực sự tính toán đuôi. 923 00:50:33,890 --> 00:50:39,990 Vì vậy, những gì chúng tôi làm công thức này là ở đây, mà tôi sẽ để cho bạn 924 00:50:39,990 --> 00:50:42,680 kẻ suy nghĩ về, và sau đó chúng ta sẽ nói về nó. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Vì vậy, đây là năng lực. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Vì vậy, đây sẽ thực sự cung cấp cho bạn một cách để làm điều đó. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Bởi vì trong trường hợp này, những gì? 931 00:51:04,330 --> 00:51:09,205 Đầu của chúng tôi là 1, kích thước của chúng tôi là 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Nếu chúng ta mod đó thêm 5, chúng tôi nhận được 0, đó là nơi mà chúng ta nên đầu vào nó. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Vì vậy, sau đó trong trường hợp tiếp theo, nếu chúng ta làm điều này, 936 00:51:26,080 --> 00:51:33,390 chúng ta nói, OK, chúng ta hãy dequeue một cái gì đó. 937 00:51:33,390 --> 00:51:34,390 Chúng tôi dequeue này. 938 00:51:34,390 --> 00:51:37,740 Chúng tôi đưa ra yếu tố này, phải không? 939 00:51:37,740 --> 00:51:47,930 >> Và bây giờ đầu của chúng tôi là chỉ ở đây, và chúng tôi muốn thêm vào một chuyện khác. 940 00:51:47,930 --> 00:51:52,470 Điều này về cơ bản là trở lại của dòng của chúng tôi, phải không? 941 00:51:52,470 --> 00:51:55,450 Hàng đợi có thể quấn xung quanh mảng. 942 00:51:55,450 --> 00:51:57,310 Đó là một trong những khác biệt chính. 943 00:51:57,310 --> 00:51:58,780 Stacks, bạn không thể làm điều này. 944 00:51:58,780 --> 00:52:01,140 >> Với hàng đợi, bạn có thể bởi vì tất cả những vấn đề 945 00:52:01,140 --> 00:52:03,940 là bạn biết những gì gần đây nhất được thêm vào. 946 00:52:03,940 --> 00:52:10,650 Kể từ khi tất cả mọi thứ sẽ được thêm vào trong hướng về phía trái này, trong trường hợp này, 947 00:52:10,650 --> 00:52:16,480 và sau đó quấn xung quanh, bạn có thể tiếp tục đưa vào các yếu tố mới 948 00:52:16,480 --> 00:52:18,830 ở phía trước của mảng bởi vì nó không thực sự 949 00:52:18,830 --> 00:52:20,640 phía trước của mảng nữa. 950 00:52:20,640 --> 00:52:26,320 Bạn có thể nghĩ đầu mảng như là nơi đầu của bạn thực sự là. 951 00:52:26,320 --> 00:52:29,710 >> Vì vậy, công thức này là như thế nào bạn tính toán đuôi của bạn. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Điều đó làm cho tinh thần? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, và sau đó các bạn có 10 phút 957 00:52:44,040 --> 00:52:48,840 hỏi tôi bất kỳ câu hỏi làm rõ bạn muốn, bởi vì tôi biết đó là điên. 958 00:52:48,840 --> 00:52:51,980 >> Tất cả các bên phải, vì vậy trong way-- cùng Tôi không biết nếu các bạn để ý, 959 00:52:51,980 --> 00:52:53,450 nhưng CS là tất cả về mô hình. 960 00:52:53,450 --> 00:52:57,370 Những điều được khá nhiều tương tự, chỉ với vài tinh chỉnh nhỏ. 961 00:52:57,370 --> 00:52:58,950 Vì vậy, cùng một điều ở đây. 962 00:52:58,950 --> 00:53:04,040 Chúng tôi cần phải kiểm tra để xem nếu chúng ta thực sự có một cái gì đó trong hàng đợi của chúng tôi, phải không? 963 00:53:04,040 --> 00:53:05,960 Nói, OK, là kích thước của chúng tôi lớn hơn 0? 964 00:53:05,960 --> 00:53:06,730 Cool. 965 00:53:06,730 --> 00:53:10,690 >> Nếu chúng ta làm, sau đó chúng tôi di chuyển đầu của chúng tôi, là những gì tôi chỉ thể hiện ở đây. 966 00:53:10,690 --> 00:53:13,870 Chúng tôi cập nhật đầu của chúng tôi là một trong hơn. 967 00:53:13,870 --> 00:53:18,390 Và sau đó chúng tôi giảm giá trị của chúng tôi kích thước và quay trở lại phần tử. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Nhiều hơn bê tông có mã trên study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 và tôi rất khuyên bạn nên đi qua nó nếu bạn có thời gian, 971 00:53:29,440 --> 00:53:30,980 thậm chí nếu nó chỉ là một pseudo-code. 972 00:53:30,980 --> 00:53:35,980 Và nếu các bạn muốn nói chuyện qua với tôi, một ngày một, xin vui lòng cho tôi 973 00:53:35,980 --> 00:53:37,500 biết. 974 00:53:37,500 --> 00:53:38,770 Tôi muốn được hạnh phúc để. 975 00:53:38,770 --> 00:53:42,720 Cấu trúc dữ liệu, nếu bạn có CS 124, bạn sẽ 976 00:53:42,720 --> 00:53:47,830 biết rằng cấu trúc dữ liệu nhận được rất niềm vui và điều này chỉ mới bắt đầu. 977 00:53:47,830 --> 00:53:50,350 >> Vì vậy, tôi biết đó là khó khăn. 978 00:53:50,350 --> 00:53:51,300 Đó là OK. 979 00:53:51,300 --> 00:53:52,410 Chúng tôi đấu tranh. 980 00:53:52,410 --> 00:53:53,630 Tôi vẫn làm. 981 00:53:53,630 --> 00:53:56,660 Vì vậy, đừng lo lắng quá nhiều về nó. 982 00:53:56,660 --> 00:54:02,390 >> Nhưng đó là về cơ bản bạn sụp đổ khóa học trong cấu trúc dữ liệu. 983 00:54:02,390 --> 00:54:03,400 Tôi biết nó rất nhiều. 984 00:54:03,400 --> 00:54:06,860 Có điều gì đó chúng tôi muốn đi qua một lần nữa? 985 00:54:06,860 --> 00:54:09,400 Bất cứ điều gì chúng ta muốn nói qua? 986 00:54:09,400 --> 00:54:10,060 Có? 987 00:54:10,060 --> 00:54:16,525 >> Đung Ví dụ đó, vì vậy đuôi mới là 0 trên đó? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Có. 989 00:54:17,150 --> 00:54:18,230 Đung OK. 990 00:54:18,230 --> 00:54:24,220 Vì vậy, sau đó đi qua, bạn muốn có 1 cộng với 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Vì vậy, bạn đã nói, khi chúng ta muốn đi làm điều này một lần nữa? 992 00:54:27,671 --> 00:54:28,296 Đung Yeah. 993 00:54:28,296 --> 00:54:38,290 Vì vậy, nếu bạn đang tìm out-- ở đâu bạn tính toán đuôi từ trong đó? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Vì vậy, đuôi là in-- tôi đã thay đổi này. 995 00:54:44,260 --> 00:54:52,010 Vì vậy, trong ví dụ này ở đây, đây là mảng chúng tôi đang tìm kiếm, OK? 996 00:54:52,010 --> 00:54:54,670 Vì vậy, chúng tôi có điều trong 1, 2, 3 và 4. 997 00:54:54,670 --> 00:55:05,850 Vì vậy, chúng tôi có đầu của chúng tôi là bằng 1 tại thời điểm này, và kích thước của chúng tôi là bằng 4 998 00:55:05,850 --> 00:55:07,050 tại thời điểm này, phải không? 999 00:55:07,050 --> 00:55:08,960 >> Các bạn đồng ý đó là trường hợp? 1000 00:55:08,960 --> 00:55:14,620 Vì vậy, chúng ta làm người đứng đầu cộng với kích thước, mà cho chúng ta 5, và sau đó chúng tôi mod bởi 5. 1001 00:55:14,620 --> 00:55:20,690 Chúng tôi nhận được 0, mà cho chúng ta biết là 0 đâu là đuôi của chúng tôi, nơi chúng tôi có không gian. 1002 00:55:20,690 --> 00:55:22,010 >> Đung một nắp là gì? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: năng lực. 1004 00:55:23,520 --> 00:55:24,020 Xin lỗi. 1005 00:55:24,020 --> 00:55:29,640 Vì vậy, đó là kích thước của mảng của bạn. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Có? 1008 00:55:36,047 --> 00:55:39,210 >> Đung [không nghe được] trước chúng tôi trở lại các yếu tố? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Vì vậy, chúng tôi di chuyển đứng đầu hoặc quay trở lại thời điểm này? 1010 00:55:46,270 --> 00:55:52,680 Vì vậy, nếu chúng ta di chuyển một, giảm các kích thước? 1011 00:55:52,680 --> 00:55:54,150 Giữ trên. 1012 00:55:54,150 --> 00:55:55,770 Tôi chắc chắn quên khác. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Đừng bận tâm. 1015 00:56:01,990 --> 00:56:04,980 Không có một công thức khác. 1016 00:56:04,980 --> 00:56:09,980 Yeah, bạn sẽ muốn quay trở lại người đứng đầu và sau đó di chuyển nó trở lại. 1017 00:56:09,980 --> 00:56:13,270 >> Đung OK, bởi vì Tại đây điểm, người đứng đầu là 0, 1018 00:56:13,270 --> 00:56:18,452 và sau đó bạn muốn quay trở lại chỉ số 0 và sau đó làm cho đầu 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Đúng vậy. 1020 00:56:19,870 --> 00:56:22,820 Tôi nghĩ rằng có một công thức loại như thế này. 1021 00:56:22,820 --> 00:56:26,970 Tôi không có nó ở trên đầu của tôi như Tôi không muốn cung cấp cho bạn một sai lầm. 1022 00:56:26,970 --> 00:56:35,470 Nhưng tôi nghĩ rằng đó là hoàn toàn hợp lệ nói, OK, lưu trữ element-- này bất cứ điều gì 1023 00:56:35,470 --> 00:56:40,759 yếu tố đầu của is-- giảm giá trị của bạn kích thước, di chuyển đầu của bạn hơn, và trở lại 1024 00:56:40,759 --> 00:56:41,800 bất cứ yếu tố đó là. 1025 00:56:41,800 --> 00:56:44,760 Đó là hoàn toàn hợp lệ. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Tôi cảm thấy như thế này không phải là như most-- bạn không 1029 00:56:53,560 --> 00:56:55,740 sẽ đi bộ ra khỏi đây như, có, tôi biết cố gắng. 1030 00:56:55,740 --> 00:56:56,880 Tôi có tất cả. 1031 00:56:56,880 --> 00:56:57,670 Đó là OK. 1032 00:56:57,670 --> 00:57:00,200 Tôi hứa. 1033 00:57:00,200 --> 00:57:05,240 Tuy nhiên, cấu trúc dữ liệu là một cái gì đó phải mất rất nhiều thời gian để làm quen. 1034 00:57:05,240 --> 00:57:10,010 Có lẽ một trong những khó khăn nhất điều, tôi nghĩ rằng, trong khóa học. 1035 00:57:10,010 --> 00:57:15,330 >> Vì vậy, nó chắc chắn có lặp lại và tìm kiếm at-- tôi 1036 00:57:15,330 --> 00:57:20,050 thực sự không biết danh sách liên kết cho đến khi tôi đã làm quá nhiều với họ, 1037 00:57:20,050 --> 00:57:22,550 trong cùng một cách mà tôi đã làm không thực sự hiểu con trỏ 1038 00:57:22,550 --> 00:57:27,040 cho đến khi tôi đã dạy nó cho hai năm và làm psets riêng của tôi với nó. 1039 00:57:27,040 --> 00:57:28,990 Phải mất rất nhiều của sự lặp lại và thời gian. 1040 00:57:28,990 --> 00:57:32,600 Và cuối cùng, nó sẽ loại nhấn chuột. 1041 00:57:32,600 --> 00:57:36,320 >> Nhưng trong khi chờ đợi, nếu bạn có loại một sự hiểu biết cao cấp của những gì 1042 00:57:36,320 --> 00:57:39,321 những làm, ưu của họ cons-- và đó là những gì 1043 00:57:39,321 --> 00:57:41,820 chúng tôi thực sự có xu hướng nhấn mạnh, đặc biệt là trong quá trình giới thiệu. 1044 00:57:41,820 --> 00:57:45,511 Giống như, tại sao chúng ta sẽ sử dụng một thử trên một mảng? 1045 00:57:45,511 --> 00:57:48,010 Giống như, những mặt tích cực là gì và tiêu cực của mỗi người? 1046 00:57:48,010 --> 00:57:51,610 >> Và sự hiểu biết về thương mại-off giữa mỗi của các cấu trúc 1047 00:57:51,610 --> 00:57:54,910 là những gì là quan trọng hơn nhiều ngay bây giờ. 1048 00:57:54,910 --> 00:57:58,140 Có thể có một điên hoặc hai câu hỏi là 1049 00:57:58,140 --> 00:58:03,710 sẽ yêu cầu bạn thực hiện đẩy hoặc thực hiện pop hoặc enqueue và dequeue. 1050 00:58:03,710 --> 00:58:07,340 Nhưng đối với hầu hết các phần, có mà hiểu biết mức độ cao hơn và nhiều hơn nữa 1051 00:58:07,340 --> 00:58:09,710 của một nắm bắt trực quan là quan trọng hơn thực tế 1052 00:58:09,710 --> 00:58:11,250 có khả năng để thực hiện nó. 1053 00:58:11,250 --> 00:58:14,880 >> Nó muốn được thực sự tuyệt vời nếu tất cả các bạn có thể đi ra ngoài và đi thực hiện một thử, 1054 00:58:14,880 --> 00:58:19,720 nhưng chúng tôi hiểu nó không nhất thiết điều hợp lý nhất ngay bây giờ. 1055 00:58:19,720 --> 00:58:23,370 Nhưng bạn có thể trong pset của bạn, nếu bạn muốn đến, và sau đó bạn sẽ nhận được thực tế, 1056 00:58:23,370 --> 00:58:27,200 và sau đó có thể bạn sẽ thấy thực sự hiểu nó. 1057 00:58:27,200 --> 00:58:27,940 Có? 1058 00:58:27,940 --> 00:58:30,440 >> Đung OK, vì vậy mà những người có chúng tôi có nghĩa là để sử dụng trong pset? 1059 00:58:30,440 --> 00:58:31,916 Tôi có cần phải sử dụng một trong số họ? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Có. 1061 00:58:32,540 --> 00:58:34,199 Vì vậy, bạn có sự lựa chọn của bạn. 1062 00:58:34,199 --> 00:58:36,740 Tôi đoán trong trường hợp này, chúng ta có thể nói về pset một chút 1063 00:58:36,740 --> 00:58:40,480 bởi vì tôi chạy qua này. 1064 00:58:40,480 --> 00:58:47,779 Vì vậy, trong pset của bạn, bạn có của bạn lựa chọn hoặc cố gắng bảng băm. 1065 00:58:47,779 --> 00:58:49,570 Một số người sẽ cố gắng và sử dụng bộ lọc nở, 1066 00:58:49,570 --> 00:58:51,840 nhưng những kỹ thuật là không chính xác. 1067 00:58:51,840 --> 00:58:55,804 Bởi vì bản chất xác suất của họ, họ cung cấp cho dương tính giả đôi khi. 1068 00:58:55,804 --> 00:58:57,095 Họ nhìn mát mẻ vào, mặc dù. 1069 00:58:57,095 --> 00:58:59,030 Khuyên bạn nên tìm kiếm tại họ ít nhất. 1070 00:58:59,030 --> 00:59:03,260 Nhưng bạn có sự lựa chọn của bạn giữa một bảng băm và một thử. 1071 00:59:03,260 --> 00:59:06,660 Và đó sẽ là nơi bạn nạp trong từ điển của bạn. 1072 00:59:06,660 --> 00:59:09,230 >> Và bạn sẽ cần phải chọn hàm băm của bạn, 1073 00:59:09,230 --> 00:59:13,420 bạn sẽ cần phải chọn bao nhiêu xô bạn có, và nó sẽ thay đổi. 1074 00:59:13,420 --> 00:59:17,440 Cũng giống như nếu bạn có nhiều xô, có thể nó sẽ chạy nhanh hơn. 1075 00:59:17,440 --> 00:59:22,790 Nhưng có lẽ bạn đang lãng phí một rất nhiều không gian theo cách đó, mặc dù. 1076 00:59:22,790 --> 00:59:26,320 Bạn phải tìm ra nó. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> ĐỐI TƯỢNG: Bạn nói trước đó chúng ta có thể sử dụng hàm băm khác, 1079 00:59:29,875 --> 00:59:31,750 rằng chúng ta không cần phải tạo một hàm băm? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Vâng, đúng. 1081 00:59:32,666 --> 00:59:38,150 Vì vậy, theo nghĩa đen cho hàm băm của bạn, như google "hàm băm" 1082 00:59:38,150 --> 00:59:40,770 và tìm kiếm một số những người mát mẻ. 1083 00:59:40,770 --> 00:59:43,250 Bạn không được dự kiến ​​sẽ xây dựng hàm băm của riêng bạn. 1084 00:59:43,250 --> 00:59:46,100 Mọi người dành của họ luận án về những điều này. 1085 00:59:46,100 --> 00:59:50,250 >> Vì vậy, đừng lo lắng về việc xây dựng của riêng bạn. 1086 00:59:50,250 --> 00:59:53,350 Tìm một trực tuyến để bắt đầu. 1087 00:59:53,350 --> 00:59:56,120 Một số trong số họ, bạn phải thao tác một chút 1088 00:59:56,120 --> 00:59:59,430 để đảm bảo loại trở lại phù hợp và không có điều gì, vì vậy trong đầu, 1089 00:59:59,430 --> 01:00:02,420 Tôi sẽ khuyên bạn nên sử dụng một cái gì đó thực sự dễ dàng mà có thể chỉ 1090 01:00:02,420 --> 01:00:04,680 băm vào chữ cái đầu tiên. 1091 01:00:04,680 --> 01:00:08,760 Và sau đó một khi bạn đã làm việc đó, kết hợp một hàm băm mát. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Đung một sẽ cố gắng được hoặc hiệu quả nhưng chỉ khó, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Vì vậy, một thử, tôi nghĩ rằng, là trực giác khó thực hiện 1095 01:00:15,880 --> 01:00:18,310 nhưng là rất nhanh. 1096 01:00:18,310 --> 01:00:20,620 Tuy nhiên, có nhiều không gian hơn. 1097 01:00:20,620 --> 01:00:25,270 Một lần nữa, bạn có thể tối ưu hóa cả của những người trong cách khác nhau và có những cách đối với: 1098 01:00:25,270 --> 01:00:26,770 ĐỐI TƯỢNG: Làm thế nào chúng ta có phân loại về điều này? 1099 01:00:26,770 --> 01:00:27,540 Liệu nó matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Vì vậy, bạn đang phân loại theo cách thông thường. 1101 01:00:29,164 --> 01:00:31,330 Bạn sẽ được chấm điểm dựa trên thiết kế. 1102 01:00:31,330 --> 01:00:36,020 Tùy theo cách bạn làm, bạn muốn chắc chắn rằng nó là thanh lịch như nó có thể được 1103 01:00:36,020 --> 01:00:38,610 và hiệu quả như nó có thể được. 1104 01:00:38,610 --> 01:00:41,950 Nhưng nếu bạn chọn một thử hoặc băm bảng, miễn là nó hoạt động, 1105 01:00:41,950 --> 01:00:45,350 chúng tôi hạnh phúc với điều đó. 1106 01:00:45,350 --> 01:00:48,370 Và nếu bạn sử dụng một cái gì đó băm trên các chữ cái đầu tiên, đó là tốt, 1107 01:00:48,370 --> 01:00:51,410 như có lẽ giống như thiết kế khôn ngoan. 1108 01:00:51,410 --> 01:00:53,410 Chúng tôi cũng đạt điểm trong semester-- này 1109 01:00:53,410 --> 01:00:55,340 Tôi không biết nếu bạn kẻ noticed-- nếu bạn 1110 01:00:55,340 --> 01:00:58,780 lớp pset giảm một chút vì thiết kế và không có điều gì, 1111 01:00:58,780 --> 01:00:59,900 đó là hoàn toàn tốt đẹp. 1112 01:00:59,900 --> 01:01:02,960 Nó nhận được đến một điểm mà bạn các chương trình đang nhận được phức tạp hơn. 1113 01:01:02,960 --> 01:01:04,830 Có rất nhiều nơi hơn bạn có thể cải thiện. 1114 01:01:04,830 --> 01:01:06,370 >> Vì vậy, nó hoàn toàn bình thường. 1115 01:01:06,370 --> 01:01:08,810 Nó không phải là bạn làm tồi tệ hơn vào pset của bạn. 1116 01:01:08,810 --> 01:01:11,885 Nó chỉ là chúng ta đang bị khó khăn hơn về bạn bây giờ. 1117 01:01:11,885 --> 01:01:13,732 Vì vậy, mọi người cảm thấy nó. 1118 01:01:13,732 --> 01:01:14,940 Tôi chỉ phân loại tất cả các psets của bạn. 1119 01:01:14,940 --> 01:01:16,490 Tôi biết mọi người đang cảm thấy nó. 1120 01:01:16,490 --> 01:01:19,600 >> Vì vậy, không phải lo lắng về điều đó. 1121 01:01:19,600 --> 01:01:23,580 Và nếu bạn có bất kỳ câu hỏi về psets trước hoặc cách bạn có thể cải thiện, 1122 01:01:23,580 --> 01:01:27,760 Tôi cố gắng và bình luận cụ thể nơi, nhưng đôi khi nó là muộn 1123 01:01:27,760 --> 01:01:30,840 và tôi cảm thấy mệt mỏi. 1124 01:01:30,840 --> 01:01:34,885 Có những thứ khác về cấu trúc dữ liệu? 1125 01:01:34,885 --> 01:01:37,510 Tôi chắc rằng các bạn không thực sự muốn nói về họ nữa, 1126 01:01:37,510 --> 01:01:42,650 nhưng nếu có, tôi hạnh phúc đến đi qua họ, cũng như bất cứ điều gì 1127 01:01:42,650 --> 01:01:45,580 từ bài giảng vừa qua tuần hoặc cuối tuần trước. 1128 01:01:45,580 --> 01:01:51,580 >> Tôi biết tuần trước đã xem xét tất cả, vì vậy chúng tôi có thể đã bỏ qua một số xét 1129 01:01:51,580 --> 01:01:54,190 từ bài giảng. 1130 01:01:54,190 --> 01:01:58,230 Bất kỳ câu hỏi khác tôi có thể trả lời? 1131 01:01:58,230 --> 01:01:59,350 OK, được rồi. 1132 01:01:59,350 --> 01:02:02,400 Vâng, các bạn có được ra sớm 15 phút. 1133 01:02:02,400 --> 01:02:08,370 >> Tôi hy vọng điều này là bán hữu ích ít nhất, và tôi sẽ gặp các bạn vào tuần tới, 1134 01:02:08,370 --> 01:02:12,150 hoặc thứ năm giờ hành chính. 1135 01:02:12,150 --> 01:02:15,285 Có những yêu cầu cho bữa ăn nhẹ cho tuần tới, đó là điều? 1136 01:02:15,285 --> 01:02:17,459 Bởi vì tôi quên kẹo ngày hôm nay. 1137 01:02:17,459 --> 01:02:19,750 Và tôi đã mang kẹo cuối cùng tuần, nhưng nó đã Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 như vậy có giống như sáu người có bốn túi kẹo cho bản thân. 1139 01:02:25,400 --> 01:02:28,820 Tôi có thể mang lại Starbursts một lần nữa nếu bạn muốn. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, âm thanh tốt. 1142 01:02:32,250 --> 01:02:35,050 Có một ngày tuyệt vời, guys. 1143 01:02:35,050 --> 01:02:39,510