Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

KUYRUK

No description
by

SEVAL KÜLÇE

on 20 May 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of KUYRUK

KUYRUK KUYRUK (QUEUES)YAPISI Kuyruk da en az yığın kadar önemli bir veri yapısı türüdür. Çalışma şekli olarak temel farklılıkla bulunmaktadır. Bunlardan en önemlisi yığındaki son giren ilk çıkar mantığının aksine kuyruk yapısında ilk giren ilk çıkar (first in first out) FIFO mantığı işlemektedir. Kuyruk denmesinin esas nedeni budur gerçek dünyadaki yemek sırası kuyruğu gibi işlemektedir. Kuyruk modeli program tasarımında birçok yerde kullanılmaktadır. İki birim arasındaki veri aktarımı, ara bellek, tampon bellek ve öncelik kuyruğu oluşturmada bu yöntem kullanılır. Kuyruk tasarımı yapılırken çeşitli yöntemler kullanılabilir. Içlerinden en yaln bir dizi ve bir indis deikeni kullanlarak yaplandr. Bu yapda stack yapsnda olduu gibi veriler bir dizide tutulur ve bir pointer ile kontrol edilir. Fakat bu kez pointer son giren veriyi iaret eder. Kuyruktan eleman çkarma ilemi ise her zaman dizinin balangç adresinden yani 0 indisli bloktan balanlarak yaplr. Fakat bu yöntemin en kötü yanlarndan birisi elemanlardan biri çkarldnda onun arkasnda deikenlerin tamam bir blok ileri kaydrlmaktadr ve bu fazlaca ilem edebilmektedir. Kuyruk tasarmnda daha pratik baka çözümlerde mümkündür. Kuyruk tasarm için genel olarak 3 deiik çözüm ekli önerilir.

•Dizi üzerinde kaydrmal (bir indis degiskenli)
•Dizi üzerinde çevrimsel (iki indis degiskenli)
•Bagli liste ile
DIZI UZERINDE KAYDIRMALI Dizi üzerinde kaydrmal kuyruk yaps belki en kolay yap olabilir. Fakat bu yöntemin eksik yönleri kuyruktaki eleman says arttkça daha çok problem oluturmaktadr. Ama az sayda eleman olan kuyruk yapsnda kullanlmas çok sorun olmamaktadr. Bu yapda kuyruk içerisindeki ilk eleman kuyruktan çkmaktadr bu eleman ayn zamanda kuyrua giren ilk elemandr. Bu elemann yani 0 indisli elemann kuyruktan çkarlmas sonucu 1 indisli eleman sfra, 2 indisli eleman 1e gelir ve bu böyle devam eder bu ilem nedeniyle dizi üzerindeki kaydrmal kuyruk yaps çok elemanl durumlarda tercih edilmemektedir. int ckart()
{
if(son<0){
puts("Kuyruk Bos");
}
veri=K[0];
for(int k=0;k<=son;k++)
K[k-1]=K[k];
son--;
return veri;
}

int ekle(int veri)
{
son++;
if(son>N){
puts("Kuyruk Dolu");
son--;
}
K[son]=veri;
}
ÖRNEK: DIZI UZERINDE CEVRIMSEL Bu yöntemde dizi üzerindeki eleman kaydırma problemine bir çözüm üretilmiştir. Burada veriler sanki dairesel bir bellek üstündeymişçesine kaydedilmektedir. Bellekteki son adrese gelindiğinde bir sonraki adres ilk adres olmaktadır yani başa dönmektedir. Bu yöntemi kullanırken dizinin sonunu nasıl saklıyor isek ayriyeten birde başını saklayan bir pointer kullanmaktayız. İlk pointerı bellekten okuma ve alma işlemlerini yaparken, son pointerı ise ekleme ve koyma işlemleri sırasında kullanılmaktadır. typedef struct kuyrukyapisi{
int bas,son,var,D[10];
}KUYRUK;
void baslangic(KUYRUK *K)
{
(*K.var)=0;
(*K.bas)=0;
(*K.son)=0;
}
int ekle(int veri, KUYRUK *K){
if((*K.var)>(N-1)){ puts("Kuyruk dolu"); }
(*K.son)=((*K.son)+1)%10;
(*K.D[(*K.son)])=veri;
(*K.var)++;
}
int cikart(KUYRUK *K, int cikarilan)
{
if(K.var<=0){
puts("Kuyruk Bos");
}
*cikarilan= (*K.D[(K.ilk)]);
(*K.ilk)=((*K.ilk)+1)%10;
(*K.var)--;
}
ÖRNEK: BAĞLANTILI LİSTE İLE KUYRUK TASARIMI Kuyruğun bağlantılı liste ile tasarımında gene bir önceki modelde olduğu gibi 2 adet ilk ve son elemanları gösteren pointerlar kullanılmaktadır. Ekleme işlemi son adlı verinin arkasına, çıkarma işlemi ise ilk adlı verinin alınması ve kuyruktan çıkarılmasıyla yapılır. Bu yaklaşımda kuyruğun boş olması ilk değişkenin NULL olması demektir. Diğer iki yönteme göre en önemli avantajı ise bağlı liste kullanılması ve dolayısıyla dinamik bellek oluşturulmasından dolayı bellekte yer oldukça yığının boyutu artabilmektedir. Kuyruk oluşumunda kullanılan ekleme ve çıkarma fonksiyonları aşağıdaki gibi oluşturulabilir. void ekle()
{
if((p=malloc(sizeof(kuyrukdugum)))==NULL){
puts("Bellekte yer yok");
}
p->veri=veri;
p->arka=NULL;
if(ilk==NULL){
ilk=p;
son=p;
}
else{
son->arka=p;
son=p;
}
}

int cikar()
{
if(ilk==NULL){
puts("Kuyruk Bos");


}
p=ilk;
ilk=ilk->arka;
if(ilk==NULL)
son=NULL;
d=p->veri;
free(p);
return d;
}

void temizle()
{
while(ilk!=NULL){
p=ilk;
ilk=p->arka;
free(p);
}
son=NULL;
}
ÖRNEK KODLAMALAR Kuyruk işlemleri: #include<stdio.h>
#include<conio.h>
#include<process.h>

const int boy=6;
int t=0,s=0,dizi[boy];
char tur='a';

//FONKSIYON PROTOTIPLERI
void menu();
void ekle(int e);
int cek();
int dolumu();
int bosmu();
void listele();
void menudon();

//ANA PROGRAM
void main() {
menu();
}
//FONKSIYON TANIMLAMA
void menu() {
clrscr();
int sec,x;
printf("KUYRUK ISLEMLERI\n\n\n1-Ekle\n2-Cek\n3-dolumu\n4-bosmu\n5-listele\n
6-Cik\n\n\n\nseciminizi girin[1-6]=");
scanf("%d",&sec);
switch(sec) {
case 1: printf("\n Eklenecek Degeri Girin=");scanf("%d",&x);ekle(x);
case 2:x=cek();if(x==-1){
clrscr();
printf("Kuyruk Bos!!Eleman cekemezsiniz!!");
menudon();
}
else
{
printf("Cekilen Eleman=%d",x);
menudon();
};
case 3:x=dolumu();if(x==1)printf("DOLU");else printf("DOLU DEGIL");menudon();
case 4:x=bosmu();if(x==0)printf("BOS");else printf("BOS DEGIL");menudon();
case 5:listele();
case 6:exit(0);
default:printf("yanlis Deger girdiniz!!1-6 aras bir rakam giriniz!!!");menudon();
}
}
void ekle(int e) {
if( dolumu()==1 ) {
printf("Kuyruk dolu!!!");
menudon();
}
//dolu degilse
dizi[s]=e;
s++;
printf("\nEleman Eklendi...");
if(s==boy){
tur='f';
s=0;
}
menudon();
}
int cek() {
//bos mu kontrol et
if(bosmu()==0)
return -1;
int k=t;
t++;
if(t==boy){
tur='a';
t=0;
}
return dizi[k];
}
int dolumu(){
if( (t==s)&&(tur=='f') )
return 1;//1 d”nerse dolu demek
return 0;//dolu degil.
}
int bosmu(){
if( (t==s)&&(tur=='a') )
return 0;//0 derse bos demek
return 1;//bos degil.
}
void listele(){
int sayac=0,x;
if( bosmu()==0 )printf("Kuyruk Bos, Listelenecek Eleman Yok!!!");
else {
x=t;
do {
sayac++;
printf("\n%d.deger=%d\n",sayac,dizi[x]);
x++;
if(x==boy)x=0;
} while(x!=s);
}
menudon();
}
void menudon() {
printf("\n Menuye Donmek Icin Bir Tusa Basnz....");
getch();
menu();
}
#ifndef KUYRUK_H
#define KUYRUK_H
#include"dugum.h"
#include<iostream>
#include<cstdlib>
using namespace std;
class Kuyruk
{
public:
Dugum *ilk;
Dugum *son;
Kuyruk(){ilk=0; son=0;}
Kuyruk(char a)
{
Dugum *p = new Dugum(a);
ilk=p;
son=p;
}
void ekle(char a)
{
Dugum *temp;

if(ilk==0 && son==0){
temp=new Dugum(a);
ilk=temp;
son=temp;
son->sonraki=0;
}
else
{
temp=new Dugum(a);
son->sonraki=temp;
son=temp;
son->sonraki=0;
}
}
char getir()
{
Dugum *temp;

if(!bosmu())
{
char a=ilk->getHarf();
if(ilk==son)
{
ilk=0;
son=0;
return a;
}
else
{
temp=ilk->sonraki;
delete ilk;
ilk=temp;
return a;
}
}
}
bool bosmu()
{
if(ilk==NULL && son == NULL)
return true;
else
return false;
}
};
#endif
Kaynaklar

•Data structures and program design in c, Robert L. Kruse

•Data structures and algorithms, Adam Drozdek

•Veri yapıları ve algoritmalar, Rıfat Çölkesen

•C Programlama ve Programlama Sanatı, Dr.M. Sabih Aksoy, Dr.Ömer Akgöbek

•www.frmtr.com

•www.bilgisayarkavramlari.com

•www.programlama.com

•http://ceng.gazi.edu.tr

•www.sistemhocasi.com
Full transcript