Linear table of data structure C/C + + implementation

Note: C is basically used, except that C + + uses references&

Sequence table

1, The pointer can be declared as long, but it also needs to be implemented as long.

#define MaxSize 50
typedef struct{
    ELemType data[MaxSize];
    int len;
}SqList;

2, Definition of operation

A data structure has many operations, but it's too difficult to remember all of them, and it's a little noisy, so in fact, you only need to remember the key operations

The core operations of a data structure generally include: creation and sales, addition, deletion, modification and query, and structural characteristics.

It's basically easy to create sales, but change and check are actually checks (change = check + assignment), so we only care about addition, deletion, check and structural characteristics

Linear tables only need to care about addition and deletion

1) Add:

First move the data after bit i backward and leave one bit blank. Pay attention to the length of the array plus 1

Legitimacy:

1. The position of inserting i can only be the first bit to len+1 bit of (logical value)
2. Whether the storage space is full, that is, whether the length of the array is exceeded after inserting x

  • The main thing is to pay attention to how to move backward. Logically, that is, I am now in position j-1, so I should be in position j after moving backward
  • Subscript problem: l.data [j] = l.data [j], not l.data [j + 1] = l.data [j], because j is a logical value, which needs to be reduced by 1 when converted to subscript value
  • Termination condition: in terms of programming habits, i prefer to use >, < instead of =, so that the sub termination condition J > i - 1 actually executes to i
bool ListInsert(SqList &L, int i, ElemType e){
}
for(int j = L.len; j > i - 1; j--){
    L.data[j] = L.data[j-1];
}
L.data[i-1] = x;
L.len++;
return true;
/*
* Legitimacy: 1. The position of inserting i can only be the first to len+1 (logical value)
* 2´╝îWhether the storage space is full, that is, whether the length of the array is exceeded after inserting x
*/
if (i < 1 || i > len+1)
    return false;
if (len == MaxSize)
    return false;

2) Delete

First take out the i-th bit, and then move the following forward. Note that the length of the array is reduced by one

Legitimacy:

1. The position of inserting i can only be from the first bit to the len bit (logical value). Note that this is the len bit, not the len+1 bit

  • Similarly, focus on how to move forward
bool ListDelete(Sqlist &L, int i, ELemtype &e){
}
e = L.data[i-1];
for(int j = i; i < L.len; j++){
    L.data[j-1] = L.data[j];
}
L.len--;
return true;
/*
* Legitimacy: 1. The position of inserting i can only be the first to len (logical value)
*/
if (i < 1 || i > len)
    return false;

3) Create, sell, change, check

You only need to define an array, and you don't need a pin. Or sometimes, if malloc is used to generate a sequence table, free is required to destroy the table

Change to query + assignment

Search: there are search by value and search by bit. Search by value is a bit by bit comparison, and search by bit is a direct subscript search

Single linked list

1, Type declaration

All nodes take the lead. The linked list without the leading node will make the first data node have no pointer. Special processing is required during insertion and deletion

Moreover, the head node makes the linked list empty and distinguishes it from the non existence of the linked list

Why use the * LinkList alias? Next, we're going to use LNode * to represent the node pointer and LinkList to represent the whole single linked list

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

2, Operation of data

The focus is still on adding and deleting

Head insertion and tail insertion are created on the surface, but their operation is actually a combination of addition and deletion and pointer movement

Destruction is also worth mentioning, because the one-way retrieval feature of the single linked list makes deletion lose my current location, and we must "remember the current location".

1) Add: mainly front insertion and back insertion. Backward interpolation is more important than forward interpolation, and forward interpolation depends on backward interpolation

i, post insertion: the subsequent node q that already has the pointer p and p is required to be inserted after p. Note "connect first and then disconnect"

s -> next = q;
p -> next = s;

ii. Forward insertion: the subsequent node q that already has pointers p and p is required to be inserted before p. A little trick is to insert s after p, and then swap the data of p and s

s -> next = q;
p -> next = s;

tmp.data = s.data;
s.data = p.data;
p.data = tmp.data;

2) Delete: in fact, it is to move the previous next pointer one bit later

//Memory release is not considered
p ->next = p -> next -> next

3) Header insertion and tail insertion: mainly remember that each node must allocate memory

void CreateListF(LinkList L, ElemType a[], int n){
    LNode *s;
    L = (ElemType*)malloc(sizeof(ElemType));
    L -> next = NULL;
    for (int i = 0, i < n, i++){
        s = (ElemType*)malloc(sizeof(ElemType));
        s -> data = a[i]; 
        s -> next = L->next;
        L -> next = s;
    }
}
void CreateListB(LinkList L, ElemType a[], int n){
    LNode *s,*p;
    L = (ElemType*)malloc(sizeof(ElemType));
    L ->next = NULL;
    
    p = L; //This is different from the head plug
    
    for (int i = 0, i < n, i++){
        s = (ElemType*)malloc(sizeof(ElemType));
        s ->data = a[i];
        
        //The following is different from the head plug
        s -> next = p ->next;//It's best not to omit this sentence, because the next of S is undefined
        p -> next = s;
        p = s;
    }
}

4) Destroy: mainly remember to create a pointer to remember the current position, and note that the termination condition is p= NULL. In fact, when p equals NULL, pre is the previous bit of P, and pre is not empty, so pay attention to releasing pre

bool ListDelete(LinkList *L, ElemType &e){
    ElemType *pre, p;
    pre = L;
    p = L -> next;
    while(p != NULL){
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);
}

Double linked list: overcome the defect that single linked list can only be retrieved in one direction

Circular linked list: because the operation of the linked list is mostly carried out at the head and tail, the circular linked list is convenient to find the head and tail

Static linked list: in fact, it is an array composed of structures. It is mainly applicable to the situation that pointers cannot be used

Keywords: C++ data structure

Added by sublimenal on Mon, 07 Mar 2022 14:03:28 +0200