Lineare Liste rekusiv füllen --> Seiteneffekte?
-
Hallo,
ich habe ein nicht ganz leicht zu formulierendes Problem.
Zunächst die beiden Datenstrukturen:typedef struct Data { struct Data *next; char *value; }Data; typedef struct List { struct Data *a_c; struct Data *d_f; struct Data *g_i; struct Data *j_l; struct Data *m_o; struct Data *p_r; struct Data *s_u; struct Data *v_z; struct Data *other; struct Data *a_c_last; struct Data *d_f_last; struct Data *g_i_last; struct Data *j_l_last; struct Data *m_o_last; struct Data *p_r_last; struct Data *s_u_last; struct Data *v_z_last; struct Data *other_last; struct Data *a_c_iterator; struct Data *d_f_iterator; struct Data *g_i_iterator; struct Data *j_l_iterator; struct Data *m_o_iterator; struct Data *p_r_iterator; struct Data *s_u_iterator; struct Data *v_z_iterator; struct Data *other_iterator; }List;Die Liste wird enorm groß, deshalb habe ich sie in 9 einzelne Listen aufgeteilt. Wenn man nun überprüfen möchte, ob ein Wert in der Liste steht,
muss man nicht mehr die gesamte Liste (mit bis zu 200000 Einträgen durchsuchen), sondern kann je nach Anfangsbuchstaben des Wertes in die entsprechende Liste gehen.struct Data a_cstellt den Zeiger auf das erste Element der Liste dar,
struct Data a_c_lastden Zeiger auf das letzte Element und
struct a_c_iteratorden Zeiger auf das aktuelle Element
Ich habe nun einen globalen Zeiger auf Liste deklariert welcher erfolgreich initialisiert wird:
struct List *type_name_liste; type_name_liste = initList();Nun rufe ich die Funktion preprocess auf und übergebe diesen Zeiger, damit diese Funktion Werte in der Liste eintragen kann:
preprocess(argv[1],0,type_name_liste);wenn in der Funktion preprocess eine #include-Anweisung gefunden wird, so ruft sie sich rekursiv auf, um die Informationen aus der Headerdatei in der Liste einzutragen:
preprocess(myHeader,1,type_name_liste);Irgendwie kommt es durch die Rekursion zu Seiteneffekten, denn es sind nicht alle Informationen in der Liste eingetragen, obwohl sie es eigentlich müssten.
Nun meine Frage:
Wie mache ich es richtig, dass ich in einer Rekursion Elemente an eine Liste hänge
und dass nach der Rekursion der Aufrufende (der Rekursion) eine aktuallisierte Liste bekommt?
Über das return- Statement kann ich es nicht machen, da diese Liste nur eine von vielen ist, welche als Beispiel dient.
Muss ich in der Definition von preprocess einen Zeiger auf einen Zeiger auf List als Parameter definieren und in der Funktion (also beim Hinzufügen von Werten) Dereferenzieren?
int preprocess(char *file,int flag,List **type_name_liste) { addValueToList(wert,*(type_name_liste)); }gibt es noch andere Möglichkeiten?
Gruß Paddy
-
Nein einen Zeiger auf einen Zeiger brauchst du für deine Liste nicht. Da du ja den Zeiger auf deine Liste nicht verändern willst in der Funktion, oder? (ich seh auf jeden Fall keinen Grund dazu.) Du willst im Endeffekt an die Elemente deiner List-Struktur, die ja auch wieder Strukturen sind, Wert anhängen.
Kannst du bitte noch den Quellcode zu preprocess() und der Funktion zum eigentlichen Befüllen deiner Elemente posten? Ich vermute, dass eher dort der Fehler liegt.
Ansonsten solltest du dich mal mit dem Debugger vertraut machen. Damit kann man Fehler leichter finden.
-
Die Add-Funktion:
int addValueToList(char *p_value,struct List *list) { if(p_value != "" || (strcmp(p_value,"\n") == 0 )) { // Fuege nur Werte ein, die noch nicht in der Liste sind if(!isInList(p_value,list)) { // Temporaeres Objekt, welches angehaengt wird struct Data *temp; temp = (Data*) malloc(sizeof(Data)); if(!temp) { return -1; } else { temp->next = NULL; // Reservier den Speicher +1 wegen des abschließendem '\0' temp->value = (char*) malloc(strlen(p_value)+1); if(temp->value == NULL) { return -1; } else { strcpy(temp->value,p_value); // Setze alle Iteratoren an den Anfang der jeweiligen Liste setBottom(list); if( p_value[0] == 'a' || p_value[0] == 'A' || p_value[0] == 'b' || p_value[0] == 'B' || p_value[0] == 'c' || p_value[0] == 'C') { // Wenn ListDe noch leer ist if(list->a_c == NULL) { list->a_c = temp; list->a_c_last = temp; list->a_c_iterator = temp; } else { while(strcmp(p_value,list->a_c_iterator->value) > 0 && list->a_c_iterator->next != NULL) { list->a_c_iterator = goNext(list->a_c_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->a_c_iterator->value) > 0) { temp->next = list->a_c_iterator->next; list->a_c_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->a_c_last = temp; } } else if(list->a_c_iterator != list->a_c) { temp->next = list->a_c_iterator; setBottomD(list); while(temp->next != list->a_c_iterator->next) { list->a_c_iterator = goNext(list->a_c_iterator); } list->a_c_iterator->next = temp; } else { temp->next = list->a_c_iterator; list->a_c = temp; } } // Ende von if(list->a_c == NULL) ... else } // Ende von if( p_value[0] == 'a' || ... else if( p_value[0] == 'd' || p_value[0] == 'D' || p_value[0] == 'e' || p_value[0] == 'E' || p_value[0] == 'f' || p_value[0] == 'F') { // Wenn ListDe noch leer ist if(list->d_f == NULL) { list->d_f = temp; list->d_f_last = temp; list->d_f_iterator = temp; } else { while(strcmp(p_value,list->d_f_iterator->value) > 0 && list->d_f_iterator->next != NULL) { list->d_f_iterator = goNext(list->d_f_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->d_f_iterator->value) > 0) { temp->next = list->d_f_iterator->next; list->d_f_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->d_f_last = temp; } } else if(list->d_f_iterator != list->d_f) { temp->next = list->d_f_iterator; setBottomD(list); while(temp->next != list->d_f_iterator->next) { list->d_f_iterator = goNext(list->d_f_iterator); } list->d_f_iterator->next = temp; } else { temp->next = list->d_f_iterator; list->d_f = temp; } } // Ende von if(list->d_f == NULL) ... else } // Ende von if( p_value[0] == 'd' || ... else if( p_value[0] == 'g' || p_value[0] == 'G' || p_value[0] == 'h' || p_value[0] == 'H' || p_value[0] == 'i' || p_value[0] == 'I') { // Wenn ListDe noch leer ist if(list->g_i == NULL) { list->g_i = temp; list->g_i_last = temp; list->g_i_iterator = temp; } else { while(strcmp(p_value,list->g_i_iterator->value) > 0 && list->g_i_iterator->next != NULL) { list->g_i_iterator = goNext(list->g_i_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->g_i_iterator->value) > 0) { temp->next = list->g_i_iterator->next; list->g_i_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->g_i_last = temp; } } else if(list->g_i_iterator != list->g_i) { temp->next = list->g_i_iterator; setBottomD(list); while(temp->next != list->g_i_iterator->next) { list->g_i_iterator = goNext(list->g_i_iterator); } list->g_i_iterator->next = temp; } else { temp->next = list->g_i_iterator; list->g_i = temp; } } // Ende von if(list->g_i == NULL) ... else } // Ende von if( p_value[0] == 'g' || ... else if( p_value[0] == 'j' || p_value[0] == 'J' || p_value[0] == 'k' || p_value[0] == 'K' || p_value[0] == 'l' || p_value[0] == 'L') { // Wenn ListDe noch leer ist if(list->j_l == NULL) { list->j_l = temp; list->j_l_last = temp; list->j_l_iterator = temp; } else { while(strcmp(p_value,list->j_l_iterator->value) > 0 && list->j_l_iterator->next != NULL) { list->j_l_iterator = goNext(list->j_l_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->j_l_iterator->value) > 0) { temp->next = list->j_l_iterator->next; list->j_l_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->j_l_last = temp; } } else if(list->j_l_iterator != list->j_l) { temp->next = list->j_l_iterator; setBottomD(list); while(temp->next != list->j_l_iterator->next) { list->j_l_iterator = goNext(list->j_l_iterator); } list->j_l_iterator->next = temp; } else { temp->next = list->j_l_iterator; list->j_l = temp; } } // Ende von if(list->j_l == NULL) ... else } // Ende von if( p_value[0] == 'j' || ... else if( p_value[0] == 'm' || p_value[0] == 'M' || p_value[0] == 'n' || p_value[0] == 'N' || p_value[0] == 'o' || p_value[0] == 'O') { // Wenn ListDe noch leer ist if(list->m_o == NULL) { list->m_o = temp; list->m_o_last = temp; list->m_o_iterator = temp; } else { while(strcmp(p_value,list->m_o_iterator->value) > 0 && list->m_o_iterator->next != NULL) { list->m_o_iterator = goNext(list->m_o_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->m_o_iterator->value) > 0) { temp->next = list->m_o_iterator->next; list->m_o_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->m_o_last = temp; } } else if(list->m_o_iterator != list->m_o) { temp->next = list->m_o_iterator; setBottomD(list); while(temp->next != list->m_o_iterator->next) { list->m_o_iterator = goNext(list->m_o_iterator); } list->m_o_iterator->next = temp; } else { temp->next = list->m_o_iterator; list->m_o = temp; } } // Ende von if(list->m_o == NULL) ... else } // Ende von if( p_value[0] == 'm' || ... else if( p_value[0] == 'p' || p_value[0] == 'P' || p_value[0] == 'q' || p_value[0] == 'Q' || p_value[0] == 'r' || p_value[0] == 'R') { // Wenn ListDe noch leer ist if(list->p_r == NULL) { list->p_r = temp; list->p_r_last = temp; list->p_r_iterator = temp; } else { while(strcmp(p_value,list->p_r_iterator->value) > 0 && list->p_r_iterator->next != NULL) { list->p_r_iterator = goNext(list->p_r_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->p_r_iterator->value) > 0) { temp->next = list->p_r_iterator->next; list->p_r_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->p_r_last = temp; } } else if(list->p_r_iterator != list->p_r) { temp->next = list->p_r_iterator; setBottomD(list); while(temp->next != list->p_r_iterator->next) { list->p_r_iterator = goNext(list->p_r_iterator); } list->p_r_iterator->next = temp; } else { temp->next = list->p_r_iterator; list->p_r = temp; } } // Ende von if(list->p_r == NULL) ... else } // Ende von if( p_value[0] == 'p' || ... else if( p_value[0] == 's' || p_value[0] == 'S' || p_value[0] == 't' || p_value[0] == 'T' || p_value[0] == 'u' || p_value[0] == 'U') { // Wenn Liste noch leer ist if(list->s_u == NULL) { list->s_u = temp; list->s_u_last = temp; list->s_u_iterator = temp; } else { while((strcmp(p_value,list->s_u_iterator->value) > 0) && (list->s_u_iterator->next != NULL)) { list->s_u_iterator = goNext(list->s_u_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->s_u_iterator->value) > 0) { temp->next = list->s_u_iterator->next; list->s_u_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->s_u_last = temp; } } else if(list->s_u_iterator != list->s_u) { temp->next = list->s_u_iterator; setBottomD(list); while(temp->next != list->s_u_iterator->next) { list->s_u_iterator = goNext(list->s_u_iterator); } list->s_u_iterator->next = temp; } else { temp->next = list->s_u_iterator; list->s_u = temp; } } // Ende von if(list->s_u == NULL) ... else } // Ende von if( p_value[0] == 's' || ... else if( p_value[0] == 'v' || p_value[0] == 'V' || p_value[0] == 'w' || p_value[0] == 'W' || p_value[0] == 'x' || p_value[0] == 'X' || p_value[0] == 'y' || p_value[0] == 'Y' || p_value[0] == 'z' || p_value[0] == 'Z') { // Wenn Liste noch leer ist if(list->v_z == NULL) { list->v_z = temp; list->v_z_last = temp; list->v_z_iterator = temp; } else { while((strcmp(p_value,list->v_z_iterator->value) > 0) && (list->v_z_iterator->next != NULL)) { list->v_z_iterator = goNext(list->v_z_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->v_z_iterator->value) > 0) { temp->next = list->v_z_iterator->next; list->v_z_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->v_z_last = temp; } } else if(list->v_z_iterator != list->v_z) { temp->next = list->v_z_iterator; setBottomD(list); while((temp->next != list->v_z_iterator->next)&& (list->v_z_iterator->next != NULL)) { list->v_z_iterator = goNext(list->v_z_iterator); } list->v_z_iterator->next = temp; } else if(list->v_z_iterator == list->v_z) { temp->next = list->v_z_iterator; list->v_z = temp; } } // Ende von if(list->v_z == NULL) ... else } // Ende von if( p_value[0] == 'v' || ... else if(p_value[0] == '_') { // Wenn ListDe noch leer ist if(list->other == NULL) { list->other = temp; list->other_last = temp; list->other_iterator = temp; } else { while(strcmp(p_value,list->other_iterator->value) > 0 && list->other_iterator->next != NULL) { list->other_iterator = goNext(list->other_iterator); } // Wenn es mindestens einen hoeheren und mindestens einen // niedrigeren Wert gibt if(strcmp(p_value,list->other_iterator->value) > 0) { temp->next = list->other_iterator->next; list->other_iterator->next = temp; // Wenn es sich um das letzte Element handelt if(temp->next == NULL) { list->other_last = temp; } } else if(list->other_iterator != list->other) { temp->next = list->other_iterator; setBottomD(list); while(temp->next != list->other_iterator->next) { list->other_iterator = goNext(list->other_iterator); } list->other_iterator->next = temp; } else { temp->next = list->other_iterator; list->other = temp; } } // Ende von if(list->other == NULL) ... else } // Ende von if(other) } // Ende von if(!temp->value) ... else } // Ende von if(!temp) ... else } // Ende von if(!isInList(p_value,list)) else { return 2; } } return 0; }die Preprocess Funktion wird nicht sehr viel bringen, da sie von lex automatisch erstellt wird und sie nicht sehr lesbar ist. In der Preprocess Funktion wird allerdings auch nur die Add-Funktion aufgerufen
-
bitte melde dich bei http://thedailywtf.com/
er nimmt keine einsendungen an, wo jemand jemand anderen in einem forum vorschlägt. aber vielleicht nimmt er es ja an, wenn man sich selber vorstellt?
-
ich vertraue dir mal, daß du eine einfache verkettete liste bauen kannst, die wo
int addValueToList(struct List *list,char *p_value)macht.
nu kannste auch machenstruct BigList{ struct List lists[256]; }; int addValueToBigList(struct BigList *bigList,char *p_value){ return addValueToList((bigList->lists)[unsigned char(*p_value)],p_value); }
-
????
-
sorry schon geschnallt.....
-
Doch nicht....
Kannst Du mir diese Zeile nochmal genauer erklären?
return addValueToList((bigList->lists)[unsigned char(*p_value)],p_value);
-
Du rufst die Funktion "addValueToList()" für die i-te Liste in deiner BigList und den einzutagenden Wert auf:
bigList - Pointer auf BigList-Objekt bigList->lists - das List-Array in bigList (bigList->lists)[i] - das i-te Element in diesem List-Array (mit i=erstes Zeichen des einzutragenden Strings)
-
aber warum die Klammern um bigList->lists ???
-
die klammern kannst du dir auch sparen. die machen an der speziellen stelle keinen unterschied.
-
paddy@work schrieb:
aber warum die Klammern um bigList->lists ???
Die Antwort liegt in der Rangfolge der Operatoren
(wobei es hier keine Probleme geben sollte, wie c.rackwitz schon angemerkt hat)
-
Danke,
dann werde ich mir wohl die Arbeit machen....
Der Quelltext vorher sah echt schlimm aus
-
paddy@work schrieb:
Danke,
dann werde ich mir wohl die Arbeit machen....
Der Quelltext vorher sah echt schlimm ausvielleicht sollten wir erst drüber reden.
du willst eine million datensätze in einfach verketteten listen einfügen und suchen? bieten sich da nicht hash tables oder bäume an?
-
bei
return addValueToList(&bigList->lists[unsigned char(*p_value)],p_value);sind viele listen völlig leer.
vielleicht magste lieberreturn addValueToList(&bigList->lists[unsigned char(*p_value)%16],p_value);aber das führt uns eh sofort zu hashtables, also für 1 mio datensätze auch ca 1 mio verkettete listen und man berechnet vorher anhand aller buchstaben im string, wo er landen soll.
-
Es geht nicht um Millionen.
Es sind "lediglich" maximal 100.000 .
Wenn man die Windows.h (inklusive aller anderen in ihr enthaltenen Includes) parst findet er 14092 Makros bzw. Defines.Wenn dann noch eigene dazukommen, ist man maximal bei 100000
Ich habe die Liste fertig und sie ist schnell genug...
In der Liste werden die Makro's ihrem namen nach alphabetisch sortiert hinzugefügt. es reicht also vollkommen aus, wenn man 53 Listen nimmt.
a-zA-Z und _
Diese lineare Verteilung kommt auch in etwa hin.
Gruß Paddy