Senarai Berkaitan Pekeliling: Kelebihan dengan Contoh Program C

Isi kandungan:

Anonim

Apakah Senarai Berkaitan Pekeliling?

Senarai terpaut bulat adalah urutan nod yang disusun sedemikian rupa sehingga setiap simpul dapat ditelusuri semula. Di sini "simpul" adalah elemen rujukan diri dengan petunjuk ke satu atau dua nod di kawasan berhampiran iI.

Di bawah ini adalah gambaran senarai terpaut bulat dengan 3 nod.

Di sini, anda dapat melihat bahawa setiap nod dapat dikesan semula. Contoh yang ditunjukkan di atas adalah senarai berangkai tunggal.

Nota: Senarai pekeliling bulat yang paling mudah, adalah simpul yang hanya dapat dilihat seperti yang ditunjukkan

Dalam tutorial senarai terpaut pekeliling ini, anda akan belajar:

  • Apakah Senarai Berkaitan Pekeliling?
  • Operasi Asas
  • Operasi Pemasangan
  • Operasi Penghapusan
  • Melintasi Senarai Berkaitan Pekeliling
  • Kelebihan Senarai Berkaitan Pekeliling
  • Senarai berangkai tunggal sebagai Senarai Berkaitan Pekeliling
  • Aplikasi Senarai Berkaitan Pekeliling

Operasi Asas

Operasi asas dalam senarai terpaut bulat adalah:

  1. Penyisipan
  2. Penghapusan dan
  3. Melintang
  • Penyisipan adalah proses meletakkan simpul pada kedudukan yang ditentukan dalam senarai terpaut bulat.
  • Penghapusan adalah proses membuang nod yang ada dari senarai terpaut. Node dapat dikenal pasti dengan berlakunya nilai atau kedudukannya.
  • Melintasi senarai terpaut bulat adalah proses memaparkan keseluruhan kandungan senarai terpaut dan mengimbas kembali ke simpul sumber.

Pada bahagian seterusnya, anda akan memahami penyisipan simpul, dan jenis penyisipan yang mungkin dilakukan dalam Senarai Pautan Bulat Bersambung.

Operasi Pemasangan

Pada mulanya, anda perlu membuat satu simpul yang menunjuk pada dirinya sendiri seperti yang ditunjukkan dalam gambar ini. Tanpa simpul ini, penyisipan membuat nod pertama.

Seterusnya, terdapat dua kemungkinan:

  • Penyisipan pada kedudukan semasa senarai terpaut pekeliling. Ini sesuai dengan penyisipan pada awal akhir senarai berangkai tunggal. Dalam senarai terpaut pekeliling, awal dan akhir adalah sama.
  • Penyisipan selepas nod yang diindeks. Node harus dikenal pasti dengan nombor indeks yang sesuai dengan nilai elemennya.

Untuk memasukkan pada permulaan / akhir senarai berangkai pekeliling, iaitu pada kedudukan di mana simpul pertama ditambahkan,

  • Anda mesti memutuskan pautan diri yang ada ke nod yang ada
  • Penunjuk seterusnya nod baru akan menghubungkan ke nod yang ada.
  • Penunjuk node terakhir akan menunjuk ke simpul yang dimasukkan.

CATATAN: Penunjuk yang merupakan token master atau permulaan / akhir bulatan boleh diubah. Ia masih akan kembali ke simpul yang sama semasa melintas, dibincangkan di hadapan.

Langkah-langkah di (a) i-iii ditunjukkan di bawah:

(Nod yang ada)

LANGKAH 1) Putus pautan yang ada

LANGKAH 2) Buat pautan ke hadapan (dari simpul baru ke nod yang ada)

LANGKAH 3) Buat pautan gelung ke nod pertama

Seterusnya, anda akan mencuba penyisipan selepas nod.

Sebagai contoh, mari kita masukkan "VALUE2" selepas simpul dengan "VALUE0". Mari kita anggap bahawa titik permulaan adalah simpul dengan "NILAI0".

  • Anda harus memutuskan garis antara nod pertama dan kedua dan meletakkan simpul dengan "VALUE2" di antara.
  • Penunjuk seterusnya nod pertama mesti menghubungkan ke nod ini, dan penunjuk seterusnya nod ini mesti memaut ke nod kedua yang lebih awal.
  • Pengaturan selebihnya tidak berubah. Semua nod dapat dikesan semula kepada diri mereka sendiri.

CATATAN: Oleh kerana terdapat susunan kitaran, memasukkan nod melibatkan prosedur yang sama untuk sebarang nod. Penunjuk yang melengkapkan kitaran melengkapkan kitaran seperti nod lain.

Ini ditunjukkan di bawah:

(Katakan hanya ada dua simpul. Ini adalah kes remeh)

LANGKAH 1) Tanggalkan pautan dalaman antara nod yang bersambung

LANGKAH 2) Sambungkan simpul sebelah kiri ke nod baru

LANGKAH 3) Sambungkan nod baru ke simpul sebelah kanan.

Operasi Penghapusan

Mari kita anggap senarai pautan bulat 3-nod. Kes penghapusan diberikan di bawah:

  • Memadamkan elemen semasa
  • Pemadaman selepas unsur.

Pemadaman pada awal / akhir:

  1. Melintasi simpul pertama dari simpul terakhir.
  2. Untuk menghapuskan dari akhir, hanya boleh ada satu langkah melintang, dari simpul terakhir hingga simpul pertama.
  3. Padamkan pautan antara nod terakhir dan nod seterusnya.
  4. Pautkan simpul terakhir ke elemen seterusnya dari nod pertama.
  5. Bebaskan nod pertama.

(Persediaan yang ada)

LANGKAH 1 ) Tanggalkan pautan bulat

LANGKAH 2) Tanggalkan pautan antara yang pertama dan seterusnya, pautkan simpul terakhir, ke simpul yang pertama

LANGKAH 3) Bebaskan / nyahpindah nod pertama

Pemadaman selepas nod:

  1. Melintasi hingga simpul seterusnya adalah nod yang akan dihapuskan.
  2. Melintasi simpul seterusnya, meletakkan penunjuk pada nod sebelumnya.
  3. Sambungkan node sebelumnya ke node selepas node sekarang, menggunakan penunjuk seterusnya.
  4. Bebaskan nod semasa (terputus).

LANGKAH 1) Katakanlah bahawa kita perlu menghapus nod dengan "NILAI1."

LANGKAH 2) Tanggalkan hubungan antara nod sebelumnya dan nod semasa. Pautkan nod sebelumnya dengan nod seterusnya yang ditunjukkan oleh simpul semasa (dengan NILAI1).

LANGKAH 3) Bebaskan atau nyahpindah nod semasa.

Melintasi Senarai Berkaitan Pekeliling

Untuk melintasi senarai terpaut bulat, bermula dari penunjuk terakhir, periksa apakah penunjuk terakhir itu sendiri adalah NULL. Sekiranya keadaan ini salah, periksa apakah hanya ada satu elemen. Jika tidak, melintasi menggunakan penunjuk sementara sehingga penunjuk terakhir dicapai lagi, atau seberapa banyak yang diperlukan, seperti yang ditunjukkan dalam GIF di bawah.

Kelebihan Senarai Berkaitan Pekeliling

Beberapa kelebihan senarai yang berkaitan dengan pekeliling adalah:

  1. Tidak ada keperluan untuk tugasan NULL dalam kod. Senarai pekeliling tidak pernah menunjukkan penunjuk NULL kecuali dinyahalokasikan sepenuhnya.
  2. Senarai yang berkaitan dengan pekeliling bermanfaat untuk operasi akhir sejak awal dan akhir bertepatan. Algoritma seperti penjadualan Round Robin dapat dengan rapi menghilangkan proses yang diatur dalam barisan tanpa berpusing tanpa menunjuk titik-titik yang merujuk atau NULL.
  3. Senarai pautan pekeliling juga melaksanakan semua fungsi biasa dari senarai yang dipautkan secara tunggal. Hakikatnya, senarai berangkai berganda yang dibahas di bawah bahkan dapat menghilangkan keperluan untuk perjalanan panjang untuk mencari elemen. Unsur itu paling tidak hanya bertentangan dengan permulaan, hanya melengkapkan separuh senarai terpaut.

Senarai Terhubung Singly sebagai Senarai Terpaut Bulat

Anda digalakkan untuk membaca dan melaksanakan kod di bawah. Ia menunjukkan aritmetik penunjuk yang berkaitan dengan senarai terpaut bulat.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Penjelasan kod:

  1. Dua baris kod pertama adalah fail header yang diperlukan.
  2. Bahagian seterusnya menerangkan struktur setiap nod rujukan diri. Ia mengandungi nilai dan penunjuk jenis yang sama dengan struktur.
  3. Setiap struktur berulang kali menghubungkan objek struktur dengan jenis yang sama.
  4. Terdapat prototaip fungsi yang berbeza untuk:
    1. Menambah elemen ke senarai terpaut kosong
    2. Memasukkan di kini tajam kedudukan senarai dikaitkan bulat.
    3. Memasukkan selepas nilai indeks tertentu dalam senarai terpaut.
    4. Mengalih keluar / Menghapus setelah nilai tertentu yang diindeks dalam senarai yang dipautkan.
    5. Mengalih keluar dari senarai terpaut bulat pada kedudukan semasa
  5. Fungsi terakhir mencetak setiap elemen melalui traversal bulat di mana-mana keadaan senarai terpaut.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Penjelasan kod:

  1. Untuk kod addEmpty, peruntukkan nod kosong menggunakan fungsi malloc.
  2. Untuk nod ini, letakkan data ke pemboleh ubah temp.
  3. Tugaskan dan pautkan satu-satunya pemboleh ubah ke pemboleh ubah temp
  4. Kembalikan elemen terakhir ke konteks utama () / aplikasi.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Penjelasan kod

  1. Sekiranya tidak ada elemen untuk dimasukkan, maka anda harus memastikan untuk menambah senarai kosong dan kawalan kembali.
  2. Buat elemen sementara untuk meletakkan selepas elemen semasa.
  3. Pautkan petunjuk seperti yang ditunjukkan.
  4. Kembalikan penunjuk terakhir seperti fungsi sebelumnya.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Penjelasan kod:

  1. Sekiranya tidak ada unsur dalam senarai, abaikan data, tambahkan item semasa sebagai item terakhir dalam senarai dan kawalan kembali
  2. Untuk setiap lelaran dalam gelung do-while memastikan bahawa ada penunjuk sebelumnya yang memegang hasil yang dilalui terakhir.
  3. Barulah traversal seterusnya dapat berlaku.
  4. Sekiranya data dijumpai, atau temp mencapai kembali ke penunjuk terakhir, masa sementara akan berakhir. Bahagian kod seterusnya memutuskan apa yang harus dilakukan dengan item tersebut.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Penjelasan kod:

  1. Sekiranya keseluruhan senarai telah dilalui, namun item tersebut tidak dijumpai, tampilkan mesej "item not found" dan kemudian kembalikan kawalan kepada pemanggil.
  2. Sekiranya terdapat simpul yang dijumpai, dan / atau simpul belum menjadi simpul terakhir, kemudian buat simpul baru.
  3. Pautkan nod sebelumnya dengan nod baru. Pautkan simpul semasa dengan temp (pembolehubah melintang).
  4. Ini memastikan bahawa elemen diletakkan setelah simpul tertentu dalam senarai pautan pekeliling. Kembali kepada pemanggil.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Penjelasan kod

  1. Untuk membuang node terakhir (semasa), periksa sama ada senarai ini kosong. Sekiranya ada, maka tidak ada unsur yang dapat dikeluarkan.
  2. Pemboleh ubah temp hanya melintasi satu pautan ke hadapan.
  3. Pautkan penunjuk terakhir ke penunjuk selepas yang pertama.
  4. Bebaskan penunjuk temp. Ini menyahaktifkan penunjuk terakhir yang tidak berkaitan.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Penjelasan kod

  1. Seperti fungsi penyingkiran sebelumnya, periksa apakah tidak ada unsur. Sekiranya ini benar, maka tidak ada unsur yang dapat dikeluarkan.
  2. Pointer diberi kedudukan khusus untuk mencari elemen yang akan dihapuskan.
  3. Petunjuknya maju, satu di belakang yang lain. (berlaku di belakang suhu)
  4. Proses berlanjutan sehingga elemen dijumpai, atau elemen seterusnya mengundur ke penunjuk terakhir.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Penjelasan program

  1. Sekiranya elemen dijumpai setelah melintasi keseluruhan senarai yang dipautkan, mesej ralat dipaparkan mengatakan item itu tidak dijumpai.
  2. Jika tidak, elemen itu dilepaskan dan dibebaskan dalam langkah 3 dan 4.
  3. Penunjuk sebelumnya dihubungkan ke alamat yang ditunjuk sebagai "seterusnya" oleh elemen yang akan dihapus (temp).
  4. Oleh itu, penunjuk suhu dibuang dan dibebaskan
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Penjelasan kod

  1. Mengintip atau melintasi tidak boleh dilakukan jika diperlukan sifar. Pengguna perlu memperuntukkan atau memasukkan nod.
  2. Sekiranya hanya ada satu simpul, tidak perlu melintasi, kandungan simpul dapat dicetak, dan gelung sementara tidak dapat dilaksanakan.
  3. Sekiranya terdapat lebih daripada satu simpul, suhu mencetak semua item hingga elemen terakhir.
  4. Sebaik sahaja elemen terakhir dicapai, gelung berakhir, dan fungsi mengembalikan panggilan ke fungsi utama.

Aplikasi Senarai Berkaitan Pekeliling

  • Melaksanakan penjadualan round-robin dalam proses sistem dan penjadualan bulat dalam grafik berkelajuan tinggi.
  • Penjadualan nada dering di rangkaian komputer.
  • Ia digunakan dalam unit paparan seperti papan kedai yang memerlukan penyebaran data secara berterusan.