Strukturen einer Skip-List

WurzelAusZwei

Hallo!

Ich habe als Programmieranfänger im Zug meines Studiums folgende Programmieraufgabe in C zu lösen: Das Programm soll Spielerdaten aus einer Binärdatei einlesen und verarbeiten. Die Datenstruktur hat zwingenderweise durch eine Skip-Liste zu erfolgen.

Jeder Datensatz besteht aus einem Header (ID, Score, Content-Länge) und einem Content (Username, Clan). Dabei sollen die eingelesenen Daten auch folgendermaßen sortiert werden: Primär nach Clan (absteigend nach der Summe der Punkte des Clans) und sekundär nach Spielerpunkten. Es sind noch weitere Funktionalitäten auszuprogrammieren, das spielt für meine Frage allerdings keine Rolle.

Die Verwendung der Skip-Liste habe ich in dem Fall so verstanden, dass jeder Datensatz nicht nur einen Zeiger auf den nächsten Datensatz hat, sondern auch einen Zeiger auf den ersten Datensatz des nächsten Clans (sofern vorhanden). Sprich, wir haben nur 2 Ebenen in der Skip-Liste (Ebene der Spieler und Ebene der Clans).

Mir bereitet jetzt aber schon die Erstellung der notwendigen Structs Probleme. Ich habe bisher 2 Ansätze:

struct _DataSetHeader_
{
  unsigned int id_;
  unsigned int score_;
  unsigned int content_length_;
};

struct _DataSetContent_
{
  char *username_;
  char *clan_;
};

struct _DataSet_
{
  struct _DataSetHeader_ *header_;
  struct _DataSetContent_ *content_;
  struct _DataSet_ *next_;
};

Problem: Wo bringe ich den Zeiger auf den nächsten Clan unter?

Die Idee war, für Spieler und Clans eigene Structs anzulegen, etwa so in der Art:

struct _Player_
{
  unsigned int id_;
  unsigned int score_;
  unsigned int content_length_;
  char *username_;
  struct _Player_ *next;
};

struct _Clan_
{
  unsigned int id_;
  char *clanname_;
  struct _Player_ *player_;
  struct _Clan_ *next_;
};

Ich wäre über jede Hilfe/jeden Denkanstoß dankbar!

Liebe Grüße
WurzelAusZwei

kann es sein dass du an der tu graz studierst und esp machst? ^^
denn ich habe komplett das gleiche beispiel und habe auch keinen plan.

ich habs mal so versucht.
bin aber nicht sicher ob das was nützt.

typedef struct _Header_
{
struct _Header_* next;
unsigned int id_;
unsigned int score_;
unsigned int content_;
};

typedef struct _Content_
{
char username_;
char clan_;
struct _Content_* skip;
};

struct _Header_* next = NULL;
struct _Content_* skip = NULL;

der skip pointer soll dann der sein der auf das erste element des nächsten clans zeigt. könnte so mal das struct aussehen? was sagst du?

WurzelAusZwei

Hm, ich denke nicht, dass deine Structs so Sinn machen. Jeder Datensatz hat aus Header und Content zu bestehen. Bei dir hast du das alles getrennt, sozusagen 2 eigene Listen.

Ich werde jetzt jedenfalls mal mit jeweils eigenem Struct für Spieler und Clan versuchen, die Sortierung umzusetzen. Mal sehen, ob das alles so klappt wie vorgestellt.

Liebe Grüße
WurzelAusZwei

Hier noch mal etwas, falls euer Script nicht ganz komplett ist:
http://www.stud.uni-karlsruhe.de/~uzbdq/tut/7.Tut.pdf

Ein wenig zur Motivation: Genutzt wird sowas bei Suchwegoptimierungen ->
Beispiel: Routenplaner

Scheint ein beliebtes Thema an den Hochschulen zu sein

MfG f.-th.

WurzelAusZwei

Hallo f.-th.,

danke für den Link! Der klärt die restlichen Unklarheiten.