Before we talked about linear tables, this article to explain the linear table of sequential storage – order table
define
The sequential storage of a linear table is also called a sequential table, which uses a group of storage units with consecutive addresses to store the data elements in a linear table. Two data elements that are logically adjacent are also physically adjacent.
regular
The logical order is the same as the physical order L = (a1a_{1} A1, a2a_{2}a2,… , aia_{i}ai, ai+1a_{i + 1}ai+1, … , ana_{n}an)
The two data elements that are logically adjacent are also stored in the same storage unit in the sequential table, and each small cell represents a storage unit.
Note that the bitorder of elements in a linear list starts at 1, while the subscripts of elements in an array start at 0
If the starting position of linear table storage is Loc(A) and sizeof(ElemType) is the storage space occupied by each data element, the storage address of each data element can be calculated according to this feature.
The address of the first element is LOC(A). Calculate the address of the second element by adding the address of the first element to the storage space of the first data element a1a_{1}a1. Use sizeof to calculate the storage space of the data element. One thing to note here is that n is meaningfully different from MaxSize, where ana_{n} AN represents the last data element in the sequence table, whereas MaxSize represents the last storage location in the array.
Two ways to implement the order table
Sequential lists can be implemented using arrays. Depending on how arrays are allocated, there are two ways to describe sequential tables. The methods of statically describing the allocation order table and dynamically describing the allocation order table are respectively. Let’s start by looking at how static array allocation describes an order table.
- Statically describe the allocation order table
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
Copy the code
This is the statement that describes the order table. The first sentence defines a macro, which defines the maximum length of a linear table to be 50, which is also the maximum size of the array. A structure is then defined. A structure is a combination of basic data types to form a new data type. Its definition statement is a typedef struct, followed by curly braces enclosing the base data type to be included. Finally, SqList represents the name of the structure.
In static allocation, the size and space of the array are fixed. Once the space is filled up, adding new data will overflow, resulting in program crash.
- Dynamically describes the allocation order table
#define MaxSize 50
typedef struct{
ElemType *data; // A pointer to dynamically allocated arrays
int MaxSize, length; // The maximum size and current number of arrays
}SqList;
Copy the code
A pointer is used to store the address of a storage unit. The sequential table calculates the location of any data element based on the address of the first data element and the size of the data element. The entire sequence table can be described as long as a pointer to the first data element is defined. However, this variable is only an address, and there is no exact space, so in use, need to dynamically apply for space. How to apply for space dynamically? :
- C’s initial dynamic allocation statement
L.data = (Elemtype*)malloc(sizeof(ElemType)*InitSize);
Copy the code
- C++ initial dynamic allocation statement
L.data = new ElemType[InitSize];
Copy the code
In dynamic allocation, once the data space is full, a larger storage space is created to replace the original storage space.
Implementation of basic operations on sequential tables
define
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
//----- The sequential storage of the order table represents -----
#define LIST_INIT_SIZE 100 // Initial allocation of storage space
#define LISTINCREMENT 10 // Storage space allocation increment
typedef struct {
ElemType *elem; // Base address of the storage space
int length; / / table
int size; // Storage capacity
int increment; // Added storage capacity during capacity expansion
} SqList; / / order form
Copy the code
Initialize the sequence table
Status InitSqlist(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(! L.elem)exit (OVERFLOW);
L.length = 0;
L.size = LIST_INIT_SIZE;
L.increment = LISTINCREMENT;
return OK;
}
Copy the code
Check whether the sequence table is empty
Status ListEmpty(SqList L){
if (L.length == 0) return OK;
else return ERROR;
}
Copy the code
The insert
Status ListInsert_Sq(SqList &L, int i, ElemType e){
if(i < 1 || i > L.length + 1)
return ERROR;
if(L.length >= L.size)
return ERROR;
for(int j = L.length; j >= i; j--)
L.elem[j] = L.elem[j - 1];
L.elem[i - 1] = e;
L.length++;
return OK;
}
Copy the code
Remove elements
Status ListDelete_Sq(SqList &L, int i, ElemType &e){
if(i < 1 || i > L.length)
return ERROR;
e = L.elem[i - 1];
for(int j = i; j < L.length; j++)
L.elem[j - 1] = L.elem[j];
L.length--;
return OK;
}
Copy the code
Output sequence table
void OutList_Sq(SqList L) {
int i;
ElemType e;
if(ListEmpty(L)) {
printf("This is an empty table!");
}
else {
printf("The order table is:");
for(i = 0; i < L.length; i++) {
printf("%6d", L.elem[i]);
}
printf("\n"); }}Copy the code
test
int main(a) {
SqList L;
int cord,i; ElemType a;
printf("First use must be initialized! \n");
do {
printf("\n Main menu \n");
printf("1 Initialization sequence table");
printf("2 inserts an element");
printf("3 Delete an element");
printf("4 End program running");
printf("\n-------------------------------------------------------------------\n");
printf("Please enter your choice (1, 2, 3, 4)");
scanf("%d", &cord);
printf("\n");
switch(cord) {
case 1:
InitSqlist(L);
OutList_Sq(L);
break;
case 2:
printf("\n Please enter the insertion position and data element to be inserted (e.g. 3 20)");
scanf("%d%d", &i, &a);
ListInsert_Sq(L, i, a);
printf("\n after insert %d element", a);
OutList_Sq(L);
break;
case 3:
printf("\n Please enter the location of the data element to be deleted (e.g., 3)");
scanf("%d", &i);
ListDelete_Sq(L, i, a);
printf("\n after deleting element in position %d", i);
OutList_Sq(L);
break;
case 4:
exit(0);
default: break; }}while(cord <= 4);
return 1;
}
Copy the code