[visual c#] błąd algorytmu sortowanie przez kopcowanie

Dla specjalistów Programowanie
#1

Witam! Na zajęciach napisaliśmy taki oto algorytm:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;


namespace WindowsFormsApplication1

{

    public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();

        }


        private void Form1_Load(object sender, EventArgs e)

        {


        }



        private void button1_Click(object sender, EventArgs e)

        {           

            int[] v_tablica = new int[] { 2, 1, 7, 4, 1, 3 };

            int[] v_tab_wynik = new int[] { };

            Wezel W = new Wezel(v_tablica[0]);



            for (int i = 1; i < v_tablica.Length -1; i++)

                 W.f_dodajElement(v_tablica[i]);



            for (int x = v_tablica.Length - 1; x > 0; --x)

            {

                v_tablica[x] = W.a_wartosc;

                W.a_wartosc = W.f_usun();

                W.f_porzadkuj();

            }


            v_tablica[0] = W.a_wartosc;



        }



    }


    public class Wezel

    {

        public Wezel a_rodzic;

        public Wezel a_lewy;

        public Wezel a_prawy;

        public int a_wartosc;

        public int a_liczbaEkementow = 0;


        public Wezel(int p_wartosc)

        {

            a_wartosc = p_wartosc;

            a_liczbaEkementow = 1;

        }


        public void f_dodajElement(Wezel p_nowy)

        {

            Wezel v_obecnie = this;

            string v_sciezka = Convert.ToString(++a_liczbaEkementow, 2);


            for (int i = 1; i < v_sciezka.Length - 1; i++)

            {

                if (v_sciezka[i].ToString() == "0")

                    v_obecnie = v_obecnie.a_lewy;

                else

                    v_obecnie = v_obecnie.a_prawy;

            }


            if (v_sciezka[v_sciezka.Length - 1].ToString() == "0")

                v_obecnie.a_lewy = p_nowy;

            else

                v_obecnie.a_prawy = p_nowy;


            p_nowy.a_rodzic = v_obecnie;

            v_obecnie = p_nowy;

            int tmp;

            while (v_obecnie.a_rodzic != null && v_obecnie.a_rodzic.a_wartosc < v_obecnie.a_wartosc)

            {

                tmp = v_obecnie.a_rodzic.a_wartosc;

                v_obecnie.a_rodzic.a_wartosc = v_obecnie.a_wartosc;

                v_obecnie.a_wartosc = tmp;

            }

        }



        public void f_dodajElement(int p_wartosc)

        {

            Wezel v_nowy = new Wezel(p_wartosc);

            f_dodajElement(v_nowy);

        }


        public int f_usun()

        {

            Wezel v_obecnie = this;

            string v_sciezka = Convert.ToString(++a_liczbaEkementow, 2);

            int r_wartosc;

            Wezel v_dziecko;


            for (int i = 1; i < v_sciezka.Length - 1; i++)

            {

                if (v_sciezka[i].ToString() == "0")

                    v_obecnie = v_obecnie.a_lewy;

                else

                    v_obecnie = v_obecnie.a_prawy;

            }


            if (v_sciezka[v_sciezka.Length - 1].ToString() == "0")

            {

                v_dziecko = v_obecnie.a_lewy;

                v_obecnie.a_lewy = null;

            }

            else

            {

                v_dziecko = v_obecnie.a_prawy;

                v_obecnie.a_prawy = null;

            }


            r_wartosc = v_dziecko.a_wartosc;

            v_dziecko.a_rodzic = null;


            --a_liczbaEkementow;

            return r_wartosc;

        }


        public void f_porzadkuj()

        {

            Wezel a_rodzic = this;

            Wezel v_dziecko;


            int v_tmp;

            while (true)

            {

                if (a_rodzic.a_prawy != null)

                {

                    if (a_rodzic.a_lewy.a_wartosc > a_rodzic.a_prawy.a_wartosc)

                        v_dziecko = a_rodzic.a_lewy;

                    else

                        v_dziecko = a_rodzic.a_prawy;


                }

                else if (a_rodzic.a_lewy != null)

                    v_dziecko = a_rodzic.a_lewy;

                else

                    break;


                if (a_rodzic.a_wartosc < v_dziecko.a_wartosc)

                {

                    v_tmp = a_rodzic.a_wartosc;

                    a_rodzic.a_wartosc = v_dziecko.a_wartosc;

                    v_dziecko.a_wartosc = v_tmp;

                    a_rodzic = v_dziecko;

                }

                else

                    break;

            }

        }



    }

}

jednak po implementacji, w zaznaczonym miejscu:

public int f_usun()

        {

            Wezel v_obecnie = this;

            string v_sciezka = Convert.ToString(++a_liczbaEkementow, 2);

            int r_wartosc;

            Wezel v_dziecko;


            for (int i = 1; i < v_sciezka.Length - 1; i++)

            {

                if (v_sciezka[i].ToString() == "0")

                    v_obecnie = v_obecnie.a_lewy;

                else

                    v_obecnie = v_obecnie.a_prawy;

            }


            if (v_sciezka[v_sciezka.Length - 1].ToString() == "0")

            {

                v_dziecko = v_obecnie.a_lewy;

                v_obecnie.a_lewy = null;

            }

            else

            {

                v_dziecko = v_obecnie.a_prawy;

                v_obecnie.a_prawy = null;

            }


            r_wartosc = v_dziecko.a_wartosc; // <-- tu mi się program wykrzacza...

            v_dziecko.a_rodzic = null;


            --a_liczbaEkementow;

            return r_wartosc;

        }

wywala błąd: przechwytywanienv.th.png

Jak to można naprawić?

#2

zadeklarowałeś obiekt:

Wezel v_dziecko;

ale nigdzie go nie zainicjowałeś np tak:

Wezel v_dziecko = new Wezel(v_tablica[0]);

czyli obiekt v_dziecko nie jest zostało utworzony więc nie możesz się do niego odwołać.

#3

Kiedyś pisałem swojąwersje tego algorytmu a że implementacja jest dużo prostrza pozwole sobie przytoczyć :

public static void sortoj_kopiec(ref int[] Array, int rozmiar)

        {

            int rodzic, temp;


            for (rodzic = rozmiar / 2; rodzic >= 0; --rodzic)

            {

                zrob_kopiec(ref Array, rodzic, rozmiar);

            }


            for (rodzic = rozmiar - 1; rodzic >= 0; --rodzic)

            {

                temp = Array[0];

                Array[0] = Array[rodzic];

                Array[rodzic] = temp;

                zrob_kopiec(ref Array, 0, rodzic);

            }

        }


        public static void zrob_kopiec(ref int[] Array, int rodzic, int rozmiar)

        {

            int dziecko, temp;

            while (rodzic < rozmiar / 2)

            {

                dziecko = (rodzic + 1) * 2 - 1;


                if (dziecko + 1 < rozmiar && Array[dziecko + 1] > Array[dziecko])

                {

                    dziecko = dziecko + 1;

                }


                if (Array[rodzic] < Array[dziecko])

                {

                    temp = Array[rodzic];

                    Array[rodzic] = Array[dziecko];

                    Array[dziecko] = temp;

                }

                else break;


                rodzic = dziecko;

            }

        }

Oraz Odpalenie

sortoj_kopiec(ref tablica, tablica.Length);