Mając dwa stosy włóż do trzeciego wszystkie ich elementy

0

Są dwa stosy w których elementy ułożone są rosnąco i trzeba je wrzucić na trzeci stos, też rosnąco.

ja bym zrobił tak, że najpierw wrzucam do tablicy elementy stosu nr.1 potem dorzucam elementy stosu nr.2 wykonuje quicksort i wrzucam na stos nr.3

ale nie bardzo wiem jak mogę w tablice wpisać te wszystkie elementy...

0

nie tak. niepotrzebnie zwiększasz złożoność sortowaniem. jeśli A i B to stosy wypełnione o rozmiarach a i b, chcesz wrzucić elementy na stos C, to:

i = 0
j = 0
for k=0 to a+b-1:
  if i<a  and  A[i] < B[j]:
    C[k] = A[i]
    i++
  else if j<b  and  B[j] <= A[i]:
    C[k] = B[j]
    j++

edit: przyjrzyj się algorytmowi sortowania przez scalanie. tam masz podobny problem.

0

A stosy mogę sobie traktować jak tablicę, nie muszę używać pop(),push(),top itp ?

1

@up - trochę myślenia, robisz to analogicznie

while !a.empty() and !b.empty():
    if a.top() < b.top():
        c.push(a.pop())
    else
        c.push(b.pop())
while !a.empty():
   c.push(a.pop())
while !b.empty():
    c.push(b.pop())
0

to zależy jak masz zaimplementowany ten stos. jako tablicę czy listę wskaźnikową?

while A or B:
  if A:
    a = A.top()
  else 
    a = infinity
  if B:
    b = B.top()
  else
    b = infinity
  if a < b:
    C.push(A.pop())
  else:
    C.push(B.pop())

po tym stos A i B są puste.

0

Nie no ok, jasne, rozumiem. Dzięki.

0

to jest to samo co w wieżach hanoi

0

nie chciałbym zakładać nowego tematu, a mam pytanie do 3 krótkich zadanek, więc może ktoś mi pomoże.

1.) Sprawdź ile jest elementów równych x w drzewie poszukiwań binarnych nie przechodząc całego drzewa.
2.) Dana jest posortowana rosnąco lista sprawdź ile jest w niej elementów większych od a i mniejszych od b
3.) usun element X z kopca typu MIN

1.) while key[x] < key
x<-right[x]
i=0
return BSTinorder(x,i)

BSTinorder(x,i)
if(x != nill )
BSTinorder(left[x])
i++
BSTinorder(right[x])
return i

2.) SPR(root)
licznik=0;
if(key[x] > a && key[x] < b) licznik++
while next[x] != nill
if key[next[x]] > a && key[next[x]] < b
licznik++
x<-next[x]
return licznik

3.) mam tu wywołać inorder dla korzenia i szukać elementu równego x ? czy może - to przecież struktura tablicowa - posortować np. qs i za pomocą dziel i zwyciężaj znaleźć ten element x i go usunąć co nie będzie łatwe przy kopcu bo musiał bym wywołać procedure budującą kopiec i przywracająca jego własności.

0
  1. zrobiłeś to czego miałeś nie robić, czyli przechodzisz całe drzewo...
s = szukana wartosc
node = root
count = 0
while node:
  if s < key[node]:
    node = left[node]
  else if s > key[node]:
    node = right[node]
  else:
    count = count + 1
    if right[node] and key[right[node]] == s:
      node = right[node]
    else if left[node] and key[left[node]] == s:
      node = left[node]
    else:
      break
item = poczatek listy
count = 0
while item and key[item] < b:
  if key[item] > a:
    count = count + 1
  item = next[item]
  1. tablica posortowana rosnąco jest kopcem typu min. ale najlepiej wstawić ostatni element zamiast pierwszego, skrócić tablicę o 1, a następnie wykonać procedure increase-key dla kopca (zobacz jak jest zaimplementowana kolejka priorytetowa z użyciem kopca, tam jest procedura pop)
0

a w 2 zadaniu, jeżeli klucz pierwszego elementu jest mniejszy od b, to nic dalej sie nie wykona ?

1 użytkowników online, w tym zalogowanych: 0, gości: 1