연결 목록의 포인터에 대한 포인터
누군가이 코드가 결과적으로 빈 목록을 제공하는 이유를 설명 할 수 있습니까?
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
하지만 포인터 포인터로 begin () 함수를 변경하면 올바른 목록이 표시됩니까?
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
왜 내가 메인에서 노드 헤드를 함수로 넘겨 줄 때 "& head"로 넘겨야하는지 설명해 주시겠습니까? 더 이상 "머리"가 아닙니다.
답변
이 코드 스 니펫의 첫 번째 프로그램에서
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
포인터 head는 begin값으로 함수 에 전달됩니다 . 그것은 headmain에서 선언 된 포인터의 값의 복사본 이 생성되고 같은 이름의 함수 begin을 가진 매개 변수에 할당됩니다.
void begin(node *head);
따라서 함수 내에서 변경된 head원래 포인터의 복사본을 처음에 보유 하는 매개 변수 가 있습니다 head. head매개 변수에 값이 지정된 원래 포인터 는 변경되지 않습니다.
main에서 선언 된 원래 포인터 헤드를 변경하려면 두 번째 프로그램에서 수행되는 것처럼 포인터 헤드에 대한 포인터를 통해 간접적으로 참조로 함수에 전달해야합니다.
따라서 함수는 다음과 같이 선언되어야합니다.
void begin(node **head);
그리고 포인터 헤드를 포인터를 통해 간접적으로 전달해야합니다.
begin( &head );
이 경우 전달 된 포인터를 역 참조하면 함수는 main에 선언 된 원래 포인터 헤드에 직접 액세스하고 변경할 수 있습니다 (첫 번째 함수 정의에서 발생하는 값의 복사본이 아님).
new->next = *head;
*head = new;
더 명확하게하기 위해이 간단한 시연 프로그램을 고려하십시오.
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
출력은 다음과 같습니다.
Before calling f t is equal to 0
After calling f t is equal to 0
함수 f는 전달 된 인수 값의 복사본을 처리하므로 tmain에서 선언 된 변수의 값은 변경되지 않았습니다.
따라서 t포인터를 통해 참조로 원래 변수를 전달해야합니다.
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
이제 프로그램 출력은
Before calling f t is equal to 0
After calling f t is equal to 10
이러한 데모 프로그램에서 이름 T은 유형의 별칭으로 사용되며 기본적으로 int개체 t는이 유형을 갖습니다.
이제 이름 T가 int * 유형의 별칭이라고 가정 해 보겠습니다.
typedef int * T;
이 경우 예를 들어 main의 선언은
T t = NULL;
변수 t에 포인터 유형이 있음을 의미합니다 int *. 즉,
int * t = NULL;
따라서 원래 변수 t를 변경해야하는 함수에 전달하려면 다음과 같이 참조로 전달해야합니다.
f( &t );
이는 해당 함수가 다음과 같이 선언 된 매개 변수 유형을 가져야 함을 의미합니다.
void f( T *t );
그러나 따라서 T별칭 int *은 함수에 유형의 매개 변수가 있음을 의미합니다 int **.
void f( int * *t );
왜냐하면 head이다 (효과적으로) 로컬 변수 때문에 변화하는 반면, 그것의 기능에는 영향이없는 외부 변화 *head어떤 변화 head따라서 포인트를 한 것은한다.
함수가 int변수 의 값을 변경할 수 있도록하려면 (예 x:) x유형을 갖는에 대한 포인터를 전달 int*하고을 x사용하여 포인터를 가져옵니다 &x. 유형 x이 무엇이든 마찬가지 입니다.
선언에서 약간의 혼란이 올 수 있습니다.
node *head;
대신에
node* head;
당신은 head. head변수이고 포인터입니다. 노드가 아닙니다. 또한 노드는 연결 목록이 아닙니다. 연결 목록은 노드의 모음이며 유용한 구현을 위해 다른 것입니다. 이것에 대해서는 나중에 더 자세히 설명하겠습니다.
사실은 당신이 main()선언 head한 것 node*입니다. 노드 자체는 아직 존재하지 않습니다. 다음 begin()과 같이 선언 했습니다.
void begin(node *head);
그리고 나는 당신이 그것을 더 명확하게 볼 것이라고 생각합니다.
void begin(node* parameter);
parameter입니다 node*.
내부 begin()에서 포인터의 복사본을 얻고 포인터를 변경해도에서 원래 포인터는 변경되지 않습니다 main(). 귀하의 경우 main()영원히 가리킬 것 NULL입니다.
중요한 것은 포인터가 모든 변수와 같다는 것입니다. 포인터에는 주소가 있습니다. 그리고 내용. 값으로 전달할 때와 마찬가지로의 포인터 는에서 온 VALUE 로 begin()시작합니다 . 그러나 그들 사이의 유대감은 초기 값 인 호출에서 끝납니다.NULLmain()
에 포인터 를 전달할 때 begin()'address of'연산자를 사용하여 &head변경 사항을 작성합니다. 연산자를 사용하여 포인터 를 '*'변경하면 가리키는 주소가 변경되므로에서 변경됩니다 main(). head에 node*대한 포인터 이므로 다음 과 같이 선언됩니다.node**
그러나 begin()다음을 사용하여 연결 목록 에 대한 선언을 변경하는 것을 고려하십시오 .
node* begin(node* node);
논리는 노드를 삽입하면 목록의 헤드가 변경 될 수 있으므로 다음과 같이 새 주소를 반환합니다.
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
이것을 쓰는 일반적인 방법입니다. 또 다른 방법은 node**.
여기서 설명하는 방식은 목록의 헤드를 변경할 수있는 모든 작업은
- 새 머리를 돌려
- 머리의 포인터에 대한 포인터 수신 및 업데이트
목록의 시작 부분에 삽입되는 다음 코드를 다시 참조하십시오.
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
반환 new하면 head업데이트됩니다. 그리고 당신은 쓸 수 있습니다main()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
선 another = _insert_begin(i, another);을 확인하면의 포인터가 어떻게 main()업데이트 되는지 확인할 수 있습니다 .
이것은 출력입니다
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
이 구현을 사용하면 한 display_list()줄에 5 개의 값을 인쇄합니다.
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
또 다른 예 : 끝에 삽입
목록이 비어있는 경우 끝에 삽입하면 헤드가 변경 될 수 있으므로 여전히 헤드 주소를 반환해야합니다.
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
또 다른 용도 : 오름차순으로 삽입
물론, 오름차순으로 삽입하면 다음과 같이 헤드를 변경할 수도 있습니다.
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
목록 삭제
목록 삭제는 node*헤드 포인터를 무효화하기 위해 a 를 반환해야합니다 . 평소입니다. 그 메커니즘에 익숙해지면 잘못된 포인터가 주변에 남아 있지 않도록합니다.
이 논리는 협력 적입니다. 헤드를 변경할 수있는 모든 호출에서 헤드 포인터를 다시 할당해야합니다.
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
실행중인 프로그램
예제 프로그램의 출력
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
예제 C 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
틀림없이 더 유용한 연결 목록 구조
다음을 고려하세요
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
이렇게하면 연결 목록이 노드의 컨테이너로 정의됩니다.
- 선택 사항도
name있습니다. size항상 사용 가능하고 최신 상태입니다.- 크기 제한은 다음과 같이 구현할 수 있습니다.
capacity - 목록이 머리와 꼬리 모두에 대한 포인터를 캡슐화하기 때문에 끝 과 시작 부분에 삽입은 다른 모든 노드 를 따를 필요가 없습니다.
- 노드에는 다음 및 이전 노드에 대한 포인터가 있으므로 재생 목록 이나 컬렉션과 같은 일부 데이터를 더 쉽게 반복 할 수 있습니다.
- 각 프로그램은이 모든 메타 데이터를 캡슐화하기 때문에 프로그램은 여러 목록을 가질 수 있습니다.
- 데이터가 void에 대한 포인터이기 때문에 목록에는 모든 것이 포함될 수 있습니다.
void* - empty () 또는 size ()와 같은 함수를 쉽게 구현할 수 있습니다.
- 모든 함수는 목록에 대한 포인터를 사용합니다.
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
에 관해서:
void begin(node *head){
변경 head하면 호출 스택 'head'만 변경되며, 필요한 것은 호출자의 함수에서 'head'가 가리키는 위치를 변경하는 것입니다. 이를 위해 호출자는 'head'의 주소를 전달해야합니다. '머리'가 그 자체로 포인터라는 사실은 수행해야 할 작업의 명확성에 도움이되지 않습니다.