数据结构与算法问题分析及源代码之栈操作.doc

栈操作1 题目 编写一个程序，实现顺序栈的各种基本算法，包括：栈操作：初始化栈、判断栈s是否非空、输出栈长度、释放栈栈元素操作：压栈、出栈2 目标 熟悉栈的定义及其基本操作的实现3 设计思想考虑到顺序栈受空间的限制较大，因此选择建立链栈，在结点定义的结构体中包含两个元素，数据和指向下一个结点的next指针。栈的特点是先入后出，进栈出栈都在一端进行，因此只需对栈顶结点进行操作就能实现压栈出栈操作，头结点用来存放长度，对头结点进行操作能实现判空、求长等操作。4 算法描述（1） 初始化栈：申请结点空间，初始化数据为0，next指针为null。（2） 判断s是否为空:头结点next指针为NULL，返回1，否则返回0。（3） 输出栈长度：返回头结点数据值。（4） 释放栈：从头结点开始，沿next指针向后逐个释放结点，直到next指向空。（5） 压栈：新申请结点，存入数据值，next赋值为NULL，修改当前栈顶结点的next指针指向新加结点，栈底结点计数器加一。（6） 出栈：保存待删除结点数据值，修改其前一个结点的next指针为null，释放删除结点，栈底的计数器减一。5 程序结构图主程序main初始化栈s InitStack(SqStack *&s)释放栈s ClearStack (SqStack *&s)判断栈s是否为空StackEmpty(SqStack *s)求栈s的长度StackLength(SqStack *s)出栈一个元素Pop(SqStack *&s ,ElemType &e)取栈顶元素GetTop(SqStack *s ,ElemType &e)进栈一个元素Push(SqStack *&s ,ElemType &e)从栈顶到栈底输出元素底DispStack(SqStack *s)6 源程序#include #include #define ERROR 0typedef struct LNodeint data;struct LNode *next;LNode,*LinkStack;LinkStack InitStack(LinkStack S)S=(LinkStack)malloc(sizeof(LNode);S-data = 0;S-next = NULL;return S;void ClearStack(LinkStack S)LinkStack f = S;while(S)S = S-next;free(f);f = S;int StackEmpty(LinkStack S)if( S-next = NULL )return 1;elsereturn 0;int StackLength(LinkStack S)return S-data;void Push(LinkStack S)int e;LinkStack p=(LinkStack)malloc(sizeof(LNode);printf(n请输入要压入栈的元素的值: );scanf(%d,&e);p-data = e;p-next = S-next;S-next = p;S-data+;printf(元素 %d 已压入栈!,e);int Pop(LinkStack S)if(StackEmpty(S)printf(栈为空);return 0;int e;LinkStack f = S-next;e = f-data;if(!StackEmpty(S)S-next = S-next-next;free(f);S-data-;printf(n出栈元素的值为: %d ,e);elseprintf(n栈为空n);void DispStack(LinkStack S)LinkStack p = S-next;if(!StackEmpty(S)while(p)printf( %d n,p-data);p = p-next;elseprintf(n栈为空);int GetTop(LinkStack S) if(S