Блог

Я работаю над cs50 pset5 speller, и в лекции они вводят новую вещь, называемую узлами. Что такое узел? Я действительно не понял, что они сказали в видео. Когда я попытался погуглить, я нашел несколько сайтов, которые объясняли, что такое узел, но я действительно не понял. Я новичок в c, поэтому я не привык к тому, что я называю «кодирующими словами». Например, я нашел это на сайте об узлах: Динамический массив может быть расширен путем удвоения размера, но есть накладные расходы, связанные с операцией копирования старых данных и освобождения памяти, связанной со старой структурой данных. Что это должно означать? Пожалуйста, помогите мне выяснить, что такое узел, потому что они кажутся важными и полезными, особенно для pset5. Мой узел определяется следующим образом:

 typedef struct node
{
    char word[LENGTH   1];
    struct node *next;
}
node;
  

Вот ссылка на пошаговое руководство по написанию pset5:https://cs50.harvard.edu/x/2020/psets/5/speller /

Узел — это общая терминология, которая используется для демонстрации одного блока linked list или tree или связанных структур данных.

Это соглашение называть его узлом, в противном случае вы можете вызвать его любым именем.

Стандартный

C

 struct node{
int data;
int *next;
};
  

или в Python

 class Node:
   def __init__(self, data, next= None):
       self.data = data
       self.next = next
  

Но вы можете вызвать его с помощью anyname

Не стандартный

C

 struct my_own_name{
int data;
int *nextptr;
};
  

или в python

 
class my_own_name:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
  

«Узел» — это концепция из теории графов. Граф состоит из узлов (вершин) и ребер, которые соединяют узлы.

Узел в C может быть представлен в виде структуры (a struct ), которая имеет все необходимые элементы данных «на борту» для реализации графика. Необязательно может потребоваться структура, представляющая ребра.

Пример:

 typedef struct NODE {
    int node_id;
    struct EDGE *edgelist;
} tNode;

typedef struct EDGE {
    tNode *from, *to;
    struct EDGE *next;
} tEdge;
  

Примечание: термин «узел» также может использоваться в других контекстах, например, для узлов двоичного дерева, узлов списка и т.д.

В дополнение к ответу Ахмада, существует ряд структур данных, которые состоят из элементов, обычно называемых «узлами» — каждый узел содержит некоторые данные и некоторую ссылку (обычно указатель на C и C ) на один или несколько других узлов. Для односвязного списка определение узла обычно выглядит следующим образом

 struct node {
  data_t data;        // for some arbitrary data_t type
  struct node *next;
};
  

Каждый узел содержит адрес следующего узла. Графическое представление обычно выглядит как

  ------ ------          ------ ------        ------ ------ 
| data | next |------->| data | next |----->| data | next |------|||
 ------ ------          ------ ------        ------ ------ 
  

У вас также может быть двусвязный список, где каждый узел указывает как на предыдущий, так и на следующий узлы:

  struct node {
   data_t data;
   struct node *prev;
   struct node *next;
 };
  

И есть бинарные деревья, где каждый узел указывает на левый и правый дочерние узлы:

  struct node {
   data_t data;
   struct node *left;
   struct node *right;
 };
  

Использование термина «узел» — это просто общее соглашение об именовании.

Динамический массив может быть расширен путем удвоения размера, но есть накладные расходы, связанные с операцией копирования старых данных и освобождением памяти, связанной со старой структурой данных. Что это должно означать?

Вы можете изменять размер динамически выделяемого буфера с помощью realloc библиотечной функции. Например, предположим, что мы хотим динамически выделить буфер для хранения строки "foo" . Мы бы написали что-то вроде:

 size_t bufsize = 4;
char *buffer = malloc( bufsize ); 
if ( buffer )
  strcpy( buffer, "foo" );
  

Мы представим, что адрес, возвращаемый из malloc , является 0x1000 :

          --- --- --- --- 
0x1000: |'f'|'o'|'o'| 0 |
         --- --- --- --- 
0x1004: | ? | ? | ? | ? |
         --- --- --- --- 
         ... ... ... ...
  

Теперь предположим, что мы хотим добавить строку "bar" к "foo" . Мы не выделили достаточно большой буфер для этого, поэтому нам нужно изменить его размер с помощью realloc библиотечной функции:

 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
}
  

Теперь, если возможно, realloc просто захватит пространство после текущего буфера, поэтому результатом этого кода будет:

          --- --- --- --- 
0x1000: |'f'|'o'|'o'|'b'|
         --- --- --- --- 
0x1004: |'a'|'r'| 0 | ? |
         --- --- --- --- 
         ... ... ... ...
  

Однако, если память в 0x1004 уже была выделена для чего-то другого, то мы не можем этого сделать. realloc придется выделить новый буфер по другому адресу и скопировать в него содержимое текущего буфера, затем освободить исходный буфер. Мы представим, что первая область свободного пространства, достаточно большая, начинается с 0x100c :

          --- --- --- --- 
0x1000: |'f'|'o'|'o'| 0 |
         --- --- --- --- 
0x1004: | ? | ? | ? | ? |
         --- --- --- --- 
         ... ... ... ...
         --- --- --- --- 
0x100c: | ? | ? | ? | ? |
         --- --- --- --- 
0x1010: | ? | ? | ? | ? |
         --- --- --- --- 
  

Итак, realloc сначала необходимо выделить 8 байтов, начиная с 0x100c , затем он должен скопировать содержимое текущего буфера в это новое пространство:

          --- --- --- --- 
0x1000: |'f'|'o'|'o'| 0 |
         --- --- --- --- 
0x1004: | ? | ? | ? | ? |
         --- --- --- --- 
         ... ... ... ...
         --- --- --- --- 
0x100c: |'f'|'o'|'o'| 0 |
         --- --- --- --- 
0x1010: | ? | ? | ? | ? |
         --- --- --- --- 
  

и затем, наконец, освободите пространство в 0x1000 . Мы добавляем "bar" к этому новый буфер, предоставляя нам:

          --- --- --- --- 
0x1000: |'f'|'o'|'o'| 0 | // free'd memory is not overwritten
         --- --- --- --- 
0x1004: | ? | ? | ? | ? |
         --- --- --- --- 
         ... ... ... ...
         --- --- --- --- 
0x100c: |'f'|'o'|'o'|'b'|
         --- --- --- --- 
0x1010: |'a'|'r'| 0 | ? |
         --- --- --- --- 
  

Если realloc не удается найти достаточно большую область для удовлетворения запроса, он вернется NULL и оставит текущий буфер на месте. Вот почему мы присваиваем возвращаемое значение realloc другой переменной указателя — если бы мы присвоили это значение NULL обратно buffer , то потеряли бы доступ к исходному буферу.

‘Node’ не является ключевым словом C.

Значение этого:

Динамический массив может быть расширен путем удвоения размера, но есть накладные расходы, связанные с операцией копирования старых данных и освобождения памяти, связанной со старой структурой данных

Динамическое распределение означает, что память выделяется в куче. Размер выделяемого пространства памяти не должен быть константой времени компиляции, как при статическом распределении памяти, и, следовательно, может быть изменен путем перераспределения большего объема памяти позже при выполнении программы.

Накладные расходы означают дополнительную стоимость выполнения операции по сравнению с каким-либо другим способом выполнения той же операции. В этом случае увеличение размера динамического массива является накладными расходами по сравнению с прямым выделением общего требуемого пространства.