kétirányú láncolt lista

C/C++

Sziaszotok!
Segítséget szeretnék kérni, a beadndóhoz. Kétirányú fejelemes láncolt listát kéne implementálni beépített típusok nélkül. A gonodom, hogy a fejelem a konstruktor meghívása után nem adódik át?
Tud valaki tanácsot adni?
Köszi a segítséget! 


//main
/*
Készítsen egy sor típust! Alkalmazzon osztályt! A sorokat kétirányú fejelemes ciklikus láncolt 
listával ábrázolja! Implementálja a szokásos műveleteket, és egy összefűző műveletet is, ami
az első sorhoz sorban hozzáfűzi a második sor elemeit! (A második sor végül legyen üres!) 
Egészítse ki az osztályt a kényelmes és biztonságos használat érdekében megfelelő metódusokkal 
(sorbeolvasó operátor>>, sorkiíró operátor<<),  alkalmazzon kivételkezelést, és bontsa modulokra 
a programját!  A teszt környezet hívja meg azt a műveletet is, amely kiszámítja két sor összefűzését! 
Az összefűzés és a többi operáció műveletigénye is ?(1), kivéve a sorbeolvasó és sorkiíró operátorokat.
*/

#include <iostream>
#include <string>
#include "sequence.h"
#include "node.h"

using namespace std;

class Menu
{
public:
	void Run();
private:
	void MenuWrite();
	void Insert();
	void Write();
	void Union();

	Sequence sor;

};

int main()
{
	
	Menu m;
	m.Run();

	return 0;
}

void Menu::Run()
{
	int n = 0;
	do
	{
		MenuWrite();
		cin >> n;
		switch (n)
		{
			case(1): Insert(); break;
			case(2): Write(); break;
			case(3): Union(); break;
		}
	}
	while (n!=0);
}

void Menu::MenuWrite()
{
	cout << "1 - Sor feltoltese " << endl;
	cout << "2 - Sor kiirasa " << endl;
	cout << "3 - Masodik sor hozzafuzese az elsohoz " << endl;
	cout << "0 - Kilepes " << endl;
}

void Menu::Insert()
{
	int i;
	string str;
	cout << "Kerem a lista elemeit: ";
	cin >> str;
	//Node();
	while (!((i=atoi(str.c_str()))==0 && str!="0"))
	{
		sor.Insert(i);
		cin >> str;
	}
}

void Menu::Write()
{
	for (sor.First(); !sor.End(); sor.Next())
	{
		cout << sor.Current() << " ";
	}
	cout << endl;
}

void Menu::Union()
{
	
}

//sequence.h
#ifndef SEQUENCE_H
#define SEQUENCE_H

#include <iostream>
#include "node.h"

class Sequence
{
public:
		Sequence();
		//Sequence(const Sequence& s);
		//Sequence& operator=(const Sequence& s);
		//~Sequence();

		void Insert(int e);
		
		int Current() const { return current->value; }
		void First()        { current = first; }
		bool End()    const { return current==NULL; }
		void Next()         { current = current -> next; }
		bool Empty()  const { return head->next== NULL; }

private:

		Node *first;
		Node *last;
		Node *current;
		Node *head;

};

#endif

//sequnce.cpp
#include <iostream>
#include "sequence.h"
#include "node.h"

using namespace std;

Sequence::Sequence()
{
	Node *head = new Node();
	head->prev = head->next = head;
	first = NULL;
	last = NULL;
	current = NULL;
}

void Sequence::Insert(int e)
{
		Node *p = new Node(e, last, NULL);
		if (last!=NULL) last->next = p;
		last = p;
		if (first==NULL) first = p;
		
}

//node.h
#ifndef NODE_H
#define NODE_H

#include <iostream>

class Node
{
public:
	int value;
	Node *next;
	Node *prev;
	Node (int value = 0, Node *prev = 0, Node *next = 0)
	{
		this->value = value;
		this->prev = prev;
		this->next = next;
	}
};

#endif

( imp | 2007. 04. 02., h – 11:36 )

valamit nagyon benéztél...
a Node default konstruktorában csinálsz egy új Node-ot, amivel aztán nem csinálsz semmit, memleak.
az Insert-nél a head-ed lehet NULL is, szóval a 'head->next' runtime errort fog dobni..

( Ballage | 2007. 04. 02., h – 11:37 )

Nekem itt több gondom is akadna:

1. Ha már a headereket osztályonként külön hozod létre (ami nagyon helyes), akkor a cpp fájlokat is illik különválasztani, tehát a Node metódusait a node.cpp-be tenni.

2. A Node::Node() létrehoz egy új node-ot (igen, még egyet!), tehát amikor default konstruktorral létrehozok egy új példányt, az mindjárt létrehoz egy további példányt, ráadásul a pointerét lokális változóba teszi (head), amit aztán nem szabadít fel soha sem!!! :-/ De nem is értem, mit kell ott létrehozni? A konstruktorban pont egy vadiúj példányon dolgozol....

3. Amúgy a default konstruktort, ha tényleg csak annyit csinál, hogy nullával inicializálja a tagváltozókat, szerinteb nyugodtan beteheted a headerbe, úgy mint a Sequence::Sequence() esetében tetted.

4. Mivel körkörösen láncolt a lista, elég egy head pointer, tail nem kell, mivel a legutolsó elemed a legelsőre mutat, a legelső prev-je meg a legutolsóra, tehát az utolsó elem címe mindig megtalálható a head->prev-ben, már ha van egyáltalán valami a listában.

5. A lista osztálytól általában külön szokták választani az iterátort, vagyis azt az osztályt, amely végigmászik a lista elemein, mivel egyidőben többen is végig akarhatnak menni az elemeken.

6. Node::Node()-ban van egy head->value = NULL, amit a fordító csont nélkül megesz (C++-ban nincs különbség a NULL pointer és a 0 integer érték között), azonban ez szemantikailag nem helyes, de legalábbis nagyon csúnya.

7. A Sequence::Insertnek két esetet kell megkülönböztetnie. Az egyik amikor tök üres a lista (head == NULL) és egy másikat, amikor már van benne elem.

Ha a head NULL, akkor a head az új node lesz, és a node prev és next pointerei mind saját magára fognak mutatni.

Ha a head nem NULL, akkor a node-ot a beszúrási mód szerint a lista elejére vagy a végére (nyilván az utóbbi alkalmasabb a gyakorlat számára) kell beszúrni. Tehát a head->prev->next és a head->prev fog az új node-ra mutatni.

Remélem érthető voltam, ha nem, akkor írj. Direkt nem írtam le kódot, hogy egy kicsit dolgozz te is! :-D

//1. Ha már a headereket osztályonként külön hozod létre (ami nagyon helyes), akkor a cpp fájlokat is //illik különválasztani, tehát a Node metódusait a node.cpp-be tenni.
Ez egy jogos megjegyzés :)

//2. A Node::Node() létrehoz egy új node-ot (igen, még egyet!), tehát amikor default konstruktorral //létrehozok egy új példányt, az mindjárt létrehoz egy további példányt, ráadásul a pointerét lokális //változóba teszi (head), amit aztán nem szabadít fel soha sem!!! :-/ De nem is értem, mit kell ott //létrehozni? A konstruktorban pont egy vadiúj példányon dolgozol....
Ez a részt nem nagyon értem :(

//3. Amúgy a default konstruktort, ha tényleg csak annyit csinál, hogy nullával inicializálja a //tagváltozókat, szerinteb nyugodtan beteheted a headerbe, úgy mint a Sequence::Sequence() esetében //tetted.
Ez is jogos, és a legegyszerübb :)

//4. Mivel körkörösen láncolt a lista, elég egy head pointer, tail nem kell, mivel a legutolsó elemed a //legelsőre mutat, a legelső prev-je meg a legutolsóra, tehát az utolsó elem címe mindig megtalálható a //head->prev-ben, már ha van egyáltalán valami a listában.
Ez is igaz, de nálunk egyetemen a feladat kiírásánál szerepel, hogy legyen ilyen pointer is, tudom értelmetlen, de ez van :)

//5. A lista osztálytól általában külön szokták választani az iterátort, vagyis azt az osztályt, amely //végigmászik a lista elemein, mivel egyidőben többen is végig akarhatnak menni az elemeken.
Ez a rész még homályos :(

//6. Node::Node()-ban van egy head->value = NULL, amit a fordító csont nélkül megesz (C++-ban nincs //különbség a NULL pointer és a 0 integer érték között), azonban ez szemantikailag nem helyes, de //legalábbis nagyon csúnya.
Ehez is kérnék egy kis magyarázatot, mert nálunk egyik tantárgynál azt mondták, hogy NULL-t írjuk, és az jó, de másiknáll hogy már c++-ban nem használjuk a NULL-t csak "0"-t. Akkor most melyik a szemantikusan a helyes?

//7. A Sequence::Insertnek két esetet kell megkülönböztetnie. Az egyik amikor tök üres a lista (head == //NULL) és egy másikat, amikor már van benne elem.
Ez is egy jogos megjegyzés, csak még a fejelemet nem tudom létrehozni, addig ezzel nincs mit foglalkozzak, de ez tökéletesen igaz

//Ha a head NULL, akkor a head az új node lesz, és a node prev és next pointerei mind saját magára //fognak mutatni.
Ez a Node::Node() konstruktorban próbálom megvalósítani, de visszatéréskor elveszik a head értéke, azaz ott lefoglalja, de visszatéréskor már nics meg, miért?

//Ha a head nem NULL, akkor a node-ot a beszúrási mód szerint a lista elejére vagy a végére (nyilván az //utóbbi alkalmasabb a gyakorlat számára) kell beszúrni. Tehát a head->prev->next és a head->prev fog //az új node-ra mutatni.

Szívessen vennék pár sor forráskodot is, mert a megjegyzések nagyon jók, de sajons nem jutottam előre :(

Egyneként válaszolok, mert el fogok veszni a sok kódban.... :-)

2-es pont: 


// Ez ugye a default konstruktorod
Node::Node()
{
	// a head nevű, lokális(!) változó egy pointer (Node * típusú), amit itt egyből
	// inicializálsz is egy új, általad lefoglalt Node példány címével, aminek itt le fog futni
	// az a konstruktora, amely a szignatúra szerint három pointert vár. Tehát amikor
	// valahol leírod a kódban azt, hogy "new Node()", akkor először lefoglalódik egy Node 
	// példány számára a hely, meghívódik a default konstruktor (tehát ez, Node::Node()), 
	// majd a következő sor megint csak létrehoz egy új Node példányt (new Node....), 
	// de azt már a másik konstruktorával inicializálja (Node::Node(Node *, Node *, Node*). Érted?
	Node *head = new Node(NULL, NULL, NULL);

	// Az új (2.) példányt aztán feltöltöd úgy, hogy saját magára mutogasson (ez még 
	// _önmagában_ nem is festene rosszul).
	head->next = head;
	head->prev = head;

	// Ez nem szép. Ha a value egyszer int-nek lett deklarálva, akkor illik egész
	// egész értékkel inicializálni: node->value = 0;
	// Amúgy a default konstruktor inicializációs része a függvény fejében pont erre való, nem itt kellene.
	head->value = NULL;

	// Következő nagy bökkenő: a head nevű vátltozód érvényessége itt megszűnik, a
	// helye felszabadul a veremről DE!!!! ez csak a pointer helye, az általad 
	// new-val lefoglalt 2. node példányt, amire ez a pointer mutatott
	// nem szabadítod fel, és ettől kezdve nem is hivatkozik rá senki ===> memóriaszivárgás!!!!
}

5. pont:

Arra gondolok, hogy elvi hiba, ha a lista más információt is tartalmaz, mint ami szorosan az ő eredeti funkciójához köthető. A listának felelőssége az elemek nyilvántartása, de az nem biztos, hogy a hatáskörébe tartozik egy végigléptetési művelet támogatása. Itt konkrétan a current változóra gondolok, ami ugye azt mutatja, hogy egy ciklusban, amely az elemeket veszi sorra, éppen hol tartok.

Ezzel az a gond, hogy mivel ezt a listához kötötted, nem teheted meg, hogy egyiedjűleg két különböző ciklussal menj végig ugyanannak a listának elemein (pl. beágyazott ciklusok), mivel ezek összekuszálnák egymást.

Erre találták ki az iterátorokat, amely a listán való végighaladás pillanatnyi állapotát (konkrétan a current változó értékét) tartják nyilván.

Sajnos rossz szokás. :)

C++-ban nincs is definiálva a NULL, tehát normál esetben hibaüzenetet kapsz.
Most azért nem, mert az iostream használja az istream-et, ami meg a cstddef-et. Érdemes leszokni (azaz rá se szokni) mert idegesítő lesz, ha véletlen ott használod, ahol épp nincs definiálva.

A lényeg, hogy C++-ban az utolsó szabvány szerint nem használunk NULL-t, csak 0-t.
(A következő szabványban lehet, hogy bejön egy null_ptr szimbólum.)

Ha a tanárod beleköt, akkor Bjarne Stroustrup: A C++ programozási nyelv 117. oldalára hivatkozhatsz. :)
(Ez egyébként a C++ biblia!)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Amint megosztod az egyes számú alakot rögtön azt használom. :)

Egyébként ez egy kifejezés, és független a biblia szó eredeti szószerinti jelentésétől.
(Úgyhogy ne kötözködj, ha nincs igazad. :) )

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

//Ha a head NULL, akkor a head az új node lesz, és a node prev és next pointerei mind saját magára //fognak mutatni.
Ez a Node::Node() konstruktorban próbálom megvalósítani, de visszatéréskor elveszik a head értéke, azaz ott lefoglalja, de visszatéréskor már nics meg, miért?

Azt hiszem itt a konstruálási folyamat nem tiszta neked. Tehát egy ojjektum példány létrehozása során először a new operátor lefoglal pontosan annyi memóriát, amely egy darab (Node) példány számára szükséges. Ennek eredménye egy mutató, ami _majd_ a new operátor értéke lesz, és amit majd értékül adsz egy pointer változónak. A foglalás után a példányt inicializálni is kell, amire való a konstruktor. Ezt az operátor a sikeres memóriafoglalás után meghívja, tehát amikor a konstruktorba kerül a vezérlés, akkor már le van foglalva neked a példány, csak inicializálnod kell. A new mindig azt a konstruktort hívja meg, amely az aktuális paraméterlistára illeszthető a szignatúrája alapján. A fentiek alapján a konstruktorban már él a this pointer (nyilván az éppen frissiben lefoglalt, de még nem (teljesen) inicializált példány címe van benne).

A te kódodban az a gond, hogy a konstruktorodban létrehozol egy _további_ node példányt, aminek a címét viszont eldobod. Szerintem nem kell létrehozni semmit sem.

Remélem ez érthetőbb volt. :-)

Csomópont beszúrása:
ha a lista üres:
head = node;
node->next = node;
node->prev = node;
egyébként
node->next = head; // az új csp. következő eleme a head lesz
node->prev = head->prev; // a csp. előző eleme a lista eddig utolsó eleme lesz

head->prev->next = node; // a lista előzőleg utolsó elemének köv. pointere az új csp-ra fog mutatni
head->prev = node; // a head előző pointere (ami a lista utolsó elemét tartja nyilván) szintén az új csp-ra fog mutatni

Tényleg jobb, ha lerajzolod.

class Sequence {
Node head;
};

Sequence::Sequence() {
head.next = &head;
head.prev = &head;
}

Bár lehet, dinamikus esetben könnyebben megy, no mind1, nekem így szimpatikusabb.

Másik eset:

class Sequence {
Node *head;
};

Sequence::Sequence() {
Node *head = new Node();
head->prev = head->next = head;
}

Sequence::~Sequence() {
...
delete head;
}

class Node {
Node * prev, *next;
int adat;

Node (int adat=0, Node *prev = 0, Node *next = 0) {
this->adat = adat;
this->prev = prev;
this->next = next;
}

};

A többit ki tudod találni

De így feleslegesen foglalsz le egy Node példányt, ami nem szép (meg pazarlás is, főleg ha egy node konkrétan egészen nagy, pl. egy másik alkalmazásban).

A lista méretét egy int taggal is tudod követni, amit a lista műveletek tartanak karban, ez szerintem máshol is így megy.

Az egyes node-ok prev/next-je sosem NULL, mivel ez kétirányú láncolt lista. Legfeljebb a head null, ami viszont az üres listát jelenti.

rotfl, 12 bájt nagy baj, de tényleg, összedől a világ. Talán olvasd el a feladatot. Fejelemes lista, ergo le kell foglalni egyet fejelemnek. Nagy objektumoknál valszeg célszerűbb a pointer mint adattag.

A head nem null, mert fejeleme mindig van.

A fejelemesben kérdésben igazad van, de én nem a 12 bájtról beszélek, hanem arról, hogy _ha_ a node nagyobb, mert nem egy darab int van benne adott esetben, akkor hatékonytalan a dolog. Vagy ha sok listát kell kezelned, akkor sem túl hatékony. Ezért kár röhögni. :-P

Ezt hogy érted? Ha _mindig_ van fejelem, akkor tökmindegy, hogy az tagváltozó, vagy pointerrel hivatkozol rá. Ha csinálsz egy listát, akkor abban mindig benne lesz egy node, vagy így, vagy úgy. Sőt, ha pointerrel tartod nyilván, akkor még a pointered is ott van (és az kemény 4 bájt, bizony! :-))

a beszúrásokkal azonos számú. Ha egy olyan listád van, ami nagyon gyakran változik, akkor nem nyerő a nem fejelemes, mert fejelem esetén a törlés és talán a beszúrás is gyorsabb lesz, pontosan egy összehasonlításnyi idővel.