单共享栈
发布网友
发布时间：2022-05-05 15:47
共1个回答
热心网友
时间：2022-06-27 17:22
一、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
-
参考资料：http://www.wz12365.com/sjjg/ADMIN/webedit/uploadfile/03.PPT
