【精品数据结构】栈和队列3

1、,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,数据结构,第二章数据结构与算法,(续),2.3 栈和队列,栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,.3.1 栈 2.3.1.1栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。,.3.1 栈 2.3.1.1栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其

2、中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除的一端。,栈中的运算：1.设置空栈 ； 2. 插入一个新的栈顶元素 3. 删除栈顶元素； 4. 读取栈顶元素 。,设数组S是一个顺序栈，栈的最大容量stacksize=4 ，初始状态top=0,栈空,10进栈,30出栈,栈满,2.3.1.2栈的存储结构 顺序栈、链栈,顺序栈： 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待

3、插入元素的位置。, 进栈算法 #define statcksize 100 int push(int s , int x, int *ptop), int top; top=*ptop; if(top= =stacksize) printf(“overflow”); return (0); else stop=x; *ptop=+top; /*实际栈顶指针加1 */ return (1) ; ,通过地址传递，用ptop带回实际栈顶指针,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,出栈算法： int pop(int s , int *ptop, int *py), i

4、nt top; top=*ptop; if(top= =0) printf(“stack empty”); return( 0); else - -top; *py=stop; /*返回出栈元素*/ *ptop=top; return(1); ,通过地址传递，用ptop带回实际栈顶指针,通过指针变量py带回出栈元素,栈 s,top,栈底,（2）链栈 用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。,链栈的类型说明如下： Typedef struct lnode int data； struct lnode next； lnode，Lstack；,进栈算法 int lpush(L

5、stack s, int e) p=(Lstack)malloc(sizeof(lnode); p-data=e; p-next=s; s=p; return (1); ,base,S,栈 s,进栈元素e,进栈算法 int lpush(Lstack s, int e) p=(Lstack)malloc(sizeof(lnode); p-data=e; p-next=s; s=p; return (1); ,base,S,进栈算法 int lpush(Lstack s, int e) p=(Lstack)malloc(sizeof(lnode); p-data=e; p-next=s; s=p;

6、 return (1); ,base,S,e,进栈算法 int lpush(Lstack s, int e) p=(Lstack)malloc(sizeof(lnode); p-data=e; p-next=s; s=p; return (1); ,base,S,e,进栈算法 int lpush(Lstack s, int e) p=(Lstack)malloc(sizeof(lnode); p-data=e; p-next=s; s=p; return (1); ,base,S,e,r,主程序,2.3.1.3 栈的应用 (1) 过程的嵌套,(2) 递归算法：,1 (n=0,1) n! = n

7、(n-1)！ (n1),函数的递归调用,1. 定义： 在调用一个函数的过程中直接或间接地调用该函数本身。 直接调用 int f(x) int x; int y,z; . z=f(x); return (2*z); ,f 函数,调用 f函数,int f1(x) int x; int y,z; . z=f2( y); return (2*z); ,int f2(t) int t; int a,c; . c=f1(a); return (3+c); ,间接调用,特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。,float fac ( int n) float f; if(n0) pr

8、intf(“n0,data error!n”); else if(n= =0|n= =1) f=1; else f=fac(n-1)* n ; return f; ,例如：写一函数求n!,以求4的阶乘为例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)=2*fac( 1),fac(1)=1,fac(4)=4*3*2*1,fac(2)=2*1,fac(3)=3*2*1,下 推,回 代,利用栈实现递归调用,递归的执行情况分析,long Fact ( int n) long s; if ( n= =1) s=1; else s=n*Fact(n-1); return

9、(s); ,运算符： * / * + - （ ） 界限符： ；,以表达式 A*B + CD 为例说明利用栈的求值过程。,优先级： 4 3 3 2 2 1 1 0,（3）表达式的计算,操作数变量：A B C D,A*B + C/D;,top2,思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断： 若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。 2.若读入的运算符的优先级

10、大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。 3. 若读入的是“；”，且运算符栈顶的符号也是“；”时，则表达式处理结束。从操作数栈弹出表达式结果。,输入：表达式符号序列,表达式求值算法：,输出：表达式值 y,初始化栈 NS、OS,Push (OS, “;” , top2)； t=0; /表示扫描下一个符号 while (t 2) IF t=0 THEN read W;,IF W 为操作数 THEN Push( NS, W, top1),ELSE p=OStop2; /

11、读运算符栈栈顶元素，存入p .,IF (Wp)or(W=“(“) THEN,Push (OS, W, top2); t=0;,ELSE IF (p=“;” ）and (W=“ ;”) THEN, Pop (NS, y,top1); t=2; /处理过程结束,ELSE IF (p=“(“ )and (w=“）”）THEN,ELSE Pop(NS,x,top1);,Pop(NS,z,top1);,Pop(OS,p,top2）；,x=z x;,Push(NS ,x ,top1);,t=1; /t=1,当前的符号下次重新考虑,输出 y; return;, Pop(OS ,p,top2); t=0; ,

12、4、 地图四染色问题 “四染色”定理是计算机科学中著名的定理之一。 使地图中相邻的国家或行政区域不重色，最少可用四种颜色对地图着色。 证明此定理的结论，利用栈采用回溯法对地图着色。 思想：对每个行政区编号：1-7 对颜色编号；a、b、c、d； 从第一号行政区开始逐一染色，每一个区域逐次用四种颜色进行试探，若所取颜色与周围不重，则用栈记下来该区域的色数，否则依次用下一色数进行试探。若出现a-d均与周围发生重色，则需退栈回溯，修改当前栈顶的色数。,1 2 3 4 5 6 7,1 2 3 4 5 6 7,(1),(2),(4),(5),(6),(7),(3),1# 粉色 2# 黄色 3# 红色 4#

13、 绿色,1 2 3 4 5 6 7,S 1 : 7 ,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4

14、 5 6 7,1 2 3 4 5 6 7,I=2,J=1,k=1,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=2,J=2,k=1,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2

15、 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=2,J=2,k=2,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=3,J=1,k=2,2,Void mapcolor(int R,int n,int s) I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1

16、,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7

17、,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7

18、,1 2 3 4 5 6 7,I=6,J=3,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7

19、,I=6,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=1,V

20、oid mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=3,Void mapcolor(i

21、nt R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=5,Void mapcolor(int R,int n,int

22、 s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=5,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=5,k=4,Void mapcolor(int R,int n,int s) I=6; J=1;

23、/ I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号

24、while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) TH

25、EN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI

26、+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5

27、6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5

28、6 7,1 2 3 4 5 6 7,I=4,J=4,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5

29、6 7,I=4,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=1,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=1,k=

30、1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=2,Void mapcolo

31、r(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=3,Void mapcolor(int R,int n,

32、int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=

33、1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染

34、色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4)

35、 THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J

36、=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4

37、 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4

38、 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2