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;
}
}