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

I plan to update the realization of all the code exercises of 23 Kingway data structure after class. Although the exam is generally written in pseudo-code, I still realized all of them because of obsessive-compulsive. The warehouse is here

  • The linear table

Then, 6

  • An ordered list ➡️ arranges the same elements together
  • Violence, open up a new array, put the different elements in
  • You need two Pointers to operate on each array
  • Time complexity O(n), space complexity O(n)
void del_same(SqList &list) {
  if (list.length == 0) return;
  
  // 1. Open an array
  SqList copied = list;
  copied.data[0] = list.data[0];

  // 2. Store the different elements
  int k = 0;
  for (int i = 1; i < list.length; i++) {
    if (list.data[k] != copied.data[i]) {
      copied.data[++k] = list.data[i];
    }
  }

  // 3. New for old
  copied.length = k + 1;
  list = copied;
}
Copy the code
  • If you think about it, you don’t really need two arrays, just two Pointers
  • The first one stores, the second one judges
  • Time complexity O(n), space complexity O(1)
void del_same2(SqList &list) {
  if (list.length == 0) return;

  int k = 0;
  for (int i = 1; i < list.length; i++) {
    if(list.data[k] ! = list.data[i]) { list.data[++k] = list.data[i]; } } list.length = k +1;
}
Copy the code

2.2.4, 7

  • This kind of question is too typical, merge ordered order list and merge ordered linked list, suggest full recitation hh
  • Loop, remove the smaller of the two and place it in the results table
  • If there’s anything left over from the last table, add everything left over to the results table
  • Time complexity O(n), space complexity O(n)
SqList merge(SqList A, SqList B) {
  SqList C;
  if (A.length + B.length > MaxSize) {
    cout << "ERROR!" << endl;
    return C;
  }

  int i = 0, j = 0, k = 0;
  // 1. Pairwise comparison, small save result table
  while (i < A.length && j < B.length) {
    if (A.data[i] <= B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  }

  // 2. Add the rest to the result table, and only one of the two loops will run
  while (i < A.length) 
    C.data[k++] = A.data[i++];
  while (i < B.length) 
    C.data[k++] = B.data[j++];

  // 3. Return the result table
  C.length = k;
  return C;
}
Copy the code
  • I’m going to add merge sort
void merge_sort(int l, int r) {
  if (l >= r) return;

  int mid = (l+r) >> 1;
  merge_sort(l, mid);
  merge_sort(mid+1, r);		

  int k = 0, i = l, j = mid+1;
  while (i <= mid && j <= r) {
    if (q[i] <= q[j]) 
      tmp[k++] = q[i++];
    else 
      tmp[k++] = q[j++];
  }
  
  while (i <= mid) 
    tmp[k++] = q[i++];
  while (j <= r) 
    tmp[k++] = q[j++];

  for (i = l, j = 0; i <= r; i++, j++) 
    q[i++] = tmp[j++];
}
Copy the code