第3章栈和队列 3.2栈的共享存储单元《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第三章：栈和队列 栈的共享存储单元 有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补，最常见的是两个栈共享一个存储空间。 当两个栈共享一个存储空间时，可以有效节省空间，提高空间使用效率。假设原先每一个栈出现上溢的机会是10%，则相同存储单元时，采用共享存储时，上溢的机会是1%。 另一方面，现实情况是共享存储的空间并非一定是两个栈原先空间之和，而可能是稍小于原先栈空间之和。 3.1.3 链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 栈的链接存储结构 链栈的类型及变量说明如下： typedef struct node { datatype data; struct node *next; }linkstack; linkstack * top; 栈的链接表示 — 链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 链栈的进栈算法 linkstack *PUSHLSTACK(top, x) linkstack *top, datatype x； { linkstack *p; p＝(linkstack *)malloc(sizeof(linkstack)); p->data＝x; p->next＝top; return p; /*返回新栈顶指针*/ } 链栈的出栈算法 linkstack *POPLSTACK ( linkstack *top, datatype *datap) { linkstack *p; if (top==NULL) { printf(“under flow ”); return NULL;} else { *datap＝top->data; p＝top; top＝top->next; free(p); return top; } } 3.2 栈的应用举例－－文字编辑器 （p46） seqstack s; EDIT() { char c; SETNULL(&s); c＝getchar(); while (c!=‘*’) /* 字符‘*’为编辑结束符 */ { if (c==‘#’) POP(&s); /* 读入字符‘＃’，则退栈 */ else if (c==‘@’) SETNULL(&s); /* 读入字符‘＃’，则置空栈 */ else PUSH(&s,c); /* c字符入栈 */ c＝getchar(); } } 汉诺塔（ Hanoi） 有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。 移动时的规则： 每次只能移动一个盘子； 只能小盘子在大盘子上面； 可以使用任一柱子。 分析： 设三根柱子分别为 x，y, z , 盘子在 x 柱上，要移到 z 柱上。 1、当 n=1 时，盘子直接从 x 柱移到 z 柱上； 2、当 n>1 时, 则: ①设法将 前 n –1 个盘子 借助 z ，从 x 移到 y 柱上，把 盘子 n 从 x 移到 z 柱上； ② 把n –1 个盘子 从 y 移到 z 柱上。 x y z n n –1 Void Hanoi ( int n, char x, char y, char z ) { //将 n 个 编号从上到下为 1…n 的盘子从 x 柱，借助 y 柱移到 z 柱 if ( n = = 1 ) move ( x , 1 , z ) ; //将编号为 1 的盘子从 x 柱移到 z 柱 else { //将 n -1个 编号从上到下为1…n-1的盘子从 x 柱，借助 y 柱移到 z 柱 Hanoi ( n-1 , x , z , y ) ; move ( x ,