Senarai terpaut ialah senarai linear yang disimpan dalam struktur storan "berantai". Alamat unit storan yang diduduki oleh elemen data senarai terpaut boleh menjadi berterusan atau tidak berterusan Ruang storan yang sepadan boleh diperuntukkan secara sementara dan secara dinamik mengikut keperluan. Hubungan logik antara elemen data boleh dinyatakan dengan "rantai".

Persekitaran pengendalian tutorial ini: sistem Windows 7, komputer Dell G3.

Untuk mengatasi kelemahan struktur storan jadual berjujukan, menggunakan sepenuhnya ruang storan dan meningkatkan kecekapan operasi, jadual linear boleh menggunakan struktur storan lain - Struktur storan berantai. Struktur storan terpaut senarai linear dirujuk sebagai "senarai pautan"

1 Gambaran keseluruhan senarai terpaut

Alamat unit storan yang diduduki oleh elemen data. daripada senarai terpaut boleh berturut-turut, atau ia boleh terputus, dan ruang storan yang sepadan boleh diperuntukkan buat sementara waktu dan secara dinamik mengikut keperluan. Hubungan logik antara elemen data boleh dinyatakan sebagai "rantai".

Sisipan dan pemadaman senarai terpaut tidak memerlukan elemen data yang dipindahkan, tetapi hanya perlu mengubah suai rantai.

Klasifikasi senarai utama:

1 Dikelaskan mengikut cara peruntukan memori senarai terpaut dilaksanakan

①Senarai terpaut dinamik

②Senarai terpaut statik

<.>2 .Dikelaskan mengikut kaedah memaut

①Senarai terpaut tunggal

②Senarai pautan bulat

③Senarai terpaut berganda

(semuanya adalah senarai terpaut dinamik . elemen data ai, kecuali

Selain menyimpan maklumatnya sendiri

, ia juga perlu

menyimpan maklumat

yang menunjukkan penggantinya yang terdekat ( lokasi simpanan pengganti - alamat). Medan yang menyimpan maklumat elemen data dipanggil medan data dan medan yang menyimpan kedudukan pengganti segera dipanggil

medan penunjuk

, maklumat yang disimpan dalam domain penunjuk dipanggil penunjuk atau rantai. Kedua-dua bahagian maklumat ini membentuk imej simpanan unsur data ai, yang dipanggil nod .

n nod dipautkan ke dalam senarai terpaut, iaitu struktur storan terpaut bagi senarai linear (a1, a2, a3,...,an), kerana setiap nod senarai terpaut hanya mengandungi satu penuding domain, jadi ia dipanggil

TunggalSenarai Terpaut

.

Untuk senarai linear, sentiasa ada kepala dan ekor, dan senarai terpaut tidak terkecuali. Penunjuk ke nod pertama senarai terpaut tunggal dalam senarai terpaut dipanggil penunjuk kepala

Akses keseluruhan senarai terpaut mesti bermula dari penunjuk kepala, dan setiap nod berikutnya Titik ialah kedudukan yang ditunjuk oleh penunjuk pengganti nod sebelumnya.

Penunjuk nod terakhir senarai terpaut ialah "null (biasanya diwakili oleh NULL)" - penuding nol. Untuk memudahkan pelaksanaan pelbagai operasi pada senarai terpaut, nod jenis yang sama ditetapkan sebelum nod data pertama senarai terpaut tunggal ini dipanggil nod kepala. Medan data nod kepala boleh menyimpan maklumat bendera khas seperti panjang senarai terpaut, atau ia tidak boleh menyimpan sebarang data. Nod data pertama dan nod terakhir senarai terpaut juga dipanggil

nod kepala dan nod ekor

.

2. Persamaan dan perbezaan antara penunjuk kepala dan nod kepalaPenunjuk kepala:

Penunjuk kepala merujuk kepada senarai terpaut Penunjuk ke nod pertama Jika senarai terpaut mempunyai nod kepala, ia adalah penunjuk kepada nod kepala.

Penuding kepala mempunyai fungsi pengenalan, dan penuding kepala sering dinamakan dengan nama senarai terpaut.

Tidak kira sama ada senarai pautan kosong atau tidak, penunjuk kepala tidak kosong.

Penuding kepala ialah elemen yang diperlukan dalam senarai terpaut

.
• Nod kepala:
• Nod kepala disediakan untuk penyatuan dan kemudahan operasi Ia diletakkan sebelum nod elemen pertama dan medan datanya Umumnya tidak disengajakan.
Dengan nod kepala, operasi memasukkan nod sebelum nod elemen pertama dan memadam nod pertama disatukan dengan nod lain.

Nod kepala tidak semestinya elemen yang diperlukan dalam senarai terpaut

.
• 3. Demonstrasi kod

3. Operasi senarai terpaut tunggal

1 Operasi sisipan

1) Simulasi sisipan

Anggapkan elemen penyimpanan nod e ialah s, masukkan s ke dalam ai Bagaimana untuk beroperasi di belakang nod?



Berfikir: Bolehkah kedua-dua kod yang dimasukkan ditukar?

Tidak, jika anda menukarnya, elemen di belakang ai 1 dan seterusnya tidak akan ditemui, kerana medan penunjuk s tidak menghala ke alamat ai 1.

2) Idea algoritma untuk memasukkan data ke-i ke dalam nod senarai terpaut tunggal

• Isytiharkan nod p yang menunjuk ke nod pertama senarai terpaut, mulakan j =1;
• Apabila j
• Jika p kosong di hujung senarai terpaut, ini bermakna elemen ke-i tidak wujud jika carian berjaya, hasilkan nod kosong s (menggunakan fungsi malloc)
• Tugaskan elemen data e kepada s->data, iaitu s->data=e;
• Sisipkan pernyataan standard: s->next=p->next; p->next=s;
• Berjaya kembali.

2. Operasi padam

1) Simulasi pemadaman

Anggapkan elemen penyimpanan nod ai ialah q, dan operasi pemadaman nod q daripada satu pautan senarai akan dilaksanakan.



2) Idea algoritma memadamkan nod data ke-i dalam senarai terpaut tunggal

• Isytiharkan nod p yang menunjuk ke nod pertama titik senarai terpaut, mulakan j=1;
• Apabila j
• Jika p mencapai penghujung senarai terpaut Jika ia kosong, ini bermakna elemen ke-i tidak wujud jika carian berjaya, padamkan nod p->seterusnya dan tetapkan ia kepada q
. Masukkan pernyataan standard: p->next=q->next;
• Tetapkan nod q kepada e, iaitu, e=q->data;
• Lepaskan nod q
• Berjaya kembali.
4. Perbandingan antara struktur senarai terpaut tunggal dan struktur senarai berjujukan
Kaedah storan:
Jadual jujukan menggunakan unit storan berterusan untuk menyimpan linear jadual dalam turutan Elemen data
• menggunakan struktur storan terpaut dan menggunakan set unit storan sewenang-wenangnya untuk menyimpan elemen jadual linear
Prestasi masa:
① Carian
Senarai jujukan O(1)
• Senarai dipautkan tunggal O(n)
②Sisipan dan pemadaman
Jujukan senarai O (n)
• Senarai terpaut tunggal O(1)
Prestasi ruang:
Jadual jujukan memerlukan ruang storan yang telah diperuntukkan ia terlalu besar, ia adalah satu pembaziran Jika dibahagikan terlalu kecil, limpahan mudah berlaku
• Senarai yang dipautkan secara tunggal tidak memerlukan pra-peruntukan ruang storan Anda boleh memperuntukkan ruang storan sebanyak yang anda perlukan, dan bilangan elemen tidak terhad
Untuk lebih banyak pengetahuan berkaitan, sila lawati ruangan

Soalan Lazim!

Atas ialah kandungan terperinci Senarai terpaut ialah senarai linear yang disimpan dalam struktur storan apa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!