本次数据结构的作业是设计一个只有尾指针的循环链队列，要求实现构造(有参 && 无参)、析构、出入列、获取头结点等功能。在完成过程中踩了很多坑(特别是在实现析构时qwq)
template
struct Node {
DataType data;
Node* next;
};
template
class LinkQueue {
public:
LinkQueue();
LinkQueue(int [], int);
~LinkQueue();
void EnQueue(DataType x);
DataType DeQueue();
DataType GetQueue();
private:
Node* rear;
};
有参构造&&无参构造
template
LinkQueue::LinkQueue(int arr[], int n) {
rear = new Node;
Node* p = rear;
//储存首地址，最后把尾巴连上
for(int i = 0; i < n; i++) {
rear->next = new Node;
rear = rear->next;
rear->data = arr[i];
}
rear->next = p;
// 把尾巴连到首部
}
template
LinkQueue::LinkQueue() {
rear = NULL;
}
进队 && 出队
template
void LinkQueue::EnQueue(DataType x) {
Node* p = new Node;
p->data = x;
if (rear == NULL) {
rear = p;
rear->next = p;
} else {
p->next = rear->next; // 新建节点连接头指针
rear->next = p; // 尾指针连接新节点
rear = p; // 尾指针后移
}
}
template
DataType LinkQueue::DeQueue() {
Node* p = NULL;
DataType x;
if (rear == NULL)
throw "dive dowm";
p = rear->next;
x = p->data;
if (rear == p)
rear = NULL;
else
rear->next = p->next;
delete p;
return x;
}
获取头结点
template
DataType LinkQueue::GetQueue() {
if (rear != NULL)
return rear->next->data;
// return rear->data;
// 这里rear已经指向队末，按照上一行代码，返回的是队末元素
else
throw "empty queue";
}
清空循环链队列(也可写成析构)
template
LinkQueue::~LinkQueue() {
Node* p;
while (rear != NULL) {
// the wrong version:
// p = rear;
// rear = rear->next;
// delete p;
p = rear->next;
if (rear == p) {
delete rear;
break;
} else
rear->next = p->next;
delete p;
}
}
关于这个析构函数，我在网上找了很多个版本，很多代码都是写成注释里的那样，包括老师给的答案也是，有些编译器直接运行可能看不出什么问题，但是放在debug模式里，就会报错
如上图，在这里我已将循环链队列所有元素delete，当我查看变量的值时，发现，没那么简单，rear指针不为null，它指向的data值也是不规则的，也就不难说明为什么跳不出第46行的while循环了
跳不出循环后，继续delete，就会报错，虽然提示 unKnown signal，实际上是队列为空，无法继续delete
那么怎么解决呢，我将出列函数改写，放到析构函数里，这样子在删除最后一个节点时就能跳出循环，结束析构
完整代码
#include
using namespace std;
template
struct Node {
DataType data;
Node* next;
};
template
class LinkQueue {
public:
LinkQueue();
LinkQueue(int[], int);
~LinkQueue();
void EnQueue(DataType x);
DataType DeQueue();
DataType GetQueue();
private:
Node* rear;
};
template
LinkQueue::LinkQueue(int arr[], int n) {
rear = new Node;
// rear->data = arr[0];
Node* p = rear; // 储存首地址，最后把尾巴连接到首部
for (int i = 0; i < n; i++) {
rear->next = new Node; // 不断开辟空间
rear = rear->next; // rear后移
rear->data = arr[i];
}
rear->next = p; //把尾巴连到首部
}
template
LinkQueue::LinkQueue() {
rear = NULL;
}
template
LinkQueue::~LinkQueue() {
Node* p;
while (rear != NULL) {
p = rear->next;
if (rear == p) {
delete rear;
break;
} else {
rear->next = p->next;
}
delete p;
}
}
template
void LinkQueue::EnQueue(DataType x) {
Node* p = NULL;
p = new Node;
p->data = x;
if (rear == NULL) {
rear = p;
rear->next = p;
} else {
p->next = rear->next; // 新建节点连接头指针
rear->next = p; // 尾指针连接新节点
rear = p; // 尾指针后移
}
}
template
DataType LinkQueue::DeQueue() {
Node* p = NULL;
DataType x;
if (rear == NULL)
throw "dive down";
p = rear->next;
x = p->data;
if (rear == p)
rear = NULL;
else
rear->next = p->next;
delete p;
return x;
}
template
DataType LinkQueue::GetQueue() {
if (rear != NULL)
return rear->next->data;
// return rear->data;
// 这里rear已指向队末，返回的是队末元素
else
throw "empty queue";
}
int main() {
LinkQueue Queue;
try {
Queue.EnQueue(5);
Queue.EnQueue(10);
Queue.EnQueue(15);
// Queue.EnQueue(20);
} catch (char* wrong) {
cout << wrong << endl;
}
cout << "get head element" << endl;
cout << Queue.GetQueue() << endl;
try {
Queue.DeQueue();
} catch (char* wrong) {
cout << wrong << endl;
}
cout << "get head element" << endl;
cout << Queue.GetQueue() << endl;
}
Original: https://www.cnblogs.com/jaydenchang/p/15455426.html
Author: JaydenChang
Title: 数据结构–不设头指针的循环链队列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/585162/
转载文章受原作者版权保护。转载请注明原作者出处！