3. doppelt verkettete Liste

doppelt verkettete Liste

  • N

    Hallo,

    habe folgende Aufgabe bekommen:

    Gegeben sei eine Liste mit Adressangaben (Index(int), PLZ(5 char), Ort(20 char), Straße(20 char), Hausnr(5 char)), die bereits nach "index" (<0!) sortiert in einer Datei vorliegt. Erstellen Sie ein C++-Programm zum einlesen und Bearbeiten der Liste im Arbeitsspeicher (Verwendung von dynamischem Speicher!).

    Verwenden Sie eine Klasse DVL_Elem, für die Elemente einer doppelt verketteten Liste (DVL). Diese Klasse enthalte die für die Realisierung einer DVL erforderlichen Zeiger. Hiervon abgeleitet wird die Klasse Data_Elem, die die entsprechenden Variablen für die Adressen bereitstellt.

    Zur Realisierung der DVL geben Sie weiterhin deine Klasse DVL an, die die zur Verwltung erforderlichen Methoden einfuege(...), entferne(...), DVL_Elem* first_V(...), DVL_Elem* first_R(...), DVL_Elem* last_V(...), DVL_Elem* last_R(...), DVL_Elem *at(int x_index) und anzeige_Liste(...) enthält. Weiterhin sind hier auch die erforderlichen Anker für die vorwärts- (..._V) und rückwärts-Verkettung (..._R) vorzusehen.

    Bei der Methode ... einfuege(...) gibt der Rückgabewert an, welcher der Index des folgenden Elemtes ist (-1 für = letztes Element). Der Index soll eindeutig bleiben, d.h. bei einem einzufügenden Element, bei dem der Index bereits existiert, wird der um eins erhöhte Index eingesetzt, Die bereits existierenden Listenelemente werden entsprechend angepasst.

    Bei der Methode ...entferne(int x_index) wird das zu dem Index x_index gehörende Element aus der Liste entfernt und bei den verbleibenden Elementen die Komponente "Index" angepasst!

    Erstellen Sie in einem Hauptprogramm ein geeignetes Menu (Einlesen der Liste, Einfuegen neues Element, Loeschen, Anzeige_Element, Ausgaben_Liste, Beenden) für die Bearbeitung der Liste!

    Mein aktuelles Programm schaut mittlerweile so aus:

    DVL_Elem.h

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

using namespace std;

#ifndef DVL_ELEM_H_INCLUDED
#define DVL_ELEM_H_INCLUDED

class DVL_Elem {
	private:
	public:
		DVL_Elem();
		~DVL_Elem();
		int value;
		DVL_Elem *next;
		DVL_Elem *prev;
};

#endif

    DVL_Elem.cpp

    #include "DVL_Elem.h"

DVL_Elem::DVL_Elem(){}
DVL_Elem::~DVL_Elem(){}

    Data_Elem.h

    #include "DVL_Elem.h"

class Data_Elem : public DVL_Elem {
	private:
		int index;
		string plz;
		string ort;
		string strasse;
		string hausnr;

	public:
		Data_Elem();
		~Data_Elem();

		Data_Elem(int iIndex, const string& iPlz, const string& iOrt , const string& iStr, const string& iNr);

		ostream & ostreamAusgabe(ostream &os);
};

ostream & operator << (ostream &os, Data_Elem &data);

    Data_Elem.cpp

    #include "Data_Elem.h"

Data_Elem::Data_Elem() {}

Data_Elem::~Data_Elem() {}

Data_Elem::Data_Elem(int iIndex, const string& iPlz, const string& iOrt , const string& iStr, const string& iNr)
: index(iIndex), plz(iPlz), ort(iOrt), strasse(iStr), hausnr(iNr) {}

ostream & operator << (ostream &os, Data_Elem &data) {
	data.ostreamAusgabe(os);
	return os;
}

ostream & Data_Elem::ostreamAusgabe(ostream &os) {
	os << index << " " << plz << " " << ort << " " << strasse << " " << hausnr << endl;
	return os;		
}

    DVL.h

    #include "DVL_Elem.h"

class DVL  {
	private:
	public:
		DVL();
		~DVL();

		DVL_Elem *first_V();
		DVL_Elem *first_R();
		DVL_Elem *last_V();
		DVL_Elem *last_R();
		DVL_Elem *at(int x_index);
		DVL_Elem *front_V();
		DVL_Elem *back_R();
		anzeige_Liste();
		entferne();

		int einfuege(int iIndex, const string& iPlz, const string& iOrt , const string& iStr, const string& iNr);
};

    DVL.cpp

    #include "DVL.h"
#include "Data_Elem.h"

DVL::DVL(){
	firstDVL_Elem = NULL;
	lastDVL_Elem = NULL;
}

DVL::~DVL(){}

int DVL::einfuege(int i, const string& p, const string& o , const string& s, const string& h) {
	Data_Elem temp(i, p, o, s, h), temp2;
	return 0;
}

    Adressen.cpp

    #include "DVL.h"
#include "Data_Elem.h"

const size_t N = 5;
enum {ind = 0, plz = 1, ort = 2, str = 3, hsnr = 4};

int menu();

int main() {
	string dateiname = "liste.dat"; //Dateiname
	ifstream input; 
	vector<string> vec;
	string tmp;	
	int action = 0;					//Wahl des Benutzers

	while(action != 'B') {
		action = menu();
		switch(action) {
			case 'L':
				//datei öffnen
				input.open(dateiname.c_str(), ios_base::in);

				//prüfe ob die datei geöffnet werden konnte
				if(!input){
					cout << "Fehler beim Oeffnen der Datei!" << endl;
					break;
				}

				// Kopiere aus dem Stream input in den Vektor vec Benutze ';' als Trenner
				while (getline(input,tmp,';')) {
					string::iterator it = find(tmp.begin(), tmp.end(), '\n');
					if(it != tmp.end()) {
						string tmp2;
						copy(tmp.begin(), it, back_inserter(tmp2));
						vec.push_back(tmp2);
						tmp2 = "";
						copy(++it, tmp.end(), back_inserter(tmp2));
						vec.push_back(tmp2);
					}
					else {
						vec.push_back(tmp);
					}
				}

				for (size_t i = 0; i <= vec.size() - N; i += N) {
					 DVL tmp;
					 tmp.einfuege((i/N)+1, vec[i+plz], vec[i+ort], vec[i+str], vec[i+hsnr]);
				}
				break;

			case 'E':
				break;
			case 'D':
				break;
			case 'A':
				break;
			case 'P':
				//Ausgabe der eingelesenen Liste
				break;
			case 'B':
				break;
		}
	}

	//datei schließen
	input.close();

	return 0;
}

int menu() {
	char choice;
	char c;

	static char menuStr[] =
		"\n\n	------------MENU-----------"
		"\n\n	L = einlesen der Liste"
		"\n\n	E = einfuegen neues Element"
		"\n\n	D = loeschen"
		"\n\n	A = Anzeige Element"
		"\n\n	P = Ausgaben Liste"
		"\n\n	B = Beenden"
		"\n\n	Auswahl: ";

	cout << menuStr;

	do {
		if(!cin.get(choice)){
			choice = 'B';
		}
		else {
			choice = toupper(choice);
		}
	}while(choice != 'L' && choice != 'E' && choice != 'D' && choice != 'A' && choice != 'P' && choice != 'B');

	// verwirft restliche Zeichen im Eingabepuffer incl. '\n'
	while(cin.get(c) && c != '\n');

	return choice;
}

    liste.dat

    1;49899;Huegelstadt;Dorfstrasse;5
2;38998;Taldorf;Wasserweg;9
3;14899;Bergheim;Altestrasse;129
4;86347;Seehain;Tiefenhofpfad;43
5;64732;Landstadt;Mittenweg;85

    Bin jetzt bei der einfuege-Funktion gestrandet und weiß nicht mehr weiter, wäre nett wenn mir jemand helfen könnte?

    Danke und Gruß, nihilfire

    0
  • C

    Im Prinzip geht das Einfügen ganz einfach:
    Als erstes hangelst du dich durch die Liste zu der Position durch, hinter der du das Element einfügen willst. Dann erstellst du dir einen neuen Listenknoten, füllst ihn mit Inhalten und setzt seine Nachbar-Zeiger (next und prev) auf pos->next bzw. pos. Zuletzt mußt du nur noch pos->next->prev und pos-next auf das neue Element umbiegen und schon ist das Element am Ziel.

    0
  • N

    Hi,
    dann müssste ich ja erstmal feststellen wieviele Elemente es überhaupt schon gibt, d.h ich brauche noch eine Variable die, die Anzahl der Elemente speichert oder?

    einfuege()

    int DVL::einfuege(int i, const string& p, const string& o , const string& s, const string& h) {
    Data_Elem temp(i, p, o, s, h);
    while (temp->prev != NULL) {
       temp = temp->prev;
    }
    Data_Elem *temp2;
    temp2 = new Data_Elem;
    temp2->prev = NULL;
    temp2->next = temp;
    temp->prev = temp2;
 }

    return 0;
}

    so sieht die einfuege-Funktion jetzt aus, aber es klappt nocht so wie ich dachte.

    Gruß, nihilfire

    0
Anmelden zum Antworten