=
pnew这个代码从队列的尾部增加新节点,
然后pq->rear
=
pnew更新队列尾部指针。队列的数据结构形式就是由一个头front指针,一个尾rear指针来表征,items的设计是用空间换时间,涉及队列大小的操作会非常方便。
队列的特征是先进先出,你给出的链式实现,其实就跟一个链表一样,链表的添加删除如果能理解了,队列只是链表的元素增加/删除
按先进先出特点的一种实现。
但对于队列来说,实现方式不是重点,先进先出的性质才是重点,这在实际应用中很多,比如排队叫号。
网络答案,已验证:#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data /*值域*/
struct Node *next /*链接指针*/
}
struct queue
{
struct Node *front /*队首指针*/
struct Node *rear /*队尾指针*/
}
/*初始化链队*/
void initQueue(struct queue *hq)
{
hq->front=hq->rear=NULL /*把队首和队尾指针置空*/
}
/*向链队中插入一个元素x*/
void inQueue(struct queue *hq, int x)
{
struct Node *newNode /*得到一个由newNode指针所指向的新结点*/
newNode=malloc(sizeof(struct Node))
if(newNode==NULL)
{
printf("内存空间分配失败! ")
exit(1)
}
newNode->data=x /*把x的值赋给新结点的值域*/
newNode->next=NULL /*把新结点的指针域置空*/
/*若链队为空,则新结点即是队首结点又是队尾结点*/
if(hq->rear==NULL)
{
hq->front=hq->rear=newNode
}else
{
/*若链队非空,则依次修改队尾结点的指针域和队尾指针,使之指向新的队尾结点*/
hq->rear=hq->rear->next=newNode
}
//return
}
/*从队列中删除一个元素*/
int delQueue(struct queue*hq)
{
struct Node*p
int temp
/*若链队为空则停止运行*/
if(hq->front==NULL)
{
printf("队列为空,无法删除! ")
exit(1)
}
temp=hq->front->data
/*暂存队首元素以便返回*/
p=hq->front
/*暂存队首指针以便回收队尾结点*/
hq->front=p->next /*使队首指针指向下一个结点*/
/*若删除后链队为空,则需同时使队尾指针为空*/
if(hq->front==NULL)
{
hq->rear=NULL
}
free(p) /*回收原队首结点*/
return temp /*返回被删除的队首元素值*/
}
/*读取队首元素*/
int peekQueue(struct queue *hq)
{ /*若链队为空则停止运行*/
if(hq->front==NULL)
{
printf("队列为空,无法删除! ")
exit(1)
}
return hq->front->data /*返回队首元素*/
}
/*检查链队是否为空,若为空则返回1,否则返回0*/
int emptyQueue(struct queue *hq)
{
/*判断队首或队尾任一个指针是否为空即可*/
if(hq->front==NULL)
{
return 1
}else
{
return 0
}
}
/*清除链队中的所有元素*/
void clearQueue(struct queue *hq)
{
struct Node *p=hq->front /*队首指针赋给p*/
/*依次删除队列中的每一个结点,最后使队首指针为空*/
while(p!=NULL)
{
hq->front=hq->front->next
free(p)
p=hq->front
}
/*循环结束后队首指针已经为空*/
hq->rear=NULL /*置队尾指针为空*/
return
}
int main(int argc,char *argv[])
{
struct queue q
int a[8]={3,8,5,17,9,30,15,22}
int i
initQueue(&q)
for(i=0i<8i++)
{
inQueue(&q,a[i])
}
printf("delnode is %d\n",delQueue(&q))
printf("delnode is %d\n",delQueue(&q))
inQueue(&q,68)
printf("peeknode is %d\n",peekQueue(&q))
while(!emptyQueue(&q))
{
printf("%d\n",delQueue(&q))
}
clearQueue(&q)
}
我自己写了一个,练练手
由于没有指定数据类型,在第三行处我用float类型了
如果改成其它类型,代码中有//Type处,涉及输入输出,也要相应的改一下
这个代码只做了简单的测试,不保证正确性
#include<stdio.h>#include<malloc.h>
#define Type float
struct node{
Type data
struct node *next
}
struct queue{
struct node *front,*rear
}
struct node * push(Type t,struct queue *q)
{
struct node *last
last=(struct node *)malloc(sizeof(struct node))
last->data=t
last->next=NULL
if(q->rear!=NULL){
q->rear->next=last
q->rear=last
}else{
q->front=last
q->rear=last
}
return last
}
Type pop(struct queue *q)
{
struct node nd
if(q->front==NULL){
printf("<<<Error:queue is blank\n")
return 0
}
nd=*(q->front)
free(q->front)
if(q->front!=q->rear)
q->front=nd.next
else{
q->front=NULL
q->rear=NULL
}
return nd.data
}
void clear(struct queue *q)
{
struct node *np,*np1
if(q->front!=NULL){
np=q->front
while(1){
np1=np
free(np)
if(np==q->rear)
break
np=np1->next
}
q->front=NULL
q->rear=NULL
}
printf("<<<The queue has been cleared\n")
}
struct queue * init()
{
struct queue *q=(struct queue *)malloc(sizeof(struct queue))
q->front=NULL
q->rear=NULL
return q
}
void display(struct queue *q)
{
struct node *np
np=q->front
if(np==NULL){
printf("<<<The queue is blank\n")
return
}
while(1){
printf(">>>%f\n",np->data)//Type
if(np==q->rear)
break
np=np->next
}
}
int main()
{
struct queue *q
unsigned int c
Type t
q=init()
printf("<<<One blank queue has been created\n")
while(1){
printf("Menu:\
\n*******************************************************\
\n\t1:push an element to queue\
\n\t2:pop an element from queue\
\n\t3:clear queue\
\n\t4:display queue\
\n\t5:exit\
\n*******************************************************\
\nPlease select operator\n")
scanf("%d",&c)
switch(c){
case 1:
printf("Please input the element pushed to queue:\n")
scanf("%f",&t)//Type
push(t,q)
break
case 2:
printf(">>>The element poped from queue is %f\n",pop(q))//Type
break
case 3:
clear(q)
break
case 4:
display(q)
break
case 5:
clear(q)
free(q)
break
default:
printf("Invalid input\n")
break
}
if(c==5)
break
}
return 0
}