当前位置:主页   - 电脑 - 程序设计 - C/C++
数据结构C语言实现之队列
来源:网络   作者:    更新时间:2010-09-26
收藏此页】    【字号    】    【打印】    【关闭

#include<stdio.h>
#include<stdlib.h>
typedefintelemType;
/************************************************************************/
/*          以下是关于队列链接存储操作的6种算法       */
/************************************************************************/
structsNode{
   elemTypedata;      /*值域*/
   structsNode*next;    /*链接指针*/
};
structqueueLK{
   structsNode*front;  /*队首指针*/
   structsNode*rear;    /*队尾指针*/
};
/*1.初始化链队*/
voidinitQueue(structqueueLK*hq)
{
   hq->front=hq->rear=NULL;    /*把队首和队尾指针置空*/
   return;
}
/*2.向链队中插入一个元素x*/
voidenQueue(structqueueLK*hq,elemTypex)
{
   /*得到一个由newP指针所指向的新结点*/
   structsNode*newP;
   newP=malloc(sizeof(structsNode));
   if(newP==NULL){
     printf("内存空间分配失败! ");
     exit(1);
   }
   /*把x的值赋给新结点的值域,把新结点的指针域置空*/
   newP->data=x;
   newP->next=NULL;
   /*若链队为空,则新结点即是队首结点又是队尾结点*/
   if(hq->rear==NULL){
     hq->front=hq->rear=newP;
   }else{  /*若链队非空,则依次修改队尾结点的指针域和队尾指针,使之指向新的队尾结点*/
     hq->rear=hq->rear->next=newP;    /*注意赋值顺序哦*/
   }
   return;
}
/*3.从队列中删除一个元素*/
elemTypeoutQueue(structqueueLK*hq)
{
   structsNode*p;
   elemTypetemp;
   /*若链队为空则停止运行*/
   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);    /*回收原队首结点*/
   returntemp;  /*返回被删除的队首元素值*/
}
/*4.读取队首元素*/
elemTypepeekQueue(structqueueLK*hq)
{
   /*若链队为空则停止运行*/
   if(hq->front==NULL){
     printf("队列为空,无法删除! ");
     exit(1);
   }
   returnhq->front->data;    /*返回队首元素*/
}
/*5.检查链队是否为空,若为空则返回1,否则返回0*/
intemptyQueue(structqueueLK*hq)
{
   /*判断队首或队尾任一个指针是否为空即可*/
   if(hq->front==NULL){
     return1;
   }else{
     return0;
   }
}
/*6.清除链队中的所有元素*/
voidclearQueue(structqueueLK*hq)
{
   structsNode*p=hq->front;    /*队首指针赋给p*/
   /*依次删除队列中的每一个结点,最后使队首指针为空*/
   while(p!=NULL){
     hq->front=hq->front->next;
     free(p);
     p=hq->front;
   }  /*循环结束后队首指针已经为空*/
   hq->rear=NULL;    /*置队尾指针为空*/
   return;
}
/************************************************************************/
intmain(intargc,char*argv[])
{
   structqueueLKq;
   inta[8]={3,8,5,17,9,30,15,22};
   inti;
   initQueue(&q);
   for(i=0;i<8;i++){
     enQueue(&q,a[i]);
   }
   printf("%d",outQueue(&q));  printf("%d ",outQueue(&q));
   enQueue(&q,68);
   printf("%d",peekQueue(&q));  printf("%d ",outQueue(&q));
   while(!emptyQueue(&q)){
     printf("%d",outQueue(&q));
   }
   printf(" ");
   clearQueue(&q);
   system("pause");
}
#include<stdio.h>
#include<stdlib.h>
typedefintelemType;
/************************************************************************/
/*           以下是关于队列顺序存储操作的6种算法       */
/************************************************************************/
structqueue{
   elemType*queue;    /*指向存储队列的数组空间*/
   intfront,rear,len;  /*队首指针(下标),队尾指针(下标),队列长度变量*/
   intmaxSize;      /*queue数组长度*/
};
voidagainMalloc(structqueue*q)
{
   /*空间扩展为原来的2倍,原内容被自动拷贝到p所指向的存储空间中*/
   elemType*p;
   p=realloc(q->queue,2*q->maxSize*sizeof(elemType));
   /*动态存储空间分配,若失败则退出运行*/
   if(!p){
     printf("空间分配失败! ");
     exit(1);
   }
   q->queue=p;    /*使queue指向新的队列空间*/
   /*把原队列的尾部内容后移maxSize个位置*/
   if(q->rear!=q->maxSize-1){
     inti;
     for(i=0;i<=q->rear;i++){
       q->queue[i+q->maxSize]=q->queue[i];
     }
     q->rear+=q->maxSize;    /*队尾指针后移maxSize个位置*/
   }
   q->maxSize=2*q->maxSize;  /*把队列空间大小修改为新的长度*/
   return;
}
/*1.初始化队列*/
voidinitQueue(structqueue*q,intms)
{
   /*检查ms是否有效,若无效则退出运行*/
   if(ms<=0){
     printf("ms值非法! ");
     exit(1);
   }
   q->maxSize=ms;    /*置队列空间大小为ms*/
   /*动态存储空间分配,若失败则退出运行*/
   q->queue=malloc(ms*sizeof(elemType));
   if(!q->queue){
     printf("内存空间分配失败! ");
     exit(1);
   }
   q->front=q->rear=0;    /*初始置队列为空*/
   return;
}
/*2.向队列中插入元素x*/
voidenQueue(structqueue*q,elemTypex)
{
   /*当队列满时进行动态生分配*/
   if((q->rear+1)%q->maxSize==q->front){
     againMalloc(q);
   }
   q->rear=(q->rear+1)%q->maxSize;    /*求出队尾的下一个位置*/
   q->queue[q->rear]=x;            /*把x的值赋给新的队尾*/
   return;
}
/*3.从队列中删除元素并返回*/
elemTypeoutQueue(structqueue*q)
{
   /*若队列为空则终止运行*/
   if(q->front==q->rear){
     printf("队列为空,无法删除! ");
     exit(1);
   }
   q->front=(q->front+1)%q->maxSize;    /*使队首指针指向下一个位置*/
   returnq->queue[q->front];          /*返回队首元素*/
}
/*4.读取队首元素,不改变队列状态*/
elemTypepeekQueue(structqueue*q)
{
   /*若队列为空则终止运行*/
   if(q->front==q->rear){
     printf("队列为空,无法删除! ");
     exit(1);
   }
   returnq->queue[(q->front+1)%q->maxSize];/*队首元素是队首指针的下一个位置中的元素*/
}
/*5.检查一个队列是否为空,若是则返回1,否则返回0*/
intemptyQueue(structqueue*q)
{
   if(q->front==q->rear){
     return1;
   }else{
     return0;
   }
}
/*6.清除一个队列,并释放动态存储空间*/
voidclearQueue(structqueue*q)
{
   if(q->queue!=NULL){
     free(q->queue);
     q->queue=NULL;      /*设置队列空间指针为空*/
     q->front=q->rear=0;    /*设置队列为空*/
     q->maxSize=0;        /*设置队列大小为0*/
;  }
   return;
}
/************************************************************************/
intmain(intargc,char*argv[])
{
   structqueueq;
   inta[8]={3,8,5,17,9,30,15,22};
   inti;
   initQueue(&q,5);
   for(i=0;i<8;i++){
     enQueue(&q,a[i]);
   }
   printf("%d",outQueue(&q));  printf("%d ",outQueue(&q));
   enQueue(&q,68);
   printf("%d",peekQueue(&q));  printf("%d ",outQueue(&q));
   while(!emptyQueue(&q)){
     printf("%d",outQueue(&q));
   }
   printf(" ");
   clearQueue(&q);
   system("pause");
   return0;
}

其它资源
来源声明

版权与免责声明
1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
3、本站部分文章来源于本站原创,本站拥有所有权利。
4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
请参阅权责声明