//Copyright 2004 @ Matthias Jauernig
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CH 500

/* -- Strukturdefinition von struct element - Element einer verketteten Liste----------	*/
typedef struct ELEMENT {
    struct ELEMENT *next;
    char *zeichenkette;
} element;

/* -- Funktionsdeklarationen ----------------------------------------------------------	*/
element *einfuegen(const char*, element*);	//Einfügen in unsort. verk. Liste
 element *sorteinfuegen(element*, element*);//Einfügen in sort. verk. Liste
void ausgabe(element*);				//verk. Liste sequentiell ausgeben
element *loese_kopf(element**);			//Kopf einer verk. Liste lösen
void durchmustern(element*, const char*);	//Liste nach Teilstring durchmustern
char my_strfind(const char*, const char*);	//Äquivalent zu strstr() aus string.h

/* -- main() --------------------------------------------------------------------------	*/
int main(int argc, char **argv){
    char tmp[MAX_CH];
    element *akt, *kopf=NULL, *kopf_tmp, *kopf2=NULL;
   
    if(argc==1){
        printf("Beim Aufruf bitte den zu suchenden String angeben!\n\n");
        return 1;
    }   
   
    //einlesen solange kein EOF oder Fehler
    while(fgets(tmp,MAX_CH,stdin)!=NULL){
        tmp[strlen(tmp)-1]='\0';		//\n mit \0 ersetzen
	if(kopf==NULL){				//wenn noch kein Element vorhanden
	    kopf=einfuegen(tmp,kopf);		//Kopf einfügen
            akt=kopf;				//akt. Ende=Kopf
        }   
        else
            akt=einfuegen(tmp,akt);		//akt. Ende auf neu eingefügtes Element
    }
    if(kopf!=NULL){				//wenn Liste1 nicht leer
    	while((kopf_tmp=loese_kopf(&kopf))!=NULL)	//solange Liste1 nicht leer akt. Kopf loesen
		kopf2=sorteinfuegen(kopf_tmp,kopf2);	//sort. Einfügen in Liste2
        ausgabe(kopf2);				//Liste2 sequentiell ausgeben
    	durchmustern(kopf2,argv[1]);		//Liste2 nach erstem Übergabeparam. durchmustern
    }
   
    return 0;   
}

/* -- loese_kopf() --------------------------------------------------------------------	*/
element *loese_kopf(element **kopf){
	element *tmp_e=*kopf;			//Kopf soll zurück gegeben werden
	if(*kopf!=NULL) *kopf=(*kopf)->next;	//Kopf der Liste weitersetzen -> auch in main()
	return tmp_e;				//Zeiger auf alten Kopf zurückgeben
}

/* -- sorteinfuegen() -----------------------------------------------------------------	*/
element *sorteinfuegen(element *tmp, element *kopf){
	element *retp=kopf;			//rück zu gebenden Zeiger auf Kopf setzen
	
	//kein Element oder das erste größer dem einzufügenden Element -> neuer Kopf
	if(kopf==NULL || strcmp(tmp->zeichenkette,kopf->zeichenkette)<0){
		tmp->next=kopf;			//next-Zeiger aus bisher erstes bzw. NULL
		retp=tmp;			//rück zu gebender Zeiger=neuer Kopf
	}else{
		//wenn noch Elemente vorh. oder kleiner einzufügendem
		while(kopf->next && strcmp(tmp->zeichenkette,kopf->next->zeichenkette)>0)
			kopf=kopf->next;		//setze Zeiger weiter
		
		tmp->next=kopf->next;		//zeige auf nächstes Element der Liste
		kopf->next=tmp;			//nächstes Listenelement=neues Element
	}
	return retp;				//neuen/alten Kopf zurückgeben
}

/* -- einfuegen() ---------------------------------------------------------------------	*/
element *einfuegen(const char *tmp, element *akt){
    element *neu=(element*)malloc(sizeof(element));	//Speicher für neues Element
    neu->zeichenkette=(char*)malloc((strlen(tmp)+1)*sizeof(char));	//Speicher für Zk
    strncpy(neu->zeichenkette,tmp,strlen(tmp)+1);	//Zk auf neuen Speicher kopieren
   
    neu->next=NULL;				//nächstes Element=Ende der Liste, also NULL
    if(akt!=NULL)  akt->next=neu;		//Elemente vorh. dann next-Zeiger auf neu setzen
    return neu;					//neues Ende zurückgeben
}

/* -- ausgabe() -----------------------------------------------------------------------	*/
void ausgabe(element *akt){
    printf("\nsequentielle Ausgabe:\n");
    while(akt){					//solange noch Elemente auszugeben
        printf("%s\n",akt->zeichenkette);
        akt=akt->next;				//steze Zeiger weiter
    }
    printf("\n");   
}

/* -- durchmustern() ------------------------------------------------------------------	*/
void durchmustern(element *akt, const char *zk){
    int listenelement=1;			//Zähler auf 1. Listenelement
   
    printf("\"%s\" gefunden in:\n",zk);
    while(akt){					//wenn noch Elemente vorh.
        if(my_strfind(akt->zeichenkette,zk))	//wenn Teilstring gefunden, dann ausgeben
                printf("Zeile %3d: %s\n",listenelement,akt->zeichenkette);
        listenelement++;			//auf nächstes Listenelement zeigen
        akt=akt->next;				//Zeiger weiter setzen
    }
}

/* -- my_strfind() --------------------------------------------------------------------	*/
char my_strfind(const char *orig, const char *teil){
    int i=0,j=0;
   
    while(i<strlen(orig) && j<strlen(teil))	//solange die Strings noch nicht komplett betrachtet
        if(orig[i++]!=teil[j++])		//wenn Unterschied, dann j zurücksetzen auf Anfang
            j=0;
   
    if(j==strlen(teil))				//Teilstring komplett betrachtet, dann gefunden in String
        return 1;
    return 0;
}