This is the 29th day of my participation in the August Wenwen Challenge.More challenges in August

Research algorithm will

1. Insert elements into the sequence table

Introduction: If we want to implement ListInsert(SeqList *L, int I, ElemType e), that is, insert the new element e in the ith position of the sequential table L, what should we do?

  1. If the insertion position is not reasonable, end the program, output exception information
  2. If the linear table length is greater than or equal to the array length, end the program and output an exception message
  3. Start from the last element in the sequence and traverse forward to the ith position, moving it back one position at a time.
  4. Inserts the element at the specified position I
  5. Table length increases by 1

As an example, let’s insert an element at the third storage location, where new is the new element to be inserted.

Sequence table insert element operation code implementation

1 ≤ I ≤ ListLength(L)
Insert a new data element e before the ith position in L, and increase the length of L by 1
int ListInsert(SeqList *L,int i,ElemType *e){
    intK;if(L->length==MAXSIZE)/* The sequential linear table is full */
        return ERROR;
 if(I <1 || i>L->length+1)/* When I is not in range */return ERROR; 
    if(i<=L->1ength){/* Insert data into table */ 
        for(k=L->length- 1; k>=i- 1; k--)/* Move the data element after the position to be inserted one bit */
            L->data[k+1]=L->data[k];
    }
    L->data[i- 1]=e;/* Inserts the new element into */
    L->length++;
    return OK;
}

Copy the code

Code analysis:

In the code above, the core statement is the judgment in the for loop that inserts into the order table should move the row position before inserting. So the insertion of a sequential linear list is O(n).

2. Delete elements from the sequence table

If you want to delete an element from a sequential linear table, implement ListDelete(SqList *L,int I,ElemType *e), that is, delete the element e at the ith position in L. First, sort out the algorithm idea:

  1. If the deleted element is not in the correct position, end the program with an exception message
  2. Take the deleted element and place it in element E
  3. Starting at the deleted element position, you traverse to the last element position, moving them forward one position at a time
  4. The length of the table minus 1

Sequential table delete element operation code implementation

1 ≤ I ≤ list.length (L)
// Delete the ith element of L and return it with e, the length of L minus 1
int ListDelete(SqList *L,int i,ElemType *e){
    int k;
    if (L->length==0)/* The linear table is empty */
        return ERROR;
    if(i<1|| i>L->length)/* Delete position is not correct */
        return ERROR;
    *e=L->data[i- 1];
if(i<L->1ength){/* If delete is not the last position */ 
    for(k = I; k<L->length; k++)/* will remove the position of the succeeding elements forward */
        L->data[k- 1]=L->data[k]; } L - > length -;return OK;
}

Copy the code

Code analysis:

The key step of the deletion algorithm is to traverse from the deleted element position to the last element position, move them forward one position respectively, and then delete the ith element. The average algorithm time for deletion is also O(n), since deletion requires the same movement as insertion before it can be performed.