Manually tear the linked list (insert, delete, sort) and pointer operation

Linked list

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node{
       // Node type of single linked list 
    int data;
    struct LNode * next;
}LNode, * PNode;  //LinkList amount to  struct Node *  Pointer form of linked list nodes 

// Create a linked list 
PNode create_list(){
       
    int len;
    int val;  // Temporarily store the node value entered by the user 

    printf(" Enter the length of the linked list len:\n");
    scanf("%d", &len);
    //(struct Node *)/(PNode) Force the allocated space to fit struct Node * Of chunk,sizeof Fill in the LNode Calculate the number of bytes occupied by a linked list node 
    // The header node that does not store data 
    LNode * pHead = (LNode *)malloc(sizeof(LNode));
    if(NULL == pHead){
    
        printf(" Allocation failed , Termination of procedure !\n");
        exit(-1);
    }
    PNode pre = pHead;
    pre->next = NULL;
    for(int i = 0; i < len ; i++){
    
        printf(" Please enter a value for this node val:\n");
        scanf("%d", &val);
        LNode * pnode = (LNode *)malloc(sizeof(LNode));  
        // take pnode Add the linked list and assign values , Set to at the end of the linked list NULL
        pre->next = pnode;
        pnode->data = val;
        pnode->next = NULL;
        pre = pnode;
    }
    return pHead;
}

// Traverse the linked list and output each element 
void traverse_list(PNode pHead){
    
    printf(" The contents of the linked list are as follows ：\n");
    PNode pcur = pHead->next;   //pHead It's empty 
    while (pcur != NULL)
    {
    
        printf("%d ", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
    return;
}

// Returns whether the list is empty 
bool is_Empty(PNode pHead){
    
    if(pHead->next == NULL){
    
        return true;
    }else{
    
        return false;
    }
}

// Return the length of the list 
int length_list(PNode pHead){
    
    PNode pcur = pHead->next;
    int len = 0;
    while (pcur != NULL)
    {
    
        len++;
        pcur = pcur->next;
    }
    return len;
}

// In the pos In a position （pos from 1 Start ） Insert an element data,  Returns whether the operation was successful  len=5 be pos It can be for 6 Not for 7
bool insert_list(PNode pHead, int pos, int val){
    
    PNode pcur = pHead;  // The initial node is the precursor node of the first node （ Head node ）
    int len = length_list(pHead);  // Get the length of the list 
    // First, judge whether the input is reasonable 
    if(pos < 1 && pos > len + 1){
    
        return false;
    }
    // Find the precursor node pcur
    for(int i = 1; i < pos; i++){
       
        pcur = pcur->next;  
    }
    // Create a new node and insert 
    PNode pNew = (PNode)malloc(sizeof(LNode)); 
    if(NULL == pHead){
    
        printf(" Allocation failed , Termination of procedure !\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->next = pcur->next;
    pcur->next = pNew;
    return true;

}

// Delete the first pos Elements in position , And return the deleted element to 
bool delete_list(PNode pHead, int pos, int * p){
    
    PNode pcur = pHead;  // The initial node is the precursor node of the first node （ Head node ）
    int len = length_list(pHead);  // Get the length of the list 
    // First, judge whether the input is reasonable 
    if(pos < 1 && pos > len){
    
        return false;
    }
    // Find the precursor node pcur
    for(int i = 1; i < pos; i++){
       
        pcur = pcur->next;  
    }
    // delete q
    PNode q = pcur->next;   //q For the node to be deleted ,  You can't write directly here pcur->next->next
    pcur->next = q->next;
    *p = q->data;
    free(q);
    return true;
}

// Sorting of linked lists ( Selection sort )  Ascending 
void sorted_list(PNode pHead){
    
    PNode p, q;  //p Is the left pointer to be compared ,q Traverse the pointer for the right 
    int t;

    for(p = pHead->next ; p->next != NULL ; p = p->next){
      // Left pointer movement ,  The loop condition ： The next element is not empty 
        for(q = p->next ; q != NULL ; q = q->next){
       // The right pointer moves , The loop condition ： The current pointer is not null 
            if(p->data > q->data){
       // When smaller values appear, they are exchanged 
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

int main(){
    
    PNode pHead = NULL;  // Must declare in advance Phead And set it as NULL
    pHead = create_list();  // Create a linked list 
    int val;  // Save the values of deleted elements 
    traverse_list(pHead);  // Traverse the output list 
    printf(" The length of the list is ：%d\n", length_list(pHead));
    // sorted_list(pHead);
    traverse_list(pHead);
    printf(" Insert an element \n");
    if(insert_list(pHead, 3, 100) == false){
    
        printf(" Illegal input ！\n");
    }
    traverse_list(pHead);
    printf(" Delete an element \n");
    if(delete_list(pHead, 2, &val) == false){
    
        printf(" Illegal input ！\n");
    }
    printf(" The deleted value is ：%d\n", val);
    traverse_list(pHead);
    return 0;
}

The pointer （ Address ）

Pointer basis

cpu Interaction with memory ： Address line 、 Control line 、 cable （ With 4G Memory, for example ）

• The pointer == Address

• A pointer variable is a variable that holds the address of a memory unit

• The essence of pointer is a non negative integer with limited operation

    int * p; //p It's a variable name ,int *  Indicates that this variable can only store int The address of a type variable 
    int i = 10;  // hypothesis i The address for 2000H, The stored value is 10
    int j;

    // p = 10; Values cannot be stored 
    p = &i;  //p Can store address , That is to say i The address of 2000H, Can be called p Yes i, be *p It stands for i
    j = *p; // Equivalent to j = i
    printf("i = %d, j = %d, p = %d\n", i, j, *p);

int *p = &i; // Equivalent to int *p; p = &i;

Modify the value of ordinary variables in the main function through the called function ：

void f(int *p){
      // Define a pointer variable （ Shape parameter ）
    *p = 100; // take p The value in the address pointed to is changed to 100
}

void function2(){
    
    int i = 9;

    f(&i);
    printf("i = %d\n", i);
}

Pointers and one-dimensional arrays

1. One dimensional array name is a pointer constant
2. a[i] Equivalent to *（a+i）
3. p±i The value of is p±i*(p The number of bytes of the variable pointed to )

void function3(){
    
    int a[5] = {
    1, 2, 3, 4, 5};
    // 3[a] = 0; // Equivalent to *(3+a) namely a[3]
    // printf("%d", a[3]);
    a[3] == *(3 + a);
    //(a+1) It stands for a+1（ The second element of the array ） The address of   The length of each element of the array 4 Bytes, so the output is as follows 4 interval 
    // Essentially  a+sizeof(int)
    printf("%p %p %p %p \n", a+1, a+2, a+3, a+4);
    printf("%d\n", *a+10);  // Fetch *a And then add 10

}

Pointer and address

32 Bit pointer 4 Bytes ,64 Bit pointer 8 Bytes , And use The address of the first byte Represents the address of the entire variable ：

void function5(){
    
    double * p;
    double x = 66.6;
    //32 Bit pointer 4 Bytes ,64 Bit pointer 8 Bytes 
    p = &x; //x Occupy 8 Bytes ,1 Bytes 8 position , however p Save only the first address （ The address of the first byte ）

    double arr[3] = {
    1.1, 2.2, 3.3};
    
    printf("%p\n", &arr[0]);
    printf("%p\n", &arr[1]);

}

Pointer in function

void Show_Array(int * p, int len){
    
    
    for(int i = 0;i<len;i++){
    
        printf("%d\n", p[i]);
    }
}

void function4(){
    
    int a[5] = {
    1, 2, 3, 4, 5};
    Show_Array(a, 5);  //a Equivalent to &a[0]
}

Modify the value of an argument through a function :

void f2(int ** q){
      //p Itself is a pointer , The address of the pointer is passed in , So the type is int **
    *q = (int *)0xFFFFFFFF;
}


void function6(){
    
    int i = 9;
    int * p = &i; //int * p; p = &i;

    printf("%p\n", p);
    f2(&p);  // Hope to rewrite p, So you need to send p The address of 
    printf("%p\n", p);
}

Structure

1. Structure variables cannot be added, subtracted, multiplied, or divided , You can assign values to each other
2. Common structure variables and structure pointers

struct Student{
    
    int sid;
    char name[200];
    int age;
};    // Semicolons cannot be omitted 

void function1(){
    
    struct Student st = {
    1000, "zhangsan", 20};
    st.sid = 100;
    strcpy(st.name, "lisi");
    // printf("%d %s %d\n", st.sid, st.name, st.age);
    struct Student * pst;
    pst = &st;
    pst->sid = 99; //pst->sid  Equivalent to  (*pst).sid  Equivalent to st.sid
    // The above formula means pst Of the structural variables pointed to sid This member 
}

void f(struct Student * pst){
    
    pst->age = 11;
    strcpy(pst->name, "aaa");
    pst->sid = 666;
}

// This method consumes memory   waste time   Not recommended ( At least... Is passed to the function 208 Bytes )  It can be changed to pointer passing 
void g(struct Student st){
    
    printf("%d %s %d\n", st.sid, st.name, st.age);  
}

void g2(struct Student * st){
    
    printf("%d %s %d\n", st->sid, st->name, st->age);
}

// Send only 8 Bytes （64 Bit pointer ）, Time saving and labor saving 
void function2(){
    
    struct Student st;
    f(&st);
    // printf("%d %s %d\n", st.sid, st.name, st.age);
    g2(&st);
}

typedef Use

typedef int element;  // by int Take a new name 

typedef struct Student{
    
    int sid;
    char name[200];
    int age;
}* PST;    // Equivalent to struct Student *

int main(){
    
    struct  Student st;
    PST ps = &st;
    
    ps->age = 200;
    printf("%d\n", ps->age);

    return 0;
}

Dynamic memory allocation

int * p = (int *)malloc(4);
free(p);
// Release p Memory pointed to ,p Itself is static , Cannot manually release ,p Its own memory can only be in p When the function in which the variable is located terminates, it is automatically released by the system 
/* 1. To use malloc function , You must add malloc.h This header file  2.malloc A function has only one parameter , And the formal parameter is an integer  3. 4 Indicates that the system is requested to allocate 4 Bytes  4.malloc The function can only return the address of the first byte  5.12 Row assigned 8 Bytes ,p Variables of 4 Bytes ,p The memory pointed to also accounts for 4 Bytes  6.p The memory itself is allocated statically ,p The memory pointed to is dynamically allocated  */