1, What is a linear table

A linear table is a finite sequence of n data elements with the same data type

• Same data type: each data element occupies the same space
• Sequence: ordered

Tip: reference "&" in the parameters passed in by C + + program functions -- > the modification results of parameters need to be "brought back", for ex amp le:

void test1(int x) {
    x = 1024;
}

void test2(int & x) {
    x = 1024;
}

int main() {
    int x = 1;
    test1(x);  //x=1
    test2(x);  //x=1024
}

2, Sequence table

1. Definition of sequence table: the linear table is realized by sequential storage, which is logically adjacent and physically adjacent

Small knowledge of C language: get the size of data element sizeof(ElemType)

eg:sizeof(int) = 4B

2. Implementation of sequence table - static allocation

#define MaxSize 10 / / define the maximum length
typedef struct{
    ElemType data[MaxSize];      //Use static "array to store data elements"
    int length;                  //Current length of sequence table
}SqList;                         //Type definition of sequence table

The above code storage space is static, and the size and capacity of the sequence table cannot be changed

3. Implementation of sequence table - dynamic allocation

#define InitSize 10 / / the initial length of the sequence table
typedef struct{
    ElemType *data;             //Pointer indicating dynamically allocated array
    int MaxSize;                //Maximum capacity of sequence table
    int length;                 //Type definition of sequence table (dynamic allocation method)
} SeqList;

                  

Specific implementation:

#include <stdlib.h>
#define InitSize 10 / / the default maximum length

typedef struct{
    int *data;               //Pointer indicating dynamically allocated array
    int MaxSize;             //Maximum capacity of sequence table
    int length;              //Current length of sequence table
} SeqList;

void InitList(SeqList &L) {
    //Using malloc function to dynamically apply for a continuous storage space
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

//Increase the length of dynamic array
void IncreaseSize(SeqList &L, int len){
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0; i<L.length; i++){
        L.data[i]=p[i];
    }
    L.MaxSize = L.MaxSize+len;
    free(p);
}

4. Characteristics of sequence table

• Random access: the ith element can be found in the time of O(1)
• High storage density
• Inconvenient to expand capacity
• It is inconvenient to insert and delete data elements

5. Bit by bit search of sequence table

ElemType GetElem(SeqList L, int i){
    return L.data[i-1];
}

Time complexity: 1

6. Search by value of sequence table

typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;

int LocateElem(SeqList L,int e){
    for(int i=0; i<L.length; i++){
        if(L.data[i]==e)
            return i+1;
    }
    return 0;
}

Time complexity:

① Best case: the target element is in the header, O(1)

② Worst case: the target element is at the end of the table, O(n)

③ Average case: suppose that the probability of the target element appearing at any position is the same, which is 1 / N, and the average number of cycles = 1 * (1 / N) + 2 * (1 / N) ++ n*(1/n)=(n+1)/2，O(n)

3, Single linked list

1. Each node of the single linked list handles and stores data elements, and also stores pointers to the next node

//typedef is used to rename data types
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

tip: use LinkList to emphasize that it is a single linked list; Using LNode, emphasize that this is a node

2. Single linked list without leading node

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

//Initialize an empty single linked list
bool InitList(LinkList &L) {
    L = NULL;         //Empty table. There is no node yet to prevent dirty data
    return true;
}

void test() {
    LinkList L;       //Declare a pointer to a single linked list
    //Initialize an empty table
    InitList(L);
    //Subsequent code
}

3. Single linked list of leading nodes

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

//Initialize an empty single linked list
bool InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));     //Assign a header node
    if (L==NULL)                //Insufficient memory, allocation failed
        return false;
    L->next = NULL;             //There is no node after the head node
    return true;
}

void test() {
    LinkList L;       //Declare a pointer to a single linked list
    //Initialize an empty table
    InitList(L);
    //Subsequent code
}

4. Insert in bit order (leading node)

The head node can be regarded as the 0th node

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

//Insert element e (leading node) at position i
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1) return false;
    LNode *p;       //Pointer p points to the currently scanned node
    int j=0;        //Which node does the current p point to
    p = L;          //L points to the head node, which is the 0th node (no data stored)
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;    //Illegal i value
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

Average time complexity: O(n)

5. Post insert operation of specified node

//Post insert operation: insert element e after node p
bool InsertNextNode(LNode *p, ElemType 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;
    return true;
}

6. Pre insert operation of specified node

//Pre insert operation: insert element e before node p
//Idea: insert element e after node p and exchange the values of e and p
bool InsertPriorNode(LNode *p, ElemType 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;
    s->data = p->data;
    p->data = e;
    return true;
}

7. Delete in bit order (leading node)

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

//Delete element e (leading node) at position i
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1) return false;
    LNode *p;       //Pointer p points to the currently scanned node
    int j=0;        //Which node does the current p point to
    p = L;          //L points to the head node, which is the 0th node (no data stored)
    while (p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;    //Illegal i value
    if(p->next==NULL) return false;    //There are no other nodes after the i-1 node
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q)
    return true;
}

Time complexity: O(n)

8. Delete the specified node

//Delete specified node p
bool DeleteNode(LNode *p){
    if(p==NULL) return false;
    p->data = p->next->data;
    LNode q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

9. Bit by bit search of single linked list

//Search by bit and return the ith element (leading node)
LNode * GetElem(LinkList L, int i){
    if(i<0) return NULL;
    int j = 0;
    LNode *p;
    p = L;
    while(p!=NULL&&j<i){
        p = p->next;
        j++;
    }
    return p;
}

10. Establishment of single linked list (tail interpolation method)

LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;                //r points to the new tail node
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

11. Establishment of single linked list (header insertion method)

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    L=(LinkList) malloc(sizeof(LNode));    //Create header node
    L->next = NULL;
    int x;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); 
    }
    return L;
}

Application: reverse single linked list

4, Double linked list

1. Initialization of double linked list (leading node)

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//init list 
bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL) return false;     //Out of memory. allocation failed
    L->prior = NULL;
    L->next = NULL;
    return true;
}

2. Insertion of double linked list

//Insert s node after p node
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL) return false;
    s->next = p->next;
    if(p->next!=NULL){
        p->next->prior = s;
    }
    s->prior=p;
    p->next=s;
    return true;
}

5, Circular linked list

1. Initialize the circular single linked list

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

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if(L==NULL) return false;
    L->next = L;            //The header node next points to the header node
    return true;
}

2. Initialize the circular double linked list

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

bool InitList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if(L==NULL) return false;
    L->prior=L;
    L->next = L;            //The header node next points to the header node
    return true;
}

6, Static linked list

1. Comparison between static linked list and single linked list

Single linked list: each node is stored discontinuously in memory

Static linked list: allocate a whole piece of continuous memory space and place each node centrally

2. Create a static linked list

#define MaxSize 10
struct Node{
    ElemType data;
    int next;
};

void testSLinkList() {
    struct Node a[MaxSize];
}

3. Static linked list insert element

Steps:

① Find an empty node and store it in the data element;

② Starting from the ab initio node, find the node with bit order i-1;

③ Modify the next of the new node;

④ Modify the next of node i-1.

7, Comparison between linear list and linked list

 

	advantage	shortcoming	establish	Destroy	Addition and deletion	lookup
Sequence table	Support random access and high storage density	It is inconvenient to allocate large continuous space and change capacity	Large contiguous spaces need to be pre allocated. The allocation is too small to expand the capacity; Excessive allocation, waste of memory resources	Static allocation: static array (the system reclaims space automatically) Dynamic allocation: dynamic array (malloc,free)	Adding / deleting elements requires moving subsequent elements backward / forward (the time complexity is O(n), and the time cost is mainly moving elements)	Search by bit: O(1) If you can find the value in the order of time (n) in the table: logo, you can find it in the order of time (n)
Linked list	Discrete small space is easy to allocate and change capacity	Non random access, low storage density	You only need to allocate a header node (or you can declare only a header pointer without a header node), and then it is convenient to expand	Delete each node in turn (free)	Adding / deleting elements only needs to modify the pointer (the time complexity is O(n), and the time cost is mainly to find the target element. In contrast, the linked list is more efficient, because if the data element is large, the time cost of moving the sequential table is higher)	Search by bit: O(n) Find by value: O(n)