数据结构 教学课件 ppt 作者 戴敏 chapter3

,数据结构 (DATA STRUCTURE),2,第三章 栈和队列,栈 ( Stack ) 栈的应用 递归 队列 ( Queue ),3,3.1 栈 ( Stack ),1）栈的定义 限定在表尾进行插入和删除操作的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO),4,ADT Stack 数据对象: D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitStack ( &S) : 栈的初始化 DestoryStack(&S) : 销毁栈S Push ( &S, e) :进栈 Pop (&S ) : 出栈 GetTop (S ): 取栈顶元素 IsEmpty (S): 判栈空否 ,2) 栈的抽象数据类型,5,1) 存储特点： 利用一组地址连续的存储单元依次存放栈元素 附设指针top指示栈顶元素在顺序栈中的位置 2) 顺序栈的表示 # define StackInitSize 100; /存储空间初始分配量 typedef int StackElementType； typedef struct StackElementType dataStackInitSize；/*栈存储空间 用一个预设的长度的一维数组来实现 */ int top； /* 栈顶指针 */ SeqStack；,3.1.1 栈的顺序存储 顺序栈,6,进栈（入栈） 分析 首先判断栈满？ （栈满:s-top = StackInitSize ) 若栈满，则不能进栈操作 栈顶指针加1 s-top+; 数据元素入栈 s-datas-top = x;,3) 基本操作的实现,7,算法 void Push(SeqStack *s, StackElementType x) if (s-top = StackInitSize) printf(“栈满! 栈发生上溢，程序运行终止!n“); exit(0); else s-top+; /* 栈顶指针加1，指向新的栈顶 */ s-datas-top = x; /* 将数据元素x压入栈 */ return; ,8,分析 首先判断栈空？（栈空:(s-top = -1 ) 数据元素出栈 temp=s-datas-top 栈顶指针减1 s-top- 算法 StackElementType Pop(SeqStack *s) StackElementType temp; if(IsEmpty(s) printf(“栈空！栈发生下溢，程序运行终止!n“); exit(0); else temp=s-datas-top; s-top-; return temp; ,出栈（退栈）,9,顺序栈演示：,10,多栈处理 栈浮动技术,n 个栈共享一个数组空间Vm 设立栈顶指针数组 t n+1 和栈底指针数组 b n+1，ti和bi分别指示第 i 个栈的栈顶与栈底 各栈初始分配空间 s = m / n 指针初始值 t0 = b0 = -1 bn = m-1 ti = bi = bi-1 + s, i = 1, 2, , n-1,11,12,3.1.2 栈的链式存储 链式栈,1）存储特点 是一种特殊形式的单链表（无表头结点；插入、删除操作限定在表头端进行） 链式栈无栈满问题，空间可扩充,13,2）链式栈的表示：同单链表 typedef struct node SElemtype data; struct node *next; linkstack;,14, 进栈（入栈） 分析 首先申请一个结点空间 (用 p 指向该结点) 若链栈不为空，将*p 插入链表的第一个结点 之前： p-next =top; top=p; 否则：p-next =NULL; top=p;,3）基本运算的实现,15,分析 首先判断栈空？ （栈空:top=NULL) 若不空，判断 *top是否为栈中最后一个元素 如不是，则将*top从链表中删除： top=top-next 否则，令top=NULL 释放栈顶元素空间;, 出栈（退栈）,16,3.1.3 栈的应用举例,例1：简单应用：数制转换问题 问题：将十进制数N转换为r进制的数，其转换方法利用辗转相除法。 分析：所转换的r 进制数按低位到高位的顺序产生，而通常的输出是从高位到低位的，恰好与计算过程相反,17,例2 中缀表达式求值,问题：根据算符优先法对表达式求值,所讨论的算术运算符包括：+ 、- 、*、/、%、(乘方)和括号()。运算规则为： 运算符的优先级为: () 、/、% +、-； 有括号时先算括号内的，后算括号外的，多层括号由内向外进行； 乘方连续出现时先算最右面的；,18,分析：表达式作为一个串，如表达式“3+2*4-5”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能有更高的运算 需要两个栈：对象栈OPND和算符栈OPTR; 自左至右扫描表达式, 若当前字符是运算对象，入OPND栈; 对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈一运算符进行运算，并将其运算结果入OPND栈，继续处理当前字符，直到遇到结束符。,19,例3 栈与递归,问题：栈的一个重要应用是在程序设计语言中实现递归过程。 n! = 分析：根据定义可以很自然的写出相应的递归函数 int fact (int n) if (n=0) return 1; else return ( n*fact(n-1); ,1 n=0 /*递归终止条件*/ n*(n-1)! n0 /*递归步骤*/,20,递归的概念,递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,21,定义是递归的,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1); ,例如，阶乘函数,22,数据结构是递归的,搜索链表最后一个结点并打印其数值 void Find ( LinkList L ) if ( Lnext = NULL ) printf ( Ldata); else Find ( Lnext ); ,例如，单链表结构,23,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,24,递归过程与递归工作栈,递归过程在实现时，需要自己调用自己。 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序 因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。,25,3.2 队列 (Queue),1) 定义 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out),26,ADT Queue 数据对象: D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitQueue ( &Q) : 初始化队列 DestoryQueue (&Q) : 销毁队列 EnQueue (&Q, e) :进队列 DeQueue (Q, &e): 出队列 GetHead (Q, &e): 取队头元素值 QueueEmpty (S): 判队列空否 ,2）队列的抽象数据类型,27,3.2.1 队列的链接存储链式队列,1) 存储特点： 队头在链头，队尾在链尾。 设置队头、队尾指针分别保存队头、队尾地址,28,2) 链队列表示：,结点类型： typedef struct Qnode QElemtype data; struct QNode *next; 定义一链队列 Qnode,*Queueptr; LinkQueue Q; 链队列类型 队头结点： typedef struct Q.front-next Queueptr front; 队尾结点： Q.rear Queueptr rear; 队尾结点数据： LinkQueue; Q.rear-next,29,3) 基本操作的实现, 入队,Queueptr EnQueue (LinkQueue Q, Qelemtype x) p=(Queueptr) malloc(sizeof(QNode); /*申请结点空间*/ if (!p) exit(overflow); p-data=x; p-next=NULL; Q.rear-next=p; Q.rear=p; return Q; ,30, 出队,Queueptr DeQueue (LinkQueue Q, Qelemtype ,31,存储特点： 利用地址连续的存储单元依次存放队列各元素。 设置两个指示器 front, rear 分别指示队头、队尾元素的下标,3.2.2 队列的顺序存储循环队列,32,存在问题: “假溢出” 解决方法: 把队列存储空间看作首尾相连的环,33,存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从 MaxSize -1直接进到0，可用C语言的取模(余数)运算实现。,1）循环队列 (Circular Queue),出队:队头指针进1 front = (front + 1) % MaxSize; 入队:队尾指针进1 rear = (rear + 1) % MaxSize; 队列初始化：front=rear= 0;,34,队空条件： 队满条件：,(rear + 1) % MaxSize = front ;,front = rear ;,35,2）循环队列数据类型描述,typedef struct QElemtyope *base; /dataMAXSIZE数据的存储区 int front; /队头指针,指向对头元素 int rear; /队尾指针,指向对尾元素的下一个位置 SqQueue; /*循环队列*/,36,3）基本操作的实现, 初始化（置空队）,37,SqQueue Init_SqQueue () SqQueue Q; Q.base=(QElemtype*)malloc(Maxsize * sizeof(QElemtype); /申请存储空间 if ( !Q.base ) exit (overflow); Q.front = Q.rear = 0; /队列置空 return Q; ,算法,38, 入队（插入）,39,SqQueue EnSqQueue (SqQueue Q , QElemtype x) if (Q.rear + 1) % MaxSize = Q.front) return ERROR; /*队满