C++题目分享
嗨嗨嗨，我又来更新这个系列了，很久没更新了。让我们看一看有那些有趣的题目：
题目一：
1.以单链表作为存储结构，实现线性表的就地逆置（提示，就地逆置：在不使用额外的数据结构或空间的情况下，将单链表中的节点顺序反转，使得原本指向下一个节点的指针指向了前一个节点。完成这一操作后，链表的第一个数据元素变为最后一个数据元素，而最后一个数据元素则成为第一个数据元素）。
2. 创建一个非递减序（有重复值）的单链表，实现删除值相同的多余结点。
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int data;
ListNode* next;
ListNode(int val) : data(val), next(nullptr) {}
};
// 单链表类
class LinkedList {
public:
LinkedList() : head(nullptr) {}
// 插入节点以保持非递减序
void insertInOrder(int val) {
ListNode* newNode = new ListNode(val);
if (head == nullptr || val <= head->data) {
newNode->next = head;
head = newNode;
} else {
ListNode* current = head;
while (current->next!= nullptr && current->next->data < val) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 就地逆置链表
void reverseList() {
ListNode* prev = nullptr;
ListNode* current = head;
ListNode* next = nullptr;
while (current!= nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
// 打印链表
void printList() {
ListNode* current = head;
while (current!= nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
// 删除值相同的多余节点
void removeDuplicates() {
ListNode* current = head;
while (current!= nullptr && current->next!= nullptr) {
if (current->data == current->next->data) {
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
} else {
current = current->next;
}
}
}
~LinkedList() {
ListNode* current = head;
while (current!= nullptr) {
ListNode* next = current->next;
delete current;
current = next;
}
}
private:
ListNode* head;
};
int main() {
LinkedList list;
// 创建非递减序单链表并插入一些值
list.insertInOrder(3);
list.insertInOrder(3);
list.insertInOrder(5);
list.insertInOrder(5);
list.insertInOrder(7);
list.insertInOrder(7);
cout << "原始链表：";
list.printList();
// 删除值相同的多余节点
list.removeDuplicates();
cout << "删除重复节点后的链表：";
list.printList();
// 就地逆置链表
list.reverseList();
cout << "逆置后的链表：";
list.printList();
return 0;
}题目二：
1.设从键盘输入一个整数序列：a1, a2, …，an，编写程序实现：采用链栈结构存储输入的整数，当ai ≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况给出相应的提示信息。
#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;
}
2.设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。编写相应的入队和出队程序。
#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;
}大家先思考一下上面的题目，看看上面的代码，我明天会出详细的解析，这期题目有一点难，大家尽量思考，我们明天见。
原文地址：https://blog.csdn.net/2301_81280642/article/details/143666842
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！