tceic.com
学霸学习网 这下你爽了
相关文章
当前位置:首页 >> 理学 >>

第3章-栈和队列_图文

第3章 栈和队列
3.1 栈 3.2 栈应用举例 3.3 栈与递归函数

3.4 队列
3.5 队列应用举例 3.6 小结

3.1 栈
1.栈的定义及其基本操作
定义:栈(stack)在逻辑上是一种线性表,记为栈 S =(a0,a1,…,an-1 )。 对栈S的运算(插入、删除等)限定在表的一端进行

X 进栈

X出栈

X
栈顶top
an-1


a1 a0 栈底bottom

栈的定义及其基本操作
栈的特点: ? 后进先出(Last In First Out,LIFO) 若元素进栈顺序为 a0 , a1 , … , an-1 ,则出栈顺序是 an-1 , an2 , … , a0 ,即后进栈的元素先出栈,故栈可称作“后进先出” 的线性表。 ? 栈顶是唯一的出入口。

当栈中没有元素时,称“栈空”。若栈的存储空间已满,再作 进栈运算时称“栈满溢出”。

栈的定义及其基本操作
栈的抽象数据类型:
ADT Stack{ 数据元素集:D={ai |ai∈datatype, i=0,1,2, ???, n-1, n≥0} 数据关系集:R={<ai, ai+1>|ai, ai+1∈D, 0≤i≤n-2} 约定an-1为栈顶元素 基本操作集:P StackInit(&S) 操作结果:创建一个空栈S。 ClearStack(&S) 初始条件:栈S存在。 操作结果:将S清为空栈。 EmptyStack(S) 初始条件:栈S存在。 操作结果:若S为空栈,则返回TRUE(或返回1),否则返回FLASE(或返回0)。

栈的定义及其基本操作
Push(&S,e) 初始条件:栈S存在且未满。 操作结果:插入数据元素e,使之成为新栈顶元素。 Pop(&S) 初始条件:栈S存在且非空。 操作结果:删除S的栈顶元素并返回其值。 GetTop(S) 初始条件:栈S存在且非空。 操作结果:返回栈顶元素的值。 ...... }ADT Stack;

3.1 栈
2.栈的顺序存储结构 (1)顺序栈的描述
#define MAXSIZE 64 //栈最大容量 typedef struct { datatype data[MAXSIZE]; //栈的存储空间 MAXSIZE-1 int top; //栈顶指针(或游标) } sqstack,*sqslink; //顺序栈说明符 S->top 若说明 sqslink S; S = (sqlink)malloc(sizeof(sqstack)); 则S指向一个顺序栈,如右图所示。 栈顶元素an-1写作:S->data [S->top]。 栈空时S->top = -1; 栈满时S->top == MAXSIZE - 1。

an-1


1
0

a1 a0

栈的顺序存储结构
(2)顺序栈基本操作的实现
1)void ClearStack (sqslink s) //置栈空 { s->top = -1; } 2)int EmptyStack (sqslink s) //判栈空 { if(s->top < 0)return 1; //栈空返回1 else return 0 ; //栈非空返回0 } 3)int Push(sqslink s, datatype x) //x进栈// { if (s->top >= MAXSIZE - 1) return -1; //栈满溢出 s->top++; s->data[s->top] = x; //x进栈 return 0; //成功 }

栈的顺序存储结构
4)int Pop(sqslink s, datatype *px) //出栈 { if (EmptyStack(s)) return -1; //栈空,返回-1 *px = s->data[s->top]; s->top--; return 0; //成功 } // 为简单起见,出栈操作常写成 x = Pop(s)

5)int GetTop(sqslink s, datatype *px) { if (EmptyStack(s)) return -1; //栈空,返回-1 *px = s->data[s->top]; return 0; //成功 }

栈的顺序存储结构
栈的共享: S1
a0 …… an-1 空闲空间 bm-1

S2
…… b0

S1底

S->top1

S->top2

S2底

多个栈共用一个数组 可以将栈S1及栈S2的栈底分别设置在头尾两端 (a0,…, an-1)为栈S1中当前元素,S->top1为栈S1的栈顶指针 (b0 ,…, bm-1)为栈S2中当前元素,S->top2为栈S2的栈顶指针

3.1 栈
2.栈的链式存储结构 (1)链式栈的描述
typedef struct node { datatype data ; struct node *next ; } snode,*slink; top an-1 //存储一个栈元素 //后继指针

……

a1

a0

^

top为栈顶指针,表示栈(a0,a1,…,an-1 )。

栈的链式存储结构
(2)链式栈基本操作的实现
1) Lclearstack(slink *ptop) //置栈空 { *ptop = NULL; } // 调用方式:Lclearstack(&top); 2) int Lemptystack(slink top) //判栈空否 { if (top == NULL) return 1; else return 0; } 3) Lpush(slink *ptop, datatype x ) //进栈 { slink p = (slink)malloc(sizeof(snode)) ; //生成进栈p结点 p->data = x; p->next = *ptop; *ptop = p; //p结点作为新的栈顶链入 } // 调用方式:Lpush(&top, x);

栈的链式存储结构
4) int Lpop(slink *ptop, datatype *px) //出栈 { if (Lemptystack(*ptop)) return -1; //栈空返回 *px = (*ptop)->data; //取栈顶元素 slink p = *ptop; *ptop = (*ptop)->next; //重置栈顶指针 free(p); return 0; //成功 } // 调用方式:Lpop(&top, &x); 5) int Lgettop(slink top, datatype *px) { if (Lemptystack(top)) return -1; //栈空返回 *px = top->data; //取栈顶元素 return 0; //成功 }

3.1 栈
3.顺序栈与链式栈的比较
? 时间复杂度:均为O(1)

? 顺序栈长度固定,浪费空间
? 链式栈有结构性开销 ? 可以用数组实现2个栈,每个栈从各自的端点向中间延伸

3.2 栈应用举例
1.数制转换
10进制正整数N与d进制数的基数d之间满足关系: N10= ( N/d )*d + N % d 整除 取模(取余数) 10进制正整数N转换为d进制数的方法: 除以d取余数(直到商为0 ),逆序排列。

数制转换
算法描述:

int x = N; ClearStack(S); //置栈空 while (x >0) { push(S, x % d ); //当前x%d进栈 x = x/d; } while (!EmptyStack(S)) { x = Pop(S); printf("%d", x); }

3.2 栈应用举例
2.表达式求值 (1) 表达式的形式
1)中缀表达式:<操作数1> <操作符> <操作数2> 如A + B 2)后缀表达式:<操作数1> <操作数2> <操作符>,或称逆波兰式 如A B + 3)前缀表达式:<操作符> <操作数1> <操作数2>,或称波兰式 如+ A B

例 中缀表达式:A + (B – C / D) * F
后缀表达式:A B C D / – F * + 前缀表达式:+ A * – B / C D F

表达式求值
(2)后缀表达式求值
后缀表达式计算不存在优先级问题。例如 ABCD/–F*+ 如何计算? 方法: 从左到右扫描,当遇到操作符时,对其左边的2个操作数进行计算,以 结果取代之,继续。

表达式求值
算法思路: 设置一个栈S; 从左到右依次扫描表达式中的各分量x: 若x是操作数:Push(S, x) ; 若x是操作符:a = Pop(S); b = Pop(S); Push(b x a的计算结果); 继续,直到表达式扫描完毕; 最后,栈顶就是表达式的值。

表达式求值
(3)中缀表达式到后缀表达式的转换
如何转换? A+B A+B-C 当扫描到+时记录下来,得AB+ 当扫描到+时记录下来; 当扫描到-时,-的优先级不大于+,说明+应先计算, 则得AB+,最后得AB+C当扫描到+时记录下来; 当扫描到*时,仍然只能先记录下来, 因为不知道后面有无优先级更高的, 最后得ABC*+

A+B*C

采用什么数据结构记录操作符? 栈!

中缀表达式到后缀表达式的转换
再如: A+B–C*D A + (B – C / D) * F 转换方法要点: ? 中缀表达式与后缀表达式的操作数出现的次序是相同的 ? 需要考虑操作符的优先级,优先级高的先转换

? 从左到右扫描表达式,将遇到的操作数输出
? 设置一个栈存放操作符 ? 遇到的第1个操作符进栈

? 将遇到的操作符与栈顶进行优先级比较
? 栈中的操作符满足条件:后进栈的优先级高于先进栈的 ? 当扫描完毕时,若栈非空,则将栈中操作符依次出栈输出

中缀表达式到后缀表达式的转换
方法:
从左到右扫描表达式,设置一个栈s存放操作符; 对于遇到的每个分量x,分以下几种情况处理: 1) x = 操作数:输出x; 2) x = '(':x进栈; 3) x = 操作符(非括号): while (1) { if (EmptyStack(s)) break; y = GetTop(s); if (y = '(') break; if (y 优先级< x) break; y出栈并输出; } x进栈; 4) x = ')' ://之前进栈的'('与')'之间的操作符应先计算! 反复出栈,输出出栈的操作符,直到遇'(',退掉; 当扫描完毕时,若栈非空,则将栈中内容依次出栈输出;

中缀表达式到后缀表达式的转换
例:转换A + (B – C / D) * F的过程。
步骤 1 2 3 4 5 6 7 8 9 10 11 12 扫描的分量 栈内容(栈底->栈顶) 输出的后缀表达式 A + ( B C / D ) * F 结束标志 + +( +( +(+(+(-/ +(-/ + +* +* A A A AB AB ABC ABC ABCD ABCD/ABCD/ABCD/-F ABCD/-F*+ 未扫描的中缀表达式 + (B – C / D) * F (B – C / D) * F B – C / D) * F – C / D) * F C / D) * F / D) * F D) * F )*F *F F

3.3 栈与递归函数
1.递归的定义和递归函数 (1) 递归定义
对于一个定义:<定义对象> = <定义描述> (左部) (右部) 若定义的右部又出现定义的左部形式,则称为一个递归定义

递归的定义和递归函数
例 n的阶乘定义: 1 当n = 0时 n! = n*( n -1)! 当n > 0时 例 Fibonacci数列定义: 0 当n = 0时 Fibnoacci(n)= 1 当n = 1时 Fibonacci(n-1)+Fibonacci(n-2) 例 Ackermam 函数定义: n +1 Ack(m,n) = Ack (m-1, 1) Ack (m-1, Ack (m, n-1))

其他

当m = 0时 当n = 0时 其他

递归的定义和递归函数
(2) 递归函数(或过程)
直接或间接调用自己 ? 直接递归 ? 间接递归

递归的定义和递归函数
(3) 递归的基本思想
? 一个大问题分解为几个子问题,其中的某些子问题与原问题相同, 只是规模比原问题小; ? 随着问题的不断分解,一定存在一个最小问题,可以直接解决,这 便是递归出口(即终止条件)。

说明: ? 对于本身就是递归定义的问题,用递归最容易实现。用非递归反而较难。 ? 任何循环均可以递归的方式来实现。当然,与循环一样,递归过程也必 须存在一个终止条件。 ? 递归过程(函数)设计的关键:保证除了出口参数外,每次调用都不破 坏以前调用时所用到的参数和中间结果。

递归的定义和递归函数
例: int Fact (int n) //求n!(只能用于小规模的n,这里只是为了说明递归) { if (n == 0) return 1; return n*Fact(n-1) ; } int Ack (int m, int n) //求Ackermam函数 { if (m == 0) return n+1; else if (n == 0) return Ack (m-1,1) ; else return ACK (m-1, Ack (m, n-1)); }

递归的定义和递归函数
例 3.10 hanoi塔问题:设有A、B、C三塔(或柱子),n(n≥ 1)个直径不 同的盘子依次从小到大编号为1,2,…,n存放于A塔中。要求将A塔上的 1到n号盘移到C塔,B 塔作为辅助塔。 移动规则:每次只能移动一个盘从一塔到另一塔,且任何时候编号大的 盘不能在编号小的盘之上。

1 2 3 1
(A)

1 2
(B) n=3时的情况

1 2 1 3
(C)

1->C, 2->B, 1->B, 3->C, 1->A, 2->C, 1->C

hanoi塔问题
如何分析设计这类递归问题的算法? 1)最小问题:n=1。可直接解决(从A移到C即可)

2)否则(n >1): ①和③与原问题相同, ① 将A上的1到(n-1)号盘移到B,C为辅助塔; 只是规模小。 ② 将A上第 n号盘移至C; ③ 将B上1到( n -1)号盘移到C,A为辅助塔。
void hanoi ( int n, char A, char B , char C) //hanoi塔算法 { if (n == 1) move (A, 1, C ); //移A上的一个盘到C else { hanoi(n-1, A, C, B); //解决子问题① move (A, n, C); //移A上的n 号盘到C hanoi (n-1, B, A, C); //解决子问题③ } }

递归的定义和递归函数
许多问题都可以很容易用递归函数来设计。例如: 求1 + 2 + 3 + ...+ N。 求N个数的最大值。 将N个数倒序。

递归的定义和递归函数
2.递归到非递归的转换
例 计算n!。 以n = 4为例,分析其计算过程。
Fact(4) = 4 * Fact(3) 3 * Fact(2) 2 * Fact(1) 1 * Fact(0) 1

int Fact (int n) //求n! { if (n == 0) return 1; else return n * Fact(n-1) ; } 返回地址

2种求解思路: (1)从整个问题开始,当不能解决时先记下,不断分解,直到最小问题 直接解决后,再逐层返回。 (2)直接从求最小问题开始。

递归到非递归的转换
非递归: (1)不用栈,直接从最小问题(0!)开始求。 int Fact(int n) { int f, i; f = 1; i = 0; while (i < n) { i++; f = f * i; } return f; }

递归到非递归的转换
(2)引入一个栈S,存放当前参数n。 思路: 当n > 0时,n进栈,然后n--,继续,直到n = 0,得f = 1; 然后,依次出栈→n,f = f * n,直到栈空为止。
int Fact(int n) { int f; ClearStack(S); while (n > 0) { Push(S, n); n--; } f = 1; while (!EmptyStack(S)) { f = f * Pop(S); } return f; }

递归到非递归的转换
说明:

? 对于某些递归问题,非递归函数必须使用栈来实现;
? 理解函数调用与返回;

? 递归过程(函数)与非递归过程(函数)没有本质区别。

递归到非递归的转换
例 求Ackerman函数。 以Ack(2, 1)为例,m=2, n=1。 Ack(2, 1) = 5
int Ack (int m, int n) //求Ackermam函数 { if (m == 0) return n+1; else if (n == 0) return Ack (m-1,1) ; else return ACK (m-1, Ack (m, n-1)); } 返回地址
Ack(2, 1) Ack(1, Ack(2, 0) Ack(1, 1) Ack(0, Ack(1, 0) Ack(0, 1) 2 3 Ack(1, 3) Ack(0, Ack(1, 2) Ack(0, Ack(1, 1) Ack(0, Ack(1, 0)) Ack(0, 1) 2 3 4 5

递归到非递归的转换
非递归: int Ack (int m, int n) //求Ackermam函数 { int f; ClearStack(S); while (1) { if (m == 0) { f = n + 1; if (EmptyStack(S)) break; m = Pop(S); n = f; } else if (n == 0) { m--; n = 1; } else { Push(S, m - 1); n--; } } return f; }

3.4 队列
1.队列的定义及其基本操作
定义:队列(Queue)逻辑上也是一种线性表,记为 Q = (a0, a1 , …, an-1) 对队Q的操作(插入,删除)限定在表的两端进行。 队头:仅能删除(出队) 队尾:仅能插入(进队)

a0 出队

a0 队头

a1

……

an-2

an-1 队尾

X 进队

队列的定义及其基本操作
队列的特点: ? 先进先出(First In First Out,FIFO) 设元素进队顺序为 a0 ,a1, …,an-1 ,则出队顺序也是 a0 ,a1 ,…, an-1,即先进队的元素先出队,故队列可称为“先进先出” 的线 性表, ? 队头是唯一的出口,队尾是唯一的入口。

当队列中没有元素时,称“队空”。若队列存储空间已满,再 作进队操作时,称“队满溢出”。

队列的定义及其基本操作
队列的抽象数据类型:
ADT Queue { 数据元素集:D={ai |ai∈datatype, i=0,1,2, ???, n-1, n≥0} 数据关系集:R={<ai, ai+1>|ai, ai+1∈D, 0≤i≤n-2} 约定a0为队头元素, an-1为队尾元素 基本操作集:P QueueInit(&Q) 操作结果:创建一个空队列Q。 ClearQueue(&Q) 初始条件:队列Q已经存在。 操作结果:清空队列。 QueueLength(Q) 初始条件:队列Q已经存在。 操作结果:返回队列Q的元素个数。

队列的定义及其基本操作
EmptyQueue(Q) 初始条件:队列Q已经存在。 操作结果:若Q为空队列,则返回TRUE,否则返回FLASE。 QueueFull(Q) 初始条件:队列Q已经存在。 操作结果:若Q为已满,则返回TRUE,否则返回FLASE。 EnQueue(&Q,e) 初始条件:队列Q已经存在且未满。 操作结果:插入数据元素e,使之成为新队尾元素。 DeQueue(&Q) 初始条件:队列Q已经存在且非空。 操作结果:删除Q的队头元素,并返回其值。 GetHead(Q) 初始条件:队列Q已经存在且非空。 操作结果:返回队头元素的值。 ...... }ADT Queue;

3.4 队列
2.队列的顺序存储结构 (1)顺序队列的描述
#define MAXSIZE 64 //队列最大容量

typedef struct {
datatype data[MAXSIZE]; //队列的存储空间 int front, rear; //队头、队尾指针

} squeue, *squlink;

队列的顺序存储结构
队头、队尾的位置以及如何变化? Q
MAXSIZE -

rear

1



an-1
an-1 a0

MAXSIZE-1

Q-> rear

j


Q-> front

i

0
a0 头


Q -> data[0]

Q->front 循环队列

队列的顺序存储结构
Q 设Q->front指向队头的前驱 Q->rear指向队尾 rear an-1
MAXSIZE-1

初始化:Q->front = Q->rear = 0
进队: Q->rear = (Q->rear + 1)% MAXSIZE; Q->data[Q->rear] = e;

0 a0 头

出队: Q->front = (Q->front + 1)%MAXSIZE; e = Q->data[Q->front];
如何判断队空/队满? Q->front == Q->rear ? 无法区分队空/队满!

Q->front

队列的顺序存储结构
Q 解决办法: rear an-1
MAXSIZE-1

1)设置1个布尔变量表示队空/队满。
当出队使得队头追上队尾,则队空 当进队使得队尾追上队头,则队满 2)牺牲1个单元,使队尾不会追上队头。 即n个单元最多放n-1个元素 队空: Q->front == Q->rear 队满: (Q->rear + 1) % MAXSIZE == Q->front

0 a0 头

Q->front

队列的顺序存储结构
(2)循环队列基本操作的实现
1) void ClearQueue(squlink Q) //置队空 { Q->front = Q->rear = 0; } 2) int EmptyQueue(squlink Q) //判队空 { return (Q->front == Q->rear); } 3) int QueueLength(squlink Q) //求队Q中当前元素个数 { int i = (Q->rear - Q->front + MAXSIZE) % MAXSIZE; return i; }

队列的顺序存储结构
4) int EnQueue(squlink Q, datatype e) //元素e进队 { if ((Q->rear + 1) % MAXSIZE == Q->front) return -1; //队满 Q->rear = (Q->rear + 1) % MAXSIZE; Q->data[Q->rear] = e; return 0; //成功 } 5) int DeQueue (squlink Q, datatype *pe) //出队 { if ( EmptyQueue(Q)) return -1; //队空 Q->front = (Q->front + 1 ) % MAXSIZE; *pe = Q->data[Q->front]); return 0; }//为了简便起见,调用时常简单地写作e = DeQueue(q);

3.4 队列
2.队列的链式存储结构
头节点 q
front rear

a0

an-1

^

(1)链式队列的描述
typedef struct node { //节点类型 datatype data; struct node *next; }Qnode, *Qlink typedef struct { //q节点类型 Qnode *front, *rear; } linkqueue;

队列的链式存储结构
(2)链式队列基本操作的实现
1) viod Lcreatqueue (linkqueue *q ) //创建空队列 { q->front = q->rear = (Qlink) malloc(sizeof(Qnode)); //申请头节点 q->front->next = NULL; }
2) int Lemptyqueue (linkqueue *q) //判队空 { return ( q->front == q->rear); }

队列的链式存储结构
3) void Lenqueue ( linkqueue *q, datatype e ) //元素e进队 { Qlink p = (Qlink) malloc ( (sizeof (Qnode) ); //申请进队节点 p->data = e; p->next = NULL; q->rear->next = p; q->rear = p; } p 进队示意: q
front rear


a0

an-1

e

^

队列的链式存储结构
4) int Ldequeue(linkqueue *q, datatype *pe) //出队 { Qlink p; if ( Lemptyqueue (q)) return -1; //队空处理 p = q->front ; q->front = p->next ; free(p); *pe = q->front->data; a0 return 0; }
出队示意: q p


front

a 头 0

an-1

^

rear

队列的链式存储结构
如果链式队列采用不带头节点的单链表,如何实现? q
front rear

a0

a1

an-1

^

1) viod Lcreatqueue (linkqueue *q ) //创建空队列 { q->front = q->rear = NULL; }

p

2) int Lemptyqueue (linkqueue *q) //判队空 { return ( q->front == NULL); }

队列的链式存储结构
3) int Lenqueue( linkqueue *q, datatype e ) //元素e进队 { Qlink p = (Qlink) malloc( (sizeof (Qnode) ); //申请进队节点 if (p == NULL ) return -1;//为简化处理,许多算法略去了对p的检查 p->data = e; p->next = NULL; if (q->rear) != NULL ) { q->rear->next = p; q->rear = p; } else { q->front = q->rear p = p; } return 0; }

队列的链式存储结构
4) int Ldequeue(linkqueue *q, datatype *pe) //出队 { Qlink p; if ( Lemptyqueue (q)) return -1; //队空处理 *pe = q->front->data; p = q->front ; q->front = q->front->next ; free(p); if (q->front == NULL ) q->rear = NULL; return 0; p }

3.5 队列应用举例
1.迷宫问题:设二维数组maze[m+2][n+2] 表示一迷宫,如m=5、
n=6 时的迷宫如下图所示。求从迷宫入口到出口的一条最短路径。
0 0 1 2 3 4 5 6
(行下标) 1 1 1 1 1 1 1

1
1 0 0 0 1 1 1

2
1 0 1 1 1 1 1

3
1 1 0 0 1 1 1

4
1 1 1 0 0 1 1

5
1 1 1 0 1 1 1

6
1 1 1 1 0 0 1

7 (列下标)
1 1 1 1 1 1 1

每一步如何走?
(x-1,y) x,y (x-1,y+1) (x,y+1)

(x-1,y-1) (x,y-1)

(x+1,y-1)

(x+1,y)

(x+1,y+1)

(搜索方向)

约定:maze[1][1]=0为迷宫入口,maze[m][n]=0为迷宫出口; maze[x][y]取值为0时表示路通,取1时表示路不通。迷宫外所围的一层为 处理问题方便所加,其相应点全为1。

迷宫问题
0 0 1 2 3 4 5 6
(行下标)

1
1
0 0 0

2
1
0 1 1

3
1
1 0 0

4
1
1 1 0

5
1
1 1 0

6
1
1 1 1

7 (列下标)
1
1 1 1

1
1 1 1

(x-1,y-1)

(x-1,y)

(x-1,y+1)

(x,y-1)
(x+1,y-1)

x,y
(x+1,y)

(x,y+1)
(x+1,y+1)

1
1 1

1
1 1

1
1 1

1
1 1

0
1 1

1
1 1

0
0 1

1
1 1

(搜索方向)

采用什么数据结构?如何处理?

1)8个搜索方向的表示:坐标增量表
2)搜索过程如何记录? 队列,要避免重复搜索

迷宫问题
算法描述:
建立空队列Q;将迷宫入口点进队; 置入口点在迷宫的值为-1; //表示已处理 CurrentPoint = Q队头元素; //入口点 while (CurrentPoint存在) { for (k = 0; k < 8; k++) { //依次处理8个搜索方向 NextPoint =相对CurrentPoint第k个方向的点; if (NextPoint可达) { 将NextPoint进队;置NextPoint在迷宫的值为-1; 在队列Q中记录NextPoint是由CurrentPoint到达的; if (NextPoint是出口点) { 根据队列Q中记录的信息输出路径;return 0; //存在路径 } } } CurrentPoint = Q中CurrentPoint的后继; } return -1; //路径不存在

迷宫问题
y: 0 x: 0 1 2 3 4 1 1 1 1 1 1 1 1 1 0 -1 0 -1 0 -1 1 1 1 2 1 0 -1 1 1 1 1 1 3 1 1 0 -1 0 -1 1 1 1 4 1 1 1 1 0 -1 1 1 5 1 1 1 0 -1 1 1 1 6 1 1 1 1 0 -1 0 -1 1 7 1 1 1 1 1 1 1 队列,p表示前驱 序号 1 2 3 4 5 6 7 8 9 10 x 1 1 2 2 3 3 4 3 4 5 y 1 2 1 3 1 3 4 5 6 6 p 0 1 1 2 3 4 6 7 8 9

5
6

最短路径:

1, 1

1, 2

2, 3

3, 3

4, 4

3, 5

4, 6

5, 6

3.5 队列应用举例
2.离散事件模拟
停车场进出车事件模拟: 停车场可停放若干辆汽车,且只 有一个出入口。汽车在停车场内按到 达的先后顺序,依次由里向外排列。 若停车场已满,后来的汽车只能在车 场外的便道上排队等候。一旦停车场 内有汽车开走,则便道上的第一辆车 可开入。当停车场内某车要开走时, 在它之后的车必须先退到临时车场为 其让路,待汽车开走后,为它让路的 车再按原次序进入停车场。
出入口 临时车场

停车场

出入口

便道

相关的数据结构: 停车场:栈 便道:队列

临时车场:栈

离散事件模拟
相关的事件及处理: 1)车来:
临时车场

停车场

if (停车场栈未满) 车进入停车场栈;
else 车进入便道队列; 2)车走:

出入口

出入口

便道

将停车场中该车后面的所有车依次出栈到临时车场栈; 该车出栈(开走); 将临时车场栈的所有车依次出栈进入停车场栈; if (便道队列非空) 队头车进入停车场栈;

离散事件模拟
停车场栈 临时车场栈

a
信号 车号 A 121 A A A A A A A 122 123 124 125 126 127 128 123

121

A:驶入 D:驶出

a 125 124
出入口

122
124 123 125 124 126 125
出入口

123
队列

D

126

127

128

3.6 小结
定义、特点(LIFO FIFO)、操作

顺序栈、循环队列

链式栈 栈 队列 链式存储结构 链式队列 重点 应用举列
数制转换、表达式求值、 递归到非递归转换等
迷宫问题、事件模拟等

算法实现

第3章 作业
1. 设元素为1,2,3,4,5 。进栈顺序约定:值小的元素先进栈,但 在两次进栈之间,可作出栈运算。写出5个可以得到的出栈序列;5 个不可以得到的出栈序列。 2. 设单链表: H H x x y y z y y x ^ x ^

为对称形式(表长=n)。使用栈操作,写出判断表H是否对称的算法: xyx(H)。


推荐相关:

第3章-栈和队列_图文.ppt

第3章-栈和队列 - 东北大学 数据结构 第3章:栈和队列 主讲:张伟 单位:计

第3章 栈和队列_图文.ppt

数据结构第3章 栈和队列 西安航空学院 计算机工程系 第3章 栈和队列内 容 栈和队列的逻辑结构 栈...

第3章栈和队列_图文.ppt

第3章栈和队列 - 3.1.1 栈的定义和特点 ADT Stack { 数据对象

数据结构 第3章栈和队列自测卷答案_图文.doc

数据结构 第3章栈和队列自测卷答案 - 大学本科计算机科技与技术专业核心课程,数据结构... 数据结构 第3章栈和队列自测卷答案_理学_高等教育_教育专区。大学本科计算...

第3章-1数据结构栈和队列_图文.ppt

第3章-1数据结构栈和队列 - 第三章 栈和队列 学习要点 理解栈和队列的基本概念和各种存储结构; 理解栈和队列的基本概念和各种存储结构; 掌握栈和队列的各种...

数据结构讲义第3章-栈和队列_图文.ppt

数据结构讲义第3章-栈和队列 - 第三章 ? 栈和队列 栈和队列是操作受限的线性表,在计算 机科学和程序设计中有广泛的应用。 3.1栈 3.2栈的应用举例 3.3栈...

第3章栈和队列_图文.ppt

第3章栈和队列 - 第三章 栈和队列 Stack and Queue 栈和队列 栈和队列都是特殊的线性表 线性表:表中数据元素之间存在着线性关系 特殊性:对表的插入和删除...

第3章_栈和队列_图文.ppt

第3章_栈和队列 - 第三章 栈和队列 (Chapter 3. Stack an

第3章 栈和队列_图文.doc

第3章 栈和队列 - 第3章 一,填空题(每空 1 分,共 15 分) 填空题( 栈和队列 1.向量, 向量, 结构, 位置插入和删除元素; 向量 栈和队列都是 线性 ...

第3章 栈和队列_图文.ppt

第3章 栈和队列_理学_高等教育_教育专区。数据结构 第3章 栈与队列数据结构(

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 『数据结构 DATA STRUCTURES』 第三章 栈和队列 第三章 栈和队列 本章要求 掌握栈和队列类型的特点,并能在相应的应用问 题中正确选用...

第3章 栈和队列_图文.ppt

第3章 栈和队列 目录第1章 第2章 第3章 第4章 第5章 第6章 第7章 第9章 第10章 绪论 线性表 栈和队列 串 数组和广义表 树和二叉树 图 查找 排序...

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 第三章 栈和队列 ? 本章内容 3.1 栈 3.1.1 栈

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 第三章 栈和队列 中北大学信息与通信工程学院 主讲:金永 副教授 算法与数据结构 第3章 栈和队列 2 /124 通常称,栈和队列是限定插入和...

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 栈和队列是程序设计中常用的两种 数据结构,是操作受限的线性表,其 逻辑结构和线性表是一样的。 第3章 栈和队列 3.1 栈 3.2 栈的应用...

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 第3章 栈和队列 3.1 栈 3.2 队列 本章小结 3.

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 第3章 栈和队列 3.1 栈 3.2 队列 本章小结 3.

第3章 栈和队列_图文.ppt

第3章 栈和队列 - 第3章 栈和队列 ? ? ? ? 重点难点 1. 栈和队列的特点 2. 逻辑结构及物理表示(顺序表示) 3.进行插入、删除等操作的相应算法 栈和...

第3章-堆栈和队列解析_图文.ppt

第3章-堆栈和队列解析 - 本章主要内容: ? ? ? ? 堆栈 堆栈的应用 队

第3章+栈和队列_图文.ppt

第3章+栈和队列 - 文档均来自网络,如有侵权请联系我删除文档... 第3章 栈和队列栈和队列是两种应用非常广泛的数据结构, 它们都来自线性表数据结构,都是“操作受...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com