Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Open a new pit and plan to update the implementation of all the code problems in the 23 King data structures.

Although the exam is generally written pseudo-code, but I am obsessive-compulsive or all the implementation of a warehouse here

Sequence list structure

It’s used directly on the exam, and it doesn’t usually ask you to write structures

#define MaxSize 50

typedef struct {
  ElemType data[MaxSize];
  int length;
}SqList; 
Copy the code

Then, 1

  • Violent solution is the general cycle, cycle once not good, come twice, twice not three times…
  • Time complexity O(n), space complexity O(1)
int del_min(SqList &list) {
  if (list.length == 0) {
    cout << "Error!" << endl;
    return - 1;
  }

  // 1. Assume element 0 is the smallest
  int min = list.data[0]; 
  int pos = 0;

  // 2. Loop to find the smallest element and record its position, starting at 1
  for (int i = 1; i < list.length; i++) {
    if(list.data[i] < min) { min = list.data[i]; pos = i; }}// 3. Delete the smallest element and replace it with the last element
  list.data[pos] = list.data[list.length - 1];
  list.length--; 

  return min;
}
Copy the code

Then, 2

  • Violence is a whole array, iterating from the end of the array into the new array
  • For space O(1), loop from the beginning to the middle, swapping the head and tail elements
  • Even or odd elements, going to the middle, both< length/2, because if the length is 4 or 5, the loop stops at index 1, and the middle element (index 2) doesn’t need to move at index 5.
  • Time complexity O(n)
void reverse(SqList &list) {
  for (int i = 0; i < list.length / 2; i++) {
    // Instead of swap(), you can define an auxiliary variable to swap
    swap(list.data[i], list.data[list.length - 1- i]); }}Copy the code

Then, 3

  • Violence is a whole array, iterating over and putting everything that’s not equal to x into the new array
  • The time complexity O(n) and space complexity O(1) require to be solved within a cycle
  • You throw everything equal to x to the end, and then you subtract the length
  • Reverse: that is, all elements that are not equal to x are thrown in front, and the elements that are equal to x follow
void del_x(SqList &list, int x) {
  int k = 0;
  for (int i = 0 ; i < list.length ; i++) {
    // 1. Put all the values to save first
    if (list.data[i] != x) {
      list.data[k++] = list.data[i];
    }
  }
  // 2. Discard the following elements directly
  list.length = k;
}
Copy the code
  • One loop -> dual Pointers
  • Like quicksort, moving from both ends to the middle, swapping x’s on the left with non-x’s on the right
// It's too much trouble
void del_x_2(SqList &list, int x) {
  int i = - 1, j = list.length, k = 0;
  while (i < j) {
    while(list.data[++i] ! = x);while (list.data[--j] == x) k++;
    if (i < j) {
      swap(list.data[i], list.data[j]);
      k++;
    }
  }
  list.length -= k;
}
Copy the code