C language notes - day04
P34_ recursion
1. Application of recursion
Hanoi
2. The essence of recursion
In principle, recursion is the behavior of the function call itself.
3. Write recursive procedures need to pay attention to
Recursive exit: the recursive program needs to set the end condition correctly, otherwise the recursive program will go on until it crashes.
Recursion point: give the repeated things to the program (think from top to bottom)
4. Advantages and disadvantages of recursion
Advantage: the thinking angle of recursion is quite different from that of ordinary iteration (you can understand it as for loop), so sometimes the problems that can not be solved by iterative thinking can be solved by recursive thinking at once.
Disadvantages: the execution efficiency of recursion is usually much lower than that of iteration, so recursive programs consume more time; Because the recursive function calls the function itself continuously, the program is consistent in consuming stack space before the bottom function starts to return, so the recursive program needs to "eat" more memory space; The end condition setting of recursion is very important, because once it is set incorrectly, it is easy to cause the program to be doomed (crash).
5. Case description
5.1. Factorial
#include <stdio.h>
int recursion(int num);
int recursion(int num) {
if (num == 1) {
return 1;
}
return num * recursion(num - 1);
}
int main() {
int ret = recursion(10);
printf("ret = %d", ret); // ret = 3628800
return 0;
}
P35_hanoi problem
reference resources: http://c.biancheng.net/view/604.html
reference resources: https://fishc.com.cn/forum.php?mod=viewthread&tid=79183&extra=page%3D2%26filter%3Dtypeid%26typeid%3D584
1. Problem description
The tower of Hanoi problem means that there are three needles A, B and C on A board. There are 64 discs of different sizes sleeved on needle A, which are arranged in the order of large ones in the bottom and small ones in the top. To move these 64 discs from needle A to needle C, only one disc can be moved at A time, and needle B can be used in the moving process. But at any time, the disc on any needle must keep the big disc at the bottom and the small disc at the top. Input the number of discs to be moved from the keyboard and give the moving process.
2. Algorithmic thought
The playing method of the above game can be simply divided into three steps:
- Move the first 63 plates from X to Y and make sure the large plate is under the small plate.
- Move the 64th plate from the bottom to the top of the 64th plate.
- Move the 63 plates on Y to Z.
In the game, because only one disc can be moved at a time, it is obvious that it can be implemented with the help of another needle in the process of moving. In other words, in step 1, move 1 ~ 63 plates to y with the help of Z; Step 3 move the 63 plates on the Y needle to the Z needle with the help of X.
Therefore, we focus our new ideas on the following two questions:
- Question 1: how to move 63 plates on X to Y with the help of Z?
- Question 2: how to move the 63 plates on Y to Z with the help of X?
The solution to these two problems is the same as "how to move the 64 plates on X to Z with the help of Y?" This problem is the same, which can be disassembled into three steps: 1, 2 and 3.
Question 1 ("how do I move the 63 plates on X to Y with the help of Z?") Disassemble as:
- Move the first 62 plates from X to Z and make sure the large plate is under the small plate.
- Move the bottom 63rd plate to Y.
- Move the 62 plates on Z to Y.
Question 2 ("how to move 63 plates on Y to Z with X?") Disassemble as:
- Move the first 62 plates from Y to X and make sure the large plate is under the small plate.
- Move the bottom 63rd plate to Z.
- Move the 62 plates on X to Y.
Yes, the disassembly process of Hanoi Tower just meets the definition of recursive algorithm. Therefore, for such a difficult problem, using recursion to solve it will become quite simple!
For the tower of Hanoi problem, when only one disk is moved, the disk is directly moved from needle A to needle C. If the moving disc is n (n > 1), it is divided into several steps: move (n-1) discs from needle A to needle B (with the help of needle C); The last disc on needle A moves to needle C; (n-1) discs on needle B move to needle C (with the aid of needle A). Each time you do it, the number of moving discs is one less, decreasing step by step. Finally, when n is 1, the whole moving process is completed.
Therefore, a recursive function can be designed to solve the Hanoi Tower problem, and the whole moving process of the disk can be realized by recursion. The solving process of the problem is the simulation of the actual operation.
3. Code implementation
Thought for an hour and wrote the code independently 😗
Game address: https://zhangxiaoleiwk.gitee.io/h.html
#include <stdio.h>
void hanoi(int num, char x, char y, char z);
void hanoi(int num, char x, char y, char z)
{
// Set recursive exit
if (num == 1)
{
// When there is only one, move directly
// Note the target column and auxiliary column and num here= 1 is different.
printf("num: %d %c Move to %c\n", num, x, z);
return;
}
// Recursive point
// 1. First remove the upper pile and move it to the auxiliary column together
hanoi(num - 1, x, z, y);
// 2. Move the lower piece to the target column
printf("num: %d %c Move to %c\n", num, x, z);
// 3. Move all above the auxiliary column to the target column
hanoi(num - 1, y, x, z);
}
int main()
{
hanoi(3, 'x', 'y', 'z');
return 0;
}
4. Summary
The hanoi() function defined in this example is a recursive function with four formal parameters "n", "X", "Y" and "Z". "N" is the number of moving discs, "X", "Y" and "Z" respectively represent three needles, whose function is to move n discs on X to Z. When n=1, directly move the disc on X to Z and output "x-z". When n=1, then recursively call hanoi() function, move (n-1) discs from X to y, and output "x-z"; Then recursively call the hanoi() function to move (n-1) disks from y to Z. In the process of recursive function call, "n=n-1", the value of n decreases step by step. Finally, n=1, terminate the recursive call, return layer by layer, and the moving process ends.
P36_ Quick sort
reference resources: https://blog.51cto.com/u_14819316/3829823
1. Quick sort concept
The records to be arranged are separated into two independent parts by one-time sorting. If the keywords of one part of the records are smaller than those of the other part, the records of the two parts can be sorted separately to achieve the order of the whole sequence. It mainly adopts the divide and conquer method and the number of excavation and filling. The divide and conquer method is to decompose the big problem into each small problem and solve the small problem, so that the big problem can be solved.
2. Algorithm idea
Let's make clear the idea of heap sorting first, and make clear the logic first, so as not to rush to write code.
We first have an unordered array, for example
int[] arr={4,2,8,0,5,7,1,3,9};
2.1. The first step is to take the benchmark number
Reference number (pivot): take the first element of the array. At this time, the reference number: arr[0]=4
Two variables i and j are defined to point to the first element start and the last element end of the unordered array respectively.
//start int i=start; int j=end; //Get benchmark number int temp=arr[start];
2.2. The second step is the partition process
In the partition process, all numbers larger than the benchmark number are placed on its right, and all numbers smaller or equal than the benchmark number are placed on its left.
We first define the first element arr[0]=4 as the reference element. At this time, the first position of the array is the pit. Then we need to start from the right to the left of the array to find the elements less than the reference number and exchange positions with the pit.
while(i<j){
//From right to left, find the one smaller than the benchmark number
while(i<j&&arr[j]>=temp){
j--;
}
//Judge the equality and fill the pit
if(i<j){
arr[i]=arr[j];
i++;
}
}
After changing the position, now convert to find elements larger than the benchmark number from the left to the right of the array:
while(i<j){
//From right to left, find the one smaller than the benchmark number
while(i<j&&arr[j]>=temp){
j--;
}
//Judge the equality and fill the pit
if(i<j){
arr[i]=arr[j];
i++;
}
//From left to right, look for one larger than the benchmark number
while(i<j&&arr[i]<temp){
i++;
}
//Judge the equality and fill the pit
if(i<j){
arr[j]=arr[i];
j--;
}
}
After changing the position, now start searching from the right to the left of the array again. Elements smaller than the benchmark number:
Repeat this operation until it is divided into left and right zones, and then fill the benchmark number into the pit, so that the first sequence is completed. As follows:
//Put the reference number at i=j arr[i]=temp;
2.3. The third step is to repeat the partition operation for the two sections
Here, we repeat the above partition operation for the two divided intervals until there is only one element in each interval.
Repeat the above operations until the left and right partitions are arranged in order, and the whole sorting process is completed:
//Quickly arrange the left half QuickSort(arr,start,i-1); //Quickly arrange the right half QuickSort(arr,i+1,end);
3. Complete code
java version
import java.util.Arrays;
public class Quick_Sort {
public static void main(String[] args) {
int[] arr=new int[]{4,2,8,0,5,7,1,3,9};
System.out.println(Arrays.toString(QuickSort(arr,0,arr.length-1)));
}
public static int[] QuickSort(int[] arr,int start,int end){
//start
int i=start;
int j=end;
//Get benchmark number
int temp=arr[start];
//I < J is the cycle condition
if(i<j){
while(i<j){
//From right to left, find the one smaller than the benchmark number
while(i<j&&arr[j]>=temp){
j--;
}
//Judge the equality and fill the pit
if(i<j){
arr[i]=arr[j];
i++;
}
//From left to right, look for one larger than the benchmark number
while(i<j&&arr[i]<temp){
i++;
}
//Judge the equality and fill the pit
if(i<j){
arr[j]=arr[i];
j--;
}
}
//Put the reference number at i=j
arr[i]=temp;
//Quickly arrange the left half
QuickSort(arr,start,i-1);
//Quickly arrange the right half
QuickSort(arr,i+1,end);
}
return arr;
}
}
c version
#include <stdio.h>
int arr[] = {1, 10, 3, 4, 9, 2, 22,0};
void quikeSort(int arr[], int _left, int _right);
void quikeSort(int arr[], int _left, int _right)
{
int left = _left;
int right = _right;
int pivot = arr[left];
while (left < right)
{
// The right starts to shrink the index toward the middle
while (left < right && arr[right] <= pivot)
{
right--;
}
// Pit filling
if (left < right)
{
arr[left] = arr[right];
left++;
}
// The left starts to shrink the index toward the middle
while (left < right && arr[left] >= pivot)
{
left++;
}
// Pit filling
if (left < right)
{
arr[right] = arr[left];
right--;
}
}
// Fill base value
arr[left] = pivot;
if (_left < right - 1)
{
quikeSort(arr, _left, right - 1);
}
if (left + 1 < _right)
{
quikeSort(arr, left + 1, _right);
}
}
int main()
{
int len = sizeof(arr) / sizeof(int);
quikeSort(arr, 0, len - 1);
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
4. Algorithm analysis
4.1. Time complexity
The worst time complexity of quick sort is O(n^2), and the best time complexity is O(nlogn), so the average time complexity is finally calculated as O(nlogn).
4.2. Spatial complexity
The space complexity is O(1), because no additional set space is used.
4.3. Algorithm stability
Quick sorting is an unstable sorting algorithm. Because we cannot guarantee that equal data will be scanned and stored in order.
The worst time complexity is O(n^2), and the best time complexity is O(nlogn), so the average time complexity is finally calculated as O(nlogn).
P37_ Dynamic memory management 1
malloc
Request dynamic memory space
free
Free dynamic memory space
calloc
Request and initialize a series of memory spaces
realloc
Reallocate memory space
1,malloc
Function prototype:
void *malloc(size_t size);
malloc function requests the system to allocate memory space of size bytes and returns a pointer to this space.
If the function call is successful, a pointer to the requested memory space is returned. Since the return type is void pointer (void *), it can be converted into any type of data; If the function call fails, the return value is NULL. In addition, if the size parameter is set to 0, the return value may also be NULL, but this does not mean that the function call fails.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *ptr;
ptr = (int *)malloc(sizeof(int));
if (ptr == NULL) {
printf("Failed to allocate memory!\n");
exit(1);
}
printf("Please enter an integer:");
scanf("%d", ptr);
printf("The integer you entered is:%d\n", *ptr);
free(ptr);
return 0;
}
2,free
Function prototype:
void free(void *ptr);
The free function frees the memory space pointed to by the ptr parameter.
This memory space must be requested by malloc, calloc, or realloc functions. Otherwise, the function will result in undefined behavior. If the ptr parameter is NULL, no action is taken. Note: this function does not modify the value of ptr parameter, so it still points to the original place (becomes illegal space) after calling.
Memory leaks even if memory space is not released
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
while (1)
{
malloc(1024);
}
return 0;
}
3. Memory leak
There are two main causes of memory leakage:
- Implicit memory leak (i.e. the memory block is exhausted and not released in time by using the free function)
- Missing memory block address
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *ptr;
int num = 123;
ptr = (int *)malloc(sizeof(int));
if (ptr == NULL)
{
printf("Failed to allocate memory!\n");
exit(1);
}
printf("Please enter an integer:");
scanf("%d", ptr);
printf("The integer you entered is:%d\n", *ptr);
ptr = #
printf("The integer you entered is:%d\n", *ptr);
free(ptr);
return 0;
}
P38_ Dynamic memory management 2
1. Initialize memory space
Functions starting with mem are compiled into the string standard library, and the declaration of the function is contained in string H in this header file:
- memset – fills the memory space with a constant byte
- memcpy – copy memory space
- memmove – copy memory space
- memcmp – compare memory space
- memchr – searches memory space for a character
2,calloc
See: https://www.runoob.com/cprogramming/c-function-calloc.html
Function prototype:
void *calloc(size_t nmemb, size_t size);
The calloc function dynamically applies for nmemb consecutive memory spaces with a length of size in memory (that is, the total space size applied is nmemb * size), and all these memory spaces are initialized to 0.
An important difference between calloc function and malloc function is:
- After applying for memory, the calloc function automatically initializes the memory space to zero
- malloc function does not initialize, and the data inside is random
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, n;
int *a;
printf("Number of elements to enter:");
scanf("%d",&n);
a = (int*)calloc(n, sizeof(int));
printf("input %d Number:\n",n);
for( i=0 ; i < n ; i++ )
{
scanf("%d",&a[i]);
}
printf("The number entered is:");
for( i=0 ; i < n ; i++ ) {
printf("%d ",a[i]);
}
free (a); // Free memory
return(0);
}
3,recalloc
Why is there no "recalloc" in the C standard?
Function prototype:
void *realloc(void *ptr, size_t size);
The following points need attention:
- The realloc function modifies the size of the memory space pointed to by ptr to size bytes
- If the newly allocated memory space is larger than the original, the data of the old memory block will not change; If the size of the new memory space is smaller than the old memory space, it may lead to data loss. Use it with caution!
- This function moves the data in the memory space and returns a new pointer
- If the ptr parameter is NULL, calling this function is equivalent to calling malloc(size)
- If the size parameter is 0 and the ptr parameter is not NULL, calling this function is equivalent to calling free(ptr)
- Unless the ptr parameter is NULL, the value of ptr must be returned by the previous function called malloc, calloc or realloc.
P39_ Memory layout law of C language
1. Memory layout law of C language
You can see that the address of the local variable is the high ground, followed by the dynamic memory space applied by the malloc function, followed by the global variable and the static local variable.
However, both of them need to distinguish whether they have been initialized. Those that have been initialized should be placed in one piece and those that have not been initialized should be placed in one piece. The uninitialized address should be higher than those that have been initialized. Next comes the string constant, and finally the address of the function.
2. Memory space division of typical C language programs
According to the memory address from low to high, it is divided into:
- Text segment
- Initialized data segment
- BSS segment (Bss segment/Uninitialized data segment)
- Stack
- Heap
3. Text segment
Code segment usually refers to a memory area used to store program execution code.
The size of this area has been determined before the program runs, and the memory area is usually read-only.
In the code segment, it is also possible to include some read-only constant variables, such as string constants.
4. Initialized data segment
Data segments are usually used to store initialized global variables and local static variables.
5. BSS segment (Bss segment/Uninitialized data segment)
BSS segment usually refers to a memory area used to store uninitialized global variables in the program.
BSS is the abbreviation of English Block Started by Symbol. The data in this section will be automatically initialized to the number 0 before the program runs.
6. Pile
Previously, we learned the dynamic memory management functions. The memory space applied by using them is allocated in this heap.
Therefore, heap is used to store the memory segment dynamically allocated during the operation of the process. Its size is not fixed and can be dynamically expanded or reduced.
When the process calls malloc and other functions to allocate memory, the newly allocated memory is dynamically added to the heap; When using functions such as free to release memory, the released memory is removed from the heap.
7. Stack
You may often hear the word stack, which generally refers to this stack.
Stack is the memory area of function execution, which usually shares the same area with the heap.
8. Comparison of heap and stack
Heap and stack are the most important elements of C language runtime. Let's compare them below.
Application method:
- The heap is manually requested by the programmer
- The stack is automatically allocated by the system
Release method:
- The heap is manually released by the programmer
- The stack is automatically released by the system
Life cycle:
- The life cycle of the heap is from dynamic application to active release by the programmer, and different functions can be accessed freely
- The life cycle of the stack starts from the function call to the end of the function return. Local variables between functions cannot access each other
Development direction:
- Heap, like other sections, develops from low address to high address
- Stack, on the contrary, develops from high address to low address