1-5 带头结点的链队列的基本操作

分数 4

作者黄复贤

单位菏泽学院

实现链队列的入队列及出队列操作。

函数接口定义：

Status QueueInsert(LinkQueue *Q,ElemType e)；

Status QueueDelete(LinkQueue *Q,ElemType *e)；

其中 Q 和 e 都是用户传入的参数。 LinkQueue 的类型定义如下：

typedef int ElemType; 
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LNode,*LinkList;
typedef struct
 {
   LinkList front,rear; /* 队头、队尾指针 */
 }LinkQueue;

裁判测试程序样例：

#include <stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType; 
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
}LNode,*LinkList;

typedef struct
 {
   LinkList front,rear; /* 队头、队尾指针 */
 }LinkQueue;
 /* 带头结点的链队列的基本操作 */
 Status InitQueue(LinkQueue *Q)
 { /* 构造一个空队列Q */
     LinkList p;
   p=(LNode*)malloc(sizeof(LNode)); 
   p->next=NULL;
   (*Q).rear=(*Q).front=p;
   return OK;
 }
Status List(LinkList L)
{
    LinkList p;
    if(!L) return ERROR;
    p=L->next;
    
    while(p)
    {
        printf(" %d",p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

int QueueLenth(LinkQueue Q)
{
    int n=0;
    LinkList p;
    if(Q.rear==Q.front)
        return 0;
    p=Q.front->next;
    while(p)
    {
        n++;
        p=p->next;
    }
    return n;
}

int main()
{
    int x;
    LinkQueue Q;
    InitQueue(&Q);
    QueueInsert(&Q,1);QueueInsert(&Q,2);QueueInsert(&Q,3);
    List(Q.front );
    QueueDelete( &Q,&x);
    printf(" %d %d\n",x,QueueLenth(Q));
    QueueDelete(&Q,&x);QueueDelete(&Q,&x);
    printf(" %d %d\n",x,QueueLenth(Q));
    return 0;
}

/* 请在这里填写答案 */

输出样例：

在这里给出相应的输出。例如：

1 2 3
1 2
3 0

解析

Status QueueInsert(LinkQueue* Q, ElemType e) {
    LinkList p = (LNode*)malloc(sizeof(LNode));
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

Status QueueDelete(LinkQueue* Q, ElemType* e) {
    if (Q->front == Q->rear) {
        return ERROR;
    }
    LinkList p = (LNode*)malloc(sizeof(LNode));
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    return OK;
}

1-6 循环队列入队出队

分数 4

作者张瑞霞

单位桂林电子科技大学

本题要求实现队列的顺序存储表示，包括入队、出队和取队头操作

函数接口定义：

void EnQueue_seq(SeqQueue squeue, DataType x)  ;
void DeQueue_seq(SeqQueue squeue)  ;
DataType FrontQueue_seq(SeqQueue squeue) ;

其中，squeue 是操作的队列，x是入队的元素

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
struct Queue
{
    int Max;  
    int f;   
    int r;  
    DataType *elem; 
};
typedef struct Queue *SeqQueue;

SeqQueue SetNullQueue_seq(int m) 
{
    SeqQueue squeue;
    squeue = (SeqQueue)malloc(sizeof(struct Queue));
    if (squeue == NULL)
    {
        printf("Alloc failure\n");
        return NULL;
    }
    squeue->elem = (char*)malloc(sizeof(DataType)*m);
    if (squeue->elem != NULL)
    {
        squeue->Max = m;
        squeue->f = 0;
        squeue->r = 0;
        return squeue;
    }
}

int IsNullQueue_seq(SeqQueue squeue) 
{
    return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue, DataType x)  
{
    @@
}
void DeQueue_seq(SeqQueue squeue)  
{
    @@
}
DataType FrontQueue_seq(SeqQueue squeue) 
{
    @@
}

int main()
{
    char ch;
    SeqQueue queueA = SetNullQueue_seq(5);
    ch = getchar();
    while (ch != '#')
    {
        EnQueue_seq(queueA, ch);
        ch = getchar();
    }
    DeQueue_seq(queueA);
    printf("%c" ,FrontQueue_seq(queueA));
    return 0;
}

输入样例：

ABCD#

输出样例：

输入样例：

A#

输出样例：

It is empty queue!

输入样例：

ABCDEF#

输出样例：

It is FULL Queue!It is FULL Queue!B

解析

void EnQueue_seq(SeqQueue squeue, DataType x) {
    if ((squeue->r + 1) % squeue->Max == squeue->f) {
        printf("It is FULL Queue!");
        return;
    }
    squeue->elem[squeue->r] = x;
    squeue->r = (squeue->r + 1) % squeue->Max;
    return;
}
void DeQueue_seq(SeqQueue squeue) {
    if (squeue->f == squeue->r) {
        return;
    }
    squeue->f = (squeue->f + 1) % squeue->Max;
}
DataType FrontQueue_seq(SeqQueue squeue) {
    if (squeue->f == squeue->r) {
        printf("It is empty queue!");
        return '\0';
    }
    char n = squeue->elem[squeue->f];
    return n;
}

注意

这个循环队列是留了一个位置当作队列满的判断的

return '\0'; // 空队列：返回合法char值（避免未定义行为）

1-7 另类循环队列

分数 4

作者 DS课程组

单位浙江大学

如果用一个循环数组表示队列，并且只设队列头指针Front，不设尾指针Rear，而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。

函数接口定义：

bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );

其中Queue结构定义如下：

typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存储元素的数组   */
    Position Front;     /* 队列的头指针     */
    int Count;          /* 队列中元素个数   */
    int MaxSize;        /* 队列最大容量     */
};
typedef PtrToQNode Queue;

注意：如果队列已满，AddQ函数必须输出“Queue Full”并且返回false；如果队列是空的，则DeleteQ函数必须输出“Queue Empty”，并且返回ERROR。

裁判测试程序样例：

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

#define ERROR -1
typedef int ElementType;
typedef enum { addq, delq, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;  /* 存储元素的数组   */
    Position Front;     /* 队列的头、尾指针 */
    int Count;          /* 队列中元素个数   */
    int MaxSize;        /* 队列最大容量     */
};
typedef PtrToQNode Queue; 

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = 0;
    Q->Count = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

bool AddQ( Queue Q, ElementType X );
ElementType DeleteQ( Queue Q );

Operation GetOp();  /* 裁判实现，细节不表 */

int main()
{
    ElementType X;
    Queue Q;
    int N, done = 0;

    scanf("%d", &N);
    Q = CreateQueue(N);
    while ( !done ) {
        switch( GetOp() ) {
        case addq: 
            scanf("%d", &X);
            AddQ(Q, X);
            break;
        case delq:
            X = DeleteQ(Q);
            if ( X!=ERROR ) printf("%d is out\n", X);
            break;
        case end:
            while (Q->Count) printf("%d ", DeleteQ(Q));
            done = 1;
            break;
        }
    }
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

4
Del
Add 5
Add 4
Add 3
Del
Del
Add 2
Add 1
Add 0
Add 10
End

输出样例：

Queue Empty
5 is out
4 is out
Queue Full
3 2 1 0

作者的第一次代码

bool AddQ(Queue Q, ElementType X) {
    if (Q->Count == Q->MaxSize) {
        printf("Queue Full\n");
        return false;
    }
    Q->Data[Q->Count] = X;
    Q->Count++;
    return 1;
}
ElementType DeleteQ(Queue Q) {
    if (Q->Count == 0) {
        printf("Queue Empty\n");
        return ERROR;
    }
    int n = Q->Data[Q->Count - 1];
    Q->Count--;
    return n;
}

你的代码未正确理解 “另类循环队列” 的核心逻辑，存在 2 处根本性错误，导致队列不符合 “先进先出（FIFO）” 特性，且与测试用例预期完全不符。以下是具体问题分析及修正方案：

一、核心问题：混淆 “队列逻辑” 与 “普通数组”，违背 FIFO 原则

循环队列的本质是 “先进先出”（先入队的元素先出队），但你的代码实际实现的是 “栈”（后入队的元素先出队），完全偏离队列逻辑。具体问题如下：

问题 1：`AddQ`（入队）错误存储元素位置

你的入队逻辑是：Q->Data[Q->Count] = X，即 “将新元素存在Count下标处，然后Count自增”。

看似合理，但忽略了循环队列的 “尾指针” 计算逻辑：由于队列仅存Front（队头指针）和Count（元素个数），

队尾位置需通过 “(Front + Count) % MaxSize” 计算（而非直接用Count作为下标）。
错误后果：若队列发生过出队操作（Front移动），新元素会覆盖已出队的位置，导致数据混乱。

示例：假设MaxSize=4，入队5、4、3后Count=3，出队 1 次（Front从 0→1，Count=2），再入队2：

你的代码会将2存在Data[2]（Count=2），但此时队尾实际应为(1+2)%4=3，正确位置是Data[3]，你的存储位置完全错误。

问题 2：`DeleteQ`（出队）错误获取元素，违背 FIFO

你的出队逻辑是：int n = Q->Data[Q->Count - 1]，即 “取Count-1下标处的元素（最后入队的元素），然后Count自减”。

这是 栈的 “弹出” 逻辑，而非队列的 “出队” 逻辑！队列应取 “队头元素”（Data[Front]），而非 “队尾元素”。
错误后果：先入队的元素无法优先出队，与测试用例预期完全冲突（如输入样例中5先入队，应先出队，但你的代码会先出队3）。

二、次要问题：`AddQ`返回值不规范（虽不影响功能，但不符合 C 语言编码习惯）

你的AddQ函数返回1，但函数声明返回bool类型（true/false）。C 语言中bool的标准值是true（本质是1）和false（本质是0），虽1能被识别为true，但建议显式返回true，增强代码可读性。

修正后的完整代码（符合循环队列 FIFO 逻辑）

核心思路：

入队时：通过(Front + Count) % MaxSize计算队尾位置，将元素存在队尾，再Count++；
出队时：取队头位置（Front） 的元素，再将Front循环移动（Front = (Front + 1) % MaxSize），最后Count--。

解析

bool AddQ(Queue Q, ElementType X) {
    if (Q->Count == Q->MaxSize) {
        printf("Queue Full\n");
        return false;
    }
    Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X;
    Q->Count++;
    return 1;
}
ElementType DeleteQ(Queue Q) {
    if (Q->Count == 0) {
        printf("Queue Empty\n");
        return ERROR;
    }
    int n = Q->Data[Q->Front];
    Q->Count--;
    Q->Front = (Q->Front + 1) % Q->MaxSize;
    return n;
}

1-8 舞伴问题

分数 3

作者张瑞霞

单位桂林电子科技大学

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

函数接口定义：

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

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

裁判测试程序样例：

#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;
}

输入样例：

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

李敏浩 M
李钟硕 M
高欣雅 F
吴彦祖 M
王思聪 M
张甜源 F
张智霖 M
许丹丹 F
马小云 F

输出样例：

高欣雅 李敏浩
张甜源 李钟硕
许丹丹 吴彦祖
马小云 王思聪

张智霖

题目分析

题目分析：舞伴问题的核心需求

题目要求将一组包含男士（‘M’）和女士（‘F’）的舞者数组进行配对，规则是：

男士和女士一一配对，输出每对舞伴的姓名；
当某一性别舞者耗尽后，输出剩余未配对舞者中队头元素的姓名（即剩余队列中第一个未配对的人）。

核心逻辑依赖队列的 “先进先出（FIFO）” 特性：舞者按输入顺序入队，配对时按入队顺序依次取出，确保先到的舞者优先配对。

题目中使用的队列结构：链队列（Linked Queue）

从裁判程序给出的代码可以看出，这里的队列是链队列，其结构定义和核心操作如下：

1. 链队列的结构组成

节点（struct Node）：存储单个元素（舞者信息DataType）和指向下一节点的指针（next）。

struct Node {
    DataType data;       // 存储舞者信息（姓名、性别）
    struct Node* next;   // 指向后续节点的指针
};

队列（struct Queue）：包含两个指针，分别指向队头（f）和队尾（r），用于快速执行入队、出队操作。

struct Queue {
    PNode f;  // 队头指针：指向队列中第一个元素
    PNode r;  // 队尾指针：指向队列中最后一个元素
};

2. 链队列的核心操作（裁判程序已实现）

初始化空队列（SetNullQueue_Link）：创建队列结构体，初始化队头（f）和队尾（r）均为NULL。
判空（IsNullQueue_link）：通过判断队头指针（f）是否为NULL，确定队列是否为空。
入队（EnQueue_link）：在队尾插入新节点（若队列为空，队头和队尾均指向新节点；否则，新节点接在队尾后，更新队尾指针）。
出队（DeQueue_link）：删除队头节点（更新队头指针为下一个节点，释放原队头节点的内存）。
取队头元素（FrontQueue_link）：返回队头节点存储的元素（f->data）。

3. 链队列的特点（为何适合本题）

动态扩容：无需预先指定大小，可根据舞者数量动态分配节点，适合处理输入规模不固定的场景（本题输入样例为 9 人，实际可更多）。
FIFO 特性：入队顺序与出队顺序一致，确保先输入的舞者优先配对，符合题目中 “按顺序配对” 的隐含要求（如输入样例中男士按 “李敏浩→李钟硕→吴彦祖→…” 顺序入队，配对时也按此顺序与女士匹配）。
高效操作：入队（队尾插入）和出队（队头删除）操作的时间复杂度均为O(1)，适合频繁的插入和删除场景（本题需要多次入队、出队配对）。

总结

本题通过链队列分离男士和女士舞者，利用队列的 FIFO 特性实现按顺序配对，最终输出配对结果和剩余未配对的队头元素。链队列的动态性和高效性使其成为解决此类 “顺序处理、成对匹配” 问题的理想数据结构。

解析

void DancePartner(DataType dancer[], int num)
{
    LinkQueue maleQueue = SetNullQueue_Link();
    LinkQueue femaleQueue = SetNullQueue_Link();

    int i;
    for (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) != 1 && IsNullQueue_link(femaleQueue) != 1) {
        DataType female = FrontQueue_link(femaleQueue);
        DataType male = FrontQueue_link(maleQueue);
        printf("%s %s\n", female.name, male.name);
        DeQueue_link(maleQueue);
        DeQueue_link(femaleQueue);
    }

    if (IsNullQueue_link(maleQueue) == 1) {
        DataType female = FrontQueue_link(femaleQueue);
        printf("\n%s\n", female.name);
        DeQueue_link(femaleQueue);
    }
    else
    {
        DataType male = FrontQueue_link(maleQueue);
        printf("\n%s\n", male.name);
        DeQueue_link(maleQueue);
    }
    return;
}

注意

1.

LinkQueue maleQueue = SetNullQueue_Link();
LinkQueue femaleQueue = SetNullQueue_Link();

和

LinkQueue maleQueue; 
maleQueue = SetNullQueue_Link();
LinkQueue femaleQueue; 
femaleQueue = SetNullQueue_Link();

都可以

2.

这几行代码是舞伴配对的 核心逻辑，作用是 “从男女队列中各取队头元素完成配对、输出结果、并删除已配对的元素”，完全遵循队列 “先进先出（FIFO）” 的特性。以下逐行拆解解释：

DataType female = FrontQueue_link(femaleQueue);

功能：从 “女士队列” 中获取 队头元素（即最早入队的女士），并存储到 female 变量中。
关键依赖：裁判程序提供的
FrontQueue_link
函数，作用是 “返回队列的队头元素”（不删除元素）：
- 若队列非空，返回队头节点存储的 DataType 结构体（包含女士的姓名 name 和性别 sex）；
- 若队列为空，返回一个默认空结构体（避免未定义行为）。
示例：假设 femaleQueue 中依次入队 “高欣雅、张甜源、许丹丹”，这行代码会先获取队头的 “高欣雅”，female.name 就是 “高欣雅”。

DataType male = FrontQueue_link(maleQueue);

功能：与上一行逻辑一致，从 “男士队列” 中获取 队头元素（最早入队的男士），存储到 male 变量中。
示例：若 maleQueue 中依次入队 “李敏浩、李钟硕、吴彦祖”，这行代码会先获取队头的 “李敏浩”，male.name 就是 “李敏浩”。

printf("%s %s\n", female.name, male.name);

功能：输出一对配对结果，格式为 “女士姓名男士姓名”，并换行（符合题目样例要求）。
关键细节：%s 是字符串格式符，female.name 对应女士的姓名字符数组（数组名本质是字符串地址，符合 %s 要求），male.name 同理。
示例：结合上面的例子，这行代码会输出 高欣雅李敏浩，与样例的第一行配对结果完全一致。

DeQueue_link(maleQueue);

功能：删除 “男士队列” 的 队头元素（即刚完成配对的男士）。
关键依赖：裁判程序提供的
DeQueue_link
函数，作用是 “删除队头节点”：
- 先找到队头节点（maleQueue->f），将队头指针更新为 “下一个节点”（maleQueue->f = maleQueue->f->next）；
- 释放被删除节点的内存（避免内存泄漏）。
示例：删除 “李敏浩” 后，maleQueue 的队头变为 “李钟硕”，下次调用 FrontQueue_link 会获取 “李钟硕”。

DeQueue_link(femaleQueue);

功能：与上一行逻辑一致，删除 “女士队列” 的 队头元素（刚完成配对的女士）。
示例：删除 “高欣雅” 后，femaleQueue 的队头变为 “张甜源”，下次配对会用 “张甜源” 和 “李钟硕”。

整体逻辑串联（以输入样例为例）

假设男女队列初始入队顺序如下：

femaleQueue：高欣雅 → 张甜源 → 许丹丹 → 马小云
maleQueue：李敏浩 → 李钟硕 → 吴彦祖 → 王思聪 → 张智霖

循环执行这 5 行代码的过程：

第 1 次循环：取高欣雅 + 李敏浩 → 输出 “高欣雅李敏浩” → 删除两人 → 队列头更新为张甜源、李钟硕；
第 2 次循环：取张甜源 + 李钟硕 → 输出 “张甜源李钟硕” → 删除两人 → 队列头更新为许丹丹、吴彦祖；
第 3 次循环：取许丹丹 + 吴彦祖 → 输出 “许丹丹吴彦祖” → 删除两人 → 队列头更新为马小云、王思聪；
第 4 次循环：取马小云 + 王思聪 → 输出 “马小云王思聪” → 删除两人 → 女士队列为空，男士队列剩张智霖；
循环结束（女士队列为空），最后输出未配对的张智霖。

核心总结

这几行代码的本质是 “取队头（配对）→ 输出 → 删队头（腾出位置给下一对）”，通过循环重复这个过程，直到某一队列为空（无法继续配对），完美实现了题目 “按顺序配对” 的需求。

1-5 带头结点的链队列的基本操作

函数接口定义：

裁判测试程序样例：

输出样例：

解析

1-6 循环队列入队出队

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

输入样例：

输出样例：

输入样例：

输出样例：

解析

注意

1-7 另类循环队列

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

作者的第一次代码

一、核心问题：混淆 “队列逻辑” 与 “普通数组”，违背 FIFO 原则

问题 1：AddQ（入队）错误存储元素位置

问题 2：DeleteQ（出队）错误获取元素，违背 FIFO

二、次要问题：AddQ返回值不规范（虽不影响功能，但不符合 C 语言编码习惯）

修正后的完整代码（符合循环队列 FIFO 逻辑）

解析

1-8 舞伴问题

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

题目分析

题目分析：舞伴问题的核心需求

题目中使用的队列结构：链队列（Linked Queue）

1. 链队列的结构组成

2. 链队列的核心操作（裁判程序已实现）

3. 链队列的特点（为何适合本题）

总结

解析

注意

1.

2.

问题 1：`AddQ`（入队）错误存储元素位置

问题 2：`DeleteQ`（出队）错误获取元素，违背 FIFO

二、次要问题：`AddQ`返回值不规范（虽不影响功能，但不符合 C 语言编码习惯）