C语言创建链队列,并实现初始化、遍历、插入、删除、销毁等基本操作。

  • 时间:
  • 来源:互联网
  • 文章标签:

从循环队列的存储结构的特点我们知道:顺序存储必须分配一块连续的内存,不够灵活,并且还要担心数组越界的问题,链式存储就体现出了它的优势。

链队列初始化:

void InitLinkQueue( LinkQueue *Q )
{
    int i ;
    QNode *p ;
    Q->front = ( QNode * )malloc( sizeof( QNode ) ) ;
    Q->rear = Q->front ;

    for( i = 0 ; i < QUEUESIZE ; i++ )
    {
        p = ( QNode * )malloc( sizeof( QNode ) * QUEUESIZE ) ;
        printf( "请输入第%d个结点的值:" , i+1 ) ;
        scanf( "%d" , &p->data ) ;

        Q->rear->next = p ;
        Q->rear = p ;
    }
    Q->rear->next = NULL ;
}

队尾插入:

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 ;
}

遍历队列:

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<stdio.h>
#include<stdlib.h>
#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 < QUEUESIZE ; i++ )
    {
        p = ( QNode * )malloc( sizeof( QNode ) * QUEUESIZE ) ;
        printf( "请输入第%d个结点的值:" , i+1 ) ;
        scanf( "%d" , &p->data ) ;

        Q->rear->next = p ;
        Q->rear = p ;
    }
    Q->rear->next = NULL ;
}

void TraverLinkQueue( LinkQueue Q )
{
    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 ;
    }
}

本文链接http://www.taodudu.cc/news/show-83215.html