Python wechat ordering applet course video

https://edu.csdn.net/course/detail/36074

Python actual combat quantitative transaction financial management system

https://edu.csdn.net/course/detail/35475

Data structure sequence table

Sequence table definition

1. Preface

The sequential storage of linear table is also called sequential table. It uses a group of storage units with continuous addresses to store the data elements in the linear table in turn, so that the two logically adjacent elements are also adjacent in physical location. Its biggest feature is that the logical order of elements is the same as its physical order.

Any element in the sequential storage structure of the linear table can be accessed randomly. Note that the bit order of the elements in the linear table starts from 1, while the subscript of the elements in the array starts from 0. Assuming that the element type of the linear table is EleType, the sequential storage type of the linear table can be described as:

#define MaxSize 50 / / defines the maximum length of a linear table
typedef struct {
    ElemType data[MaxSize];	//Elements of sequence table
    int length;	//Current length of sequence table
}SqList；	//Type definition of sequence table

2. Dynamic implementation

1. Structure definition:

#define InitSize 10 / / the default maximum length
typedef struct{
    int *data;		//Pointer indicating dynamically allocated array
    int MaxSize;	//Maximum capacity of sequence table
    int length;		//Current length of sequence table
}SeqList；

2. Initialization sequence table:

void InitList(SeqList &L){
    //Apply for a piece of continuous storage space with malloc function
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

3. Increase the length of dynamic array:

void IncreaseSize(SeqList &L,int len){
    int *p=L.data;
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i//Copying data to a new area is time-consuming
 L.MaxSize=L.MaxSize+len; //Increase the maximum length of sequence table by len
 free(p); //Free up the original memory space
}

Basic operations on sequence table

1. Insert operation (listsert)

Insert the specified element e at the ith position in table L. The following is implemented in the way of "static allocation".

The following is the main code part of the implementation, which is easy for us to read and understand:

#define MaxSize 10 / / defines the maximum length of a linear table
typedef struct {
    int data[MaxSize];	//Use a static "array" to store data elements
    int length;	//Current length of sequence table
}SqList；	//Type definition of sequence table
    
bool ListInsert(Sqlist &L,int i,int e){
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)   //The current storage space is full and cannot be inserted
        return false;
    for(int j=L.length;j>=i;j--)    //Move the ith element and its subsequent elements backward
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;  //Place e at position i
    L.length++; //Length of linear table plus 1
    return true;
    
int main(){
    SqList L;	//Declare a sequence table
    InitList(L);	//Initialization sequence table
    //... The code to insert several elements is omitted here
    ListInsert(L,3,3);
    return 0;
}

Time complexity analysis of insertion operation:

By observing the above code, when analyzing the time complexity, we only need to pay attention to the relationship between the execution times of the deepest loop statement and the problem scale n. That is, the statement * * "L.data[j]=L.data[j-1];"** You can:

• Best case: insert the new element into the epitope without moving the element, i=n+1, cycle 0 times; The best time complexity is O(1)
• Worst case: when the new element is inserted into the header, all the original n elements need to be moved backward, i =1, and cycle n times; The worst time complexity is O(n);
• Average situation: assuming that the probability of inserting new elements into any position is the same, the probability is P=1/(n+1). i=1, N cycles; When i =2, cycle n-1 times; When i =3, cycle n-2 times... When i =n+1, cycle 0 times. Average number of cycles = np+(n-1)p+(n-2)p +... + 1 p= n/2. The average time complexity = O(n)

Tip: if the relationship between the value of i and the number of cycles n in the above analysis is not clear, recall that the bit order of the elements in the linear table mentioned at the beginning starts from 1, while the subscript of the elements in the array starts from 0.

2. Delete (ListDelete (SqList & L, int i, int & E))

Delete the element at position i (1 < = i < = L.Length) in the sequence table L and return it with the reference variable e. If the i entered is illegal, false will be returned; Otherwise, assign the deleted element to the reference variable e, move the i+1 element and all subsequent elements forward one position at a time, and return true.

Here are some codes to help us understand and read:

bool ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.length)	//Judge whether the range of i is valid
        return false；
     e=L.data[i-1];	//Assign the deleted element to the reference variable e
    for(int j=i;j//Move the element after the ith position forward
 L.data[j-1]=L.data[j];//Here we remind you again of the relationship between bit order and array subscript
 L.length--; //Linear table length minus 1
 return true;
}

int main(){
 SqList L; //Declare a sequence table
 InitList(L); //initialization
 //..... Omit some code
 int e=-1; //"Bring back" deleted variables with scalar e
 if(ListDelete(L,3,3))
 printf("The third element has been deleted, and the value of the deleted element is=%d\n",e);//want a go
 else
 printf("Bit order i Illegal, deletion failed\n");
 return 0;
}

The deletion operation is a time complexity analysis:

By observing the above code, when analyzing the time complexity, we only need to pay attention to the relationship between the execution times of the deepest loop statement and the problem scale n. That is, the statement * * "L.data[j-1]=L.data[j];"** You can:

• Best case: delete elements without moving other elements, i=n, cycle 0 times; The best time complexity is O(1)
• Worst case: to delete the header element, you need to move all the subsequent n-1 elements forward. i=1, cycle n-1 times; Worst time complexity = O(n)
• Average case: suppose that the probability of deleting any element is the same, and p=1/n, i=1, cycle n-1 times; i=2, cycle n-2 times... When i=n, cycle 0 times, so the average number of cycles = (n-1)p+(n-2)p +... + 1 p=(n-1)/2. Then the time complexity is O(n)

3. Search by bit (GetElem(L,i))

Gets the value of the element at position i in table L. Here is a simple code example:

#define InitSize 10 / / the initial length of the sequence table
typedef struct{
    ElemType *data;	//Pointer indicating dynamically allocated array
    int MaxSize;	//Maximum capacity in sequence table
    int length;	//Current length of sequence table
}SeqList;		//Definition of type of sequence table (dynamic allocation method)

ElemType GetElem(SeqList L,int i){
    return L.data[i-1];
}

Since the elements of the sequence table are stored continuously in memory, the i-th element can be found immediately according to the starting address and the size of the data element, which is the embodiment of the random access feature. Therefore, its time complexity can be obtained as O(1).

4. Find by value (locateelem (L, e))

Finds the element with the given keyword in table L. Find the L-bit of the element in the following order and return the value in the following order:

int LocateElem(SeqList L,ElemType e){
    for(int i=0;iif(L.data[i]==e)
 return i+1; //Pay attention to the relationship between array subscript and bit order
 return 0; //Exit the loop, indicating that the search failed
}

Analysis of time complexity:

By observing the above code, when analyzing the time complexity, we only need to pay attention to the relationship between the execution times of the deepest loop statement and the problem scale n. That is, the statement * * "if(L.data[i]==e" * * can be used:

• Best case: the target element is in the header and circulates once; The best time complexity is O(1)
• Worst case: the target element is at the end of the table and circulates n times; The worst time complexity is O(n);
• Average situation: assuming that the probability of the target element appearing at any position is the same, which is 1/n, and the target element is in the first place, cycle once; Bit 2, cycle 2 times If n is the number of cycles, the average number of cycles = 1\n+2.1/n +... + n.1/n=(n+1)/2; Then the average time complexity is O(n).

Let's say so much about the sequence table first. Let's encourage each other!