问题描述

设编号为1,2,3 ……,n(n > 0)个人按顺时针方向围坐一圈,没人持有一个正整数密码。开始时任意给出一个报数上限值m,从第一个人开始顺时针方向自 1 起顺序报数,报到 m 时停止报数,报 m 的人出列,并将他的密码作为新的 m 值,从他在顺时针方向上的下一个人开始重新从 1 开始顺序报数;如此下去,直到所有人全部出列为止。
基本要求:设计程序模拟该过程,给出出列人的编号序列。
测试数据:n=7,密码依次为:3,1,7,2,4,8,4,m= 20。

问题分析:

  1. 要求输出编号序列,所以得保存每个人的编号;
  2. 在出列过程中,要用到该出列人的密码,所以得保存密码。
  3. 顺时针方向围坐一圈。
基于以上三点,可以设采用不带头结点单向循环链表。如下:

代码实现:

结点类:
public class Node {	private int no;	private int mima;	private Node next;	public Node(int no, int mima) {		this.no = no;		this.mima = mima;	}	public int getNo() {		return no;	}	public void setNo(int no) {		this.no = no;	}	public int getMima() {		return mima;	}	public void setMima(int mima) {		this.mima = mima;	}	public Node getNext() {		return next;	}	public void setNext(Node next) {		this.next = next;	}}

不带头结点的单向循环链表类:

//不带头结点的单向循环链表public class NoHeadOneWayLoopList {	private Node head;	private int currentSize;	public NoHeadOneWayLoopList() {		head = null;		currentSize = 0;	}	// 返回下标为 i 的那个结点的指针,结点编号从0开始;	public Node index(int i) {		if (i >= 0 && i < currentSize) {			Node temp = head;			for (int j = 0; j < i; j++) {				temp = temp.getNext();			}			return temp;		} else {			System.out.println("下标超界!");			return null;		}	}	// 插入结点,使其成为第 i 个结点。	public void insertNode(Node node, int i) {		if (head == null) {			head = node;			head.setNext(head);		} else {			Node temp = index(i - 1);			node.setNext(temp.getNext());			temp.setNext(node);		}		currentSize++;	}	public void deleteNode(int i) {		if (i == 0) {			if (currentSize == 1) {				head = null;			} else {				Node preNode = index(currentSize - 1);				Node deletedNode = preNode.getNext();				head = deletedNode.getNext();				preNode.setNext(head);				deletedNode.setNext(null);			}		} else {			Node preNode = index(i - 1);			Node deletedNode = preNode.getNext();			head = deletedNode.getNext();			preNode.setNext(head);			deletedNode.setNext(null);		}		currentSize--;	}	public Node getHead() {		return head;	}	public void setHead(Node head) {		this.head = head;	}	public int getCurrentSize() {		return currentSize;	}	public void setCurrentSize(int currentSize) {		this.currentSize = currentSize;	}}
测试类:

public class TestClass {	private static NoHeadOneWayLoopList list;	public static void main(String[] args) {		list = new NoHeadOneWayLoopList();		list.insertNode(new Node(1, 3), 0);		list.insertNode(new Node(2, 1), 1);		list.insertNode(new Node(3, 7), 2);		list.insertNode(new Node(4, 2), 3);		list.insertNode(new Node(5, 4), 4);		list.insertNode(new Node(6, 8), 5);		list.insertNode(new Node(7, 4), 6);		f(list.index(list.getCurrentSize() - 1), 20);	}	public static void f(Node first, int m) {		if (first.getNext() != first) {			for (int i = 0; i < m - 1; i++) {				first = first.getNext();			}			Node deletedNode = first.getNext();			int mima = deletedNode.getMima();			System.out.print(deletedNode.getNo() + "   ");			first.setNext(deletedNode.getNext());			deletedNode.setNext(null);			list.setCurrentSize(list.getCurrentSize() - 1);			f(first, mima);		} else {			System.out.print(first.getNo() + "   ");		}	}}

输出结果:



收藏 打印