數(shù)據(jù)結(jié)構(gòu)（六）——循環(huán)鏈表

數(shù)據(jù)結(jié)構(gòu)（六）——循環(huán)鏈表

一、循序鏈表簡介

1、循環(huán)鏈表的定義

循環(huán)鏈表的任意元素都有一個前驅(qū)和一個后繼，所有數(shù)據(jù)元素在關(guān)系上構(gòu)成邏輯上的環(huán)。
循環(huán)鏈表是一種特殊的單鏈表，尾結(jié)點的指針指向首結(jié)點的地址。
循環(huán)鏈表的邏輯關(guān)系圖如下：

2、循環(huán)鏈表的設(shè)計實現(xiàn)

循環(huán)鏈表的設(shè)計實現(xiàn)要點：
A、通過模板定義CircleList，繼承自LinkedList
B、定義連接鏈表首尾的內(nèi)部函數(shù)
C、實現(xiàn)首元素的插入和刪除操作
D、重寫清空操作和遍歷操作

3、循環(huán)鏈表的實現(xiàn)關(guān)鍵

A、插入位置為0時，頭結(jié)點和尾結(jié)點均指向新結(jié)點，新結(jié)點作為首結(jié)點插入鏈表。
B、刪除位置為0時，頭結(jié)點和尾結(jié)點指向位置為1的結(jié)點，刪除銷毀首結(jié)點

二、循環(huán)鏈表的操作

1、尾結(jié)點獲取

Node* last()
{
     return this->position(this->m_length - 1)->next;
}

2、首尾結(jié)點連接

void lastToFirst()
{
     last()->next = this->m_header.next;
}

三、循環(huán)鏈表的實現(xiàn)

 template <typename T>
  class CircleList:public LinkedList<T>
  {
  protected:
      typedef typename LinkedList<T>::Node Node;
      //尾結(jié)點
      Node* last()
      {
          return this->position(this->m_length - 1)->next;
      }
      //鏈接最后一個結(jié)點和首結(jié)點
      void lastToFirst()
      {
          last()->next = this->m_header.next;
      }
      int mod(int index)const
      {
          return (this->m_length == 0)?0:(index % this->m_length);
      }
  public:
      bool insert(int index, const T& value)
      {
          bool ret = true;
          //計算插入結(jié)點的位置
          index = index % (this->m_length + 1);
          ret = LinkedList<T>::insert(index, value);
          //如果插入位置為0
          if(ret && (index == 0))
          {
              lastToFirst();//連接首尾結(jié)點
          }
          return ret;
      }
      bool insert(const T& value)
      {
          return insert(this->m_length, value);
      }
      bool remove(int index)
      {
          bool ret = true;
          index = mod(index);
          //刪除結(jié)點為首結(jié)點
          if(index == 0)
          {
              //首結(jié)點
              Node* toDel = this->m_header.next;
              if(toDel)
              {
                  //將頭結(jié)點的下一個結(jié)點指向首結(jié)點的下一個結(jié)點
                  this->m_header.next = toDel->next;
                  this->m_length--;//鏈表長度減1
                  //鏈表不為空
                  if(this->m_length > 0)
                  {
                      lastToFirst();//連接新的首結(jié)點與尾結(jié)點
                      if(this->m_current == toDel)
                      {
                          this->m_current = toDel->next;
                      }
                  }
                  else
                  {
                      //鏈表為空，置空
                      this->m_header.next = NULL;
                      this->m_current = NULL;
                  }
                  //銷毀要刪除的結(jié)點
                  this->destroy(toDel);
              }
              else
              {
                  ret = false;
              }
          }
          else
          {
              //刪除的結(jié)點不是首結(jié)點，按單鏈表處理
              ret = LinkedList<T>::remove(index);
          }
          return ret;
      }
      bool set(int index, const T& value)
      {
          index = mod(index);
          return LinkedList<T>::set(index, value);
      }
      T get(int index)const
      {
          index = mod(index);
          return LinkedList<T>::get(index);
      }
      bool get(int index, T& value)
      {
          index = mod(index);
          return LinkedList<T>::get(index, value);
      }
      int find(const T& value)
      {
          int ret = -1;
          //首結(jié)點
          Node* current = this->m_header.next;
          //遍歷鏈表查找數(shù)據(jù)元素
          for(int i = 0; i < this->length(); i++)
          {
              if(current->value == value)
              {
                  ret = i;
                  break;
              }
              //移動游標
              current = current->next;
          }
          return ret;
      }
      void clear()
      {
          //刪除鏈表中結(jié)點至頭結(jié)點
          while(this->m_length > 1)
          {
              remove(1);
          }
          //刪除首結(jié)點
          if(this->m_length == 1)
          {
              Node* toDel = this->m_header.next;
              this->m_header.next = NULL;
              this->m_current = NULL;
              this->m_length = 0;
              this->destroy(toDel);
          }
      }
      bool move(int pos, int step)
      {
          pos = mod(pos);
          return LinkedList<T>::move(pos, step);
      }
      bool end()
      {
          return (this->m_length == 0) || (this->m_current == NULL);
      }
      ~CircleList()
      {
          clear();
      }
  };

四、約瑟夫環(huán)（Josephus）

1、約瑟夫環(huán)簡介

Josephu約瑟夫環(huán)問題為：設(shè)編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數(shù)，數(shù)到m 的那個人出列，它的下一位又從1開始報數(shù)，數(shù)到m的那個人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個出隊編號的序列。

2、循環(huán)鏈表解決約瑟夫環(huán)問題

//約瑟夫環(huán)
void jusephus(int n, int k, int m)
{
  //構(gòu)建循環(huán)鏈表
  CircleList<int> cl;
  for(int i = 1; i <= n; i++)
  {
      cl.insert(i);
  }
  //移動當前結(jié)點到位置k-1，設(shè)置步長為m-1
  cl.move(k-1, m-1);
  while(cl.length() > 0)
  {
      cl.next();//移動到目標位置
      cout << cl.current() << endl;
      //刪除目標位置結(jié)點
      cl.remove(cl.find(cl.current()));
  }
}

3、遞歸方法解決約瑟夫環(huán)問題

當編號為1開始時可以使用遞歸
假設(shè)n=10,m=3
1 2 3 4 5 6 7 8 9 10 m=3
第一次有人出列后：1 2 4 5 6 7 8 9 10
出環(huán)的序列：4 5 6 7 8 9 10 1 2
轉(zhuǎn)換為：1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 4 5 6 7 8 9 10 1 2
設(shè)f(n,m,i)為n個人的環(huán)，報數(shù)為m，第i個人出環(huán)的編號，則f(10,3,10)是我們要的結(jié)果
當i=1時，? f(n,m,i) = (n-1+m)%n
當i>1時，? f(n,m,i)= ( f(n-1,m,i-1)+m )%n
當編號為0開始時可以使用遞歸
假設(shè)n=10,m=3
0 1 2 3 4 5 6 7 8 9 m=3
第一次有人出列后：0 1 3 4 5 6 7 8 9
3 4 5 6 7 8 9 0 1
1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 3 4 5 6 7 8 9 1 2
設(shè)f(n,m,i)為n個人的環(huán)，報數(shù)為m，第i個人出環(huán)的編號，則f(10,3,10)是我們要的結(jié)果
當i=1時，? f(n,m,i) = (n-1+m)%n
當i>1時，? f(n,m,i)= ( f(n-1,m,i-1)+m )%n

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

int Josephu_recursion(int n, int m, int i)
{
    if(1 == i)
        return (n-1 + m) % n;
    else
        return (Josephu_recursion(n-1, m, i-1) + m) % n;
}

int main(void)
{
    int i;
    for(i = 1; i <= 10; i ++) 
        printf("第%2d次出環(huán)：%2d\n", i, Josephu_recursion(10, 3, i));
}

4、數(shù)組方法解決約瑟夫環(huán)問題

/***********************************************
 * 約瑟夫環(huán)問題的數(shù)組解決
 * n:約瑟夫環(huán)的長度
 * k:起點
 * m:步長
 * *********************************************/
int JosephuArray(int n, int k, int m)
{
    //分配n+1個int空間
    int *a = (int *)malloc((n+1) * sizeof(int));
    int i, j;
    //下標從1開始賦值
    for(i = 1; i <= n; i++)
        a[i] = i;//從a[1]開始
    //依次出環(huán)
    for(i = n; i >= 1; i--)
    {
        //計算每次出環(huán)的k值
        k = (k + m -1) % i;
        if(k == 0)
            k = i;
        printf("%2d\n", a[k]);//打印出出環(huán)的序號
        //將出環(huán)的位置后的元素前移
        for(j = k; j < i; j++)
            a[j] = a[j+1];
    }
    free(a);
}