C++ Ayrintilar

[Penthesilea]

Merhaba,
Benim yine mulakat var bu sefer de her seyden emin olmadan girmicem diye inandim, ondan ben bu 3-4 gun suresince bu basliga aklima gelen sacma sapan sorulari yazicam :)

C++ hatirlamak icin bastan tum data structurelari implement ederek basladim ise, hem boylece uzerlerinde algoritma sorularini da kodlayabilecem. Gecen sefer boyle bisey yapmamanin zararini cok gordum, istediginiz kadar iyi bilmis olun zamaninda, adam sana 3.5 sene sonra BST'den node cikarcak fonksiyon yaz dedigi zaman olaylari hatirlaman bi sure aliyor ve oyle bi luksun olmuyor genelde.

Soracaklarimin neredeyse hepsinin cevabini biliyorum aslinda, da emin olmak istiyorum.

1- Pointerli bir data structureda, ornegin linklist veya tree, bir node u delete ettigimde, o node u gosteren node'u NULL'a esitlemem gerek degil mi (Programin butunlugunu bozmamak amaciyla yani)? Java'daki gibi bir obje silinince ona giden pointerlar null olmuyor cop sayilar oluyor.

2- BinarySearchTree classi implement ettiginizi dusunun. private BSTNode *root tutuyorsunuz, en azindan ben tutuyorum :) Simdi mesela Linklist'te head'i dummy olarak tutarim ben, hicbi deger tasimaz ilk elemani gosterir. Ama Tree'de ayni basitlikle mumkun degil bu.
Ben de onun yerine add islemi yaparken ilk root'a bakiyorum deger atanmis mi diye, atanmamissa direk rootun value sunu yeni value'ya set ediyorum. atanmissa, bildiginiz add iste. bana mantikli geldi boyle bisey, 3 sene once nasil yaptigimi hatirlamiyorum, en pratik yontem nedir?

3- Yine bi BST sorusu, mesela bi node'u remove edicez, 2 tane children'i var, boyle bi durumda left subtree'nin en buyuk elemanini silecegimiz node'un yerine koyup node'u oyle siliyorduk (veya iste right'in en kucugu). Boyle bi durumda, "guzel" olan yontem, direk asagidan getirecegimiz node'un value'sunu, silecegimiz node'un value suyla degistirip asagidakini silmek mi, yoksa nodelar bir butundur, bolunemez, diye dusunup once usttekini silip sonra alttakine giden pointerlarla mi oynamaliyiz. ilki daha pratik ama iste ayni olcude temiz mi?

Ben soru oldukca sorucam burda 4'ten devam ederek :)

[riglous]

2- Karsilastirarak asagi ineceksin, en duzgun yontem bu.
insert(newNode){
insert2(head, newNode)
}
insert2(temp, newNode){
if temp is null
temp=newNode
else if newNode > temp
insert2(temp.right, newNode)
else
insert2(temp.left, newNode)
}

3- Asagidakini silip yukariya yerlestirmek, onun da en mantiklisi sag subtree'nin en kucugunu almak.
Asagidakini (successor) silmezsen, stack dahilinde, o sildigin subtree'nin duzenini dengeli tutamazsin. Bu nedenle once silecegin node'un successor'unu silmen lazim, daha sonra da silecegin node'un yerine o successor'u koyman lazim.

[Prosciutto]

1- o node u gösteren pointerı dicektin sanırım, evet null yapman lazım.

2 - en pratik yöntem rootu kontrol etmek evet. list olsun tree olsun ben de böyle yaparım.

3 - ilk yöntemde sadece value değiştirmen yetmez yine pointerlarla oynaman gerekir gibi geldi bi an, ama emin
değilim. kafam dağınık biraz, daha sonra bakarım tekrar :)

[Penthesilea]

riglous said:

insert(newNode){
insert2(head, newNode)
}
insert2(temp, newNode){
if temp is null
temp=newNode
else if newNode > temp
insert2(temp.right, newNode)
else
insert2(temp.left, newNode)
}

hm boyle bisey yapabiliyor muyuz?

aslinda evet, boyle recursive gittin gittin null olan bi yer buldun, buraya yeni node yerlestirirsen zaten oraya bakan bi pointer var dogru.

unutmusum ya cidden, ben o yuzden hep recursion'da bi step geriden bi step ileriye bakiyordum, mesela left'ine yerlestiricez, temp->left de null ise temp->left = newnode yapiyordum. anlatabilmisimdir umarim ikisinin arasindaki farki, benimki daha komplike oluyodu tabi haliyle.

null olan bi yer bulup da oraya koyabiliyoruz direk yani, parent'i zaten orayi gosteriyor olacak diyerekten. iyi oldu bu tesekkurler, unutmusum cidden boyle basit seyleri.

[Penthesilea]

Prosciutto said:

1- o node u gösteren pointerı dicektin sanırım, evet null yapman lazım.

2 - en pratik yöntem rootu kontrol etmek evet. list olsun tree olsun ben de böyle yaparım.

3 - ilk yöntemde sadece value değiştirmen yetmez yine pointerlarla oynaman gerekir gibi geldi bi an, ama emin
değilim. kafam dağınık biraz, daha sonra bakarım tekrar :)

evet evet pointeri dicektim, tesekkurler :)

yok pointerlarla yine oynucam, yani o sag subtree'nin en kucuk elemaninina giden pointeri null'a esitliyosun sonra da o node u siliyosun iste, degerini de silinen.
ama diger yontemde silecegin node u direk silip, sonra onun parentini sagin en kucugundeki adama goturuyosun, sag in en kucugundeki adamin pointerlarini sildigin node'un cocuklarina goturuyosun falan.

[Penthesilea]

Penthesilea said:

riglous said:

insert(newNode){
insert2(head, newNode)
}
insert2(temp, newNode){
if temp is null
temp=newNode
else if newNode > temp
insert2(temp.right, newNode)
else
insert2(temp.left, newNode)
}

hm boyle bisey yapabiliyor muyuz?

aslinda evet, boyle recursive gittin gittin null olan bi yer buldun, buraya yeni node yerlestirirsen zaten oraya bakan bi pointer var dogru.

unutmusum ya cidden, ben o yuzden hep recursion'da bi step geriden bi step ileriye bakiyordum, mesela left'ine yerlestiricez, temp->left de null ise temp->left = newnode yapiyordum. anlatabilmisimdir umarim ikisinin arasindaki farki, benimki daha komplike oluyodu tabi haliyle.

null olan bi yer bulup da oraya koyabiliyoruz direk yani, parent'i zaten orayi gosteriyor olacak diyerekten. iyi oldu bu tesekkurler, unutmusum cidden boyle basit seyleri.

Bu yazdigin yanlis riglous, olmuyo bu.
ilk basta yaptigim gibiymis dogrusu

yaptigim su hatta duzgun calisiyo da baska tricky biseyler varsa diye

bu recursive

	BSTNode *addrecHelper(BSTNode *root, BSTNode *newnode) {

		if(newnode->val == root->val) {

			cout << "The value already exists, cannot insert."<<endl;

			return NULL;		

		}

		if(newnode->val < root->val) {

			if(root->left == NULL)

				return root->left = newnode;

			else

				return addrecHelper(root->left, newnode);

		}

		else {

			if(root->right == NULL)

				return root->right = newnode;

			else

				return addrecHelper(root->right, newnode);

		}

	}

	

	

	BSTNode * BST::addrec(int val) {

		if(root->val == EMPTY) {

			root->val = val;

			return root;

		}

		else {

			BSTNode *newnode = new BSTNode(val);

			return addrecHelper(root, newnode);

		}

	}

	

bu iterative

	BSTNode * BST::add(int val) {

		if(root->val == EMPTY) {

			root->val = val;

			cout << "Added " << val << endl;

			return root;

		}

		else {

			BSTNode *temp = root;

			BSTNode *newnode = new BSTNode(val);

			bool added = false;

			while(!added) {

				if(val == temp->val) {

					cout << "The value already exists, cannot insert."<<endl;

					return NULL;

				}

				if(val < temp->val) {

					if(temp->left == NULL) {

						temp->left = newnode;

						added = true;

					}

					else {

						temp = temp->left;

					}

				}

				else{

					if(temp->right == NULL) {

						temp->right = newnode;

						added = true;

					}

					else {

						temp = temp->right;

					}

				}

			}

			return newnode;

		}

	}

	

[Penthesilea]

kafam karisti acikcasi, cunku simdi bi yerde daha senin soyledigini yapan birini gordum, ama benim compilerimda en azindan calismiyor.
wikideki algoritmalarda da benimki gibi.


kisacasi sorum su:

Node *x = NULL;
Node *y;

y->right = x;
x = new Node(5);

bu, y->right->value yu 5 yapar mi yapmaz mi?


PS. simdi denedim, su kod ile null cikiyor m->next. ben eclipse'in c++ projesini kullaniyorum yani artik compiler falan mi farkli dicem.

	Node *n = NULL;

		Node *m = new Node(1);

		m->next = n;

		if(n == NULL) {

			cout << "A" << endl;

			n = new Node(2);

	

		}

		cout << m->next << endl;

	

[reyou]

visual studio ile derlenen c++ projeleri ile diger derleyicilerle derlenen projeler arasinda performans farki oluyomu?

[Penthesilea]

normal kullanici seviyesinde fark olmamasi lazim, ust seviyeleri bilmiyorum.

ben linuxda C++ yazdigimda g++ ile derliyorum, for looplarinin icindeki declaration bi fark vardi, benim her loop icinde yeni bir int i=0; yapmami benim derleyici kabul ediyorken, kiz arkadasiminki kabul etmiyordu (tek bi i declare edip sonra hep onu kullanmak) ki normal olan da benimki yani.

ben mac os kullandigim icin GUI kullanmamin bildigim kadariyla tek yolu Eclipse, e Eclipse'i de seviyorum ondan onu kullaniyorum ben de.

[Enzelna]

Penthesilea said:

kisacasi sorum su:

Node *x = NULL;
Node *y;

y->right = x;
x = new Node(5);

bu, y->right->value yu 5 yapar mi yapmaz mi?

c++ mantığını bilmiyorum ama tahminen 5 yapmaz çünkü x'e Node(5) değerini y->right yaptıktan sonra atıyorsun.

şöyle sölim,

int x = 0;
int y = x;

x = 5;

yapmakla aynı mantıktaysa, y nin değeri 0 olur, çünkü y'yi x'e atarken x'in değeri 0 dı.

[Penthesilea]

Tesekkurler, evet zaten durgun kafayla okuyunca bu mantikli.
O zaman nette yanlis implementationlar da geziyor kisaca diyip isin icinden siyriliyorum :)

Yatiyim o zaman ben, yarin karsiniza templated classlar veya inplace array modification sorulariyla gelebilirim :P

[riglous]

Enzelna said:

c++ mantığını bilmiyorum ama tahminen 5 yapmaz çünkü x'e Node(5) değerini y->right yaptıktan sonra atıyorsun.

şöyle sölim,

int x = 0;
int y = x;

x = 5;

yapmakla aynı mantıktaysa, y nin değeri 0 olur, çünkü y'yi x'e atarken x'in değeri 0 dı.

C++'in gucu pointer'lardan gelmiyo mu?
sen int y=x yerine y'yi x'in adresine point edersen, daha sonra x'i ne kadar degistirirsen degistir, y daima x'in adresine esit olur.
cout y dersen de sana x'in adresini verir. Bu nedenle y'nin point ettigi adresin degerini yazdir dersen, o zaman x ne kadar degisirse degissin son value'yu kullanacaktir. midir?

[Enzelna]

hmm doğrudur ben başta mantığını bilmiyorum dedim zaten, sadece bi tahmindi benimki :)

[Prosciutto]

Penthesilea said:

kisacasi sorum su:

Node *x = NULL;
Node *y;

y->right = x;
x = new Node(5);

bu, y->right->value yu 5 yapar mi yapmaz mi?

NULL direkt olarak 0'a karşılık geliyor yani x bellekteki 0 no'lu adresi gösteriyor gibi düşünebilirsin. y->right 'a da 0 atamış oluyorsun. ama daha sonra new Node(5) ile bellekte farklı bi bölge ayırıp x'e o bölgenin adresini atıyorsun yani sonuç olarak x ve y farklı adresleri gösteriyor. 5 olmaz değeri yani.

[Prosciutto]

reyou said:

visual studio ile derlenen c++ projeleri ile diger derleyicilerle derlenen projeler arasinda performans farki oluyomu?

ufak tefek farklar olabilir de genelde farkedilmez. her derleyici farklı kod üretip farklı optimizasyonlar yapabiliyor çünkü.