Datensätze mit Hilfe von Listen speichern

[Eddy131]

Hallo Comunity,

ich kaue seit zwei Wochen an einem Problem.
Ich möchte, wie der Titel schon sagt, das Speichern von Studentendatensätze mit Hilfe von Listen bewerkstelligen.
Als Array krieg ich das ohne Probleme hin. Ich habe auch Anleitungen befolgt (sogar 1:1 kopiert) und trotzdem will er nicht.
Ich hab's zich mal durchgedacht und verschiedenes probiert, aber ganz ehrlich: Ich habe keine Ahnung warum es nicht funktioniert.

Hier einmal mein aktueller Quellcode mit erstem case:

------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <iomanip>
#include <conio.h>

using namespace std;

struct tListe
{
	int matrNr;
	string vName;
	string fName;
	tListe *pNext;
};

void ausgabe (tListe *pRoot);

void main (void)
{
	tListe *pRoot = 0, *hp;

	hp = new tListe;

	while (true)
	{
		cout << "Was wollen Sie tun?\n\n";
		cout << "Einfuegen von neuen Datensaetzen      [E/e]\n";
		cout << "Sortieren nach Matrikelnummer         [R/r]\n";
		cout << "Suchen nach bestimmten Datensatz      [S/s]\n";
		cout << "Ausgabe der Datensaetze               [A/a]\n";
		cout << "Programm beenden                      [B/b]\n\n";

		switch (tolower(_getch()))
		{
			case 'e':
				system ("cls");
				cout << "Bitte geben Sie die entsprechenden Daten ein:\n\n";

				cout << "\t\tMatrikelnummer:\n\t\t";
				cin >> hp ->matrNr;
				cout << "\t\tFamilienname:\n\t\t"; 
				cin >> hp ->fName;
				cout << "\t\tVorname:\n\t\t";
				cin >> hp ->vName;

				hp ->pNext = NULL;

				if (pRoot == 0)
				{
					pRoot = hp;
				}
				else
				{
					hp ->pNext = pRoot;
					pRoot = hp;
				}
				hp = hp ->pNext;

				break;

------------------------------------------------------------------------------

den Rest krieg ich hin, wenn das Speichern der Listen selber funktioniert.
An sich funktioniert das Programm so, aber sobald ich einen zweiten Datensatz eingeben möchte kommt eine Fehlermeldung (also an dem Punkt, wo die Daten für den neuen Satz in hp überschrieben werden.)

Ich hatte das ganze auch mit speichern am Ende ausprobiert. Da sah das (aus dem Kopf jetzt) so ähnlich aus:

if (pRoot == 0)
{
pRoot = pLast = hp;
}

Und da wurde bei jedem durchlauf alles was ich in hp geschrieben hab auch in pRoot und pLast gespeichert - aber erst ab dem zweiten durchlauf.

Kann mir da bitte jemand helfen?
Es soll nur ein ganz einfaches Programm sein, ohne viel schnickschnack, damit ich verstehe, was ich falsch mache und wie es funktioniert.

Wär echt super!

MfG
Eddy131

/edit pumuckl: cpp-Tags spendiert. Demnächst bitte selber machen!

[pyhax]

Schon wieder etwas mit einer "Matrikelnummer" ... Das gab es doch erst

[eddy131]

Das ist nur als Beispiel^^

Hab mir einfach irgendwelche Daten genommen. Können auch Hunderassen mit wahrscheinlichkeit eines Flohbefalls sein^^

Ich dachte halt nur für das sortieren wär ne Zahl gut, die sich nicht wiederholen kann. War halt das Erste das mit durch den Kopf ging.

Aber wenn dort das gleiche Problem mit einer Lösung ist, würd ich mich über einen Link freuen

[Psycho]

wo hollst du dir den speicher für den 2ten eintrag ?

[pyhax]

Was bekommst du den für eine Fehlermeldung

[Eddy131]

@Psycho: Das mach ich doch mit dem hp = hp ->pNext ? Oder?

@pyhax: Die hier (Ich benutze Visual Studio 2010):

Unbehandelte Ausnahme bei 0x517d2258 (msvcp100d.dll) in Datensätze verwalten mit Listen.exe: 0xC0000005: Zugriffsverletzung beim Schreiben an Position 0x00000000.

[pyhax]

Nein. Guck mal was da passiert (mit dem Zeiger hp):

[START DES PROGRAMMS] -> hp zeigt auf eine neue Liste (hp = new tListe)
[1. EINGABE EINES DATENSATZES]
    1. Die Liste wird befüllt.
    2. hp->pNext wird auf Null gesetzt
    3. hp wird auf hp->pNext gesetzt, also hp=NULL
[hp=NULL]
[2. EINGABE EINES DATENSATZES]
    1. Es wird versucht, etwas nach hp->matrNr zu schreiben,
       was dazu führt, das versucht wird einen Nullpointer zu 
       dereferenzieren (hp ist ja NULL)
[CRASH]

[Eddy131]

OK...

Aber pRoot wird doch auch mit 0 (oder NULL) initialisiert. Wieso klappt es da (Wird ja sogar gefordert)?

Und wie kann ich das sonst machen?

Wie gesagt, probier ich schon die ganze Zeit hin und her und ich bekomm die Liste nicht dazu sich hintereinander su speichern, also wie es soll, das ein Listenelement auf das nächste zeigt.

[pyhax]

pRoot wird ja wenn es Null ist auf hp gesetzt (in dem if). Zeiger zeigen nur auf Speicherbereiche, und wenn du nur einmal new verwendest, hast du auch nur einen Speicherbereich auf den du zeigen kannst. Wobei ich außerdem in deinem Code kein delete entdecke (-> der Speicher wird nicht wieder freigegeben. )

Und willst du wirklich std::list nachprogrammieren? (wobei std::vector meist std::list vorzuziehen ist.)

[Psycho]

nach dem ersten eintrag wird dein pRoot auf den "aktuellen" hp gestetzt und dein hp->next auf 0.
dann holst dir mit new ein neues listenelement und gibst deine daten ein. das hängst du dann an pRoot->next dran usw. auf jeden fall brauchst du pro eingegebenem datensatz ein new, und am ende auch pro new ein delete.

[Eddy131]

Ok, das mit delete hab ich vergessen.

In der Uni haben wir aber immer nur einmal new genutzt. Wie hat der Prof das dann angestellt? oder soll das mit new und delete in die while-Schleife rein?
Wir haben Listen aber auch nur am Rande gestriffen.

@pyhax: Ehrlich gesagt versteh ich das mit std::list und std::vector nicht so ganz.. Ist das wichtig?

Könntet ihr mir vielleicht die Grundstrucktur eines lauffähigen Quellcodes aufschreiben? Wenn ich mich daran entlang hangle versteh ich das meistens am besten.

[pyhax]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

struct Person {
    int matrikelnr;
    std::string vName;
    std::string nName;

    Person(std::string vName, std::string nName, int matrikelnr): matrikelnr(matrikelnr), vName(vName), nName(nName) {}
    Person(): matrikelnr(0) {}
};

std::istream& operator>>(std::istream & in, Person &p) {
    std::cout << "Vorname: ";
    in >> p.vName;
    std::cout << "Nachname: ";
    in >> p.nName;
    std::cout << "Matrikelnummer: ";
	return in >> p.matrikelnr;
}

std::ostream& operator<<(std::ostream & out, const Person &p) {
    out << "Vorname: " << p.vName << "\n";
    out << "Nachname: " << p.nName << "\n";
    return out << "Matrikelnummer: " << p.matrikelnr << "\n";
}

bool matrikelOrder(const Person &p1, const Person &p2) { return p1.matrikelnr < p2.matrikelnr; }

class NachnameComparer {
    private:
        std::string nachname;
    public:
       NachnameComparer(std::string name): nachname(name) {}
       bool operator()(const Person &p) { return p.nName == nachname; } 
};

int main() {
    std::vector<Person> daten;
    bool run = true;
    while (run)
    {
        std::cout << "Was wollen Sie tun?\n\n";
        std::cout << "Einfuegen von neuen Datensaetzen      [E/e]\n";
        std::cout << "Sortieren nach Matrikelnummer         [R/r]\n";
        std::cout << "Suchen nach bestimmten Datensatz      [S/s]\n";
        std::cout << "Ausgabe der Datensaetze               [A/a]\n";
        std::cout << "Programm beenden                      [B/b]\n\n";
		std::cout << "Wahl: ";

        switch (tolower(std::cin.get()))
        {
            case 'e': {
                std::cout << "Bitte gebe die Daten der Person ein.\n";
                Person p;
                std::cin >> p;
                daten.push_back(p);
                break;
            }
            case 'r':
                std::sort(daten.begin(), daten.end(), matrikelOrder);
				break;
            case 's': {
                std::string nachname;
				std::cout << "Bitte gebe den Nachnamen der Person ein, nach der gesucht werden soll: ";
                std::cin >> nachname;
                std::vector<Person>::iterator pos = std::find_if(daten.begin(), daten.end(), NachnameComparer(nachname) );
                if(pos == daten.end() ) 
                    std::cout << "Die Person wurde nicht gefunden.\n";
                else {
                    std::cout << "Daten der Person: \n";
                    std::cout << (*pos);
                }
                break;
            }
            case 'a':
				std::cout << "Datensätze: " << std::endl;
		    	for(std::vector<Person>::iterator pos = daten.begin(); pos != daten.end(); ++pos) {
		    		std::cout << (*pos) << "\n";
		    	}
		        break;
            case 'b':
               run = false;
        }

		std::cin.get();
    }
}

So mein ich das mit std::vector. Oder sollt ihr die ganzen Algorithmen wie Suchen, Einfügen, ... selber implementieren?

[Eddy131]

Hammer, danke, klappt wunderbar!
Auf jedenfall besser als bei mir.

Aber ich versteh so gut wie nichts davon XD
Ich will es ja verstehen und nicht einfach nur haben.
Nebenbei: Hab erst ein Semester Informatik hinter mir.

Die Aufgabe soll auch definitiv mit Listen gelöst werden.
Bei dir sieht das in der struct irgendwie anders aus.. ich vermiss den *pNext zeiger. ISt das eine andere Art der Listen?

Ach, und ja, wir sollen alle Funktionen selber implementieren
Bzw. die Aufgabe die mir gestellt wurde hieß "Datenverwaltung mit Hilfe von Listen".
Die komplexität hab ich mir selber ausgesucht.
Aber ich bezweifle doch eher stark, das mir irgendwer glaubt ich hätt das Programm von dir oder ein ähnliches selber geschrieben.

Würd es dir was ausmachen, das Programm nochmal für meinen Wissenstand kompatibel zu schreiben?
Nur die Listenverwaltung an sich.
Suchen, Ausgabe und beenden klappt bei mir dann schon

Aber echt danke für die Mühe!

[pyhax]

Die Liste ist das:

std::vector<Person> daten;

Ich kann ja mal probieren ob ich auch eine Version ohne std::vector hinbekomme

[pyhax]

Bitte:

#include <iostream>
#include <string>

struct tNode {
	tNode *next;
    std::string vName;
    std::string nName;
	int index;
};

tNode * createNode (tNode * list) {
	tNode *node = new tNode;
	node->next = list;
	return node;
}

tNode * deleteList (tNode * node) {
	if(node->next) deleteList(node->next);
	delete node;
}

tNode * removeElement (tNode * list, tNode * element) {
	if(list == element) return list->next;
	else {
		tNode * cur = list;
		tNode * pre = list;
		while( (cur = cur->next) ) {
			if(cur == element) {
				pre->next = cur->next;
			}
			pre = pre->next;
		}
	}
	return list;
}

tNode * findMin (tNode * list) {
    if(!list || !list->next) return list;
	tNode * next = findMin(list->next);
	return (next->index > list->index) ? (list) : (next);
}

tNode * sort (tNode * list) {
    if(!list) return NULL;
	tNode * first = findMin(list);
	first->next = sort(removeElement(list, first) );
	return first;
}

tNode * findNachname (tNode * list, std::string nachname) {
	if(!list) return NULL;
	else if (list->nName == nachname) return list;
	else return findNachname(list->next, nachname);
}

void printNode (tNode * node) {
	if(!node) return;
	std::cout << "Vorname: " << node->vName << "\n";
	std::cout << "Nachname: " << node->nName << "\n";
	std::cout << "Matrikelnummer: " << node->index << "\n";
}

void printList (tNode * list) {
	printNode(list);
	std::cout << "-------------------------------------\n";
	if(list) printList(list->next);
}

int main() {
	tNode *list = NULL;
	bool run = true;
	while(run)
	{
		std::cout << "Was wollen Sie tun?\n\n";
        std::cout << "Einfuegen von neuen Datensaetzen      [E/e]\n";
        std::cout << "Sortieren nach Matrikelnummer         [R/r]\n";
        std::cout << "Suchen nach bestimmten Datensatz      [S/s]\n";
        std::cout << "Ausgabe der Datensaetze               [A/a]\n";
        std::cout << "Programm beenden                      [B/b]\n\n";
		std::cout << "Wahl: ";

        switch (tolower(std::cin.get()))
        {
            case 'e': {
                std::cout << "Bitte gebe die Daten der Person ein.\n";
                list = createNode(list);
				std::cout << "Vorname: ";
				std::cin >> list->vName;
				std::cout << "Nachname: ";
				std::cin >> list->nName;
				std::cout << "Matrikelnummer: ";
				std::cin >> list->index;
                break;
            }
            case 'r':
                list = sort(list);
				break;
            case 's': {
                std::string nachname;
				std::cout << "Bitte gebe den Nachnamen der Person ein, nach der gesucht werden soll: ";
                std::cin >> nachname;
				tNode * element = findNachname(list, nachname);
				if(element) {
					std::cout << "Daten der Person: \n";
					printNode(element);
				} else {
					std::cout << "Keine Person mit Nachname " << nachname << " gefunden. \n";
				}
                break;
            }
            case 'a':
				std::cout << "Datensätze: \n";
				printList(list);
				break;
            case 'b':
			   deleteList(list);
               run = false;
        }

		while(std::cin.get() != '\n');
	}
}

Ist eigentlich bis auf das std::cout / std::cin C.

[Eddy131]

Danke!

Damit kann ich was anfangen.
Ich arbeite mich da mal durch, bis ich es verstanden hab.

Danke nochmal.

[Eddy131]

Hab's jetzt bei Visual Studio reinkopiert und erstmal ggetestet.

Kommt gleich ne Fehlermeldung..

(26): error C4716: 'deleteList': Muss einen Wert zurückgeben

Hab's mit return 0 und return node versucht. Wie du dir denken kannst hat das nicht geklappt... :p

Meinst du mit "ist eigentlich bis auf das std::cout / std::cin C.", das ein c++ Programm das nicht interpretieren kann?
Du schreibst die funktionen alle über die main-Funktion.
Ich hab das so gelernt, das die oben vorgestellt werden müssen und dann unten die Funktionen selber sind. also in der Form etwa:

-----------------------------------------------------
Ausgabe(int abc, string wort);
Eingabe(char hallo, int abc, int hallo);

void main (void)
{
//...
}

Ausgabe(int abc, string wort)
{
//...
}

Eingabe(char hallo, int abc, int hallo)
{
//...
}

-----------------------------------------------------

Ist deine Variante C Typisch oder geht das auch bei C++?
Also könnt ich auch die Funktionen nach unten packen, oben vorstellen und es würde auch laufen?

Und warum schreibst du die while-Schleife so:

---------------------
bool run = true;
while(run)
---------------------

?
Hat das einen Vorteil gegenüber

-----------------
while(true)
-----------------

?

Nebenbei: Ist "using namespace std;" nicht einfacher und weniger Schreibkramm als immer st:: davor zu schreiben?

Ich hoffe meine Fragen ermüden dich nicht irgendwann
Ich will's halt wirklich wissen, weil's Spaß macht, und hier im Forum bekomme ich immer gute Antworten

[Werner Salomon]

Eddy131 schrieb:

Hab's jetzt bei Visual Studio reinkopiert und erstmal ggetestet.

Kommt gleich ne Fehlermeldung..

(26): error C4716: 'deleteList': Muss einen Wert zurückgeben

Hallo Eddy131

statt

tNode * deleteList (tNode * node) {

darf es ruhig

void deleteList (tNode * node) {

heißen

Eddy131 schrieb:

Meinst du mit "ist eigentlich bis auf das std::cout / std::cin C.", das ein c++ Programm das nicht interpretieren kann?
Du schreibst die funktionen alle über die main-Funktion. ..

Nein - mit dem Voranstellen der Funktionsprototypen hat das nichts zu tun. Was pyhax wahrscheinlich meint, ist die Tatsache, dass er hier sowohl auf Container des C++-Standard als auch auf die Möglichkeiten der OOP komplett verzichtet hat.
Beides wird extrem wichtig, sobald Du Programme schreibst, die länger als 2 Seiten Sourcecode werden.

In vielen Kursen und Seminaren wird die Implementierung einer einfach verketten Liste geübt. Ich unterstelle mal, dass es es auch bei Dir so ist. Was dabei meistens leider versäumt wird, ist die Möglichkeit, die Liste als Objekt darzustellen. Es scheint wirklich Dozenten zu geben, die 20-30 Jahre hinter der Entwicklung in der Softwaretechnologie hinter her sind.
Wenn Du jemals als Informatiker erfolgreich sein willst, solltest Du Dich genau damit auseinander setzen. Das ist viel wichtiger als das Gefummele mit den Zeiger.

Versuche die Liste als ein Objekt zu begreifen, dem man Elemente (tListe) hinzufügen kann, von dem man Elemente entfernen kann, auf das Algorithmen wie 'Sortieren' angewendet werden können oder in dem man nach bestimmten Elementen suchen kann. In der Applikation - also da, wo Du die einzelnen Elemente einliest, hat die Listenverwaltung - und damit auch das new - nichts zu suchen.
Das könnte etwa so aussehen:

#include <iostream>
#include <string>
#include <iomanip>
#include <conio.h>

struct tListe
{
    int matrNr;
    std::string vName;
    std::string fName;
    tListe *pNext;
};
std::ostream& operator<<( std::ostream& out, const tListe& data )
{
    return out << data.vName << " " << data.fName << " Matr.#" << data.matrNr;
}

struct Liste
{
    Liste() : pRoot(0) {}
    ~Liste() { clear(); }

    void clear()
    {
        for( tListe* p = pRoot; p; )
        {
            tListe* tmp = p;
            p = p->pNext;
            delete tmp;
        }
    }

    // -- füge am Anfang der Liste ein Element ein
    void push_front( const tListe& data )
    {
        tListe* p = new tListe( data );
        p->pNext = pRoot;
        pRoot = p;
    }

    // -- gebe alle Elemente auf 'out' aus
    void ausgabe( std::ostream& out )
    {
        for( tListe* p = pRoot; p; p = p->pNext )
            out << *p << "\n";
    }

private:
    Liste( const Liste& );
    Liste& operator=( const Liste& );

    tListe* pRoot;
};

int main ()
{
    using namespace std;
    Liste liste;
    while (true)
    {
        tListe hp;
        cout << "Was wollen Sie tun?\n\n";
        cout << "Einfuegen von neuen Datensaetzen [E/e]\n";
        cout << "Sortieren nach Matrikelnummer [R/r]\n";
        cout << "Suchen nach bestimmten Datensatz [S/s]\n";
        cout << "Ausgabe der Datensaetze [A/a]\n";
        cout << "Programm beenden [B/b]\n\n";

        switch (tolower(_getch()))
        {
        case 'e':
            system ("cls");
            cout << "Bitte geben Sie die entsprechenden Daten ein:\n\n";

            cout << "\t\tMatrikelnummer:\n\t\t";
            cin >> hp.matrNr;
            cout << "\t\tFamilienname:\n\t\t";
            cin >> hp.fName;
            cout << "\t\tVorname:\n\t\t";
            cin >> hp.vName;

            liste.pop_front( hp );
            break;

        case 'a':
            liste.ausgabe( cout );
            break;
        case 'b':
            return 0;
        }
    }
    return 0;
}

Mit das wichtigste an einem Objekt sind Konstruktor und Destruktor, soweit dieser notwendig ist. Im Konstruktor (Zeile 20) wird pRoot mit 0 initialisiert, Du hast also keine Chance diese Liste zu verwenden, ohne dessen Zeiger zu initialisieren. er hat immer einen gültigen Wert. Im Destruktor (Zeile 21) wird die Liste wieder abgeräumt - mit der Methode clear(). Auch hier kannst Du als Anwender nichts verkehrt machen, es können keine Memoryleaks erzeugt werden.
Kopieren und Zuweisen habe ich stillgelegt (Zeile 49,50) .. machen wir vielleicht später.
Und in der Applikation - hier die Funktion main - findest Du kein new und keinen Zeiger mehr.

Das ist zwar noch nicht der Weisheit letzter Schluss, aber ein Riesenschritt in die richtige Richtung.

Eddy131 schrieb:

Nebenbei: Ist "using namespace std;" nicht einfacher und weniger Schreibkramm als immer st:: davor zu schreiben?

Man sollte überall dort, wo Typen definiert werden (z.B. tListe) das std:: davor schreiben. Der Grund dafür liegt einfach darin, dass die Typdefinitionen sehr schnell in einem H-File landen und dort solltest Du auf keinen Fall ein 'using namespace std' stehen haben.
Warum das so ist ... ok, schreib erst mal größere Programme. Letztlich hebelst Du den namespace-Mechanimus damit aus. Wenn das schief geht, wird's wirklich unangenehm.

Eddy131 schrieb:

Ich hoffe meine Fragen ermüden dich nicht irgendwann
Ich will's halt wirklich wissen, weil's Spaß macht, und hier im Forum bekomme ich immer gute Antworten

registriere Dich doch - kritisch wird es erst, wenn Du gar keine Antworten mehr bekommst

Gruß
Werner

@Edit: pop_front nach push_front geändert

[Michael E.]

Werner: pop_front ist für das Einfügen kein toller Name

[Werner Salomon]

Michael E. schrieb:

Werner: pop_front ist für das Einfügen kein toller Name

- Du hast Recht - ich ändere das