数据结构（1~10）

（1）双栈

#include <iostream>
#include <algorithm>
using namespace std;
// 定义栈元素的类型
typedef int SElemType;// 定义双栈数据结构
typedef struct {int top[2];int bot[2];SElemType *V;int m;
} DblStack;// 初始化双栈
void InitDblStack(DblStack *S, int maxSize) {S->m = maxSize;S->V = new SElemType[maxSize]; // 使用 new 替代 mallocS->bot[0] = -1;S->top[0] = -1; // 0号栈为空S->bot[1] = maxSize;S->top[1] = maxSize; // 1号栈为空
}// 判断0号栈是否为空
bool StackEmpty0(DblStack *S) {return S->top[0] == -1;
}// 判断1号栈是否为空
bool StackEmpty1(DblStack *S) {return S->top[1] == S->m;
}// 判断双栈是否已满
bool StackFull(DblStack *S) {return S->top[0] + 1 == S->top[1];
}// 0号栈进栈操作
bool Push0(DblStack *S, SElemType e) {if (StackFull(S)) {std::cout << "栈溢出！" <<endl;return false;}S->V[++(S->top[0])] = e;return true;
}// 1号栈进栈操作
bool Push1(DblStack *S, SElemType e) {if (StackFull(S)) {cout << "栈溢出！" << endl;return false;}S->V[--(S->top[1])] = e;return true;
}// 0号栈出栈操作
bool Pop0(DblStack *S, SElemType *e) {if (StackEmpty0(S)) {cout << "栈下溢！" << endl;return false;}*e = S->V[(S->top[0])--];return true;
}// 1号栈出栈操作
bool Pop1(DblStack *S, SElemType *e) {if (StackEmpty1(S)) {cout << "栈下溢！" << endl;return false;}*e = S->V[(S->top[1])--];return true;
}// 打印栈数组
void PrintStack(DblStack *S) {cout << "栈数组: ";for (int i = 0; i < S->m; i++) {std::cout << S->V[i] << " ";}cout << "\n栈顶索引: 0: " << S->top[0] << ", 1: " << S->top[1] << endl;
}int main() {DblStack S;int maxSize = 10;InitDblStack(&S, maxSize);// 测试0号栈Push0(&S, 1);Push0(&S, 2);Push0(&S, 3);int e;Pop0(&S, &e);cout << "从0号栈弹出: " << e << endl;// 测试1号栈Push1(&S, 7);Push1(&S, 8);Push1(&S, 9);Pop1(&S, &e);cout << "从1号栈弹出: " << e << endl;// 打印栈数组PrintStack(&S);// 释放内存delete[] S.V; return 0;
}

（2）回文数

#include <iostream>
#include<string> 
#include<algorithm>
using namespace std;
int main() 
{string s;cin >> s;string oris = s;reverse(s.begin(),s.end());if(oris == s)cout <<"YES"<< endl;elsecout << "NO" << endl; return 0;
}

（3）设从键盘输入一整数的序列：a1,a2,a3,...,an，用栈结构存储输入的整数，当ai不等于-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>const int  MAX_SIZE = 100 ;typedef struct {int data[MAX_SIZE]; // 存储栈中元素的数组int top; // 栈顶位置
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1; // 栈顶位置初始化为-1，表示栈为空
}// 判断栈是否为空
bool isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
bool isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}// 压栈操作
bool push(Stack *s, int value) {if (isFull(s)) {printf("栈满，无法压栈！\n");return false;}s->data[++(s->top)] = value; // 先增加栈顶位置，再赋值return true;
}// 弹栈操作
bool pop(Stack *s, int *value) {if (isEmpty(s)) {printf("栈空，无法弹栈！\n");return false;}*value = s->data[(s->top)--]; return true;
}// 获取栈顶元素
bool top(Stack *s, int *value) {if (isEmpty(s)) {printf("栈空，无法获取栈顶元素！\n");return false;}*value = s->data[s->top];return true;
}int main() {Stack s;initStack(&s);int input;printf("请输入一整数的序列，以-1表示输出栈顶并出栈：\n");while (scanf("%d", &input) != EOF) {if (input != -1) {if (!push(&s, input)) {break; }} else {int value;if (top(&s, &value) && pop(&s, &value)) {printf("栈顶整数：%d\n", value);}}}return 0;
}

（4）从键盘上输入一个后缀表达式，规定：后缀表达式长度不超过一行，以’$'结束操作数之间用空格分割。且操作符只有 + - * / 四种。
后缀表达式：234 34 + 2 *$

#include <iostream>
#include <stack>
#include <sstream>
#include <string>
#include <cctype>using namespace std;// 函数：判断一个字符串是否是有效的操作符
bool isOperator(const string& token) {return token == "+" || token == "-" || token == "*" || token == "/";
}// 函数：将字符串转换为整数
int stringToInt(const string& str) {return stoi(str);
}// 函数：计算两个操作数的结果，根据给定的操作符
int applyOperator(const string& op, int a, int b) {if (op == "+") return a + b;if (op == "-") return a - b;if (op == "*") return a * b;if (op == "/") {if (b == 0) {cerr << "Error: Division by zero!" << endl;exit(EXIT_FAILURE); // 处理除以零的错误情况}return a / b;}return 0; 
}int main() {stack<int> values; // 用于存储操作数的栈string line;getline(cin, line, '$'); // 从键盘读取一行输入，直到遇到'$'字符istringstream iss(line); // 使用输入字符串流来解析输入string token;while (iss >> token) { if (isOperator(token)){ // 如果token是操作符int b = values.top(); values.pop(); int a = values.top(); values.pop(); int result = applyOperator(token, a, b); // 计算结果values.push(result); // 将结果压入栈中}else { values.push(stringToInt(token)); // 将操作数转换为整数并压入栈中}}// 栈中应该只剩下一个元素，即表达式的最终结果if (!values.empty()) {cout << "计算结果： " << values.top() << endl;} else {cerr << "错误：后缀表达式计算结果导致了一个空堆栈！ " << endl;}return 0;
}

（5）假设以I和O分别表示入栈和出栈操作。

#include <iostream>
#include <string>using namespace std;//检查给定的IO序列是否为合法序列
bool isValidSequence(const string& sequence) 
{int balance = 0; // 用于跟踪栈的平衡状态for (char ch : sequence) {if (ch == 'I'){balance++; // 入栈操作，增加平衡计数}else if (ch == 'O') {if (balance == 0) {// 出栈操作，但栈为空，因此序列非法return false;}balance--; // 出栈操作，减少平衡计数} else {// 序列中包含非法字符return false;}}return balance == 0;
}int main() {string sequence;cout << "请输入一个由I和O组成的序列：";cin >> sequence;if (isValidSequence(sequence)) {cout << "序列是合法的。" << endl;} else {cout << "序列是非法的。" << endl;}return 0;
}

(6)假设以带头结点的循环链表表示队列

#include <stdio.h>
#include <stdlib.h>// 定义链表结点结构
typedef struct Node {int data;struct Node* next;
} Node;// 定义队列结构，包含一个指向队尾元素的指针
typedef struct {Node* tail; 
} CircularQueue;// 初始化队列
void initQueue(CircularQueue* q) 
{// 创建一个头结点，它同时也是尾结点的前驱q->tail = (Node*)malloc(sizeof(Node));if (q->tail == NULL) {printf("内存分配失败 ");exit(1);}q->tail->data = 0; q->tail->next = q->tail; 
}// 入队列操作
void enqueue(CircularQueue* q, int value) 
{Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败 ");exit(1);}newNode->data = value;newNode->next = q->tail->next;q->tail->next = newNode;q->tail = newNode; 
}// 出队列操作，返回队首元素的值，并移除该元素
int dequeue(CircularQueue* q) 
{if (q->tail->next == q->tail) {printf("栈是空的");exit(1); }Node* temp = q->tail->next;int value = temp->data; q->tail->next = temp->next; free(temp); // 释放队首元素的内存return value;
}// 打印队列中的所有元素（用于调试）
void printQueue(CircularQueue* q) {if (q->tail->next == q->tail) {printf("Queue is empty\n");return;}Node* current = q->tail->next;while (current != q->tail) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 主函数用于测试队列操作
int main() {CircularQueue q;initQueue(&q);enqueue(&q, 1);enqueue(&q, 2);enqueue(&q, 3);printQueue(&q); // 输出: 1 2 3printf("队列: %d\n", dequeue(&q)); printQueue(&q); // 输出: 2 3return 0;
}

(7)假设以数组q[m]存放

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define M 5 // 队列的最大容量typedef struct {int Q[M]; // 队列元素数组int front; // 队头指针int rear; // 队尾指针int tag; // 队列状态标志，0表示空，1表示满，-1表示初始状态（可选，用于更明确的初始化检查）
} CircularQueue;// 初始化队列
void initQueue(CircularQueue* q) {q->front = 0;q->rear = 0;q->tag = -1; 
}// 判断队列是否为空
bool isEmpty(CircularQueue* q) {return q->tag == 0 && q->front == q->rear;
}// 判断队列是否已满
bool isFull(CircularQueue* q) {return q->tag == 1 || ((q->rear + 1) % M == q->front);
}// 入队列操作
bool enqueue(CircularQueue* q, int value) {if (isFull(q)) {printf("队列已满，无法入队\n");return false;}if (q->tag == -1) {q->tag = 0; // 如果队列处于初始状态，则将其设置为空状态}q->Q[q->rear] = value;q->rear = (q->rear + 1) % M;if (q->rear == q->front) { if (!isEmpty(q)) { q->tag = 1;}}return true;
}// 出队列操作
bool dequeue(CircularQueue* q, int* value) {if (isEmpty(q)) {printf("队列为空，无法出队\n");return false;}*value = q->Q[q->front];q->front = (q->front + 1) % M;if (q->front == q->rear) { // 出队后front追上了rear，队列变为空q->tag = 0;} else {q->tag = -1;}return true;
}int main() {CircularQueue q;initQueue(&q);// 测试入队列操作enqueue(&q, 1);enqueue(&q, 2);enqueue(&q, 3);enqueue(&q, 4);enqueue(&q, 5); // 此时队列应已满// 测试出队列操作int value;dequeue(&q, &value);printf("出队元素: %d\n", value);dequeue(&q, &value);printf("出队元素: %d\n", value);// 再次测试入队列操作，检查队列是否能正确循环enqueue(&q, 6);printf("入队元素: 6\n");// 检查队列状态if (isEmpty(&q)) {printf("队列为空\n");} else if (isFull(&q)) {printf("队列已满\n");} else {printf("队列既不满也不空\n");}return 0;
}

（8）如果允许在循环队列的

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define M 5 // 队列的最大容量typedef struct {int Q[M]; // 队列元素数组int front; // 队头指针int rear; // 队尾指针（指向下一个空闲位置）int size; // 队列中当前元素的个数
} CircularQueue;// 初始化队列
void initQueue(CircularQueue* q) {q->front = 0;q->rear = 0;q->size = 0;
}// 判断队列是否为空
bool isEmpty(CircularQueue* q) {return q->size == 0;
}// 判断队列是否已满
bool isFull(CircularQueue* q) {return q->size == M;
}// 从队头插入元素
bool enqueueFront(CircularQueue* q, int value) {if (isFull(q)) {printf("队列已满，无法从队头插入\n");return false;}int newFront = (q->front - 1 + M) % M; // 计算新的队头位置（考虑循环）if (newFront == q->rear) {printf("内部错误：插入位置冲突\n");return false;}q->Q[newFront] = value;q->front = newFront;q->size++;return true;
}// 从队尾删除元素
bool dequeueRear(CircularQueue* q, int* value) {if (isEmpty(q)) {printf("队列为空，无法从队尾删除\n");return false;}*value = q->Q[q->rear - 1]; q->rear = (q->rear - 1 + M) % M; // 更新队尾指针（考虑循环）q->size--;if (q->size == 0) {q->front = 0;q->rear = 0;}return true;
}// 打印队列元素（用于调试）
void printQueue(CircularQueue* q) {if (isEmpty(q)) {printf("队列为空\n");return;}printf("队列元素: ");int i = q->front;for (int count = 0; count < q->size; count++) {printf("%d ", q->Q[i]);i = (i + 1) % M;}printf("\n");
}int main() {CircularQueue q;initQueue(&q);// 测试从队头插入enqueueFront(&q, 10);enqueueFront(&q, 20);enqueueFront(&q, 30);printQueue(&q); // 应打印: 队列元素: 30 20 10// 测试从队尾删除int value;dequeueRear(&q, &value);printf("从队尾删除的元素: %d\n", value); printQueue(&q);return 0;
}

（10）已知f为单链表的

#include <iostream>
#include <climits> // 定义链表节点结构
struct Node {int data;Node* next;// 构造函数Node(int val) : data(val), next(nullptr) {}
};// （1）求链表中的最大整数
int findMaxRecursive(Node* head) {if (head == nullptr) {std::cerr << "Error: head is nullptr" << std::endl;exit(EXIT_FAILURE); }// 只有一个元素时，直接返回该元素if (head->next == nullptr) {return head->data;}// 递归情况：比较当前元素和剩余链表中的最大值int maxInRest = findMaxRecursive(head->next);return (head->data > maxInRest) ? head->data : maxInRest;
}// （2）求链表的节点个数
int countNodesRecursive(Node* head) {// 基本情况：链表为空时，节点个数为0if (head == nullptr) {return 0;}// 递归情况：当前节点加上剩余链表的节点个数return 1 + countNodesRecursive(head->next);
}// （3）求链表中所有元素的平均值（使用辅助函数）
double findAverageHelper(Node* head, int& totalSum, int& totalCount) {if (head == nullptr) {return 0;}totalSum += head->data;totalCount++;return findAverageHelper(head->next, totalSum, totalCount);
}double findAverageRecursive(Node* head) {int totalSum = 0;int totalCount = 0;// 调用辅助函数进行递归计算findAverageHelper(head, totalSum, totalCount);// 返回平均值return (totalCount > 0) ? static_cast<double>(totalSum) / totalCount : 0.0;
}int main() {// 创建链表：1 -> 3 -> 2 -> 5 -> 4Node* first = new Node(1);first->next = new Node(3);first->next->next = new Node(2);first->next->next->next = new Node(5);first->next->next->next->next = new Node(4);// 测试函数std::cout << "最大整数: " << findMaxRecursive(first) << std::endl; // 应输出5std::cout << "节点个数: " << countNodesRecursive(first) << std::endl; // 应输出5std::cout << "所有整数的平均值: " << findAverageRecursive(first) << std::endl; // 应输出3.0return 0;
}