链表队列很简单,之前看到过,没有用程序实现。其原理就是遵循FIFO原则,只能从队首取元素,从队尾插入元素,就和排队模型一样。因此只需要队首指针和队尾指针就可以方便的进行队列操作。因为在最近看的图论算法中,经常用到队列,在这里就先用程序实现链表队列。
和单链表一样,为了运算方便,我们也在队头节点前附加一个头结点,且头指针指向头结点。其链表队列的示意图如下:
下面是具体的程序实现:
#include<stdio.h> #include<stdlib.h> typedef struct node//定义节点的结构体 { int data; struct node *next; }linklist; typedef struct//定义链表 { linklist *front,*rear;//定义指向节点的头尾指针 }linkqueue; void SetNull(linkqueue *q)//置空队列(含空的头节点,便于处理) { q->front=(linklist *)malloc(sizeof(linklist)); q->front->next=NULL; q->rear=q->front; } int Empty(linkqueue *q)//判断队列是否为空 { if(q->front==q->rear) return 1; else return 0; } int Front(linkqueue *q)//取出队列的头元素 { if(Empty(q)) { printf("queue is empty!"); return -1; } else return q->front->next->data;//注意有头指针,该指针的下个元素才是第一个元素 } void ENqueue(linkqueue *q,int x)//进队列 { linklist * newnode=(linklist *)malloc(sizeof(linklist)); q->rear->next=newnode; q->rear=newnode; q->rear->data=x; q->rear->next=NULL; } int DEqueue(linkqueue *q)//出队列 { int temp; linklist *s; if(Empty(q)) { printf("queue is empty!"); return -1; } else { s=q->front->next; if(s->next==NULL) { q->front->next=NULL; q->rear=q->front; } else q->front->next=s->next; temp=s->data; return temp; } } void main() { linkqueue q;//这里是产生队列q,而不是产生指向队列的指正,是为了方便初始化。 //如果为指针的话,必须初始化,则头尾指针无法初始化。 SetNull(&q);//相当于初始化 ENqueue(&q,2);//将关键字2入队 ENqueue(&q,3);//将关键字3入队 ENqueue(&q,4);//将关键字4入队 DEqueue(&q);//将关键字2出队 DEqueue(&q);//将关键字3出队 int a=0; a=Front(&q);//取队头元素 printf("%d\n",a); }
注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明
原文:http://blog.csdn.net/tengweitw/article/details/17170743
作者:nineheadedbird
时间: 2024-10-29 11:59:51