This is the 22nd day of my participation in the August Wen Challenge.More challenges in August
preface
In introducing data organizations, we talked about four basic types of data structures, and today we will talk about one of the most common — linear tables. And linear tables because of their own differences, and divided into many types. By the different storage mode, and appeared sequential list and linked list. Stacks and queues emerge from the constraints of operations on tables. Today I’m going to talk to you about the order table.
1.1. What is a linear table
Linear tables are a very common type of data structure, like the array we’ve seen before. The characteristic of a linear table is that there is a one-to-one relationship between the elements. Let’s first assume the following sequence table L:
L = {a1, a2, a3, a4, a5, a6...... an}Copy the codeLet’s take A2 as our reference. The element before A2 is called the direct precursor. The element after a2 we call the immediate successor. In the table above we can see that any element in L has at most one immediate precursor and one immediate successor. That’s the property of a linear list, there’s only zero or one direct precursor, there’s only zero or one direct successor. This is what we call a one-to-one relationship.
1.2. What are the common linear tables
In the future, we will learn about four types of linear lists: sequential lists, linked lists, stacks, and queues. Both of them belong to linear lists, in which due to the physical implementation (storage mode) difference, the sequential list and the linked list, the difference is that the sequential list uses the sequential storage structure, while the linked list uses the chain storage structure. We restrict the basic operations of a linear table, resulting in stacks and queues that can only be accessed from one end of the table, and queues that can only delete at the head of the queue and insert at the end of the queue.
1.3. Some operations on linear tables
Before we get into order tables, let’s take a look at some of the linear table-based operations we usually need to implement, most of which are generic for order tables.
L: a pointer to a linear table * return: returns 1 on initialization success, 0 on initialization failure
int InitList(*L);
L: pointer to the linear table to be destroyed */
void DestroyList(*L);
L: pointer to the linear table to be emptied */
void CleaerList(*L);
L: The length of the linear table to get * return: the length of the linear table */
int LengthList(*L);
Return: Returns 0 if it is null, returns its length if it is not null */
int EmptyList(*L);
/** * returns: returns 1 on success, or returns 0 on failure. /** * returns 1 on success, or returns 0 on failure
int GetEleme(*L, int i, ElemType *e);
/** * return: Returns 1 on success, or 0 on failure. /** * returns 0 on failure
int LocateElem(*L, ElemType e, int *i);
/** * function: Insert element e into the ith position in linear table L * L: the linear table to operate on * I: the position to be inserted, starting from 1 * e: the element to be inserted * return: Returns 1 on success, 0 on failure */
int InsertList(*L, int i, ElemType e);
L: the linear table to be operated on * I: the position of the element to be deleted, starting from 1 *e: Used to store the element to be deleted * return: Returns 1 on success, 0 on failure */
int DeleteList(*L, int i, ElemType *e);
/** * function: print linear table * L: print linear table */
void DisplayList(*L);
Copy the codeAbove defines some linear table basic operations, after understanding these basic operations we can enter the study of sequential table.
Second, the order table
As mentioned earlier, a sequential table is a kind of linear table, so a regular linear table is a sequential table with a sequential storage structure. The elements in the sequential table are stored in continuous memory, which is convenient for searching. Therefore, we can choose to use the sequential table to store the data sets that often need to be searched.
2.1. Representation of sequence table
When we study data structures, we usually use structures to represent a data type. The representation of a sequential table requires three data items, namely data, subscript, and memory size. Where the type of data we are usually uncertain, so we need a custom type, aspect modification:
typedef int ElemType;
Copy the codeHere we define int as ElemType, we will use ElemType to replace the following data type, and then we implement the structure of the order table:
typedef struct{
ElemType *elem; // The header pointer to the data element (base address)
int length; // The current length of the sequence table
int listsize; // listsize*sizeof(ElemType)
}SqList;
Copy the codeOf course, there is no unique way to represent a sequential table, and many tutorials use a fixed-length array as a data item.
2.2. Implementation of sequence table
Once we know how to represent the order table, we can implement its various operations. Before implementing each operation, we will give some macro definitions:
#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
Copy the codeLIST_INIT_SIZE represents the initializing length of the order table, while LIST_INCREMENT represents the incrementing length of the order table when the length of the table is insufficient. The specific value can be defined by yourself. Next we initialize the order table.
(1) Initialize the sequence table
Table initialization we need to perform operations on three data items, each operation is as follows:
- Elem: LIST_INIT_SIZE*sizeof(ElemType)
- Length: the length of the initialization table is 0
- Listsize: Initializes the table memory as LIST_INIT_SIZE
We use code to do this:
int InitList_Sq(SqList *L){
// Dynamically allocate memory
L->elem = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
// There is not enough memory
if(! L->elem){return 0;
}
// Set the initialization table length to 0
L->length = 0;
// Set the memory of the initialization table to LIST_INIT_SIZE
L->list_size = LIST_INIT_SIZE;
return 1;
}
Copy the codeThe above method passes in a pointer to the order table that returns 1 on success and 0 on failure.
Note: When allocating memory dynamically, a cast is usually performed, but this operation is not necessary. If you are taking an exam, this step is necessary.
(2) Destruction sequence table
Since we are allocating memory dynamically, we need to use the free() function to free the memory. The code implementation is as follows:
void DestroyList_Sq(SqList *L){
// Free memory
free(L->elem);
// Set the length to 0
L->length = 0;
// Set memory to 0
L->list_size = 0;
}
Copy the code(3) Insert data
To test the functionality of the order table as quickly as possible, let’s implement the insert operation first. Let’s look at the flow chart for inserting input:
Cond1 =>condition: I Whether the table is reasonable cond2=>condition: whether the table is long op=>operation: Parameters *L, I, e op1=>operation: Extended table length op2=>operation: insert operation e=>end: St ->op-> conD1 cond1(yes)->cond2 cond1(no)-> E cond2(yes)-> OP2 cond2(no)-> OP1 op1-> OP2 op2-> ETo simplify the flowchart, I did not add a judgment about whether memory was sufficient when I extended the table length. Next, we use code to implement the above flowchart:
int InsertList_Sq(SqList *L, int i, ElemType e){
// Define an ElemType pointer to expand memory when the length is insufficient
ElemType *newbase;
int j;
// The insertion position is invalid
if(i <= 0 || i > L->length+1) {return 0;
}
// The current order table is full
if(L->length == L->list_size){
// Realloc functions are used to reallocate memory
newbase = realloc(L->elem, (L->list_size + LIST_INCREMENT)*sizeof(ElemType));
// Cannot allocate new memory
if(! newbase){return 0;
}
// Update the sequence table with memory expansion
L->elem = newbase;
L->list_size += LIST_INCREMENT;
}
// Move the last element back to the ith element
for(j = L->length; j >= i; j--){
L->elem[j] = L->elem[j- 1];
}
// put e into the ith element's location: L->elem[i-1]
L->elem[i- 1] = e;
// The length of the order table is +1
L->length++;
return 1;
}
Copy the code(4) Display the sequence table
Let’s look at how to display the order table. Since Pointers are used in much the same way as arrays, we can use subscripts to access elements of the order table:
void DisplayList_Sq(SqList *L){
for (int i = 0; i < L->length; i++) {
printf("%d\n", L->elem[i]); }}Copy the codeWe can also access elements as follows:
printf("%d\n", *((L->elem)+i));
Copy the codeThis is pointer knowledge, but I don’t want to extend it here.
Note: L->elem[0] is actually a shorthand for *(L->elem), just a syntactic sugar, essentially no difference.
Then we can test the above method:
int main(a){
SqList L; // Declare a sequence table
InitList_Sq(&L); // Initialize the sequence table
// Loop to add data
for(int i = 0; i < 300; i++){
InsertList_Sq(&L, i+1, i+1);
}
// Display the order table
DisplayList_Sq(&L);
// Destroy the sequence table
DestroyList_Sq(&L);
return 0;
}
Copy the codeBecause of the large amount of data, the printed results will not be posted, you can test yourself.
For (int I = 0; i < 10; I++) this way of defining variables inside loops is new in c99. This is not accepted in the exam.
(5) Delete data
To delete data, we also need to pass in three parameters: the first is the order table, the second is the location of the element to be deleted, and the third is to return the element to be deleted. The concrete implementation is as follows:
int DeleteList_Sq(SqList *L, int i, ElemType *e){
// When the position passed in is illegal
if(i < 0 || i > L->length- 1) {return 0;
}
// Use e to receive deleted data
*e = L->elem[i- 1];
// The length of the sequence table is reduced by 1
L->length--;
// Iterate through the data from the ith element (the ith element is subscript i-1)
for(int j = i- 1; j < L->length; j++){
// Assign the value of the latter element to the former
L->elem[j] = L->elem[j+1];
}
return 1;
}
Copy the code(6) Locating elements
Here we get the position of an element’s first occurrence in the order table and use a variable to store that position.
int LocateElem_Sq(SqList *L, ElemType e, int *i){
int j;
// Iterate over the elements in the order table
for(j = 0; j < L->length; j++){
// When the data is matched
if(L->elem[j] == e){
// Remember its position, (subscript +1) returns 1
*i = j+1;
return 1; }}// No data was matched
return 0;
}
Copy the code(7) Get elements
Above, the position is obtained by the data element; here, the element is obtained by the subscript. This is a little bit easier.
int GetElem_Sq(SqList *L, int i, ElemType *e){
// If the I passed is invalid, return 0
if(i < 0 || i > L->length){
return 0;
}
// Store the ith element in the order table
*e = L->elem[i- 1];
return 1;
}
Copy the code(8) Clear the order table
The emptying and destroying of sequential tables are different concepts. Emptying only empties the data in the table and does not free the memory. Table destruction frees up memory that we have dynamically requested.
void ClearList_Sq(SqList *L){
// Set the length of the order table to 0
L->length = 0;
}
Copy the codeAfter we call this method, we can still get the other elements using the base address, but we assume that all operations on the order table will be implemented using our predefined methods, so we can’t get that data.
(9) Determine whether the table is empty
int EmptyList_Sq(SqList *L){
// A table with a length of 0 returns 1, indicating an empty table
if(L->length == 0) {return 1;
}
// Otherwise return 0, indicating that the table is not empty
return 0;
}
Copy the code(10) Obtain the length of table
int LengthList_Sq(SqList *L){
Return the length of the table
return L->length;
}
Copy the codeAt this point, we have implemented some of the basic operations commonly used in order tables.
2.3. Some other operations on the sequence table
In addition to some common operations, sometimes we also need to implement some special operations, such as table copy, table merge, table inversion, and so on, now we will implement some special operations, readers can choose to read according to their interests.
(1) Copy the sequence table
The implementation of the copy order table requires that we pass in two order tables, the first is the copied order table, and we copy the data from the first order table into the second order table.
int CopyList_Sq(SqList *L1, SqList *L2){
// Apply for the same size of memory as L1
L2->elem = malloc(sizeof(ElemType)*L1->list_size);
// Out of memory returns 0
if(! L2->elem){return 0;
}
// Set the length of L2
L2->length = L1->length;
// Set L2's memory
L2->list_size = L1->list_size;
// Loop assignment
for(int i = 0; i < L2->length; i++){
L2->elem[i] = L1->elem[i];
}
return 1;
}
Copy the code(2) Merge order table
When implementing the merge order table, we can borrow some of the operations we’ve already implemented to make our merge easier.
int MergeList_Sq(SqList *L1, SqList *L2, SqList *L3){
int status = - 1;
// create table L1
status = CopyList_Sq(L1, L3);
if(! status){return 0;
}
// Add data from L2 to L3
for(int i = 0; i < L2->length; i++){
status = InsertList_Sq(L3, L3->length+1, L2->elem[i]);
if(! status){return 0; }}return 1;
}
Copy the codeThe above algorithm is relatively simple to implement, but its efficiency is very low, you can improve it.
(3) Reverse the sequence table
void ReversalList_Sq(SqList *L){
// Temporary variable, used for exchange
ElemType temp;
// Swap the first half of the sequence with the second half
for(int i = 0; i < L->length/2; i++){
temp = L->elem[i];
L->elem[i] = L->elem[L->length- 1-i];
L->elem[L->length- 1-i] = temp; }}Copy the codeSo that’s all I have to say about order tables.