第 4 章 数据结构.ppt

,第 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)入栈：栈的插入操作(往栈中插入一个元素)(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)栈的两种存储结构,顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。链式存储结构：用于收集计算机存储器中所有空闲存储空间,来保存自栈底到栈顶的数据元素。,顺序栈：顺序存储结构的栈称为顺序栈。链栈：链式存储结构栈称为链栈。,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,顺序栈实现：一维数组dataM,注意：数组是倒过来图示的。故，top指向的是其箭头上面的存储空间,顺序栈实现：一维数组dataM,栈顶指针并不一定是指针变量，也可以是下标变量,#define SIZE 50typedef struct char dataSIZE; int top; 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=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=-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)顺序栈的基本运算：,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 队列,定义：指允许在一端插入,而在另一端进行删除的线性表。,队列结构示意图：队列Q=(a1，a2, , an ),1.3栈和队列,1.3.2 队列,队列修改原则：先进先出(FIFO)或后进后出(LILO),队头元素总是最先进队列的,也总是最先出队列队尾元素总是最后进队列,也是最后出队列,新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,2.链队列: 用链表表示的队列。,Q.front,Q.rear,···,具有n个元素的队列,struct queueNode  int data;/存放数据元素   struct queueNode * next;/指向下一个结点;struct queue   struct queueNode * front;    struct queueNode * rear;struct queue *Q;,void InitQueue(struct queue *q)   /初始化队列  struct queueNode * node;  node=(struct queueNode *)malloc(sizeof(struct queueNode );  node->next=NULL;  q->front=node;  q->rear=node;,node,q.front,q.rear,带头结点的空队列,/入队列void AddQueue(struct queue * q, int e)    struct queueNode * node;    node=(struct queueNode *)malloc(sizeof(struct queueNode );    node->data=e;    node->next=NULL;    q->rear->next=node;    q->rear=node;   ,q.front,q.rear,1,又调用一次,node,/入队列void AddQueue(struct queue * q, int e)    struct queueNode * node;    node=(struct queueNode *)malloc(sizeof(struct queueNode );    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,又调用一次,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入队列,新元素入队时插在头结点之后,修改rear指针删除一个元素时,修改front指针。,Q.front,Q.rear,队列中有两个数据元素,出队列,删除唯一元素时, front与rear回缩到头结点，为空队列。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,3.顺序队列,定义：队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。,约定：初始化队列令front=rear=0,入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。,在非空队列中头指针front始终指向队列头元素尾指针指向队尾元素的下一个位置,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.顺序队列,缺点：有“假溢出”现象，为克服这点，引入循环队列。,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,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 出队:队头front加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.23415 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. 取出队首指针所指位置上的元素 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.线性表、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素，在_删除元素。,线性、栈顶、队尾、队头,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.栈又称为_表，队列又称为_表。,后进先出、先进先出,