4. Lineare Liste rekusiv füllen --> Seiteneffekte?

Lineare Liste rekusiv füllen --> Seiteneffekte?

  • ?

    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

    0
  • V

    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?

    0
  • V

    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 machen

    struct BigList{
   struct List lists[256];
};
int addValueToBigList(struct BigList *bigList,char *p_value){
   return addValueToList((bigList->lists)[unsigned char(*p_value)],p_value);
}
    0
  • ?

    ????

    0
  • ?

    sorry schon geschnallt.....
    🙄

    0
  • ?

    Doch nicht.... 😕

    Kannst Du mir diese Zeile nochmal genauer erklären?

    return addValueToList((bigList->lists)[unsigned char(*p_value)],p_value);
    0
  • ?

    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)
    0
  • ?

    aber warum die Klammern um bigList->lists ???

    0
  • C

    die klammern kannst du dir auch sparen. die machen an der speziellen stelle keinen unterschied.

    0
  • A

    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)

    0
  • ?

    Danke,

    dann werde ich mir wohl die Arbeit machen....

    Der Quelltext vorher sah echt schlimm aus 🙄

    0
  • V

    paddy@work schrieb:

    Danke,
    dann werde ich mir wohl die Arbeit machen....
    Der Quelltext vorher sah echt schlimm aus 🙄

    vielleicht 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?

    0
  • V

    bei

    return addValueToList(&bigList->lists[unsigned char(*p_value)],p_value);

    sind viele listen völlig leer.
    vielleicht magste lieber

    return 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.

    0
  • ?

    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

    0
Anmelden zum Antworten