2009-7-31第 3章
1
第 3章 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列
2009-7-31 第 3章 2
3.1 栈 ( Stack )
1.定义：限定只在表的一端 (表尾 )进行插入和删除操作的线性表
特点,后进先出 (LIFO)
允许插入和删除的一端称为 栈顶
(top)，另一端称为 栈底 (bottom)
表尾表头
2009-7-31第 3章
3
2,栈的表示和实现
1）顺序栈 ——栈的顺序存储结构
2）链栈 ——栈的链式存储结构
3）静态分配整型指针
2009-7-31第 3章
4
1）顺序栈 ——栈的顺序存储结构限定在表尾进行插入和删除操作的顺序表类型定义,p46
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
SqStack s;
（顺序栈有三个域：栈顶和栈底指针，栈的最大容量）
2009-7-31第 3章
5
说明：
base称为栈底指针，始终指向栈底；
当 base = NULL时，表明栈结构不存在。
top为栈顶指针
a,top的初始值指向栈底，即 top=base
b,空栈：当 top=base时为栈空的标记
c,当栈非空时,top的位置：指向当前栈顶元素的下一个位置
stacksize ——当前栈可使用的最大容量
2009-7-31第 3章
6
进栈示例
base base base base base
stacksize
2009-7-31第 3章
7
退栈示例
base base base base base
2009-7-31第 3章
8
几点说明：
栈空条件,s,top =s,base 此时不能出栈
栈满条件,s.top-s.base>=s.stacksize
进栈操作,*s.top++=e; 或 *s.top=e; s.top++;
退栈操作,e=*--s.top； 或 s.top--； e=*s.top；
当栈满时再做进栈运算必定产生空间溢出，
简称“上溢” ;
当栈空时再做退栈运算也将产生溢出，简称“下溢”。
2009-7-31第 3章
9
基本操作的实现
栈的初始化操作 p47
Status InitStack(SqStack &S)
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
进栈操作 p47
Status Push(SqStack &S,SElemType e)
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
2009-7-31第 3章
10
栈的初始化操作 p47
Status InitStack (SqStack &S) {
S.base = (SElemType )malloc(STACK_INIT_SIZE *
sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top=S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
2009-7-31第 3章
11
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}
2009-7-31第 3章
12
进栈操作 p47
Status Push(SqStack &S,SElemType e)
{
if (S.top-S.base>=S.stacksize)
{ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top = S.base +S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; /* *S.top = e; S.top = S.top+1;
return OK;
}
2009-7-31第 3章
13
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e=*--S.top; /* S.top= S.top;-1; e=*S.top;
return OK;
}
2009-7-31第 3章
14
2）链栈 ——栈的链式存储结构
不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。
类型定义：
typedef struct SNode{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack s;
2009-7-31第 3章
15
链栈示意图 p47 图 3.3
栈空条件,s=NULL
栈满条件,无 / 无 Free Memory可申请
2009-7-31第 3章
16
进栈操作：
Status Push_L (LinkStack &s,SElemType e)
{ p=(LinkStack)malloc(sizeof(SNode));
if (!p) exit(Overflow);
p->data = e; p->next = s; s=p;
return OK;
}
2009-7-31第 3章
17
退栈操作
Status Pop_L (LinkStack &s,SElemType &e)
{ if (!s) return ERROR;
e=s->data; p=s; s=s->next;
free(p);
return OK;
}
2009-7-31第 3章
18
3）静态分配整型指针
定义
#define MAXSIZE 100
typedef struct {
SElemType base[MAXSIZE];
int top;
}SqStack;
SqStack s;
2009-7-31第 3章
19
初始化
status InitStack(SqStack &s)
{ s.top = 0;
return OK;
}
2009-7-31第 3章
20
进栈
Status Push(SqStack &s,SElemType e)
{ if (s.top == MAXSIZE) return ERROR;
s.base[s.top] = e; s.top++;
return OK;
}
2009-7-31第 3章
21
退栈
Status Pop(SqStack &s,SElemType &e)
{ if (s.top ==0) return ERROR;
s.top--;
e=s.base[s.top];
return OK;
}
2009-7-31第 3章
22
取栈顶元素
Status GetTop(SqStack s,SElemType &e)
{
if (s.top == 0) return ERROR;
e=s.base[s.top-1];
return OK;
}
2009-7-31第 3章
23
3.2 栈的应用
1,数制转换 p48 算法 3.1
2,表达式求值 p52 ~ p54
2009-7-31第 3章
24
1,数制转换 p48
十进制 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
低位高位
2009-7-31第 3章
25
算法 3.1
要求：输入一个非负十进制整数，输出任意进制数
void Conversion()
{ InitStack(s);
scanf("%d,%d",&N,&base);
N1=N;
while (N1)
{ Push(s,N1%base);
N1 = N1/base; }
while (!(StackEmpty(s))
{ Pop(s,e);
if (e>9) printf("%c",e+55);
else printf("%c",e+48); }
printf("\n");
}
2009-7-31第 3章
26
2、栈的应用 __算术表达式求值表达式的的三种表示形式：
–中辍式,3*2^（ 4+2*2-6） -5；
–前辍式,-*3^2-+4*2 2 6 5；
–后辍式,3 2 4 2 2*+6-^*5-；
2009-7-31第 3章
27
1）中缀表达式及其计算规则：
（ 1）括号优先。
（ 2）先乘除，后加减。
（ 3）优先级相同的操作符按照先后次序进行。
2009-7-31第 3章
28
2）后缀表达式及其求值：
后缀表达式中只有操作数和操作符，不含有括号，操作符在两个操作数之后，计算规则简单。
由于操作数也是以字符的形式存放的，
所以需要一个函数实现读取一个数，即将一连续的数字字符和圆点组成的字符序列转换为实数。算法见下页：
2009-7-31第 3章
29
float readnumber(char f[],int *i)
{float x=0.0; int k=0;
while(f[*i]>=‘0’ && f[*i]<=‘9’ )
{x=x*10+(f[*i]-’0’);(*i)++;}
if(f[*i]==‘.’)
{(*i)++;
while(f[*i]>=‘0’ && f[*i]<=‘9’ )
{x=x*10+(f[*i]-’0’);(*i)++;k++;}
}
while(k!=0)
{ x=x/10.0; k=k-1;}
return(x);
}
2009-7-31第 3章
30
后缀表达式求值,
将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。
2009-7-31第 3章
31
求一个后缀表达式的值
double evalpost(char f[])
{ double obst[100]; /*操作数栈 */
int top=0; int i=0; double x1,x2;
while(f[i]!=’#’)
{ if (f[i]>=’0’ && f[i]<=’9’)
{obst[top]=readnumber(f,&i);top++;}
else if (f[i]==’’) i++;
else if (f[i]==’+’)
{ x2=obst[--top];
x1=obst[--top]
obst[top]=x1+x2;top++;
i++;
}
2009-7-31第 3章
32
else if (f[i]==’-’)
{ x2=obst[--top]; x1=obst[--top]
obst[top]=x1-x2;top++; i++; }
else if (f[i]==’*’)
{ x2=obst[--top]; x1=obst[--top];
obst[top]=x1*x2; top++; i++; }
else if (f[i]==’/’)
{ x2=obst[--top]; x1=obst[--top];
obst[top]=x1/x2; top++; i++; }
}
return obst[0];
}
2009-7-31第 3章
33
3）中缀表达式转换为后缀表达式：
算法思想：
（ 1）从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和,.”,则直接将它们写入后缀表达式中。
（ 2）如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”
弹出，表明这一层括号内的操作处理完毕。
（ 3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：
2009-7-31第 3章
34
a)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；
b)当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。
重复上述步骤直到遇到中缀表达式的结束标记,#”，弹出栈中的所有元素并放入后缀表达式中，算法结束。
2009-7-31第 3章
35
判断一个字符是否为运算符
int is_operation(char op)
{
switch(op)
{ case ’+’:
case ’-’:
case ’*’:
case ’/’,return 1;
default,return 0;
}
}
2009-7-31第 3章
36
求运算符的优先级别
int priority (char op)
{ switch(op)
{ case ’#’,return -1;
case ’(’,return 0;
case ’+’:
case ’-’,return 1;
case ’*’:
case ’/’,return 2;
default,return -1;
}
}
2009-7-31第 3章
37
将一个中缀表达式,转换为与它等价的后缀表达式
void postfix(char e[],char f[])
{ int i=0,j=0; char opst[100]; int top,t;
top=0; opst[top]=’#’; top++;
while(e[i]!=’#’)
{if((e[i]>=’0’&&e[i]<=’9’)||e[i]==’.’)
f[j++]=e[i]; /*遇到数字和小数点直接写入后缀表达式 */
else if(e[i]==’(’)
{ opst[top]=e[i];top++;}
else if(e[i]==’)’)
/*遇到右括号将其对应的左括号后的操作符全部写入后缀表达式 */
2009-7-31第 3章
38
{ t=top-1;
while (opst[t]!=’(’) {f[j++]=opst[--top];t=top-1;}
top--; /*’(’出栈 */
}
else if (is_operation(e[i])) /*’+,-,*,/’*/
{ f[j++]=’’; /*用空格分开两个操作数 */
while(priority(opst[top-1])>=priority(e[i]))
f[j++]=opst[--top];
opst[top]=e[i];top++; /*当前元素进栈 */
}
i++; /*处理下一个元素 */
}
while(top) f[j++]=opst[--top];
}
2009-7-31第 3章
39
3.4 队列
1,定义
2,链队列 ----队列的链式存储结构
3,循环队列 ----队列的顺序存储结构
2009-7-31第 3章
40
1,定义
是限定在表的一端进行删除，在表的另一端进行插入操作的线性表。
允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性,FIFO(First In First Out)
表头 表尾
2009-7-31第 3章
41
2,链队列 ——队列的链式存储结构
实质是 带头结点的线性链表 ；
两个指针,
队头指针 Q.front指向头结点
队尾指针 Q.rear指向尾结点
初始态,队空条件
头指针和尾指针均指向头结点
Q.front = Q.rear
2009-7-31第 3章
42
1）链队列的类型定义 p61
typedef struct QNode { //元素结点
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //特殊结点
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
LinkQueue Q;
Q.front——指向头结点
Q.rear ——指向链尾结点
2009-7-31第 3章
43
2）链队列示意图 p61图 3.10
2009-7-31第 3章
44
队列运算指针变化状况空队列
2009-7-31第 3章
45
3）基本操作与实现
初始化 p62
Status InitQueue (LinkQueue &Q)
销毁队列 p62
Status DestroyQueue (LinkQueue &Q)
入队 p62
Status EnQueue(LinkQueue &Q,QElemType e)
出队 p62
Status DeQueue(LinkQueue &Q,QElemType &e)
判队空
Status QueueEmpty(LinkQueue Q)
取队头元素
Status GetHead(LinkQueue Q,QElemType &e)
2009-7-31第 3章
46
链队列初始化
Status InitQueue (LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
2009-7-31第 3章
47
链队列的销毁
Status DestroyQueue (LinkQueue &Q)
{ while (Q.front)
{ Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
2009-7-31第 3章
48
Status EnQueue (LinkQueue &Q,QElemType e)
{ p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
链队列的插入（入队）
2009-7-31第 3章
49
Status DeQueue (LinkQueue &Q,ElemType &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if (Q.rear == p) Q.rear=Q.front;
free(p);
return OK;
}
链队列的删除（出队）
2009-7-31第 3章
50
Status QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
判断链队列是否为空
2009-7-31第 3章
51
Status GetHead(LinkQueue Q,QElemType &e)
{
if (QueueEmpty(Q)) return ERROR;
e=Q.front->next->data;
return OK;
}
取链队列的第一个元素结点
2009-7-31第 3章
52
3,循环队列 ——队列的顺序存储结构
顺序队列,
– 用一组地址连续的存储单元依次存放从队列头到队列尾的元素
设两个指针,
– Q.front 指向队列头元素；
– Q.rear 指向队列尾元素的下一个位置
初始状态（空队列）,
– Q.front = Q.rear=0
队列的真满与假满
2009-7-31第 3章
53
类型定义 p64
#define MAXSIZE 100
typedef struct {
QElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
2009-7-31第 3章
54
队列的进队和出队
进队时，将新元素按 Q.rear 指示位置加入，再将队尾指针增 1,Q.rear = Q.rear + 1 。
出队时，将下标为 Q.front 的元素取出，再将队头指针增 1,Q.front = Q.front + 1 。
队满时再进队将溢出出错；队空时再出队作队空处理。上图为,假满,
2009-7-31第 3章
55
存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加 1时从 maxSize -1直接进到 0，
可用语言的取模 (余数 )运算实现。
队头指针进 1,Q.front = (Q.front + 1)% MAXSIZE
队尾指针进 1,Q.rear = (Q.rear + 1)% MAXSIZE;
队列初始化,Q.front = Q.rear = 0;
队空条件,Q.front == Q.rear;
队满条件,(Q.rear + 1) % MAXSIZE == Q.front
队列长度,(Q.rear-
Q.front+MAXSIZE)%MAXSIZE
循环队列 (Circular Queue)
2009-7-31第 3章
56
循环队列的进队和出队
2009-7-31第 3章
57
说明
不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最大队列长度。
循环队列中要有一个元素空间浪费掉 --
--p63 约定队列头指针在队列尾指针的下一位置上为“满”的标志
解决 Q.front=Q.rear不能判别队列“空”
还是“满”的其他办法：
– 使用一个计数器记录队列中元素的总数
（即队列长度）
– 设一个标志变量以区别队列是空或满
2009-7-31第 3章
58
基本操作
初始化 p64
Status InitQueue (SqQueue &Q)
求队列的长度 p64
int QueueLength(SqQueue Q)
入队 p65
Status EnQueue (SqQueue &Q,QElemType e)
出队 p65
Status DeQueue(SqQueue &Q,QElemType &e)
判队空
Status QueueEmpty(SqQueue Q)
取队头元素
Status GetHead(SqQueue Q,QElemType &e)
2009-7-31第 3章
59
Status InitQueue (SqQueue &Q)
{
Q.base=(QElemTye
*)malloc(MAXQSIZE*sizeof(QElemType
));
if (!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
2009-7-31第 3章
60
int QueueLength(SqQueue Q)
{
return (Q.rear-
Q.front+MAXQSIZE)%MAXQSIZE;
}
2009-7-31第 3章
61
Status EnQueue (SqQueue &Q,
QElemType e)
{
if ((Q.rear+1) % MAXQSIZE
==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
2009-7-31第 3章
62
Status DeQueue(SqQueue &Q,
QElemType &e)
{
if (Q.rear==Q.front) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
2009-7-31第 3章
63
Status QueueEmpty(SqQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
2009-7-31第 3章
64
Status GetHead(SqQueue Q,QElemType
&e)
{
if QueueEmpty(Q) return ERROR;
e=Q.base[Q.front];
return OK;
}
2009-7-31第 3章
65
非循环队列
类型定义：与循环队列完全一样
关键：修改队尾 /队头指针 Q.rear =
Q.rear + 1; Q.front = Q.front+1;
在判断时，有 %MAXQSIZE为循环队列，
否则为非循环队列
队空条件,Q.front = Q.rear
队满条件,Q.rear>= MAXQSIZE
注意“假上溢”的处理
长度,Q.rear - Q.front
2009-7-31第 3章
66
思考题：
1、假定有四个元素 A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
2,什么是队列的上溢现象？一般有几种解决方法，
试简述之。什么是队列的上溢现象？一般有几种解决方法，试简述之。
1
第 3章 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列
2009-7-31 第 3章 2
3.1 栈 ( Stack )
1.定义：限定只在表的一端 (表尾 )进行插入和删除操作的线性表
特点,后进先出 (LIFO)
允许插入和删除的一端称为 栈顶
(top)，另一端称为 栈底 (bottom)
表尾表头
2009-7-31第 3章
3
2,栈的表示和实现
1）顺序栈 ——栈的顺序存储结构
2）链栈 ——栈的链式存储结构
3）静态分配整型指针
2009-7-31第 3章
4
1）顺序栈 ——栈的顺序存储结构限定在表尾进行插入和删除操作的顺序表类型定义,p46
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
SqStack s;
（顺序栈有三个域：栈顶和栈底指针，栈的最大容量）
2009-7-31第 3章
5
说明：
base称为栈底指针，始终指向栈底；
当 base = NULL时，表明栈结构不存在。
top为栈顶指针
a,top的初始值指向栈底，即 top=base
b,空栈：当 top=base时为栈空的标记
c,当栈非空时,top的位置：指向当前栈顶元素的下一个位置
stacksize ——当前栈可使用的最大容量
2009-7-31第 3章
6
进栈示例
base base base base base
stacksize
2009-7-31第 3章
7
退栈示例
base base base base base
2009-7-31第 3章
8
几点说明：
栈空条件,s,top =s,base 此时不能出栈
栈满条件,s.top-s.base>=s.stacksize
进栈操作,*s.top++=e; 或 *s.top=e; s.top++;
退栈操作,e=*--s.top； 或 s.top--； e=*s.top；
当栈满时再做进栈运算必定产生空间溢出，
简称“上溢” ;
当栈空时再做退栈运算也将产生溢出，简称“下溢”。
2009-7-31第 3章
9
基本操作的实现
栈的初始化操作 p47
Status InitStack(SqStack &S)
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
进栈操作 p47
Status Push(SqStack &S,SElemType e)
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
2009-7-31第 3章
10
栈的初始化操作 p47
Status InitStack (SqStack &S) {
S.base = (SElemType )malloc(STACK_INIT_SIZE *
sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top=S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
2009-7-31第 3章
11
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}
2009-7-31第 3章
12
进栈操作 p47
Status Push(SqStack &S,SElemType e)
{
if (S.top-S.base>=S.stacksize)
{ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top = S.base +S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; /* *S.top = e; S.top = S.top+1;
return OK;
}
2009-7-31第 3章
13
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e=*--S.top; /* S.top= S.top;-1; e=*S.top;
return OK;
}
2009-7-31第 3章
14
2）链栈 ——栈的链式存储结构
不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。
类型定义：
typedef struct SNode{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack s;
2009-7-31第 3章
15
链栈示意图 p47 图 3.3
栈空条件,s=NULL
栈满条件,无 / 无 Free Memory可申请
2009-7-31第 3章
16
进栈操作：
Status Push_L (LinkStack &s,SElemType e)
{ p=(LinkStack)malloc(sizeof(SNode));
if (!p) exit(Overflow);
p->data = e; p->next = s; s=p;
return OK;
}
2009-7-31第 3章
17
退栈操作
Status Pop_L (LinkStack &s,SElemType &e)
{ if (!s) return ERROR;
e=s->data; p=s; s=s->next;
free(p);
return OK;
}
2009-7-31第 3章
18
3）静态分配整型指针
定义
#define MAXSIZE 100
typedef struct {
SElemType base[MAXSIZE];
int top;
}SqStack;
SqStack s;
2009-7-31第 3章
19
初始化
status InitStack(SqStack &s)
{ s.top = 0;
return OK;
}
2009-7-31第 3章
20
进栈
Status Push(SqStack &s,SElemType e)
{ if (s.top == MAXSIZE) return ERROR;
s.base[s.top] = e; s.top++;
return OK;
}
2009-7-31第 3章
21
退栈
Status Pop(SqStack &s,SElemType &e)
{ if (s.top ==0) return ERROR;
s.top--;
e=s.base[s.top];
return OK;
}
2009-7-31第 3章
22
取栈顶元素
Status GetTop(SqStack s,SElemType &e)
{
if (s.top == 0) return ERROR;
e=s.base[s.top-1];
return OK;
}
2009-7-31第 3章
23
3.2 栈的应用
1,数制转换 p48 算法 3.1
2,表达式求值 p52 ~ p54
2009-7-31第 3章
24
1,数制转换 p48
十进制 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
低位高位
2009-7-31第 3章
25
算法 3.1
要求：输入一个非负十进制整数，输出任意进制数
void Conversion()
{ InitStack(s);
scanf("%d,%d",&N,&base);
N1=N;
while (N1)
{ Push(s,N1%base);
N1 = N1/base; }
while (!(StackEmpty(s))
{ Pop(s,e);
if (e>9) printf("%c",e+55);
else printf("%c",e+48); }
printf("\n");
}
2009-7-31第 3章
26
2、栈的应用 __算术表达式求值表达式的的三种表示形式：
–中辍式,3*2^（ 4+2*2-6） -5；
–前辍式,-*3^2-+4*2 2 6 5；
–后辍式,3 2 4 2 2*+6-^*5-；
2009-7-31第 3章
27
1）中缀表达式及其计算规则：
（ 1）括号优先。
（ 2）先乘除，后加减。
（ 3）优先级相同的操作符按照先后次序进行。
2009-7-31第 3章
28
2）后缀表达式及其求值：
后缀表达式中只有操作数和操作符，不含有括号，操作符在两个操作数之后，计算规则简单。
由于操作数也是以字符的形式存放的，
所以需要一个函数实现读取一个数，即将一连续的数字字符和圆点组成的字符序列转换为实数。算法见下页：
2009-7-31第 3章
29
float readnumber(char f[],int *i)
{float x=0.0; int k=0;
while(f[*i]>=‘0’ && f[*i]<=‘9’ )
{x=x*10+(f[*i]-’0’);(*i)++;}
if(f[*i]==‘.’)
{(*i)++;
while(f[*i]>=‘0’ && f[*i]<=‘9’ )
{x=x*10+(f[*i]-’0’);(*i)++;k++;}
}
while(k!=0)
{ x=x/10.0; k=k-1;}
return(x);
}
2009-7-31第 3章
30
后缀表达式求值,
将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。
2009-7-31第 3章
31
求一个后缀表达式的值
double evalpost(char f[])
{ double obst[100]; /*操作数栈 */
int top=0; int i=0; double x1,x2;
while(f[i]!=’#’)
{ if (f[i]>=’0’ && f[i]<=’9’)
{obst[top]=readnumber(f,&i);top++;}
else if (f[i]==’’) i++;
else if (f[i]==’+’)
{ x2=obst[--top];
x1=obst[--top]
obst[top]=x1+x2;top++;
i++;
}
2009-7-31第 3章
32
else if (f[i]==’-’)
{ x2=obst[--top]; x1=obst[--top]
obst[top]=x1-x2;top++; i++; }
else if (f[i]==’*’)
{ x2=obst[--top]; x1=obst[--top];
obst[top]=x1*x2; top++; i++; }
else if (f[i]==’/’)
{ x2=obst[--top]; x1=obst[--top];
obst[top]=x1/x2; top++; i++; }
}
return obst[0];
}
2009-7-31第 3章
33
3）中缀表达式转换为后缀表达式：
算法思想：
（ 1）从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和,.”,则直接将它们写入后缀表达式中。
（ 2）如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”
弹出，表明这一层括号内的操作处理完毕。
（ 3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：
2009-7-31第 3章
34
a)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；
b)当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。
重复上述步骤直到遇到中缀表达式的结束标记,#”，弹出栈中的所有元素并放入后缀表达式中，算法结束。
2009-7-31第 3章
35
判断一个字符是否为运算符
int is_operation(char op)
{
switch(op)
{ case ’+’:
case ’-’:
case ’*’:
case ’/’,return 1;
default,return 0;
}
}
2009-7-31第 3章
36
求运算符的优先级别
int priority (char op)
{ switch(op)
{ case ’#’,return -1;
case ’(’,return 0;
case ’+’:
case ’-’,return 1;
case ’*’:
case ’/’,return 2;
default,return -1;
}
}
2009-7-31第 3章
37
将一个中缀表达式,转换为与它等价的后缀表达式
void postfix(char e[],char f[])
{ int i=0,j=0; char opst[100]; int top,t;
top=0; opst[top]=’#’; top++;
while(e[i]!=’#’)
{if((e[i]>=’0’&&e[i]<=’9’)||e[i]==’.’)
f[j++]=e[i]; /*遇到数字和小数点直接写入后缀表达式 */
else if(e[i]==’(’)
{ opst[top]=e[i];top++;}
else if(e[i]==’)’)
/*遇到右括号将其对应的左括号后的操作符全部写入后缀表达式 */
2009-7-31第 3章
38
{ t=top-1;
while (opst[t]!=’(’) {f[j++]=opst[--top];t=top-1;}
top--; /*’(’出栈 */
}
else if (is_operation(e[i])) /*’+,-,*,/’*/
{ f[j++]=’’; /*用空格分开两个操作数 */
while(priority(opst[top-1])>=priority(e[i]))
f[j++]=opst[--top];
opst[top]=e[i];top++; /*当前元素进栈 */
}
i++; /*处理下一个元素 */
}
while(top) f[j++]=opst[--top];
}
2009-7-31第 3章
39
3.4 队列
1,定义
2,链队列 ----队列的链式存储结构
3,循环队列 ----队列的顺序存储结构
2009-7-31第 3章
40
1,定义
是限定在表的一端进行删除，在表的另一端进行插入操作的线性表。
允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性,FIFO(First In First Out)
表头 表尾
2009-7-31第 3章
41
2,链队列 ——队列的链式存储结构
实质是 带头结点的线性链表 ；
两个指针,
队头指针 Q.front指向头结点
队尾指针 Q.rear指向尾结点
初始态,队空条件
头指针和尾指针均指向头结点
Q.front = Q.rear
2009-7-31第 3章
42
1）链队列的类型定义 p61
typedef struct QNode { //元素结点
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //特殊结点
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
LinkQueue Q;
Q.front——指向头结点
Q.rear ——指向链尾结点
2009-7-31第 3章
43
2）链队列示意图 p61图 3.10
2009-7-31第 3章
44
队列运算指针变化状况空队列
2009-7-31第 3章
45
3）基本操作与实现
初始化 p62
Status InitQueue (LinkQueue &Q)
销毁队列 p62
Status DestroyQueue (LinkQueue &Q)
入队 p62
Status EnQueue(LinkQueue &Q,QElemType e)
出队 p62
Status DeQueue(LinkQueue &Q,QElemType &e)
判队空
Status QueueEmpty(LinkQueue Q)
取队头元素
Status GetHead(LinkQueue Q,QElemType &e)
2009-7-31第 3章
46
链队列初始化
Status InitQueue (LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
2009-7-31第 3章
47
链队列的销毁
Status DestroyQueue (LinkQueue &Q)
{ while (Q.front)
{ Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
2009-7-31第 3章
48
Status EnQueue (LinkQueue &Q,QElemType e)
{ p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
链队列的插入（入队）
2009-7-31第 3章
49
Status DeQueue (LinkQueue &Q,ElemType &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if (Q.rear == p) Q.rear=Q.front;
free(p);
return OK;
}
链队列的删除（出队）
2009-7-31第 3章
50
Status QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
判断链队列是否为空
2009-7-31第 3章
51
Status GetHead(LinkQueue Q,QElemType &e)
{
if (QueueEmpty(Q)) return ERROR;
e=Q.front->next->data;
return OK;
}
取链队列的第一个元素结点
2009-7-31第 3章
52
3,循环队列 ——队列的顺序存储结构
顺序队列,
– 用一组地址连续的存储单元依次存放从队列头到队列尾的元素
设两个指针,
– Q.front 指向队列头元素；
– Q.rear 指向队列尾元素的下一个位置
初始状态（空队列）,
– Q.front = Q.rear=0
队列的真满与假满
2009-7-31第 3章
53
类型定义 p64
#define MAXSIZE 100
typedef struct {
QElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
2009-7-31第 3章
54
队列的进队和出队
进队时，将新元素按 Q.rear 指示位置加入，再将队尾指针增 1,Q.rear = Q.rear + 1 。
出队时，将下标为 Q.front 的元素取出，再将队头指针增 1,Q.front = Q.front + 1 。
队满时再进队将溢出出错；队空时再出队作队空处理。上图为,假满,
2009-7-31第 3章
55
存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加 1时从 maxSize -1直接进到 0，
可用语言的取模 (余数 )运算实现。
队头指针进 1,Q.front = (Q.front + 1)% MAXSIZE
队尾指针进 1,Q.rear = (Q.rear + 1)% MAXSIZE;
队列初始化,Q.front = Q.rear = 0;
队空条件,Q.front == Q.rear;
队满条件,(Q.rear + 1) % MAXSIZE == Q.front
队列长度,(Q.rear-
Q.front+MAXSIZE)%MAXSIZE
循环队列 (Circular Queue)
2009-7-31第 3章
56
循环队列的进队和出队
2009-7-31第 3章
57
说明
不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最大队列长度。
循环队列中要有一个元素空间浪费掉 --
--p63 约定队列头指针在队列尾指针的下一位置上为“满”的标志
解决 Q.front=Q.rear不能判别队列“空”
还是“满”的其他办法：
– 使用一个计数器记录队列中元素的总数
（即队列长度）
– 设一个标志变量以区别队列是空或满
2009-7-31第 3章
58
基本操作
初始化 p64
Status InitQueue (SqQueue &Q)
求队列的长度 p64
int QueueLength(SqQueue Q)
入队 p65
Status EnQueue (SqQueue &Q,QElemType e)
出队 p65
Status DeQueue(SqQueue &Q,QElemType &e)
判队空
Status QueueEmpty(SqQueue Q)
取队头元素
Status GetHead(SqQueue Q,QElemType &e)
2009-7-31第 3章
59
Status InitQueue (SqQueue &Q)
{
Q.base=(QElemTye
*)malloc(MAXQSIZE*sizeof(QElemType
));
if (!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
2009-7-31第 3章
60
int QueueLength(SqQueue Q)
{
return (Q.rear-
Q.front+MAXQSIZE)%MAXQSIZE;
}
2009-7-31第 3章
61
Status EnQueue (SqQueue &Q,
QElemType e)
{
if ((Q.rear+1) % MAXQSIZE
==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
2009-7-31第 3章
62
Status DeQueue(SqQueue &Q,
QElemType &e)
{
if (Q.rear==Q.front) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
2009-7-31第 3章
63
Status QueueEmpty(SqQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
2009-7-31第 3章
64
Status GetHead(SqQueue Q,QElemType
&e)
{
if QueueEmpty(Q) return ERROR;
e=Q.base[Q.front];
return OK;
}
2009-7-31第 3章
65
非循环队列
类型定义：与循环队列完全一样
关键：修改队尾 /队头指针 Q.rear =
Q.rear + 1; Q.front = Q.front+1;
在判断时，有 %MAXQSIZE为循环队列，
否则为非循环队列
队空条件,Q.front = Q.rear
队满条件,Q.rear>= MAXQSIZE
注意“假上溢”的处理
长度,Q.rear - Q.front
2009-7-31第 3章
66
思考题：
1、假定有四个元素 A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
2,什么是队列的上溢现象？一般有几种解决方法，
试简述之。什么是队列的上溢现象？一般有几种解决方法，试简述之。
