Forum

drzewa BST

[+] Twoje konto

Subskrybuj kanał najnowszych wypowiedzi w tym temacie

Wątek Forum > Porady > Programowanie > drzewa BST

Przemierzanie struktur dynamicznych, przepisywanie, sortowanie oraz sumowanie
Idź do strony:1
Ocena: (Ocen: 0)
Wypowiedzi 1 - 8 z 8
 Zarejestrowany, zwieszony browar04 Kopiuj nick (79.190.8.*) |  
Wypowiedź dodana: 27 marca 2012, 08:32:12
« Opcje

Błagam Pomocy!!!!

Mam bardzo poważy problem z zaliczeniem przedmiotu… Żeby zaliczyć algorytmy i struktury danych muszę napisać następujące procedury/algorytmy:

1. Przepisywanie drzewa na listę z zachowaniem porządku rosnącego ( chodzi o 2 zbiory liczb uporządkowanych rosnąco)

2. Sumowanie z listy jako sumowanie 2 zbiorów

Czy ktoś mógł by mi pomóc bo nic nie przychodzi mi do głowy … i zupełnie nie wiem jak to napisach… z góry dziękuje

 Gość REKLAMA Kopiuj nick (*->*)
Wypowiedź dodana: 27 marca 2012, 08:32:13

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (77.252.83.*) |  
Wypowiedź dodana: 27 marca 2012, 19:51:35
« Opcje

1. Proponuję proste, rekurencyjne przemierzanie drzewa i algorytm sortowania przez wstawianie.
2. Nie rozumiem.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

 Zarejestrowany, zwieszony browar04 Kopiuj nick (79.190.8.*) |  
Wypowiedź dodana: 28 marca 2012, 08:48:50
« Opcje

1 a coś więcej... jakiś przykład... chodzi mi o pierwszą część... bo sortowanie przez wstawianie to nie problem

2 chodzi o liste która jest wynikie sumy 2 zbiorów

 Zarejestrowany, zwieszony browar04 Kopiuj nick (79.190.8.*) |  
Wypowiedź dodana: 28 marca 2012, 09:19:36 | Wypowiedź edytowana Ostatnio edytowana: 28 marca 2012, 17:43:19 po raz 2-gi przez: Dżyszla
« Opcje

czy mogło by to być tak:

procedure inorder (t : ref);

begin
if t <> nil then
begin
inorder (t^.lewy);
P(t);
inorder (t^.prawy);
end;
end;

procedure sort z wstaw(n:integer; var a:tab);
var
j,p:integer;
begin
i:=2;
while (i<=n) do
begin
j:=i;
p:=a[i];
while (a[j-1]>p)and(j>0) do
begin
a[j]:=a[j-1];
j:=j-1;
end;

a[j]:=p;
i:=i+1;
end;
end;

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (77.252.83.*) |  
Wypowiedź dodana: 28 marca 2012, 17:51:29
« Opcje

Co do przemierzania drzewa, to jest ok. Dokładnie tak się robi. Choć nie wiem, co to P w środku jest, ale domyślam się że coś związanego z przepisaniem. Czemu akurat środek? (oczywiście działa, ale jakoś dziwne miejsce).

Co do sortowania - nie do końca tak... Co prawda tok poprawny, ale pewne uchybienia są. Najpierw powinniśmy znaleźć element większy od wstawianego (jeśli szukamy od lewej). Zakładam, że wstawiamy elementy dodatnie, a tablica wypełniona jest na początku zerami. Czyli na początku powinniśmy przelecieć tablicę szukając pierwszego elementu o wartości większej od wstawianego. W tym momencie ta pętla powinna się zakończyć.
Drugim etapem jest właśnie przesunięcie elementów. Jeśli wstawiamy od lewej, to wszystkie elementy od znalezionego do końca powinny być przesunięte w prawo. A więc od prawej strony schodzimy pętlą aż do indeksu, który wskazała poprzednia pętla. Potem wstawiamy.

No chyba, że miałeś inne założenie tego algorytmu sortowania, a ja nie dostrzegam czegoś?


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

 Zarejestrowany, zwieszony browar04 Kopiuj nick (79.190.8.*) |  
Wypowiedź dodana: 30 marca 2012, 10:59:00
« Opcje

Jeśli chodzi o P to jest to korzeń drzewa …

Co do reszty algorytmu to….. chodzi tutaj o 2 tablice wypełnioną dodatnimi liczbami uporządkowanymi rosnąco czyli od lewej do prawej

Czyli i = i + 1 tak??? a nie i = n

 Zarejestrowany, zwieszony browar04 Kopiuj nick (79.190.8.*) |  
Wypowiedź dodana: 30 marca 2012, 11:31:51 | Wypowiedź edytowana Ostatnio edytowana: 30 marca 2012, 17:24:01 po raz 1-wszy przez: Dżyszla
« Opcje

Wpadł mi do głowy pewien pomysł a czy można to zrobić tak:

procedure inorder (t : ref);
begin
if t <> nil then
begin
inorder (t^.lewy);
P(t);
inorder (t^.prawy);
end;
end;


var
a : array [1..n] of integer;

procedure quicksort;

procedure sort(l,p : integer);

var i,j : integer;
x,w: integer;

begin
i := l;
j := p;
x := a[(l + p) div 2];
repeat
while a[i] < x do i := i + 1;
while x < a[j] do j := j – 1;
if i <= j then
begin
w := a[i];
a[i] := a[j];
a[j] := w;
i := i + 1;
j := j – 1;
end
until i > j;
if l < j then sort (l,j);
if i < p then sort (i,p)
end;

begin
sort(1,n)
end

tylko mam jeden dylemat bo to są 2 oddzielne listy I musze je chba jakoś zsumować tak?

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (77.252.83.*) |  
Wypowiedź dodana: 30 marca 2012, 17:28:34
« Opcje

Ja bym to sortowanie przez wstawianie podzielił wyraźnie na dwie funkcje:
1. Znajdź miejsce do wstawienia (tablica, wartość): miejsce
1.a Pętla od lewej do miejsca, gdzie wartość jest większa od stawianego.
2. Wstaw (tablica, miejsce, wartość)
2.a. Od prawej do określonego przesuwa w prawo (a[i+1]:=a[i]).
2.b. Ustaw wartość.

To, co podałeś w drugim kodzie, to algorytm sortowania QuickSort. Ten algorytm pracuje na już wypełnionych tablicach. Jeśli jednak wstawiasz elementy to nie ma sensu jego używania - lepiej sortować przez wstawianie. Oczywiście takie sortowanie przez wstawianie można optymalizować, aby np miejsce wstawienia wyszukać poprzez bisekcję a nie liniowo. Ale to już jakiś tam kolejny krok. BTW - zastosowanie listy dynamicznej zamiast tablicy także pozwoli na znacznie wydajniejsze sortowanie przez wstawianie.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

 
Idź do strony:1

[+] Pokaż/odśwież listę czytających i monitorujących ten wątek

Podobne tematy:
Tytuł wątkuDziałWypowiedziWyświetleńOcenaOstatnia wypowiedź
Wątekdrzewo bstPorady / Programowanie2327 14.09.2007 21:01:05
WątekJakość wydruku po napełnieniu wkładu oraz resetowanie pojemników 339
Spadek jakości wydruków w drukarce HP DJ 5740 po napełnieniu wkładu 399 atramentem oraz sposób na zresetowanie wskaźnika poziomu tuszu
Porady / Sprzęt4340 17.10.2010 18:37:33
WątekDążenie do celu
Przemierzanie równoległych ścieżek pomiędzy dwoma punktami
Porady / Programowanie161 25.04.2008 12:19:06
WątekStatua Wolności oraz Wieża Eiffla
Komentarze do zdjęcia Statua Wolności oraz Wieża Eiffla
Komentarze / Galerie2189 12.09.2011 10:06:17
Wątek[Linux] Problem z uruchomieniem sieci WiFi pod Mandrivą 2007
Jak zainstalować sterowniki oraz skonfigurować kartę WiFi pod Mandrivą?
Porady / Oprogramowanie, systemy operacyjne151 894 29.02.2008 20:59:41

Nowa wypowiedź

Nowa wypowiedź
Nie jesteś zalogowany; będziesz traktowany jako gość!
Zaloguj Zaloguj
Nick (gość): | Przepisz ten kod [?]: 357d5:
Tekst:

 
* Wysyłając formularz wyrażasz zgodę na przetwarzanie przekazanych danych w zakresie wskazanym w Regulaminie

Subskrybuj kanał najnowszych wypowiedzi w tym temacie


Chcesz mieć też takie forum na swojej stronie? Napisz!

Strona istnieje od 25.01.2001
Ta strona używa plików Cookie.
Korzystając z niej wyrażasz zgodę na przetwarzanie danych a zakresie podanym w Polityce Prywatności.
Reklama  
archive To tylko kopia strony wykonana przez robota internetowego! Aby wyświetlić aktualną zawartość przejdź do strony.

Optymalizowane dla przeglądarki Firefox
© Copyright 2001-2018 Dawid Najgiebauer. Wszelkie prawa zastrzeżone.
Ostatnia aktualizacja podstrony: 15.07.2018 16:27
Wszystkie czasy dla strefy czasowej: Europe/Warsaw