数据结构之栈链表

向右看齐 2022-05-10 10:44 188阅读 0赞

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

\#define OVERFLOW        -1  
\#define STACK\_INIT\_SIZE 10  
\#define STACKINCREMENT   2  
\#define OK               1  
\#define ERROR            0  
\#define TRUE             1  
\#define FALSE            0

typedef int SElemType;  
typedef int Status;

typedef struct StackNode  
\{  
    SElemType data;  
    struct StackNode \*next;  
\}StackNode, \*LinkStackPtr;

typedef struct LinkStack  
\{  
    LinkStackPtr top;  
    int count;  
\}\*PLinkStack;

/\*初始化栈\*/  
Status InitStack(PLinkStack \*S)  
\{  
    \*S = (PLinkStack)malloc(sizeof(struct LinkStack));  
    (\*S)->top = NULL;  
    (\*S)->count = 0;  
    return OK;  
\}

/\*清空栈\*/  
Status ClearStack(PLinkStack S)  
\{  
    LinkStackPtr p;  
    while(S->top)\{  
        p = S->top;  
        S->top = S->top->next;  
        S->count--;  
        free(p);  
    \}  
    return OK;  
\}

/\*销毁栈\*/  
Status DestroyStack(PLinkStack \*S)  
\{  
    ClearStack(\*S);  
    free(\*S);  
    return OK;  
\}

/\*判断栈是否为空\*/  
Status StackEmpty(PLinkStack S)  
\{  
    if(S->top)/\*栈存在且非空\*/  
        return FALSE;  
    else  
        return TRUE;  
\}

/\* 若栈存在且非空，用e返回S的栈顶元素 \*/  
Status GetTop(PLinkStack S,SElemType \*e)  
\{  
    if(!S->top)return ERROR;  
    \*e = S->top->data;  
    return OK;  
\}

/\*入栈\*/  
Status Push(PLinkStack S,SElemType \*e)  
\{  
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(struct StackNode));  
    p->data = \*e;  
    p->next = S->top;  
    S->top = p;  
    S->count++;  
    return OK;  
\}

/\*出栈\*/  
Status Pop(PLinkStack S,SElemType \*e)  
\{  
    LinkStackPtr p;  
    if(!GetTop(S,e))return ERROR;  
    p = S->top;  
    S->top = S->top->next;  
    S->count--;  
    free(p);  
    return OK;  
\}

/\*遍历栈中所有元素\*/  
Status StackTraverse(PLinkStack S,Status (\* visit)(SElemType))  
\{  
    LinkStackPtr p;  
    p = S->top;  
    while(p)\{  
        visit(p->data);  
        p = p->next;  
    \}  
    printf("\\n");  
    return OK;  
\}

/\*显示元素格式\*/  
Status visit(SElemType e)  
\{  
    printf("%d ",e);  
    return OK;  
\}

int main()  
\{  
      
  SElemType e,m;  
  PLinkStack s;   
  printf("构造一个空栈……\\n");     
  InitStack(&s);   
  int n;   
  puts("请输入要进栈的个数：");   
  scanf("%d", &n);  
  printf("请输入进栈元素：");   
  for(e = 1; e <= n ; e++)  
  \{  
           scanf("%d", &m);   
         Push(s,&e);  
  \}  
  printf("现在栈中的元素是:\\n");  
  StackTraverse(s, visit);   
  printf("\\n");  
  printf("……本栈是空栈吗？？……\\n");  
  if (StackEmpty(s) )  
         printf("YES !!!\\n");  
  else  
         printf("NO !!!\\n");  
  printf("……输出栈顶元素……\\n");  
  GetTop(s,&e);  
  printf("栈顶元素是:\\n");  
  printf("%d\\n",e);  
  printf("……栈顶插入元素……\\n");  
  printf("请输入要插入的元素的数值:\\n");  
  scanf("%d",&e);  
  Push(s,&e);  
  printf("现在栈中的元素是:\\n");  
  StackTraverse(s, visit);   
  printf("\\n");  
  printf("……栈顶删除元素……\\n");  
  printf("删除的元素是:\\n");  
  scanf("%d",&e);  
  Pop(s,&e);  
  printf("现在栈中的元素是:\\n");  
  StackTraverse(s, visit);   
  printf("\\n");    
  printf("……销毁栈……\\n");  
    if(DestroyStack(&s))  
         printf("销毁栈成功\\n");  
    else  
         printf("销毁栈失败\\n");  
  printf("……清空栈……\\n");  
  if((ClearStack(s)))  
         printf("清空栈成功\\n");  
    else  
         printf("清空栈失败\\n");  
  printf("您已经成功完成所有的功能!!!\\n");   
    return 0;  
\}