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!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 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!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 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!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 
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ą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ęt4316 17.10.2010 18:37:33
WątekDążenie do celu
Przemierzanie równoległych ścieżek pomiędzy dwoma punktami
Porady / Programowanie154 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 / Galerie2180 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 876 29.02.2008 20:59:41
WątekIDG - problemy z Forum IDG, z Wydawnictwem, z poziomem artykułów itd.
Czy IDG schodzi na psy? Tu możesz się wypowiedzieć o sytuacji na Forum IDG, poziomie artykułów oraz polityce administracyjnej Wydawnictwa IDG
Pogaduchy2 89089 559 11.09.2012 09:25:48

Nowa wypowiedź

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

 

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
Reklama  
archive To tylko kopia strony wykonana przez robota internetowego! Aby wyświetlić aktualną zawartość przejdź do strony.
Ładowanie...

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