资源预览内容
第1页 / 共708页
第2页 / 共708页
第3页 / 共708页
第4页 / 共708页
第5页 / 共708页
第6页 / 共708页
第7页 / 共708页
第8页 / 共708页
第9页 / 共708页
第10页 / 共708页
亲,该文档总共708页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第3章 栈和队列,栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。 栈在计算机的实现有多种方式: 硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快; 软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种。 本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。,3.1 栈,3.1.1 栈的基本概念,1 栈的概念 栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。 栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。 栈底(Bottom):是固定端,又称为表头。 空栈:当表中没有元素时称为空栈。,设栈S=(a1,a2,an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。 栈中元素按a1,a2,an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。,2 栈的抽象数据类型定义 ADT Stack 数据对象:D = ai|aiElemSet, i=1,2,n,n0 数据关系:R =|ai-1,aiD, i=2,3,n 基本操作:初始化、进栈、出栈、取栈顶元素等 ADT Stack,栈的顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储栈。根据数组是否可以根据需要增大,又可分为静态顺序栈和动态顺序栈。 静态顺序栈实现简单,但不能根据需要增大栈的存储空间; 动态顺序栈可以根据需要增大栈的存储空间,但实现稍为复杂。,3.1.2 栈的顺序存储表示,采用动态一维数组来存储栈。所谓动态,指的是栈的大小可以根据需要增加。 用bottom表示栈底指针,栈底固定不变的;栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。 用top=bottom作为栈空的标记,每次top指向栈顶数组中的下一个存储位置。 结点进栈:首先将数据元素保存到栈顶(top所指的当前位置),然后执行top加1,使top指向栈顶的下一个存储位置;,3.1.2.1 栈的动态顺序存储表示, 结点出栈:首先执行top减1,使top指向栈顶元素的存储位置,然后将栈顶元素取出。 图3-2是一个动态栈的变化示意图。,基本操作的实现 1 栈的类型定义 #define STACK_SIZE 100 /* 栈初始向量大小 */ #define STACKINCREMENT 10 /* 存储空间分配增量 */ #typedef int ElemType ; typedef struct sqstack ElemType *bottom; /* 栈不存在时值为NULL */ ElemType *top; /* 栈顶指针 */ int stacksize ; /* 当前已分配空间,以元素为单位 */ SqStack ;,2 栈的初始化 Status Init_Stack(void) SqStack S ; S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType); if (! S.bottom) return ERROR; S.top=S.bottom ; /* 栈空时栈顶和栈底指针相同 */ S. stacksize=STACK_SIZE; return OK ; ,3 压栈(元素进栈) Status push(SqStack S , ElemType e) if (S.top-S.bottom=S. stacksize-1) S.bottom=(ElemType *)realloc(S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType); /* 栈满,追加存储空间 */ if (! S.bottom) return ERROR; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; *S.top=e; S.top+ ; /* 栈顶指针加1,e成为新的栈顶 */ return OK; ,4 弹栈(元素出栈) Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ if ( S.top= S.bottom ) return ERROR ; /* 栈空,返回失败标志 */ S.top- ; e=*S. top ; return OK ; ,采用静态一维数组来存储栈。 栈底固定不变的,而栈顶则随着进栈和退栈操作变化的, 栈底固定不变的;栈顶则随着进栈和退栈操作而变化,用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。 用top=0表示栈空的初始状态,每次top指向栈顶在数组中的存储位置。 结点进栈:首先执行top加1,使top指向新的栈顶位置,然后将数据元素保存到栈顶(top所指的当前位置)。,3.1.2.2 栈的静态顺序存储表示, 结点出栈:首先把top指向的栈顶元素取出,然后执行top减1,使top指向新的栈顶位置。 若栈的数组有Maxsize个元素,则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。,基本操作的实现 1 栈的类型定义 # define MAX_STACK_SIZE 100 /* 栈向量大小 */ # typedef int ElemType ; typedef struct sqstack ElemType stack_arrayMAX_STACK_SIZE ; int top; SqStack ;,2 栈的初始化 SqStack Init_Stack(void) SqStack S ; S.bottom=S.top=0 ; return(S) ; ,3 压栈(元素进栈) Status push(SqStack S , ElemType e) /* 使数据元素e进栈成为新的栈顶 */ if (S.top=MAX_STACK_SIZE-1) return ERROR; /* 栈满,返回错误标志 */ S.top+ ; /* 栈顶指针加1 */ S.stack_arrayS.top=e ; /* e成为新的栈顶 */ return OK; /* 压栈成功 */ ,4 弹栈(元素出栈) Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ if ( S.top=0 ) return ERROR ; /* 栈空,返回错误标志 */ *e=S.stack_arrayS.top ; S.top- ; return OK ; ,当栈满时做进栈运算必定产生空间溢出,简称“上溢”。上溢是一种出错状态,应设法避免。 当栈空时做退栈运算也将产生溢出,简称“下溢”。下溢则可能是正常现象,因为栈在使用时,其初态或终态都是空栈,所以下溢常用来作为控制转移的条件。,1 栈的链式表示 栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。,3.1.3 栈的链式存储表示,链栈的结点类型说明如下: typedef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ;,2 链栈基本操作的实现 (1) 栈的初始化 Stack_Node *Init_Link_Stack(void) Stack_Node *top ; top=(Stack_Node *)malloc(sizeof(Stack_Node ) ; top-next=NULL ; return(top) ; ,(2) 压栈(元素进栈) Status push(Stack_Node *top , ElemType e) Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node) ; if (!p) return ERROR; /* 申请新结点失败,返回错误标志 */ p-data=e ; p-next=top-next ; top-next=p ; /* 钩链 */ return OK; ,(3) 弹栈(元素出栈) Status pop(Stack_Node *top , ElemType *e) /* 将栈顶元素出栈 */ Stack_Node *p ; ElemType e ; if (top-next=NULL ) return ERROR ; /* 栈空,返回错误标志 */ p=top-next ; e=p-data ; /* 取栈顶元素 */ top-next=p-next ; /* 修改栈顶指针 */ free(p) ; return OK ; ,3.2 栈的应用,由于栈具有的“后进先出”的固有特性,因此,栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。,3.2.1 数制转换,十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。 转换法则:该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d 其中:div为整除运算,mod为求余运算 例如 (1348)10= (2504)8,其运算过程如下: n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,采用静态顺序栈方式实现 void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ SqStack S ; int k, *e ; S=Init_Stack(); while (n0) k=n%d ; push(S , k) ; n=n/d ; /* 求出所有的余数,进栈 */ while (S.top!=0) /* 栈不空时出栈,输出 */ pop(S, e) ; printf(“%1d” , *e) ; ,3.2.2 括号匹配问题,在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个表达式中的括号是否相匹配? 匹配思想:从左至右扫描一个字符串(或表达式),则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶删除该左括号。 算法思想:设置一个栈,当读到左括号时,左括号进栈。当读到右括号时,则从栈中弹出一个元素,与读到的左括号进行匹配,若匹配成功,继续读入;否则匹配失败,返回FLASE。,算法描述 #define TRUE 0 #define FLASE -1 SqStack S ; S=Init_Stack() ; /*堆栈初始化*/ int Match_Brackets( ) char ch , x ; scanf(“%c” , while (asc(ch)!=13), if (ch=()|(ch=) push(S , ch) ; else if (ch=) x=pop(S)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号