HZNUOJ

【数据结构】栈(Stack)的链表实现

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:263     AC:73     Score:96.13

Description


链表的头插法,如字面意思,每次新插入的节点位置都在头节点的后面。具体操作过程如下:

插入操作:

1.     新建节点NewNode

2.     NewNode->next指向Head->next

3.     Head->next指向NewNode

删除操作:

1.     节点指针TempPtr指向Head->next

2.     Head->next指向Head->next->next

3.     释放TempPtr

 

Tips:链表有两种写法,一种是有头节点的链表,另外一种是没有头节点的链表,两者在插入操作中没有区别,但是在删除操作中,没有头节点的链表需要特判,而有头节点的链表不需要。

 

现在对希望你对于给定的Stack结构体完成以下几类操作:

1.  Status Push(LinkStack *S,SElemType *e)    //将e压入栈中

2.  Status Pop(LinkStack *S,SElemType *e)     //将栈顶元素从栈中取出

3.  Status StackTraverse(LinkStack *S)        //从上到下输出栈内元素

 

详细要求如下:

1.  对于S,将e压入栈中,成为栈顶元素

2.  对于S,将该栈中的栈顶元素取出

3.  对于S,自上向下输出栈内元素,每个元素之间用空格隔开,若栈空则输出空行

 

Tips:主体代码已给出,你只需要提交函数



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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0


typedef int Status;
typedef int SElemType;
typedef struct SNode SNode;
typedef struct SNode* SNptr;

struct SNode
{
	SElemType data;
	SNptr next;
};

typedef struct
{
	SNptr top;
	int count;
}LinkStack;

Status LinkStackInit(LinkStack *s)
{
	s->top = NULL;
	s->top = (SNptr)malloc(sizeof (SNode));
	if (!s->top)return FALSE;
	s->top->next = NULL;
	s->count = 0;
	return OK;
}

Status LinkStackClear(LinkStack *s)
{
	SNptr p = s->top->next,tmp;
	while (p)
	{
		tmp = p;
		p = p->next;
		free(tmp);
	}
	s->count = 0;
	return OK;
}

Status StackIsEmopty(LinkStack *s)
{
	if (s->count)return FALSE;
	else return TRUE;
}

int StackSize(LinkStack *s)
{
	return s->count;
}

Status StackTop(LinkStack *s, SElemType *e)
{
	if (!s->top)return FALSE;
	*e = s->top->data;
	return TRUE;
}
Status StackVisit(SNptr s)
{
	if (!s)return FALSE;
	printf("%d", s->data);
	return OK;
}

Status StackPush(LinkStack *s, SElemType e);
Status StackPop(LinkStack *s);
Status StackTraverse(LinkStack *S);

int main()
{
	int n;
	char ctl[10];
	LinkStack ss;
	LinkStack *ssp = &ss;
	ssp->top = NULL;
	LinkStackInit(ssp);
	scanf("%d", &n);
	while (n--)
	{
		scanf("%s", ctl);
		if (strcmp(ctl, "Push") == 0)
		{
			SElemType e;
			scanf("%d", &e);
			StackPush(ssp,e);
		}
		else if (strcmp(ctl, "Pop") == 0)
		{
			SElemType e;
			if (StackIsEmopty(ssp))printf("ERROR: Stack is empty!\n");
			else
			{
				StackTop(ssp, &e);
				StackPop(ssp);
				printf("%d\n", e);
			}
		}
		else if (strcmp(ctl, "ShowAll") == 0)
		{
			StackTraverse(ssp);
		}
	}
}



Input


Samples

input
8 Push 3 Push 2 Pop Pop Pop Push 6 Push 5 ShowAll
output
2 3 ERROR: Stack is empty! 5 6