[Powered by Google Translate] Dalam pengaturcaraan, kita sering perlu untuk mewakili senarai nilai-nilai, seperti nama pelajar di dalam seksyen atau skor mereka pada kuiz terbaru. 

Dalam bahasa C, mengisytiharkan tatasusunan boleh digunakan untuk menyimpan senarai. Ia mudah untuk menghitung unsur senarai disimpan di dalam array, dan jika anda perlu untuk mengakses atau mengubahsuai elemen senarai engan bagi indeks beberapa sembarangan Saya, yang boleh dilakukan dalam masa yang berterusan, tetapi array mempunyai kelemahan, terlalu. 

Apabila kita mengaku mereka, kita dikehendaki untuk mengatakan depan bagaimana besar mereka, iaitu, berapa banyak elemen mereka boleh menyimpan dan bagaimana besar elemen-elemen ini, yang ditentukan oleh jenis mereka. Sebagai contoh, int arr (10) boleh menyimpan 10 item yang saiz int. 

Kita tidak boleh mengubah saiz pelbagai selepas perisytiharan. Kita perlu membuat pelbagai baru jika kita mahu menyimpan lebih banyak elemen. Sebab had ini wujud adalah bahawa kami program menyimpan pelbagai keseluruhan sebagai sebahagian berdampingan ingatan. Katakanlah ini adalah penampan di mana kita disimpan dalam pelbagai kami. Mungkin ada pembolehubah lain terletak betul-betul bersebelahan dengan array dalam ingatan, jadi kita tidak boleh hanya membuat array besar. 

Kadang-kadang kita ingin perdagangan akses data kelajuan cepat array untuk fleksibiliti yang lebih sedikit. Masukkan senarai yang berkaitan, satu lagi struktur data asas anda mungkin tidak seperti biasa dengan. Pada tahap yang tinggi, senarai yang dipautkan menyimpan data dalam jujukan nod yang bersambung antara satu sama lain dengan pautan, maka nama 'senarai berkaitan.' Seperti yang kita akan lihat, ini perbezaan dalam reka bentuk membawa kepada kelebihan dan kelemahan yang berbeza daripada array. 

Berikut adalah beberapa kod C untuk senarai yang sangat mudah dikaitkan integer. Anda boleh melihat bahawa kita telah diwakili setiap nod dalam senarai sebagai struct yang mengandungi 2 perkara, integer untuk menyimpan dipanggil 'Val' dan link ke nod seterusnya dalam senarai yang kita mewakili sebagai penunjuk dipanggil 'seterusnya'. Dengan cara ini, kita boleh menjejaki seluruh senarai dengan hanya penunjuk tunggal kepada nod 1, dan kemudian kita boleh mengikuti petunjuk seterusnya kepada nod 2, kepada nod 3, kepada nod 4, dan sebagainya, sehingga kita sampai ke akhir senarai. 

Anda mungkin dapat melihat 1 kesempatan ini mempunyai lebih struktur pelbagai statik - dengan senarai dikaitkan, kita tidak perlu sebahagian besar daripada ingatan sama sekali. Nod 1 senarai boleh hidup di tempat ini dalam ingatan, dan nod 2 boleh menjadi semua cara di sini. Kita boleh sampai ke semua nod tidak kira di mana dalam ingatan mereka, kerana bermula pada nod 1, penunjuk setiap nod seterusnya memberitahu kita betul-betul di mana untuk pergi seterusnya. 

Selain itu, kita tidak perlu untuk mengatakan di depan berapa besar senarai yang dipautkan akan menjadi cara kita lakukan dengan barisan statik, kerana kita boleh menyimpan menambah nod ke senarai selagi ada ruang tempat dalam ingatan untuk nod baru. Oleh itu, senarai berkaitan adalah mudah untuk mengubah saiz dinamik. Katakanlah (wahai Muhammad), kemudian dalam program ini kita perlu menambah lebih nod ke dalam senarai kami. Untuk memasukkan nod baru ke dalam senarai kami on the fly, semua yang perlu kita lakukan adalah memperuntukkan memori untuk nod tersebut, mencebur dalam nilai data, dan kemudian meletakkannya di mana kita mahu dengan menyesuaikan petunjuk yang sesuai. 

Sebagai contoh, jika kita mahu meletakkan nod di antara nod 2 dan 3 senarai,  kita tidak akan mempunyai untuk bergerak nod yang ke-2 atau ke-3 pada semua. Katakanlah kita memasukkan ini nod merah. Semua kita akan perlu lakukan adalah menetapkan penunjuk nod seterusnya baru untuk menunjuk kepada nod 3 dan kemudian rewire penunjuk seterusnya nod 2 untuk menunjukkan kepada nod baru kami. Jadi, kita boleh mengubah saiz senarai kami on the fly sejak komputer kita tidak bergantung pada pengindeksan, tetapi menghubungkan menggunakan petunjuk untuk menyimpan mereka. 

Walau bagaimanapun, kelemahan dikaitkan senarai adalah bahawa, tidak seperti pelbagai statik, komputer tidak boleh hanya melompat ke tengah-tengah senarai. Sejak komputer untuk melawat setiap nod dalam senarai berkaitan untuk mendapatkan satu depan, ia akan mengambil masa yang lama untuk mencari nod tertentu daripada ia akan dalam array. Untuk merentasi seluruh senarai mengambil masa berkadar panjang senarai, atau O (n) dalam notasi asimptot. Pada purata, sampai ke mana-mana nod juga mengambil masa berkadar dengan n. 

Sekarang, mari kita sebenarnya menulis beberapa kod yang bekerja dengan senarai yang dipautkan. Katakan kita mahu senarai dikaitkan integer. Kita boleh mewakili nod dalam senarai kami lagi sebagai struct dengan 2 bidang, nilai integer dipanggil 'Val' dan penunjuk sebelah nod seterusnya senarai. Nah, seolah-olah cukup mudah. 

Katakan kita mahu menulis fungsi yang merentasi senarai dan mencetak keluar nilai yang disimpan di dalam nod terakhir senarai. Nah, itu bermakna kita perlu merentasi semua nod dalam senarai untuk mencari satu lepas, tetapi kerana kita tidak menambah atau memadam apa-apa, kita tidak mahu berubah struktur dalaman petunjuk seterusnya dalam senarai. 

Jadi, kita perlukan penunjuk khusus untuk penyusuran yang kita akan panggil 'crawler'. Ia akan merangkak melalui semua elemen senarai dengan berikutan rantaian petunjuk seterusnya. Semua kita telah disimpan adalah penunjuk kepada nod 1, atau 'kepala' senarai. Ketua mata kepada nod 1. Ia adalah jenis penunjuk-to-nod. 

Untuk mendapatkan sebenar 1 nod dalam senarai, kita mempunyai untuk dereference penunjuk ini, tetapi sebelum kita boleh dereference, kita perlu menyemak jika penunjuk nol pertama. Jika ia adalah batal, senarai adalah kosong, dan kita harus mencetak mesej itu, kerana senarai adalah kosong, tiada nod terakhir. Tetapi, mari kita mengatakan senarai tidak kosong. Jika tidak, maka kita perlu merangkak melalui senarai keseluruhan sehingga kita dapat nod terakhir senarai, dan bagaimana kita boleh memberitahu jika kita sedang melihat nod terakhir dalam senarai? 

Nah, jika penunjuk nod seterusnya adalah batal, kita tahu kita berada di akhir sejak penunjuk seterusnya terakhir akan tidak mempunyai nod seterusnya dalam senarai untuk menunjukkan. Ia adalah amalan yang baik untuk sentiasa menyimpan penunjuk seterusnya nod terakhir dimulakan untuk menyeimbangkan mempunyai harta standard yang memberitahu kita apabila kita telah sampai ke penghujung senarai. 

Jadi, jika crawler → seterusnya adalah batal, ingat bahawa sintaks arrow adalah jalan pintas untuk dereferencing penunjuk untuk struct, maka mengakses bersebelahan bidang yang bersamaan dengan yang janggal: (* Crawler). Seterusnya. Apabila kita dapati nod terakhir, kita mahu untuk mencetak crawler → Val, nilai dalam nod semasa yang kita tahu adalah yang terakhir. Jika tidak, jika kita tidak berada lagi di nod terakhir dalam senarai, kita perlu bergerak ke nod seterusnya dalam senarai dan memeriksa jika itulah yang terakhir. Untuk melakukan ini, kita hanya menetapkan penunjuk crawler kami untuk menunjukkan nilai seterusnya nod semasa, yang, nod seterusnya dalam senarai. Ini dilakukan dengan menetapkan crawler = crawler → depan. Kemudian kita mengulangi proses ini, dengan gelung misalnya, sehingga kita dapati nod terakhir. Maka, misalnya, jika crawler menunjuk ke kepala, kita tetapkan crawler untuk menunjukkan kepada crawler → seterusnya, yang sama seperti medan seterusnya nod 1. Jadi, sekarang crawler kami menunjuk kepada nod 2, dan, sekali lagi, kita mengulangi ini dengan gelung, sehingga kita dapati nod terakhir, iaitu, mana penunjuk nod seterusnya menunjuk untuk menyeimbangkan. Dan ada kita mempunyai, kita dapati nod terakhir dalam senarai, dan untuk mencetak nilainya, kita hanya menggunakan crawler → Val. 

Menyeberangi tidak begitu buruk, tetapi bagaimana pula dengan memasukkan? Katakanlah kita mahu untuk memasukkan integer ke kedudukan ke-4 dalam senarai integer. Itu adalah antara nod 3 dan 4 semasa. Sekali lagi, kita perlu merentasi senarai hanya untuk sampai ke elemen 3, satu yang kita memasukkan selepas. Jadi, kita mewujudkan penunjuk crawler lagi untuk merentasi senarai, memeriksa jika penunjuk kepala kita adalah batal, dan jika ia tidak, titik penunjuk crawler kami di nod kepala. Jadi, kita berada pada elemen 1. Kita perlu pergi ke hadapan 2 lebih elemen sebelum kita boleh memasukkan, jadi kita boleh gunakan untuk gelung int i = 1; i <3; i + + dan dalam setiap lelaran gelung, memajukan penunjuk crawler kami ke hadapan dengan nod 1 dengan memeriksa jika medan seterusnya nod semasa adalah batal, dan jika ia tidak, bergerak penunjuk crawler kami ke nod seterusnya dengan menetapkan ia bersamaan dengan penunjuk nod seterusnya semasa. Jadi, sejak gelung untuk kita mengatakan untuk berbuat demikian dua kali, kita telah mencapai nod 3, dan sekali penunjuk crawler kami telah mencapai nod selepas yang kita mahu untuk memasukkan integer baru kami, bagaimana kita sebenarnya memasukkan? 

Nah, integer baru kami akan dimasukkan ke dalam senarai sebagai sebahagian daripada struct nod sendiri, kerana ini adalah benar-benar satu jujukan nod. Jadi, mari kita membuat penunjuk baru kepada nod dipanggil 'new_node,' dan menetapkan ia untuk menunjukkan ingatan bahawa kita kini memperuntukkan pada timbunan untuk nod sendiri, dan berapa banyak memori yang kita perlu memperuntukkan? Nah, saiz nod, dan kita mahu untuk menetapkan bidang Val kepada integer yang kita mahu untuk memasukkan. Katakan, 6. Sekarang, nod mengandungi nilai integer kami. Ia juga amalan yang baik untuk memulakan medan seterusnya nod baru untuk menunjukkan untuk menyeimbangkan, tetapi sekarang apa? 

Kita perlu menukar struktur dalaman senarai dan petunjuk seterusnya yang terkandung di dalam senarai yang sedia ada Nod 3 dan 4. Sejak petunjuk seterusnya menentukan perintah senarai, dan kerana kita sedang memasukkan nod baru kami kanan ke tengah-tengah senarai, ia boleh menjadi sedikit sukar. Ini adalah kerana, ingat, komputer kita hanya tahu lokasi nod dalam senarai kerana petunjuk seterusnya disimpan di dalam nod sebelumnya. Jadi, jika kita pernah hilang mengesan mana-mana lokasi, mengatakan dengan menukar salah satu petunjuk yang seterusnya dalam senarai kami, contoh, katakan kita berubah nod 3 bidang depan untuk menunjukkan kepada beberapa nod di sini. Kita akan keluar nasib, kerana kita tidak akan mempunyai apa-apa idea di mana untuk mencari seluruh senarai, dan itulah jelas benar-benar buruk. Jadi, kita perlu benar-benar berhati-hati mengenai perintah itu di mana kita memanipulasi petunjuk seterusnya kami semasa kemasukan. 

Jadi, untuk memudahkan ini, katakan bahawa kami first 4 nod dipanggil A, B, C, dan D, dengan anak panah mewakili rantaian petunjuk yang menghubungkan nod. Jadi, kita perlu memasukkan nod baru kami di antara nod C dan D. Ia adalah penting untuk melakukannya dalam susunan yang betul, dan saya akan menunjukkan kepada anda mengapa. 

Mari kita melihat dengan cara yang salah untuk melakukannya terlebih dahulu. Hei, kita tahu nod baru telah datang sejurus selepas C, jadi mari kita menetapkan penunjuk seterusnya C untuk menunjukkan untuk new_node. Baiklah, nampaknya okay, kita hanya perlu selesaikan sekarang dengan membuat titik penunjuk seterusnya nod baru kepada D, tetapi menunggu, bagaimana kita boleh berbuat demikian? Satu-satunya perkara yang boleh memberitahu kita di mana D, penunjuk seterusnya sebelum ini disimpan di C, tetapi kita hanya menulis semula penunjuk yang untuk menunjukkan kepada nod baru, supaya kita tidak lagi mempunyai sebarang petunjuk di mana D adalah dalam ingatan, dan kita telah kehilangan seluruh senarai. Tidak baik pada semua. 

Jadi, bagaimana kita melakukan hak ini? Pertama, titik penunjuk depan nod baru di D. Kini, kedua-dua baru nod dan C petunjuk seterusnya menunjuk kepada nod yang sama, D, tetapi itulah denda. Sekarang kita boleh titik penunjuk seterusnya C di nod baru. Jadi, kami telah melakukan ini tanpa kehilangan sebarang data. Dalam kod, C adalah nod semasa bahawa penyusuran pointer crawler menunjuk ke, dan D diwakili oleh nod ditunjukkan oleh medan seterusnya nod semasa, atau crawler → seterusnya. Jadi, kita mula-mula menetapkan penunjuk nod seterusnya baru untuk menunjukkan kepada crawler → seterusnya, cara yang sama kita berkata penunjuk seterusnya new_node menunjukkan D dalam ilustrasi. Kemudian, kita boleh menetapkan penunjuk nod seterusnya semasa nod baru kami, hanya kerana kami terpaksa menunggu untuk menunjukkan C untuk new_node dalam lukisan. Sekarang segala-galanya dalam perintah, dan kita tidak kehilangan mengesan apa-apa data, dan kita dapat hanya melekat nod baru kami di tengah-tengah senarai tanpa membina semula segala-galanya ataupun memindahkan sebarang unsur-unsur cara kita akan terpaksa dengan pelbagai panjang tetap. 

Jadi, senarai berkaitan adalah asas, tetapi penting, dinamik struktur data yang mempunyai kedua-dua kebaikan dan keburukan berbanding kepada barisan dan lain-lain struktur data, dan seperti yang sering berlaku dalam bidang sains komputer, ia adalah penting untuk tahu bila untuk menggunakan setiap alat, supaya anda boleh memilih alat yang tepat untuk kerja yang betul. 

Untuk amalan yang lebih, cuba menulis fungsi untuk memadam nod dari senarai berkaitan - ingat untuk berhati-hati mengenai perintah di mana anda menyusun semula petunjuk seterusnya anda untuk memastikan bahawa anda tidak kehilangan sebahagian senarai anda - atau fungsi untuk mengira nod dalam senarai berkaitan, atau satu keseronokan, mengakas perintah semua nod dalam senarai berkaitan. 

Nama saya adalah Jackson Steinkamp, ​​ini adalah CS50.