Wskaźnikowa lista dwukierunkowa z różnymi typami danych

Odpowiedz Nowy wątek
2015-01-12 15:59
0

Witam.
Mam wskaźnikową listę dwukierunkową i zastanawiam się czy i w jaki sposób jest możliwość aby do jednej listy wskaźnikowej dodawać "różne typy danych":

a) różne rekordy danych, na tym mi najbardziej zależy np.

TRecKolo = record
x,y: Integer;
R: Real;
end;

TRecProstokad = record
x,y: Integer;
a,b: Real;
kat: Real;
end;

b) różne klasy;

Znam TList ale chcę spróbować z listą wskaźnikową.

Pozostało 580 znaków

2015-01-12 19:10
2

a) zadeklaruj rekord pojedynczego węzła listy tak, aby oprócz wskaźników na kolejny/poprzedni węzeł, posiadał także pole typu np. Pointer - dzięki temu do węzła będziesz mógł wpisać wskaźnik na dowolne dane, nawet różnych typów;

b) zadeklaruj pole typu TObject i w sumie tak jak wyżej;

Ten sam sposób wykorzystałem we własnej konstrukcji bufora cyklicznego, działającego na zasadzie zapętlonej listy jednokierunkowej; Tyle że ja mam wszystko opakowane w klasy, więc taka konstrukcja była konieczna dla bazowej klasy bufora, aby na jej podstawie móc stworzyć klasy obsługujące dane już konkretnego typu.


edytowany 2x, ostatnio: furious programming, 2015-01-12 19:13

Pozostało 580 znaków

2015-01-12 19:16
3
TKolo = class
  private
    x,y : TPoint;
    r : Word;
  public
    // konstruktor destruktor itp.
end;

TProstakat = class
  private
    x, y, szerokosc, wysokosc : TPoint
  public
    // konstruktor destruktor itp.
end;

PElementListy = ^TElementListy;
TElementListy = record
  Objekt : TObject;
  prev,next : PElementListy
end;

Pozostało 580 znaków

2015-01-12 19:16
0

Dziękuję. Jak będę miał pytania jeszcze do tematu to się odezwę.

edit. Nawet przykład się trafił. Super dzięki :)

edytowany 1x, ostatnio: Integers, 2015-01-12 19:18

Pozostało 580 znaków

2015-01-12 19:29

@babubabu podał Ci przykład z klasami, a poniżej przykład z rekordami:

type
  TListNodeDataKind = (lndkCircle, lndkRectangle);

type
  PListNode = ^TListNode;
  TListNode = record
    PrevNode: PListNode;
    NextNode: PListNode;
    DataKind: TListNodeDataKind;
    Data: Pointer;
  end;

type
  PCircle = ^TCircle;
  TCircle = record
    Position: TPoint;
    R: UInt32;
  end;

type
  PRectangle = ^TRectangle;
  TRectangle = record
    Position: TPoint;
    A: UInt32;
  end;

Lista posiadać będzie węzły typu PListNode, a każdy węzeł będzie mógł przechowywać wskazanie na rekordy typu TCircle, TRectangle itd., czyli wpisane pointery typu PCircle, PRectangle itd.; A żeby dało się rozróżnić zawartość pola Data - wystarczy poprawnie uzupełnić pole DataKind i używać przy odczycie danych z węzła.


edytowany 1x, ostatnio: furious programming, 2015-01-12 19:31
Zabrałeś mi ptaszka >.< - babubabu 2015-01-12 22:27
To nie ja, to pytacz... ;P - furious programming 2015-01-12 22:59

Pozostało 580 znaków

2015-01-12 19:50
0

No fakt to będzie komplet :]. Jeszcze raz wielkie dzięki.. dwóch "ptaszków" zaznaczyć się nie da więc musiałem się na coś zdecydować.

Pozostało 580 znaków

2015-01-23 00:56
0

Witam ponownie. Co prawda z innej beczki ale na ten sam temat (było by w jednym miejscu).

Otóż mam pytanie bo wszędzie przeszukiwanie listy odbywa się w pętli While .. p:= p^.Next; poprzez przeskakiwanie po wskaźnikach.. czy i jak zrobić skok do konkretnego elementu listy w celu poprania danych.

Załóżmy że lista ma ten sam typ danych umieszczony w strukturach w przypadku:

TElementListy = record
  Objekt : TObject;
  prev,next : PElementListy
end;

oraz w przypadku zadeklarowanych powyżej ale dla przypomnienia:

  TListNode = record
    PrevNode: PListNode;
    NextNode: PListNode;
    DataKind: TListNodeDataKind;
    Data: Pointer;
  end;

Dla jasności. Np lista ma 10 pozycji, a jest potrzeba skoczyć do pozycji Index = 6.

  1. Na oko kombinowałbym z Size Of() ale no właśnie "of co" (dla klasy i dla rekordu).
  2. i może potem skok do Index*Size.. tylko jak? (dla klasy i rekordu)
    Na tym moje domysły się kończą więc z góry przepraszam jeśli "zabrzmiało" to komicznie :) Jeśli się nie da to ok ale może się da i zaoszczędziło by to Prockowi pracy przy przedzieraniu się przez dużą listę było by super.

Wszystko po to żeby skoczyć do danych tak jak tablicy dynamicznej w pozycji [Index] i to w miarę sprawnie.
Pozdrawiam

edytowany 2x, ostatnio: Integers, 2015-01-23 01:02

Pozostało 580 znaków

2015-01-23 03:22
1

Nie da się - albo rybki albo akwarium.

Pozostało 580 znaków

2015-01-23 03:27
2

czy i jak zrobić skok do konkretnego elementu listy w celu poprania danych.

Nijak inaczej - musisz przejść przez pewną ilość węzłów, bo innego wyjścia nie ma; Co prawda można to zoptymalizować, jednak i tak jakoś super szybko nie będzie, bo niestety, ale tak wygląda praca na listach;

Możesz trzymać wskaźniki na pierwszy i ostatni element listy; Przy wyszukiwaniu danego węzła, albo iterować po nich od pierwszego, albo w tył od ostatniego - to zależy w której połowie listy znajduje się szukany węzeł; Czyli jeśli w początkowej połowie to szukać od pierwszego, a jeśli w tej drugiej - od ostatniego;

Jest też taka opcja, żeby trzymać wskaźnik na aktualny węzeł i jego indeks; Co więcej, wyszukiwanie zawsze wykonywać od tego aktualnego, w zadanym kierunku (zależnym od indeksu szukanego węzła); Inicjujesz indeks na 0 oraz wskaźnik na pierwszy węzeł listy; Teraz jeśli indeks szukanego węzła jest większy od indeksu bieżącego - iterujesz po węzłach poprzez pole Next, gdzie w pętli wykonujesz tyle iteracji, ile jest różnycy pomiędzy tymi indeksami; Jeśli indeks szukanego węzła jest mniejszy - analogicznie używasz Prev i obliczasz ile iteracji pętli potrzebujesz;

Ten drugi sposób może być przydatny w pewnych warunkach, np. odczytywanie danych z kolejnych węzłów (w dowolnym kierunku); Dzięki temu zawsze wystarczy jedno przejście do Next lub Prev, bez konieczności wertowania całej listy; Tym bardziej, jeśli lista jest bardzo długa - zawsze będziesz miał stałą złożoność;

Jakkolwiek byś tego nie zrobił, i tak nie będziesz miał możliwości dostania się do danego węzła w tak prosty i szybki sposób, jak to ma miejsce w przypadku zwykłych macierzy i korzystaniu z indeksu bezpośrednio;

  1. i może potem skok do Index*Size.. tylko jak? (dla klasy i rekordu)

Znowu - nijak :]

Listy dają taką zaletę, że nie potrzebują alokacji ciągłego bloku pamięci; Dzięki temu wstawianie nowego węzła czy usuwanie istniejącego trwa bardzo krótko, bo nie trzeba przenosić danych po usuwanym elemencie i skracać bloku pamięci; A że nie potrzbują ciągłego bloku - kolejne ich węzły nie muszą istnieć w pamięci zaraz koło siebie;

Co prawda może się tak zdażyć, że akurat bloki pamięci wszystkich węzłów będą koło siebie, ale nic tego nie gwarantuje; Dlatego też żadna arytmetyka nie pomoże - po prostu trzeba iterować po węzłach; Jednak samo iterowanie można różnymi sposobami skrócić - o tym napisałem wcześniej;

PS: O drugim sposobie z zapamiętywaniem aktualnego węzła nigdy nic nie czytałem - po prostu kiedyś wpadłem na taki pomysł; Jednak szczegółowych badań na ten temat nie przeprowadziłem, więc trzeba by wykonać testy.


Pozostało 580 znaków

2015-01-23 10:12
0

@szopenfx też mi się tak wydaje ale może się uda jakiś konsensus wywalczyć ;)

Dzięki @furious programming.. po tym jak zamieściłem wpis przyszło mi do głowy że przecież często używam Stringów bez deklarowanej długości więc Size of nie poskutkowało by. Pozostaje chyba zrobić listę pomocniczą z dziesięciu "strażników" wskazujących na elementy oddalone od siebie ok np.10% długości listy.. albo co tysięczny element jeśli lista będzie długa.

I teraz mam dylemat bo tam gdzie lista się ewidentnie nadaje z szybkim przeglądaniem i pokazywaniem na całej długości to nie mam wątpliwości. Ale w przypadku najprostszej tabeli danych z sortowaniem wg kolumn i wyświetlanie w TStringGrid .. bo do tego można by najprościej "pożądany efekt" porównać.
Może na przykładzie.. w tej chwili w jednym z przypadków mam (w uproszczeniu) dynamiczną listę rekordów np

ArrD: TArrD = array of TDane; 

i listę dynamiczna list dynamicznych typu

ArrI: TArrI = array of Integer

służące do sortowań.
W efekcie listy indeksów są jako struktura

TArrI2 = array of TArrI 

Więc nawet jeśli przyjmiemy że najprościej dodać nowy rekord danych na końcu listy a uaktualnić listy indeksów na te rekordy to potem mamy przy przeglądaniu listy posortowanej wg którejś kolumny całej listy lub tylko wybranych danych np dla konkretnego parametru

Nazwisko='Kowalski'

W tej chwili odwołanie żeby wyświetlić wygląda tak

ArrD[ ArrI2[IndexListyNazwisk,j] ].Nazwisko

Więc nie wiem czy dobrze kombinuję ale może listę danych zrobić jako pozostawić tabelę dynamiczną bo tu są częste odwołania do konkretnej pozycji na liście a listy indeksów zrobić jako wskaźniki? Bo tu przeglądanie listy jest i przy wstawianiu kasowaniu pozycji a także przy wyświetlaniu?

dodanie znaczników <code class="delphi"> - @furious programming

edytowany 10x, ostatnio: Integers, 2015-01-23 15:35
moja wina z tymi znacznikami, poprawię się - Integers 2015-01-23 12:36

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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