logo elektroda
logo elektroda
X
logo elektroda
Szukanie Zaawansowane
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Usuwanie elementów o wartości minimalnej w liście dwukierunkowej Turbo Pascal

DeDeZabrzE 23 Mar 2009 17:16 6214 3
Zgłoś naruszenie prawa
Odpowiedz | Nowy temat
  • #1 6321675
    DeDeZabrzE
    Poziom 10  
    Posty: 16
    Ocena: 1
    Witam oto dostałem zadanie domowe. Napisz program tworzący listę dwukierunkową oraz realizujacy zadania:
    -usuwania elementów o wartości minimalnej
    -wypisywania elementów listy od końca.

    Wypisywanie już zrobiłem, lecz nie daje rady z tym usuwaniem. Czy może ktoś pomóc ???
    a oto kod
    Kod: text Rozwiń Zaznacz wszystko Kopiuj do schowka
    
program dwukierunkowa;
uses crt;
const
  N = 15;
type wskLista = ^element;
  element = record
    dane : integer;
    wskPoprzednika : wskLista;
    wskNastepnika : wskLista;
  end;
type nodeList = ^e;
  e = record
    first : wskLista;
    last: wskLista;
    aktualny: wskLista;
  end;
var
  lista: nodeList;
  wartosc : integer;
  co: char;
procedure showActual(var lista: nodeList);
begin
  writeln(lista^.aktualny^.dane);
end;
procedure createList(var lista : nodeList);
begin
  lista^.first := nil;
  lista^.last := nil;
  lista^.aktualny := nil;
end;
procedure deleteList(var lista : nodeList);
var
  tmp: wskLista;
begin
  lista^.aktualny := lista^.first;
while lista^.aktualny <> nil do
    begin
      tmp := lista^.aktualny^.wskNastepnika;
      writeln('Usuwam element ',tmp^.dane,' offset: ',ofs(tmp^.dane));
      dispose(lista^.aktualny);
      lista^.aktualny := tmp;
    end
end;

procedure readList(var lista : wskLista);
var
  tmp : wskLista;
begin
  writeln('Zawartosc Listy od Konca');
  tmp := lista;

  while tmp <> nil do
    begin
      write(' => ',tmp^.dane);
      tmp := tmp^.wskPoprzednika;
    end;
  writeln;
end;
procedure pushFront(var lista : nodeList; nowy: wskLista);
begin
  lista^.first := nowy;
  nowy^.wskNastepnika := lista^.aktualny;
  lista^.aktualny^.wskPoprzednika := nowy;
  nowy^.wskPoprzednika := nil;
  lista^.aktualny := nowy;
end;
procedure pushInside(var lista : nodeList; nowy: wskLista);
begin
  lista^.aktualny^.wskPoprzednika^.wskNastepnika := nowy;
  nowy^.wskNastepnika := lista^.aktualny;
  nowy^.wskPoprzednika := lista^.aktualny^.wskPoprzednika;
  lista^.aktualny^.wskPoprzednika := nowy;
end;
procedure pushEnd(var lista: nodeList; nowy: wskLista);
begin
	if lista^.first = nil then
		lista^.first := nowy
	else
		begin
			lista^.last^.wskNastepnika := nowy;
			nowy^.wskPoprzednika := lista^.last;
		end;
	lista^.last := nowy;
end;
procedure push(var lista: nodeList; wart: integer);
var
	nowy: wskLista;
begin
	new(nowy);
	nowy^.dane := wart;
	if lista^.aktualny <> nil then
		begin
			if lista^.aktualny = lista^.first then
				pushFront(lista, nowy)
			else
				pushInside(lista, nowy)
		end
	else
		pushEnd(lista, nowy)
end;

begin
  new(lista);
  createList(lista);
  repeat
    clrscr;
    writeln('d - dodaj do listy');
    writeln('z - usun z listy minimalna wartosc');
    writeln('w - wypisz liste od Konca');
    writeln('q - koniec');
    co:=readkey;
    case co of
      'd': begin write('podaj warosc: '); read(wartosc); push(lista, wartosc); end;
     // 'z': begin pop(lista); end; //
      'w': begin readList(lista^.last); co:=readkey; end;
    end;
  until co='q';
  deleteList(lista);

end.

    oraz zwykle usuwanie, którego ma nie byc w programie.
    Kod: text Rozwiń Zaznacz wszystko Kopiuj do schowka
    
procedure popFront(var lista: nodeList);
begin
	lista^.first := lista^.first^.wskNastepnika;
	write('usunieto aktualny czyli ');
	showActual(lista);
	dispose(lista^.aktualny);
	lista^.aktualny := lista^.first;
	if lista^.first <> nil then
		lista^.first^.wskPoprzednika := nil
	else
		lista^.last := nil
end;
procedure popInside(var lista: nodeList);
var
	tmp: wskLista;
begin
	tmp := lista^.aktualny^.wskPoprzednika;
	tmp^.wskNastepnika := lista^.aktualny^.wskNastepnika;
	lista^.aktualny^.wskNastepnika^.wskPoprzednika := tmp;
	write('usunieto aktualny czyli ');
	showActual(lista);
	dispose(lista^.aktualny);
	lista^.aktualny := tmp;
end;
procedure popEnd(var lista: nodeList);
var
	tmp: wskLista;
        begin
	tmp := lista^.aktualny^.wskPoprzednika;
	tmp^.wskNastepnika := nil;
	lista^.last := tmp;
	write('usunieto aktualny czyli ');
	showActual(lista);
	dispose(lista^.aktualny);
	lista^.aktualny := lista^.last;
end;
procedure pop(var lista : nodeList);
begin
	if lista^.aktualny <> nil then
	begin
	if lista^.aktualny = lista^.first then
		popFront(lista)
	else
	begin
		if lista^.aktualny = lista^.last then
			popEnd(lista)
		else
			popInside(lista)
	end
	end
end;
    eufyMake E1 - łatwa personalizacja za pomocą druku UV [sponsorowany]
  • #2 6327593
    adamz74
    Poziom 33  
    Posty: 1287
    Pomógł: 269
    Ocena: 194
    Na wstępie musisz się wypowiedzieć, co w przypadku, gdy występuje w liście kilka elementów o wartości równej i jednocześnie będzie to wartość minimalna. IMO, mogą być następujące rozwiązania:
    1. wyświetlamy komunikat i nic nie robimy,
    2. usuwamy pierwszy (lub ostatni) napotkany element,
    3. usuwamy wszystkie elementy o wartości minimalnej.

    Odnośnie poz. 3. można, to zrobić na dwa sposoby:
    a. powtarzamy usuwanie z pkt. 2 tyle razy, ile razy występuje dana wartość,
    b. tworzymy listę elementów o wartości minimalnej i następnie je usuwamy.

    Najprościej będzie zrobić "usuwanie pierwszego lub ostatniego napotkanego elementu o wartości minimalnej". Usuwanie wszystkich wystąpień jest już trochę trudniejsze. Pomijam rozwiązanie z wyświetlaniem komunikatu :)

    Co należy należy zrobić:
    1. znaleźć element o wartości minimalnej, czyli:
    - zdefiniować zmienne pomocnicze do przechowywanie bieżącej wartości minimalnej i wskaźnik (rozwiązanie 3b - listę wskaźników) do elementu, który ma tą wartość oraz licznik wystąpień,
    - przewędrować listę do początku do końca lub odwrotnie, w końcu jest dwukierunkowa i znaleźć element (elementy) o wartości minimalnej (Uwaga: jest to etap w którym jednocześnie możemy podliczać ilość wystąpień - rozwiązanie 3a i/lub tworzyć listę wskaźników do elementów z wartością minimalną - rozwiązanie 3b),
    - po zakończeniu powinno się otrzymać jaka jest wartość minimalna w całej liście oraz wskaźnik (lub listę wskaźników - rozwiązanie 3b) do tego elementu oraz ilość wystąpień elementu o wartości minimalnej.

    2. usunąć element n (lub elementy - rozwiązanie 3b), czyli:
    - zmodyfikować wskaźniki następny i poprzedni dla n-1 i n+1 żeby wskazywały na siebie,
    - usunąć element n,

    (dla rozwiązania 3a po usunięciu elementu, jeśli ilość wystąpień elementu o wartości minimalnej byłaby większa od 1 należałoby wrócić pkt. 1)

    W nawiasach dopisałem co należy zrobić w przypadku usuwania wszystkich wystąpień na wartości minimalnej. Mam nadzieję, że za bardzo nie namieszałem :)

    Pozdr!
  • #3 6332302
    DeDeZabrzE
    Poziom 10  
    Posty: 16
    Ocena: 1
    Nie no dobra, przyjacielu u mnie dostał byś 6+ za tą wypowiedz. Lecz szczerze powiedziawszy rozumię 1/3 twojej wypowiedzi. Pewnie zrozumiał by ją fachowy programista, lecz ja jestem na grafice i PS wogóle się nie przejmuję. Czy mógłbym dostac jeszcze jakieś wskazówki ? może jakaś procedurka z objaśnieniami?
  • #4 6336684
    adamz74
    Poziom 33  
    Posty: 1287
    Pomógł: 269
    Ocena: 194
    Wypowiedź miała trochę nakierować i zmusić do myślenia. To, że jesteś na grafice nie oznacza wcale, że znajomość programowania Ci się nie przyda... no chyba, że robisz akademię sztuk pięknych, jakieś malarstwo olejne lub akwarele :D. Tak się składa, że programy graficzne (i wiele innych, nawet Exel i Word) mają wbudowane całkiem złożone języki skryptowe i uwierz mi: znajomość programowania się bardzo przydaje!

    Na początek procedurka, która w założeniu (nie mam jak tego przetestować, więc mogłem popełnić jakiś błąd!) ma znaleźć element minimalny i zwrócić wskaźnik do niego. Dodatkowo zwraca minimalną znalezioną wartość i ile razy występuje ona w liście.

    Kod: text Rozwiń Zaznacz wszystko Kopiuj do schowka
    
procedure znajdzMin(var lista : nodeList; var minElement : wskLista; var minWartosc : Integer; var ileWystapien : Integer);
begin
  minElement := nil;
  ileWystapien := 0;
  
  lista^.aktualny := lista^.first;
  while lista^.aktualny <> nil do
   begin
     if minElement = nil then begin
        minElement := lista^.aktualny;
        minWartosc := minElement^.dane;
        ileWystapien := 1;
      end else
        if lista^.aktualny^.dane < minWartosc then begin
           minElement := lista^.aktualny;
           minWartosc := minElement^.dane;
           ileWystapien := 1;           
         end else 
           if lista^.aktualny^.dane = minWartosc then ileWystapien := ileWystapien + 1;
     lista^.aktualny := lista^.aktualny^.wskNastepnika;
   end;
end; 


    Sprawdź czy działa i sam pokombinuj jak usunąć taki element z listy :D
Odpowiedz | Nowy temat
Zgłoś naruszenie prawa
REKLAMA