Sortierte Liste in C

[mihe7]

Wenn ich Dich richtig verstehe, sieht Dein Baum also so aus:

       next
  A1 --------> A2
   |             \____
   | son           son\      next
   v     next          A2.1 -----> A2.2
  A1.1 --------> A1.2
   |
   | son
   |
   v       next
  A1.1.1 --------> A1.1.2

Effizient Suchen ist da aber nicht drin...

Um im Baum k den Wert w zu finden, sollte folgender Pseudocode funktionieren:

suche(k, w) {
    if (k == null || k.wert == w) { return k; }
    ergebnis = suche(k.son, w); // durchsuche Sohn
    if (ergebnis == null) {
        ergebnis = suche(k.next, w); // durchsuche nächsten Knoten
    }
    return ergebnis;
}

 

[ocsme]

Das werde ich morgen mal ausprobieren.
Ich hab oben 2x return gehabt statt es einer Variablen zu zuordnen und diese zurück zu geben grrr... was hab ich da wieder für ein Käse gemacht. Naja werd es morgen Probieren bin jetzt zu Müde.

Eine Frage hätte ich noch zu C. Wenn ich ein Array der größe [16] in der struct vereinbare, die Eingabe des Strings aber größer später ist als 16 dann printet der mir ja komische Zeichen.
Hatte versucht das weg zu bekommen mit if(MAX_SIZE(16)-1 > strlen(string))array[15] = '\0';
Doch dann bekomme ich gar keine Ausgabe mehr
Wenn nicht muss ich es morgen mal wieder hinfrickeln das ganze habe ich nämlich wieder gelöscht gehabt und dachte mir dann naja darf man eben nichts eingaben was größer als 15 Zeichen ist

PS:
Also die suche und das einfügen scheinen jetzt zu klappen Danke.
Hab es mal probiert werde es morgen aber nochmal Testen

 

[mihe7]

Wenn ich ein Array der größe [16] in der struct vereinbare, die Eingabe des Strings aber größer später ist als 16 dann printet der mir ja komische Zeichen.

Du meinst bei printf("%s")? Ggf. ja

Das ist ganz einfach: in C wird eine Zeichenkette durch ein 0-char beendet. Wenn Du eine Zeichenkette haben willst, die 16 Zeichen aufnimmt, muss für ein Zeichen (0-char) mehr Platz reserviert werden.

Schreibst Du ein Array voll, dann wird der 0-char hinter dem Array im Speicher platziert, bei einer Struktur im nächsten Element:

#include <stdio.h>
#include <memory.h>

typedef struct {
    char z1[4];
    char z2[4];
} struktur;

int main()
{
    struktur x;
    memset(&x, 'X', sizeof(struktur));
    x.z1[3] = 0;
    x.z2[3] = 0;
    printf("%s\n%s\n", x.z1, x.z2);

    scanf("%s", x.z1);
    printf("%s\n%s\n", x.z1, x.z2);
}

Wenn Du das ausführst, hast Du Platz für zwei Strings der Länge 3. Am Anfang werden beide mit XXX initialisiert.

Gibst Du nun drei Zeichen ein, z. B. AAA ein, ist alles so, wie es sein soll, und es wird

AAA
XXX

ausgegeben.

Gibst Du dagegen vier Zeichen ein, z. B. AAAA, dann wird nur noch AAAA ausgegeben. Der zweite String ist "leer". Warum?

Der Speicher sieht in etwa so aus:

 z1   z2 
0123 0123 Indizes
------------------------------
XXX0 XXX0 Initialzustand
AAA0 XXX0 Nach Eingabe von 3 A
AAAA 0XX0 Nach Eingabe von 4 A
AAAA A0X0 Nach Eingabe von 5 A

Wenn Du jetzt überlegst, dass printf() bis zum Erreichen des 0-Zeichens ausgibt, dann wird die Sache klar. Kannst Du anhand des Programms überprüfen. Du solltest aber nicht mehr als 7 Zeichen eingeben, denn sonst wird einfach der aktuelle Inhalt Deines Speichers in Form von Zeichen ausgegeben, bis eine 0 erreicht wird oder das Betriebssystem einen Seitenzugriff verhindert.

 

[ocsme]

Danke @mihe7 super erklärt und das auch noch um diese Uhrzeit

Eine Doofe frage hätte ich noch dazu. Es geht hier mehr um das Thema Sicherheit. Sagen wir mal wie hätten so eine Struktur:

struct Test {
    char value[16];
};

struct Test init(char *name) {
    struct Test erg;
    strcpy(erg.value, name);
    return erg;
}

int main(void) {

    struct Test a = init("Hallo");
    printf("%s\n", a.value);
    struct Test b = init("So und jetzt mehr"); //Hier würden mehr als 16 Zeichen gelesen werden was ein Überlauf provoziert
    printf("%s\n", b.value);

    return 0;
}

Diesen Überlauf kann ich doch dann so z. B. in der init() Methode verhindern oder ist daran auch etwas Falsch?

struct Test init(char *name) {
    struct Test erg;
    int i = strlen(name); //zählt ohne den '\0'
    strcpy(erg.value, name);
    if (i > 16 - 1)
        erg.value[15] = '\0';
    return erg;
}

Natürlich würde dadurch der rest des Strings verloren gehen bzw. der rest würde zwar fürs erst noch im Speicher hinten dran stehen doch sicherlich nicht sehr lange, oder könnte man dadurch schon die Software angreifen?

Dann hätte ich noch diese Variante die mir eingefallen ist als ich diesen Beitrag geschrieben habe:

struct Test init(char *name) {
    struct Test erg;
    int i = strlen(name); //zählt ohne den '\0'
    strncpy(erg.value, name, 15);
    if (i < 15)
        erg.value[i] = '\0';
    return erg;
}

Das letzte gefällt mir am besten
Da dort gleich von vorne rein verhindert wird das mehr Zeichen als gewollt geschrieben werden dürfen

 

[mihe7]

Natürlich würde dadurch der rest des Strings verloren gehen bzw. der rest würde zwar fürs erst noch im Speicher hinten dran stehen doch sicherlich nicht sehr lange, oder könnte man dadurch schon die Software angreifen?

Die bleiben ja im Speicher stehen Das Schreiben der 0 "kürzt" ja nichts, sondern sorgt nur dafür, dass dort eine 0 steht. Was vorher geschrieben wurde, bleibt im Speicher und genau so entstehen dann Sicherheitslücken. Beispielsweise kann auf diese Weise die Rücksprungadresse eines Funktionsaufrufs verändert werden. Moderne Compiler haben Gegenmaßnahmen dafür.

Da dort gleich von vorne rein verhindert wird das mehr Zeichen als gewollt geschrieben werden dürfen

So ist das richtig.

 

[ocsme]

Guten Abend,
ich sitze schon wieder an einem String Problem
Was ich versuche ist eine Methode zu schreiben die ein String (char *string) übergeben bekommt und diesen String dann Wort weiße als Liste abspeichert.

Die Strukturen sehen so aus:

typedef struct Node {
    char value[WORD_SIZE];
    struct Node *next;
    struct Node *prev;
}node;

typedef struct List {
    node *anfang, *ende;
    int anzahl;
}list;

Und meine Methode derzeit so:

list createListFromArray(char *array) {
    int i, j = strlen(array);
    char string[j];
    strcpy(string, "");
    list erg = createEmptyList();
    for (i = 0; i < j; i++) {
        if (array[i] == ' ') {
            insertWordAtFront(&erg, string);
        }
        string[i] = array[i];
    }
    return erg;
}

Mit dieser Murks Methode habe ich aber 2 Probleme.
1. Ich bekomme viel misst ausgegeben da ich den char string ja so groß mache wie den übergebenen Array-String. Weiß leider nicht wie ich den char string[j] in jedem durchlauf auf Null setzen kann bzw. bräuchte ich für jeden Satz durchlauf ein neuen String mit der passenden größe des einzelnen Wort ein Beispiel:

Das ist das Haus vom Nikolaus.
Bräuchte ich 6 einzelne Knoten mit den größen 3, 3, 3, 4, 3, 9 bzw. 10 hier ist der Satz zu ende also '\0'

2. läuft derzeit die Methode nur bis zu einem 'Leerzeichen'. Wie erkenne ich hierbei in C das ich an einem ende eines Wortes wäre.

Vielleicht könnt Ihr mir hierbei nochmals unter die Arme greifen

Danke im voraus

mfg

 

[mihe7]

Die Strukturen sehen so aus:

Wenn Du die Werte nicht aus die Länge des char-Arrays (value) begrenzen willst, mach aus value einen Zeiger:

typedef struct Node {
    char *value;
    struct Node *next;
    struct Node *prev;
}node;

Wenn Du von einem gegebenen char* eine Kopie ablegen willst, reservierst Du für value ausreichend Speicher (malloc) und kopierst mittels strncpy.

 

[ocsme]

mhhh... ich wollte in der Struktur das Array eigentlich drin lassen
Denn durch den Satz muss ich ja eh immer laufen um herauszufinden wieviele Wörter im Satz stehen und wie lang diese dann sind mhhh...
Wie bekomme ich den einzelne Strings in der Länge erstellt wie lang eben ein einzelnes Wort ist?

Also nehmen wir mein Beispiel von oben:
Das ist das Haus ...
Dann wäre der erste String ja 3 Wörter lang.
Kann ich dann nicht irgendwie über strncpy es machen?
Man erstellt zwei string Variablen die eine nutzt man als tmp und übertragt den ganzen Satz nach und nach in tmp. Die andere String Variable nimmt man dann sobald man auf ein ' ' kommt benutzt man strncpy(string, tmp, i) <- wobei ich jetzt wieder nicht weiß welche Reihenfolge hier wo rein kopiert wird müsste ich mir anschauen wie die strncpy dokumentiert ist. Was ich noch gerade nicht weiß ist die Rechenformschrift denn das i wandert ja weiter doch ich muss den alten i Wert ja abziehen damit ich nicht wie oben immer wieder den ersten Anfang mit Kopiere

ob das klappen könnte falls man es hier versteht?
LG

 

[ocsme]

Nö so bekomme ich nur eine Endlosschleife Bekomme es so nicht hin! Das lasse ich erst einmal. Man die Strings in C sind ja mal mega anstrengend

char word[] = "Das sollte ein Test werden.";
    list erg = createListFromArray(word);
    printList(erg);

list createListFromArray(char array[]) {
    list erg = createEmptySentence();
    char delimiter[] = " ";
    char *ptr = NULL;
    ptr = strtok(array,delimiter);
    while(ptr != NULL) {
        insertWordAtFront(&erg, ptr);
        ptr = strtok(array,delimiter);
    }
    return erg;
}

 

[kneitzel]

Also array ist ja unverändert - daher wird strtok(array,delimiter); immer NULL oder eben kein NULL zurück geben.

Daher ist in der while Scheife das array als Parameter nicht korrekt.

http://www.c-howto.de/tutorial/strings-zeichenketten/string-funktionen/string-zerteilen/ ist evtl. hilfreich.

 

[ocsme]

Danke für die schnelle Antwort.

also jetzt geht es. Wieso verstehe ich zwar noch nicht so ganz aber es geht
Eine Frage habe ich aber noch. Wenn ich der Methode einen char *ptr übergebe geht es nur wenn ich in meiner main ein char string[] = "Kurt Kanns 555678 DE"; erstelle. Wieso geht es nicht so: char *k = "Kurt Kanns";?

list createListFromArray(char *array) <- so sieht der Methodenkopf aus wieso geht dann nicht das hier? char *k = "Kurt Kanns"

 

[kneitzel]

Ich nehme einmal an, dass Du einfach den Aufruf in der while Schleife angepasst hast und Du nicht mehr array sondern NULL übergeben hast.

Und der Link, den ich gegeben habe, erläutert es doch auch:

Beim ersten Aufruf muss strtok mit einem String initialisiert werden. Die Rückgabe ist hierbei der erste Abschnitt. Bei Folgeaufrufen wird statt string der NULL Wert übergeben, da strtok bereits initialisiert ist und intern einen Zeiger auf string gespeichert hat.

list createListFromArray(char *array) <- so sieht der Methodenkopf aus wieso geht dann nicht das hier? char *k = "Kurt Kanns"

Wieso sollte das nicht gehen? https://www.prismnet.com/~mcmahon/Notes/strings.html gibt das als Beispiel an, aber wir probieren es noch einmal:
test.c:

#include <stdio.h>

void main() {
   char *k = "Kurt kanns";
   printf(k);
}

dann noch:
gcc -o test test.c
./test

Und schon steht da "Kurt kanns".

 

[ocsme]

Bei mir geht das nicht. Er gibt dann mal wieder nichts mehr aus. Ich muss aufhören denn bin wieder total verwirrt

Also erst einmal hier die wie es bei mir aussieht. Vielleicht geht es bei dir ja

    char string[] = "Kurt Kanns 555678 DE";
    char *k = "Kurt Kanns";
    list erg = createSentenceFromArray(string);
    printList(erg);
    printf("\n");
    list tmp = createSentenceFromArray(k);
    printList(tmp); //wird nicht gedruckt!!!

so sieht die Methode ja dazu aus:

//list createSentenceFromArray(char *array) {
//    list erg = createEmptySentence();
//    char delimiter[] = " ";
//    char *ptr = NULL;
//    ptr = strtok(array,delimiter);
//    while(ptr != NULL) {
//        insertWordAtFront(&erg, ptr);
//        ptr = strtok(NULL,delimiter);
//    }
//    return erg;
//}

Denn ich habe eine weitere Methode dazu geschrieben um ein Array von node zu übergeben und diese node dann in meine Liste einzufügen.
Erstes Problem daran ich hab 20 Minuten gebraucht bis ich das node[] initialiserit bekommen habe. Wollte es per for Schleife machen doch das hat nicht geklappt
Zweites Problem wieso muss hier an der Stelle der Punkt hin?

list createSentenceFromArray(node word[], int pos) {
    list erg = createEmptySentence(); int i;
    for(i = 0; i < pos; i++)
        insertWordAtEnd(&erg, word[i].value); //warum kommt hier der Punkt hin?

    return erg;
}

Ein Array ist doch nichts weiter als ein Pointer oder?
node *word sollte oben im Methodenkopf also auch funktionieren. Wieso muss man dann word.value schreiben hab es versucht so umzuschreiben das geht aber nicht! *(word+i)->value geht auch nicht so *(word+i).value!
Das hier hat mich mehr verwirrt als es mir etwas gebracht hat so ein misst aber auch

So habe ich es dann Initialisiert am Ende da ich nicht mehr weiter kam

node a[2];
    node test = {"Test", NULL, NULL};
    node test2 = {"Test2", NULL, NULL};
    a[0] = test;
    a[1] = test2;
    list t = createSentenceFromArray(a, 2);
    printList(t);

 

[kneitzel]

Zugriff auf Elemente:
a) wenn du einen Pointer hast, also z.B. node *pnNode: pnNode->element
b) wenn du eine instanz hast: node nNode: nNode.element
Also bei pointer -> und bei instanz .

Bezüglich der Ausgabe:
Hast du es wieder aus eclipse gestartet? Mach es dann direkt von der Kommandozeile! Oder besorg Dir eine andere IDE, wenn eclipse so spinnt.

 

[ocsme]

a) wenn du einen Pointer hast, also z.B. node *pnNode: pnNode->element
b) wenn du eine instanz hast: node nNode: nNode.element

Ja das ist mir irgendwie klar
Doch ein Array ist doch eigentlich auch ein Pointer deswegen dachte ich dort muss auch der -> hin

Hast du es wieder aus eclipse gestartet? Mach es dann direkt von der Kommandozeile! Oder besorg Dir eine andere IDE, wenn eclipse so spinnt.

Ja hab es wieder wie alles aus Eclipse gestartet. Dann sollte ich das mal ausprobieren ohne Eclipse.

Danke nochmals

Achso weisst du wie ich mein node word[] besser initialisieren kann?

LG

 

[kneitzel]

Ja das ist mir irgendwie klar
Doch ein Array ist doch eigentlich auch ein Pointer deswegen dachte ich dort muss auch der -> hin

Also word ist das Array und damit wäre es ein Pointer. Das word[i] ist dann aber ein konkretes Element. Also der Pointer aufgelöst. Das word[i] ist nichts anderes als ein *(word+i), was dann ja zeigt: Das ist nicht mehr der Pointer sondern das Element.

Und auf das (word+i) noch einmal zurück kommen:
word ist ein pointer auf das erste Element eines Arrays.
(word+i) ist ein Zeiger auf das ite Element des Arrays.
Nun kannst Du auf Elemente zugreifen. Bei einem Pointer wäre dies dann z.B. (word+i)->value
Wenn Du einen Pointer hast, dann kannst Du mit * das Element dahinter bekommen, also ist *(word+i) das Element des Arrays.
Wenn Du da nun .value anhängen willst, dann geht das nicht *(word+i).value ist für den Compiler *((word+i).value), d.h. er würde da den Pointer nehmen und Zugriff als Element -> Das wird nichts. Aber wir können da natürlich Klammern setzen:
(*(word+i)).value.
Aber das ist natürlich Quatsch - da nutzt man natürlich entweder word.value oder von mir aus noch (word+i)->value, was ich aber unleserlich finde.

Ja hab es wieder wie alles aus Eclipse gestartet. Dann sollte ich das mal ausprobieren ohne Eclipse.

Ich habe keine Ahnung, was da mit Deinem Eclipse los ist, aber ich habe Eclipse auch noch nie mit C oder C++ genutzt. Da hatte ich damals unter Windows Visual Studio und unter Linux KDevelop oder Anjuta im Einsatz. Aber es gibt auch noch einige andere IDEs, die gerade für Anfänger gut sein könnten, da sie nicht so überladen sind. CodeBlocks fällt mir da z.B. gerade ein....

Achso weisst du wie ich mein node word[] besser initialisieren kann?

Wie initialisierst Du das derzeit? Ich habe gerade keinen wirklichen Überblick, was Du da wie machst. Ich habe aber da mal noch paar Aussagen / Fragen von Dir aufgearbeitet, auf die ich vorher noch nicht eingegangen bin.

 

[ocsme]

Also word ist das Array und damit wäre es ein Pointer. Das word[i] ist dann aber ein konkretes Element. Also der Pointer aufgelöst. Das word[i] ist nichts anderes als ein *(word+i), was dann ja zeigt: Das ist nicht mehr der Pointer sondern das Element.

Stimmt deswegen auch der .

Was mit meinem Eclipse dann los ist weis ich auch nicht. Vielleicht sollte ich die Programme öfters dann über die Konsole laufen lassen.

Derzeit Initialisierie ich das node word[] so:
in meiner main:

node a[2];
    node test = {"Test", NULL, NULL};
    node test2 = {"Test2", NULL, NULL};
    a[0] = test;
    a[1] = test2;
    list t = createSentenceFromArray(a, 2);
    printList(t);

Mein Node sieht so aus:

typedef struct word {
    char value[WORD_SIZE];
    struct word *next;
    struct word *prev;
}node;

Ich wollte es in einer Schleife Initialisieren geht das Überhaut in C?

Danke.

 

[kneitzel]

Also bezüglich des Initialisierens habe ich noch immer Probleme, Dich so richtig zu verstehen, aber das liegt evtl. daran, dass ich derzeit nicht den Überblick habe, was Du erreichen möchtest....

Aber natürlich kann man auch in C ein Array in einer Schleife initialisieren. (Generell geht alles, was in Java und Co geht, auch in C/C++. Aber natürlich ist dies ggf. etwas umständlicher. Aber Java ist ja auch irgendwie entwickelt worden und das was Java Compiler und JVM machen, geht natürlich auch in C ... Egal wie Du etwas schreibst: Am Ende ist es der Computer der irgendwas macht ... Aber das heißt natürlich nicht, dass etwas einfach ist ... )

Also ein Beispiel, wie ein node Array in einer Schleife initialisiert wird:

#include <stdio.h>
 
typedef struct Node {
    char value[100];
    struct Node *next;
    struct Node *prev;
}node;

void main() {
        node array[10];

        for (int i=0; i<10; i++) {
                sprintf(array[i].value, "Element %d", i);
                array[i].next = NULL;
                array[i].prev = NULL;
        }
}

Also Node ist klein bisschen geändert - statt deiner Constante habe ich eine Magic Number ... hab beim Copy & Paste nicht aufgepasst und dann zu faul, erneut zum Browser zu wechseln ...

 

[mihe7]

Eine Frage habe ich aber noch. Wenn ich der Methode einen char *ptr übergebe geht es nur wenn ich in meiner main ein char string[] = "Kurt Kanns 555678 DE"; erstelle. Wieso geht es nicht so: char *k = "Kurt Kanns";?

Erstmal sind

char string[] = "ABCD";
char *k = "ABCD";

zwei unterschiedliche Dinge.

Im ersten Fall erzeugst Du ein Array, das mit den Zeichen aus dem Literal (inkl. der abschließenden 0) initialisiert wird. Im zweiten Fall erzeugst Du einen Zeiger auf ein Literal.

Das Verhalten beim Versuch, ein Literal zu verändern, ist nicht definiert. Der GCC legt das Literal in ein Read-Only-Segment ab, so dass Versuche, das Literal zu verändern, mit einem Speicherzugriffsfehler quittiert werden.

Zur Veranschaulichung:

#include <stdio.h>

int main(int argc, char *argv[]) {
    char string[] = "ABCD";
    char *k = "ABCD";
    char *m = "ABCD";

    printf("%p\n%p\n%p\n", string, k, m);
    return 0;
}

Wenn Du das mit dem GCC übersetzt, wirst Du vermutlich feststellen, dass k und m auf die gleiche Adresse zeigen. Das Literal wird also nur einmal für die beiden Zeiger abgelegt. Jetzt wäre es ziemlich ungünstig, wenn Du über m das Literal ändern könntest, denn dann würde sich automatisch auch k verändern. Insofern macht es durchaus Sinn, dass der Compiler für Literale ein RO-Segment verwendet.

Da strtok die übergebene Zeichenkette verändert, muss die Angabe eines Zeigers auf ein Literal zu einem Speicherzugriffsfehler führen.

 

[kneitzel]

Also da macht es evtl. Sinn, das noch einmal ganz ausführlich zu bringen: http://www.lysator.liu.se/c/c-faq/c-2.html

Da werden viele Punkte durchgesprochen und erläutert, die evtl. beim Verständnis des ganzen Sachverhaltes helfen.

 

[ocsme]

Nochmals Danke an euch beide
Muss mir die Strings, Arrays und Pointer noch einmal anschauen. Bei der ganzen Sache jetzt habe ich mich wieder total verwirrt

Des weiteren war ich wohl etwas vorlaut das ich Bäume rekursiv hin bekomme grr.... ich dachte ich hätte es verstanden :'(

 

[kneitzel]

Evtl. einmal den Link von mir ansehen? Der zeigt das alles recht anschaulich finde ich... Und dann evtl. daran etwas entlang hangeln? Ich habe im Augenblick keinen Ansatz, wo wir für Verwirrung gesorgt haben ....

Ansonsten kann ich dir ggf. auch einmal ein direktes Gespräch anbieten. Das hilft evtl. mehr wie schreiben....

 

[ocsme]

? Ich habe im Augenblick keinen Ansatz, wo wir für Verwirrung gesorgt haben ....

Ohhh.. nicht falsch verstehen. Ihr habt euch ja super nette Mühe gegeben Das ganze liegt an mir!

Bin ja schon einmal froh das wenigstens die paar Listen Algorithmen nun laufen Der Rest ist erst einmal neben Sache.

Ich hätte aber noch ein kleines Problem aber zum Thema Suchbaum. Soll ich ein neues Thema erstellen da es hier ja um die Liste geht und falls jemand auch so ein Problem hat es auch finden kann?
Wollte bei einem Suchbaum eine Methode schreiben die mir den Vaterknoten sucht für den Wert den ich gerne einfügen möchte. Doch irgendwie klappt es Rekursiv mal wieder überhaupt nicht bzw. hab es sogar wieder komplett gelöscht.
Es ist echt zum Haare raufen.

 

[mihe7]

Soll ich ein neues Thema erstellen

Ja, besser ist das.