信息系统项目管理师_2024年软考学习应考交流_信息系统项目管理师考试
标题:
数据结构之栈专题
[打印本页]
作者:
退隐网络
时间:
2009-2-19 22:08
标题:
数据结构之栈专题
栈
（
Stack
）是限定仅在表尾进行插入或删除操作的线性表。表尾端称栈顶（
top
），表头端称栈底（
bottom
）。
若有栈
S=
（
s0
，
s1
，…，
sn-1
）则
s0
为栈底结点，
sn-1
为栈顶结点。通常称栈的结点插入为进栈，栈的结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特点。
栈有两种存储结构：
顺序栈和链栈
顺序栈
即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针
top
指示栈顶元素的当前位置。
栈也可以用链表实现，链式存储结构的栈简称链栈。若同时需两个以上的栈，则最好采用这种结构。对于栈上的操作，总结如下，大家可以仔细看一下这些程序，一个大的程序都是由一些对数据结构的小的操作组成的。
顺序存储的栈的基本操作如下：
判断栈满：
int stackfull(seqstack *s)
{
return (s->top= =stacksize-1);
}
进栈：
void
push(seqstack *s,datatype
x)
{
if (stackfull(s))
error(“stack verflow”);
s->data[++s->top]=x;
}
判断栈空：
int stackempty(seqstack *s)
{
return (s->top= = -1);
}
出栈：
datatype pop(seqstack *s)
{
if (stackempty(s))
error(“stack underflow”);
x=s->data[top];
s->top--;
return (x);
}
链接存储栈
：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。若同时需要两个以上的栈，最好采用链表作存储结构。链接存储的栈的操作如下：
进栈：
Void push(linkstack *p,datatype x)
{
stacknode *q q=(stacknode*)malloc(sizeof(stacknode));
q–>data=x;
q–>next=p–>top;
p–>top=q;
}
出栈：
Datatype
pop(linkstack
*p)
{
datatype
x;
stacknode
*q=p–>top;
if(stackempty(p)
error(“stack underflow.”);
x=q–>data;
p–>top=q–>next;
free(q);
return x;
}
多栈处理
栈浮动技术：
n
个栈共享一个数组空间
V[m]
n
设立栈顶指针数组
t [n+1]
和
栈底指针数组
b [n+1]
，
t
和
b
分别指示第
i
个栈的栈顶与栈底，
b[n]
作为控制量，指到数组最高下标各栈初始分配空间
s = m/n
指针初始值
，
t[0] = b[0] = -1
，
b[n] = m-1
，
t
= b
= b[i-1] + s
，
i = 1, 2, …, n-1
。
作者:
cherie
时间:
2011-7-5 05:36
越办越好~~~~~~~~~`
作者:
不变的信仰
时间:
2011-7-6 15:04
精神世界充实。
作者:
清露
时间:
2011-7-6 15:04
呵呵，找个机会...
作者:
ctdsb2011
时间:
2011-7-16 17:36
好帖子，谢楼主
作者:
anything
时间:
2011-7-16 17:36
支持一下吧
作者:
土豆
时间:
2011-7-18 09:28
不错哦，顶起
作者:
titmc
时间:
2011-7-18 09:28
顶你一下，好贴要顶！
作者:
土豆
时间:
2011-7-18 09:28
ding 支持
作者:
anything
时间:
2011-7-21 15:06
先看看怎么样！
作者:
蜗牛
时间:
2011-7-21 15:06
呵呵，找个机会...
作者:
anything
时间:
2011-7-21 15:06
支持一下
作者:
titmc
时间:
2011-7-25 09:34
不错，感谢楼主
作者:
绿茶
时间:
2011-7-25 09:34
呵呵,明白了
作者:
titmc
时间:
2011-7-25 09:34
顶也～
作者:
aizhijia
时间:
2011-7-30 10:14
帮顶
作者:
anything
时间:
2011-7-30 10:14
谢谢哦
作者:
土豆
时间:
2011-8-3 05:37
谢谢楼主啊！
作者:
hasee
时间:
2011-8-3 05:37
天啊.
作者:
大熊
时间:
2011-8-6 20:03
鉴定完毕.!
欢迎光临 信息系统项目管理师_2024年软考学习应考交流_信息系统项目管理师考试 (http://bbs.tuandui.org.cn/)
Powered by Discuz! X3.2