数据结构舞伴问题c语言

舞伴问题是一种经典的数据结构问题，可以用C语言来实现。以下是一个简单的实现，包括创建舞者队列、分别创建男女队列、从队列中依次将队首元素出队并判断其性别，并添加至男女队列中。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAME_LEN 20

// 舞者结构体
typedef struct Dancer {
    char name[MAX_NAME_LEN]; // 姓名
    char sex; // 性别
    int age; // 年龄
    struct Dancer *next; // 指向下一个舞者的指针
} Dancer;

// 队列结构体
typedef struct Queue {
    Dancer *front; // 队首指针
    Dancer *rear; // 队尾指针
    int size; // 队列大小
} Queue;

// 初始化队列
void initQueue(Queue *queue) {
    queue->front = queue->rear = NULL;
    queue->size = 0;
}

// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
    return queue->size == 0;
}

// 入队
void enqueue(Queue *queue, Dancer *dancer) {
    if (isQueueEmpty(queue)) {
        queue->front = dancer;
    } else {
        queue->rear->next = dancer;
    }
    queue->rear = dancer;
    dancer->next = NULL;
    queue->size++;
}

// 出队
Dancer *dequeue(Queue *queue) {
    if (isQueueEmpty(queue)) {
        return NULL;
    }
    Dancer *dancer = queue->front;
    queue->front = dancer->next;
    queue->size--;
    return dancer;
}

// 创建舞者队列
void createDancerQueue(Queue *queue) {
    int n;
    printf("请输入舞者人数：");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        Dancer *dancer = (Dancer *)malloc(sizeof(Dancer));
        printf("请输入第%d个舞者的姓名、性别和年龄：", i + 1);
        scanf("%s %c %d", dancer->name, &dancer->sex, &dancer->age);
        enqueue(queue, dancer);
    }
}

// 创建男女队列
void createMaleFemaleQueue(Queue *maleQueue, Queue *femaleQueue, Queue *dancerQueue) {
    while (!isQueueEmpty(dancerQueue)) {
        Dancer *dancer = dequeue(dancerQueue);
        if (dancer->sex == 'M') {
            enqueue(maleQueue, dancer);
        } else {
            enqueue(femaleQueue, dancer);
        }
    }
}

// 匹配舞伴
void matchDancers(Queue *maleQueue, Queue *femaleQueue) {
    while (!isQueueEmpty(maleQueue) && !isQueueEmpty(femaleQueue)) {
        Dancer *maleDancer = dequeue(maleQueue);
        Dancer *femaleDancer = dequeue(femaleQueue);
        printf("%s和%s配对跳舞\n", maleDancer->name, femaleDancer->name);
        free(maleDancer);
        free(femaleDancer);
    }
}

int main() {
    Queue dancerQueue, maleQueue, femaleQueue;
    initQueue(&dancerQueue);
    initQueue(&maleQueue);
    initQueue(&femaleQueue);
    createDancerQueue(&dancerQueue);
    createMaleFemaleQueue(&maleQueue, &femaleQueue, &dancerQueue);
    matchDancers(&maleQueue, &femaleQueue);
    if (!isQueueEmpty(&maleQueue)) {
        printf("男队还有%d人等待下一轮舞曲\n", maleQueue.size);
    }
    if (!isQueueEmpty(&femaleQueue)) {
        printf("女队还有%d人等待下一轮舞曲\n", femaleQueue.size);
    }
    return 0;
}