算法设计题(栈)
1.编写一个函数,要求借助一个栈,把一个数组中的数据元素逆置。
代码:
#include <stdio.h>
#include <stdbool.h>
#define N 100
typedef struct {
int data[N];
int top;
} Stack;
// 初始化栈
void init(Stack* s) {
s->top = -1;
}
// 判断栈是否为空
bool isSempty(Stack* s) {
if (s == NULL) {
return true; // 如果栈指针为空,认为栈为空
}
return s->top == -1; // 判断栈顶指针是否为 -1
}
// 判断栈是否为满
bool isFull(Stack* s) {
if (s == NULL) {
return false; // 如果栈指针为空,认为栈不满
}
return s->top == N - 1; // 判断栈顶指针是否达到最大值
}
// 入栈操作
bool push(Stack* s, int x) {
if (isFull(s)) {
return false; // 栈满时返回 false
}
s->top = s->top + 1;
s->data[s->top] = x;
return true; // 成功入栈返回 true
}
// 出栈操作
bool pop(Stack* s, int* x) { // 出栈返回值通过指针传递
if (isSempty(s)) {
return false; // 栈空时返回 false
}
*x = s->data[s->top]; // 将栈顶元素赋值给 x
s->top--; // 栈顶指针减 1
return true; // 成功出栈返回 true
}
// 翻转数组
void reverse(int arr[], int size) {
Stack s;
init(&s); // 初始化栈
for (int i = 0; i < size; i++) {
push(&s, arr[i]); // 将数组元素压入栈中
}
for (int i = 0; i < size; i++) {
pop(&s, &arr[i]); // 从栈中弹出元素并存回数组
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
printf("原来的数组: ");
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
reverse(arr, size);
printf("反转后的数组: ");
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
2.设计一个算法,要求判断一个算术表达式中的圆括号配对是否正确
代码:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define N 100 // 栈的最大容量
// 定义栈结构体
typedef struct {
char data[N]; // 存储栈元素的数组
int top; // 栈顶指针
} Stack;
// 初始化栈
void init(Stack* s) {
s->top = -1; // 将栈顶指针初始化为 -1,表示栈为空
}
// 判断栈是否为空
bool isSempty(Stack* s) {
if (s == NULL) {
return true; // 如果栈指针为空,认为栈为空
}
return s->top == -1; // 判断栈顶指针是否为 -1
}
// 判断栈是否为满
bool isFull(Stack* s) {
if (s == NULL) {
return false; // 如果栈指针为空,认为栈不满
}
return s->top == N - 1; // 判断栈顶指针是否达到最大值
}
// 入栈操作
bool push(Stack* s, char x) {
if (isFull(s)) {
return false; // 栈满时返回 false
}
s->top = s->top + 1; // 栈顶指针加 1
s->data[s->top] = x; // 将元素 x 压入栈顶
return true; // 成功入栈返回 true
}
// 出栈操作
bool pop(Stack* s, char* x) { // 出栈返回值通过指针传递
if (isSempty(s)) {
return false; // 栈空时返回 false
}
*x = s->data[s->top]; // 将栈顶元素赋值给 x
s->top--; // 栈顶指针减 1
return true; // 成功出栈返回 true
}
// 检查表达式中的圆括号是否配对正确
bool isTrue(const char* expression) {
Stack s;
init(&s); // 初始化栈
int len = strlen(expression); // 获取表达式的长度
for (int i = 0; i < len; i++) {
if (expression[i] == '(') { // 遇到左括号
push(&s, '('); // 将左括号压入栈中
} else if (expression[i] == ')') { // 遇到右括号
char temp;
if (pop(&s, &temp)) { // 尝试从栈中弹出一个元素
if (temp != '(') { // 如果弹出的元素不是左括号
return false; // 括号不匹配,返回 false
}
} else {
return false; // 栈为空时遇到右括号,括号不匹配,返回 false
}
}
}
return isSempty(&s); // 如果栈为空,说明所有括号都匹配,返回 true
}
int main() {
const char* expression1 = "(a + b) * (c - d)"; // 合法表达式
const char* expression2 = "((a + b) * (c - d)"; // 不合法表达式
const char* expression3 = "(a + b) * (c - d))"; // 不合法表达式
printf("表达式 1: %s\n", isTrue(expression1) ? "正确" : "不正确");
printf("表达式 2: %s\n", isTrue(expression2) ? "正确" : "不正确");
printf("表达式 3: %s\n", isTrue(expression3) ? "正确" : "不正确");
return 0;
}
3设计一个将十进制正整数转换为十六进制数的算法
代码:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define N 100 // 栈的最大容量
// 定义栈结构体
typedef struct {
char data[N]; // 存储栈元素的数组
int top; // 栈顶指针
} Stack;
// 初始化栈
void init(Stack* s) {
s->top = -1; // 将栈顶指针初始化为 -1,表示栈为空
}
// 判断栈是否为空
bool isSempty(Stack* s) {
if (s == NULL) {
return true; // 如果栈指针为空,认为栈为空
}
return s->top == -1; // 判断栈顶指针是否为 -1
}
// 判断栈是否为满
bool isFull(Stack* s) {
if (s == NULL) {
return false; // 如果栈指针为空,认为栈不满
}
return s->top == N - 1; // 判断栈顶指针是否达到最大值
}
// 入栈操作
bool push(Stack* s, char x) {
if (isFull(s)) {
return false; // 栈满时返回 false
}
s->top = s->top + 1; // 栈顶指针加 1
s->data[s->top] = x; // 将元素 x 压入栈顶
return true; // 成功入栈返回 true
}
// 出栈操作
bool pop(Stack* s, char* x) { // 出栈返回值通过指针传递
if (isSempty(s)) {
return false; // 栈空时返回 false
}
*x = s->data[s->top]; // 将栈顶元素赋值给 x
s->top--; // 栈顶指针减 1
return true; // 成功出栈返回 true
}
// 将十进制整数转换为十六进制字符
char toHexChar(int data) {
if (data >= 0 && data <= 9) {
return '0' + data; // 0-9 转换为 '0'-'9'
} else {
return 'A' + (data - 10); // 10-15 转换为 'A'-'F'
}
}
// 进制转换函数
void transform(int num, int base) {
Stack s;
init(&s); // 初始化栈
while (num > 0) {
push(&s, num % base); // 将余数压入栈
num = num / base; // 更新 num 为商
}
printf("转换为%d进制: ", base); // 输出提示信息
while (!isSempty(&s)) {
char remainder;
pop(&s, &remainder); // 从栈顶依次弹出余数
char hexChar = toHexChar(remainder); // 将余数转换为十六进制字符
printf("%c", hexChar); // 输出字符
}
printf("\n"); // 换行
}
int main() {
int num;
printf("请输入一个整数: ");
scanf("%d", &num); // 获取用户输入的整数
transform(num, 16); // 将输入的整数转换为十六进制
return 0;
}
4设单链表中存放n个字符,利用栈的原理,试设计算法判断字符串是否如ABCD. DCBA那样中心对称
代码:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
char data; // 节点存储的字符数据
struct Node* next; // 指向下一个节点的指针
} Node;
// 初始化链表
Node* InItList(char* arr, int n) {
Node* head = NULL; // 链表头指针
Node* tail = NULL; // 链表尾指针
for (int i = 0; i < n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = arr[i]; // 设置新节点的数据
newNode->next = NULL; // 新节点的下一个节点指针初始化为NULL
if (head == NULL) { // 如果链表为空
head = newNode; // 新节点成为头节点
tail = newNode; // 新节点也成为尾节点
} else {
tail->next = newNode; // 将新节点添加到链表尾部
tail = newNode; // 更新尾指针
}
}
return head; // 返回链表头指针
}
// 判断链表是否中心对称
bool isduichen(Node* head) {
if (head == NULL || head->next == NULL) {
return true; // 空链表或单个元素的链表是中心对称的
}
// 使用快慢指针找到链表的中点
Node* slow = head; // 慢指针
Node* fast = head; // 快指针
Node* pre = NULL; // 记录慢指针的前一个节点
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next; // 快指针每次移动两步
pre = slow; // 记录当前慢指针的位置
slow = slow->next; // 慢指针每次移动一步
}
// 处理奇数长度链表的情况
if (fast != NULL) {
slow = slow->next; // 对于奇数长度的链表,慢指针需要再移动一步
}
// 创建一个栈
Node* stack = NULL;
pre->next = NULL; // 断开前半部分和后半部分的链接
// 将前半部分的字符压入栈中
Node* p = head;
while (p != NULL) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = p->data; // 设置新节点的数据
newNode->next = stack; // 将新节点压入栈顶
stack = newNode; // 更新栈顶指针
p = p->next; // 继续遍历链表
}
// 比较后半部分的字符和栈中的字符
p = slow; // 从中间节点开始遍历后半部分
while (p != NULL) {
if (p->data != stack->data) {
return false; // 字符不匹配,不是中心对称的
}
Node* tmp = stack; // 临时指针指向栈顶节点
stack = stack->next; // 弹出栈顶节点
free(tmp); // 释放栈顶节点的内存
p = p->next; // 继续遍历链表
}
return true; // 字符全部匹配,是中心对称的
}
int main() {
char arr[] = {'a', 'b', 'c', 'b', 'a'}; // 测试字符数组
int n = sizeof(arr) / sizeof(arr[0]); // 计算字符数组的长度
Node* head = InItList(arr, n); // 初始化链表
if (isduichen(head)) {
printf("该链表中的字符串是中心对称的。\n"); // 输出结果
} else {
printf("该链表中的字符串不是中心对称的。\n"); // 输出结果
}
// 释放链表内存(省略具体实现)
return 0;
}
原文地址:https://blog.csdn.net/m0_74859128/article/details/143688500
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!