首页 / 软件开发 / 数据结构与算法 / 链栈的实现示例

#ifndef STACK_H_INCLUDED#define STACK_H_INCLUDED#include "ds.h" //for Status,OK ...#ifndef ElemType#define ElemType int /* 数据元素类型默认为 int */#define ELEMTYPE_TAG#endif/////////////////////////////////////////////////////////////链栈的存储结构定义 typedef struct LNode {ElemType data;struct LNode *next;} LNode, *LinkList;typedef LinkList LinkStack; //链栈类型 /////////////////////////////////////////////////////////////链栈的基本操作声明//构造一个空栈S Status InitStack（LinkStack &S）;//销毁栈S Status DestroyStack（LinkStack &S）;//将栈S清空 Status ClearStack（LinkStack &S）;//若栈S为空返回TRUE，否则FALSE Status StackEmpty（LinkStack S）;//返回栈S中的元素个数intStackLength（LinkStack S）;//用e返回栈顶元素//前提：栈S存在且不空 Status GetTop（LinkStack S, ElemType &e）;//元素e入栈S Status Push（LinkStack &S, ElemType e）;//S出栈用e返回出栈元素 //前提：栈S存在且不空 Status Pop（LinkStack &S, ElemType &e）;/////////////////////////////////////////////////////////////链栈的基本操作的实现//构造一个空栈S Status InitStack（LinkStack &S）{// TODO （#1#）: 构造一个空栈S，不带头结点S=（LinkStack）malloc（sizeof（LNode））;if（！S） return ERROR;S->next=NULL;return OK;//-------------------------------------}//销毁栈S Status DestroyStack（LinkStack &S）{// TODO （#1#）:销毁栈S，相当于清空栈
// http://www.bianceng.cnLinkStack p;while（S）{ p=S->next; free（S）; S=p;}return OK;//-------------------------------------}//将栈S清空 Status ClearStack（LinkStack &S）{// TODO （#1#）: 将栈S清空，释放所有结点LinkStack p,q;p=S->next;while（p）{ q=p->next; free（p）; p=q;}S->next=NULL;return OK;//-------------------------------------}//若栈S为空返回TRUE，否则FALSE Status StackEmpty（LinkStack S）{// TODO （#1#）: 若栈S为空返回TRUE，否则FALSEif（S==NULL）return 1;elsereturn 0;//-------------------------------------}//返回栈S中的元素个数intStackLength（LinkStack S）{// TODO （#1#）: 返回栈S中的元素个数LinkStack p;int x=0;p=S->next;while（p！=NULL）{ x++; pp=p->next;}return x;//-------------------------------------}//用e返回栈顶元素//前提：栈S存在且不空 Status GetTop（LinkStack S, ElemType &e）{// TODO （#1#）:若栈S不空，则用e返回栈顶元素
if（S==NULL） exit（OVERFLOW）;e=S->data;return OK;//-------------------------------------}//元素e入栈S Status Push（LinkStack &S, ElemType e）{// TODO （#1#）: 插入元素e作为新的栈顶 LinkStack p;p=（LinkStack）malloc（sizeof（LNode））;if（！p）exit（OVERFLOW）;p->data=e;p->next=NULL;p->next=S->next;S->next=p;return OK;//-------------------------------------}//S出栈用e返回出栈元素 //前提：栈S存在且不空 Status Pop（LinkStack &S, ElemType &e）{// TODO （#1#）:若栈S不空，则删除栈顶元素用e返回 if（S==NULL） return ERROR;e=S->data;SS=S->next;return OK;//-------------------------------------}#ifdef ELEMTYPE_TAG#undef ElemType#undef ELEMTYPE_TAG#endif#endif