資料結構 (C#)：循環鏈結串列實作與約瑟夫問題應用

C# 循環雙向鏈結串列：繼承雙向鏈結串列實作與經典約瑟夫問題解法

循環鏈結串列將尾節點指向頭節點，形成環狀結構。本文繼承雙向鏈結串列實作循環雙向鏈結串列，提供 GetNext/GetPrevious 循環游標操作，並以約瑟夫問題展示實戰應用。

一、循環鏈結串列完整程式碼

using System;

namespace Xianfen.Net.DataStructure
{
    public class CircularlyLinkedList<T> : DoubleLinkedList<T>
    {
        private DoubleLinkedListNode<T> m_CurrentNode;
        private int m_CurrentIndex;

        public int CurrentIndex { get { return m_CurrentIndex; } }

        public CircularlyLinkedList() : base()
        {
            m_CurrentNode = m_Head.Next;
            m_CurrentIndex = 0;
        }

        public CircularlyLinkedList(T t) : base(t)
        {
            m_CurrentNode = m_Head.Next;
            m_CurrentIndex = 0;
        }

        public T GetCurrent()
        {
            if (m_Count == 0) throw new IndexOutOfRangeException();
            return m_CurrentNode.Value;
        }

        public T GetNext()
        {
            if (m_Count == 0) throw new IndexOutOfRangeException();

            if (m_CurrentNode != null)
            {
                m_CurrentNode = m_CurrentNode.Next;
                m_CurrentIndex++;
            }

            // 到達尾端，循環回頭節點
            if (m_CurrentNode == null)
            {
                m_CurrentNode = m_Head.Next;
                m_CurrentIndex = 0;
            }

            return m_CurrentNode.Value;
        }

        public T GetPrevious()
        {
            if (m_Count == 0) throw new IndexOutOfRangeException();

            if (m_CurrentNode != null)
            {
                m_CurrentNode = m_CurrentNode.Prior;
                m_CurrentIndex--;
            }

            // 到達頭哨兵節點，循環至尾節點
            if (m_CurrentNode == null || m_CurrentNode == m_Head)
            {
                m_CurrentNode = m_Tail;
                m_CurrentIndex = m_Count - 1;
            }

            return m_CurrentNode.Value;
        }
    }
}

二、應用範例：約瑟夫問題

問題：N 人圍圈，從 1 開始報數，報到 M 出列，下一人從 1 重新報數，重複至剩 1 人。

程式碼實作

const int M = 9; // 總人數 1~8 (程式碼邏輯為 < M)
const int N = 7; // 報數上限

CircularlyLinkedList<int> list = new CircularlyLinkedList<int>();

// 填充 1~8
for (int i = 1; i < M; i++) list.Add(i);

int tempCounter = 0;

while (list.Count > 1)
{
    tempCounter++;
    list.GetPrevious(); // 逆向移動游標

    // 選中者出列
    if (tempCounter == N)
    {
        tempCounter = 0;
        Console.WriteLine(list.GetCurrent() + " 出列！");
        list.RemoveAt(list.CurrentIndex);
    }
}

Console.WriteLine(list.GetNext() + " 為剩者");

執行結果 (GetPrevious 逆向)

2 出列！
3 出列！
1 出列！
7 出列！
4 出列！
8 出列！
6 出列！
5 為剩者

修改為 GetNext 正向

將 list.GetPrevious() 改為 list.GetNext()：

7 出列！
6 出列！
8 出列！
2 出列！
5 出列！
1 出列！
3 出列！
4 為剩者

三、核心設計重點

• 繼承 DoubleLinkedList<T> 復用節點管理邏輯。
• 維護 m_CurrentNode 與 m_CurrentIndex 追蹤游標位置。
• GetNext 遇 null 循環至 m_Head.Next；GetPrevious 遇 null 或 m_Head 循環至 m_Tail。
• 約瑟夫問題展示循環結構在淘汰賽、輪詢排程等場景的天然優勢。