约瑟夫单循环链表的c++实现 - 编程论坛

#2

m21wo2010-10-17 09:08

程序代码：

#include <iostream>
using namespace std;
template <class T>
class Node
{
public:
    T  element;
    Node<T> *link;
    Node(T elem=0,Node<T>* lk=0):element(elem),link(lk)
    {}
    template <class T> friend void Josephus(Node<T>*& first, int m);
};

template <class T>
void Josephus(Node<T>*& first, int m)
{
    Node<T> *q=first,*p=first;
    while(p&&p!=p->link)
    {
        for(int i=1;i<m;q=p,p=p->link)
            i++;
        cout<<p->element<<"  ";
        q->link=p->link;
        delete p;p=q->link;
    }
    if(p)
    {
        cout<<p->element<<"  ";
        delete p;
    }
    first=NULL;
}

int main()
{
    int s,n;
    cout<<"请输入人数：";
    cin>>n;
    cout<<"请输入间隔：";
    cin>>s;
    Node<int> *u=new Node<int>(1,0);
    u->link=u;                               //构成循环链表
    Node<int> *q=u;
    for(int i=2;i<=n;i++)
    {
        q->link=new Node<int>(i,q->link);
        q=q->link;
    }
    Josephus(u,s);
    cout<<endl;

}

小帮你一下！

#3

yoyolive2010-10-17 19:47

#4

xin3109232010-10-19 13:33

看来还得在回去继续看书去

#5

tanghf10142010-10-24 22:50

试试这个
#include<stdio.h>
#include<malloc.h>
typedef  struct node
{
    int data;
    struct node *next;
}Lnode ,*Linknode;
Linknode Create_node (int i)
{
    int j;
    Linknode p,q,head;
    p=q=(Linknode)malloc(sizeof(Lnode));
    head=p;
    for(j=1;j<i;j++)
    {
        p=(Linknode)malloc(sizeof(Lnode));
        q->next =p;
        q=p;
    }
    q->next =head;
    return head;
}
void Josep_linklist( Linknode Josep_link,int s,int m)
{
    Linknode p,pre,q;/*p指向当前的节点，pre指向其前驱节点*/
    int count;
    p=Josep_link;
    for(count =1;count<s;count++)  /*查找第s个节点，并用p指向第s各节点*/
    {
        p=p->next ;
    }
    printf(" 输入约瑟夫的序列：");
    while (p!=p->next )  /*输出n-1个元素的节点*/
    {
        for(count=1;count<m;count++)
        {
            pre=p;

            p=p->next ;
        }
        q=p;
        printf("%d\t",p->data);
        pre->next =p->next;
        free(q);

        p=pre->next ;
    }
    printf("%d\t",p->data );

    free (p);
}

void main()
{
    Linknode j,k;
    int k1,k2;
    int m,p;
    int n=0;
    printf("请输入你想创建josep的个数：\n");
    scanf("%d",&m);
    k=j=Create_node(m);
    printf(" 请输入josep中的数据：\n");
    while(n<m)
    {
        scanf("%d",&p);
        j->data =p;
        j=j->next ;
        n++;
    }
    printf("请输入你想输入的开始位置和数到第几个输出：\n");
    scanf("%d,%d",&k1,&k2);
    Josep_linklist(k,k1,k2);
}

运行OK

#6

意义2010-10-25 16:41

#include<iostream.h>
#include<stdlib.h>
template<class T>
struct CircLinkNode//循环链表结点定义
{ T data;//数据域
  CircLinkNode<T> *link;//指针域
  //仅初始化指针成员的构造函数
  CircLinkNode(){link=NULL;}
  //初始化数据与指针成员的构造函数
  CircLinkNode(T& x)
  {data=x;link=NULL;}
};

template<class T>
class CircList//无附加头结点的循环链表类定义
{ private:
    CircLinkNode<T> *first,*last;//头指针，尾指针
  public:
    CircList();//无参构造函数
    CircLinkNode<T> *getHead()const{return first;}//获取头指针
    void input(int n);//输入函数
    void output(int n);//输出函数
};
template<class T>
CircList<T>::CircList()
{ //无参构造函数
  first=last=new CircLinkNode<T>;
  last->link=first;
}

template<class T>
void CircList<T>::output(int n)
{ //输出无附加头结点的循环链表中n个结点的数据
  CircLinkNode<T> *current=first;
  cout<<"循环链表各结点的数据值为:"<<endl;
  for(int i=1;i<=n;i++)
  { cout<<current->data<<" ";
    current=current->link;
  }
  cout<<endl;
}

template<class T>
void CircList<T>::input(int n)
{ //用后插法输入含n个结点的无附加头结点的循环链表
   CircLinkNode<T> *newNode;
   T value;
   cout<<"请输入"<<n<<"个结点的数据值"<<endl;
   for(int i=1;i<=n;i++)
   { //创建第i个结点
     cin>>value;
     newNode=new CircLinkNode<T>(value);
     if(newNode==NULL)
     { cerr<<"存储分配错误！"<<endl;exit(1);}
     if(i==1)
     {//创建第1个结点
       first=last=newNode;
       last->link=first;
     }
     else
     { //创建其它结点
       last->link=newNode;
       last=newNode;
       last->link=first;
     }
    }
}
template<class T>
void Josephus(CircList<T>& Js,int n,int m)
{ CircLinkNode<T> *p=Js.getHead(),*pre=NULL;
  int i,j;
  for(i=0;i<n-1;i++)//执行n-1次
   { for(j=1;j<m;j++) //数m-1人
      { pre=p;p=p->link;}
     cout<<"出列的人是"<<p->data<<endl;//输出
     pre->link=p->link;delete p;//删去
     p=pre->link;
   }
   cout<<"幸运者为"<<p->data<<"号"<<endl;
}

void main()
{ CircList<int> clist;
  int n,m;
  cout<<"输入旅客人数和报数值:";
  cin>>n>>m;
  clist.input(n);//输入含n个结点的循环链表
  //输出2*n个结点的数据值，观察链表是否为循环的
  clist.output(2*n);
  Josephus(clist,n,m);//调用约瑟夫函数
}