Sobre o uso de multi-listas em c

[Philipe de Souza]

Pessoal, muito boa tarde.

 

Estou com uma dificuldade imensa em implementação de multi-listas em C e quase não encontro nada nas pesquisas que realizei na internet.

Não estou pedindo códigos prontos, e sim um material de estudo ou até mesmo exemplos práticos sobre isso.

 

No trabalho em questão, o sistema tem 5 atributos (cpf, nome, sexo, idade e ocupação) e os armazenam nas tais 'multi-listas',

essa multi-lista será composta por lista de pessoas do sexo masculino, lista de pessoas do sexo feminino, de 18-35 anos, só analistas, só desenvolvedores e por aí vai.

 

A minha dúvida fica por conta de como vai ficar a implementação, pois realmente não consegui compreender a lógica!

Se alguém souber algum exemplo pratico similar eu agradeceria muito.

 

Obrigado.

 

[1freakday]

Tem certeza que se chama multi-lista, acredito que seja lista duplamente encadeada, segue um artigo útil para estudo:

http://www.out4mind.com/listas-duplamente-ligadas-em-c-parte-i/

[Philipe de Souza]

Olá 1freakday, sim certeza absoluta, o nome é multi-lista, conhecido em inglês como 'multi-linked list'. 

 

Já até estudei lista duplamente encadeada, mas não consigo encontrar a forma de implementar da maneira que o professor solicitou na especificação do trabalho. Na 'multi-lista' deve-se varrer todo o vetor para encontrar um dado em especial, é como se fosse uma 'lista de listas'.

Sem mais delongas, segue especificação do exercício:

http://moodlep.catolica-es.edu.br/moodle/pluginfile.php/81928/mod_resource/content/1/ED-ICA04-Sistema de Emprego.pdf

Desculpe a folga pessoal, se estou postando aqui é porque realmente estou desesperado.

 

 

[danieltm64]

Olá, Philipe.

 

Apenas para recordar, uma lista simplesmente encadeada é uma lista encadeada em que cada nodo contém, além do dado a ser armazenado, um apontador para o nodo seguinte, enquanto uma lista duplamente encadeada é uma lista encadeada em que cada nodo contém, além do dado a ser armazenado, dois apontadores: um para o nodo anterior e outro para o nodo seguinte.

 

Uma multi-lista é uma lista encadeada em que cada nodo contém múltiplos apontadores. Uma lista duplamente encadeada é um caso particular de multi-lista, mas o termo ‘multi-lista’ é comumente usado para referir-se a listas encadeadas com 3 apontadores ou mais.

 

O propósito de multi-listas é ordenar um único conjunto de dados de várias maneiras eficientemente. Por exemplo, suponhamos que cada elemento da lista representa um funcionário, e cada funcionário tem nome, salário e sexo. Cada nodo da lista contém um funcionário e 3 apontadores. Assim você pode ter um único conjunto de funcionários e, de maneira muito eficiente, você pode percorrer essa lista de funcionários em diversas ordens, como: percorrer por nome em ordem alfabética, percorrer por salário em ordem crescente, e percorrer por sexo. Exemplo:

 

Começo:

* Apontador (Nome): Nodo 1

* Apontador (Salário): Nodo 2

* Apontador (Sexo Masculino): Nodo 3

* Apontador (Sexo Feminino): Nodo 2

 

Nodo 1

* Nome: Antônio

* Salário: 3000

* Sexo: Masculino

* Apontador (Nome): Nodo 3

* Apontador (Salário): NULL

* Apontador (Sexo): NULL

 

Nodo 2

* Nome: Paula

* Salário: 1000

* Sexo: Feminino

* Apontador (Nome): NULL

* Apontador (Salário): Nodo 3

* Apontador (Sexo): NULL

 

Nodo 3

* Nome: Bernardo

* Salário: 2000

* Sexo: Masculino

* Apontador (Nome): Nodo 2

* Apontador (Salário): Nodo 1

* Apontador (Sexo): Nodo 1

 

Como você pode ver, cada nodo possui 3 apontadores, e se você sempre seguir o apontador associado ao nome do funcionário, você percorrerá a lista em ordem alfabética dos nomes dos funcionários, e se você sempre seguir o apontador associado ao salário do funcionário, você percorrerá a lista em ordem crescente de salário, e assim por diante. Assim, o dado só existe uma vez e eficientemente você consegue ordenar os dados de acordo com diversos critérios.

 

Para verificar isso, note que o apontador associado ao nome no começo aponta para o nodo 1, cujo funcionário tem nome começando com A, e esse nodo aponta para o nodo 3, cujo funcionário tem nome começando com B, e esse nodo aponta para o nodo 2, cujo funcionário tem nome começando com P. Assim os funcionários estão ordenados por nome em ordem alfabética. O mesmo vale para o salário, pois o começo aponta para o nodo 2, cujo funcionário tem o menor salário, e esse nodo aponta para o nodo 3, cujo funcionário tem um salário maior, e esse nodo aponta para o nodo 1, cujo funcionário tem o maior salário. Com relação ao sexo masculino, o começo aponta para o nodo 3, cujo funcionário é homem, e esse nodo aponta para o nodo 1, cujo funcionário também é homem. Já com o sexo feminino, o começo aponta para o nodo 2, cujo funcionário é mulher.

 

Com base nesse exemplo, um elemento da multi-lista poderia ser definido da seguinte forma em C:

struct nodo
{
    char *nome;
    int salario;
    bool sexo;

    struct nodo *proximoNome;
    struct nodo *proximoSalario;
    struct nodo *proximoSexo;
}

Ou, se você quiser permitir percorrer a lista de trás pra frente, um elemento da multi-lista poderia ser definido assim:

struct nodo
{
	char *nome;
	int salario;
	bool sexo;

	struct nodo *anteriorNome;
	struct nodo *proximoNome;

	struct nodo *anteriorSalario;
	struct nodo *proximoSalario;

	struct nodo *anteriorSexo;
	struct nodo *proximoSexo;
}

 

 

[Philipe de Souza]

Boa tarde Daniel, agradeço desde já pela sua paciência e boa vontade em me ajudar.

 

Estou tentando começar o código mas está dando alguns erros de programação, seria algo em torno disso?

 

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

typedef struct node{
  int CPF;
  char *nome;
  char *sexo;
  char *ocupacao;

  struct node *proximo;
  struct node *byCPF;
  struct node *byNome;
  struct node *bySexo;
  struct node *byOcu;
}Node;

void insert (Node *n, Node newNode) {

  if (n == NULL) {
    n = &newNode;
    newNode.proximo = NULL;
  }
  else {
    n = n->proximo;
    insert(n, newNode);
  }

}

void ins_by (Node *n, Node newNode) {
  if ( (newNode.CPF == n->CPF) && (n->byCPF == NULL) ) {
    n->byCPF = &newNode;
    newNode.byCPF == NULL;
  }
  if ( (strcmp(newNode.nome, n->nome)) && (n->byNome == NULL) ) {
    n->byNome = &newNode;
    newNode.byNome == NULL;
  }
  if ( (strcmp(newNode.sexo, n->sexo)) && (n->bySexo == NULL) ) {
    n->bySexo = &newNode;
    newNode.bySexo == NULL;
  }
  if ( (strcmp(newNode.ocupacao, n->ocupacao)) && (n->byOcu == NULL) ) {
    n->byOcu = &newNode;
    newNode.byOcu == NULL;
  }
  if (n->proximo != NULL) {
    n = n->proximo;
    ins_by (n, newNode);
  }
}

int main (int argc, char **argv) {
  Node *myList = NULL;
  Node *newNode = (Node *) malloc(sizeof(Node));

  printf("Digite um nome: ");
  scanf("%s", &newNode->nome);
  printf("Digite um CPF: ");
  scanf("%d", &newNode->CPF);
  printf("Digite o sexo: ");
  scanf("%s", &newNode->sexo);
  printf("Digite a ocupação: ");
  scanf("%s", &newNode->ocupacao);
  newNode->proximo = NULL;

  insert(myList, newNode);
  ins_by(myList, newNode);

  return 0;
}