What is a sequence table in Python
1、 Sequence table introduction
Sequence table is the simplest kind of linear structure. Logically, the storage positions of adjacent data in the computer are also adjacent. You can quickly locate the first element. No space is allowed in the middle, so you need to move a lot when inserting or deleting. element. The sequence table can allocate a continuous storage space Maxsize, use elem to record the base address, and length to record the actual number of elements, that is, the length of the sequence table
Figure 1 above shows the basic form of the sequence table. The data elements themselves are stored continuously, and the storage unit size occupied by each element is fixed and the same. The subscript of the element is its logical address, and the physical address of the element storage (the actual memory address) It can be calculated by the starting address Loc (e0) of the storage area plus the product of the logical address (the i-th element) and the storage unit size (c), namely: Loc(element i) = Loc(e0) + c* i
Therefore, when accessing the specified element, there is no need to traverse from the beginning, and the corresponding address can be obtained through calculation, and the time complexity is O(1).
If the size of the elements is not uniform, the external elements of Figure 2 must be used to store the actual data elements separately, and each unit position in the sequence table stores the address information (ie links) of the corresponding elements. Since each link requires the same amount of storage, through the above formula, the storage location of the element link can be calculated, and then the actual stored data element can be found along the link. Note that c in Figure 2 is no longer the size of the data element, but the amount of storage required to store a link address, which is usually very small.
The sequence table shown in Figure 2 is also called an index to actual data, which is the simplest index structure.
2、 Sequence table structure
The complete information of a sequence table consists of two parts, one part is the collection of elements in the table, and the other part is the information that needs to be recorded for correct operation, that is, the information about the overall situation of the table. This part of information mainly includes the capacity of the element storage area And the number of elements in the current table.
3、 Two basic implementation methods of sequence table
1 As an integrated structure, the unit for storing table information and the element storage area are arranged in a storage area in a continuous manner, and the two parts of data form a complete sequential table object. The integrated structure has strong integrity and easy management. But because the data element storage area is a part of the table object, after the sequence table is created, the element storage area is fixed.
2 For a separated structure, only the information related to the entire table (ie capacity and number of elements) is stored in the table object, and the actual data elements are stored in another independent element storage area, which is associated with the basic table object through links.
4、 Element storage area replacement
Integral structure Because the sequence table information area and the data area are continuously stored together, if you want to replace the data area, you can only move it as a whole, that is, the entire sequence table object (referring to the area where the structure information of the sequence table is stored) is changed. If you want to replace the data area in the separated structure, you only need to update the link address of the data area in the table information area, and the sequence table object remains unchanged.
5、 Element storage area expansion
Using a sequence table with a separate structure, if the data area is replaced with a larger storage space, the data storage area can be expanded without changing the table object, and all the places where this table is used do not need to be modified. As long as the program's operating environment (computer system) has free storage, this table structure will not cause operations to fail because it is full. People call the sequence table implemented by this technology a dynamic sequence table because its capacity can be dynamically changed during use.
Two strategies for expansion
Each expansion adds a fixed number of storage locations. For example, each expansion adds 10 element locations. This strategy can be called linear growth.
Features: Save space, but frequent expansion operations and many operations.
Each expansion doubles the capacity, such as doubles the storage space each expansion.
Features: Reduce the number of executions of expansion operations, but may waste space resources. The recommended way to trade space for time.
6、 Python code implementation of sequence table addition, deletion, modification, and query operation
# Create sequence table classSequence_Table():
# initialization
def __init__(self):
self.date =[None]*100
self.length =0
# Determine if it is full
def isFull(self):if self.length 100:print("The sequence table is full and cannot add elements")return1else:return0
# Search by index in the table below
def selectByIndex(self,index):if index =0 and index<=self.length-1:return self.date[index]else:print("The subscript you entered is incorrect, please re-enter\n")return0
# Search subscript by element
def selectByNum(self,num):
isContain =0for i inrange(0,self.length):if self.date[i]== num:
isContain =1print("The index of the element you are looking for is%d\n"%i)if isContain ==0:print("Did not find the data you want")
# Append data
def addNum(self,num):if self.isFull()==0:
self.date[self.length]= num
self.length +=1
# Print order table
def printAllNum(self):for i inrange(self.length):print("a[%s]=%s"%(i,self.date[i]),end=" ")print("\n")
# Press to insert data
def insertNumByIndex(self,num,index):if index<0 or index self.length:return0
self.length +=1for i inrange(self.length-1,index,-1):
temp = self.date[i]
self.date[i]= self.date[i-1]
self.date[i-1]= temp
self.date[index]= num
return1 #Press to delete data
def delectNumByIndex(self,index):if self.length <=0:print("There is no data in the sequence table, no need to delete")for i inrange(index,self.length-1):
temp = self.date[i]
self.date[i]= self.date[i +1]
self.date[i +1]= temp
self.date[self.length-1]=0
self.length -= 1def main(): #Create sequence table object
seq_t =Sequence_Table()
# Insert three elements
seq_t.addNum(1)
seq_t.addNum(2)
seq_t.addNum(3)
# Print verification
seq_t.printAllNum()
# Search by index
num = seq_t.selectByIndex(2)print("The data you are looking for is%d\n"% num)
# Insert data according to the index
seq_t.insertNumByIndex(4,1)
seq_t.printAllNum()
# Check the subscript according to the number
seq_t.selectByNum(4)
# delete data
seq_t.delectNumByIndex(1)
seq_t.printAllNum()if __name__ =="__main__":main()
The running result is:
a[0]=1 a[1]=2 a[2]=3
The data you are looking for is 3
a[0]=1 a[1]=4 a[2]=2 a[3]=3
The index of the element you are looking for is 1
a[0]=1 a[1]=2 a[2]=3
7、 C language code implementation of sequence table addition, deletion, modification, and check operation
# include<stdio.h
//1. Define the storage structure of the sequence table
typedef struct
{ //Use arrays to store elements in linear tables
int data[100];//The number of elements in the sequence table
int length;}Sequence_table,*p_Sequence_table;//2. Initialization of the sequence table, voidinitSequenceTable(p_Sequence_table T){//Judge whether the passed table is empty, if it is empty, exit if(T == NULL){return;}//Set the default length to 0
T- length =0;}//3. Find the length of the sequence table
int lengthOfSequenceTable(p_Sequence_table T){if(T==NULL){return0;}return T- length;}//4. Determine whether the sequence table is full
int isFull(p_Sequence_table T){if(T- length =100){printf("The sequence table is full, no more elements can be added");return1;}return0;}//5. Search by serial number
int selectSequenceTableByIndex(p_Sequence_table T,int index){if(index =0&&index<=T- length-1){return T- data[index];}printf("The serial number you entered is incorrect, please re-enter\n");return0;}//6. Search by content for the existence of voidselectSequenceTableByNum(p_Sequence_table T,int num){
int isContain =0;for(int i=0; i<T- length; i++){if(T- data[i]== num){
isContain =1;printf("The subscript of the element you are looking for is:%d\n",i);}}if(isContain ==0){printf("Did not find the data you were looking for\n");}}//7. Add elements (add at the end of the team) voidaddNumber(p_Sequence_table T,int num){//If the sequence table is not full(isFull(T)==0){
T- data[T- length]= num;
T- length++;}}//8. Traversal of sequence table voidprintAllNumOfSequenceTable(p_Sequence_table T){for(int i =0; i<T- length; i++){printf("T[%d]=%d ",i,T- data[i]);}printf("\n");}//9. Insert operation
int insertNumByIndex(p_Sequence_table T, int num,int index){if(index<0||index T- length){return0;}
T- length++;for(int i = T- length-1; i index; i--){
int temp = T- data[i];
T- data[i]= T- data[i-1];
T- data[i-1]= temp;}
T- data[index]= num;return1;}//10. Delete the element voiddelectNum(p_Sequence_table T,int index){if(T- length <=0){printf("There is no data in the sequence table, no need to delete");}for(int i = index;i<T- length-1; i++){
int temp = T- data[i];
T- data[i]= T- data[i+1];
T- data[i+1]= temp;}
T- data[T- length-1]=0;
T- length--;}
int main(int argc,const char * argv[]){//Create sequence table structure
Sequence_table seq_t;//Initialize initSequenceTable(&seq_t);//Add data addNumber(&seq_t,1);addNumber(&seq_t,2);addNumber(&seq_t,3);//Print verification printAllNumOfSequenceTable(&seq_t);//Check the content according to the index
int num =selectSequenceTableByIndex(&seq_t,2);printf("The data you check is:%d\n",num);//Insert insertNumByIndex(&seq_t,4,1);printAllNumOfSequenceTable(&seq_t);//Check the subscript according to the content selectSequenceTableByNum(&seq_t,4);//Delete data according to subscript delectNum(&seq_t,1);printAllNumOfSequenceTable(&seq_t);return0;}
The running result is:
T[0]=1 T[1]=2 T[2]=3
The data you check is: 3
T[0]=1 T[1]=4 T[2]=2 T[3]=3
The subscript of the element you are looking for is: 1
T[0]=1 T[1]=2 T[2]=3
Knowledge point expansion:
The two types of list and tuple in Python adopt the implementation technology of sequential lists, which have all the properties of sequential lists discussed earlier.
Tuple is an immutable type, that is, an invariable sequence list, so it does not support any operation that changes its internal state, and in other respects, it is similar to the nature of the list.
Basic realization technology of list
The Python standard type list is a linear list with a variable number of elements. You can add and delete elements, and maintain the order of existing elements in various operations (that is, order preservation), and also has the following behavioral characteristics:
Efficient element access and update based on subscript (location), the time complexity should be O(1);
In order to meet this feature, sequential table technology should be used, and the elements in the table are stored in a continuous storage area.
It is allowed to add elements arbitrarily, and in the process of adding elements, the identifier of the table object (the value obtained by the function id) does not change.
To meet this feature, it is necessary to be able to replace the element storage area, and to ensure that the identification id of the list object remains unchanged when the storage area is replaced, only a separate implementation technology can be used.
In the official implementation of Python, list is a dynamic sequence list implemented using separate technology. This is why it is more efficient to use list.append(x) (or list.insert(len(list), x), insert at the end) than to insert an element at a specified position.
In the official implementation of Python, the list implementation adopts the following strategy: when creating an empty table (or a small table), the system allocates a storage area that can hold 8 elements; when performing an insert operation (insert or append) , If the element storage area is full, change a storage area that is 4 times larger. But if the table is already very large at this time (the current threshold is 50000), change the strategy and use the method of doubling. The introduction of this change strategy is to avoid too many free storage locations.
The above is the detailed content of what is the sequence table in Python. For more detailed information about the sequence table in Python, please pay attention to other related articles on ZaLou.Cn!
Recommended Posts