implementação lista ligada 'multiuso' em puro C

StackOverflow https://stackoverflow.com/questions/736307

Pergunta

Este não é exatamente uma questão técnica, desde que eu sei C tipo de suficiente para fazer as coisas que eu preciso (quero dizer, em termos de não 'deixar o get linguagem em seu caminho'), assim que esta questão é basicamente um 'que rumo tomar' questão.

Situação é: Atualmente, estou tomando um algoritmos avançados claro, e por uma questão de 'crescer como programadores', eu sou obrigado a utilizar C puro para implementar os trabalhos práticos (que funciona bem: praticamente qualquer pequeno erro você faça realmente força você a entender completamente o que você está fazendo, a fim de corrigi-lo). No decurso da execução, eu, obviamente, correr para o problema de ter de implementar as estruturas de dados 'de base' de baixo para cima: na verdade, não só ligados listas, mas também pilhas, árvores, et cetera

.

Estou concentrando-se em listas neste tópico porque é tipicamente uma estrutura de eu acabar usando muito no programa, seja como uma estrutura de 'main' ou como uma estrutura de 'ajudante' para outros maiores (por exemplo, um hash árvore que resolve conflitos usando uma lista ligada).

Isto requer que os elementos da lista lojas de lotes de diferentes tipos. Estou assumindo aqui como uma premissa que eu não quero re-código da lista para cada tipo. Então, eu posso vir acima com estas alternativas:

  • Fazer uma lista de ponteiros void (kinda deselegante; mais difícil de debug)
  • Fazendo apenas uma lista, mas ter um união como 'tipo de elemento', contendo todos os tipos de elementos que vou usar no programa (mais fácil de depurar; resíduos espaço se elementos não são todos do mesmo tamanho )
  • Usar uma macro pré-processador para gerar o código para cada tipo, no estilo de SGLIB , 'imitando' C ++ 's STL (solução criativa; não desperdiça espaço; elementos têm o tipo explícito que realmente são quando eles são devolvidos; qualquer alteração no código de lista pode ser muito dramática )
  • O seu ideia / solução

Para tornar a questão clara: qual uma das opções acima é melhor

PS: Desde que eu sou basicamente em um contexto acadêmico, eu também estou muito interessado na opinião de pessoas que trabalham com pura C lá fora na indústria. Eu entendo que a maioria dos programadores C puro estão na área de dispositivos incorporados, onde eu não acho que esse tipo de problema que estou enfrentando é comum. No entanto, se alguém aí sabe como ele é feito 'no mundo real', eu estaria muito interessado em sua opinião.

Foi útil?

Solução

A void * é um pouco de dor em uma lista ligada desde que você tem que gerenciar alocação lo da separadamente para a própria lista. Uma abordagem que eu usei no passado é ter uma 'variável dimensionada' estrutura como: 

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

Agora eu percebo que não olhar de tamanho variável, mas vamos alocar uma estrutura assim: 

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

Agora você tem um nó que, para todos os efeitos, parece que isso: 

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

ou, na forma de gráfico (em que os meios [n] n bytes): 

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

Isto é, supondo que você sabe como lidar com a carga corretamente. Isso pode ser feito da seguinte forma: 

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

Essa linha elenco simplesmente lança o endereço do caráter payload (no tipo tNode) de ser um endereço do tipo tPerson carga real.

Usando esse método, você pode carregar qualquer tipo de carga que você quer em um nó, mesmo diferentes tipos de carga útil em cada nó , sem o espaço desperdiçado de uma união. Este desperdício pode ser visto com o seguinte: 

union {
    int x;
    char y[100];
} u;

onde 96 bytes são desperdiçados a cada vez que você armazenar um tipo inteiro na lista (para um inteiro de 4 bytes).

O tipo de carga no tNode permite detectar facilmente que tipo de carga útil este nó está realizando, assim que seu código pode decidir como processá-lo. Você pode usar algo ao longo das linhas de: 

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

ou (provavelmente melhor): 

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Outras dicas

My $ .002:

  • Fazer uma lista de ponteiros void (kinda diselegant; mais difícil de debug)

Esta não é uma má escolha, IMHO, se você deve escrever em C. Você pode adicionar métodos API para permitir que o aplicativo para fornecer um método print () para facilitar a depuração. Métodos semelhantes podem ser invocado quando (por exemplo) os itens são adicionados ou removidos da lista. (Para listas ligadas, isso geralmente não é necessário, mas para estruturas mais complexas de dados - tabelas de hash, por exemplo) -. Às vezes pode ser um salva-vidas)

  • Fazendo apenas uma lista, mas ter uma união como 'tipo de elemento', contendo todos os tipos de elementos que vou usar no programa (mais fácil de depurar; resíduos espaço se elementos não são todos do mesmo tamanho)

Gostaria evitar este como a peste. (Bem, você pediu.) Ter um manualmente-configurado, a dependência em tempo de compilação da estrutura de dados para seus tipos contidos é o pior de todos os mundos. Mais uma vez, IMHO.

  • Usar uma macro pré-processador para gerar o código para cada tipo, no estilo de SGLIB (sglib.sourceforge.net), 'imitando' s C ++ 'STL (solução criativa; não desperdiça espaço; elementos têm o tipo explícito que eles realmente são quando eles são devolvidos; qualquer alteração no código de lista pode ser muito dramático)

idéia intrigante, mas desde que eu não sei SGLIB, eu não posso dizer muito mais do que isso.

  • O seu ideia / solução

Eu iria com a primeira escolha.

Eu fiz isso no passado, em nosso código (que já foi convertido em C ++), e na época, decidiu sobre a abordagem void *. Eu só fiz isso para flexibilidade -. Estávamos quase sempre armazenar um ponteiro na lista de qualquer maneira, e a simplicidade da solução, e usabilidade do que compensados ??(para mim) as desvantagens para as outras abordagens

Dito isto, houve um tempo em que causou algum erro desagradável que era difícil de debug, então definitivamente não é uma solução perfeita. Eu acho que ainda é aquele que eu tomaria, embora, se eu estava fazendo isso de novo agora.

Usando uma macro pré-processador é a melhor opção. O href="http://isis.poly.edu/kulesh/stuff/src/klist/" Linux lista ligada do kernel é uma excelente implementação de um eficient de uma circular ligada lista em C. é muito portátil e fácil de usar. aqui uma versão autónoma do Linux Kernel 2.6.29 list.h cabeçalho .

O FreeBSD / OpenBSD sys / fila é outra opção boa para uma lista ligada macro genérico baseado

Eu não codificado C em anos, mas GLib reivindicações para fornecer "um grande conjunto de funções utilitárias para strings e estruturas de dados comuns", entre as quais estão ligadas listas.

Embora seja tentador pensar sobre como resolver este tipo de problema usando as técnicas de outro idioma, por exemplo, os genéricos, na prática, raramente é uma vitória. Há provavelmente algumas soluções enlatados que obtê-lo direito na maioria das vezes (e dizer-lhe em sua documentação quando eles obtê-lo errado), usando que pode perder o ponto do trabalho, então eu pensaria duas vezes sobre ele. Para um número muito reduzido número de casos, pode ser feasable para rolar o seu próprio, mas para um projeto de qualquer tamanho razoável, não é provável que seja a pena o esforço de depuração.

Ao contrário, Ao programar em linguagem x, você deve usar as expressões idiomáticas da língua x. Fazer java não escrita quando você está usando python. Não escreva C quando você está usando esquema. Não escreva C ++ quando você está usando C99.

Eu, eu provavelmente acabam usando algo parecido com a sugestão de Pax, mas realmente usar uma união de char [1] e void * e int, para fazer os casos comuns conveniente (e um tipo de bandeira enumed)

(Eu também, provavelmente, acabar implementando uma árvore de Fibonacci, justa causa que soa puro, e você só pode implementar RB Árvores tantas vezes antes que ele perde seu sabor, mesmo que é melhor para os casos comuns que iria ser utilizado.)

Editar: com base no seu comentário, parece que você tem um caso muito bom para a utilização de uma solução enlatada. Se seu instrutor permite que ele, ea sintaxe que oferece sente confortável, dar um giro.

Este é um problema bom. Há duas soluções que eu gosto:

  • Dave Hanson C Interfaces e Implementações usa uma lista de void * ponteiros, o que é bom o suficiente para mim.

  • Para o meu estudantes , eu escrevi um roteiro awk para gerar funções de lista de tipo específico . Comparado com macros de pré-processamento, que requer uma etapa de compilação extra, mas a operação do sistema é muito mais transparente para os programadores, sem muita experiência. E isso realmente ajuda a tornar o caso para o polimorfismo paramétrico, que vêem mais tarde, em seu currículo.

    Aqui está o que um conjunto de funções parece com: 

    int      lengthEL (Explist *l);
Exp*     nthEL    (Explist *l, unsigned n);
Explist *mkEL     (Exp *hd, Explist *tl);

    O script awk é um horror 150-line; ele procura código C durante typedefs e gera um conjunto de funções de lista para cada um. É muito antiga; Eu provavelmente poderia fazer melhor agora: -)

Eu não daria uma lista de sindicatos a hora do dia (ou espaço no meu disco rígido). Não é seguro, e não é extensível, de modo que você pode também apenas usar void * e ser feito com ele.

Uma melhoria sobre tornando-se uma lista de void * seria tornando-se uma lista de estruturas que contêm a * vazio e alguns meta-dados sobre o que os void * aponta para, incluindo seu tipo, tamanho, etc.

Outras idéias:. Incorporar um interpretador Perl ou Lisp

Ou ir a meio caminho:. Ligação com a biblioteca Perl e torná-lo uma lista de Perl SVs ou algo

Eu provavelmente ir com o * abordagem vazio mim mesmo, mas ocorreu-me que você pode armazenar seus dados como XML. Em seguida, a lista pode ter apenas um char * para os dados (que você iria analisar na demanda por qualquer sub elementos que você precisa) ....

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top