首页 > 其他分享 >栈和队列章节课后习题答案集锦

栈和队列章节课后习题答案集锦

时间：2024-03-21 18:32:47浏览次数：23  
标签：return 课后 int top Stack 集锦 printf 习题 stack

目录

4.3

4.4

4.5

4.8

4.9

4.11

4.12

4.3

#include <stdio.h>
#include <stdlib.h>

// 定义栈的最大容量
#define MAX_SIZE 100

// 定义栈结构
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 入栈操作
void push(Stack *s, char c) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack is full\n");
        exit(1);
    }
    s->data[++(s->top)] = c;
}

// 出栈操作
char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

// 车厢调度函数
void trainDispatch(char *carriages, int n) {
    Stack s;
    initStack(&s);

    int i = 0;
    while (i < n) {
        // 如果栈为空或者栈顶车厢不是硬卧车厢，则将当前车厢入栈
        if (isEmpty(&s) || s.data[s.top] != 'H') {
            push(&s, carriages[i++]);
        } else {
            // 否则将栈顶车厢出栈，并输出出栈操作
            char c = pop(&s);
            printf("出栈: %c\n", c);
        }
    }

    // 将栈中剩余的车厢依次出栈
    while (!isEmpty(&s)) {
        char c = pop(&s);
        printf("出栈: %c\n", c);
    }
}

int main() {
    int n;
    printf("请输入车厢数量: ");
    scanf("%d", &n);

    char carriages[MAX_SIZE];
    printf("请输入车厢序列（例如：SHSHS）: ");
    scanf("%s", carriages);

    trainDispatch(carriages, n);

    return 0;
}

4.4

#include <stdio.h>
#include <string.h>

int isPattern(char *sequence) {
    int length = strlen(sequence);
    int i, j, k;

    for (i = 1; i < length - 1; i++) {
        if (sequence[i] == '&') {
            // 分割序列
            char sequence1[50];
            char sequence2[50];
            strncpy(sequence1, sequence, i);//strncpy用于将一个字符串的一部分复制到另一个字符串中 
            sequence1[i] = '\0';
            strncpy(sequence2, sequence + i + 1, length - i - 1);
            sequence2[length - i - 1] = '\0';

            // 检查序列2是否是序列1的逆序列的逆序列
            int len1 = strlen(sequence1);
            int len2 = strlen(sequence2);
            if (len1 != len2) {
                return 0;
            }
            for (j = 0, k = len2 - 1; j < len1 && k >= 0; j++, k--) {
                if (sequence1[j] != sequence2[k]) {
                    return 0;
                }
            }
            if (j != len1 || k != -1) {
                return 0;
            }
            return 1;
        }
    }
    return 0;
}

int main() {
    char sequence[100];
    printf("请输入一个以'@'为结束符的字符序列：\n");
    scanf("%[^@]s", sequence);//表示除了@之外的字符输入，^表示取反 

    if (isPattern(sequence)) {
        printf("该字符序列符合模式。\n");
    } else {
        printf("该字符序列不符合模式。\n");
    }

    return 0;
}

4.5

#include <stdio.h>
#include <stdbool.h>

// 定义栈结构
#define MAX_SIZE 100
typedef struct {
    char items[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *stack) {
    stack->top = -1;
}

// 压栈
void push(Stack *stack, char c) {
    stack->items[++stack->top] = c;
}

// 弹栈
char pop(Stack *stack) {
    return stack->items[stack->top--];
}

// 判断括号是否合法
bool isValidParentheses(char *expression) {
    Stack stack;
    initStack(&stack);

    while (*expression) {
        if (*expression == '(' || *expression == '{' || *expression == '[') {
            push(&stack, *expression);
        } else if (*expression == ')' || *expression == '}' || *expression == ']') {
            if (stack.top == -1) {
                return false; // 右括号多余，返回 false
            }
            char topChar = pop(&stack);
            if ((*expression == ')' && topChar != '(') ||
                (*expression == '}' && topChar != '{') ||
                (*expression == ']' && topChar != '[')) {
                return false; // 括号不匹配，返回 false
            }
        }
        expression++;
    }
    return stack.top == -1; // 栈为空则括号匹配，否则返回 false
}

int main() {
    char expression[] = "{[()]}";
    if (isValidParentheses(expression)) {
        printf("括号匹配\n");
    } else {
        printf("括号不匹配\n");
    }
    return 0;
}

4.8

#include <stdio.h>
#include <stdlib.h>

// 定义栈节点结构体
typedef struct StackNode {
    int m;
    int n;
    int result;
    struct StackNode* next;
} StackNode;

// 定义栈结构体
typedef struct {
    StackNode* top;
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}

// 入栈
void push(Stack* stack, int m, int n, int result) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->m = m;
    newNode->n = n;
    newNode->result = result;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈
void pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack is empty.\n");
        exit(1);
    }
    StackNode* temp = stack->top;
    stack->top = stack->top->next;
    free(temp);
}

// 取栈顶元素
StackNode* top(Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return stack->top;
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 非递归形式的 g 函数
int g(int m, int n) {
    Stack stack;
    initStack(&stack);
    int result = 0;
    push(&stack, m, n, result);

    while (!isEmpty(&stack)) {
        StackNode* topNode = top(&stack);
        if (topNode->m == 0 && topNode->n >= 0) {
            topNode->result = 0;
        } else if (topNode->m > 0 && topNode->n >= 0) {
            pop(&stack);
            push(&stack, topNode->m - 1, 2 * topNode->n, 0);
            push(&stack, 0, 0, topNode->n);
            continue;
        }
        if (!isEmpty(&stack)) {
            StackNode* parent = top(&stack);
            parent->result += topNode->result;
        }
        pop(&stack);
    }
    return result;
}

int main() {
    int m, n;
    printf("Enter the values of m and n: ");
    scanf("%d %d", &m, &n);
    printf("g(%d, %d) = %d\n", m, n, g(m, n));
    return 0;
}

4.9

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* rear;
} Queue;

void initQueue(Queue* q) {
    q->rear = NULL;
}

void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = value;
    if (q->rear == NULL) {
        q->rear = newNode;
        newNode->next = newNode;
    } else {
        newNode->next = q->rear->next;
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeue(Queue* q) {
    if (q->rear == NULL) {
        printf("Queue is empty.\n");
        exit(1);
    }

    Node* front = q->rear->next;
    int value = front->data;

    if (q->rear == front) {
        free(front);
        q->rear = NULL;
    } else {
        q->rear->next = front->next;
        free(front);
    }
    return value;
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Dequeued element: %d\n", dequeue(&q));
    return 0;
}

4.11

#include <stdio.h>
#include <stdlib.h>

#define maxSize 5  // 假设队列最大容量为 5

typedef struct {
    int data[maxSize];
    int rear;   // 队尾指针
    int length; // 队列中元素个数
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->rear = 0;
    q->length = 0;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->length == 0;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return q->length == maxSize;
}

// 入队
void enQueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full, cannot enqueue.\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % maxSize;
    q->length++;
}

// 出队
int deQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty, cannot dequeue.\n");
        exit(1);
    }
    int value = q->data[(q->rear - q->length + maxSize) % maxSize];
    q->length--;
    return value;
}

int main() {
    Queue q;
    initQueue(&q);
    // 入队操作
    enQueue(&q, 1);
    enQueue(&q, 2);
    enQueue(&q, 3);
    enQueue(&q, 4);
    enQueue(&q, 5);
    // 队满，无法再入队
    enQueue(&q, 6);
    // 出队操作
    printf("Dequeued element: %d\n", deQueue(&q));
    printf("Dequeued element: %d\n", deQueue(&q));
    printf("Dequeued element: %d\n", deQueue(&q));
    printf("Dequeued element: %d\n", deQueue(&q));
    printf("Dequeued element: %d\n", deQueue(&q));
    // 队空，无法再出队
    deQueue(&q);
    return 0;
}

4.12

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_LENGTH 100

// 定义栈结构
typedef struct {
    char data[MAX_LENGTH];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_LENGTH - 1;
}

// 入栈
void push(Stack *s, char c) {
    if (isFull(s)) {
        printf("栈已满，无法入栈\n");
        return;
    }
    s->data[++(s->top)] = c;
}

// 出栈
char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈已空，无法出栈\n");
        return '\0';
    }
    return s->data[(s->top)--];
}

int main() {
    char str[MAX_LENGTH];
    char ch;
    int length = 0;
    Stack s;
    initStack(&s); // 初始化
    printf("请输入以#结束的字符序列：\n");
    while ((ch = getchar()) != '#') {
        if (length >= MAX_LENGTH - 1) {
            printf("字符序列过长！\n");
            return 1;
        }
        str[length++] = ch;
        push(&s, ch); // 将字符压入栈中
    }
    str[length] = '\0'; // 添加字符串结束符
    // 依次弹出栈中的字符与字符序列比较
    bool isPalindrome = true;
    int i;
    for (i = 0; i < length; i++) {
        if (str[i] != pop(&s)) {
            isPalindrome = false;
            break;
        }
    }
    if (isPalindrome) {
        printf("是回文字符串\n");
    } else {
        printf("不是回文字符串\n");
    }

    return 0;
}

标签：return,课后,int,top,Stack,集锦,printf,习题,stack
From： https://blog.csdn.net/m0_72674633/article/details/136858423

相关文章

  • [数组练习题]二分法查找操作实例:使用二分法查找有序数组中元素。 找到返回索引，不存在
    文章目录题干一、题目分析1.定义数组,用于后续在数组中查找元素2.对数组进行排序3.定义方法4.调用方法,打印输出二、代码1.代码块2.一图流总结题干提示：这段是题干,仔细阅读仔细分析：二分法查找操作：使用二分法查找有序数组中元素。找到返回索引，不存在输出-1。......
  • 概率期望进阶 + Min-Max容斥 练习题
    Luogu5644[PKUWC2018]猎人杀link题意：有\(n\)个人，每次在剩下的人中选择一个人杀死，选择\(i\)的概率为\(\dfrac{w_i}{\sum_jw_j}\)，求第\(1\)个人是最后一个杀死的概率，答案对\(998244353\)取模。\(w_i\ge1,\space\sum\limits_{i=1}^nw_i\le10^5\)考虑容斥，枚举钦定......
  • 习题加餐4. 鸡哥的购物挑战
     问题描述鸡哥在“无尽的夏日”购物节上看中了一系列的商品，这些商品的价格各不相同。然而，鸡哥的购物车有一条特殊的规则：购物车中的商品数量必须是偶数个。鸡哥希望在满足购物车规则的前提下，选择总价值最高的商品。他将商品的价格列表给了你，希望你能帮他计算出他能购买到的......
  • Hive SQL必刷练习题：向用户推荐朋友收藏的商品(两种思路)
    问题需求：需要请向所有用户推荐其朋友收藏但是用户自己未收藏的商品，请从好友关系表（friendship_info）和收藏表（favor_info）中查询出应向哪位用户推荐哪些商品。期望结果如下：1）部分结果展示user_id（用户id）sku_id（应向该用户推荐的商品id）101210141017101910181011110112）相关表结构......
  • 第三章课后习题
    一、分析计算机页面布局   实现如下图所示的效果图实现步骤     在zy3.wxml中写下以下代码：<viewclass="c1"><viewclass="ly-top"><viewclass="sc">3×8</view></view><viewclass="ly-bottom">......
  • pyCharm oj 习题 列表合并、去重、排序
    列表合并、去重、排序ProblemDescription从键盘输入两个数列，构成两个列表list1、list2，合并这两个列表为list3，将list3去掉重复元素、降序排序后生成list4.InputDescription输入两个数列，以英文逗号分隔OutputDescription输出列表list1、list2、list3、list4SampleInpu......
  • 线性表章节课后习题答案集锦
    目录2.52.62.72.82.92.102.112.122.132.5/*要比较两个单词在字典中的顺序，可以逐个比较它们的字符。首先比较两个单词的第一个字符，如果相同，则继续比较下一个字符，直到找到不同的字符或者某个单词比较完毕。比较时，可以利用ASCII码进行比较，因为字母在ASCII码中是按顺......
  • 蓝桥练习题-K倍区间
    16.k倍区间-蓝桥云课(lanqiao.cn)首先，看到这个题，想到暴力求解，但显然，数据过大，暴力法过不了；然后看到了一个办法：对所有元素的前缀和取K的模，若s[i],s[j]相同，则在j-1到i的区间内，区间和为K的倍数。C++代码：#include<iostream>#include<queue>usingnamespacestd;ty......
  • 蓝桥练习题-分考场
    0分考场-蓝桥云课(lanqiao.cn)思路：暴力dfs，dfs(x,room)x为待放入教室的人，room为当前最大有几号教室，对x依次遍历教室1到教室room，若某教室当前没该同学认识的人，直接放入，接着放下一个人，若room个教室里都存在x认识的人，即x不能放入任何教室，则在开辟一块新教室放入该同学，dfs结束......
  • 数组练习-小习题
    多个字符从两端开始移动，向中间汇聚输出，例如：打印Hello，word！第一个打印出来H（左一），然后打印！（右一），接着e（右二），下面是d（左二）.......依次打印，这里介绍一个关键字：strlen（），用来测量字符串的长度，注意字符串如果带有"\0",strlen是不计算\0的，只计算\0之前的字符数。system（“cls”）：清理屏幕。#i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99