文档章节

小蚂蚁学习数据结构(28)——题目——顺序栈的遍历输出

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/01 19:17
字数 1098
阅读 323
收藏 4
点赞 1
评论 0

已知栈的顺序存储结构定义如下:

typedef int SElemType;

typedef struct{

    SElemType * base;

    SElemType * top;

    int stacksize;

}SqStact;

下面是依次弹出栈中的所有元素、并逐个输出的类C_算法,操作的结果使栈变成空栈,请填空

void Pop_Print_Sq(SqStack &S);

/*
	顺序栈的操作
	题目要求:依次弹出栈中元素、并逐个输出的类C算法。
*/
# include <stdio.h>
# include <malloc.h>

# define ERROR 0
# define OK	   1
# define STACK_INIT_SIZE 5
# define STACKINCREMENT  1

typedef char Elemtype;
typedef int  Status;

typedef struct stack
{
	Elemtype * base;	//栈底指针
	Elemtype * top;		//栈顶指针
	int stacksize;		//栈总空间
}SqStack;

//栈操作函数前置声明
//初始化一个栈
Status InitStack( SqStack & );
//销毁这个栈
Status DestroyStack( SqStack & );
//清空这个栈
Status ClearStack( SqStack & );
//判断这个栈是否为空
bool StackEmtpy( SqStack & );
//返回这个栈的长度
Status StackLength( SqStack & );
//得到栈顶元素
Status GetTop( SqStack &, Elemtype & );
//往栈中压入一个元素
Status Push( SqStack &, Elemtype );
//弹出一个元素,并且返回弹出元素的值
Status Pop( SqStack &, Elemtype & );
//遍历整个栈
Status StackTraverse( SqStack & );
//题目要求的函数
void Pop_Print_Sq( SqStack & );

//初始化这个栈
Status InitStack( SqStack & S )
{
	/*
		为栈指针分配空间
		PS:malloc分配空间这里,超出后也正常的原因需要重点标注一下。
	*/
	S.base = ( Elemtype * )malloc( sizeof( Elemtype ) * STACK_INIT_SIZE );
	if( NULL == S.base )
	{
		printf( "动态空间分配失败\n" );
		return ERROR;
	}
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	
	return OK;
}

//向栈中压入一个元素
Status Push( SqStack & S, Elemtype val)
{
	
	if( S.top - S.base >= S.stacksize )
	{
		//如果存储空间已满,就需要增加新的空间
		S.base = ( Elemtype * )realloc( S.base, ( S.stacksize + STACKINCREMENT ) * sizeof( Elemtype ) );
		if( NULL == S.base )
		{
			printf( "动态空间分配失败\n" );
			return ERROR;
		}
		/*
			重新设定栈顶指针top,因为之前top指向的是一个不属于自己的空间,
			现在新开辟了一个属于自己的空间,所以重新指定一下
			万一地址换了也是有可能的!
		*/
		S.top = S.base + S.stacksize;
		//修改结构体中,空间的总大小
		S.stacksize = S.stacksize + STACKINCREMENT;
	}
	
	*S.top = val;
	S.top++;
	return OK;
}

//遍历整个栈
Status StackTraverse( SqStack & S )
{
	if( S.top == S.base )
	{
		return ERROR;
	}
	else
	{
		Elemtype * p = S.base;
		while( p != S.top )
		{
			printf( "%c ", *p );
			p++;
		}
		printf( "\n" );
		
		return OK;
	}
}

//判断这个栈是否为空
bool StackEmtpy( SqStack & S )
{
	if( S.top == S.base )
	{
		return true;
	}
	else
	{
		return false;
	}
}

//返回这个栈的长度
int StackLength( SqStack & S )
{
	return S.top - S.base;
}

//返回栈顶元素
Status GetTop( SqStack & S, Elemtype & c )
{
	if( S.top == S.base )
	{
		return ERROR;
	}
	else
	{
		c = *(S.top-1);
	}
}

//弹出一个元素,并且返回弹出元素的值
Status Pop( SqStack & S, Elemtype & c )
{
	if( S.top == S.base )
	{
		return ERROR;
	}
	else
	{
		c = *(S.top-1);
		S.top--;
		S.stacksize--;
	}
}

//清空这个栈
Status ClearStack( SqStack & S )
{
	S.top = S.base;
	return OK;
}

//销毁这个栈
Status DestroyStack( SqStack & S )
{
	//释放栈空间
	free( S.base );
	//初始化栈结构体
	S.top  = NULL;
	S.base = NULL;
	S.stacksize = 0;
	
	return OK;
}

/*
	题目要求的函数
	题目貌似没有说是从上往下遍历,还是从下往上遍历
*/
void Pop_Print_Sq( SqStack & S )
{
	while( S.top != S.base )
	{
		S.top--;
		printf( "%c ", *S.top );
	}
}

int main( void )
{
	char c;
	//创建一个栈
	SqStack STA;
	//初始化这个栈
	InitStack( STA );
	//为栈中压入一个元素
	Push( STA, 'a' );
	Push( STA, 'b' );
	Push( STA, 'c' );
	Push( STA, 'd' );
	Push( STA, 'e' );
	Push( STA, 'f' );
	Push( STA, 'g' );
	Push( STA, 'h' );
	Push( STA, 'i' );
	Push( STA, 'j' );
	Push( STA, 'k' );
	//遍历这个栈
	printf( "压入元素从a~k,遍历这个栈:\n" );
	StackTraverse( STA );
	
	printf( "判断这个栈是否为空?" );
	if( StackEmtpy( STA ) )
	{
		printf( "这个栈为空\n" );
	}
	else
	{
		printf( "这个栈不为空\n" );
	}
	
	printf( "该链表的长度为:%d\n", StackLength( STA ) );
	
	GetTop( STA, c );
	printf( "目前栈顶元素为:%c\n", c );
	
	Pop( STA, c );
	printf( "弹出的栈顶元素为:%c\n此刻的栈中元素是:", c );
	StackTraverse( STA );
	
	//题目要求的函数
	printf( "依次弹出栈中元素、并将栈清空:\n" );
	Pop_Print_Sq( STA );
	StackTraverse( STA );
	printf( "\n" );
	//清空这个栈
	ClearStack( STA );
	StackTraverse( STA );
	
	//销毁这个栈
	DestroyStack( STA );
	
	return 0;
}
/*
	VC++6.0输出的结果是
	========================================
	压入元素从a~k,遍历这个栈:
	a b c d e f g h i j k
	判断这个栈是否为空?这个栈不为空
	该链表的长度为:11
	目前栈顶元素为:k
	弹出的栈顶元素为:k
	此刻的栈中元素是:a b c d e f g h i j
	依次弹出栈中元素、并将栈清空:
	j i h g f e d c b a
	========================================
	总结:
		整体上没有什么难度,之前写过链表的栈,趁着这个机会把顺序栈也
		练习一下。在malloc那里有点迷糊了,由于字数比较多,就在下面单独
		总结吧。
*/


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 137
博文 161
码字总数 100864
作品 0
郑州
程序员
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
07/11
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
若干数据结构 && 算法面试题【四】(更新ing)

这是我的第三个面试题汇总。 想看之前的内容请移步 http://zhweizhi.blog.51cto.com/10800691/1763237 若干数据结构 && 算法面试题【一】更新完毕 http://zhweizhi.blog.51cto.com/10800691/...

shangluyi
2016/07/08
0
0
编程题——21~30

二十一、包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调 用min、push及pop的时间复杂度都是O(1)。 二十二、栈的压入、弹出序列 输入两...

thanatos_y
2016/07/22
1
0
小蚂蚁学习数据结构(30)——图的其他知识点简介

图的遍历 图的遍历,是对图中的每个顶点都进行一次访问且仅进行一次访问。 图的深度遍历: 类似于树的先根遍历。 图的广度遍历: 优先遍历第一顶点的所有邻接点,类似树的层次遍历。 连通网的...

嗜学如命的小蚂蚁
2016/02/05
77
0
编程题——1~10

一、CMyString类的实现(主要是构造函数、拷贝构造函数、赋值运算符、异常安全性) 二、Singleton的实现 1、ns3里的实现 实现程序如下: 2、《C++设计新思维》第6章 多线程实现程序如下: 三...

thanatos_y
2016/07/19
3
0
剑指Offer学习总结-从尾到头打印链表

剑指Offer学习总结-从尾到头打印链表 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
01/16
0
0
大家都懂的 JSON 解析器原理(一)简介 & 低配版入门

没学过编译原理,做一个 JSON 解析器难吗?——难!是不是就不能“迎难而上”呢?——不是!越是难的越是一个挑战!——笔者这里尝试通过通俗易懂的行文为大家介绍一下 JSON 解析器,——那一...

zhangxin09
2017/08/13
0
0
ACM Summer Training Warm up

ACM Summer Training Warm up Cover 热身水题 题目 HDU 4500 小Q系列故事——屌丝的逆袭 思路 简单的模拟,一个数组读入数据,一个数组计算维护结果 HDU 2109 Fighting for HDU 思路 简单排序...

SpiffyEight77
2017/08/14
0
0
这是自考本科的数据结构试题,自考中山大学的计算机及应用,自考的试————题和本b或者本a哪个难度更高

全国2012年1月高等教育自学考试 数据结构试dd题 课程代码:02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写...

给我一分钟灵感
2015/11/21
339
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

TextView设置行间距、字体间距

一、设置行间距 1、设置行间距:android:lineSpacingExtra,取值范围:正数、负数和0,正数表示增加相应的大小,负数表示减少相应的大小,0表示无变化 2、设置行间距的倍数:android:lineSpa...

王先森oO
9分钟前
0
0
适配器模式

适配器模式(Adapter):将一个类的接口转换成客户端希望的另外一个接口,适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 适配器用于连接两种不同种类的对象,使其毫...

阿元
9分钟前
0
0
CoreText进阶(四)-文字行数限制和显示更多

CoreText进阶(四)-文字行数限制和显示更多 用例和效果 Demo:CoreTextDemo 效果图: 默认的截断标识和自定义的截断标识符效果图  点击查看更多之后的效果图  为了可以设置显示的行数以...

aron1992
12分钟前
0
0
nginx的五种负载算法

nginx的五种负载算法 2017年04月26日 15:01:11 阅读数:1297 1.round robin(默认) 轮询方式,依次将请求分配到各个后台服务器中,默认的负载均衡方式。 适用于后台机器性能一致的情况。 挂...

linjin200
14分钟前
0
0
Android RecyclerView快速上手

RecyclerView mainMenu = findViewById(R.id.fragmentMain); mainMenu.setLayoutManager(new GridLayoutManager(getActivity(),4)); mainMenu.setAdapter(new MainAdapter......

燕归南
16分钟前
0
0
RabbitMQ实战:理解消息通信 

应用RabbitMQ的5种队列 一、简单队列 P:消息的生产者 C:消息的消费者 红色:队列 简单队列的生产者和消费者关系一对一 但有时我们的需求,需要一个生产者,对应多个消费者,那就可以采用第...

spinachgit
17分钟前
0
0
Linux的使用技巧:到底要不要会用?[图]

Linux的使用技巧:到底要不要会用?[图] 最近有个项目接近了尾声,要进入到调试测试阶段。这是一个使用Springboot框架为后台程序,mpvue构建的小程序项目。服务器我最终仍旧选择了Linux操作系...

原创小博客
18分钟前
0
0
记elasticdump 备份数据导出导入

版本: elasticsearch 5.5.2 elasticdump 2.2 系统 CentOS7.3 因项目需求 从生产导出一份索引到测试 帮助文档 https://github.com/taskrabbit/elasticsearch-dump?utm_source=dbweekly&utm_m......

雁南飞丶
19分钟前
0
0
saltstack配置目录管理

1.服务端配置 -接着编辑之前的 top.sls 文件 #vim /srv/salt/top.sls //修改为如下 base: 'slaver.test.com': - filedir -新建 filedir.sls 文件 # vim /srv/salt/filedir.sls file-dir: fi......

硅谷课堂
19分钟前
0
0
python日期时间

日期和时间 Python内建的datetime模块提供了datetime、date和time类型。datetime类型结合了date和time,是最常使用的: In [102]: from datetime import datetime, date, timeIn [103]:...

火力全開
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部