Új hozzászólás Aktív témák
-
Azazel999
csendes tag
válasz
alratar
#2006
üzenetére
Várj csak! Rákerestem egy másikra, ami még hasznosabb, csak nem emlékeztem a címére, de képekre kerestem google-ben és úgy meglett (csak a borítótól ismerem fel, mindig elfelejtem a pontos címet
). Szóval a "Szoftverfejlesztés C++ nyelven" című könyvről van szó, a szerzők pedig Benedek Zoltán és Levendovszky Tihamér. Ez tényleg tök jó anyag és kezdőknek főleg hasznos, mert nagyon szájbarágós. Legalább is nekem annak tűnt, amikor olvastam. -
Azazel999
csendes tag
válasz
alratar
#2003
üzenetére
"Tanuljuk meg a C++ 24 óra alatt"
Ez a könyv nekem is megvan, szerintem kezdésnek bőven megteszi, például a Prog II (nekünk ezen tanították a C++-t egyetemen) ennek egy részét fedi le. Ez persze ne azt jelenti, hogy holnapra már C++ programozó vagy, hanem hogy 24 leckét tartalmaz, amik kb 1-2 órát vesznek igénybe, ha tényleg tanulni akarod.
-
Azazel999
csendes tag
Köszönöm a gratulációkat, de még inkább a segítségeteket
A beszúrás egy kicsit összetettebb, ahogy én értelmeztem az előadásfóliákról. Ebbe a bizonyos szájba vert önszervező bináris keresőfába nem lehet csak úgy beszúrni, mint egy sima bin.ker. fába. Ha új elemet akarunk, akkor keresést futtatunk az elemre, ami nyilván null-ba fut, mert az elem még nincs a fában. Ha mégis benne volt, akkor nem is kell csinálni semmit. Na most, ha ez megvan, akkor ugye keresés közben dobáltuk a részfákat a két vektorunkba (a kisebb/nagyobb csoportokba). Ezután úgy teszünk, mintha csak megvágtuk volna a fát a beszúrandó elemnél, tehát ő lesz a gyökér és rákapaszkodik a kisebb és a nagyobb fa balról, illetve jobbról. Ez volna a beszúrás. A törlést még nem sikerült kihámoznom, de erőlködök vele még holnapig, mert az a határidő. -
Azazel999
csendes tag
válasz
kingabo
#1999
üzenetére
Sikerült!
Ez lett a vágás metódus:
Fa* Fa::vag(Fa* v_pont){
vector<Fa*> kicsik;
vector<Fa*> nagyok;
Fa *aktualis = this, *kovetkezo;
//fa szétdarabolása
int count = 0;
while (aktualis->kulcs != v_pont->kulcs){
if (aktualis->kulcs < v_pont->kulcs){
kicsik.push_back(aktualis);
kovetkezo = aktualis->jobb;
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
cout << "jobbra" << endl;
} else if (aktualis->kulcs > v_pont->kulcs){
nagyok.push_back(aktualis);
kovetkezo = aktualis->bal;
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
cout << "balra" << endl;
}
aktualis = kovetkezo;
}
cout << "kint vagyok a ciklusbol" << endl;
//vágási elem gyrekeinek levágása
if (aktualis->bal != NULL){
cout << "vagasi_pontnak bal fia van" << endl;
kicsik.push_back(aktualis->bal);
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
}
if (aktualis->jobb != NULL){
cout << "vagasi_pontnak jobb fia van" << endl;
nagyok.push_back(aktualis->jobb);
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
}
cout << "vagasi pont gyerekei levagva" << endl;
vector<Fa*>::const_iterator iter;
//a kisebb- és nagyobb fa felépítése
for(int i = 1; i < kicsik.size(); ++i){
cout << "kisfa" << endl;
kicsik.at(0)->beszur(kicsik.at(i));
//kicsik.at(i)->kiir();
}
for(int j = 1; j < nagyok.size(); ++j){
cout << "nagyfa" << endl;
nagyok.at(0)->beszur(nagyok.at(j));
//nagyok.at(j)->kiir();
}
//a vágási pont gyökérré tétele, a két fa ráakasztása
v_pont->bal = kicsik.at(0);
v_pont->jobb = nagyok.at(0);
v_pont->bal->apa = v_pont;
v_pont->jobb->apa = v_pont;
//v_pont->kiir();
return v_pont;
}Bocs, ha nem volt egyértelmű a megfogalmazás, igyekeztem részletesen körülírni. Németh Tamás (SZTE-n tanít) honlapján az alga II. előadásfóliák között ott ez az önszervező bináris keresőfa (nem tudom, hogy szabad-e linkelni ide, ezért nem teszem). Ott folyamatábrával szemlélteti is, az sokkal érthetőbb, mint az én makogásom. Egyébként igazad lehet a rekurzióval, valószínűleg sokkal egyszerűbb lenne vele, de én már ennek is örülök. Ezt a metódust meg kell hívni a fa gyökerére, és a visszaadott érték lesz az új fa.
-
Azazel999
csendes tag
válasz
Azazel999
#1996
üzenetére
Nos, erre jutottam, de futtatáskor a vektoromból kifutok a számlálással valamiért:
void Fa::vag(Fa* v_pont){
vector<Fa*> kicsik;
vector<Fa*> nagyok;
Fa *aktualis = this, *kovetkezo;
//fa szétdarabolása
while (aktualis->kulcs != v_pont->kulcs){
if (aktualis->kulcs < v_pont->kulcs){
kicsik.push_back(aktualis);
kovetkezo = aktualis->jobb;
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
} else if (aktualis->kulcs > v_pont->kulcs){
nagyok.push_back(aktualis);
kovetkezo = aktualis->bal;
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
}
}
//vágási elem gyrekeinek levágása
if (aktualis->bal != NULL){
kicsik.push_back(aktualis->bal);
kovetkezo = aktualis->jobb;
aktualis->jobb->apa = NULL;
aktualis->jobb = NULL;
} else if (aktualis->jobb != NULL){
nagyok.push_back(aktualis->jobb);
kovetkezo = aktualis->bal;
aktualis->bal->apa = NULL;
aktualis->bal = NULL;
}
//a kisebb- és nagyobb fa felépítése
for(int i = 1; i < kicsik.size(); i++){
kicsik.at(0)->beszur(kicsik.at(i));
}
for(int j = 1; j < nagyok.size(); j++){
nagyok.at(0)->beszur(nagyok.at(j));
}
//a vágási pont gyökérré tétele, a két fa ráakasztása
v_pont->bal = kicsik.at(0);
v_pont->jobb = nagyok.at(0);
v_pont->bal->apa = v_pont;
v_pont->jobb->apa = v_pont;
} -
Azazel999
csendes tag
válasz
kingabo
#1995
üzenetére
Szóval amit én tudok róla, az ez:
- Van egy egyszerű bináris keresőfának kinéző fánk
- Az elemei között fennálló relációk ennek megfelelőek (jobb gyerek kisebb, bal nagyobb)
- Legfeljebb két gyereke van egy elemnek
- Ezt a fát meg lehet vágni bármelyik pontjánál (értelemszerűen, ha gyökérbél vágjuk, önmagát adja majd vissza)
- A vágás így zajlik:
+ A keresés algoritmus szerint elindulunk a gyökértől a vágási pont (v_pont) felé
+ Ha v_pontnál kisebb elemet találunk, az "a" részfa lesz a neve (1 az első és i mindig nő eggyel)
+ Ha nagyobbat, akkor "b[j]" részfa lesz belőle (1 az első és j is mindig nő eggyel)
+ Minden lépésnél levágjuk az adott elemről azt a gyerekét, amelyik felé lépünk (nem lesz apja)
+ Ha elértük a v_pontot, akkor az előző két lépést végrehajtjuk a két gyerekére is (ha van neki)
+ Az a(i) fákat beszúrjuk a[1]-be egymás után sorrendben (i > 1)
+ b[j] fákat a b[1]-be (j > 1)
+a[1] és b[1] apja is v_pont lesz (ezért ők pedig a gyerekei)
+ véget érte az algoritmusHa rosszul tudnám, akkor valaki javítson ki, mert erre később is nagy szükségem lesz, ezért gáz, ha nem jól tudom.
Azért önszervező, mert ezt csinálja, ha "megvágod" és ugyanígy lehet beszúrni bele új elemet, csak ott luftot üt a keresés, és ott ér véget az algoritmus.
-
Azazel999
csendes tag
válasz
kingabo
#1992
üzenetére
Köszi, de ez nem AVL fa akar lenni, hanem konkrétan önszervező bináris keresőfa. Egyébként lehet, hogy a beszúrás, törlés metódusaim sem passzolnak hozzá :S Szóval tudom, minek kell történnie, ezt le is írtam. Nem ezzel van a baj, de nem tudom lekódolni. Tényleg sok próbálkozáson túl vagyok, de egyszerűen képtelen vagyok megoldani. Nem tudom, hogyan kódoljam le azt, hogy induljunk el a gyökértől kereséssel és nyisszantsunk le minden lépésnél a fából, majd a levágottakból gyúrjunk két fát, az egyikben a vágási pontnál kisebb, a másikban nagyobb elemekből és a két gyökér apja legyen a vágási pont.
-
Azazel999
csendes tag
válasz
Azazel999
#1987
üzenetére
És közben rájöttem, hogy a "szétszedem őket két csoportba és egyenként beszúrom a két fába" ötlet nem jó, mivel ha más a sorrend, nem ugyanazok lesznek a részfák megfelelő részei, mint az eredetiek voltak, mert telejsen újakat épít belőlük. Szóval marad az átláncolás, de hogy a jó életbe lehet azt megcsinálni? Ha Java-ban egyszerűbb, úgy is elmagyarázhatjátok, de C++ az elsődleges célom, mivel abban magamtól is eljutottam idáig.
-
Azazel999
csendes tag
válasz
Jester01
#1986
üzenetére
Köszönöm, de nem ez volt a baj. Tökéletesen értem a pointereket (szerintem) és az, hogyan működnek. A problémám az, hogy nem tudom hogyan valósítsam meg a vágás/összeragasztás műveletét az önszervező bin.ker. fáknál. Tudom rá a szabályt, meg lerajzolom füzetben az egészet, de egyszerűen nem tudom lekódolni. Már tényleg sokféleképpen próbáltam.
-
Azazel999
csendes tag
Tudom, de már három órája nem kaptam választ és gondoltam jelzem, hogy még várok rá. Csak mert találkoztam már olyannal, hogy senki nem írt semmit, aztán mikor bepöccentem rajta, nagy flegmán közölték, hogy azért nem írtak, mert olyan egyszerű volt a kérdés, hogy szégyen még feltenni is.
-
#1982
Azazel999
csendes tag
WonderCSabo
#1978
Azazel999
csendes tag
válasz
WonderCSabo
#1978
üzenetére
Na jó, most már nagyon belekavarodtam. Tudnál adni valami támpontot az átláncoláshoz?
-
#1981
Azazel999
csendes tag
WonderCSabo
#1978
Azazel999
csendes tag
válasz
WonderCSabo
#1978
üzenetére
Csak, hogy tisztázzuk, jól tudom-e a vágás szabályait:
- a vágási elem bal részfájában lesz minden, nála kisebb elem
- a jobb részfájában minden, nála nagyobb elemTehát, ha ő egy olyan elem volt, aki három szint mélyen van és még ilyen mélyen van neki jobb és bal részfája is, akkor nem tudom, csak úgy átláncolni, vagy igen?
-
#1980
Azazel999
csendes tag
WonderCSabo
#1978
Azazel999
csendes tag
válasz
WonderCSabo
#1978
üzenetére
Ráadásul a beszúrással gondom akadt, mert elkezdtem írni a vágás metódust és rájöttem, hogy üres (vagyis NULL pointer) fába nem tud beszúrni ez a szerencsétlen.
-
#1979
Azazel999
csendes tag
WonderCSabo
#1978
Azazel999
csendes tag
válasz
WonderCSabo
#1978
üzenetére
Átláncolom? Ezt most nem igazán értem.
A javas megoldás pedig továbbra is elképzelhetetlen számomra.
-
Azazel999
csendes tag
válasz
Azazel999
#1976
üzenetére
Ja, és a kereső metódusban meg kell fordítani a kacsacsőröket, mert különben nem jól dolgozik:
Fa* Fa::keres(int kulcs){
if (this->kulcs == kulcs){
return this;
} else if (this->kulcs > kulcs){
return this->bal->keres(kulcs);
} else {
return this->jobb->keres(kulcs);
}
} -
Azazel999
csendes tag
válasz
Azazel999
#1975
üzenetére
Viszont a vágás megvalósításáról még lövésem sincs. Azt tudom, hogy kettévágom a fát két fává a vágási elem mentén. Az egyik fába kerülnek a nála kisebb elemeket tartalmazó részfák, a másikba a nála nagyobbak. Majd ő lesz az új fa gyökere és a két másik fát hozzácsapjuk bal-. és jobb leszármazottaknak. A hozzácsapással nincs is gond, az tulajdonképpen csak beszúrás, de hogyan hámozhatom ki az összes nála kisebb/nagyobb elemet, hogy aztán fát gyúrjak belőlük? Van erre valami bevált módszer?
-
Azazel999
csendes tag
Sziasztok!
C++-ban szeretnék készíteni egy önszervező bináris keresőfát (vagy Java-ban, de azzal elakadtam, mert pointerek nélkül nehézkes a dolog, szóval inkább C++). A vágás (vagyis a legfontosabb metódus
) még nincs meg, de azon kívül minden más igen (keresés, beszúrás, törlés, minimális/maximális elem, előző/ következő elem, teljes fa és egyetlen elem kiíratása). A problémám az, hogy bár a kód "szépen" néz ki és működnie is kéne, összeomlik, amikor keresek egy elemet. Már pedig ez nagyon nagy baj, mert a többi metódus szinte mind elemekre (részfa-gyökerekre) mutató pointereket kér paraméternek. Ebből adódóan egyik sem fut, mert nem tudok nekik pointert adni. Van egy Fa osztályom és egy Main állományom, ezek lennének:Fa.cpp
#include "Fa.hpp"
#include <iostream>
#include <cstddef>
using namespace std;
Fa::Fa(){
this->kulcs = -1;
this->bal = NULL;
this->jobb = NULL;
this->apa = NULL;
}
Fa::Fa(int kulcs, Fa* bal, Fa* jobb, Fa* apa){
this->kulcs = kulcs;
this->bal = bal;
this->jobb = jobb;
this->apa = apa;
}
Fa::~Fa(){}
Fa::Fa(Fa& other){
this->kulcs = other.kulcs;
this->bal = other.bal;
this->jobb = other.jobb;
this->apa = other.apa;
}
Fa* Fa::keres(int kulcs){
if (this->kulcs == kulcs){
return this;
} else if (this->kulcs < kulcs){
return this->bal->keres(kulcs);
} else {
return this->jobb->keres(kulcs);
}
}
Fa* Fa::min(){
if (this->bal == NULL){
return this;
} else {
return this->bal->min();
}
}
Fa* Fa::max(){
if (this->jobb == NULL){
return this;
} else {
return this->jobb->max();
}
}
Fa* Fa::kovetkezo(){
if (this->jobb != NULL){
return this->jobb->min();
} else {
Fa* q = this->apa;
Fa* p = this;
while (q != NULL && p == q->jobb){
p = q;
q = p->apa;
}
return q;
}
}
Fa* Fa::elozo(){
if (this->bal != NULL){
return this->bal->max();
} else {
Fa* p = this->apa;
Fa* q = this;
while (q != NULL && p == q->bal){
p = q;
q = p->apa;
}
return q;
}
}
void Fa::beszur(/*Fa* fa, */Fa* beszurando){
Fa* y = NULL;
Fa* x = this;
while (x != NULL){
y = x;
if (beszurando->kulcs < y->kulcs){
x = x->bal;
} else {
x = x->jobb;
}
}
beszurando->apa = y;
if (y == NULL){
//fa = beszurando; //Ures volt a fa
} else {
if (beszurando->kulcs < y->kulcs){
y->bal = beszurando;
} else {
y->jobb = beszurando;
}
}
}
void Fa::torol(Fa* fa, Fa* torlendo){
Fa *x, *y;
if (torlendo->bal == NULL || torlendo->jobb == NULL){
y = torlendo;
} else {
y= torlendo->kovetkezo();
}
if (y->bal != NULL){
x = y->bal;
} else {
x = y->jobb;
}
if (x != NULL){
x->apa = y->apa;
}
if (y->apa = NULL){
fa = x;
} else if (y == y->apa->bal) {
y->apa->bal = x;
} else {
y->apa->jobb = x;
}
if (y != torlendo){
torlendo->kulcs = y->kulcs;
}
}
void Fa::kiir(){
cout << "kulcs: " << this->kulcs;
if (this->bal != NULL){
cout << " bal: " << this->bal->kulcs;
} else {
cout << " bal: NULL";
}
if (this->jobb != NULL){
cout << " jobb: " << this->jobb->kulcs;
} else {
cout << " jobb: NULL";
}
if (this->apa != NULL){
cout << " apa: " << this->apa->kulcs << endl;
} else {
cout << " apa: NULL" << endl;
}
if (this->bal != NULL){
this->bal->kiir();
}
if (this->jobb != NULL){
this->jobb->kiir();
}
}
void Fa::kiir_egyet(){
cout << "kulcs: " << this->kulcs;
if (this->bal != NULL){
cout << " bal: " << this->bal->kulcs;
} else {
cout << " bal: NULL";
}
if (this->jobb != NULL){
cout << " jobb: " << this->jobb->kulcs;
} else {
cout << " jobb: NULL";
}
if (this->apa != NULL){
cout << " apa: " << this->apa->kulcs << endl;
} else {
cout << " apa: NULL" << endl;
}
}Main.cpp
#include <iostream>
#include <cstddef>
#include <cstring>
#include "Fa.hpp"
using namespace std;
int main (int argc, char** argv){
//fa letrehozasa
Fa *fa = new Fa(5, NULL, NULL, NULL);
fa->beszur(new Fa(3, NULL, NULL, NULL));
fa->beszur(new Fa(4, NULL, NULL, NULL));
fa->beszur(new Fa(15, NULL, NULL, NULL));
fa->beszur(new Fa(2, NULL, NULL, NULL));
fa->beszur(new Fa(7, NULL, NULL, NULL));
cout << endl;
fa->kiir();
cout << "\n" << endl;
//cout << fa->keres(15)->kiir_egyet();
}Tudnátok adni valami tippet, hogy mi lehet a baj?
Az egy kurzus neve volt: "Programozás II. informatikusoknak"
A beszúrás egy kicsit összetettebb, ahogy én értelmeztem az előadásfóliákról. Ebbe a bizonyos szájba vert önszervező bináris keresőfába nem lehet csak úgy beszúrni, mint egy sima bin.ker. fába. Ha új elemet akarunk, akkor keresést futtatunk az elemre, ami nyilván null-ba fut, mert az elem még nincs a fában. Ha mégis benne volt, akkor nem is kell csinálni semmit. Na most, ha ez megvan, akkor ugye keresés közben dobáltuk a részfákat a két vektorunkba (a kisebb/nagyobb csoportokba). Ezután úgy teszünk, mintha csak megvágtuk volna a fát a beszúrandó elemnél, tehát ő lesz a gyökér és rákapaszkodik a kisebb és a nagyobb fa balról, illetve jobbról. Ez volna a beszúrás. A törlést még nem sikerült kihámoznom, de erőlködök vele még holnapig, mert az a határidő.
Új hozzászólás Aktív témák
Hirdetés
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- Üzleti Fujitsu Lifebook u7510 15,6" FHD IPS 2021/08. havi gyártás
- NEC MultiSync V421 monitor (42") 1920 x1080px
- Dell Latitude 5495 Full HD IPS Ryzen 5 pro 2500u Radeon Vega Mobile Gfx i5-8350u verő Bp MPL Foxpost
- Samsung Galaxy S23 , 8/128 GB , Kártyafüggetlen
- Bomba ár! Lenovo ThinkPad X250 - i5-5GEN I 8GB I 128GB SSD I 12,5" HD I Cam I W10 I Garancia!
Állásajánlatok
Cég: PC Trade Systems Kft.
Város: Szeged
Cég: PC Trade Systems Kft.
Város: Szeged