Problem source
When writing data structure programs in c/c++, level-2 pointers or level-1 pointer references are often used in linked lists and binary trees. When to use them and when not to use them?
Test code
See the following simple c++ linked list operation program:
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 / * initial allocation of storage space*/
typedef int Status;/* Status Is the type of the function, and its value is the function result status code, such as OK */
typedef int ElemType;/* ElemType The type depends on the actual situation. Here, it is assumed to be int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* Define LinkList */
//Initialize the header with a level-1 pointer (this method is invalid)
Status InitList1(LinkList L) //Equivalent to Node *L
{
L=(LinkList)malloc(sizeof(Node)); /* Generate a header node and make L point to this header node */
if(!L) /* Storage allocation failed */
return ERROR;
L->next=NULL; /* Pointer field is null */
return OK;
}
//Initialize the header with a secondary pointer
Status InitList2(LinkList *L) //Equivalent to Node **L
{
*L=(LinkList)malloc(sizeof(Node)); /* Generate a header node and make L point to this header node */
if(!(*L)) /* Storage allocation failed */
return ERROR;
(*L)->next=NULL; /* Pointer field is null */
return OK;
}
//Initialize the header and reference it with a level-1 pointer
Status InitList3(LinkList &L) //Equivalent to node * &l
{
L=(LinkList)malloc(sizeof(Node)); /* Generate a header node and make L point to this header node */
if(!L) /* Storage allocation failed */
return ERROR;
L->next=NULL; /* Pointer field is null */
return OK;
}
//Clear the linked list and use the secondary pointer
Status ClearList1(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p Point to the first node */
while(p) /* Not to the end of the table */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* The header node pointer field is null */
return OK;
}
//Clear the linked list and use the first level pointer
Status ClearList2(LinkList L)
{
LinkList p,q;
p=L->next; /* p Point to the first node */
while(p) /* Not to the end of the table */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* The header node pointer field is null */
return OK;
}
//Destroy the linked list and use the first level pointer (this method is invalid)
Status DestroyList1(LinkList L)
{
LinkList p,q;
p=L->next; /* p Point to the first node */
while(p) /* Not to the end of the table */
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
return OK;
}
//Destroy the linked list and use the secondary pointer
Status DestroyList2(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p Point to the first node */
while(p) /* Not to the end of the table */
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
return OK;
}
//Destroy the linked list and use the first level pointer reference
Status DestroyList3(LinkList &L)
{
LinkList p,q;
p=L->next; /* p Point to the first node */
while(p) /* Not to the end of the table */
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
return OK;
}
/* Initial condition: sequential linear table l already exists, 1 ≤ i ≤ ListLength(L) */
/* Operation result: use e to return the value of the ith data element in L */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* Declare a node p */
p = L->next; /* Let p point to the first node of the linked list L */
j = 1; /* j Is a counter */
while (p && j<i) /* p When it is not empty or the counter j is not equal to i, the loop continues */
{
p = p->next; /* Let p point to the next node */
++j;
}
if ( !p || j>i )
return ERROR; /* The ith element does not exist */
*e = p->data; /* Take the data of the i th element */
return OK;
}
//Insert an element in the middle with a second level pointer
Status ListInsert1(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i) /* Find the ith node */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* The ith element does not exist */
s = (LinkList)malloc(sizeof(Node)); /* Generate a new node (C language standard function) */
s->data = e;
s->next = p->next; /* Assign the successor node of p to the successor node of s */
p->next = s; /* Assign s to the successor of p */
return OK;
}
//Insert an element in the middle with a first-order pointer
Status ListInsert2(LinkList L,int i,ElemType e)
{
int j;
LinkList p,s;
p = L;
j = 1;
while (p && j < i) /* Find the ith node */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* The ith element does not exist */
s = (LinkList)malloc(sizeof(Node)); /* Generate a new node (C language standard function) */
s->data = e;
s->next = p->next; /* Assign the successor node of p to the successor node of s */
p->next = s; /* Assign s to the successor of p */
return OK;
}
//Delete an element with a second level pointer
Status ListDelete1(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i) /* Traverse to find the ith element */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* The ith element does not exist */
q = p->next;
p->next = q->next; /* Assign the successor of q to the successor of p */
*e = q->data; /* Give the data in the q node to e */
free(q); /* Let the system reclaim this node to free memory */
return OK;
}
//Delete an element with a first level pointer
Status ListDelete2(LinkList L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = L;
j = 1;
while (p->next && j < i) /* Traverse to find the ith element */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* The ith element does not exist */
q = p->next;
p->next = q->next; /* Assign the successor of q to the successor of p */
*e = q->data; /* Give the data in the q node to e */
free(q); /* Let the system reclaim this node to free memory */
return OK;
}
/* Initial condition: sequential linear table L already exists */
/* Operation result: output to each data element of L in turn */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k;
//InitList1(L); // Failed to create header in level-1 pointer mode
//InitList2(&L); // The header was created successfully in the secondary pointer mode
InitList3(L); //First level pointer reference method creates header successfully
for(j=1;j<=7;j++)
ListInsert2(L,1,j);
printf("First level pointer mode L Insert the header of 1 in turn～7 After:");
ListTraverse(L);
ListInsert1(&L,3,12);
printf("Secondary pointer mode L After inserting 12 in the middle of:");
ListTraverse(L);
ListInsert2(L,5,27);
printf("First level pointer at L After inserting 27 in the middle of:");
ListTraverse(L);
GetElem(L,5,&e);
printf("The value of the 5th element is:%d\n",e);
ListDelete1(&L,5,&e); /* Delete the 5th data */
printf("Delete the second level pointer mode%d Element values of are:%d\n",5,e);
printf("Sequential output L Element of:");
ListTraverse(L);
ListDelete2(L,3,&e); /* Delete the 3rd data */
printf("Delete the first level pointer mode%d Element values of are:%d\n",3,e);
printf("Sequential output L Element of:");
ListTraverse(L);
printf("Clear the linked list in the secondary pointer mode\n");
ClearList1(&L);
printf("Sequential output L Element of:");
ListTraverse(L);
for(j=1;j<=7;j++)
ListInsert2(L,j,j);
printf("stay L Insert 1 at the end of the table～7 After:");
ListTraverse(L);
printf("Clear the linked list in the first level pointer mode\n");
ClearList2(L);
printf("Sequential output L Element of:");
ListTraverse(L);
printf("Destroy linked list\n");
//DestroyList1(L); // The first level pointer method fails to destroy the linked list, and the full screen is garbled
//DestroyList2(&L); // Destroy the linked list in the second level pointer mode. Successful
DestroyList3(L); //Destroy the linked list in the first level pointer reference mode. Successful
return 0;
}
Output results:
conclusion
-
Initializing the head pointer of the linked list requires the reference of the second level pointer or the first level pointer;
-
Destroying the linked list requires the reference of the second level pointer or the first level pointer;
-
Insert, delete, traverse and clear nodes with a level-1 pointer.
analysis
-
As long as the header pointer is modified, the address of the header pointer must be passed. Otherwise, the header pointer value can be passed (that is, the header pointer itself). This is similar to ordinary variables. When the value of an ordinary variable needs to be modified, its address needs to be passed. Otherwise, the value of an ordinary variable can be passed (that is, a copy of this variable). Using the second level pointer, you can easily modify the value of the first level pointer of the incoming node; If you use a level-1 pointer, you can only modify the contents indicated by the pointer through the pointer, but you cannot modify the value of the pointer, that is, the memory block indicated by the pointer. So creating a linked list and destroying a linked list requires a second level pointer or a first level pointer reference.
-
Where there is no need to modify the header pointer, you can use the first level pointer, such as inserting, deleting, traversing, and clearing nodes. If the header pointer is L, only one level of pointer needs to be passed for L->next and subsequent node pointers;
-
For example, for a node p, if you want to modify the point of p in the function, you need to use the secondary pointer. If you only want to modify the next point of p, you can use the primary pointer.
To pass a pointer in a function and change the value of the pointer in a function is to change the data information in the arguments. However, changing the value of the pointer here actually refers to changing the value of the pointer pointing to the address, because passing the pointer is to pass the address of the pointer pointing to the variable, rather than just passing in a copy of the argument like passing the value. So when we change the value of the pointer, the arguments change.
A closer look at the function InitList2(LinkList *L) shows that the pointer is changed in this function, that is, the value of the pointer itself is changed. In contrast to passing by value, the "value" here is a pointer, so we must use a secondary pointer if we want the change of the pointer itself to be reflected on the actual parameter pointer.
Take the following example to understand:
#include <iostream>
#include <string.h>
using namespace std;
void fun1(char* str)
{
str = new char[5];
strcpy (str, "test string");
}
void fun2(char** str)
{
*str = new char[5];
strcpy (*str, "test string");
}
int main()
{
char* s = NULL;
cout << "call function fun1" << endl;
fun1 (s);
if (!s)
cout << "s is null!" << endl;
else
cout << s << endl;
cout << "call function fun2" << endl;
fun2 (&s);
if (!s)
cout << "s is null!" << endl;
else
cout << s << endl;
return 0;
}
Output results:
In the above code, we can understand as follows: in function fun1, we pass the pointer variable s of char type to the pointer variable STR of char type. At this time, only strcopy the value of S. what STR does later has nothing to do with S. therefore, when str=new char[5] is called, the value of STR changes, but the value of s does not change. In fun2, the variable STR is a secondary pointer, which stores the value of the pointer variable s of char type. Here str=new char[5], *str is s, so allocating space to *str is allocating space to s.
Take drawing as an example:
-
When fun1 is executed
-
When fun2 is executed
Postscript
Secondary pointer create header pointer
- Only header pointer, no header node
- Header pointer and header node
-
If the secondary pointer is not used, directly passing a primary pointer is equivalent to generating a copy of L, but the allocated space for M is independent of L
L2 pointer destroy header pointer
Whether or not there is a header node, it should be destroyed by passing parameters through the reference of the second level pointer or the first level pointer.
Two level pointer and one level pointer inserting node
Transferring the second level pointer is to operate on the linked list from the chain header pointer. Transferring the first level pointer is only to generate a copy of M for the header node L. the next of m still points to the next of L. therefore, the subsequent operations are still operated on the original linked list.
Deleting nodes by level-2 pointer and level-1 pointer
The principle of deletion is the same as that of insertion.
Points needing attention
If there is no incoming header node, the second level pointer must be used. It is invalid to use the first level pointer.
For example:
void insert(Node *p)
{
//do something to change the structure
}
void fun(Node *T)
{
Node *p;
insert(p) //OK,the head T is in
}
int main()
{
Node *T;
fun(T); //OK,the head T is in
}
Because the head pointer of the data structure (linked list and binary tree) is passed in the fun function, the formal parameter of the insert function in this function can be a first-class pointer.
However, if a node in the Secretary structure is directly and independently operated in the main function, the first level pointer cannot be used.
void insert1(Node *p)
{
//do something to change the structure
}
void insert2(Node **P)
{
//do something to change the structure
}
int main()
{
Node *p;
insert1(p); //error
insert2(&p); //OK
}
[original link] https://blog.csdn.net/u012234115/article/details/39717215