Apakah struktur data senarai terpaut?
Senarai terpaut ialah struktur storan tidak berterusan dan tidak berurutan pada unit storan fizikal Susunan logik elemen data direalisasikan melalui susunan pautan penunjuk dalam senarai terpaut struktur senarai linear Jadual yang dihasilkan dipanggil "senarai terpaut". Setiap elemen data dalam senarai terpaut terdiri daripada dua bahagian: 1. Maklumat itu sendiri, dipanggil "medan data" 2. Penunjuk kepada pengganti langsung, dipanggil "medan penunjuk". Kedua-dua bahagian maklumat ini membentuk struktur penyimpanan elemen data, yang dipanggil "nod"; n nod dipautkan antara satu sama lain melalui medan penunjuk untuk membentuk senarai terpaut.
Persekitaran pengendalian tutorial ini: sistem Windows 7, komputer Dell G3.
Struktur data ialah cara komputer menyimpan dan menyusun data. Struktur data merujuk kepada koleksi elemen data yang mempunyai satu atau lebih hubungan khusus antara satu sama lain. Selalunya, struktur data yang dipilih dengan teliti boleh membawa kepada kecekapan pengendalian atau penyimpanan yang lebih tinggi. Struktur data selalunya berkaitan dengan algoritma perolehan semula yang cekap dan teknik pengindeksan.
Senarai terpaut 链表
dalam struktur data ialah fizikal yang tidak berterusan dan tidak berurutan unit storan Struktur storan, susunan logik elemen data direalisasikan melalui susunan pautan penunjuk dalam senarai terpaut. Senarai terpaut terdiri daripada satu siri nod (setiap elemen dalam senarai terpaut dipanggil nod), dan nod boleh dijana secara dinamik pada masa jalan.
Data yang satu demi satu dalam struktur logik tidak bersebelahan antara satu sama lain seperti jadual jujukan apabila sebenarnya disimpan. Sebaliknya, data diedarkan secara rawak di pelbagai lokasi dalam memori Struktur storan ini dipanggil storan terpaut senarai linear.
Disebabkan storan terdesentralisasi, untuk menggambarkan hubungan logik antara elemen data, setiap elemen data mesti dilengkapi dengan penunjuk untuk menunjuk kepada elemen pengganti langsungnya, iaitu setiap elemen data elemen data seterusnya (yang terakhir menunjuk ke NULL (kosong)).
Seperti yang ditunjukkan dalam rajah di atas, apabila setiap elemen data dipautkan ke elemen data seterusnya dengan penunjuk, rantai terbentuk dan kepala rantai terletak dalam elemen data pertama, kaedah storan ini ialah storan rantai.
Jadual yang dijana oleh struktur storan terpaut senarai linear dipanggil "senarai terpaut".
Komposisi elemen data dalam senarai terpaut
Setiap elemen itu sendiri terdiri daripada dua bahagian:
itu sendiri Maklumat, dipanggil "medan data";
penunjuk kepada pengganti segera, dipanggil "medan penunjuk".
Dua bahagian maklumat ini membentuk struktur penyimpanan elemen data, yang dipanggil "nod". n nod dipautkan antara satu sama lain melalui medan penunjuk untuk membentuk senarai terpaut.
Nod kepala, penuding kepala dan nod pertama
Nod kepala: kadangkala, pada nod pertama dalam senarai terpaut Tambahan nod akan ditambah sebelum nod Medan data nod secara amnya tidak menyimpan data (dalam beberapa kes, ia juga boleh menyimpan maklumat seperti panjang senarai terpaut ini dipanggil nod kepala).
Jika medan penunjuk nod kepala ialah NULL, ini menunjukkan bahawa senarai terpaut ialah senarai kosong. Nod kepala tidak diperlukan untuk senarai terpaut Apabila menangani masalah tertentu, menambah nod kepala pada senarai terpaut akan menjadikan masalah lebih mudah.
Nod kepala: Nod tempat terletaknya elemen pertama dalam senarai terpaut Ia adalah nod pertama selepas nod kepala.
Penuding kepala: sentiasa menunjuk ke kedudukan nod pertama dalam senarai terpaut (jika senarai terpaut mempunyai nod kepala, penuding kepala menghala ke nod kepala; jika tidak, penuding kepala menghala ke nod pertama nod).
Perbezaan antara nod kepala dan penuding kepala: penuding kepala ialah penuding, yang menghala ke nod kepala atau nod pertama senarai terpaut ialah nod sebenar, yang Mengandungi data medan dan medan penunjuk. Manifestasi langsung kedua-duanya dalam program ini ialah penunjuk kepala hanya diisytiharkan tetapi tiada ruang storan diperuntukkan, dan nod kepala diisytiharkan dan memori fizikal sebenar sesuatu nod diperuntukkan.
Menggunakan struktur senarai terpaut boleh mengatasi kekurangan senarai terpaut tatasusunan yang saiz data perlu diketahui terlebih dahulu Struktur senarai terpaut boleh menggunakan sepenuhnya ruang memori komputer dan mencapai dinamik memori yang fleksibel. Walau bagaimanapun, senarai terpaut kehilangan kelebihan bacaan rawak tatasusunan Pada masa yang sama, senarai terpaut mempunyai overhed ruang yang agak besar disebabkan oleh peningkatan medan penunjuk nod. Faedah paling jelas bagi senarai terpaut ialah cara tatasusunan biasa menyusun item yang berkaitan mungkin berbeza daripada tertib item data ini disusun dalam ingatan atau pada cakera, dan akses kepada data selalunya memerlukan pertukaran antara susunan yang berbeza.
Ciri-ciri
Ciri perwakilan storan terpaut bagi jadual linear ialah menggunakan set unit storan arbitrari untuk menyimpan elemen data jadual linear (set unit storan ini boleh berterusan atau tidak berterusan). Oleh itu, untuk mewakili hubungan logik antara setiap elemen data dan elemen data pengganti langsungnya, untuk elemen data, selain menyimpan maklumatnya sendiri, ia juga perlu untuk menyimpan maklumat yang menunjukkan pengganti langsungnya (iaitu penyimpanan lokasi pengganti langsung). Kedua-dua maklumat ini membentuk "nod" (seperti yang ditunjukkan dalam rajah di bawah), yang mewakili elemen data dalam jadual linear. Satu kelemahan perwakilan storan terpaut bagi jadual linear ialah untuk mencari nombor, anda perlu bermula dari awal, yang sangat menyusahkan.
Mengikut situasi, anda juga boleh mereka sendiri sambungan lain senarai terpaut. Walau bagaimanapun, data secara amnya tidak dilampirkan pada tepi, kerana titik dan tepi senarai terpaut pada asasnya dalam surat-menyurat satu dengan satu (kecuali nod pertama atau terakhir, tetapi tiada keadaan khas akan berlaku). Walau bagaimanapun, satu kes khas ialah jika senarai terpaut menyokong penuding belakang depan dan belakang dalam bahagian senarai terpaut, mungkin lebih mudah untuk menambah tanda terbalik pada tepi.
Untuk senarai terpaut bukan linear, anda boleh merujuk kepada struktur data lain yang berkaitan, seperti pepohon dan graf. Terdapat juga struktur data berdasarkan senarai pautan berbilang linear: langkau senarai Kepantasan operasi asas seperti sisipan, pemadaman dan carian boleh mencapai O(nlogn), sama seperti pokok binari yang seimbang.
Domain yang menyimpan maklumat elemen data dipanggil domain data (biar nama domain sebagai data), dan domain yang menyimpan lokasi storan pengganti langsung dipanggil domain penunjuk (biar nama domain di sebelah) . Maklumat yang disimpan dalam medan penunjuk juga dipanggil penunjuk atau rantai.
Senarai terpaut yang terdiri daripada N nod yang masing-masing mewakili,,..., dipaut dalam urutan, dipanggil perwakilan storan terpaut bagi senarai linear, kerana setiap nod senarai terpaut tersebut hanya mengandungi satu penuding field , jadi ia juga dipanggil senarai pautan tunggal atau senarai pautan linear.
Sisipan dan pengalihan keluar nod daripada senarai terpaut
Senarai terpaut membenarkan sisipan dan pengalihan keluar nod pada sebarang kedudukan pada jadual, tetapi tidak membenarkan akses rawak.
1. Masukkan nod ke dalam senarai terpaut
Masukkan nod kepala ke dalam senarai terpaut, yang dibahagikan kepada 3 jenis mengikut kedudukan sisipan:
dimasukkan ke dalam kepala senarai terpaut, iaitu antara nod kepala dan nod pertama
dimasukkan ke dalam kedudukan tertentu; di tengah-tengah senarai terpaut; >Walaupun kedudukan sisipan berbeza, kaedah sisipan yang sama digunakan. Ia dibahagikan kepada dua langkah, seperti yang ditunjukkan dalam rajah di atas:
-
menunjuk penunjuk seterusnya nod baharu ke nod selepas kedudukan sisipan; >
Penunjuk seterusnya nod sebelum kedudukan sisipan menghala ke nod sisipan; kedudukan. Dalam Rajah 4, juga Iaitu untuk mencari nod 1, dan nod yang sepadan 2 boleh diwakili oleh penunjuk seterusnya nod 1. Dengan cara ini, langkah 1 dilakukan terlebih dahulu, dan kemudian langkah 2 dilakukan perlu menambah petunjuk tambahan lain semasa proses pelaksanaan.
Apabila anda perlu memadamkan nod daripada senarai terpaut, anda perlu melakukan dua langkah:
- Keluarkan nod daripada senarai terpaut;
- Lepaskan nod secara manual dan tuntut semula ruang memori yang diduduki oleh nod;
- Lebih berkaitan Untuk pengetahuan, sila lawati ruangan
!
Atas ialah kandungan terperinci Apakah struktur data senarai terpaut?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas



Apabila menggunakan struktur data kompleks dalam Java, Comparator digunakan untuk menyediakan mekanisme perbandingan yang fleksibel. Langkah-langkah khusus termasuk: mentakrifkan kelas pembanding, menulis semula kaedah bandingkan untuk menentukan logik perbandingan. Buat contoh pembanding. Gunakan kaedah Collections.sort, menghantar contoh koleksi dan pembanding.

Struktur data dan algoritma ialah asas pembangunan Java Artikel ini meneroka secara mendalam struktur data utama (seperti tatasusunan, senarai terpaut, pepohon, dll.) dan algoritma (seperti pengisihan, carian, algoritma graf, dll.) dalam Java. Struktur ini diilustrasikan dengan contoh praktikal, termasuk menggunakan tatasusunan untuk menyimpan skor, senarai terpaut untuk mengurus senarai beli-belah, tindanan untuk melaksanakan rekursi, baris gilir untuk menyegerakkan benang, dan pepohon dan jadual cincang untuk carian dan pengesahan pantas. Memahami konsep ini membolehkan anda menulis kod Java yang cekap dan boleh diselenggara.

Jenis rujukan ialah jenis data khas dalam bahasa Go Nilai mereka tidak menyimpan data itu sendiri secara langsung, tetapi alamat data yang disimpan. Dalam bahasa Go, jenis rujukan termasuk kepingan, peta, saluran dan penunjuk. Pemahaman mendalam tentang jenis rujukan adalah penting untuk memahami pengurusan memori dan kaedah pemindahan data bahasa Go. Artikel ini akan menggabungkan contoh kod khusus untuk memperkenalkan ciri dan penggunaan jenis rujukan dalam bahasa Go. 1. Slices Slices ialah salah satu jenis rujukan yang paling biasa digunakan dalam bahasa Go.

Pokok AVL ialah pokok carian binari seimbang yang memastikan operasi data yang pantas dan cekap. Untuk mencapai keseimbangan, ia melakukan operasi belok kiri dan kanan, melaraskan subpokok yang melanggar keseimbangan. Pokok AVL menggunakan pengimbangan ketinggian untuk memastikan ketinggian pokok sentiasa kecil berbanding bilangan nod, dengan itu mencapai kerumitan masa logaritma (O(logn)) operasi carian dan mengekalkan kecekapan struktur data walaupun pada set data yang besar.

Gambaran Keseluruhan Rangka Kerja Koleksi Java Rangka kerja pengumpulan Java ialah bahagian penting dalam bahasa pengaturcaraan Java Ia menyediakan satu siri perpustakaan kelas kontena yang boleh menyimpan dan mengurus data. Pustaka kelas kontena ini mempunyai struktur data yang berbeza untuk memenuhi keperluan penyimpanan dan pemprosesan data dalam senario yang berbeza. Kelebihan rangka kerja koleksi ialah ia menyediakan antara muka bersatu, membolehkan pembangun mengendalikan perpustakaan kelas kontena yang berbeza dengan cara yang sama, dengan itu mengurangkan kesukaran pembangunan. Struktur data rangka kerja pengumpulan Java Rangka kerja pengumpulan Java mengandungi pelbagai struktur data, setiap satunya mempunyai ciri unik dan senario yang boleh digunakan. Berikut adalah beberapa struktur data rangka kerja pengumpulan Java yang biasa: 1. Senarai: Senarai ialah koleksi tersusun yang membolehkan elemen diulang. Li

Kajian mendalam tentang misteri struktur data bahasa Go memerlukan contoh kod khusus Sebagai bahasa pengaturcaraan yang ringkas dan cekap, bahasa Go juga menunjukkan daya tarikannya yang unik dalam memproses struktur data. Struktur data adalah konsep asas dalam sains komputer, yang bertujuan untuk mengatur dan mengurus data supaya ia boleh diakses dan dimanipulasi dengan lebih cekap. Dengan mempelajari secara mendalam tentang misteri struktur data bahasa Go, kami dapat memahami dengan lebih baik cara data disimpan dan dikendalikan, seterusnya meningkatkan kecekapan pengaturcaraan dan kualiti kod. 1. Array Array ialah salah satu struktur data yang paling mudah

Perbandingan kerumitan masa algoritma tatasusunan dan senarai terpaut: mengakses tatasusunan O(1), senarai terpaut O(n), senarai terpaut O(1)/O(n); ), senarai terpaut O(n) (n); tatasusunan carian O(n), senarai terpaut O(n).

Gambaran Keseluruhan Perpustakaan Struktur Data PHPSPL Pustaka struktur data PHPSPL (Perpustakaan Standard PHP) mengandungi satu set kelas dan antara muka untuk menyimpan dan memanipulasi pelbagai struktur data. Struktur data ini termasuk tatasusunan, senarai terpaut, tindanan, baris gilir dan set, setiap satunya menyediakan set kaedah dan sifat khusus untuk memanipulasi data. Tatasusunan Dalam PHP, tatasusunan ialah koleksi tertib yang menyimpan jujukan elemen. Kelas tatasusunan SPL menyediakan fungsi yang dipertingkatkan untuk tatasusunan PHP asli, termasuk pengisihan, penapisan dan pemetaan. Berikut ialah contoh menggunakan kelas tatasusunan SPL: useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array