感觉做程序如果要走的足够远的话,数据结构的底子还得扎实,然大学毕业后好多年,忘了不少,故从今天起开始尽可能抽闲暇时间进行复习总结,博客里面难免有错误和不对的地方,希望能指出,当然我也会抽时间来回顾下,查漏补缺,写博客是个好习惯希望自己能坚持下去。
数据的四种逻辑结构:
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就是双向的链表结构。