第三章栈和队列【数据结构与算法】【精致版】-阿里云开发者社区

前言

2023-11-2 22:12:24

以下内容源自《【数据结构与算法】【精致版】》

仅供学习交流使用

第 3 章栈和队列

第2章介绍了线性表的概念,从数据结构上看,栈和队列也是线性表,只不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、在另一端进行删除操作。因而,栈和队列也可以被称为操作受限的线性表。从数据类型的角度来看，栈与队列是与线性表不同的抽象数据结构。

3.1 应用实例

应用实例一迷宫求解问题

这是实验心理学中的一个经典问题，心理学家用一个无顶盖的大盒子做成“迷宫”从然后把一只老鼠从入口处赶进迷宫。迷宫中设置了很多隔断，对老鼠的前进方向构成多处障碍，在迷宫的唯一出口处放置了一块奶酪,吸引老鼠寻找正确的通路以到达出口。

可以用一个mxn的方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计

一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得到没有通路的结论。

计算机解迷宫时,通常是采用“穷举求解”的方法,即从入口出发,沿某方向向前探索,若能走通则继续往前走;否则沿原路返回,换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然要用具有后进先出特性的栈来保存从入口到当前位置的路径。

应用实例二“马”踏棋盘问题

将棋子“马”随机地放在国际象棋8x8棋盘Board[8][8]的某个方格中,“马”按走棋规则进行移动,要求每个方格只进入一次,走遍棋盘上所有的64个方格。编写（非）递归程序,求出“马” 的行走路线,并按求出的行走路线将数字1,2,…,64依次填入一个8x8的方阵并输出。

求解时可采用栈的数据结构,即将“马”的行走顺序压人栈中。每次在多个可走的位置中选择其中一个进行试探,其余未曾试探过的可走位置必须用适当的结构妥善管理,以备试探失败时的“回溯”(悔棋)使用。

以上实例的分析与实现将在3.4节详细介绍。

3.2栈

3.2.1 栈的概念及运算

栈(stack)是一种只允许在一端进行插人和删除操作的线性表,它是一
种操作受限的线性表。

在表中允许进行插入和删除的一端称为“栈顶”(top),另一端称为“栈底”(bottom)。

栈的插入操作通常称为“入栈”或“进栈”(push)，

而栈的删除操作则称为“出栈”或“退栈”(pop)。

当栈中无数据元素时,称为“空栈”。

栈具有后进先出的特性,因此又称为“后进先出”(Last In First Out,LIFO)表。

栈的示意图

栈的基本运算有以下几种。
① InitStack(S) 初始化:初始化一个新的栈。
② Empy(S )栈的非空判断:若栈S不空,则返回TRUE;否则,返回FALSE。
③ Push(S.x) 入楼:在栈S的顶部插入元素x,若栈满,则返回FALSE;否则,返回TRUE
④ Pop(S) 出栈:若栈S不空,则返回栈顶元素,并从栈顶中删除该元素;否则,返回空元素  
⑤ GetTop(S) 取栈顶元素:若栈S不空,则返回栈顶元素;否则返回空元素NULL。
⑥ SetEmpty(S) 置栈空操作:置栈S为空栈。

栈是一种特殊的线性表,因此栈可采用顺序存储结构存储,也可以使用链式存储结构存储。

3.2.2栈的顺序存储结构

1. 顺序栈

利用顺序存储的方式实现的栈称为“顺序栈”。类似于顺序表的定义，栈中的数据元素用一个
预设的足够长度的一维数组来实现:ElemType elem[MAXSIZE]。栈底位置可以设置在数组任
一个端点,而栈顶是随着插人和删除而变化的。用int top来作为栈顶的指针,指明当前栈顶的    位置,同时将elem和top封装在一个结构中。顺序栈的类型描述如下。

#define MAXSIZE<栈最大元素数>
typedef struct{ 
  ElemType elem[MAXSIZE];
  int top;
}SeqStack;

定义一个指向顺序栈的指针:

SeqStack *s;

常将0下标端设为栈底,这样空栈时校顶指针s->top=-1;入栈时,栈顶指针加1,即s->top++；出栈时,栈顶指针减1,即s->top–。

1-顺序栈.h

#include<stdio.h> 
#include<stdlib.h> 
//在使用的使用命名 
//typedef int ElemType;
//定义顺序栈 
#define MAXSIZE 10
typedef int  ElemType; 
typedef struct{ 
  ElemType elem[MAXSIZE];
  int top;
}SeqStack;
//(1)置空栈
//首先建立栈空间,然后初始化栈顶指针。
SeqStack * InitStack(){
  SeqStack *s;
  s=(SeqStack * ) malloc(sizeof( SeqStack));  
  s->top=-1;
  return s;
}
//(2)判空栈
int Empty(SeqStack *s){
  if(s->top==-1) return 1;  //代表空 
  else return 0;
}
//(3)入栈
int Push(SeqStack *s, ElemType x){
  if(s->top==MAXSIZE-1) return 0;//栈满不能入栈,否则将造成“上溢” 
  else {s->top++;
  s->elem[s->top]=x;
  return 1;
  } 
}
//(4)出栈
int Pop( SeqStack *s, ElemType *x){
  if(Empty(s)) return 0;  //栈空不能出栈
  else { 
    *x=s->elem[s->top];//栈顶元素存入*x,返回
    s->top--;
    return 1;
  }
}
//(5)取栈顶元素
ElemType GetTop(SeqStack *s){
  if(Empty(s)) return 0;//栈空
  else return (s->elem[s->top]);
}

1-顺序栈测试.c

typedef int ElemType; 
#include "1-顺序栈.h" 
int main(){
  SeqStack *s=InitStack();
  printf("%d",Empty(s));//1 
  int x1=1;
  Push(s,x1); 
  int x2=2;
  Push(s,x2);
  printf("%d",Empty(s));//0
  int x3;
  Pop(s,&x3);
  printf("%d",x3);//2
  int t=GetTop(s);
  printf("%d",t);//1
}

2. 多栈共享邻接空间

栈的共享中最常见的是两栈共享。

假设两个栈共享一维数组elem[MAXSIZE],则可以利用栈的“栈底位置不变,栈顶位置动态变化”特性,两个栈底分别为-1和MAXSIZE,而它们的栈顶都往中间方向延伸。因此,只要整个数组elem[MAXSIZE]未被满,无论哪个栈的人栈都不会发生上溢。

两栈共享的数据结构可定义如下。

typedef struct{
  ElemType elem[ MAXSIZE];
  int lefttop;//左栈栈顶位置指示器
  int righttop;//右栈栈顶位置指示器
} Dupsqstack;

两个栈共享邻接空间的示意图如图3-4所示。左栈入栈时,栈顶指针加1,右栈人栈时,栈顶指针减1。由于两个栈顶均可向中间伸展,互补余缺,因此使得每个栈的最大空间均大于MAXSIZE/2。

为了识别左右栈,必须另外设定标志:

char status;
status ='L';  //左栈
status ='R';//右栈

在进行栈操作时,需指定栈号status=L’为左栈,status='R’为右栈;判断栈满的条件如下:

s->lefttop+1=s->righttop;

2-共享栈.c

勘误：
P63共享栈的初始化，应该是二级指针或者返回一级指针
P64入栈的右栈进栈有误，应为righttop

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
//定义顺序栈 
#define MAXSIZE 10
typedef int  ElemType; 
typedef struct{
  ElemType elem[MAXSIZE];
  int lefttop;//左栈栈顶位置指示器
  int righttop;//右栈栈顶位置指示器
} Dupsqstack;
//(1)初始化操作
//错误；初始化不了 
//s的初始化，并不能传递到实参
//需要使用二级指针 
//int InitDupStack(Dupsqstack *s){
//  //创建两个共享邻接空间的空栈由指针s指出
//  if ((s=(Dupsqstack * )malloc(sizeof(Dupsqstack)))==NULL)  
//    return FALSE;
//  s->lefttop=-1;
//  s->righttop=MAXSIZE;
//  return TRUE;
//}
//修改 
int InitDupStack(Dupsqstack **s){
  //创建两个共享邻接空间的空栈由指针s指出
  if ((*s=(Dupsqstack * )malloc(sizeof(Dupsqstack)))==NULL)  
    return FALSE;
  (*s)->lefttop=-1;
  (*s)->righttop=MAXSIZE;
  return TRUE;
}
//(2)入栈操作
int PushDupSrack(Dupsqstack *s,char status, ElemType x){
  //把数据元素x。压入左栈或右栈
  if(s->lefttop+1==s->righttop)return FALSE;//栈满
  if(status=='L') s->elem[++s->lefttop]=x;//左栈进栈
  if(status=='R') s->elem[--s->righttop]=x;//右栈进栈
  else return FALSE;//参数错误
  return TRUE;
}
//(3)出栈操作
ElemType PopDupStack(Dupsqstack * s,char status){
  //从左楼(satus='L')或右栈(status='R')退出栈顶元素
  if(status=='L'){    
    if(s->lefttop<0) return 999;//左栈为空
    else return (s->elem[s->lefttop--]);//左栈出栈
  }else if(status=='R'){  
    if(s->righttop>MAXSIZE-1) return 999;//右栈为空
    else return (s->elem[s->righttop++]);//右栈出栈
  }else return 999;//参数错误
}
// 去栈顶元素
ElemType GetDupsqTop(Dupsqstack * s,char status){
  if(status=='L'){    
    if(s->lefttop<0) {return 999;}//左栈为空
    else return (s->elem[s->lefttop]);//取左栈顶元素 
  }else if(status=='R'){  
    if(s->righttop>MAXSIZE-1) return 999;//右栈为空
    else return (s->elem[s->righttop]);//取右栈顶元素 
  }
}

int main(){
  Dupsqstack *d;
  InitDupStack(&d);
  int l0=1;
  int r0=2;
  PushDupSrack(d,'L',l0);
  PushDupSrack(d,'R',r0);
  int l=GetDupsqTop(d,'L');
  int r=GetDupsqTop(d,'R');
  printf("%d\n",l);//1
  printf("%d\n",r);//2
}

3.2.3栈的链式存储结构

栈也可以采用链式存储结构表示，这种结构简称为“链栈”。

在一个链栈中,栈底就是结表的最后一个结点,而栈顶总是链表的第一个结点。采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针top就作为栈顶指针,top始终指向当前栈顶元素前面的头结点,即top->next为栈顶元素,当top->next==NULL,则代表栈空。

1）链栈定义

//链栈的C语言定义如下。
typedef int DataType;
typedef struct Stacknode{
  DataType data;
  struct Stacknode * next;
}slStacktype;

2）链栈操作

3-链栈.h

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
//链栈的C语言定义如下。
typedef int DataType;
typedef struct Stacknode{
  DataType data;
  struct Stacknode * next;
}slStacktype;
// 初始化
slStacktype* Init(){
  slStacktype *p;
  if((p=(slStacktype * )malloc(sizeof( slStacktype)))==NULL) 
    return NULL;
  return p;
} 
//(1)入栈操作
//将元素x压入链栈top中
int PushLstack(slStacktype * top, DataType x){  
  slStacktype *p;
  //申请一个结点
  if((p=(slStacktype * )malloc(sizeof( slStacktype)))==NULL) 
    return FALSE;
  p->data=x;
  p->next=top->next;
  top->next=p;
  return TRUE;
}
//(2)出栈操作
//从链栈top中删除栈顶元素
DataType PopLstack(slStacktype * top){
  slStacktype * p;
  DataType x;
  if(top->next==NULL){//空栈  
    printf("此栈为空!");  
    return;
  }
  p=top->next;
  top->next=p->next;  
  x=p->data;
  free(p);
  return x;
}
//取栈顶元素
DataType GetLsPop(slStacktype * top){
  if(top->next==NULL){//空栈  
    printf("此栈为空!");  
    return;
  }
  DataType x=top->next->data;
  return x;
}

3-链栈.c

#include"3-链栈.h"
int main(){
  slStacktype *sl=Init();
  int x=1;
  PushLstack(sl,x);
  int y=GetLsPop(sl);
  printf("%d",y);//1 
  int z=PopLstack(sl);
  printf("%d",z);//1
}

(3)多个链栈的操作

可将多个单链栈的栈顶指针放在一个一维数组中统一管理。

设一维数组top[M]：

slStacktype* top[M]

其中top[0] ,top[1],…,top[i],…,top[M-1]指向M个不同的链栈,分别是M个链栈的栈顶指针,这样只需确定链栈号i,然后以top[i]为栈顶指针进行栈操作,即可实现各种操价。多个链栈示意图如图3-6所示。

多个链栈的基本操作

4-多个链栈.c

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
#define M 10 
//链栈的C语言定义如下。
typedef int DataType;
typedef struct Stacknode{
  DataType data;
  struct Stacknode * next;
}slStacktype;
// 初始化
void Init(slStacktype * top[M],int i){
  if((top[i]=(slStacktype * )malloc(sizeof( slStacktype)))==NULL) 
    printf("初始化出错");
    return;
} 
//①入栈操作
//将元素x压人链栈top[i]中
int PushDupLs(slStacktype * top[M],int i, DataType x){
  Init(top,i);
  slStacktype * p;
  //申请一个结点
  if((p=(slStacktype *)malloc(sizeof(slStacktype)))==NULL){
    return FALSE;   
  }
  p->data=x;
  p->next=top[i]->next;
  top[i]->next=p;
  return TRUE;
}
//②出栈操作
//从链栈top[i]中删除栈顶元素
DataType PopDupLs(slStacktype * top[M],int i){
  slStacktype *p;
  DataType x;
  if(top[i]->next==NULL){//空栈
    printf("此栈为空!");
    return;
  }
  p=top[i]->next;
  top[i]->next=p->next;
  x=p->data;
  free(p);
  return x;
}
//取栈顶元素
DataType GetTopDupLs(slStacktype * top[M],int i){
  slStacktype *p;
  DataType x;
  if(top[i]->next==NULL){//空栈
    printf("此栈为空！");
    return;
  }
  p=top[i]->next; 
  x=p->data;
  free(p);
  return x;
}

int main(){
  slStacktype * top[M];
  int x1=1;
  PushDupLs(top,1,x1);
  int x11=GetTopDupLs(top,1);
  printf("%d",x11);//1
  int x2=2;
  PushDupLs(top,2,x2);
  int x22=GetTopDupLs(top,2);
  printf("%d",x22);//2
}

在上面的两个算法中,当指定栈号i(0<=i<=M-1)时,则只对第i个链栈操作,不会影响其他链栈。

3.2.4栈的应用

0. 括号匹配

判断都是括号所构成的字符串是否括号都是一一对应的

5-括号匹配.c

typedef char ElemType; 
#include "1-顺序栈.h"
int Match(char x,char y){
  if(x=='('){
    if(y==')'){
      return 1;
    }
  }
  if(x=='['){
    if(y==']'){
      return 1;
    }
  }
  if(x=='{'){
    if(y=='}'){
      return 1;
    }
  }
  return 0;
}
void BracketMatch(char *str){ 
  SeqStack* _S=InitStack();
  SeqStack S=*_S;
  int i;
  char ch;
  for(i=0;str[i]!='\0';i++){
    switch(str[i]){
      case'(':
      case'[':
      case'{': 
        Push(&S,str[i]);
        break;  
      case ')':
      case ']':
      case '}': 
        if(Empty(&S)){
          printf("右括号多余!");  
          return;
        }else{
          ch=GetTop(&S);
          if(Match(ch,str[i])){
            Pop(&S,&ch);
          }else{
            printf("对应的左右括号不同类!");  
            return;
          }
        } 
    }
  }
  if(Empty(&S))
    printf("括号匹配!");
  else
    printf("左括号多余!");
}

int main(){
  char str[10];
  printf("输入括号字符串\n"); 
  gets(str);
  printf("%s",str);
  BracketMatch(str);
}

运行结果如下

1. 算术表达式求值(上机)

表达式求值是程序设计语言编译中的一个最基本问题,它的实现方法是栈的一个典型的应用实例,

在计算机中,任何一个表达式都是由操作数(operand)、运算符(operalor)和界限符(delimiter)组成的。其中操作数可以是常数,也可以是变量或常量的标识符;运算符可以是算术运算符、关系运算符和逻辑运算值；界限符为左右括号和标识表达式结束的结束符。在本节中,仅讨论简单算术表达式的求值问题。假设在这种表达式中只含加、减、乘、除四则运算,所有的运算对象均为整型常数,表达式的结束符为“#”,即仅含符号+、一、*、/、(、)和#。

算术四则运算的规则如下。

①先乘除、后加减。

②同级运算时先左后右。

③先括号内,后括号外。

3.3 队列

3.3.1队列的概念及其运算

队列(queue)是另一种限定性线性表,它只允许插人在表的一端进行,而删除在表的另一端进行,允许插人的一端叫队尾(rear),而允许删除的一端叫队头(front)。

队列的插人操作通常为“入队”或“进队”,而队列的删除操作则称为“出队”或“退队”。当队列中无数据元素时,所“空队列”。

根据队列的定义可知，队头元素总是最先进队列,也总是最先出队列;队尾元素总最后进队列,因而也是最后出队列。这种表是按照先进先出（First In First Out,FIFO)的原则组织数据的,因此,队列也被称为“先进先出”表。

在队列上进行的基本操作如下。

①队列初始化:InitQutoe(ql
相始条件:队列q不存在，
操作结果:构造了一个空队列:
②人队操作:InQuene(q.x)
初始条件:队列q存在。
操作结果:对已存在的队列q,插人一个元素x到队尾。操作成功,返回值为TRUE,否则返回值为FALSE
③出队操作:OutQueue(q.x)
初始条件:队列g存在且非空。
操作结果:删除队首元素,并返回其值。操作成功,返回值为TRUE,否则返回值为FALSE
④读队头元素:FrontQueue(q,x)
初始条件:队列q存在且非空。
操作结果:读队头元素,并返回其值,队列不变。操作成功,返回值为TRUE,否则返回值为FALSE.
⑤判队空操作:EmptyQueue(q)
初始条件:队列q存在
操作结果:若q为空队列则返回为TRUE,否则返回为FALSE.

队列的顺序存储结构可以简称为“顺序队列”,另外再设立两个指示器:一个为指向队头元素位置的指示器front,另一个为指向队尾元素位置的指示器rear。

C语言中,数组的下标是从0开始的,因此为了算法设计的方便,在此约定:初始化队列时，空队列的front=rear=-1,当插人新的数据元素时,尾指示器rear加1,而当队头元素出队列时,头指示器front加1。另外还约定,在非空队列中,头指示器front总是指向队列中实际队头元素的前面一个位置,而尾指示器rear总是指向队尾元素(这样的设置是为了某些运算的方便,并不是唯一的方法)。

顺序队列的类型定义如下

define MAXSIZE<最大元素数>//队列的最大容量
vypedef struct{
  ElemType elem[MAXSIZE];//队列元素的存储空间
  int rear,front;//队尾、队头指针
}SeQueue;

定义一个指向队列的指针变量：SeQueue *sq;

申请一个顺序队列的存储空间：sq=(SeQueue*)malloc(sizeof(SeQueue));

存在“假溢出”的问题

3.3.2循环队列

解决假溢出的方法之一是将队列的数据区elem[0~MAXSIZE-1]看成头、尾相接的循环结构，即规定最后一个单元的后维为第个单元,这样整个数据区就像一个环,我们形象地称之为循环队列

入队时队尾指针加1操作修改为

sq->rear=(sq->rear+1)%MAXSIZE

出队时队尾指针加1操作修改为

sq->rear=(sq->front+1)%MAXSIZE

又产生一个新问题队空和队满的条件相同都为front==rear

解决的方法之一是少用一个元素空间，把如图所示视为队满。

队满的条件是(rear+1)%MAXSIZE==front

就能和队空区别开。

另外一种方法是附设一个存储队列中元素个数的变量，如num，当num == 0时队空，当num==MAXSIZE时队满

还有一种在习题（8）中

下面的循环队列及操作依据少用一个元素空间来实现的。

循环队列的类型定义

#define MAXSIZE 10
//下面的循环以列及操作依据少用个元素空间来实现
//循环队列的类型定义及基本运算如下。
typedef int ElemType;
typedef struct{ 
  ElemType elem [MAXSIZE];//队列的存储区
  //队头队尾指针
  int front, rear;  
}CSeQueue;//循环队列

循环队列的基本运算

6-循环队列.c

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
#define MAXSIZE 10
//下面的循环以列及操作依据少用个元素空间来实现
//循环队列的类型定义及基本运算如下。
typedef int ElemType;
typedef struct{ 
  ElemType elem [MAXSIZE];//队列的存储区
  //队头队尾指针
  int front, rear;  
}CSeQueue;//循环队列
//(1)置空队
CSeQueue * IniseQueue(){
  CSeQueue * q=(CSeQueue *)malloc(sizeof(CSeQueue));
  q->front=q->rear=MAXSIZE-1;
  return q;
}
//(2)入队
int InSeQueue( CSeQueue * q,ElemType x){
  if((q->rear+1)%MAXSIZE==q->front){//队满不能人队
    printf("队满");
    return FALSE;
  }else{
    q->rear=(q->rear+1)%MAXSIZE;
    q->elem[q->rear]=x;
    return TRUE;//人队完成
  }
}
//(3)出队
int OutSeQueue( CSeQueue *q , ElemType *x){
  if(q->front==q->rear){
    printf("队空");
    return FALSE;
  }else{
    q->front=(q->front+1)%MAXSIZE;
    *x=q->elem[q->front];//读出队头元素
    return TRUE;//出队完成
  }
}
//(4) 判断队空
int EmptySeQueue(CSeQueue *q){
  if(q->front==q->rear) return TRUE;
  else return FALSE;
}

int main(){
  CSeQueue *cs=IniseQueue();
  int x=1;
  InSeQueue(cs,x);
  printf("%d",EmptySeQueue(cs));//0
  int x0;
  OutSeQueue(cs,&x0);
  printf("%d",x0);//1
  printf("%d",EmptySeQueue(cs));//1
}

3.3.3 链队列

链式存储的队列称为链队列

可以采用带头结点的单链表表示队列。

头指针始终指向头结点，尾指针指向当前最后一个元素结点

//链队列的数据类型描述如下。
typedef struct node{ 
  DataType data;
  struct node * next;
}QNode;
//链队列结点的类型
typedef struct{  
  QNode * front;
  QNode * rear;
} LQueue;//将头尾指针封装在一起的链队列

链队列的基本运算

7-链队列.c

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
#define MAXSIZE 10
typedef int  DataType; 
//链队列的数据类型描述如下。
typedef struct node{ 
  DataType data;
  struct node * next;
}QNode;
//链队列结点的类型
typedef struct{  
  QNode * front;
  QNode * rear;
} LQueue;//将头尾指针封装在一起的链队列
//(1)创建一个带头结点的空队
LQueue * Init_LQueue(){
  LQueue *q; QNode*p;
  q=(LQueue*)malloc( sizeof(LQueue));//申请头尾指针结点  
  p=(QNode*)malloc( sizeof(QNode));//申请链队列头结点  
  p->next=NULL;
  q->front=q->rear=p;
  return q;
}
//(2)入队
void InLQueue(LQueue *q , DataType x){ 
  QNode *p;
  p=(QNode*)malloc(sizeof(QNode));//申请新结点  
  p->data=x;
  p->next=NULL; 
  q->rear->next=p;
  q->rear=p;
}
//(3)判队空
int Empty_LQueue(LQueue *q){
  if(q->front==q->rear) return 1;//代表空 
  else return 0;
}
//(4)出队
int Out_LQueue(LQueue *q, DataType *x){
  QNode *p;
  if(Empty_LQueue(q)){
    printf("队空");
    return FALSE;
  }
  else{ 
    p=q->front->next;
    q->front->next=p->next;
    *x=p->data;//队头元素放x中
    free(p);
    if(q->front->next==NULL)//只有一个元素时,出队后队空,修改队尾指针
      q->rear=q->front;
    return TRUE;
  }
}

int main(){
  LQueue *lq=Init_LQueue();
  printf("%d",Empty_LQueue(lq));//1
  int x=1;
  InLQueue(lq,x);
  printf("%d",Empty_LQueue(lq));//0
  int x0;
  Out_LQueue(lq,&x0);
  printf("%d",x0);//1 
  printf("%d",Empty_LQueue(lq));//0
}

3.4 实例分析与实现

应用实例一迷宫求解

应用实例二马踏棋盘

应用实例三计算器

3.5 算法总结 ——递归与分治算法

实验

应用实例一迷宫求解

应用实例二马踏棋盘

应用实例三计算器

习题3

1.单项选择题

(1)(2010考研真题)若元素a,b,e,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是____。 D

A. d,c,e,b,f,a

B. c,b,d,a,e,f

C. b.c,a,e,f,d

D. a,f,e,d,c,b

(2)若某堆栈的输人序列为1,2,3,n-l,n,输出序列的第1个元素为n,则第i个输出元素为____。 A

A. n-i+1

B. n-1

C. i

D.哪个元素都有可能

(3)以数组Q[0…m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是___。 D

A. rear-qulen

B. rear-qulen+m

C. m-qulen

D. (1+(rear-qulentm))mod m

(4)设输人元素为1,2,3,A,B,输人次序为123AB,元素经过栈后到达输出序列,当所有元素均到达输出序列后,序列____是不可能的。 C

A. BA321

B. A3B21

C. B32A1

D. AB321

(5)(2012年考研真题)已知操作符包括“+”“一”“”“/”“(”和“)”。将中缀表达式a+b-a((c+d)/e-)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空,则转换过程中同时保存在栈中的操作符的最大个数是___。 A

A. 5

B. 7

C. 8

D.11

2.综合题

(2) 回文是指正读反读均相同的字符序列,如“abba”和“abdba"均是回文,但“good"不是回文。试写一个算法判定给定的字符串是否为回文。

2.c

#include<string.h>
typedef char ElemType; 
#include "1-顺序栈.h" 
int Match(char x,char y){
  if(x==y){   
    return 1;
  }
  return 0;
}
void BracketMatch(char *str){ 
  SeqStack* _S=InitStack();
  SeqStack S=*_S;
  int i;
  char ch;
    int len=strlen(str); 
    int mid=len/2;
  for(i=0;str[i]!='\0';i++){
    if(i==mid&&len%2==1){
      continue;
    }
    if(i<mid){      
      Push(&S,str[i]); 
    }else{
      if(Empty(&S)){
        printf("右字符多余!");  
        return;
      }else{
        ch=GetTop(&S);
        if(Match(ch,str[i])){
          Pop(&S,&ch);
        }else{
          printf("对应的左右字符不同!");  
          return;
        }
      } 
    }
  }
  if(Empty(&S))
    printf("回文!");
  else
    printf("左字符多余!");
}

int main(){
  char str[10];
  printf("输入字符串\n");
  gets(str);
  printf("%s",str);
  BracketMatch(str);
}

运行结果如下

(6) 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的置空队、判队空、入队和出队算法。

6.c

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
#define MAXSIZE 10
typedef int  DataType; 
//链队列的数据类型描述如下。
typedef struct node{ 
  DataType data;
  struct node * next;
}QNode;
//链队列结点的类型
typedef struct{  
  QNode * rear;
} XQueue;//将尾指针封装在一起的链队列
//(1)创建一个带头结点的空队
XQueue * Init_XQueue(){
  XQueue *q; QNode*p;
  q=(XQueue*)malloc(sizeof(XQueue));//申请尾指针结点  
  p=(QNode*)malloc(sizeof(QNode));//申请循环队列头结点  
  p->next=p;
  q->rear=p;
  return q;
}
//(2)入队
void InXQueue(XQueue *q , DataType x){ 
  QNode *p;
  p=(QNode*)malloc(sizeof(QNode));//申请新结点  
  p->data=x;
  p->next=q->rear->next; 
  q->rear->next=p;
  q->rear=p;
}
//(3)判队空
int Empty_XQueue(XQueue *q){
  if(q->rear->next==q->rear) return 1;//代表空 
  else return 0;
}
//(4)出队
int Out_XQueue(XQueue *q, DataType *x){
  QNode *p;
  if(Empty_XQueue(q)){
    printf("队空");
    return FALSE;
  }
  else{ 
    p=q->rear->next->next;//q->rear->next相当于q->front 
    q->rear->next->next=p->next;
    *x=p->data;//队头元素放x中
    free(p);
    if(q->rear->next->next==NULL)//只有一个元素时,出队后队空,修改队尾指针
      q->rear=q->rear->next;
    return TRUE;
  }
}

int main(){
  XQueue *lq=Init_XQueue();
  printf("%d",Empty_XQueue(lq));//1
  int x1=1;
  InXQueue(lq,x1);
  printf("%d",Empty_XQueue(lq));//0
  int x2=2;
  InXQueue(lq,x2);
  int y1;
  Out_XQueue(lq,&y1);
  printf("%d",x1);//1 
  int y2;
  Out_XQueue(lq,&y2);
  printf("%d",y2);//2
  printf("%d",Empty_XQueue(lq));//0
}

(8) 在循环队列中,可以设置一个标志域tag,以区分当尾指针和头指针相等时,队列状态是“空”还是“满”（tag的值为0表示“空”,tag的值为1表示“满”),编写此结构相应的队列初始化、入队、出队算法。

8.c

#include<stdio.h>
#include<stdlib.h> 
#define FALSE 0
#define TRUE 1
#define MAXSIZE 2
//下面的循环以列及操作依据少用个元素空间来实现
//循环队列的类型定义及基本运算如下。
typedef int ElemType;
typedef struct{ 
  ElemType elem [MAXSIZE];//队列的存储区
  //队头队尾指针
  int front, rear;
  int flag; 
}CSeQueue;//循环队列
//先声明一下，就不会有Warning 
int EmptySeQueue(CSeQueue *q);
int ManSeQueue(CSeQueue *q);
//(1)置空队
CSeQueue * IniseQueue(){
  CSeQueue * q=(CSeQueue *)malloc(sizeof(CSeQueue));
  q->front=q->rear=MAXSIZE-1;
  q->flag=0;
  return q;
}
//(2)入队
int InSeQueue( CSeQueue * q,ElemType x){
  if(ManSeQueue(q)){//队满不能人队
    printf("队满");
    return FALSE;
  }else{
    q->rear=(q->rear+1)%MAXSIZE;
    q->elem[q->rear]=x;
    q->flag=1;
    return TRUE;//人队完成
  }
}
//(3)出队
int OutSeQueue( CSeQueue *q , ElemType *x){
  if(EmptySeQueue(q)){
    printf("队空");
    return FALSE;
  }else{
    q->front=(q->front+1)%MAXSIZE;
    *x=q->elem[q->front];//读出队头元素
    q->flag=0;
    return TRUE;//出队完成
  }
}
//(4) 判断队空
int EmptySeQueue(CSeQueue *q){
  if(q->front==q->rear&&q->flag==0) return TRUE;
  else return FALSE;
} 
//(5)判断队满
int ManSeQueue(CSeQueue *q){
  if(q->front==q->rear&&q->flag==1) return TRUE;
  else return FALSE;
}

int main(){
  CSeQueue *cs=IniseQueue();
  printf("%d",EmptySeQueue(cs));//1
  int x1=1;
  InSeQueue(cs,x1);
  int x2=2;
  InSeQueue(cs,x2);
  printf("%d",ManSeQueue(cs));//1
  int y1;
  OutSeQueue(cs,&y1);
  printf("%d",y1);//1
  printf("%d",EmptySeQueue(cs));//0
  int y2;
  OutSeQueue(cs,&y2);
  printf("%d",y2);//2
  printf("%d",EmptySeQueue(cs));//1
}

最后

2023-11-2 23:24:48

我们都有光明的未来

不必感谢我，也不必记得我

祝大家考研上岸

祝大家工作顺利

祝大家得偿所愿

祝大家如愿以偿

点赞收藏关注哦

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

第三章 栈和队列【数据结构与算法】【精致版】

前言

第 3 章 栈和队列

3.1 应用实例

应用实例一 迷宫求解问题

应用实例二“马”踏棋盘问题

3.2栈

3.2.1 栈的概念及运算

3.2.2栈的顺序存储结构

1. 顺序栈

1-顺序栈.h

2. 多栈共享邻接空间

2-共享栈.c

3.2.3栈的链式存储结构

1）链栈定义

2）链栈操作

3-链栈.h

(3)多个链栈的操作

多个链栈的基本操作

4-多个链栈.c

3.2.4栈的应用

0. 括号匹配

5-括号匹配.c

1. 算术表达式求值(上机)

3.3 队列

3.3.1队列的概念及其运算

3.3.2循环队列

循环队列的类型定义

循环队列的基本运算

6-循环队列.c

3.3.3 链队列

链队列的基本运算

7-链队列.c

3.4 实例分析与实现

应用实例一 迷宫求解

应用实例二 马踏棋盘

应用实例三 计算器

3.5 算法总结 ——递归与分治 算法

实验

应用实例一 迷宫求解

应用实例二 马踏棋盘

应用实例三 计算器

习题3

1.单项选择题

2.综合题

(2) 回文是指正读反读均相同的字符序列,如“abba”和“abdba"均是回文,但“good"不是回文。试写一个算法判定给定的字符串是否为回文。

(6) 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的置空队、判队空、入队和出队算法。

(8) 在循环队列中,可以设置一个标志域tag,以区分当尾指针和头指针相等时,队列状态是“空”还是“满”（tag的值为0表示“空”,tag的值为1表示“满”),编写此结构相应的队列初始化、入队、出队算法。

最后

热门文章

最新文章

相关课程

相关电子书

相关实验场景

第三章栈和队列【数据结构与算法】【精致版】

第 3 章栈和队列

应用实例一迷宫求解问题

应用实例一迷宫求解

应用实例二马踏棋盘

应用实例三计算器

3.5 算法总结 ——递归与分治算法

应用实例一迷宫求解

应用实例二马踏棋盘

应用实例三计算器