1 00:00:00,000 --> 00:00:02,832 >> [MUSIC PLAYING] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> Doug LLOYD: OK, jadi pada saat ini dalam kursus, 4 00:00:08,560 --> 00:00:15,300 kita telah membahas banyak dasar-dasar C. Kami tahu banyak tentang variabel, array, 5 00:00:15,300 --> 00:00:17,610 pointer, semua hal yang baik. 6 00:00:17,610 --> 00:00:21,610 Mereka semua jenis dibangun untuk melihat sebagai fundamental, 7 00:00:21,610 --> 00:00:23,880 tapi kita bisa berbuat lebih banyak, kan? 8 00:00:23,880 --> 00:00:27,930 Kita bisa menggabungkan hal-hal bersama-sama dengan cara yang menarik. 9 00:00:27,930 --> 00:00:31,010 >> Dan jadi mari kita melakukan itu, mari kita mulai untuk cabang keluar dari apa C memberi kita, 10 00:00:31,010 --> 00:00:35,270 dan mulai untuk membuat data kita sendiri struktur menggunakan bangunan tersebut 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 dapat kita lakukan ini untuk berbicara tentang koleksi. 13 00:00:43,420 --> 00:00:48,360 Jadi sejauh ini kita sudah punya satu jenis data struktur untuk mewakili koleksi 14 00:00:48,360 --> 00:00:51,030 dari seperti nilai-nilai, nilai-nilai yang sama. 15 00:00:51,030 --> 00:00:52,350 Itu akan menjadi sebuah array. 16 00:00:52,350 --> 00:00:57,020 Kami memiliki koleksi bilangan bulat, atau koleksi karakter dan sebagainya. 17 00:00:57,020 --> 00:01:00,890 >> Struktur juga mengurutkan data yang struktur untuk mengumpulkan informasi, 18 00:01:00,890 --> 00:01:03,220 tapi tidak untuk mengumpulkan seperti nilai-nilai. 19 00:01:03,220 --> 00:01:08,090 Biasanya campuran jenis data yang berbeda bersama-sama dalam satu kotak. 20 00:01:08,090 --> 00:01:10,750 Tapi itu tidak sendiri digunakan untuk rantai bersama-sama 21 00:01:10,750 --> 00:01:16,920 atau menghubungkan bersama-sama sejenis item, seperti array. 22 00:01:16,920 --> 00:01:20,960 Array yang besar untuk Unsur melihat ke atas, tapi ingat 23 00:01:20,960 --> 00:01:24,262 bahwa itu sangat sulit untuk memasukkan ke dalam sebuah array, 24 00:01:24,262 --> 00:01:26,470 kecuali kita memasukkan di akhir dari array. 25 00:01:26,470 --> 00:01:29,730 >> Dan contoh terbaik yang saya miliki untuk itu adalah insertion sort. 26 00:01:29,730 --> 00:01:31,650 Jika Anda ingat video kami pada insertion sort, 27 00:01:31,650 --> 00:01:34,110 ada banyak biaya yang terlibat dalam memiliki 28 00:01:34,110 --> 00:01:37,970 untuk mengambil elemen, dan pergeseran mereka keluar dari jalan untuk menyesuaikan sesuatu 29 00:01:37,970 --> 00:01:41,290 ke tengah array Anda. 30 00:01:41,290 --> 00:01:44,690 Array juga menderita lain Masalahnya, yang tidak fleksibel. 31 00:01:44,690 --> 00:01:47,150 Ketika kita mendeklarasikan array, kita mendapatkan satu kesempatan itu. 32 00:01:47,150 --> 00:01:49,790 Kita bisa mengatakan, saya ingin ini banyak unsur. 33 00:01:49,790 --> 00:01:51,940 Mungkin 100, itu mungkin 1.000, itu mungkin 34 00:01:51,940 --> 00:01:55,930 menjadi x di mana x adalah angka yang pengguna memberi kami pada prompt atau perintah 35 00:01:55,930 --> 00:01:56,630 line. 36 00:01:56,630 --> 00:01:59,905 >> Tapi kami hanya mendapatkan satu kesempatan, kita tidak bisa kemudian berkata oh, sebenarnya saya 37 00:01:59,905 --> 00:02:04,360 dibutuhkan 101, atau saya butuhkan x ditambah 20. 38 00:02:04,360 --> 00:02:07,910 Terlambat, kita sudah mendeklarasikan array, dan jika kita ingin mendapatkan 101 atau x 39 00:02:07,910 --> 00:02:12,050 ditambah 20, kita harus menyatakan array yang sama sekali berbeda, 40 00:02:12,050 --> 00:02:15,540 menyalin semua elemen array lebih, dan kemudian kita memiliki cukup. 41 00:02:15,540 --> 00:02:19,880 Dan bagaimana jika kita salah lagi, apa jika kita benar-benar membutuhkan 102, atau x ditambah 40, 42 00:02:19,880 --> 00:02:21,970 kita harus melakukan ini lagi. 43 00:02:21,970 --> 00:02:26,250 Jadi mereka sangat fleksibel untuk mengubah ukuran data kami, 44 00:02:26,250 --> 00:02:29,360 tetapi jika kita menggabungkan bersama-sama beberapa dari dasar-dasar yang kita sudah sudah 45 00:02:29,360 --> 00:02:33,230 belajar tentang pointer dan struktur, khususnya menggunakan memori dinamis 46 00:02:33,230 --> 00:02:36,180 Alokasi dengan malloc, kami dapat menempatkan potongan-potongan ini bersama-sama 47 00:02:36,180 --> 00:02:40,960 untuk membuat data baru structure-- sebuah tunggal linked list kita mungkin say-- 48 00:02:40,960 --> 00:02:45,400 yang memungkinkan kita untuk tumbuh dan menyusut koleksi nilai 49 00:02:45,400 --> 00:02:48,800 dan kami tidak akan memiliki ruang kosong. 50 00:02:48,800 --> 00:02:53,320 >> Jadi sekali lagi, kita sebut ide ini, gagasan ini, linked list. 51 00:02:53,320 --> 00:02:56,320 Secara khusus, dalam video ini kami berbicara tentang daftar sendiri-sendiri terkait, 52 00:02:56,320 --> 00:02:59,185 dan kemudian video lain kita akan bicara daftar tentang ganda terkait, 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 Tapi daftar sendiri-sendiri terkait terdiri dari node, 55 00:03:05,200 --> 00:03:08,559 node hanya menjadi term-- abstrak itu hanya sesuatu yang saya menelepon 56 00:03:08,559 --> 00:03:10,350 itu semacam struktur, pada dasarnya, aku? 57 00:03:10,350 --> 00:03:16,190 Hanya akan menyebutnya node-- dan ini node memiliki dua anggota, atau dua bidang. 58 00:03:16,190 --> 00:03:20,300 Ini memiliki data, biasanya integer, float karakter, 59 00:03:20,300 --> 00:03:23,790 atau bisa beberapa jenis data lain bahwa Anda telah didefinisikan dengan tipe def. 60 00:03:23,790 --> 00:03:29,290 Dan berisi pointer ke node lain dari jenis yang sama. 61 00:03:29,290 --> 00:03:34,710 >> Jadi kita memiliki dua hal dalam node ini, data dan pointer 62 00:03:34,710 --> 00:03:36,380 ke node lain. 63 00:03:36,380 --> 00:03:39,370 Dan jika Anda mulai untuk memvisualisasikan ini, Anda dapat berpikir tentang hal ini 64 00:03:39,370 --> 00:03:42,280 seperti rantai node yang terhubung bersama-sama. 65 00:03:42,280 --> 00:03:45,070 Kami memiliki node pertama, berisi data, dan pointer 66 00:03:45,070 --> 00:03:49,110 ke node kedua, yang berisi data, dan pointer ke node ketiga. 67 00:03:49,110 --> 00:03:52,940 Dan jadi itu sebabnya kami menyebutnya linked list, mereka dihubungkan bersama. 68 00:03:52,940 --> 00:03:56,070 >> Apa ini khusus struktur simpul terlihat seperti? 69 00:03:56,070 --> 00:04:01,120 Nah, jika Anda ingat dari video kami di mendefinisikan jenis kustom, dengan tipe def, 70 00:04:01,120 --> 00:04:05,400 kita dapat mendefinisikan structure-- dan ketik menentukan struktur seperti ini. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, dan kemudian aku menggunakan nilai kata di sini sewenang-wenang 72 00:04:11,240 --> 00:04:13,891 untuk menunjukkan jenis data yang benar-benar. 73 00:04:13,891 --> 00:04:16,890 Anda bisa menyampaikan integer atau float, Anda bisa memiliki apa pun yang Anda inginkan. 74 00:04:16,890 --> 00:04:19,389 Ini tidak terbatas hanya bilangan bulat, atau sesuatu seperti itu. 75 00:04:19,389 --> 00:04:22,790 Jadi nilai hanya sebuah sewenang-wenang tipe data, dan kemudian pointer 76 00:04:22,790 --> 00:04:26,310 ke node lain dari jenis yang sama. 77 00:04:26,310 --> 00:04:29,690 >> Sekarang, ada menangkap sedikit di sini dengan mendefinisikan struktur 78 00:04:29,690 --> 00:04:33,030 ketika itu struktur referensial diri. 79 00:04:33,030 --> 00:04:35,340 Saya harus memiliki sementara nama untuk struktur saya. 80 00:04:35,340 --> 00:04:37,640 Pada akhir hari saya jelas ingin menyebutnya 81 00:04:37,640 --> 00:04:43,030 sll node, yang akhirnya baru nama bagian dari jenis definisi saya, 82 00:04:43,030 --> 00:04:47,450 tapi saya tidak dapat menggunakan sll simpul di tengah-tengah ini. 83 00:04:47,450 --> 00:04:51,430 Alasannya, saya tidak menciptakan jenis yang disebut sll simpul 84 00:04:51,430 --> 00:04:55,200 sampai aku memukul titik akhir ini di sini. 85 00:04:55,200 --> 00:04:59,720 Sampai saat itu, saya harus memiliki cara lain untuk merujuk pada tipe data ini. 86 00:04:59,720 --> 00:05:02,440 >> Dan ini adalah diri referensial tipe data. 87 00:05:02,440 --> 00:05:06,314 Itu; s tipe data dari struktur yang berisi data, 88 00:05:06,314 --> 00:05:08,480 dan pointer ke yang lain struktur dari jenis yang sama. 89 00:05:08,480 --> 00:05:11,750 Jadi saya harus mampu untuk merujuk tipe data ini setidaknya untuk sementara, 90 00:05:11,750 --> 00:05:14,910 sehingga memberikan sebuah sementara nama struct sllist 91 00:05:14,910 --> 00:05:18,540 memungkinkan saya untuk kemudian mengatakan saya ingin pointer ke struct sllist lain, 92 00:05:18,540 --> 00:05:24,690 bintang struct sllist, dan kemudian setelah saya menyelesaikan definisi, 93 00:05:24,690 --> 00:05:27,220 Sekarang saya bisa menyebut jenis node sll. 94 00:05:27,220 --> 00:05:30,520 >> Jadi itu sebabnya Anda melihat ada nama sementara di sini, 95 00:05:30,520 --> 00:05:31,879 tapi 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 misalnya, yang tidak referensial diri, yang 98 00:05:36,570 --> 00:05:39,390 tidak memiliki nama specifier sini. 99 00:05:39,390 --> 00:05:43,040 Itu hanya akan mengatakan typedef struct, membuka penjepit keriting dan kemudian mendefinisikannya. 100 00:05:43,040 --> 00:05:45,620 Tapi jika Anda struct diri referensial, seperti yang satu ini, 101 00:05:45,620 --> 00:05:49,010 Anda perlu menentukan nama tipe sementara. 102 00:05:49,010 --> 00:05:51,310 Tapi pada akhirnya, sekarang bahwa kita sudah melakukan ini, 103 00:05:51,310 --> 00:05:53,620 kita hanya dapat merujuk node ini, unit-unit ini, 104 00:05:53,620 --> 00:05:57,900 sebagai node sll untuk tujuan dari sisa video ini. 105 00:05:57,900 --> 00:06:00,900 >> Baiklah, jadi kita tahu bagaimana membuat daftar simpul terkait. 106 00:06:00,900 --> 00:06:03,240 Kita tahu bagaimana mendefinisikan daftar simpul terkait. 107 00:06:03,240 --> 00:06:06,670 Sekarang, jika kita akan memulai menggunakan mereka untuk mengumpulkan informasi, 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 cara membuat linked list dari udara tipis. 110 00:06:12,860 --> 00:06:14,901 Jika tidak ada daftar sudah, kami ingin memulai satu. 111 00:06:14,901 --> 00:06:16,960 Jadi kita harus mampu untuk membuat daftar link, 112 00:06:16,960 --> 00:06:19,130 kita perlu mencari mungkin melalui daftar link yang 113 00:06:19,130 --> 00:06:21,830 untuk menemukan elemen yang kita cari. 114 00:06:21,830 --> 00:06:24,430 Kita harus mampu memasukkan hal-hal baru ke dalam daftar, 115 00:06:24,430 --> 00:06:25,930 kami ingin daftar kami untuk dapat tumbuh. 116 00:06:25,930 --> 00:06:28,638 Dan sama, kami ingin bisa untuk menghapus hal-hal dari daftar kami, 117 00:06:28,638 --> 00:06:30,250 kami ingin daftar kami dapat menyusut. 118 00:06:30,250 --> 00:06:32,160 Dan pada akhir kami program, terutama 119 00:06:32,160 --> 00:06:34,550 jika Anda ingat bahwa kita dinamis mengalokasikan memori 120 00:06:34,550 --> 00:06:38,337 untuk membangun daftar ini biasanya, kami ingin membebaskan semua memori yang 121 00:06:38,337 --> 00:06:39,670 ketika kita sudah selesai bekerja dengan itu. 122 00:06:39,670 --> 00:06:44,627 Dan jadi kita harus mampu untuk menghapus Seluruh linked list dalam satu gagal menukik. 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 dapat memvisualisasikan mereka, berbicara dalam kode pseudo khusus. 125 00:06:51,192 --> 00:06:53,150 Jadi kita ingin membuat linked list, jadi mungkin kita 126 00:06:53,150 --> 00:06:56,480 ingin mendefinisikan fungsi dengan prototipe ini. 127 00:06:56,480 --> 00:07:01,690 sll bintang node, membuat, dan aku melewati di satu argumen, beberapa data sewenang-wenang 128 00:07:01,690 --> 00:07:05,530 ketik lagi, beberapa tipe data yang sewenang-wenang. 129 00:07:05,530 --> 00:07:10,482 Tapi aku returning-- fungsi ini harus kembali ke saya pointer, untuk sendiri-sendiri 130 00:07:10,482 --> 00:07:11,190 linked list simpul. 131 00:07:11,190 --> 00:07:14,050 Sekali lagi, kami mencoba untuk membuat linked list dari udara tipis, 132 00:07:14,050 --> 00:07:17,900 jadi saya perlu pointer ke bahwa daftar ketika aku sudah selesai. 133 00:07:17,900 --> 00:07:19,420 >> Jadi apa langkah-langkah yang terlibat di sini? 134 00:07:19,420 --> 00:07:20,960 Nah, hal pertama yang saya akan lakukan adalah dinamis 135 00:07:20,960 --> 00:07:22,550 mengalokasikan ruang untuk node baru. 136 00:07:22,550 --> 00:07:26,689 Sekali lagi, kita sedang menciptakan keluar dari tipis udara, jadi kita perlu ruang malloc untuk itu. 137 00:07:26,689 --> 00:07:28,480 Dan tentu saja, segera setelah kami malloc, 138 00:07:28,480 --> 00:07:31,692 kami selalu memeriksa untuk memastikan bahwa kami pointer-- kami tidak mendapatkan kembali nol. 139 00:07:31,692 --> 00:07:33,650 Karena jika kita mencoba dan rasa hormat pointer null, 140 00:07:33,650 --> 00:07:36,190 kita akan menderita segfault dan kami tidak menginginkan hal itu. 141 00:07:36,190 --> 00:07:39,510 >> Kemudian kita ingin mengisi di lapangan, kami ingin menginisialisasi bidang nilai 142 00:07:39,510 --> 00:07:41,690 dan menginisialisasi kolom berikutnya. 143 00:07:41,690 --> 00:07:45,450 Dan kemudian kita ingin to-- akhirnya sebagai Fungsi prototipe indicates-- kita ingin 144 00:07:45,450 --> 00:07:49,940 untuk kembali pointer ke node sll. 145 00:07:49,940 --> 00:07:51,710 Jadi apa yang membuat ini terlihat seperti visual? 146 00:07:51,710 --> 00:07:55,230 Yah, pertama kita akan dinamis mengalokasikan ruang untuk sll node baru, 147 00:07:55,230 --> 00:07:58,320 jadi kami malloc-- itu representasi visual 148 00:07:58,320 --> 00:08:00,020 node yang baru kita buat. 149 00:08:00,020 --> 00:08:02,757 Dan kami periksa untuk memastikan itu tidak null-- dalam kasus ini, 150 00:08:02,757 --> 00:08:04,840 gambar tidak akan muncul jika itu nol, 151 00:08:04,840 --> 00:08:07,298 kita akan kehabisan memori, jadi kita baik untuk pergi ke sana. 152 00:08:07,298 --> 00:08:10,200 Jadi sekarang kita ke langkah C, menginisialisasi bidang nilai node. 153 00:08:10,200 --> 00:08:12,280 Nah, berdasarkan fungsi ini menelepon saya gunakan di sini, 154 00:08:12,280 --> 00:08:16,700 Sepertinya aku ingin lulus dalam 6, jadi saya akan 6 di bidang nilai. 155 00:08:16,700 --> 00:08:18,865 Sekarang, menginisialisasi kolom berikutnya. 156 00:08:18,865 --> 00:08:21,640 Nah, apa yang akan saya lakukan di sana, tidak ada yang berikutnya, benar, 157 00:08:21,640 --> 00:08:23,600 ini adalah satu-satunya hal dalam daftar. 158 00:08:23,600 --> 00:08:27,206 Jadi apa hal berikutnya dalam daftar? 159 00:08:27,206 --> 00:08:29,660 >> Tidak harus menunjuk ke sesuatu, benar. 160 00:08:29,660 --> 00:08:33,600 Tidak ada yang lain di sana, jadi apa konsep kita tahu itu nothing-- 161 00:08:33,600 --> 00:08:35,638 pointer ke apa-apa? 162 00:08:35,638 --> 00:08:37,929 Itu harus mungkin kita ingin untuk menempatkan pointer null ada, 163 00:08:37,929 --> 00:08:40,178 dan aku akan mewakili nol pointer hanya sebagai kotak merah, 164 00:08:40,178 --> 00:08:41,559 kita tidak bisa pergi lebih jauh. 165 00:08:41,559 --> 00:08:44,430 Seperti yang akan kita lihat sedikit nanti, kita akan memiliki akhirnya rantai 166 00:08:44,430 --> 00:08:46,330 panah menghubungkan node ini bersama-sama, 167 00:08:46,330 --> 00:08:48,480 tetapi ketika Anda menekan kotak merah, itu nol, 168 00:08:48,480 --> 00:08:51,150 kita tidak bisa pergi lebih jauh, itulah akhir dari daftar. 169 00:08:51,150 --> 00:08:53,960 >> Dan terakhir, kita hanya ingin kembali pointer ke node ini. 170 00:08:53,960 --> 00:08:56,160 Jadi kita akan menyebutnya baru, dan akan kembali baru 171 00:08:56,160 --> 00:08:59,370 sehingga dapat digunakan dalam Fungsi apapun menciptakannya. 172 00:08:59,370 --> 00:09:03,100 Jadi ada kita pergi, Kami telah menciptakan sendiri-sendiri linked list simpul dari udara tipis, 173 00:09:03,100 --> 00:09:05,920 dan sekarang kami memiliki daftar kami dapat bekerja dengan. 174 00:09:05,920 --> 00:09:08,260 >> Sekarang, katakanlah kita sudah memiliki rantai besar, 175 00:09:08,260 --> 00:09:09,800 dan kita ingin mencari sesuatu di dalamnya. 176 00:09:09,800 --> 00:09:12,716 Dan kami ingin fungsi yang akan untuk kembali benar atau salah, tergantung 177 00:09:12,716 --> 00:09:15,840 apakah suatu nilai ada dalam daftar itu. 178 00:09:15,840 --> 00:09:18,160 Sebuah prototipe fungsi, atau deklarasi untuk fungsi itu, 179 00:09:18,160 --> 00:09:23,320 mungkin terlihat seperti this-- Bool menemukan, dan maka kita ingin lulus dalam dua argumen. 180 00:09:23,320 --> 00:09:26,996 >> Yang pertama, adalah pointer ke elemen pertama dari linked list. 181 00:09:26,996 --> 00:09:29,620 Ini sebenarnya sesuatu yang Anda akan selalu ingin melacak, 182 00:09:29,620 --> 00:09:33,110 dan benar-benar mungkin sesuatu yang Anda bahkan dimasukkan ke dalam variabel global. 183 00:09:33,110 --> 00:09:35,360 Setelah Anda membuat daftar, Anda selalu, selalu 184 00:09:35,360 --> 00:09:38,990 ingin melacak sangat elemen pertama dari daftar. 185 00:09:38,990 --> 00:09:43,690 Dengan cara itu Anda dapat merujuk ke semua lainnya elemen dengan hanya mengikuti rantai, 186 00:09:43,690 --> 00:09:47,300 tanpa harus menjaga pointer utuh untuk setiap elemen tunggal. 187 00:09:47,300 --> 00:09:50,920 Anda hanya perlu untuk melacak pertama satu jika mereka semua dirantai bersama-sama. 188 00:09:50,920 --> 00:09:52,460 >> Dan kemudian hal yang kedua kita melewati lagi 189 00:09:52,460 --> 00:09:54,376 adalah sewenang-wenang some-- apapun jenis data yang kami 190 00:09:54,376 --> 00:09:59,640 mencari ada dalam mudah-mudahan salah satu node dalam daftar. 191 00:09:59,640 --> 00:10:00,980 Jadi apa langkah-langkah? 192 00:10:00,980 --> 00:10:04,250 Nah, hal pertama yang kami lakukan adalah kami membuat pointer transversal 193 00:10:04,250 --> 00:10:06,015 menunjuk ke kepala daftar. 194 00:10:06,015 --> 00:10:08,890 Nah, mengapa kita melakukan itu, kita sudah memiliki pointer di kepala daftar, 195 00:10:08,890 --> 00:10:10,974 kenapa tidak kita hanya bergerak satu bahwa sekitar? 196 00:10:10,974 --> 00:10:13,140 Nah, seperti saya hanya berkata, itu benar-benar penting bagi kami 197 00:10:13,140 --> 00:10:17,580 untuk selalu melacak Unsur pertama dalam daftar. 198 00:10:17,580 --> 00:10:21,270 Dan itu benar-benar baik untuk membuat duplikat dari itu, 199 00:10:21,270 --> 00:10:25,350 dan menggunakannya untuk bergerak sehingga kita tidak pernah sengaja menjauh, atau kita selalu 200 00:10:25,350 --> 00:10:30,430 memiliki pointer di beberapa titik yang tepat pada elemen pertama dari daftar. 201 00:10:30,430 --> 00:10:33,290 Jadi lebih baik untuk membuat kedua satu yang kita gunakan untuk bergerak. 202 00:10:33,290 --> 00:10:35,877 >> Kemudian kita hanya membandingkan apakah bidang nilai pada node yang 203 00:10:35,877 --> 00:10:38,960 adalah apa yang kita cari, dan jika itu tidak, kita hanya pindah ke node berikutnya. 204 00:10:38,960 --> 00:10:41,040 Dan kami terus melakukan itu lebih, dan lebih, dan lebih, 205 00:10:41,040 --> 00:10:44,811 sampai kita baik menemukan elemen, atau kita memukul 206 00:10:44,811 --> 00:10:47,310 null-- kita telah mencapai akhir dari daftar dan tidak ada. 207 00:10:47,310 --> 00:10:50,540 Ini harus mudah-mudahan membunyikan lonceng Anda hanya sebagai pencarian linear, 208 00:10:50,540 --> 00:10:54,430 kami hanya mereplikasi dalam struktur daftar sendiri-sendiri terkait 209 00:10:54,430 --> 00:10:56,280 alih-alih menggunakan array untuk melakukannya. 210 00:10:56,280 --> 00:10:58,210 >> Jadi di sini adalah contoh daftar sendiri-sendiri terkait. 211 00:10:58,210 --> 00:11:00,043 Yang satu ini terdiri dari lima node, dan kami memiliki 212 00:11:00,043 --> 00:11:04,330 pointer ke kepala daftar, yang disebut daftar. 213 00:11:04,330 --> 00:11:07,385 Hal pertama yang kami ingin lakukan adalah lagi, buat yang traversal pointer. 214 00:11:07,385 --> 00:11:09,760 Jadi kita miliki sekarang dua pointer saat itu untuk hal yang sama. 215 00:11:09,760 --> 00:11:15,025 >> Sekarang, perhatikan di sini juga, saya tidak harus malloc ada ruang untuk trav. 216 00:11:15,025 --> 00:11:18,970 Saya tidak mengatakan trav sama malloc sesuatu, simpul yang sudah ada, 217 00:11:18,970 --> 00:11:21,160 bahwa ruang dalam memori sudah ada. 218 00:11:21,160 --> 00:11:24,290 Jadi semua aku benar-benar lakukan adalah menciptakan pointer lain untuk itu. 219 00:11:24,290 --> 00:11:28,210 Saya tidak mallocing tambahan ruang, hanya sekarang dua pointer 220 00:11:28,210 --> 00:11:31,370 menunjuk ke hal 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 Nah, tidak ada, jadi bukan aku akan pindah ke yang berikutnya. 223 00:11:37,220 --> 00:11:41,740 Jadi pada dasarnya saya akan mengatakan, trav sama trav berikutnya. 224 00:11:41,740 --> 00:11:43,630 Apakah 3 apa yang saya cari, tidak ada. 225 00:11:43,630 --> 00:11:45,780 Jadi saya terus pergi melalui, sampai akhirnya 226 00:11:45,780 --> 00:11:48,690 sampai ke 6 yang merupakan apa yang saya cari untuk didasarkan pada fungsi panggilan 227 00:11:48,690 --> 00:11:51,600 Saya memiliki di atas ada, dan jadi saya sudah selesai. 228 00:11:51,600 --> 00:11:54,150 >> Sekarang, bagaimana jika elemen aku cari tidak dalam daftar, 229 00:11:54,150 --> 00:11:55,510 apakah masih akan bekerja? 230 00:11:55,510 --> 00:11:57,120 Nah, perhatikan bahwa daftar di sini adalah agak berbeda, 231 00:11:57,120 --> 00:11:59,410 dan ini adalah hal lain yang penting dengan daftar terkait, 232 00:11:59,410 --> 00:12:01,780 Anda tidak perlu melestarikan mereka dalam urutan tertentu. 233 00:12:01,780 --> 00:12:05,390 Anda dapat jika Anda inginkan, tetapi Anda mungkin sudah menyadari 234 00:12:05,390 --> 00:12:09,310 bahwa kita tidak melacak apa elemen nomor kita di. 235 00:12:09,310 --> 00:12:13,150 >> Dan itu semacam salah satu perdagangan yang kita memiliki dengan linked list ayat array, 236 00:12:13,150 --> 00:12:15,300 apakah kita tidak memiliki akses acak lagi. 237 00:12:15,300 --> 00:12:18,150 Kita tidak bisa hanya mengatakan, saya ingin untuk pergi ke elemen 0, 238 00:12:18,150 --> 00:12:21,410 atau elemen 6 dari array saya, yang bisa saya lakukan dalam array. 239 00:12:21,410 --> 00:12:25,080 Saya tidak bisa mengatakan saya ingin pergi ke Elemen 0, atau elemen 6, 240 00:12:25,080 --> 00:12:30,360 atau elemen-25 daftar link saya, tidak ada indeks yang terkait dengan mereka. 241 00:12:30,360 --> 00:12:33,660 Dan sehingga tidak terlalu penting jika kita melestarikan daftar kami dalam rangka. 242 00:12:33,660 --> 00:12:36,080 Jika Anda ingin Anda pasti bisa, tapi ada 243 00:12:36,080 --> 00:12:38,567 tidak ada alasan mengapa mereka perlu dipertahankan dalam urutan apapun. 244 00:12:38,567 --> 00:12:40,400 Jadi sekali lagi, mari kita coba dan menemukan 6 dalam daftar ini. 245 00:12:40,400 --> 00:12:43,200 Nah, kita mulai di mulai, kita tidak menemukan 6, 246 00:12:43,200 --> 00:12:47,690 dan kemudian kita terus tidak menemukan 6, sampai kita akhirnya sampai ke sini. 247 00:12:47,690 --> 00:12:52,790 Jadi sekarang trav poin ke node mengandung 8, dan enam tidak di sana. 248 00:12:52,790 --> 00:12:55,250 >> Jadi langkah berikutnya akan untuk pergi ke pointer berikutnya, 249 00:12:55,250 --> 00:12:57,440 sehingga mengatakan trav sama trav berikutnya. 250 00:12:57,440 --> 00:13:00,750 Nah, trav berikutnya, ditandai dengan kotak merah ada, adalah null. 251 00:13:00,750 --> 00:13:03,020 Jadi ada tempat lain untuk pergi, dan pada titik ini 252 00:13:03,020 --> 00:13:06,120 kita dapat menyimpulkan bahwa kami telah mencapai akhir linked list, 253 00:13:06,120 --> 00:13:07,190 dan 6 tidak di sana. 254 00:13:07,190 --> 00:13:10,980 Dan itu akan dikembalikan palsu dalam kasus ini. 255 00:13:10,980 --> 00:13:14,540 >> OK, bagaimana kita memasukkan baru simpul ke dalam linked list? 256 00:13:14,540 --> 00:13:17,310 Jadi kita sudah mampu menciptakan linked list entah dari mana, 257 00:13:17,310 --> 00:13:19,370 tapi kami mungkin ingin membangun rantai dan tidak 258 00:13:19,370 --> 00:13:22,620 membuat sekelompok daftar yang berbeda. 259 00:13:22,620 --> 00:13:25,700 Kami ingin memiliki satu daftar yang memiliki banyak node di dalamnya, 260 00:13:25,700 --> 00:13:28,040 tidak banyak daftar dengan node tunggal. 261 00:13:28,040 --> 00:13:31,260 Jadi kita tidak bisa terus menggunakan Buat Fungsi kita ditetapkan sebelumnya, sekarang kita 262 00:13:31,260 --> 00:13:33,860 ingin memasukkan ke dalam daftar yang sudah ada. 263 00:13:33,860 --> 00:13:36,499 >> Jadi hal ini, kita akan untuk lulus dalam dua argumen, 264 00:13:36,499 --> 00:13:39,290 pointer ke kepala yang linked list yang ingin kita tambahkan ke. 265 00:13:39,290 --> 00:13:40,910 Sekali lagi, itu mengapa begitu penting bahwa kita selalu 266 00:13:40,910 --> 00:13:43,400 melacak, karena itu satu-satunya cara kita benar-benar 267 00:13:43,400 --> 00:13:46,690 harus mengacu pada seluruh daftar adalah hanya dengan pointer ke elemen pertama. 268 00:13:46,690 --> 00:13:49,360 Jadi kami ingin lulus dalam pointer ke elemen pertama, 269 00:13:49,360 --> 00:13:52,226 dan nilai yang kita apa pun ingin menambah daftar. 270 00:13:52,226 --> 00:13:54,600 Dan akhirnya fungsi ini akan kembali pointer 271 00:13:54,600 --> 00:13:57,980 dengan kepala baru dari linked list. 272 00:13:57,980 --> 00:13:59,700 >> Apa langkah-langkah yang terlibat di sini? 273 00:13:59,700 --> 00:14:02,249 Nah, seperti dengan membuat, kita perlu mengalokasikan secara dinamis 274 00:14:02,249 --> 00:14:05,540 ruang untuk node baru, dan periksa untuk memastikan yakin kita tidak kehabisan memori, sekali lagi, 275 00:14:05,540 --> 00:14:07,150 karena kita menggunakan malloc. 276 00:14:07,150 --> 00:14:09,080 Kemudian kita ingin mengisi dan masukkan node, 277 00:14:09,080 --> 00:14:12,730 sehingga menempatkan angka, apa pun val adalah, dalam node. 278 00:14:12,730 --> 00:14:17,310 Kami ingin memasukkan node di awal linked list. 279 00:14:17,310 --> 00:14:19,619 >> Ada alasan bahwa saya ingin melakukan ini, dan itu 280 00:14:19,619 --> 00:14:21,910 mungkin layak mengambil kedua untuk menghentikan video di sini, 281 00:14:21,910 --> 00:14:25,860 dan berpikir tentang mengapa saya ingin masukkan pada awal terkait 282 00:14:25,860 --> 00:14:26,589 daftar. 283 00:14:26,589 --> 00:14:28,630 Sekali lagi, saya sebutkan sebelumnya bahwa itu tidak benar-benar 284 00:14:28,630 --> 00:14:33,020 masalah jika kita melestarikannya dalam order, jadi mungkin itu petunjuk. 285 00:14:33,020 --> 00:14:36,040 Dan Anda melihat apa yang akan terjadi jika kita ingin to-- atau dari hanya satu detik 286 00:14:36,040 --> 00:14:37,360 lalu ketika kami akan melalui pencarian Anda 287 00:14:37,360 --> 00:14:39,235 bisa melihat apa yang mungkin terjadi jika kita mencoba 288 00:14:39,235 --> 00:14:41,330 untuk menyisipkan pada akhir daftar. 289 00:14:41,330 --> 00:14:44,750 Karena kita tidak memiliki pointer ke akhir daftar. 290 00:14:44,750 --> 00:14:47,490 >> Jadi alasan bahwa saya ingin untuk menyisipkan di awal, 291 00:14:47,490 --> 00:14:49,380 adalah karena saya bisa melakukannya segera. 292 00:14:49,380 --> 00:14:52,730 Saya memiliki pointer di awal, dan kita akan melihat ini dalam visual dalam satu detik. 293 00:14:52,730 --> 00:14:55,605 Tapi jika saya ingin memasukkan di akhir, Saya harus mulai dari awal, 294 00:14:55,605 --> 00:14:58,760 melintasi semua jalan ke akhir, dan kemudian taktik pada. 295 00:14:58,760 --> 00:15:01,420 Jadi itu berarti bahwa memasukkan pada akhir daftar 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 diskusi kami kompleksitas komputasi. 298 00:15:06,720 --> 00:15:10,140 Ini akan menjadi o operasi n, di mana sebagai daftar menjadi lebih besar, dan lebih besar, 299 00:15:10,140 --> 00:15:13,310 dan lebih besar, itu akan menjadi lebih dan lebih sulit untuk memakukan sesuatu 300 00:15:13,310 --> 00:15:14,661 pada di akhir. 301 00:15:14,661 --> 00:15:17,410 Tapi selalu benar-benar mudah untuk taktik sesuatu di di awal, 302 00:15:17,410 --> 00:15:19,060 Anda selalu di awal. 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 setelah kami selesai, setelah kami telah dimasukkan node baru, 305 00:15:24,100 --> 00:15:26,880 kami ingin kembali pointer untuk kepala baru dari linked list, yang 306 00:15:26,880 --> 00:15:29,213 karena kita sedang memasukkan di mulai, akan benar-benar 307 00:15:29,213 --> 00:15:31,060 pointer ke node yang baru kita buat. 308 00:15:31,060 --> 00:15:33,280 Mari kita memvisualisasikan ini, karena saya pikir itu akan membantu. 309 00:15:33,280 --> 00:15:36,661 >> Jadi, inilah daftar kami, terdiri dari empat unsur, node yang mengandung 15, 310 00:15:36,661 --> 00:15:38,410 yang menunjuk ke node mengandung 9, yang 311 00:15:38,410 --> 00:15:41,370 menunjuk ke node yang mengandung 13, yang menunjuk ke node yang mengandung 312 00:15:41,370 --> 00:15:44,840 10, yang memiliki nol pointer sebagai pointer berikutnya 313 00:15:44,840 --> 00:15:47,010 jadi itu akhir daftar. 314 00:15:47,010 --> 00:15:50,200 Jadi kita ingin menyisipkan node baru dengan nilai 12 315 00:15:50,200 --> 00:15:52,720 pada awal ini daftar, apa yang kita lakukan? 316 00:15:52,720 --> 00:15:58,770 Yah, pertama kita malloc ruang untuk node, dan kemudian kami menempatkan 12 di sana. 317 00:15:58,770 --> 00:16:02,211 >> Jadi sekarang kita sudah mencapai titik keputusan, kan? 318 00:16:02,211 --> 00:16:03,960 Kami memiliki beberapa pointer yang kita bisa 319 00:16:03,960 --> 00:16:06,770 bergerak, mana yang harus kita bergerak pertama? 320 00:16:06,770 --> 00:16:09,250 Haruskah kita membuat 12 poin untuk kepala baru list-- yang 321 00:16:09,250 --> 00:16:13,020 atau permisi, kita harus membuat 12 menunjuk ke kepala lama daftar? 322 00:16:13,020 --> 00:16:15,319 Atau harus kita katakan bahwa daftar sekarang dimulai pada 12. 323 00:16:15,319 --> 00:16:17,110 Ada perbedaan ada, dan kita akan melihat 324 00:16:17,110 --> 00:16:19,870 apa yang terjadi dengan kedua dalam detik. 325 00:16:19,870 --> 00:16:23,350 >> Tapi ini mengarah ke topik besar untuk sidebar, 326 00:16:23,350 --> 00:16:26,280 yaitu bahwa salah satu hal paling sulit dengan daftar terkait 327 00:16:26,280 --> 00:16:30,980 adalah untuk mengatur pointer dalam urutan yang benar. 328 00:16:30,980 --> 00:16:34,520 Jika Anda memindahkan barang-barang rusak, Anda dapat berakhir sengaja 329 00:16:34,520 --> 00:16:36,050 orphaning sisa daftar. 330 00:16:36,050 --> 00:16:37,300 Dan inilah contoh dari itu. 331 00:16:37,300 --> 00:16:40,540 Jadi mari kita pergi dengan ide of-- baik, kita baru saja membuat 12. 332 00:16:40,540 --> 00:16:43,180 Kita tahu 12 akan menjadi kepala baru dari daftar, 333 00:16:43,180 --> 00:16:47,660 dan jadi mengapa tidak kita hanya bergerak daftar pointer ke titik di sana. 334 00:16:47,660 --> 00:16:49,070 >> OK, jadi itu bagus. 335 00:16:49,070 --> 00:16:51,560 Jadi sekarang di mana tidak 12 titik berikutnya? 336 00:16:51,560 --> 00:16:54,580 Maksudku, secara visual kita dapat melihat bahwa ia akan menunjuk ke 15, 337 00:16:54,580 --> 00:16:57,250 sebagai manusia itu benar-benar jelas bagi kita. 338 00:16:57,250 --> 00:17:00,300 Bagaimana komputer tahu? 339 00:17:00,300 --> 00:17:02,720 Kami tidak punya apa-apa menunjuk ke 15 lagi, kan? 340 00:17:02,720 --> 00:17:05,869 >> Kami telah kehilangan setiap kemampuan untuk merujuk ke 15. 341 00:17:05,869 --> 00:17:11,460 Kita tidak bisa mengatakan panah baru equals berikutnya sesuatu, tidak ada ada. 342 00:17:11,460 --> 00:17:13,510 Bahkan, kami sudah yatim sisa daftar 343 00:17:13,510 --> 00:17:16,465 dengan demikian, kami telah sengaja rusak rantai. 344 00:17:16,465 --> 00:17:18,089 Dan kita tentu tidak ingin melakukan itu. 345 00:17:18,089 --> 00:17:20,000 >> Jadi mari kita kembali dan mencoba lagi ini. 346 00:17:20,000 --> 00:17:24,060 Mungkin hal yang benar untuk dilakukan adalah untuk mengatur 12 ini pointer berikutnya 347 00:17:24,060 --> 00:17:28,290 kepala lama daftar pertama, maka kita dapat memindahkan daftar lebih. 348 00:17:28,290 --> 00:17:30,420 Dan pada kenyataannya, itu adalah urutan yang benar bahwa kita 349 00:17:30,420 --> 00:17:32,836 harus mengikuti ketika kita bekerja dengan daftar sendiri-sendiri terkait. 350 00:17:32,836 --> 00:17:36,460 Kami selalu ingin menghubungkan elemen baru ke dalam daftar, 351 00:17:36,460 --> 00:17:41,010 sebelum kita mengambil semacam langkah penting untuk mengubah 352 00:17:41,010 --> 00:17:43,360 di mana kepala linked list adalah. 353 00:17:43,360 --> 00:17:46,740 Sekali lagi, itu suatu hal yang mendasar, kita tidak ingin kehilangan jejak itu. 354 00:17:46,740 --> 00:17:49,310 >> Jadi kami ingin memastikan bahwa semuanya dirantai bersama-sama, 355 00:17:49,310 --> 00:17:52,040 sebelum kita bergerak pointer itu. 356 00:17:52,040 --> 00:17:55,300 Dan jadi ini akan menjadi urutan yang benar, yang menghubungkan 12 ke dalam daftar, 357 00:17:55,300 --> 00:17:57,630 kemudian mengatakan bahwa daftar dimulai 12. 358 00:17:57,630 --> 00:18:00,860 Jika kita mengatakan daftar dimulai pada 12 dan kemudian mencoba untuk menghubungkan 12 ke dalam daftar, 359 00:18:00,860 --> 00:18:02,193 yang telah kita lihat apa yang terjadi. 360 00:18:02,193 --> 00:18:04,920 Kami kehilangan daftar dengan kesalahan. 361 00:18:04,920 --> 00:18:06,740 >> OK, jadi satu hal lagi untuk dibicarakan. 362 00:18:06,740 --> 00:18:09,750 Bagaimana jika kita ingin menyingkirkan seluruh linked list sekaligus? 363 00:18:09,750 --> 00:18:11,750 Sekali lagi, kita mallocing semua ruang ini, dan jadi kami 364 00:18:11,750 --> 00:18:13,351 perlu membebaskan ketika kita sudah selesai. 365 00:18:13,351 --> 00:18:15,350 Jadi sekarang kita ingin menghapus seluruh linked list. 366 00:18:15,350 --> 00:18:16,850 Nah, apa yang kita ingin lakukan? 367 00:18:16,850 --> 00:18:20,460 >> Jika kita sudah mencapai pointer null, kita ingin berhenti, jika tidak, hapus saja 368 00:18:20,460 --> 00:18:23,420 sisa daftar, kemudian membebaskan saya. 369 00:18:23,420 --> 00:18:28,890 Hapus sisanya dari daftar, dan kemudian membebaskan node saat. 370 00:18:28,890 --> 00:18:32,850 Apa yang terdengar seperti, Teknik apa yang harus kita berbicara 371 00:18:32,850 --> 00:18:35,440 tentang sebelumnya apakah itu terdengar seperti? 372 00:18:35,440 --> 00:18:39,560 Hapus orang lain, maka kembali dan menghapus saya. 373 00:18:39,560 --> 00:18:42,380 >> Itu rekursi, kami telah membuat masalah sedikit lebih kecil, 374 00:18:42,380 --> 00:18:46,910 kita mengatakan menghapus semua lain, maka Anda dapat menghapus saya. 375 00:18:46,910 --> 00:18:50,940 Dan lebih lanjut di jalan, node yang akan mengatakan, menghapus orang lain. 376 00:18:50,940 --> 00:18:53,940 Tapi akhirnya kita akan sampai ke titik di mana daftar adalah null, 377 00:18:53,940 --> 00:18:55,310 dan itulah kasus dasar kami. 378 00:18:55,310 --> 00:18:57,010 >> Jadi mari kita lihat ini, dan bagaimana ini bisa bekerja. 379 00:18:57,010 --> 00:18:59,759 Jadi, inilah daftar kami, itu sama daftar kami hanya berbicara 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, tapi mudah-mudahan visualisasi akan membantu. 382 00:19:04,200 --> 00:19:08,557 >> Jadi kita have-- dan saya juga ditarik up kami tumpukan frame ilustrasi 383 00:19:08,557 --> 00:19:10,890 dari video kami pada tumpukan panggilan, dan mudah-mudahan semua ini 384 00:19:10,890 --> 00:19:13,260 bersama-sama akan menunjukkan apa yang terjadi. 385 00:19:13,260 --> 00:19:14,510 Jadi, inilah kode pseudo kami. 386 00:19:14,510 --> 00:19:17,830 Jika kita mencapai null pointer, berhenti, jika tidak, 387 00:19:17,830 --> 00:19:21,320 menghapus sisanya dari daftar, kemudian membebaskan node saat ini. 388 00:19:21,320 --> 00:19:25,700 Jadi sekarang, list-- pointer yang kami 389 00:19:25,700 --> 00:19:28,410 lewat di untuk menghancurkan poin ke 12. 390 00:19:28,410 --> 00:19:33,340 12 tidak pointer nol, jadi kita akan menghapus sisa daftar. 391 00:19:33,340 --> 00:19:35,450 >> Apa yang menghapus sisa dari kita yang terlibat? 392 00:19:35,450 --> 00:19:37,950 Nah, itu berarti membuat panggilan untuk menghancurkan, mengatakan 393 00:19:37,950 --> 00:19:42,060 bahwa 15 adalah awal dari sisa daftar kami ingin menghancurkan. 394 00:19:42,060 --> 00:19:47,480 Dan panggilan untuk menghancurkan 12 adalah jenis ditahan. 395 00:19:47,480 --> 00:19:52,690 Ini beku di sana, menunggu panggilan untuk menghancurkan 15, untuk menyelesaikan tugasnya. 396 00:19:52,690 --> 00:19:56,280 >> Nah, 15 tidak null pointer, dan sehingga akan mengatakan, baiklah, 397 00:19:56,280 --> 00:19:58,450 baik, menghapus sisa daftar. 398 00:19:58,450 --> 00:20:00,760 Sisa daftar dimulai di 9, dan jadi kami hanya akan 399 00:20:00,760 --> 00:20:04,514 tunggu sampai Anda menghapus semua yang hal, kemudian kembali dan menghapus saya. 400 00:20:04,514 --> 00:20:06,680 Nah 9 akan mengatakan, baik, Aku bukan pointer null, 401 00:20:06,680 --> 00:20:09,020 sehingga menghapus sisanya daftar dari sini. 402 00:20:09,020 --> 00:20:11,805 Dan jadi coba dan menghancurkan 13. 403 00:20:11,805 --> 00:20:15,550 13 kata, aku tidak null pointer, Hal yang sama, melewati buck. 404 00:20:15,550 --> 00:20:17,930 10 tidak null pointer, 10 mengandung pointer null, 405 00:20:17,930 --> 00:20:20,200 tapi 10 tidak sendiri merupakan nol pointer sekarang, 406 00:20:20,200 --> 00:20:22,470 dan melewati uang juga. 407 00:20:22,470 --> 00:20:25,560 >> Dan sekarang daftar poin di sana, itu benar-benar akan menunjuk ke some-- 408 00:20:25,560 --> 00:20:28,710 jika saya memiliki lebih banyak ruang dalam gambar, itu akan menunjuk ke beberapa ruang acak 409 00:20:28,710 --> 00:20:29,960 bahwa kita tidak tahu apa itu. 410 00:20:29,960 --> 00:20:34,680 Ini adalah pointer nol meskipun, daftar secara harfiah sekarang ditetapkan itu nilai null. 411 00:20:34,680 --> 00:20:36,820 Itu menunjuk tepat di dalam kotak merah. 412 00:20:36,820 --> 00:20:39,960 Kami mencapai pointer nol, sehingga kita bisa berhenti, dan kami sudah selesai. 413 00:20:39,960 --> 00:20:46,230 >> Dan sehingga bingkai ungu adalah sekarang-- di atas stack-- itu frame aktif, 414 00:20:46,230 --> 00:20:47,017 tapi itu dilakukan. 415 00:20:47,017 --> 00:20:48,600 Jika kita sudah mencapai null pointer, berhenti. 416 00:20:48,600 --> 00:20:51,290 Kami tidak melakukan apa-apa, kita tidak bisa membebaskan pointer null, 417 00:20:51,290 --> 00:20:55,070 kami tidak malloc apapun ruang, dan jadi kita sudah selesai. 418 00:20:55,070 --> 00:20:57,590 Sehingga bingkai fungsi hancur, dan kami 419 00:20:57,590 --> 00:21:00,930 resume-- kami mengambil tempat kami meninggalkan off dengan yang berikutnya tertinggi, yang 420 00:21:00,930 --> 00:21:02,807 adalah ini bingkai biru tua di sini. 421 00:21:02,807 --> 00:21:04,390 Jadi kami mengambil tepat di mana kita tinggalkan. 422 00:21:04,390 --> 00:21:06,598 Kami menghapus sisa daftar sudah, jadi sekarang kita 423 00:21:06,598 --> 00:21:08,000 akan membebaskan node saat ini. 424 00:21:08,000 --> 00:21:12,920 Jadi sekarang kita bisa bebas node ini, dan sekarang kita telah mencapai akhir dari fungsi. 425 00:21:12,920 --> 00:21:16,810 Dan sehingga bingkai fungsi hancur, dan kami menjemput di satu biru muda. 426 00:21:16,810 --> 00:21:20,650 >> Jadi says-- saya sudah done-- menghapus sisa daftar, sehingga 427 00:21:20,650 --> 00:21:23,140 membebaskan node saat ini. 428 00:21:23,140 --> 00:21:26,520 Dan sekarang bingkai kuning kembali di atas tumpukan. 429 00:21:26,520 --> 00:21:29,655 Dan seperti yang Anda lihat, kami sekarang menghancurkan daftar 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 terjadi, meskipun, jika kita telah melakukan hal-hal dengan cara yang salah? 432 00:21:37,280 --> 00:21:39,410 Sama seperti ketika kita mencoba untuk menambahkan elemen. 433 00:21:39,410 --> 00:21:41,909 Jika kita kacau rantai, jika kami tidak menghubungkan pointer 434 00:21:41,909 --> 00:21:44,690 dalam urutan yang benar, jika kita hanya dibebaskan elemen pertama, 435 00:21:44,690 --> 00:21:47,420 jika kita hanya membebaskan Kepala daftar, sekarang kita 436 00:21:47,420 --> 00:21:49,642 tidak memiliki cara untuk merujuk sisa daftar. 437 00:21:49,642 --> 00:21:51,350 Dan sehingga kita akan memiliki semuanya yatim, 438 00:21:51,350 --> 00:21:53,880 kita akan memiliki apa yang disebut kebocoran memori. 439 00:21:53,880 --> 00:21:56,800 Jika Anda ingat dari video kami alokasi memori dinamis, 440 00:21:56,800 --> 00:21:58,650 itu tidak hal yang sangat baik. 441 00:21:58,650 --> 00:22:00,810 >> Jadi seperti yang saya katakan, ada beberapa operasi 442 00:22:00,810 --> 00:22:04,010 bahwa kita perlu menggunakan untuk bekerja dengan linked list efektif. 443 00:22:04,010 --> 00:22:08,430 Dan Anda mungkin telah memperhatikan saya dihilangkan satu, menghapus satu elemen dari linked 444 00:22:08,430 --> 00:22:09,064 daftar. 445 00:22:09,064 --> 00:22:10,980 Alasan saya melakukan itu itu sebenarnya semacam 446 00:22:10,980 --> 00:22:14,360 sulit untuk berpikir tentang bagaimana untuk menghapus satu elemen dari sendiri-sendiri 447 00:22:14,360 --> 00:22:15,600 linked list. 448 00:22:15,600 --> 00:22:19,950 Kita harus mampu untuk melewatkan sesuatu dalam daftar, yang 449 00:22:19,950 --> 00:22:22,975 berarti kita bisa kita point-- ingin menghapus node-- ini 450 00:22:22,975 --> 00:22:25,350 tetapi untuk membuatnya jadi kita tidak kehilangan informasi apapun, 451 00:22:25,350 --> 00:22:30,530 kita perlu menghubungkan ini simpul di sini, di sini. 452 00:22:30,530 --> 00:22:33,390 >> Jadi saya mungkin melakukan itu salah dari perspektif visual. 453 00:22:33,390 --> 00:22:36,830 Jadi kita di awal kami daftar, kita melanjutkan melalui, 454 00:22:36,830 --> 00:22:40,510 kita ingin menghapus node ini. 455 00:22:40,510 --> 00:22:43,440 Jika kita hanya menghapusnya, kami telah rusak rantai. 456 00:22:43,440 --> 00:22:45,950 Simpul ini di sini mengacu pada segala sesuatu yang lain, 457 00:22:45,950 --> 00:22:48,260 mengandung rantai pada keluar dari sini. 458 00:22:48,260 --> 00:22:51,190 >> Jadi apa yang perlu kita lakukan benar-benar setelah kami sampai ke titik ini, 459 00:22:51,190 --> 00:22:56,670 adalah kita harus melangkah mundur satu, dan menghubungkan node ini ke node ini, 460 00:22:56,670 --> 00:22:58,590 sehingga kita kemudian dapat menghapus satu di tengah. 461 00:22:58,590 --> 00:23:02,120 Tapi daftar tunggal terkait tidak memberikan kami cara untuk pergi ke belakang. 462 00:23:02,120 --> 00:23:05,160 Jadi kita perlu menjaga baik dua pointer, dan memindahkan mereka 463 00:23:05,160 --> 00:23:09,527 semacam off langkah, satu di belakang lain seperti yang kita pergi, atau sampai ke titik 464 00:23:09,527 --> 00:23:11,110 dan kemudian mengirim pointer lain melalui. 465 00:23:11,110 --> 00:23:13,150 Dan seperti yang Anda lihat, itu bisa mendapatkan sedikit berantakan. 466 00:23:13,150 --> 00:23:15,360 Untungnya, kita memiliki cara lain untuk menyelesaikan itu, 467 00:23:15,360 --> 00:23:17,810 ketika kita berbicara tentang daftar ganda terkait. 468 00:23:17,810 --> 00:23:20,720 >> Aku Doug Lloyd, ini CS50. 469 00:23:20,720 --> 00:23:22,298