# 分類題庫

## Linked List
### ZeroJudge b586. 文章壓縮 26/03/16
做一個linked list來存新的單字。按題目要求，把已經認識的單字，提到list前頭。
我犯過的儍：
1. strtok不適用，雖然它可以parse單字，卻會把comma搞不見。
2. scanf不適用，因為它會斷在句子的空白。用fgets或getchar取代之。
3. 不需要和'A'、'Z'、'a'、'z'比較，只要用isalpha即可確認。
4. 結束行0，使用strncmp比較一個字即可。

// ZEROJUDGE b586. 文章壓縮

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

typedef struct node
{
    char *word;
    struct node *next;
} Node;

void move(Node *h, Node *prev, Node *curr)
{
    Node *p = curr;
    prev->next = p->next;

    Node *first = h->next;
    p->next = first;
    h->next = p;
}

int search(Node *h, char *s)
{
    Node *prev = h,
         *curr = h->next;
    int sn = 0;
    while (NULL != curr)
    {
        ++sn;
        if (!strcmp(curr->word, s))
        {
            break;
        }

        prev = curr;
        curr = curr->next;
    }

    if (NULL == curr)
    {
        return -1;
    }

    // printf("[%d] %d:%s\n", __LINE__, sn, s);
    move(h, prev, curr);
    return sn;
}

void insert(Node *h, char *s)
{
    int len = strlen(s) + 1;
    Node *p = (Node *)malloc(sizeof(Node));
    p->word = (char *)malloc(len);
    memset(p->word, 0, len);
    strcpy(p->word, s);
    Node *np = h->next;
    p->next = np;
    h->next = p;
}

// void print(Node *h)
// {
//     Node *p = h->next;
//     while (p)
//     {
//         printf("%s ", p->word);
//         p = p->next;
//     }
// }

void destroy(Node *h)
{
    Node *p = h->next;
    while (NULL != p)
    {
        h->next = p->next;
        free(p->word);
        free(p);
        p = h->next;
    }

    free(h);
}

int main()
{
    char ibuf[1001], word[51];
    // char obuf[1001] = {0};
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;

    // while (scanf("%[^\n]", ibuf))
    while (fgets(ibuf, 1001, stdin))
    {
        if (!strncmp(ibuf, "0", 1))
        {
            break;
        }
#if 0
        const char *delim = " -,'";
        char *pch = strtok(ibuf, delim);
        while (pch)
        {
            // printf("%s\n", pch);
            int v = search(head, pch);
            // int v = 0;
            if (-1 == v)
            {
                // printf("%s ", pch);
                insert(head, pch);
            }

            pch = strtok(NULL, delim);
        }
#endif
        int i = 0, j = 0;
        while (ibuf[i])
        {
            if (isalpha(ibuf[i]))
            {
                word[j] = ibuf[i];
                ++i;
                ++j;
            }
            else
            {
                if (0 != j)
                {
                    word[j] = 0;
                    // printf("[%d] %s\n", __LINE__, word);
                    int v = search(head, word);
                    if (-1 == v)
                    {
                        printf("%s", word);
                        // strcat(obuf, word);
                        insert(head, word);
                    }
                    else
                    {
                        // char num[80];
                        printf("%d", v);
                        // sprintf(num, "%d", v);
                        // strcat(obuf, num);
                    }

                    j = 0;
                }

                // char punc[80];
                printf("%c", ibuf[i++]);
                // sprintf(punc, "%c", ibuf[i++]);
                // strcat(obuf, punc);
            }
        }
    }

    // print(head);
    // printf("%s", obuf);

    destroy(head);

    return 0;
}

### ZeroJudge b938. kevin 愛殺殺 26/03/14
本題中「會叫編號k的人、把他後面的人殺掉」，故使用陣列來實做linked list，會比使用指標搜尋速度快。

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

typedef struct node
{
    int sn;
    int next;
} Node;

void init(Node *head, int n)
{
    for (int i = 1; i <= n - 1; ++i)
    {
        head[i].sn = i;
        head[i].next = i + 1;
    }
    head[n].sn = n;
    head[n].next = -1;
}

void print(Node *head)
{
    Node *p = head + 1;
    while (-1 != p->next)
    {
        printf("%d,", p->sn);
        p = head + p->next;
    }

    printf("%d\n", p->sn);
}

void del(Node *h, int k)
{
    int k1 = h[k].next;
    if (-1 != k1)
    {
        h[k].next = h[k1].next;
        h[k1].next = -1;
        printf("%d\n", k1);
    }
    else
    {
        printf("0u0 ...... ?\n");
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    Node *head = (Node *)malloc(sizeof(Node) * (n + 1));
    init(head, n);
    // print(head);

    while (m--)
    {
        int k;
        scanf("%d", &k);
        del(head, k);
    }

    free(head);
    return 0;
}

## 參考資料
1. 林盈達. 大學程式能力檢定: CPE祕笈. 二版. 臺北市: 美商麥格羅希爾國際股份有限公司臺灣分公司, 2021. Print.
1. 增井敏克., and 許郁文. 培養刷題基本功: Python程式設計師的頭腦體操. 初版. 臺北市: 碁峰資訊, 2021. Print.
1. 付東來. 刷題實戰筆記: 演算法工程師求職加分的祕笈. 初版. 新北市: 博碩文化, 2021. Print.
1. 林奈爾, Reuven M Lerner, and 施威銘研究室. Python刷題鍛鍊班: 老手都刷過的50道程式題,求職面試最給力. 初版. 臺北市: 旗標發行, 2021. Print.