Danh sách vòng

#ifndef CLIST_H
#define CLIST_H

#include <stddef.h>

typedef struct CNode {
    int           data;
    struct CNode *next;
} CNode;

/* Chỉ cần giữ tail. Nút đầu luôn là tail->next.
   Bất biến:
     1. tail == NULL  khi và chỉ khi  size == 0
     2. tail != NULL  thì đi theo next từ tail đúng size bước sẽ về lại tail
     3. size == số nút trong vòng                                        */
typedef struct {
    CNode *tail;
    size_t size;
} CList;

void clist_khoi_tao(CList *l);
void clist_huy(CList *l);
int  clist_them_dau(CList *l, int data);
int  clist_them_cuoi(CList *l, int data);
int  clist_xoa_dau(CList *l, int *out);
void clist_in(const CList *l);

#endif

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

#include "clist.h"

void clist_khoi_tao(CList *l)
{
    l->tail = NULL;
    l->size = 0;
}

void clist_in(const CList *l)
{
    printf("(");

    if (l->tail != NULL) {
        const CNode *dau = l->tail->next;
        const CNode *p   = dau;

        do {
            printf("%d", p->data);
            p = p->next;

            if (p != dau) printf(" -> ");
        } while (p != dau);

        printf(" -> ...");
    }

    printf(")  (size = %zu)\n", l->size);
}

static CNode *cnode_tao(int data)
{
    CNode *n = malloc(sizeof *n);

    if (n == NULL) return NULL;

    n->data = data;
    n->next = n;          /* nút đơn độc là một vòng một phần tử */

    return n;
}

/* Thêm vào đầu, tức ngay sau tail. O(1). */
int clist_them_dau(CList *l, int data)
{
    CNode *n = cnode_tao(data);

    if (n == NULL) return -1;

    if (l->tail == NULL) {
        l->tail = n;              /* n->next đã trỏ về chính nó */
    } else {
        n->next       = l->tail->next;
        l->tail->next = n;
    }

    ++l->size;

    return 0;
}

/* Thêm vào cuối: y hệt thêm đầu, chỉ khác là tail lùi sang nút mới. O(1). */
int clist_them_cuoi(CList *l, int data)
{
    if (clist_them_dau(l, data) != 0) return -1;

    l->tail = l->tail->next;      /* nút vừa thêm giờ là cuối */

    return 0;
}

/* Xóa nút đầu, tức tail->next. O(1). */
int clist_xoa_dau(CList *l, int *out)
{
    if (l->tail == NULL) return -1;

    CNode *dau = l->tail->next;

    if (out != NULL) *out = dau->data;

    if (dau == l->tail) {              /* chỉ còn một nút */
        l->tail = NULL;
    } else {
        l->tail->next = dau->next;
    }

    free(dau);
    --l->size;

    return 0;
}

void clist_huy(CList *l)
{
    while (clist_xoa_dau(l, NULL) == 0) { }

    /* Sau vòng lặp: tail đã NULL và size đã 0 */
}

/* Nối toàn bộ b vào cuối a. Sau khi gọi, b thành rỗng. O(1). */
void clist_ghep(CList *a, CList *b)
{
    if (b->tail == NULL) return;

    if (a->tail == NULL) {
        a->tail = b->tail;
        a->size = b->size;
    } else {
        CNode *dau_a = a->tail->next;
        CNode *dau_b = b->tail->next;

        a->tail->next = dau_b;      /* cuối a nối vào đầu b */
        b->tail->next = dau_a;      /* cuối b khép lại về đầu a */

        a->tail  = b->tail;         /* cuối chung là cuối b */
        a->size += b->size;
    }

    clist_khoi_tao(b);
}

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

typedef struct CNode { int data; struct CNode *next; } CNode;

/* Trả về số của người sống sót, hoặc -1 nếu hết bộ nhớ.
   In ra thứ tự bị loại nếu in_buoc khác 0. */
int josephus(int n, int k, int in_buoc)
{
    if (n <= 0 || k <= 0) return -1;

    /* Dựng vòng n nút, giữ tail */
    CNode *tail = NULL;

    for (int i = 1; i <= n; ++i) {
        CNode *m = malloc(sizeof *m);

        if (m == NULL) {
            /* Dọn phần đã dựng rồi báo lỗi */
            if (tail != NULL) {
                CNode *p = tail->next;

                while (p != tail) { CNode *t = p->next; free(p); p = t; }

                free(tail);
            }

            return -1;
        }

        m->data = i;

        if (tail == NULL) { m->next = m; }
        else              { m->next = tail->next; tail->next = m; }

        tail = m;
    }

    /* truoc luôn là nút đứng ngay trước nút đang xét */
    CNode *truoc = tail;

    while (truoc->next != truoc) {          /* còn nhiều hơn một nút */
        for (int b = 1; b < k; ++b)
            truoc = truoc->next;            /* đi k-1 bước */

        CNode *loai = truoc->next;          /* nút thứ k bị loại */

        if (in_buoc) printf("loai %d\n", loai->data);

        truoc->next = loai->next;
        free(loai);
    }

    int song = truoc->data;

    free(truoc);

    return song;
}

int main(void)
{
    printf("n = 7, k = 3\n");

    int s = josephus(7, 3, 1);

    printf("song sot: %d\n\n", s);

    for (int k = 2; k <= 4; ++k)
        printf("n = 41, k = %d  -> song sot %d\n", k, josephus(41, k, 0));

    return 0;
}

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

typedef struct TT {
    char        ten[16];
    int         con_lai;      /* số lượng tử thời gian còn cần */
    struct TT  *next;
} TT;

/* Mỗi lượt cho một tiến trình chạy đúng mot lượng tử.
   Tiến trình xong thì bị gỡ khỏi vòng. */
void chay(TT *tail)
{
    int thoi_diem = 0;

    while (tail != NULL) {
        TT *hien = tail->next;

        --hien->con_lai;
        ++thoi_diem;

        printf("t=%2d  chay %-6s con lai %d\n",
               thoi_diem, hien->ten, hien->con_lai);

        if (hien->con_lai == 0) {
            printf("      %s xong\n", hien->ten);

            if (hien == tail) {           /* tiến trình cuối cùng */
                free(hien);
                tail = NULL;
            } else {
                tail->next = hien->next;
                free(hien);
            }
        } else {
            tail = hien;                  /* tiến sang tiến trình kế */
        }
    }
}