第 4 章 数据结构.ppt

《第 4 章 数据结构.ppt》由会员分享，可在线阅读，更多相关《第 4 章 数据结构.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,第 1 章 数据结构,1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 内部排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,一叠书或一叠盘子。,栈顶,栈底,a1,栈s=(a1,a2,，an),a2,an-1,an,一种操作受限的线性表,只允许在表的一端进行插入和删除,1.栈的定义,定义：只允许在线性表的一端进行插入和删除的线性表。,与栈有关的相关术语：,1.3栈和队列,(1)栈顶： 允许插入与删除的一端称为栈顶(2)栈底： 不允许插入与删除的一端称为栈底(3)入栈：栈的插入操作(往栈中插入一个元素)(

2、4)出栈：栈的删除操作(从栈中删除一个元素)(5)栈空： top=0(6)栈满： top=m(m为栈最大容量),进栈,出栈,栈顶,栈底,假设栈：s=(a1,a2,，an),1.3.1 栈,栈空：top=-1,栈示意图：,修改栈的原则：(考点)先进后出(FILO, First In Last Out)或后进先出(LIFO),栈顶元素总是最后入栈，而最先出栈的栈底元素总是最先入栈，而最后出栈的,堆栈操作,出栈元素顺序： B C D A,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。链式

3、存储结构：用于收集计算机存储器中所有空闲存储空间,来保存自栈底到栈顶的数据元素。,顺序栈：顺序存储结构的栈称为顺序栈。链栈：链式存储结构栈称为链栈。,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,顺序栈实现：一维数组dataM,注意：数组是倒过来图示的。故，top指向的是其箭头上面的存储空间,顺序栈实现：一维数组dataM,栈顶指针并不一定是指针变量，也可以是下标变量,#define SIZE 50typedef struct char dataSIZE; int t

4、op; SeqStack;,/*置栈空*/ void InitStack（SeqStack *S） S-top=0; ,/* 进栈*/void Push（SeqStack *S，char x） if (StackFull(S) printf(“Stack overflow”); /上溢，退出运行 exit(0) ; S-dataS-top=x;/将x入栈 S-top=S-top+1; /栈顶指针加1 ,/* 出栈*/char Pop（SeqStack *S） if(StackEmpty(S) printf(“Stack underflow”); /下溢，退出运行 exit(0); S-top=

5、S-top-1; /将栈顶指针减1 return S-dataS-top; /栈顶元素返回 ,top=0,栈空,A,top=1,假设：调用两次Push函数 Push( S, A);Push(S, B);,top=2,B,假设：调用一次Pop函数 Pop( S);,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算： 入栈、出栈与读栈顶元素,(1)入栈,新元素插入到栈顶指针指向位置栈顶指针top加1,步骤：,注意: 栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误.,栈空：top=0,思考：当栈空条件为：top=

6、-1时，入栈步骤,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算： 入栈、出栈与读栈顶元素,(2)出栈,步骤：,栈顶指针top减1栈顶元素赋给一个指定的变量,栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算： 入栈、出栈与读栈顶元素,(3)读栈顶元素,概念：将栈顶元素赋给一个指定变量,注意：不删除栈顶元素，栈顶指针不会改变,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈

7、的基本运算：,3)栈的典型应用,进制的转换,139,10001011,(139)10=(10001011)2,除余倒序法,(139)10（？）2,139,除余倒序法,(139)10（？）2,1,1,0,1,0,0,0,1,余数栈,定义：指允许在一端插入,而在另一端进行删除的线性表。,与队列有关的相关术语:(1)队尾：允许插入的一端称为队尾。 rear队尾指针，指向队尾元素的下一个位置(2)队头：允许进行删除的一端称为队头。 front队头指针，指向队头元素。(3)入队列：队列插入操作(进队列)(4)出队列：队列的删除操作(退队列)(5)空队列：队列中无数据元素,1.3栈和队列,1.3.2 队列

8、,定义：指允许在一端插入,而在另一端进行删除的线性表。,队列结构示意图：队列Q=(a1，a2, , an ),1.3栈和队列,1.3.2 队列,队列修改原则：先进先出(FIFO)或后进后出(LILO),队头元素总是最先进队列的,也总是最先出队列队尾元素总是最后进队列,也是最后出队列,新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,2.链队列: 用链表表示的队列。,Q.front,Q.rear,具有n个元素的队列,structqueueNodei

9、ntdata;/存放数据元素structqueueNode*next;/指向下一个结点;structqueuestructqueueNode*front;structqueueNode*rear;struct queue *Q;,void InitQueue(structqueue *q) /初始化队列 structqueueNode*node; node=(structqueueNode*)malloc(sizeof(structqueueNode); node-next=NULL; q-front=node; q-rear=node;,node,q.front,q.rear,带头结点的空队

10、列,/入队列voidAddQueue(structqueue*q,inte)structqueueNode*node;node=(structqueueNode*)malloc(sizeof(structqueueNode);node-data=e;node-next=NULL;q-rear-next=node;q-rear=node;,q.front,q.rear,1,又调用一次,node,/入队列voidAddQueue(structqueue*q,inte)structqueueNode*node;node=(structqueueNode*)malloc(sizeof(structqu

11、eueNode);node-data=e;node-next=NULL;q-rear-next=node;q-rear=node;,q.front,q.rear,1,又调用一次,2,node,node,/出队int DelQueue (struct Queue *q) int x; struct QueueNode *p; p=q-front-next; q-front-next=p-next; if(p-next=NULL) q-rear=q-front; / 防止尾指针丢失 x=p-data; free(p); return x;,q.front,q.rear,1,2,p,x,1,又调用一

12、次,if不成立,/出队int DelQueue (struct Queue *q) int x; struct QueueNode *p; p=q-front-next; q-front-next=p-next; if(p-next=NULL) q-rear=q-front; / 防止尾指针丢失 x=p-data; free(p); return x;,q.front,q.rear,2,x,1,又调用一次,p,if成立,2,新元素入队时插在头结点之后,修改rear指针删除一个元素时,修改front指针。,Q.front,Q.rear,空队列,Q.front,Q.rear,a1入队列,新元素入队

13、时插在头结点之后,修改rear指针删除一个元素时,修改front指针。,Q.front,Q.rear,队列中有两个数据元素,出队列,删除唯一元素时, front与rear回缩到头结点，为空队列。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,3.顺序队列,定义：队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。,约定：初始化队列令front=rear=0,入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。,在非空队列中头指针front始终指

14、向队列头元素尾指针指向队尾元素的下一个位置,2.链队列: 用链表表示的队列。,举例：顺序队列头尾指针变化情况,A,B,C,D,Q.front,ABCD相继入队,Q.front,空对列,front=rear=0,举例：顺序队列头尾指针变化情况,A,B,C,D,Q.front,出队,Q.front,空队列,front=rear=0,Q.front,Q.front,Q.front,E,入队,F,队未满,却不能再入队，假溢出,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,2.链队列: 用链表表示的队列。,3.顺序队列,缺点：有“假溢出”现象，为克服这点，引入循

15、环队列。,4.循环队列,定义： 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。,0,4,3,2,1,Q.front,对应为：,A,B,C,D,入队,A,B,C,D,出队,Q.front,Q.front,0,4,3,2,1,对应为：,C,D,入队,C,D,出队,Q.front,E,E,队尾指针指出数组外,队未满,却不能再入队，假溢出,0,若用循环队列：,即,问题是如何让rear（等于4）加1之后能够回退到0,方法一： if(Q.rear+1=5) Q.rear=0; else Q.rear=Q.rear+1;,方法二：利用“求余运算Q.rear=(Q.rear+1)%5；,0

16、,4,3,2,1,对应为：,C,D,入队,C,D,出队,Q.front,E,E,F,F,继续入队,G,G,队满：Q.rear=Q.front,但是,考虑出队情况,队空：Q.rear=Q.front,因此，一般循环队列少用一个存储空间;队满条件就变为：(Q.rear+1)%M=Q.front,0,4,3,2,1,C,D,E,F,0,4,3,2,1,C,D,E,F,G,队满,指针基本运算空与满上溢与下溢,栈 队列顺序栈 顺序队列 循环队列,top:指向栈顶下一个位置,front:队头元素rear: 队尾元素的下一个位置,同左,入栈:top加1出栈:top减1,入队: 队尾rear加1 出队:队头f

17、ront加1,入队: (rear+1)%m 出队:(front+1)%m,栈空:top=0栈满:top=m,队空: front= rear=0 队满: rear=m,front= rear(rear+1)%m=front,栈顶已满,不能入栈栈空,不能退栈,上溢:队满,不能入队下溢:队空,不能退队,总结,m为存储空间长度,练习1一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（ ）。A. 1，2，3，4 B. 4，3，2，1 C. 1，3，4，2 D. 4，1，2，3,2. 一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列。 A. 31245 B.41325 C.23

18、415 D.142533. 假定利用数组aN顺序存储一个栈，用top表示栈顶指针， top= =-1表示栈空，并已知栈未满，当元素x进栈时所执行的操 作为（）A. a-top=x B. atop-=x C. a+top=x D .atop+=x,top=-1栈空：先top1，再x赋值过来 top=0栈空：x先赋值过来，再top+1,4.一个队列的入队序列是1，2，3，4，则队列的输出序列是（）A.4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D .3，2，4，15.从一个顺序循环队列中删除元素时，首先需要（）A. 前移队首指针 B. 后移队首指针C. 取出队首指针所指位置上的元素

19、 D . 取出队尾指针所指位置上的元素6.假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队列空的条件为（） A.front+1= =rear B.rear+1= =front C. front= =0 D . front= =rear,7.假定一个顺序循环队列存储于数组aN中，其队首和队尾指针分别用front和rear表示，则判断队列满的条件为（）A. （rear-1）%N= =front B. （rear+1）%N= =front C. （front-1）%N= =rear D . （front+1）%N= =rear5,8.线性表、栈和队列都是_结构，对于栈只能

20、在_插入和删除元素；对于队列只能在_插入元素，在_删除元素。,线性、栈顶、队尾、队头,9.设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push ,pop, push ,push后，对应的输出序列是_。,2,3,10. 设元素1，2，3，4，5依次进栈，若要在输出端得到序列 34251，则应进行的操作序列为push(S,1),push(S,2), _， pop(S)，push(S,4)，pop(S)，_， _, pop(S)， pop(S)。,push(S,3),pop(S),push(S,5),11.在一个具有n个存储单元的循环队列中，当队列满时共有_ 个元素。,n-1,12.栈又称为_表，队列又称为_表。,后进先出、先进先出,