java之浅谈数据结构

 

Java之浅谈数据结构

 

      数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

 

   上边应该算是比较官方的解释了，具体定义姑且不论，今天主要谈一谈队列，链表和二叉树。其中队列又制作了泛型的版本，在此仅供参考。文中如有不当之处，还望各路英雄指正。

 

 

 

1、先谈队列，这里以string类型的简易队列为例

 

 

 

       建立队列要先建立一个数组，然后来实现队列的功能。那么我们要什么样的功能呢？起码添加删除是少不了的，插入和获取也可以制作一下。先不考虑怎么实现，先考虑有什么是我们需要的，先写上，再来思考怎么做。

 

public class array {

	//定义一个长度为0的初始数组 
	String[] src = new String[0];

                   /**
	 * 往队列中添加一个元素
	 */
	public void add(String s){

	}
		 
	/**
	 * 取出对应下标位置的元素
	 * @param index 元素的下标位置
	 * @return 返回取得的元素
	 */
	public String get(int index){

	}
	
	
	/**
	 * 容器中的元素个数
	 * @return 返回元素个数
	 */
	public int size(){

	}

	/**
	 * 删除指定下标的元素
	 */
	public void delete(int index){

	}
	
		
	/**
	 * 将值为s的元素删除
	 * @param s
	 */
	public void delete(String s){

	}
		
	/**
	 * 将指定元素s插入指定位置index
	 * @param s
	 * @param index
	 */
	public void insert(String s,int index){

	}
		
	/**
	 * 将指定位置的元素修改为指定的值
	 * @param s
	 * @param index
	 */
	public void modify(String s,int index){

	}
		

}

 

 

      因为上一篇文中已经给出了较为完全的代码，这里仅给手懒的孩纸们发一个add（）方法作为借鉴，思路是建立一个新的更大的数组来存放数据，然后把数据放进去，把原数组名指向新的数组的地址。多嘴一句，C++在这里需要delete原来的指针。

 

public void add(String s){
		//定义新数组，长度是原始数组长度+1
		String[] dest = new String[src.length+1];
		//将原数组中的数据按下标顺序拷贝到新数组
		for(int i=0;i<src.length;i++){
			dest[i]=src[i];
		}
		//将新元素放到新数组最后一个下标位置
		dest[src.length] = s;
		//将新数组赋给原数组
		src = dest;	
	}

     个人自认为注释写得已经比较完善了，这里不多解释。快速进入下一话。

 

 

 

 

2、现在我们来谈一个比较成熟强大的队列。 

 

       建立队列有很多地方需要注意，事实上我们像刚才上文中的简易队列一样每添加一个就要申请一个新的空间是比较麻烦的，而且上文的队列只能适用于单一的类型，如果变量类型不同还要重新编写，实在过于麻烦。

 

       这一点要用到泛型，这是java的一个很有用的特色，也是多态的重要体现。

 

        首先建立一个队列，和上边的类似，但是这回我们要定义一个可以适用于任何类型的队列。

public class array<E> {
//E是变量的类型	
	private int count=0;//数组中有值的个数
	private  int increase=5;//每次数组扩充大小
	private  int start=10;//初始数组大小
	private  Object[] src;//声明数组，注意，所有变量本质都是一个对象，
        //所以我们可以建立一个“对象”数组，它是真的可以存放任意对象的！
}

       然后考虑到使用者水平可能不同，写两种构造方法：    

//无参构造函数-----小白版
	array(){
		src=new Object[start];
	}
	
	//有参构造函数-----大侠版
	array(int increase,int start){
		this.increase=increase;
		this.start=start;
		src=new Object[start];
	}

 

 

       第一种一切采用默认值，第二种一切都由使用者确定。

 

      之后添加各种方法，当然最好在建立队列类的时候就先写上，完了再填充内容。

 

 

 

/**
	 * 装数据的方法
	 * @param s 要装入容器的数据，这里E是变量的类型
         */
	public void add(E s){
		if(count==this.size())//若原数组已满
		{	
			//定义新数组，长度是原始数组长度+increase
			Object[] dest = new Object[src.length+increase];
			//将原数组中的数据按下标顺序拷贝到新数组
			for(int i=0;i<this.count;i++){
				dest[i]=src[i];
			}
			//将新元素放到新数组最后一个下标位置
			dest[this.count] = s;
			//将新数组赋给原数组
			src = dest;	
		}
		else
			src[this.count] = s;//数组未满直接加
		count++;//数组中有值的个数+1
	}
	 

	
	 
	/**
	 * 取出对应下标位置的元素
	 * @param index 元素的下标位置
	 * @return 返回取得的元素，这里E是变量的类型
	 */
	public E get(int index){
		if(index<0||index>=src.length){	
			throw new RuntimeException("传入的下标超出边界："+src.length);
		}
		return (E)src[index];
	}
	
	
	/**
	 * 容器的长度
	 * @return 返回元素个数
	 */
	public int size(){
		return src.length;
	}	
	/**
	 * 容器中的元素个数
	 * @return 返回元素个数
	 */
	public int getcount(){
		return this.count;
	}	

	/**
	 * 删除指定下标的元素
	 */
	public void delete(int index){
		//定义新数组，长度是原始数组长度-1
		Object[] dest = new Object[src.length-1];
		//将原数组中的数据按下标顺序拷贝到新数组(跳过指定位置的元素)
		for(int i=0;i<index;i++){
			dest[i]=src[i];
		}
		for(int i=index+1;i<src.length;i++){
			dest[i-1]=src[i];
		}
		//将新数组赋给原数组
		src = dest;	
	}
	/**
	 * 将值为s的元素删除
	 * @param s
	 */
	public void delete(E s){
		for(int i=0;i<src.length;i++){
			if(src[i]==s)
				delete(i);
		}
	}
		
	/**
	 * 将含有字符s的元素删除---若要制作需要分别考虑每一种基础类型
	 * @param s
	
	public void delete(String s){
		for(int i=0;i<src.length;i++){
			if(src[i].contains(s))
				delete(i);
		}
	} */
		
	/**
	 * 将指定元素s插入指定位置index
	 * @param s
	 * @param index
	 */
	public void insert(E s,int index){
		//定义新数组，长度是原始数组长度+1
		Object[] dest = new Object[src.length+1];
		//将原数组中的数据按下标顺序拷贝到新数组
		for(int i=0;i<index;i++){
			dest[i]=src[i];
		}
		//将新元素放到新数组指定下标位置
		dest[index] = s;
		for(int i=index;i<src.length;i++){
			dest[i+1]=src[i];
		}
		//将新数组赋给原数组
		src = dest;	
	}
		
	/**
	 * 将指定位置的元素修改为指定的值
	 * @param s
	 * @param index
	 */
	public void modify(Object s,int index){
		//定义新数组，长度是原始数组长度
		Object[] dest = new Object[src.length];
		//将原数组中的数据按下标顺序拷贝到新数组
		for(int i=0;i<index;i++){
			dest[i]=src[i];
		}
		//将新元素放到新数组指定下标位置
		dest[index] = s;
		for(int i=index+1;i<src.length;i++){
			dest[i]=src[i];
		}
		//将新数组赋给原数组
		src = dest;	
	}

   其实这时候需要考虑很多了，包括使用者可能犯得所有错误，尤其是空指针和数组越界。

 

 

    最后是测试：

public class myarray {
	public static void main(String[] args) {

		// 创建队列对象，<>中表明具体类型
		array<String> array = new array();

		for (int i = 0; i < 10; i++) {
			String s = "元素" + i;
			// 将元素放入队列
			array.add(s);
		}
		
		//加一个
		array.add("新来的");
		//减两个个
		array.delete("元素4");
		array.delete(2);//下标为2，是第三个
		//插入一个
		array.insert("最新版", 6);//下标为6，是第七个
		//	改一个
		array.modify("就是这个",8);
		// 取出元素打印

		for (int i = 0; i < array.getcount(); i++) {
			String s = array.get(i);
			System.out.println(s);
		}

	}
}

 

 

3、链表

 

      终于解决完了队列，现在换换口味。

      链表是个看起来很简单的东西，直接接触到的只有头指针和计数变量，头指针实际上也是一个对象，这个对象有两个属性，一个是同一个类的一个新的对象（就相当于一个指向下一个对象的指针），另一个则是值（这个才是真正存放的东西）。

//链表的节点类，这两个是每个节点都具有的属性，但是链表最尾端的节点指向
//下一个的指针的空的
public class JNode {

	//定义一个储值属性
	public  int value;
	//定义一个指向下一个的指针（新的节点类对象，可以不起名）	
	public JNode Next;
}

 

 

//这个是链表类，它基于节点类
public class linearray {
	
	private JNode head;//定义一个头指针（节点类对象）；
	private int count=0;//定义一个变量用于计数；
	
}

 

 

       链表的每一节都有指向下一个对象的指针，这样就可以通过头指针调用出链表中存放的每一个值（以下代码存在于linearray类）：

//获得链表中的节点个数
        public int getcount(){
		return count;
	}
	//在最后边添加一个
	public void add(JNode node){
		insert(node,count);
                //提高代码的有效利用率，直接调用后边的insert方法
	}
	//删除第index+1个(因为从零开始，这里要注意数组时从0开始的)
	public JNode delete(int index){

                //先考虑特殊情况
		if(index<0||index>=count)
		{
			System.out.println("删除位置超出范围!");
			return null;//返回空，结束函数调用
		}
		if(count==0)
		{
			System.out.println("数组元素为空!");
			return null;
		}	
		//正常情况
		JNode flag = head ;//必须新建一个另外的浮动节点
		for(int i=0;i<index-1;i++)
		{
			flag=flag.Next;//浮动节点下移
		}
		flag.Next =(flag.Next).Next ;//跳过要删除的
		count--;//计数减一（跳过的掉链了，脱离链表）
		return head ;
	}
	//在第index+1个处插入node
	public JNode insert(JNode node,int index){
                //先考虑越界的问题和链表为空的问题 
		if(index>count||index<0)
			{
				System.out.println("Error!!!");
				return null;
			}
		if(count==0)			
			{
				head=node;
				count++;
				return head;
			}
		else {
			
			JNode flag = head ;
			for(int i=0;i<index-1;i++)
			{
				flag=flag.Next;
			}
			node.Next=flag.Next;
			flag.Next=node;
			count++;
			return head;
		}
	}
	//获取第index个
	public JNode get(int index){
       //先考虑越界的问题和链表为空的问题 	
	if(index>count||index<0)
		{
			System.out.println("Error!!!");
			return null;
		}
		JNode flag = head ;
		for(int i=0;i<index;i++)
		{
			flag=flag.Next;
		}
		return head ;
	}
	
	//对应值查找
	 public int search(JNode node){
			JNode flag = head ;
			for(int i=0;i<count;i++)
			{	
				if(flag.value==node.value)
				return i;
				flag=flag.Next;				
			}
			return -1;//用-1表示没有找到
	}
	 //展示
	 public void display(){
			JNode flag = head ;
			for(int i=0;i<count;i++)
			{					
				System.out.println("链表第"+i+"个是："+flag.value);
				flag=flag.Next;				
			}
	}

 

 

         接下来是测试：

 

public class test {


	public static void main(String args[]){
		linearray nncc = new linearray();
		//测试添加
		for(int i=0;i<100;i++)
		{	
			JNode flag = new JNode();
			flag.value=i;
			nncc.add(flag);			
		}
		//测试插入
		JNode flag = new JNode();
		flag.value=77;
		nncc.insert(flag,7);
		
		//测试删除
		nncc.delete(2);//删除第2个
		//测试获取第x个
		int x=33;
		JNode flag0=nncc.get(x);
		
		JNode flag1 = new JNode();
		flag1.value=99;
		//测试搜索
		int a =nncc.search(flag1);
		nncc.display();
		System.out.println("获得链表中第"+x+"个的结果是:"+flag0.value);
		System.out.println("有关于"+flag1.value+"搜索到的结果是链表中第"+a+"个");
	}
	
	
}

 

 

4、最后来讨论二叉树

 

      二叉树就像链表一直分叉，节点类如果只有一个指向下一个节点的指针，那就是链表，两个，就是二叉树，三个四个&…………

      和链表一样，先建立节点类和树类：

//节点类
public class Treeclass {
	
	public int Value;//存值（数据结构终究还是用来存放值的）
	public Treeclass lefttree;//左分叉
	public Treeclass righttree;//右分叉
	//基础构造函数
	Treeclass(){
		Value=0;
		lefttree=null;
		righttree=null;
	}
}

 

//树类
public class Tree {
	private Treeclass root;//树的根节点	
}

  然后再建立树的具体方法。和链表很像，这里简化一下，只写最基础的两个方法：

 

 

 

 

//直接加的手段
	public void add(int value){
		root = insert(root,value);
	}
	//实际加法
	private Treeclass insert(Treeclass node, int data) {  
	//如果为空
	if (node == null) {  
		node = new Treeclass();  
		node.Value= data;  
		
		} else {  
			if (data <= node.Value) {  //判断大小，小的去左边
				node.lefttree = insert(node.lefttree, data);  //递归
			} else {  
				node.righttree = insert(node.righttree, data);  
			}  
	}  
	return (node);  
	} 
	
	//中序遍历调用
	public void middle(){
		middleshow(root.lefttree);
		System.out.println(root.Value +" ");
		middleshow(root.righttree);		
	}
        //中序遍历
	public void middleshow(Treeclass node){
		if(node==null)
			return;
		middleshow(node.lefttree);
		System.out.println(node.Value +" ");
		middleshow(node.righttree);		
	}
}

 

 

       这里只写了加的方法和遍历的方法。删除查找类似上文不再多说，但是遍历是个很有意思的事，只要把输出语句System.out.println的位置换到middleshow（node.lefttree)上边，或者middleshow(node.righttree)下边，中序遍历就会变成前序或者后续，输出结果也大不一样。

 

 

      匆匆写下这篇博客，光阴易逝，与诸君共勉。希望能为大家提供一些微薄之力。文笔仓促，有误之处还请指正，见谅。