排隊買飯（連結清單） SDUT OJ4516

排隊買飯

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

理工大的食堂到了飯點人可以說是相當多了，按理來說排隊的時候先來的同學應該會先走，但實際情況可能并不一樣，我們注意到對于一個隊列往往由以下兩種操作組成

當輸入 1 時：代表隊列最左面的同學完成了買飯操作，由于他會幫他的好朋友一起買，是以買完飯後會叫上所有與他編号相同的好朋友一起走，如果輸入1時隊伍已經為空則不進行任何操作。換句話說，如果序列不為空則會在序列中删除最左邊的一個元素和與之編号相同的所有元素，否則不删除。

當輸入 2 時：代表編号為 b 的同學想要插隊買飯，由于他與編号為 a 的同學是好朋友，他會插入到隊列從左往右的第一個編号為 a 的同學右邊，如果隊伍中沒有編号為 a 的同學，他就會傷心的離開。換句話說，會在隊列的從左往右的第一個 a 後面插入一個 b，如果隊列中沒有 a 則不插入。

需要注意的是，每次操作後都需要你判斷一下隊列是否為空，如果為空則輸出“EMPTY”。

最後一行輸出所有操作後的序列。

Input

第一行一個數 n 代表初始時序列中的元素 ( n<=1e5)

第二行 n個 int 範圍内的數，最多有1000個不同的。

第三行一個數 m 代表操作的次數。(m<=1e5)

後面m行每行第一個數代表操作種類。

如果操作為 2 則再輸入兩個數 a，b。

Output

對于每次操作，如果操作後隊列為空，則輸出"EMPTY"。

所有操作完成後輸出最終的序列。

（最下方提示有補充測試樣例）

Sample Input

6
1 1 4 3 1 2
3
2 4 5
1
1      

Sample Output

5 3 2      

Hint

補充樣例：

input：

6

1 1 4 3 1 2

5

2 6 5

1

1

1

1

output：

EMPTY

此題目中有歧義：“EMPTY”的輸出應該是每一次操作無論成功與否，在傳回前都會判斷是否為空，若連結清單為空，則輸出

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    struct node *next;
};
struct node *Sequence_Linked_List(int);
void one(struct node *);
void two(struct node *, int, int);
void output(struct node *);
int main()
{
    int n, m, a, b, x;
    struct node *head;
    scanf("%d", &n);
    head = Sequence_Linked_List(n);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &x);
        if(x == 1)
        {
            one(head);
        }
        else
        {
            scanf("%d %d", &a, &b);
            two(head, a, b);
        }
    }
    output(head);
    return 0;
}
struct node *Sequence_Linked_List(int n)
{///順序建立連結清單，輸入隊伍中編号
    struct node *head, *tail, *p;
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;
    tail = head;
    while(n--)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d", &p->data);
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
    return head;
};
void one(struct node *head)
{///如果序列不為空，在序列中删除最左邊的一個元素和與之編号相同的所有元素
///否則不進行操作
    struct node *q, *p;
    int x;
    if(head->next == NULL)
    {///當序列為空時，不進行操作
        printf("EMPTY\n");
        return;
    }
    else
    {
        q = head;
        p = q->next;
        x = head->next->data;/// x = p->data 記錄最左邊第一個元素的編号
        while(p)
        {
            if(p->data == x)
            {///當隊列中存在與 x 相同的編号，則删除該元素
                q->next = p->next;
                free(p);
                p = q->next;
                if(head->next == NULL)
                {///每一次操作後，判斷隊列是否為空，如果為空，則輸出"EMPTY"并傳回
                    printf("EMPTY\n");
                    return;
                }
            }
            else
            {
                q = p;
                p = p->next;
            }
        }
    }
}
void two(struct node *head, int a, int b)
{///如果有編号為 a 的同學，則在 a 後插入編号為 b 的結點
///若沒有編号為 a 的同學，則不進行操作
    struct node *p, *k;
    p = head->next;
    while(p)
    {
        if(p->data == a)
        {///若找到編号為 a 的同學，則在其後面插入編号為 b 的結點
            k = (struct node *)malloc(sizeof(struct node));
            k->data = b;
            k->next = p->next;
            p->next = k;
            break;
        }
        p = p->next;
    }
    if(head->next == NULL)
    {
        printf("EMPTY\n");
        return;
    }
}
void output(struct node *head)
{
    struct node *p;
    p = head->next;
    while(p)
    {
        if(p == head->next)
        {
            printf("%d", p->data);
        }
        else
        {
            printf(" %d", p->data);
        }
        p = p->next;
    }
    printf("\n");
}