c++ - C++ 数组队列实现方法错误
问题描述
我正在尝试使用 C++ 中的数组来实现队列。我一生都无法弄清楚为什么我的某些方法无法正常工作。我的 exists 方法没有找到队列中的值,而我的重复方法是复制队列的后部而不是前部。复制方法应该获取队列前面的任何内容(假设它不是空的或满的),复制该值,并将其放在队列的前面。我的会取后面的值,复制它,然后把它放在后面的一个位置。此外,Enqueue 方法未正确插入值。
#include <iostream>
#include "queue.h"
using namespace std;
static int nums[10];
int front = 0, rear = 0, sizeOfArray = 0;
int initialCapacity = 10;
int Enqueue(int num) {
if (sizeOfArray == initialCapacity) {
return -58;
}
for (int i = 0; i < initialCapacity; i++) {
if (nums[i] == num) {
return -62;
}
else {
nums[rear] = num;
rear = (rear + 1);
sizeOfArray++;
return 0;
}
}
}
int Dequeue(int& num) {
if (sizeOfArray == 0) {
return -64;
}
front = (front + 1);
sizeOfArray--;
return 0;
}
int isEmpty() {
if (sizeOfArray == 0) {
return 1;
}
else {
return 0;
}
}
int Exists(int num) {
for (int i = 0; i < sizeOfArray; i++) {
int index = (front + i);
if (nums[index] == num) {
return 1;
}
else {
return 0;
}
}
return 0;
}
void Clear(void) {
front = rear = sizeOfArray = 0;
}
void Print(void) {
for (int i = 0; i < sizeOfArray; i++) {
cout << nums[i] << " ";
}
cout << endl;
}
int Duplicate(void) {
if (sizeOfArray == 0) {
return -78;
}
if (sizeOfArray == initialCapacity) {
return -81;
}
int dupeNum;
dupeNum = nums[front];
nums[front + 1] = dupeNum;
sizeOfArray++;
return 0;
}
每当我在测试驱动程序中执行以下方法时: Enqueue 4 Enqueue 5 Exists 5 Duplicate Print
我得到这个输出:
测试 1 0 - 0 表示成功
测试 2 0 - 0 表示成功
测试 3 0 - 0 表示失败
测试 4 0 - 表示成功
4 4 0
解决方案
首先,除非front
总是为零,否则这段代码不会像您期望的那样:
int index = (front + i);
if (nums[index] == num) ...
那是因为您将尝试读取超出其末尾的数组。您需要在数组的顶端环绕,例如:
int index = (front + i) % initialCapacity;
其他问题是:
- 您的排队函数检查数组的所有元素中的重复项,即使是那些技术上未填充的元素。您应该只检查填充的值(从
front
到front + sizeOfArray
,如上所述的包装)。 - 添加项目时,它也无法正确处理环绕。在最后一个数组项中插入一个元素后,下一个值
rear
应该回零:rear = (rear + 1) % initialCapacity
。 - 在调整
front
. - 使用魔术返回码是一个坏主意,更好的方法是使用枚举(请参阅下面的代码示例)。
- 您的 dequeue 从未真正将 dequed 值放入您传入的引用参数中,这意味着它永远不会被更改。在你增加之前
front
(确保你已经修复了包装),你可以做num = nums[front]
.
可能还有其他问题,但您最大的问题是,尽管使用了某些 C++ 东西,但这并不是真正的 C++ 代码。C++ 程序员可能犯的最大错误就是成为 C+ 程序员,那个奇怪的品种在 C 和 C++ 世界之间迷失了一半:-)
您的队列实际上应该是一个类,而不仅仅是独立的函数。这样,您可以正确封装它并保护数据免受外部干扰。
我不会告诉你如何做到这一点,因为它会使这个答案变得难以忍受,但是,你越早开始这样做,你就会成为一个更好的 C++ 程序员。
例如,下面的完整程序显示了执行此操作的一种方法。我不会将其作为您自己的工作提交,但了解 C++ 程序员如何做到这一点很有用:
#include <cstdlib>
#include <memory>
template<class T>
class MyQ {
private:
size_t m_sz, m_first, m_next, m_used;
T *m_data;
public:
enum RetCode { OK, FULL, EMPTY };
MyQ(size_t sz = 10) : m_sz(sz), m_first(0), m_next(0), m_used(0), m_data(new T[sz]) {}
~MyQ() { delete [] m_data; }
enum RetCode Enqueue(T item) {
if (m_used == m_sz) return FULL;
m_data[m_next] = item;
m_next = (m_next + 1) % m_sz;
++m_used;
return OK;
}
enum RetCode Dequeue(T &item) {
if (m_used == 0) return EMPTY;
item = m_data[m_first];
m_first = (m_first + 1) % m_sz;
--m_used;
return OK;
}
};
// The class proper is above, the following is just a test harness.
#include <iostream>
int main() {
MyQ<int> x(6);
for (int i = 0; i < 7; i++) {
std::cout << "Enqueueing " << i << " returns " << x.Enqueue(i) << '\n';
}
std::cout << '\n';
int val;
for (int i = 0; i < 4; i++) {
MyQ<int>::RetCode rc = x.Dequeue(val);
if (rc == MyQ<int>::OK) {
std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
} else {
std::cout << "Dequeueing returns " << rc << '\n';
}
std::cout << "Enqueueing " << (i + 7) << " returns " << x.Enqueue(i + 7) << '\n';
}
std::cout << '\n';
for (int i = 0; i < 7; i++) {
MyQ<int>::RetCode rc = x.Dequeue(val);
if (rc == MyQ<int>::OK) {
std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
} else {
std::cout << "Dequeueing returns " << rc << '\n';
}
}
std::cout << '\n';
}
输出显示各种操作和错误情况:
Enqueueing 0 returns 0
Enqueueing 1 returns 0
Enqueueing 2 returns 0
Enqueueing 3 returns 0
Enqueueing 4 returns 0
Enqueueing 5 returns 0
Enqueueing 6 returns 1
Dequeueing returns 0, value was 0
Enqueueing 7 returns 0
Dequeueing returns 0, value was 1
Enqueueing 8 returns 0
Dequeueing returns 0, value was 2
Enqueueing 9 returns 0
Dequeueing returns 0, value was 3
Enqueueing 10 returns 0
Dequeueing returns 0, value was 4
Dequeueing returns 0, value was 5
Dequeueing returns 0, value was 7
Dequeueing returns 0, value was 8
Dequeueing returns 0, value was 9
Dequeueing returns 0, value was 10
Dequeueing returns 2
推荐阅读
- powershell - 文本匹配的代码文件的Powershell搜索目录输入一个txt文件
- ruby-on-rails - 即使引用了用户,评论中的未定义方法“用户名”
- python - PYTHON:requests.post() 如何发送 request_body 编码为 application/x-www-form-urlencoded
- python - 院子内花园检测 (cv2)
- javascript - 递归地从数组Javascript中获取每个第n个元素
- post - 如何使用 Hyper 或 Reqwest 获取原始 HttpResponse?
- macos - 尽管我使用了 IdleSystemSleepDisabled,为什么我的 Mac 还在睡觉
- pandas - 根据来自另一个数据帧的两个行值的对应值将列添加到数据帧
- arrays - 如何输入小于 100 的整数作为数字字符数组,并将其单词形式的数字输出为 C 中的字符串?
- spring - 如何在 Spring Boot 2 应用程序中配置多个子上下文?