C++数据结构实验题目解析2
目录
前言：
在进入正题之前我先来纠正一个问题，在上篇文章的第一题第二问中，删除多余相同值的代码中出现一个小bug，那就是我们无法删除非相邻的重复值（比如：1，2，1，3，1，4）；所以我又对上次的代码进行了优化。（下列代码为优化后的代码）。C++数据结构实验题目解析
void removeDuplicates()
{
ListNode* current = head;
// 当链表不为空且还有剩余节点可比较时，进行遍历
while (current != nullptr && current->next != nullptr)
{
// 如果当前节点与下一个节点的值相同，则删除下一个节点
if (current->data == current->next->data)
{
ListNode* toDelete = current->next; // 记录待删除的节点
current->next = toDelete->next; // 从链表中移除待删除节点
delete toDelete; // 释放待删除节点的内存
}
else
{
// 如果没有重复，则继续遍历下一个节点
current = current->next;
}
}
}题目：
1.设从键盘输入一个整数序列：a1, a2, …，an，编写程序实现：采用链栈结构存储输入的整数，当ai ≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况给出相应的提示信息。
2.设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。编写相应的入队和出队程序。
考点分析：
基础：栈的基础知识和基本操作；队列的基础知识和基本操作
重点：链栈的实现，循环队列
这里的基础我们就不再赘述，由于篇幅原因我们就主要讲一讲重点，这一个题目比起上一篇题目要稍微简单一点。
难点1：链栈
链栈的基础知识和基本操作，这里就不提了，这些都是课本或者课堂上提到的，大家可以自行复习一下。
核心代码分析：
这段代码定义了一个基于单链表的栈（Stack）数据结构。栈是一种后进先出（LIFO, Last In First Out）的数据结构，这意味着最后添加到栈中的元素将是第一个被移除的元素。下面是对这个栈类及其方法的详细解释：
push 函数
void push(int val)
{
StackNode* newNode = new StackNode(val);
newNode->next = top;
top = newNode;
}
push方法创建一个新的栈节点newNode，并将其数据成员设置为传入的val值。然后，它将新节点的next指针指向当前的栈顶元素（如果有的话），并更新top指针指向新节点。这样，新节点就成为了栈顶元素。
popAndOutput 函数
popAndOutput方法首先检查栈是否为空。如果为空，则打印一条消息并返回。如果不为空，它首先输出栈顶元素的值，然后移除栈顶元素（即将top指针更新为指向下一个元素），并删除被移除的节点以释放内存。
void popAndOutput()
{
if (top == nullptr)
{
cout << "栈为空，无法出栈和输出." << endl;
return;
}
cout << "栈顶元素为：" << top->data << endl;
StackNode* temp = top;
top = top->next;
delete temp;
}
void push(int val)
{
StackNode* newNode = new StackNode(val);
newNode->next = top;
top = newNode;
}
void popAndOutput()
{
if (top == nullptr)
{
cout << "栈为空，无法出栈和输出." << endl;
return;
}
cout << "栈顶元素为：" << top->data << endl;
StackNode* temp = top;
top = top->next;
delete temp;
}
~Stack()
{
while (top!= nullptr)
{
StackNode* temp = top;
top = top->next;
delete temp;
}
}
};难点2：循环队列
核心代码分析：
这段代码实现了一个基于单链表的循环队列的基本操作：入队（enqueue）和出队（dequeue）。循环队列是一种数据结构，其中最后一个元素指向第一个元素，形成一个环状结构。这允许队列在逻辑上被视为首尾相连，从而有效地利用空间。下面是对这两个函数的详细解释：
enqueue 函数
enqueue函数用于将一个新值val添加到队列的末尾。
首先，创建一个新的节点
newNode，其值为val。如果队列为空（即
rear为nullptr），则将新节点的next指针指向它自己，形成一个自环，并将rear指向这个新节点。这表示队列中只有一个元素，且这个元素既是队头也是队尾。如果队列不为空，则将新节点的
next指针指向当前的队头（rear->next），然后将当前队尾的next指针指向新节点，最后更新rear指针指向新节点。这样，新节点就被添加到了队列的末尾，并且保持了队列的循环特性。dequeue 函数
dequeue函数用于从队列中移除并删除队头的元素。
如果队列为空（即
rear为nullptr），则打印错误信息并返回。如果队列中只有一个元素（即
rear->next == rear），则直接删除这个元素，并将rear指针置为nullptr。这表示队列现在为空。如果队列中有多个元素，首先找到队头元素（即
rear->next指向的元素，因为在循环队列中，真正的队头元素是通过访问rear->next得到的），然后更新队尾元素的next指针，使其跳过队头元素直接指向下一个元素。接着，删除队头元素。这样，就成功地从队列中移除了队头元素。
注意事项
-
这段代码没有显示
Node结构体的定义和队列类中的其他成员变量（如rear），但基于上下文可以推断出它们的存在和用途。 -
循环队列的实现需要特别注意边界条件，尤其是在队列为空或只有一个元素时。
-
出队操作中的
if (rear->next == rear)检查确保了当队列中只有一个元素时，能够正确地删除这个元素并使队列变为空。 -
这段代码没有处理内存泄漏或异常，这在生产环境中是需要注意的。
void enqueue(int val) {
Node* newNode = new Node(val);
if (rear == nullptr) {
newNode->next = newNode;
rear = newNode;
} else {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
}
void dequeue() {
if (rear == nullptr) {
cout << "队列为空，无法出队." << endl;
return;
}
if (rear->next == rear) {
delete rear;
rear = nullptr;
} else {
Node* temp = rear->next;
rear->next = temp->next;
delete temp;
}
}感谢大家阅读，求一个免费的赞。
完整代码：
1
#include <iostream>
using namespace std;
struct StackNode {
int data;
StackNode* next;
StackNode(int val) : data(val), next(nullptr) {}
};
class Stack {
private:
StackNode* top;
public:
Stack() : top(nullptr) {}
void push(int val) {
StackNode* newNode = new StackNode(val);
newNode->next = top;
top = newNode;
}
void popAndOutput() {
if (top == nullptr) {
cout << "栈为空，无法出栈和输出." << endl;
return;
}
cout << "栈顶元素为：" << top->data << endl;
StackNode* temp = top;
top = top->next;
delete temp;
}
~Stack() {
while (top!= nullptr) {
StackNode* temp = top;
top = top->next;
delete temp;
}
}
};
int main() {
Stack stack;
int input;
cout << "请输入整数序列，以 -1 结束输入：" << endl;
while (true) {
cin >> input;
if (input == -1) {
stack.popAndOutput();
break;
} else {
stack.push(input);
}
}
return 0;
}
2
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class Queue {
private:
Node* rear;
public:
Queue() : rear(nullptr) {}
void enqueue(int val) {
Node* newNode = new Node(val);
if (rear == nullptr) {
newNode->next = newNode;
rear = newNode;
} else {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
}
void dequeue() {
if (rear == nullptr) {
cout << "队列为空，无法出队." << endl;
return;
}
if (rear->next == rear) {
delete rear;
rear = nullptr;
} else {
Node* temp = rear->next;
rear->next = temp->next;
delete temp;
}
}
~Queue() {
while (rear!= nullptr) {
dequeue();
}
}
};
int main() {
Queue queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue();
queue.dequeue();
queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
return 0;
}原文地址：https://blog.csdn.net/2301_81280642/article/details/143691899
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！