Veri Yapıları | Ahmet Cevahir ÇINAR

Veri Yapıları

Eki 13, 2017 |

İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme Nasıl Yapılır?

İkili ağaç, her düğümünde en fazla iki düğüm bağlı olan ağaç yapısıdır. İkili arama ağacı ise kök düğümün solunda kökten küçük değerlerin, sağında ise kökten büyük değerlerin sıralandığı araçtır.

İkili ağaç, rekürsif(özyineli) bir yapıdadır. İkili ağaçlara Directed Acyclic Graph(DAG) ismi de verilmektedir.

Aynı sayıları farklı sıralarda eklersek farklı ikili arama ağaçları oluşur.

Ağaçta dolaşmak için infix, prefix ve postfix stratejileri bulunur.

infix-> LNR, RNL -> Sol-Kök-Sağ veya Sağ-Kök-Sol
prefix -> NLR, NRL -> Kök-Sol-Sağ veya Kök-Sağ-Sol
postfix -> LRN, RLN -> Sol-Sağ-Kök veya Sağ-Sol-Kök

Şadi Evren ŞEKER’in anlatımındaki İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme yapan kod aşağıdadır:

#include <stdio.h>
#include <stdlib.h>
struct n{
	int data;
	n * sol;
	n * sag;
};
typedef n node;
node * ekle (node *agac,int x){
	if(agac == NULL){
		node *root= (node *)malloc(sizeof(node));
		root -> sol = NULL;
		root -> sag = NULL;
		root -> data = x;
		return root;
	}
	
	if(agac->data < x){
		agac->sag = ekle(agac->sag,x);
		return agac;
	}
	agac->sol = ekle (agac->sol,x);
	return agac;
}
void dolas(node *agac){
	if(agac == NULL)
		return;
	printf("%d ",agac->data);
	dolas(agac->sag);
	dolas(agac->sol);
}
int bul (node * agac,int aranan){
	if(agac == NULL)
		return -1;
	if(agac->data == aranan)
		return 1;
	if(bul(agac->sag,aranan)==1)
		return 1;
	if(bul(agac->sol,aranan)==1)
		return 1;
	return -1;
}
int max(node *agac){

	while(agac->sag!=NULL)
		agac=agac->sag;
	return agac->data;
}
int min(node *agac){
	while(agac->sol!=NULL)
		agac=agac->sol;
	return agac->data;
}
node * sil(node *agac,int x){
	if(agac==NULL)
		return NULL;
	if(agac->data == x){
		if(agac->sol==NULL && agac->sag==NULL)
			return NULL;
		if(agac->sag!=NULL){
			agac->data = min(agac->sag);
			agac->sag = sil(agac->sag, min(agac->sag));
			return agac;
		}
		agac->data = max(agac->sol);
		agac->sol = sil(agac->sol,max(agac->sol));
		return agac;
	}	
	if(agac->data < x){
		agac->sag = sil(agac->sag,x);
		return agac;
	}
	agac->sol= sil(agac->sol,x);
	return agac;
	

}
int main(){
	node * agac=NULL;
	agac=ekle(agac,56);
	agac=ekle(agac,200);
	agac=ekle(agac,26);
	agac=ekle(agac,190);
	agac=ekle(agac,213);
	agac=ekle(agac,18);
	agac=ekle(agac,28);
	agac=ekle(agac,12);
	agac=ekle(agac,24);
	agac=ekle(agac,27);
	dolas(agac);	
	printf("arama sonucu: %d",bul(agac,24));
	printf("max = %d min = %d",max(agac),min(agac));
	agac= sil(agac,56);
	dolas(agac);
}

#include <stdio.h>

#include <stdlib.h>

struct n{

int data;

n * sol;

n * sag;

};

typedef n node;

node * ekle (node *agac,int x){

if(agac == NULL){

node *root= (node *)malloc(sizeof(node));

root -> sol = NULL;

root -> sag = NULL;

root -> data = x;

return root;

}

if(agac->data < x){

agac->sag = ekle(agac->sag,x);

return agac;

}

agac->sol = ekle (agac->sol,x);

return agac;

}

void dolas(node *agac){

if(agac == NULL)

return;

printf("%d ",agac->data);

dolas(agac->sag);

dolas(agac->sol);

}

int bul (node * agac,int aranan){

if(agac == NULL)

return -1;

if(agac->data == aranan)

return 1;

if(bul(agac->sag,aranan)==1)

return 1;

if(bul(agac->sol,aranan)==1)

return 1;

return -1;

}

int max(node *agac){

while(agac->sag!=NULL)

agac=agac->sag;

return agac->data;

}

int min(node *agac){

while(agac->sol!=NULL)

agac=agac->sol;

return agac->data;

}

node * sil(node *agac,int x){

if(agac==NULL)

return NULL;

if(agac->data == x){

if(agac->sol==NULL && agac->sag==NULL)

return NULL;

if(agac->sag!=NULL){

agac->data = min(agac->sag);

agac->sag = sil(agac->sag, min(agac->sag));

return agac;

}

agac->data = max(agac->sol);

agac->sol = sil(agac->sol,max(agac->sol));

return agac;

}

if(agac->data < x){

agac->sag = sil(agac->sag,x);

return agac;

}

agac->sol= sil(agac->sol,x);

return agac;

}

int main(){

node * agac=NULL;

agac=ekle(agac,56);

agac=ekle(agac,200);

agac=ekle(agac,26);

agac=ekle(agac,190);

agac=ekle(agac,213);

agac=ekle(agac,18);

agac=ekle(agac,28);

agac=ekle(agac,12);

agac=ekle(agac,24);

agac=ekle(agac,27);

dolas(agac);

printf("arama sonucu: %d",bul(agac,24));

printf("max = %d min = %d",max(agac),min(agac));

agac= sil(agac,56);

dolas(agac);

}

Arama Directed Acyclic Graph(DAG)Dolaşma düğüm Ekleme En Büyük Eleman Bulma En Küçük Eleman Bulma İkili ağaç İkili Arama Ağacı INFIX POSTFIX PREFIX Silme

Eki 12, 2017 |

Yorum Yok

Dairesel Bağlı Listede Ekleme, Sıralı Ekleme ve Silme İşlemi Nasıl Yapılır?

Şadi Evren ŞEKER’in anlatımındaki kod:

#include <stdio.h>
#include <stdlib.h>

struct n{
 int x;
 struct n * next;
};

typedef struct n node;

void bastir( node * r){
  node * iter=r;
  printf("%d ", iter->x);
  iter = iter -> next;
 while (iter != r){
  printf("%d ", iter->x);
  iter = iter -> next;
 }
 printf("\n");
}

void ekle( node * r, int x){
  node * iter=r;
 while( iter -> next != r){
  iter =iter -> next;
 }
 iter->next=( node * ) malloc ( sizeof ( node ) );
 iter->next->x=x;
 iter->next->next=r;
}

node * ekleSirali ( node * r, int x){
 if( r == NULL){ 
  r = (node *) malloc ( sizeof ( node) );
  r -> next = r;
  r -> x = x;
  return r;
 }
 if(r->x > x){ 
  node * temp = ( node * ) malloc ( sizeof ( node ) );
  temp -> x = x;
  temp -> next = r;
  node * iter=r;
  while(iter->next!=r){
    iter=iter->next;
  }
  iter->next=temp;
  return temp;
 }
 node * iter = r;
 while( iter -> next != r && iter -> next -> x < x ){
  iter = iter -> next;
 }

 node * temp = (node*)malloc(sizeof(node));
 temp->next = iter->next;
 iter->next = temp;
 temp->x = x;
 return r;
}

node * sil(node *r, int x){
 node *temp;
 node *iter = r;
 if( r->x == x){
   while(iter->next!=r){
     iter=iter->next;
   }
   iter->next=r->next;
   free(r);
   return iter->next;
 }
 
 while ( iter->next != r && iter->next->x != x){
  iter = iter->next;
 }
 if ( iter->next == r){
  printf( "Sayi bulunamadi!\n" );
  return r;
 }
 temp = iter->next;
 iter->next = iter->next->next; 
 free (temp);
 return r;
}

int main ()
{
 node * root;
 root = NULL;
 root = ekleSirali( root, 400);
  bastir(root);
 root = ekleSirali( root, 40);
   bastir(root);
 root = ekleSirali( root, 4);
   bastir(root);
 root = ekleSirali( root, 450);
   bastir(root);
 root = ekleSirali( root, 50);
   bastir(root);
 root = sil( root, 50);
 bastir(root);
 root = sil( root, 999);
 bastir(root);
 root = sil( root, 4);
 bastir(root);
 root = sil( root, 450);
 bastir(root);
}

100

101

102

103

104

105

106

107

108

109

#include <stdio.h>

#include <stdlib.h>

struct n{

int x;

struct n * next;

};

typedef struct n node;

void bastir( node * r){

node * iter=r;

printf("%d ", iter->x);

iter = iter -> next;

while (iter != r){

printf("%d ", iter->x);

iter = iter -> next;

}

printf("\n");

}

void ekle( node * r, int x){

node * iter=r;

while( iter -> next != r){

iter =iter -> next;

}

iter->next=( node * ) malloc ( sizeof ( node ) );

iter->next->x=x;

iter->next->next=r;

}

node * ekleSirali ( node * r, int x){

if( r == NULL){

r = (node *) malloc ( sizeof ( node) );

r -> next = r;

r -> x = x;

return r;

}

if(r->x > x){

node * temp = ( node * ) malloc ( sizeof ( node ) );

temp -> x = x;

temp -> next = r;

node * iter=r;

while(iter->next!=r){

iter=iter->next;

}

iter->next=temp;

return temp;

}

node * iter = r;

while( iter -> next != r && iter -> next -> x < x ){

iter = iter -> next;

}

node * temp = (node*)malloc(sizeof(node));

temp->next = iter->next;

iter->next = temp;

temp->x = x;

return r;

}

node * sil(node *r, int x){

node *temp;

node *iter = r;

if( r->x == x){

while(iter->next!=r){

iter=iter->next;

}

iter->next=r->next;

free(r);

return iter->next;

}

while ( iter->next != r && iter->next->x != x){

iter = iter->next;

}

if ( iter->next == r){

printf( "Sayi bulunamadi!\n" );

return r;

}

temp = iter->next;

iter->next = iter->next->next;

free (temp);

return r;

}

int main ()

{

node * root;

root = NULL;

root = ekleSirali( root, 400);

bastir(root);

root = ekleSirali( root, 40);

bastir(root);

root = ekleSirali( root, 4);

bastir(root);

root = ekleSirali( root, 450);

bastir(root);

root = ekleSirali( root, 50);

bastir(root);

root = sil( root, 50);

bastir(root);

root = sil( root, 999);

bastir(root);

root = sil( root, 4);

bastir(root);

root = sil( root, 450);

bastir(root);

}

Bağlı Liste Dairesel Dairesel Bağlı Liste Ekleme Silme sıralı ekleme

Eki 10, 2017 |

Yorum Yok

Bağlı listeden eleman silme

Bağlı listeden eleman silme, Şadi Evren ŞEKER’in anlatımındaki kod:

#include <stdio.h>
#include <stdlib.h>

struct n{
 int x;
 struct n * next;
};

typedef struct n node;

void bastir( node * r){
 while (r != NULL){
  printf("%d ", r->x);
  r = r -> next;
 }
 printf("\n");
}

void ekle( node * r, int x){
 while( r -> next != NULL){
  r =r -> next;
 }
 r -> next = ( node *) malloc (sizeof (node ) );
 r -> next -> x = x;
 r -> next -> next = NULL;
 
}

node * ekleSirali ( node * r, int x){
 if( r == NULL){ //link list božsa
  r = (node *) malloc ( sizeof ( node) );
  r -> next = NULL;
  r -> x = x;
  return r;
 }
 if(r -> x > x){ 
  node * temp = ( node * ) malloc ( sizeof ( node ) );
  temp -> x = x;
  temp -> next = r;
  r = temp;
  return temp;
 }
 node * iter = r;
 while( iter -> next != NULL && iter -> next -> x < x ){
  iter = iter -> next;
 }

 node * temp = (node*)malloc(sizeof(node));
 temp->next = iter->next;
 iter->next = temp;
 temp->x = x;
 return r;
}

node * sil(node *r, int x){
 node *temp;
 node *iter = r;
 if( r->x == x){
  temp = r;
  r = r->next;
  free (temp);
  return r;
 }
 
 while ( iter->next != NULL && iter->next->x != x){
  iter = iter->next;
 }
 if ( iter->next == NULL){
  printf( "Sayi bulunamadi!\n" );
  return r;
 }
 temp = iter->next;
 iter->next = iter->next->next; 
 free (temp);
 return r;
}

int main ()
{
 node * root;
 root = NULL;
 root = ekleSirali( root, 400);
 root = ekleSirali( root, 40);
 root = ekleSirali( root, 4);
 root = ekleSirali( root, 450);
 root = ekleSirali( root, 50);
 bastir(root);
 root = sil( root, 50);
 bastir(root);
 root = sil( root, 999);
 bastir(root);
 root = sil( root, 4);
 bastir(root);
 root = sil( root, 450);
 bastir(root);  
}

#include <stdio.h>

#include <stdlib.h>

struct n{

int x;

struct n * next;

};

typedef struct n node;

void bastir( node * r){

while (r != NULL){

printf("%d ", r->x);

r = r -> next;

}

printf("\n");

}

void ekle( node * r, int x){

while( r -> next != NULL){

r =r -> next;

}

r -> next = ( node *) malloc (sizeof (node ) );

r -> next -> x = x;

r -> next -> next = NULL;

}

node * ekleSirali ( node * r, int x){

if( r == NULL){ //link list božsa

r = (node *) malloc ( sizeof ( node) );

r -> next = NULL;

r -> x = x;

return r;

}

if(r -> x > x){

node * temp = ( node * ) malloc ( sizeof ( node ) );

temp -> x = x;

temp -> next = r;

r = temp;

return temp;

}

node * iter = r;

while( iter -> next != NULL && iter -> next -> x < x ){

iter = iter -> next;

}

node * temp = (node*)malloc(sizeof(node));

temp->next = iter->next;

iter->next = temp;

temp->x = x;

return r;

}

node * sil(node *r, int x){

node *temp;

node *iter = r;

if( r->x == x){

temp = r;

r = r->next;

free (temp);

return r;

}

while ( iter->next != NULL && iter->next->x != x){

iter = iter->next;

}

if ( iter->next == NULL){

printf( "Sayi bulunamadi!\n" );

return r;

}

temp = iter->next;

iter->next = iter->next->next;

free (temp);

return r;

}

int main ()

{

node * root;

root = NULL;

root = ekleSirali( root, 400);

root = ekleSirali( root, 40);

root = ekleSirali( root, 4);

root = ekleSirali( root, 450);

root = ekleSirali( root, 50);

bastir(root);

root = sil( root, 50);

bastir(root);

root = sil( root, 999);

bastir(root);

root = sil( root, 4);

bastir(root);

root = sil( root, 450);

bastir(root);

}

Ekran çıktısı:

Bağlı Liste Bağlı listeden eleman silme

Eki 10, 2017 |

Yorum Yok

Bağlı listede araya ekleme ve sıralı ekleme nasıl yapılır?

Şadi Evren ŞEKER’in anlatımı sırasında kullandığı kod aşağıdadır:

#include <stdio.h>
#include <stdlib.h>

typedef struct n{
	int x;
	struct n * next;
} node;

typedef struct n node;

void bastir(node * r){
    while(r!=NULL){
        printf("%d\n",r->x);
        r=r->next;
    }
}

node * ekleSirali(node *r,int x){
  if (r==NULL){
    r=(node *)malloc(sizeof(node));
    r->next=NULL;
    r->x=x;
    return r;
  }
  if (r->x > x){
    node * temp=(node *)malloc(sizeof(node));
    temp->x=x;
    temp->next=r;
    return temp;
  }
  node * iter=r;
  while(iter->next!=NULL && iter->next->x < x ){
    iter=iter->next;
  }
  node * temp=(node *)malloc(sizeof(node));
  temp->next=iter->next;
  iter->next=temp;
  temp->x=x;
  return r;
}
int main()
{
node * root;
root=NULL;
root=ekleSirali(root,400);
root=ekleSirali(root,40);
root=ekleSirali(root,4);
root=ekleSirali(root,450);
root=ekleSirali(root,50);
bastir(root);
}

#include <stdio.h>

#include <stdlib.h>

typedef struct n{

int x;

struct n * next;

} node;

typedef struct n node;

void bastir(node * r){

while(r!=NULL){

printf("%d\n",r->x);

r=r->next;

}

node * ekleSirali(node *r,int x){

if (r==NULL){

r=(node *)malloc(sizeof(node));

r->next=NULL;

r->x=x;

return r;

}

if (r->x > x){

node * temp=(node *)malloc(sizeof(node));

temp->x=x;

temp->next=r;

return temp;

}

node * iter=r;

while(iter->next!=NULL && iter->next->x < x ){

iter=iter->next;

}

node * temp=(node *)malloc(sizeof(node));

temp->next=iter->next;

iter->next=temp;

temp->x=x;

return r;

}

int main()

{

node * root;

root=NULL;

root=ekleSirali(root,400);

root=ekleSirali(root,40);

root=ekleSirali(root,4);

root=ekleSirali(root,450);

root=ekleSirali(root,50);

bastir(root);

}

Ekran çıktısı:

araya ekleme Bağlı Liste sıralı ekleme

Sayfalar:12 ›