数据结构小结——数组、链表、树

一、前言——数据结构

        数据结构的定义是指相互之间存在一种或多种特定关系的数据元素的集合。简单的理解就是就是装数据的容器，将不同数据以不同方式组合。

根据存储方式的不同，有连续、不连续之分，而连续的又有顺序（如数组）、链式（如链表）之分。

这里主要介绍数组、链表、树。

二、数组实现队列

 

     //创建一个数组对象，数组长度为0
	Object array[]=new Object[0];
	//创建返回元素下标的值
	int x=0;
	/**
	 * 添加一个值为s的元素
	 * @param s  添加的元素的值
	 */
	public void add(E e){
		//再次创建一个数组,数组的长度为原数组+1
		Object array1[]=new Object[array.length+1];
		//将数组array中的元素复制到array1中
		for(int i=0;i<array.length;i++){
			array1[i]=array[i];
		}
		//设置最后一个元素为新添加的元素
		array1[array.length]=e;
		//将原数组变量指向新数组
		array=array1;
	}
	
	/**
	 * 取得指定下标位置的元素值
	 * @param index 取得元素的下标
	 * @return 返回所取得的元素
	 */
	public E get(int index){
		Object s=array[index];
		return (E)s;
	}
	/**
	 * 取得数组的长度（容器的空间）
	 * @return 返回数组长度的值
	 */
	public int size(){
		return array.length;
	}
	
	/**
	 * 删除指定下标位置的元素
	 * @param index 要删除的元素的下标位置
	 */
	public void delete(int index){
		//再次创建一个数组,数组的长度为原数组+1
		Object array2[]=new Object[array.length-1];
		//将数组array中的下标在index之前的元素复制到array2中
		for(int i=0;i<index;i++){
			array2[i]=array[i];
		}
		//将数组array中的下标在index之后的元素复制到array2中
		for(int i=index+1;i<array.length;i++){
			array2[i-1]=array[i];
		}
		//将原数组变量指向新数组
		array=array2;
	}
	/**
	 * 查询是否存在指定元素值的元素
	 * @param s要查询的元素值
	 * @return 返回真假
	 */
	public boolean search(E e){
		int temp=0;
		for(int i=0;i<array.length;i++){
			if(e.equals(this.get(i))){
				temp=1;
				x=i;
			}
		}
		if(temp==0){
			return false;
		}
		else{
			return true;
		}
		
		
	}
	/**
	 * 得到指定元素值的下标位置
	 * @param s 指定的元素值
	 * @return 返回指定元素值的下标位置
	 */
	public int getIndex(E e){
		return x;
	}
	/**
	 * 制定规则：如果有相同元素，只删除后一个。
	 * 删除方法的重载，删除指定元素值的元素
	 * @param s 要删除的元素的元素值
	 */
	public void delete(E e){
		if(this.search(e)){
			//再次创建一个数组,数组的长度为原数组-1
			Object array3[]=new Object[array.length-1];
			//将数组array中的下标在ix之前的元素复制到array3中
			for(int i=0;i<x;i++){
				array3[i]=array[i];
			}
			//将数组array中的下标在x之后的元素复制到array3中
			for(int i=x+1;i<array.length;i++){
				array3[i-1]=array[i];
			}
			//将原数组变量指向新数组
			array=array3;
		}
	}
	/**
	 * 在指定位置插入指定字符串
	 * @param s 要插入的字符串
	 * @param index 要插入字符串的位置
	 */
	public void insert(E e,int index){
		//再次创建一个数组,数组的长度为原数组+1
		Object array4[]=new Object[array.length+1];
		//将数组array中的下标在index之前的元素复制到array4中
		for(int i=0;i<index;i++){
			array4[i]=array[i];
		}
		//将数组array中的下标在index之后的元素复制到array4中
		for(int i=index+1;i<array.length+1;i++){
			array4[i]=array[i-1];
		}
		//设置插入的元素
		array4[index]=e;
		//将原数组变量指向新数组
		array=array4;
	}
	/**
	 * 在指定位置修改为指定字符串
	 * @param s 要修改为的字符串
	 * @param index 要修改字符串的位置
	 */
	
	public void modify(E e,int index){
		//再次创建一个数组,数组的长度为原数组+1
		Object array5[]=new Object[array.length];
		//将数组array中的下标在index之前的元素复制到array4中
		for(int i=0;i<index;i++){
		array5[i]=array[i];
		}
		//将数组array中的下标在index之后的元素复制到array4中
		for(int i=index+1;i<array.length;i++){
		array5[i]=array[i];
		}
		//设置插入的元素
		array5[index]=e;
		//将原数组变量指向新数组
		array=array5;
	}

 

 三、链表与链表实现队列

 

 

 

 

/**
 * 定义一个链表类
 * @author zsc
 *
 */
class Link{
	/**
	 * 把节点类定义为内部类
	 */
	  class Node{
		//保存节点内容
		private String data;
		//保存下一个节点
		private Node next;
		//构造方法
		public Node(String data){
			this.data=data;
		}
		//递归实现增加节点的操作
		public void add(Node newNode){
			if(this.next==null){
				this.next=newNode;
			}else{
				this.next.add(newNode);
			}
		}
		//递归实现打印输出的操作
		public void print(){
			System.out.print(this.data+"\t");
			if(this.next!=null){
				this.next.print();
			}
		}
		//递归实现查询的操作
		public boolean search(String data){
			if(data.equals(this.data)){
				return true;
			}else{
				if(this.next!=null){
					return this.next.search(data);
				}
				else{
					return false;
				}
			}
		}
		//递归实现删除操作
		public void delete(Node previous,String data){
			if(data.equals(this.data)){
				previous.next=this.next;
			}else{
				if(this.next!=null){
					this.next.delete(this,data);
				}
			}
		}
	}
	//根节点
	private Node root;
	//增加节点的方法
	public void addNode(String data){
		//实例化新节点的对象
		Node newNode =new Node(data);
		if(this.root==null){
			this.root=newNode;
		}
		else{
			this.root.add(newNode);
		}
	}
	//打印输出接点的方法
	public void printNode(){
		if(this.root!=null){
			this.root.print();
		}
	}
	//判断节点是否存在
	public boolean contains(String data){
		return this.root.search(data);
	}
	//删除节点
	public void deleteNode(String data){
		if(this.contains(data)){
			if(this.root.equals(data)){
				this.root=this.root.next;
			}else{
				this.root.next.delete(root, data);
			}
		}
	}
}

 

四、数组与链表的区别

       数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

       链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

      简单的说：

      数组实现队列：容易实现查询、但是插入、删除会很慢
                              查询时间复杂度：o(1)
      链表实现队列：容易实现增加、插入、删除，但是查询会很慢
                              链表长度n：查询时间复杂度：o(n)

 五、树

/**
 * 树的节点类
 * @author zsc
 *
 */
public class JTreeNode {
	private int nValue;
	private JTreeNode leftNode;
	private JTreeNode rightNode;
	public JTreeNode(int nValue){
		this.nValue=nValue;
	}
	public void setValue(int nValue){
		this.nValue=nValue;
	}
	public int getValue(){
		return this.nValue;
	}
	public void setLChild(JTreeNode leftChild){
		this.leftNode=leftChild;
	}
	public JTreeNode getLChild(){
		return this.leftNode;
	}
	public void setRChild(JTreeNode rightChild){
		this.rightNode=rightChild;
	}
	public JTreeNode getRChild(){
		return this.rightNode;
	}
}
/**
 
 * 创建树的类
 
 * @author zsc
 
 *
 
 */
public class JTree {
	//根节点
	public JTreeNode root;
	/**
	 * 添加节点
	 * @param value：添加的节点内容
	 */
	public void add(int value){
		JTreeNode temp=new JTreeNode(value);
		//根节点为空时则为根
		if(root==null){
			root=temp;
		}
		else{
			add(root,temp);
		}
	}
	/**
	 * 添加节点
	 * @param head：节点的父节点
	 * @param node：添加的新节点
	 */
	public void add(JTreeNode head,JTreeNode node){
		//如果新节点的值小于父节点的值放左侧
		if(node.getValue()<=head.getValue()){
			//左子节点为空直接放置
			if(head.getLChild()==null){
				head.setLChild(node);
			}
			//左子节点不为空，递归，父节点——》父节点的左子节点
			else{
				add(head.getLChild(),node);
			}
		}
		//如果新节点的值大于父节点的值放右侧
		else{
			//右子节点为空直接放置
			if(head.getRChild()==null){
				head.setRChild(node);
			}
			//右子节点不为空，递归，父节点——》父节点的右子节点
			else{
				add(head.getRChild(),node);
			}
		}
	}
	//中序遍历
	public void middle(){
		middleEX(root.getLChild());
		System.out.print(root.getValue()+" ");
		middleEX(root.getRChild());
	}
	public void middleEX(JTreeNode node){
		if(node==null){
			return;
		}
		middleEX(node.getLChild());
		System.out.print(node.getValue()+" ");
		middleEX(node.getRChild());
	}
	//左序遍历
	public void leftPrint(){
		System.out.print(root.getValue()+" ");
		leftEX(root.getLChild());
		leftEX(root.getRChild());
	}
	public void leftEX(JTreeNode node){
		if(node==null){
			return;
		}
		System.out.print(node.getValue()+" ");
		leftEX(node.getLChild());
		leftEX(node.getRChild());
	}
	//右序遍历
	public void rightPrint(){
		rightEx(root.getLChild());
		rightEx(root.getRChild());
		System.out.print(root.getValue()+" ");
	}
	public void rightEx(JTreeNode node){
		if(node==null){
			return;
		}
		rightEx(node.getLChild());
		rightEx(node.getRChild());
		System.out.print(node.getValue()+" ");
	}
}