Make writing a habit together! This is the 14th 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 14/14
  • The list of 7/25

2.3.7, 6

  • Take the list data and sort it in an array, and then put the sorted numbers back into the list
  • Typical space swap time, sorting time O(nlogn), space complexity O(n)
void sortList(LinkList &L, int len) {
  // 1. Copy the linked list data into the array
  LNode *head = L->next;
  int a[len], i = 0;
  while(head ! =NULL) {
    a[i++] = head->data;
    head = head->next;
  }

  / / 2. Sort
  sort(a, a+len);

  // 3. Copy the sorted array back to the list
  head = L->next, i = 0;
  while(head ! =NULL) { head->data = a[i++]; head = head->next; }}Copy the code
  • Insert sort, first construct an ordered list pre with only one node
  • The rest of the P-linked list can be inserted separately
  • Time complexity O(n2), space complexity O(1)
void sortList2(LinkList &L) {
  LNode *p = L->next, *pre;
  LNode *q = p->next;
  p->next = NULL;     // 1. Build an ordered linked list with only one node
  p = q;

  // 2
  while(p ! =NULL) {
    q = p->next;
    pre = L;
    
    // Find the ordered position
    while(pre->next ! =NULL && pre->next->data < p->data) {
      pre = pre->next;
    }
    / / insertp->next = pre->next; pre->next = p; p = q; }}Copy the code

2.3.7, 7

  • This problem is very simple, directly through one by one check, do not meet the deletion
  • Double pointer, delete must have its precursor pointer
  • Time complexity O(n), space complexity O(1)
void delRange(LinkList &L, int min, int max) {
  LNode *p = L->next, *pre = L;

  while(p ! =NULL) {
    if (p->data > min && p->data < max) {
      // Delete within the range
      pre->next = p->next;
      free(p);
      p = pre->next;
    } else {
      // Continue traversing if not in rangepre = pre->next; p = p->next; }}}Copy the code