《[医学]栈和队列000》由会员分享，可在线阅读，更多相关《[医学]栈和队列000（108页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列 栈和队列是两种特殊的线性表，它们是运算时要 受到某些限制的线性表，故也称为限定性的数据 结构。3.1 栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an），其中a1是栈底元素， an是栈顶元素。a1a2.an进栈出栈栈顶栈底3.1 栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an），其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bott
2、om):不允许插入和删除的一端。a1a2.an进栈出栈栈顶栈底栈的习题 入栈出栈的次序判断 栈的特性3.1.2栈的存储结构顺序栈、链栈a2a1a1a2top(1)顺序栈：用顺序存储结构表示的栈。(1) 顺序栈用一组连续的存储单元 存放自栈底到栈顶的数据元素， 一般用一维数组表示，设置一个 简单变量top指示栈顶位置，称为 栈顶指针，它始终指向待插入元 素的位置。栈中的运算：1.设置空栈 ； 2. 插入一个新的栈顶元素 3. 删除栈顶元素； 4. 读取栈顶元素 。 设数组S是一个顺序栈，栈的最大容量stacksize=4 ，初始状态top=010S4231 0base stop=xtop=top
3、+1top102530S4231 0topbase top=top-1 x=stop栈空10进栈30出栈S4231 0 Top=0top栈满top=stacksize10253040S4231 0top=4base 进栈算法#define statcksize 100int 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) ; 通过地址传递，用 pto
4、p带回实际栈顶指 针a2a3a49 876543 21a10top出栈算法：int pop(int s , int *ptop, int *py)int top;top=*ptop;if(top= =0) printf(“stack empty”); return( 0); else - -top;*py=stop; /*返回出栈元素*/*ptop=top;return(1);通过地址传递，用 ptop带回实际栈顶指 针通过指针变量py 带回出栈元素栈 sa2a3a49 876543 21a10topxtop栈底（2）链栈用指针来实现的栈叫链栈。栈的容量事先不能 估计时采用这种存储结构。链栈的
5、类型说明如下：Typedef struct lnodeint data；struct lnode next；lnode，Lstack；进栈算法int lpush(Lstack s, int e)p=(Lstack)malloc(sizeof(lnode);p-data=e; p-next=s;s=p;return (1);baseS栈 s进栈元素e进栈算法int lpush(Lstack s, int e)p=(Lstack)malloc(sizeof(lnode);p-data=e; p-next=s;s=p;return (1);PbaseS进栈算法int lpush(Lstack s,
6、int e)p=(Lstack)malloc(sizeof(lnode);p-data=e; p-next=s;s=p;return (1);PbaseSe进栈算法int lpush(Lstack s, int e)p=(Lstack)malloc(sizeof(lnode);p-data=e; p-next=s;s=p;return (1);PbaseSe进栈算法int lpush(Lstack s, int e)p=(Lstack)malloc(sizeof(lnode);p-data=e; p-next=s;s=p;return (1);PbaseSSer主程序s rrrs子程序1rst
7、子程序2rst子程序33.1.3 栈的应用(1) 过程的嵌套(2) 递归算法： 1 (n=0,1) n! = n(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); 间接调用 特点是无终止的递归调用，因此，应该给定一个限制递 归次数的条件。
8、f 1函数调用 f2函数f 2函数调用 f1函数float fac ( int n)float f;if(n 2) IF t=0 THEN read W;IF W 为操作数 THEN Push( NS, W, top1) ELSE p=OStop2; /读运算符栈栈顶元素，存入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=“）”）THENELSE Pop(NS,x,to
9、p1); 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; 4、 地图四染色问题“四染色”定理是计算机科学中著名的定理之一。使地图中相邻的国家或行政区域不重色，最少可用四种 颜色对地图着色。证明此定理的结论，利用栈采用回溯法对地图着色。思想：对每个行政区编号：1-7对颜色编号；a、b、c、d；从第一号行政区开始逐一染色，每一个区域逐次用四种 颜色进行试探，若所取颜色与周围不重，则用栈记下来 该区域的色数，否则依次用下
10、一色数进行试探。若出现 a-d均与周围发生重色，则需退栈回溯，修改当前栈顶 的色数。011 11 10100001010011001010110101101011011000000000R 1: 7 , 1 : 7 1 2 3 4 5 6 71 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)(4)(5)(6)(7)(3)1# 粉色2# 黄色3# 红色4# 绿色123212312243123243123
11、241232431122341 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 000000000110110101101011010100110010100001011 11 101 2 3 4 5 6 71 2 3 4 5 6 7 11 2 3 4 5 6 7 Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色I=2; J=1; / I为区域号，J为染
12、色号while ( I4) THEN I=I-1; J=sI+1 011 11 101000010100110010101101011010110110000000001 2 3 4 5 6 71 2 3 4 5 6 7 11 2 3 4 5 6 7 I=2,J=1k=1Void 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 011 11 101000010100110010101101011010110110000000001 2 3 4 5 6
13、 71 2 3 4 5 6 7 11 2 3 4 5 6 7 I=2,J=2k=1Void 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 011 11 101000010100110010101101011010110110000000001 2 3 4 5 6 71 2 3 4 5 6 7 11 2 3 4 5 6 7 1I=2,J=2k=2Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色I=2;
14、J=1; / I为区域号，J为染色号while ( I4) THEN I=I-1; J=sI+1 000000000110110101101011010100110010100001011 11 101 2 3 4 5 6 71 2 3 4 5 6 7 11 2 3 4 5 6 7 1I=3,J=1k=22Void mapcolor(int R,int n,int s) I=2; J=1; / I为区域号，J为染色号while ( I4) THEN I=I-1; J=sI+1 011 11 101000010100110010101101011010110110000000001 2 3 4 5 6 71 2 3 4 5 6 7 122341 2 3 4 5 6 7 I=6,J=1k=1Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号while ( I4) THEN I=I-1; J=sI+1 000000000110110101101011010100110010100001011 11 101 2 3 4 5 6 71 2 3 4 5 6 7 432211 2 3 4 5 6 7 I=6,J=2k=1Void
