practice-2main.cpp

数据结构题集实习1.2 约瑟夫环 清华大学 严蔚敏

#include<iostream>
using namespace std;

struct kid {
       int code;
       int No;
       kid *next;
       };
       
kid* enter(kid* f,int N)
{
       kid *v = (kid*)malloc(sizeof(kid));
       if(!v) {
              cout << "内存分配错误" <<endl;
              system("pause");
              exit(1);
              } 
       cin >> v->code;
       v->No = N;
       v->next = f;
       return v; 
       }

void compute(kid *s,int x,int y)
{              
     kid *k;
     k = NULL;
     for(int n = 0;n != y;n++) {
                  if(x == 1 && k == NULL) {//考虑如果m=1时，复制后一个结点到该结点，并删除后一个结点 
                  cout << s->No <<"\t";
                  x = s->code;
                  s->code = s->next->code;
                  s->No = s->next->No;
                  s->next = s->next->next;
                  free(s->next);
                  }
                  else {
                        for(int i = 0;i != x - 1;++i) {
                                k = s;
                                s = s->next;
                                }
                                x = s->code;
                                cout << s->No << "\t";                    
                                k->next = s->next;
                                free(s);
                                s = k->next;
                                }
                  }                                       
}    
       
int main()
{
    int n,m;
    cout << "输入学生数："; 
    cin >> n;
    cout << "输入报数上限："; 
    cin >> m;
    cout << "输入每个人的密码，按回车分开。" <<endl; 
    
    kid *head,*p;    
    p = enter(head,1);
    head = p;//不能放在p = enter(head,1)前 
          
    for(int i = 0;i != n - 1;i++) {
            kid *l = enter(head,i + 2);
            p->next = l;//*的优先级高于->,不能用*p->next=*s 
            p = p->next;
                }            
    kid* t = head;
    cout << "出列顺序为：" << endl;        
    compute(t,m,n);
    
    system("pause");    
    return 0;
}