Lista jednokierunkowa, problem z sortowaniem.

Hej, muszę napisać listę jednokierunkową z napisami i ilością ich wystąpień. Dodawanie elementów ma być połączone z sortowaniem ich. Rozwiązałem prawie całą część problemu, niestety jeżeli chcę dodać jakiś wyraz leksykograficznie wyższy niż te, które są na liście, to program się wysypuje. Siedziałem trochę nad tym i trudno mi wymyśleć rozwiązanie, tym bardziej że sprawa komplikuje się przez nulla, który jest końcem tej listy...
Czy ktoś mógłby mi rzucić pomysł, byłbym wdzięczny za jakiś pseudokod czy cokolwiek.

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

#define TRUE 1
#define FALSE 0


struct element
{
	char *word;
	unsigned int arity;
    struct element *next;
};

struct element *head;

void dopisz();
void usun();
void wyswietl();

int main()
{
    head = (struct element*)malloc(sizeof(struct element));
    head = NULL;
	int isEnd = FALSE, answer;
	while(!isEnd)
	{
		printf("\n\t\tMENU\n");
		printf("[0] - zakonczenie programu\n");
		printf("[1] - dopisanie wyrazu\n");
		printf("[2] - usuniecie wyrazu\n");
		printf("[3] - wyswietlenie zawartosci listy\n");

		scanf("%d", &answer); getchar();

		switch(answer)
		{
			case 0:
				printf("Zakonczenie!\n");
				isEnd=TRUE;
				break;
			case 1:
				dopisz();
				break;
			case 2:
				usun();
				break;
			case 3:
				wyswietl();
				break;
			default:
				printf("Bledny wybor...\n");
		}
	}
	return 0;
}


void dopisz()
{
    char bufor[31];
    struct element *new;
    new = (struct element*)malloc(sizeof(struct element));
    if(new == NULL)
    {
        printf("Brak pamieci\n");
    }
    printf("Wyraz: ");
	scanf("%s", bufor); getchar();
	new->word = (char*)malloc(sizeof(char)*strlen(bufor));
	strcpy(new->word, bufor);
    new->arity=1;

    struct element *temp;
    for(temp=head; temp!=NULL; temp=temp->next)
    {
        if(strcmp(new->word, temp->word)==0)
        {
            temp->arity++;
            free(new);
            return;
        }
        else if( (head==NULL) )
        // lub else if( (head==NULL) || (strcmp(new->word, head->word)<0) )
        {
                new->next=head;
                head = new;
                return;
        }
        else if((strcmp(new->word, temp->word)>0) && (strcmp(new->word, temp->next->word)<0))
        {
            struct element *pom;
            pom = temp->next;
            temp->next = new;
            new->next = pom;
            return;
        }
//        else if(temp->next==NULL)
//        {
//            head->next = new;
//            new->next = NULL;
//            head=new;
//            return;
//        }

   }
//    new->next=head;
//    head = new;
}

void usun()
{
    char bufor[31];
    printf("\nJaki wyraz usunac?\t");
    scanf("%s", bufor); getchar();
    struct element *temp;
    for(temp=head; temp!=NULL; temp=temp->next)
    {
        if(strcmp(temp->word, bufor)==0)
        {
            if(temp->arity>1)
            {
                temp->arity--;
                printf("Zmniejszono ilosc wystapien wyrazu o 1.\n");
                return;
            }

            else
            {
                struct element *pom;
                pom = head;
                head = pom->next;
                free(pom);
                printf("Usunieto wyraz.\n");
                return;
            }
        }
    }
    printf("Nie ma takiego wyrazu!\n");
}


void wyswietl()
{
    struct element *temp;
    printf("\n");
    if(head==NULL)
        printf("Lista pusta\n");
	for  (temp=head; temp!=NULL; temp=temp->next)
	{
        printf("%s\t%d\t adres: %p\t \n", temp->word, temp->arity, temp);
	}
}
 

Pozdrawiam.

    /* najpierw szukamy */
    struct element *curr, *prev = NULL;
    int cmp = - 1;
    for(curr=head; curr!=NULL; curr=curr->next)
    {
        cmp = strcmp(curr->word, bufor);
        if (cmp >= 0) break;
        prev = curr;
    }
    
    if (cmp == 0) { // znaleziono
        curr->arity++;
    } else { // nie znaleziono, wstawiamy
        /* tworzymy element */
        struct element *new = (struct element*)malloc(sizeof(struct element));
        new->word = strdup(bufor);
        new->arity=1;

        /* łączymy z listą, mamy 2 wskaźniki do uaktualnienia */
        /* od nowego elementu do następnika */
        new->next=curr;
        /* i od poprzednika do nowego elementu */
        if (prev!=NULL) {
            prev->next = new;
        } else {
            head = new;
        }
    }

Operacje na liście powinieneś wydzielić do osobnych funkcji np. powyższy fragment. Podpowiedź: np. wyświetlenie komunikatu (printf) czy pobranie łańcucha (scanf) nie są operacjami na liście ;)

Podobnie powinieneś postąpić przy usuwaniu bo tam też jakieś niehalo jest. Czyli najpierw wyszukujesz element do usunięcia jednocześnie zapamiętując jego poprzednika. Następnie uaktualniasz odpowiednie wskaźniki.

Bardzo ładnie to napisałeś, niestety ja muszę dodatkowo to sortować w trakcie dodawania elementów. :( Usuwanie miałem jeszcze z wersji całkowicie początkowej, piszę ten program etapami i z początku dodawałem elementy po prostu z przodu, wtedy usuwanie chyba dobrze działało z tego co pamiętam. W każdym razie teraz przerobiłem to trochę, niestety jak zostaje jeden element na liście i chcę to usunąć, to mam nieprzewidziane działanie programu. Problem taki jak z sortowaniem chyba, ja czegoś w tej liście nie rozumiem. I to jest problem z tym początkiem listy chyba. Szkoda, że nie mogę znaleźć żadnego podobnego kodu w internecie, jakbym rzucił okiem na to rozwiązanie, to chyba bym zapamiętał do końca życia jak ta lista funkcjonuje. Siedzę przy tym już kilka dni. Te napisy na razie zostawię, takie szczegóły to poprawię jak wszystko będzie działać zgodnie z oczekiwaniami moimi i prowadzącego laboratoria na uczelni.

void usun()
{
    char bufor[31];
    printf("\nJaki wyraz usunac?\t");
    scanf("%s", bufor); getchar();

    struct element *curr;
    struct element *prev;
    curr = (struct element*)malloc(sizeof(struct element));
    prev = (struct element*)malloc(sizeof(struct element));


    for(curr=head; curr!=NULL; curr=curr->next)
    {
        if(strcmp(curr->word, bufor)==0)
        {
            if(curr->arity>1)
            {
                curr->arity--;
                printf("Zmniejszono ilosc wystapien wyrazu o 1.\n");
                return;
            }

            else
            {
                if(curr->next == NULL)
                {
                    prev->next = NULL;
                }
                else
                {
                    prev->next = curr->next;
                }

                free(curr);
                printf("Usunieto wyraz.\n");
                return;
            }
        }
        prev = curr;
    }
    printf("Nie ma takiego wyrazu!\n");
}

mba napisał(a):

Bardzo ładnie to napisałeś, niestety ja muszę dodatkowo to sortować w trakcie dodawania elementów. :(
Weź no jeszcze raz popatrz na to co napisałem. Najpierw jest wyszukiwanie miejsca, w które wstawić napis tak, aby utrzymać porządek posortowany.

Co do usuwania to tak jak pisałem - sposób masz praktycznie podany przeze mnie, usuwanie będzie podobne do dodawania. Zrób tak jak mówiłem, wyszukaj element i jego poprzednika. Początek kodu, czyli ta pierwsza pętla wyszukująca, będzie identyczny. Jak znajdziesz, to uaktualnij odpowiednie wskaźniki. Do uaktualnienia będzie zawsze 1 wskaźnik - wskaźnik 'next' poprzednika usuwanego elementu. Jeśli element nie ma poprzednika to, zamiast niego, do uaktualnienia jest głowa listy.

No i koniecznie wydziel to do osobnych funkcji, będzie ci łatwiej.

Spróbuj zrozumieć to co napisałem bo jest to właśnie przepis na to jak postępować z listą jednokierunkową. Jak czegoś nie rozumiesz to pytaj.

Napisałem już prawie wszystko, rozdzieliłem na funkcje. Problem mam tylko z usuwaniem pierwszego elementu. To ma być coś takiego? Z ifem jest na bank źle, ale else dobrze usuwa.

if(prev==NULL)
{
        head=curr->next;
        free(curr);
        return;
}
else
{
        prev->next = curr->next;
        free(curr);
        return;
}
 

edit:

Odpocząłem sobie chwilkę i zauważyłem błąd. Nie przypisywałem wskaźnikowi prev wartości NULL, stąd wynikało błędne działanie . Teraz już wszystko działa. Rozbiłem to troszkę na funkcje, ale nie wiem czy o to Ci chodziło.

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

#define TRUE 1
#define FALSE 0


struct element
{
	char *word;
	unsigned int arity;
    struct element *next;
};

struct element *head;

void dopisz();
void usun();
void show();
void del(char *bufor);
void add(char *bufor);

int main()
{
    head = (struct element*)malloc(sizeof(struct element));
    head = NULL;
	int isEnd = FALSE, answer;
	while(!isEnd)
	{
		printf("\n\t\tMENU\n");
		printf("[0] - zakonczenie programu\n");
		printf("[1] - dopisanie wyrazu\n");
		printf("[2] - usuniecie wyrazu\n");
		printf("[3] - wyswietlenie zawartosci listy\n");

		scanf("%d", &answer);

		switch(answer)
		{
			case 0:
				printf("Zakonczenie!\n");
				isEnd=TRUE;
				break;
			case 1:
				dopisz();
				break;
			case 2:
				usun();
				break;
			case 3:
				show();
				break;
			default:
				printf("Bledny wybor...\n");
		}
	}
	return 0;
}


void dopisz()
{
    char bufor[31];

    printf("Wyraz: ");
	scanf("%s", bufor);
	add(bufor);
}

void usun()
{
    char bufor[31];
    printf("\nJaki wyraz usunac?\t");
    scanf("%s", bufor);
    del(bufor);

}


void show()
{
    struct element *temp;
    printf("\n");
    if(head==NULL)
        printf("Lista pusta\n");
	for  (temp=head; temp!=NULL; temp=temp->next)
	{
        printf("%s\t%d\t adres: %p\t \n", temp->word, temp->arity, temp);
	}
}

void add(char *bufor)
{
    struct element *curr, *prev = NULL;
    int cmp = - 1;
    for(curr=head; curr!=NULL; curr=curr->next)
    {
        cmp = strcmp(curr->word, bufor);
        if (cmp >= 0) break;
        prev = curr;
    }

    if (cmp == 0)
    {
        curr->arity++;
    }
    else
    {
        struct element *new = (struct element*)malloc(sizeof(struct element));
        if(new == NULL)
        {
            printf("Brak pamieci\n");
            return;
        }
        new->word = strdup(bufor);
        new->arity=1;
        new->next=curr;
        if (prev!=NULL)
        {
            prev->next = new;
        }
        else
        {
            head = new;
        }
    }
}

void del(char *bufor)
{
    int cmp=-1;
    struct element *curr;
    struct element *prev = NULL;

    for(curr=head; curr!=NULL; curr=curr->next)
    {
        cmp = strcmp(curr->word, bufor);
        if (cmp >= 0) break;
        prev = curr;
    }

    if (cmp == 0)
    {
        if(curr->arity > 1)
        {
            curr->arity--;
            return;
        }
        else
        {
            if(prev==NULL)
            {
                head=curr->next;
                free(curr);
                return;
            }
            else
            {
                prev->next = curr->next;
                free(curr);
                return;
            }
        }
    }
    else
    {
        printf("Wyraz nie istnieje.\n");
    }
}
 

No i super. Jeszcze można troszkę dopieścić.

Wypisywanie komunikatu "Wyraz nie istnieje.\n" nie powinno się znaleźć w funkcji del tylko poza nią. Niech funkcja del zwraca wartość różną od zera gdy usuwanie się powiodło, zero gdy elementu nie znaleziono. Wtedy możesz zrobić coś takiego:

    printf("\nJaki wyraz usunac?\t");
    scanf("%s", bufor);
    if (del(bufor)) {
        puts("Usunieto wyraz.\n");
    } else {
        puts("Wyraz nie istnieje.\n");
    }

Druga sprawa to za dużo tych returnów, a free(curren) wystarczy w jednym miejscu. Kod się upraszcza:

    if (cmp == 0)
    {
        if(curr->arity > 1)
        {
            curr->arity--;
        }
        else
        {
            if(prev==NULL)
            {
                head=curr->next;
            }
            else
            {
                prev->next = curr->next;
            }
            free(curr);
        }
    }
    return cmp == 0;

Jeszcze kosmetyka. bufor to niezbyt trafna nazwa dla parametru funkcji add i del. Taka nazwa raczej sugeruje, że przekazujemy jakiś bufor który to nasza funkcja ma za zadanie wypełnić. Lepiej nazwać go item albo word.

Ok, poprawiłem to wszystko zgodnie ze wskazówkami, wywaliłem niepotrzebne klamry i program prezentuje się wybornie. Mam jeszcze pytanie, czy dałoby radę zaimplementować wyszukiwanie binarne w funkcji usuwania? Mogłoby to być szybsze niż przejeżdżanie po każdym elemencie.

Wyszukiwanie binarne wymaga random access, listy z reguły mają dostęp liniowy.

winerfresh napisał(a):

Wyszukiwanie binarne wymaga random access, listy z reguły mają dostęp liniowy.
Od listy do drzewa już nie daleko ;)