Java가 실현한 순환 단일 체인 테이블과 조세프 링의 실현

노드 구조체 정의


자바로 노드를 실현하려면 내부 클래스의 형식을 사용하는 것이 좋다.


Node 세부 코드 블록

private class Node{
		E data;
		Node next;
		public Node() {
			this(null, null);
		}

		public Node(E data) {
			this(data, null);
		}

		public Node(E data, Node next) {
			this.data=data;
			this.next=next;
		}
	}

단방향 순환 체인 테이블의 실현

import  .List;

public class LinkedListSinglyCircular implements List {
	Node head;
	Node rear;
	int size;
	public LinkedListSinglyCircular() {
		head = new Node();
		head.next=head;
		rear = head;
		size = 0;
	}
	private class Node{
		E data;
		Node next;
		public Node() {
			this(null, null);
		}

		public Node(E data) {
			this(data, null);
		}

		public Node(E data, Node next) {
			this.data=data;
			this.next=next;
		}
	}
	@Override
	public int getSize() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return getSize()==0;
	}

	@Override
	public void add(int index, E e) {
		// TODO Auto-generated method stub
		if(index<0||index>size) {
			throw new IllegalArgumentException(" ");
		}
		// 
		Node n=new Node(e);// e
		if(index==0) {
			n.next=head.next;
			head.next=n;
			if(isEmpty()){//   
				rear=n;
				rear.next=rear;
			}else{
				rear.next=head.next;
			}
		}
		// 
		else if(index==size) {
			n.next=rear.next;
			rear.next=n;
			rear=n;
		}
		// 
		else {
			Node p=head;
			for(int i=0;isize-1) {
			throw new IllegalArgumentException(" ");
		}
		if(index>0) {
			index=index%size;
		}else {
			index=index%size+size;
		}
		Node p=head;
		for(int i=0;isize-1) {
			throw new IllegalArgumentException(" ");
		}
		E flag=null;
		if(index==0) {// 
			Node p=head;
			flag=p.next.data;
			head.next=p.next.next;
			if(size==1) {
				rear=head;
				rear.next=rear;// rear , ,
			}
		}else if(index==size-1) {
			// 
			flag=rear.data;
			Node p=head;
			while(p.next!=rear) {
				p=p.next;
			}
			p.next=rear.next;
			rear=p;
		}
		else {
			// 
			Node p=head;
			for(int i=0;i show(){
		SingleLinkList l=new SingleLinkList<>();
		Node p=head;
		while(size>0) {
			p=p.next.next;
			Node n=p.next;	
			p.next=p.next.next;
			l.addLast((Integer)n.data);
			size--;// !!!!
		}
		return l;
	}
	
}

요셉 링

public SingleLinkList show(){
		SingleLinkList l=new SingleLinkList<>();
		Node p=head;
		while(size>0) {
			p=p.next.next;
			Node n=p.next;	
			p.next=p.next.next;
			l.addLast((Integer)n.data);
			size--;// !!!!
		}
		return l;
	}	

테스트

package p02. ;

public class TestlinklistCircular {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedListSinglyCircular t=new LinkedListSinglyCircular();
	    for(int i=39;i>=1;i--) {
	    	t.addFirst(i);
	    }
	     System.out.println(t);
	     System.out.println(t.show());
	}

}

테스트 결과

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39]
[3,6,9,12,15,18,21,24,27,30,33,36,39,4,8,13,17,22,26,31,35,1,7,14,20,28,34,2,11,23,32,5,19,37,16,38,29,10,25]

위쪽은 사람의 초기 정류장 순서이고, 아래쪽은 자살 순서다.

좋은 웹페이지 즐겨찾기