成都 网站建设培训网页制作与设计教程

嗨嗨嗨，我又来更新这个系列了，很久没更新了。让我们看一看有那些有趣的题目：

题目一：

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;
}

大家先思考一下上面的题目，看看上面的代码，我明天会出详细的解析，这期题目有一点难，大家尽量思考，我们明天见。