一、 数据结构简介
1 什么是数据结构
简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了 数据结构对于某些操作是高效的，而对于其他操作则是低效的。所以我们需要理解各种数据 结构，才能在处理实际问题时选取最合适的数据结构。 数据结构=逻辑结构+物理结构（顺序、链式、索引、散列） 逻辑结构：数据元素间抽象化的相互关系 物理结构：（存储结构），在计算机存储器中的存储形式
2 数据结构逻辑分类
数据结构从逻辑上划分为三种基本类型：
2.1线性结构
数据结构中的元素存在一对一的相互关系；
常见的线性结构： 线性表，栈，队列，串(一维数组)等。
2.2树形结构
数据结构中的元素存在一对多的相互关系；
常见树形结构： 二叉树，红黑树，B 树，哈夫曼树等。
2.3图形结构
数据结构中的元素存在多对多的相互关系；
常见图形结构： 有向图，无向图，简单图等。
二、 线性结构
1 栈结构
1.1栈的定义
栈是一种只能从一端存取数据且遵循 "后进先出(LIFO)" 原则的线性存储结构。
1.2实现栈容器
1.2.1 创建栈容器
/*** * 自定义栈容器 */ public class MyStack<E> { private Object[] arr;//存放元素的物理结构 private int stackLength = 4;//数组的默认长度 private int size; //记录栈容器的元素个数 private int index = -1;//操作数组下标位置的指针 /** * 判断栈容器是否为空 * @return */ public boolean empty(){ return false; } /** * 获取栈顶元素 * @return */ public E pop(){ return null; } /** * 向栈容器中添加元素 * @param item * @return */ public E push(E item){ return null; } public static void main(String[] args) { } }
1.2.2 实现添加元素
/** * 向栈容器中添加元素 * @param item * @return */ public E push(E item){ //初始化数组 this.capacity(); //向数组中添加元素 this.arr[++index]=item; //记录元素个数 this.size++; return item; } /** * 数组初始化或者以 1.5 倍容量对数组扩容 */ private void capacity(){ //数据初始化 if(this.arr == null){ this.arr = new Object[this.stackLength]; } //以 1.5 倍对数组扩容 if(this.size - (this.stackLength-1) >= 0) this.stackLength = this.stackLength + (this.stackLength >> 1); this.arr = Arrays.copyOf(this.arr,this.stackLength); } }
1.2.3 实现获取元素
/** * 获取栈顶元素 * @return */ public E pop(){ //如果栈容器中没有元素则抛出异常 if(this.index == -1){ throw new EmptyStackException(); } //记录元素个数 this.size--; //返回栈顶元素 return (E) this.arr[index--]; }
1.2.4 判断栈容器是否为空
/** * 判断栈容器是否为空 * @return */ public boolean empty(){ return this.size == 0 }
2 链表结构
2.1链表结构的定义
2.1.1 什么是链表
链表结构是由许多节点构成的，每个节点都包含两部分：
数据部分：保存该节点的实际数据。
地址部分：保存的是上一个或下一个节点的地址。
2.1.2 链表分类
单向链表
双向链表
双向循环链
2.1.3 链表的特点
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
访问时只能通过头或者尾指针进入链表，并通过每个结点的指针域向后或向前扫描 其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
链表的优缺点： 优点：数据元素的个数可以自由扩充 、插入、删除等操作不必移动数据，只需修 改链接指针，修改效率较高。 缺点：必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问，访问 节点效率较低。
2.2单向链表结构
2.2.1 单向链表定义
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问 要通过从头部开始顺序读取。
2.2.2 实现单向链表
2.2.2.1 创建链表接
/** * 基于链表结构存取元素的方法 API 定义 * @param <E> */ public interface MyList<E> { void add(E element); E get(int index); int size(); E remove(int index); }
2.2.2.2 创建单向链表类
/** * 基于单向链表实现元素存取的容器 * @param <E> */ public class MySinglyLinkedList<E> implements MyList<E> { /** * 向链表中添加元素 * @param element */ @Override public void add(E element) { } /** * 根据元素的位置获取元素 * @param index * @return */ @Override public E get(int index) { return null; } /** * 获取元素个数 * @return */ @Override public int size() { return 0; } /** * 根据元素的位置删除元素 * @param index * @return */ @Override public E remove(int index) { return null } public static void main(String[] args) { } }
2.2.2.3 创建节点类
/** * 定义单向链表中的节点对象 */ class Node<E>{ private E item;//存储元素 private Node next;//存储下一个节点对象的地址 Node(E item,Node next){ this.item = item; this.next = next; } }
2.2.2.4 实现添加元素方法
private Node head;//存放链表中的头节点。 private int size;//记录元素个数。 /** * 向链表中添加元素 * @param element */ @Override public void add(E element) { //创建节点 Node<E> node = new Node<>(element,null); //找到尾节点 Node tail = getTail(); //节点的挂接 if(tail == null) this.head = node; else tail.next = node; //记录元素个数 this.size++; } /** * 找尾节点 */ private Node getTail(){ //头节点是否存在 if(this.head == null){ return null; } //查找尾节点 Node node = this.head; while(true){ if(node.next == null)break; node = node.next;//移动指针，指向下一个节点 } return node; }
2.2.2.5 实现获取元素方法
/** * 根据元素的位置获取元素 * @param index * @return */ @Override public E get(int index) { //校验 Index 的合法性 this.checkIndex(index); //根据位置获取指定节点 Node<E> node = this.getNode(index); //将该节点中的元素返回 return node.item; } /** * 对 Index 进行校验 */ private void checkIndex(int index){ if(!(index >= 0 && index < this.size)){ throw new IndexOutOfBoundsException("Index: "+index+" Size: "+this.size); } } /** * 根据位置获取节点 */ private Node getNode(int index){ Node<E> node = this.head; for(int i=0;i<index;i++){ node = node.next; } return node; }
2.2.2.6 实现删除元素方法
/** * 根据元素的位置删除元素 * @param index * @return */ @Override public E remove(int index) { //校验 Index 的合法性 this.checkIndex(index); //根据位置找到该节点对象 Node<E> node = this.getNode(index); //获取该节点对象中的元素 E item = node.item; //将该节点对象从单向链表中移除 //判断当前删除的节点是否为头结点 if(this.head == node){ this.head = node.next; }else{ Node<E> temp = this.head; for(int i=0;i< index - 1;i++){ temp = temp.next; } temp.next = node.next; } node.next = null; //记录元素个数 this.size--; //将该元素返回 return item; }
2.2.2.7 实现获取元素个数
/** * 获取元素个数 * @return */ @Override public int size() { return this.size; }
2.3双向链表结构
2.3.1 双向链表定义
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直 接前驱和直接后继。
2.3.2 实现双向链表
2.3.2.1 创建双向链表类
/** * 基于双向链表实现元素存取的容器 * @param <E> */ public class MyDoublyLinkedList<E> implements MyList<E> { /** * 向双向链表中添加元素的方法 * @param element */ @Override public void add(E element) { } /** * 根据指定位置获取元素 * @param index * @return */ @Override public E get(int index) { return null; } /** * 返回元素的个数 * @return */ @Override public int size() { return 0; } /** * 根据指定位置删除元素 * @param index * @return */ @Override public E remove(int index) { return null; } public static void main(String[] args) { } }
2.3.2.2 创建节点类
/** * 定义双向链表的节点对 */ class Node<E>{ E item;//记录元素 Node<E> prev;//记录前一个节点对象 Node<E> next;//记录下一个节点对象 Node(Node<E> prev,E item,Node<E> next){ this.prev = prev; this.item = item; this.next = next; } }
2.3.2.3 实现添加元素方法
private Node head; //记录头节点 private Node tail; //记录尾节点 private int size; //记录元素个数 /** * 向双向链表中添加元素的方法 * @param element */ @Override public void add(E element) { this.linkLast(element); } /** * 将节点对象添加到双向链表的尾部 */ private void linkLast(E element){ //获取尾节点 Node t = this.tail; //创建节点对象 Node<E> node = new Node<>(t,element,null); //将新节点定义为尾节点 this.tail = node; if(t == null){ this.head = node; }else{ t.next = node; } this.size++; }
2.3.2.4 实现获取元素方法
/** * 根据指定位置获取元素 * @param index * @return */ @Override public E get(int index) { //对 Index 做合法性校验 this.checkIndex(index); //根据位置查找节点对象 Node<E> node = this.getNode(index); return node.item; } /** * 校验 Index 的合法性 */ private void checkIndex(int index){ if(!(index >= 0 && index < this.size)){ throw new IndexOutOfBoundsException("Index: "+index+" Size:"+size); } } /** * 根据位置获取指定节点对象 */ private Node getNode(int index){ //判断当前位置距离头或者尾哪个节点更近 if(index < (this.size >> 1)){ Node node = this.head; for(int i=0;i<index;i++){ node = node.next; } return node; }else{ Node node = this.tail; for(int i=this.size-1;i>index;i--){ node = node.prev; } return node; } }
2.3.2.5 实现删除元素方法
/** * 根据指定位置删除元素 * @param index * @return */ @Override public E remove(int index) { //对 Index 进行合法性校验 this.checkIndex(index); //根据指定位置获取节点对象 Node<E> node = this.getNode(index); //获取节点对象中的元素 E item = node.item; //判断当前节点是否为头节点 if(node.prev ==null){ this.head = node.next; }else{ //完成当前节点的直接前驱节点与当前节点的直接后继节点的挂接 node.prev.next = node.next; } //判断当前节点是否为尾节点 if(node.next == null){ this.tail = node.prev; }else{ //完成当前节点的直接后继节点与当前节点的直接前驱节点的挂接 node.next.prev = node.prev; } //当前节点断掉与它直接前驱节点的连接 node.prev = null; //当前节点断掉与它直接后继节点的连接 node.next = null; node.item = null; //记录元素个数 this.size--; return item; }
2.3.2.6 获取元素的个数
/** * 返回元素的个数 * @return */ @Override public int size() { return this.size; }
2.3.2.7 实现在双向链表的头添加元素
/** * 在双向链表的头添加元素 * */ public void addFirst(E element){ this.linkFirst(element); } /** * 在链表的头添加元素 * */ private void linkFirst(E element){ //获取头节点对象 Node head = this.head; Node node = new Node(null,element,head); //将新节点定义为头节点 this.head = node; //判断当前链表中是否有节点如果没有，那么该节点既是头节点也是尾节点 if(head == null){ this.tail = node; }else{ head.prev = node; } //记录元素个数 this.size++; }
2.3.2.8 实现在双向链表的尾添加元素
/** * 在链表的尾添加元素 * @param element */ public void addLast(E element){ this.linkLast(element); }
