Erstes Programm: "Laufzeit"fehler und Projektidee

Ja, Arrays sind automatische Variablen,
Automatische Variablen werden beim verlassen des Scopes, in dem sie definiert wurden, ungültig.

Arrays kann man nach ihrer Definition nicht in der Größe ändern oder einen anderen Speicherplatz zuweisen. (sie wachsen nicht dynamisch - auch nicht statisch)
Darum gibt es auch keine GC.

Bei dynamischen Speicher sieht da anders aus. Aber da bist du (als Programmierer) für die Anforderung und Freigabe zuständig. Darum gibt es auch keine GC.^*

Ja, auch structs sind automatische Variablen (im Prinzip alles was einen Namen hat und Speicherplatz anbietet).
Speicher von malloc hat keinen Namen, Stringliterale auch nicht.
Ein Array hat einen Namen.

^*Mag sein das freie benachbarte Speicherblöcke wieder zusammengefasst werden.

regInfo000*

Ok, ich hab' jetzt mal einen Binärbaum ohne löschen/Remove geschrieben, um malloc und struct kennenzulernen:

/*
 * Kommentar
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	char str[20];
	struct Node *left;
	struct Node *right;
} Node;

Node *tree = NULL;

void cop1(char str[], Node *nod) {
	int i;
	for (i = 0; str[i] != '\0' && i < 19; i++)
		nod->str[i] = str[i];
	nod->str[i] = '\0';
	nod->left = NULL;
	nod->right = NULL;
}

void add1(char str[], Node *nod) {
	if (nod->left == NULL || nod->right == NULL) {
		Node *newNod = (Node *) malloc(sizeof(Node));
		cop1(str, newNod);
		if (nod->left == NULL)
			nod->left = newNod;
		if (nod->right == NULL)
			nod->right = newNod;
		return;
	}
	if (rand() % 2 == 0)
		add1(str, nod->left);
	else
		add1(str, nod->right);
}

void add(char str[]) {
	if (tree == NULL) {
		tree = (Node *) malloc(sizeof(Node));
		cop1(str, tree);
		return;
	}
	add1(str, tree);
}

void printTree1(int ebe, Node *nod) {
	if (nod == NULL)
		return;
	printf("%-5i%s%p%p\n", ebe, nod->str, nod->left, nod->right);
	ebe++;
	printTree1(ebe, nod->left);
	printTree1(ebe, nod->right);
}

void printTree(void) {
	printTree1(1, tree);
}

int main(void) {
	int i;
	int array[10];          /* Deklaration */
	int *pointer1, *pointer2;
	pointer1 = array;       /* pointer1 auf Anfangsadresse von array */
	pointer2 = array + 3;   /* pointer2 auf 4.Element von array      */

	array[0]      = 99;    /* array[0] */
	pointer1[1]   = 88;    /* array[1] */
	*(pointer1+2) = 77;    /* array[2] */
	*pointer2     = 66;    /* array[3] */

	for (i = 0; i < 10; i++)
		printf("%5i\n", array[i]);

	add("eins");
	add("Zwei");
	add("drei");
	add("Vier");
	add("fuenf");
	add("Sechs");
	add("sieben");
	add("Acht");
	add("neun");
	add("Sehr laaannngggeeer String/Zeichenkette!!");
	printTree();

	getchar();
	return EXIT_SUCCESS;
}

Der BinTree wird zufällig befüllt (damit entsteht auch keine Liste).

Warum muss ich typedef struct Node .... Node schreiben? Dieses Node ist doppelt. Aber ohne müsste ich immer (struct Node schreiben, wieso?
Die Ausgabe (Wurzel-Links-Rechts / dfs) dreht total durch bei mir, was habe ich vergessen?
Ist string copy richtig, wenn ich in der Struct immer Zeichenketten mit genau 20 Zeichen (inklusive '\n') haben möchte?
Wieso kann ich
struct Node *left = NULL;
nicht schreiben?
Wie kann ich relativ einfach eine Breitensuche hinbekommen?

Danke noch mal für Antworten

PS. Zeile 65 bis 74 habe ich einer anderen Quelle (c_von_a_bis_z) entnommen und gehört eig. nicht zum Programm. (Nicht verwirren lassen)

regInfo000? schrieb:

Warum muss ich typedef struct Node .... Node schreiben? Dieses Node ist doppelt. Aber ohne müsste ich immer (struct Node schreiben, wieso?

Das ist C-Syntax.

regInfo000? schrieb:

Die Ausgabe (Wurzel-Links-Rechts / dfs) dreht total durch bei mir, was habe ich vergessen?

Du trägst bei add1 den neuen Node links und rechts ein.

regInfo000? schrieb:

Ist string copy richtig, wenn ich in der Struct immer Zeichenketten mit genau 20 Zeichen (inklusive '\n') haben möchte?

string copy kenne ich nicht. Interresanter wäre auch das '\0'

regInfo000? schrieb:

Wieso kann ich
struct Node *left = NULL;
nicht schreiben?

Weil du eine Wertzuweisung nur bei der Definition der Variablen machen kannst. Dazu gehört aber nicht typedef.
Du kannst bei der Definition die Werte übergeben:

Node knoten = {"", NULL, NULL);

oder wenn es dynamisch werden soll, nimm calloc.

regInfo000*

Allerdings Platz für ein 20-elemntiges Array wird in der Struct bzw. bei malloc angelegt.

if (nod->left == NULL)
            nod->left = newNod;
        else if (nod->right == NULL)
            nod->right = newNod;
/*....*/
	printf("%-5i%-19s%7p%7p%7p\n", ebe, nod->str, nod, nod->left, nod->right);

funktioniert.

Kann ich

if (nod->left == NULL || nod->right == NULL) {

umschreiben in

if (nod == NULL) {

und dann &nod "etwas neues" zuweisen?

Verwendet ihr auch den -> für (*variable).element ?

regInfo000? schrieb:

Allerdings Platz für ein 20-elemntiges Array wird in der Struct bzw. bei malloc angelegt.

Hat das jemand bestritten? In welchem Zusammenhang meinst du das?

regInfo000? schrieb:

Kann ich ... umschreiben in ... und dann &nod "etwas neues" zuweisen?

Du darfst dir mal selber überlegen was das bedeutet:
was ist
nod?
nod->left bzw. nod->right?
&nod?
NULL?

regInfo000? schrieb:

Verwendet ihr auch den -> für (*variable).element ?

Sicher, dafür ist er da. Ist ja auch weniger Schreibarbeit (und auch lesbarer)

regInfo000*

nod ist ein Zeiger auf ein/e Struct. D. h. der Wert von nod ist eine Adresse (16-bit, 32-bit, abhängig vom System und der Implementierung). An/Bei dieser Adresse liegt/liegen "die Werte von Struct".

Idee/Vermutung: (*nod) oder nod-> liefert mir den Inhalt von nod (Dereferenzierung). &nod liefert mir die Adresse der Adresse/des Zeigers nod... Damit kann ich zur Zeit nichts anfangen. void * malloc(....) will nur eine Variable oder Typ haben, für den Speicherplatz reserviert werden soll. Dass an/bei der Adresse des NULL-Werts der Struct Speicherplatz reserviert werden soll, kann ich wahrscheinlich nicht angeben. Olay, dann erübrigt sich meine Frage grad...

Einen Wert NULL kann ich also nicht einfach in eine Struct umwandeln. Welche Adresse malloc nach dem rEservieren zurückgibt ,ist unbekannt.

Prinzipiell ist das wie mit Objektreferenzen in Java - und eine Struct (<- wie nennt man die Dinger eigentlich=?) ist so etwas wie ein Objekt (ohne Funktionen/Methoden/Prozeduren, aber mit "Variablen" [<- und wie nennen sich die=?] für Daten)...

Zukünftig werde ich wieder meinen Kopf einschalten..

regInfo000*

Hallo, ich habe es mal überarbeitet:

/*
 * Kommentar
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define STRING_SIZE 20

typedef struct Node {
	char str[STRING_SIZE];
	struct Node *left;
	struct Node *right;
} Node;

Node *tree = NULL;

void cop1(char str[], Node *nod) {
	int i;
	for (i = 0; str[i] != '\0' && i < STRING_SIZE - 1; i++)
		nod->str[i] = str[i];
	for(; i < STRING_SIZE - 1; i++) /* optionally */
		nod->str[i] = '*';
	nod->str[i] = '\0';
	nod->left = NULL;
	nod->right = NULL;
}

void add1(char str[], Node *nod, Node *newNod) {
	if (nod->left == NULL)
		if (nod->right == NULL)
			if (rand() % 2 == 0)
				nod->left = newNod;
			else
				nod->right = newNod;
		else
			nod->left = newNod;
	else if (nod->right == NULL)
		nod->right = newNod;
	else if (rand() % 2 == 0)
		add1(str, nod->left, newNod);
	else
		add1(str, nod->right, newNod);
}

void add(char str[]) {
	Node *newNod = (Node *) malloc(sizeof(Node));
	cop1(str, newNod);
	if (tree == NULL) {
		tree = newNod;
		return;
	}
	add1(str, tree, newNod);
}

void printTree1(int ebe, Node *nod) {
	if (nod == NULL)
		return;
	printf("%-2i%-19s%7p%7p%7p\n", ebe, nod->str, nod, nod->left, nod->right);
	ebe++;
	printTree1(ebe, nod->left);
	printTree1(ebe, nod->right);
}

void printTree(void) {
	printTree1(1, tree);
}

int main(void) {
	int i;
	int array[10];          /* Deklaration */
	int *pointer1, *pointer2;
	pointer1 = array;       /* pointer1 auf Anfangsadresse von array */
	pointer2 = array + 3;   /* pointer2 auf 4.Element von array      */

	array[0]      = 99;     /* array[0] */
	pointer1[1]   = 88;     /* array[1] */
	*(pointer1+2) = 77;     /* array[2] */
	*pointer2     = 66;     /* array[3] */

	for (i = 0; i < 10; i++)
		printf("%5i\n", array[i]);

	for (i = 0; i < 13; i++) {
	add("eins");
	add("Zwei");
	add("drei");
	add("Vier");
	add("fuenf");
	add("Sechs");
	add("sieben");
	add("Acht");
	add("neun");
	add("!!Sehr laaannngggeeer String/Zeichenkette!!");
	}
	printTree();

	getchar();
	return EXIT_SUCCESS;
}

Ausgabe bei mir:
[SPOILER]

C:\Users\MyName\Desktop>%gcc% HelloWorld.c
 (gcc == gcc -ansi -pedantic -Wall -o HelloWorld.exe )
C:\Users\MyName\Desktop>HelloWorld.exe
   99
   88
   77
   66
1962414434
1962761156
4202240
2686824
4202334
4202240
1 eins*************** 5213e8 520f68 521410
2 drei*************** 520f68 520fe0 520fb8
3 Sechs************** 520fe0 521008 5210f8
4 sieben************* 521008 526388 5263b0
5 Sechs************** 526388 526450 5267c0
6 eins*************** 526450 6474a8      0
7 Acht*************** 6474a8      0      0
6 drei*************** 5267c0 5269f0 526928
7 sieben************* 5269f0      0      0
7 Zwei*************** 526928      0      0
5 sieben************* 5263b0 5264f0 526540
6 fuenf************** 5264f0      0 647688
7 !!Sehr laaannngggee 647688      0      0
6 sieben************* 526540 647250 647340
7 drei*************** 647250      0      0
7 neun*************** 647340      0 6476d8
8 Zwei*************** 6476d8      0      0
4 drei*************** 5210f8 5265e0 526608
5 eins*************** 5265e0 5266a8 526748
6 Sechs************** 5266a8 647570 647408
7 drei*************** 647570      0      0
7 Vier*************** 647408      0      0
6 !!Sehr laaannngggee 526748 526978 6475e8
7 Vier*************** 526978      0 6477c8
8 Acht*************** 6477c8      0      0
7 Sechs************** 6475e8      0      0
5 Zwei*************** 526608 647070 647020
6 eins*************** 647070 6470e8 647138
7 Vier*************** 6470e8      0      0
7 Sechs************** 647138 647318      0
8 Acht*************** 647318      0      0
6 neun*************** 647020 647750      0
7 fuenf************** 647750      0      0
3 fuenf************** 520fb8 5210d0 521030
4 Zwei*************** 5210d0 521148 521198
5 fuenf************** 521148 526680 526720
6 fuenf************** 526680      0 526e70
7 neun*************** 526e70      0      0
6 neun*************** 526720 647200 526fb0
7 eins*************** 647200      0      0
7 sieben************* 526fb0      0      0
5 sieben************* 521198 647368 526590
6 !!Sehr laaannngggee 647368      0 526ee8
7 Zwei*************** 526ee8      0      0
6 neun*************** 526590      0 647458
7 Sechs************** 647458      0      0
4 Acht*************** 521030 526400 526798
5 neun*************** 526400 5268b0 526860
6 neun*************** 5268b0 526950 647548
7 drei*************** 526950 526f38      0
8 Vier*************** 526f38      0      0
7 Zwei*************** 647548 647610 527000
8 sieben************* 647610      0      0
8 neun*************** 527000      0      0
6 sieben************* 526860 6473e0 6473b8
7 drei*************** 6473e0      0 647778
8 Sechs************** 647778      0      0
7 Zwei*************** 6473b8      0 526f60
8 fuenf************** 526f60      0      0
5 Zwei*************** 526798 647638 647480
6 Acht*************** 647638 6477a0 647660
7 sieben************* 6477a0      0      0
7 neun*************** 647660      0      0
6 sieben************* 647480      0      0
2 Zwei*************** 521410 520f90 521058
3 Vier*************** 520f90 521120 5210a8
4 Vier*************** 521120 526360 5262e8
5 fuenf************** 526360 647278 5269c8
6 Vier*************** 647278 647390 647700
7 eins*************** 647390      0      0
7 drei*************** 647700      0      0
6 Sechs************** 5269c8 647520 6472a0
7 eins*************** 647520      0 526e98
8 !!Sehr laaannngggee 526e98      0      0
7 fuenf************** 6472a0      0      0
5 Zwei*************** 5262e8 526478 526770
6 Zwei*************** 526478 526888 6475c0
7 Acht*************** 526888      0      0
7 fuenf************** 6475c0      0      0
6 eins*************** 526770 647048      0
7 !!Sehr laaannngggee 647048      0      0
4 eins*************** 5210a8 526270 5211c0
5 neun*************** 526270 5263d8 5265b8
6 Acht*************** 5263d8 526900 6472c8
7 eins*************** 526900      0 6474d0
8 neun*************** 6474d0      0      0
7 Sechs************** 6472c8      0      0
6 !!Sehr laaannngggee 5265b8 5266d0 6470c0
7 sieben************* 5266d0      0 647728
8 Vier*************** 647728      0      0
7 drei*************** 6470c0      0      0
5 Acht*************** 5211c0 526298 526518
6 !!Sehr laaannngggee 526298 6472f0 647110
7 sieben************* 6472f0      0      0
7 fuenf************** 647110      0      0
6 Sechs************** 526518 5266f8 647098
7 Acht*************** 5266f8      0      0
7 Zwei*************** 647098 647430 647228
8 fuenf************** 647430      0      0
8 Zwei*************** 647228      0      0
3 neun*************** 521058 521170 521080
4 Sechs************** 521170 526338 526428
5 Vier*************** 526338 5264a0 5269a0
6 drei*************** 5264a0 647598 526a18
7 Vier*************** 647598      0      0
7 Acht*************** 526a18      0      0
6 fuenf************** 5269a0 6471d8 6474f8
7 !!Sehr laaannngggee 6471d8      0      0
7 !!Sehr laaannngggee 6474f8      0      0
5 !!Sehr laaannngggee 526428 5267e8 526838
6 Vier*************** 5267e8 647160 527028
7 sieben************* 647160      0      0
7 !!Sehr laaannngggee 527028      0      0
6 Sechs************** 526838      0      0
4 !!Sehr laaannngggee 521080 5262c0 526310
5 eins*************** 5262c0 526568 526810
6 Acht*************** 526568 6476b0      0
7 eins*************** 6476b0      0      0
6 fuenf************** 526810 526f88 6471b0
7 Sechs************** 526f88      0      0
7 neun*************** 6471b0      0      0
5 drei*************** 526310 526630 5264c8
6 drei*************** 526630 526ec0 647188
7 eins*************** 526ec0      0      0
7 Acht*************** 647188      0      0
6 Vier*************** 5264c8 5268d8 526658
7 !!Sehr laaannngggee 5268d8 526fd8      0
8 Acht*************** 526fd8      0      0
7 Vier*************** 526658 526f10      0
8 drei*************** 526f10      0      0

C:\Users\MyName\Desktop>

[/SPOILER]
Fragen:
(0) Wer einen Baum mit Höhe > 9 bekommt (0-basiert oder wie auch immer), bei dem stimmt etwas mit dem Zufall nicht...

Arbeite ich so mit den Zeigern korrekt?
Muss ich in Zeile 25 immer nod->str[i] = '\0'; schreiben, oder ist das 20ste Zeichen immer '\0'?
Kann ich nicht einfach einen Zeiger auf "dies ist ein String" zuweisen?
Lässt sich ab Zeile 30 das "if-else if-else"-Konstrukt vereinfachen?
Ist es sinnvoll, schon in der Funktion add Speicherplatz zu allokieren/allozieren und einen Zeiger darauf bei jedem Aufruf von add1 mitzugeben? Schließlich wird dann jedes mal kopiert...
Was könntet ihr anhand der obigen Ausgabe über mein System sagen?

regInfo000*

sry for doppelpost...

/*
 * Kommentar
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define STRING_SIZE 20

typedef struct Node {
	char str[STRING_SIZE];
	struct Node *left;
	struct Node *right;
} Node;

Node *tree = NULL;

void cop1(char str[], Node *newNod) {
	int i;
	for (i = 0; str[i] != '\0' && i < STRING_SIZE - 1; i++)
		newNod->str[i] = str[i];
	for(; i < STRING_SIZE - 1; i++) /* optionally */
		newNod->str[i] = '*';
	newNod->str[i] = '\0';
	newNod->left = NULL;
	newNod->right = NULL;
}

int trueOrFalse(void) {
	return rand() % 2;
}

void add1(Node *nod, Node *newNod) {
	if (nod->left == NULL)
		if (nod->right == NULL)
			if (trueOrFalse())
				nod->left = newNod;
			else
				nod->right = newNod;
		else
			nod->left = newNod;
	else if (nod->right == NULL)
		nod->right = newNod;
	else if (trueOrFalse())
		add1(nod->left, newNod);
	else
		add1(nod->right, newNod);
}

void add(char str[]) {
	Node *newNod = (Node *) malloc(sizeof(Node));
	cop1(str, newNod);
	if (tree == NULL) {
		tree = newNod;
		return;
	}
	add1(tree, newNod);
}

void printTree1(int *val, Node *nod) {
	if (nod == NULL)
		return;
	printf("%-4i%-19s%7p%7p%7p\n", ++(*val), nod->str, nod, nod->left, nod->right);
	printTree1(val, nod->left);
	printTree1(val, nod->right);
}

void printTree(void) {
	int val = 0;
	printTree1(&val, tree);
}

int compare(char *str1, char *str2) {
	int i;
	int len = sizeof(str1);
	int len2 = sizeof(str2);
	if (len2 < len)
		len = len2;
	for (i = 0; i < len; i++)
		if (str1[i] != str2[i])
			return 0;
	return 1;
}

char * search1(char *str, int *i, char **ptrptr) {
	return "not yet implemented";
}

char * search(char *str) {
	int i = 0;
	char *ptr = "";
	char **ptrptr = &ptr;
	if (tree == NULL || compare(tree->str, str))
		return "";
	return search1(str, &i, ptrptr);
}

int main(void) {

	getchar();
	return EXIT_SUCCESS;
}

Ich möchte jetzt in Zeile 90 die Funktion search implementieren. Wenn die Wurzel des Baums gleich dem String str ist, soll "" zurückgegeben werden. Wenn der Baum so aufgebaut ist:

"a"
  / \
"b" "c"
/ \  / \
|"d" | |

und str=="d" ist, dann soll "LR" für Links und Rechts zurückgegeben werden. Usw.

Welche Parameter muss die Funktion search1 haben?

char **ptrptr dachte ich mir, damit an den String *ptrptr ein Zeichen mittels malloc angehängt werden kann...

Danke noch mal fürs Drüberschauen

regInfo000*

Kann jmd. diese drei Funktionen implementieren:

int compare(char *str1, char *str2) {
	int i;
	int len = sizeof(str1);
	int len2 = sizeof(str2);
	if (len2 < len)
		len = len2;
	/* len /= sizeof(char); */
	for (i = 0; i < len; i++)
		if (str1[i] != str2[i])
			return 0;
	return 1;
}

void appendChar(char **ptrptr, char ch) {

}

void replaceChar(char **ptrptr, char ch) {

}

void removeChar(char **ptrptr) {

}

int search1(char *str, Node *nod, char **ptrptr) {
	if (nod == NULL)
		return 0;
	if (compare(str, nod->str))
		return 1;
	appendChar(ptrptr, 'L');
	if (search1(str, nod->left, ptrptr ))
		return 1;
	replaceChar(ptrptr, 'R');
	if (search1(str, nod->right, ptrptr))
		return 1;
	removeChar(ptrptr);
	return 0;
}

char * search(char *str) {
	char *ptr = "";
	char **ptrptr = &ptr;
	search1(str, tree, ptrptr);
	return *ptrptr;
}

append soll das Zeichen ch an ptrptr hängen, replace das letzte Zeichen von ptrptr durch ch ersetzen, remove das letzte Zeichen von ptrptr entfernen/beseitigen/wie auch immer.

Leider hab' ich zu spät bemerkt, das der Wertebereich von char implementationsabhängig ist, d. h., bei mir ist das der Bereich von -128 bis 127, und nicht von 0 - 255, wie es bei UTF-8 und so der Fall ist. Gibt's 'ne Möglichkeit, alle vVorkommen von char durch z. B. (unsigned char) zu ersetzen?

regInfo000*

Hallo noch mal,

/*
 * Kommentar
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define STRING_SIZE 20

typedef struct Node {
	char str[STRING_SIZE];
	struct Node *left;
	struct Node *right;
} Node;

Node *tree = NULL;

void cop1(char *str, Node *newNod) {
	int i;
	for (i = 0; str[i] != '\0' && i < STRING_SIZE - 1; i++)
		newNod->str[i] = str[i];
	for(; i < STRING_SIZE - 1; i++) /* optionally */
		newNod->str[i] = '*';
	newNod->str[i] = '\0';
	newNod->left = NULL;
	newNod->right = NULL;
}

int trueOrFalse(void) {
	return rand() % 2;
}

void add1(Node *nod, Node *newNod) {
	if (nod->left == NULL)
		if (nod->right == NULL)
			if (trueOrFalse())
				nod->left = newNod;
			else
				nod->right = newNod;
		else
			nod->left = newNod;
	else if (nod->right == NULL)
		nod->right = newNod;
	else if (trueOrFalse())
		add1(nod->left, newNod);
	else
		add1(nod->right, newNod);
}

void add(char *str) {
	Node *newNod = (Node *) malloc(sizeof(Node));
	cop1(str, newNod);
	if (tree == NULL) {
		tree = newNod;
		return;
	}
	add1(tree, newNod);
}

void printTree1(Node *nod, int *val) {
	if (nod == NULL)
		return;
	printf("%-3i%-19s%7p%7p%7p\n", ++(*val), nod->str, nod, nod->left, nod->right);
	printTree1(nod->left, val );
	printTree1(nod->right, val);
}

void printTree(void) {
	int val = 0;
	printTree1(tree, &val);
}

int compare(char *str1, char *str2) {
	int i;
	int len = sizeof(str1);
	int len2 = sizeof(str2);
	if (len2 < len)
		len = len2;
	/* len /= sizeof(char); */
	for (i = 0; i < len; i++)
		if (str1[i] != str2[i])
			return 0;
	return 1;

 /* printf("%i\n", compare("", ""));          1
	printf("%i\n", compare("eins", "eins"));  1
	printf("%i\n", compare("eins", "einse")); 1
	printf("%i\n", compare("einse", "eins")); 1
	printf("%i\n", compare("e1ns", "einse")); 0
	printf("%i\n", compare("einse", "e1ns")); 0 */
}

void appendChar(char **ptrptr, char ch) {
	int i;
	char *ptr = (char *) malloc(sizeof(*ptrptr) + 1);
	for (i = 0; (*ptrptr)[i] != '\0'; i++)
		ptr[i] = (*ptrptr)[i];
	ptr[i++] = ch;
	ptr[i] = '\0';
	free(*ptrptr);
	*ptrptr = ptr;
}

void replaceChar(char **ptrptr, char ch) {
	(*ptrptr)[sizeof(*ptrptr) - 2] = ch;
}

void removeChar(char **ptrptr) {
	int i;
	int len = sizeof(*ptrptr) - 2;
	char *ptr = (char *) malloc(len + 1);
	for (i = 0; i < len; i++)
		ptr[i] = (*ptrptr)[i];
	ptr[i] = '\0';
	free(*ptrptr);
	*ptrptr = ptr;
}

int search1(char *str, Node *nod, char **ptrptr) {
	if (nod == NULL)
		return 0;
	if (compare(str, nod->str))
		return 1;
	appendChar(ptrptr, 'L');
	if (search1(str, nod->left, ptrptr  ))
		return 1;
	replaceChar(ptrptr, 'R');
	if (search1(str, nod->right, ptrptr ))
		return 1;
	removeChar(ptrptr);
	return 0;
}

char * search(char *str) {
	char *ptr = "";
	char **ptrptr = &ptr;
	printf("%i\n", search1(str, tree, ptrptr));
	return *ptrptr;
}

int main(void) {
	int i;
	int array[10];          /* Deklaration */
	int *pointer1, *pointer2;
	pointer1 = array;       /* pointer1 auf Anfangsadresse von array */
	pointer2 = array + 3;   /* pointer2 auf 4.Element von array      */

	array[0]      = 99;     /* array[0] */
	pointer1[1]   = 88;     /* array[1] */
	*(pointer1+2) = 77;     /* array[2] */
	*pointer2     = 66;     /* array[3] */

	for (i = 0; i < 10; i++)
		printf("%5i\n", array[i]);

	for (i = 0; i < 1; i++) {
	add("eins");
	add("Zwei");
	add("drei");
	add("Vier");
	add("fuenf");
	add("Sechs");
	add("sieben");
	add("Acht");
	add("neun");
	add("!!Sehr laaannngggeeer String/Zeichenkette!!");
	}
	printTree();

	printf("%s\n", search("siieben"));

	getchar();
	return EXIT_SUCCESS;
}

Jetzt druckt er mir anstatt des leeren Strings immer "LL". Was ist an appendChar und/oder replaceChar und/oder removeChar falsch?

Angenommen, sizeof(str) == 20, dann Index 0 - 18 Zeichen und Index 19 '\0'. Also muss ich malloc mit 20 -2 +1 aufrufen, kopieren (zuweisen) und Index 18 '\0' zuweisen. Richtig?

Andere Frage: Mir ist aufgefallen, nicht in welcher Reihenfolge man formale Parameter von Funktionen/Prozeduren schreiben sollte.
Bsp.: int search1(char *str, Node *nod, char **ptrptr)

Mir wurde gesagt, übersichtlich, lesbar und wenn möglich von links nach rechts (Funktionsaufrufe) lesbar. Was bedeutet das konkret? Oder gibt es eine Konvention diesbezüglich?

Danke, wer den jetzt doch recht lang gewordenen Quelltext einmal überfliegen tut..

Grüße, Euer [ regInfo000? ]

sizeof() bei einem Pointer, gibt dir die Größe des Pointers, nicht die Größe des Speichers auf den er zeigt. (Geht auch nicht, das kann man nicht rausfinden)

sizeof(Zeiger) ist i.A 4 bei 32-Bit Systemen und 8 bei 64-Bit Systemen.

regInfo000*

Also muss ich quasi "händisch"/manuell über die Zeichenkette bis zu dem '\0'-Zeichen iterieren?

Danke erst mal

Ist bei C-Strings eh sinnvoller, da das Array ja auch größer sein kann als der String darin.

Warum nimmst du nicht strcmp() für den Vergleich (dafür ist es im Standard).
Oder schaust dir mal den Code dafür an.

Wutz

Globale Variablen sind Schrott.
Das wird nicht dadurch besser, dass auch verkettete Listen hinzukommen.
Potenziert werden deine Probleme auch noch durch mangelndes Verständnis von Array und Zeiger, wie du mit deiner sizeof-Verwendung dokumentierst.

Definiere dir deinen Stringtyp und verwalte diesen in einer einfachen Liste, die sich die Anzahl der Elemente merkt:

#define STRING_SIZE 20

typedef char MeinString[STRING_SIZE+1];
typedef struct Node {
    MeinString *liste;
    size_t x;
} Liste;

Als Ergebnis reduzierst du den Codeumfang erheblich, dafür steigerst du die Übersichtlichkeit.

regInfo000*

Aha, hier schreibt wieder jmd., der voll die Ahnung hat...

Nur zur kenntnisnahme, ich habe sizeof entfernt und du hast mit typedef struct .... .... bereits eine globale Variable definiert.

(Einfach) Verkettete Listen sind was für Langweiler (und in jeder Laufzeitanalyse unterirdisch). Mindestens ein BinTree sollte drin sein.

Verbessert sieht das jetzt so aus (die unsinnigen Ausgaben in der main seien mal dahingestellt):

/*
 * Kommentar
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define STRING_SIZE 20

typedef struct Node {
	char str[STRING_SIZE];
	struct Node *left;
	struct Node *right;
} Node;

Node *tree = NULL;

void cop1(char *str, Node *newNod) {
	int i;
	for (i = 0; str[i] != '\0' && i < STRING_SIZE - 1; i++)
		newNod->str[i] = str[i];
	for(; i < STRING_SIZE - 1; i++) /* optionally */
		newNod->str[i] = '*';
	newNod->str[i] = '\0';
	newNod->left = NULL;
	newNod->right = NULL;
}

int trueOrFalse(void) {
	return rand() % 2;
}

void add1(Node *nod, Node *newNod) {
	if (nod->left == NULL)
		if (nod->right == NULL)
			if (trueOrFalse())
				nod->left = newNod;
			else
				nod->right = newNod;
		else
			nod->left = newNod;
	else if (nod->right == NULL)
		nod->right = newNod;
	else if (trueOrFalse())
		add1(nod->left, newNod);
	else
		add1(nod->right, newNod);
}

void add(char *str) {
	Node *newNod = (Node *) malloc(sizeof(Node));
	cop1(str, newNod);
	if (tree == NULL) {
		tree = newNod;
		return;
	}
	add1(tree, newNod);
}

void printTree1(Node *nod, int *val) {
	if (nod == NULL)
		return;
	printf("%-3i%-19s%7p%7p%7p\n", ++(*val), nod->str, nod, nod->left, nod->right);
	printTree1(nod->left, val );
	printTree1(nod->right, val);
}

void printTree(void) {
	int val = 0;
	printTree1(tree, &val);
}

int compare(char *str1, char *str2) {
	int i;
	for (i = 0; str1[i] != '\0' && str2[i] != '\0'; i++)
		if (str1[i] != str2[i])
			return 0;
	return 1;

 /* printf("%i\n", compare("", ""));          1
	printf("%i\n", compare("eins", "eins"));  1
	printf("%i\n", compare("eins", "einse")); 1
	printf("%i\n", compare("einse", "eins")); 1
	printf("%i\n", compare("e1ns", "einse")); 0
	printf("%i\n", compare("einse", "e1ns")); 0 */
}

int len(char *str) {
	int i;
	for (i = 0; str[i] != '\0'; i++)
		;
	return ++i;
}

void appendChar(char **ptrptr, char ch) {
	int i;
	int laen = len(*ptrptr);
	char *ptr = (char *) malloc(laen + 1);
	for (i = 0; (*ptrptr)[i] != '\0'; i++)
		ptr[i] = (*ptrptr)[i];
	ptr[i++] = ch;
	ptr[i] = '\0';
	free(*ptrptr);
	*ptrptr = ptr;
}

void replaceChar(char **ptrptr, char ch) {
	(*ptrptr)[len(*ptrptr) - 2] = ch;
}

void removeChar(char **ptrptr) {
	int i;
	int laen = len(*ptrptr) - 2;
	char *ptr = (char *) malloc(laen + 1);
	for (i = 0; i < laen; i++)
		ptr[i] = (*ptrptr)[i];
	ptr[i] = '\0';
	free(*ptrptr);
	*ptrptr = ptr;
}

int search1(char *str, Node *nod, char **ptrptr) {
	if (nod == NULL)
		return 0;
	if (compare(str, nod->str))
		return 1;
	appendChar(ptrptr, 'L');
	if (search1(str, nod->left, ptrptr  ))
		return 1;
	replaceChar(ptrptr, 'R');
	if (search1(str, nod->right, ptrptr ))
		return 1;
	removeChar(ptrptr);
	return 0;
}

char * search(char *str) {
	char *ptr = "";
	char **ptrptr = &ptr;
	printf("%i\n", search1(str, tree, ptrptr));
	return *ptrptr;
}

int main(void) {
	int i;
	int array[10];          /* Deklaration */
	int *pointer1, *pointer2;
	pointer1 = array;       /* pointer1 auf Anfangsadresse von array */
	pointer2 = array + 3;   /* pointer2 auf 4.Element von array      */

	array[0]      = 99;     /* array[0] */
	pointer1[1]   = 88;     /* array[1] */
	*(pointer1+2) = 77;     /* array[2] */
	*pointer2     = 66;     /* array[3] */

	for (i = 0; i < 10; i++)
		printf("%5i\n", array[i]);

	srand((unsigned) time(NULL));

	for (i = 0; i < 1; i++) {
	add("eins");
	add("Zwei");
	add("drei");
	add("Vier");
	add("fuenf");
	add("Sechs");
	add("sieben");
	add("Acht");
	add("neun");
	add("!!Sehr laaannngggeeer String/Zeichenkette!!");
	}
	printTree();

	printf("%i\n", compare("", ""));
	printf("%i\n", compare("eins", "eins"));
	printf("%i\n", compare("eins", "einse"));
	printf("%i\n", compare("einse", "eins"));
	printf("%i\n", compare("e1ns", "einse"));
	printf("%i\n", compare("einse", "e1ns"));

	printf("%s\n", search("Acht"));

	for (i = 0; i < 10; i++)
		printf("%i\n", trueOrFalse());

	getchar();
	return EXIT_SUCCESS;
}

Wutz

regInfo000? schrieb:

Nur zur kenntnisnahme, ich habe sizeof entfernt und du hast mit typedef struct .... .... bereits eine globale Variable definiert.

Du hast keine Ahnung.
Du hast keine Ahnung von typedef, Deklaration und Definition.
Du hast keine Ahnung, wovon du redest.

Du musst dir dringend realloc ansehen!
Das ist eine Standardfunktion.

Den Speicher vom Stringliteral aus Zeile 139 (der Leerstring) willst du irgendwann in Zeile 104 frei geben. Das geht nicht!

Eine void-Funktion mit einem Doppelzeiger als Paramter ist schlechtes Design.

regInfo000*

Streng genommen wird free("") nicht aufgerufen, denn vor jedem removeChar wird einmal append/replaceChar aufgerufen... Aber vom Design her ist das nicht so Banane.

Aber dann bleibt eigentlich nur ein Array mit vorher festgelegter Größe oder ein pointer auf irgendeine Datenstruktur oder eine globale Variable übrig.

Bei einer festgelegten Größe darf der Binärbaum nicht tiefer/höher als z. B. 20 sein. (2^20 ist auch schon viel, aber ein Binärbaum kann immer auch eine Liste sein.)

Es ginge auch ein integer typ, 0==nicht gefunden, 1==Wurzel, 5==L usw.

Selbstverständlich ist das neu allokieren und kopieren nicht gerade schnell, aber zum lernen ist das 1a.

Bibliotheksfunktionen, Schnittstellen oder wie auch immer kommen erst dran, wenn ich die einfachen Sachen gelernt habe.

Frage,: was ist zulässig (was passiert nach der Abarbeitung einer Funktion):

return &321;

int i = 321;
return &321;

int i = 321;
return i;

?

Ich muss das wissen, ob ich z. B.:

char *ptr = "";
    char **ptrptr = &ptr;
    doSomethingWith(ptrptr);
    return ptr or *ptrptr;

schreiben darf, wegen automatischen Variablen und so etwas. - Danke.

regInfo000? schrieb:

Streng genommen wird free("") nicht aufgerufen, denn vor jedem removeChar wird einmal append/replaceChar aufgerufen..

Die Zeile 104 ist in appendChar.
Aufrufreihenfolge ist: search (Z141)-> search1 (Z128)-> appendChar (Z104)-> free -> bang!

Dein Code gekürzt:

char *ptr = NULL;  // handle it
    doSomethingWith(&ptr);
    return ptr;  // der Zeiger ptr hört hier auf zu existieren, aber nicht das, worauf er zeigt (wegen malloc aus doSomethingWith).

regInfo000*

Nabend,

ich möchte eine Zahl (int) als Binärzahl / in Binärformat der Länge 2 per/via printf() in ANSI-C auf dem Terminal ausgeben.

Hintergrund:

int i = ((a-1)<<1)|(b-1);
printf("Mode: %b\n", i);

%2b funktioniert nicht.

Querverweis (nicht Stack Overflow): http://www.osxentwicklerforum.de/index.php?page=Thread&threadID=806

Was muss ich jetzt zu tun?

Erstes Programm: &quot;Laufzeit&quot;fehler und Projektidee

Erstes Programm: "Laufzeit"fehler und Projektidee