Cos'è un nodo in C?
Sto lavorando allo speller cs50 pset5 e nella lezione introducono una nuova cosa chiamata nodi. Cos'è un nodo? Non ho davvero capito cosa hanno detto nel video. Quando ho provato a cercarlo su Google, ho trovato alcuni siti che spiegavano cos'è un nodo, ma non ho capito bene. Sono nuovo in c, quindi non sono abituato a ciò che chiamo "parole in codice". Ad esempio, ho trovato questo su un sito sui nodi: un array dinamico può essere esteso raddoppiando le dimensioni ma c'è un sovraccarico associato all'operazione di copia dei vecchi dati e liberazione della memoria associata alla vecchia struttura dati. Cosa dovrebbe significare? Per favore aiutami a capire cos'è un nodo perché sembrano importanti e utili, specialmente per pset5. Il mio nodo è definito così:
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
Ecco il collegamento alla guida dettagliata di speller pset5: https://cs50.harvard.edu/x/2020/psets/5/speller/
Risposte
Il nodo è una terminologia comune utilizzata per dimostrare un singolo blocco di linked listo treeo strutture di dati correlate.
È una convenzione chiamarlo nodo, altrimenti puoi chiamarlo con qualsiasi nome.
Standard
C ++
struct node{
int data;
int *next;
};
o in Python
class Node:
def __init__(self, data, next= None):
self.data = data
self.next = next
Ma puoi chiamarlo con qualsiasi nome
Non standard
C ++
struct my_own_name{
int data;
int *nextptr;
};
o in pitone
class my_own_name:
def __init__(self, data, next=None):
self.data = data
self.next = next
Un "nodo" è un concetto tratto dalla teoria dei grafi. Un grafo è costituito da nodi (vertici) e bordi che collegano i nodi.
Un nodo in C può essere rappresentato come una struttura (a struct) che ha tutti gli elementi di dati necessari "a bordo" per implementare un grafico. Opzionalmente può essere richiesta una struttura che rappresenti i bordi.
Esempio:
typedef struct NODE {
int node_id;
struct EDGE *edgelist;
} tNode;
typedef struct EDGE {
tNode *from, *to;
struct EDGE *next;
} tEdge;
Nota: il termine "nodo" può essere utilizzato anche in altri contesti, ad esempio i nodi di un albero binario, i nodi di una lista, ecc.
Un "nodo" non è una parola chiave C.
Il significato di questo:
Un array dinamico può essere esteso raddoppiando la dimensione ma c'è un sovraccarico associato all'operazione di copia dei vecchi dati e liberazione della memoria associata alla vecchia struttura dati
L'allocazione dinamica significa che la memoria viene allocata nell'heap . La dimensione dello spazio di memoria allocato non deve essere una costante del tempo di compilazione come nell'allocazione della memoria statica e quindi può essere modificata riallocando più memoria in seguito durante l'esecuzione del programma.
Overhead indica il costo aggiuntivo di eseguire un'operazione rispetto a qualche altro modo per eseguire la stessa operazione. In questo caso, aumentare la dimensione di un array dinamico è un sovraccarico rispetto all'allocazione diretta dello spazio totale richiesto.
Espandendo la risposta di Ahmad, ci sono un certo numero di strutture di dati che sono costruite da elementi comunemente chiamati "nodi" - ogni nodo contiene alcuni dati e qualche tipo di riferimento (tipicamente un puntatore in C e C ++) a uno o più altri nodi. Per un elenco collegato singolarmente, la definizione del nodo in genere è simile
struct node {
data_t data; // for some arbitrary data_t type
struct node *next;
};
Ogni nodo contiene l'indirizzo del nodo successivo. Una rappresentazione grafica sembra tipicamente
+------+------+ +------+------+ +------+------+
| data | next |------->| data | next |----->| data | next |------|||
+------+------+ +------+------+ +------+------+
Puoi anche avere una lista doppiamente collegata, in cui ogni nodo punta sia al nodo precedente che a quello successivo:
struct node {
data_t data;
struct node *prev;
struct node *next;
};
E ci sono alberi binari, in cui ogni nodo punta ai nodi figlio sinistro e destro:
struct node {
data_t data;
struct node *left;
struct node *right;
};
L'uso del termine "nodo" è solo una comune convenzione di denominazione.
Un array dinamico può essere esteso raddoppiando la dimensione ma c'è un sovraccarico associato all'operazione di copia dei vecchi dati e liberazione della memoria associata alla vecchia struttura dei dati. Cosa dovrebbe significare?
È possibile ridimensionare un buffer allocato dinamicamente utilizzando la reallocfunzione di libreria. Ad esempio, supponiamo di voler allocare dinamicamente un buffer per memorizzare la stringa "foo". Scriveremmo qualcosa del tipo:
size_t bufsize = 4;
char *buffer = malloc( bufsize );
if ( buffer )
strcpy( buffer, "foo" );
Immaginiamo che l'indirizzo restituito da mallocè 0x1000:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
Supponiamo ora di voler aggiungere la stringa "bar"a "foo". Non abbiamo allocato un buffer abbastanza grande per farlo, quindi dobbiamo ridimensionarlo utilizzando la reallocfunzione di libreria:
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
}
Ora, se possibile, reallocprenderà solo lo spazio che segue il buffer corrente, quindi il risultato di quel codice sarebbe:
+---+---+---+---+
0x1000: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1004: |'a'|'r'| 0 | ? |
+---+---+---+---+
... ... ... ...
Tuttavia, se la memoria in 0x1004era già stata allocata per qualcos'altro, non possiamo farlo. reallocdovrà allocare un nuovo buffer a un indirizzo diverso e copiare il contenuto del buffer corrente in esso, quindi deallocare il buffer originale. Immaginiamo che la prima regione di spazio libero abbastanza grande inizi da 0x100c:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: | ? | ? | ? | ? |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
Quindi reallocdeve prima allocare gli 8 byte a partire da 0x100c, quindi deve copiare il contenuto del buffer corrente in quel nuovo spazio:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
e infine rilascia lo spazio in 0x1000. Aggiungiamo "bar"a questo nuovo buffer, dandoci:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 | // free'd memory is not overwritten
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1010: |'a'|'r'| 0 | ? |
+---+---+---+---+
Se reallocnon riesce a trovare una regione abbastanza grande per soddisfare la richiesta, tornerà NULLe lascerà il buffer corrente al suo posto. Questo è il motivo per cui assegniamo il valore di ritorno realloca una diversa variabile del puntatore: se lo assegnassimo di NULLnuovo a buffer, perderemmo l'accesso al buffer originale.