Loading... ## 实验三第一题 【问题描述】 输入给定的10个数据建立一个顺序栈,从栈顶到栈底依次显示栈内元素;从键盘输入出栈元素个数n(1<=n<=10),将n个元素依次出栈并显示出栈元素,再显示此时栈顶元素。 【输入样例】 4 5 72 60 2 49 38 87 52 31 2 【输出样例】 31 52 87 38 49 2 60 72 5 4 31 52 87 ```C++ #include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAXSIZE - 1; } int push(Stack *s, int x) { if (isFull(s)) { return 0; } s->top++; s->data[s->top] = x; return 1; } //出栈操作 int pop(Stack *s, int *x) { if (isEmpty(s)) { return 0; } *x = s->data[s->top]; s->top--; return 1; } int getTop(Stack *s, int *x) { if (isEmpty(s)) { return 0; } *x = s->data[s->top]; return 1; } void printStack(Stack *s) { if (isEmpty(s)) { printf("The stack is empty.\n"); return; } for (int i = s->top; i >= 0; i--) { printf("%d ", s->data[i]); } printf("\n"); } //主函数测试代码 int main() { Stack s; initStack(&s); int arr[10] = {4, 5, 72, 60, 2, 49, 38, 87, 52, 31}; for (int i = 0; i < 10; i++) { push(&s, arr[i]); } printStack(&s); int n; scanf("%d", &n); if (n < 1 || n > 10) { printf("Invalid input.\n"); exit(0); } for (int i = 0; i < n-2; i++) { int x; pop(&s, &x); printf("%d ", x); } printf("\n"); int top; getTop(&s, &top); printf("%d\n", top); return 0; } ``` ## 第二题 【问题描述】 输入给定的10个数据建立一个链栈,从栈顶到栈底依次显示栈内元素;从键盘输入出栈元素个数n(1<=n<=10),将n个元素依次出栈并显示出栈元素,再显示此时栈顶元素。 【输入样例】 5 1 3 38 15 57 85 89 74 84 5 【输出样例】 84 74 89 85 57 15 38 3 1 5 84 74 89 85 57 15 ```C++ #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* push(Node *top, int data) { Node *new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = top; return new_node; } Node* pop(Node *top) { if (top == NULL) { printf("栈已空\n"); return NULL; } Node *temp = top; printf("%d ", temp->data); top = top->next; free(temp); return top; } void display(Node *top) { Node *temp = top; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } int main() { Node *top = NULL; for (int i = 0; i < 10; i++) { int data; scanf("%d", &data); top = push(top, data); } display(top); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { top = pop(top); } printf("\n"); if (top != NULL) { printf("%d\n", top->data); } return 0; } ``` ## 第三题 【问题描述】 输入给定的10个数据建立循环队列,显示循环队列中所有数据元素;从键盘输入出队元素个数n(1<=n<=10),将n个元素出队后显示队中剩余元素。 【输入样例】 56 19 52 81 39 65 32 56 19 6 3 【输出样例】 56 19 52 81 39 65 32 56 19 6 56 19 52 81 39 65 32 56 19 6 ```C++ #include <stdio.h> #define SIZE 11 int queue[SIZE]; int front = -1, rear = -1; void enqueue(int item) { if ((rear + 1) % SIZE == front) { printf("队列已满\n"); return; } if (front == -1) front = 0; rear = (rear + 1) % SIZE; queue[rear] = item; } int dequeue() { if (front == -1) { printf("队列为空\n"); return -1; } int item = queue[front]; printf("%d ", item); if (front == rear) front = rear = -1; else front = (front + 1) % SIZE; return item; } void display() { if (front == -1) { printf("队列为空\n"); return; } int i = front; while (i != rear) { printf("%d ", queue[i]); i = (i + 1) % SIZE; } printf("%d\n", queue[i]); } int main() { for (int i = 0; i < 10; i++) { int data; scanf("%d", &data); enqueue(data); } display(); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { dequeue(); } printf("\n"); display(); return 0; } ``` ## 第四题 【问题描述】 输入给定的10个数据建立循环队列,显示循环队列中所有数据元素;从键盘输入出队元素个数n(1<=n<=10),将n个元素出队后显示此时的队头元素。 【输入样例】 41 45 14 73 98 29 42 74 3 66 3 【输出样例】 41 45 14 73 98 29 42 74 3 66 41 45 14 73 ```C++ #include <stdio.h> #define SIZE 11 int queue[SIZE]; int front = -1, rear = -1; void enqueue(int item) { if ((rear + 1) % SIZE == front) { printf("队列已满\n"); return; } if (front == -1) front = 0; rear = (rear + 1) % SIZE; queue[rear] = item; } int dequeue() { if (front == -1) { printf("队列为空\n"); return -1; } int item = queue[front]; printf("%d ", item); if (front == rear) front = rear = -1; else front = (front + 1) % SIZE; return item; } void display() { if (front == -1) { printf("队列为空\n"); return; } int i = front; while (i != rear) { printf("%d ", queue[i]); i = (i + 1) % SIZE; } printf("%d\n", queue[i]); } int main() { for (int i = 0; i < 10; i++) { int data; scanf("%d", &data); enqueue(data); } display(); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { dequeue(); } printf("\n"); if (front != -1) { printf("%d\n", queue[front]); } return 0; } ``` ## 第五题 【问题描述】 输入给定的10个数据建立链队列,显示链队列中所有数据元素;从键盘输入出队元素个数n(1<=n<=10),将n个元素出队后显示此时的队头元素。 【输入样例】 82 38 50 12 82 90 40 69 30 36 5 【输出样例】 82 38 50 12 82 90 40 69 30 36 82 38 50 12 82 90 ```C++ #include <stdio.h> #define SIZE 11 int queue[SIZE]; int front = -1, rear = -1; void enqueue(int item) { if ((rear + 1) % SIZE == front) { printf("队列已满\n"); return; } if (front == -1) front = 0; rear = (rear + 1) % SIZE; queue[rear] = item; } int dequeue() { if (front == -1) { printf("队列为空\n"); return -1; } int item = queue[front]; printf("%d ", item); if (front == rear) front = rear = -1; else front = (front + 1) % SIZE; return item; } void display() { if (front == -1) { printf("队列为空\n"); return; } int i = front; while (i != rear) { printf("%d ", queue[i]); i = (i + 1) % SIZE; } printf("%d\n", queue[i]); } int main() { for (int i = 0; i < 10; i++) { int data; scanf("%d", &data); enqueue(data); } display(); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { dequeue(); } printf("\n"); if (front != -1) { printf("%d\n", queue[front]); } return 0; } ``` ## 第六题 【问题描述】 输入一个算术表达式中包含圆括号、方括号和花括号3种类型的括号,编写一个算法判断其中的括号是否匹配。 提示:本题使用一个运算符栈,当遇到(、[或{时进栈,当遇到}、]、)时判断栈顶是否为相应的括号,若是退栈则继续执行,否则算法结束。 【输入样例】 {3+[(1-2)*(6-5)/6]*2} 【输出样例】 匹配成功 ```C++ #include <stdio.h> #include <stdlib.h> typedef struct Node { char data; struct Node *next; } Node; Node* push(Node *top, char data) { Node *new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = top; return new_node; } Node* pop(Node *top) { if (top == NULL) { printf("栈已空\n"); return NULL; } Node *temp = top; top = top->next; free(temp); return top; } char peek(Node *top) { if (top == NULL) { printf("栈已空\n"); return '\0'; } return top->data; } int isMatchingPair(char character1, char character2) { if (character1 == '(' && character2 == ')') return 1; else if (character1 == '{' && character2 == '}') return 1; else if (character1 == '[' && character2 == ']') return 1; else return 0; } int areParenthesisBalanced(char exp[]) { Node *stack = NULL; for (int i=0; exp[i]!='\0'; i++) { if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[') stack = push(stack, exp[i]); if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') { if (stack == NULL) return 0; else if (!isMatchingPair(peek(stack), exp[i])) return 0; else stack = pop(stack); } } if (stack == NULL) return 1; else return 0; } int main() { char exp[100]; scanf("%s", exp); if (areParenthesisBalanced(exp)) printf("匹配成功\n"); else printf("匹配失败\n"); return 0; } ``` ## 第七题 【问题描述】 表达式求值。设运算符有+、-、*、/、#和(),其中#为表达式的定界符,对于任意给定的表达式进行求值运算,给出求值结果。 【输入样例】 (3+((1-2)*(6-5)/2)*2) 【输出样例】 2.000000 ```C++ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #define MAX_SIZE 100 double operators[MAX_SIZE]; double operands[MAX_SIZE]; int top_operator = -1; int top_operand = -1; char s[MAX_SIZE]; double calculate(double a, double b, char op) { switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': if (b == 0) { printf("Error: Division by zero.\n"); exit(1); } return a / b; } return 0; // Never reach here } void push_operator(char c) { operators[++top_operator] = c; } char pop_operator() { return operators[top_operator--]; } void push_operand(double num) { operands[++top_operand] = num; } double pop_operand() { return operands[top_operand--]; } int precedence(char op) { if (op == '#' || op == '(') return 0; if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return -1; // Invalid operator } int main() { fgets(s, MAX_SIZE, stdin); s[strcspn(s, "\n")] = '\0'; int i = 0; while (s[i] != '\0') { if (isdigit(s[i])) { double num = 0; while (isdigit(s[i])) { num = num * 10 + (s[i] - '0'); i++; } push_operand(num); } else if (isalpha(s[i])) { char op = s[i++]; while (precedence(op) <= precedence(pop_operator())) { char prev_op = pop_operator(); double b = pop_operand(); double a = pop_operand(); push_operand(calculate(a, b, prev_op)); } push_operator(op); } else if (s[i] == '(') { push_operator(s[i++]); } else if (s[i] == ')') { while (pop_operator() != '(') { double b = pop_operand(); double a = pop_operand(); char op = pop_operator(); push_operand(calculate(a, b, op)); } i++; } else { i++; } } while (top_operator >= 0) { char op = pop_operator(); double b = pop_operand(); double a = pop_operand(); push_operand(calculate(a, b, op)); } printf("%.6lf\n", pop_operand()); return 0; } ``` 最后修改:2024 年 01 月 13 日 © 允许规范转载 赞 2 如果觉得我的文章对你有用,请随意赞赏
1 条评论
|´・ω・)ノ嗨嗨嗨