《大话数据结构》读书笔记之栈抽象数据类型（数组实现）

/*
    Name: 栈抽象数据类型（使用数组实现）
    Copyright:
    Author: 巧若拙
    Date:13-09-14 18:28
    Description:
*/

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

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

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

typedef struct{
    ElemType data[MAXSIZE];//数组存储栈元素
    int top;//栈顶指针
} SqStack;

Status InitStack(SqStack *S);//建立一个空的栈S
Status StackEmpty(SqStack S);//若栈为空，返回TRUE，否则返回FALSE
Status ClearStack(SqStack *S);//将栈清空
int StackLength(SqStack S);//返回栈S的元素个数
Status DisplayStack(SqStack S);//输出栈S的所有元素
Status GetTop(SqStack S, ElemType *e);//用e返回栈S的栈顶元素
Status LocateElem(SqStack S, ElemType e);//在栈S中查找是否存在与给定值e相等的元素
Status Push(SqStack *S, ElemType e);//在栈S中插入新元素e
Status Pop(SqStack *S, ElemType *e);//删除栈S的栈顶元素，并将该元素值赋给e

int main(void)
{
    SqStack a;
    ElemType *p, e = 0;
    int i;
   
    InitStack(&a);//建立一个空的栈
   
    for (i=0; i<MAXSIZE; i++)
    {
        Push(&a, i+1);//在栈S中插入新元素e
    }
   
    DisplayStack(a);
   
    for (i=1; i<StackLength(a); i+=2)
    {
        Pop(&a, &e);//删除栈S的栈顶元素，并将该元素值赋给e
    }
    printf("e = %d\n", e);
   
    DisplayStack(a);
 
    e = 50;
    if (LocateElem(a, e))//在栈S中查找是否存在与给定值e相等的元素
    {
        printf("存在%d\n", e);
    }
    else
    {
        printf("不存在%d\n", e);
        Push(&a, e);//在栈S中插入新元素e
    }
   
    DisplayStack(a);
   
    ClearStack(&a);//将栈清空
    DisplayStack(a);
   
    return 0;
}

/*
函数功能：建立一个空的栈S
初始条件：无
操作结果：初始化栈S。操作成功返回OK，否则返回ERROR  
*/
Status InitStack(SqStack *S)
{
    S->top = -1;
   
    return OK;
}

/*
函数功能：判断栈是否为空
初始条件：顺序栈S已经存在
操作结果：若栈为空，返回TRUE，否则返回FALSE
*/
Status StackEmpty(SqStack S)
{
    return (S.top == -1) ? TRUE : FALSE;
}

/*
函数功能：将栈清空
初始条件：顺序栈S已经存在
操作结果：将栈清空。操作成功返回OK，否则返回ERROR  
*/
Status ClearStack(SqStack *S)
{
    if (S == NULL)
    {
        return ERROR;
    }
   
    S->top = -1;
    return OK;
}

/*
函数功能：返回栈S的元素个数
初始条件：顺序栈S已经存在
操作结果：返回栈S的元素个数
*/
int StackLength(SqStack S)
{
    return S.top + 1;
}

/*
函数功能：输出栈S的所有元素
初始条件：顺序栈S已经存在
操作结果：输出栈S的所有元素。操作成功返回OK，否则返回ERROR
*/
Status DisplayStack(SqStack S)
{
    int i;
   
    if (S.top == -1)
    {
        printf("none!\n");   
        return ERROR;
    }
   
    for (i=0; i<=S.top; i++)
    {
        printf("data[%d] = %d, ", i, S.data[i]);
    }
    printf("\n");
        
    return OK;
}

/*
函数功能：用e返回栈S的栈顶元素
初始条件：顺序栈S已经存在
操作结果：用e返回栈S的栈顶元素。操作成功返回OK，否则返回ERROR
*/
Status GetTop(SqStack S, ElemType *e)
{
    if (S.top == -1)
    {
        return ERROR;
    }
   
    *e = S.data[S.top];
    return OK;
}

/*
函数功能：在栈S中查找是否存在与给定值e相等的元素
初始条件：顺序栈S已经存在
操作结果：在栈S中查找是否存在与给定值e相等的元素。找到返回TRUE，否则返回FALSE
*/
Status LocateElem(SqStack S, ElemType e)
{
    int i;
   
    for (i=0; i<=S.top; i++)
    {
        if (S.data[i] == e)
        {
            return TRUE;
        }
    }
   
    return FALSE;
}

/*
函数功能：在栈S中插入新元素e
初始条件：顺序栈S已经存在
操作结果：在栈S中插入新元素e。操作成功返回OK，否则返回ERROR  
*/
Status Push(SqStack *S, ElemType e)
{
    if (S->top == MAXSIZE - 1)
    {
        return ERROR;
    }
   
    S->top++;
    S->data[S->top] = e;
   
    return OK;
}

/*
函数功能：删除栈S的栈顶元素，并将该元素值赋给e
初始条件：顺序栈S已经存在
操作结果：删除栈S的栈顶元素，并将该元素值赋给e。
操作成功返回OK，否则返回ERROR  
*/
Status Pop(SqStack *S, ElemType *e)
{
    if (S->top == -1)
    {
        return ERROR;
    }
   
    *e = S->data[S->top];
    S->top--;
   
    return OK;
}