数据结构总结

数据结构总结

最近学了数据结构，大致有以下几种：数组、队列、链表、树、二叉树、哈夫曼树

一、数组

1、格式：创建：类名或数据类型 [ ]  数组名 = new　类名或数据类型 [数组长度];

                  引用：数组名 [下标]           

2、特点：1）对应内存中一段连续的空间，储存一系列数据或对象，个数为数组长度

                  2）创建时必须指明数组长度，且数组长度不可动态定义

                  3）元素引用方便，直接数组名+下标引用，下标0—数组名-1

3、应用：适合储存数据个数一定的数据时使用

例：int [] a = new int [9];  a[3] = 1;

二、多维数组

1、格式：创建：类名或数据类型 [ ][ ][ ]…数组名 = new　类名或数据类型 [长度][长度][长度]…;   引用：数组名[下标][下标][下标]…

2、特点：与一维数组类似，定义时第一维可不写，在赋值时系统自动分配。

三、数组实现的队列

1、定义：一种长度可变的数据储存结构。

2、格式：以五子棋中储存棋子的队列为例

public class DiscList {
 Disc[] arrect = new Disc[0];
 //添加的方法
 public void add (Disc disc) {
  Disc[] arr = new Disc[arrect.length+1];
  for(int i = 0;i<arrect.length;i++){
   arr[i] = arrect[i];
  }
  arr[arrect.length] = disc;
  arrect = arr;
 }
 //按编号引用元素的方法
 public Disc get(int Index) {
  return arrect[Index];
 }
 //返回队列长度
 public int size() {
  return arrect.length;
 }
 //删除元素的方法
 public Object remove(int Index) {
  Disc[] arr = new Disc[arrect.length-1];
  for(int i = 0;i<Index;i++){
   arr[i] = arrect[i];
  }
  Disc t = arrect[Index];
  for(int i = Index;i<arr.length;i++){
   arr[i] = arrect[i+1];
  }
  arrect = arr;
  return t;
 }
 //插入元素的方法
 public void insert(int Index, Disc disc) {
  Disc[] arr = new Disc[arrect.length+1];
  for (int i = 0;i<Index;i++){
   arr[i] = arrect[i];
  }
  arr[Index] = disc;
  for (int i = Index+1;i<arr.length;i++){
   arr[i] = arrect[i-1];
  }
  arrect = arr;
 }
 //打印所有元素信息
 public void showList(){
  for(int i = 0;i<arrect.length;i++){
   System.out.print("arrect "+i+" ="+arrect[i]+"\t");
   if(i%4 == 0 && i!= 0)
    System.out.println("");
  }
  System.out.println("");
 }
}

分析：这里的队列类中含有一个数组，每次添加或删除元素时，创建一个新数组，长度与原数组不同，将未改动的元素原封不动赋值后，加入新元素后再用新数组代替原数组，从而实现队列长度的及时变动。

3、特点：1）本质还是数组

         2）每次添加或删除元素时都要进行大量赋值，因而不适合要频繁进行数据插入删除操作的数据

4、优化方法：1）根据需要将数组初始化长度改大些

             2）将数组每次变化的长度加大些，以减少无谓的赋值操作

例：修改后的棋子队列

public class DiscList {
 //控制数列初始长度的变量
 private int initlength = 100;
 //控制每次改变长度的变量
 private int change = 20;
 //累计元素个数的变量
 private int count = 0;
 Disc[] arrect = new Disc[initlength];
 //用户自行设置初始变量的方法
 public DiscList(int initlength,int change){
  this.initlength = initlength;
  this.change = change;
  this.arrect = new Disc[initlength];
 }
 //添加的方法
 public void add (Disc disc) {
  if(count<arrect.length){
   arrect[count++] = disc;
  }else{
   Disc[] arr = new Disc[arrect.length+change];
   for(int i = 0;i<arrect.length;i++){
    arr[i] = arrect[i];
   }
   arr[count++] = disc;
   arrect = arr;
  }
 }
 …………

 //返回队列长度
 public int size() {
  return count;
 }
 …………
 }
使用initlength与change两个变量，避免了硬编码，同时优化了队列的执行效率，使该队列有更广的应用。

四、链表

1、定义：一系列节点通过指针指向联系起来的一种数据储存结构。

2、格式：例

节点类

public class LinkNode {
 //数据
 private Object date;
 //储存下一个节点
 private LinkNode next;
 //编号（可没有）
 private int num;
 public int getNum() {
  return num;
 }
 public void setNum(int num) {
  this.num = num;
 }
 public Object getDate() {
  return date;
 }
 public void setDate(Object date) {
  this.date = date;
 }
 public LinkNode getNext() {
  return next;
 }
 public void setNext(LinkNode next) {
  this.next = next;
 }
}

链表类

public class MyLinkQueue {
 private LinkNode root;
 public LinkNode getRoot() {
  return root;
 }
 private LinkNode tail;
 private int count = 0;
 //添加数据节点的方法
 public void add(String s){
  if(null == root){
   root = new LinkNode();
   tail = root;
   tail.setDate(s);
   tail.setNum(++count);
  }else{
  LinkNode ln = new LinkNode ();
  ln.setDate(s);
  ln.setNum(++count);
  tail.setNext(ln);
  tail = tail.getNext();
  }
 }
 //找到指定节点的方法
 public LinkNode getNode(int Index){
  LinkNode tNode= root;
  while(tNode.getNext() != null){
   if(tNode.getNum() == Index){
    return tNode;
   }
   tNode = tNode.getNext();
  }
  System.out.println("未找到该节点");
  return null;
 }
 //遍历链表的方法
 public void showLink(LinkNode root){
  LinkNode ln = root;
  while(ln != null){
   System.out.println("+++"+(String)ln.getDate());
   ln = ln.getNext();
  }
 //插入节点方法
 public void insert(String s,int localtion){
  LinkNode ln = new LinkNode();
  LinkNode t = root;
  ln.setDate(s);
  int i = 0;
  while(i++<localtion){
   t = t.getNext();
  }
  ln.setNext(t.getNext());
  t.setNext(ln);
 }
}

分析：这里的链表各节点通过指针next指向互相联系起来成为一个链状整体结构，利用内存中离散的空间储存数据。

3、特点：1）与数组不同，各节点占用的内存一般不连续

         2）由于每个节点出原始数据外都要多一个指针域，所以占用总空间较原始数据要大些

         3）添加删除等操作只需改变指针指向，而不需要改动其他元素

五、树

1、定义：树是图论中的一个概念，其中每个节点都可以指向一个或多个其他节点，总体连成树状结构。其中没有父节点的节点叫根节点，没有子节点的叫叶子节点。

2、格式：以二叉树为例

节点类

public class Node {
  Object data;
  Node left;
  Node right;
}

树类

public class BinTree {
 //根节点
 private Node root;
 //添加某节点左节点的方法
 public void addleft(Node fa,Object dd){
  Node left = new Node();
  left.data = dd;
  fa.left = left;
 }
 //添加某节点右节点的方法
 public void addright(Node fa,Object dd){
  Node right = new Node();
  right.data = dd;
  fa.right = right;
 }
}

3、特点：1）数据节点间一般有较强的从属、相关关系

         2）数据储存更有层次感，便于查找分析等操作（如二分查找）

六、哈夫曼树

1、定义：这里介绍的是以二叉树为基础的哈夫曼树，原始数据存在叶子节点，每次选取权值（数值）最小的两个数据，其和构成上一层节点，其中一般规定较小的数据为左节点，较大的为右节点，新节点与其余的继续参与上述过程，直至得到最终的根节点，即形成一完整的哈夫曼树。从根节点开始，规定向左为0，向右为1，则每个叶节点可以得到一串01组成的编码，我们称为哈夫曼编码。

2、示例：

 

这是一手动建立的哈夫曼树

public class HuffmanTree {

 /**
  * 手工实现的哈夫曼编码
  *   */
 public static void main(String[] args) {
  int [] da = {1,2,3,4,5,6};
  
  Node n1 = new Node();
  n1.data = 1;
  
  Node n2 = new Node();
  n2.data = 2;
  
  Node n3 = new Node();
  n3.data = n1.data + n2.data ;
  n3.left = n1;
  n3.right = n2;
  
  Node n4 = new Node();
  n4.data = 3;
  
  Node n5 = new Node();
  n5.data = n3.data +n4.data ;
  n5.left = n3;
  n5.right = n4;
  
  Node n6 = new Node();
  n6.data = 4;
  
  Node n7 = new Node();
  n7.data = 5;
  
  Node n8 = new Node();
  n8.data = n6.data+n7.data;
  n8.left = n6;
  n8.right = n7;
  
  Node n9 = new Node();
  n9.data = 6;
  
  Node n10 = new Node();
  n10.data = n5.data + n9.data;
  n10.left = n5;
  n10.right = n9;
  
  Node root = new Node();
  root.data = n8.data + n10.data;
  root.left = n8;
  root.right = n10;
  
  HuffmanTree ht = new HuffmanTree();
  ht.print(root,"");
 }

 private void print(Node node,String code) {
  if(node.left == null && node.right == null){
   System.out.println("节点"+node.data+"的哈夫曼编码是"+code);
  }
  if(node.left != null){
   print(node.left,code+"0");
  }
  if(node.right != null){
   print(node.right,code+"1");
  }
 }

}

运行后得到各节点的哈夫曼编码：

节点1的哈夫曼编码是1000
节点2的哈夫曼编码是1001
节点3的哈夫曼编码是101

节点4的哈夫曼编码是00
节点5的哈夫曼编码是01
节点6的哈夫曼编码是11

3、应用：哈夫曼树可以将原本占用一字节的字符通过权值转换为占用位数更少的哈夫曼编码，从而实现数据压缩。