| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 7628 人关注过本帖
标题:循环队列的初始化
只看楼主 加入收藏
ldsh304
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:7
帖 子:242
专家分:755
注 册:2016-1-18
结帖率:100%
收藏
已结贴  问题点数:5 回复次数:6 
循环队列的初始化
程序代码:
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 3
#define INCREASESIZE 3

typedef struct SqListQueeu
{
    int *elem;
    int front;
    int rear;
    int maxsize;
    int increasesize;
}SqQueue;

 
bool Init(SqQueue &Q)//初始化队列 
{
    Q.elem = (int *)malloc(MAXSIZE * sizeof(int));//18
    Q.maxsize = MAXSIZE;
    Q.increasesize = INCREASESIZE;
    Q.front = Q.rear = 0;
}

void increase(SqQueue &Q)//进队列 
{
    Q.elem = (int *)realloc(Q.elem, (Q.maxsize + Q.increasesize) * sizeof(int));
    Q.maxsize += Q.increasesize;
}

void EnQueue(SqQueue &Q, int e)//入队列 
{
    if (Q.front == (Q.rear + 1) % Q.maxsize)
        increase(Q);
    Q.elem[Q.rear] = e;
    Q.rear = (Q.rear + 1) % Q.maxsize;
}
bool is_empty(SqQueue Q)//判空 
{
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

int length(SqQueue Q)//求队列的长度
{
    return (Q.rear - Q.front + Q.maxsize) % Q.maxsize;
}

 
bool DeQueue(SqQueue &Q, int &e)//出队列 
{
    if (is_empty(Q))
    {
        printf("Queue is empty! ^_^ \n");
        e = 0;
        return false;
    }
    e = Q.elem[Q.front];
    Q.front = (Q.front + 1) % Q.maxsize;
    return true;
}

bool print(SqQueue Q)//输出元素 
{
    int e;
    while (!is_empty(Q))
    {
        DeQueue(Q, e);
        printf("%d  ", e);
    }
    printf("\b\b \n");
}

int main()
{
    SqQueue Q;
    
    Init(Q);
    EnQueue(Q, 0);
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 7);
    EnQueue(Q, 8);
    EnQueue(Q, 9);
    printf("LENGTH = %d\n", length(Q)); 
    print(Q);
    
    return 0;
} 

在书中18行是    Q.elem = (int *)malloc((MAXSIZE + 1) * sizeof(int));
请问为什么要这样分配空间,这样不是浪费内存吗?
若不分配会出现什么问题?

[此贴子已经被作者于2016-5-14 19:23编辑过]

2016-05-14 19:17
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:2 
初始化空间,不是浪费内存,不分配会导致入队失败

ps:EnQueue中调用了realloc但是没有进行数据移动,会出现数据丢失。


[fly]存在即是合理[/fly]
2016-05-15 10:40
weidelong
Rank: 3Rank: 3
等 级:论坛游侠
威 望:3
帖 子:31
专家分:158
注 册:2015-2-6
收藏
得分:3 
因为判断队列满的条件Q.front == (Q.rear + 1),需要增加1个存储空间,即(int *)malloc((MAXSIZE + 1) * sizeof(int)),而不是realloc的问题。
或者可以增加一个计数的成员变量代替
具体见http://blog.
2016-05-15 12:21
ldsh304
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:7
帖 子:242
专家分:755
注 册:2016-1-18
收藏
得分:0 
回复 楼主 ldsh304
但是没有加1时,运行时正常的,怎么会入队失败?
看了好多程序在初始化都是没有加1的。
realloc()是将原有数据从头到尾拷贝到新分配的内存区域,而后释放原来mem_address所指内存区域(注意:原来指针是自动释放,不需要使用free),同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
怎样会造成数据丢失?

[此贴子已经被作者于2016-5-15 14:31编辑过]

2016-05-15 14:23
ldsh304
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:7
帖 子:242
专家分:755
注 册:2016-1-18
收藏
得分:0 
回复 3楼 weidelong
这是队满条件
[/[code]if(Q->front==(Q->rear+1)%Q->maxsize)    //判断循环链表是否满,留一个预留空间不用  
code]
并不是Q->front==Q->rear+1
2016-05-15 14:29
weidelong
Rank: 3Rank: 3
等 级:论坛游侠
威 望:3
帖 子:31
专家分:158
注 册:2015-2-6
收藏
得分:0 
回复 5楼 ldsh304
从你那个入队列函数第一句复制的,没复制全,不就是判断没满的意思吗
2016-05-15 14:54
ldsh304
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:7
帖 子:242
专家分:755
注 册:2016-1-18
收藏
得分:0 
回复 6楼 weidelong
是,
但是我说的是 你所说的判断条件错了
  Q->front==(Q->rear+1)%Q->maxsize
并不是    Q->front==Q->rear+1
2016-05-15 17:12
快速回复:循环队列的初始化
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016723 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved