1、问题描述
以邻接两个数之和为素数的方式，将1~n的n个自然数排列成环状，构成一个素数环。
2、基本要求
设计算法对任意输入的自然数n，求解素数环问题。 如果没有解，会给出相应的提示； 否则，依次输出素数循环中的数据。
3、思路
(1)导入顺序表类Sqlist和链队列类LinkQueue后，作为用于存储素数循环的数据要素的顺序表，制作Sqlist类的对象l，制作LinkQueue类的对象q，并追加到素数循环中
2 )初始化顺序表l和队列Q:在顺序表l中添加1，在q队列中添加2~n的所有自然数。
)3)将出队队伍的开头要素p和素数环的最后数据要素q相加。
(a )如果p不是队伍的最后一个。 如果两个数之和是素数，则将p添加到素数环中，并递归添加以下数。 如果递归成功，则返回结果。 否则，删除素数环的最后一个元素并排队等待。 否则，p表示暂时无法处理，必须再次入队等待，重复该过程(3)。
) b )如果p是队友。 还需要判断添加到素数循环第一个数据元素的和的数量是否为素数。 素数的情况下，将p追加到素数循环中，结束计算。 如果不是素数，则p必须再次入队并等待，等待队列为空，或者遍历队列中的所有数据元素一次，然后重复(3)直到无法加入素数循环。
以六种元素的素数环为例
首先在顺序表(CS )队列中添加1，将链表队列初始化为2到6
将从链表队列中弹出的开头元素和顺序表的末尾元素分别相加，判断两个数之和是否为素数。 将弹出的链表元素添加到顺序表中，否则将弹出的链表元素放回链表队列，等待下一个堆栈
如果发现链表队列中的元素无论如何排序插入都无法构成素数环(这里在代码中会有判断),则将顺序表的队尾元素弹出并入链表队列中（关键）这类似于使用回溯法的原理
直接打代码
首先，构建节点类、顺序队列类和链队列类
节点类public class node { public objectdata； 公共节点下一个； public Node () {this )，null )； }publicnode(objectdata ) this (data，null )； }publicnode(objectdata，Node next ) { this.data=data； this.next=next； }方法的接口
publicinterfaceiqueue { void clear (； 布尔型isempty (； 输入长度(； Object peek (； voidoffer(Objectx ) throws Exception； 对象池(； objectgetrear (布尔标志； void display (； }序列队列类
publicclasscirclesqueueimplementsiqueue { private object [ ] queue elem； //队列存储空间private int front； //团队领导引用private int rear； //队尾引用publiccirclesqueue(intmaxsize ) { front=rear=0； queueElem=new Object[maxSize]； //清空队列@Override public void clear () { front=rear=0； //判断队列是否为空@ overridepublicbooleanisempty ({ return front==rear； //队列长度@Override public int length () return ) rear-front%queueElem.length ) queueelem.length； (//领导团队的第一个元素@Override public Object peek ) ) if ) front==rear ) { return null； }else { return queueElem[front]； }//入队@ overridepublicvoidoffer (objectx ) throws exception (if ) ) rear1) %queueElem.length==front ) thrownewewexwexexexexexexextion
eElem[rear]=x; rear=(rear+1)%queueElem.length; } //出队 @Override public Object poll() { if(front==rear) return null; else { Object t = queueElem[front]; front = (front+1)%queueElem.length; return t; } } //如果flag为true,表示将队尾元素弹出,否则只取出 @Override public Object getrear(boolean flag) { Object x = queueElem[rear-1]; if (flag) rear=(rear-1)%queueElem.length; return x; } //输出队列中的所有元素（从队首到队尾） @Override public void display() { if(!isEmpty()){ for(int i=front;i!=rear;i=(i+1)%queueElem.length){ System.out.print(queueElem[i].toString()+" "); } } }}链队列类
public class LinkQueue implements IQueue { private Node front;//队首指针 private Node rear;//队尾指针 //链队列类的构造函数 public LinkQueue(){ front = rear = null; } @Override public void clear() { front = rear = null; } @Override public boolean isEmpty() { return front==null; } @Override public int length() { Node p = front; int length = 0; while (p!=null){ p=p.next;//指针下移 ++length; } return length; } @Override public Object peek() { if(front!=null) return front.data; else return null; } @Override public void offer(Object x) throws Exception { Node p = new Node(x); if(front!=null){ rear.next=p; rear=p; }else { front=rear=p; } } @Override public Object poll() { if(front!=null){ Node p = front; front = front.next; if(p==rear) rear = null; return p.data; } return null; } @Override public Object getrear(boolean flag) { return null; } @Override public void display() { }} 定义方法用于求出素数环 public class Prime_Circle { private CircleSqQueue cs;//CircleSqQueue(顺序表)用于存放素数环的数据元素 private LinkQueue lq;//LinkQueue(链队列)用于存放未加入到素数环中的自然数 private int length;//顺序表的长度 public Prime_Circle(int length){ this.length=length; cs = new CircleSqQueue(length+1);//构造顺序表 lq = new LinkQueue();//构造链队列 } //判断正整数是否为素数 public boolean isPrime(int num){ if(num==1) return false; Double n = Math.sqrt(num); for(int i=2;i<=n.intValue();i++){ if(num%i==0) return false; } return true; } public void makePrimeRing()throws Exception { if(length%2!=0){//length为奇数则素数环不存在,因为肯定有两个奇数相邻,而奇数与奇数的和肯定为偶数 throw new Exception("素数环不存在"); } cs.offer(1);//初始化顺序表(cs)的首结点为1 for(int i=2;i<=length;i++){ lq.offer(i);//初始化链队列 } insertRing(2,length); cs.display();//调用方法 } //在CircleSqQueue中插入第m个数,使其与顺序表中第m-1个数的和为素数 public CircleSqQueue insertRing(int m,int n)throws Exception{ int count=0;//设置计数器，记录遍历队列中的数据元素的个数，防止在一次循环中重复遍历 while (!lq.isEmpty()&&count<=n-m){//队列非空且为重复遍历队列 int p = (int) lq.poll();//弹出链队列(lq)中的头元素 int q = (int) cs.getrear(false);//取出顺序表(cs)中的尾元素 if(m==n){//相等则表示此时链队列(lq)中只有一个元素,此时不仅要判断与顺序表第m-1个元素之和为素数,还有判断与第一个元素之和是否为素数 if(isPrime(p+q)&&isPrime(p+1)){ cs.offer(p);//将p入队 return cs; }else {//不满足条件,则将该数再放进链队列(lq)中，等待下次出队进行判断 lq.offer(p); } }else if(isPrime(p+q)){//链队列(lq)中还未遍历最后一个元素且此时满足素数环的条件 cs.offer(p);//将从链队列(lq)中取出的数加入到顺序表(cs)队尾 if(insertRing(m+1,n)!=null){//调用递归函数 return cs; } //如果返回为空则将顺序表(cs)中的队尾元素弹出并将其放进链队列(lq)的队尾中 lq.offer(cs.getrear(true)); }else {//从链队列(lq)中取出的数不满足素数环的条件且未遍历到最后一个元素,则将q继续入列 lq.offer(p); } count++;//遍历次数增一 } return null; }} 测试类 public class PrimeRing_Test { public static void main(String[] args) throws Exception { Scanner scanner = new Scanner(System.in); System.out.println("请输入要构造的素数环的长度:"); int length; while (true){ length = scanner.nextInt(); if(length>0){ break; } System.out.println("输入的长度不合法，请重新输入!!!"); } Prime_Circle pc = new Prime_Circle(length); pc.makePrimeRing();//调用方法显示结果 }}效果如下