精华内容
下载资源
问答
  • Relax-and-Recover Relax-and-Recover is the leading Open Source bare metal disaster recovery and system migration solution....ready-to-go workflows for common situations. ...Relax-and-Recover produces ...
  • 队列的数组表示

    2020-03-30 22:05:15
    1、队列结构特点和操作 复习一下队列:数据结构“队列”与我们日常生活中...和顺序栈相类似,再利用顺序分配存储结构实现队列时,除了一纬数组描述队列中的数据元素存储区域,还需要设立两个指针front 和 re...

    1、队列的结构特点和操作

    复习一下队列:数据结构“队列”与我们日常生活中的排队非常相似,按照先到先办的原则办事,并且严格规定不能加塞,也不允许中途离队。
    队列:限定只能在队尾进行插入元素,在表头进行删除。允许插入的一端叫队尾,允许删除的一端叫队头。

    1.1循环队列

    和顺序栈相类似,再利用顺序分配存储结构实现队列时,除了用一纬数组描述队列中的数据元素的存储区域,还需要设立两个指针front 和 rear 分别表示队头和队尾的位置。
    初始化队列时front = rear =0;每当插入一个元素后,rear+1;每当删除一个元素是front++;因此在非空队列时,头指针始终指向队头元素,尾指针始终指向队尾元素的下一个位置。如图是一个最大空间为6 的队列。初始化时如下图
    在这里插入图片描述图a表示初始化为一个最大空间为6的空队列。
    图b,开始插入元素,尾指针后移。始终指向队尾元素的下一个位置。
    图c删除队列元素,头指针加1;
    图d继续插入元素,这里如果尾指针在增加一的话指针数组元素就要越界了。
    那么还有什么办法呢,如果这样的话,随着删除元素,这个数组空间就会浪费了。
    我们可以让尾指针循环呀,这就解决了这个问题。看图:
    在这里插入图片描述如图e,这就完美解决了看见浪费的问题
    如图f 队列满的时候尾指针和头指针相等
    如图g 队列为空的时候尾指针和头指针相等
    这样我们就不能部分变队列是空还是满。要解决这个问题的办法有很多,我们可以采取牺牲一个空间,如图h表示队列满。
    要想使rear循环,使用公式rear = (rear+1)%(队列最大容量)

    下面是整体代码

    #include<stdlib,h>
    #include<stdio.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFFLOW -2
    #define INIT_SIZE 10//初始化队列大小
    typedef int QElemtype;
    typedef int Status;
    
    typedef struct SqQueue{
    	QElemtype *base;
    	int top;
    	int rear;
    }SqQueue;//定义一个线性表
    /初始化
    Status InitQueue(SqQueue *Q)
    {
    	Q->base=(QElemtype *)malloc(sizeof(QElemtype)*INIT_SIZE);
    	if(Q->base)
    	{
    	Q->top=0;
    	Q->rear=0;
    	return OK;	
    	}
    	return ERROR;
    	
     } 
     //队列的长度
     int QueueLength(SqQueue Q)
     {
    
    		return ((Q.rear-Q.top+INIT_SIZE)%INIT_SIZE) ;
    
     } 
     //入队
    Status EnQueue(SqQueue *Q,QElemtype e)
    {
    	if((Q->rear+1)%INIT_SIZE+1 == Q->top)  return ERROR;
    	
    	Q->base[Q->rear]= e;
    	Q->rear = (Q->rear+1)%INIT_SIZE;
    	return OK;
    	
    } 
    //出队
    Status DeQueue(SqQueue *Q,QElemtype *e)
    {
    	if(Q->top == Q->rear)return ERROR;
    	*e = Q->base[Q->top];
    	Q->top = (Q->top+1)%INIT_SIZE;
    	return OK;
     } 
    //访问
     void visit(QElemtype e)
     {
     	printf("%d",e);
     }
     
     void Tr(SqQueue Q,void (*visit)(QElemtype e))
     {
     	while(Q.top != Q.rear)
    	 {
    	 	(*visit)(Q.base[Q.top]);
    	 	Q.top=(Q.top+1)%INIT_SIZE;
    	  } 
     }
     int main()
     {
     	SqQueue Q;
     	if(InitQueue(&Q))
     		printf("初始化成功\n");
     	for(int i=0;i<9;i++)
     	{
     		EnQueue(&Q,i);	
    	 }
     	
    	
    	 Tr(Q,visit);
    	 int a = QueueLength(Q);
    	 printf("%d",a);
    	 return 0;
    	 
     }
    
    展开全文
  • 队列是一种先进先出的的数据...循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head==tail时,表示队列为空。当(tail+1)%MAX_SIZE == head,表示队列已满。 我判断队满方法:牺牲一个单元来区分对空和

           队列是一种先进先出的的数据结构,我们同样可以使用数组、链表等来实现。我们可以在队列的尾部进行插入元素,在队列的头部取出元素。普通的队列由于空间利用率不高,所以我们一般都用循环队列。循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head==tail时,表示队列为空。当(tail+1)%MAX_SIZE == head,表示队列已满。

           我判断队满的方法:牺牲一个单元来区分对空和队满,入队时少用一个队列单元,相当于浪费一个存储空间。“队头指针的队尾指针的下一位置作为队满的标志”。代码上传至:https://github.com/chenyufeng1991/Queue_Array  。

    (1)进队列

    //进队列
    void EnQueue(int value){
    
        //要先判断队列是否已满
        if ((tail + 1) % QUEUE_SIZE == head) {
            printf("队列已满,无法从队尾插入元素\n");
        }else{
    
            queue[tail] = value;
            tail = (tail + 1) % QUEUE_SIZE;
        }
    }

    (2)出队列

    //出队列
    int DeQueue(){
    
        int temp;
        if (tail == head) {
            printf("队列为空,元素无法出队列\n");
        }else{
    
            temp = queue[head];
            head = (head + 1) % QUEUE_SIZE;
        }
    
        printf("%d\n",temp);
        return temp;
    }

    (3)判断队列是否为空

    //判断队列是否为空
    int IsEmpty(){
        if (head == tail) {
            printf("队列为空\n");
            return 1;
        }
    
        printf("队列不为空\n");
        return 0;
    }

    (4)判断队列是否已满

    //判断队列是否已满
    /**
     *  我这里判断队满的的方法:
     牺牲一个单元来区分队空和队满,入队时少用一个队列单元。如果数组的大小为Size,那么实际只能存放(Size-1)个元素。(这是比较常用的判满的方式)
     *
     */
    int IsFull(){
    
        if ((tail + 1) % QUEUE_SIZE == head) {
            printf("队列已满\n");
            return 1;
        }
    
        printf("队列未满\n");
        return 0;
    }

    (5)打印队列元素

    //打印出队列元素
    void PrintQueue(){
    
        for (int i = head; i < tail; i++) {
            printf("%d ",queue[i]);
        }
        printf("\n");
    }

    (6)测试代码

    int main(int argc, const char * argv[]) {
    
        EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8);
        PrintQueue();
    
        DeQueue();DeQueue();
        PrintQueue();
        
        return 0;
    }


    展开全文
  • 线性结构主要操作就是插入和删除,我们前面讲过顺序线性表、单链表、双链表都没有限制插入和删除操作位置。如果我们限定插入和删除操作... 队列的实现可以顺序线性表也可以链表。实际使用有一种更常用


      线性结构的主要操作就是插入和删除,我们前面讲过的顺序线性表、单链表、双链表都没有限制插入和删除操作的位置。如果我们限定插入和删除操作在线性表的同一端进行那么这种结构就是栈;如果限定插入在一端而删除在另一端,这种结构就是对列;栈的特点是先进后出(FILO)而对列是先进先出(FIFO)。进行插入的一端叫队尾,删除的一端叫队头。
       队列的实现可以用顺序线性表也可以用链表。在实际使用中有一种更常用的队列叫循环队列。循环队列是把队列的头和尾在逻辑上连接起来,构成一个环。循环队列中首尾相连,分不清头和尾,此时需要两个指示器分别指向头部和尾部。插入就在尾部指示器的指示位置处插入,删除就在头部指示器的指示位置删除。
       循环队列在插入时也要判断其是否已满,删除时要判断其是否已空。为空的条件比较简单当头部指示器和尾部指示器指向同一个位置时表示循环队列为空;因为尾部指示器指示的是最后一个元素的下一个位置,所以循环队列已满时头部指示器和尾部指示器也指向同一个位置,为了区分这两种状况有两种方法,一种增加一个标识变量来区分,另一种损失循环队列中的一个元素,即头和尾之间的位置不用,此时循环队列为满的条件变成头部指示器加1等于尾部指示器;为空的条件成为头部指示器和尾部指示器指向同一位置。
       循环队列的首尾相连是通过取余操作来实现的,把头和尾的位置都除以队列最大长度然后取余。当到达尾部及最后一个位置时再加1就成了队列的长度刚好可以整除余0即又回到了队头。
       循环队列的主要操作:
       (1)创建循环队列
       (2)初始化循环队列
       (3)判断循环队列是否为空
       (4)判断循环队列是否为满
       (5)入队
       (6)出队
      Microsoft Visual Studio .NET 2003下的程序:
      #include
      #include
      #define MAXSIZE 100
      typedef struct
      {
      int elem[MAXSIZE];
      int front,rear;
      }Quque; //定义队头
      
      int initQue(Quque **q) //初始化
      {
      (*q)->front=0;
      (*q)->rear=0;
      }
      
      int isFull(Quque *q)
      {
      if(q->front==(q->rear+1)%MAXSIZE) //判满
      return 1;
      else
      return 0;
      }
      int insertQue(Quque **q,int elem)
      {
      if(isFull(*q)) return -1;
      (*q)->elem[(*q)->rear]=elem;
      (*q)->rear=((*q)->rear+1)%MAXSIZE; //插入
      return 0;
      }
      int isEmpty(Quque *q)
      {
      if(q->front==q->rear) //判空
      return 1;
      else
      return 0;
      }
      int deleteQue(Quque ** q,int *pelem)
      {
      if(isEmpty(*q))
      return 0;
      *pelem=(*q)->elem[(*q)->front];
      (*q)->front =((*q)->front +1)%MAXSIZE;
      return 0;
      }
      
      int main(void)
      {
      int i=0,elem;
      Quque *q=(Quque *)malloc(sizeof(Quque));
      initQue(&q);
      for(;i<10;i++)
      {
      insertQue(&q,i);
      }
      for(i=0;i<10;i++)
      {
      deleteQue(&q,&elem);
      printf("%d/n",elem);
      }
      system("pause");
      return 0;
      }

    展开全文
  • 在用数组表示的循环队列中,front值一定小于等于rear值。 F 1-3 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况. T 选择题 2-1 若用大小为6的数组来实现循环队列,且当前front和rear的值分别为...

    判断题
    1-1
    所谓“循环队列”是指用单向循环链表或者循环数组表示的队列F

    循环队列指的是循环数组,和单向循环链表无关

    1-2
    在用数组表示的循环队列中,front值一定小于等于rear值。F

    1-3
    不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况.T

    选择题

    2-1
    若用大小为6的数组来实现循环队列,且当前front和rear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,front和rear的值分别为多少? A
    A.2和0
    B.2和2
    C.2和4
    D.2和6

    2-2
    如果循环队列用大小为m的数组表示,且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围,那么这样的循环队列可以容纳的元素个数最多为: B
    A.m-1
    B.m
    C.m+1
    D.不能确定

    2-3
    如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为: D
    A.front+size
    B.front+size-1
    C.(front+size)%m
    D.(front+size-1)%m

    展开全文
  • 数据结构——循环队列PTA习题

    千次阅读 2020-12-17 23:39:58
    文章目录单选题题解函数题6-1 另类循环队列 (20分)输入样例:输出样例:代码6...在用数组表示的循环队列中,front值一定小于等于rear值。 错 3 为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓
  • 判断题: 1-1所谓“循环队列”是指用单向循环链表或者...1-2在用数组表示的循环队列中,front值一定小于等于rear值。(F) (1分) 解析:由于出队与入队操作front = (front+1)% n,rear = (rear + 1)% n; ...
  • rear和length表示的循环队列

    千次阅读 2018-06-23 19:43:37
    试给出此循环队列的队满条件,并写出相应入队列和出队列算法(出队列算法要返回队头元素)。 输入先输入一个不大于100正整数n(输入数据个数)和m(循环队列数组的大小),再输入n个整数,其中输入0...
  • 循环队列不能通过队头队尾指针相等判别队列空间是“空”...从上述分析可见,C语言不能动态分配一维数组来实现循环队列。如果用户应用程序设有循环队列,则必须为它设定一个最大队列长度(顺序);若用户...
  • 具体应用通常链表或者数组来实现。队列只允许后端(称为rear)进行插入操作,前端(称为front)进行删除操作。 循环队列可以更简单防止伪溢出发生,但是队列大小是固定。 2.实例代码: /* 队列...
  • 数组和广义表 2021-1-16

    2021-01-16 14:37:36
    在用数组表示的循环队列中,front值一定小于等于rear值。 F 1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用顺序表存储最节省时间。 T 1-3 若用链表来表示一个线性表,...
  • 波波数据结构-队列

    2020-12-20 01:16:34
    在用数组表示的循环队列中,front值一定小于等于rear值 F 解析:环形循环队列font的值有可能大于rear 1-2 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。T 解析:顺序存储结构都是要定义数组...
  • 数据结构-队列

    2019-09-22 12:09:06
    1.在用数组表示的循环队列中,front值一定小于等于rear值。 T F 2.循环队列执行出队操作时会引起大量元素的移动。 T F 3.栈是插入和删除只能在一端进行的线性表;队列是插入在一端进行,删除在另...
  • 1.循环队列中判断队空方法是判断front==rear,队满方法是判断front=(rear+1)%maxSize。(我曾经想过为什么不用一个length表示队长,当length==maxSize时队满)原因就是,频繁队列操作中,多出一个变量会...
  • 循环队列

    2020-02-19 00:29:28
    循环队列是队列一种顺序表示和实现方法。与顺序栈类似,队列顺序存储结构一组地址连续存储单元依次存放从队头到队尾元素,如一维数组Queue[ MAXSIZE]。此外,由于队列中队头和队尾位置都是动态...
  • 队列-顺序循环队列

    2020-03-11 20:50:29
    一维数组来存放顺序队列中的数据元素。 队头位置设在数组下标为 0 端, front 表示; 队尾位置设在数组的另一端, rear 表示。 front 和 rear 随着插入和删除而变化。 当队列为空时, front=rear=0。 因为...
  • 数据结构作业9—队列(判断题)

    千次阅读 2018-12-20 16:50:22
    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分) T F 作者: DS课程组 ...1-3在用数组表示的循环队列中,front值一定小于等于rear值。 (1分) T F 作者: DS课程组 ...
  • 作业9-队列及其应用

    2020-12-11 21:35:12
    在用数组表示的循环队列中,front值一定小于等于rear值 (F) 提示:最后一个元素时 front = rear; 最后一个元素用掉后 front > rear 2-8 如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为...
  • 1-1 若一个栈的输入序列为1,2,3,…,N,输出序列的第...在用数组表示的循环队列中,front值一定小于等于rear值。 F 循环数组 大于小于等于都有可能 大于max后会取余 1-5 栈和队列的存储方式,既可以是顺序方式,也
  • 队列先进先出,涉及到两个位置操作,一个是队首,一个是队尾,我们分别用两个整型变量来表示队首和队尾,另外需要注意是我们实现队列时要借助循环数组,具体代码已经很清楚了。实现过程中的技巧与用数组实现...
  •  在队列的顺序存储结构,除了一组地址连续存储单元依次存放从队列头 到 队列元素之外, 尚需附设两个 变量(虚拟指针): front 和 rear 分别指向 头 和 尾对应的数组下标。为了 C 语言描述方便, ...
  • 第三章 循环队列及线性结构综合

    千次阅读 2018-10-11 18:01:32
    所谓“循环队列”是指单向循环链表或者循环数组表示的队列。 (1分)  F F:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储其中的队列称为循环队列(Circular Queue)。这种循环队列可以...
  • 队列中可以插入的一端为队尾(rear),允许删除的一端称为队头(front)。 队列也分为两种,一种是用数组的存储表示,一种是基于链表的存储表示。 基于数组的存储表示的队列被称为顺序队列。其数据成员包括,一...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 211
精华内容 84
关键字:

在用数组表示的循环队列中