Sorting Simple Linked List - C

Question

[UPTATED WITH ANSWER AT THE END] I tried many things but I still don't know how I can do any sorting with a simple linked list. It should be sorted like the number saved on each node goes from the lower till the higher one. What can I do? I'm not allowed to sort the numbers as I save then on the list. The sorting must be made after the list is complete.

the code isn't completely ready yet

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define pi 3.14159265359
#define N 50

typedef struct lista{
    char palavra[N];
    int repeticao;
    struct lista *prox;
    } Lista;

Lista* lista_cria(){
    return NULL;
}

    int vazia(Lista *LISTA){
    if(LISTA->prox == NULL) return 1;
    else return 0;
}


void insere(Lista **lis, char *s){
    Lista* novo = (Lista*) malloc (sizeof(Lista));
    strcpy(novo->palavra, s);
    novo->prox = NULL;

    while (*lis)
        lis = &(*lis)->prox;
        *lis = novo;
}

Lista* retira(Lista* lis, char *s){
    Lista* ant = NULL;
    Lista* p = lis;

    while(p != NULL && (strcmp(s, p->palavra) != 0)){
        ant = p;
        p = p->prox;
    }

    if(p == NULL) return lis;
    if(ant == NULL) lis = p->prox;
    else ant->prox = p->prox;

    free(p);
    return lis;
}

void imprimir_lista(Lista* lis){
        Lista* p;
        for(p = lis; p != NULL; p = p->prox)
            printf("%s ", p->palavra);
    printf("\n \n");
}

int busca(Lista* lis, char *s){
        Lista *p;
    int cont = 0;

        for(p = lis; p != NULL; p = p->prox){
        if(strcmp(p->palavra, s) == 0) cont++;
    }

        return cont;
}

Lista* repeticao(Lista* lis, int i){
    Lista *p;
char s[50];
int cont;
printf("\n \n Doc%d", i);
    for(p = lis; p != NULL; p = p->prox){
    strcpy(s, p->palavra);
    cont = busca(p, s);
    printf(" \n\t %s: %d ", s, cont);
    p->repeticao = cont;
}

    return lis; /* return p*/
}

void liberar_lista(Lista *lis){
    Lista *aux = lis;
while (aux != NULL) {
    Lista *aux2 = aux->prox;
    free(aux);
    aux = aux2;
}
}

float produto_escalar (Lista *lis1, Lista *lis2) {
Lista *aux1 = lis1, *aux2 = lis2;
float resultado=0;
while (aux1 != NULL) {
    while (aux2 != NULL) {
        if (strcmp(aux1->palavra, aux2->palavra) == 0 ) {
            resultado+=(aux1->repeticao*aux2->repeticao);
            aux2 = aux2->prox;
            break;
        }
        else {
            aux2 = aux2->prox;
        }
    }
aux1 = aux1->prox;
aux2 = lis2;
}
return resultado;
}

float formula (Lista *lis1, Lista *lis2){
float resultado;
resultado = acos(produto_escalar(lis1, lis2)/(sqrt(produto_escalar(lis1, lis1))*sqrt(produto_escalar(lis2, lis2))));
resultado = (((resultado *50)*4)/pi)-100;
    if (resultado<0){
        resultado*=-1;
    }
return resultado;
}

void checa_plagio (float resultado) {
if (resultado>=50) {
    printf("\n O arquivo foi plagiado. \n\t Arquivo é %.3f%% parecido.", resultado);
}
else
    printf("\n O arquivo não foi plagiado \n\t Arquivo é %.3f%% parecido.", resultado);

}


int main () {
char arquivo1[] = "doc1.txt", arquivo2[] = "doc2.txt";
char string[50];
double resposta;
FILE *fp1, *fp2;
Lista *lista1, *lista2;

lista1 = lista_cria();
lista2 = lista_cria();

fp1 = fopen (arquivo1, "r+") ;

if (fp1 == NULL) {
    printf("\nErro. Não foi possível abrir o arquivo.\n");
    return EXIT_FAILURE;
}

while(!feof(fp1)){
    fscanf(fp1, "%s[A-Z a-z]", string);
    insere(&lista1, string);
}

fclose(fp1);

fp2 = fopen (arquivo2, "r+") ;

if (fp2 == NULL) {
    printf("\nErro. Não foi possível abrir o arquivo.\n");
    return EXIT_FAILURE;
}

while(!feof(fp2)){
    fscanf(fp2, "%s[A-Z a-z]", string);
    insere(&lista2, string);
}

fclose(fp2);

/*imprimir_lista(lista1);
imprimir_lista(lista2);*/

lista1 = repeticao(lista1, 1);
lista2 = repeticao(lista2, 2);

resposta = formula (lista1, lista2);
checa_plagio(resposta);


liberar_lista(lista1);
liberar_lista(lista2);

return EXIT_SUCCESS;
}

[UPDATED WITH ANSWER] THE CODE I USED TO SORT:

#define N 50
#include <stdlib.h>
#include <stdio.h>

typedef struct lista{
    char palavra[N];
    int repeticao;
    struct lista *prox;
} Lista;

Lista* sort (Lista *lis) {
    Lista *temp, *empurra;
    Lista *aux1, *aux2;
    Lista *guarda;

    aux1 = NULL;
    for (temp = lis; temp != NULL; temp = temp->prox){
        aux2 = temp;
        for (empurra=temp->prox; empurra != NULL; empurra = empurra->prox){
            if (empurra->repeticao < temp->repeticao){
                guarda = temp->prox;
                temp->prox = empurra->prox;
                if(guarda == empurra)
                    empurra->prox = temp;
                else
                    empurra->prox = guarda;
                if(aux2 != temp)
                    aux2->prox = temp;
                if(aux1)
                    aux1->prox = empurra;
                else
                lis = empurra;
                guarda = temp;
                temp = empurra;
                empurra = guarda;
            }
            aux2 = empurra;
        }
        aux1 = temp;
    }
return lis;
}

int main (){
return 0;
}

Welcome to stackoverflow.com. Please take some time to read the help pages, especially the sections named "What topics can I ask about here?" and "What types of questions should I avoid asking?". And more importantly, please read the Stack Overflow question checklist. You might also want to learn how to create a Minimal, Complete, and Verifiable example. — Some programmer dude
– Some programmer dude, Commented Aug 26, 2014 at 2:12
If you can live with bubble sort, that should be a simple algorithm to implement. en.wikipedia.org/wiki/Bubble_sort. — R Sahu
– R Sahu, Commented Aug 26, 2014 at 2:49
You should convert it to an array, sort it, and then convert it back to a linked list == O(nlogn) — Steve P.
– Steve P., Commented Aug 26, 2014 at 5:07

braindf · Accepted Answer · 2014-08-26 22:28:00Z

I think the most learning approach that you can take, it's to think that the linked list is an array. With that approach you can simply, access the elements of the array and apply a sort algorithm (like bubble sort) and when make the swap of the elements using the pointer to the elements. With that would be just a matter to redirect the pointers (to next elements) for the right elements.

Also, pay attention to the particular cases of the sorts (the beginning and the end of list, in this case).

Here's a example:

Suppose that we have the structure for the linked list:

typedef struct list{
        int n;
        struct list *next;
        } List;

And we want to sort the linked list using the int n, a code example would be something like this:

void sort (List * begin) {
    List *currentElement, *previousElement;
    int swapped = 1;
    while (swapped) {
        swapped = 1;
        while (swapped != 0) {
            swapped = 0;
            currentElement = begin;
            previousElement = NULL; //No previous element in the beginning of the list
            while(currentElement->next != NULL) { //Has another element, it's not the end of the list
                List *nextElement = currentElement->next;
                if(currentElement->n > nextElement->n) {
                    //swapping the elements
                    if (previousElement == NULL) { //is the first element
                        List *auxPtr = nextElement->next;
                        nextElement->next = currentElement;
                        currentElement->next = auxPtr;
                        begin = nextElement; //nextElement is the first element of the list now
                    }
                    else {
                        previousElement->next = nextElement;
                        currentElement->nextElement->next;
                        nextElement->next = currentElement;
                    }
                    previousElement = nextElement; //The nextElement is 'behind' the currentElement so it should be the previousElement
                    swapped = 1; // a swap was made
                    //The elements where swapped so currentElement is already in the 'position' of the next element, there is no need to upload it value
                }
                else { // there is no need to swap, just walk foward in the list
                    previousElement = currentElement;
                    currentElement = nextElement;
                }
            }
        }
    }
}

I used a simple bubble sort for the sorting

Collectives™ on Stack Overflow

Sorting Simple Linked List - C

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related