C Struct's em C - Estrutura de Dados

[blvsman]

Olá, estou com dúvida a respeito desse código:

typedef struct no_ NO;
typedef struct lista_ LISTA;

struct lista_{
	NO *inicio;
	int profundidade;  /* prof. da lista general */
};

struct no_{
	union{
		ITEM atomo;  /*define o campo genérico que armazena atomo ou sublista */
		NO *sublista;
	}info;
	int tipo;
	NO *prox;
}

 

Por que ela definiu as structs em cima das structs ? Qual a diferença entre definir uma "struct" e uma "typedef struct"? O "union" é uma struct dentro de uma struct ?

[V!OLADOR]

Bom, ela (?) não definiu uma estrutura em cima da estrutura. Definiu-se dois identificadores, "lista_" e "no_" dentro do namespace "struct". Ambos vão representar a abstração de um tipo de objeto usado mais tarde. Na sintaxe de C o identificador e o namespace são usados juntos, por exemplo,

 

struct no_ a, b, c;

 

Ou seja, declaramos três objetos, a, b e c, do tipo "struct no_". A palavra-chave typedef permite que você possa renomear "struct no_" pra algo mais conveniente. Por exemplo,

 

NO a, b, c;

 

Leia-se "NO" como um apelido pra "struct no_". E no caso de uma union, representa-se tipos polimorficos. Ou seja, um objeto desse tipo pode receber um valor de cada tipo utilizado na sua definição. Mas um por vez. No teu exemplo, um objeto do tipo "info" pode receber um valor de um objeto de tipos "ITEM" ou "NO" (a.k.a "struct no_").

[arfneto]

São estruturas distintas.

Entenda que um nó não é uma lista. Uma lista é uma coleção de nós. collection em java, container em C++... Quando você programa uma lista com uma estrutura apenas de nós o resultado em geral é ruim e o trabalho muito maior. Em geral todas essas estruturas de dados tem uma parte de controle, que alguns chamam de metadados, e uma carga, um dado. E o que se busca é usar uma coisa genérica para poder reusar o resto da vida.

 

Um typedef define um alias, como o using de C++. Um nome alternativo. Ajuda muito quando tem nomes enormes por exemplo. E no mínimo em C evita que você tenha que escrever toda hora  struct isso ou aquilo. Só que no caminho essa informação de ser uma struct some e por isso todo mundo procura padronizar algo, como no seu exemplo usar o nome em maiúsculas, para diferenciar um tipo definido pelo usuário de uma variável definida pelo usuário.

 

union é um troço que costuma ser chamado de variant record e é um jeito de usar o mesmo espaço para guardar alternadamente várias coisas. Às vezes é só uma frescura mas tem casos em que é muito importante e salvador. 

 

Exemplo:

 

Tem umas estruturas, como árvores, que tem em cada nó muitos ponteiros, às vezes dezenas deles. E tem algum dado no nó. Um tipo muito importante de árvore --- trie ---  tem um único símbolo em cada nó terminal, as tais folhas. Mas cada nó pode ter dezenas de ponteiros. Então usar uma union como está no seu exemplo, permite que ao final do registro você tenha um valor que é um dado apenas, com digamos 4 bytes, e não tenha os 80 bytes de ponteiros por exemplo... Os registros tem tamanho variável mas compartilham um prefixo. E assim o enorme desperdício de espaço é evitado, porque todos os nós terminais tem a versão curtinha já que não apontam pra ninguém 

[blvsman]

@arfneto @V!OLADOR

 

Eu entendi e achei ótima a explicação. Só me confirma uma coisa, então na struct lista_ o ponteiro "NO *inicio" está apontando pra struct no_ ?

[arfneto]

2 horas atrás, blvsman disse:

@arfneto @V!OLADOR

 

Eu entendi e achei ótima a explicação. Só me confirma uma coisa, então na struct lista_ o ponteiro "NO *inicio" está apontando pra struct no_ ?

Sim. Para um particular NO. Como poderia ter um NO* fim.

 Em geral você quer inserir no início, no fim ou em alguma ordem. E usa ponteiros para frente e para trás em cada nó. Mas pode salvar também "favoritos", como uma lista dentro da lista, como numa lista de volumes para despachar e ter uma lista de produtos de pequeno volume, ou com prioridade