循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。使用求余运算可以判断队列是否已满。
代码
//circular Queue 循环队列实现 #include <stdlib.h>#include <stdio.h>#define MAXSIZE 100typedef int ElemType typedef struct { ElemType *base//存储内存分配基地址 int front //队列头索引 int rear //队列尾索引}circularQueue//初始化队列InitQueue(circularQueue *q){ q->base = (ElemType *)malloc((MAXSIZE) * sizeof(ElemType))if (!q->base) exit(0)q->front = q->rear = 0} //入队列 *** 作InsertQueue(circularQueue *q, ElemType e){ if ((q->rear + 1) % MAXSIZE == q->front) return//队列已满时,不执行入队 *** 作 q->base[q->rear] = e //将元素放入队列尾部 q->rear = (q->rear + 1) % MAXSIZE//尾部元素指向下一个空间位置,取模运算保证了索引不越界(余数一定小于除数)} //出队列 *** 作DeleteQueue(circularQueue *q, ElemType *e){ if (q->front == q->rear) return //空队列,直接返回 *e = q->base[q->front] //头部元素出队 q->front = (q->front + 1) % MAXSIZE}
更多信息可以参考《Linux就该这么学》
彻底修改好了,请看:#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define maxqsize 10
#define overlow 0
#define error 0
#define ok 1
typedef struct
{
char *base
int front
int rear
} sqqueue
int initqueue_sq(sqqueue *q)
{ //初始化顺序队
q->base = (char *) malloc(maxqsize * sizeof (char))
if (!q->base)
return overlow//存储分配失败
q->front = q->rear = 0
return ok
}
int enqueue_sq(sqqueue *q, char e)
{ //e插入队尾作为新元素
if ((q->rear + 1) % maxqsize == q->front)
return error//存储分配失败
q->base[q->rear] = e
q->rear = (q->rear + 1) % maxqsize
return ok
}
int dequeue_sq(sqqueue *q, char *e)
{ //出队,返回首元素e的值
if (q->front == q->rear)
return error
*e = q->base[q->front]
q->front = (q->front + 1) % maxqsize
return ok
}
int queuelength_sq(sqqueue *q) //求对长
{
return (q->rear - q->front + maxqsize) % maxqsize
}
//int queuetraverse_sq(sqqueue q, int(*visit)()) //这里的参数visit应该跟下面的函数visit格式一致
int queuetraverse_sq(sqqueue q, int(*visit)(char *))
{ //遍历顺序循环队
int i, n
n = queuelength_sq(&q)
for (i = 0i <ni++)
//visit(q.base + i)//应该从front遍历到rear,而不是从base开始,直接遍历N个元素
visit(q.base + (q.front+i)%maxqsize)
return ok
}
//#-----------------这个函数写的问题有问题
/*int visit(char (q.base))
{
printf("%c", *(q.base))
return ok
} */
//#---------------------------------
int visit(char *base)
{
printf("%c", *base)
return ok
}
int main()
{
sqqueue q
char e
int i, n, m
initqueue_sq(&q)
printf("input the number of the datas:")
scanf("%d", &n)
for (i = 0i <ni++)
{
//fflush(stdin)//用下面几句代码,替换fflush
int c
if(feof(stdin) || ferror(stdin))
{
break
}
while ( (c = getchar()) != '\n' &&c != EOF )
printf("enter the queue:")
scanf("%c", &e)
if(!enqueue_sq(&q, e))
{
printf("the queue is full!\n")
break
}
}
printf("traverse the queue now:")
//queuetraverse_sq(q, int(*e))//不知道你这样写,有什么意图,应该是下面这句的吧?
queuetraverse_sq(q, (*visit))
printf("\nthe length of the queue is %d\n", queuelength_sq(&q))
printf("input the number of the datas to out:")
scanf("%d", &m)
for (i = 0i <mi++)
{
printf("output the first data in the queue:")
dequeue_sq(&q, &e)
printf("%c\n", e)
}
printf("traverse the queue now:")
queuetraverse_sq(q, (*visit))
printf("\nthe length of the queue is %d\n", queuelength_sq(&q))
getchar()getchar()//暂停一下
}
s表示的是循环队列的成员个数front是队列的头指针
rear是队列的尾指针
s=0表示循环队列中的成员个数为0,当然也就是队列为空了
s=1表示循环队列中的成员个数为1,front=rear说明队列的头指针和尾指针都指向同一个队列成员,也就是说这个/队列已经封闭了(首尾已经相接),那么这个队列也就满了
>>front=rear=m其中的m也不晓得是什么了
这个m就是具体的成员的地址了,front=rear=m,m就成了当前循环队列中唯一的成员
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)