Dijkstra algoritması – Graf teorisindeki tek-kaynaklı en küçük yol probleminin çözümüdür.
Yönlü ve yönsüz grafların her ikisi için kullanılır. Fakat, kenarların hepsinin negatif olmayan ağırlıkları olmalıdır.
Ör – 1:
Ör -2 :
Graf, bir olay veya ifadenin düğüm ve çizgiler kullanılarak
gösterilmesi şeklidir
Graf, matematiksel anlamda düğümler ve düğümler arasındaki ilişkiyi gösteren kenarlardan oluşan bir kümedir. Mantıksal ilişki düğüm ile düğüm veya düğüm ile kenar arasında kurulur.
Köse (vertex) adı verilen düğümlerden ve kenar (edge) adı verilip köseleri birbirine bağlayan bağlantılardan oluşan veri yapısıdır.
Aynen ağaçlar gibi çizgeler de doğrusal olmayan veri yapıları grubuna girerler.
Bağlantılı listeler ve ağaçlar grafların özel örneklerindendir. Her kenar iki düğümü birleştirir.
Huffman Kodu, Bilgisayar biliminde, veri sıkıştırması için kullanılan, bir entropi kodlama algoritmasıdır. David A. Huffman tarafından 1952 yılında geliştirilmiştir.
Huffman’ın algoritması, her sembol (veya karakter) için özel bir kod üretir. Bu kodlar (ikilik sistemdeki 1 ve 0’lardan oluşan) bit haritası şeklindedir. Veri içerisinde en az kullanılan karakter için en uzun, en çok kullanılan karakter için ise en kısa kodu üretir.
Huffman’ın algoritması, veri içerisindeki karakterlerin kullanım sıklığına (frekans) göre bir ağaç oluşturur. Ağacın en tepesinden aşağıya doğru ilerlerken sola ayrılan dal için 0, sağa ayrılan dal için 1 kodu verilir.
Ör: “AAAABBBCC” kelimesinin huffman algoritması ile sıkıştırma oranını bulunuz.
1- Öncelikle karakterlerin metinde bulunma sıklığı(frekans) larını buluyoruz.
A karakteri metinde 4 kere geçmiş yani frekansı 4
A: 4 , B: 3 , C: 2
2- Bundan sonra yapılacak işlem en düşük frekansa sahip iki elemanı seçerek onlardan ağaç oluşturma işlemi
3- Şimdide bu karakterlerin yeni hallerinin ne olacağına. Ağaçta kökten itibaren eğer karakterimiz sol alt ağaçta bulunuyorsa koda 0 ekliyoruz , eğer karakter sağ alt ağaçta ise 1 ekliyoruz. Buna göre:
A: 0 oluyor
B: 11
C: 10
Sonuç: Normalde “AAAABBBCC” metinini 8*9 bit ile saklıyorduk. Şimdi ise bu metni şu şekilde saklıyoruz.
AAAA = 0000
BBB = 111111
CC = 1010
“AAAABBBCC” = 00001111111010 yani 14 bit.
Sıkıştırma oranı ((72- 14) / 72) * 100 = %80 oranında sıkıştırdık.
Ör 2:
Ör 3 :
Ağaçlar,doğrusal olmayan belirli niteliklere sahip iki boyutlu veri yapılarıdır.
İkili ağaçlar,düğümlerinde en fazla iki bağ içeren ağaçlardır.
Ağacın en üsteki düğümüne kök (root) denir.
Ağaçlar kökü yukarıda yaprakları aşağıda olacak şekilde çizilirler.
Ağaç veri modelinde ;
Sıralı veya sırasız listedeki bir elemanın yerinin bulunması işlemine arama denir.Bir liste veya dizi içerisindeki veriler(sayısal veya string olabilir)belirli bir anahtar(key) ifadeye göre aranır.Bu anahtar ifade kelime ,sözcük veya her ikisi de olabilir.
Genelde küçük boyutlu ve sırasız verilerin aranmasında doğrusal arama ,büyük boyutlu ve sıralı verilerin aranmasında ikili arama algoritmaları seçilir.
Okumaya devam edin 12-Arama Algoritmaları (Searching Algoritm)
sıralama,bir grup veriyi artan ya da azalan bir
şekilde art arda yerleştirme işlemidir.
!Sıralamalar genellikle küçükten büyüğe doğru.
Okumaya devam edin 11-Sıralama Algoritmaları (Sorting Algorithm)
– Giriş : Belirlenen veri kümesinden algoritma giriş değerleri alır.
– Çıkış : Algoritma her bir giriş kümesinde çıkış değerleri üretir. Bu
değerler problemin çözümüdür.
– Açıklık : Algoritmanın adımları açık olarak tanımlanmalıdır.
– Doğruluk : Algoritma her bir giriş kümesi için doğru çıkış üretmelidir.
– Sonluluk : Algoritma, her bir giriş kümesi için amaçlanan çıkışı, sonlu
işlem adımı(büyük olabilir) sonunda üretmelidir
– Verimlilik : Algoritmanın her bir adımı tam ve sonlu bir zaman diliminde gerçeklenmelidir.
– Genellik : Yordam formdaki her probleme uygulanabilecek şekilde
genel olmalıdır.
Okumaya devam edin 10-Algoritma Analizi, Algoritmalarda Karmaşıklık ve Zaman Karmaşıklığı
Liste : Aralarında doğrusal ilişki olan veriler topluluğudur.
Yığın(stack) ve kuyrukların(Queue) genişletilmesi (üzerindeki sınırlandırılmanın kaldırılması) ile liste yapısına ulaşır.
Bağlı Liste : Verilerin birbirlerine bir işaretçi ile bağlandıkları doğrusal veri yapılarıdır.
Bağlı listeler adres bölgelerinde tutuluyorsa, bu bellek bölgesinin adresinin değerini öğrenebilecek işaretçi üyesine sahip olması gerekir.
! Dinamik bellek yöntemi: Derleyici tarafından işletim sistemi tarafından istenir kullanır ve daha sonra istenirse bu bölge boşaltılır.
Diziler
Diziler doğrusal liste yapısındadır.
Dinamik veri yapıları olup düğüm(node) ismi verilen bellek büyüklükleri kullanılır.
! Bağlı listelerde bir ilk düğüm olması gerekir.Bu düğümün adresi bir değişkende tutularak listedeki diğer düğümlere bu adresten ilerleyerek ulaşılabilir(Listedeki düğümler birbirlerinin adresini tutar). Son düğümün bağ alanına ‘0’ yazarak listenin bitişi belirtilir.
Doğrusal Bağlı Liste
Temel Liste Fonksiyonları
Dinamik Dizi Fonksiyonları
Daha fazla bilgi için : http://www1.gantep.edu.tr/~bingul/c/index.php?ders=13
http://www.cemdemir.net/c-programlama-dili/dinamik-bellek-yonetimi-321.html
Kendi tipinde bir yapıyı gösteren bir işaretçi üyesine sahip yapılara self referential structures(kendine referans yapılar)denir.
struct node{
char info;
struct node*next;
};
yukarıda struct’da char tipi info adlı elemanın yanında struct node yapısında bellek bölgesine işaret eden next pointerına sahiptir.
Bağlı listelerde elemanların sıralı olacak şekilde uygulanmasına sıralı bağlı listeler denir.
Sıralı olmayan bağlı listeler ile arasındaki fark ;eleman ekleme işleminde listeyi sıralı tutacak şekilde dolaşarak araya eklenmesidir.
Sıralı bağlı listelerdeki çıkarma işlemi Sıralı olmayan bağlı listeler ile aynıdır(silinmek istenen eleman bulunana kadar liste üzerinde dolaşıp elemanın listeden çıkarır).
Bağlı Liste Veri Yapısı ve Avantajları
Dizilerde bir eleman silerken arada boşluk kalmaması için sağındaki(ilerisindeki) tüm elemanları bir sola(geriye) kaydırmak gerekir.
Kuyrukların Bağlı Liste Gösterimi
Dairesel Bağlı Listeler
Her düğüm kendinden sonraki düğümü son düğüm ise ilk elemanı gösterir(dairesel yapı).
Çift Bağlı Listeler
Her düğümü iki bağ içerir.Bağlardan biri kendinden önceki diğeri kendinden sonraki düğümü gösterir.Çift bağlı listelerde,tek bağlı listelerdeki geriye doğru listeleme ve dolaşmadaki sorunlar kalkar.
Dairesel Çift Bağlı Listeler
Hem dairesellik hem çift bağlılık özelliklerine sahip listelerdir.
İlk düğümden önceki düğüm son,son düğümden sonraki düğüm ilk düğümdür.
Kuyruk yapısı => FILO(First In Last Out)
Kuyruk(Queue) Temel Fonksiyonlar
createQueue : Boş bir kuyruk oluşturur.
enqueue(q,x) : q kuyruğa x ekler.
dequeue(q) : q kuyruğunun başındaki elemanı siler.
queueEmpty : Kuyruğun boş olup olmadığını bilgisini verir.
queueFull : Kuyruğun dolu olup olmadığını bilgisini verir.
! = Dizinin başında kullanılmayan gözlerolduğu zaman gelen elemanlar kuyruğun sonuna eklendiği için gereksizyer işgal edeceğinden, kuruktan eleman çıkacağı zaman dizinin bütün elemanları öne doğru birer kaydırılmalıdır,(bu sistemin daha yavaş çalışmasına neden olur) yada dairesel kuyruk yapısı kullanılmalıdır(önerilen).
Dairesel kuyruk
Kuyruk başını ve kuyruk sonunu gösteren adreslerin dairesel olarak ilerlediği kuyruk yapısıdır.
Animasyon => http://sdrv.ms/IfaciZ
1.Örnek:
// VeriYapıları8.1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
using namespace std;
#define MAXSIZE 200
int Q[MAXSIZE];//Queue tanımladık
int front = 0,rear = 0;//front : kuyruk başı ,rear: kuyruk arkası(sonu)
void Add(int a)
{
if(rear > MAXSIZE)
{
cout<<"Queue empty..";
}
else
{
Q[rear] = a;
rear++;
cout<<"rear: "<<rear<<"front :"<<front;
}
}
int Del(int a)
{
if(Full())
{
cout<<"Queue empty..";
//return 0;
}
else
{
a = Q[front];
front++;
return a;
}
}
bool Full()
{
if(front == rear)
return true;//true as for Queue empty
else
false;//false as for Queue full
}
int _tmain(int argc, _TCHAR* argv[])
{
int istek = 1;
while(istek == 1)
{
int value;
cout<<"1.Queue add \n\2.Queue delete";
switch(istek)
{
case 1:
cout<<"Value enter:"<<value;
Add(value);
break;
case 2:
int i = Del(value);
cout<<"Del func"<<i<<endl;
break;
default:
cout<<"Invalid selection..."<<endl;
break;
}
cout<<"If you want to continue to select 1";
cin>>istek;
}
system("pause");
return 0;
}
Yığın yapısı ->LIFO(Last In First Out)
Stack Temel Fonksiyonlar
createStack : Belli miktarda eleman alabilecek boş bir stack oluşturur.
push : stack’e veri ekler. “push(s,i)”//s yığınına i değişkeni ekler.
pop : stack’ten veri çıkarır. “i = pop(s)”//s yığının en üsteki elemanın çıkarır i değişkenine atar.
ibrahim kaya 