关于数据结构

        数据结构这个词，让人听起来就觉得晦涩难懂。其实很多东西，你不打开它的包装是很难知道它究竟是什么的，就像之前说的队列，打开它华丽的包装，其实里面装的就是数组。

        数据结构是这样定义的：是相互之前存在着一种或多种特定关系的数组元素的集合。将这样一句话封装成这样一个词，大概是显得高深一点吧，但我们打破这个封装，就会对所谓的数据结构稍有了解了。那我们继续撕开它的包装，数据结构是可以这样划分的：线性结构，树形结构，图状结构和集合结构（如下图）。

                        

        当我们可以用图形表示一个东西时，那它就不再高深难懂。当然，数据结构不可能只包括这些简单的内容，不过这里我们先实现这些。

        

【第一篇——单向链表】

        链表，也就是我们所说的线性结构，而所谓单向，那就不言而喻了。

        首先要写一个类来定义链表中所需要的量：

public class JNode {
	public int Value;     //记录的值
	public JNode Next;    //指向下一个节点的指针
}

         现在我们就仿照数组实现的队列来写链表，先实现它最基本的插入方法。这时会出现一个问题，当我们传参数时，肯定会传入要插入的元素，但是位置呢？所以我们需要有两种方法，一种是默认插入到最后的，另一种是插入到指定位置的。这就为我们编程提供了一种很好的思想——为用户着想。

        如果把两种方法都写一遍，就会发现方法内容其实是重复的，那我们是不是可以在默认插入到最后的方法中直接调用插入到指定位置的方法，只不过指定的位置就是链表末端，这样就只需要写一遍具体方法了。

        在写具体方法时，又要考虑到链表本身的情况，它是否有元素，或者传入的要插入的位置是否存在等等，我们必须要考虑到每一种情况才不会让用户使用是找到bug。

        private JNode head=null;    //定义一个头指针
	private int count = 0;      //count记录个数
        
        //默认插入到最后
	public void insert(JNode node){
		insert(count,node);
	}
	
	//插入到pos处
	public void insert(int pos,JNode node){	
		//如果pos<0或者pos>count，直接返回
		if(pos<0||pos>count){
			return;
		}
		//如果链表为空，直接插在第一位
		if(count==0){
			head=node;
			count++;
			return;
		}
		//正常情况
		JNode flag = head;    //定义一个标志
		//循环找到pos的位置
		for(int i=0;i<pos-1;i++){
			flag = flag.Next;	
		}
                //把指定位置后面的元素放在插入元素的后面
		node.Next = flag.Next;
                //再把要插入的元素赋给指定位置后面的元素
		flag.Next = node;
		//每插入一个元素，count就++
		count++;
	}

         既然有插入，那对应就要有删除方法，删除的思想和插入是一样的，但还需增加一点，就是返回给用户他删除的元素：

        //默认在头删除
	public JNode delete(){
		return delete(0);	
	}
	
	//在Pos出删除
	public JNode delete(int pos){

		//如果删除位置不对
		if(pos <0 || pos >count -1){
			System.out.println("删除位置错误");
			return null;
		}
		//如果没有元素
		if(count == 0){
			System.out.println("数组元素为空");
			return null;
		}
		JNode flag = head;    //定义一个标志
		//如果只有一个元素
		if(count==1){
			head = null;
			count = 0;
			return head;		
		}
		//如果pos=0
		if(pos==0){
			head=head.Next;
			flag.Next=null;
			count--;
			return flag;
		}	
		//循环找到pos的位置
		for(int i=0;i<pos-1;i++){
			flag = flag.Next;	
		}
		JNode temp = flag.Next;
		flag.Next = temp.Next;
		temp = null;
		count--;
		return temp;	
	}

         后面还要有获取元素的方法，获取个数的方法等等，相对简答一点，这里就不说明了，只要记得为用户着想就不会有问题。

         线性结构不仅包括链表，也包括数组实现的队列。写完链表就会发现，其实它们的区别并不大，只是用另一种方法实现一样的东西，在用途上是没有区别的。但还是可以轻易的发现它们各自的优缺点：一方面，数组实现的队列很容易获取到它的个数，因为数组是有下标的，个数就是下标+1，但链表就需要定义一个计数器，插入元素时+1，删除元素的-1；另一方面，队列在插入元素时，需要把其余的元素一个一个拷贝到临时数组中，在一个一个的拷贝回去，过程比较繁琐，但链表只需要把指针指向不同的元素就可以做到了。

 

 【第二篇——树】

        对于树来说，我们先简单的了解一下如何建树。

        树，这个字已经可以说明很多了，比如它肯定有一个根节点，然后分支出去就会有左节点、右节点，每个节点会有相应的值，有这几个量就可以实现树了。同样地，我们新建一个类来定义它们：

public class TreeNode {
	public int value;
	public TreeNode left;
	public TreeNode right;
}

       现在我们开始建树，当我们把每个值放到节点中时，要考虑它和它的根节点值的大小，这里将较小值放在左节点，较大值放在右节点（反过来也一样），等于的情况可以随意设定。那我们就需要考虑一个问题，用户在用这个方法时，他不会告诉你哪个是根节点，它只会输入要放入树中的数据，考虑到这点，就可以很容易的建好树了：

        private TreeNode root;	   //定义一个根节点
	//增加节点  值为value
	public void add(int value){		
		//建一个临时的树
		TreeNode temp = new TreeNode();		
		//把value值赋给temp
		temp.value = value;		
		//添加节点 在根下面添加temp
		//如果根节点为空，直接跳出
		if(root == null){
			root = temp;
			return;
		}
		//不为空，则在root下添加temp
		add(root,temp);
	}
	//增加节点，在head下面添加node
	public void add(TreeNode head ,TreeNode node){
		//判断节点大小，如果node<head,放到左边
		if(node.value<=head.value){		
			//如果左边不为空
			if(head.left!=null){
				add(head.left,node);
			}
			//如果左边为空
			else{				
				head.left=node;
			}
		}
		//如果大于，放右边
		else{
			//如果右边不为空
			if(head.right!=null){
				add(head.right,node);
			}
			//如果右边为空
			else{
				head.right=node;
			}		
		}	
	}

         其实现在我们已经建好了树，但是对于用户来说，它虽然可以把数据放进去，但却看不到这个树，那我们就需要写一个遍历树的方法，让用户看到这个树，这里写的是中序（左根右）遍历：

        //中序遍历
	public void middle(){
		middleEx(root.left);
		System.out.println(root.value+"  ");
		middleEx(root.right);
	}	
	private void middleEx(TreeNode node){
		if(node==null)
			return;
		middleEx(node.left);
		System.out.print(node.value +" ");
		middleEx(node.right);
	}

         现在只是以中序输出了数据，其实最佳方法是用图形来展示出这个树，毕竟图形化界面才会真正让用户简单明了的看到数据的存放。