Nút trong C là gì?
Tôi đang làm việc trên cs50 pset5 speller và trong bài giảng họ giới thiệu một thứ mới gọi là các nút. Nút là gì? Tôi thực sự không hiểu họ nói gì trong video. Khi tôi thử googling nó, tôi nhận được một số trang web giải thích nút là gì, nhưng tôi không thực sự hiểu. Tôi mới làm quen với c nên tôi không quen với những gì tôi gọi là 'từ mã hóa'. Ví dụ: tôi tìm thấy điều này trên một trang web về các nút: Một mảng động có thể được mở rộng bằng cách tăng gấp đôi kích thước nhưng có chi phí liên quan đến hoạt động sao chép dữ liệu cũ và giải phóng bộ nhớ được liên kết với cấu trúc dữ liệu cũ. Điều đó nghĩa là gì? Vui lòng giúp tôi tìm ra nút là gì vì chúng có vẻ quan trọng và hữu ích, đặc biệt là đối với pset5. Nút của tôi được định nghĩa như thế này:
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
Đây là liên kết đến phần hướng dẫn của speller pset5: https://cs50.harvard.edu/x/2020/psets/5/speller/
Trả lời
Node là một thuật ngữ phổ biến được sử dụng để chứng minh một khối linked listhoặc treehoặc cấu trúc dữ liệu liên quan.
Đó là một quy ước để đặt tên nó là nút, nếu không bạn có thể gọi nó với bất kỳ tên nào.
Tiêu chuẩn
C ++
struct node{
int data;
int *next;
};
hoặc bằng Python
class Node:
def __init__(self, data, next= None):
self.data = data
self.next = next
Nhưng bạn có thể gọi nó với tên bất kỳ
Không chuẩn
C ++
struct my_own_name{
int data;
int *nextptr;
};
hoặc trong trăn
class my_own_name:
def __init__(self, data, next=None):
self.data = data
self.next = next
"Nút" là một khái niệm từ lý thuyết đồ thị. Một đồ thị bao gồm các nút (đỉnh) và các cạnh nối các nút.
Một nút trong C có thể được biểu diễn dưới dạng cấu trúc (a struct) có tất cả các phần tử dữ liệu cần thiết "trên tàu" để thực hiện một đồ thị. Tùy ý có thể yêu cầu một cấu trúc đại diện cho các cạnh.
Thí dụ:
typedef struct NODE {
int node_id;
struct EDGE *edgelist;
} tNode;
typedef struct EDGE {
tNode *from, *to;
struct EDGE *next;
} tEdge;
Lưu ý: thuật ngữ "nút" cũng có thể được sử dụng trong các ngữ cảnh khác, ví dụ: các nút của cây nhị phân, các nút của danh sách, v.v.
Một 'nút' không phải là một từ khóa C.
Ý nghĩa của điều này:
Một mảng động có thể được mở rộng bằng cách tăng gấp đôi kích thước nhưng có chi phí liên quan đến hoạt động sao chép dữ liệu cũ và giải phóng bộ nhớ liên quan đến cấu trúc dữ liệu cũ
Cấp phát động có nghĩa là bộ nhớ được cấp phát trên heap . Kích thước của không gian bộ nhớ được cấp phát không phải là một hằng số thời gian biên dịch như trong cấp phát bộ nhớ tĩnh, và do đó có thể được sửa đổi bằng cách phân bổ lại nhiều bộ nhớ hơn sau này trong quá trình thực thi chương trình.
Chi phí có nghĩa là chi phí bổ sung để thực hiện một hoạt động so với một số cách khác để thực hiện cùng một hoạt động. Trong trường hợp này, việc tăng kích thước của một mảng động là một chi phí lớn hơn so với việc phân bổ trực tiếp tổng không gian cần thiết.
Mở rộng câu trả lời của Ahmad, có một số cấu trúc dữ liệu được xây dựng từ các phần tử thường được gọi là "nút" - mỗi nút chứa một số dữ liệu và một số loại tham chiếu (thường là một con trỏ trong C và C ++) tới một hoặc nhiều nút khác. Đối với danh sách được liên kết đơn, định nghĩa nút thường trông giống như
struct node {
data_t data; // for some arbitrary data_t type
struct node *next;
};
Mỗi nút chứa địa chỉ của nút sau. Biểu diễn đồ họa thường trông giống như
+------+------+ +------+------+ +------+------+
| data | next |------->| data | next |----->| data | next |------|||
+------+------+ +------+------+ +------+------+
Bạn cũng có thể có danh sách được liên kết kép, trong đó mỗi nút trỏ đến cả nút trước và nút sau:
struct node {
data_t data;
struct node *prev;
struct node *next;
};
Và có cây nhị phân, trong đó mỗi nút trỏ đến các nút con bên trái và bên phải:
struct node {
data_t data;
struct node *left;
struct node *right;
};
Việc sử dụng thuật ngữ "nút" chỉ là một quy ước đặt tên chung.
Một mảng động có thể được mở rộng bằng cách tăng gấp đôi kích thước nhưng có chi phí liên quan đến hoạt động sao chép dữ liệu cũ và giải phóng bộ nhớ liên quan đến cấu trúc dữ liệu cũ. Điều đó nghĩa là gì?
Bạn có thể thay đổi kích thước bộ đệm được cấp phát động bằng cách sử dụng reallochàm thư viện. Ví dụ, giả sử chúng ta muốn cấp phát động một bộ đệm để lưu chuỗi "foo". Chúng tôi sẽ viết một cái gì đó như:
size_t bufsize = 4;
char *buffer = malloc( bufsize );
if ( buffer )
strcpy( buffer, "foo" );
Chúng tôi sẽ tưởng tượng địa chỉ trả về malloclà 0x1000:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
Bây giờ, giả sử chúng ta muốn nối chuỗi "bar"vào "foo". Chúng tôi đã không phân bổ một bộ đệm đủ lớn để làm điều đó, vì vậy chúng tôi cần thay đổi kích thước nó bằng cách sử dụng reallochàm thư viện:
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
}
Bây giờ, nếu có thể, reallocsẽ chỉ lấy khoảng trống sau bộ đệm hiện tại, vì vậy kết quả của đoạn mã đó sẽ là:
+---+---+---+---+
0x1000: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1004: |'a'|'r'| 0 | ? |
+---+---+---+---+
... ... ... ...
Tuy nhiên, nếu bộ nhớ tại 0x1004đã được cấp phát cho thứ khác, thì chúng ta không thể làm điều đó. reallocsẽ phải cấp phát một bộ đệm mới tại một địa chỉ khác và sao chép nội dung của bộ đệm hiện tại vào đó, sau đó phân bổ bộ đệm ban đầu. Chúng ta sẽ tưởng tượng rằng vùng đầu tiên của không gian trống đủ lớn bắt đầu ở 0x100c:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: | ? | ? | ? | ? |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
Vì vậy, realloctrước tiên phải cấp phát 8 byte bắt đầu từ 0x100c, sau đó nó phải sao chép nội dung của bộ đệm hiện tại vào không gian mới đó:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'| 0 |
+---+---+---+---+
0x1010: | ? | ? | ? | ? |
+---+---+---+---+
và sau đó cuối cùng giải phóng không gian tại 0x1000. Chúng tôi thêm "bar"vào bộ đệm mới này , mang lại cho chúng tôi:
+---+---+---+---+
0x1000: |'f'|'o'|'o'| 0 | // free'd memory is not overwritten
+---+---+---+---+
0x1004: | ? | ? | ? | ? |
+---+---+---+---+
... ... ... ...
+---+---+---+---+
0x100c: |'f'|'o'|'o'|'b'|
+---+---+---+---+
0x1010: |'a'|'r'| 0 | ? |
+---+---+---+---+
Nếu reallockhông thể tìm thấy một vùng đủ lớn để đáp ứng yêu cầu, nó sẽ quay trở lại NULLvà để nguyên bộ đệm hiện tại. Đây là lý do tại sao chúng tôi gán giá trị trả về của reallocmột biến con trỏ khác - nếu chúng tôi gán nó NULLtrở lại buffer, thì chúng tôi sẽ mất quyền truy cập vào bộ đệm ban đầu.