反向链式队列
头文件 reLink.h
#include <stdio.h>
#include <stdlib.h>
//反向链式队列
struct node
{
int data;
struct node *pNext;
};
void init(struct node **ppNext);
struct node * enqueue(struct node *p, int newData);
struct node * dequeue(struct node *p,int *pOut);
void show(struct node *p);主体 reLink.c
#include "reLink.h"
void init(struct node **ppNext) //初始化队列
{
*ppNext = NULL;
}
struct node * enqueue(struct node *p, int newData) //进队
{
struct node *pNew = malloc(sizeof(struct node)); //给节点分配内存
pNew->data = newData; //将数据放入节点上
pNew->pNext = NULL;
if (p == NULL) //队列为空
{
p = pNew;
return p;
}
else //不为空
{
pNew->pNext = p; //插入到头部节点
p = pNew;
return p;
}
}
struct node * dequeue(struct node *p, int *pOut) //出队
{
if (p == NULL) //为空时,直接返回
{
return NULL;
}
else if (p->pNext == NULL) //只有一个节点时
{
*pOut = p->data; //出队,将节点的数据指向pOut
free(p);
p = NULL;
return p;
}
else //多个节点时
{
struct node *pTemp = p; //声明一个节点指针
while (pTemp->pNext->pNext != NULL) //通过pTemp->pNext->pNext判断是不是最后的节点
{
pTemp = pTemp->pNext;
}
*pOut = pTemp->pNext->data;
pTemp->pNext = NULL; //出队,将节点的pNext为空
free(pTemp->pNext);
return p;
}
}
void show(struct node *p) //打印队列中数据
{
if (p == NULL)
{
return;
}
else
{
printf("%4d", p->data);
show(p->pNext); //递归调用
}
}
int main(int argc, char *argv[])
{
struct node *pHead;
init(&pHead);
for (int i = 0; i < 10; i++)
{
pHead = enqueue(pHead, i);
printf("\n");
show(pHead);
}
while (pHead != NULL)
{
int num;
pHead = dequeue(pHead, &num);
printf("\n dequeue is %4d", num);
printf("\n");
show(pHead);
}
system("pause");
return 0;
}
秋风
2016-07-05