Linear table
Sequential list and linked list
Abstract data structure - data combination and operation set
Header node: the first node that does not store data elements
First element node: the first node where data elements are stored
1, Definition of linear table
A finite sequence of zero or more data elements
There is order between elements. If there are multiple elements, the first element has no precursor and the last element has no successor. Every other element has and has only one precursor and one successor.
In a more complex linear table, a data element can be composed of several data items
2, Sequential storage structure of linear table
A storage unit with continuous addresses is used to store the data elements of the linear table in turn - physical address continuity
1. Generally, one-dimensional array is used to realize the sequential storage structure
//Maximum storage capacity
#define MAXSIZE 20
typedef struct Array
{
int data[MAXSIZE];//An array stores data elements (or pointers) int* element
int length;//Current length of linear table
int Size;//Maximum capacity of linear meter
}Array;
2. Three attributes are required to describe the sequential storage structure
Starting position of storage space: the storage position of array data is the storage position of storage space
Maximum storage capacity of linear table: array length MAXSIZE
Current length of linear table: length
Each storage unit in the memory has its own number, which is the address
3. Initialize linear table
//initialization
Array init_array()
{
//Define an abstract data type
Array array;
array.length = 0;
array.Size = MAXSIZE;
return array;
}4. Find elements
//Find element - returns the subscript of the element (you can also find according to the subscript and return the element value)
int find_ArrayElement(int find_key, Array* array)
{
if (array->length == 0)
{
printf("Lookup error: the table is empty!\n");
return -1;
}
for (int i = 0; i < array->length; i++)
{
if (array->data[i] == find_key)
{
return i;
}
}
//Element not found
return -1;
}
//Find by subscript
void find_ArrayIndex(int index,Array* array)
{
//Judge whether the subscript is reasonable
if(index<0||index>=array->length)
{
printf("Search error: subscript error!\n");
return;
}
return array->data[index];
}5. Insertion operation
Idea:
1. The insertion position is unreasonable and an exception is thrown
2. If the length of the linear table is greater than or equal to the length of the array, throw an exception or dynamically increase the capacity of the array
3. Traverse forward from the last element to the position to be inserted, and move them back one position respectively
4. Insert element, linear table length + 1
//Insert in two ways
1.
//Insert element - sequential insert
void insert_ArrayTail(int key, Array* array)
{
//The array still has capacity to insert
if (array->length < array->Size)
{
array->data[array->length] = key;
array->length++;
}
else
{
printf("Insert error: insufficient array capacity!\n");
}
}
2.
//Insert element - middle position insert
void insert_ArrayIndex(int key, int index, Array* array)
{
//Determine whether the insertion position is correct
if (index<0 || index>array->length)
{
printf("Insert error: insert position error!\n");
return;
}
//Record the current array pointing position
int pos = array->length;
//The array still has capacity
if (array->length < array->Size)
{
while (index<pos)
{
//Move backward one bit in turn
array->data[pos] = array->data[pos - 1];
pos--;
}
//Insert element
array->data[index] = key;
//Array length + 1
array->length++;
}
else
{
printf("Insert error: insufficient array capacity!\n");
}
}6. Delete
Idea:
1. If the deletion position is unreasonable, an exception will be thrown
2. Traverse from the deletion position to the last element position and move them forward one position respectively
3. Table length-1
//Two ways
1.
//Delete element - delete according to the element
void delete_ArrayElement(int delete_key, Array* array)
{
//Find the element subscript first
int delete_index = find_Array(delete_key,array);
//Judge whether the subscript is correct
if (delete_index == -1)
{
printf("Delete error: this element is not in the array!\n");
return;
}
//Move the elements forward in turn to overwrite the elements to be deleted
while (delete_index < array->length)
{
//Element forward overlay
array->data[delete_index] = array->data[delete_index + 1];
delete_index++;
}
//Array element - 1
array->length--;
}
2.
//Delete element - delete by subscript
void delete_ArrayIndex(int index, Array* array)
{
//Judge whether the subscript is reasonable
if (index<0 || index>=array->length)
{
printf("Error deleting subscript!\n");
return;
}
//Move the elements forward in turn to overwrite the elements to be deleted
while (index < array->length)
{
//Element forward overlay
array->data[index] = array->data[index + 1];
index++;
}
//Array element - 1
array->length--;
}7. Modification operation
//Two ways
1.
//Change element - change according to subscript
void change_ArrayIndex(int change_key,int index, Array* array)
{
//Judge whether the subscript is reasonable
if (index < 0 || index >= array->length)
{
printf("Change error: subscript error!\n");
return;
}
array->data[index] = change_key;
}
2.
//Change element - change according to the element
void change_ArrayElement(int key, int change_key, Array* array)
{
//Find the element subscript first
int change_pos = find_Array(key, array);
//Judge whether the subscript is correct
if (change_pos == -1)
{
printf("Change error: this element is not in the array!\n");
return;
}
array->data[change_pos] = change_key;
}8. Advantages and disadvantages
The sequential storage structure of linear table. When reading data (looking for elements - returning element values according to subscripts or changing elements), the time complexity is O(1), while when inserting and deleting, the time complexity is O(n).
Therefore, the sequential storage structure of linear table does not change much compared with the number of elements, but is more used to access data
advantage:
1. There is no need to add additional storage space to represent the logical relationship between elements
2. You can quickly access elements in any position in the table
Disadvantages:
1. Insert and delete operations require moving a large number of elements - time consuming
2. When the length of linear table changes greatly, it is difficult to determine the capacity of storage space
3. "Debris" causing storage space
3, Linked storage structure of linear list (single linked list)
1. Definitions
1. Features: use a group of arbitrary storage units to store the data elements of the linear table. This group of storage units can be continuous or discontinuous. Therefore, these data elements can exist in any location where memory is not occupied
In the chain structure, the storage address of its subsequent elements needs to be stored
2. The domain in which data element information is stored is called data field
3. The field storing the direct successor position is called pointer field
4. These two parts constitute the depositor image of the data element List, which is called the node
5.n nodes are linked into a linked list, which is the linked storage structure of linear list. Each node contains only one pointer field, so it is called single linked list
6. Initial node: the first node of the single linked list
7. Header pointer: the storage location of the first node of the linked list
8. Head node: a node attached before the first element node
2. Similarities and differences between head pointer and head node
Header pointer:
1. Pointer to the first node of the linked list. If the linked list has a head node, it refers to the pointer to the head node
2. The head pointer has the function of marking, so the head pointer is often labeled with the name of Lina watch
3. Whether the linked list is empty or not, the header pointer is not empty. The head pointer is a necessary element of the linked list (only through the head pointer can we find the subsequent nodes)
Header node:
1. It is set up for the unity and convenience of linked list operation. Before the first element, its data field is generally meaningless
2. With the header node, the operation of inserting and deleting the first element node before the first element node is unified with that of other nodes
3. The head node is not necessarily a necessary element of the linked list
3. Creation, addition, deletion, modification and query of single linked list
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//Define linked list nodes
typedef struct NodeList
{
int element;//Data domain
struct NodeList* pNext;//Pointer field
}Node;
//Initialize header node
Node* init_head();
//Insert element - value of random n elements - header interpolation
void allinit_List_head(int n, Node* node);
// Insert element - value of random n elements - tail interpolation
void allinit_List_tail(int n, Node* node);
//Insert element header method
void insert_ListHead(int key,Node* node);
//Insert element tail method
void insert_ListTail(int key, Node* node);
//Insert element - middle insert
void insert_ListIndex(int key,int index, Node* node);
//Delete element - delete according to the element
void delete_ListElement(int delete_key,Node* node);
//Delete element - delete according to the position of the element
void delete_ListIndex(int index, Node* node);
//Delete element - entire table delete
void delete_List(Node* node);
//Change element - change according to position
void change_List(int change_key, int index, Node* node);
//Find element - return the element position (define the initial node position as 1) (you can also return the node pointer)
int find_List(int find_key ,Node* node);
//Print linked list
void print(Node* node);
int main()
{
//initialization
Node* mylist = init_head();
//Head insert
insert_ListHead(2, mylist);
//Tail insertion
insert_ListTail(4, mylist);
insert_ListHead(1, mylist);
//Middle insertion
insert_ListIndex(3, 3, mylist);
//Whole table insert
//allinit_List_head(0, mylist);
delete_List(mylist);
print(mylist);
return 0;
}
//Initialize header node
Node* init_head()
{
//Define a header node
Node* head = (Node*)malloc(sizeof(Node));
//Determine whether the initialization is successful
if (head)//success
{
//Give a pointer to the pointer field in the header node
head->pNext = NULL;
//Indicates the number of linked list elements
head->element = 0;
}
else//fail
{
printf("Failed to allocate memory!");
exit(0);
}
return head;
}
//Insert element - the value of n random elements
void allinit_List_head(int n, Node* node)
{
if (n < 1)
{
printf("Insert error: the number of elements cannot be less than 1!\n");
return;
}
//Generate random number seed
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++)
{
//Initialize new node
Node* temp = (Node*)malloc(sizeof(Node));
//Assign a value to the data in the data field
temp->element = rand() % 100 + 1;
//Let this new node become the initial node
temp->pNext = node->pNext;
node->pNext = temp;
//Linked list element + 1
node->element++;
}
}
// Insert element - value of random n elements - tail interpolation
void allinit_List_tail(int n, Node* node)
{
if (n < 1)
{
printf("Insertion error: cannot be less than 1!\n");
return;
}
//Generate random number seed
srand((unsigned int)time(NULL));
//Temporary pointer, used to traverse the linked list
Node* pcurrent = node;
//Traverse the linked list to the last node
while (pcurrent->pNext)
{
pcurrent = pcurrent->pNext;
}
//Insert
for (int i = 0; i < n; i++)
{
//Initialize new node
Node* temp = (Node*)malloc(sizeof(Node));
//Assign a value to the data in the data field
temp->element = rand() % 100 + 1;
//Let this new node become the last node
pcurrent->pNext = temp;
temp->pNext = NULL;
//Move temporary pointer
pcurrent = temp;
//Linked list element + 1
node->element++;
}
}
//Insert element header method
void insert_ListHead(int key, Node* node)
{
//Define a node to be inserted
Node* temp = (Node*)malloc(sizeof(Node));
//Insert element
temp->element = key;
//List head point
temp->pNext = node->pNext;
//The header node points to temp
node->pNext = temp;
//Number of linked list elements plus 1
node->element++;
}
//Insert element tail method
void insert_ListTail(int key, Node* node)
{
//Create node to be inserted
Node* temp = (Node*)malloc(sizeof(Node));
//Insert element
temp->element = key;
//Temporary pointer, used to traverse the linked list and find the insertion position (you can also define a tail node)
Node* pcurrent = node;
//Traversal linked list
while (pcurrent->pNext)
{
pcurrent = pcurrent->pNext;
}
//At this time, pccurrent is the last node
//Make it point to the node to be inserted
pcurrent->pNext = temp;
//Make temp the last node
temp->pNext = NULL;
//Number of linked list elements plus 1
node->element++;
}
//Middle position insertion
void insert_ListIndex(int key,int index, Node* node)
{
//Determine whether the insertion position is correct
if (index<1 || index>node->element)
{
printf("Insert error: insert position error!\n");
return;
}
//Define a node to be inserted
Node* temp = (Node*)malloc(sizeof(Node));
temp->element = key;
//Record node location
int pos = 1;
//Find the location to insert
//Temporary pointer, used to traverse the linked list
Node* pcurrent = node;
//Traversal linked list
while (pcurrent->pNext)
{
//Find the subscript and insert it
if (index == pos)
{
//Make the node to be inserted point to the original node
temp->pNext = pcurrent->pNext;
pcurrent->pNext = temp;
//Linked list element + 1
node->element++;
return;
}
//Subscript not found
pcurrent = pcurrent->pNext;
pos++;
}
}
//Delete element - delete according to the element
void delete_ListElement(int delete_key, Node* node)
{
//The position of the element to be deleted first
int delete_pos = find_List(delete_key, node);
if (delete_pos == -1)
{
printf("Delete error: there is no such element!\n");
return;
}
//Record the previous position of the element to be deleted
int front_pos = 0;
//Temporary pointer, used to traverse the linked list
Node* pcurret = node;
//Traversal linked list
while (pcurret->pNext)
{
//Find node location
if (front_pos == delete_pos - 1)
{
//Find the deleted node
Node* free_node = pcurret->pNext;
pcurret->pNext = pcurret->pNext->pNext;
//Release deleted nodes
free(free_node);
//Linked list element-1
node->element--;
return;
}
//not found
pcurret = pcurret->pNext;
front_pos++;
}
}
//Delete element - delete according to the position of the element
void delete_ListIndex(int index, Node* node)
{
//Determine whether the element position is correct
if (index<1 || index>node->element)
{
printf("Delete error: delete element position error!\n");
return;
}
//Record the previous position of the element to be deleted
int front_pos = 0;
//Temporary pointer, used to traverse the linked list
Node* pcurret = node;
//Traversal linked list
while (pcurret->pNext)
{
//Find node location
if (front_pos == index - 1)
{
//Find the deleted node
Node* free_node = pcurret->pNext;
pcurret->pNext = pcurret->pNext->pNext;
//Release deleted nodes
free(free_node);
//Linked list element-1
node->element--;
return;
}
//not found
pcurret = pcurret->pNext;
front_pos++;
}
}
//Delete element - entire table delete
void delete_List(Node* node)
{
//Define two temporary pointers. Pccurrent is used to move the pointer position, free_node is used to delete nodes
Node* pcurrent = node->pNext;
Node* free_node;
while (pcurrent)
{
free_node = pcurrent;
pcurrent = pcurrent->pNext;
free(free_node);
//The header pointer will not be deleted, element - 1
node->element--;
}
//The header node pointer field is null
node->pNext = NULL;
}
//Change element - change according to position
void change_List(int change_key, int index, Node* node)
{
//Determine whether the position to be changed is correct
if (index<1 || index>node->element)
{
printf("Change error: wrong position!\n");
return;
}
//Record element location
int change_pos = 1;
//Temporary pointer, used to traverse the linked list
Node* pcurrent = node;
//Traversal linked list
while (pcurrent->pNext)
{
//Find the position of the element to be changed
if (change_pos == index)
{
pcurrent->pNext->element = change_key;
return;
}
//not found
pcurrent = pcurrent->pNext;
change_pos++;
}
}
//Find element - return the element position (define the initial node position as 1) (you can also return the node pointer)
int find_List(int find_key,Node* node)
{
//Temporary pointer, used to traverse the linked list
Node* pcurrent = node->pNext;
//Represents the position of the element
int pos = 1;
//Traverse the linked list to find
while (pcurrent)
{
if (pcurrent->element == find_key)
{
return pos;
}
pcurrent = pcurrent->pNext;
//Move element position backward
pos++;
}
return -1;
}
//Print linked list
void print(Node* node)
{
//Temporary pointer, used to traverse the linked list
Node* pcurrent = node;
//Record element location
int pos = 1;
//Number of linked list elements
printf("altogether %d Elements!\n", node->element);
//Traverse the linked list and print
while (pcurrent->pNext)
{
printf("The first %d The first element is:%d\n", pos, pcurrent->pNext->element);
pcurrent = pcurrent->pNext;
pos++;
}
}
4, Selection of linear table
1. If the linear table needs frequent search and few insert and delete operations, the sequential storage structure should be adopted
2. If you need to insert and delete frequently, you should use the single linked list structure
3. When the number of elements in the linear table changes greatly or you don't know how big it is, it's best to use the single linked list structure. In this way, there is no need to consider the size of storage space
4. The sequential storage structure and chain storage structure of linear table have their own advantages and disadvantages. When using, the structure that can meet the requirements and has higher performance should be selected according to the actual situation
For example:
In game development, the user's personal information, in addition to inserting data during registration, is more often read data, and the sequential storage structure can be considered
For the player's weapon and equipment list, equipment will often be added or discarded. At this time, chain storage structure can be considered. However, this is only a simple metaphor, and the problems considered in reality will be more complex
5, Other chained storage structures
1. Static linked list: it is a method designed for high-level language without pointer to realize the ability of single linked list
2. Circular linked list: change the pointer field of the last node in the single linked list from null pointer to head node, so that the whole single linked list forms a closed loop
Solved: starting from a certain node, access to all nodes of the linked list
3. Bidirectional linked list: in the pointer field of each node of the single linked list, another pointer field pointing to its predecessor node is set (space for time)
0