算法导论 10.2-3

浏览数：17 / 时间：2015年06月08日

题目：使用单链表实现队列，Enqueue与Dequeue操作时间为O(1)

代码：

struct Node;
struct QueueRecord;
typedef struct Node * PtrToNode;
typedef struct QueueRecord * Queue;

struct Node
{
    ElementType Element;
    PtrToNode Next;
};

struct QueueRecord
{
    PtrToNode Front;
    PtrToNode Rear;
};

Queue CreateQueue( );
void DisposeQueue( Queue Q );
int IsEmpty( Queue Q );
void MakeEmpty( Queue Q );
void Enqueue( ElementType X, Queue Q );
void Dequeue( Queue Q );
ElementType Front( Queue Q );
ElementType FrontAndDequeue( Queue Q );

Queue CreateQueue()
{
    Queue Q;

    Q = (Queue) malloc( sizeof( struct QueueRecord ) );
    if ( NULL == Q )
    {
        printf( "Out of Space!!!" );
        return NULL;
    }

    // 链表栈中含有头结点
    Q->Front = Q->Rear = ( PtrToNode ) malloc( sizeof( struct QueueRecord ) );
    if ( Q->Front == NULL )
    {
        printf( "Out of space!!!" );
        return NULL;
    }

    Q->Front->Next = NULL;
    return Q;
}

void DisposeQueue( Queue Q )
{
    while( !IsEmpty(Q) )
        Dequeue( Q );

    free( Q->Front );
    free( Q );
}

void Enqueue( ElementType X, Queue Q )
{
    PtrToNode TmpCell;

    TmpCell = (PtrToNode) malloc( sizeof( struct Node ) );
    if ( TmpCell == NULL )
    {
        printf("Out of space!!!");
        return;
    }
    else
    {
        TmpCell->Element = X;
        TmpCell->Next = NULL;
        Q->Rear->Next = TmpCell;
        Q->Rear = TmpCell;
    }
}

void Dequeue( Queue Q )
{
    if ( IsEmpty(Q) )
    {
        printf( "Out of space!!!" );
        return;
    }
    else
    {
        PtrToNode TmpCell;

        TmpCell = Q->Front->Next;
        Q->Front->Next = TmpCell->Next;
        if ( Q->Rear == TmpCell )
            Q->Rear = Q->Front;
        free( TmpCell );
    }
}

int IsEmpty( Queue Q )
{
    return Q->Front->Next == NULL;
}

void MakeEmpty( Queue Q )
{
    if ( Q == NULL )
    {
        printf( "Must creat queue first!" );
        return;
    }
    
    while ( !IsEmpty(Q) )
        Dequeue( Q );
}

ElementType Front( Queue Q )
{
    if ( IsEmpty(Q) )
    {
        printf( "Empty Queue" );
        return 0;
    }
    else
        return Q->Front->Next->Element;
}

ElementType FrontAndDequeue( Queue Q )
{
    ElementType TmpCell;

    if ( IsEmpty(Q) )
    {
        printf( "Empty Queue" );
        return 0;        
    }
    else
    {
        TmpCell = Front( Q );
        Dequeue( Q );
        return TmpCell;
    }
}