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);
}