Mustafa Kemal Üniversitesi
Transkript
Mustafa Kemal Üniversitesi
Algoritma Geliştirme ve Veri Yapıları – 7 Liste ve Bağlantılı Liste Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Liste birbiriyle ilişkili verileri içeren bir kümedir, programlama açısından liste en basitinden bir dizi üzerinde tutulur. Dizi elemanları art arda gelen bellek gözlerinde tutulur. • Bağlantılı liste ise aynı kümeye ait verilerin birbirlerine bellek üzerinde sanal bağlar ile bağlanması ile oluşur. • Bağlantılı listenin zayıf yönü, liste üzerindeki ara elemanlara kolayca erişilememesi ve sık sık arama gerektiren uygulamalarda arama karmaşıklığının göreceli olarak büyük olmasıdır. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Uzunluk: Liste üzerindeki düğümlerin sayısıdır. • Anahtar Sözcük: Liste üzerinde arama yapılacağı veya listenin sıralanacağı durumlarda kullanılacak veri parçasıdır. • Öncelikli Liste: Listeye yeni verilerin eklenmesi işleminde eklemenin bir bir anahtar değere göre sıralı yapılmasıdır(Öğrenci numarasına göre). • Boş Liste: Liste veya bağlantılı listenin hiçbir elemanı olmaması; üzerinde hiçbir veri tutulmamasıdır. Bu durumda ilk ve son işaretçilerinde boş anlamında NULL değer tutulur. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Bağlantılı liste türleri: o Tek Yönlü Bağlantılı Liste • Birbirini izleyen düğümler arasında tek-yönlü bir bağlantı vardır. Ekleme, arama, listeleme gibi işlemlerin karmaşıklığı O(n) dir. Listenin oluşturulması için iki tane işaretçi kullanılırsa ekleme karmaşıklığı O(1), arama ve listeleme karmaşıklığı O(n) olur. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Bağlantılı liste türleri: o Çift Yönlü Bağlantılı Liste • Düğümler arasındaki bağlantı hem ileri hem de öne doğru ilerleyecek şekilde iki yönlüdür. Yani bir düğüm hem bir sonraki hem de bir önceki düğümü işaret eder. • Çift yönlü bağlantılı liste araya ekleme ve silme işlemlerini de kolaylaştırır. Çünkü silinecek düğümün hem arkasındaki hem de önündeki düğüm bilindiği için silmeyi sağlayacak bağlantı düzenlemesi kolayca yapılır. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Bağlantılı liste türleri: o Çevrimsel Bağlantılı Liste • Düğümler arasında çevrimsel bir bağlantı vardır. Yani listenin son düğümü ilk düğümünü işaret eder. Böylece çevrimsel bir yapı oluşturulur. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Gereksinimler o İşaretçi değişkenler ve liste için gerekli veri yapısının tanımlanması o Dinamik bellek ihtiyacı • Bellek ihtiyaçları malloc() veya benzeri bir fonksiyon ile sağlanır belleğin kullanımının ardından free() veya benzeri bir fonksiyonla bellek kullanımı durdurulabilir. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Dinamik bellek kullanılması sebebiyle tanımlamalar işaretçi kullanılarak gerçekleştirilir. • Bağlantılı liste boş iken her iki değerde NULL dur. • İlk eleman içi bellekten yer tahsis edilmesi şekilde gösterilmiştir. • Oluşturulan elemanı bellek yönetimine geri iade etmek için free(p) fonksiyonunu kullanmak yeterlidir. Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Bağlantılı Liste Veri Yapısı struct baglantililiste{ int sayi; struct baglantililiste *arka; }; struct baglantililiste *ilk=NULL, *son=NULL; baglantililiste *p; p=(baglantililiste *)malloc(sizeof(struct baglantililiste)); Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Ekleme işlemi baglantililiste *p=(baglantililiste *)malloc(sizeof(struct baglantililiste)); if(p!=NULL){ if(ilk==NULL){ ilk=p; son=p; ilk->arka=NULL; son->arka=NULL; }else{ son->arka=p; son=p; p->arka=NULL; }} Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Listeleme İşlemi baglantili *adr =ilk ; while(adr!=NULL) { cout<<(adr->sayi)<<endl; adr=adr->arka; } Mustafa Kemal Üniversitesi Liste ve Bağlantılı Liste • Silme İşlemi baglantili *adr=ilk,*onceki=ilk,*silinecekveri=silinecek; while(adr!=NULL){ if(adr ==silinecekveri){ onceki->arka=adr->arka; free(adr); Break; } onceki=adr; adr=adr->arka; } Mustafa Kemal Üniversitesi