openjudge数据结构练习集 字符栈的实现

字符栈的实现

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms

内存限制: 

1024kB

描述

本程序定义了一个有头结点的链栈，栈的数据元素类型是字符型。并实现了它的创建，入栈，出栈，获取栈顶元素，判断栈是否为空，销毁栈等操作。为了测试这些操作，在主函数中读入一些字符，当读入回车符时结束读入。利用栈反向输出这些字符。 学习要求：
1、理解所有代码行的含义和作用，能像我上课在黑板上画的图一样，自己在纸上画出程序的执行过程。

2、能在不看我的代码的情况下，写出createStack，push, pop,top,empty,destroy函数的定义。

/*本程序定义了一个有头结点的链栈，栈的数据元素类型是字符型。
并实现了它的创建，入栈，出栈，获取栈顶元素，判断栈是否为空，销毁栈等操作。
为了测试这些操作，在主函数中读入一些字符，当读入回车符时结束读入。利用栈反向输出这些字符。
 学习要求：
 1、理解所有代码行的含义和作用，能像我上课在黑板上画的图一样，自己在纸上画出程序的执行过程。
 2、能在不看我的代码的情况下，写出createStack，push, pop,top,empty,destroy函数的定义。
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//数据结点类型
typedef struct node
{
    char data;//结点中存储的数据
    struct node *link;//指向下一个结点的指针
}node;

//栈的头结点类型
typedef struct Stack
{
    int count; //栈中的元素个数，初始值为0
    node *top; //指向栈顶的指针，当栈空时次指针为NULL
}Stack;

//创建栈，返回指向头结点的指针
Stack* createStack();
//入栈,向指针myStack所指向的栈中压入元素x
//入栈成功返回true，否则返回false
bool push(Stack *myStack, char x);
//出栈,把myStack指向的栈的栈顶元素弹栈
//出栈成功返回true，否则返回false
bool pop(Stack *myStack);
//获取指针myStack所指向栈的栈顶元素。
//获取成功返回true，否则返回false。
//当前栈顶的值通过指针p传回给调用者
bool top(Stack *myStack, char *p);
//判断指针myStack指向的栈是否为空。
//栈空返回true，否则返回false。
bool empty(Stack *myStack);
//销毁指针myStack所指向的栈
bool destroy(Stack *myStack);

int main(void)
{
    Stack *head; //定义指向栈结构的指针
    char c;
    head = createStack(); //创建一个空栈
    c = getchar(); //读入第1个字符
    while (c != '\n')
    {//当读入的字符不是换行符时进入循环
        push(head, c); //字符变量C的值入栈
        c = getchar(); //读取下一个c
    }
    while (!empty(head))
    {//当栈不为空时进入循环
        top(head, &c); //获取当前栈顶元素，由变量c得到栈顶元素的值
        printf("%c\n", c); //输出变量c的值到屏幕
        pop(head); //出栈1次
    }
    destroy(head);//销毁栈空间
    return 0;
}

//请写出6个函数的定义
// 在此处补充你的代码

输入

一行字符，以回车符结束。

输出

反向输出每个字符，每个字符占1行。

样例输入

abcd

样例输出

d
c
b
a

Stack * createStack()
{
	Stack *L = (Stack *)malloc(sizeof(Stack));
	L->count = 0;
	L->top = NULL;//栈为空，top为空
	return L;//返回L的地址
}

bool push(Stack * S, char x)	//头插法
{
	node *pnew = (node *)malloc(sizeof(node));
	pnew->data = x; //把输入的值带入结构体内储存
	pnew->link = S->top;	//后继为空
	S->top = pnew;	//新的节点为头
	S->count++;// 元素加一
	return true;
}

bool pop(Stack * S)
{
	node *p = S->top;
	S->top = S->top->link;
	free(p);
	S->count--;
	return true;
}

bool top(Stack * S, char * p)
{
	if(S->top != NULL)
	*p = S->top->data;
	return true;
}

bool empty(Stack * S)
{
	if (S->top != NULL)
		return false;
	else
		return true;
}

bool destroy(Stack * S)
{
	free(S);
	return false;
}