【数据结构】——【队列】算法代码实现（C/C++语言实现）（整理不易，请多关注）

目录

1.队列的顺序表示：类型和函数声明

2.队列的顺序表示：函数定义

3.队列链接表示：类型和界面函数声明

4.队列链接表示：函数定义

5.用队列解决农夫过河问题的算法

1.队列的顺序表示：类型和函数声明

typedef int DataType;
#define MAXNUM 20  

struct  SeqQueue 
{       
    int f, r;
    DataType q[MAXNUM];
};

typedef struct SeqQueue SeqQueue, *PSeqQueue; 


PSeqQueue createEmptyQueue_seq( void );


int isEmptyQueue_seq( PSeqQueue paqu );


void enQueue_seq( PSeqQueue paqu, DataType x );


void deQueue_seq( PSeqQueue paqu );


DataType frontQueue_seq( PSeqQueue paqu );

2.队列的顺序表示：函数定义

#include 
#include 

#include "squeue.h"


PSeqQueue  createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu==NULL)
        printf("Out of space!! n");
    else
        paqu->f = paqu->r = 0;
    return paqu;
}


int  isEmptyQueue_seq( PSeqQueue paqu ) 
{
    return paqu->f == paqu->r;
}


void  enQueue_seq( PSeqQueue paqu, DataType x ) 
{
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.n" );
    else       {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}


void  deQueue_seq( PSeqQueue paqu ) 
{
    if( paqu->f == paqu->r )
        printf( "Empty Queue.n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}


DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return paqu->q[paqu->f];
}

3.队列链接表示：类型和界面函数声明

typedef int DataType;
struct  Node;
typedef  struct Node *PNode;

struct  Node 
{              
    DataType    info;
    PNode       link;
};

struct  LinkQueue 
{        
    PNode  f;          
    PNode  r;          
};

typedef struct LinkQueue *PLinkQueue;


PLinkQueue  createEmptyQueue_link( );

 
int  isEmptyQueue_link( PLinkQueue plqu );


void  enQueue_link( PLinkQueue plqu, DataType x);


void  deQueue_link( PLinkQueue plqu );


DataType  frontQueue_link( PLinkQueue plqu );

4.队列链接表示：函数定义

#include
#include

#include "lqueue.h"


PLinkQueue  createEmptyQueue_link( ) 
{       
    PLinkQueue plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue));
    if (plqu != NULL)
        plqu->f = plqu->r = NULL;
    else
        printf("Out of space!! n");
               
    return (plqu);
}

 
int  isEmptyQueue_link( PLinkQueue plqu ) 
{
    return (plqu->f == NULL);
}



void  enQueue_link( PLinkQueue plqu, DataType x) 
{ 
    PNode p = (PNode )malloc( sizeof( struct Node ) );
    if ( p == NULL  )
        printf("Out of space!");
    else { 
        p->info = x;
        p->link = NULL;
        if (plqu->f == NULL)
            plqu->f = p;
        else
            plqu->r->link = p;

        plqu->r = p;
    }
}


void  deQueue_link( PLinkQueue plqu ) 
{ 
    PNode   p;
    if( plqu->f == NULL )
        printf( "Empty queue.n " );
    else { 
        p = plqu->f;
        plqu->f = plqu->f->link;
        free(p);
    }
}


DataType  frontQueue_link( PLinkQueue plqu ) 
{ 
    return (plqu->f->info);
}

5.用队列解决农夫过河问题的算法

#include
#include

#define  MAXNUM   20

typedef int DataType;
struct  SeqQueue 
{              
    int  f, r;
    DataType q[MAXNUM];
};

typedef struct SeqQueue *PSeqQueue;   

PSeqQueue createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! n");
    else
        paqu->f = paqu->r = 0;
    return (paqu);
}

int isEmptyQueue_seq( PSeqQueue paqu ) 
{
    return paqu->f == paqu->r;
}


void  enQueue_seq( PSeqQueue paqu, DataType x ) 
{
    if ( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}


void  deQueue_seq( PSeqQueue paqu ) 
{
    if( paqu->f == paqu->r )
        printf( "Empty Queue.n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}


DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return (paqu->q[paqu->f]);
}

int farmer(int location) 
{
    return 0 != (location & 0x08);
}

int wolf(int location) 
{
    return 0 != (location & 0x04);
}

int cabbage(int location) 
{
    return 0 != (location & 0x02);
}

int goat(int location) 
{
    return 0 !=(location & 0x01);
}


int safe(int location) 
{
    
    if ((goat(location) == cabbage(location)) &&  
          (goat(location) != farmer(location)) )  
        return 0;
    
    if ((goat(location) == wolf(location)) &&  
          (goat(location) != farmer(location)))  
        return 0;
    return 1;   
}


void farmerProblem( ) 
{
    int movers, i, location, newlocation;
    int route[16];        
    PSeqQueue moveTo; 
    
    moveTo = createEmptyQueue_seq( );
    enQueue_seq(moveTo, 0x00);
    for (i = 0; i < 16; i++) route[i] = -1;
    route[0]=0;
    
    
while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1)) 
{
        
        location = frontQueue_seq(moveTo);
        deQueue_seq(moveTo);
        for (movers = 1; movers <= 8; movers <<= 1) 
{
            
            if ((0 != (location & 0x08)) == (0 != (location & movers))) {
                newlocation = location^(0x08|movers);
                if (safe(newlocation) && (route[newlocation] == -1)) 
{ 
                    route[newlocation] = location;
                    enQueue_seq(moveTo, newlocation);
                }
            }
        }
    }
    
    
if(route[15] != -1) 
{
        printf("The reverse path is : n");
        for(location = 15; location >= 0; location = route[location]) 
{ 
            printf("The location is : %dn",location);
            if (location == 0) return;
        }
    }
    else 
        printf("No solution.n");
}


int main() 
{
    farmerProblem( );
    return 0;
}