自学内容网 自学内容网

算法设计题(栈)

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)!