Implementar Lista de Músicas

[jeantdz]

Olá pessoal,

Sinceramente, não tenho a mínima ideia de como fazer o exercício abaixo e entendo que não devo criar um tópico nesse estilo ? - Mas peço ajudar para que possam ao menos me dar uma luz ou de fato fazerem.

Citar

 

Implemente uma lista circular com nomes de músicas a qual tenha as seguintes características:

* Alocação de memória dinâmica para as músicas inseridas
* Uma função de busca de músicas por nomes
* Contagem da quantidade de músicas presentes na lista
* Remoção de músicas
* Adição de músicasA ultima música aponta para a primeira música da lista

 

 

Obrigado!

Editado Setembro 16, 2022 em 12:04 por jeantdz

[fredericopissarra]

Existem diversas maneiras de implementar listas, especialmente circulares... Eu recomendo a implementação de lista circular com encadeamento duplo e com um nó sentinela "cabeça" (head) vazio. Isso facilita um bocado a implementação e permite a implementação via polimorfismo (mesmo em C). Assim, uma lista vazia sempre terá um nó cabeça onde os links apontam para si mesmo... adicionar nós é questão de mudar os links apenas.

Isso também facilita a alocação, já que num novo nó só tem que obedecer a ordem dos links do nó "cabeça", com membros adicionados.

A decisão de como a lista será implementada é o primeiro passo (deixo para sua pesquisa e tentativa de implementação -- não mostrarei aqui).

Buscar por um nó da lista é simplesmente percorrer todos os elementos "depois" do nó "cabeça" até voltar a ele, comparando as "chaves" com a desejada...

Contar quantos nós existem é simplesmente percorrer toda lista à partir do próximo nó depois da "cabeça" até retornar a ela.

Apagar um nó é só modificar os links e dealocar a memória do nó.

Depois que tiver algum trabalho feito, poste aqui... Não acho que alguém vá fazer o trabalho por você...

[]s
Fred

[fredericopissarra]

Para tentar ajudar, eis um método de implementar lista encadeada dupla circular... começamos com uma estrutura do nó "cabeça":

struct list_head {
  struct list_head *prev_, *next_;
};

Uma lista vazia tem sempre esse nó e os links prev e next apontando para ele mesmo. Podemos criar um macro para isso:

#define LIST_HEAD_INIT(list__) { &(list_), &(list__) }

Podemos ter, também, uma inicialização em runtime:

static inline void list_init( struct list_head *list )
{ list->prev_ = list->next_ = list; }

Uma lista vazia poderia ser declarada (em tempo de compilação) como:

struct list_head mylist = LIST_HEAD_INIT(mylist);

Para facilitar a criação de nós "polimórficos" usarei o seguinte macro:

#define LIST_HEAD_PTRS struct list_head *prev_, *next_

Ou, em runtime, como:

{
  struct list_head list;

  list_init( &list );
  ...
}

O nosso nó pode ser declarado como:

struct music_entry {
  LIST_HEAD_PTRS;
  
  char *name;  // Nome da música (usarei como "chave").
  // ... outros campos aqui.
};

Com isso struct music_entry tem exatamente a mesma estrutura que struct list_head, nos dois primeiros membros (os links). De fato, qualquer estrutura que declare LIST_HEAD_PTRS como seu primeiro membro pode ser usada como nó para uma lista. Assim, todas as nossas rotinas para manipulação de lista podem, simplesmente, usar struct list_head como nó base.

Primeira rotina: Adicionar um nó na lista... De posse do ponteiro de um nó qualquer, podemos adicionar um nó depois ou antes desse:
 

// Rotina "privada" (repare o underscore no nome).
// Passamos o elemento a inserir na lista e os ponteiros prev e next
// que serão usados.
static inline void list_add_(struct list_head *element,
                             struct list_head *prev, struct list_head *next )
{
  element->prev_ = prev;
  element->next_ = next;
  prev->next_ = element;
  next->prev_ = element;
}

// Adiciona um elemento depois de um nó:
static inline void list_add_after( struct list_head *element,
                                   struct list_head *node )
{ list_add_( element, node, node->next_ ); }

// Adiciona um elemento antes de um nó:
static inline void list_add_before( struct list_head *element,
                                    struct list_head *node )
{ list_add_( element, node->prev, node ); }	

Segunda rotina: Apagar um nó.
 

// Rotina "privada". Dados os links prev e next, retira o elemento do meio.
static inline void list_del_( struct list_head *prev,
                              struct list_head *next )
{ prev->next_ = next; next->prev_ = prev; }

// Retira um elemento da lista.
static inline void list_del( struct list_head *element )
{ list_del_( element->prev, element->next ); }

Note que, se a lista estiver vazia e passarmos o ponteiro da "cabeça" nada é, de fato, feito (essa é a vantagem de usar esse nó "sentinela").

Uma outra rotina útil é a determinação se uma lista está vazia ou não... para isso precisamos usar SEMPRE o nó "cabeça". Algo semelhante é a determinação se estamos ou não na cabeça:

static inline int list_is_empty( struct list_head *head )
{ return head == head->next_; }

Para percorrermos todos os elementos da lista podemos usar um macro assim:

// iterção "para frente"
#define list_for_each( iter__, head__ ) \
  for ( iter__ = (head__)->next_; iter__ != (head__); iter__ = iter__->next_ )

// iteração "para trás"
#define list_for_earch_prev( iter__, head__ ) \
  for ( iter__ = (head__)->prev_; iter__ != (head__); iter__ = iter__->prev_ )

// iterção segura "para frente" (para o caso de queremos modificar
// um elemento na iterção). Usa um ponteiro "temporário" extra.
#define list_for_each_safe( iter__, tmp__, head__ ) \
  for ( iter__ = (head__)->next_, tmp__ = (iter__)->next_; \
        iter__ != (head__); \
        iter__ = tmp__, tmp__ = (iter__)->next_ )

// iterção segura "para trás" (para o caso de queremos modificar
// um elemento na iterção). Usa um ponteiro "temporário" extra.
#define list_for_each_prev_safe( iter__, tmp__, head__ ) \
  for ( iter__ = (head__)->prev_, tmp__ = (iter__)->prev_; \
        iter__ != (head__); \
        iter__ = tmp__, tmp__= (iter__)->prev_ )

Assim, considere se tivermos uma lista list e queremos procurar pela música "Owner of a lonely heart":

struct list_head *i;
struct music_entry *p;

list_for_each( i, &list )
{
  p = (struct music_entry *)i;

  if ( ! strcasecmp( p->name, "Owner of a lonely heart" ) )
    break;
}

// Não estamos na cabeça, entao achamos.
if ( i != &list )
  printf( "found '%s'.", p->name );

Acredito que, com isso, a implementação do programinha fique mais simples, huh?

PS: Alguns perceberão que essa implementação é praticamente idêntica a do Linux, mas, na verdade, esse método é o de Robert Sedgewick.

Editado Setembro 16, 2022 em 17:42 por fredericopissarra