上一页 下一页

C 编程基础

一个链式栈示例

动态数据结构的一个很好例子是一个简单的栈库，它使用动态列表并包含初始化 (init)、清空 (clear)、压入 (push) 和弹出 (pop) 等函数。该库的头文件如下所示：

/* Stack Library - This library offers the
   minimal stack operations for a
   stack of integers (easily changeable) */

typedef int stack_data;

extern void stack_init();
/* Initializes this library.
   Call first before calling anything. */

extern void stack_clear();
/* Clears the stack of all entries. */

extern int stack_empty();
/* Returns 1 if the stack is empty, 0 otherwise. */

extern void stack_push(stack_data d);
/* Pushes the value d onto the stack. */

extern stack_data stack_pop();
/* Returns the top element of the stack,
   and removes that element.
   Returns garbage if the stack is empty. */

该库的代码文件如下：

广告

#include "stack.h"
#include <stdio.h>

/* Stack Library - This library offers the
   minimal stack operations for a stack of integers */

struct stack_rec
{
    stack_data data;
    struct stack_rec *next;
};

struct stack_rec *top=NULL;

void stack_init()
/* Initializes this library.
   Call before calling anything else. */
{
    top=NULL;
}

void stack_clear()
/* Clears the stack of all entries. */
{
    stack_data x;

    while (!stack_empty())
    x=stack_pop();
}

int stack_empty()
/* Returns 1 if the stack is empty, 0 otherwise. */
{
    if (top==NULL)
        return(1);
    else
        return(0);
}

void stack_push(stack_data d)
/* Pushes the value d onto the stack. */
{
    struct stack_rec *temp;
    temp=
  (struct stack_rec *)malloc(sizeof(struct stack_rec));
    temp->data=d;
    temp->next=top;
    top=temp;
}

stack_data stack_pop()
/* Returns the top element of the stack,
   and removes that element.
   Returns garbage if the stack is empty. */
{
    struct stack_rec *temp;
    stack_data d=0;
    if (top!=NULL)
    {
        d=top->data;
        temp=top;
        top=top->next;
        free(temp);
    }
    return(d);
}

请注意该库如何实践信息隐藏：只能看到头文件的人无法判断栈是使用数组、指针、文件还是其他方式实现的。另请注意，C 语言使用 NULL。NULL 在 stdio.h 中定义，因此在使用指针时几乎总是需要包含 stdio.h。NULL 等同于零。

C 语言常见错误

  • 在引用记录时忘记包含括号，如上文的 (*p).i。
  • 未能释放您分配的任何块——例如，在栈函数中不应将 top 设置为 NULL，因为该操作会导致需要释放的块变为孤立块。
  • 在任何指针操作中忘记包含 stdio.h，导致无法访问 NULL。

其他尝试

向栈库添加 dup、count 和 add 函数，分别用于复制栈顶元素、返回栈中元素的数量以及将栈中顶部两个元素相加。

引用