数据结构——栈

班公湖里洗过脚

1277人浏览 · 2018-02-12 09:41:30

班公湖里洗过脚 · 2018-02-12 09:41:30 发布

栈是一种重要的数据结构，它广泛应用于各种软件系统中，这种数据结构与线性表有密切的联系。从逻辑上看，栈属于线性结构，是一种特殊的线性表。其特殊性在于栈的基本操作是线性表操作的子集，它是限定公在表尾进行插入或删除操作的线性表，是操作受限的线性表。

学习要点：

1.了解栈的概念。

2.掌握栈的数据结构定义方法和基本运算的实现方法。

3.能够使用栈这种数据结构来解决具体的问题

栈的定义

栈（Stack）是一种特殊的线性表，是限定公在表尾进行插入或删除操作的线性表。栈的表尾称为栈顶（top），处于栈顶位置的数据元素称为栈顶元素。栈的表头称为栈底（bottom），处于栈底位置的数据元素称为栈底元素。不含任何元素的表称为空栈。

下面来看栈的使用代码实现

1. 栈的顺序存储的实现

【问题描述】

实现栈的顺序存储结构的基本运算。

【算法描述】

要求通过具体的算法来实现栈的顺序存储。首先建立栈的顺序结构，对栈的各个运算的算法做详细的描述，然后在主函数中通过函数调用实现顺序栈的置空、数据元素进栈、出栈等。

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define EQUAL 1
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int ElementType ;
struct STU
{
    char name[20];
    char stuno[10];
    int age;
    int score;
};
typedef struct STU SElemType;
struct STACK
{
    SElemType *base;
    SElemType *top;
    int stacksize;
};
typedef struct STACK SqStack;
typedef struct STACK *pSqstack;
ElementType InitStack(SqStack **S);
void DestroyStack(SqStack *S);
void ClearStack(SqStack *S);
ElementType StackEmpty(SqStack S);
int StackLength(SqStack S);
ElementType GetTop(SqStack S,SElemType *e);
ElementType Push(SqStack *S,SElemType e);
ElementType Pop(SqStack *S,SElemType *e);
ElementType StackTraverse(SqStack S,ElementType (*visit)());


ElementType InitStack(SqStack **S) /* 栈的初始化 */
{
    (*S)=(SqStack *) malloc(sizeof(SqStack));
    (*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
    if(!(*S)->base)
        exit(OVERFLOW);
    (*S)->top=(*S)->base;
    (*S)->stacksize=STACK_INIT_SIZE;
    return OK;
}
void DestroyStack(SqStack *S) /* 栈的释放 */
{
    free(S->base);
    free(S);
}

void ClearStack(SqStack *S) /* 栈的置空 */
{
    S->top=S->base;
}

ElementType StackEmpty(SqStack S)
{
    if(S.top==S.base)
        return TRUE;
    else
        return FALSE;
}

int StackLength(SqStack S)
{
    int i;
    SElemType *p;
    i=0;
    p=S.top;
    while(p!=S.base)
    {
        p++;
        i++;
    }

    return i;
}

ElementType GetTop(SqStack S,SElemType *e)
{
    if(S.top==S.base) return ERROR;
    *e=*(S.top-1);
    return OK;
}

ElementType Push(SqStack *S,SElemType e)
{
    *(S->top++)=e;
    return OK;
}

ElementType Pop(SqStack *S,SElemType *e)
{
    if(S->top==S->base) return ERROR;
    *e=*--S->top;
    return OK;
}

ElementType StackPrintElem(SElemType * e)
{
    printf("%s %s %d %d\n",e->name,e->stuno,e->age,e->score);
}

ElementType StackTraverse(SqStack S, ElementType (*visit)())
{
    while(S.top!=S.base)
        visit(--S.top);
}

int main(void) /* 顺序栈的主函数 */
{
    SElemType e;
    SqStack *Sa;

    printf("\n\n------------SqStack Demo is running...-----------\n\n");
    printf("First is Push function.\n");
    InitStack(&Sa);
    strcpy(e.name,"stu1");
    strcpy(e.stuno,"100001");
    e.age=80;
    e.score=1000;
    printf("Now Stack is Empty.\n");
    StackTraverse(*Sa,StackPrintElem);
    Push(Sa,e);
    printf("Now Stack has one element.\n");
    StackTraverse(*Sa,StackPrintElem);
    strcpy(e.name,"stu3");
    strcpy(e.stuno,"100002");
    e.age=80;
    e.score=1000;
    Push(Sa,e);
    printf("Now Stack has another element.\n");
    StackTraverse(*Sa,StackPrintElem);
    printf("Now Pop Stack,the top elem put into variable e.\n");
    Pop(Sa,&e);
    printf("%s\n%s\n%d\n%d\n",e.name,e.stuno,e.age,e.score);
    printf("Let's see the left of Stack's elem:\n");
    StackTraverse(*Sa,StackPrintElem);

    printf("\n\n\nWelcom to visit http://zmofun.topcool.net\n\n");

    return 0;
}

运行结果

2. 栈的链式存储的实现

【问题描述】

链栈是栈的另一种存储方式，要求通过具体的算法实现链栈的倒置、出栈等运算。

【算法描述】

在设计链栈的基本运算之前，首先定义链栈的存储类型、结点类型，然后分别设计各种运算的具体函数。最后在主函数中实现链栈的各种运算时，分别调用相应的函数即可。

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

#define NULL 0

typedef char ElementType;

typedef struct stacknode
{
     ElementType data;
     struct stacknode *next;
}StackNode;

typedef struct
{
     StackNode *top;
}LinkStack;

void InitStack(LinkStack *s)
{
     s->top=NULL;
}

int StackEmpty(LinkStack *s)
{
    return s->top==NULL;
}
/* 链栈的节点是动态分配的,无须判断 Full(上溢) */
void Push(LinkStack *s, ElementType x)
{
    StackNode *p;
    p=malloc(sizeof(StackNode));
    p->next=s->top;             /* 由于是在栈顶 PUSH，所以要指向栈顶 */
    p->data=x;
    s->top=p;                   /* 插入 */
}

ElementType Pop(LinkStack *s)
{
    ElementType x;
    StackNode *p=s->top;        /* 指向栈顶 */
    if (StackEmpty(s))
    {
         printf("栈为空,不能出栈...\n");
         exit(-1);
    }
    x=p->data;
    s->top=p->next;             /* 当前的栈顶指向原栈的 next */
    free(p);
    return x;
}

ElementType StackTop(LinkStack *s)
{
    if (StackEmpty(s))
    {
         printf("栈为空,不能出栈...\n");
         exit(-1);
    }
    return s->top->data;
}

void Disp(LinkStack *s)
{
      StackNode *p=s->top;
      printf("=======================================\n");
      while (p!=NULL)
      {
         printf("\n%c",p->data);
         p=p->next;
      }
      printf("=======================================\n");
}

void RevStack(LinkStack *s)
{
     int i, n=0;
     char dat[50];
     while(!StackEmpty(s))
     {
         dat[n]=Pop(s); /* 保存退栈后的数据到数组 */
         n++;
     }
     for (i=0;i<n;i++)
        Push(s,dat[i]);
}

int main(void)
{
     LinkStack * s=(LinkStack *)malloc(sizeof(LinkStack));
     char ch,ch2,ch3;
     printf("================= 链栈操作 DEMO =================\nn");
     InitStack(s);
     printf("依次压栈 a,b,c,d,e 后,栈中的数据为：\n");
     Push(s,'a');
     Push(s,'b');
     Push(s,'c');
     Push(s,'d');
     Push(s,'e');
     Disp(s);
     printf("\n 将此栈倒置,栈中的数据序列为：\n");
     RevStack(s);
     Disp(s);
     ch=Pop(s);
     printf("\n 出栈操作开始,第一次出栈得到的数据：%c",ch);
     ch2=Pop(s);
     printf("\n 第二次出栈得到的数据：%c",ch2);
     ch3=StackTop(s);
     printf("\n 此时的栈顶元素为：%c",ch3);

     return 0;
}

运行结果：

3. 计算表达式的值

【问题描述】

计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式，比中缀表达式计算起来更方便简单些，中缀表达式计算存在着括号的匹配问题，所以在计算表达式值时一般都是先转换成后缀表达式，再用后缀法计算表达式的值。如表达式(a+b*c)/d-e 用后缀法表示应为 abc*+d/e-1。只考虑四则算术运算，且假设输入的操作数均为 1 位十进制数(0～9)，并且输入的后缀形式表达式不含语法错误。

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

#define add 43
/* 运算符加号'+'的 ASCII 码 */
#define subs 45
/* 运算符减号'-'的 ASCII 码 */
#define mult 42
/* 运算符乘号'*'的 ASCII 码 */
#define div 47
/* 运算符除号'/'的 ASCII 码 */
#define MAXSIZE 100
typedef struct
{
    int stkdata[MAXSIZE];
    /* 用数组来表示栈空间，定义长度为 MAXSIZE 的堆栈 */
    int top ;
    /* 栈顶 */
}STKzone;
typedef STKzone *STK;

typedef enum{ok,error} status;
STKzone expSTKzone;
STK expSTK;
STK initSTK(STKzone *stack_zone)
{
    /* 执行栈初始化，建栈指针 */
    STK p;
    p=stack_zone;
    p->top=0;

    return p;
}

status push(int *term,STK pstk)
{
    /* 将一结构型数据送入栈中 */
    if(pstk->top==MAXSIZE)
        return error; /* 栈满，进栈失败 */
    pstk->stkdata[pstk->top] =*term;
    (pstk->top)++;/* 栈顶指针移动 */
    return ok;
}/* push */
bool emptySTK(STK pstk)
{

    return(pstk->top==0);
}
status pop(int *pdata, STK pstk)
{
    /* 从栈中取出一结构型数据 */
    if(emptySTK(pstk))
        return error;
    (pstk->top)--; /* 退栈 */
    *pdata =pstk->stkdata[pstk->top];
    return ok;
}
void synerror()
{
    printf("\n 表达式语法错！");
    exit(-1);
}
int eval(char tag,int a1,int a2)
{
    switch(tag)
    {
    case add:return(a1+a2);
    case subs:return(a1-a2);
    case mult:return(a1*a2);
    case div:return(a1/a2);
    }
}

int main()
{
    char c;
    int opd1,opd2,temp,c1;
    expSTK=initSTK(&expSTKzone);
    printf("\n 后置表达式: ");
    while((c=getchar())!='\n')
    {
        if(c== ' ')
            continue;
        if((c>47)&&(c<58))
            /* 判断是否是 0～9 的字符 */
        {
            putchar(c);
            c1=c-48;
            /* 把输入的字符型数字转换成数字 */
            if(push(&c1,expSTK)==error) /* 运算分量进栈 */
            {
                printf("\n 表达式太长\n");
                exit(-1);
            }
        }
        else if((c==add)||(c==subs)||(c==mult)||(c==div))
        {
            putchar(c);
            if(pop(&opd1,expSTK)==error) /* 将运算量 1 出栈 */
                synerror();
            if(pop(&opd2,expSTK)==error) /* 将运算量 2 出栈 */
                synerror();
            temp=eval(c,opd2,opd1); /* 计算得到结果 */
            push(&temp,expSTK); /* 将运算结果进栈 */
        }
        else synerror(); /* 出现非法字符 */
    } /* while */
    if(pop(&opd1,expSTK)==error) synerror();
    if(!(emptySTK(expSTK))) synerror();
    printf("=%-3d\n",opd1);

    return 0;
}

运行结果：

4. 递归程序设计实训例题：求 Fibonacci 数列函数的实现前 n 项的值，n 由键盘输入，每行输出 4 项。

【问题描述】

由题意可知，Fibonacci 数列的第一项、第二项的值都为 1，从第三项起，每一项的值均是其前面两项值之和。

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

long fib(int i)
{
    if(i==1||i==2)
        return(1);
    else
        return(fib(i-1)+fib(i-2));
}

int main()
{
    int i,n;
    long fib();
    printf("Please input fibnacci number:");
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        printf("fib(%d)=%2ld   ",i,fib(i));
        if(i%4==0)
            printf("\n");
    }
    
    return 0;
}

运行结果：