Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Heap vs. Stack

Werbeanzeige

Triac

Treue Seele

Beiträge: 199

  • Private Nachricht senden

11

11.01.2006, 11:11

hehe .. da gehts ja wie in einer kuschelecke zu :-D

Zitat


Helmut du bist ein Schatz könnte dich echt Küssen!
Das das so einfach ist hätte ich jetzt auch nicht gedacht!
Also einfach aus der Struktur eine Klasse machen mit einem Konstruktor und dann klappt es auch schon.
Helmut du hast was bei mir gut!


mfg Triac
/Acer Aspire 5920

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

12

11.01.2006, 11:30

auch strukturen können konstruktoren haben, zumindest ging das mal mit den ms vc++ :)
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Anonymous

unregistriert

13

11.01.2006, 20:15

Also ob du strukturen benutzt oder klassen ist bei c++ nahezu völlig gelichhültig.

In c++ sind Klassen und Strukturen fast das selbe.
Der einzige Unterschied ist der, dass das Zeug in Klassen standardmäßig privat ist und in Strukturen standardmäßig public.

Wenn man immer Begriffe wie private und public nutzt gibt es keinerlei Unterschiede.

Meandor

Frischling

  • »Meandor« ist der Autor dieses Themas

Beiträge: 55

Wohnort: Oberhausen

Beruf: Student

  • Private Nachricht senden

14

12.01.2006, 12:16

hätte denn einer eine Idee zu dem sort() Befehl! Wie kann man sich das erklären wonach die Liste sortiert wird und wie man die den Befehl anders schreiben müsste damit die Liste richtig sortiert wird zum Beispiel soll das Listenelement mit der kleinsten Zeit vorne stehen. (Wie geht das?) Oder benötige ich dazu einen komplett anderen Aufbau der Liste?

Mit bestem Dank

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

15

12.01.2006, 12:48

Zum Neusortieren einer Liste eignet sich "Heap-Sort". Der hat eine Laufzeitkomplexität von O( n * log n ), wobei n die Anzahl der Elemente der Liste bezeichnet.
Heap-Sort arbeitet mit einer Liste in Form eines Arrays. Liegt eine verkettete Liste vor, sollte diese also erst in ein Array konvertiert werden. Das ist aber kein Problem und es gibt auch mehr oder weniger effiziente Verfahren hierfür: Entweder man erzeugt ein Array, das als Elemente genau die Elemente der linearen Liste enthält.
Besser ist allerdings ein Array mit Referenzen auf die einzelnen Knoten zu halten, da -- je nach Größe der Objekte -- so weniger Kopieraufwand betrieben werden muss. Die "Nachfolger-Zeiger" (und ggf. "Vorgänger-Zeiger") der einzelnen Knoten können dann zum Schluss neu gesetzt werden, indem das (sortierte) Array durchlaufen wird.
Wenn die Liste Zeiger auf Objekte speichert, bietet es sich sogar an, das Array mit den Zeigern dieser Objekte zu speichern und neu zu sortieren. Am Ende würden so nur die Referenzen der Knoten auf diese Objekte neu gesetzt.
Je nachdem, was Du (vor-)hast, bietet sich die ein oder andere Alternative an.
Darüber hinaus gibt es auch noch andere Sortier-Verfahren...

edit: "Heap-Sort", der Begriff hat jetzt weniger was mit "Stack" und "Heap" zu tun.

koschka

Community-Fossil

Beiträge: 2 862

Wohnort: Dresden

Beruf: Student

  • Private Nachricht senden

16

12.01.2006, 13:12

.... bei den meisten Listen reicht ein Pointer auf den Nachfolger, man kann trotzdem einen Knoten auch vorn daran machen. Nur so als kleine Ergänzung ^^

Phil_GDM

Alter Hase

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

17

12.01.2006, 14:24

Zitat von »"Meandor"«

hätte denn einer eine Idee zu dem sort() Befehl! Wie kann man sich das erklären wonach die Liste sortiert wird und wie man die den Befehl anders schreiben müsste damit die Liste richtig sortiert wird zum Beispiel soll das Listenelement mit der kleinsten Zeit vorne stehen. (Wie geht das?) Oder benötige ich dazu einen komplett anderen Aufbau der Liste?

Mit bestem Dank


Die Datenstruktur muss einfach nur den Operator < implementiert haben, dann kann die Liste sortiert werden denn zum Sortieren ist nun mal eine Vergleichsoperation notwendig
(Anmerkung: ausser du verwendest ein Sortierverfahren wie Fachverteilung etc., das nicht auf dem Vergleichsprinzip beruht)
Das mit dem < Operator gilt glaub ich jetzt für die STL-Liste, wenn du eine eigene Liste schreibst, könntest du auch festlegen, dass es der > Operator für die Datenstruktur definiert sein muss.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct time
{
  __uint32 hour, minute, second;
  bool operator < (time& const t) const
  {
     if(hour <= t.hour)
     {
         if(minute <= t.minute)
         {
              if(second < t.second)
                  return true;
          }
      }
      return false;
   }
};

mfg Philipp

Meandor

Frischling

  • »Meandor« ist der Autor dieses Themas

Beiträge: 55

Wohnort: Oberhausen

Beruf: Student

  • Private Nachricht senden

18

12.01.2006, 15:04

Jungs das sagt mir jetzt alles immer weniger! Natürlich kenne ich auch Listen die immer nur einen Zeiger auf das nächste Element haben und den Vorgänger nicht kennen.
Ich bin aber kein Profi (sondern Neuling) also versuche ich es mit der STL Liste. Die hat ja wohl wie mir sicher jeder bestätigen kann den Befehl sort(); also sortieren.

Heiko schreibt im Listing 9.5 eine verkettet Liste mit <int> und diese wird dann doch anschließend sortiert. 1,1,2,3,3,4,6,6,7, usw...... egal an welcher Stelle er Elemente mittels insert() bzw erase() verändert hat.

Das gleich will ich auch nur mit mehreren Listenelementen also in etwa so.
Nr, Zeit, Status
1, 500, GEMELDET
2, 500, GEMELDET
3, 900, GEMELDET
4, 700, GEMELDET
5, 400, AKTIV
6, 900, GEMELDET
7, 450, AKTIV
8, 700, AKTIV

jetzt soll die STL einfach mal mir die Arbeit erleichtern und ich schreibe einfach
lAuftragsliste.remove ('AKTIV') //wäre nur Beispiel
und schwupps sollen alle Aktiven Elemente aus der Liste gelöscht werden und wenn ich die Liste ausgeben würde erschiene.

1, 500, GEMELDET
2, 500, GEMELDET
3, 900, GEMELDET
4, 700, GEMELDET
6, 900, GEMELDET

ich hatte ja schon eine Idee wie man das machen könnte

Zitat von mir selber!

Zitat


Ich mein klar man kann das umgehen in dem man einfach eine Prüffunktion schreibt die die Liste durchläuft und bei
(*i)->Status==GEMELDET die Position ausgibt und dieses Element wird dann mittels lAuftrag.erase(Position) gelöscht.

Aber mittels remove() müsste das doch in einem Ruck gehen.
Frage wäre also was muss man der remove Funktion übergeben das diese direkt alle Elemente löscht.


Aber dazu benötige ich mehrere Schleifen Durchläufe was ja auch Zeit kostet.
Ich will also wie in einer Excel Tabelle aufanhieb alle Element löschen die einen bestimmten Eintrag enthalten.

Phil_GDM

Alter Hase

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

19

12.01.2006, 15:35

hast du mein vorheriges Postiong gelesen?
Denn dann solltest du bereits wissen, wie das geht.

In dem Fall den du jetzt beschrieben hast:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

enum STATUS
{
  ACTIVE, REGISTERED;
};

struct Element
{
  __uint32 nr, time;
  STATUS status;
  
  bool operator < (Element& e const) const
  {
    if(status == REGISTERED && e.status == ACTIVE)
      return true;
    return false;
  }
};


So würde die STL-Liste beim Aufruf von Sort wissen, wie der Datentyp sortiert werden kann und alle Records mit dem Status Registered an den Anfang der Liste geben

mfg Philipp

Meandor

Frischling

  • »Meandor« ist der Autor dieses Themas

Beiträge: 55

Wohnort: Oberhausen

Beruf: Student

  • Private Nachricht senden

20

12.01.2006, 17:41

So bin gerade nach Hause gekommen und wieder fleißig am Werk den Code von Phil zu verstehen (ist mir noch nicht ganz klar!)

Ersteinmal super Einfall das mit dem Enum das erleichtert einiges! Ist besser als #define GEMELDET 'G' .

aber:

Zitat


enum STATUS
{
ACTIVE, REGISTERED;
};


nach den REGISTERED darf kein Semi stehen! Also das schon mal weg lassen. Sonst Compiler Fehler! Zumindest gab es das bei mir!

was ich jetzt nicht ganz verstehe ist

C-/C++-Quelltext

 
1
2
3
4
5
6

bool operator < (Element& e const) const 
  { 
    if(status == REGISTERED && e.status == ACTIVE) 
      return true; 
    return false; 
  }

das ist also eine Funktion innerhalb der Struktur (wußte gar nicht das das geht dachte das klappt nur bei Klassen solche memberfunktionen oder was ist das genau also laut msdn verstehe ich das das neue Wort operator für Overloadings zuständig ist. Was sollen die zwei const in der einen Zeile?

wie kann ich denn eine solche Funktion dann auf rufen einfach nur sort(); und fertig??
verbiegt diese Funktion dann automatisch die Listenzeiger auf den nachfolgenden bzw dem Vorgänger?
Ansich gibt diese Funktion ja nur eine NULL oder eine 1 aus.

Werbeanzeige