BuringStraw

#include <stdio.h>
#include <stdlib.h>
#define MAXN 50005//數據範圍
#define MOD 400000//取模，不要太大，否則會超內存
int a[MAXN];//用來保存結果

struct node
{
    struct node* next;//指向下一項的指針
    int value;//這個節點保存的值
};

struct node* head[MOD];//哈希表，由一堆鏈表組成，存的是鏈表頭指針

void insert(struct node* p, int v)//在節點p後面插入v
{
    if (p == NULL) return;//不能對NULL操作，保險
    struct node *t = malloc(sizeof(struct node));//為新的節點分配內存
    t -> value = v;//設置值
    //一個插入過程
    t -> next = p -> next;//這一項的下一項設置為前一項的下一項
    p -> next = t;//前一項的下一項設置為這一項
}

int find(struct node*p, int v)//從節點p開始向後查找，直到找到或到鏈表末尾
{
    while(p != NULL)//跳到NULL停止，最後一項的next默認為NULL
    {
        if (p -> value == v)//查到v了
        {
            return 1;//找到了就直接退出循環
        }
        p = p -> next;//往前跳
    }
    return 0;//沒找到才有機會結束循環
}

int main() {
    int t;//數據組數
    scanf("%d", &t);
    while (t--)//只循環t次
    {
        for (int i = 0; i < MOD; ++i)
        {
            head[i] = NULL;
        }
        int n;
        scanf("%d", &n);
        int newp = 0;//記錄a中最新元素的下標，由於個人習慣我們將1作為第一個元素的下標
        for (int i = 1; i <= n; ++i)
        {
            int x;
            scanf("%d", &x);//輸入一個數
            int flag = 0;//0表示沒有相同數據，1表示有
            int m = x % MOD;//取模後的結果，用於在head中索引
            if (m < 0)//負數取模得到負數，導致下標越
                m = -m;
            //查找時分三種情況
            if (head[m] == NULL)//head[m]指向的鏈表不存在
            {//手動初始化第一個元素
                head[m] = malloc(sizeof(struct node));//分配內存
                head[m] -> value = x;//設置值
                head[m] -> next = NULL;//下一項還沒有
            } else
            {//鏈表存在
                if (find(head[m], x)/*查找x*/) flag = 1;//找到了
                else
                {//沒找到
                    struct node* p = head[m];//得到鏈表頭指針
                    while (p -> next != NULL) p = p -> next;//直達尾部
                    insert(p, x);//插入
                }
            }
            if (!flag) a[++newp] = x;//好的我們沒找到x，可以往a裡插新元素了
        }

        for (int i = 1; i <= newp; ++i)//輸出。。
        {
            printf("%d ", a[i]);
        }
        putchar('\n');
    }
    return 0;
}