sorting a linked list with qsort()

**caduardo21** · 04-18-2005

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.

**xxxrugby** · 04-18-2005

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
http://cboard.cprogramming.com/showt...ighlight=qsort

**caduardo21** · 04-18-2005

How would I "keep checking" until the end of the linked list? That's what confuses me.

**caduardo21** · 04-18-2005

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.

**tjohnsson** · 04-19-2005

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...

**quzah** · 04-19-2005

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.

**caduardo21** · 04-19-2005

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

**caduardo21** · 04-19-2005

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

**quzah** · 04-19-2005

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.

**caduardo21** · 04-19-2005

Can you show me how to do that please? I'm not being lazy, I'm just really confused

**quzah** · 04-19-2005

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.

**caduardo21** · 04-19-2005

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

**quzah** · 04-19-2005

Code:

ptr[i]->proximo = NULL;

What is the value of i here?

Quzah.

Thread: sorting a linked list with qsort()

Thread Tools

Search Thread

Display

sorting a linked list with qsort()

Similar Threads

single linked list to double linked list (help)

Please Help - Problem with Compilers

Linked List

Linked list with two class types within template.

singly linked list