Erstes Programm: "Laufzeit"fehler und Projektidee

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?

SeppJ

regInfo000? schrieb:

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

Was muss ich jetzt zu tun?

Den verlinkten Thread lesen?

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

Erstes Programm: "Laufzeit"fehler und Projektidee