Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Sortowanie listy dwukerunkowej



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Mariusz M
Gość





PostWysłany: Wto Maj 22, 2018 9:39 pm  OP    Temat postu: Sortowanie listy dwukerunkowej Odpowiedz z cytatem Pisownia

Znalazłem funkcje realizujące sortowanie listy jednokierunkowej
Jak ustawić wskaźniki na poprzedniki tak aby znalezione funkcje realizowały także
sortowanie list dwukierunkowych

Kod:


procedure split(head:PNode;var front,back:PNode);
var fast,slow:PNode;
begin
  if (head = NIL)or(head^.next = NIL)then
  begin
    front := head;
    back := NIL;
  end
  else
  begin
    slow := head;
    fast := head^.next;
    while fast <> NIL do
    begin
      fast := fast^.next;
      if fast <> NIL then
      begin
        slow := slow^.next;
        fast := fast^.next;
      end;
    end;
    front := head;
    back := slow^.next;
    slow^.next := NIL;
  end;
end;

procedure merge(var head:PNode;l1,l2:PNode);
var dummy,curr:PNode;
begin
  new(dummy);
  dummy^.next := NIL;
  curr := dummy;
  while(l1 <> NIL)and(l2 <> NIL)do
  if l1^.key < l2^.key then
  begin
    curr^.next := l1;
    curr := curr^.next;
    l1 := l1^.next;
  end
  else
      if l1^.key > l2^.key then
      begin
        curr^.next := l2;
        curr := curr^.next;
        l2 := l2^.next;
      end
      else
      begin
        curr^.next := l1;
        curr := curr^.next;
        l1 := l1^.next;
        curr^.next := l2;
        curr := curr^.next;
        l2 := l2^.next;
      end;
      if l1 = NIL then
        curr^.next := l2
      else
        curr^.next := l1;
      head := dummy^.next;
      dispose(dummy);
end;

procedure mergeSort(var head:PNode);
var h1,h2:PNode;
begin
  h1 := NIL;
  h2 := NIL;
  if (head <> NIL)and(head^.next <> NIL)then
  begin
    split(head,h1,h2);
    mergeSort(h1);
    mergeSort(h2);
    merge(head,h1,h2);
  end;
end;



Jak zmieniłby się kod gdybyśmy zrezygnowali z użycia wartownika w funkcji scalającej
Co zyskujemy wprowadzając wartownika do funkcji scalającej


Jeśli chodzi o sortowanie przez podział to znalazłem algorytm dla tablic w przykładach Pascala
Jak go przepisać tak aby działał także dla listy
Zamianę elementów chciałbym zastąpić wstawianiem i usuwaniem bo zamiana elementów lepiej
działa dla tablic

Znalazłem też funkcje przydatne do sortowania drzewem BST
i wydaje się kod napisany z użyciem znalezionych funkcji działa
Powrót do góry
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.11589 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |