sorting a linked list with qsort()

This is a discussion on sorting a linked list with qsort() within the C Programming forums, part of the General Programming Boards category; First question: is it even possible? If yes, I'll continue... The struct looks like this: Code: struct data { char ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    204

    sorting a linked list with qsort()

    First question: is it even possible? If yes, I'll continue...

    The struct looks like this:
    Code:
    struct data {
        char id[6];
        char name[40];
        char course[20];
        char grade[3];
    };
    I read a file into the linked list and now I want to sort it by the name struct member. I have no idea as where to start, so can you guys give me some hints? Thanks.

  2. #2
    Registered User xxxrugby's Avatar
    Join Date
    Jan 2005
    Posts
    178
    Code:
    int compare_on_name_ascending( const void *a, const void *b)
    {
        return strcmp( ((data*)a)->name, ((data*)b)->name);
    }
    Look at this thread.
    Here AndyHunter explain excelent qsort
    Help here with qsort!
    Last edited by xxxrugby; 04-18-2005 at 03:03 PM.
    Sorry for spelling errors, not English!
    xxxrugby: "All Human Race Will Die From My Hand!"
    xxxrugby: "We are all philosophers, when question is about politics!"

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    How would I "keep checking" until the end of the linked list? That's what confuses me.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    I was able to come up with this:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int numero_nodes(void);
    int comparar_nome(const void *, const void *);
    void remover_newline(char *); /* função para remover o \n do final do array */
    void ordenar_nome(const int);
    
    struct dados {
    	char matricula[6]; /* a função fgets() vai ler até 6 - 1 (o que é 5) */
    	char nome[41];     /* mesma coisa aqui... serão lidos até 40 caracteres */
    	char curso[21];    /* serão lidos 20 caracteres */
    	char nota[3];      /* serão lidos 2 caracteres */
    	struct dados *proximo;
    };
    
    struct dados *primeiro = NULL;
    
    int main(void)
    {
    	int nodes;
    	char ch;
    	char linha[41];
    	FILE *dados;
    	struct dados *novo;
    	struct dados *guia;
    	
    	
    	
    	dados = fopen("dados.txt", "r");
    	if(dados == NULL){
    		printf("dados.txt - arquivo desconhecido\n");
    		getchar();
    		exit(1);
    	}
    
    	while(fgets(linha, sizeof(linha), dados) != NULL){
    
    		novo = (struct dados *)malloc(1 * sizeof(*novo));
    		
    		if(novo == NULL){
    			printf("Erro alocando memoria...");
    			getchar();
    			exit(1);
    		}
    
    		novo->proximo = NULL;
    		
    		remover_newline(linha);
    		strcpy(novo->matricula, linha);
    
    		fgets(linha, sizeof(linha), dados);
    		remover_newline(linha);
    		strcpy(novo->nome, linha);
    
    		fgets(linha, sizeof(linha), dados);
    		remover_newline(linha);
    		strcpy(novo->curso, linha);
    
    		fgets(linha, sizeof(linha), dados);
    		remover_newline(linha);
    		strcpy(novo->nota, linha);
    
    		/* pula a linha em branco */
    		fgets(linha, sizeof(linha), dados);
    
    		if(primeiro == NULL)
    			primeiro = novo;
    
    		else{
    			guia = primeiro;
    
    			while(guia->proximo != NULL)
    				guia = guia->proximo;
    
    			guia->proximo = novo;
    		}
    	}
    
    	fclose(dados);
    
    	printf("Arquivo lido...\n\n");
    
    	printf("Ordenar por\n");
    	printf("[1] Nome\n");
    	printf("[2] Nota\n");
    	printf("> ");
    	ch = getchar();
    
    	nodes = numero_nodes();
    
    	if(ch == '1')
    		ordenar_nome(nodes);
    
    	/*else
    		ordenar_nota();*/
    
    	return 0;
    }
    
    void remover_newline(char *linha)
    {
    	char *ptr;
    
    	ptr = strchr(linha, '\n');
    	if(ptr != NULL)
    		*ptr = '\0';
    }
    
    int numero_nodes(void)
    {
    	int quantidade = 0;
    	struct dados *guia;
    
    	guia = primeiro;
    	while(guia->proximo != NULL){
    		++quantidade;
    		guia = guia->proximo;
    	}
    
    	return quantidade;
    }
    
    void ordenar_nome(const int nodes)
    {
    	struct dados *guia;
    	
    	qsort((void *)primeiro, nodes, sizeof(*primeiro) * nodes, comparar_nome);
    
    	guia = primeiro;
    	while(guia->proximo != NULL){
    		printf("%s\n", guia->matricula);
    		printf("%s\n", guia->nome);
    		printf("%s\n", guia->curso);
    		printf("%s\n\n", guia->nota);
    
    		guia = guia->proximo;
    	}
    }
    
    int comparar_nome(const void *nome1, const void *nome2)
    {
    	return strcmp(((dados *)nome1)->nome, ((dados *)nome2)->nome);
    }
    When I choose option number 1 (sort by name), here's the output:
    Code:
    Arquivo lido...
    
    Ordenar por
    [1] Nome
    [2] Nota
    > 1
    ════44
    
    
    a da Silva Sauro
    Here's the file the program reads:
    Code:
    20451
    Denis Rocha da Silva
    Arquitetura Arquiter
    5
    
    98364
    Tom Hanks
    Teatro
    38
    
    44076
    Nicolas Cage
    Futebol
    44
    
    10902
    Sabrina da Silva Sauro
    Basquete
    3
    
    12008
    Charles Petzold
    Tiro ao alvo
    12
    I really don't know what is wrong. Help me fix my program please. Thanks.

  5. #5
    SleepWalker tjohnsson's Avatar
    Join Date
    Apr 2004
    Posts
    70
    No you cannot use qsort for linked lists, qsort is for arrays
    Copy your linked list to the array, sort it and rearrange your list nodes
    in order of an array...
    -- Add Your Signature Here --

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Use an array of pointers to nodes, and sort that. Then construct the linked list from it by just moving through the sorted array and reasigning the "next" and "previous" pointers.

    Or you could just do it the easy way, and sort the list as you build it.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Hum, I see. I know how many nodes I'll need because I have a function that counts them after I'm done with the linked list. I was trying to declare an array of pointers to nodes like this but I get a compiler error...
    Code:
    struct dados *array[qtd_nodes];
    Help please

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void remover_newline(char *); /* função para remover o \n do final do array */
    int quantidade_nodes(void);
    void ordenar_nome(struct dados **, const int);
    int comparar_nome(const void *, const void *);
    
    struct dados {
    	char matricula[6]; /* a função fgets() vai ler até 6 - 1 (o que é 5) */
    	char nome[41];     /* mesma coisa aqui... serão lidos até 40 caracteres */
    	char curso[21];    /* serão lidos 20 caracteres */
    	char nota[3];      /* serão lidos 2 caracteres */
    	struct dados *proximo;
    };
    
    struct dados *primeiro = NULL;
    
    int main(void)
    {
    	int i = 0;
    	char ch;
    	char linha[41];
    	int qtd_nodes;
    	FILE *arquivo;
    	struct dados *novo;
    	struct dados *guia;
    	struct dados **ptr;
    	
    	
    	
    	arquivo = fopen("dados.txt", "r");
    	if(arquivo == NULL){
    		printf("dados.txt - arquivo desconhecido\n");
    		getchar();
    		exit(1);
    	}
    
    	while(fgets(linha, sizeof(linha), arquivo) != NULL){
    
    		novo = (struct dados *)malloc(1 * sizeof(*novo));
    		
    		if(novo == NULL){
    			printf("Erro alocando memoria...");
    			getchar();
    			exit(1);
    		}
    
    		novo->proximo = NULL;
    		
    		remover_newline(linha);
    		strcpy(novo->matricula, linha);
    
    		fgets(linha, sizeof(linha), arquivo);
    		remover_newline(linha);
    		strcpy(novo->nome, linha);
    
    		fgets(linha, sizeof(linha), arquivo);
    		remover_newline(linha);
    		strcpy(novo->curso, linha);
    
    		fgets(linha, sizeof(linha), arquivo);
    		remover_newline(linha);
    		strcpy(novo->nota, linha);
    
    		/* pula a linha em branco */
    		fgets(linha, sizeof(linha), arquivo);
    
    		if(primeiro == NULL)
    			primeiro = novo;
    
    		else{
    			guia = primeiro;
    
    			while(guia->proximo != NULL)
    				guia = guia->proximo;
    
    			guia->proximo = novo;
    		}
    	}
    
    	fclose(arquivo);
    
    	printf("Arquivo lido...\n\n");
    
    	printf("Ordenar por\n");
    	printf("[1] Nome\n");
    	printf("[2] Nota\n");
    	printf("> ");
    	ch = getchar();
    
    	qtd_nodes = quantidade_nodes();
    	guia = primeiro;
    	ptr = (struct dados **)malloc(qtd_nodes * sizeof(*novo));
    
    	while(guia->proximo != NULL){
    		ptr[i] = guia;
    		guia = guia->proximo;
    		i++;
    	}
    
    	if(ch == '1')
    		ordenar_nome(ptr, qtd_nodes);
    
    	/*else
    		ordenar_nota();*/
    
    	return 0;
    }
    
    void remover_newline(char *linha)
    {
    	char *ptr;
    
    	ptr = strchr(linha, '\n');
    	if(ptr != NULL)
    		*ptr = '\0';
    }
    
    int quantidade_nodes(void)
    {
    	int quantidade = 0;
    	struct dados *guia;
    
    	guia = primeiro;
    	
    	while(guia->proximo != NULL){
    		guia = guia->proximo;
    		quantidade++;
    	}
    
    	return quantidade;
    }
    
    void ordenar_nome(struct dados **ptr, const int qtd_nodes)
    {
    	int i = 0;
    
    	qsort((void *)ptr, qtd_nodes, sizeof(*primeiro) * qtd_nodes, comparar_nome);
    
    	while(ptr[i]->proximo != NULL){
    		printf("%s\n", ptr[i]->matricula);
    		printf("%s\n", ptr[i]->nome);
    		printf("%s\n", ptr[i]->curso);
    		printf("%s\n\n", ptr[i]->nota);
    
    		ptr[i] = ptr[i + 1]->proximo;
    		i++;
    	}
    }
    
    int comparar_nome(const void *nome1, const void *nome2)
    {
    	return strcmp(((dados *)nome1)->nome, ((dados *)nome2)->nome);
    }
    It at least prints something on the screen, but the sorting doesn't seem to be working and the program closes with an error

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I've already told you, sorting an array of structures does not reassociate all of the "next" pointers for you. After you call sort, you have to walk through your array, and assign all of the pointers again correctly.

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Can you show me how to do that please? I'm not being lazy, I'm just really confused

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    while not at the end of the array
        set this array's node's next pointer to the next one in the array
    now set the last one's next to null
    It's not a complex issue.

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Do you mean like this?
    Code:
    void ordenar_nome(struct dados **ptr, const int qtd_nodes)
    {
    	int i;
    
    	qsort((void *)ptr, qtd_nodes, sizeof(*primeiro) * qtd_nodes, comparar_nome);
    
    	for(i = 0; i < qtd_nodes; i++)
    		ptr[i]->proximo = ptr[i + 1];
    
    	ptr[i]->proximo = NULL;
    
    	i = 0;
    
    	while(ptr[i]->proximo != NULL){
    		printf("%s\n", ptr[i]->matricula);
    		printf("%s\n", ptr[i]->nome);
    		printf("%s\n", ptr[i]->curso);
    		printf("%s\n\n", ptr[i]->nota);
    
    		ptr[i] = ptr[i + 1]->proximo;
    		i++;
    	}
    }
    If yes, now all I get is that little window asking me if I want to send the error report to MS

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    ptr[i]->proximo = NULL;
    What is the value of i here?

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  2. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21