中国高校课件下载中心 》 教学资源 》 大学文库

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

文档信息
资源类别:文库
文档格式:PPT
文档页数:60
文件大小:784KB
团购合买:点击进入团购
内容简介
山东第一医科大学(泰山医学院):《数据结构》课程教学资源(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); }

刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档