C의 노드는 무엇입니까?
저는 cs50 pset5 맞춤법에 대해 작업하고 있으며 강의에서 노드라는 새로운 것을 소개합니다. 노드 란 무엇입니까? 나는 그들이 비디오에서 말한 것을 정말로 이해하지 못했습니다. 인터넷 검색을 시도했을 때 노드가 무엇인지 설명하는 사이트를 찾았지만 실제로는 이해하지 못했습니다. 나는 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
하지만 어떤 이름으로도 부를 수 있습니다
표준 아님
C ++
struct my_own_name{
int data;
int *nextptr;
};
또는 파이썬
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 키워드가 아닙니다.
이것의 의미 :
동적 배열은 크기를 두 배로 늘릴 수 있지만 이전 데이터를 복사하고 이전 데이터 구조와 관련된 메모리를 해제하는 작업과 관련된 오버 헤드가 있습니다.
동적 할당은 메모리가 힙 에 할당됨을 의미합니다 . 할당 된 메모리 공간의 사이즈는 않는다 하지 나중에 프로그램의 실행시에 메모리를 재 할당하여 수정 될 수있다, 따라서 정적 할당 같이 컴파일 시간 일정하게, 그리고.
오버 헤드 란 동일한 작업을 수행하는 다른 방법에 비해 작업 수행에 따른 추가 비용 을 의미합니다 . 이 경우 동적 어레이의 크기를 늘리는 것은 필요한 총 공간을 직접 할당하는 것과 비교하여 오버 헤드입니다.
Ahmad의 답변을 확장하면 일반적으로 "노드"라고하는 요소로 구성된 여러 데이터 구조가 있습니다. 각 노드에는 일부 데이터와 하나 이상의 다른 노드에 대한 참조 (일반적으로 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하면 원래 버퍼에 대한 액세스 권한을 잃게됩니다.