注册 登录
编程论坛 数据结构与算法

望大神帮我看看这个关于栈的问题

选调生 发布于 2018-02-10 17:21, 1813 次点击
(1)书上说非空栈的栈顶指针始终指向栈顶元素的下一位置,第一张图里也有示图:
只有本站会员才能查看附件,请 登录

(2)但是在链栈里,S为什么又指向栈顶?——这么说吧,我的疑问都在下面的注释里,大佬帮看看。谢啦第二张图:
只有本站会员才能查看附件,请 登录

程序代码:

Status GetTop(LinkStack S,ElemType &e) {
  if(!(S->top->next))   exit(ERROR);      
   S->top=S->top->next;  //这里先让top指向了它的next,相当于top现在该指向第二张图中S的下面(即第二层)   
   e=S->top->data;  //然后再把新的第二层top所指的结点的data给了e,那么这样一来返回的不就是第二层的数据了吗?而不是栈顶元素了。。。   
   return OK;
}

然后是删除
程序代码:

Status   Pop ( LinkStack *S, SElemType *e ) {  
    LinkStackPtr  p;  
    if ( StackEmpty( *S ))    return   ERROR;  
    *e = S->top->data;  //这儿先把top(也就是第二张图里的第一层)所指的数据给了e   
    p = S->top;  
    S->top = S->top->next;   //然后在这里才让top指向它的next(即第二层),所以都是对栈顶操作,为啥一个是取第一层数据,一个是取第二层数据??
    free (p);    S->count - -;  
    return OK;
}


[此贴子已经被作者于2018-2-10 17:28编辑过]

3 回复
#2
Jonny02012018-02-10 19:31
按照你的书上的设定,是不带头节点的链栈
只有本站会员才能查看附件,请 登录

如图所示,就是你书上的链栈的横向表达形式
GetTop 函数中,S->top = S->top->next 是因为 top 按照你书上的设定,是指向一个空的节点,它的下一个节点才是真正的栈顶,top 指向的节点本身是没有数据的
你书上的栈的表达挺麻烦的,base 没有存在的必要,因为在 base 之前的元素出去之前,base 是不能动的


[此贴子已经被作者于2018-2-10 19:37编辑过]

#3
选调生2018-02-10 20:29
回复 2楼 Jonny0201
哦哦,所以说抛开前面那些话,只看我那两个程序,Pop函数所描述的是没有头结点的,而GetTop函数里是有头结点的,是吧
#4
书生牛犊2018-02-13 21:13
回复 3楼 选调生
你的理解是对的。但是有一个词汇用的不准确。

不能说Pop函数所在的那个程序源代码里栈没有头结点,而GetTOP有头结点。应该说GetTop的链表会有一个没数据的头结点,而Pop的链表则是从头结点就开始存储数据。

换句话说,往栈内压入同样多的数据,GetTOP链表所要消耗空间回避Pop链表多一个结点。    而多这一个节点,会让代码好写一些。
1