preface
This chapter introduces the storage elements in the data structure - the sequential table in the linear table
Linear table
A linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential table, linked list, stack, queue, string
A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When a linear table is stored physically, it is usually stored in the form of array and chain structure
Sequence table
-
Sequential table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used. Complete the addition, deletion, query and modification of data on the array
-
Static and dynamic sequence tables
-
Static order - uses a fixed length array to store elements
-
Dynamic sequential table - dynamic storage elements
-
Static and dynamic comparison
The static sequence table is only applicable to the scenario where you know how much data needs to be stored. The fixed length array of static sequence table leads to large N and more space
The charge is not enough. Therefore, in reality, dynamic sequential tables are basically used to dynamically allocate space according to needs, so we implement the following steps
Current dynamic sequence table
Dynamic sequence table
Structure declaration
Since dynamic storage elements. Naturally, it is necessary to first determine the maximum capacity of the currently developed memory - capacity and the index for recording effective data to facilitate memory access. Therefore, define the structure:
typedef int SLDateType;//It is convenient to modify the element type of the sequence table
typedef struct SeqList//Rename structure to SL
{
SLDateType* psl;//psl points to the dynamic application space
size_t sz;//Number of valid data recorded
size_t capacity;//Capacity of open space
}SL;
Initialize structure
- The array subscript starts from 0, so sz in initialization always points to the subscript of the next element in the array, which is very special!!!! Later, you should pay attention to whether the space currently applied for is full.
void SeqListInit(SL* p)
{
assert(p);
p->psl = NULL;
p->sz = 0;
p->capacity = 0;
}
Determine whether the array is full
- Suppose the maximum capacity of the array is 10, so the array subscript starts from 0, so it is full when sz is equal to capacity.
void SeqListRealloc(SL* p)
{
if (p->sz == p->capacity)//When it is equal, it needs to be expanded. Here I will expand it with two compensation
{
p->capacity = p->capacity == 0 ? 4 : 2 * p->capacity;
SLDateType* tmp = (SLDateType*)realloc(p->psl, p->capacity * sizeof(SLDateType));
if (tmp == NULL)
{
printf("");
exit(-1);
}
p->psl = tmp;
}
}
Insert element at specified position
-
Head insertion and tail insertion are just one of them. You can reuse SeqListInsert later
-
Note the array subscript
void SeqListInsert(SL* p, size_t pos, SLDateType x)//At the specified position pos, insert the element.
{
assert(p);
assert(pos <= p->sz && pos>=0);//The sequence table is filled with data in turn, so capacity cannot be compared
SeqListRealloc(p);//Determine whether capacity expansion is required.
for (size_t i = p->sz; i>pos; --i)//size_ Tto consider
{
p->psl[i] = p->psl[i-1];
}
p->psl[pos] = x;
p->sz++;
}
Header insert element
void SeqListPushFront(SL* p, SLDateType x)//Insert header element
{
assert(p);
SeqListInsert(p, 0, x);
}
Tail insert element
void SeqListPushBack(SL* p, SLDateType x)//Trailing element
{
assert(p);
SeqListInsert(p, p->sz, x);
}
Delete element at specified location
- Note that deleting an element is not really deleting it, but in the form of sz -. On the one hand, when subsequently adding elements, it is OK to add elements at the corresponding position. On the other hand, the dynamically opened memory is not allowed to release dynamic memory in the middle.
void SeqListErase(SL* p, size_t pos)//The specified position POS (representing array subscript) is deleted
{
assert(p);
assert(pos <= p->sz && pos >= 0);
for (size_t i = pos; i < p->sz - 1; ++i)
{
p->psl[i] = p->psl[i + 1];
}
p->sz--;
}
Header deletion element
void SeqListPopFront(SL* p)//Header delete element
{
assert(p);
SeqListErase(p, 0);
}
Tail deletion element
void SeqListPopBack(SL* p)//Tail delete element
{
assert(p);
SeqListErase(p, p->sz-1);
}
Find element
int SeqListFind(SL* p, SLDateType x)//When searching for elements, find the return subscript, otherwise 0;
{
for (size_t i = 0; i < p->sz; ++i)
{
if (x == p->psl[i])
{
return i;
}
}
return 0;
}
Print array
void SeqListPrint(SL* p)//Print
{
assert(p);
for (size_t i = 0; i < p->sz; ++i)
{
printf("%d ", p->psl[i]);
}
printf("\n");
}
Destroy the requested space
void SeqLIstDestory(SL* p)//free
{
free(p->psl);
p->psl = NULL;
p->capacity = 0;
p->sz = 0;
}
menu
// Build a dynamic sequence table.
enum whole
{
Exit,
pushfront,
pushback,
pushinsert,
popfront,
popback,
poperase,
popdate,
print
};
void menu()
{
printf("************************************************************\n");
printf("***************Static sequence table***********************************\n");
printf("*********1.Head insert 2.Tail insert 3.Insert at any position*****************\n");
printf("*********4.Header deletion 5.Tail deletion 6.Delete anywhere*****************\n");
printf("*********7.Specified element delete 8.Print 0 .Exit ********************\n");
printf("************************************************************\n");
}
int main ()
{
SL s;
int input = 0;
SeqListInit(&s);
SLDateType x = 0;//If you are an integer, you need to modify scanf
int Flage = 0;
size_t pos = 0;//position
int ret = 0;
do
{
menu();
printf("Please enter your choice:");
scanf("%d", &input);
switch (input)
{
case pushfront:
printf("\t Head insert\n");
printf("Please enter the element you want to insert->,End with 0\n");
scanf("%d", &x);
while (x)
{
SeqListPushFront(&s, x);
scanf("%d", &x);
}
break;
case pushback:
printf("\t Tail insertion\n");
printf("Please enter the element you want to insert->,End with 0\n");
scanf("%d", &x);
while (x)
{
SeqListPushBack(&s, x);
scanf("%d", &x);
}
break;
case pushinsert:
printf("\t Insert at any position\n");
printf("Please enter the element you want to insert->And location->,End with 0\n");
scanf("%d%d", &x,&pos);
while (x)
{
SeqListInsert(&s,pos, x);
scanf("%d%d", &x,&pos);
}
break;
case popfront:
printf("\t Header deletion\n");
printf("Enter a number. A non-zero number indicates header deletion, and 0 indicates end\n");
scanf("%d", &Flage);
while (Flage)
{
SeqListPopFront(&s);
scanf("%d", &Flage);
}
break;
case popback:
printf("\t Tail deletion\n");
printf("Enter a number. A non-zero number indicates tail deletion, and 0 indicates end\n");
scanf("%d", &Flage);
while (Flage)
{
SeqListPopBack(&s);
scanf("%d", &Flage);
}
break;
case poperase:
printf("\t Delete anywhere\n");
printf("Please enter a number to delete anywhere with 1,End with 0 and enter a location\n");
scanf("%d%d", &Flage,&pos);
while (Flage)
{
SeqListErase(&s,pos);
scanf("%d%d", &Flage, &pos);
}
break;
case popdate:
printf("\t Specify element deletion\n");
printf("Enter a number. A non-zero number indicates header deletion, and 0 indicates end,And enter the specified element\n");
scanf("%d%d", &Flage, &x);
while (Flage)
{
ret = SeqListFind(&s, x);
if (ret != -1)
{
SeqListErase(&s, ret);
printf("Delete succeeded\n");
}
else
{
printf("The data does not exist\n");
}
scanf("%d%d", &Flage, &x);
}
break;
case print:
SeqListPrint(&s);
break;
case Exit:
SeqLIstDestory(&s);
system("cls");
printf("Thanks for using!\n");
break;
default:printf("Input error, please re-enter");
}
} while (input);
return 0;
}
Effect display
summary
- This is to get familiar with the dynamic sequence table. In addition, the menu in the program does not need to be paid special attention. It's right to be able to work out the code functions without bugs.
- The following describes the linked list in the sequence list - 8 linked list forms, mainly 2 of which are used.