数据结构：栈基本操作

/************************************************************************/

/* 数据结构：栈基本操作：进栈、出栈、打印栈                   */

/* 挑灯看剑[e-mail] 2010-10                                   */

/* 云歌国际（Cloud Singers International） www.cocoral.com            */

/************************************************************************/

 

#include <stdio.h>

#include <malloc.h>

#include "core.h"

 

//结点数据结构

typedef struct NODE

{

       int data;

       struct NODE* next;

       struct NODE* prior;

}Node, * NodePointer;

 

//栈元数据结构

typedef struct STACK

{

       int len;

       struct NODE* top;

       struct NODE* base;

}Stack, * StackPointer;

 

void main()

{

       //*************函数原型******************

       Status StackIn(StackPointer SP, int e);

       void autoStack(StackPointer SP, int n);

       void StackPrint(Stack S, char tag);

       Status StackOut(StackPointer SP, NodePointer NP);

       //*************函数原型******************

 

 

       Stack S =

       {

              0, NULL, NULL

       };

       Node N =

       {

              0, NULL, NULL

       };

 

       int i = 0;

 

       autoStack(&S, 10);

       StackPrint(S, 'b');

 

       for (i = 0; i <= 11; i++)

       {

              StackOut(&S, &N);

              if (N.next == NULL && N.prior != NULL)

              {

                     printf("删除结点值：%d，前驱结点值：%d\n", N.data, N.prior->data);

              }

              else

              {

                     printf("删除结点值：%d\n", N.data);

              }

              StackPrint(S, 'b');

       }

       //StackPrint(S,'b');

}

//进栈操作，结点作为栈顶元素入栈

Status StackIn(StackPointer SP, int e)

{

       static Status StackIsEmpty(Stack S);//函数原型

       Status status = ERROR;

       NodePointer p = NULL;//遍历指针，非游离指针

       NodePointer NP = (NodePointer) malloc(sizeof(Node));

       NP->data = e;

       //进行预处理

       if (!StackIsEmpty(*SP))

       {

              //将结点追加为栈顶元素

              p = SP->top; //p指向栈顶

              p->next = NP;

 

              NP->prior = p;

              NP->next = NULL;

 

              SP->top = NP;

              SP->len += 1; //长度加1

              //puts("进栈成功！");

              status = OK;

       }

       else

       {

              SP->base = SP->top = NP;

              NP->next = NP->prior = NULL;

              SP->len = 1; //长度为1

              //puts("进栈成功！");

              status = OK;

       }

       return status;

}

 

//自动化栈

void autoStack(StackPointer SP, int n)

{

       COUNT i = 0;

       for (i = 0; i < n; i++)

       {

              if (StackIn(SP, i))

              {

              }

              else

              {

                     break;

              }

       }

}

 

static Status StackIsEmpty(Stack S)

{

       if (S.len == 0 || S.base == NULL || S.top == NULL)

              return TRUE;

       else

              return FALSE;

}

 

//出栈操作，并用结点返回该值

Status StackOut(StackPointer SP, NodePointer NP)

{

       Status status = ERROR;

       NodePointer p = SP->top; //p指向栈顶

       if (!StackIsEmpty(*SP))

       {

              if (SP->len == 1)

              {

                     SP->base = SP->top = NULL;

                     SP->len = 0; //长度为0

 

                     NP->data = p->data;

                     NP->next = p->next;

                     NP->prior = p->prior;

                     //puts("出栈成功！");

                     status = OK;

              }

              else

              {

                     p->prior->next = NULL;

                     SP->top = p->prior;

                     SP->len -= 1; //长度减1

                     NP->data = p->data;

                     NP->next = p->next;

                     NP->prior = p->prior;

                     //puts("出栈成功！");

                     status = OK;

              }

       }

       else

       {

              //puts("出栈失败！栈为空！");

              status = ERROR;

       }

       free(p); //p为游离结点，最后释放p内存

       return status;

}

 

//栈打印操作，tag参数IN SET{'B','T'}

void StackPrint(Stack S, char tag)

{

       static Status StackIsEmpty(Stack S);//函数原型

       NodePointer p = NULL;

       COUNT i = 1;

       COUNT n = S.len;

       printf("栈长度：%d\n", n);

       if (!StackIsEmpty(S)) //如果线性链表非空

       {

              switch (tag)

              {

              case 'B':

                     p = S.base;

                     puts("打印结点信息（栈底到栈顶）：");

                     for (i = 1; i <= n; i++)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->next;

                     }

                     break;

              case 'b':

                     p = S.base;

                     puts("打印结点信息（栈底到栈顶）：");

                     for (i = 1; i <= n; i++)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->next;

                     }

                     break;

              case 'T':

                     p = S.top;

                     puts("打印结点信息（栈顶到栈底）：");

                     for (i = n; i >= 1; i--)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->prior;

                     }

                     break;

              case 't':

                     p = S.top;

                     puts("打印结点信息（栈顶到栈底）：");

                     for (i = n; i >= 1; i--)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->prior;

                     }

                     break;

              default:

                     puts("打印失败！");

                     break;

              }

       }

       else //如果栈为空

       {

              puts("打印失败！栈为空！");

       }

 

       free(p);//p为游离结点，最后释放p内存

}