Skiplist in C++ programmieren

Romsl · 26. November 2004

Hi,

ich brauch eine Skiplist aus int Werten. Das Problem hierbei ist nur, dass ich nicht genau weiß wie ich das realisieren soll. Kenn mich in Java ausreichend aus. In C++ nur spärlich.

Das Problem hier ist, wie verlinke ich die einzelnen Zellen einer Zahl und mit der Zelle der nächsten Zahl?

Gruß

Romsl

RedWing · 26. November 2004

Hallo,
in C++ verwendet man zum Implementieren von Listen sogenannte Pointer...
Eine Skipliste selber hab ich noch nicht implementiert aber der folgende
Code sollte dir zeigen wie man eine Liste in C aufbauen kann.
Du müsstest es dann halt für deine Skiplist erweitern, mit
zufääligen Knotenniveuos etc...

Code:

#include <iostream>

using namespace std;

class simplelist{   

        int element;
        simplelist *next;

        public: 
        simplelist(int n):element(n), next(NULL){}

        ~simplelist(){

                if(next != NULL)
                        delete next;
        }

        void insert(int n){
                
                if(next != NULL)
                        next->insert(n);                
                else{
                        next = new simplelist(n); 
                }
        }

        void print(){
                cout << element << endl;
                if(next != NULL)
                        next->print();
        }
};

int main(){

        simplelist *list = new simplelist(5); 
        list->insert(3);
        list->insert(1);
        list->print();
        delete list;
}

Ich hoffe das hilft dir a weng weiter bzw zeigt dir zumindest die Verkettung der
einzelnen Elemente einer Liste...
Falls du das mit der Skiplist mal in Angriff nehmen solltest würde mich
deine Implementierung intressieren...

Gruß

RedWing

//edit in C++ gibt es destruktoren; und zum Löschen eines Pointers verwendet
man den Operator delete der implizit den Destruktor (~simplelist()) eines Objektes aufruft=>
Eine Methode removeAll entfällt bei dem obigen Beispiel

MPNuts · 29. November 2004

Hi,

ich habe da so ziemlich das selbe Problem, aber nur in C. Das heißt, ich sollte keine Klassen verwenden. Ich hab das ganze mit Strukts aus dem Skript meines Profs rausgelesen, aber ich verstehe ein paar Dinge dabei noch nicht so ganz!
Hier jetzt erstmal die Strukts:

Code:

struct Daten{
 char  * zweck; //Soll ein String unbekannter Größe aufnehmen
 double betrag;
 int index;
 char * datum; //Soll das Datum aufnehmen
};
struct Liste{
 struct Daten *pDaten;
 struct Liste *next;
};
struct ListHead
{
struct Liste *head;
struct Liste *tail;
};

Was ich nicht so richtig verstehe, ist die Verbindung zwischen "struct Liste" und " struct ListHead".
Warum kommt mein "struct Liste" in "struct ListHead" zweimal vor? Erstelle ich ein neues Element von "struct Daten" jetzt in "struct Liste, mit *next. Dann gebe ich das in eine Funktion und schreib das neue Struct auf welchen Pointer von "struct ListHead". Was mache ich mit dem Anderen?
Meine größste Frage, wenn ich jetzt mehrere Listenelemente erstellt habe, wie komme ich an sie ran!

Wäre nett, wenn mir das jemand mal etwas durchleuchten könnte, oder eine besser verständliche Quelle angeben könnte.

RedWing · 29. November 2004

Was ich nicht so richtig verstehe, ist die Verbindung zwischen "struct Liste" und " struct ListHead". Warum kommt mein "struct Liste" in "struct ListHead" zweimal vor?

Deine struct Liste ist einfach deine Liste mit einem Zeiger auf das nächste Element der Liste,
und einen Zeiger auf die Daten....
Ein passendere Name für "struct Liste" wäre vielleicht "struct Node"
Und deine struct ListHead beinhaltet einfach nur ein Zeiger auf den Anfang und das Ende der
Liste. Wobei der Zeiger auf das Ende nur Sinn bei doppelt verketteteten Listen macht um die
Elemente bei einem Durchsucehn der Liste schneller finden zu können...

Meine größste Frage, wenn ich jetzt mehrere Listenelemente erstellt habe, wie komme ich an sie ran!

Ein durchlaufen der von dir erstellten Liste könnte so aussehen:

Code:

void print(ListHead *first){

        if(first != NULL){   
                Liste *tmp = first->next;

                while(tmp){          
                         Daten *dummy = tmp->pDaten;
                        cout << dummy->zweck << " " << dummy->betrag << " " << dummy->index << " " << dummy->datum << endl;
                        tmp = tmp->next;     
                }
        }
}

Der Code sollte dir zeigen wie man die Liste von vorn nach hinten durchlaufen könnte.

Erstelle ich ein neues Element von "struct Daten" jetzt in "struct Liste, mit *next. Dann gebe ich das in eine Funktion und schreib das neue Struct auf welchen Pointer von "struct ListHead". Was mache ich mit dem Anderen?

Das habe ich jetzt nicht so richtig verstanden...
Es gibt zwei Möglichkeiten was an die Liste anzuhängen:
Am Anfang, oder am Ende der Liste.

Bsp. Am Ende der Liste:
Du merkst dir den Anfang der Liste in einer temportären Variablen vom Typ List
, deswegen solltest du deiner Funktion (z.B. insert()) den ListHead mitgeben und mit Hilfe von
ListHead->head dir den Anfang der Liste merken. Dann durchläufst du mit Hilfe der temp. Variablen die Liste bis zum Schluss,bis tmp->next (tmp = temp Variable vom Ttyp List) ==
NULL ist...
Dann holst du dir Speicherplatz für ein neues "struct Liste".
und dann für Liste->pDaten Speicherplatz für "struct Daten" und beschreibst diesen
Speciherplatz mit deinen einzufuegenden Daten...
Und zum Schluss solltest du das neue Listenelement hinten anhängen, (sprich
tmp->next auf dein neues Listenelement zeigen lassen) und fertig ist das Geflecht...

Ich hoffe ich konnte ein wenig Licht ins dunkel bringen...

Gruß

RedWing

RedWing · 29. November 2004

RedWing hat gesagt.:
Wobei der Zeiger auf das Ende nur Sinn bei doppelt verketteteten Listen

Sorry das war ein Irrtum, in deinem Fall macht der Zeiger auf das Ende sehr wohl
was aus.
Du könntest dir nämlich zwei funktionen definieren,
ungefähr so:

Code:

void push_front(ListHead *list, Data* data);
void push_back(ListHead *list, Data* data);

push_front fügt vorne was an push_back hinten an die Liste...
In push_front kannst du dann list->head hernehmen um zum Anfang zu gelangen
und in push_back list->tail um am Ende was einzufügen...
Somit ersparst du dir das von mir beschriebene Durchlaufen der Liste
beim hinten anhängen und ein hinten und vorne anhängen geht
zusätzlich noch optimal schnell...

Sorry nochmal für den Irrtum...

Gruß

RedWIng

MPNuts · 30. November 2004

Danke, ich glaube ich habe es verstanden!

Ich werde jetzt mal etwas damit rumprobieren.

Nochmals vielen Dank für die Erläuterung, warum kann mein Prof das denn nicht so schreiben, das man es vieleicht auch mal versteht?

Daniel Toplak · 30. November 2004

Bitte benutzt doch mal die Forum Suche, denn da gibt es zig Beiträge über verkettete Listen, z.B.:
http://www.tutorials.de/tutorials15326.html&highlight=verkettete+liste

Gruß Homer

Mr.Undertaker · 1. Dezember 2004

Wenn du mit C++ programmierst, dann darfst du doch sicherlich die
STL (standard template library) verwenden, oder ?
Falls ja, dann such mal nach "vector" (einfach verkettete Liste) oder nach
"list" (doppelt verkettete Liste).
Das Zeugs selber machen ist zwar eine nette Pointer-Übung, aber man
muss ja nicht jedesmal das Rad neu erfinden.

Gruß

P.S.: Was genau ist denn eine Skipliste

RedWing · 1. Dezember 2004

Eine Skiplist basiert auf einer sortierten verketteten Liste.
Nur das bei einer Skiplist jedes Element k (k>= 1) Zeiger hat,
also aus einen Block von Zeigern besteht.
Dieses k wird probabilistisch bestimmt mit einer Wahrscheinlichkeit von 0.5
Es sei nun i € k; jeder i-te Zeiger eines Elements zeigt auf das nächste Element
der Liste welches auch einen i-ten Zeiger besitzt. => Weil k>= 1, zeigen die Zeiger
der Schicht i=1 immer auf das direkt nächste Element
Zusätzlich besitzt die Liste noch ein Anfangs und Endelement welche soviele
Zeiger besitzen wie der maximale Block der Liste...

Nutzen:
In einer einfach verketteten Liste ist der Aufwand der Suche nach einem
bestimmten Element im Mittel linear.
Eine Skiplist besitzt bei der Suche nach einem bestimmten Element die
gleiche Komplexitätsklasse wie ein ausgeglichener Suchbaum,
nämlich O(log

)

Siehe auch:
http://en.wikipedia.org/wiki/Skiplist

Gruß

RedWing

Romsl · 10. Dezember 2004

Meine Lösung zu diesem Problem

Hier ist meine Lösung zu diesem Problem.

Falls jemand mal wieder jemand eine Skiplist benötigt.

Code:

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

class SkiplistElement
{
	public:
		//value of the skiplist element
		int value;
		
		//vectors of the skiplist element
		vector<SkiplistElement*> next;
	
		/**
		 * standard constructor
		 */
		SkiplistElement()
		{
			value = -1;
		}
		
		/**
		 * constructor set value of list element
		 */
		SkiplistElement(int n)
		{
			value = n;
		}
		
		/**
		 * destructor
		 */
		~SkiplistElement()
		{
			//empty
		}
};

using namespace std;

/**
 *
 */
class Skiplist
{
	public:
		//head of the skiplist
		SkiplistElement *head;
		
		//tail of the skiplist
		SkiplistElement *tail;
		
		//count skiplist elements without head and tail
		int countElements;
		
		//needed to calculate the height of the skiplist element
		int probability;
		
		//height of the skiplist element
		int h;
	
		/**
		 * standard constructor
		 */
		Skiplist()
		{
			countElements = 0;
			head = new SkiplistElement();
			tail = new SkiplistElement();
			tail->next.push_back(NULL);
			head->next.push_back(tail);
		}
		
		/**
		 * Method to insert a skiplist element with value n.
		 */
		void insert(int n, int h_help)
		{
			countElements++;
			SkiplistElement *tmp = new SkiplistElement(n);
			
			if (h_help == 0)
			{
				probability = 1;
				h = 1;
			
				while (probability == 1)
				{
					probability = rand() % 2;
					
					if (probability == 1)
					{
						h++;
					}
				}
			}
			else
			{
				probability = 1;
				h = 1;
				h_help--;
				
				while (probability == 1 && h_help > 0)
				{
					probability = rand() % 2;
					
					if (probability == 1)
					{
						h++;
					}
					
					h_help--;
				}
			}
			
			//compound head vectors with tail vectors
			while (head->next.size() < h)
			{
				tail->next.push_back(NULL);
				head->next.push_back(tail);
			}
			
			//compound head with new element and new element with tail elements
			for (int i = 0; i < h; i++)
			{
				tmp->next.push_back(head->next[i]);
				head->next[i] = tmp;
			}
		}
		
		/**
		 * Search value in skiplist and count the compares of the value with element values.
		 * Returns 1 if the value exists in the skiplist, else 0;
		 */
		int find(int value, int *compares)
		{
			/*
			 * temporary elements
			 * tmp1 to jump back
			 * tmp2 next element
			 */
			SkiplistElement *tmp1 = head;
			SkiplistElement *tmp2;
			
			//max size for walking through the skiplist
			int max_size = head->next.size() - 1;
			
			//while the value isn't equal as the element value
			while (tmp1->value != value && max_size >= 0)
			{
				*compares = *compares + 1;
			
				if (tmp1->value < value)
				{
					if (tmp1->next[max_size] != NULL)
					{
						tmp2 = tmp1;
						tmp1 = tmp1->next[max_size];
					}
					else
					{
						max_size--;
					
						if (max_size >= 0)
						{
							tmp1 = tmp2->next[max_size];
						}
					}
				}
				else if (tmp1->value > value)
				{
					max_size--;
					
					if (max_size >= 0)
					{
						tmp1 = tmp2->next[max_size];
					}
				}
			}
			
			if (tmp1->value == value)
			{
				return 1;
			}
			else
			{
				return 0;
			}
		}
		
		/**
		 * destructor
		 */
		~Skiplist()
		{
			//empty
		}
};

MfG

Romsl

Skiplist in C++ programmieren

Romsl

Erfahrenes Mitglied

RedWing

Erfahrenes Mitglied

MPNuts

Mitglied

RedWing

Erfahrenes Mitglied

RedWing

Erfahrenes Mitglied

MPNuts

Mitglied

Daniel Toplak

Erfahrenes Mitglied

Mr.Undertaker

Erfahrenes Mitglied

RedWing

Erfahrenes Mitglied

Romsl

Erfahrenes Mitglied

Neue Beiträge