Linear lists of data structures – static linked lists

1. Why do static lists come into being?

Because both the sequential storage structure and the chained storage structure have their own advantages, as shown in the following table.

performance	Specific function	Sequential storage	Chain store
Space performance	Storage allocation	Lump-sum allocation	Dynamic allocation (excellent)
Space performance	Storage density (Explained below)	= 1 (best)	< 1
Time performance	To find the	O(n/2)	O(n/2)
Time performance	Read operation	The O (1) (best)	O((n+1)/2) Best case is 1, worst case is N
Time performance	Insert operation (Performance mainly refers to Number of elements to move)	O (n / 2) is best Best case is 0, worst case is N	The O (1), the better
Time performance	Delete operation	O((n-1)/2) Best case is 0, worst case is N minus 1	The O (1), the better

So we need to create a storage structure that can combine the advantages of sequential and linked lists, so as to achieve fast access to elements, but also can quickly add or delete data elements, so static linked lists are generated.

2. Static lists

Static linked list: a linear storage structure that combines the advantages of sequential and linked lists.

Features: 1. Allocate all memory at one time. 2. All data is stored in an array and the storage location is random. 3. The “one to one” logical relationship between data is maintained by an integer variable “cursor”.

The storage structure is as follows:Structure type:

typedef struct LNode{
	int data;// Data domain: used to store data.
	int next;// Cursor: used to find the position of the successor element in the array.
}LNode;
Copy the code

4. Spare lists

In a static linked list, in addition to the linked list composed of the data itself through the cursor, there needs to be a linked list connecting each free position, called the standby linked list.

What the standby list does: You can clearly see in the arrayIs there any free space availableTo be used when adding data. When a static linked listThe array contains data at index 0The proofAn array is full.

3. Create static linked lists

#include <bits/stdc++.h>
using namespace std;
#define maxSize 100

typedef struct LNode{
    int data;
    int next;
}LNode;

// Create an alternate linked list
void reserveArr(LNode *array){
    for(int i=0; i<maxSize; i++){ array[i].next=i+1;
        array[i].data=- 1;
    }
    array[maxSize- 1].next=0;
}

// Extract the allocated space
int mallocArr(LNode *array){
    int i=array[0].next;
    if(array[0].next){
        array[0].next=array[i].next;
    }
    return i;
}

// Create a static list
int initArr(LNode *array){
    reserveArr(array);
    int body=mallocArr(array);
    int tempBody=body;
    int length;
    cin>>length;
    for(int i=1; i<length+1; i++){int j=mallocArr(array);
        array[tempBody].next=j;
        int temp;
        cin>>temp;
        array[j].data=temp;
        tempBody=j;
    }
    array[tempBody].next=0;
    return body;
}

// Iterate over the input
void dispalyArr(LNode *array,int body){
    int tempBody=body+1;
    while(array[tempBody].next){
        cout<<array[tempBody].data<<"";
        tempBody=array[tempBody].next;
    }
    cout<<array[tempBody].data<<"";
}

int main(a){
    LNode array[maxSize];
    int body=initArr(array);
    dispalyArr(array,body);
    return 0;
}
Copy the code

Results:

4. Add data

// Insert data
void insertArr(LNode * array,int body,int add,char a){
    int tempBody=body;//tempBody is used to iterate over an array of structures
    // Find the position of the last node in the array
    for (int i=1; i<add; i++) {
        tempBody=array[tempBody].next;
    }
    int insert=mallocArr(array);// Request space, ready to insert
    array[insert].data=a;
    array[insert].next=array[tempBody].next;// The cursor of the newly inserted node is equal to the cursor of its immediate precursor
    array[tempBody].next=insert;// The cursor of the immediate precursor node is equal to the index in the array of the newly inserted node
}
Copy the code

Overall code:

#include <bits/stdc++.h>
using namespace std;
#define maxSize 100

typedef struct LNode{
    int data;
    int next;
}LNode;

// Create an alternate linked list
void reserveArr(LNode *array){
    for(int i=0; i<maxSize; i++){ array[i].next=i+1;
        array[i].data=- 1;
    }
    array[maxSize- 1].next=0;
}

// Extract the allocated space
int mallocArr(LNode *array){
    int i=array[0].next;
    if(array[0].next){
        array[0].next=array[i].next;
    }
    return i;
}

// Create a static list
int initArr(LNode *array){
    reserveArr(array);
    int body=mallocArr(array);
    int tempBody=body;
    int length;
    cin>>length;
    for(int i=1; i<length+1; i++){int j=mallocArr(array);
        array[tempBody].next=j;
        int temp;
        cin>>temp;
        array[j].data=temp;
        tempBody=j;
    }
    array[tempBody].next=0;
    return body;
}

// Insert data
void insertArr(LNode * array,int body,int add,char a){
    int tempBody=body;
    for (int i=1; i<add; i++) {
        tempBody=array[tempBody].next;
    }
    int insert=mallocArr(array);
    array[insert].data=a;
    array[insert].next=array[tempBody].next;
    array[tempBody].next=insert;
}

// Iterate over the input
void dispalyArr(LNode *array,int body){
    int tempBody=body+1;
    while(array[tempBody].next){
        cout<<array[tempBody].data<<"";
        tempBody=array[tempBody].next;
    }
    cout<<array[tempBody].data<<"";
}

int main(a){
    LNode array[maxSize];
    int body=initArr(array);
    dispalyArr(array,body);
    cout<<endl;
    insertArr(array,body,2.10);
    dispalyArr(array,body);
    return 0;
}
Copy the code

Results:

5. Delete the vm

// A function to reclaim space for the standby linked list, where array is the array storing data and k is the index of the array where the node is not used
void freeArr(LNode * array,int k){
    array[k].next=array[0].next;
    array[0].next=k;
}
// Delete node function. A represents the data stored in the data field of the node to be deleted
void deletArr(LNode * array,int body,char a){
    int tempBody=body;
    // Find the location of the deleted node
    while(array[tempBody].data! =a) { tempBody=array[tempBody].next;// When tempBody is 0, the list traversal ends, indicating that there is no node in the list to store the data
        if (tempBody==0) {
            printf("This data is not in the linked list");
            return; }}// Run this command to prove that the node exists
    int del=tempBody;
    tempBody=body;
    // Find the last node of this node and delete it
    while(array[tempBody].next! =del) { tempBody=array[tempBody].next; }// Add the cursor directly to the upper node of the deleted node
    array[tempBody].next=array[del].next;
    // Reclaim the space of the removed node
    freeArr(array, del);
}

// Insert data
void insertArr(LNode * array,int body,int add,char a){
    int tempBody=body;//tempBody is used to iterate over an array of structures
    // Find the position of the last node in the array
    for (int i=1; i<add; i++) {
        tempBody=array[tempBody].next;
    }
    int insert=mallocArr(array);// Request space, ready to insert
    array[insert].data=a;
    array[insert].next=array[tempBody].next;// The cursor of the newly inserted node is equal to the cursor of its immediate precursor
    array[tempBody].next=insert;// The cursor of the immediate precursor node is equal to the index in the array of the newly inserted node
}
Copy the code

// Total code

#include <bits/stdc++.h>
using namespace std;
#define maxSize 100

typedef struct LNode{
    int data;
    int next;
}LNode;

// Create an alternate linked list
void reserveArr(LNode *array){
    for(int i=0; i<maxSize; i++){ array[i].next=i+1;
        array[i].data=- 1;
    }
    array[maxSize- 1].next=0;
}

// Extract the allocated space
int mallocArr(LNode *array){
    int i=array[0].next;
    if(array[0].next){
        array[0].next=array[i].next;
    }
    return i;
}

// Create a static list
int initArr(LNode *array){
    reserveArr(array);
    int body=mallocArr(array);
    int tempBody=body;
    int length;
    cin>>length;
    for(int i=1; i<length+1; i++){int j=mallocArr(array);
        array[tempBody].next=j;
        int temp;
        cin>>temp;
        array[j].data=temp;
        tempBody=j;
    }
    array[tempBody].next=0;
    return body;
}

// A function to reclaim space for the standby linked list, where array is the array storing data and k is the index of the array where the node is not used
void freeArr(LNode * array,int k){
    array[k].next=array[0].next;
    array[0].next=k;
}
// Delete node function. A represents the data stored in the data field of the node to be deleted
void deletArr(LNode * array,int body,char a){
    int tempBody=body;
    // Find the location of the deleted node
    while(array[tempBody].data! =a) { tempBody=array[tempBody].next;// When tempBody is 0, the list traversal ends, indicating that there is no node in the list to store the data
        if (tempBody==0) {
            printf("This data is not in the linked list");
            return; }}// Run this command to prove that the node exists
    int del=tempBody;
    tempBody=body;
    // Find the last node of this node and delete it
    while(array[tempBody].next! =del) { tempBody=array[tempBody].next; }// Add the cursor directly to the upper node of the deleted node
    array[tempBody].next=array[del].next;
    // Reclaim the space of the removed node
    freeArr(array, del);
}

// Insert data
void insertArr(LNode * array,int body,int add,char a){
    int tempBody=body;//tempBody is used to iterate over an array of structures
    // Find the position of the last node in the array
    for (int i=1; i<add; i++) {
        tempBody=array[tempBody].next;
    }
    int insert=mallocArr(array);// Request space, ready to insert
    array[insert].data=a;
    array[insert].next=array[tempBody].next;// The cursor of the newly inserted node is equal to the cursor of its immediate precursor
    array[tempBody].next=insert;// The cursor of the immediate precursor node is equal to the index in the array of the newly inserted node
}

// Iterate over the input
void dispalyArr(LNode *array,int body){
    int tempBody=body+1;
    while(array[tempBody].next){
        cout<<array[tempBody].data<<"";
        tempBody=array[tempBody].next;
    }
    cout<<array[tempBody].data<<"";
}

int main(a){
    LNode array[maxSize];
    int body=initArr(array);
    dispalyArr(array,body);
    cout<<endl;
    insertArr(array,body,2.10);
    dispalyArr(array,body);
    cout<<endl;
    deletArr(array,body,10);
    dispalyArr(array,body);
    return 0;
}
Copy the code

6. Query data

// Insert data
void insertArr(LNode * array,int body,int add,char a){
    int tempBody=body;//tempBody is used to iterate over an array of structures
    // Find the position of the last node in the array
    for (int i=1; i<add; i++) {
        tempBody=array[tempBody].next;
    }
    int insert=mallocArr(array);// Request space, ready to insert
    array[insert].data=a;
    array[insert].next=array[tempBody].next;// The cursor of the newly inserted node is equal to the cursor of its immediate precursor
    array[tempBody].next=insert;// The cursor of the immediate precursor node is equal to the index in the array of the newly inserted node
}
Copy the code

Refer to the original blog: c.biancheng.net/view/3340.h…