Showing posts with label veri yapıları. Show all posts
Showing posts with label veri yapıları. Show all posts
Heap Ağacı
//8.Bölüm-Ağaçlar (Heap Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
struct dugum
{
int key;
//İstenilen diğer bilgiler.
};
struct heap
{
struct dugum *dizi;
int kapasite; //Toplam düğüm sayısı. Tutulabilecek en fazla eleman sayısı.
int eleman_sayisi;
};
struct heap *heap_olustur(int kapasite)
{
struct heap *gecici;
gecici=(struct heap *)malloc( sizeof(struct heap) );
if(!gecici)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
gecici->dizi=(struct dugum *)malloc( kapasite*sizeof(struct dugum) );
if(!gecici->dizi)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
gecici->kapasite=kapasite;
gecici->eleman_sayisi=0;
return gecici;
}
/*
void heap_olustur_yeni(struct heap **h,int kapasite)
{
*h=(struct heap *)malloc( sizeof(struct heap) );
if(!*h)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
(*h)->dizi=(struct dugum *)malloc( kapasite*sizeof(struct dugum) );
if(!(*h)->dizi)
{
printf("Dinamik alan ayirma basarisiz...");
exit(1);
}
(*h)->kapasite=kapasite;
(*h)->eleman_sayisi=0;
}
*/
void print_heap(struct heap *heap)
{
int i;
for(i=0;i<heap->eleman_sayisi;i++)
printf("%4d",heap->dizi[i].key);
printf("\n");
}
void initialize_heap(struct heap *heap,int eleman_sayisi,int aralik)
{
int i,j;
int yeni,cik;
srand(time(NULL)); //Her defasında farklı sayılar üretilir.
heap->dizi[0].key=rand()%aralik;
for(i=1;i<eleman_sayisi;i++)
{
while(1)
{
cik=1;
yeni=rand()%aralik;
for(j=0;j<i;j++) //Öncei anahtarlar kontrol edilmektedir.
{
if(yeni==heap->dizi[j].key)
{
cik=0;
break;
}
}
if(!cik) //cik==0
continue;
heap->dizi[i].key=yeni;
break;
}
}
heap->eleman_sayisi=eleman_sayisi;
}
void buble_down(struct heap *heap,int index)
{
int sol,sag;
sol=2*index+1;
sag=2*index+2;
int temp_key;
while( (sol < heap->eleman_sayisi && heap->dizi[index].key < heap->dizi[sol].key) || (sag < heap->eleman_sayisi && heap->dizi[index].key < heap->dizi[sag].key) )
{ /*Sol düğümün olup olmadığı kontrol edilir.
İlk kısım doğruysa ya sağı büyüktür, ya da solu büyüktür.*/
if(sag>=heap->eleman_sayisi || heap->dizi[sol].key > heap->dizi[sag].key) //Sağı yoksa || soldaki sağdakinden büyükse.
{
temp_key=heap->dizi[sol].key;
heap->dizi[sol].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=2*index+1;
}
else
{
temp_key=heap->dizi[sag].key;
heap->dizi[sag].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=2*index+2;
}
sol=2*index+1;
sag=2*index+2;
}
}
void heapify(struct heap *heap)
{
int i;
for(i=heap->eleman_sayisi/2-1;i>=0;i--)
buble_down(heap,i);
}
void buble_up(struct heap *heap,int index) //Eklenen eleman sonrası heap özelliği bozulması sonucu (bozulmayabilir) heap özellği kazandırılıyor.
{
int parent,temp_key;
parent=(index-1)/2;
while(parent>=0 && heap->dizi[parent].key < heap->dizi[index].key)
{
temp_key=heap->dizi[parent].key;
heap->dizi[parent].key=heap->dizi[index].key;
heap->dizi[index].key=temp_key;
index=parent;
parent=(index-1)/2;
}
}
void heap_insert(struct heap *heap,int key)
{
if(heap->eleman_sayisi < heap->kapasite)
{
heap->eleman_sayisi++;
heap->dizi[heap->eleman_sayisi - 1].key=key;
buble_up(heap,heap->eleman_sayisi - 1);
}
}
void delete_max(struct heap *heap) //Sürekli uygulanarak dizi sıralı hale getirilebilir.
{
int temp_key;
if(heap->eleman_sayisi > 1)
{
temp_key=heap->dizi[0].key;
heap->dizi[0].key=heap->dizi[heap->eleman_sayisi - 1].key;
heap->dizi[heap->eleman_sayisi - 1].key=temp_key;
heap->eleman_sayisi--;
buble_down(heap,0);
}
}
void heap_sort(struct heap *heap)
{
int i;
int temp=heap->eleman_sayisi;
for(i=1;i<temp;i++)
delete_max(heap);
heap->eleman_sayisi=temp;
}
int main(int argc, char** argv)
{
struct heap *heap=heap_olustur(20);
/*
struct heap *h1=NULL;
heap_olustur_yeni(&h1,kapasite);
*/
initialize_heap(heap,10,101); //10 tane elaman.
print_heap(heap); //31 87 67 74 9 35 1 47 20 46
heapify(heap);
print_heap(heap); //87 74 67 47 46 35 1 31 20 9
heap_sort(heap);
print_heap(heap); //1 9 20 31 35 46 47 67 74 87
/*
heap_insert(heap,55);
heap_insert(heap,75);
print_heap(heap);
*/
getch();
return 0;
}
void liste_eleman_sil(int silinecek,struct eleman **ListeBasi){
struct dugum *b = *ListeBasi;
struct dugum *a;
while(*BagliListe != NULL){
a = b;
b = b->sonraki;
}
if(b == NULL){
return;
}
else if(b == *ListeBasi){
*ListeBasi = (*ListeBasi)->sonraki;
}
else{
a->sonraki = b->sonraki;
}
free(b);
}
void liste_ters_cevir(struct dugum **BagliListe){
struct dugum *a,*b;
a = NULL;
While(*BagliListe != NULL){
b = *BagliListe;
*BagliListe = (*BagliListe)->sonraki;
b->sonraki = a;
a = b;
}
*BagliListe = a;
}
void tersten_recursive_liste_yaz(struct dugum *ListeBasi){
if(ListeBasi != NULL){
tersten_recursive_liste_yaz(ListeBasi->sonraki);
printf("%d ",ListeBasi->icerik);
}
}
Hash Tablosu
//7.Bölüm-Hash Tables
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
struct CELL
{
char *anahtar;
struct CELL *next;
};
int lookup(char *anahtar,struct CELL *l) //Arama
{
if(l==NULL)
return 0;
else if( !strcmp(anahtar,l->anahtar) ) //Eşitse (string ifadeler eşitse) 0 döndürür. Değili 1.
return 1;
else
return lookup(anahtar,l->next);
}
int insert(char *anahtar,struct CELL **l)
{
if(*l==NULL) //Liste boş ise.
{
*l=(struct CELL *)malloc( sizeof(struct CELL) );
(*l)->anahtar=(char *)malloc( (strlen(anahtar)+1)*sizeof(char) ); //strlen(anahtar)=>string uzunluğu.
strcpy( (*l)->anahtar,anahtar );
(*l)->next=NULL;
return 1;
}
else if( strcmp(anahtar,(*l)->anahtar) )
return insert( anahtar,&( (*l)->next ) );
else
return 0;
}
void print_list(struct CELL *l)
{
if(l!=NULL)
{
printf("%s ",l->anahtar);
print_list(l->next);
}
/*
while(l!=NULL)
{
printf("%s",l->anahtar);
l=l->next;
}
*/
}
struct table_node
{
int counter;
struct CELL *header; //Listenin başlangıç adresini tutar.
};
struct hash_tablosu
{
struct table_node *tablo_basi; //[tablo_basi][tablo_uzunlugu][multiplier]
int tablo_uzunlugu;
int multiplier;
};
unsigned hash(char *anahtar,int multiplier,int table_size)
{
int i=0;
unsigned int value=0;
while(anahtar[i]) //while(anahtar[i]!=NULL)
{
value=( anahtar[i]+multiplier*value )%table_size;
i++;
}
return value;
}
void initialize_hash_table(struct hash_tablosu **hash_table,int multiplier,int table_size)
{
int i;
*hash_table=(struct hash_tablosu *)malloc( sizeof(struct hash_tablosu) );
if(*hash_table==NULL)
{
printf("Hash tablosu icin yer ayrilamadi...");
exit(1);
}
(*hash_table)->tablo_basi=(struct table_node *)malloc( table_size*sizeof(struct table_node) );
if( (*hash_table)->tablo_basi==NULL )
{
printf("Hash tablosu icin yer ayrilamadi...");
exit(1);
}
(*hash_table)->tablo_uzunlugu=table_size;
(*hash_table)->multiplier=multiplier;
for(i=0;i<table_size;i++)
{
( ( (*hash_table)->tablo_basi )+i )->counter=0;
( ( (*hash_table)->tablo_basi )+i )->header=NULL;
}
}
void insert_hash_table(struct hash_tablosu *hash_table,char *anahtar)
{
int hash_index=hash(anahtar,hash_table->multiplier,hash_table->tablo_uzunlugu);
if(insert( anahtar,&( (hash_table->tablo_basi + hash_index)->header) ) );
(hash_table->tablo_basi+hash_index)->counter++;
}
void print_hash_table(struct hash_tablosu *hash_table)
{
if(hash_table) //Null degilse.
{
int index;
printf("----------HASH TABLOSU-------\n");
for(index=0;index<hash_table->tablo_uzunlugu;index++)
{
printf("%5d : (%d) ",index,(hash_table->tablo_basi+index)->counter);
print_list((hash_table->tablo_basi+index)->header);
printf("\n");
}
}
else
printf("Hash tablosu bos...\n");
}
int delete_dugum_liste(struct CELL **header,char *anahtar)
{
struct CELL *simdiki,*onceki;
simdiki=*header;
while( simdiki && strcmp(simdiki->anahtar,anahtar) )
{
onceki=simdiki;
simdiki=simdiki->next;
}
if(!simdiki)
return 0;
if(simdiki==*header)
{
*header=(*header)->next;
}
else
{
onceki->next=simdiki->next;
}
free(simdiki->anahtar);
free(simdiki);
return 1;
}
void delete_hash_table(struct hash_tablosu *table,char *anahtar)
{
int hash_index=hash(anahtar,table->multiplier,table->tablo_uzunlugu);
if(delete_dugum_liste( &( (table->tablo_basi +hash_index)->header ),anahtar) )
(table->tablo_basi + hash_index)->counter--;
}
void liste_yok_et(struct CELL **liste_basi)
{
struct CELL *onceki;
while(*liste_basi)
{
onceki=*liste_basi;
*liste_basi=(*liste_basi)->next;
free(onceki->anahtar);
free(onceki);
}
}
void hash_table_yok_et(struct hash_tablosu **hash_table)
{
int index;
if(*hash_table)
{
for(index=0;index<(*hash_table)->tablo_uzunlugu;index++)
liste_yok_et( &( (*hash_table)->tablo_basi+index )->header );
free( (*hash_table)->tablo_basi );
free(*hash_table);
}
*hash_table=NULL;
}
struct hash_tablosu *hash_table_buyut(struct hash_tablosu **htable,int multiplier,int tablo_uzunlugu)
{
int i;
struct CELL *liste_basi;
struct hash_tablosu *yeni_tablo;
if(!*htable)
return NULL;
initialize_hash_table(¥i_tablo,multiplier,tablo_uzunlugu);
for(i=0;i<(*htable)->tablo_uzunlugu;i++)
{
liste_basi=( (*htable)->tablo_basi + i )->header;
while(liste_basi!=NULL)
{
insert_hash_table(yeni_tablo,liste_basi->anahtar);
liste_basi=liste_basi->next;
}
}
hash_table_yok_et(htable);
return yeni_tablo;
}
int main(int argc, char** argv)
{
struct hash_tablosu *htable;
initialize_hash_table(&htable,7,11);
print_hash_table(htable);
/*
0 [0][NULL]
1 [0][NULL]
...
10[0][NULL]
*/
insert_hash_table(htable,"kadayif");
insert_hash_table(htable,"trabzonspor");
insert_hash_table(htable,"kadayif");
insert_hash_table(htable,"gundogdu");
insert_hash_table(htable,"besiktas");
insert_hash_table(htable,"baklava");
insert_hash_table(htable,"dembaba");
insert_hash_table(htable,"cardozo");
print_hash_table(htable);
/*
0:(1) dembaba
1:(2) kadayif
2:(0)
3:(1) gundogdu
4:(1) trabzonspor
5:(0)
6:(0)
7:(2) baklava cardozo
8:(1) besiktas
9:()
10:()
*/
htable=hash_table_buyut(&htable,17,19);
print_hash_table(htable);
/*
0:(0)
1:(0)
2:(0)
3:(0)
4:(1) kadayif
5:(0)
6:(0)
7:(1) cardozo
8:(0)
9:(2) dembaba baklava
10:(0)
11:(0)
12:(1) trabzonspor
13:(0)
14:(1) gundogdu
15:(0)
16:(0)
17:(0)
18:(1) besiktas
*/
getch();
return 0;
}
Ağaçlar (AVL Ağacı)
//6.Bölüm-Ağaçlar (AVL Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct node
{
int key;
struct node *left;
struct node *right;
int height; //Derinlik.
};
int max(int a,int b)
{
return a>b ? a:b; //Doğru ise a, yanlış ise b döndürülür.
}
struct node *newNode(int key)
{
struct node *node=(struct node *)malloc( sizeof(struct node) );
node->key=key;
node->left=node->right=NULL;
node->height=1;
return node;
}
int height(struct node *node)
{
if(node==NULL)
return 0;
return node->height;
}
struct node *rightRotate(struct node *y) //Sol-Sol Durumu.
{
struct node *x=y->left, *T=x->right;
x->right=y;
y->left=T;
y->height=max( height(y->left),height(y->right) )+1;
x->height=max( height(x->left),height(x->right) )+1;
return x;
}
struct node *leftRotate(struct node *x) //Sağ-Sağ Durumu.
{
struct node *y=x->right, *T=y->left;
y->left=x;
x->right=T;
x->height=max( height(x->left),height(x->right) )+1;
y->height=max( height(y->left),height(y->right) )+1;
return y;
}
int getBalance(struct node *node)
{
if(node==NULL) //Ağaç NULL ise.
return 0;
return height(node->left) - height(node->right);
}
struct node *insert(struct node *node,int key)
{
int balance;
if(node==NULL)
return newNode(key);
if(key < node->key)
node->left=insert(node->left,key);
else
node->right=insert(node->right,key);
node->height=max( height(node->left),height(node->right) )+1;
balance=getBalance(node);
if(balance>1 && key < node->left->key) //Sol-Sol Durumu.
return rightRotate(node);
if(balance<-1 && key > node->right->key) //Sağ-Sağ Durumu.
return leftRotate(node);
if(balance>1 && key > node->left->key) //Sol-Sağ Durumu.
{
node->left=leftRotate(node->left);
return rightRotate(node);
}
if(balance<-1 && key < node->right->key) //Sağ-Sol Durumu
{
node->right=rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preorder_yardimci(struct node *node)
{
if(node!=NULL)
{
printf("%d (%d) ",node->key,node->height);
preorder_yardimci(node->left);
preorder_yardimci(node->right);
}
}
void preorder(struct node *node)
{
preorder_yardimci(node);
printf("\n");
}
struct node *minValueNode(struct node *root)
{
struct node *current=root;
if(current==NULL)
return NULL;
while(current->left)
current=current->left;
return current;
}
struct node *deleteNode(struct node *root,int key)
{
if(root==NULL)
return root;
if(key < root->key) //Sol taraftan gidilir.
root->left=deleteNode(root->left,key);
else if(key > root->key) //Sağ taraftan gidilir.
root->right=deleteNode(root->right,key);
else //Silinen düğüme göre kontroller yapılır.
{
if(root->left==NULL || root->right==NULL) //Düğüm yaprak ise...
{
struct node *temp=root->left ? root->left:root->right; //if true:if false
if(temp==NULL)
{
temp=root;
root=NULL;
}
else
*root=*temp; //İcerikler kopyalanıyor.
/*root->key=temp->key;
root->right=temp->right;
root->left=temp->left*/
free(temp);
}
else
{
struct node *temp=minValueNode(root->right);
root->key=temp->key;
root->right=deleteNode(root->right,temp->key);
}
}
if(root==NULL)
return root;
root->height=max( height(root->left),height(root->right) )+1;
int balance=getBalance(root);
if( balance>1 && getBalance(root->left)>=0 )
return rightRotate(root);
if( balance>1 && getBalance(root->left)<0 )
{
root->left=leftRotate(root->left);
return rightRotate(root);
}
if(balance<-1 && getBalance(root->right)<=0)
return leftRotate(root);
if(balance<-1 && getBalance(root->right)>0)
{ root->right=rightRotate(root->right);
return leftRotate(root);
}
return root;
}
int main(int argc, char** argv)
{
struct node *root=NULL;
root=insert(root,90);
root=insert(root,150);
root=insert(root,173);
root=insert(root,73);
root=insert(root,40);
root=insert(root,80);
root=insert(root,160);
root=insert(root,180);
preorder(root); //90(4) 73(2) 40(1) 80(1) 160(3) 150(1) 173(2) 180(1)
/*
root=deleteNode(root,90);
root=deleteNode(root,160);
root=deleteNode(root,73);
root=deleteNode(root,80);
root=deleteNode(root,40);
root=deleteNode(root,173);
root=deleteNode(root,180);
root=deleteNode(root,150);
*/
getch();
return 0;
}
struct dugum* EnKucukDugum(struct dugum *BagliListe){
struct dugum *EnKucuk = NULL;
struct dugum *ListedeGez = BagliListe;
int EnKucukDeger = ListedeGez->icerik;
While(ListedeGez != NULL){
if(ListedeGez->icerik <= EnKucukDeger){
EnKucukDeger = ListedeGez->icerik;
EnKucuk= ListedeGez;
}
ListedeGez = ListedeGez->sonraki;
return EnKucuk;
}
Kendisine gönderilen ikili arama ağacındaki tek çocuk düğüme sahip olan düğümlerin sayısını veren fonksiyonun c kodu
int TekCocukluDugumSayisi(struct dugum *agac){
if(agac->sag != NULL && agac->sol != NULL){
return TekCocukluDugumSayisi(agac->sol) + TekCocukluDugumSayisi(agac->sag);
}
else if(agac->sag == NULL && agac->sol != NULL){
return 1 + TekCocukluDugumSayisi(agac->sol);
}
else if(agac->sag != NULL && agac->sol == NULL){
return 1 + TekCocukluDugumSayisi(agac->sag);
}
else{
return 0;
}
}
Ağaçlar(İkili Arama Ağacı)
//5.Bölüm-Ağaçlar (İkili Arama Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct dugum
{
int icerik;
struct dugum *sol;
struct dugum *sag;
};
struct ikili_arama_agaci
{
struct dugum *kok; //En tepedeki kısım
};
void ikili_arama_agaci_olustur(struct ikili_arama_agaci **agac)
{
*agac=(struct ikili_arama_agaci *)malloc( sizeof(struct ikili_arama_agaci) ); //4 Bayt'lık yer ayrıldı. (Pointer=>4 Bayt)
if(*agac==NULL)
{
printf("Heap'te gerekli yer ayrilmadi...");
exit(1);
}
(*agac)->kok=NULL;
}
int ikili_agac_bosmu(struct ikili_arama_agaci *agac)
{
if(agac->kok==NULL)
return 1;
else
return 0;
}
struct dugum *dugum_olustur(int icerik)
{
struct dugum *d=(struct dugum *)malloc( sizeof(struct dugum) ); //12 Bayt'lık yer ayrıldı.
if(d==NULL)
{
printf("Heap'te gerekli yer ayrilmadi...");
exit(1);
}
d->icerik=icerik; //(*d).icerik=icerik
d->sol=d->sag=NULL; //Önce sag'a NULL atanıyor sonra bu değer sol'a aktarılıyor.
return d;
}
void ekle(struct ikili_arama_agaci *agac,int icerik)
{
struct dugum *dugum;
struct dugum *d;
struct dugum *geri; //[ ][icerik][geri]
d=agac->kok;
while(d!=NULL)
{
geri=d;
if(icerik < d->icerik)
d=d->sol;
else if(icerik > d->icerik)
d=d->sag;
else
return;
}
dugum=dugum_olustur(icerik);
if(agac->kok==NULL)
{
agac->kok=dugum;
return;
}
if(icerik < geri->icerik)
geri->sol=dugum;
else
geri->sag=dugum;
}
void inorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
inorder_yardimci(kok->sol);
printf("%4d ",kok->icerik);
inorder_yardimci(kok->sag);
}
void inorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
inorder_yardimci(agac->kok);
printf("\n");
}
void preorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
printf("%4d ",kok->icerik);
preorder_yardimci(kok->sol);
preorder_yardimci(kok->sag);
}
void preorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
preorder_yardimci(agac->kok);
printf("\n");
}
void postorder_yardimci(struct dugum *kok)
{
if(kok==NULL)
return;
postorder_yardimci(kok->sol);
postorder_yardimci(kok->sag);
printf("%4d ",kok->icerik);
}
void postorder(struct ikili_arama_agaci *agac)
{
if(agac==NULL)
return;
postorder_yardimci(agac->kok);
printf("\n");
}
int dugum_sayisi(struct dugum *kok)
{
if(kok==NULL)
return 0;
return 1+dugum_sayisi(kok->sol)+dugum_sayisi(kok->sag);
}
int yaprak_sayisi(struct dugum *kok)
{
if(kok==NULL)
return 0;
if(kok->sol==NULL && kok->sag==NULL)
return 1;
else
return yaprak_sayisi(kok->sol)+yaprak_sayisi(kok->sag);
}
void sil(struct ikili_arama_agaci *agac,int silinen)
{
struct dugum *d=agac->kok;
struct dugum *parent=NULL; //Silinen elemanın bir üstü.
struct dugum *d1,*d2;
int sol; //Parentin solundan.
while(d!=NULL)
{
if(silinen < d->icerik) //Silinmeye soldan devam edilir.
{
parent=d;
d=d->sol;
sol=1; //Silinen elemana nereden yaklaşıldığını tespit etmek için.
}
else if(silinen > d->icerik)
{
parent=d;
d=d->sag;
sol=0;
}
else
break;
}
if(d==NULL)
return;
if(d->sol==NULL) //Silinen düğümün solu boş.
{
if(parent==NULL)
agac->kok=d->sag;
else
{
if(sol==1)
parent->sol=d->sag;
else
parent->sag=d->sag;
}
}
else if(d->sag==NULL) //Silinen düğümün sağı boş.
{
if(parent==NULL)
agac->kok=d->sol;
else
{
if(sol==1)
parent->sol=d->sol;
else
parent->sag=d->sol;
}
}
else //Silinen düğümün hem sağı hem de solu dolu.
{ //Silinecek düğümün solunun en sağına git.
//En sağdaki düğüm silinen düğümün konumunu alır.
d1=d->sol;
d2=NULL;
while(d1->sag!=NULL)
{
d2=d1;
d1=d1->sag;
}
if(d2!=NULL)
{
d2->sag=d1->sol;
d1->sol=d->sol;
}
d1->sag=d->sag;
if(parent==NULL)
agac->kok=d1; //Ağacın kökü değişti.
else
{
if(sol==1)
parent->sol=d1;
else
parent->sag=d1;
}
}
/*else //Silinen düğümün hem sağı hem de solu dolu.
{ //Silinecek düğümün sağının en soluna git.
//En soldaki düğüm silinen düğümün konumunu alır.
d1=d->sag;
d2=NULL;
while(d1->sol!=NULL)
{
d2=d1;
d1=d1->sol;
}
if(d2!=NULL)
{
d2->sag=d1->sag;
d1->sol=d->sag;
}
d1->sag=d->sol;
if(parent==NULL)
agac->kok=d1; //Ağacın kökü değişti.
else
{
if(sol==1)
parent->sol=d1;
else
parent->sag=d1;
}
}*/
}
void yoket(struct dugum **kok) //Kök değişeceği için ** .
{
if(*kok!=NULL)
{
yoket( &(*kok)->sol );
yoket( &(*kok)->sag );
free(*kok);
*kok=NULL;
}
}
int main()
{
struct ikili_arama_agaci *agac; //Başlangıç değeri random bir değer.
ikili_arama_agaci_olustur(&agac);
/*Not 1:
Yazdırma Biçimleri: 100
Inorder: 5-80-100-200 80 200
Preorder: 100-80-5-200 5
Postorder: 5-80-200-100
*/
/*Not 2:
struct dugum d; => Nesnenin kendisi. (*d).icerik şeklinde bir tanımlama olamaz!
struct dugum *p; => Nesnenin göstericisi. (*p).icerik || p->icerik şeklinde tanımlanabilir.
*/
/*Not 3:
ekle(agac,100); 100
ekle(agac,80); 80 120
ekle(agac,45); 45 167
ekle(agac,120); 150
ekle(agac,167);
ekle(agac,150);
inorder(agac); //45 80 100 120 150 167
preorder(agac); //100 80 45 120 167 150
postorder(agac); //45 80 150 167 120 100
printf( "Dugum Sayisi: %4d\n",dugum_sayisi(agac->kok) ); //Düğüm Sayısı:6
printf( "Yaprak Sayisi: %4d\n",yaprak_sayisi(agac->kok) ); //Yaprak Sayısı:2
*/
ekle(agac,100);
ekle(agac,50);
ekle(agac,200);
ekle(agac,25);
ekle(agac,75);
ekle(agac,20);
ekle(agac,35);
ekle(agac,98);
ekle(agac,99);
ekle(agac,500);
ekle(agac,400);
ekle(agac,300);
ekle(agac,210);
ekle(agac,375);
inorder(agac); //20 25 35 50 75 98 99 100 200 210 300 375 400 500
preorder(agac); //100 50 25 20 35 75 98 99 200 500 400 300 210 375
postorder(agac); //20 35 25 99 98 75 50 210 375 300 400 500 200 100
/*
[100]----
[50] [200]--------
[25] [75] [500]
[20][35] [98] [400]
[99] [300]
[210][375]
*/
//sil(agac,50);
//preorder(agac);
//yoket(&agac->kok);
//preorder(agac);
getch();
return 0;
}
(Yığın (Dinamik Liste))
//4.Bölüm-Yığın (Dinamik Liste Şeklinde)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define SENTINEL -10000000
struct dugum
{
int icerik;
struct dugum *link;
};
struct dugum *dugum_olustur(int icerik)
{
struct dugum *d;
d=(struct dugum *)malloc( sizeof(struct dugum) );
if(d==NULL)
{
printf("Yer ayrilamadi...");
exit(1);
}
d->icerik=icerik;
d->link=NULL;
return d;
}
void ekle(int icerik,struct dugum **dugum_gostergesi)
{
struct dugum *d=dugum_olustur(icerik);
d->link=*dugum_gostergesi;
*dugum_gostergesi=d;
}
void yazdir(struct dugum *yigin_gostergesi)
{
while(yigin_gostergesi)
{
printf("%4d ",yigin_gostergesi->icerik);
yigin_gostergesi=yigin_gostergesi->link;
}
printf("\n");
}
void yazdir_yanlis(struct dugum **yigin_gostergesi) //Mantık hatası!
{
while(*yigin_gostergesi)
{
printf("%4d ",(*yigin_gostergesi)->icerik);
*yigin_gostergesi=(*yigin_gostergesi)->link;
}
printf("\n");
}
int cikar(struct dugum **yigin_gostergesi)
{
struct dugum *d;
int icerik;
if(*yigin_gostergesi==NULL)
return SENTINEL;
d=*yigin_gostergesi;
*yigin_gostergesi=(*yigin_gostergesi)->link;
icerik=d->icerik;
free(d);
//return d->icerik; //Hata! d silindiği için içeriğe erişilemez.
return icerik;
}
int yigin_bosmu(struct dugum *yigin_isaretcisi)
{
if(yigin_isaretcisi==NULL)
return 1; //0'ın haricindekiler true olduğu için return -1 de yazılabilir.
else
return 0;
}
int main()
{
int a;
struct dugum *yigin_gostergesi=NULL;
ekle(100,&yigin_gostergesi);
ekle(20,&yigin_gostergesi);
ekle(60,&yigin_gostergesi);
yazdir(yigin_gostergesi); // 60 20 100
yazdir(yigin_gostergesi); // 60 20 100
//yazdir_yanlis(&yigin_gostergesi); //1.seferde elemanlar ekrana yazılacaktır.
//yazdir_yanlis(&yigin_gostergesi); //Ancak 2.seferde ve sonrası için ekrana yazılmayacaktır.
a=cikar(&yigin_gostergesi); //Yığının en tepesindeki eleman dışarıya çıkarılacaktır.
if(a!=SENTINEL)
printf("%4d \n",a); //60
yazdir(yigin_gostergesi); //20 100
getch();
return 0;
}
Yığın
//3.Bölüm-Yığın#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define SENTINEL -10000000
struct yigin //Yığın veri yapısı tanımlandı.
{
int *dizi;
int ust;
int kapasite;
};
struct yigin *yigin_olustur(int kapasite) //Yığın oluşturma 1.Yol
{
if(kapasite<=0)
{
printf("Kapasite pozitif bir tamsayi olmali...");
exit(1); //Program başarıyla sonlandırıldı.
}
struct yigin *ptr=(struct yigin *)malloc( sizeof(struct yigin) ); //Yığının boyutu kadar yer ayrıldı (12 Bayt).
ptr->dizi=(int *)malloc( kapasite*sizeof(int) );
ptr->ust=-1;
ptr->kapasite=kapasite;
return ptr;
}
void yigin_olustur_parametre_ile(int kapasite,struct yigin **y) //Yığın oluşturma 2.Yol
{ //**y => Alınan adresde değişiklik yapılacağı için.
if(kapasite<=0)
{
printf("Kapasite pozitif bir tamsayi olmali...");
exit(1); //Program başarıyla sonlandırıldı.
}
*y=(struct yigin *)malloc( sizeof(struct yigin) );
(*y)->dizi=(int *)malloc( kapasite*sizeof(int) );
(*y)->ust=-1;
(*y)->kapasite=kapasite;
}
int yigin_bosmu(struct yigin *y)
{
if(y->ust==-1)
return 1; //Yığın boş.
else
return 0; //Yığın boş değil.
}
int yigin_dolumu(struct yigin *y)
{
if(y->ust==y->kapasite-1)
return 1;
else
return 0;
}
void yigin_ekle(int eleman,struct yigin *y)
{
if( yigin_dolumu(y) )
{
printf("Yigin dolu ekleme yapilamiyor...");
return;
}
y->dizi[++y->ust]=eleman;
}
void yigin_yok_et(struct yigin **y) //A'nın tuttuğu adres değiştirileceği için ** .
{
free( (*y)->dizi );
free(*y);
*y=NULL;
}
struct yigin *kapasiteyi_artir(struct yigin **ptr,int kackat) //Kapasite artırma 1.Yol
{
struct yigin *yeni;
int i;
yeni=yigin_olustur( kackat*( (*ptr)->kapasite) ); //Eskisi yeniye kopyalandı.
for(i=0;i<=(*ptr)->ust;i++)
yeni->dizi[i]=(*ptr)->dizi[i];
yeni->ust=(*ptr)->ust;
yigin_yok_et( &(*ptr) ); //yigin_yok_et(ptr);
return yeni;
}
void kapasiteyi_artir_yeni(struct yigin **ptr,int kackat) //Kapasite artırma 2.Yol
{
struct yigin *yeni;
int i;
yeni=yigin_olustur( kackat*( (*ptr)->kapasite) );
for(i=0;i<=(*ptr)->ust;i++)
yeni->dizi[i]=(*ptr)->dizi[i];
yeni->ust=(*ptr)->ust;
yigin_yok_et( &(*ptr) ); //yigin_yok_et(ptr);
*ptr=yeni;
}
void yigin_yaz(struct yigin *y)
{
int i;
printf("Yigin Kapasitesi :%d\n",y->kapasite);
printf("Yigindaki Eleman Sayisi:%d\n ",y->ust+1);
for(i=y->ust;i>=0;i--)
{
printf("%4d ",y->dizi[i]);
}
printf("\n");
}
int yigin_eleman_sil(struct yigin *y)
{
if( yigin_bosmu(y) )
return SENTINEL;
return y->dizi[y->ust--];
}
int main()
{
struct yigin *A=NULL;
struct yigin *B=NULL;
int silinen;
A=yigin_olustur(10); //Kapasitesi 10 olan yığın oluşturuluyor.
//yigin_olustur_parametre_ile(10,&A);
yigin_ekle(12,A);
yigin_ekle(56,A);
yigin_ekle(-20,A); //En son eklenen eleman yığının en tepesine eklenir.
yigin_yaz(A); //-20 56 12
silinen=yigin_eleman_sil(A); //Yığının başındaki elemandan silinmeye başlanır.
printf("\nSilinen:%4d\n",silinen);
yigin_yaz(A); //56 12
yigin_ekle(100,A); //Yığının başına 100 elemanı eklenir. Sonuna eklenmez.
yigin_yaz(A); //100 56 12
//A=kapasiteyi_artir(&A,3); //1.Yol
kapasiteyi_artir_yeni(&A,3); //2.Yol
yigin_yaz(A); //100 56 12
//En son yığın kapasitesi 30 olur.
getch();
return 0;
}