PTA（栈和队列）1-8 舞伴问题

1-8 舞伴问题

分数 3

作者 张瑞霞

单位 桂林电子科技大学

假设男士和女士的记录存放在一个数组中，设计算法实现舞伴配对，要求输出配对的舞伴，并输出没有配对的队头元素的姓名。

函数接口定义：

1
void DancePartner(DataType dancer[], int num) ;

其中 dancer[]是存放男士和女士信息的数组，num是数组大小。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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 main()
{
    DataType dancer[9];
    for (int i = 0; i < 9; i++)
    scanf("%s %c", dancer[i].name, &dancer[i].sex);
    DancePartner(dancer, 9);
    return 0;
}

输入样例：

在这里给出一组输入。例如：

1
2
3
4
5
6
7
8
9
李敏浩 M
李钟硕 M
高欣雅 F
吴彦祖 M
王思聪 M
张甜源 F
张智霖 M
许丹丹 F
马小云 F

输出样例：

1
2
3
4
5
6
高欣雅 李敏浩
张甜源 李钟硕
许丹丹 吴彦祖
马小云 王思聪

张智霖

  • 观察这个输入输出，发现先输入的男生女生先输出，说明是队列

  • 第一个结构体：观察得知每个人是一个结构体，里面存放了每个人的名字和性别

  • 第二个结构体：还有一个Node结构体，使用的是链式存储结构，每个人相当于一个结点，通过指针相连

  • 第三个结构体：是指向前面链式存储结构的头指针和尾指针，构成了链队列

注意：题目要求输出未配对队头元素

  • 所以最后未匹配的不用while，用if就行

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void DancePartner(DataType dancer[], int num)
{
    // main函数中什么都没有，就是让我调用它的这些函数
    LinkQueue maleQueue;
    LinkQueue femaleQueue;
    maleQueue = SetNullQueue_Link(); // 初始化一个男性空链队列
    femaleQueue = SetNullQueue_Link(); // 初始化一个女性空链队列\

    // 入队列
    for (int i = 0; i < num; ++i) {
        if (dancer[i].sex == 'M') { // 如果是男性
            EnQueue_link(maleQueue, dancer[i]);
        } else {
            EnQueue_link(femaleQueue, dancer[i]);
        }
    }

    // 出队列
    // 如果男性和女性队列有一个为空，直接退出，说明没有一对对的男女了
    while (!IsNullQueue_link(maleQueue) && !IsNullQueue_link(femaleQueue)) {
        DataType female = FrontQueue_link(femaleQueue); // 存下女性队头的信息
        DataType male = FrontQueue_link(maleQueue); // 存下男性队头的信息
        printf("%s %s\n", female.name, male.name);
        DeQueue_link(femaleQueue); // 队头出队
        DeQueue_link(maleQueue); // 队头出队
    }

    //剩余没配对的出队
    printf("\n"); // 依据题目要求，先换行

    // 男性队列里面还有,是输出队头就行，所以不用while
    if (!IsNullQueue_link(maleQueue)) {
        DataType male = FrontQueue_link(maleQueue); // 存下男性队头的信息
        printf("%s\n", male.name);
        DeQueue_link(maleQueue); // 队头出队
    }

    // 女性队列里面还有，是输出队头就行，所以不用while
    if (!IsNullQueue_link(femaleQueue)) {
        DataType female = FrontQueue_link(femaleQueue); // 存下女性队头的信息
        printf("%s\n", female.name);
        DeQueue_link(femaleQueue); // 队头出队
    }
}