Rumah masalah biasa Apakah struktur data senarai terpaut?

Apakah struktur data senarai terpaut?

Aug 23, 2022 pm 02:50 PM
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.

Apakah struktur data 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)).

Apakah struktur data senarai terpaut?

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".

Apakah struktur data senarai terpaut?

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.

Apakah struktur data 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.

Apakah struktur data senarai terpaut?

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.

Apakah struktur data senarai terpaut?

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.
2. Padamkan nod daripada senarai terpaut

Apakah struktur data senarai terpaut?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
Soalan Lazim

!

Atas ialah kandungan terperinci Apakah struktur data senarai terpaut?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Cara Membuka Segala -galanya Di Myrise
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Bandingkan struktur data kompleks menggunakan perbandingan fungsi Java Bandingkan struktur data kompleks menggunakan perbandingan fungsi Java Apr 19, 2024 pm 10:24 PM

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 dan algoritma data Java: penjelasan mendalam Struktur dan algoritma data Java: penjelasan mendalam May 08, 2024 pm 10:12 PM

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.

Pemahaman mendalam tentang jenis rujukan dalam bahasa Go Pemahaman mendalam tentang jenis rujukan dalam bahasa Go Feb 21, 2024 pm 11:36 PM

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.

Struktur data PHP: Keseimbangan pepohon AVL, mengekalkan struktur data yang cekap dan teratur Struktur data PHP: Keseimbangan pepohon AVL, mengekalkan struktur data yang cekap dan teratur Jun 03, 2024 am 09:58 AM

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.

Analisis penuh rangka kerja pengumpulan Java: membedah struktur data dan mendedahkan rahsia storan yang cekap Analisis penuh rangka kerja pengumpulan Java: membedah struktur data dan mendedahkan rahsia storan yang cekap Feb 23, 2024 am 10:49 AM

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

Ketahui rahsia struktur data bahasa Go secara mendalam Ketahui rahsia struktur data bahasa Go secara mendalam Mar 29, 2024 pm 12:42 PM

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 PHP dan senarai terpaut Perbandingan kerumitan masa algoritma tatasusunan PHP dan senarai terpaut May 07, 2024 pm 01:54 PM

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).

Struktur data PHP SPL: Menyuntik kelajuan dan fleksibiliti ke dalam projek anda Struktur data PHP SPL: Menyuntik kelajuan dan fleksibiliti ke dalam projek anda Feb 19, 2024 pm 11:00 PM

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