Jump to content

Implementar Lista de Músicas


jeantdz

Recommended Posts

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!

Edited by jeantdz
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Edited by fredericopissarra
  • l33t 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...