C语言详解：栈的结构与操作(初学者指南)

需积分: 9 22 浏览量更新于2024-09-18 收藏 39KB DOC 举报

本文档详细介绍了栈的基本结构和操作，使用C语言进行描述，特别适合数据结构初学者。栈是一种具有特定顺序访问规则的数据结构，遵循“后进先出”（LIFO，Last In First Out）的原则。这里主要关注的是栈的顺序存储表示，通过数组实现。首先，定义了几个关键的数据类型，如`Status`（用于表示函数结果的状态，如OK、ERROR等）、`Boolean`（布尔类型，代表TRUE或FALSE）以及栈元素类型`SElemType`。接着，我们看到`SqStack`结构体，它包含以下成员： 1. `base`：栈底指针，初始化时为NULL。 2. `top`：栈顶指针，指向栈内当前元素的位置。 3. `stacksize`：当前已分配的栈空间，以元素计。接下来，文档介绍了栈的四个基本操作： 1. **InitStack(SqStack *S)**：构造一个新的栈，函数会为栈分配初始容量`STACK_INIT_SIZE`（这里是12），并将`base`和`top`都设置为NULL。 2. **DestoryStack(SqStack *S)**：销毁栈`S`，释放之前分配的所有内存空间，确保栈不再被使用。 3. **ClearStack(SqStack *S)**：清空栈`S`，将`top`指针指向`base`，即栈底，表示栈中没有元素。 4. **StackEmpty(SqStack S)**：判断栈`S`是否为空，如果`top`等于`base`，则返回TRUE，表示栈空；反之返回FALSE。 5. **StackLength(SqStack S)**：返回栈`S`的元素个数，即`top`与`base`之间的距离，不包括`base`。 6. **GetTop(SqStack S, SElemType *e)**：如果栈不为空，将栈顶元素存储到`e`中，并返回TRUE；否则返回FALSE。 7. **Push(SqStack *S, SElemType e)**：将元素`e`压入栈顶，如果栈未满（即`stacksize`还有空间），则更新`top`指针并增加`stacksize`；否则返回OVERFLOW错误。 8. **Pop(SqStack *S, SElemType *e)**：如果栈不为空，弹出栈顶元素并将其存储到`e`中，然后更新`top`指针。若栈已空，返回ERROR。这些操作都是为了实现栈的基本功能，如元素的存取和管理，是许多算法和数据结构应用的基础。掌握栈的操作有助于理解其他高级数据结构，如递归调用栈、表达式求值、括号匹配等。对于学习C语言的数据结构编程，理解和实现这些基本操作至关重要。

#include<stdio.h> /* EOF(=^Z 或 F6),NULL */

#include<stdlib.h> /* atoi() */

#include<string.h>

#include<malloc.h> /* malloc()等 */

#include<io.h> /* eof() */

#include<process.h> /* exit() */

/* 函数结果状态代码 */

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */

typedef int Boolean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */

typedef int SElemType; // 定义栈元素类型

//栈的顺序存储表示

#define STACK_INIT_SIZE 12 //存储空间初始分配量

#define STACKINCREMENT 2 //存储空间分配增量

typedef struct{

SElemType *base;//栈底指针，在构造之前和销毁之后，base 为 NULL

SElemType *top;//栈顶指针

int stacksize;//当前已分配的栈空间，以元素为单位

}SqStack;

//-----栈的基本操作-------

Status InitStack(SqStack *S);//构造一个新的栈

Status DestoryStack(SqStack *S);//销毁栈 S

Status ClearStack(SqStack *S);//把栈 S 置为空

Status StackEmpty(SqStack S);//判断 S 是否为空，若为空，返回 TRUE，否则返回 FALSE

int StackLength(SqStack S);//返回 S 的元素个数，及栈的长度

Status GetTop(SqStack S,SElemType *e);// 若栈不为空，用 e 返回 S 的栈顶元素，并返回

TRUE，否则返回 FALSE

Status Push(SqStack *S,SElemType e);//插入元素 e 为新的栈顶元素

Status Pop(SqStack *S,SElemType *e);//若栈不为空，则删除栈顶元素，并用 e 返回其值，返

回 OK，否则返回 ERROR

Status StackTraverse(SqStack S,Status(*visit)());//从栈顶到栈底依次对栈中每个元素调用函数

visit(),一旦调用 visit()失败，则操作失败

Status visit(SElemType c);

下载后可阅读完整内容，剩余3页未读，立即下载

zhangchao3322218

粉丝: 175
资源: 13

C语言详解：栈的结构与操作(初学者指南)

《数据结构—用C语言描述》

《数据结构——用C语言描述》-蔡明志

栈的基本操作的实现c语言

用c语言描述栈10个基本操作的头文件

C语言描述 数据结构C语言描述课件

数据结构辅导书 c语言描述

数据结构与算法 c语言描述

用栈实现迷宫求解c语言描述

数据结构课件 (c语言描述)

数据结构课件(c语言描述)

最新资源

C语言描述数据结构C语言描述课件