正文

轻松掌握C语言：如何高效建立堆栈函数及实际应用案例

/0 浏览量
0424

在C语言编程中，堆栈是一种非常重要的数据结构，它用于存储局部变量、函数参数、返回地址等信息。掌握堆栈函数的建立对于提高程序效率和安全性至关重要。本文将详细介绍如何在C语言中高效建立堆栈函数，并探讨其实际应用案例。

堆栈的基本概念

堆栈是一种后进先出（LIFO）的数据结构，它允许在顶部添加或删除元素。在C语言中，堆栈通常通过数组或链表实现。数组实现简单，但固定大小可能限制其使用；链表则更加灵活，但需要额外的内存管理。

堆栈函数的建立

使用数组实现堆栈

以下是一个使用数组实现的堆栈函数示例：

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int item) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++s->top] = item;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->items[s->top--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->items[s->top];
}

使用链表实现堆栈

使用链表实现的堆栈更加灵活，以下是一个简单的链表堆栈实现：

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

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

typedef struct {
    Node *top;
} Stack;

void initStack(Stack *s) {
    s->top = NULL;
}

bool isFull(Stack *s) {
    // 对于链表，我们通常不关心是否满了，因为链表可以动态扩展
    return false;
}

bool isEmpty(Stack *s) {
    return s->top == NULL;
}

void push(Stack *s, int item) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = item;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    Node *temp = s->top;
    int item = temp->data;
    s->top = s->top->next;
    free(temp);
    return item;
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->top->data;
}

实际应用案例

递归函数中的堆栈

在C语言中，递归函数通常会使用堆栈来存储函数调用的信息。以下是一个使用递归计算阶乘的例子：

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int number = 5;
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

在这个例子中，每次递归调用都会在堆栈上添加一个新的帧，直到达到基线条件。

实现深度优先搜索（DFS）

在图论中，深度优先搜索是一种常用的遍历算法。以下是一个使用堆栈实现DFS的例子：

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

#define MAX_VERTICES 100

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

typedef struct {
    Node *head;
} Stack;

void initStack(Stack *s) {
    s->head = NULL;
}

bool isEmpty(Stack *s) {
    return s->head == NULL;
}

void push(Stack *s, int vertex) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = s->head;
    s->head = newNode;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        return -1;
    }
    Node *temp = s->head;
    int vertex = temp->vertex;
    s->head = s->head->next;
    free(temp);
    return vertex;
}

void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int start) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < MAX_VERTICES; i++) {
        graph[i][start] = 1;
    }

    push(&stack, start);

    while (!isEmpty(&stack)) {
        int current = pop(&stack);
        printf("Visited vertex: %d\n", current);

        for (int i = 0; i < MAX_VERTICES; i++) {
            if (graph[current][i] == 1 && graph[i][current] == 0) {
                graph[i][current] = 1;
                push(&stack, i);
            }
        }
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {0};
    int startVertex = 0;

    // 构建图...
    DFS(graph, startVertex);
    return 0;
}

在这个例子中，我们使用堆栈来存储需要访问的顶点，实现深度优先搜索。

通过以上示例，我们可以看到堆栈在C语言编程中的强大功能和广泛应用。掌握堆栈函数的建立对于编写高效、安全的C语言程序至关重要。

-- 展开阅读全文 --