Data structure = data definition + data operation
Sequence table: an area of continuous storage
Structure definition:
Size: represents the current order of table size
length: how many elements are currently stored
data_type: type of stored element
Structure operation:
Insert:
Delete:
1. Definition of data structure:
typedef struct Vector{
int *data;
int size,length;
}Vector;
Redefine the struct structure type into the vector data type
int * data: the pointer is the address. Data is a continuous storage area,
2. Initialize the sequence table that stores n elements
Vector *init(int n){
Vector *vec = (Vector *)malloc(sizeof(Vector));
vec->data = (int*)malloc(sizeof(int)*n);
vec->size = n;
vec->length = 0;
return vec;
}
The data type is Vector *, that is, the previous structure
Function name init
Parameter int n
A vec sequence table is defined in the function, and a memory space is initialized for the sequence table
Then, a space is also initialized for the data continuously stored in the sequence table
The number of elements size is initialized to n, that is, the passed in parameter
The initial value of the existing element length is 0
Finally, the sequence table vec is returned
3. Destroy sequence table:
void clear(Vector *vec){
if(vec == NULL)return;
free(vec->data);
free(vec);
return;
}Defines a function with no return value, and the passed in parameter is the sequence table
if the sequence table is empty, return directly
Address of data storage space that is not empty
Release sequence table.
4. Sequence table insertion:
int insert(Vector *vec, int ind, int val){
if (vec == NULL ) return 0;
if (vec->length == vec->size) return 0;
if (ind <0 || ind>vec->length ) return 0;
for (int i = vec->length;i>ind;i--){
vec->data[i] = vec->data[i-1];
}
vec->data[ind] = val;
vec->length +=1;
return 1;
}
Define an insert function of type int, which returns 1. 0 after successful insertion The failure is 0
The parameters passed in are the values to be passed in from vec sequence table # ind position # and val
There are several illegal situations
1. When the table is empty
2. The watch is full
3. The insertion position exceeds the upper and lower limits
All the above are illegal and cannot be inserted. 0.0 is returned directly
During the insertion operation, we need to move the insertion position and the following data back in turn
After the move is completed, write the data we want to insert at the insertion position
A for loop is defined, which initializes i to the number of stored in the sequence table. Since it starts from 0, it is not necessary to add 1
The end condition of the loop is to loop to the position ind we want to insert
When the cycle ends
Then insert our value at the insertion position
Length plus 1
Return 1: successful insertion
5. Delete sequence table element
int erase(Vector *vec , int ind){
if (vec == NULL ) return 0;
if (vec->length == 0) return 0;
if (ind <0 || ind>vec->length ) return 0;
for(int i = ind+1;i<vec->length;i++){
vec->data[i-1] = vec->data[i];
}
vec->length -=1;
return 1;
}The specific is similar to the insertion. I won't explain it in detail
6. Functions that sequentially output the elements in the sequence table
The output format is similar to this [1,2,2,3,6]
void output(Vector *vec){
printf("Vector(%d) = [",vec->length);
for (int i = 0;i<vec->length ; i++){
printf("%d",vec->data[i]);
}
printf("]\n");
return;
}
A function that does not return a value
The incoming element is a sequence table
Output vector (% d). How many elements are there in the table? Similar to vector (10), it is an element
Traversing the sequence table with the for loop
6. Main function test sequence table
Randomly insert and delete values at random positions.
Introduce random seed
int main()
{
srand(time(0));
#define MAX_OP 20
Vector *vec = init(MAX_OP);
int op ,ind ,val;
for(int i=0 ;i<MAX_OP;i++){
op = rand()%2;
ind = rand()%(vec->length +1);
val = rand()%100;
switch(op){
case 0:{
printf("insert %d at %d to vector \n",val,ind);
insert(vec,ind,val);
}break;
case 1:{
printf("erase item at %d from vector \n",ind);
erase(vec,ind);
}break;
}
output(vec);
}
return 0;
}
Import header file
#include <time.h>
Define a 20 constant
Initialization sequence table
Variables that define insertion, deletion, location, and value
op is 0 and 1
0 insert
1 delete
Define a for loop
Cycle condition 0-20
%2 random out 0 and 1
%(VEC - > length + 1) random from the size of existing elements
%100 random to 100 number insertion
Use switch to judge whether to insert or delete
And output
The complete code is as follows
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Vector{
int *data;
int size,length;
}Vector;
Vector *init(int n){
Vector *vec = (Vector *)malloc(sizeof(Vector));
vec->data = (int*)malloc(sizeof(int)*n);
vec->size = n;
vec->length = 0;
return vec;
}
void clear(Vector *vec){
if(vec == NULL)return;
free(vec->data);
free(vec);
return;
}
int insert(Vector *vec, int ind, int val){
if (vec == NULL ) return 0;
if (vec->length == vec->size) return 0;
if (ind <0 || ind>vec->length ) return 0;
for (int i = vec->length;i>ind;i--){
vec->data[i] = vec->data[i-1];
}
vec->data[ind] = val;
vec->length +=1;
return 1;
}
int erase(Vector *vec , int ind){
if (vec == NULL ) return 0;
if (vec->length == 0) return 0;
if (ind <0 || ind>vec->length ) return 0;
for(int i = ind+1;i<vec->length;i++){
vec->data[i-1] = vec->data[i];
}
vec->length -=1;
return 1;
}
void output(Vector *vec){
printf("Vector(%d) = [",vec->length);
for (int i = 0;i<vec->length ; i++){
if (i!=0) printf(",");
printf("%d",vec->data[i]);
}
printf("]\n");
return;
}
int main()
{
srand(time(0));
#define MAX_OP 20
Vector *vec = init(MAX_OP);
int op ,ind ,val;
for(int i=0 ;i<MAX_OP;i++){
op = rand()%2;
ind = rand()%(vec->length +1);
val = rand()%100;
switch(op){
case 0:{
printf("insert %d at %d to vector \n",val,ind);
insert(vec,ind,val);
}break;
case 1:{
printf("erase item at %d from vector \n",ind);
erase(vec,ind);
}break;
}
output(vec);
}
return 0;
}