Baumstruktur anpassen

Joe1903

Mitglied
Hi zusammen,

ich habe unten stehenden Code. Es gibt die Frequency of Occurence von Wörtern absteigend an.Nun möchte ich es aber so anpassen,dass falls die Freqency für 2 Wörter gleich, die Sortierung alphabetisch aufsteigend sein soll.An welcher Stelle kann man das realisieren?
Vielen Dank im Voraus.

C++:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


typedef struct WORD
{
        char *Word;
        size_t Count;
        struct WORD *Left;
        struct WORD *Right;
} WORD;


#define SUCCESS                      0
#define CANNOT_MALLOC_WORDARRAY      1
#define NO_WORDS_ON_INPUT            2
#define NO_MEMORY_FOR_WORDNODE       3
#define NO_MEMORY_FOR_WORD           4


#define NONALPHA "1234567890 \v\f\n\t\r+=-*/\\,.;:'#~?<>|{}[]`!\".$%^&()"


int ReadInputToTree(
        WORD **DestTree,
        size_t *Treecount,
        FILE *Input);

int AddToTree(
        WORD **DestTree,
        size_t *Treecount,
        char *Word);

int WalkTree(
        WORD **DestArray,
        WORD *Word);

int CompareCounts(
        const void *vWord1,
        const void *vWord2);

int OutputWords(
        FILE *Dest,
        size_t Count,
        WORD **WordArray);

void FreeTree(
        WORD *W);

char *dupstr(
        char *s);



main()
{
        int Status = SUCCESS;
        WORD *Words = NULL;
        size_t Treecount = 0;
        WORD **WordArray = NULL;

        if(Status == SUCCESS)
        {
                Status = ReadInputToTree(&Words, &Treecount, stdin);
        }

        if(Status == SUCCESS)
        {
                if(0 == Treecount)
                {
                        Status = NO_WORDS_ON_INPUT;
                }
        }

        if(Status == SUCCESS)
        {
                WordArray = malloc(Treecount * sizeof *WordArray);
                if(WordArray == NULL)
                {
                        Status = CANNOT_MALLOC_WORDARRAY;
                }
        }

        if(Status == SUCCESS)
        {
                Status = WalkTree(WordArray, Words);
        }

        if(Status == SUCCESS)
        {
                qsort(WordArray, Treecount, sizeof *WordArray, CompareCounts);
        }

        if(Status == SUCCESS)
        {
                Status = OutputWords(stdout, Treecount, WordArray);
        }

        if(WordArray != NULL)
        {
                free(WordArray);
                WordArray = NULL;
        }

        if(Words != NULL)
        {
                FreeTree(Words);
                Words = NULL;
        }

        if(Status != SUCCESS)
        {
                fprintf(stderr, "Program failed with code %d\n", Status);
        }
        return (SUCCESS == Status ? EXIT_SUCCESS : EXIT_FAILURE);
}


void FreeTree(
        WORD *W)
{
        if(W != NULL)
        {
                if(W->Word != NULL)
                {
                        free(W->Word);
                        W->Word = NULL;
                }
                if(W->Left != NULL)
                {
                        FreeTree(W->Left);
                        W->Left = NULL;
                }
                if(W->Right != NULL)
                {
                        FreeTree(W->Right);
                        W->Right = NULL;
                }
        }
}


int AddToTree(
        WORD **DestTree,
        size_t *Treecount,
        char *Word)
{
        int Status = SUCCESS;
        int CompResult = 0;

        if(*DestTree == NULL)
        {
                *DestTree = malloc(sizeof **DestTree);
                if(*DestTree == NULL)
                {
                        Status = NO_MEMORY_FOR_WORDNODE;
                }
                else
                {
                        (*DestTree)->Left = NULL;
                        (*DestTree)->Right = NULL;
                        (*DestTree)->Count = 1;
                        (*DestTree)->Word = dupstr(Word);
                        if((*DestTree)->Word == NULL)
                        {
                                Status = NO_MEMORY_FOR_WORD;
                                free(*DestTree);
                                *DestTree = NULL;
                        }
                        else
                        {
                                ++(*Treecount);
                        }
                }
        }
        else
        {
                CompResult = strcmp(Word, (*DestTree)->Word);
                if(0 < CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
                }
                else if(0 > CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
                }
                else
                {
                        ++(*DestTree)->Count;
                }
        }

        return (Status);
}


int ReadInputToTree(
        WORD **DestTree,
        size_t *Treecount,
        FILE *Input)
{
        int Status = SUCCESS;
        char *Buf = NULL;
        size_t bufsize = 0;
        char *Word = NULL;
        char *bufbase = NULL;
        char *tmp = NULL;

        if (Input != stdin)
        {
                size_t tmp = ftell(Input);
                fseek(Input, 0, SEEK_END);
                bufsize = ftell(Input);
                fseek(Input, tmp, SEEK_SET);

                Buf = (char*)malloc(bufsize);
                if (Buf == NULL)
                {
                        return (-1);
                }

                if (fread(Buf, sizeof(char), bufsize, Input) != bufsize)
                {
                        printf("The promised amount was not read.\n");
                }
        }
        else
        {
                bufsize = 256;
                Buf = calloc(bufsize, sizeof(char));
                if (Buf == NULL)
                {
                        return (-1);
                }
                bufbase = Buf;
                while (fgets(Buf, (int)(bufsize - (Buf - bufbase)), Input) != NULL)
                {
                        Buf += (int)(bufsize - (Buf - bufbase)) -1;
                        if (bufbase[bufsize - 2] != 0)
                        {
                                tmp = (char*)realloc(bufbase, bufsize * 2);
                                if (tmp == NULL)
                                {
                                        printf("Failed to realloc.\n");
                                        free(bufbase);
                                        return (-1);
                                }
                                Buf = tmp + (Buf - bufbase);
                                bufbase = tmp;
                                bufsize *= 2;
                                bufbase[bufsize - 2] = 0;
                        }
                        Buf = bufbase + strlen(bufbase);
                }
                Buf = bufbase;
        }

        Word = strtok(Buf, NONALPHA);
        while (Status == SUCCESS && Word != NULL)
        {
                Status = AddToTree(DestTree, Treecount, Word);
                if (Status == SUCCESS)
                {
                        Word = strtok(NULL, NONALPHA);
                }
        }
        free(Buf);
        return (Status);
}


int WalkTree(
        WORD **DestArray,
        WORD *Word)
{
        int Status = SUCCESS;
        static WORD **Write = NULL;

        if(DestArray != NULL)
        {
                Write = DestArray;
        }

        if(Word != NULL)
        {
                *Write = Word;
                ++(Write);

                if(Word->Left != NULL)
                {
                        Status = WalkTree(NULL, Word->Left);
                }
                if(Word->Right != NULL)
                {
                        Status = WalkTree(NULL, Word->Right);
                }
        }

        return (Status);
}


int CompareCounts(
        const void *vWord1,
        const void *vWord2)
{
        int Result = 0;
        WORD * const *Word1 = vWord1;
        WORD * const *Word2 = vWord2;

        if((*Word1)->Count < (*Word2)->Count)
        {
                Result = 1;
        }
        else if((*Word1)->Count > (*Word2)->Count)
        {
                Result = -1;
        }
        else
        {
                Result = 0;
        }

        return (Result);
}


int OutputWords(
        FILE *Dest,
        size_t Count,
        WORD **WordArray)
{
        int Status = SUCCESS;
        size_t Pos = 0;

        fprintf(Dest, "Total Words : %lu\n", (unsigned long)Count);

        while(Status == SUCCESS && Pos < Count)
        {
                fprintf(Dest, "%10lu %s\n", (unsigned long)WordArray[Pos]->Count
, WordArray[Pos]->Word);
                ++(Pos);
        }

        return (Status);
}


char *dupstr(
        char *s)
{
        char *Result = NULL;
        size_t slen = 0;

        slen = strlen(s);

        Result = malloc(slen + 1);

        if(Result != NULL)
        {
                memcpy(Result, s, slen);
                *(Result + slen) = '\0';
        }

        return (Result);
}
 

cwriter

Erfahrenes Mitglied
C:
if(0 < CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe unten*/
                }
                else if(0 > CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe oben*/
                }
                else
                {
                        ++(*DestTree)->Count;
                }
Nun möchte ich es aber so anpassen,dass falls die Freqency für 2 Wörter gleich, die Sortierung alphabetisch aufsteigend sein soll.
Naja. Einfachkeitshalber würde ich sagen: Da der Baum ja nach Frequency "sortiert" ist, solltest du die gleichen Frequencies schnell haben. Dann hast du eine Liste von Nodes, deren Werte(!) du vertauschen kannst, ohne die Baumbedingung zu verletzen.

An welcher Stelle kann man das realisieren?
Was denkst du?

Ein Vorschlag wäre ganz am Ende nochmals durch den ganzen Baum zu gehen. Dafür bräuchtest du aber nochmals eine eigene Funktion.

Ahja und dupstr()? Warum willst du nicht den Standard strdup() verwenden? IBM scheint die Funktion zumindest auch mit K&R-C zu haben.

Gruss
cwriter
 

Joe1903

Mitglied
C:
if(0 < CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe unten*/
                }
                else if(0 > CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe oben*/
                }
                else
                {
                        ++(*DestTree)->Count;
                }

Naja. Einfachkeitshalber würde ich sagen: Da der Baum ja nach Frequency "sortiert" ist, solltest du die gleichen Frequencies schnell haben. Dann hast du eine Liste von Nodes, deren Werte(!) du vertauschen kannst, ohne die Baumbedingung zu verletzen.


Was denkst du?

Ein Vorschlag wäre ganz am Ende nochmals durch den ganzen Baum zu gehen. Dafür bräuchtest du aber nochmals eine eigene Funktion.

Ahja und dupstr()? Warum willst du nicht den Standard strdup() verwenden? IBM scheint die Funktion zumindest auch mit K&R-C zu haben.

Gruss
cwriter
Ganz am Ende nochmal eine Funktion möchte ich nicht.Ich möchte das oben bei CompResult einbauen,weiss aber echt nicht wie ich es angehen soll..
 

Joe1903

Mitglied
C:
if(0 < CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe unten*/
                }
                else if(0 > CompResult)
                {
                        Status = AddToTree(&(*DestTree)->Left, Treecount, Word); /*Sicher? Siehe oben*/
                }
                else
                {
                        ++(*DestTree)->Count;
                }

Naja. Einfachkeitshalber würde ich sagen: Da der Baum ja nach Frequency "sortiert" ist, solltest du die gleichen Frequencies schnell haben. Dann hast du eine Liste von Nodes, deren Werte(!) du vertauschen kannst, ohne die Baumbedingung zu verletzen.


Was denkst du?

Ein Vorschlag wäre ganz am Ende nochmals durch den ganzen Baum zu gehen. Dafür bräuchtest du aber nochmals eine eigene Funktion.

Ahja und dupstr()? Warum willst du nicht den Standard strdup() verwenden? IBM scheint die Funktion zumindest auch mit K&R-C zu haben.

Gruss
cwriter

Kann ich hier beim return ein strcmp machen,um es zu sortieren?Kannst du mir ein kleines Beispiel aufzeigen bitte?
 

cwriter

Erfahrenes Mitglied
Kann ich hier beim return ein strcmp machen,um es zu sortieren?
Beim return? Welches Return? Und ein strcmp hast du ja schon. Du hast nur keinen Baum, sondern eine Liste erstellt...
Kannst du mir ein kleines Beispiel aufzeigen bitte?
Ein Beispiel wovon bzw. wofür?

Die Baumstruktur ist schlicht eine schlechte Datenstruktur für diese Aufgabe.
Dein Baum ist ja nicht einmal ein Heap o_O.
Jedes AddToTree fügt das Wort ja nach Alphabetischer Reihenfolge ein (bzw. würde, wenn dein Code korrekt wäre), d.h. dein Baum ist nach Wörtern, nicht nach Frequency sortiert. (Frequency wäre ein schlechter Schlüssel, da sich die Frequency ja ändern kann).

Die gesamte Aufgabe ist kaputt (eine Liste bzw. ein Array wäre besser geeignet) und deine (bisherige) Implementierung davon ist auch nicht gerade das Gelbe vom Ei. Wenn du die Wörter nach dem Alphabet einfügst, dann ist der Baum Alphabetisch sortiert. Der Baum kann nicht gleichzeitig nach 2 Schlüsseln "sortiert" sein; du bräuchtest dafür 2 Bäume. Ansonsten kannst du auch bei deiner Output-Funktion einen neuen Baum erstellen, aber beides in einem geht eigentlich nicht.

Gruss
cwriter