Data structure (2) – 1000 words linear table

This is the 11th day of my participation in Gwen Challenge

The linear table

A linear table is a finite sequence of N data elements of the same data type, where n is the table length.

Initialize, find table length, find by value, find by bit, Insert, delete, output, void, destroy

A sequential representation of a linear table

The sequential storage of a linear table is also called a sequential table. It uses a group of storage units with consecutive addresses to store data elements in a linear table in sequence, so that logically adjacent elements are physically adjacent. Thus, the characteristic of a sequential table is that the logical order of the elements in the table is the same as their physical order

Suppose that the element type of the linear table is ElemType, the sequential storage type of the linear table is described as

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize]; // The elements of the sequence table
    int length;    // The current length of the sequence table
}SqList   // The type definition of the sequence table
Copy the code

Dynamic allocation

#define InitSize 100
typedef struct{
    ElemType *data; // A pointer to dynamically allocated arrays
    int MaxSize,length; // The maximum size and current number of arrays
}SeqList;
Copy the code

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
Copy the code

Dynamic allocation is not chain storage, it is also a sequential storage structure, the physical structure does not change, it is still random storage, but the size of the allocation can be determined at run time

The most important feature of sequential tables is random access, that is, the specified element can be found in O(1) by starting address and element ordinal number

Elements that are logically adjacent to a sequential table are also physically adjacent, so insert and delete operations require moving a large number of elements

Basic operation

• The insert

bool ListInsert(SqList &L,int i,ElemType e){
    // Insert element e into the ith position of the sequence table L
    if(i<1||i>L.length+1)return false;
    if(L.length>=MaxSize)return false;
    for(intj=L.length; j>=i; j--)L.data[j]=L.data[j- 1];
    L.data[i- 1]=e;
    L.length++;
    return true;
}
Copy the code

• • Best case O(1)
  • Worst case O(n)
  • The average O (n)
• Delete operation

bool ListDelete(SqList &L,int i,Elemtype &e){
    if(i<1||i>L.length) return false;
    e = L.data[i- 1];
    for(int j=1; j<L.length; j++)L.data[j- 1] = L.data[j];
    L.length--;
    return true;
}
Copy the code

• • Best case: drop the element at the end of the table (I =n) without moving the element, time complexity O(1)
  • Worst case O(n)
  • The average O (n)
• According to the value lookup
  • Best case O(1)
  • Worst case O(n)
  • The average O (n)

A chained representation of a linear list

Singly linked lists

typedef struct LNode{ // Define a single linked list node type
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
Copy the code

Singly linked list is a non-random access storage structure, that is, a specific node in the table cannot be found directly

• A NULL header pointer indicates an empty table
• For ease of operation, a header is usually set.
• The header data field can be set with no information or record information such as table length.

Introduce the advantages of headers

• Because the start node is placed in the pointer field of the head node, the operation at the first position in the list is the same as the operation at the rest of the table, with no special handling required
• No matter whether the linked list is empty or not, its head pointer points to the non-null pointer of the head node, so the treatment of empty and non-empty tables is unified.

Head plug method to build a single linked list

LinkList List_HeadInsert(LinkList &L){
    // create single-linked list L from the end of the table to the header, insert elements after the header each time
    LNode *s;int x;
    L = (LinkList)malloc(sizeof(LNode)); // Create a header
    L->next = NULL; // Start with an empty list
    scanf("%d",&x); // Enter the value of the node
    while(x! =9999) {// Enter 9999 to indicate the end
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x); 
    }
    return L;
}
Copy the code

Tail plug method to build a single – linked list

We need to set a tail r

LinkList List_TailInsert(LinkList &L){
    Create table L from head to tail, insert elements into tail
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;//r is the end pointer of the table
    scanf("%d",&x); 
    while(x! =9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
    	r->next = s;
        r = s;
        scanf("%d",&x); 
    }
    r->next = NULL;
    return L;
}
Copy the code

Find node values by ordinal number

LNode *GetElem(LinkList L,int i){
    // This algorithm takes the node pointer at the ith position in the single linked list L (head node)
    int j = 1;
    LNode *p = L->next;
    if(i==0)return L;
    if(i<1)return Null;
    while(p&&j<i){
        p = p->next;
        j++
    }
    return p;
}
Copy the code

Find table nodes by value

LNode *LocationElem(LinkList L,ElemType e){
    // This algorithm looks for Pointers to nodes in L whose data field value is equal to e, otherwise returns NULL
    LNode *p = L->next;
    while(p! =NULL&&p->data! =e) p = p->nextreturn p;
}
Copy the code

Insert node operation

p = GetElem(L,i-1);
s->next = p->next;
p->next = s;
Copy the code

Delete node operation

p = GetElem(L,i- 1);
q = p->next;
p->next = q->next;
free(q);
Copy the code

Double linked list

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

Insert operation of double linked list

s->next = p->next;
p->next->prior = s;
s->prior = p;
p -> next = s;
Copy the code

Double linked list delete operation

p->next = q->next;
q->next->prior = p;
free(q);
Copy the code

Circular linked list

The pointer to the last node of the circular list points to the head node, so that the entire list forms a loop

Circular double-linked lists

When a circular double-linked list is empty, the prior and next fields of its head nodes are equal to L

A static linked list

#define MaxSize 50
typedef struct{
    ElemType data;
    int next; 
}SLinkList[MaxSize];
Copy the code

Comparison of sequential and chained lists