Linear table sequence table comprehensive application problem p18

Definition of a single linked list

typedef struct LNode {
    
    int data;
    struct LNode *next;
} LNode, *LinkList;

Initialization of single chain table

No leading node

bool InitList(LinkList &L) {
    
    L = NULL;
    return true;
}

Leading node

bool InitList(LinkList &L) {
    
    L = (LNode *) malloc(sizeof(LNode));	// Assign a head node 
    if (L == NULL)	// Out of memory ,  Allocation failed 
        return false;
    L->next = NULL;		// Apply for a header node , Set the pointer field to null .
    return true;
}

The distinction between head node and head pointer ： No matter with or without , The header pointer always points to the first node of the single linked list , The head node is the first node in the single linked list of the head node , Information is usually not stored in nodes .

Determine whether the single chain table is empty

No leading node

bool Empty(LinkList L) {
    
    return L == NULL;
}

Leading node

bool Empty(LinkList L) {
    
    return L->next == NULL;
}

Insert operation of single chain table

In bit order ( No leading node )

bool ListInsert(LinkList &L, int i, int e) {
    
    if (i < 1) return false;
    if (i==1) {
    
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode *p;   // The pointer p Point to the currently scanned node 
    int j = 1;  // Record pointer p Which node is it currently on 
    p = L;  //L Point to the head node ,  And the header node does not store data 

    while (p != NULL && j < i - 1) {
     // Loop to find number i-1 Nodes ,  Add data after 
        p = p->next;
        j++;
    }
    if (p == NULL) return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;    // assignment 
    s->next = p->next;  // First the p The original later node   And   New node s Connect 
    p->next = s;    // then p The node of   And   New node s Connect 
    return true;
}

In bit order ( Leading node )

bool ListInsert(LinkList &L, int i, int e) {
    
    if (i < 1) return false;
    LNode *p;   // The pointer p Point to the currently scanned node 
    int j = 0;  // Record pointer p Which node is it currently on 
    p = L;  //L Point to the head node ,  And the header node does not store data 

    while (p != NULL && j < i - 1) {
     // Loop to find number i-1 Nodes ,  Add data after 
        p = p->next;
        j++;
    }
    if (p == NULL) return false;	// Judge i Whether the value of is legal 

    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;    // assignment 
    s->next = p->next;  // First the p The original later node   And   New node s Connect 
    p->next = s;    // then p The node of   And   New node s Connect 
    return true;
}

Post insert operation

stay p Insert element after node e

bool InsertNextNode(LNode *p, int e) {
    
    if (p == NULL) return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;	// The node s Connected to the p after 
    return true;
}

simplify : In the i Location insert element e( Leading node )

bool ListInsert(LinkList &L, int i, int e) {
    
    if (i < 1) return false;
    LNode *p;   // The pointer p Point to the currently scanned node 
    int j = 0;  // Record pointer p Which node is it currently on 
    p = L;  //L Point to the head node ,  And the header node does not store data 

    while (p != NULL && j < i - 1) {
     // Loop to find number i-1 Nodes ,  Add data after 
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e );
}

Forward operation

stay p Insert element before node e ( place a substitute by subterfuge )

bool InsertPriorNode(LNode *p, int e) {
    
    if (p == NULL) return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL) return false;

    s->next = p->next;
    p->next = s;    // New node s Connected to the p after 
    s->data = p->data;  // take p Copy the value of to s in 
    p->data = e;    //e Assign a value to p,  Now s Equivalent to the original p,  current p For the new node inserted before 
    return true;
}

Single linked list deletion operation

In bit order ( Leading node )

//L  Single chain list  i  Deleted bit order  e  Deleted values 
bool ListDelete(LinkList &L, int i, int &e) {
    
    if (i < 1) return false;
    LNode *p;
    int j = 0;
    p = L;    //L Point to the head node 
    while (p != NULL && j < i - 1) {
    
        p = p->next;
        j++;
    }
    if (p == NULL) return false;    //i The value of is illegal 
    if (p->next == NULL) return false;    // The first i-1 There are no other nodes after nodes 

    LNode *q = p->next;     // Make p Point to the deleted node 
    e = q->data;    // use e Returns the value of the deleted node 
    p->next = q->next;  // take q The node is disconnected from the linked list 
    free(q);    // Release the storage space of the node 
    return true;

}

Delete... In bit order ( No leading node )

bool ListDeleteWithout(LinkList &L, int i, int &e) {
    
    if (i < 1) return false;
    if (i == 1) {
    
        LNode *p = L->next;
        e = p->data;
        L->data = p->data;
        L->next = p->next;
        free(p);
        return true;
    }

    LNode *p;
    int j = 1;
    p = L;    //L Point to the head node 
    while (p != NULL && j < i - 1) {
    
        p = p->next;
        j++;
    }
    if (p == NULL) return false;    //i The value of is illegal 
    if (p->next == NULL) return false;    // The first i-1 There are no other nodes after nodes 

    LNode *q = p->next;     // Make p Point to the deleted node 
    e = q->data;    // use e Returns the value of the deleted node 
    p->next = q->next;  // take q The node is disconnected from the linked list 
    free(q);    // Release the storage space of the node 
    return true;

}

Specify node deletion

Expand : Delete node *p

​ To delete a given node *p, The usual way is to find the precursor node from the head node of the linked list , Then perform the delete operation , The time complexity of the algorithm is O(n)

​ Actually , Delete node *p The operation of can be deleted *p The following node operation of , The essence is to give the value of its subsequent node to its body , Then delete the following node , It can also make the time complexity O(1)

q = p->next;
p->data = q->data;	//q->data It can also be written as p->next->data
p->next = q->next;
free(q);

Focus on understanding the special operations of pre insertion and deletion

Single linked list lookup operation

Find... In bit order

Algorithmic thought ： Starting from the first node of a single linked list , Search down the pointer field one by one , Until I find the i It's a node , Otherwise, the pointer field of the last node is returned NULL.

Core code

//  Find single linked list L pass the civil examinations  i  Node pointer at position 
LNode *GetElem(LinkList L, int i) {
    
    if (i < 0) return NULL;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i) {
    
        p = p->next;
        j++;
    }
    return p;
}

According to the value lookup

Algorithmic thought ： Starting from the first node of a single linked list , Compare the values of the data fields of each node in the table in turn , If the value of a node's data field is equal to x, Then return the pointer of the node and record the location of the node index; If there is no such node in the whole single linked list , It returns null .

Core code

/** *  Find value x In a single linked list L Node pointer in  * @param L  Single chain list  * @param e  The value of the search  * @param index  The position corresponding to the value  * @return */
LNode *LocateElem(LinkList L, int e, int &index) {
    
    index = 1;
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
     // From 1 Search nodes data The value is e The node of 
        p = p->next;
        index++;
    }
    return p;
}

Create a single linked list ( Leading node )

The forward interpolation method establishes

Algorithmic thought ： Initialize a single list first , Its header node is empty , Then insert new nodes circularly *s： take s Of next Points to the next node of the head node , And then put the next Point to s.

Core code

LinkList HeadInsert(LinkList &L) {
    
    InitList(L);    // Initialize single chain table 
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;    // Insert the new node into the table , L For the head pointer 
        scanf("%d", &x);
    }
    return L;
}

It's important to point out that , The order of nodes in the single linked list established by head interpolation is inconsistent with the order of input data , It's the opposite . If you want the order of the two to be consistent , You can use the tail interpolation method to establish a single linked list .

The tail insertion method is established

Algorithmic thought ： Initialize a single list first , Then declare a tail pointer r, Give Way r Always point to the tail node of the current linked list , Loop to insert a new node into the tail of the single linked list *s, Tail pointer r Of next The domain points to the new node , Then modify the tail pointer r Point to the new node , That is, the tail node of the current linked list . Finally, don't forget to empty the pointer field of the tail node .

Core code

LinkList TailInsert(LinkList &L) {
    
    InitList(L);    // Initialize single chain table 
    int x;
    LNode *s, *r = L;
    scanf("%d", &x);
    while (x != 9999) {
    
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;      //r Point to the new tail node 
        scanf("%d", &x);
    }
    r->next = NULL;     // The tail node pointer is set to null 
    return L;
}

The length of a single list

Algorithmic thought ： Declare a pointer p,p Point to the first node that the header node points to , If p The node pointed to is not empty , Then add one to the length , take p Point to the next node , Until the last node is traversed .

Core code

int Length(LinkList L) {
    
    int len = 0;
    LNode *p = L;
    while (p->next != NULL) {
    
        p = p->next;
        len++;
    }
    return len;
}

Traversing a single linked list

Algorithmic thought ： Declare a pointer p, Start from the first node pointed to by the ab initio node , If p Not empty , Then output the value of the current node , And will p Point to the next node , Until the last node is traversed .

Core code

void PrintList(LinkList L) {
    
    LNode *p = L->next;
    while (p) {
    
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

Single chain table search , Complete code after creation

/** * @Author JiaHaoHao * @Date 2022/07/01 12:44 * @ClassName: test11 * @Description:  Single linked list establishment  */
#include "stdio.h"
#include "stdlib.h"

typedef struct LNode {
    
    int data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList &L) {
    
    L = (LNode *) malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

/** *  Forward interpolation method to establish a single linked list  * @param L * @return */
LinkList HeadInsert(LinkList &L) {
    
    InitList(L);    // Initialize single chain table 
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;    // Insert the new node into the table , L For the head pointer 
        scanf("%d", &x);
    }
    return L;
}

/** *  To establish a single chain table by tail insertion  * @param L * @return */
LinkList TailInsert(LinkList &L) {
    
    InitList(L);    // Initialize single chain table 
    int x;
    LNode *s, *r = L;
    scanf("%d", &x);
    while (x != 9999) {
    
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;      //r Point to the new tail node 
        scanf("%d", &x);
    }
    r->next = NULL;     // The tail node pointer is set to null 
    return L;
}

// Print linked list 
void PrintList(LinkList L) {
    
    LNode *p = L->next;
    while (p) {
    
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

/** *  Find... In bit order  * @param L * @param i * @return */
LNode *GetElem(LinkList L, int i) {
    
    if (i < 0) return NULL;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i) {
    
        p = p->next;
        j++;
    }
    return p;
}

/** *  According to the value lookup  * @param L  Single chain list  * @param e  The value of the search  * @param index  The position corresponding to the value  * @return */
LNode *LocateElem(LinkList L, int e, int &index) {
    
    index = 1;
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
     // From 1 Search nodes data The value is e The node of 
        p = p->next;
        index++;
    }
    return p;
}

// Long table 
int Length(LinkList L) {
    
    int len = 0;
    LNode *p = L;
    while (p->next != NULL) {
    
        p = p->next;
        len++;
    }
    return len;
}


int main() {
    
    LinkList L;

// HeadInsert(L); // Head insertion to create 
    TailInsert(L);  // The tail insertion method is established 
    PrintList(L);   // Print linked list ;

    int i = 3;
    printf(" The first %d The values are %d\n", i, GetElem(L, i)->data);

    int e = 4;
    int index = -1;
    LocateElem(L, e, index);
    printf(" The value is %d The node of is %d\n", e, index);

    printf(" Long table : %d\n", Length(L));

    return 0;
}

Running results

//  Tail insertion creates 
C:\Users\User\Desktop\dataStructure\cmake-build-debug\01xianxingbiao11.exe
1 5 9 8 4 5 6 2 1 4 9999
1	5	9	8	4	5	6	2	1	4	
 The first 3 The values are 9
 The value is 4 The node of is 5
 Long table : 10

Process finished with exit code 0