基本操作的算法描述 Status Push(SqStack&s, SElemType e插入元素e为新 的栈顶元素 f(Stop- s, base>=s. stac size)栈满,追加存储空间 o s base= sElemType*)remalloc(S.stacksize+STACKINCR EMENT)*sizeof (ELlem Type)); ●if( s, base)exit( OVERFLOW);∥|储分配失败 e Stop=Sbase+S.stacksize .s.stacksize+=STACKINCREMENT, ●*stop++=e; return oK;}∥PUSH 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 基本操作的算法描述 ⚫ Status Push (SqStack &s, SElemType e){/插入元素e为新 的栈顶元素 ⚫ If (S.top-S.base>=S.stacksize){栈满，追加存储空间 ⚫ S.base=(SElemType*)remalloc(S.stacksize+STACKINCR EMENT) *sizeof（ELlemType））; ⚫ if (!S.base) exit (OVERFLOW);//存储分配失败 ⚫ S.top=S.base+S.stacksize; ⚫ S.stacksize+=STACKINCREMENT;} ⚫ *S.top++=e; return OK;} //PUSH
基本操作的算法描述 e Status Pop sqstack &s, SElemType e)ll 若栈不空,则删除S的栈顶元素,用e返回其值, 并返回OK;否则返回 ERROR e If(stop==S base return ERROR e=*-S top ● return oK;}∥Pop 北京邮电大学自动化学院
北京邮电大学自动化学院 17 基本操作的算法描述 ⚫ Status Pop (SqStack &s, SElemType e){// ⚫若栈不空，则删除S的栈顶元素，用e返回其值， 并返回OK；否则返回ERROR ⚫ If (S.top==S.base ）return ERROR; ⚫ e=*--S.top; ⚫ return OK;} //Pop
2、链栈 栈的链式存储结构称为链栈,它是运算受限的单链表,插 入和删除操作仅限制在表头位置上进行。由于只能在链表 头部进行操作,故链表没有必要像单链表那样附加头结 点。栈顶指针就是链表的头指针。 ●链栈的类型说明如下: typedef struct stacknode i ● datatype data o struct stacknode * next fstacknode; 北京邮电大学自动化学院
北京邮电大学自动化学院 18 ⚫ 栈的链式存储结构称为链栈，它是运算受限的单链表，插 入和删除操作仅限制在表头位置上进行。由于只能在链表 头部进行操作，故链表没有必要像单链表那样附加头结 点。栈顶指针就是链表的头指针。 2、 链栈 ⚫ 链栈的类型说明如下： ⚫ typedef struct stacknode { ⚫datatype data ⚫struct stacknode *next ⚫}stacknode;
栈的链接表示一链式栈 ●链式栈的特点: ●链式栈无栈满问题 ●空间可扩充 ●插入与删除仅在栈顶处执行 链式栈的栈顶在链头 ●适合于多栈操作 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 ⚫ 链式栈的特点： 栈的链接表示 — 链式栈 ⚫ 链式栈无栈满问题 ⚫ 空间可扩充 ⚫ 插入与删除仅在栈顶处执行 ⚫ 链式栈的栈顶在链头 ⚫ 适合于多栈操作
32栈的应用举例 例1:数制转换十进制数N和其他d进制数的转换是计算机实 现计算的基本问题。其中一个简单算法基于下列原理 N=( n diy d)×d+ nmod d ·例如:(1348)10=(2504)8,其运算过程如下: N ndiy 8 nmod 计算顺序 ●1348 168 ●168 21 ●21 4052 ●2 20 输出顺序 北京邮电大学自动化学院
北京邮电大学自动化学院 20 计 算 顺 序 输 出 顺 序 ⚫ 例1: 数制转换 十进制数N和其他d进制数的转换是计算机实 现计算的基本问题。其中一个简单算法基于下列原理: 3.2 栈的应用举例 ⚫ 例如：（1348)10 = (2504)8 ，其运算过程如下： ⚫ N=(N div d)d+N mod d ⚫ N N div 8 N mod ⚫ 1348 168 4 ⚫ 168 21 0 ⚫ 21 2 5 ⚫ 2 0 2