Dairesel Bağlantılı Liste: C Programı Örneğinin Avantajları

İçindekiler:

Anonim

Dairesel Bağlantılı Liste nedir?

Dairesel bağlantılı bir liste, her bir düğümün kendi kendine izlenebileceği şekilde düzenlenmiş bir düğüm dizisidir. Burada bir "düğüm", iI'nin yakın çevresindeki bir veya iki düğüme işaretçileri olan kendi kendine başvuran bir öğedir.

Aşağıda 3 düğümlü döngüsel bağlantılı bir listenin tasviri bulunmaktadır.

Burada, her bir düğümün kendi kendine izlenebilir olduğunu görebilirsiniz. Yukarıda gösterilen örnek, dairesel tek bağlantılı bir listedir.

Not: En basit dairesel bağlantılı liste, gösterildiği gibi yalnızca kendisini izleyen bir düğümdür.

Bu döngüsel bağlantılı liste eğitiminde şunları öğreneceksiniz:

  • Dairesel Bağlantılı Liste nedir?
  • Temel işlemler
  • Yerleştirme İşlemi
  • Silme İşlemi
  • Dairesel Bağlantılı Listenin Geçiş
  • Dairesel Bağlantılı Listenin Avantajları
  • Dairesel Bağlantılı Liste olarak tek bağlantılı liste
  • Dairesel Bağlantılı Liste Başvuruları

Temel işlemler

Dairesel bağlantılı bir listedeki temel işlemler şunlardır:

  1. Yerleştirme
  2. Silme ve
  3. Geçiş
  • Ekleme, dairesel bağlantılı listede belirtilen bir konuma bir düğüm yerleştirme işlemidir.
  • Silme, bağlı listeden mevcut bir düğümü kaldırma işlemidir. Düğüm, değerinin oluşumu veya konumu ile tanımlanabilir.
  • Dairesel bağlantılı bir listenin geçişi, bağlantılı listenin tüm içeriğini görüntüleme ve kaynak düğüme geri dönme işlemidir.

Bir sonraki bölümde, bir düğümün eklenmesini ve Dairesel Tek Bağlantılı Listede olası ekleme türlerini anlayacaksınız.

Yerleştirme İşlemi

Başlangıçta, bu resimde gösterildiği gibi kendisine işaret eden bir düğüm oluşturmanız gerekir. Bu düğüm olmadan, ekleme ilk düğümü oluşturur.

Sonra, iki olasılık var:

  • Dairesel bağlantılı listenin mevcut konumuna ekleme. Bu, normal bir tekil bağlantılı listenin sonunun başlangıcındaki eklemeye karşılık gelir. Döngüsel bağlantılı bir listede, başlangıç ​​ve son aynıdır.
  • Dizine alınmış bir düğümden sonra ekleme. Düğüm, eleman değerine karşılık gelen bir dizin numarasıyla tanımlanmalıdır.

Dairesel bağlantılı listenin başında / sonunda, yani ilk düğümün eklendiği konumda eklemek için,

  • Mevcut kendi kendine bağlantıyı mevcut düğümle kesmeniz gerekecek
  • Yeni düğümün bir sonraki göstericisi mevcut düğüme bağlanacaktır.
  • Son düğümün sonraki işaretçisi eklenen düğümü gösterecektir.

NOT: Ana simge olan işaretçi veya dairenin başlangıcı / sonu değiştirilebilir. İleride tartışılan bir çapraz geçişte yine aynı düğüme dönecektir.

(A) i-iii'teki adımlar aşağıda gösterilmiştir:

(Mevcut düğüm)

ADIM 1) Mevcut bağlantıyı koparın

ADIM 2) Bir ileri bağlantı oluşturun (yeni düğümden mevcut bir düğüme)

ADIM 3) İlk düğüme bir döngü bağlantısı oluşturun

Ardından, bir düğümden sonra eklemeyi deneyeceksiniz.

Örneğin, "VALUE0" ile düğümün arkasına "VALUE2" ekleyelim. Başlangıç ​​noktasının "VALUE0" olan düğüm olduğunu varsayalım.

  • Birinci ve ikinci düğüm arasındaki çizgiyi kırmanız ve arasına "VALUE2" olan düğümü yerleştirmeniz gerekir.
  • İlk düğümün sonraki göstericisi bu düğüme bağlanmalıdır ve bu düğümün sonraki göstericisi önceki ikinci düğüme bağlanmalıdır.
  • Düzenlemenin geri kalanı değişmeden kalır. Tüm düğümler kendi kendilerine izlenebilir.

NOT: Döngüsel bir düzenleme olduğundan, bir düğüm eklemek herhangi bir düğüm için aynı prosedürü içerir. Bir döngüyü tamamlayan işaretçi, diğer herhangi bir düğüm gibi döngüyü tamamlar.

Bu aşağıda gösterilmiştir:

(Sadece iki düğüm olduğunu varsayalım. Bu önemsiz bir durumdur)

ADIM 1) Bağlı düğümler arasındaki iç bağlantıyı çıkarın

ADIM 2) Sol taraftaki düğümü yeni düğüme bağlayın

ADIM 3) Yeni düğümü sağ taraftaki düğüme bağlayın.

Silme İşlemi

3 düğümlü dairesel bağlantılı bir liste varsayalım. Silme durumları aşağıda verilmiştir:

  • Mevcut öğeyi silme
  • Bir elemandan sonra silme.

Başlangıçta / sonda silme:

  1. Son düğümden ilk düğüme geçin.
  2. Sondan silmek için, son düğümden ilk düğüme kadar yalnızca bir geçiş adımı olmalıdır.
  3. Son düğüm ile sonraki düğüm arasındaki bağlantıyı silin.
  4. Son düğümü, ilk düğümün sonraki öğesine bağlayın.
  5. İlk düğümü serbest bırakın.

(Mevcut kurulum)

ADIM 1 ) Dairesel bağlantıyı çıkarın

ADIMLAR 2) İlk ve sonraki arasındaki bağlantıyı kaldırın, son düğümü ilk düğümü takip eden düğüme bağlayın

ADIM 3) İlk düğümü serbest bırakın / serbest bırakın

Bir düğümden sonra silme:

  1. Silinecek düğüm sonraki düğüme kadar çapraz geçiş yapın.
  2. Önceki düğüme bir işaretçi yerleştirerek sonraki düğüme geçin.
  3. Önceki düğümü, sonraki işaretçisini kullanarak mevcut düğümden sonraki düğüme bağlayın.
  4. Geçerli (bağlantısı kesilmiş) düğümü serbest bırakın.

ADIM 1) "VALUE1" olan bir düğümü silmemiz gerektiğini varsayalım.

ADIM 2) Önceki düğüm ile mevcut düğüm arasındaki bağlantıyı kaldırın. Önceki düğümünü, geçerli düğümün gösterdiği sonraki düğüme bağlayın (VALUE1 ile).

ADIM 3) Mevcut düğümü serbest bırakın veya serbest bırakın.

Dairesel Bağlantılı Listenin Geçiş

Dairesel bağlantılı bir listeyi son bir işaretçiden başlayarak geçmek için, son işaretçinin kendisinin NULL olup olmadığını kontrol edin. Bu koşul yanlışsa, yalnızca bir öğe olup olmadığını kontrol edin. Aksi takdirde, son işaretçiye tekrar ulaşılıncaya kadar veya aşağıdaki GIF'de gösterildiği gibi gerektiği kadar çok kez geçici bir işaretçi kullanarak ilerleyin.

Dairesel Bağlantılı Listenin Avantajları

Döngüsel bağlantılı listelerin avantajlarından bazıları şunlardır:

  1. Kodda NULL atama gerekliliği yoktur. Döngüsel liste, tamamen serbest bırakılmadıkça hiçbir zaman bir NULL işaretçisine işaret etmez.
  2. Döngüsel bağlantılı listeler, başlangıç ​​ve bitiş çakıştığı için son işlemler için avantajlıdır. Round Robin zamanlama gibi algoritmalar, sarkan veya NULL referanslı işaretçilerle karşılaşmadan döngüsel bir şekilde sıraya alınan süreçleri düzgün bir şekilde ortadan kaldırabilir.
  3. Dairesel bağlantılı liste, tekil bağlantılı bir listenin tüm normal işlevlerini de gerçekleştirir. Aslında, aşağıda tartışılan dairesel çift bağlantılı listeler, bir elemanın konumlandırılması için tam uzunlukta bir çapraz geçiş ihtiyacını bile ortadan kaldırabilir. Bu öğe, en fazla, yalnızca başlangıca tam tersi olur ve bağlantılı listenin yarısını tamamlar.

Dairesel Bağlantılı Liste Olarak Tek Bağlantılı Liste

Aşağıdaki kodu okuyup uygulamaya çalışmanız tavsiye edilir. Dairesel bağlantılı listelerle ilişkili işaretçi aritmetiğini sunar.

#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(){…

Kod açıklaması:

  1. İlk iki kod satırı, gerekli olan başlık dosyalarıdır.
  2. Sonraki bölüm, her bir kendine başvuran düğümün yapısını açıklar. Yapıyla aynı tipte bir değer ve işaretçi içerir.
  3. Her yapı, aynı tipteki yapı nesnelerine tekrar tekrar bağlanır.
  4. Aşağıdakiler için farklı işlev prototipleri vardır:
    1. Boş bir bağlantılı listeye bir eleman ekleme
    2. Dairesel bağlantılı bir listenin o anda işaret edilen konumuna ekleme .
    3. Bağlantılı listedeki belirli bir indekslenmiş değerden sonra ekleme .
    4. Bağlantılı listedeki belirli bir endekslenmiş değerden sonra Kaldırma / Silme .
    5. Dairesel bağlantılı bir listenin şu anda işaret edilen konumundan kaldırma
  5. Son işlev, her bir öğeyi bağlantılı listenin herhangi bir durumunda dairesel bir geçişle yazdırır.
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)

Kod açıklaması:

  1. AddEmpty kodu için malloc işlevini kullanarak boş bir düğüm ayırın.
  2. Bu düğüm için verileri temp değişkenine yerleştirin.
  3. Tek değişkeni geçici değişkene atayın ve bağlayın
  4. Son öğeyi main () / application bağlamına döndürür.
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;…

Kod açıklaması

  1. Eklenecek bir öğe yoksa, boş bir listeye eklediğinizden ve denetimi döndürdüğünüzden emin olmalısınız.
  2. Mevcut öğeden sonra yerleştirmek için geçici bir öğe oluşturun.
  3. İşaretçileri gösterildiği gibi bağlayın.
  4. Son işaretçiyi önceki işlevde olduğu gibi döndür.
… 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");…

Kod açıklaması:

  1. Listede herhangi bir öğe yoksa, veriyi yok sayın, mevcut öğeyi listedeki son öğe olarak ekleyin ve kontrolü geri verin
  2. Do-while döngüsündeki her yineleme için, en son gezilen sonucu tutan önceki bir işaretçinin bulunduğundan emin olun.
  3. Ancak o zaman bir sonraki geçiş gerçekleşebilir.
  4. Veriler bulunursa veya temp, son işaretçiye geri dönerse, do-while sona erer. Kodun bir sonraki bölümü, öğeyle ne yapılması gerektiğine karar verir.
… 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)…

Kod açıklaması:

  1. Listenin tamamı tarandıysa, ancak öğe bulunamazsa, bir "öğe bulunamadı" mesajı görüntüleyin ve ardından kontrolü arayana geri döndürün.
  2. Bulunan bir düğüm varsa ve / veya düğüm henüz son düğüm değilse, yeni bir düğüm oluşturun.
  3. Bağlantı yeni bir düğüm ile önceki düğümü. Geçerli düğümü temp (geçiş değişkeni) ile bağlayın.
  4. Bu, elemanın dairesel bağlantılı listedeki belirli bir düğümden sonra yerleştirilmesini sağlar. Arayana geri dönün.
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)

Kod açıklaması

  1. Yalnızca son (mevcut) düğümü kaldırmak için, bu listenin boş olup olmadığını kontrol edin. Öyleyse, hiçbir öğe kaldırılamaz.
  2. Temp değişkeni yalnızca bir bağlantı ileri gider.
  3. Son işaretçiyi ilkinden sonraki işaretçiye bağlayın.
  4. Sıcaklık işaretçisini serbest bırakın. Bağlantısız son işaretçiyi serbest bırakır.
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");…

Kod açıklaması

  1. Önceki kaldırma işlevinde olduğu gibi, öğe olup olmadığını kontrol edin. Bu doğruysa, hiçbir öğe kaldırılamaz.
  2. İşaretçiler, silinecek öğeyi bulmak için belirli konumlara atanır.
  3. İşaretçiler birbiri ardına ileri düzeydedir. (temp arkasında önceki)
  4. Süreç, bir öğe bulunana kadar veya sonraki öğe son işaretçiye geri dönene kadar devam eder.
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;

Programın açıklaması

  1. Öğe, bağlantılı listenin tamamından geçtikten sonra bulunursa, öğenin bulunamadığını belirten bir hata mesajı görüntülenir.
  2. Aksi takdirde, öğenin bağlantısı kesilir ve 3. ve 4. adımlarda serbest bırakılır.
  3. Önceki işaretçi, silinecek öğe tarafından "sonraki" olarak gösterilen adrese bağlanır (temp).
  4. Bu nedenle, geçici işaretçi serbest bırakılır ve serbest bırakılır.
… 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;}}

Kod açıklaması

  1. Sıfır gerekli ise gözetleme veya geçiş mümkün değildir. Kullanıcının bir düğüm ataması veya eklemesi gerekir.
  2. Yalnızca bir düğüm varsa, geçiş yapmaya gerek yoktur, düğümün içeriği yazdırılabilir ve while döngüsü çalışmaz.
  3. Birden fazla düğüm varsa, temp, tüm öğeyi son öğeye kadar yazdırır.
  4. Son elemana ulaşıldığı anda döngü sona erer ve işlev çağrıyı ana işleve döndürür.

Dairesel Bağlantılı Liste Başvuruları

  • Sistem süreçlerinde döngüsel zamanlama ve yüksek hızlı grafiklerde döngüsel çizelgeleme uygulama.
  • Token, bilgisayar ağlarında programlamayı çalar.
  • Sürekli veri geçişi gerektiren mağaza panoları gibi ekran birimlerinde kullanılır.