Notes

/*
1. Aşağıda Bağlı listelerle ilgili sizlerden istenen fonksiyonları gerçekleştirmeniz istenmektedir.
Bu listelerde “10, 20, 100, 50, 40, 60, 30, 90” sayılarını kullanmalısınız.
a. Tek Yönlü Bağlı Liste ile İlgili Fonksiyonlar;
i. TYBL_basaelemanekle()
ii. TYBL_sonaelemanekle()
iii. TYBL_siralielemanekle()
iv. TYBL_bastanelemansilme()
v. TYBL_sondanelemansilme()
vi. TYBL_belirlielemansilme()
(Açıklama: Main fonksiyonundan gönderilen bir değeri eğer bağlı listede varsa silme işlemi yapacak,
yoksa “girilen eleman bağlı listede bulunmamaktadır” şeklinde mesaj döndürecek)
*/

#include <iostream>
#include <cstdlib>

using namespace std;

struct TYBL{
int veri;
struct TYBL *sonraki;
};
typedef TYBL dugum;

void TYBL_basa_eleman_ekle(dugum** kok, int deger){
dugum* gecici = (dugum*)malloc(sizeof(dugum));
gecici->veri = deger;
gecici->sonraki = (*kok);
(*kok) = gecici;
}


void TYBL_sona_eleman_ekle(dugum** kok, int deger){
dugum* gecici = (dugum*) malloc(sizeof(dugum));
dugum *sonuncu = *kok;
gecici->veri = deger;
gecici->sonraki = NULL;
if (*kok == NULL){
*kok = gecici;
return;
}

while (sonuncu->sonraki != NULL){
sonuncu = sonuncu->sonraki;
}
sonuncu->sonraki = gecici;
return;
}


dugum* TYBL_sirali_eleman_ekle(dugum ** kok, int deger){
dugum *kontrol = *kok;
if(kontrol == NULL){
kontrol = (dugum *)malloc(sizeof(dugum));
kontrol->sonraki = NULL;
kontrol->veri = deger;
return kontrol;
}
if(kontrol->veri > deger){
dugum *gecici = (dugum *)malloc(sizeof(dugum));
gecici->veri = deger;
gecici->sonraki = kontrol;
return gecici;
}
dugum *ilerle = kontrol;
while(ilerle->sonraki != NULL && ilerle->sonraki->veri < deger ){
ilerle = ilerle->sonraki;
}

dugum *gecici = (dugum *)malloc(sizeof(dugum));
gecici->sonraki = ilerle->sonraki;
ilerle->sonraki = gecici;
gecici->veri = deger;
return kontrol;
}


dugum* TYBL_bastan_eleman_silme(dugum* kok){
if (kok == NULL){
return NULL;
}
dugum* gecici = kok;
kok = kok->sonraki;
free(gecici);
return kok;
}


dugum* TYBL_sondan_eleman_silme(dugum* kok){
if (kok == NULL){
return NULL;
}
if (kok->sonraki == NULL){
free(kok);
return NULL;
}
dugum* sondan_ikinci = kok;
while (sondan_ikinci->sonraki->sonraki != NULL){
sondan_ikinci = sondan_ikinci->sonraki;
}
free(sondan_ikinci->sonraki);
sondan_ikinci->sonraki = NULL;
return kok;
}



void TYBL_belirli_eleman_silme(dugum **kok, int deger){
dugum* gecici = *kok, *onceki;
if (gecici != NULL && gecici->veri == deger){
*kok = gecici->sonraki;
free(gecici);
return;
}
while (gecici != NULL && gecici->veri != deger){
onceki = gecici;
gecici = gecici->sonraki;
}
if (gecici == NULL){
return;
}
onceki->sonraki = gecici->sonraki;
free(gecici);
}

void yazdir(dugum *kok){
while (kok != NULL){
cout << kok->veri << " ";
kok = kok->sonraki;
}
cout << "n";
}


int main(){
dugum* kok = NULL;

TYBL_sona_eleman_ekle(&kok, 100);
TYBL_basa_eleman_ekle(&kok, 20);
TYBL_sona_eleman_ekle(&kok, 90);

yazdir(kok);

kok = TYBL_sirali_eleman_ekle(&kok, 60);
kok = TYBL_sirali_eleman_ekle(&kok, 30);
kok = TYBL_sirali_eleman_ekle(&kok, 40);

yazdir(kok);

kok = TYBL_bastan_eleman_silme(kok);
kok = TYBL_sondan_eleman_silme(kok);

yazdir(kok);

TYBL_sona_eleman_ekle(&kok, 50);

yazdir(kok);

TYBL_belirli_eleman_silme(&kok, 50);

yazdir(kok);

return 0;
}







/*
1. Aşağıda Bağlı listelerle ilgili sizlerden istenen fonksiyonları gerçekleştirmeniz istenmektedir.
Bu listelerde “10, 20, 100, 50, 40, 60, 30, 90” sayılarını kullanmalısınız.
b. Çift Yönlü Dairesel Bağlı Liste ile İlgili Fonksiyonlar;
i. CYDBL_basaelemanekle()
ii. CYDBL_sonaelemanekle()
iii. CYDBL_siralielemanekle()
iv. CYDBL_bastanelemansilme()
v. CYDBL_sondanelemansilme()
vi. CYDBL_belirlielemansilme()
(Açıklama: Main fonksiyonundan gönderilen bir değeri eğer bağlı listede varsa silme işlemi yapacak,
yoksa “girilen eleman bağlı listede bulunmamaktadır” şeklinde mesaj döndürecek)
*/

#include <iostream>
#include <cstdlib>

using namespace std;

struct CYDBL{
int veri;
CYDBL *onceki;
CYDBL *sonraki;
};
typedef CYDBL dugum;

void CYDBL_basa_eleman_ekle(dugum** ilk, int deger){
dugum *son = (*ilk)->onceki;
dugum* yeni_dugum = new dugum;
yeni_dugum->veri = deger;
yeni_dugum->sonraki = *ilk;
yeni_dugum->onceki = son;
son->sonraki = (*ilk)->onceki = yeni_dugum;
*ilk = yeni_dugum;
}

void CYDBL_sona_eleman_ekle(dugum** ilk, int deger){
if (*ilk == NULL){
dugum* yeni_dugum = new dugum;
yeni_dugum->veri = deger;
yeni_dugum->sonraki = yeni_dugum->onceki = yeni_dugum;
*ilk = yeni_dugum;
return;
}
dugum *son = (*ilk)->onceki;
dugum* yeni_dugum = new dugum;
yeni_dugum->veri = deger;
yeni_dugum->sonraki = *ilk;
(*ilk)->onceki = yeni_dugum;
yeni_dugum->onceki = son;
son->sonraki = yeni_dugum;
}

void CYDBL_belirli_eleman_silme(dugum** ilk, int deger){
if (*ilk == NULL){
return;
}
dugum* x = *ilk, *bir_onceki = NULL;
while (x->veri != deger){
if (x->sonraki == *ilk){
cout << deger << "'i dizide yok" << endl;
return;
}
bir_onceki = x;
x = x->sonraki;
}
if (x->sonraki == *ilk && bir_onceki == NULL){
(*ilk) = NULL;
free(x);
return;
}
if (x == *ilk){
bir_onceki = (*ilk)->onceki;
*ilk = (*ilk)->sonraki;
bir_onceki->sonraki = *ilk;
(*ilk)->onceki = bir_onceki;
free(x);
}else if (x->sonraki == *ilk){
bir_onceki->sonraki = *ilk;
(*ilk)->onceki = bir_onceki;
free(x);
}else{
dugum* gecici = x->sonraki;
bir_onceki->sonraki = gecici;
gecici->onceki = bir_onceki;
free(x);
}
}

void yazdir(dugum* ilk) {
dugum *gecici = ilk;
while (gecici->sonraki != ilk){
cout <<gecici->veri << " ";
gecici = gecici->sonraki;
}
cout << gecici->veri << " ";
}

int main(){
dugum* kok = NULL;
CYDBL_sona_eleman_ekle(&kok, 20);
CYDBL_basa_eleman_ekle(&kok, 50);
CYDBL_basa_eleman_ekle(&kok, 100);
CYDBL_sona_eleman_ekle(&kok, 10);

yazdir(kok);
cout << "n";

CYDBL_belirli_eleman_silme(&kok, 50);

yazdir(kok);
cout << "n";

CYDBL_belirli_eleman_silme(&kok, 50);

return 0;
}




/*
2. 4 diskli Hanoi kulelerini A noktasından C noktasına kaç harekette taşınır?
Nasıl taşınır şekil çizerek anlatınız?
Bu işlemi gerçekleştiren yazılımın main() dosyasını ve fonksiyonlarını yazarak gerçekleştiriniz.
*/

#include <iostream>
#include <cstdlib>

using namespace std;

int hamle = 0;

void hanoi_kulesi(int n, char ilk_kule, char son_kule, char orta_kule){
if (n == 1){
hamle++;
cout << "Disk 1 " << ilk_kule << " kulesinden " << son_kule << " kulesine tasindi" << endl;
return;
}
hanoi_kulesi(n-1, ilk_kule, orta_kule, son_kule);
cout << "Disk " << n << " " << ilk_kule << " kulesinden " << son_kule << " kulesine tasindi" << endl;
hamle++;
hanoi_kulesi(n-1, orta_kule, son_kule, ilk_kule);
}

int main(){
hanoi_kulesi(4, 'A', 'C', 'B');
cout << "Toplam hamle sayisi: " << hamle << endl;
return 0;
}


/*
3. “40, 30, 20, 60, 80, 100, 120,140, 136, 130”
sayılarını ikili arma ağacı(Binary Search Tree)’na ekleme,
silme,
arama,
ağacı yazdırma,
en büyük düğümü bulan,
en küçük düğümü bulan fonksiyonları yazarak gerçekleştiriniz.
*/

#include <iostream>
#include <cstdlib>

using namespace std;


struct agac{
int veri;
agac *solcocuk;
agac *sagcocuk;
};
typedef agac dugum;

dugum* dugum_ekle(dugum* kok, int deger){
if (kok == NULL){
dugum *gecici = (dugum *)malloc(sizeof(dugum));
gecici->veri = deger;
gecici->solcocuk = NULL;
gecici->sagcocuk = NULL;
return gecici;
}
if (deger < kok->veri){
kok->solcocuk = dugum_ekle(kok->solcocuk, deger);
}else{
kok->sagcocuk = dugum_ekle(kok->sagcocuk, deger);
}
return kok;
}

dugum* dugum_ara(dugum* kok, int deger){
if (kok == NULL || kok->veri == deger){
return kok;
}
if (kok->veri < deger){
return dugum_ara(kok->sagcocuk, deger);
}
return dugum_ara(kok->solcocuk, deger);
}

int en_buyuk_deger(dugum *agac){
while (agac->sagcocuk != NULL){
agac = agac->sagcocuk;
}
return agac->veri;
}

int en_kucuk_deger(dugum *agac){
while(agac->solcocuk != NULL){
agac = agac->solcocuk;
}
return agac->veri;
}

void yazdir(dugum* kok){
if (kok != NULL){
yazdir(kok->solcocuk);
cout<< kok->veri << " ";
yazdir(kok->sagcocuk);
}
}

dugum* en_kucuk_dugum(dugum* kok){
dugum* gecici = kok;
while (gecici && gecici->solcocuk != NULL){
gecici = gecici->solcocuk;
}
return gecici;
}

dugum* en_buyuk_dugum(dugum* kok) {
dugum* gecici = kok;
while (gecici && gecici->sagcocuk != NULL){
gecici = gecici->sagcocuk;
}
return gecici;
}

dugum* dugum_sil(dugum* kok, int deger){
if (kok == NULL){
return kok;
}
if (deger < kok->veri){
kok->solcocuk = dugum_sil(kok->solcocuk, deger);
}else if (deger > kok->veri){
kok->sagcocuk = dugum_sil(kok->sagcocuk, deger);
}else{
if (kok->solcocuk == NULL){
dugum *gecici = kok->sagcocuk;
free(kok);
return gecici;
}else if (kok->sagcocuk == NULL){
dugum *gecici = kok->solcocuk;
free(kok);
return gecici;
}
dugum* gecici = en_kucuk_dugum(kok->sagcocuk);
kok->veri = gecici->veri;
kok->sagcocuk = dugum_sil(kok->sagcocuk, gecici->veri);
}
return kok;
}

// “40, 30, 20, 60, 80, 100, 120,140, 136, 130”
int main()
{

dugum *kok = NULL;
kok = dugum_ekle(kok, 40);
kok = dugum_ekle(kok, 30);
kok = dugum_ekle(kok, 20);
kok = dugum_ekle(kok, 60);
kok = dugum_ekle(kok, 80);
kok = dugum_ekle(kok, 100);

yazdir(kok);
cout<<"n";

kok = dugum_sil(kok, 20);

yazdir(kok);
cout<<"n";

kok = dugum_sil(kok, 80);

yazdir(kok);
cout<<"n";

int en_kucuk = en_kucuk_deger(kok);
int en_buyuk = en_buyuk_deger(kok);

cout << "En buyuk deger: " << en_buyuk << endl;
cout << "En kucuk deger: " << en_kucuk << endl;

return 0;
}










/*
4. “60, 45, 30, 90, 120” sayılarını AVL ağacına ve Heap’e ekleyecek fonksiyonu yazınız.
*/

#include <iostream>
#include <cstdlib>

using namespace std;

void degistir(int *x, int *y);

class min_heap {
int *ptr;
int kapasite;
int heap_boyutu;

public:
min_heap(int kapasite);

void min_heapify(int);

int ebeveyn(int i){
return (i-1)/2;
}

int solcocuk(int i){
return (2*i + 1);
}

int sagcocuk(int i){
return (2*i + 2);
}

int en_kucugu_ayir();

void degeri_arttir(int i, int yeni_Deger);

int en_kucugu_dondur(){
return ptr[0];
}

void deger_sil(int i);

void deger_ekle(int k);
};

min_heap::min_heap(int kap){
heap_boyutu = 0;
kapasite = kap;
ptr = new int[kap];
}

void min_heap::deger_ekle(int k){
if (heap_boyutu == kapasite){
cout << "nDeger eklenemedin";
return;
}
heap_boyutu++;
int i = heap_boyutu - 1;
ptr[i] = k;
while (i != 0 && ptr[ebeveyn(i)] > ptr[i]){
degistir(&ptr[i], &ptr[ebeveyn(i)]);
i = ebeveyn(i);
}
}

void min_heap::degeri_arttir(int i, int yeni_deger){
ptr[i] = yeni_deger;
while (i != 0 && ptr[ebeveyn(i)] > ptr[i]) {
degistir(&ptr[i], &ptr[ebeveyn(i)]);
i = ebeveyn(i);
}
}

int min_heap::en_kucugu_ayir(){
if (heap_boyutu <= 0){
return INT_MAX;
}
if (heap_boyutu == 1) {
heap_boyutu--;
return ptr[0];
}
int kok = ptr[0];
ptr[0] = ptr[heap_boyutu-1];
heap_boyutu--;
min_heapify(0);
return kok;
}

void min_heap::deger_sil(int i){
degeri_arttir(i, INT_MIN);
en_kucugu_ayir();
}

void min_heap::min_heapify(int i){
int l = solcocuk(i);
int r = sagcocuk(i);
int en_kucuk = i;
if (l < heap_boyutu && ptr[l] < ptr[i]){
en_kucuk = l;
}
if (r < heap_boyutu && ptr[r] < ptr[en_kucuk]){
en_kucuk = r;
}
if (en_kucuk != i) {
degistir(&ptr[i], &ptr[en_kucuk]);
min_heapify(en_kucuk);
}
}

void degistir(int *x, int *y){
int gecici = *x;
*x = *y;
*y = gecici;
}

int main(){
min_heap h(5);
h.deger_ekle(60);
h.deger_ekle(45);
h.deger_ekle(30);
h.deger_ekle(90);
h.deger_ekle(120);

return 0;
}








/*
4. “60, 45, 30, 90, 120” sayılarını AVL ağacına ve Heap’e ekleyecek fonksiyonu yazınız.
*/

#include <iostream>
#include <cstdlib>

using namespace std;

struct agac{
int veri;
int yukseklik;
agac *solcocuk;
agac* sagcocuk;
};
typedef agac dugum;

int agacin_yuksekligi(dugum *kok){
if (kok == NULL){
return 0;
}
return kok->yukseklik;
}

int maksimum(int a, int b){
if(a > b){
return a;
}else{
return b;
}
}

dugum* yeni_dugum(int deger){
dugum* gecici = (dugum*)malloc(sizeof(dugum));
gecici->veri = deger;
gecici->solcocuk = NULL;
gecici->sagcocuk = NULL;
gecici->yukseklik = 1;
return(gecici);
}

dugum *saga_dondur(dugum *kok){
dugum *gecici = kok->solcocuk;
dugum *x = gecici->sagcocuk;
gecici->sagcocuk = kok;
kok->solcocuk = x;
kok->yukseklik = maksimum(agacin_yuksekligi(kok->solcocuk), agacin_yuksekligi(kok->sagcocuk))+1;
gecici->yukseklik = maksimum(agacin_yuksekligi(gecici->solcocuk), agacin_yuksekligi(gecici->sagcocuk))+1;
return gecici;
}

dugum *sola_dondur(dugum *kok){
dugum *gecici = kok->sagcocuk;
dugum *x = gecici->solcocuk;
gecici->solcocuk = kok;
kok->sagcocuk = x;
kok->yukseklik = maksimum(agacin_yuksekligi(kok->solcocuk), agacin_yuksekligi(kok->sagcocuk))+1;
gecici->yukseklik = maksimum(agacin_yuksekligi(gecici->solcocuk), agacin_yuksekligi(gecici->sagcocuk))+1;
return gecici;
}

int dengele (dugum *kok){
if (kok == NULL){
return 0;
}
return agacin_yuksekligi(kok->solcocuk) - agacin_yuksekligi(kok->sagcocuk);
}

dugum* ekle(dugum* kok, int deger){
if (kok == NULL){
return(yeni_dugum(deger));
}
if (deger < kok->veri){
kok->solcocuk = ekle(kok->solcocuk, deger);
}else if (deger > kok->veri){
kok->sagcocuk = ekle(kok->sagcocuk, deger);
}else{
return kok;
}

kok->yukseklik = 1 + maksimum(agacin_yuksekligi(kok->solcocuk),agacin_yuksekligi(kok->sagcocuk));
int denge = dengele(kok);
if (denge > 1 && deger < kok->solcocuk->veri){
return saga_dondur(kok);
}

if (denge < -1 && deger > kok->sagcocuk->veri){
return sola_dondur(kok);
}

if (denge > 1 && deger > kok->solcocuk->veri){
kok->solcocuk = sola_dondur(kok->solcocuk);
return saga_dondur(kok);
}


if (denge < -1 && deger < kok->sagcocuk->veri){
kok->sagcocuk = saga_dondur(kok->sagcocuk);
return sola_dondur(kok);
}
return kok;
}

void yazdir(dugum *kok){
if(kok != NULL){
cout << kok->veri << " ";
yazdir(kok->solcocuk);
yazdir(kok->sagcocuk);
}
}

int main(){
dugum *kok = NULL;

kok = ekle(kok, 60);
kok = ekle(kok, 45);
kok = ekle(kok, 30);
kok = ekle(kok, 90);
kok = ekle(kok, 120);

yazdir(kok);

return 0;
}













/*
8. [7, 3, 5, 8, 2, 9, 4, 15, 6] dizisini aşağıda verilen algoritmaları kullanarak sıralayınız.
a. İnsertion Sort (araya sokma sıralaması),
b. Selection Sort (seçmeli sıralama),
c. Bubble Sort (kabarcık sıralama),
d. Merge Sort (Birleşmeli sıralama),
Hazırlayacağınız projede yukarıda bahsedilen algoritmaların her birini ayrı ayrı fonksiyon olarak yazınız.
*/

#include <iostream>
#include <cstdlib>

using namespace std;

void yazdir(int dizi[], int uzunluk){
int i;
for (i=0; i < uzunluk; i++){
cout << dizi[i] << " ";
}
cout << "n";
}

//İnsertion sort
void insertion_sort(int dizi[], int dizi_uzunluk){
int i, j, gecici;
for(i=1; i < dizi_uzunluk; i++){
gecici = dizi[i];
j = i-1;
while (j >= 0 && dizi[j] > gecici){
dizi[j+1] = dizi[j];
j--;
}
dizi[j+1] = gecici;
}
}

//Selection sort
void selection_sort(int dizi[] , int dizi_uzunluk){
int i,j,gecici;
for(i =0 ; i< dizi_uzunluk; i++){
for(j=i+1; j< dizi_uzunluk; j++){
if(dizi[j] < dizi[i]){
gecici = dizi[i];
dizi[i] = dizi[j];
dizi[j] = gecici;
}
}
}
}

//Buble sort
void bubble_sort(int dizi[] , int dizi_uzunluk){
int i,j,gecici;
for(i=0; i< dizi_uzunluk; i++){
for(j=dizi_uzunluk-1; j>i; j--){
if(dizi[j-1] > dizi[j]){
gecici = dizi[j-1];
dizi[j-1] = dizi[j];
dizi[j] = gecici;
}
}
}
}

//Merge sort
void merge(int dizi[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];

for (i = 0; i < n1; i++){
L[i] = dizi[l + i];
}
for (j = 0; j < n2; j++){
R[j] = dizi[m + 1+ j];
}

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2){
if (L[i] <= R[j]){
dizi[k] = L[i];
i++;
}else{
dizi[k] = R[j];
j++;
}
k++;
}
while (i < n1){
dizi[k] = L[i];
i++;
k++;
}
while (j < n2){
dizi[k] = R[j];
j++;
k++;
}
}


void merge_sort(int dizi[], int l, int r){
if (l < r){
int m = l+(r-l)/2;
merge_sort(dizi, l, m);
merge_sort(dizi, m+1, r);
merge(dizi, l, m, r);
}
}

int main() {
int dizi[] = {7, 3, 5, 8, 2, 9, 4, 15, 6};
int dizi_boyutu = sizeof(dizi)/sizeof(dizi[0]);
yazdir(dizi, dizi_boyutu);
cout << "Insertion sort: ";
insertion_sort(dizi, dizi_boyutu);
yazdir(dizi, dizi_boyutu);
cout << "n";

int dizi2[] = {7, 3, 5, 8, 2, 9, 4, 15, 6};
yazdir(dizi2, dizi_boyutu);
cout << "Selection sort: ";
selection_sort(dizi2, dizi_boyutu);
yazdir(dizi2, dizi_boyutu);
cout << "n";

int dizi3[] = {7, 3, 5, 8, 2, 9, 4, 15, 6};
yazdir(dizi3, dizi_boyutu);
cout << "Bubble sort: ";
bubble_sort(dizi3, dizi_boyutu);
yazdir(dizi3, dizi_boyutu);
cout << "n";

int dizi4[] = {7, 3, 5, 8, 2, 9, 4, 15, 6};
yazdir(dizi4, dizi_boyutu);
cout << "Merge sort: ";
merge_sort(dizi4,0,dizi_boyutu-1);
yazdir(dizi4, dizi_boyutu);

return 0;
}