当前位置：网站首页>Preliminary introduction to C miscellaneous lecture linked list

Linked list It's a kind of Physical storage is discontinuous , Data elements Logical continuity Through the Pointer to the variable preservation Next node The address of , A linear storage structure .

3、 The characteristics of linked list

The linked list consists of a series of node （ Each element in the linked list is called a node ） form , Nodes are running Dynamic generation （malloc,calloc）, Every node package It consists of two parts ：

Data fields ： Store node data （ The core ）

Pointer to the domain ： Structure pointer variable Save the address of the next node

Knowledge point 2【 Static list 】

#include <stdio.h>
// Design node type 
typedef struct stu
{
    // Data fields 
    int num;
    char name[32];
    float score;

    // Pointer to the domain 
    struct stu *next;
}STU;

int main(int argc, char const *argv[])
{
    // Node of static linked list   Not from the heap 
    STU node1={100, "lucy", 77.7f};
    STU node2={101, "bob", 66.7f};
    STU node3={102, "tom", 55.7f};
    STU node4={103, "hehe", 74.7f};
    STU node5={104, "xixi", 73.7f};
    
    // Build a list 
    STU *head = NULL;
    head = &node1;
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = NULL;

    // Traversing the linked list ( From the beginning    Traverse node by node )
    STU *pb = head;
    while(pb != NULL)
    {
        printf("%d %s %f\n", pb->num, pb->name, pb->score);
        // Move to the next node 
        pb = pb->next;
    }

    return 0;
}

Knowledge point 3【 Operation of linked list 】

increase 、 Delete 、 Change 、 check

Student management system Explain the linked list

1、 Linked list insertion node

Help information function ：

void help(void)
{
    printf("******************************\n");
    printf("* insert: Insert linked list node         *\n");
    printf("* printf: Traversing linked list nodes         *\n");
    printf("* search: Query linked list nodes         *\n");
    printf("* delete: Delete the linked list node         *\n");
    printf("* free: Release the linked list node           *\n");
    printf("* quit: Traversing linked list nodes           *\n");
    printf("******************************\n"); 
    return; 
}

1.1： Head Insert node before

STU* insert_link(STU *head, STU tmp)
{
    // Apply for space for the inserted node 
    STU *pi = (STU *)calloc(1,sizeof(STU));
    // Assign a value to a space 
    *pi = tmp;
    pi->next = NULL;

    // Determine whether the linked list exists 
    if(NULL == head)// empty 
    {
        head = pi;
        //return head;
    }
    else// Non empty 
    {
        pi->next = head;
        head = pi;
        //return head;
    }

    return head;
}

1.2： The tail Insert node after

// Tail insertion node 
STU* insert_link(STU *head, STU tmp)
{
    // Apply for space for the inserted node 
    STU *pi = (STU *)calloc(1,sizeof(STU));
    // Assign a value to a space 
    *pi = tmp;
    pi->next = NULL;

    // Determine whether the linked list exists 
    if(NULL == head)
    {
        head = pi;
        return head;
    }
    else
    {
        // Find the tail node 
        STU *pb = head;
        while(pb->next != NULL)
            pb = pb->next;
        
        // take pi Insert into   After the tail node 
        pb->next = pi;
        return head;
    }

    return head;
}

1.3： Orderly Insert node

// Insert nodes in order 
STU* insert_link(STU *head, STU tmp)
{
    // Apply for space for the inserted node 
    STU *pi = (STU *)calloc(1,sizeof(STU));
    // Assign a value to a space 
    *pi = tmp;
    pi->next = NULL;

    // Determine whether the linked list exists 
    if(NULL == head)
    {
        head = pi;
        return head;
    }
    else
    {
        // Look for the insertion point 
        STU *pf = NULL, *pb = NULL;
        pf = pb = head;
        // from childhood ---> Big sort 
        while((pb->num < pi->num) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }

        if(pb->num >= pi->num)// Head insertion 、 Middle insert 
        {
            if(pb == head)// Head insertion 
            {
                pi->next = head;
                head = pi;
            }
            else// Middle insert 
            {
                pf->next = pi;
                pi->next = pb;
            }
        }
        else if(pb->next == NULL)// Tail insertion 
        {
            pb->next = pi;
        }
    }

    return head;
}

2、 Traversing linked list nodes

void printf_link(STU *head)
{
    //1、 Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return;
    }
    else//2、 The linked list exists , Traverse the linked list node by node 
    {
        STU *pb = head;
        while(pb != NULL)
        {
            printf("%d %s %f\n", pb->num, pb->name, pb->score);
            //pb Point to next node 
            pb = pb->next;
        }
    }

    return;
}

3、 Query the specified node

STU *search_link(STU *head, char *name)
{
    // Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return NULL;
    }
    else// The linked list exists 
    {
        // Query node by node 
        STU *pb = head;
        while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
        {
            pb = pb->next;
        }

        if(strcmp(pb->name, name) == 0)// find 
            return pb;
        else
        {
            printf(" Relevant node information not found \n");
            return NULL;
        }
    }

    return NULL;
}

4、 Delete the specified node

STU* delete_link(STU *head, char *name)
 {
     // Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return head;
    }
    else
    {
        STU *pf =NULL, *pb=NULL;
        pf = pb = head;
        // Look for deletion points 
        while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }

        // Find the deletion point 
        if(strcmp(pb->name, name) == 0)
        {
            if(head == pb)// Head delete 
            {
                head= head->next;
            }
            else// Middle and end delete 
            {
                pf->next = pb->next;
            }

            // Release pb
            if(pb != NULL)
            {
                free(pb);
                pb=NULL;
            }
        }
        else// Deletion point not found 
        {
            printf(" No relevant node information was found for deletion \n");
        }
    }
    
    return head;
 }

5、 Release list

STU* free_link(STU *head)
 {
    // Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return head;
    }
    else// The linked list exists 
    {
        STU *pb = head;
        while(pb != NULL)
        {
            //head Record the position of the next node 
            head = head->next;
            // Release pb Node to 
            if(pb != NULL)
            {
                free(pb);
                pb = NULL;
            }
            //pb Point to next node 
            pb=head;
        }
        printf(" The linked list node has been completely released \n");
    }

    return head;
 }

6、 The flip of the list

STU* reverse_link(STU *head)
 {
    // Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return head;
    }
    else
    {
        STU *pb = head->next;
        STU *pn = NULL;

        // Point the header pointer field to NULL
        head->next = NULL;

        // Flip node by node 
        while(pb != NULL)
        {
            //pn Record pb->next The node of 
            pn = pb->next;
            // Reverse connection 
            pb->next = head;
            // Move head To pb On 
            head = pb;
            //pb Point to pb The node of 
            pb = pn;
        }  
    }
    return head;
 }

7、 Sorting of linked lists

// Select method to sort the linked list 
 void sort_link(STU *head)
 {
    // Determine whether the linked list exists 
    if(NULL == head)
    {
        printf(" The list does not exist \n");
        return;
    }
    else
    {
        STU *p_i = head, *p_j = head;//int i=0, j=0;
        while(p_i->next != NULL)//for(i=0;i<n-1; i++)
        {
            STU *p_min = p_i;//int min = i;
            p_j = p_min->next;//j=min+1
            while(p_j != NULL)//j<n
            {
                if(p_min->num > p_j->num)//if(arr[min] > arr[j])
                    p_min = p_j;//min = j;
                p_j = p_j->next;//j++
            }

            if(p_i != p_min)//if(i != min)
            {
                // Whole exchange 
                STU tmp = *p_i;
                *p_i = *p_min;
                *p_min = tmp;

                // Pointer field exchange 
                tmp.next = p_i->next;
                p_i->next = p_min->next;
                p_min->next = tmp.next;
            }

            p_i = p_i->next;//i++
        }
    }

    return;
 }

原网站

版权声明
本文为[Bright-SKY]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/208/202207271609319335.html