데이터 구조 - 순환 링크, 꼬리 포인터 만 설 치 된 순환 링크, 조세 프 링

  1 //    ，       link    NULL，                
  2 //// p               ，    p          p->link == first
  3 
  4 
  5 //         
  6 typedef int DataType;
  7 typedef struct node//      
  8 {
  9     DataType data;//    
 10     struct node *link;//      
 11 }CirNode, *CirList;
 12 
 13 //         
 14 int Insert(CirNode *first, int i, DataType x)
 15 {//    x         i(1<=i)     。          0,      1.
 16     if(i<1)
 17         return 0;
 18     CirNode *p = first, *q;
 19     int k = 0;
 20     while(p->link != first && k< i-1)//    i-1   ，  i           
 21     {
 22         p = p->link;
 23         k++;
 24     }
 25     q = new CirNode;//      q  
 26     if(!q){cerr<data = x;
 28     q->link = p->link;// *q   *p  
 29     p->link = p;
 30     return 1;//    
 31 }
 32 

 33 //         
 34 int Remove(CirList& first, int i, DataType& x)
 35 {//      i     ，       x       
 36 //  i        ，    0,       1
 37     if(i<1)return 0;//i  ，   
 38     CirNode *p = first, *q;
 39     int k = 0;
 40     while(p->link != first && k < i-1)
 41     {
 42         p = p->link;
 43         k++;
 44     }
 45     //if(p->link == L)//i  ，       
 46      //   return 0;
 47     q = p->link;// q        
 48     p->link = q->link;//    ，          
 49     x = q->data;//         
 50     delete q;//    
 51     return 1;
 52 }

 55 //          
 56 //                   rear  ，                 O(l)
 57 //         p      
 58 int Remove(CirNode* &p, DataType& x)
 59 {//       p          ，       x       
 60 
 61     CirNode *q = p->link;
 62     x = p->data;//  p     
 63     p->data = q->data;//              
 64     p->link = q->link;//    ，          
 65     delete q;//      
 66     return 1;
 67 }
 68 //          newNode       
 69 int Insert(CirNode* &p, DataType& x)
 70 {//rear    
 71     CirNode *newNode;
 72     newNode->data = x;
 73     newNode->link = rear->link;
 74     rear->link = newNode;
 75 }

 78 //        
 79 
 80 void Josephus(CirNode* & Js, int n, int m)
 81 {
 82     CirNode *p = Js, *pre = NULL;
 83     for(int i = 0; ilink;
 89         }
 90         cout<data<link = p->link;
 92         delete p;//    *p
 93         p = pre->link;
 94     }
 95     cout<data<link = clist;
104     last = clist;//      
105     cout<>n>>m;
107     for(int i=1; i<=n; i++)
108     {
109         last->link = new CirNode;//      
110         if(!last->link){cerr<link;//            
112         last->data = i;
113     }

114     Josephus(clist, n, m);//        
115     return 0;
116 }
117 //       O(n*m)

  1 #include"stdio.h"
  2 #include 
  3 
  4 //      
  5 typedef struct Node
  6 {
  7     int index;
  8     int key;
  9     struct Node *next;
 10 }LinkNode, *LinkList;
 11 
 12 //    
 13 LinkList CreatLinkList()
 14 {
 15     LinkList L;
 16     L = (LinkList)malloc(sizeof(Node));
 17     printf("          ：
");
 18     int key;
 19     scanf_s("%d",&key);
 20     L->key = key;
 21     L->index = 1;
 22     L->next = L;
 23     Node *tail;
 24     Node *s;
 25     tail = L;
 26 
 27     printf("             -1：");//           
 28     int len;
 29     scanf_s("%d",&len);
 30 
 31     for (int i = 1; i < len; i++)
 32     {
 33         s = (Node *)malloc(sizeof(Node));
 34         scanf_s("%d", &s->key);
 35         s->index = i + 1;
 36         s->next = tail->next;
 37         tail->next = s;

 38         tail = s;
 39     }
 40     return L;
 41 }
 42 
 43 //       
 44 void yuesef(LinkList L,int Password)
 45 {
 46     int count = 1;
 47     Node *p;
 48     Node *s, *r;
 49     p = L;
 50     while (p->next != p)
 51     {
 52         if (count == Password - 1)
 53         {
 54             printf("  ：%d    ：%d
", p->next->index, p->next->key);
 55             s = p->next;
 56             p->next = s->next;
 57             Password = s->key;
 58             while (Password == 1 && p->next != p)
 59             {
 60                 printf("  ：%d    ：%d
", p->next->index, p->next->key);
 61                 r = p->next;
 62                 p->next = r->next;
 63                 Password = r->key;
 64                 free(r);
 65             }
 66             free(s);
 67             count = 1;
 68             p = p->next;
 69         }
 70         else
 71         {
 72             p = p->next;
 73             count++;

 74         }
 75     }
 76     printf("  ：%d    ：%d
", p->index, p->key);
 77 }
 78 
 79 int main(void)
 80 {
 81     LinkList L;
 82     L = CreatLinkList();
 83     Node *p;
 84     p = L;
 85     printf("%d %d 
", p->index, p->key);
 86     p = p->next;
 87     //      
 88     while (p != L)
 89     {
 90         printf("%d %d 
", p->index, p->key);
 91         p = p->next;
 92     }
 93     printf("        ：
");
 94     int Password;
 95     scanf_s("%d",&Password);
 96     yuesef(L, Password);
 97     getchar();
 98     getchar();
 99     return 0;
100 }