JAvaチェーンテーブル、スタック、キュー、ツリーの実装

6513 ワード

最近何気なく1冊の本をめくって、暇に何行かのコードを書いて、いくつかのよく使われるデータ構造を実現して、後で調べる準備をします.
一、リニアテーブル(チェーンテーブル)
1、ノード定義
/**      
 * @author colonel
 *
 */
class Node {
	public int data;
	Node next=null;
	public Node(int data){
		this.data=data;
	}
	
}
、チェーンテーブル操作類
/**     
 * @author colonel
 *
 */
public class operateClass {

	public Node headNode=null;
	
	/*        
	 * @param data       
	 */
	public Node addNode(int data){ 
		Node newNode=new Node(data);
		if (headNode==null) {
			headNode=newNode;
			newNode.next=null;
			return headNode;
		}
		Node tempNode=headNode;
		while (tempNode.next!=null) {
			//tempNode=headNode;
			tempNode=tempNode.next;
		}
		tempNode.next=newNode;
		return headNode;
	}
	
	/**    
	 * @param        
	 * 
	 */
	public boolean delNode(int index){
		
		if (index<1||index>length()) {
			return false;
		}
		
		if (index==1) {
			headNode=headNode.next;
			return true;
		}
		Node preNode=headNode;
		Node curNode=preNode.next;
		int count=2;
		while (curNode!=null) {
			if (count==index) {
				preNode.next=curNode.next;
				return true;
			}
			preNode=curNode;
			curNode=curNode.next;
			count++;			
		}		
		return true;
	}
	
	/**      
	 * @return       
	 */
	public int length(){
		int length=0;
		Node temp=headNode;
		while (temp!=null) {
			length++;
			temp=temp.next;
		}		
		return length;
	}
	
	
	
	/**           
	 * @return            
	 */
	public Node orderList(){
		Node nextNode=null;
		int temp=0;
		Node curNode=headNode;
		while (curNode.next!=null) {
			nextNode=curNode.next;
			while (nextNode!=null) {
				if (curNode.data>nextNode.data) {
				temp=curNode.data;
				curNode.data=nextNode.data;
				nextNode.data=temp;
			
			}
			nextNode=nextNode.next;
			}
				curNode=curNode.next;
		
		}
			return headNode;
	}
	
	/**
	 *             
	 */
	public void redRepeat(){
		if (length()<=1) {
			return;
		}
		Node curNode=headNode;	
		while (curNode!=null) {
			Node insidNode=curNode.next;
			Node insidPreNode=insidNode;
			while (insidNode!=null) {
				if (insidNode.data==curNode.data) {
					insidPreNode.next=insidNode.next;				
					//return;
				}
				insidPreNode=insidNode;
				insidNode=insidNode.next;			
			}
			
			curNode=curNode.next;

			
		}	
	}
	
	/**            
	 * @param hNode      
	 */
	public void reversePrint(Node hNode){
		if (hNode!=null) {
			reversePrint(hNode.next);
			System.out.println(hNode.data);
		}
	}

	/**
	 *                 
	 */
	public void printList(){
		Node tmpNode=headNode;
		while (tmpNode!=null) {
			System.out.println(tmpNode.data);
			tmpNode=tmpNode.next;
		}
	}
			
	
}

二、桟
1、このスタックは配列を用いて実現し、具体的なスタック操作クラス
class MyStack{
	private Object[] stack;
	 int top=-1;
	public MyStack(){
		stack=new Object[10];
	}
	public boolean isEmpty(){
		return top==0;
	}
	
	/**      (   )
	 * @return
	 */
	public E peek(){
		if (isEmpty()) {
			return null;
		}
		return (E) stack[top];
	}
	/**      
	 * @return     
	 */
	public E pop(){
		E e=peek();
		stack[top]=null;
		top--;
		return e;
	}
	/**  
	 * @param item     
	 * @return       
	 */
	public E push(E item){
		//ensureCapacity(top+1);
		stack[++top]=item;
		return item;
	}
	/**    
	 * @param size
	 */
	public void ensureCapacity(int size){
		int len=stack.length;
		if (size>len) {
			int newLen=10;
			stack=Arrays.copyOf(stack, newLen);
			
		}
	}
	/**      
	 * @return
	 */
	public E getTop(){
		if (top==-1) {
			return null;
		}
		return (E) stack[top];
	}
	

}


三、行列
このキューはチェーンで実装されます
1、キューノード定義
/**
 * @author colonel
 *     
 * @param 
 */
class queueNode{
	queueNode nextNode=null;
	Elem data;
	public queueNode(Elem data){
		this.data=data;
	}
	
}
、キュー操作クラス、
/**
 * @author colonel
 *     
 * @param 
 */
class MyQueue{
	private queueNode headNode=null;
	private queueNode tailNode=null;
	private queueNode lastNode=null;
	
	/**         
	 * @return   true or false
	 */
	public boolean isEmpty(){
		return headNode==tailNode;
	}
	/**    
	 * @param data      
	 */
	public void put(Elem data){
		queueNode newNode=new queueNode(data);
		if (headNode==null&&tailNode==null) {
			headNode=tailNode=newNode;
			//tailNode=headNode.nextNode;
			lastNode=tailNode.nextNode;
			return;
		}
		tailNode.nextNode=newNode;
		tailNode=newNode;
		lastNode=tailNode.nextNode;
		//tailNode=tailNode.nextNode;
	}
	/**    
	 * @return                                                                          
	 */
	public Elem pop(){
		if (headNode==lastNode) {
			return null;
		}
		queueNode tempNode=headNode;
		Elem statElem=tempNode.data;
		headNode=tempNode.nextNode;
		return statElem;
	}
		
	/**      
	 * @return   
	 */
	public int size(){
		if (isEmpty()) {
			return 0;
		}
		int length=0;
		queueNode temp=headNode;
		while (temp!=null) {
			length++;
			temp=temp.nextNode;
		}
		return length;
	}
	
	
	
}


四、二叉木
1、ノード定義
/**     
 * @author colonel
 *
 */
class TreeNode{
	public int data;
	public TreeNode leftNode;
	public TreeNode rightNode;
	public TreeNode(int data){
		this.data=data;
		this.leftNode=null;
		this.rightNode=null;
	}
	
}

2、ツリー操作類
/**        
 * @author colonel
 *
 */
class OperateTree{
	public  TreeNode rootNode;
	public OperateTree(){
		rootNode=null;
		
	}
	/**         
	 * @param data       
	 */
	public void insert(int data){
		TreeNode newNode=new TreeNode(data);
		if (rootNode==null) {
			rootNode=newNode;
		}else {
				TreeNode current=rootNode;
				TreeNode parent;
			while (true) {
				parent=current;
				if (data myQueue=new LinkedList<>();
		myQueue.add(rootNode);
		while (!myQueue.isEmpty()) {
			TreeNode tempNode=myQueue.poll();
			System.out.println(tempNode.data);
			if (tempNode.leftNode!=null) {
				myQueue.add(tempNode.leftNode);
			}
			if (tempNode.rightNode!=null) {
				myQueue.add(tempNode.rightNode);
			}
		}
	}
	

五、まとめ
  データ構造が何であるかをよりよく理解するには、引き続き探求し、覚えておく必要があります.by:colonel