利用链队列解决舞伴配对问题，c语言实现

不念不忘少年蓝@ 2022-12-17 04:25 237阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center 1]  
基本思路  
① 初始化Mdancers队列和Fdancers队列。  
② 反复循环，依次将跳舞者根据其性别插入Mdancers队列或Fdancers队列。  
③ 当Mdancers队列和Fdancers队列均为非空时，反复循环，依次输出男女舞伴的姓名。  
④ 如果Fdancers队列非空，则输出Fdancers队列的队头女士的姓名。  
⑤ 如果Mdancers队列非空，则输出Mdancers队列的队头男士的姓名。

代码及注释如下

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct
    { 
    	char name[20];
    	char sex;
    } DataType;
    
    struct Node { 
    	DataType	  data;
    	struct Node*  next;
    };
    typedef struct Node  *PNode;
    struct Queue
    { 
    	PNode		f;
    	PNode		r;
    };
    typedef struct Queue *LinkQueue;
    LinkQueue  SetNullQueue_Link()
    { 
    	LinkQueue lqueue;
    	lqueue = (LinkQueue)malloc(sizeof(struct Queue));
    	if (lqueue != NULL)
    	{ 
    		lqueue->f = NULL;
    		lqueue->r = NULL;
    	}
    	else
    		printf("Alloc failure! \n");
    	return  lqueue;
    }
    
    int IsNullQueue_link(LinkQueue lqueue)
    { 
    	return (lqueue->f == NULL);
    }
    
    void EnQueue_link(LinkQueue lqueue, DataType x)
    { 
    	PNode  p;
    	p = (PNode)malloc(sizeof(struct Node));
    	if (p == NULL)
    		printf("Alloc failure!");
    	else { 
    		p->data = x;
    		p->next = NULL;
    		if (lqueue->f == NULL)
    		{ 
    			lqueue->f = p;
    			lqueue->r = p;
    		}
    		else
    		{ 
    			lqueue->r->next = p;
    			lqueue->r = p;
    		}
    	}
    }
    void DeQueue_link(LinkQueue lqueue)
    { 
    	struct Node  * p;
    	if (lqueue->f == NULL)
    		printf("It is empty queue!\n ");
    	else
    	{ 
    		p = lqueue->f;
    		lqueue->f = lqueue->f->next;
    		free(p);
    	}
    }
    DataType  FrontQueue_link(LinkQueue lqueue)
    { 
    	if (lqueue->f == NULL)
    	{ 
    		printf("It is empty queue!\n");
    	}
    	else
    		return (lqueue->f->data);
    }
    
    void DancePartner(DataType dancer[], int num)
    { 
        int i;
       LinkQueue Mdancers=SetNullQueue_Link();
       LinkQueue Fdancers=SetNullQueue_Link();
      for (i = 0; i < num; i++)
      { 
          if(dancer[i].sex=='M')
          { 
              EnQueue_link(Mdancers,dancer[i]);
          }
          if(dancer[i].sex=='F')
          { 
              EnQueue_link(Fdancers,dancer[i]);
          }
      }
       while(!IsNullQueue_link(Mdancers)&&!IsNullQueue_link(Fdancers))
          { 
              printf("%s %s\n",FrontQueue_link(Fdancers).name,FrontQueue_link(Mdancers).name);
              DeQueue_link(Mdancers);
              DeQueue_link(Fdancers);
          }
          printf("\n");
          if(!IsNullQueue_link(Mdancers))
            printf("%s\n",FrontQueue_link(Mdancers).name);
          else
          printf("%s\n",FrontQueue_link(Fdancers).name);
    }
    
    int main()
    { 
        int i;
    	DataType dancer[9];
    	for( i = 0; i < 9; i++)
    	scanf("%s %c", dancer[i].name, &dancer[i].sex);
    	DancePartner(dancer, 9);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0a3fecb6b57a4b1aa636984a9480d3c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/19368f54e54e4e6ea8510d8a300983df.png