1 00:00:00,000 --> 00:00:02,832 >> [Bermain muzik] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, jadi sekurang- ketika ini dalam perjalanan, 4 00:00:08,560 --> 00:00:15,300 kami telah meliputi banyak asas-asas C. Kami tahu banyak tentang pembolehubah, tatasusunan, 5 00:00:15,300 --> 00:00:17,610 petunjuk, semua barangan yang baik. 6 00:00:17,610 --> 00:00:21,610 Mereka semua jenis dibina untuk melihat sebagai asas-asas, 7 00:00:21,610 --> 00:00:23,880 tetapi kita boleh melakukan lebih banyak, bukan? 8 00:00:23,880 --> 00:00:27,930 Kita boleh menggabungkan perkara-perkara bersama-sama dengan cara yang menarik. 9 00:00:27,930 --> 00:00:31,010 >> Dan begitu mari kita buat itu, mari kita mulakan berkembang daripada apa yang C memberikan kita, 10 00:00:31,010 --> 00:00:35,270 dan mula membuat data kita sendiri struktur menggunakan bangunan ini 11 00:00:35,270 --> 00:00:40,590 blok bersama-sama untuk melakukan sesuatu benar-benar berharga, berguna. 12 00:00:40,590 --> 00:00:43,420 Salah satu cara yang boleh kita lakukan ini adalah untuk bercakap tentang koleksi. 13 00:00:43,420 --> 00:00:48,360 Jadi setakat ini kita mempunyai satu jenis data struktur bagi mewakili koleksi 14 00:00:48,360 --> 00:00:51,030 daripada suka nilai, nilai-nilai yang sama. 15 00:00:51,030 --> 00:00:52,350 Itu akan menjadi array. 16 00:00:52,350 --> 00:00:57,020 Kami mempunyai koleksi integer, atau koleksi watak-watak dan sebagainya. 17 00:00:57,020 --> 00:01:00,890 >> Struktur juga menyusun data yang struktur bagi mengumpul maklumat, 18 00:01:00,890 --> 00:01:03,220 tetapi ia bukan untuk mengumpul seperti nilai-nilai. 19 00:01:03,220 --> 00:01:08,090 Ia biasanya menggabungkan data berlainan jenis bersama-sama di dalam kotak tunggal. 20 00:01:08,090 --> 00:01:10,750 Tetapi ia tidak sendiri digunakan untuk rantaian bersama-sama 21 00:01:10,750 --> 00:01:16,920 atau menyambung bersama-sama sama barang-barang, seperti array. 22 00:01:16,920 --> 00:01:20,960 Array yang besar untuk elemen mencari, tetapi ingat 23 00:01:20,960 --> 00:01:24,262 bahawa itu sangat sukar untuk memasukkan ke dalam array, 24 00:01:24,262 --> 00:01:26,470 melainkan jika kita memasukkan di akhir sangat array itu. 25 00:01:26,470 --> 00:01:29,730 >> Dan contoh terbaik saya kerana itu adalah jenis kemasukan. 26 00:01:29,730 --> 00:01:31,650 Jika anda masih ingat video kami pada jenis kemasukan, 27 00:01:31,650 --> 00:01:34,110 terdapat banyak perbelanjaan yang terlibat dalam mempunyai 28 00:01:34,110 --> 00:01:37,970 untuk mengambil elemen, dan memindahkan mereka keluar dari jalan untuk memenuhi sesuatu 29 00:01:37,970 --> 00:01:41,290 ke tengah-tengah lokasi anda. 30 00:01:41,290 --> 00:01:44,690 Tatasusunan juga mengalami satu lagi masalah, yang tidak fleksibel. 31 00:01:44,690 --> 00:01:47,150 Apabila kita mengisytiharkan array, kita akan mendapat satu pukulan di dalamnya. 32 00:01:47,150 --> 00:01:49,790 Kita dapat mengatakan, saya mahu ini banyak unsur. 33 00:01:49,790 --> 00:01:51,940 Mungkin 100, ia mungkin menjadi 1,000, ia mungkin 34 00:01:51,940 --> 00:01:55,930 menjadi x di mana x ialah nombor yang pengguna memberikan kita pada cepat atau sekurang-arahan 35 00:01:55,930 --> 00:01:56,630 garis. 36 00:01:56,630 --> 00:01:59,905 >> Tetapi kita hanya mendapat satu pukulan pada itu, kita tidak mendapat untuk kemudian berkata oh, sebenarnya saya 37 00:01:59,905 --> 00:02:04,360 diperlukan 101, atau saya perlu x campur 20. 38 00:02:04,360 --> 00:02:07,910 Terlambat, kita sudah mengisytiharkan pelbagai, dan jika kita ingin mendapatkan 101 atau x 39 00:02:07,910 --> 00:02:12,050 ditambah 20, kita perlu mengisytiharkan pelbagai sekali berbeza, 40 00:02:12,050 --> 00:02:15,540 menyalin semua elemen array lebih, dan kemudian kita mempunyai cukup. 41 00:02:15,540 --> 00:02:19,880 Dan bagaimana jika kita silap lagi, apa jika kita benar-benar perlu 102, atau x campur 40, 42 00:02:19,880 --> 00:02:21,970 yang perlu kita lakukan ini sekali lagi. 43 00:02:21,970 --> 00:02:26,250 Jadi mereka sangat fleksibel untuk saiz semula data kami, 44 00:02:26,250 --> 00:02:29,360 tetapi jika kita menggabungkan bersama-sama beberapa perkara asas yang kita ada sudah 45 00:02:29,360 --> 00:02:33,230 belajar tentang petunjuk dan struktur, khususnya menggunakan memori dinamik 46 00:02:33,230 --> 00:02:36,180 peruntukan dengan malloc, kita boleh meletakkan keping ini bersama-sama 47 00:02:36,180 --> 00:02:40,960 untuk mewujudkan data baru structure-- yang senarai kita mungkin iaitu- secara tunggal dikaitkan 48 00:02:40,960 --> 00:02:45,400 yang membolehkan kita untuk berkembang dan mengecut koleksi nilai 49 00:02:45,400 --> 00:02:48,800 dan kami tidak akan mempunyai ruang sia-sia. 50 00:02:48,800 --> 00:02:53,320 >> Jadi sekali lagi, kita panggil idea ini, idea ini, senarai berpaut. 51 00:02:53,320 --> 00:02:56,320 Khususnya, dalam video ini kami bercakap tentang senarai secara tunggal berkaitan, 52 00:02:56,320 --> 00:02:59,185 dan kemudian video lain kita akan bercakap senarai kira-kira dua kali ganda berkaitan, yang 53 00:02:59,185 --> 00:03:01,560 hanya variasi pada tema di sini. 54 00:03:01,560 --> 00:03:05,200 Tetapi senarai yang dikaitkan secara tunggal terdiri daripada nod, 55 00:03:05,200 --> 00:03:08,559 nod hanya menjadi satu term-- abstrak ia hanya sesuatu yang saya memanggil 56 00:03:08,559 --> 00:03:10,350 itu adalah satu jenis struktur, pada dasarnya, saya? 57 00:03:10,350 --> 00:03:16,190 Hanya akan memanggilnya node-- dan ini nod mempunyai dua ahli, atau dua bidang. 58 00:03:16,190 --> 00:03:20,300 Ia mempunyai data, biasanya integer, apungan watak, 59 00:03:20,300 --> 00:03:23,790 atau boleh menjadi beberapa jenis data lain yang anda telah ditakrifkan dengan def jenis. 60 00:03:23,790 --> 00:03:29,290 Dan ia mengandungi penunjuk kepada lain nod dari jenis yang sama. 61 00:03:29,290 --> 00:03:34,710 >> Jadi kita mempunyai dua perkara di dalam nod ini, data dan penunjuk 62 00:03:34,710 --> 00:03:36,380 kepada nod yang lain. 63 00:03:36,380 --> 00:03:39,370 Dan jika anda mula untuk menggambarkan ini, anda boleh berfikir tentang hal itu 64 00:03:39,370 --> 00:03:42,280 seperti rangkaian nod yang disambung bersama. 65 00:03:42,280 --> 00:03:45,070 Kami mempunyai nod yang pertama, ia mengandungi data dan penunjuk 66 00:03:45,070 --> 00:03:49,110 kepada nod yang kedua, yang mengandungi data dan penunjuk kepada nod ketiga. 67 00:03:49,110 --> 00:03:52,940 Dan supaya sebabnya kita memanggilnya senarai berpaut, mereka dikaitkan bersama-sama. 68 00:03:52,940 --> 00:03:56,070 >> Apakah yang istimewa ini struktur nod kelihatan seperti? 69 00:03:56,070 --> 00:04:01,120 Nah, jika anda ingat dari video kami di menentukan jenis adat, dengan jenis def, 70 00:04:01,120 --> 00:04:05,400 kita boleh menentukan structure-- dan menaip menentukan struktur yang seperti ini. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, dan kemudian saya menggunakan nilai perkataan di sini sewenang-wenangnya 72 00:04:11,240 --> 00:04:13,891 untuk menunjukkan apa-apa jenis data benar-benar. 73 00:04:13,891 --> 00:04:16,890 Anda boleh memindahkan integer atau terapung, anda boleh mempunyai apa sahaja yang anda mahu. 74 00:04:16,890 --> 00:04:19,389 Ia tidak terhad kepada hanya integer, atau apa-apa seperti itu. 75 00:04:19,389 --> 00:04:22,790 Jadi nilai hanya sewenang-wenangnya jenis data, dan kemudian penunjuk 76 00:04:22,790 --> 00:04:26,310 yang lain nod dari jenis yang sama. 77 00:04:26,310 --> 00:04:29,690 >> Sekarang, ada muslihat sedikit di sini dengan menentukan struktur yang 78 00:04:29,690 --> 00:04:33,030 apabila ia adalah satu struktur rujukan diri. 79 00:04:33,030 --> 00:04:35,340 Saya perlu mempunyai sementara menamakan struktur saya. 80 00:04:35,340 --> 00:04:37,640 Pada akhir hari, saya yang jelas mahu memanggilnya 81 00:04:37,640 --> 00:04:43,030 nod SLL, itu akhirnya baru menamakan sebahagian daripada definisi jenis saya, 82 00:04:43,030 --> 00:04:47,450 tetapi saya tidak boleh menggunakan nod SLL di pertengahan ini. 83 00:04:47,450 --> 00:04:51,430 Sebabnya, saya tidak mempunyai mencipta satu jenis dipanggil nod SLL 84 00:04:51,430 --> 00:04:55,200 sehingga saya memukul titik akhir ini di sini. 85 00:04:55,200 --> 00:04:59,720 Sehingga ketika itu, saya perlu mempunyai cara lain untuk merujuk kepada jenis data ini. 86 00:04:59,720 --> 00:05:02,440 >> Dan ini adalah diri yang jenis data rujukan. 87 00:05:02,440 --> 00:05:06,314 Ia; s jenis data daripada struktur yang mengandungi data, 88 00:05:06,314 --> 00:05:08,480 dan penunjuk yang lain struktur jenis yang sama. 89 00:05:08,480 --> 00:05:11,750 Jadi saya perlu berupaya untuk merujuk kepada jenis data ini sekurang-kurangnya buat sementara waktu, 90 00:05:11,750 --> 00:05:14,910 supaya memberikan sementara nama struct sllist 91 00:05:14,910 --> 00:05:18,540 membolehkan saya untuk kemudian mengatakan saya mahu penunjuk yang lain sllist struct, 92 00:05:18,540 --> 00:05:24,690 bintang struct sllist, dan kemudian selepas saya telah menyelesaikan definisi, 93 00:05:24,690 --> 00:05:27,220 Sekarang saya boleh memanggil jenis nod SLL. 94 00:05:27,220 --> 00:05:30,520 >> Jadi itulah sebabnya anda melihat ada nama sementara di sini, 95 00:05:30,520 --> 00:05:31,879 tetapi nama tetap di sini. 96 00:05:31,879 --> 00:05:33,920 Kadang-kadang anda mungkin melihat definisi struktur, 97 00:05:33,920 --> 00:05:36,570 sebagai contoh, yang tidak rujukan sendiri, yang 98 00:05:36,570 --> 00:05:39,390 tidak mempunyai nama specifier sini. 99 00:05:39,390 --> 00:05:43,040 Ia hanya akan berkata typedef struct, membuka kerinting dan kemudian menentukan ia. 100 00:05:43,040 --> 00:05:45,620 Tetapi jika anda struct adalah diri rujukan, yang satu ini adalah, 101 00:05:45,620 --> 00:05:49,010 anda perlu untuk menentukan nama jenis sementara. 102 00:05:49,010 --> 00:05:51,310 Tetapi akhirnya, sekarang bahawa kita telah melakukan ini, 103 00:05:51,310 --> 00:05:53,620 kita hanya boleh merujuk kepada nod ini, unit-unit ini, 104 00:05:53,620 --> 00:05:57,900 sebagai nod SLL untuk tujuan negara lain di video ini. 105 00:05:57,900 --> 00:06:00,900 >> Baiklah, jadi kita tahu bagaimana untuk mewujudkan nod senarai berkaitan. 106 00:06:00,900 --> 00:06:03,240 Kita tahu bagaimana untuk menentukan nod senarai berkaitan. 107 00:06:03,240 --> 00:06:06,670 Sekarang, jika kita akan mula menggunakan mereka untuk mengumpul maklumat, 108 00:06:06,670 --> 00:06:10,360 ada beberapa operasi kami perlu memahami dan bekerja dengan. 109 00:06:10,360 --> 00:06:12,860 Kita perlu tahu bagaimana untuk membuat senarai berpaut dari udara tipis. 110 00:06:12,860 --> 00:06:14,901 Jika tiada senarai sudah, kita mahu memulakan satu. 111 00:06:14,901 --> 00:06:16,960 Oleh itu, kita perlu berupaya untuk membuat senarai berpaut, 112 00:06:16,960 --> 00:06:19,130 kita perlu mungkin mencari melalui senarai link 113 00:06:19,130 --> 00:06:21,830 untuk mencari elemen yang kami cari. 114 00:06:21,830 --> 00:06:24,430 Kita perlu dapat memasukkan perkara-perkara baru ke dalam senarai, 115 00:06:24,430 --> 00:06:25,930 kita mahu senarai kami dapat berkembang. 116 00:06:25,930 --> 00:06:28,638 Begitu juga, kita mahu dapat untuk memadam perkara dari senarai kami, 117 00:06:28,638 --> 00:06:30,250 kita mahu senarai kami dapat mengecut. 118 00:06:30,250 --> 00:06:32,160 Dan pada akhir kami program, terutamanya 119 00:06:32,160 --> 00:06:34,550 jika anda masih ingat bahawa kita dinamik memperuntukkan memori 120 00:06:34,550 --> 00:06:38,337 untuk membina senarai ini biasanya, kita mahu membebaskan kesemua memori yang 121 00:06:38,337 --> 00:06:39,670 apabila kami sudah selesai bekerja dengannya. 122 00:06:39,670 --> 00:06:44,627 Dan dengan itu kita perlu berupaya untuk memadam senarai keseluruhan dikaitkan dalam satu kali kejadian gagal. 123 00:06:44,627 --> 00:06:46,460 Jadi mari kita pergi melalui beberapa operasi ini 124 00:06:46,460 --> 00:06:51,192 dan bagaimana kita boleh menggambarkan mereka, bercakap kod pseudo secara khusus. 125 00:06:51,192 --> 00:06:53,150 Oleh itu, kita ingin membuat senarai bersambung, jadi mungkin kita 126 00:06:53,150 --> 00:06:56,480 hendak menentukan fungsi dengan prototaip ini. 127 00:06:56,480 --> 00:07:01,690 SLL nod bintang, buat dan saya lulus dalam satu hujah, beberapa data yang sewenang-wenangnya 128 00:07:01,690 --> 00:07:05,530 menaip lagi, beberapa sewenang-wenangnya jenis data. 129 00:07:05,530 --> 00:07:10,482 Tetapi saya returning-- fungsi ini perlu kembali kepadaku penunjuk, kepada secara tunggal 130 00:07:10,482 --> 00:07:11,190 dikaitkan nod senarai. 131 00:07:11,190 --> 00:07:14,050 Sekali lagi, kita cuba untuk mewujudkan senarai berpaut dari udara tipis, 132 00:07:14,050 --> 00:07:17,900 jadi saya perlu penunjuk kepada senarai itu apabila aku selesai. 133 00:07:17,900 --> 00:07:19,420 >> Jadi apakah langkah-langkah yang terlibat di sini? 134 00:07:19,420 --> 00:07:20,960 Nah, perkara pertama saya akan lakukan adalah dinamik 135 00:07:20,960 --> 00:07:22,550 memperuntukkan ruang untuk nod baru. 136 00:07:22,550 --> 00:07:26,689 Sekali lagi, kami mewujudkan ia keluar dari nipis udara, jadi kita perlu ruang malloc untuk itu. 137 00:07:26,689 --> 00:07:28,480 Dan sudah tentu, dengan serta-merta selepas kami malloc, 138 00:07:28,480 --> 00:07:31,692 kita sentiasa periksa untuk memastikan bahawa kami pointer-- kita tidak kembali null. 139 00:07:31,692 --> 00:07:33,650 Kerana jika kita cuba rasa hormat penunjuk null, 140 00:07:33,650 --> 00:07:36,190 kita akan mengalami segfault dan kita tidak mahu itu. 141 00:07:36,190 --> 00:07:39,510 >> Kemudian kita mahu mengisi dalam bidang ini, kita mahu memulakan bidang nilai 142 00:07:39,510 --> 00:07:41,690 dan memulakan medan seterusnya. 143 00:07:41,690 --> 00:07:45,450 Dan kemudian kita mahu supaya- akhirnya sebagai fungsi prototaip indicates-- kita mahu 144 00:07:45,450 --> 00:07:49,940 untuk kembali penunjuk kepada nod SLL. 145 00:07:49,940 --> 00:07:51,710 Jadi apa yang membuat ini kelihatan seperti cacat? 146 00:07:51,710 --> 00:07:55,230 Well, pertama kita akan secara dinamik memperuntukkan ruang untuk nod SLL baru, 147 00:07:55,230 --> 00:07:58,320 jadi kami malloc-- itulah representasi visual 148 00:07:58,320 --> 00:08:00,020 nod yang kita buat. 149 00:08:00,020 --> 00:08:02,757 Dan kita periksa untuk memastikan ia tidak null-- dalam kes ini, 150 00:08:02,757 --> 00:08:04,840 gambar tidak akan mempunyai ditunjukkan jika ia adalah tidak sah, 151 00:08:04,840 --> 00:08:07,298 kita akan kehabisan memori, supaya kita baik untuk pergi ke sana. 152 00:08:07,298 --> 00:08:10,200 Jadi sekarang kita ke langkah C, memulakan bidang nilai nod. 153 00:08:10,200 --> 00:08:12,280 Nah, berdasarkan fungsi ini memanggil saya menggunakan di sini, 154 00:08:12,280 --> 00:08:16,700 kelihatan seperti saya mahu lulus di 6, jadi saya akan 6 dalam bidang nilai. 155 00:08:16,700 --> 00:08:18,865 Sekarang, memulakan medan seterusnya. 156 00:08:18,865 --> 00:08:21,640 Nah, apa yang saya akan lakukan di sana, tiada apa yang akan datang, betul, 157 00:08:21,640 --> 00:08:23,600 ini adalah satu-satunya perkara dalam senarai. 158 00:08:23,600 --> 00:08:27,206 Jadi apa perkara yang akan datang dalam senarai? 159 00:08:27,206 --> 00:08:29,660 >> Ia tidak seharusnya menunjukkan apa-apa, betul. 160 00:08:29,660 --> 00:08:33,600 Ada apa-apa lagi di sana, jadi apa yang konsep yang kita tahu itulah nothing-- 161 00:08:33,600 --> 00:08:35,638 petunjuk untuk apa-apa? 162 00:08:35,638 --> 00:08:37,929 Ia harus menjadi mungkin kita mahu untuk meletakkan penunjuk null sana, 163 00:08:37,929 --> 00:08:40,178 dan saya akan mewakili null penunjuk sebagai hanya sebuah kotak merah, 164 00:08:40,178 --> 00:08:41,559 kita tidak boleh pergi mana-mana lagi. 165 00:08:41,559 --> 00:08:44,430 Seperti yang kita akan melihat sedikit di kemudian hari, kita akan mempunyai akhirnya rantaian 166 00:08:44,430 --> 00:08:46,330 anak panah yang menghubungkan nod ini bersama-sama, 167 00:08:46,330 --> 00:08:48,480 tetapi apabila anda melanda kotak merah, itu batal, 168 00:08:48,480 --> 00:08:51,150 kita tidak boleh pergi mana-mana lagi, itulah akhir senarai. 169 00:08:51,150 --> 00:08:53,960 >> Dan akhir sekali, kami hanya mahu kembali penunjuk kepada nod ini. 170 00:08:53,960 --> 00:08:56,160 Oleh itu, kita akan memanggilnya baru, dan akan kembali baru 171 00:08:56,160 --> 00:08:59,370 supaya ia boleh digunakan dalam apa fungsi menciptakannya. 172 00:08:59,370 --> 00:09:03,100 Jadi ada kita pergi, Kami telah mencipta satu secara tunggal dikaitkan nod senarai dari udara tipis, 173 00:09:03,100 --> 00:09:05,920 dan sekarang kita mempunyai senarai yang kami boleh bekerja dengan. 174 00:09:05,920 --> 00:09:08,260 >> Sekarang, mari kita mengatakan bahawa kita sudah mempunyai rangkaian yang besar, 175 00:09:08,260 --> 00:09:09,800 dan kami ingin mencari sesuatu di dalamnya. 176 00:09:09,800 --> 00:09:12,716 Dan kita mahu satu fungsi yang akan untuk kembali benar atau salah, bergantung 177 00:09:12,716 --> 00:09:15,840 sama ada nilai yang wujud dalam senarai itu. 178 00:09:15,840 --> 00:09:18,160 Satu prototaip fungsi, atau penerangan bagi fungsi itu, 179 00:09:18,160 --> 00:09:23,320 mungkin kelihatan seperti this-- bool mencari, dan maka kita mahu lulus dalam dua hujah. 180 00:09:23,320 --> 00:09:26,996 >> Yang pertama, adalah penunjuk kepada Elemen pertama dalam senarai yang dipautkan. 181 00:09:26,996 --> 00:09:29,620 Ini sebenarnya adalah sesuatu yang anda akan sentiasa mahu untuk mengesan, 182 00:09:29,620 --> 00:09:33,110 dan sebenarnya mungkin menjadi sesuatu yang anda juga dimasukkan ke dalam pembolehubah global. 183 00:09:33,110 --> 00:09:35,360 Sebaik sahaja anda membuat senarai, anda sentiasa, sentiasa 184 00:09:35,360 --> 00:09:38,990 mahu untuk mengesan yang Elemen pertama dalam senarai itu. 185 00:09:38,990 --> 00:09:43,690 Dengan cara itu anda boleh merujuk kepada semua yang lain unsur-unsur dengan hanya mengikuti rantai, 186 00:09:43,690 --> 00:09:47,300 tanpa perlu menyimpan petunjuk utuh kepada setiap elemen tunggal. 187 00:09:47,300 --> 00:09:50,920 Anda hanya perlu untuk mengesan satu yang pertama satu jika mereka semua dirantai bersama-sama. 188 00:09:50,920 --> 00:09:52,460 >> Kemudian perkara yang kedua kita lulus dalam lagi 189 00:09:52,460 --> 00:09:54,376 adalah sewenang-wenangnya some-- apa sahaja jenis data kami 190 00:09:54,376 --> 00:09:59,640 cari ada di dalam mudah-mudahan salah satu daripada nod dalam senarai. 191 00:09:59,640 --> 00:10:00,980 Jadi apakah langkah-langkah? 192 00:10:00,980 --> 00:10:04,250 Nah, perkara pertama yang kami lakukan adalah kita mewujudkan penunjuk melintang 193 00:10:04,250 --> 00:10:06,015 menunjuk ke kepala menyenaraikan. 194 00:10:06,015 --> 00:10:08,890 Nah, mengapa kita berbuat demikian, kita sudah mempunyai penunjuk di kepala menyenaraikan, 195 00:10:08,890 --> 00:10:10,974 mengapa tidak kita hanya bergerak satu yang di sekeliling? 196 00:10:10,974 --> 00:10:13,140 Well, seperti saya hanya berkata, ia benar-benar penting untuk kita 197 00:10:13,140 --> 00:10:17,580 untuk sentiasa mengesan elemen yang pertama dalam senarai. 198 00:10:17,580 --> 00:10:21,270 Dan supaya ia sebenarnya lebih baik untuk membuat pendua itu, 199 00:10:21,270 --> 00:10:25,350 dan menggunakannya untuk bergerak jadi kami tidak pernah sengaja bergerak, atau kita sentiasa 200 00:10:25,350 --> 00:10:30,430 mempunyai penunjuk pada satu ketika yang kanan pada elemen pertama dalam senarai itu. 201 00:10:30,430 --> 00:10:33,290 Jadi ia adalah lebih baik untuk mewujudkan satu saat yang kita gunakan untuk bergerak. 202 00:10:33,290 --> 00:10:35,877 >> Maka kita hanya membandingkan sama ada bidang nilai pada nod yang 203 00:10:35,877 --> 00:10:38,960 adalah apa yang kita cari, dan jika ia tidak, kita hanya bergerak ke nod seterusnya. 204 00:10:38,960 --> 00:10:41,040 Dan kita terus melakukan itu ke atas, dan ke atas, dan ke atas, 205 00:10:41,040 --> 00:10:44,811 sehingga kita sama ada mencari unsur, atau kita mencapai 206 00:10:44,811 --> 00:10:47,310 null-- kami telah mencapai akhir senarai dan ia tidak ada. 207 00:10:47,310 --> 00:10:50,540 Ini diharapkan dapat berdering loceng kepada anda sebagai hanya carian linear, 208 00:10:50,540 --> 00:10:54,430 kami hanya mereplikasi dalam struktur senarai secara tunggal dikaitkan 209 00:10:54,430 --> 00:10:56,280 bukannya menggunakan array untuk melakukannya. 210 00:10:56,280 --> 00:10:58,210 >> Jadi di sini adalah satu contoh senarai secara tunggal berkaitan. 211 00:10:58,210 --> 00:11:00,043 Yang ini terdiri daripada lima nod, dan kami mempunyai 212 00:11:00,043 --> 00:11:04,330 penunjuk kepada ketua senarai, yang dipanggil senarai. 213 00:11:04,330 --> 00:11:07,385 Perkara pertama yang kita mahu lakukan adalah lagi, buat bahawa penunjuk penyusuran. 214 00:11:07,385 --> 00:11:09,760 Oleh itu, kita kini mempunyai dua petunjuk ketika itu kepada perkara yang sama. 215 00:11:09,760 --> 00:11:15,025 >> Sekarang, perhatikan di sini juga, saya tidak perlu malloc mana-mana ruang untuk trav. 216 00:11:15,025 --> 00:11:18,970 Saya tidak mengatakan trav sama malloc sesuatu, nod tersebut telah ada 217 00:11:18,970 --> 00:11:21,160 ruang yang di dalam memori telah wujud. 218 00:11:21,160 --> 00:11:24,290 Jadi semua Saya sebenarnya lakukan adalah mewujudkan satu lagi penunjuk kepadanya. 219 00:11:24,290 --> 00:11:28,210 Saya tidak mallocing tambahan ruang, hanya ada sekarang dua petunjuk 220 00:11:28,210 --> 00:11:31,370 menunjuk kepada perkara yang sama. 221 00:11:31,370 --> 00:11:33,710 >> Jadi adalah 2 apa yang saya cari? 222 00:11:33,710 --> 00:11:37,220 Well, tidak, jadi bukannya Saya akan bergerak ke satu depan. 223 00:11:37,220 --> 00:11:41,740 Jadi, pada asasnya saya akan berkata, trav sama trav depan. 224 00:11:41,740 --> 00:11:43,630 Adalah 3 apa yang saya cari, tidak. 225 00:11:43,630 --> 00:11:45,780 Jadi saya terus pergi melalui, sehingga akhirnya 226 00:11:45,780 --> 00:11:48,690 mendapatkan hingga 6 yang merupakan apa yang saya cari berasaskan kepada panggilan fungsi 227 00:11:48,690 --> 00:11:51,600 Saya mempunyai di bahagian atas di sana, dan supaya aku selesai. 228 00:11:51,600 --> 00:11:54,150 >> Sekarang, bagaimana jika unsur Saya cari tidak dalam senarai, 229 00:11:54,150 --> 00:11:55,510 ia masih akan bekerja? 230 00:11:55,510 --> 00:11:57,120 Nah, perhatikan bahawa senarai di sini adalah secara halus berbeza, 231 00:11:57,120 --> 00:11:59,410 dan ini adalah satu lagi perkara itu penting dengan senarai berkaitan, 232 00:11:59,410 --> 00:12:01,780 anda tidak perlu untuk memelihara mereka dalam mana-mana perintah tertentu. 233 00:12:01,780 --> 00:12:05,390 Anda boleh jika anda mahu, tetapi anda mungkin perasan 234 00:12:05,390 --> 00:12:09,310 bahawa kita tidak mengesan apa elemen nombor kita berada di. 235 00:12:09,310 --> 00:12:13,150 >> Dan itu semacam satu perdagangan yang kita mempunyai dengan senarai dikaitkan ayat tatasusunan, 236 00:12:13,150 --> 00:12:15,300 adakah ia kita tidak mempunyai capaian rawak lagi. 237 00:12:15,300 --> 00:12:18,150 Kita tidak boleh hanya berkata, saya mahu untuk pergi ke unsur 0, 238 00:12:18,150 --> 00:12:21,410 atau unsur ke-6 daripada pelbagai saya, yang boleh saya lakukan dalam array. 239 00:12:21,410 --> 00:12:25,080 Saya tidak boleh mengatakan saya mahu pergi ke Unsur 0, atau unsur ke-6, 240 00:12:25,080 --> 00:12:30,360 atau unsur ke-25 senarai dikaitkan saya, tidak ada indeks yang berkaitan dengan mereka. 241 00:12:30,360 --> 00:12:33,660 Dan supaya ia tidak benar-benar perkara jika kita memelihara senarai kami teratur. 242 00:12:33,660 --> 00:12:36,080 Jika anda mahu anda pasti boleh, tetapi ada 243 00:12:36,080 --> 00:12:38,567 ada sebab mengapa mereka perlu dikekalkan dalam mana-mana perintah. 244 00:12:38,567 --> 00:12:40,400 Jadi sekali lagi, mari kita cuba dan mencari 6 dalam senarai ini. 245 00:12:40,400 --> 00:12:43,200 Nah, kita bermula pada bermula, kita tidak mencari 6, 246 00:12:43,200 --> 00:12:47,690 dan kemudian kita terus tidak mencari 6, sehingga kita akhirnya sampai ke sini. 247 00:12:47,690 --> 00:12:52,790 Jadi betul mata sekarang trav kepada nod mengandungi 8, dan enam tidak ada di dalam sana. 248 00:12:52,790 --> 00:12:55,250 >> Jadi, langkah seterusnya adalah untuk pergi ke penunjuk yang akan datang, 249 00:12:55,250 --> 00:12:57,440 jadi berkata trav sama trav depan. 250 00:12:57,440 --> 00:13:00,750 Nah, trav depan, ditunjukkan oleh kotak merah di sana, adalah batal. 251 00:13:00,750 --> 00:13:03,020 Jadi ada tempat lain untuk pergi, dan sebagainya pada ketika ini 252 00:13:03,020 --> 00:13:06,120 kita boleh menyimpulkan bahawa kita telah mencapai akhir senarai berkaitan, 253 00:13:06,120 --> 00:13:07,190 dan 6 tidak ada di sana. 254 00:13:07,190 --> 00:13:10,980 Dan ia akan dikembalikan palsu dalam kes ini. 255 00:13:10,980 --> 00:13:14,540 >> OK, bagaimana kita memasukkan baru nod dalam senarai berpaut? 256 00:13:14,540 --> 00:13:17,310 Oleh itu, kita telah dapat mewujudkan senarai berpaut entah dari mana, 257 00:13:17,310 --> 00:13:19,370 tetapi kita mungkin mahu membina rantai dan tidak 258 00:13:19,370 --> 00:13:22,620 mewujudkan sekumpulan senarai berbeza. 259 00:13:22,620 --> 00:13:25,700 Kami mahu mempunyai satu senarai yang mempunyai sekumpulan nod di dalamnya, 260 00:13:25,700 --> 00:13:28,040 bukan sekumpulan senarai dengan nod tunggal. 261 00:13:28,040 --> 00:13:31,260 Oleh itu, kita tidak boleh hanya terus menggunakan Cipta fungsi kita ditakrifkan sebelum ini, sekarang kita 262 00:13:31,260 --> 00:13:33,860 mahu masukkan ke dalam senarai itu telah wujud. 263 00:13:33,860 --> 00:13:36,499 >> Jadi kes ini, kita akan lulus dalam dua hujah, 264 00:13:36,499 --> 00:13:39,290 penunjuk kepada ketua yang senarai yang kita mahu untuk menambah berkaitan. 265 00:13:39,290 --> 00:13:40,910 Sekali lagi, itulah sebabnya ia begitu penting untuk kita sentiasa 266 00:13:40,910 --> 00:13:43,400 mengesan, kerana ia adalah satu-satunya cara kita benar-benar 267 00:13:43,400 --> 00:13:46,690 perlu merujuk kepada keseluruhan senarai adalah hanya dengan penunjuk kepada elemen pertama. 268 00:13:46,690 --> 00:13:49,360 Oleh itu, kita mahu lulus dalam penunjuk kepada elemen pertama, 269 00:13:49,360 --> 00:13:52,226 dan apa sahaja yang kita nilai ingin menambah kepada senarai. 270 00:13:52,226 --> 00:13:54,600 Dan akhirnya fungsi ini akan kembali penunjuk 271 00:13:54,600 --> 00:13:57,980 kepada ketua baru senarai berpaut. 272 00:13:57,980 --> 00:13:59,700 >> Apakah langkah-langkah yang terlibat di sini? 273 00:13:59,700 --> 00:14:02,249 Nah, sama seperti dengan membuat, kita perlu dinamik memperuntukkan 274 00:14:02,249 --> 00:14:05,540 ruang untuk nod baru, dan periksa untuk memastikan kita tidak kehabisan memori, sekali lagi, 275 00:14:05,540 --> 00:14:07,150 kerana kita menggunakan malloc. 276 00:14:07,150 --> 00:14:09,080 Maka kita mahu untuk mengisi dan masukkan nod, 277 00:14:09,080 --> 00:14:12,730 jadi meletakkan jumlah itu, apa sahaja yang val adalah, ke dalam nod. 278 00:14:12,730 --> 00:14:17,310 Kami mahu memasukkan nod di permulaan senarai yang dipautkan. 279 00:14:17,310 --> 00:14:19,619 >> Ada sebab yang saya mahu melakukan ini, dan ia 280 00:14:19,619 --> 00:14:21,910 mungkin bernilai mengambil kedua untuk menjedakan video di sini, 281 00:14:21,910 --> 00:14:25,860 dan berfikir tentang mengapa saya mahu memasukkan pada awal berpaut 282 00:14:25,860 --> 00:14:26,589 senarai. 283 00:14:26,589 --> 00:14:28,630 Sekali lagi, saya nyatakan sebelum ini bahawa ia tidak benar-benar 284 00:14:28,630 --> 00:14:33,020 kira jika kita mengekalkan ia dalam mana-mana perintah, jadi mungkin itulah petunjuk. 285 00:14:33,020 --> 00:14:36,040 Dan anda melihat apa yang akan berlaku jika kita mahu supaya- atau daripada hanya sesaat 286 00:14:36,040 --> 00:14:37,360 lalu apabila kami pergi melalui carian anda 287 00:14:37,360 --> 00:14:39,235 dapat melihat apa yang mungkin berlaku jika kita cuba 288 00:14:39,235 --> 00:14:41,330 untuk memasukkan pada akhir senarai. 289 00:14:41,330 --> 00:14:44,750 Kerana kita tidak mempunyai penunjuk kepada akhir senarai. 290 00:14:44,750 --> 00:14:47,490 >> Jadi sebab itu saya mahu untuk memasukkan pada permulaan, 291 00:14:47,490 --> 00:14:49,380 kerana saya boleh melakukannya dengan segera. 292 00:14:49,380 --> 00:14:52,730 Saya mempunyai penunjuk pada permulaan, dan kita akan melihat ini dalam visual dalam satu saat. 293 00:14:52,730 --> 00:14:55,605 Tetapi jika saya mahu memasukkan pada akhirnya, Saya perlu bermula pada awal, 294 00:14:55,605 --> 00:14:58,760 merentasi semua jalan ke akhir, dan kemudian jelujur ia. 295 00:14:58,760 --> 00:15:01,420 Supaya bermakna memasukkan di akhir senarai 296 00:15:01,420 --> 00:15:04,140 akan menjadi o n operasi, akan kembali 297 00:15:04,140 --> 00:15:06,720 untuk perbincangan kita tentang kerumitan pengiraan. 298 00:15:06,720 --> 00:15:10,140 Ia akan menjadi o n operasi, di mana sebagai senarai yang mendapat lebih besar, dan lebih besar, 299 00:15:10,140 --> 00:15:13,310 dan lebih besar, ia akan menjadi lebih dan lebih sukar untuk jelujur sesuatu 300 00:15:13,310 --> 00:15:14,661 pada pada akhir. 301 00:15:14,661 --> 00:15:17,410 Tetapi ia sentiasa benar-benar mudah untuk jelujur sesuatu pada pada permulaan, 302 00:15:17,410 --> 00:15:19,060 anda sentiasa pada permulaan. 303 00:15:19,060 --> 00:15:21,620 >> Dan kita akan melihat visual ini lagi. 304 00:15:21,620 --> 00:15:24,100 Dan kemudian sebaik sahaja kami selesai, sebaik sahaja kami telah dimasukkan nod baru, 305 00:15:24,100 --> 00:15:26,880 kita mahu kembali penunjuk kami untuk ketua baru senarai berpaut, yang 306 00:15:26,880 --> 00:15:29,213 kerana kita memasukkan di permulaan, benar-benar akan menjadi 307 00:15:29,213 --> 00:15:31,060 penunjuk kepada nod yang kita buat. 308 00:15:31,060 --> 00:15:33,280 Mari kita menggambarkan hal ini, kerana saya fikir ia akan membantu. 309 00:15:33,280 --> 00:15:36,661 >> Jadi di sini adalah senarai kami, ia terdiri daripada empat elemen, nod yang mengandungi 15, 310 00:15:36,661 --> 00:15:38,410 yang menunjuk kepada nod mengandungi 9, yang 311 00:15:38,410 --> 00:15:41,370 menunjuk kepada nod yang mengandungi 13, yang menunjuk kepada nod yang mengandungi 312 00:15:41,370 --> 00:15:44,840 10, yang mempunyai null penunjuk sebagai penunjuk seterusnya 313 00:15:44,840 --> 00:15:47,010 jadi itulah akhir senarai. 314 00:15:47,010 --> 00:15:50,200 Oleh itu, kita mahu untuk memasukkan nod baru dengan nilai 12 315 00:15:50,200 --> 00:15:52,720 pada awal ini senarai, apa yang kita lakukan? 316 00:15:52,720 --> 00:15:58,770 Well, pertama kita malloc ruang untuk nod, dan kemudian kita masukkan ke 12 di sana. 317 00:15:58,770 --> 00:16:02,211 >> Jadi sekarang kita telah mencapai titik keputusan, bukan? 318 00:16:02,211 --> 00:16:03,960 Kami mempunyai beberapa petunjuk yang kita boleh 319 00:16:03,960 --> 00:16:06,770 bergerak, yang mana satu yang patut kita bergerak dahulu? 320 00:16:06,770 --> 00:16:09,250 Sekiranya kita membuat 12 mata untuk ketua baru list-- yang 321 00:16:09,250 --> 00:16:13,020 atau maafkan saya, kita perlu membuat 12 menunjukkan kepala lama senarai? 322 00:16:13,020 --> 00:16:15,319 Atau kita tidak mengatakan bahawa Senarai kini bermula pada 12. 323 00:16:15,319 --> 00:16:17,110 Ada perbezaan yang di sana, dan kita akan melihat 324 00:16:17,110 --> 00:16:19,870 apa yang berlaku dengan kedua-dua dalam satu saat. 325 00:16:19,870 --> 00:16:23,350 >> Tetapi ini membawa kepada topik yang besar untuk bar sisi, 326 00:16:23,350 --> 00:16:26,280 yang adalah bahawa salah satu daripada perkara yang paling sukar dengan senarai berkaitan 327 00:16:26,280 --> 00:16:30,980 adalah untuk menyusun petunjuk dalam susunan yang betul. 328 00:16:30,980 --> 00:16:34,520 Jika anda bergerak perkara daripada perintah, anda boleh berakhir tidak sengaja 329 00:16:34,520 --> 00:16:36,050 anak yatim yang lain dalam senarai itu. 330 00:16:36,050 --> 00:16:37,300 Dan di sini adalah satu contoh itu. 331 00:16:37,300 --> 00:16:40,540 Jadi mari kita pergi dengan idea daripada- baik, kami telah membina 12. 332 00:16:40,540 --> 00:16:43,180 Kita tahu 12 akan menjadi ketua baru senarai, 333 00:16:43,180 --> 00:16:47,660 dan jadi mengapa tidak kita hanya bergerak penunjuk senarai untuk menunjukkan di sana. 334 00:16:47,660 --> 00:16:49,070 >> OK, jadi itulah yang baik. 335 00:16:49,070 --> 00:16:51,560 Jadi sekarang di mana tidak 12 Fakta yang seterusnya? 336 00:16:51,560 --> 00:16:54,580 Maksud saya, visual yang kita dapat lihat supaya ia menunjuk kepada 15, 337 00:16:54,580 --> 00:16:57,250 sebagai manusia ia benar-benar jelas kepada kami. 338 00:16:57,250 --> 00:17:00,300 Bagaimana komputer tahu? 339 00:17:00,300 --> 00:17:02,720 Kami tidak mempunyai apa-apa menunjuk ke 15 lagi, bukan? 340 00:17:02,720 --> 00:17:05,869 >> Kami telah kehilangan apa-apa keupayaan untuk merujuk kepada 15. 341 00:17:05,869 --> 00:17:11,460 Kita tidak boleh mengatakan anak panah baru setaraf seterusnya sesuatu, tiada apa-apa di sana. 342 00:17:11,460 --> 00:17:13,510 Malah, kami telah yatim yang lain dalam senarai 343 00:17:13,510 --> 00:17:16,465 dengan berbuat demikian, kami telah sengaja rosak rantai. 344 00:17:16,465 --> 00:17:18,089 Dan kami tidak mahu berbuat demikian. 345 00:17:18,089 --> 00:17:20,000 >> Oleh itu, marilah kita kembali dan cuba ini lagi. 346 00:17:20,000 --> 00:17:24,060 Mungkin perkara yang betul untuk melakukan adalah untuk menetapkan penunjuk tempoh 12 ini 347 00:17:24,060 --> 00:17:28,290 kepala lama dalam senarai yang pertama, maka kita boleh menggerakkan senarai lebih. 348 00:17:28,290 --> 00:17:30,420 Dan sebenarnya, iaitu susunan yang betul yang kita 349 00:17:30,420 --> 00:17:32,836 perlu mengikuti apabila kami bekerja dengan senarai secara tunggal berkaitan. 350 00:17:32,836 --> 00:17:36,460 Kami sentiasa mahu menyambung elemen baru ke dalam senarai, 351 00:17:36,460 --> 00:17:41,010 sebelum kita mengambil yang jenis langkah yang penting untuk mengubah 352 00:17:41,010 --> 00:17:43,360 di mana ketua senarai berkaitan adalah. 353 00:17:43,360 --> 00:17:46,740 Sekali lagi, itu satu perkara yang asas, kita tidak mahu untuk mengesan kehilangan ia. 354 00:17:46,740 --> 00:17:49,310 >> Oleh itu, kita mahu memastikan bahawa semuanya dirantai bersama-sama, 355 00:17:49,310 --> 00:17:52,040 sebelum kita gerakkan penuding itu. 356 00:17:52,040 --> 00:17:55,300 Dan sebagainya ini akan menjadi susunan yang betul, iaitu untuk menyambung 12 ke dalam senarai, 357 00:17:55,300 --> 00:17:57,630 kemudian mengatakan bahawa senarai itu bermula 12. 358 00:17:57,630 --> 00:18:00,860 Jika kita berkata senarai itu bermula pada 12 dan kemudian cuba untuk menyambung 12 ke dalam senarai, 359 00:18:00,860 --> 00:18:02,193 kita telah pun melihat apa yang berlaku. 360 00:18:02,193 --> 00:18:04,920 Kita kehilangan senarai dengan sengaja. 361 00:18:04,920 --> 00:18:06,740 >> OK, jadi satu perkara lagi untuk bercakap tentang. 362 00:18:06,740 --> 00:18:09,750 Bagaimana jika kita mahu untuk menghilangkan keseluruhan senarai dikaitkan sekaligus? 363 00:18:09,750 --> 00:18:11,750 Sekali lagi, kami mallocing semua ruang ini, dan dengan itu kita 364 00:18:11,750 --> 00:18:13,351 perlu untuk membebaskan apabila kita selesai. 365 00:18:13,351 --> 00:18:15,350 Jadi sekarang kita mahu memadam senarai dikaitkan keseluruhan. 366 00:18:15,350 --> 00:18:16,850 Well, apa yang kita mahu lakukan? 367 00:18:16,850 --> 00:18:20,460 >> Jika kita telah mencapai penunjuk nol, kita mahu berhenti, jika tidak, hanya memadam 368 00:18:20,460 --> 00:18:23,420 yang lain dalam senarai dan kemudian membebaskan saya. 369 00:18:23,420 --> 00:18:28,890 Padam selebihnya senarai, dan kemudian membebaskan nod semasa. 370 00:18:28,890 --> 00:18:32,850 Apakah bunyi yang seperti, apa teknik perlu kita bercakap 371 00:18:32,850 --> 00:18:35,440 tentang sebelum adakah itu bunyi seperti? 372 00:18:35,440 --> 00:18:39,560 Memadam semua orang lain, maka kembali dan memadam saya. 373 00:18:39,560 --> 00:18:42,380 >> Itulah rekursi, kami telah membuat masalah sedikit lebih kecil, 374 00:18:42,380 --> 00:18:46,910 kita katakan memadam semua orang lain, maka anda boleh memadam saya. 375 00:18:46,910 --> 00:18:50,940 Dan lebih bawah jalan, nod yang akan berkata, memadam orang lain. 376 00:18:50,940 --> 00:18:53,940 Tetapi akhirnya kita akan sampai ke titik di mana senarai itu adalah batal, 377 00:18:53,940 --> 00:18:55,310 dan itulah kes asas kami. 378 00:18:55,310 --> 00:18:57,010 >> Jadi mari kita lihat ini, dan bagaimana ini mungkin bekerja. 379 00:18:57,010 --> 00:18:59,759 Jadi di sini adalah senarai kami, ia adalah sama senarai kami hanya bercakap tentang, 380 00:18:59,759 --> 00:19:00,980 dan ada langkah-langkah. 381 00:19:00,980 --> 00:19:04,200 Ada banyak teks di sini, tetapi mudah-mudahan visualisasi akan membantu. 382 00:19:04,200 --> 00:19:08,557 >> Oleh itu, kita ada-- dan saya juga ditarik sehingga ilustrasi bingkai tindanan kami 383 00:19:08,557 --> 00:19:10,890 dari video kami pada susunan panggilan, dan mudah-mudahan semua ini 384 00:19:10,890 --> 00:19:13,260 bersama-sama akan menunjukkan kepada anda apa yang sedang berlaku. 385 00:19:13,260 --> 00:19:14,510 Jadi di sini adalah kod kod pseudo kami. 386 00:19:14,510 --> 00:19:17,830 Jika kita mencapai null yang penunjuk, berhenti, jika tidak, 387 00:19:17,830 --> 00:19:21,320 memadam selebihnya senarai, kemudian membebaskan nod semasa. 388 00:19:21,320 --> 00:19:25,700 Jadi sekarang, list-- penunjuk bahawa kita 389 00:19:25,700 --> 00:19:28,410 lulus dalam untuk memusnahkan mata kepada 12. 390 00:19:28,410 --> 00:19:33,340 12 bukan penunjuk null, jadi kami akan memadam yang lain dalam senarai itu. 391 00:19:33,340 --> 00:19:35,450 >> Apa yang memotong lain daripada kita yang terlibat? 392 00:19:35,450 --> 00:19:37,950 Nah, ia bermakna membuat memanggil untuk memusnahkan, berkata 393 00:19:37,950 --> 00:19:42,060 yang 15 adalah permulaan lain dalam senarai yang kita mahu untuk memusnahkan. 394 00:19:42,060 --> 00:19:47,480 Dan sebagainya panggilan untuk memusnahkan 12 adalah jenis ditahan. 395 00:19:47,480 --> 00:19:52,690 Ia beku di sana, menunggu memanggil untuk memusnahkan 15, untuk menyelesaikan tugasnya. 396 00:19:52,690 --> 00:19:56,280 >> Well, 15 bukan penunjuk null, dan jadi ia akan berkata, semua hak, 397 00:19:56,280 --> 00:19:58,450 baik, memadam seluruh senarai. 398 00:19:58,450 --> 00:20:00,760 Selebihnya senarai bermula pada 9, dan dengan itu kita akan hanya 399 00:20:00,760 --> 00:20:04,514 tunggu sehingga anda memadam semua yang barangan, kemudian kembali dan memadam saya. 400 00:20:04,514 --> 00:20:06,680 Well 9 akan berkata, baik, Saya bukan penunjuk null, 401 00:20:06,680 --> 00:20:09,020 supaya memadam selebihnya senarai dari sini. 402 00:20:09,020 --> 00:20:11,805 Dan jadi cuba dan memusnahkan 13. 403 00:20:11,805 --> 00:20:15,550 13 berkata, saya tidak penunjuk null, Perkara yang sama, ia pas tanggungjawab itu. 404 00:20:15,550 --> 00:20:17,930 10 tidak penunjuk null, 10 mengandungi penunjuk null, 405 00:20:17,930 --> 00:20:20,200 tetapi 10 tidak sendiri adalah null penunjuk sekarang, 406 00:20:20,200 --> 00:20:22,470 dan oleh itu pas tanggungjawab itu juga. 407 00:20:22,470 --> 00:20:25,560 >> Dan kini senarai mata di sana, ia benar-benar akan menunjukkan some-- 408 00:20:25,560 --> 00:20:28,710 jika saya mempunyai lebih banyak ruang dalam imej, ia akan menunjukkan beberapa ruang rawak 409 00:20:28,710 --> 00:20:29,960 bahawa kita tidak tahu apa yang ada. 410 00:20:29,960 --> 00:20:34,680 Ia adalah penunjuk nol walaupun, senarai secara literal kini ditetapkan itu nilai-nilai null. 411 00:20:34,680 --> 00:20:36,820 Ia menunjuk betul di dalam kotak yang merah. 412 00:20:36,820 --> 00:20:39,960 Kami sampai penunjuk batal, jadi kita boleh berhenti, dan kami sudah selesai. 413 00:20:39,960 --> 00:20:46,230 >> Dan supaya rangka ungu adalah sekarang-- di atas stack-- itulah bingkai aktif, 414 00:20:46,230 --> 00:20:47,017 tetapi ia dilakukan. 415 00:20:47,017 --> 00:20:48,600 Jika kita telah mencapai penunjuk null, berhenti. 416 00:20:48,600 --> 00:20:51,290 Kami tidak berbuat apa-apa, kita tidak boleh membebaskan penunjuk null, 417 00:20:51,290 --> 00:20:55,070 kami tidak malloc apa-apa ruang, dan dengan itu kita selesai. 418 00:20:55,070 --> 00:20:57,590 Supaya rangka fungsi dimusnahkan, dan kami 419 00:20:57,590 --> 00:21:00,930 resume-- kami mengambil mana kita mati dengan yang paling tinggi yang seterusnya, yang 420 00:21:00,930 --> 00:21:02,807 adalah tempoh yang gelap biru di sini. 421 00:21:02,807 --> 00:21:04,390 Oleh itu, kita mengambil hak mana kita berhenti. 422 00:21:04,390 --> 00:21:06,598 Kami telah membuang yang lain daripada senarai sudah, jadi sekarang kita 423 00:21:06,598 --> 00:21:08,000 akan membebaskan nod semasa. 424 00:21:08,000 --> 00:21:12,920 Jadi sekarang kita boleh bebas nod ini, dan kini kami telah sampai ke penghujung majlis itu. 425 00:21:12,920 --> 00:21:16,810 Dan supaya rangka fungsi dimusnahkan, dan kami menjemput di satu biru cahaya. 426 00:21:16,810 --> 00:21:20,650 >> Jadi ia says-- saya telah done-- memotong yang lain dalam senarai ini, jadi 427 00:21:20,650 --> 00:21:23,140 membebaskan nod semasa. 428 00:21:23,140 --> 00:21:26,520 Dan sekarang bingkai kuning adalah kembali di atas timbunan. 429 00:21:26,520 --> 00:21:29,655 Dan sebagainya seperti yang anda lihat, kami sekarang memusnahkan senarai dari kanan ke kiri. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Apa yang akan berlaku, walaupun, jika kita telah melakukan sesuatu dengan cara yang salah? 432 00:21:37,280 --> 00:21:39,410 Sama seperti apabila kita cuba untuk menambah unsur. 433 00:21:39,410 --> 00:21:41,909 Jika kita sehingga merosakkan rantai, jika kami tidak menyambung petunjuk 434 00:21:41,909 --> 00:21:44,690 dalam susunan yang betul, jika kita hanya dibebaskan elemen pertama, 435 00:21:44,690 --> 00:21:47,420 jika kita hanya dibebaskan ketua senarai, sekarang kita 436 00:21:47,420 --> 00:21:49,642 tidak mempunyai cara untuk merujuk kepada seluruh senarai. 437 00:21:49,642 --> 00:21:51,350 Dan dengan itu kita akan mempunyai segala-galanya yatim, 438 00:21:51,350 --> 00:21:53,880 kita akan mempunyai apa yang dipanggil kebocoran memori. 439 00:21:53,880 --> 00:21:56,800 Jika anda ingat dari video kami mengenai peruntukan memori dinamik, 440 00:21:56,800 --> 00:21:58,650 itu bukan perkara yang sangat baik. 441 00:21:58,650 --> 00:22:00,810 >> Jadi seperti yang saya katakan, terdapat beberapa operasi 442 00:22:00,810 --> 00:22:04,010 yang perlu kita gunakan untuk bekerja dengan senarai dikaitkan dengan berkesan. 443 00:22:04,010 --> 00:22:08,430 Dan anda mungkin perasan saya ditinggalkan satu, memotong satu unsur dari berpaut 444 00:22:08,430 --> 00:22:09,064 senarai. 445 00:22:09,064 --> 00:22:10,980 Alasan saya berbuat demikian adalah ia sebenarnya sejenis 446 00:22:10,980 --> 00:22:14,360 sukar untuk berfikir tentang bagaimana untuk memadam satu unsur dari secara tunggal 447 00:22:14,360 --> 00:22:15,600 senarai berkaitan. 448 00:22:15,600 --> 00:22:19,950 Kita perlu dapat melangkau lebih sesuatu dalam senarai, yang 449 00:22:19,950 --> 00:22:22,975 ertinya kita dapat, kita point-- mahu memadam node-- ini 450 00:22:22,975 --> 00:22:25,350 tetapi untuk membuat ia supaya kita tidak kehilangan apa-apa maklumat, 451 00:22:25,350 --> 00:22:30,530 kita perlu menyambungkan ini nod di sini, di sini. 452 00:22:30,530 --> 00:22:33,390 >> Jadi saya mungkin melakukan yang salah dari perspektif yang dengar. 453 00:22:33,390 --> 00:22:36,830 Oleh itu, kita berada pada awal kami senarai, kami meneruskan perjalanan melalui, 454 00:22:36,830 --> 00:22:40,510 kami mahu memadam nod ini. 455 00:22:40,510 --> 00:22:43,440 Jika kita hanya memadamnya, kami telah rosak rantai. 456 00:22:43,440 --> 00:22:45,950 Nod ini di sini merujuk kepada segala-galanya, 457 00:22:45,950 --> 00:22:48,260 ia mengandungi rantai dari sini pada keluar. 458 00:22:48,260 --> 00:22:51,190 >> Jadi apa yang perlu kita lakukan sebenarnya selepas kita sampai ke tahap ini, 459 00:22:51,190 --> 00:22:56,670 adalah kita perlu untuk langkah ke belakang satu, dan menyambung nod ini ke nod ini, 460 00:22:56,670 --> 00:22:58,590 jadi kami boleh memadam yang di tengah-tengah. 461 00:22:58,590 --> 00:23:02,120 Tetapi senarai secara tunggal berkaitan tidak memberikan kita satu cara untuk pergi ke belakang. 462 00:23:02,120 --> 00:23:05,160 Oleh itu, kita perlu sama ada untuk menyimpan dua petunjuk, dan memindahkan mereka 463 00:23:05,160 --> 00:23:09,527 semacam langkah di luar, satu di belakang yang lain seperti yang kita pergi, atau mendapatkan ke satu tahap 464 00:23:09,527 --> 00:23:11,110 dan kemudian menghantar penunjuk lain melalui. 465 00:23:11,110 --> 00:23:13,150 Dan seperti yang anda boleh lihat, ia boleh mendapatkan kemas sedikit. 466 00:23:13,150 --> 00:23:15,360 Mujurlah, kami mempunyai cara lain untuk menyelesaikan itu, 467 00:23:15,360 --> 00:23:17,810 apabila kita bercakap mengenai senarai duanya adalah terpakai dikaitkan. 468 00:23:17,810 --> 00:23:20,720 >> Saya Doug Lloyd, ini adalah CS50. 469 00:23:20,720 --> 00:23:22,298