拉丁方陣生成算法：基於單向循環鏈表的 C 語言實現

拉丁方陣生成算法：基於單向循環鏈表的 C 語言實現

拉丁方陣是 n×n 矩陣，包含 n 種元素，每行每列各元素恰好出現一次。歐拉以拉丁字母作元素符號，故名。本文展示一種利用單向循環鏈表「循環移位」特性生成拉丁方陣的巧妙方法。

核心洞察

第 1 行輸出鏈表順序：1 2 3 ... n
第 2 行從第 2 個元素開始：2 3 ... n 1
第 k 行從第 k 個元素開始：k k+1 ... n 1 ... k-1
單向循環鏈表天然支持此「首尾相接、循環遍歷」操作。

鏈表構建：無頭結點、尾指針指向首元

typedef struct Node { int data; struct Node* next; } Node, *LinkList;

void CreateSimpleCycleList_tail(LinkList* L, int number) {
    *L = (LinkList)malloc(sizeof(Node)); // 臨時頭結點
    (*L)->next = *L;
    for (int i = 1; i <= number; i++) {
        LinkList newNode = (LinkList)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = (*L)->next; // 頭插法
        (*L)->next = newNode;
        *L = newNode; // 尾指針後移
    }
    // 刪除臨時頭結點，調整為無頭結點循環鏈表
    LinkList temp = (*L)->next;
    (*L)->next = temp->next;
    *L = temp->next;
    free(temp);
}

拉丁方陣輸出：雙層循環控制行與列

void ShowLatinSquare(LinkList L, int number) {
    int row = 1, col;
    LinkList temp = L;
    while (row <= number) {
        col = 1;
        while (col <= number) {
            printf("%d ", L->data);
            L = L->next;
            col++;
        }
        printf("\n");
        L = L->next; // 行末額外後移一位，實現下一行起始位置右移
        row++;
    }
}

關鍵技巧：內層循環輸出完一行後，L 已指向下一行的起始元素；外層循環再 L = L->next 使起始位置再右移一格，完美實現每行左移一位的循環移位效果。

運行示例（n=4）

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

總結

此法將拉丁方陣的行列約束轉化為循環鏈表的指針操作，代碼極其簡潔（核心邏輯 < 20 行），時間 O(n²)、空間 O(n)，展示了數據結構特性與問題模型完美契合時的優雅解法。