① 请问“多个栈共存时,最好用链式存储空间作为存储结构”,这是为什么啊
如果只有两个栈,则可以将一个放在数组的低空间,一个放在高空间,两者从两头向中间扩展,这样没有空间浪费
如果多于两个栈时,还是采用顺序存储,则一个满了另外栈空间虽然有空,但是必须要移动栈中元素才能使用别的浪费的空间,这样算法的效率就不高了,此时不如直接采用链接存储好了
② 数据结构问题
尼玛这个优点总结的也太不明显了,有点牵强附会。不过既然人家总结了,并且还有你问了,那我就姑且给你分析下说这话人的意图。
什么叫多个栈共享存储空间?咋一理解还以为是他妈是基于同一块存储空间定义多个栈,然后各栈来回切换使用,尼玛这样搞的话,即使可行,也乱套了!是个人都不会这样干!那是什么意思呢?
原来人家说的是栈的存储是单链表结构,动态分配内存的,所以在没有存储需求的情况下,绝对不会开辟新的空间,并且在栈回退的情况下,还可以动态释放空间。这就为其他数据存储提供了更多存储空间机会。
不过话说回来,就这样子能说多个栈共享存储空间吗?简直尼玛胡扯!
---------------------------------------------------
刚才骂的有点不冷静,为了不误人子弟,回过头来,再补充一下。
系统在执行程序时,一般都会有一个栈,在进入函数时,将所有参数值压栈,当函数执行完毕后,再将参数弹出栈,保持栈的原来状态。试想一下,当系统从一个函数的内部再进入另一个函数时,栈操作将进行相同的过程,只有栈足够大,可以无限递归下去。栈可以在任意层函数的执行过程中保持正确的状态。告诉你这个栈的使用场景是让你更好对链栈进行认识。
③ 栈的共享存储单元是什么
有时,一个程序设计中,需要使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补。
1.双栈为两个栈共同开辟一个存储空间,让一个栈的栈底为该空间的始端,另一栈的栈底为该空间的末端,当元素进栈时,都从两端向中间“增长”,这样能够使剩余的空间为任意一个栈所使用,即当一个栈的深度不足整个空间的一半时,另一个栈的深度可超过其一半,从而提高了存储空间的利用率。可以使用一个数组同时存两个栈,让一个栈的栈底为数组的始端,另一个栈的栈底为数组的末端,每个栈从各自的端点向中间延伸,双栈示意如图1所示。其中,MAXSTACKSIZE为整个数组空间的长度,栈1的底端固定在下标为0的一端,栈2的底端固定在下标为MAXSTACKSIZE-1的一端。top1和top2分别为栈1和栈2的栈顶指针,并约定栈顶指针指向当前元素,即栈1空的条件是top1=-1,栈1满的条件是top1==top2-1,栈2空的条件是top2=MAXSTACKSIZE,栈2满的条件是top2==top1+1。
图1两相栈共享存储单元示意
④ 链栈中为什么需要头结点
链栈中需要头结点原因:因为栈是后进先出的数据结构,我们不可能直接就对栈底元素进行操作,要想操作栈底元素,必须得先依次让非栈底元素出栈。
即使设了头指针,也没有用处,对栈顶元素的操作,与头指针没关系。所以不必设头指针指向栈底元素。
1、头结点不存储数据,此时它只是个标记。链表从这里开始,意义在于头结点中的next。引出后面的链表数据。这就是平常写的头结点。
2、头结点存储数据,它此时就不只是个标记和引出后面的链表数据,还有它里面的data。意义在于data 和 next。
两个栈共享同一存储空间:
当程序中同时使用两个栈时,可以将两个栈的栈底设在向量空间的两端,让两个栈各自向中间延伸。当一个栈里的元素较多,超过向量空间的一半时,只要另一个栈的元素不多,那么前者就可以占用后者的部分存储空间。
只有当整个向量空间被两个栈占满(即两个栈顶相遇)时,才会发生上溢。因此,两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为└m/2┘和┌m/2┐的向量空间比较,前者发生上溢的概率比后者要小得多。
⑤ 简述栈和队列的顺序存储结构和链式存储结构的优缺点
顺序栈--入栈操作受数组上界的约束有可能发生栈上溢,且需要地址连续的存储单元。
链栈--无须地址连续,便于多个栈共享存储单元,且不存在栈满上溢情况。
顺序队列--需地址连续且有假上溢现象(需改为循环队列才可解决假上溢)
链式队列--特别适合于数据元素变动比较大的情况,且不存在队列满而产生的溢出问题。
⑥ 两个栈共享一段内存区域是什么意思
当程序中同时使用两个栈时,可以将两个栈的栈底设在向量空间的两端,让两个栈各自向中间延伸。如下图所示:
当一个栈的元素较多,超过向量空间的一半时,只要另一个栈的元素不多,那么前者就可以占用后者的部分存储空间。
只有当整个向量空间被两个栈占满(即两个栈顶相遇)时,才会发生上溢,因此两个栈共享一个长度为m的向量空间
⑦ 当栈的元素个数变化较大用那种栈
摘要 链栈
⑧ 两栈共享一个存储空间,判定栈满的条件是什么
肯定是top[1]+1=top[2]啊,你想要是top[1]=top[2]那么,两个栈顶在同一个位置,等于一个位置存了两个元素,说明你前一步插入的元素没有空间了,就是1和2相邻的时候已经满了。
⑨ 单共享栈
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性数据结构。应用广,作用大。
一、1、 栈的定义:限定仅在表尾进行插入或删除操作的线性表,因此,对栈来说,表尾端有其特殊含义,表尾—栈顶(top) ,表头—栈底(bottom) ,不含元素的空表称空栈。
例4:计算机系2001年考研题(程序设计基础)
设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是:
A)a,b,c,d B)c,d,a,b
C)b,c,d,a D)a,c,d,b
A、D可以( B、C不行)。
答:
例5、习题集P22 3.4
status algo1(stack s)
{int i,n,a[255];
n=0;
While(!stackempty(s))
{n++;
pop (s,a[n]);}
For(i=1;i<=n;i++) push (s,a[i]);
}
5、补充公式:
若输入的序列为1、2、3 ….n,则可能出现的输出序列符合卡塔南数列:
验证:
二、 栈的表示和实现:
顺序存贮结构__顺序栈;
链式存贮结构__链栈;
(一) 顺序栈
利用一组地址连续的存贮单元依次自栈底到栈顶存放栈的数据元素.
栈底元素是最先进入的,实际上是线性表的第一个元素
数组(静态数组):空间固定
动态数组:动态申请空间(用指针表示)
表示容量;
表示数据元素个数;
// 顺序栈的C表示
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置;base表示栈底指针;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ SElemType *Base; // 栈底指针
SElemType *Top; // 栈顶指针
int StackSize;//当前已分配的存储空间,以元素为 单位。
}SqStack
空栈
A
A进栈
top
base
top
base
s.top=0 或s.top=s.base 表示空栈;
s.base=NULL表示栈不存在;
当插入新的栈顶元素时,指针s.top++;
删除栈顶元素时,指针s.top--;
当s.top-s.base>=stacksize时,栈满,溢出
顺序栈初始化
SqStack s;
s.Base = NULL;
s.Top = NULL;
s.StackSize = 0;
base
stacksize
top
&s
s.base = s.top =
( SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType ));
顺序栈的C图示
base
top
空栈:
base = top;
A
base
top
*top = A;
top ++;
E
C
B
A
D
base
top
B
A
base
top
出栈:
if( top != base )
{
top --;
e = *top;
}
入栈:
if( 没有空间 )
{
//realloc,调整top
}
顺序栈基本算法_InitStack
// 初始化顺序栈, 构造一个空栈
Status InitStack( SqStack &S )
{
s.base = (SElemType *)malloc(
STACK_INIT_SIZE * sizeof( SElemType));
if( !s.base )
{
return OVERFLOW;
}
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
顺序栈基本算法:GetTop
// 用e返回栈S的栈顶元素,若栈空,函数返回ERROR
Status GetTop( SqStack S, SElemType &e)
{
if( s.top != s.base ) // 栈空吗?
{
e = *( s.top – 1 );
return OK;
}
else
{
return ERROR;
}
}// GetTop
顺序栈基本算法:Push
//把元素e入栈
Status Push(SqStack &S, SElemType e )
{
// 若栈,追加存贮空间
if( s.top == s.base + s.stacksize )
{
p = (SElemType *)realloc( s.base,
(s.stacksize + STACKINCREMENT)*sizeof(SElemType));
if( !p )
{
return OVERFLOW;
}
s.base = p;
顺序栈基本算法:Push
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top = e;
s.top++;
return OK;
}// Push
顺序栈基本算法:Pop
// 出栈
Status Pop( SqStack &S, SElemType &e )
{
if( s.top == s.base ) // 空吗?
{
return ERROR;
}
s.top --;
e = *s.top;
return OK;
}// Pop
顺序栈基本算法:其他
// 取顺序栈长度
int StackLength( SqStack S )
{
return s.top – s.base;
}// StackLength
#define StackLength( S ) ((S).top – (S).base)
// 顺序栈空吗?
Status StackEmpty( SqStack S )
{
return s.top == s.base ? TRUE:FALSE;
}
#define StackEmpty( S ) (((S).top == (S).base )?TRUE:FALSE)
顺序栈基本算法:ClearStack
// 清空栈
Status ClearStack( SqStack S )
{
if( s.base )
{
s.top = s.base;
}
return OK;
}// ClearStack
顺序栈基本算法:DestroyStack
// 销毁栈
Status DestroyStack( SqStack &S )
{
if( s.base )
{
free( s.base );
s.stacksize = 0;
s.base = s.top = NULL;
}
}// DestroyStack
3.1.3 链栈
栈的链式存储结构称为链栈,它的运算是受限的单链表,插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作,故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
链栈的类型说明如下:
栈的链接存储结构
链栈的结点定义
typedef struct node
{ ElemType data;
struct node *next;
} LinkStack;
栈的链接表示 — 链式栈
链式栈无栈满问题,空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
链栈的进栈算法
LinkStack *PUSH (LinkStack *top, ElemType x)
{ LinkStack *p;
p=malloc(sizeof(LinkStack));
p->data=x; p->next=top;top=p;
return top;
}
链栈的出栈算法
linkstack *POP (linkstack *top, ElemType *datap)
{ linkstack *p;
if (top==NULL)
{printf(“under flow\n”); return NULL;}
else
{ *datap=top->data;
p=top;
top=top->next;
free(p);
return top;
}
}
栈的共享存储单元
有时,一个程序设计中,需要使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补。
栈的应用---基本应用
void read_write()
{ stack S;
int n,x;
cout<<”Please input num int n”;
cin>>n; //输入元素个数
init_stack(S); //初始化栈
for (i=1; i<=n; i++)
{ cin>>x; //读入一个数
push_stack(S,x); //入栈
}
while (stack_empty(S)!=TRUE)
{stack_top(S,x); //取出栈顶元素
cout<<x; //输出
pop_stack(S); //退栈
}
}
读入一个有限大小的整数n,并读入n个整数,然后按输入次序的相反次序输出各元素的值。
3.2 栈的应用举例
一、 数制转换
二、 括号匹配的检验
三、 行编辑程序问题
四、 表达式求值
五、 迷宫求解
六、 实现递归
一、数制转换
十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:
N=(n div d)*d+n mod d
( 其中:div为整除运算,mod为求余运算)
例如 (1348)10=(2504)8,
其运算过程如下:
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
0
计算顺序
输出顺序
算法分析:
由十进制转换为其他进制的数的规则,可知,求得的余数的顺序为由低位到高位,而输出则是由高位到低位。
因此,这正好利用栈的特点,先将求得的余数依次入栈,输出时,再将栈中的数据出栈。
void conversion () {
InitStack(S); // 构造空栈
scanf ("%d",&N); //输入一个十进制数
while (N) {
Push(S, N % 8); // "余数"入栈
N = N/8; // 非零"商"继续运算
}
while (!StackEmpty(S)) {
Pop(S,&e);
//和"求余"所得相逆的顺序输出八进制的各位数
printf ( "%d", e );
}
} // conversion
二、 括号匹配的检验
假设在表达式中
(〔〕())或〔(〔 〕〔 〕)〕
等为正确的格式,
(〔]( ) 或(()))或 〔( 〕)均为不正确的格式。
则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
算法的设计思想:
读入表达式
1)凡出现左括号,则进栈;
2)凡出现右括号,首先检查栈是否空
若栈空,则表明该“右括号”多余,
否则和栈顶元素比较,
若相匹配,则“左括号出栈” ,
否则表明不匹配。
3)表达式检验结束时,
若栈空,则表明表达式中匹配正确,
否则表明“左括号”有余。
Status matching(char exp[ ] ) {
while (i<=Length(exp)) {
switch exp[i] {
case '(‘ || '[' :{Push(S,exp[i]); i++; break;}
case ')' : {
if( !StackEmpty(S)&& GetTop(S)= '(' )
{Pop(S,e); i++;}
else return ERROR;
break; }
case ‘]' : {
if( !StackEmpty(S)&& GetTop(S)= ‘[' )
{Pop(S,e); i++;}
else return ERROR;
break; } }
if (StackEmpty(S)) return OK;
}
三、行编辑程序问题
“每接受一个字符即存入存储器” ?
并不恰当!
设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区,并假设“#”为退格符,“@”为退行符。
在用户输入一行的过程中,允许用户输入出差错,并在发现有误时可以及时更正。
合理的作法是:
假设从终端接受了这样两行字符:
whli##ilr#e(s#*s)
outcha@putchar(*s=#++);
则实际有效的是下列两行:
while (*s)
putchar(*s++);
可设这个输入缓冲区为一个栈结构,每当从终端接受了一个字符之后先作如下判断:
1、既不是退格也不是退行符,则将该字符压入栈顶;
2、如果是一个退格符,则从栈顶删去一个字符;
3、如果是一个退行符,则将字符栈清为空栈 。
while (ch != EOF && ch != '\n') {
switch (ch) {
case ‘#’ : Pop(S, c); break;//栈非空,退栈
case '@': ClearStack(S); break;// 重置S为空栈
default : Push(S, ch); break; //未考虑栈满
}
ch = getchar( ); // 从终端接收下一个字符
}
ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar( );
}
DestroyStack(S); }
Void LineEdit( ) {
InitStack(S);
ch=getchar();
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区;
补充习题:
1、设计一个算法,用栈的基本运算,判定一个字符串是否为对称字符串,若是,则返回1,否则返回0。(abccba)
四、表达式求值
1、算术表达式的组成:
将表达式视为由操作数、运算符、界限符(称为单词)组成。
操作数:常数、变量或符号常量。
算符:运算符、界限符
表达式求值是程序设计语言编译的一个最基本的问题。它的实现是栈应用的又一典型例子。 仅以算术表达式为例
2、算术表达式的形式:
中缀(infix)表达式——表达式的运算符在操作数的中间。 <操作数> <操作符> <操作数>
例:A*B 例:5+9*7
后缀(postfix)算术表达式(逆波兰式)——将运算符置两个操作数后面的算术表达式。 <操作数> <操作数> <操作符>
例:AB* 例:5 9 7*+
前缀(prefix)表达式(波兰式)又称波兰式,与后缀表达式相反。把运算符放在两个运算数的前面, <操作符> <操作数> <操作数>
例:*AB 例:+5*9 7
3、介绍中缀算术表达式的求值
例如:3*(7 – 2 )
(1)算术四则运算的规则:
a. 从左算到右
b. 先乘除,后加减
c. 先括号内,后括号外
由此,此表达式的计算顺序为:
3*(7 – 2 )= 3 * 5 = 15
(2)根据上述三条运算规则,在运算的每一步中,对任意相继出现的算符1和2 ,都要比较优先权关系。
一般任意两个相继出现的两个算符p1和p2之间的优先关系至多有下面三种之一:
p1<p2 p2的优先权高于p1
p1=p2 二者优先权相等
p1>p2 p2的优先权低于p1
算符优先法所依据的算符间的优先关系
见教材P53表3.1
θ1<θ2,表明不能进行θ1 的运算,θ2 入栈,读 下一字符。
θ1>θ2,表明可以进行θ1 的运算,θ1退栈,运算,运算结果入栈。
θ1=θ2,脱括号,读下一字符或表达式结束。
(3)算法思想:
设定两栈:操作符栈 OPTR ,操作数栈 OPND
栈初始化:设操作数栈 OPND 为空;操作符栈 OPTR 的栈底元素为表达式起始符 ‘#’;
依次读入字符:是操作数则入OPND栈,是操作符则要判断:
if 操作符 < 栈顶元素,则退栈、计算,结果压入OPND栈;
操作符 = 栈顶元素且不为‘#’,脱括号(弹出左括号);
操作符 > 栈顶元素,压入OPTR栈。
扫描基本符号
是否操作数?
Y
栈顶运算符低
于当前运算符?
操作数
入栈
N
Y
N
运算符
入栈
取出S栈顶运算符和
O栈顶的两个操作数
运算,结果入栈O
定义运算符栈S
和操作数栈O
栈S为空?
Y
结束
Y
一般作为相同运算符,先出现的比后出现的优先级高;
先出现的运算符优先级低于“(”,高于“)”;
后出现的运算符优先级高于“(”,低于“)”;优先权相等的仅有“(”和“)”、“#”。
#:作为表达式结束符,通常在表达式之前加一“#”使之成对,当出现“#”=“#”时,表明表达式求值结束,“#”的优先级最低。
OPTR
OPND
INPUT
OPERATE
3*(7-2)#
Push(opnd,’3’)
#
*(7-2)#
3
#
Push(optr,’*’)
#,*
3
(7-2)#
Push(optr,’(’)
#,*,(
3
7-2)#
Push(opnd,’7’)
#,*,(
3,7
-2)#
Push(optr,’-’)
#,*,(,-
3,7
2)#
Push(opnd,’2’)
#,*,(,-
3,7,2
)#
Operate(7-2)
#,*,(
3,5
)#
Pop(optr)
#,*
3,5
#
Operate(3*5)
#
15
#
GetTop(opnd)
例:3*(7-2)
Status EvaluateExpression( OperandType &result) {
InitStack(OPND); InitStack(OPTR);
Push(OPTR ,’#’);c=getchar();
while((c!=‘#’)&&(GetTop(OPTR)!=‘#’))
{ if (!In(c,OP) { Push(OPND,c); c=getchar();}
else switch(compare(c,GetTop(OPTR)))
{case ‘>’ : Push(OPTR , c); c=getchar();break;
case ‘=’: Pop(OPTR);c=getchar();break;
case ‘<’ : temat=Pop(OPTR); b=Pop();a=Pop();
result= Operate(a,temat,b);Push(OPND,result);
c=getchar();break;
} //switch }//while
result=GetTop(OPND);}//EvaluateExpression
此函数在哪里?
4、计算后缀表达式
(1)为什么要把中缀表示法变为后缀表示法?
计算机计算表达式是机械执行,只能从左至右扫描。计算中缀表达式比较困难。
后缀表达式的求值过程是自左至右运算符出现的次序和真正的计算次序是完全一样的。
顺序扫描表达式的每一项,根据它的类型做如下相应操作:
若该项是操作数,则将其压栈;
若该项是操作符<op>,则连续从栈中退出两个操作数Y和X,形成运算指令X<op>Y,并将计算结果重新压栈。
当表达式的所有项都扫描并处理完后,栈顶存放的就是最后的计
算结果。
人们仍然使用中缀表达式 ,而让机器把它们转换成后缀表达式。
(2)后缀表达式求值实例:
A=B*C + D*(E-F)
ABC*DEF-*+=
ABC*—做 B*C=T1
AT1DEF- –—做E-F=T2
AT1DT2*—做D*T2=T3
AT1T3+—做T1+T3=T4
AT4=—做A=T4
后缀表达式“32422*+13*-^*5-”,栈中状态变化情况:
typedef char elemtype ;
double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/
{ Seq_Starck s ;
ch=*A++ ; Init_SeqStack(s) ;
while ( ch != ’#’ )
{ if (ch!=运算符) Push_SeqStack (s , ch) ;
else { Pop_SeqStack (s , &a) ;
Pop_SeqStack (s , &b) ; /*取出两个运算量*/
switch (ch).
{ case ch= =’+’: c=b+a ; break ;
case ch= =’-’: c=b-a ; break ;
case ch= =’*’: c=b*a ; break ;
case ch= =’/ ’: c=b/a ; break ;
case ch= =’%’: c=b%a ; break ; }
Push_SeqStack (s, c) ; }
ch=*A++ ;
}
Pop _SeqStack ( s , result ) ;
return result ;
}
(3)中缀表达式变后缀表达式
表达式中操作数次序不变,,运算符次序发生变化,运算符放在操作数的后面。同时去掉了圆括号 。
例:3+(7*8-9)
运算符的优先数表
5
4
3
2
1
0
优先数
^
*,/
+,-
=
)
(
操作
存储结构
W(I)存放表达式的第I个字符。
利用一个栈S()。P为栈指针。
算法设计
Step1:输入是变量则输出它;
Step2:是左括号“(”,无条件地压入堆栈;
Step3:输入运算符优先数是2,3,4,5时,如果栈空,则进栈。如果栈不空,则将它与栈顶元进行比较。倘若优先数大于顶元,则进栈;小于顶元,则顶元退栈并输出之。然后再继续比较,直到大于顶元或栈空时它进栈;
Step4:若是右括号“)”,同时栈顶元又为左括号“(”,则退栈,并抹去“)”。否则按Step3处理;
Step5:输入完而栈非空,则将栈内内容逐一退栈,并输出之。
模拟算法执行过程
A=B*C+D*(E-F)
ABC*DEF-*+=
)
F
-
E
(
*
D
+
C
*
B
=
A
W(I):
栈s ():
top=0
A
变量,输出
输出:
说明:
)
F
-
E
(
*
D
+
C
*
B
=
A
W(I):
栈s ():
A
算符,栈空,入栈
=
输出:
说明:
top=0
top=0
top=1
)
F
-
E
(
*
D
+
C
*
B
=
A
W(I):
=
栈s ():
top=1
A
变量,输出
输出:
说明:
B
)
F
-
E
(
*
D
+
C
*
B
=
A
W(I):
=
栈s ():
AB
算符*,优先级等于4,大于栈顶元素=优先级,入栈
输出:
说明:
*
top=1
top=1
top=2
)
F
-
⑩ 设有两个栈s1和s2共享存储空间c[1,m0],其中一个栈底设在c[1]处,另一个栈底设在c[m0]处,分别编写s1和s2的
void push(x,i)
int x,i;
{
if (top1==top2-1)
printf(“overflow!\n”)
else if (i==1)
{top 1++;c[top1]=x;
}
else
}
top2--;c[top2]=x;
}