In the previous article, we talked about the static sequence table of data structure and the implementation of static sequence table. For details, see my previous article - > > > Static sequence table of data structure.
We can know that the disadvantage of static sequence table is that because it uses fixed length array, it will waste space if there is less space and more space
Therefore, we introduce a new sequence table - dynamic sequence table
catalogue
I What is a dynamic sequence table
What are logical and physical structures
II Advantages and disadvantages of dynamic sequence table
4. Sequence table capacity increase
13. Number of elements in the sequence table
14. Destruction sequence table
Attachment: original code link
I What is a dynamic sequence table?
Dynamic sequence table: use the dynamically developed array storage, and use the pointer to point to the dynamically developed array to expand the capacity. You can add, delete, query and modify the contents of the array.
By the way, what are logical structure and physical structure
- Logical structure: it is artificially imagined but does not actually exist
- Physical structure: it actually exists and can be observed
II Advantages and disadvantages of dynamic sequence table
Advantages: continuous space, support random access.
Disadvantages: 1 The insertion time complexity of the middle or front part is O(N),
2. The cost of capacity increase is relatively high
III Create project
| Engineering documents | Contents stored |
|---|---|
| SeqList.h | Function declaration, macro definition |
| SeqList.c | Definition of function interface to implement sequence table |
| test.c | Test whether the function interface can realize the function |
IV Interface implementation
1. Define sequence table
For convenience when we want to change the data type later, we generally typedef the type.
typedef int SeqlistType;
//Create structure
typedef struct Seqlist
{
SeqlistType* arr; //Point to a dynamic array
SeqlistType size; //Effective number
SeqlistType capacity;//capacity
}SL;
2. Structure initialization
Pass value: because the formal parameter is a temporary copy of the argument, changes to the formal parameter will not change the argument. So we should pass the address of the structure variable and receive it with the structure pointer! To prevent null pointers from being passed, we can assert with assert!
void SeqlistInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}3. Print data
We only need to traverse the sequence table to finish printing
void SeqlistPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}4. Sequence table capacity increase
When inserting data, we should first check whether the capacity of the sequence table is full (PS - > size = = PS - > capacity)
Because we didn't give capacity at the beginning (capacity = 0), we can give 4 spaces first, and then double the capacity when there is not enough space in the future!
//Check capacity
void SeqlistCheckCapacity(SL* ps)
{
assert(ps);
//When size == capacity, the capacity needs to be expanded
int newcapacity = 0;
if (ps->size == ps->capacity)
{
newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
//If the initial capacity is 0, give 4 spaces
//If it is not 0, it will be expanded to twice the original
//Capacity expansion needs to reopen space - > realloc
SeqlistType* tmp =
(SeqlistType*)realloc(ps->arr, sizeof(SeqlistType) * newcapacity);
//Note: it is necessary to judge whether the development is successful
if (tmp == NULL)
{
printf("Capacity expansion failed\n");
//exit(-1);
return;
}
else
{
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
}5. Header data
Header data: 1 Check the capacity of the sequence table first. If it is not enough, expand the capacity
2. Header insertion is to put the data in the first position. Then we can move the original data of the array back! Pay attention to moving from the rightmost (I = PS - > size-1), otherwise the previous data will overwrite the subsequent data!
3. After inserting data, mark the size+1 of the significant number;
//Head insert
void SeqlistPushFront(SL* ps, SeqlistType x)
{
assert(ps);
//Check the capacity first!!!!
SeqlistCheckCapacity(ps);
int i = 0;
for (i = ps->size-1; i >=0; i--)
{
ps->arr[i+1] = ps->arr[i];
}
ps->arr[0] = x;
ps->size++;
}6. Tail interpolation data
Tail interpolation data: 1 The capacity should also be checked before tailoring data
2. Insert data at the position of the array, i.e. PS - > size position
3. Insert data, szie + +;
//Tail insertion
void SeqlistPushBack(SL* ps, SeqlistType x)
{
assert(ps);
//Check the capacity first!!!!
SeqlistCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}7. Header deletion data
Header deletion data: 1 Overwrite the following data to the front. Pay attention to start from the left (i=0), otherwise it will cause data loss!
2. Deleted data, size--
void SeqlistPopFront(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i+1];
}
ps->size--;
}8. Tail deletion data
Just make the significant number - 1. Although the data is still in the array, we can't access it!
void SeqlistPopBack(SL* ps)
{
assert(ps);
ps->size--;
}
9. Find data
1 find out whether the element is in the sequence table, if the element is in the subscript in the array
2. If not, return - 1 (- 1 is invalid coordinate)
3. The return type is int. if the return type is written as the type of typedef before us, pay attention to the type of typedef!
int SeqlistFind(SL* ps, SeqlistType x)
{
assert(ps);
//Traversal search
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1; //-1 is an invalid coordinate
}10. Insert data at a location
Function interface implementation content: give a subscript and insert data in the position before the subscript
1. Ensure that the position is within the valid range of the array (PS - > size-1 range)
2. Move the data to be inserted and the following data backward. Pay attention to moving from the last data (I = PS - > size-1), otherwise the previous data will overwrite the following data.
3. Finally, insert the data into the location, size++
//insert
void SeqlistInsert (SL* ps, SeqlistType pos, SeqlistType x)
{
assert(ps);
//Be sure to insert in the valid area
assert(pos < ps->size);
//Move the pos position and the data behind it back
// To move from the back
//To ensure capacity
SeqlistCheckCapacity(ps);
for (int i = ps->size-1; i >=pos;i--)
{
ps->arr[i+1] = ps->arr[i];
}
ps->arr[pos] = x;
ps->size++;
}11. Delete a location
Function interface implementation content: give a subscript and delete the position.
1. Ensure that the array of positions to be deleted is within the data range ((PS - > size-1 range))
2. Move the data behind the location forward and overwrite the data of the location to be deleted.
3. Delete element - > size--
//delete
void SeqlistErase(SL* ps, SeqlistType pos)
{
assert(ps);
assert(pos<ps->size);
//Move the things behind the pos forward
for (int i = pos + 1; i < ps->size; i++)
{
ps->arr[i-1] = ps->arr[i];
}
ps->size--;
}
12. Modify a location data
Function interface implementation content: give a subscript and modify the value corresponding to the subscript
Ensure that the subscript is within the data range of the array (PS - > size-1 range)
//change data
void SeqlistModify(SL* ps, SeqlistType pos, SeqlistType x)
{
//Make sure to change within the valid data range
assert(pos < ps->size);
ps->arr[pos] = x;
}
13. Number of elements in the sequence table
size indicates the number of significant digits in the sequence table
//Count the number of elements in the sequence table
int SeqListSize(SL* ps)
{
assert(ps);
return ps->size;
}14. Destruction sequence table
Release the dynamically opened array. free and pointer null should be used at the same time! Otherwise, it may cause wild pointer!
//Destroy space
void SeqlistDestory(SL* ps)
{
//free and NULL should be used together
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}Summary:
1. Some children's shoes can't understand the relationship between size and array subscript! Now look at the picture
Size is the number of significant numbers, that is, how many elements the array has. The subscript of the array starts from 0, so PS - > arr [PS - > size] is the position after the last element of the array. The index of the last element of the array is PS - > arr [PS - > size-1]
Other precautions:
! Find out whether to transmit value or address!
Pass value: a formal parameter is a temporary copy of an argument. Changes to the formal parameter will not change the argument
1. Check the capacity when inserting data!
2. When modifying / deleting / inserting data in a subscript, ensure that the subscript is within the range of array subscripts (PS - > size-1)
3. After inserting / deleting data, size should also remember + + / --!
4. When the header plug is deleted and inserted in front of a subscript position, it is necessary to find out which side of the element to move from!
When we implement all the interfaces, we can design a game menu!
Effect display:
The specific game code and all the codes in this article are in the appendix!