Java

数据结构存储——数组，链表，队列，树


     数组，链表，队列和树都是用于存储数据的数据结构
  1.功能的相通性
      在使用之前，都需要先声明，内存给分配指定的大小，然后把要存储的数据加到数组、链表、队列或者树（通过构建树来实现）中 ，系统提供的系统数组类里面有相应的方法，如添加、删除、查找、求长度等，但我们可以自己定义相应的方法来熟悉这个执行的过程，比如
数组的添加和删除部分代码如下：
     public void add(Object o) {
//定义一个新的数组，长度为原来的数组长度加1
Object[] array=new Object[ary.length+1];
//把原来的数组拷贝一份到原来的数组中
for(int i=0;i<ary.length;i++){
array[i]=ary[i];
}
//把新的数据放到数组中
array[ary.length]=o;
//把新数组的名字改为旧数组的名字
array=ary;
}
/**
* 删除数组中元素
*/

public void delete() {
//删除数组最后一个元素
Object array[]=new Object[0];
//把原来的数组的前面部分拷贝一份到新数组中
for(int i=0;i<=ary.length-1;i++){
array[i]=ary[i];
}
//把新的数组名改为原来的数组名
array=ary;

}



  往数组中添加元素的思想是:定义一个新的数组array，其长度比原来的数组ary长度大1，即array.length=ary.length+1,然后把用一个循环把ary的n个数依次赋值给新的数组的前n个数，新数组的最后一个元素另外在一条语句中赋值，把要加入的元素赋值给最后一个元素；同样删除数组中数的话，也要先建立新数组，然后赋值；[color=red][/color]，不过，要注意的是：数组中不管是添加数据还是删除都只能在末尾进行，而对于链表、队列、树等则可以在任何地方进行。


      在链表或队列中，添加或删除的思路和数组差不多，但由于他们可以在任何位置加入或删除，所以要用到其前后的元素对它进行标记，即指针（前驱和后继），例如构建链表需考虑队列中是否只有一个元素：
        public void add(Object o){//o是要添加的对象
//要添加节点的话，的首先创建节点对象
LinkNode n=new LinkNode();
//并把要要添加的数据放在节点上
n.data=o;
//如果根节点为空，则添加进去的结点即为头结点
if(root==null){
root=n;
last=n;

}else{//否则加到链表的后面
last.next=n;
last=n;
}
   length++;
}
           若要在链表或队列中间某个位置加入一个元素的话，将要加入的元素设为中间变量，然后将原来那个点的父结点改为中间变量的父节点，而原来的结点改为中间变量的下一个结点。删除的思想也是改变指针所对应的结点。如下：
           //删除链表中元素并返回被删除的数
public Object remove(int index){
//判断链表是否超界
if(index<0||index>=length){
throw new java.lang.ArrayIndexOutOfBoundsException("超出范围");
}
//如果删除的点为父节点，后面所有元素序前移
if(index==0){
length--;
Object data=root.data;
root=root.next;
return data;
}

//如果删除的是中间某个节点
LinkNode temp=root;
//先令根节点即为父节点
LinkNode prev=root;
for(int i=0;i<index;i++){
prev=temp;
temp=temp.next;
}
prev.next=temp.next;
System.out.println(temp);
if(index==(length-1)){
last=prev;
System.out.println("last="+last.data);
}

length--;
return temp.data;
     

     对于链表和队列在加入元素的时候需要考虑是否超界

    

    对于树来说，父节点和子节点之间往往存在某种对应关系，以最优二叉树为代表，父节点是两个子节点的和，可以利用父节点和子节点间的位置来输出子节点的哈弗曼编码，其中，在输出结点的哈弗曼编码时：要用到递归，还要判断结点是否为空。
    输出哈弗曼编码的部分参考代码如下：
        //取每一个也子节点的哈弗曼编码
public void getBM(TreeNode root,String curcode){//s为编码

if(root!=null){
System.out.println(root.data+"的编码是："+curcode);
getBM(root.left,curcode+"0");
getBM(root.right,curcode+"1");
}


     当然，这些结点都属于结点类，得首先定义一个结点类，改结点类里面包括了根节点、下一个结点、左结点、右结点、编码等属性。

评论

1 楼 ayaome 2014-03-20  

可以总结下他们各自的优点、缺点，各自适合在什么样的场合使用