数据结构实验报告-栈

实  验 三 报  告

一、实验目的

1.掌握栈的定义、特点、逻辑结构，理解栈的抽象数据类型。

2.熟练掌握顺序栈的结构类型定义、特点和基于顺序栈的基本运算的实现。

3.熟练掌握链栈的结构类型定义、特点和基于链栈的基本运算的实现。

4.理解递归算法执行过程中栈的状态变化过程，初步掌握递归的应用。

5.掌握栈的应用。

二、实验内容

1．编写一个算法判断给定的字符向量是否为回文。回文是指正读与反读均相同的字符序列，如" abba "和" abdba "均是回文，但" good "不是回文。

#include <stdio.h>

#include <string.h>

#include <stdbool.h>

bool is_palindrome(char s[]) {

    int i = 0;

    int j = strlen(s) - 1;

    while (i < j) {

        if (s[i] != s[j]) {

            return false;

        }

        i++;

        j--;

    }

    return true;

}

int main() {

    char str1[] = "abba";

    char str2[] = "abdba";

    char str3[] = "good";

    printf("%s\n", is_palindrome(str1) ? "Palindrome" : "Not Palindrome");

    printf("%s\n", is_palindrome(str2) ? "Palindrome" : "Not Palindrome");

    printf("%s\n", is_palindrome(str3) ? "Palindrome" : "Not Palindrome");

    return 0;

}

}

1. 编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {

    int items[MAX_SIZE];

    int top;

} Stack;

void push(Stack *stack, int item) {

    stack->items[++stack->top] = item;

}

int pop(Stack *stack) {

    return stack->items[stack->top--];

}

void reverse_stack(Stack *stack) {

    Stack temp_stack;

    temp_stack.top = -1;

    while (stack->top != -1) {

        push(&temp_stack, pop(stack));

    }

    *stack = temp_stack; // 将逆序后的栈赋值回原栈

}

int main() {

    Stack stack;

    stack.top = -1;

    push(&stack, 1);

    push(&stack, 2);

    push(&stack, 3);

    reverse_stack(&stack);

    while (stack.top != -1) {

        printf("%d\n", pop(&stack));

    }

    return 0;

}

1. 设整数序列a1,a2,…, an ，给出求解其中最大值的递归算法。

#include <stdio.h>

int find_max_recursive(int arr[], int n) {

    if (n == 1) {

        return arr[0];

    }

    int max_rest = find_max_recursive(arr, n - 1);

    return (arr[n - 1] > max_rest) ? arr[n - 1] : max_rest;

}

int main() {

    int arr[] = {3, 7, 2, 8, 5};

    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Max Value: %d\n", find_max_recursive(arr, n));

    return 0;

}

三、实验心得：
在本次实验中，我系统地学习了关于栈的知识，并获得了以下几方面的收获和心得体会：

首先，我深入理解了栈的定义、特点和逻辑结构，以及栈作为一种抽象数据类型的重要性。栈是一种后进先出（LIFO）的数据结构，其特点在于只能在栈顶进行插入和删除操作，这使得栈在很多算法和程序设计中具有重要应用价值。

其次，我熟练掌握了顺序栈和链栈两种结构类型的定义、特点以及基本操作的实现方法。顺序栈通过数组实现，操作简单高效；而链栈则利用链表结构实现，具有更大的灵活性。通过实践操作，我掌握了两种栈结构的操作方式，能够熟练地进行栈的基本操作。

进一步地，我理解了递归算法执行过程中栈的状态变化过程，以及递归在算法设计中的应用。递归算法的本质是将大问题划分为相同或类似的子问题，通过不断调用函数自身来解决问题。而栈在递归执行过程中扮演了关键的角色，记录了每一层递归的信息。

最后，我认识到栈在实际应用中的广泛性和重要性。栈在计算机科学中有着诸多应用，如表达式求值、函数调用和递归实现等。通过本次实验的学习，我不仅提升了对栈的理论认识，同时也增强了自己的算法设计能力和应用实践能力，在未来的学习和工作中能够更好地运用栈这一数据结构。