数据结构--线性表复习

时间:2021-03-15 10:34:14

  感觉做程序如果要走的足够远的话,数据结构的底子还得扎实,然大学毕业后好多年,忘了不少,故从今天起开始尽可能抽闲暇时间进行复习总结,博客里面难免有错误和不对的地方,希望能指出,当然我也会抽时间来回顾下,查漏补缺,写博客是个好习惯希望自己能坚持下去。
  
  数据的四种逻辑结构:
  
  1,集合:数据元素之间只有“同属于一个集合”关系;
  
  2,线性结构:数据元素直接存在一个对应一个的关系;
  
  3,树形结构:数据元素之间存在一个队多个的关系;
  
  4,图形结构和网状结构:数据元素之间存在多个对多个之间的关系。
  
  物理存储结构:
  
  1,顺序存储结构;
  
  2,链式存储结构。
  
  常用数据结构分类:
  
  1,线性结构-->主要是线性表;
  
  2,非线性结构-->主要是图和树。
  
  线性表定义和特征:
  
  定义:
  
  1,线性表长度为0为空表,否则数据元素长度为线性表长度。
  
  特征:
  
  1,线性表存在第一个 和 最后一个数据元素;
  
  2,除了第一个和最后一个都存在前驱元素和后驱元素。
  
  线性表之顺序存储结构:
  
  特征:在物理和逻辑上一致的存储结构。
  
  通常利用数组来标示线性表的结构。
  
  顺序线性表表底层采用数组来进行存储数据元素。
  
  实际代码演示之插入一个新元素:

  

 1 import java.util.Arrays;
 2 
 3 
 4 public class MyList<T> {
 5     //定义数组的长度
 6     private int DEFAULT_SIZE = 18;
 7     //保存数组的长度。
 8     private int capacity;
 9     //定义一个数组用于保存顺序线性表的元素
10     private Object[] elementData;
11     //保存顺序表中元素的当前个数
12     private int size = 0;
13     
14     public MyList() {
15         capacity = DEFAULT_SIZE;
16         //初始化数组默认长度
17         elementData = new Object[capacity];
18     }
19     
20   //在线性顺序表的开始处添加一个元素。
21     public void add(T element)
22     {
23         insert(element , size);
24     }
25     /**
26      * 
27     * @Title: insert 
28     * @Description: TODO(向数组指定位置index插入某元素element) 
29     * @param @param element 插入的元素
30     * @param @param index    插入元素的位置
31     * @return void    返回类型 
32     * @throws
33      */
34     private void insert(T element , int index) {
35         if (index < 0 || index > size)
36         {
37             throw new IndexOutOfBoundsException("线性表索引越界");
38         }
39         ensureCapacity(size + 1);
40         //将index处以后所有元素向后移动一格。
41         //从旧的elementData中复制数据,从index位置开始,复制给目标elementData数组从index+1到最后的元素,长度为size-index
42         //详情看http://blog.csdn.net/kesalin/article/details/566354
43         System.arraycopy(elementData , index , elementData
44              , index + 1 , size - index);
45         elementData[index] = element;
46         size++;
47     }
48     /**
49       *原来的数组+1
50      */
51     private void ensureCapacity(int minCapacity) {
52       //如果数组的原有长度小于目前所需的长度
53         if (minCapacity > capacity)
54         {
55             //不断地将capacity * 2,直到capacity大于minCapacity为止
56             while (capacity < minCapacity)
57             {
58                 capacity <<= 1;
59             }
60             //复制数组元素,返回新的数组对象
61             //详情看http://www.iteedu.com/plang/java/javadiary/24.php
62             elementData = Arrays.copyOf(elementData , capacity);
63         }        
64     }
65 
66     /** 
67      * @Name toString
68      * @Description TODO(这里用一句话描述这个方法的作用) 
69      * @return
70      * @see java.lang.Object#toString()
71      * @Date 2016-3-19 下午9:41:26
72     **/
73     @Override
74     public String toString() {
75         StringBuilder builder = new StringBuilder();
76         builder.append("MyList [elementData=")
77             .append(Arrays.toString(elementData))
78             .append("]");
79         return builder.toString();
80     }
81     
82 }

  测试类:

  

public class Test {
    
    public static void main(String[] args) {
        MyList<String> list = new MyList<String>();
        list.add("佐助");
        list.add("鸣人");
        list.add("卡卡西");
        list.add("小樱");
        list.add("日向");
        list.add("我爱罗");
        list.add("天天");
        System.out.println(list.toString());
        
    }
    
}

测试结果:

MyList [elementData=[佐助, 鸣人, 卡卡西, 小樱, 日向, 我爱罗, 天天, null, null, null, null, null, null, null, null, null, null, null]]
MyList [elementData=[佐助, 鸣人, 卡卡西, 小樱, 日向, 我爱罗, 天天, 佐井, null, null, null, null, null, null, null, null, null, null]]

默认长度18,向尾部插入新元素“佐井”

   修改insert方法为public

   将新元素插入中间:

1 list.insert("插入中间的元素", 3);
2  System.out.println(list.toString());

测试结果:

MyList [elementData=[佐助, 鸣人, 卡卡西, 插入中间的元素, 小樱, 日向, 我爱罗, 天天, 佐井, null, null, null, null, null, null, null, null, null]]

新的元素放入position为3的位置。

 

删除指定位置的数据:

 1     //删除顺序线性表中指定索引处的元素
 2     //删除的是index的元素
 3     
 4     public T delete(int index)
 5     {
 6         if (index < 0 || index > size - 1)
 7         {
 8             throw new IndexOutOfBoundsException("线性表索引越界");
 9         }
10         T oldValue = (T)elementData[index];
11         //数组长度-1
12         int numMoved = size - index - 1;
13         if (numMoved > 0)
14         {
15             /**
16              * 复制elementData中index+1位置开始到最后的数组,给从index到最后的元素,长度为numMoved
17              */
18             System.arraycopy(elementData , index+1 19 , elementData, index , numMoved); 20         }
21         //清空最后一个元素,因为最后的元素是删除后(复制数据后残留的数据)
22         elementData[--size] = null; 23         return oldValue;
24     }

测试:

public class Test {
    
    public static void main(String[] args) {
        MyList<String> list = new MyList<String>();
        list.add("佐助");
        list.add("鸣人");
        list.add("卡卡西");
        list.add("小樱");
        list.add("日向");
        list.add("我爱罗");
        list.add("天天");
        System.out.println(list.toString());
        list.add("佐井");
        System.out.println(list.toString());
        list.insert("插入中间的元素", 3);
        System.out.println(list.toString());
        list.delete(3);//删除插入插入中间的数据
        System.out.println(list.toString());
    }
    
}

返回结果:

MyList [elementData=[佐助, 鸣人, 卡卡西, 小樱, 日向, 我爱罗, 天天, null, null, null, null, null, null, null, null, null, null, null]]
MyList [elementData=[佐助, 鸣人, 卡卡西, 小樱, 日向, 我爱罗, 天天, 佐井, null, null, null, null, null, null, null, null, null, null]]
MyList [elementData=[佐助, 鸣人, 卡卡西, 插入中间的元素, 小樱, 日向, 我爱罗, 天天, 佐井, null, null, null, null, null, null, null, null, null]]
MyList [elementData=[佐助, 鸣人, 卡卡西, 小樱, 日向, 我爱罗, 天天, 佐井, null, null, null, null, null, null, null, null, null, null]]

可见删除的是position位置为3的数据


2016年4月24日21:50:50更新:

 

 循环链表

首尾相连,尾节点的next指向链表头部的head节点,这就是循环链表。

图是从其他地方抠的,侵权删:

数据结构--线性表复习

双向链表:

既可以向前,又可以向后访问的链表结构。

数据结构--线性表复习

双向链表删除:

数据结构--线性表复习

线性表在java中的表现主要是List,LinkedList就是双向的链表结构。