前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Tarjan中栈的分析与SLT栈的实现

Tarjan中栈的分析与SLT栈的实现

作者头像
attack
发布2018-04-12 13:59:52
6320
发布2018-04-12 13:59:52
举报

首先看一下手写的栈:

代码语言:javascript
复制
1 do{
2     printf("%d ",stack[index]);
3     visit[stack[index]]=0;
4     index--;
5     }while(x!=stack[index+1]);//出栈,并且输出。
6 printf("\n");

我们可以发现。x是与index的上一个元素比较的

举个例子

栈:1 3 2 4 5     x=2

这样的话会输出 5  4   2

但是stl不支持和栈顶的上一个元素比较,因为上一个元素一定是被pop掉的。

那么我们可以怎么实现呢?

1.首先我们需要明白一点,如果我们把循环的条件改为

代码语言:javascript
复制
 1 x!=stack.top; 

那么当栈已经空的时候,还是会执行一下判断操作,这样就会导致re,

所以我们可以记录下pop之前的元素,这样就可以保证在判断的时候不会越界,而且是与pop之前的元素进行比较的

code:

代码语言:javascript
复制
1 int h;
2 do
3 {
4     h=s.top();
5     if(!color[s.top()])
6     color[s.top()]=colornum;
7     vis[s.top()]=0;
8     s.pop();
9 }while(now!=h);

2.一般的do while语句都可以用while语句来实现

我们如果单纯的把do while改成while,

那么在上面的例子中会输出 5  4

所以我们还需要判断一次,把当前的栈顶给输出

代码:

代码语言:javascript
复制
 1 while(now!=s.top())
 2 {
 3     if(!color[s.top()])
 4     color[s.top()]=colornum;
 5     vis[s.top()]=0;
 6     s.pop();
 7 }
 8 if(!color[s.top()])
 9 color[s.top()]=colornum;
10 vis[s.top()]=0;
11 s.pop();

如果你还有其他什么写法的话欢迎发表评论或者通过其他方式联系我。

谢谢

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-07-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档