preface
At the beginning of this article, we will start a new series, data structure, the importance of data structure in algorithm or programming is self-evident, so it is necessary to learn data structure. This paper mainly introduces the first structure of data structure – linear table, mainly divided into the following parts: 1. Concept 2. Storage structure
- Sequential storage
- Chain store
3. Compare the advantages and disadvantages of storage structures. 4
- Single linked list operation
- Double linked list operation
Note: This series will be written in C, so you need some basic knowledge of C to understand this series.
concept
A linear list is a finite sequence consisting of zero or more data elements with the same characteristics. The number of elements contained in the sequence is called the length of a linear list. A linear list has the following characteristics:
- The first is a sequence
- The second is finite
- It can be ordered or it can be unordered, and you can think of a linear list as a group of students, and you can have them go from small to large in order of height, or you can have them go into a random line
- The beginning element of a linear list has no precursor element and only its successor, and the end element of a linear list has no successor element and only its precursor element. In addition to the beginning element and the end element, each element has one and only one precursor element and only one successor element.
Storage structure
The storage structure of linear list has two kinds: sequential storage structure and chain storage structure. The former is called sequential list, and the latter is called linked list.
Sequential storage structure
Sequential table is to store all the elements in a linear table in a logical order to a contiguous storage space starting from a specified location.
The difference between the length of an array and the length of a linear table is as follows: The length of an array is the length of the storage space used to store a linear table. The length of a linear table is the number of data elements in a linear table. The length of a linear table changes with the insertion and deletion of a linear table.
Order table structure definition:
typedef struct
{
int data[maxsize]; // Create an array that holds data of type int
int lengeth; // Store the length of the order table
}
Copy the codeThere is also a more concise way to write, as follows:
int A[maxsize];
int n;
Copy the codeAdvantages and disadvantages of the sequential storage structure of linear tables
| advantages | disadvantages |
|---|---|
| No additional storage is required to represent logical relationships between elements in the table | Insert and delete operations require moving a large number of elements |
| You can quickly access elements anywhere in the table | Insert and delete operations require moving a large number of elements |
| When the length of linear table varies greatly, it is difficult to determine the capacity of storage space | |
| The storage space is fragmented |
Chain storage structure
The chain storage structure is designed to improve the disadvantage of the sequential storage structure. The biggest disadvantage of the sequential storage structure is that a large number of elements need to be moved when inserting and deleting an element, which is very time-consuming. Why will appear this kind of move and delete one element need to move a large number of elements, because the storage location is also with neighboring relationship between two elements, also next to their location in memory, no empty, cannot directly to insert, want to insert, need to move the other elements, in the same way, if you delete an element, It’s going to flow out of the gap, and it’s going to have to move other elements around. To sum up, the main problem with sequential storage is that adjacent elements are stored next to each other, in memory.
Sequential storage problems we already know that now, then you just need to targeted to solve, let elements don’t have to be adjacent, between the positions of location in memory also don’t have to close to the can, we call this kind of storage structure chain storage structure, the characteristics of the chain of the linear table storage structure is to use a set of arbitrary linear table storage unit to store the data elements, This set of storage units can be contiguous or discontiguous, which means that the data elements can reside anywhere that memory is not occupied. Another point is that in the sequential storage structure, each data space only needs to store the information of the data element, but in the chain structure, in addition to the information of the data element, it also needs to store the location of its successors. The domain storing data element information is called data domain, the domain storing direct successor location is called pointer domain, the information stored in pointer domain is called pointer or chain, and the storage image of data element composed of data domain and pointer domain is called node.
1. The singly linked list
N nodes are linked to form a linked list, which is the chain storage structure of a linear list. Because each node of the linked list contains only one pointer field, it is called a single linked list. A single linked list links the data elements of a linear list in their logical order through the pointer field of each node.
Some lists have headers and some do not. The data field of a header node can store no information, including additional information such as the length of a linear table. The pointer field of a header node stores a pointer to the first node. When a linked list has a head node, it is like a locomotive, only used to show the direction of the train sequence, not the passenger. (Linked lists usually contain headers.)
In the single linked list of the head node, the head pointer heads to the head node, the data field of the head node does not contain any information, and the subsequent nodes of the head node start to store data information. The head pointer is always not NULL, and when head->next is NULL, the linked list is empty.
If head is NULL (head->=NULL), the list is NULL.
The entire linked list must be accessed from the beginning of the pointer, and each node after that is the position of the subsequent pointer to the previous node. The pointer to the last node (terminal node) is NULL, usually represented by NULL or ^.
Single linked list node definition
typedef struct LNode
{
int data; //data stores the node data field
struct LNode *next; // A pointer to a successor node
}LNode; // Define a single linked list node type
Copy the code2. Static lists
The previous single list uses Pointers, but some programming languages do not have Pointers, so what? There were always smart people, people who came up with the idea of arrays instead of Pointers, describing singlelinked lists, where each array element was made up of two data fields, and each subscript of the array had two data fields, one for the data element and one for the next pointer. We call these arrays of linked lists static lists.
3. Circular linked lists
Changing the pointer end of the terminal node in a single linked list to point to the head node instead of the null pointer will make the whole single linked list form a ring. This kind of single linked list is called single circular linked list, or circular linked list for short.
4. Bidirectional linked lists
On the basis of single linked list, a pointer field pointing to its precursor node is set in each node, so that a node can point to its front and the next one, we call this kind of linked list bidirectional linked list.
Double linked list node definition
typedef struct DLLNode
{
int data; // Data to store node data field (default int, can also be other)
struct DLNode *prior; // A pointer to a precursor node
struct DLNode *next; // A pointer to a successor node
}DLNode; // Define double linked list node types
Copy the codeA node is a piece of storage space allocated by the user in memory. Only one address is used to indicate its existence, and there is no explicit name. Therefore, when allocating the linked list node space, we define a pointer to store the address of this space (this process is colloquially called pointer to a node). The name of the pointer is often used as the node name, such as the following:
LNode *A = (LNode*)malloc(sizeof(LNode)); // When the user assigns A sizeof LNode space, we define A pointer to this node and use A as its name.
Copy the codeSequential storage compared to chain storage
Because the storage address of the sequential table is continuous, we only need to know the location of the first element, so we can obtain any element in the sequential table by the offset of the starting position. We call this feature random access feature.
The data elements in a sequential table are stored in a contiguous space, and the storage space (i.e. storage location) must be allocated in advance. Once allocated, it is not changed during operation.
A sequential table moves a large number of elements when an element is inserted or deleted.
Because the storage structure of linked lists is that one element contains the location information of the next data element, and the next contains the next, that is, each data element is connected by a single line. To know where the last element is, you have to go from the beginning to the end. Therefore, linked lists do not support random access.
Each node in a linked list needs to allocate some space to store Pointers to the next node, so the storage space utilization of nodes in a linked list is lower than that of a sequential list.
Linked lists support dynamic storage space allocation.
When a linked list inserts and deletes an element, there is no need to move a large number of elements, just change the pointer pointing to the insertion position.
The operation of the table
Table operations can be divided into several types: search, insert and delete
Sequential table operations:
1. Search algorithm by element value,
int findElem (Sqlist L,int e)
{
int i;
for (i=0,i<L.length,++i) // iterate over each position in the L length
if(e == L.data[i]) // Get the corresponding value of each position and e value to judge, where equal can be greater than or less than
return i; // If a value equal to e is found, the position corresponding to that value is returned
return - 1; // If it cannot be found, -1 is returned
}
Copy the code2. Insert data element algorithm
Insert a new element e into the PTH (0< P <length) position of the sequence table L. If the input of P is incorrect, 0 is returned, indicating that the insertion failed. If the input of p is correct, the PTH element and subsequent elements in the sequence table will be moved one place to the right, leaving an empty place to insert a new element, and the length of the sequence table will be increased by 1. The insertion operation is successful, and 1 will be returned.
int insertElem(Sqlist &L,int p,int e) //L is the length of the order table, so use the reference type
{
int i
if (p<0 || p>L.length || L.length==maxsize) // If p is less than 0, or greater than L, or the length of L is equal to the maximum storage space of the order table
return 0;
for (i=L.length- 1; i>=p; --i)// Every position in L greater than p is iterated from the last element in L
L.data[i+1]=L.data[i]; // Assign the ith position to I +1
L.data[p]=e; // Insert the p position into e
++(L.length); // The length of L plus 1
return 1; // Successful insertion returns 1
}
Copy the code3. Delete the data element algorithm
Delete the element E in the PTH position of the sequence table. If the input of P is incorrect, 0 is returned, indicating that the deletion fails. If the input of p is correct, the elements following position P in the sequence table will be passed forward and the elements at position P will be overwritten.
int deleteElem (Sqlist &L,int p,int &e) // Use reference type for variables that need to be changed
{
int i;
if(p<0 || p>L.length- 1) // Check the position p, if the position is incorrect, return 0, indicating that the deletion failed
return 0;
e=L.data[p]; // Assign the value to be deleted to e
for(i=p; i<L.length- 1; ++i)// Start at position p and overwrite the elements after it one by one
L.data[i]=L.data[i+1];
--(L.length) // Subtract the length of the table by 1
return 1; // Delete successfully, return 1
}
Copy the codeSingle linked list operation
1. Merge operation of single linked list
A and B are two single linked lists, in which the elements are increasing in order. An algorithm is designed to merge A and B into A non-decreasing ordered linked list C, which is composed of A and B.
Analysis: given the increasing order of the elements in A and B, to make the elements in C still orderly after merging, the smallest element can be selected from A and B and inserted into the tail of C, so that when all elements in A and B are inserted into C, C must be increasing order.
void merge(LNode *A,LNode *B,LNode *&C)
{
LNode *p = A->next; // use pointer P to trace the next pointer to list A
LNode *p = B->next; // use pointer P to trace the next pointer to list B
Lnode *r; //r always points to the endpoint of C
C = A; // use A as A header for C
C-> = NULL; //
free(B);
r = C;
while(p! =NULL&&q! =NULL) // When p and q are not null, insert the smaller value of the node indicated by p and q into the tail of C
{
if(p->data<=q->data) // If the value of p is less than or equal to the value of q, then the node of P points to r, that is, C, and the next node of P points to P
{
r->next = p; p = p->next;
r=r->next;
}
else
{
r->next=q; q=q-next;
r=r->next;
}
}
r->next = NULL;
if(p! =NULL)r->next=p;
if(q! =NULL)r->next=q;
}
Copy the code2. Tail plug method of single linked list
Given that n elements are stored in array A, the linked list C is created by tail insertion
void createlistR(LNode *&C,int a[],int n) // Use the reference type for values that require constant change
{
LNode *s,*r; //s is used to refer to the newly requested node, and r always refers to the terminal node of C
int i;
C = (LNode * )malloc(sizeof(LNode)); // Request a header space
C -> next = NULL // Initialize an empty linked list
r = C; //r is a pointer to the header C, which is also the endpoint
for(i=0; i<n; ++i):
{
s = (LNode*)malloc(sizeof(LNode)); // apply for a new node
s -> data = a[i] // Assign the array element a[I] to the pointer s to the range of the node
// Now that we have the node range and pointer, we have a complete node. We want to insert this node into the list C
// Just point the header pointer to this node
r -> next = s; // the header pointer points to s
r = r -> next; // Update the current point of the r pointer
}
r -> next = NULL; // Until the terminal node is NULL, indicating successful insertion
}
Copy the code3. Head plug method of single linked list
The head insertion method and the tail insertion method are corresponding. The head insertion method starts from the head of the linked list and keeps the terminal node unchanged. Tail inserts start at the end of the list, leaving the head unchanged.
void createlistF(LNode *&C,int a[],int n) // Use the reference type for values that require constant change
{
LNode *s;
int i;
C = (LNode * )malloc(sizeof(LNode)); // apply for the node space of C
C -> next = NULL // This object is empty
for(i=0; i<n; ++i):
{
s = (LNode*)malloc(sizeof(LNode)); // apply for a new node
s -> data = a[i] // Assign the array element a[I] to the pointer s to the range of the node
// Now that we have the node range and pointer, we have a complete node. We want to insert this node into the list C
// Make the pointer to this node point to the start of list C
s -> next = C -> next; // s points to the beginning of the C pointer
C -> next = s; // Update the current point of the r pointer
}
}
Copy the codeDouble linked list operation
1. Use tail plug method to establish double linked list
void createFlistR(DLNode *&L,int a[],int n)
{
DLNode *s,*r;
int i;
L = (DLNode*)malloc(sizeof(DLNode)); // create a new node L
L -> prior = NULL;
L -> next = NULL;
r = L; // the r pointer points to the terminal of node L. The start head is also the end
for(i=0; i<n; ++i)
{ s = (DLNode*)malloc(sizeof(DLNode)); // Create a new node s
s -> data = a[i] // node s = a[I]
r -> next = s; // the successor of r pointer points to s
s ->prior = r; // the first node of s points to r
r = s; // Update the pointer to r
}
r -> next = NULL; // Until the r pointer is NULL
}
Copy the code2. Algorithm to find nodes
Returns a pointer to the node x in the doubly linked list, if found, or NULL otherwise.
DLNode* findNode(DLNode *C,int x)
{
DLNode *p = C -> next;
while(p ! =NULL)
{
if(p -> data == x)
break;
p = p -> next;
}
return p;
}
Copy the code3. Algorithm of node insertion
Insert a node S after the node referred to by P in the double-linked list. The core idea is to assign the pointing of P to S, that is, to make S refer to p. The former node of S is P, and the latter node of P is S.
s -> next = p -> next;
s -> prior = p;
p -> next = s;
s -> next -> prior = s;
Copy the code4. Algorithm for deleting nodes
To delete the successor node of p in the double-linked list, the core idea is to first give the successor node of P to Q, and then make P point to the successor node of Q, the predecessor node of Q is P, and then release Q, the specific code is as follows:
q = p -> next;
p -> = q -> next;
q -> next -> prior = p;
free(q);
Copy the code