O que é um nó em C?
Estou trabalhando no speller cs50 pset5, e na palestra eles apresentam uma coisa nova chamada nodes. O que é um nó? Eu realmente não entendi o que eles disseram no vídeo. Quando tentei pesquisar no Google, encontrei alguns sites que explicavam o que é um nó, mas não entendi direito. Eu sou novo em c, então não estou acostumado com o que chamo de 'palavras de codificação'. Por exemplo, encontrei isso em um site sobre nós: um array dinâmico pode ser estendido dobrando o tamanho, mas há sobrecarga associada à operação de copiar dados antigos e liberar a memória associada à estrutura de dados antiga. O que isto quer dizer? Por favor, me ajude a descobrir o que é um nó porque eles parecem importantes e úteis, especialmente para pset5. Meu nó é definido assim:
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
Aqui está o link para o passo a passo do speller pset5: https://cs50.harvard.edu/x/2020/psets/5/speller/
Respostas
Nó é uma terminologia comum usada para demonstrar um único bloco linked listou treeestruturas de dados relacionadas.
É uma convenção chamá-lo de nó, caso contrário, você pode chamá-lo com qualquer nome.
Padrão
C ++
struct node{
int data;
int *next;
};
ou em Python
class Node:
def __init__(self, data, next= None):
self.data = data
self.next = next
Mas você pode chamá-lo com qualquer nome
Não Padrão
C ++
struct my_own_name{
int data;
int *nextptr;
};
ou em python
class my_own_name:
def __init__(self, data, next=None):
self.data = data
self.next = next
Um "nó" é um conceito da teoria dos grafos. Um gráfico consiste em nós (vértices) e arestas que conectam os nós.
Um nó em C pode ser representado como uma estrutura (a struct) que possui todos os elementos de dados necessários "a bordo" para implementar um gráfico. Opcionalmente, pode ser necessária uma estrutura que represente as bordas.
Exemplo:
typedef struct NODE {
int node_id;
struct EDGE *edgelist;
} tNode;
typedef struct EDGE {
tNode *from, *to;
struct EDGE *next;
} tEdge;
Nota: o termo "nó" também pode ser usado em outros contextos, por exemplo, os nós de uma árvore binária, os nós de uma lista, etc.
Um 'nó' não é uma palavra-chave C.
O significado disso:
Uma matriz dinâmica pode ser estendida dobrando o tamanho, mas há sobrecarga associada à operação de copiar dados antigos e liberar a memória associada à estrutura de dados antiga
A alocação dinâmica significa que a memória é alocada no heap . O tamanho do espaço de memória alocado não precisa ser uma constante de tempo de compilação como na alocação de memória estática e, portanto, pode ser modificado pela realocação de mais memória posteriormente na execução do programa.
Sobrecarga significa o custo adicional de fazer uma operação em comparação com alguma outra maneira de fazer a mesma operação. Nesse caso, aumentar o tamanho de um array dinâmico é uma sobrecarga em comparação com a alocação direta do espaço total necessário.
Expandindo a resposta de Ahmad, há uma série de estruturas de dados que são construídas de elementos comumente chamados de "nós" - cada nó contém alguns dados e algum tipo de referência (normalmente um ponteiro em C e C ++) para um ou mais outros nós. Para uma lista ligada isoladamente, a definição do nó normalmente se parece com
struct node {
data_t data; // for some arbitrary data_t type
struct node *next;
};
Cada nó contém o endereço do seguinte nó. Uma representação gráfica normalmente se parece com
+------+------+ +------+------+ +------+------+
| data | next |------->| data | next |----->| data | next |------|||
+------+------+ +------+------+ +------+------+
Você também pode ter uma lista duplamente vinculada, em que cada nó aponta para os nós anteriores e seguintes:
struct node {
data_t data;
struct node *prev;
struct node *next;
};
E há árvores binárias, onde cada nó aponta para nós filhos esquerdo e direito:
struct node {
data_t data;
struct node *left;
struct node *right;
};
O uso do termo "nó" é apenas uma convenção de nomenclatura comum.
Um array dinâmico pode ser estendido dobrando o tamanho, mas há sobrecarga associada à operação de copiar dados antigos e liberar a memória associada à estrutura de dados antiga. O que isto quer dizer?
Você pode redimensionar um buffer alocado dinamicamente usando a reallocfunção de biblioteca. Por exemplo, suponha que desejamos alocar dinamicamente um buffer para armazenar a string "foo". Escreveríamos algo como:
size_t bufsize = 4;
char *buffer = malloc( bufsize );
if ( buffer )
strcpy( buffer, "foo" );
Vamos imaginar que o endereço de retorno mallocé 0x1000:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
Agora, suponha que queremos anexar a string "bar"a "foo". Não alocamos um buffer grande o suficiente para fazer isso, então precisamos redimensioná-lo usando a reallocfunção de biblioteca:
char *tmp = realloc( buffer, bufsize * 2 ); // double the buffer size
if ( tmp )
{
buffer = tmp;
bufsize *= 2;
strcat( buffer, "bar" );
}
else
{
// could not extend buffer, handle as appropriate
}
Agora, se possível, reallocapenas pegarei o espaço após o buffer atual, então o resultado desse código seria:
+---+---+---+---+
0x1000: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1004: |'a'|'r'| 0 | ? |
+---+---+---+---+
... ... ... ...
No entanto, se a memória em 0x1004já tiver sido alocada para outra coisa, não podemos fazer isso. reallocterá que alocar um novo buffer em um endereço diferente e copiar o conteúdo do buffer atual para ele e, em seguida, desalocar o buffer original. Vamos imaginar que a primeira região de espaço livre grande o suficiente começa em 0x100c:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: | ? | ? | ? | ? |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
Portanto, reallocprimeiro deve alocar os 8 bytes começando em e 0x100c, em seguida, deve copiar o conteúdo do buffer atual para esse novo espaço:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
e, finalmente, libere o espaço em 0x1000. Acrescentamos "bar"a este novo buffer, dando-nos:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 | // free'd memory is not overwritten
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1010: |'a'|'r'| 0 | ? |
+---+---+---+---+
Se reallocnão conseguir encontrar uma região grande o suficiente para satisfazer a solicitação, ele retornará NULLe deixará o buffer atual no lugar. É por isso que atribuímos o valor de retorno de realloca uma variável de ponteiro diferente - se atribuíssemos de NULLvolta a buffer, perderíamos nosso acesso ao buffer original.