Verkettete Liste (Suche)

MandaJohn

Hallo Leute,
hab mal wieder eine Frage. Versuche gerade was mit Verkettete Listen zu machen. Läuft soweit auch ganz gut. Bis auf einer Suche. Ich versuche einfach nur paar eingaben zu machen und dann danach zu suchen.
Hier der such Code:

int main(void)
{
struct prufung *start_pointer = NULL;

printf("\n\nSuche nach Punkten: ");
	scanf("%d", &punkte);

	if( (ptr = punkteSuchen(punkte, start_pointer)) == NULL )
		printf("\nPruefung mit Punkte kleiner als: %d nicht vorhanden", punkte);
	else
	{
		printf("\nDie Veranstaltung: %s", ptr->veranstaltung);
		printf("\nDie Punkte       : %d", ptr->punkte);
		printf("\nDas Datum        : %s", ptr->datum);
		printf("\nDer Professor    : %s", ptr->professor);
	}
}

struct prufung *punkteSuchen(int punkte, prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	while(ptr != NULL && (punkte <= ptr->punkte) )
		ptr = ptr->next;

	return ptr;
}

main() ist nicht komplett, sondern nur der Teil wo es aufgerufen werden soll. Ich versuche einfach paar Prüfungen einzugeben und dann nach den Punkte suchen lassen.
Wenn ich jetzt 3 Prüfungen mit (10punkten, 8punkten, 9punkten) eingebe und sage, dass ich jetzt ALLE Prüfungen haben will die KleinerGleich 10punkte sind, dann gibt er mir nur die eine Prüfung aus und nicht 2 wie er es sollte.

Hab ich was in der punkteSuchen() funktion was falsch gemacht? Möchte gerne auch die restlichen Prüfungen haben.

Danke schon mal!

Gruß
Manda

^^die funktion gibt ja auch nur eine struct prufung zurück. mach dir doch 'ne callback-funktion, die bei jedem match aufgerufen wird.

MandaJohn

In meinem struct sind die ganzen Prüfungen...die kann ich auch alle anzeigen lassen. Ich kann auch nach dem Namen suchen, aber problem ist nur wenn ich mehrere Prüfungen habe die was weis ich kleiner 10punkte sind, dass er nicht alle anzeigt, sondern nur eine.

Was meinst du mit "callback" funktion? Hab das irgendwie nicht verstanden

MandaJohn schrieb:

Was meinst du mit "callback" funktion? Hab das irgendwie nicht verstanden

na, jedesmal, wenn der vergleich positiv ist, wird eine funktion aufgerufen, die die gefundene struct bekommt (zum anzeigen z.b.).

Das was fricky meint in etwa so:

void callback (prufung_t *ptr) {
    printf("\nDie Veranstaltung: %s", ptr->veranstaltung);
    printf("\nDie Punkte       : %d", ptr->punkte);
    printf("\nDas Datum        : %s", ptr->datum);
    printf("\nDer Professor    : %s", ptr->professor);
}

void punkteSuchen(int punkte, prufung_t *ptr, void (*callback)(prufung_t *)) {
    while(ptr != NULL)
    if (ptr->punkte < punkte) {
        callback (ptr);
    }
    ptr = ptr->next;
}

Eine andere Variante wäre deine bestehende Funktion einfach immer wieder mit rückgabewert->next als Parameter aufzurufen bis rückgabewert NULL ist.

Cefour

Eine weiter möglichkeit ist du gibst eine neue Verkettete Liste mit allen Ergenissen zurück d.h Die while schleife die du hast bricht nicht ab sondern speichert jeden gefundenen Wert erstmal in eine neue Liste ein und gibt diese am Ende zurück

MandaJohn

@Tim - wollte meine Funktion benutzen und deinen Tip beherzigen...
wo du sagtest, mit dem Rückgabewert->next immer wieder aufrufen bis NULL ist

Mache ich das eigentlich schon nicht?

while(ptr != NULL && (punkte <= ptr->punkte) )

Hier frage ich ja auch ob ptr!= NULL ist oder seh ich das falsch?

Diese Schleife läuft aber nur solange bis ein Element gefunden wurde (oder du am Ende der Liste bist) und gibst dann nur _einen_ Zeiger auf ein Element der Liste (oder halt NULL) zurück. Was du machen musst ist die Funktion punkteSuchen() in main() in einer Schleife aufzurufen (eben solange der Rückgabewert nicht NULL ist).

MandaJohn

Ok Danke für den Tip. Ich probier das mal mit einer Schleife...

Gruß
Manda

Konfusius

while(ptr != NULL && (punkte <= ptr->punkte) )

Du solltest in dieser Zeile <= durch < ersetzen. Sonst wird das gesuchte Listenelement übersprungen.

Das Beispiel von Tim funktioniert auch, wäre mM aber ein konzeptioneller Overkill.

Konfusius schrieb:

Das Beispiel von Tim funktioniert auch, wäre mM aber ein konzeptioneller Overkill.

was schlägst du vor?

hartmut1164

Eventl. ueber eine zweite Liste mit Pointer auf das jeweilige Datenelement arbeiten:

struct PrufungList
{
    struct Prufung      *pData;
    struct PrufungList  *pBefore,
                        *pNext;
}

struct PrufungList *NewList (Prufung   *pPrufung)
{
    PrufungList *pReturn;

    pReturn = malloc (sizeof (PrufungList);

    pReturn->pNext    = NULL;
    pReturn->pBefore  = NULL;
    pReturn->pData    = pPrufung;

    return pReturn;
}

struct PrufungList *SearchPoint (Prufung   *pPrufung,
                                 int        iPoint)
{
    Prufung     *pCurrent;
    PrufungList *pReturn       = NULL,
                *pCurrentList  = NULL,
                *pTemp;

    pCurrent = pPrufung;

    while (pCurrent != NULL)
    {
        if (pCurrent->punkte < pPoint)
        {
            pTemp = NewList (pCurrent);
            if (pReturn == NULL)
                pReturn = pTemp;
            else
            {
                pTemp->pBefore = pCurrentList;
                pCurrentList->pNext = pNext;
            }

            pCurrentList = pTemp;
        }

        pCurrent = pCurrent->pNext;
    }

    return pReturn;
}

void PrintListSingle (PrufungList *pToPrint)
{
    printf("\nDie Veranstaltung: %s", pToPrint->pData->veranstaltung);
    printf("\nDie Punkte       : %d", pToPrint->pData->punkte);
    printf("\nDas Datum        : %s", pToPrint->pData->datum);
    printf("\nDer Professor    : %s", pToPrint->pData->professor); 
}

void PrintList (PrufungList *pIn)
{
    if (pIn != NULL)
    {
        PrintListSingle (pIn);
        PrintList (pIn->pNext);
    }
}

In main sahe das dann etwa so aus:

Prufung     *pPrufung,
PrufungList *pSearchResults;

pSearchResults = SearchPoint (pPrufung, 123);
if (pSearchResults == NULL)
    printf ("Leer!");
else
    PrintList (pPrufung);

MandaJohn

Ich würde mal meinen Code posten wollen.
@Hartmut 1164 - Danke für den Code! Aber ich verliere irgendwie die Überischt. Versuche es so einfach wie möglich zu machen.

Hier der Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <conio.h>

#define MAX 21

struct student
{	
	char nachname[MAX];
	char vorname[MAX];
	int matrikel;
	struct prufung *first;
};

struct prufung
{
	char veranstaltung[MAX];
	int punkte;
	char datum[MAX];
	char professor[MAX];
	struct prufung *next;
};

typedef struct student student_t;
typedef struct prufung prufung_t;

int einfugenPrufung(char *veranstaltung, int punkte, char *datum, char *professor, prufung_t **start_pointer);
void prufungAusgeben(prufung_t *start_pointer);
struct prufung *nameSuchen(char *name, prufung_t *start_pointer);
struct prufung *punkteSuchen(int punkte, prufung_t *start_pointer);
void listeSpeichern(prufung_t *start_pointer);
void listeLesen(void);

int main(void)
{
	char nachname[MAX];
	char vorname[MAX];
	int matrikel;

	char veranstaltung[MAX];
	int punkte;
	char datum[MAX];
	char professor[MAX];

	struct student *str = NULL;
	struct prufung *ptr = NULL;
	struct prufung *start_pointer = NULL;

	printf("\nWollen Sie Daten aus der liste.dat lesen [j/n]?");
	if(getch() == 'j')
		listeLesen();

	printf("\n\n");
	printf("Geben Sie einen Studenten ein:\n");
	printf("==============================\n");

	printf("\nNachname   : ");
	scanf("%s", nachname);

	printf("Vorname    : ");
	scanf("%s", vorname);

	printf("MatrikelNr.: ");
	scanf("%d", &matrikel);

	if( (str = (struct student*)malloc(sizeof(struct student))) == NULL)
		return 1;
	else
	{
		strcpy(str->nachname, nachname);
		strcpy(str->vorname, vorname);
		str->matrikel = matrikel;
	}

	printf("\n+-----------------------------------+");
	printf("\nWollen Sie Pruefungen eingeben [j/n]?\n");

	if(getch() == 'j')
	{
		do
		{
			printf("\nVeranstaltung: ");
			scanf("%s", veranstaltung);

			printf("Punkte: ");
			scanf("%d", &punkte);

			printf("Datum [TTMMJJJJ]: ");
			scanf("%s", datum);

			printf("Professor: ");
			scanf("%s", professor);

			if(einfugenPrufung(veranstaltung, punkte, datum, professor, &start_pointer) != 0)
			{
				printf("\nFehler beim Hinzufuegen einer Pruefung");
				return 1;
			}		
			printf("\nWollen Sie weitere Pruefungen eingeben [j/n]?\n");
		}
		while(getch() == 'j');

		prufungAusgeben(start_pointer);
	}

	printf("\n+-----------------------------------+");
	printf("\n\nSuche nach 'Veranstaltung': ");
	scanf("%s", veranstaltung);

	if( (ptr = nameSuchen(veranstaltung, start_pointer)) == NULL )
		printf("\nVeranstaltung mit Namen %s nicht vorhanden!", veranstaltung);
	else
	{
		printf("\nDie Veranstaltung: %s", ptr->veranstaltung);
		printf("\nDie Punkte       : %d", ptr->punkte);
		printf("\nDas Datum        : %s", ptr->datum);
		printf("\nDer Professor    : %s", ptr->professor);
	}

	printf("\n+-----------------------------------+");
	printf("\n\nSuche nach Punkten: ");
	scanf("%d", &punkte);

	if( (ptr = punkteSuchen(punkte, start_pointer)) == NULL )
		printf("\nPruefung mit Punkte kleiner als: %d nicht vorhanden", punkte);
	else
	{
		printf("\nDie Veranstaltung: %s", ptr->veranstaltung);
		printf("\nDie Punkte       : %d", ptr->punkte);
		printf("\nDas Datum        : %s", ptr->datum);
		printf("\nDer Professor    : %s", ptr->professor);
	}

	printf("\n+-----------------------------------+");
	printf("\nWollen Sie die Liste Speichern [j/n]?");
	if(getch() == 'j')
		listeSpeichern(start_pointer);	
	else
		printf("\nEs werden keine Daten gespeichert!");

	free(str);
	free(ptr);	

	printf("\n\n");
	return 0;
}

int einfugenPrufung(char *veranstaltung, int punkte, char *datum, char *professor, prufung_t **start_pointer)
{
	struct prufung *ptr = NULL;

	if( (ptr = (struct prufung*)malloc(sizeof(struct prufung))) == NULL )	
		return 1;
	else
	{
		strcpy(ptr->veranstaltung, veranstaltung);
		ptr->punkte = punkte;
		strcpy(ptr->datum, datum);
		strcpy(ptr->professor, professor);
		ptr->next = *start_pointer;
		*start_pointer = ptr;

		return 0;
	}
}

void prufungAusgeben(prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	printf("\n\n+-----------------------------------+");
	printf("\nAusgabe der Pruefungen eines Studenten:\n");
	while(ptr != NULL)
	{	
		printf("\nVeranstaltung: %s", ptr->veranstaltung);
		printf("\nPunkte       : %d", ptr->punkte);
		printf("\nDatum        : %s", ptr->datum);
		printf("\nProfessor    : %s", ptr->professor);
		printf("\n");
		ptr = ptr->next;
	}
}

struct prufung *nameSuchen(char *name, prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	while(ptr != NULL && strcmp(ptr->veranstaltung, name))
		ptr = ptr->next;

	return ptr;
}

struct prufung *punkteSuchen(int punkte, prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	while(ptr != NULL && (ptr->punkte < punkte) )
		ptr = ptr->next;	

	return ptr;
}

void listeSpeichern(prufung_t *start_pointer)
{
	FILE *file;
	prufung_t *ptr;

	file = fopen("liste.dat", "wb");
	if(file == NULL)
	{
		perror("Fehler beim Oeffnen");
		exit(EXIT_FAILURE);
	}

	fseek(file, 0, SEEK_END);

	ptr = start_pointer;

	while(ptr != NULL)
	{
		fwrite(ptr, sizeof(prufung_t), 1, file);
		ptr = ptr->next;
	}

	fclose(file);
}

void listeLesen(void)
{
	FILE *file;
	prufung_t ptr;

	file = fopen("liste.dat", "rb");
	if(file == NULL)
	{
		perror("\nFehler beim Oeffnen");
		getch();
		main();		
	}

	while(fread (&ptr, sizeof(prufung_t), 1, file) == 1)
	{
		printf("\n+-----------------------------------+");
		printf("\nDie Pruefungen sind:");
		printf("\n");
		printf("\nVeranstaltung: %s", ptr.veranstaltung);
		printf("\nPunkte       : %d", ptr.punkte);
		printf("\nDatum        : %s", ptr.datum);
		printf("\nProfessor    : %s", ptr.professor);		
	}	
	fclose(file);
}

Könnte ich die Suche nach den Punkten in meiner Funktion nicht verändern, anstatt neuen struct zu machen?
Ein anderes Problem habe ich auch noch. Wenn ich die Liste abspeichern will (als Binärdatei) dann gibt er mir eine Fehlermeldung aus. Aber er speichert trotzdem.
Ich kann die Daten auch wieder laden und sie werden auch angezeigt. Beim nächsten Speichern (also beim Anhängen) bekomme ich keine Fehlermeldung.

Danke schonmal!
Schönen Gruß
Manda

Skalli

Meh, da sind ein paar böse Fehler im Code
Ich hab nicht alles gelesen, aber das:

if(file == NULL)
    {
        perror("\nFehler beim Oeffnen");
        getch();
        main();       
    }

ist eine indirekte Rekursion und ich glaube nicht das du das an der Stelle willst!
Du rufst dort die main()-Funktion auf ohne die andere Funktion beendet zu haben.
Anstelle main() sollte da ein return stehen, ohne einen Wert da du ja void hast.
Der Fehler fiel mir gerade ins Auge, den Rest des Codes habe ich (noch) nicht gelesen.

Ansonsten würde ich es wie es auch schonmal Vorgeschlagen wurde mit einer 2. Liste machen in die alle gefundenen Einträge eingetragen werden. Dann wird diese Liste zurück gegeben...

hartmut1164

Statt nun fuer jeden Suchparameter eine Funktion zu schreiben, mach doch folgendens:

struct PrufungList *BuildSearchResults (int (*Found (Prufung   *pPrufung,
                                                     void      *pCriterium))
{

    Prufung     *pCurrent;
    PrufungList *pReturn       = NULL,
                *pCurrentList  = NULL,
                *pTemp;

    pCurrent = pPrufung;

    while (pCurrent != NULL)
    {
        if (Found (pCurrent, pCriterium) == 0)
        {
            pTemp = NewList (pCurrent);
            if (pReturn == NULL)
                pReturn = pTemp;
            else
            {
                pTemp->pBefore = pCurrentList;
                pCurrentList->pNext = pNext;
            }

            pCurrentList = pTemp;
        }

        pCurrent = pCurrent->pNext;
    }

    return pReturn;
}

Dann brauchst Du die Verwaltung der Liste der Ergebnisse nur einmal zu schreiben und das Suchkriterium mittels der Uebergabe der entsprechenden Funktion bestimmen.

MandaJohn

@Skalli, danke für den Hinweis. Wollte eigentlich damit wieder in main() zurück. Aber habe jetzt ein "return" drin.
@Hartum, ich müsste eigentlich nur für diese beiden Kriterien was suchen. Aber deine Funktion scheint universeller. Ich probier es mal. Hoffe das ich den Überblick nicht langsam verlieren

Danke!

MandaJohn

@Hartmut - Bin gerade dabei deine Funktion zu implementieren. Aber irgendwie kriege ich komische Fehlermeldungen, wie:
- inkompatible typen (in Funktion: *BuildSearchResult, im else-Zweig)
- undeclared identifier (in der gleichen Funktion, bei: pCurrent = pPrufung; )
Ich glaube er erkennt die parameterliste nicht.
Hoffe du kannst mir da noch malhelfen

Danke.

hartmut1164

War frueh am morgen:

struct PrufungList *BuildSearchResults (Prufung   *pPrufung, void *pCriterium,int (*Found (Prufung   *pCurrentIn, void  *pCriterium)))
{
//...

MandaJohn

@Harmut - Im else Zweig zeigt er immer "kompatibilitäts-Probleme" an. Die ich nicht verstehe. Ich habe stattdessen, eine andere variante versucht, die auch zu funktionieren scheint.
Undzwar folgende:

struct prufung *punkteSuchen(int punkte, prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	while(ptr != NULL)
	{
		if(ptr->punkte < punkte)
		{
			printf("\n");
			printf("\nVeranstaltung: %s", ptr->veranstaltung);
			printf("\nDatum        : %s", ptr->datum);
			printf("\nPunkte       : %d", ptr->punkte);
			printf("\nProfessor    : %s", ptr->professor);				
		}
		ptr = ptr->next;
	}	
	return ptr;
}

Habe nur diese Funktion umgeändert, einfach ein if rein und es klappt.
Was allerdings nicht geht und ich aber haben muss ist folgendes:
Wenn man die Datei abspeichert und dann neustartet. Diesmal aber gleich von der Datei liest. Dann zeigt er auch die Daten an.
Ich kann allerdings nichts dadrin suchen. Wenn ich eine Veranstaltung suche oder Punkte suche, dann sagt er, es gibt nichts.
Eigentlich sollte er die Daten ja ausgeben, die da drin sind.

Hat jemand da eine idee? Oder mache ich was falsch?

MandaJohn

Hallo Leute, das Problem hat sich erledigt. Ich kann jetzt auch von der Liste die Daten suchen lassen. Funktioniert soweit alles.
Hätte da noch eine Frage zum struct tm (muss das Datum dadurch einlesen).
Ich geb mal den Code vor:
Mein Struct:

struct prufung
{
	char veranstaltung[MAX];
	int punkte;
	char datum[MAX];
	char professor[MAX];
	struct prufung *next;
};

Hier lese ich die Prüfungen ein:

do
		{
			printf("\nVeranstaltung: ");
			scanf("%s", veranstaltung);

			printf("Punkte: ");
			scanf("%d", &punkte);

			printf("Datum [TTMMJJJJ]: ");
			scanf("%s", datum);

			printf("Professor: ");
			scanf("%s", professor);

			if(einfugenPrufung(veranstaltung, punkte, datum, professor, &start_pointer) != 0)
			{
				printf("\nFehler beim Hinzufuegen einer Pruefung");
				return 1;
			}		
			printf("\nWollen Sie weitere Pruefungen eingeben [j/n]?\n");
		}
		while(getch() == 'j');

Ich hab jetzt einfach nur ein char-array für das Datum genommen. Wollte erstmal nur, dass es läuft.
Nun zum Problem:
Das datum soll in dieser Form angegeben werden: Datum[TTMMYYYY]: 01022009
In der Ausgabe soll es aber Konvertiert werden, so: 01.02.2009
Wie kriege ich das mit dem struct tm hin?

Hier die Ausgabe:

void prufungAusgeben(prufung_t *start_pointer)
{
	struct prufung *ptr = start_pointer;

	printf("\n\n+-----------------------------------+");
	printf("\nAusgabe der Pruefungen eines Studenten:\n");
	while(ptr != NULL)
	{	
		printf("\nVeranstaltung: %s", ptr->veranstaltung);
		printf("\nPunkte       : %d", ptr->punkte);
		printf("\nDatum        : %s", ptr->datum);
		printf("\nProfessor    : %s", ptr->professor);
		printf("\n");
		ptr = ptr->next;
	}
}

Kann mir jemand mit dem struct tm helfen??

Danke schonmal!
Gruß
Manda