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.

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