数据结构、算法及应用 张宪超 主编——第二章课后习题答案

此篇文章是我根据课本上的知识，同时结合一些互联网上的相关信息，自己整理作答。可能会存在算法不够好，甚至存在错误的情况。请大家理解，同时希望大家在发现错误的时候，能够在评论区留下自己的意见，大家共同学习，共同进步。谢谢！

1. 线性表可用于顺序表或链表存储，试问：

（1）两种存储表示各有哪些主要优缺点？

（2）如果有 n 个表同时并存，并且在处理中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？

（3）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应采用哪种存储表示？为什么？

答案：

（1）

顺序表：

优点：顺序表的存储密度高，在存储上使用相邻的内存空间，访问速度非常快，时间复杂度是 o(1)。

缺点：顺序表的大小固定，不支持动态扩展。数组的插入和删除的时间复杂度高，除了在末尾插入和删除外，其他位置均需要移动元素，平均时间复杂度为 o(n)。

链表：

优点：链表可以方便的动态申请内存，如果不考虑物理内存的限制，链表可以做到无限大。链表的插入和删除操作仅需维护节点和其前驱与后继的关系，不需要移动元素，插入和删除效率高。

缺点：使用额外的空间来存储前后链表前后元素之间“相邻”的关系。链表的访问不是随机的，除了首尾元素，其他元素的访问均需要顺着链表的头节点通过指针一个一个的检索，访问元素的平均时间复杂度为o(n)。

（2）

因为表的长度会动态变化，所以适合使用链表，因为链表支持动态的空间变化。

（3）

由于表的总数稳定，而且很少进行插入和删除操作，同时要求快速的存取表中的元素，因此适合使用顺序表。

2. 采用顺序表的操作，实现以下函数：

（1）从顺序表中删除具有最小值的元素并由函数返回被删除的元素的值，空出的位置由最后一个元素填补。

（2）从顺序表中删除具有给定值 x 的所有元素。

（3）从顺序表中删除其值在给定值 s 与 t 之间（s < t）的所有元素。

答案：

（1）直接实现为顺序表的成员函数，顺序表的类的定义请参考课本：

template 
void ArrayList::RemoveMinimum() 
{
    int MinIndex = 0;
    for (int i = 1; i < curLen; ++i)     {
        if (arrayList[i] < arrayList[MinIndex]) 
        {
            MinIndex = i;
        }
    }
    // 如果最小值的位置不是最后位置，将值最小的位置的值用最后的值替换，
    // 同时将顺序表的长度减 1
    if (MinIndex != curLen - 1)
    {
        arrayList[MinIndex] = arrayList[--curLen];
    }
    // 最小值就是最后位置，直接将数组的大小减 1
    else {
        curLen--;
    }
}

（2）直接实现为顺序表的成员函数

template 
void ArrayList::RemoveSpecialValue(T x) 
{
    for (int i = 0; i < curLen; ++i)
    {
        if (arrayList[i] == x) 
        {
            // 最后一个元素，没有补充的位置，直接删除
            if (i == curLen - 1) 
            {
                curLen--;
            }
            // 将当前的值为 x 的位置的值替换为最后的值，同时将顺序表的长度减 1，
            // 注意：最后元素的值得检查一下，如果也是 x，就得一直向前追溯，直到
            // 不是 x，或者追溯到当前的元素
            while (arrayList[curLen - 1] == x && curLen != i + 1) 
            {
                curLen--;
            }
            // 如果没有追溯到当前元素，使用最后一个不是 x 的元素替换当前的元素
            if (curLen != i + 1)
            {
                arrayList[i] = arrayList[--curLen];
            }
            // 如果追溯到了当前元素，直接将 curLen - 1
            else
            {
                curLen--;
            }
        }
    }
}

（3）直接实现为顺序表的成员函数，江湖规矩，前闭后开 [s, t)

template 
void ArrayList::RemoveBetween(T s, T t) 
{
    for (int i = 0; i < curLen; ++i)
    {
        // 如果当前元素位于 s 和 t 之间
        if (arrayList[i] >= s && arrayList[i] < t) 
        {
            // 最后一个元素，没有补充的位置，直接删除
            if (i == curLen - 1) 
            {
                curLen--;
            }
            // 将当前的值位于 s 和 t 之间的位置替换为最后的值，同时将顺序表的长度减 1，
            // 注意：最后元素的值得检查一下，如果也位于 s 和 t 之间，就得一直向前追溯，
            // 直到不位于 s 和 t 之间，或者追溯到当前的元素
            while (arrayList[curLen - 1] >= s && arrayList[curLen -1] < t && curLen != i + 1) 
            {
                curLen--;
            }
            // 如果没有追溯到当前元素，使用最后一个不位于 s 和 t 之间的元素替换当前的元素
            if (curLen != i + 1)
            {
                arrayList[i] = arrayList[--curLen];
            }
            // 如果追溯到了当前元素，直接将 curLen - 1
            else
            {
                curLen--;
            }
        }
    }
}

3. 给定一个不带头节点的单链表，写出将链表倒置的算法。

template 
void LinkList::reverse() {
  // 由于是不带头节点的链表，当链表中没有元素时，链表的 head 和 tail 均是空指针
  // 这种情况下直接返回，不用处理了
  if (head == NULL)
    return;
  // 如果是链表不是空，此时如果 head 和 tail 指向相同，证明链表只有一个节点，此时
  // 倒置的链表和不倒置是完全一致的（此种情况可以和上面的情况合并统一处理，这里分开
  // 是为了使不同的情况更加清晰）
  if (head == tail)
    return;
  
  // 下面的代码的作用和上面两个 if 语句的作用一致
  // if (head == tail)
  //   return;
  prevPtr = head;
  currPtr = head->link;
  // 当前处理节点的下一节点
  LinkNode *nextPtr;
  // 头节点变成尾节点
  head->link = NULL;
  tail = head;
  while (currPtr != NULL) {
    nextPtr = currPtr->link;
    currPtr->link = prevPtr;
    prevPtr = currPtr;
    currPtr = nextPtr;
  }
  head = prevPtr;
}

4. 已知 head 为单链表的表头指针，链表中存储的都是整型数据，实现下列运算的递归算法：

（1）求链表中的最大值。

（2）求链表中的节点个数。

（3）求所有整数的平均值。

答案：

（1）

int getMaximumValue(LinkNode *head) {
  if (head == NULL) {
    return -1;
    std::cout << "输入的链表是空链表，请检查输入!" << std::endl;
  }
  int value = head->data;
  if (head->link == NULL) {
    return value;
  }
  return value > getMaximumValue(head->link) ? value : getMaximumValue(head->link);
}

（2）

int getNodeNum(LinkNode *head) {
  if (head == NULL)
    return 0;
  if (head->link == NULL) {
    return 1;
  }
  return getNodeNum(head->link) + 1;
}

（3）

void getNodeAveValue(LinkNode *head, int &sum, int &num) {
  if (head == NULL) {
    return;
    std::cout << "输入的链表是空链表，请检查输入!" << std::endl;
  }
  sum += head->data;
  num += 1;
  if (head->link == NULL) {
    return;
  }
  getNodeAveValue(head->link, sum, num);
}

5. 设 A 和 B 是两个单链表，其表中元素递增有序。试写一算法将 A 和 B 归并成一个按元素值递减有序的单链表 C，并要求辅助空间为 O(1)，试分析算法的时间复杂度。

// 辅助空间为 O(1)，说明只能使用常数个额外的空间来存储临时值。
// 下面的实现是我自己设计的，算法思路：
// 从两个链表各自的头节点开始，向各自的尾节点遍历，使用指针 currPtr1, nextPtr1 和
// currPtr2, nextPtr2 分别记录每个链表自己当前处理的节点和下一个节点，然后使用指针
// currMinNode 和 nextNodeToLink 分别记录未加入到逆序链表中的最小值节点和次小值节点
// currMinNode 初始化为链表中最小值节点，nextNodeToLink 初始化为 NULL，在 
// nextNodeToLink 获取新值之前，先将 currMinNode 的 link 设置为 nextNodeToLink;
// 然后将 nextNodeToLink 设置为两个链表中的次小值，并将 nextNodeToLink 的 link 设
// 置为 currMinNode。循环重复上面的过程，直到有一个链表到达结尾。此时，链表的情况：
// 可能链表 1 和 链表 2 都处理完了，可能链表 1 没处理完链表 2 处理完了，可能链表 2 
// 没处理完链表 1 处理完了，因此还得处理可能没处理完的链表，将其中剩余的元素逆序链接
// 在刚才已经处理的链表上面。
// 算法时间和空间复杂度分析：
// 时间复杂度：算法遍历 2 个链表 1 次， 假设链表的长度分别为 m 和 n，那么时间复杂度
// 为 O(m + n)
// 空间复杂度：没有使用额外的辅助空间，因此空间复杂度为 O(0)
template 
void mergeLinkListAndReverse(LinkList *list1, LinkList *list2,
                             LinkList *list3 ) {
  // 如果链表 1 是空的，将链表 2 倒置一下就行
  if (list1->getHead() == NULL) {
    list2->reverse();
    list3->setHead(list2->getHead());
    list3->setTail(list2->getTail());
    return;
  }
  // 如果链表 2 是空的，将链表 1 倒置一下就行
  if (list2->getHead() == NULL) {
    list1->reverse();
    list3->setHead(list1->getHead());
    list3->setTail(list1->getTail());
    return;
  }
  LinkNode *head3 = NULL, *tail3 = NULL; // 新的链表的头指针和尾指针
  LinkNode *currMinNode = NULL;  // 当前最小的链表节点
  LinkNode *nextNodeToLink = NULL; // 即将加入到新链表中的下一个元素
  LinkNode *currPtr1, *nextPtr1, *currPtr2,
              *nextPtr2;  // 链表 1 和 链表 2 的当前节点以及下一个节点的指针
  currPtr1 = list1->getHead();
  currPtr2 = list2->getHead(); // 标记位，将最小的节点标记为尾节点
  while (currPtr1 != NULL && currPtr2 != NULL) {
    nextPtr1 = currPtr1->link;
    nextPtr2 = currPtr2->link;
    if (currPtr1->data <= currPtr2->data) {
      currMinNode = currPtr1;
      currPtr1 = nextPtr1;
    }
    else {
      currMinNode = currPtr2;
      currPtr2 = nextPtr2;
    }
    // 如果两个链表都没有后续节点了，当前的节点就是融合链表的最头节点
    if (currPtr1 == NULL && currPtr2 == NULL) {
      nextNodeToLink->link = currMinNode;
      head3 = currMinNode;
      break;
    } else if (currPtr1 == NULL) {
    // 如果链表 1 没有后续节点了但是链表 2 有，直接下一个节点就是链表 2 的节点
      currMinNode->link = nextNodeToLink; // 当前最小的节点的 Link 是上一次的 nextNodeToLink
      if (nextNodeToLink == NULL) { // 第一个链接的是尾节点
        tail3 = currMinNode;
      }
      nextNodeToLink = currPtr2;
      currPtr2 = nextPtr2;
      nextNodeToLink->link = currMinNode;
    } else if (currPtr2 == NULL) {
    // 如果链表 2 没有后续节点了但是链表 1 有，直接下一个节点就是链表 1 的节点
      currMinNode->link = nextNodeToLink; // 当前最小的节点的 Link 是上一次的 nextNodeToLink
      if (nextNodeToLink == NULL) { // 第一个链接的是尾节点
        tail3 = currMinNode;
      }
      nextNodeToLink = currPtr1;
      currPtr1 = nextPtr1;
      nextNodeToLink->link = currMinNode;
    } else {
    // 链表 1 和 链表 2 都有充足的节点，谁的当前节点小就是谁下一个链接进来
      if (currPtr1->data <= currPtr2->data) {
        currMinNode->link = nextNodeToLink; // 当前最小的节点的 Link 是上一次的
        if (nextNodeToLink == NULL) { // 第一个链接的是尾节点 nextNodeToLink
          tail3 = currMinNode;
        }
        nextNodeToLink = currPtr1;
        currPtr1 = nextPtr1;
        nextNodeToLink->link = currMinNode;
      } else {
        currMinNode->link = nextNodeToLink; // 当前最小的节点的 Link 是上一次的 nextNodeToLink
        if (nextNodeToLink == NULL) { // 第一个链接的是尾节点
          tail3 = currMinNode;
        }
        nextNodeToLink = currPtr2;
        currPtr2 = nextPtr2;
        nextNodeToLink->link = currMinNode;
      }
    }
    head3 = nextNodeToLink;
  }
  
  // 前面的 while 循环处理完之后可能还有一条链没有处理完成，此时再处理这条链，将
  // 这条链上的剩余元素直接逆序就行
  while (currPtr1 != NULL) {
    nextPtr1 = currPtr1->link;
    currMinNode = currPtr1;
    currPtr1 = nextPtr1;
    currMinNode->link = nextNodeToLink;
    nextNodeToLink = currMinNode;
    head3 = nextNodeToLink;
  }
  while (currPtr2 != NULL) {
    nextPtr2 = currPtr2->link;
    currMinNode = currPtr2;
    currPtr2 = nextPtr2;
    currMinNode->link = nextNodeToLink;
    nextNodeToLink = currMinNode;
    head3 = nextNodeToLink;
  }
  // 需要将原始的链表对象清除，不然会重复释放同一片内存区域，如果实现了 list 的 clear 函数，可以调用之
  list1->setHead(NULL);
  list2->setHead(NULL);
  list1->setTail(NULL);
  list2->setTail(NULL);
  list3->setHead(head3);
  list3->setTail(tail3);
}

6. 设 ha 和 hb 分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许由重复的数据。

// 两个带头节点的非递减单链表合并成一个非递减单链表
template 
void mergeLinkListWithHead(LinkList *list1, LinkList *list2, LinkList *list3) {
  LinkNode *hc = NULL, *tc = NULL;  // 新链表的头节点，尾节点
  LinkNode *ha = list1->getHead();
  LinkNode *hb = list2->getHead();
  LinkNode *currMinNode = NULL;
  LinkNode *nextNodeToLink = NULL;

  if (ha->link == NULL) {
    hc = hb;
    tc = hb;
  }
  if (hb->link == NULL) {
    hc = ha;
    tc = ha;
  }
  LinkNode *curr1 = ha->link;
  LinkNode *curr2 = hb->link;
  LinkNode *next1 = NULL, *next2 = NULL;
  while (curr1 != NULL && curr2 != NULL) {
    next1 = curr1->link;
    next2 = curr2->link;
    if (curr1->data <= curr2->data) {
      currMinNode = curr1;
      if (nextNodeToLink == NULL) { // 如果下一个要链接的节点为空，证明上面的最小节点是融合链表中的第一个节点
        hc = currMinNode;
      } else { // 否则，上一次最后融进链表的节点的后继是当前最小的节点
        nextNodeToLink->link = currMinNode;
        tc = currMinNode;
      }
      curr1 = next1;
    } else {
      currMinNode = curr2;
      if (nextNodeToLink == NULL) { // 如果下一个要链接的节点为空，证明上面的最小节点是融合链表中的第一个节点
        hc = currMinNode;
      } else { // 否则，上一次最后融进链表的节点的后继是当前最小的节点
        nextNodeToLink->link = currMinNode;
      }
      curr2 = next2;
    }
    if (curr1 == NULL && curr2 == NULL) {  // 如果 list1 和 list2 都处理完了，当前最小的节点就是尾节点
      tc = currMinNode;
      break;
    } else if (curr1 == NULL) {
      nextNodeToLink = curr2;
      curr2 = next2;
      currMinNode->link = nextNodeToLink;
      tc = nextNodeToLink;
    } else if (curr2 == NULL) {
      nextNodeToLink = curr1;
      curr1 = next1;
      currMinNode->link = nextNodeToLink;
      tc = nextNodeToLink;
    } else {
      if (curr1->data <= curr2->data) {
        nextNodeToLink = curr1;
        curr1 = next1;
        currMinNode->link = nextNodeToLink;
        tc = nextNodeToLink;
      } else {
        nextNodeToLink = curr2;
        curr2 = next2;
        currMinNode->link = nextNodeToLink;
        tc = nextNodeToLink;
      }
    }
  }
  // 前面的 while 循环处理完之后可能还有一条链没有处理完成，此时再处理这条链，将
  // 当前的 tail 直接 link 到剩余的节点上就好
  if (curr1 != NULL) {
    tc->link = curr1;
    tc = list1->getTail();
  }
  if (curr2 != NULL) {
    tc->link = curr2;
    tc = list2->getTail();
  }
  // 融合之后的链表应该也有头节点
  if (ha->link == hc) {
    hc = ha;
    // 需要释放另一个头节点的空间
    delete hb;
  } else {
    hc = hb;
    // 需要释放另一个头节点的空间
    delete ha;
  }
  // 需要将原始的链表对象清除，不然会重复释放同一片内存区域，如果实现了 list 的 clear 函数，可以调用之
  list1->setHead(NULL);
  list2->setHead(NULL);
  list1->setTail(NULL);
  list2->setTail(NULL);
  list3->setHead(hc);
  list3->setTail(tc);
}

7. 设双链表表示的线性表 L=(a1, a2, ...,an)，试写一个时间复杂度为 O(n) 的算法，将 L 改造为 L=(a1,a3,...,an,...,a4,a2)。

// 算法的思路：
// 使用 3 个指针 curr1, next1 和 crossNext 分别指向当前节点，下一节点和下下一个节点，
// 然后当前节点和下下节点从头向尾链接，下一节点从尾向头链接，然后将当前节点移动到下下节点
// 然后重复上面的操作。但是存在节点总数是奇数和偶数的情况，如果是偶数，上面的过程就能够
// 完美链接好所有节点，但是如果是奇数的话，最中间节点的前驱和后继会存在没有连接好的情况，
// 此时需要单独处理一下该节点
template 
void reformDLLLinkList(DLLLinkList *list) {
  // 如果是空的链表，不用改造
  if (list->getHead() == NULL)
    return;
  DLLNode *curr1 = list->getHead();          // 当前正在处理的指针
  DLLNode *next1 = list->getHead()->next;    // 当前正在处理的指针的下一位置
  DLLNode *crossNext = NULL;      // 当前正在处理的指针的下两位置
  // 如果只有一个节点，不用改造
  if (next1 == NULL)
    return;
  DLLNode *front = NULL;   // 链表前端已经改造好的位置的指针
  DLLNode *back = NULL;    // 链表后端已经改造好的位置的指针
  while (curr1 != NULL && next1 != NULL) {
    crossNext = next1->next;
    curr1->prev = front;  // 当前正在处理的指针的前驱是上一个已经处理好的前端节点
    if (crossNext != NULL) {
      curr1->next = crossNext;
    }
    next1->next = back;
    if (back != NULL) {
      next1->next->prev = next1;
    } else {
      list->setTail(next1);   // 第一个链接到末尾的节点是尾节点
    }
    front = curr1;
    back = next1;
    curr1 = crossNext;
    if (curr1 != NULL) {
      next1 = curr1->next;
    }
  }
  // 链表节点是奇数的情况
  if (curr1 != NULL) {
    curr1->next = back;
    curr1->prev = front;
    back->prev = curr1;
  }
}

8. 已知有一个循环双链表，p 指向第一个元素值为 x 的节点，设计一个算法从改循环双链表中删除 *p 节点。

// 循环双链表的构造使用双链表类，然后将尾节点的后继节点和
// 头节点的前驱节点修改一下，形成循环双链表，实现为成员函数
// 方便操作
template 
void DLLLinkList::deleteSpecificNode(const T item) {
  if (head == NULL)
    return;
  if (head->next == head) {
    if (head->data == item) {
      delete head;
      head = NULL;
      tail = NULL;
    } else {
      std::cout << "No elements valued " << item << " in List" << std::endl;
    }
    return;
  }
  DLLNode *curr = head;
  while (true) {
    prevPtr = curr->prev;
    currPtr = curr->next;
    if (curr->data == item) {
      prevPtr->next = curr->next;
      currPtr->prev = curr->prev;
      if (curr == head)
        head = currPtr;
      if (curr == tail)
        tail = prevPtr;
      delete curr;
      curr = NULL;
      return;
    }
    curr = curr->next;
    if (curr == head) {
      std::cout << "No elements valued " << item << " in List" << std::endl;
      return;
    }
  }
}

9. 内存中一片连续空间（不妨假设地址从 1 到 m），提供给两个栈 S1 和 S2 使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

答：S1 以地址 1 为栈底， S2 以地址 m 为栈底。S1 的 size 为 (top)，S2 的 size 为(m - top + 1)。S1 的入栈操作是 top++, 出栈操作时 top--；S2 的入栈操作是 top--，出栈操作是 top++。S1 的栈空标志是 top == 0; S2 的栈空标志是 top == m + 1。S1和 S2 的栈满标志是 S1.top + 1 == S2.top。

10. 简述线性表、栈和队列的异同？

答：

不同之处：线性表具有唯一的头元素、尾元素，除了头元素和尾元素外，其他元素均有一个直接前驱和后继；栈是一种限制访问端口的线性表，左右的操作都限定在线性表的一端进行。队列也是一种限制访问端口的线性表，元素只能从表的一端插入，从表的另一端删除。

相同之处： 3 种数据结构本质上都是线性表，只是访问方式和操作有不同的限制。它们都有顺序存储和链式存储两种存储方式。

11. 设有一个数列的输入顺序为 123456，若采用栈结构，并以 A 和 D 分别表示进栈和出栈操作，试问通过进栈和出栈操作的合法序列有多少种？能否得到输出顺序为 325641 的序列？能否得到输出顺序为 154623 的序列？

答：前面的 5 个输入都对应着两种操作（进栈和出栈），会影响后续的输出序列，最后一个的操作不会影响其他的，所以合法序列有 2^5 = 32 种。

325641 是合法序列。

154623 是非法序列。

12. 设计一个算法把一个十进制整数转换为二至九之间任意进制数输出。

#include 
​
// 递归算法
void baseConverter(int dNum, int base) {
  int rem = dNum % base;
  dNum = dNum / base;
  if (dNum == 0) {
    std::cout << rem;
    return;
  }
  baseConverter(dNum, base);
  std::cout << rem;
}
​
// 循环算法
void baseConverter2(int dNum, int base) {
  int rem;
  int power = 1;
  int result = 0;
  while (dNum != 0) {
    rem = dNum % base;
    dNum /= base;
    result = result + rem * power;
    power *= 10;
  }
  std::cout << result << std::endl;
}
​
int main() {
  int num = 100;
  int base = 8;
  baseConverter(num, base);
  std::cout << std::endl;
  baseConverter2(num, base);
  return 0;
}

13. 假设表达式中允许包含 3 种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。

bool BracketsMatchCheck(const char *expr) {
  ArrayStack stack1(100);
  const char *ch = expr;
  char topSymbol;
  while (*ch != '') {
    switch (*ch) {
    case '{':
    case '[':
    case '(':
      stack1.Push(*ch);
      break;
    case ')':
      if (stack1.Pop(topSymbol)) {
        if (topSymbol == '(')
          break;
      }
      return false;
    case ']':
      if (stack1.Pop(topSymbol)) {
        if (topSymbol == '[')
          break;
      }
      return false;
    case '}':
      if (stack1.Pop(topSymbol)) {
        if (topSymbol == '{')
          break;
      }
      return false;
    default:
      return false;
    }
    ++ch;
  }
  if (stack1.IsEmpty()) {
    return true;
  }
  return false;
}

14. 由用户输入 n 个 10 以内的数，每输入 i(0<= i <= 9)，就把它插入到第 i 号队列中。最后把 10 个队列中非空队列，按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。

#include "LinkQueue.h"
#include 
​
int main() {
  LinkQueue queue1(0);
  std::vector> vec(10, queue1);
  int i, n = 10;
  while(n > 0) {
    std::cin >> i;
    vec[i].EnQueue(i);
    n--;
  }
  for (const auto &qItem : vec) {
    if (!qItem.IsEmpty()) {
      auto index = qItem.GetFront();
      while (index != NULL) {
        queue1.EnQueue(index->data);
        index = index->link;
      }
    }
  }
  
  std::cout << "合并后的队列是:" << std::endl;
  for (auto index = queue1.GetFront(); index != NULL; index = index->link) {
    std::cout << index->data;
    if (index != queue1.GetRear()) {
      std::cout << "->";
    }
  }
  std::cout << std::endl;
  return 0;
}

15. 设计一个环形队列，用 front 和 rear 分别表示对头和队尾指针，另外用一个 tag 表示队列是空（0）还是不空（1），这样就可以用 front == rear 作为队满的条件。要求设计队列的相关基本运算算法。

template 
class ArrayQueue : public Queue {
private:
  int maxSize;                  // 存放队列数组的大小
  int front;                    // 表示队头所在位置的下标
  int rear;                     // 表示对为所在位置的下标
  int tag;                      // 当 front == rear 时，
                                // 如果队列是空（0），如果不空（1）
  T *queue;                     // 存放类型为 T 的队列元素的数组
  
public:
  ArrayQueue(int size) {        // 创建队列的实例
    maxSize = size;         // 多出一个空间，区分队列空与满
    queue = new T[maxSize];
    front = rear = 0;
    tag = 0;
  }
  
  ~ArrayQueue() {               // 析构函数
    delete [] queue;
  }
  
  void Clear() {                // 清空队列
    front = rear;
    tag = 0;
  }
  
  bool EnQueue(const T item) {  // item 入队，插入队尾
    if (rear % maxSize == front && tag ==1) {
      std::cout << "队列已满，溢出" << std::endl;
      return false;
    }
    queue[rear] = item;
    rear = rear % maxSize;
    if (front == rear)
      tag = 1;
    return true;
  }
  
  bool DeQueue(T &item) {       // 返回队头元素，并删除该元素
    if (front == rear) {
      std::cout << "队列为空" << std::endl;
      return false;
    }
    item = queue[front];
    front = front % maxSize;
    if (front == rear)
      tag = 0;
    return true;
  }
  
  bool GetFront(T &item) {      // 返回队头元素，但不删除
    if (front == rear) {
      std::cout << "队列为空" << std::endl;
      return false;
    }
    item = queue[front];
    return true;
  }
};

16. 已知 t = "abcaabbcabcaabdab"，求模式串的 next 数组值。

// StringUtil.h
​
#include 
#include 
​
int *Next(std::string P) {
  int m = P.length();                 // 模式 P 的长度
  assert(m > 0);                      // 若 m = 0，则退出
  int *N = new int[m];                // 在动态存储区开辟新的数组
  assert(N != 0);                     // 检查数组是否开辟成功
  N[0] = 0;
  for (int i = 1; i < m; i++) {
    int k = N[i - 1];
    while (k > 0 && P[i] != P[k])
      k = N[k - 1];
    if (P[i] == P[k])
      N[i] = k + 1;
    else
      N[i] = 0;
  }
  return N;
}
​
// Test.cpp
​
#include "StringUtil.h"
#include 
​
int main() {
  std::string SrcStr = "abcaabbcabcaabdab";
  int *N = Next(SrcStr);
  int *index = N;
  for (int i = 0; i < sizeof(N) - 1; ++i) {
    std::cout << *index << "t";
    ++index;
  }
  std::cout << *index << std::endl;
  return 0;
}
​
// 输出结果：0   0   0   1   1   2   0   0

17. 设计Strcmp(s, t) 算法，实现两个字符串 s 和 t 的比较。

int Strcmp(const char *s, const char *t) {
  while (*s != '' && *t != '') {
    if (*s > *t)
      return 1;
    else if (*s < *t)
      return -1;
    ++s;
    ++t;
  }
  if (*s == '' && *t != '')
    return -1;
  else if (*s != '' && *t == '')
    return 1;
  return 0;
}

18. 设计一个算法，在串 str 中查找子串 substr 最后一次出现的位置（不能使用 STL）。

// 更改课本上 KMP 算法的思路，第一次匹配成功之后不退出，继续匹配，
// 直到匹配失败，此时输出最后一次匹配成功的位置
#include "StringUtil.h"
#include 
​
int KMPStrMatching(std::string T, std::string P, int *N, int startIndex) {
  int lastIndex = T.length() - P.length();
  if (lastIndex - startIndex < 0)        // 若 startIndex 过大，则无法匹配成功
    return (-1);
  int i;                                 // 指向 T 内部字符的游标
  int j = 0;                             // 指向 P 内部字符的游标
  int lastMatch = -1;                    // 记录最后一次匹配的位置
  for (i = startIndex; i < T.length(); ++i) {
    while (P[j] != T[i] && j > 0)
      j = N[j - 1];
    if (P[j] == T[i])                    // 当 P 的第 j 位和 T 的第 i 位相同时，则继续
      ++j;
    if (j == P.length()) {
      lastMatch = i - j + 1;             // 匹配成功，更新最后一次匹配成功的位置
      j = 0;
    }              
  }
  return lastMatch;
}
​
​
int main() {
  std::string Target = "abcdacccabcbeababceabcdaeeedandwaeabcdaeedabcd";
  std::string Pattern = "abcda";
  int *N = Next(Pattern);
  int result = KMPStrMatching(Target, Pattern, N, 0);
  if (result == -1) {
    std::cout << "匹配失败，目标串中不存在模式串" << std::endl;
  } else {
    std::cout << "模式串最后一次在目标串中出现的位置是: " << result << std::endl;
  }
  return 0;
}
​
// 输出结果：模式串最后一次在目标串中出现的位置是: 34