山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第3章 栈和队列

第三章栈和队列 栈和队列是两种特殊的线性表,是操作受限的线 性表,称限定性DS §3.1栈(stack) ★栈的定义和特点 定义:限定仅在表尾进行插入或删除操作的线性表, 表尾一栈顶,表头一栈底,不含元素的空表称空栈 特点:先进后出(FLO)或后进先出(LFO) 进栈 出栈 顶 An 栈s=(al,a2,.…,an a2 栈底 a1
第三章 栈和队列 栈和队列是两种特殊的线性表,是操作受限的线 性表,称限定性DS §3.1 栈(stack) 栈的定义和特点 ❖定义:限定仅在表尾进行插入或删除操作的线性表, 表尾—栈顶,表头—栈底,不含元素的空表称空栈 ❖特点:先进后出(FILO)或后进先出(LIFO) an a1 a2……... 栈底 栈 顶 进栈 ... 出栈 栈s=(a1,a2,……,an)

饯的类型定义 ADT Stack{ 数据对象 D={a|a:∈ElemSet,.i=l,2,.,n,n≥0} 数据关系: RI={ai-,aED,i=2,...n 约定a,端为栈顶,a端为栈底。 基本操作: ADT Stack
栈的类型定义 ADT Stack { 数据对象: D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系: R1={ | ai-1 , ai∈D, i=2,...,n } 约定an 端为栈顶,a1 端为栈底。 基本操作: } ADT Stack

InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,&e) StackTravers(S,visitO)
InitStack(&S) DestroyStack(&S) ClearStack(&S) StackEmpty(s) StackLength(S) GetTop(S, &e) Push(&S, e) Pop(&S, &e) StackTravers(S, visit())

★栈的表示和实现 顺序栈 ●实现: 一维数组S[M我满 栈空 top top 5 F top top 4 top E top 4 3 top D top 3 3 2 top c top 2 top top B A top top=0 栈空 出栈 栈顶指针top,指向实际栈顶 设数组维数为M 后的空位置,初值为0 top=O,栈空,此时出栈,则下溢(underflow) top=M,栈满,此时入栈,则上溢(overflow)
栈的表示和实现 ❖顺序栈 ⚫实现:一维数组s[M] top=0 1 2 3 4 5 0 栈空 栈顶指针top,指向实际栈顶 后的空位置,初值为0 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组维数为M top=0,栈空,此时出栈,则下溢(underflow) top=M,栈满,此时入栈,则上溢(overflow) top top top top top 1 2 3 4 5 A 0 B C D E top F top top top top top 栈空

栈的顺序存储表示: #define STACK INIT SIZE 100: #define STACKINCREMENT 10: Typedef struct{ SElemType *base; SElemType *top; int stacksize; SqStack; ●初始化算法 ●取栈项元素算法
⚫初始化算法 ⚫取栈项元素算法 栈的顺序存储表示: #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; Typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack;

构造空栈 Status InitStack(SqStack &S){ /构造一个空栈$ S.base=(SElemType *)malloc (STACK INIT SIZE sizeof(SElemType)); if(IS.base)exit(OVERFLOW);H/存储分配失败 S.top-S.base; S.stacksize=STACK INIT SIZE: return OK; //InitStack
Status InitStack(SqStack &S) { // 构造一个空栈S S.base=(SElemType *) malloc (STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit (OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack 构造空栈

Stack GetTop(SqStack S,SElemType &e){ /若栈不空,则用返回S的栈顶元素,并返回OK, /否则返回ERROR; if(S.top-=S.base)return ERROR; e-*(S.top-1); return OK: //GetTop
Stack GetTop (SqStack S,SElemType &e) { //若栈不空,则用e返回S的栈顶元素,并返回OK, //否则返回ERROR; if (S.top==S.base) return ERROR; e=*(S.top-1); return OK; }//GetTop

●入栈算法 ●出栈算法 ●在一个程序中同时使用两个栈 M-1 栈1底 栈1顶 栈2顶 栈2底
⚫入栈算法 0 M-1 栈1底 栈1顶 栈2顶 栈2底 ⚫出栈算法 ⚫在一个程序中同时使用两个栈

入栈 Status Push(SqStack &S,SElemType e){ /插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize){ S.base=(ElemType *)realloc (S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType));; if(IS.base)exit (OVERFLOW): S.top-S.base+S.stacksize; S.stacksize+=STACKINCREMENT: } *S.top++-e; return OK; //Push
Status Push(SqStack &S,SElemType e) { //插入元素e为新的栈顶元素 if (S.top-S.base>=S.stacksize) { S.base=(ElemType *) realloc (S.base, (S.stacksize+STACKINCREMENT)* sizeof(ElemType));; if (!S.base) exit (OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push 入栈

int push(int s[],int x,int top) if(top=-M) printf("overflow"): return(-M): s[top]-x; return(++top); d
int push(int s[],int x,int top) { if(top==M) { printf("overflow"); return(-M); } s[top]=x; return(++top); }
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第2章 线性表.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第1章 绪论(主讲教师:王玫).ppt
- 大连大学:信息工程学院计算机科学与技术专业课程教学大纲汇编.pdf
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程授课电子教案 Computer Image Processing.doc
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程PPT教学课件讲稿(负责人:张兆臣).ppt
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程各章作业习题.doc
- 大连大学:软件工程学院软件工程专业课程教学大纲汇编.pdf
- 湖南人文科技学院:《Web前端开发》课程思政教学资源(PPT课件)网站开发基础.pptx
- 湖南人文科技学院:《Web前端开发》课程思政教学资源(授课教案)网站开发基础(主讲教师:刘鹃梅).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《毕业论文》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《认知见习》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《专业见习2》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《专业见习1》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《校内见习》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《C语言程序设计》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《综合设计(数学建模)》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《数值分析课程设计》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《多媒体技术应用》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《微机原理与接口技术》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《PHP动态网站开发》课程教学大纲(2015).pdf
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第4章 串.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第5章 数组和广义表.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第6章 树.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第7章 图.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第9章 查找.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第10章 排序.ppt
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第一章 Java语言基础(主讲:高洋).pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第二章 使用Java解决简单的问题.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第三章 类、类的继承和接口.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第四章 Java类库简介和数据结构类使用.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第五章 异常和多线程.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第七章 Java的图形与用户界面.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第2章 数字图像处理基础.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第1章 绪论(冈萨雷斯 Rafael C.Gonzalez、Richard E. Woods).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.1 人眼视觉感知基础(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.2 图像数字化(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.3 图像插值(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.4 像素间关系.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第3章 灰度变换与空间滤波.pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)灰度变换与空间滤波 3.1 邻域 邻接、连接 区域、边界 距离.pdf