Veri Yapıları Heap, Hashing Uygulaması | 2019-12-17 tarihinde oluşturuldu.
Burada yazdığım kodlar aşağıdaki problemlere çözüm bulmak için yazılmıştır.

a) Tam sayıları tutan bir min Heap yapısı tanımlayarak ekleme, silme işlemlerini gerçekleştiren kodu yazınız?

b) Bu min Heap yapısını kullanarak farklı uzunlukta M tane sıralı listeyi sıralı olarak O(nlgn) karmaşıklığında birleştiren programı yazınız?

c) Oluşturduğunuz min-heap’i O(n) zamanda max-heap’e dönüştüren metodu yazınız?

d) parametre olarak bir dizi alan ve dizinin min-heap olup olmadığını true veya false olarak döndüren metodu yazınız?

e) Elinizde sıralı olmayan bir dizi bulunmaktadır. Bu dizide elemanları toplamı verilen bir değere eşit olan eleman çiftlerini O(n)zamanda bulan metodu yazınız?

f) Kendisine parametre olarak iki dizgi alan ve bu iki dizginin anagram olup olmadığını O(n) zamanda bulan metodu yazınız? NOT: Anagram, bir sözcüğün veya sözcük grubunun harflerinin değişik düzenle başka bir sözcüğü veya sözcük grubunu oluşturmasıdır.

g) Verilen bir dizinin ikinci bir dizinin alt kümesi olup olmadığını Hash kullanarak bulunuz?

h) Hash için çakışma çözme tekniklerinden doğrusal sınama ve zincir hash’i gerçekleştirerek ekleme ve arama işlemlerini yapınız?


public class Liste {
    lst_dgm[] L;
    int tmp;
    int indis, e_uzun;
    
    public Liste(int M){
        L = new lst_dgm[M];
        indis = 0;
        e_uzun = 0;
        tmp = 0;
    }
    
    public void ekle(lst_dgm eleman){
        L[indis] = eleman;
        ++indis;
        en_uzun(eleman.l.length);
    }
    
    public int goster(int i, int j){
        return L[i-1].deger(j);
    }
    
    public int uzunluk(){
        int top = 0;
        for (int i=0; i<indis; i++) {
            top += L[i].l.length;
        }
        return top;
    }
    
    public void en_uzun(int uzunluk){
        if (uzunluk >= e_uzun) e_uzun = uzunluk;
    }
}

class lst_dgm {
    int[] l;
    
    public lst_dgm(int[] l){
        this.l = l;
    }
    
    public int deger(int j){
        return l[j-1];
    }
}

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */
public class minHeap {
    private Dugum[] Dizi;
    int doluluk;
    private int boyut;
    private Dugum ilk;
    boolean takas;
 
    private static final int FRONT = 1;
 
    public minHeap(int boyut)
    {
        ilk = new Dugum(Integer.MIN_VALUE);
        this.boyut = boyut;
        this.doluluk = 0;
        Dizi = new Dugum[this.boyut + 1];
        Dizi[0] = ilk;
        takas = false;
    }
 
    // Aktif düğümün ebeveyninin dizi üzerindeki indis bilgisi
    private int ebeveyn(int aktif)
    {
        return aktif / 2;
    }
 
    // Aktif düğümün sol çocuğunun dizi üzerindeki indis bilgisi
    private int sol_cocuk(int aktif)
    {
        return (2 * aktif);
    }
 
    // Aktif düğümün sag çocuğunun dizi üzerindeki indis bilgisi
    private int sag_cocuk(int aktif)
    {
        return (2 * aktif) + 1;
    }
 
   
    // Düğüm bir yaprak mı? Evet ise sonuç: True
    private boolean yaprak_mi(int aktif)
    {
        if (aktif > (doluluk / 2) && aktif <= doluluk) {
            return true;
        }
        return false;
    }
 
    // Düğümlerin yerini değiştirir.
    private void yer_degis(int bb, int ogl)
    {
        takas = true;
        Dugum tmp;
        tmp = Dizi[bb];
        Dizi[bb] = Dizi[ogl];
        Dizi[ogl] = tmp;
    }
 
    // postaki düğümü yığınlama işlemi
    private void yiginla(int aktif)
    {
        // Düğüm yaprak değilse ve çocuğundan büyükse
        if (!yaprak_mi(aktif)) {
            if (Dizi[aktif].no > Dizi[sol_cocuk(aktif)].no || Dizi[aktif].no > Dizi[sag_cocuk(aktif)].no) {
                 
                // Sol çocuk sağdan küçükse
                // Sol çocukla yer değiştir ve soldaki çocuğu yığınla
                if (Dizi[sol_cocuk(aktif)].no < Dizi[sag_cocuk(aktif)].no) {
                    yer_degis(aktif, sol_cocuk(aktif));
                    yiginla(sol_cocuk(aktif));
                }
 
                // Sağ çocukla yer değiştir ve sağdaki çocuğu yığınla
                else {
                    yer_degis(aktif, sag_cocuk(aktif));
                    yiginla(sag_cocuk(aktif));
                }
            }
        }
    }
   
    private void yiginla2(int aktif)
    {
        // Düğüm yaprak değilse ve çocuğundan büyükse
       
        if (!yaprak_mi(aktif)) {
            if (Dizi[aktif].no < Dizi[sol_cocuk(aktif)].no || Dizi[aktif].no < Dizi[sag_cocuk(aktif)].no) {
                 
                // Sol çocuk sağdan küçükse
                // Sol çocukla yer değiştir ve soldaki çocuğu yığınla
                if (Dizi[sol_cocuk(aktif)].no < Dizi[sag_cocuk(aktif)].no) {
                    yer_degis(aktif, sag_cocuk(aktif));
                    yiginla2(sag_cocuk(aktif));
                }
 
                // Sağ çocukla yer değiştir ve sağdaki çocuğu yığınla
                else {
                    yer_degis(aktif, sol_cocuk(aktif));
                    yiginla2(sol_cocuk(aktif));
                }
            }
        }
    }
 
    // Düğüm ekleme
    public void ekle(int deger)
    {
        if (doluluk >= boyut) {
            return;
        }
        Dugum yeni_dgm = new Dugum(deger);
        Dizi[++doluluk] = yeni_dgm;
        int yeni = doluluk;
 
        while (Dizi[yeni].no < Dizi[ebeveyn(yeni)].no) {
            yer_degis(yeni, ebeveyn(yeni));
            yeni = ebeveyn(yeni);
        }
    }
 
    // Ağaç içeriğini yazdırma
    public void yazdir()
    {
        for (int i = 1; i <= doluluk / 2; i++) {
            if (doluluk % 2 == 0 && i == doluluk / 2) {
                System.out.print("\t EBEVEYN : " + Dizi[i].no
                                + "\n Sol Çocuk :" + Dizi[2 * i].no + "\n");
                System.out.println();
            }
            else {
                System.out.print("\t EBEVEYN : " + Dizi[i].no
                                + "\n Sol Çocuk :" + Dizi[2 * i].no
                                + " - Sağ Çocuk :" + Dizi[2 * i + 1].no + "\n");
                System.out.println();
            }
        }
    }
 
    // Function to build the min heap using
    // the minHeapify
    // minhepify fonksiyonunu kullanarak yığınlama işlemi
    public void minHeap()
    {
        for (int pos = (doluluk / 2); pos >= 1; pos--) {
            yiginla(pos);
        }
    }
   
    public void maxHeap() {
        for (int pos = (doluluk / 2); pos >= 1; pos--) {
            yiginla2(pos);
        }
    }
   
    public boolean minHeap_mi(int[] Dz){
        boolean durum = false;
        for (int i = Dz.length/2; i>=0; i--){
            if (!(2*i+1>=Dz.length)) {
                if (!(2*i+2>=Dz.length)) { // Sol ve Sag çocuk varsa
                    if (Dz[i]<Dz[2*i+1] && Dz[i]<Dz[2*i+2]) durum = true;
                    else durum = false;
                }
                else { // Sol çocuk varsa
                    if (Dz[i]<Dz[2*i+1]) durum = true;
                    else durum = false;
                }
            }
        }
        return durum;
    }
 
    // Eleman silme (Kökteki eleman silinir..!)
    public int remove()
    {
        int popped = Dizi[FRONT].no;
        Dizi[FRONT] = Dizi[doluluk--];
        yiginla(FRONT);
        return popped;
    }
}

class Dugum {
    int no;
    public Dugum(int no){
        this.no = no;
    }
}

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */
public class Hash {
    H_Dugum[] HD;
    //H_Dugum sonraki, bas;
    int[] degerler;
    int uzunluk;
   
    public Hash(int[] degerler){
        this.degerler = degerler;
        HD = new H_Dugum[this.degerler.length];
        uzunluk = HD.length;
        //sonraki = null;
        //bas = null;
    }
   
    public void liner_diz(){
        for (int i = 0; i < uzunluk; i++) {
            if (HD[degerler[i]%uzunluk] == null) {
                HD[degerler[i]%uzunluk] = new H_Dugum(degerler[i]);;
                System.out.println(degerler[i]%uzunluk + " indisine eklendi-a " + HD[degerler[i]%uzunluk].deger);
            }
            else {
                for (int j = (degerler[i]%uzunluk+1)%uzunluk; j!=degerler[i]%uzunluk; j++) {
                    if (HD[j] == null) {
                        HD[j] = new H_Dugum(degerler[i]);
                        System.out.println(j + " indisine eklendi-b " + HD[j].deger);
                        j = degerler[i]%uzunluk-1;
                    }
                   
                   
                    if (j==uzunluk-1) j = 0;
                }
            }
        }
    }
   
    public void liner_arama(int aranan){
        int hash_adresi = aranan % uzunluk;
        boolean durum = false;
       
        if (HD[hash_adresi].deger==aranan) {
            System.out.println("Eleman bulundu, dizinin " + hash_adresi + ". adresinde..!");
            durum = true;
        }
       
        else {
            int hash_adresi2 = (hash_adresi + 1) % uzunluk;
           
            for (int i = hash_adresi2; i != hash_adresi2-1; i++) {
               
                if (HD[hash_adresi2].deger == aranan) {
                    System.out.println("Eleman bulundu, dizinin " + hash_adresi2 + ". adresinde..!");
                    durum = true;
                    i = hash_adresi2-2;
                }
                else durum = false;
               
                if (i==uzunluk-1) i=-1;
            }
        }
       
        if (!durum) System.out.println("Eleman yok");
    }
   
    public void zincir_diz(){
        int hash_adresi, icerik;
       
        for (int i = 0; i < uzunluk; i++) {
            hash_adresi = degerler[i]%uzunluk;
            icerik = degerler[i];
           
            if (HD[hash_adresi] == null) {
                HD[hash_adresi] = new H_Dugum(icerik);
                System.out.println(hash_adresi + " indisine eklendi-a " + HD[hash_adresi].deger);
            }
            else {
                H_Dugum gecici = halka_gez(HD[hash_adresi]);
                gecici.sonraki = new H_Dugum(icerik);
                System.out.println("\t" + hash_adresi + " indis sonrasına-b " + halka_gez(gecici).deger);
            }
        }
    }
   
    H_Dugum halka_gez(H_Dugum kok){
        H_Dugum tmp = null;
        if (kok.sonraki != null) {
            tmp = halka_gez(kok.sonraki);
        }
        else tmp = kok;
        return tmp;
    }
   
    H_Dugum halka_ara(H_Dugum kok, int aranan){
        H_Dugum tmp = null;
        if (kok.sonraki != null && kok.sonraki.deger == aranan) {
            tmp = kok.sonraki;
            //tmp = halka_ara(kok.sonraki, aranan);
        }
        else if (kok.sonraki == null) return tmp;
        else tmp = halka_ara(kok.sonraki, aranan);
        return tmp;
    }
   
    public void zincir_ara(int aranan) {
        //System.out.println(HD[3].sonraki.sonraki.deger);
        boolean durum = false;
        int hash_adresi = aranan % uzunluk;
        int hash_adr_on = (hash_adresi - 1) % uzunluk;
        for (int i = hash_adresi; i != hash_adr_on; i++) {
            if (HD[i] != null) {
                if (HD[i].deger == aranan) {
                    System.out.println("Bulundu");
                    durum = true;
                }
                else {
                    H_Dugum gcc = halka_ara(HD[i], aranan);
                    if (gcc != null) System.out.println("Bulundu");
                    durum = true;
                }
            }
            else i = hash_adr_on - 1;
            if (i==uzunluk-1) i = -1;
        }
        if (!durum) System.out.println("Bulunamadı");
    }
}

class H_Dugum {
    int deger;
    H_Dugum sonraki;
   
    H_Dugum(int deger){
        this.deger = deger;
        sonraki = null;
    }
}

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author sskirat
 */
public class Ana_Program {
    public static void main(String[] args){
   
    // {+} 1. Soru
        // [+] 1.A Şıkkı
        System.out.println("Heap Ağacı");
        minHeap minHeap = new minHeap(15);
        minHeap.ekle(5);
        minHeap.ekle(3);
        minHeap.ekle(17);
        minHeap.ekle(10);
        minHeap.ekle(84);
        minHeap.ekle(19);
        minHeap.ekle(6);
        minHeap.ekle(22);
        minHeap.ekle(9);
 
        minHeap.yazdir();
        System.out.println("Ağaçtaki En Küçük Değer :" + minHeap.remove());
        System.out.println("Ağaçtaki En Küçük Değer :" + minHeap.remove());
        // [-] 1.A Şıkkı
       
        // --------------------------------
       
        // [+] 1.B Şıkkı
        Liste L = new Liste(5);
       
        int[] d1 = {3, 5, 6};
        int[] d2 = {1, 10};
        int[] d3 = {2, 7, 8, 46};
        int[] d4 = {4, 9};
        int[] d5 = {11, 13, 23, 44};
       
        L.ekle(new lst_dgm(d1));
        L.ekle(new lst_dgm(d2));
        L.ekle(new lst_dgm(d3));
        L.ekle(new lst_dgm(d4));
        L.ekle(new lst_dgm(d5));
       
        //System.out.println(L.goster(3, 4));
        //System.out.println("Toplam Uznuluk: " + L.uzunluk());
        //System.out.println("En Uzun Olan: " + L.e_uzun);
        //System.out.println("Eleman Sayisi: " + L.indis);
        program(L);
        // [-] 1.B Şıkkı
       
        // --------------------------------
       
        // [+] 1.C Şıkkı
        System.out.println("------MaxHeap Ağaç------");
        minHeap.maxHeap();
        minHeap.yazdir();
        // [-] 1.C Şıkkı

        // --------------------------------
       
        // [+] 1.D Şıkkı
        int[] dz = {1,3,2,4,6,5,10,7,9,13,11,8,23,46,44};
        System.out.println("Durum: " + minHeap.minHeap_mi(dz));
        // [-] 1.D Şıkkı
    // {-} 1. Soru
   
    // ############################################
   
    // {+} 2. Soru
        // [+] 2.A Şıkkı
        int[] diz = {4,8,3,0,2,1};
        dizi_elm_tpl(diz, 13);
        // [-] 2.A Şıkkı
       
        // --------------------------------
       
        // [+] 2.B Şıkkı
        anagram_kontrol("ırak", "arık");
        // [-] 2.B Şıkkı
       
        // --------------------------------
       
        // [+] 2.C Şıkkı
        int[] di1 = {5,3,2};
        int[] di2 = {1,3,5,15,8,4,89};
        alt_kume_kontrol(di1, di2);
        // [-] 2.C Şıkkı
       
        // --------------------------------
       
        // [+] 2.D Şıkkı
       
        int[] hash_dizisi = {3, 6, 8, 13, 12};
        Hash HS = new Hash(hash_dizisi);
        /*
        HS.liner_diz();
        HS.liner_arama(13);
        */
        HS.zincir_diz();
        HS.zincir_ara(15);
        // [-] 2.D Şıkkı
    // {-} 2. Soru
   
        HDugum HDD1 = new HDugum(2);
        HDugum HDD2 = new HDugum(3);
        HDugum HDD3 = new HDugum(1);
        HDugum HDD4 = new HDugum(5);
        HDugum HDD5 = new HDugum(10);
        HDugum HDD6 = new HDugum(9);
        HDugum HDD7 = new HDugum(7);
        HDugum HDD8 = new HDugum(4);
        HDugum HDD9 = new HDugum(6);
        HDugum HDD10 = new HDugum(8);
       
        Heap Siralama = new Heap(10);
        Siralama.ekle(HDD1);
        Siralama.ekle(HDD2);
        Siralama.ekle(HDD3);
        Siralama.ekle(HDD4);
        Siralama.ekle(HDD5);
        Siralama.ekle(HDD6);
        Siralama.ekle(HDD7);
        Siralama.ekle(HDD8);
        Siralama.ekle(HDD9);
        Siralama.ekle(HDD10);
        for (int i=0; i<=Siralama.e_say; i++){
            System.out.println(Siralama.d[i].no);
        }
        System.out.println("\n");
        int x = Siralama.e_say;
        for (int i=0; i<=x; i++){
            System.out.println(Siralama.sil().no);
        }
    }
   
    static void program(Liste Lst){
        minHeap dene = new minHeap(Lst.uzunluk());
       
        for (int i = 0; i < Lst.e_uzun; i++){ // En uzun elemanın eleman sayısı kadar dön      
           
            for (int j = 0; j < Lst.indis; j++) { // Her elemanın ilk elemanını kontrol et
               
                if ((i+1) <= Lst.L[j].l.length) dene.ekle(Lst.L[j].l[i]);
            }
        }
        System.out.println("------MinHeap Ağaç------");
        dene.minHeap();
        dene.yazdir();
        System.out.println("------MaxHeap Ağaç------");
        dene.maxHeap();
        dene.yazdir();
    }
   
    static void dizi_elm_tpl(int[] dz, int deger){
        boolean durum = false;
        for (int i = 0, j = i+1; (i < dz.length-1) && (j < dz.length); j++) {
           
            if((dz[i] + dz[j]) == deger) {
                System.out.println((i+1) + ". eleman ile " + (j+1) + ". eleman koşulu sağlar");
                durum = true;
            }
           
            if(j == dz.length-1) {
                ++i;
                j = i;
            }
        }
        if (durum == false) System.out.println("Koşulu sağlayan eleman çifti bulunamadı.");
    }

    static void anagram_kontrol(String str1, String str2){
        boolean durum = false;
        if (str1.length() == str2.length()) {
           
            for (int i=0; i<str1.length(); i++) {
                System.out.println(str2.indexOf(str1.charAt(i)));
                if (str2.indexOf(str1.charAt(i)) < 0) {
                    durum = false;
                    i = str1.length();
                }
                else durum = true;
            }
        }
        if (durum == true) System.out.println("Bu dizgiler anagram");
        else System.out.println("Bu dizgiler anagram değil");
    }

    static void alt_kume_kontrol(int[] dz1, int[] dz2){
        boolean durum = false;
        for (int j = 0; j<dz1.length; j++) {
           
            if (dz1[j] == dz2[(dz1[j] % dz2.length)]) {
                durum = true;
            }
           
            else {
               
                for (int k = (dz1[j] % dz2.length)+1; k<dz2.length && k != (dz1[j] % dz2.length); k++) {
                    if (dz1[j] == dz2[k]) {
                        durum = true;
                    }
                }
            }
        }
        if (durum) System.out.println("Alt küme");
        else System.out.println("Alt küme değil");
    }

}






YORUMLAR | Bu konuya toplam (0) yorum yapılmış


YORUM YAZ
Adınızı Girin:  * Doldurulması zorunludur



   Doğrulama Kodu


KATEGORİLER
  Genel (4)
  Güvenlik (1)
  Program (5)
  Windows (6)
  Mobil (2)
  Python 3.X (15)
  PARDUS (5)
  M.E.B. (1)
  Donanım (1)
  Java (9)
  Robotik (9)

SON YAZILARIM
  Ders 7 - Tür Dönüşümleri ve input() Fonksiyonu | 2020-04-07
  Ders 6 - Veri Türleri, type() ve len() Fonksiyonları | 2020-04-06
  Java List Interface | 2020-03-29
  Java Map Interface | 2020-03-29
  Java Set Interface | 2020-03-29
  Java Thread Sınıfı | 2020-03-29
  Java'da Tatih Biçimlendirme | 2020-03-28
  Matris Çarpımı | 2020-03-28
  Java Hata Türleri (Exceptions) | 2020-03-28
  Ders 1 - Python Nedir? | 2020-03-27