【实验课】3. 学生排队

这题是想考察我们对链表或者顺序表的插入和删除操作，也是基础题。

【问题描述】

体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。

例如，下面给出了一组移动的例子，例子中学生的人数为8人。
0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。

【输入形式】

输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
第二行包含一个整数m，表示调整的次数。
接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。

【输出形式】

输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。

【样例输入】

8
3
3 2
8 -3
3 -2

【样例输出】

1 2 4 3 5 8 6 7

【样例说明】

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。

【代码&&注释】

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

typedef struct Stu{
    int id;
    struct Stu* next;
}Stu, *Stuptr;

int main()
{
    // 学生数量n, 调整次数m
    int n, m, i;
    scanf("%d %d", &n, &m);
    // 头节点 工作指针
    Stuptr h = (Stuptr)malloc(sizeof(Stu)), p0;
    p0 = h;
    h -> next = NULL;
    // 赋初值， 链上他们......
    for(i = 0; i < n; i++)
    {
        Stuptr last = (Stuptr)malloc(sizeof(Stu));
        last -> id = i + 1;
        last -> next = NULL;
        p0 = p0 -> next = last;
    }
    int p, q;
    int j, k;
    Stuptr p1, p2, temp = h;
    
    // 开始输入 & 移动
    for(i = 0; i < m; i++)
    {
        p1 = p2 = h;
        scanf("%d %d", &p, &q);
        // 找到id为p的stu
        for(j = 0; j < n; j++)
        {
            temp = p1;
            p1 = p1 -> next;
            if(p1 -> id == p) break;
        }
        // 找到目标位置前一个stu
        if(q > 0){
            for(k = 0; k < j + q + 1; k++)
            {
                p2 = p2 -> next;
            }
        }
        else
        {
            for(k = 0; k < j + q; k++)
            {
                p2 = p2 -> next;
            }
        }
        // 插入
        temp -> next = p1 -> next;
        p1 -> next = p2 -> next;
        p2 -> next = p1;
    }
    
    // 输出最后的顺序
    h = h -> next;
    while(h)
    {
        printf("%d ", h -> id);
        Stuptr f = h -> next;
        free(h);
        h = f;
    }
    
    
    return 0;
}

如有疑问，可通过 chenrongxin0130@gmail.com 联系我