JAvaチェーンテーブル、スタック、キュー、ツリーの実装
6513 ワード
最近何気なく1冊の本をめくって、暇に何行かのコードを書いて、いくつかのよく使われるデータ構造を実現して、後で調べる準備をします.
一、リニアテーブル(チェーンテーブル)
1、ノード定義
二、桟
1、このスタックは配列を用いて実現し、具体的なスタック操作クラス
三、行列
このキューはチェーンで実装されます
1、キューノード定義
四、二叉木
1、ノード定義
2、ツリー操作類
五、まとめ
データ構造が何であるかをよりよく理解するには、引き続き探求し、覚えておく必要があります.by:colonel
一、リニアテーブル(チェーンテーブル)
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