Why structures and Pointers

The segment fault is the segment fault. The segment fault is the segment fault. The segment fault is the segment fault.

Segment fault: Runtime Error when accessing unallocated memory

There are also memory leaks in C, which can end up throwing a segment error, or a program running unresponsive, or returning a line like this at the end of the run

Process exited after 5.252 seconds with return value 3221225477

These memory problems are often caused by improper use of Pointers, neglect of pointer initialization, or confusion over pointer pointing. Because I didn’t work hard enough in learning C language in my freshman year, I had considerable deficiencies in the basis of Pointers and structures. In order to make up for these deficiencies and facilitate the subsequent IMPLEMENTATION of C in data institutions, I decided to re-explore C and Pointers.

In the process of learning, I also appreciate THE book C and Pointers. I focused on reading the content of chapters 6, 10, 11 and 12, and I will put the PDF version at the end of the paper.

Definition and use of structures

struct ListNode {
    int a;
    float b;
    char* c;
};
// Life structure variables must follow the struct keyword before defining type
struct ListNode ln = {0};  // Initialize, a=0,b=0.000000, c = NULL/0
struct ListNode* p;
// A typedef can be omitted from the struct and declared as a ListNode
typedef struct ListNode ListNode;
ListNode ln; //valid
typedef struct ListNode* PtrToListNode;
PtrToListNode p;  //valid
Copy the code

Uses of structs

  1. Similar to the functions of object-oriented classes, easy access to structured data
  2. Using Pointers to implement lists is probably the most common use of structures. after all, why not choose an object-oriented language to use classes, so this article focuses on lists.

Structure storage allocation, interesting problem

Let’s look at these two structures

struct s1
{
	char a;
	int b;
	char c;
};
struct s2
{
	int b;
	char a;
	char c;
};
Copy the code

Their member fields are exactly the same, except that the order of the health variables is different. What about their sizes?

printf("s1 size:%d\n", sizeof(struct s1));
printf("s2 size:%d\n", sizeof(struct s2));
Copy the code

Output result:

s1 size:12

s2 size:8

That’s the difference in the storage structure between these two structures, as we all know

1 int = 4 bytes

1 character = 1 byte

  • S1: Take 1 byte to store A, and the next 3 bytes after A are free, the next 4 bytes of B, and the last 1 byte of C are free to store the next structure, 12 bytes in total

  • S2: B occupies 4 bytes, A and C occupy 2 consecutive bytes, and the last 2 bytes are left free to store the next structure, a total of 8 bytes

Pointer to the

1. Basic concepts of Pointers

  • A pointer is also a variable
  • Pointer declarations do not automatically allocate any memory. Pointers must be initialized, and those not explicitly pointed to must be initialized to NULL
  • A pointer points to the memory address of another variable (or pointer)
  • The content of a pointer is the value of the variable to which it points
  • The value of a pointer is an integer
  • The size of the pointer is a constant (usually 4 bytes, 8 bytes on 64-bit operating systems, but the compiler may default to 32 bits for all)
  • The type of the pointer (void*/int*/flot*, etc.) determines how the value will be resolved for indirect references (the value is represented in memory as a string of binary bits, obviously the type of the value is not inherent to the value itself, but depends on how it is used).

Example: a 32 bit 4 bytes (byte) value: 01100111011011000110111101100010

type value
The value is a 32-bit integer 1735159650
Two 16-bit integers 26476 and 28514
Four characters glob
Floating point Numbers 1.116533 * 10 ^ 24

2. Use of Pointers

Pointer usage scenarios:

  1. Build list
  2. Passed as a function parameter
  3. As a function return value
  4. Use Pointers like normal arrays
  5. Build a variable length array

1. Establishment of single linked lists

struct ListNode {
    int val;
    struct ListNode *next; // Notice the * here. Is the definition of this structure valid without *?
};
Copy the code

Linked lists are difficult data structures in C language. I will explain more about linked lists in my next blog post.

2. When to use Pointers as function arguments?

Ans:

  1. To change the value of an argument passed from outside a function by a function, you can only use address passing, which means passing a pointer as an argument to the function.
  2. Even if variable modification is not required, it is best to use Pointers as arguments.

In particular, if the parameter is too large, such as a structure with many members, it is best to replace it with a pointer to the structure, a maximum of 8 bytes. Moreover, the C language pass-by-value method requires that a copy of the parameter be passed to the function.

Therefore, value passing is a huge waste of space and time, and as we will see examples of Pointers as arguments will be common. The only drawback of address passing is that there are functions that modify the variable, which can be avoided by setting it to a constant pointer.

void print_large_struct(large_struct const * st){}

This line tells the compiler that my pointer to st is a constant pointer, and that its contents cannot be changed. If I accidentally change its contents in a function, please give me an error.

You can only use the pointer example — call a function to change the value of A

// Two ways to change the value of a parameter
void changeByValue(int a){
	a = Awesome!;
	printf("in the func:%d\n", a);
}
void changeByAddr(int* a){
	*a = Awesome!;
}
int main(a)
{
	int a = 0;
	
	changeByValue(a);  //a is used as an argument
	printf("out the func:%d\n", a);

	changeByAddr(&a); // take the address of a as an argument
	printf("after changeByAddr:%d\n", a);

	return 0;
}
Copy the code

Output result:

in the func:666 out the func:0

after changeByAddr:666

3. Why use Pointers as return values?

Ans: I mean, you can do that sometimes

4. Pointers and plain arrays

  • Pointer to array
int a[3] = {1.2.3};
int* pa = a;
for (int i = 0; i < 3; ++i)
	printf("%d\n", *pa++);
Copy the code

Pa ++ is an indirect reference to pa, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1, pa = pa+ 1

  • int
for (int i = 0; i < 3; ++i)
	printf("%d\n", pa++);
Copy the code

Output result:

6487600

6487604

6487608

  • double
double b[3] = {1.2.3};
double *pb = b;
for (int i = 0; i < 3; ++i)
  printf("%d\n", pb++);
Copy the code

Output result:

6487552

6487560

6487568

Meanwhile, the array variable itself is a pointer to the first element of the array, a[0]. It contains the address of the first element, so it is perfectly acceptable to use a as a pointer.

p = a;
p = &a[0]; // Same as above, p points to array A

//a++ is invalid. The array name cannot be incremented by an lvalue
for (int i = 0; i < 3; ++i)
	printf("%d\n", *(a+i));
Copy the code

5. Define a variable-length array for operation Pointers?

When I wrote this point, I read Weng Kai’s MOOC (Advanced C language). 4.1 is very classic, and it is basically the prototype of linear table.

  • Variable-length array
//Q1
typedef struct Array{
	int * array;
	int size;
}Array;
//Q2
Array arrary_create(int init_size){
	Array a;
	a.size = init_size;
	a.array = (int*)malloc(init_size * sizeof(int));
	return a;
}

void array_free(Array* a){
	free(a->array);
	a->array = NULL;
	a->size = 0;
}
//Q3
void array_inflate(Array* a, int more_size){
	int* p = (int*)malloc((a->size + more_size) * sizeof(int));
	for (int i = 0; i < a->size; ++i)
		p[i] = a->array[i];
	free(a->array);
	a->array = p;
	a->size = a->size + more_size;
}
//Q4
int array_at(Array const * a, int index){
	return a->array[index];
}
Copy the code

In the code above, I’ve made four flags that correspond to four questions.

Q1:Why Array not Array* ?

  • typedef struct Array{... }* Array

To do so? I can’t get a local variable of a structure, I can only manipulate a pointer to that structure, but I can’t generate a structure, which is a ridiculous question, who should MY pointer point to? At the same time, see Array A; Can you think of a as a pointer?

Q2: Again? Why Array not Array* ?

Array* array_create(int init_size){
	Array a;
	a.size = init_size;
	a.array = (int*)malloc(init_size * sizeof(int));
	return &a;
}
Copy the code

To do this? Notice that this a is a local variable defined in array_create. Let’s take a look at the recycling mechanism in C, and you’ll see why this doesn’t work.

  1. If they are defined within a function, they are called local variables and stored in stack space. Its space is freed up after the function call.
  2. If a global variable is stored in the DATA or BSS segment, its space is always available until the program ends.
  3. If it is new or malloc, it is stored in the HEAP and is occupied until the end of the process unless manually deleted or free.

The function does return a pointer, but when the function returns, a is returned, so the address of a you return is a pointer to an unknown location, an ambiguous value, no longer pointing to the structure you thought you created in the function.

Another way to do it?

Array* array_create(Array* a, int init_size){
	a->size = init_size;
	a->array = (int*)malloc(init_size * sizeof(int));
	return a;
}
Copy the code

This is possible, but there are two potential risks

  1. If a == NULL, then this must raise a memory access error;
  2. A already refers to an existing structure. Do you want to make a->array free?

Instead of this complexity, we can take a simpler approach and return a structure itself.

Q3: Is it too complicated to copy the elements of the original array into the new applied space each time?

Of course, you can also do this:

void array_inflate(Array* a, int more_size){
	a->array = (int*)realloc(a->array, (a->size + more_size) * sizeof(int));
	a->size = a->size + more_size;
}
Copy the code

Now that you’ve touched malloc and Realloc, let’s summarize the following functions.

Malloc calloc Realloc and Free

They are all available from the heap (consecutive? The first address of the memory block, which returns a pointer to void*, is at least logically contiguous, but physically not contiguous, depending on the operating system. They may request slightly more memory than you requested and return a NULL pointer if the memory library is empty. The reality is that this is possible! Therefore, when using dynamic memory allocation, always check whether the return is NULL!

  • Realloc differs from Malloc in that realLOc requires an address of the original memory and an enlarged size. If the original memory is followed by a block of memory that is available, this portion is allocated to the original address. Otherwise, a large enough memory is found, the new address is returned and the data is automatically copied to the new memory
  • Calloc The first parameter is the number of applications and the second parameter is the size of each unit, for examplecalloc(100,sizeof(int))Request 100 ints of memory. Note that calloc’s biggest difference is that it automatically initializes this memory, and the pointer is initialized to NULL, largely avoiding some uninitialized errors.
  • Free takes an argument of type pointer, which is either NULL,free(NULL)It’s safe. Or it has to be the memory that the top three brothers allocated from the heap.

Q4: Why const* ?

So that’s kind of an example of a pointer being passed as a function argument, const because I don’t want a to get changed when I access an element in A, so TELL the compiler to keep an eye on it for me. In fact, we can see that it’s safe in the function that we didn’t change *a, and if the function is simple enough, we can get rid of const.

3. Pointer operation

Note that pointer operations are meaningless when they point to something other than an array

// A pointer is an integer. It can be calculated between them, but the following is meaningless
int a = 3;
int b = 1;
int* pa = &a;
int* pb = &b;
printf("%d\n", pb - pa);
Copy the code

But when a pointer points to an array, the subtraction means the distance between the two Pointers, and that distance is also a logical distance

int a[5];
int *pa, *pb;
pa = &a[0], pb = &a[3];
int distance = pb - pa;
Copy the code

The resulting distance is 16/4 (1 int4 bytes), which is 4; Another interesting example is the relational operation on Pointers.

// Make all elements of A 5
int a[3] = {1.2.3};
int* p;
for(p = &a[0]; p < &a[3]; *p ++ = 5); // A weirdly legal for loop
Copy the code

A ++ and ++a are both similar in that a+1 is given to a, but the difference is that a++ is given to the program before +1, while ++a is given to the program before +1.

Here we access the address after the last element of the array and compare it to determine the edge of the advance. This turns out to be legal. In fact, our P was already pointing to that location at the last comparison, but we didn’t access it indirectly, so this set of loops is perfectly legal. Consider the following example:

// Change all elements of A to 0
for(p = &a[2]; p >= &a[0]; p--)
  *p = 0;
Copy the code

In the last comparison, p has been reduced by 1 from a[0], that is, it has moved out of the array. Unlike the previous example, it will be compared with the address of a[0], which is meaningless. The criteria involved are as follows:

The standard allows a pointer to an array element to be compared with a pointer to the memory location after the last element of the array, but not with a pointer to the memory location before the first element of the array

As for Pointers in C, the content is really too much, and I will make summaries while stepping on pits in future learning. The reason for writing this paper is also to make a record of my mistakes, accumulate experience in the summary, and keep moving forward. In short, come on ~