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

Tags:

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:主体代码已给出，你只需要提交函数

Toggle Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#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