2015-数据结构2-栈与队列解读.pptx

1 E-mail: zpyang@mail.xjtu.edu.cn 大学计算机基础Ⅰ 第8章 数据结构（2） 2 主要内容 数据与数据结构 线性表 栈与队列 图和树 3 栈与队列 栈与队列是操作受限的线性表结构。 线性表 例如： InsertList(L,i,x)-在表L的第i个位置插入元素x DeleteFromList(L,i)-删除表L中第i个位置的元素 4 回顾： 一. 栈的概念 在顺序表结构中，插入或删除操作可以在表的任意位置进行。 5 列车仅从调度站的一端进和出。 一摞盘子 生活中遇到的其它现象… 顶端 取和放操作在其顶端进行 “盘子线性表”：表中“元素”为盘子，但存放和取出操作限制在表的一端进行。 “列车调度站线性表”：表中“元素”为列车，但进站和出站操作也限制在表的一端进行。 6 将限制在一端进行插入和删除操作的线性表称为棧。 棧在软件设计中有着广泛的应用。利用棧可方便实现“元素”的“后进先出”功能。 共同特征 对上述现象抽象 利用栈的“后进先出”特性进行“数制转换” 问题： （22）10=（ ） 2 算法： 整数棧 22 2 0 11 2 1 5 2 1 2 2 0 1 2 0 0 1 1 0 1 1 除入栈、出栈操作外，栈的基本操作还有哪些？这些基本操作算法如何实现？ n=22 do { r=n % 2; r入栈 n=n / 2; } while(n!=0); while(栈非空) { 栈顶元素出栈并输出 } 例：对于输入序列A,B,C，经过入栈和出棧操作，能得到的出栈序列有哪些。 ABC,ACB,BAC,BCA,CBA,CAB 8 只有CAB是不可能的。 二.栈的基本操作定义及其实现 置空栈-Clear(s) 求棧的长度-GetLength(s) 判断棧是否为空-IsEmpty(s) 入栈-Push(s,x) 出棧-Pop(s) 取栈顶元素-GetTop(s) 销毁栈-Destroy(s) 9 栈的基本操作包括： 用数组作为栈的存储结构-顺序栈 定义栈类型（结构类型） 实现栈的基本操作 编写主函数进行测试 10 编写步骤： 栈类型定义-顺序栈 11 例：整数棧类型定义 在C中，顺序栈是用数组作为存储结构的。 顺序栈类型的三要素： 声明一维数组作为栈的存储空间（也可动态分配）； 声明指示栈顶位置的变量； 声明指示栈底位置的变量。 typedef struct STACK { int *stackArray; int top; int bottom; } Stack; 其中，Stack为栈类型 栈的元素类型定义： typedef int DataType; 栈变量的定义 12 S棧 0 1 2 3 4 5 6 7 98 99 … 例：定义Stack类型变量S，其栈的空间预设为100个元素。 #define MAXLEN 100 Stack s； s.stackArray= (int *)malloc(sizeof(int)*MAXLEN); 空栈约定： 栈顶和栈底标记为数组的0号元素位置。 其中：s为整数栈变量 s.stackArray指向100元素的存储空间； s.top表示栈顶位置； s.bottom表示栈底位置。 这时S栈已满 进栈操作-Push(S,x) 将元素X进栈，栈顶指针后移 13 … … … … 整数0进栈过程 0 1 2 3 4 5 6 7 98 99 0 提示：进棧操作时，应检查棧满的情况。 if( s-top=棧的长度) 输出信息“棧空间已满！” else { s-stackArray[s-top]=x; s-top+=1; } … S棧 最后一个元素 代码：s-stackArray[s-top]=x; s-top+=1; Push(S,x)操作的完整代码 ‘入栈操作 void Push(Stack * s , int x) { if( s-top=MAXLEN) printf(“棧空间已满！\n”); else { s-stackArray[s-top]=x; s-top+=1; } } 14 出栈操作-Pop(S) 15 提示：出棧操作时，应检查棧空的情况。 if(s-tops-bottom ) { s-top--; return s-stackArray[s-top]; } else { printf(“棧空间已空！\n”); return -1;//失败 }