数据结构C语言实现系列介绍
#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;
}