|
从循环队列的存储结构的特点我们知道：顺序存储必须分配一块连续的内存，不够灵活，并且还要担心数组越界的问题，链式存储就体现出了它的优势。
链队列初始化：
void InitLinkQueue( LinkQueue *Q )
{
int i ;
QNode *p ;
Q->front = ( QNode * )malloc( sizeof( QNode ) ) ;
Q->rear = Q->front ;
for( i = 0 ; i
QNode *p ;
p = ( QNode * )malloc( sizeof( QNode ) ) ;
p->data = val ;
p->next = NULL ;
Q->rear->next = p ;
Q->rear = p ;
return OK ;
}
队头删除：
Status DeLinkQueue( LinkQueue *Q , int *val )
{
if( Q->front == Q->rear )
return ERROR ;
else
{
QNode *p = Q->front->next ;
*val = p->data ;
if( Q->front->next == Q->rear )
{
Q->rear = Q->front ;
Q->front->next = NULL ;
}
else
Q->front->next = p->next ;
free( p ) ;
}
return OK ;
}
遍历队列：
void TraverLinkQueue( LinkQueue Q )
{
QNode *p = Q.front->next ;
while( p )
{
printf( "%d " , p->data ) ;
p = p->next ;
}
printf( "\n" ) ;
}
取队头结点：
Status GetHead( LinkQueue Q , int *val )
{
if( Q.front == Q.rear )
return ERROR ;
else
{
*val = Q.front->next->data ;
return OK ;
}
}
求队列长度：
int GetLength( LinkQueue Q )
{
int length = 0 ;
QNode *p = Q.front->next ;
while( p )
{
length++ ;
p = p->next ;
}
return length ;
}
清空队列：
Status ClearLinkQueue( LinkQueue *Q )
{
if( !Q )
return ERROR ;
else
{
QNode *p ;
p = Q->front->next ;
Q->rear = Q->front ;
while( p )
{
Q->front->next = p->next ;
free( p ) ;
p = Q->front->next ;
}
return OK ;
}
}
销毁队列：
Status DesLinkQueue( LinkQueue *Q )
{
if( !Q )
return ERROR ;
else
{
while( Q->front )
{
Q->rear = Q->front->next ;
free( Q->front ) ;
Q->front = Q->rear ;
}
return OK ;
}
}
源代码：
#include
#include
#define OK 1
#define ERROR 0
#define QUEUESIZE 5
typedef int Status ;
typedef struct QNode
{
int data ;
struct QNode *next ;
} QNode ;
typedef struct LinkQueue
{
QNode *front , *rear ;
} LinkQueue ;
void InitLinkQueue( LinkQueue *Q ) ;
void TraverLinkQueue( LinkQueue Q ) ;
Status EnLinkQueue( LinkQueue *Q , int val ) ;
Status DeLinkQueue( LinkQueue *Q , int *val ) ;
Status ClearLinkQueue( LinkQueue *Q ) ;
Status DesLinkQueue( LinkQueue *Q ) ;
Status GetHead( LinkQueue Q , int *val ) ;
int GetLength( LinkQueue Q ) ;
int main( void )
{
int val ;
LinkQueue Q ;
printf( "将要建立结点数为 < %d > 的链队列\n" , QUEUESIZE ) ;
InitLinkQueue( &Q ) ;
printf( "遍历刚生成的链队列：\n" ) ;
TraverLinkQueue( Q ) ; printf( "\n" ) ;
EnLinkQueue( &Q , -99 ) ;
printf( "从队列尾结点插入一个元素后再遍历链队列：\n" ) ;
TraverLinkQueue( Q ) ; printf( "\n" ) ;
DeLinkQueue( &Q , &val ) ;
printf( "删除队列头节点元素后再遍历链队列：\n" ) ;
TraverLinkQueue( Q ) ; printf( "\n" ) ;
GetHead( Q , &val ) ;
printf( "队列的头节点元素是：%d\n" , val ) ; printf( "\n" ) ;
printf( "经过一系列操作后，现在链队列的长度为：%d\n" , GetLength( Q ) ) ;
DesLinkQueue( &Q ) ;
return 0 ;
}
void InitLinkQueue( LinkQueue *Q )
{
int i ;
QNode *p ;
Q->front = ( QNode * )malloc( sizeof( QNode ) ) ;
Q->rear = Q->front ;
for( i = 0 ; i
QNode *p = Q.front->next ;
while( p )
{
printf( "%d " , p->data ) ;
p = p->next ;
}
printf( "\n" ) ;
}
Status EnLinkQueue( LinkQueue *Q , int val )
{
QNode *p ;
p = ( QNode * )malloc( sizeof( QNode ) ) ;
p->data = val ;
p->next = NULL ;
Q->rear->next = p ;
Q->rear = p ;
return OK ;
}
Status DeLinkQueue( LinkQueue *Q , int *val )
{
if( Q->front == Q->rear )
return ERROR ;
else
{
QNode *p = Q->front->next ;
*val = p->data ;
if( Q->front->next == Q->rear )
{
Q->rear = Q->front ;
Q->front->next = NULL ;
}
else
Q->front->next = p->next ;
free( p ) ;
}
return OK ;
}
Status ClearLinkQueue( LinkQueue *Q )
{
if( !Q )
return ERROR ;
else
{
QNode *p ;
p = Q->front->next ;
Q->rear = Q->front ;
while( p )
{
Q->front->next = p->next ;
free( p ) ;
p = Q->front->next ;
}
return OK ;
}
}
Status DesLinkQueue( LinkQueue *Q )
{
if( !Q )
return ERROR ;
else
{
while( Q->front )
{
Q->rear = Q->front->next ;
free( Q->front ) ;
Q->front = Q->rear ;
}
return OK ;
}
}
int GetLength( LinkQueue Q )
{
int length = 0 ;
QNode *p = Q.front->next ;
while( p )
{
length++ ;
p = p->next ;
}
return length ;
}
Status GetHead( LinkQueue Q , int *val )
{
if( Q.front == Q.rear )
return ERROR ;
else
{
*val = Q.front->next->data ;
return OK ;
}
}
|