数据结构课件(栈和队列)

《数据结构课件(栈和队列)》由会员分享，可在线阅读，更多相关《数据结构课件(栈和队列)（65页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 1数据结构第三章 栈和队列*第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3

2、队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 2第三章 栈和队列3.1 栈栈和队列也是线性表，只不过是操作受限的线性表。 栈是限定在表尾进行插入或删除操作的线性表。表尾 端称栈顶，表头端称栈底。如图。an.a2 a1栈底栈顶出栈进栈栈顶（TOP）-允许插入和删除的一端。栈底(bottom)-不允许插入和删除的一端。空栈-表中没有元素。 进栈-最先插入的元素放在栈的底部。 退栈-最后插入的元素最先退栈。 所以栈又称为后进先出的线性表（ LIFO表，Last In First Out）第三章第三章 3.1 栈 3.1.1栈的

3、类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 33.1 栈3.1.1 栈的类型定义ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端 为栈顶，a1 端为栈底。 基本操作： InitStack( /存储空间的基址，数据元 素的

4、数据类型约定为SElemType SElemType * top; /表示栈顶，如果top=base ，表示空栈 int stacksize; /当前分配的存储容量，以 sizeof(ElemType) 为单位 SqStack 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 63 2 1 0Top=b

5、ase 空栈TopbaseA3 2 1 0TOPA进栈base3 2 1 0DCBAB、C、D依次进栈TOPbase3 2 1 0BATOPD、C依次退栈base3 2 1 0B、A退栈baseTOP3.1 栈第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 73.1.2 栈的表示和实现-顺序表示顺序栈

6、基本操作的实现Status InitStack(SqStack if(!S.base)exit(OVERFLOW); S.top=S.base; /置栈S为空栈 S.stacksize=STACK_INIT_SIZE; return OK; /InitStack 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊

7、的线性表 83.1.2 栈的表示和实现-顺序表示顺序栈基本操作的实现Status GetTop(SqStack S,SElemType e=*(S.top-1); return OK; /GetTop 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 93.1.2 栈的表示和实现-顺序表示顺序栈基本操作

8、的实现Status Push(SqStack if(!S.base)exit(OVERFLOW); /存储分配失败 S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; /Push第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 103.1.2 栈的表示和

9、实现-顺序表示顺序栈基本操作的实现Status Pop(SqStack e=*-S.top; return OK; /Pop 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 113.1.2 栈的表示和实现-顺序表示顺序栈基本操作的实现Status DestroyStack(SqStack free(S

10、.base); S.base=NULL; S.top= NULL; return OK; /DestroyStack Status ClearStack(SqStack return OK; /ClearStack 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 123.1.2 栈的表示和实现-顺序表

11、示顺序栈基本操作的实现Status StackEmpty(SqStack S) /如果栈为空栈，则返回TRUE，否则返回 FALSE if(S.top=S.base)return TRUE; else return FALSE; /StackEmpty Status StackLength(SqStack S) /返回栈S的长度 return S.top-S.base; /StackLength第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.

12、2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 133.1.2 栈的表示和实现-顺序表示顺序栈基本操作的实现Status StackTraverse(SqStack S, Status (*visit)(SElemType e) /从栈底到栈顶依次对栈中每个元素调用visit函数，如 果visit失败，则操作失败 if(S.top=S.base)return ERROR; for(i=0;i S.top-S.base;i+) if(visit(S.basei)=ERROR) return ERROR

13、; return OK; /StackTraverse 第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 143.1.2 栈的表示和实现- 链接表示链栈的表示struct Node/* 单链表结点结构 */ ElemType info;struct Node *link; struct LinkStac

14、k/* 链栈类型定义 */ struct Node *top;/* 指向栈顶结点 */LinkStack, *PLinkStack;bat cat eat mat headtopbottom第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序栈 3.1.3链栈 3. 2 栈的应 用举例 3.2.1数制转 换 3.2.2表达式 求值 3.2.3汉诺塔 问题 3.3队列 3.3.2顺序队 列 3.3.3队列的 基本操作 3.3.4队列的 类型定义 3.3.5链队列 的定义 3.3.6循环队 列 3.4几种特殊 的线性表 153.1.2 栈的表示和实现- 链接表示链栈基本操作的实现PL

15、inkStack createEmptyStack_link( ) /创建一个空栈PLinkStack plstack;plstack = (struct LinkStack *)malloc( sizeof(struct LinkStack);if (plstack != NULL) plstack-top = NULL; else printf(“Out of space! n“); return plstack; DataType top_link( PLinkStack plstack ) /* 对非空栈求栈顶元素 */ return plstack-top-info；第三章第三章 3.1 栈 3.1.1栈的类 型定义 3.1.2顺序