王道2.3.7综合应用题

目录

• 王道2.3.7综合应用题
  • 1
  • 2
  • 3
  • 4
  • 5

王道2.3.7综合应用题

1

设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点

void delx(LinkList &L, ElementType x) {
    if (L == nullptr) return;
    if (L->data != x) delx(L->next, x);
    else {
        p = L;
        L = L->next; // note
        delete p;
        delx(L, x);
    }
}

错误理解：当前结点data==x，立即删除，然后递归下一个结点，造成被删结点前驱没有指向被删结点的后继，从而造成断链

正确理解：没有断链。比如2->3->4，要删除的是3，当遍历到2的时候，发现不是要删除的结点，执行delx(L->next, x)，注意L是引用类型，相当于此处进入下一个递归之后，L就引用了L->next，伪代码表示就是2->next，然后开始处理结点3，发现3是要删除的结点，并执行L=L->next，则相当于执行2->next=2->next->next，即做到了将被删除结点的前驱指向被删除结点的后继

2

在带头结点的单链表L中，删除所有值为x的结点，释放其空间，假设值为x的结点不唯一，试编写算法实现上述操作

相当于上一题的带头结点并且不要求递归

void delx(LinkList &L, ElementType x) {
    LNode *p = L->next, *pre = L;
    while (p != nullptr) {
        if (p->data == x) {
            pre->next = p->next;
            delete p;
            p = pre.next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

3

设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值

• 逆置链表（把指针指向前驱）

  void printRev(LinkList &L) {
      // reverse
      LNode *p = L->next, *q;
      L->next = nullptr;
      while (p != nullptr) {
          q = p->next;
          p->next = L->next;
          L->next = p;
          p = q;
      }
      // print
      p = L->next;
      while (p != nullptr) {
          cout << p->data;
          p = p->next;
      }
  }
  

• 栈

  void printStack(LinkList &L) {
      stack<LNode*> s;
      auto p = L->next;
      while (p != nullptr) {
          s.push(p);
          p = p->next;
      }
      while (!s.empty()) {
          cout << s.top();
          s.pop();
      }
  }
  

• 递归

  void print(LinkList &L) {
      print_(L->next);
  }
  
  void print_(LinkList L) {
      if (L != null) print_(L->next);
      cout << L->data;
  }
  

4

试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小结点是唯一的）

void delmin(LinkList &L) {
    if (L->next == nullptr) return;
    LNode *min = L->next, *pre = L, *p = L;
    while (p->next != nullptr) {
        if (p->next->data < min->data) {
            pre = p;
            min = p->next;
        }
        p = p->next;
    }
    pre->next = min->next;
    delete min;
}

5

就地逆置带头结点的单链表（空间复杂度O(1)）

void printRev(LinkList &L) {
    LNode *p = L->next, *q;
    L->next = nullptr;
    while (p != nullptr) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}