一、数据结构简介

1.什么是数据结构

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。

数据结构=逻辑结构+物理结构（顺序、链式、索引、散列）。

逻辑结构：数据元素间抽象化的相互关系。

物理结构：（存储结构），在计算机存储器中的存储形式。

2.数据结构逻辑分类

数据结构从逻辑上划分为三种基本类型：

线性结构：数据结构中的元素存在一对一的相互关系；常见的线性结构：线性表，栈，队列，串(一维数组)等。

树形结构：数据结构中的元素存在一对多的相互关系；常见树形结构：二叉树，红黑树，B树，哈夫曼树等。

图形结构：数据结构中的元素存在多对多的相互关系；常见图形结构：有向图，无向图，简单图等。

二、线性结构

1.栈结构

栈的定义

栈是一种只能从一端存取数据且遵循"后进先出(LIFO)"原则的线性存储结构。

实现栈容器

package cn.pxy.test;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * 自定义栈容器
 * @author 胖咸鱼
 * @param <E>
 *
 */
public class MyStack<E> {
	
	private Object[] arr;//存放元素的物理结构，此时数组被定义，但未创建，使用需初始化
	private int stackLength=4;//数组的默认长度
	private int size;//记录栈容器的元素个数
	private int index=-1;//操作数组下标位置的指针，开始时，不指向元素。
	
	/**
	 * 判断栈是否为空
	 * @return
	 */
	public boolean empty() {
		return this.size==0;
	}
	/**
	 * 获取栈顶元素
	 * @return
	 */
	public E pop() {
		//如果栈容器里没有元素则抛出异常
		if(this.index==-1) {
			throw new EmptyStackException();
		}
		//记录元素个数，取出后栈里的元素-1
		this.size--;
		//返回栈顶元素,指针向下移动
		return (E)this.arr[index--];
	}
	/**
	 * 向容器中添加元素
	 * @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倍容量对数组扩容,相当于新建一个1.5倍容量的数组，把旧的数组复制进去
		if(this.size-(this.stackLength-1)>=0) {
			this.stackLength=this.stackLength+(this.stackLength>>1);
			this.arr=Arrays.copyOf(this.arr, this.stackLength);
		}
	}
	
	public static void main(String[] args) {
		MyStack<String> myStack=new MyStack<>();
		//添加元素，添加6个元素测试扩容
		myStack.push("a");
		myStack.push("b");
		myStack.push("c");
		myStack.push("d");
		myStack.push("e");
		myStack.push("f");
		System.out.println(myStack.size);
		System.out.println(myStack.pop());
		System.out.println(myStack.pop());
		System.out.println(myStack.empty());
		System.out.println(myStack.size);
	}
}

运行结果：

2.链表结构

链表结构的定义：链表结构是由许多节点构成的，每个节点都包含两部分：1.数据部分：保存该节点的实际数据。2.地址部分：保存的是上一个或下一个节点的地址。

链表分类：单向链表、双向链表、双向循环链表

链表的特点：1.结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。2.访问时只能通过头或者尾指针进入链表，并通过每个结点的指针域向后或向前扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

链表的优缺点：1.优点：数据元素的个数可以自由扩充、插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高。2.缺点：必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问，访问节点效率较低。

单向链表结构

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始顺序读取。

实现单向链表

创建列表接口：

package cn.pxy.test;
/**
 * 基于链表结构存储元素的方法API定义
 * @author 胖咸鱼
 *
 * @param <E>
 */
public interface MyList<E> {
	//添加元素的方法
	void add(E element);
	//获取元素的方法
	E get (int index);
	//获取元素个数的方法
	int size();
	//根据元素位置删除元素的方法
	E remove(int index);
}

创建单向列表类：

package cn.pxy.test;
/**
 * 基于单向列表实现元素存取的容器
 * @author 胖咸鱼
 *
 * @param <E>
 */
public class MySinglyLinkedList<E> implements MyList<E> {
	/**
	 * 定义单向列表中的节点对象
	 */
	class Node<E>{
		private E item;//存储元素
		private Node next;//存储下一个节点对象的地址
		Node(E item,Node next){
			this.item=item;
			this.next=next;
		}
	}
	
	private Node head;//存放链表中的头节点
	private int size;//记录元素个数
	/**
	 * 向列表中添加元素
	 */
	@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;//node指向头结点，通过移动node来找尾结点
		while(true) {
			if(node.next==null) {//如果找到尾结点，则退出循环
				break;
			}
			node=node.next;//移动指针指向下一个节点
		}
		return node;
	}

	/**
	 * 根据元素位置获取元素
	 */
	@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;
	}

	/**
	 * 获取元素个数
	 */
	@Override
	public int size() {
		return this.size;
	}

	/**
	 * 根据元素位置删除元素
	 */
	@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;
	}
	public static void main(String[] args) {
		MySinglyLinkedList<String> msll=new MySinglyLinkedList<>();
		msll.add("a");
		msll.add("b");
		msll.add("c");
		msll.add("d");
		System.out.println("删除前元素个数为："+msll.size);
		System.out.println(msll.remove(2));
		System.out.println("删除后元素个数为："+msll.size);
		for(int i=0;i<msll.size;i++) {
			System.out.println(msll.get(i));
		}
	}

}

双向链表结构

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接前驱和直接后继。

实现双向列表：

package cn.pxy.test;
/**
 * 基于双向链表实现元素存取的容器
 * @author 胖咸鱼
 *
 */
public class MyDoublyLinkedList<E> implements MyList<E> {

	/**
	 * 定义双向列表节点对象
	 */
	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;
		}
	}
	
	private Node head;//记录头结点
	private Node tail;//记录尾结点
	private int size;//记录元素个数
	
	/**
	 * 添加元素,默认在尾部添加
	 */
	@Override
	public void add(E element) {
		this.linkLast(element);
	}
	/**
	 * 将节点对象添加到双向链表的尾部
	 */
	private void linkLast(E element) {
		//获取尾结点
		Node t=this.tail;
		//创建新节点,由于添加到尾部，所以新节点的头结点是原先链表的尾结点（t）
		Node<E> node=new Node<>(t,element,null);
		//将新节点定义为尾结点，即添加节点后，新的节点变为链表尾结点
		this.tail=node;
		//如果链表没有元素，则新添加的节点即是尾结点又是头结点
		if(t==null) {
			this.head=node;
		}else {//如果链表不为空，则原先链表的尾结点（t）的后置要指向新的节点
			t.next=node;
		}
		this.size++;
	}

	/**
	 * Index合法性的校验
	 */
	private void checkIndex(int index) {
		if(!(index>=0 && index<this.size)) {
			throw new IndexOutOfBoundsException("Index:"+index+" Size:"+this.size);
		}
	}
	
	/**
	 * 根据指定位置获取元素
	 */
	@Override
	public E get(int index) {
		// 校验index
		this.checkIndex(index);
		//根据位置查找节点对象
		Node<E> node=this.getNode(index);
		//返回节点元素
		return node.item;
	}
	/**
	 * 根据位置查找节点对象
	 */
	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;
		}
	}

	/**
	 * 返回元素个数
	 */
	@Override
	public int size() {
		return this.size;
	}

	/**
	 * 根据指定位置删除元素
	 */
	@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;
	}
	
	/**
	 * 在双向链表的头部添加元素
	 * @param args
	 */
	public void addFirst(E element) {
		this.linkFirst(element);
	}
	/**
	 * 在链表的头部添加元素
	 * @param 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++;
		
	}
	
	/**
	 * 在链表的尾部添加元素
	 * @param args
	 */
	public void addLast(E element) {
		this.linkLast(element);
	}
	
	public static void main(String[] args) {
		MyDoublyLinkedList<String> myList=new MyDoublyLinkedList<>();
		myList.add("a");
		myList.addFirst("A");
		myList.addLast("B");
		myList.add("d");
		System.out.println("添加元素后的链表：");
		for(int i=0;i<myList.size();i++) {
			System.out.print(" "+myList.get(i));
		}
		System.out.println();
		System.out.println("链表的长度："+myList.size());
		System.out.println("删除的元素："+myList.remove(2));
		System.out.println("删除后的链表长度："+myList.size());
		System.out.println("删除后的链表：");
		for(int i=0;i<myList.size();i++) {
			System.out.print(" "+myList.get(i));
		}
	}
}

运行结果：

三、树形结构

1.树形结构简介

树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

2.树的相关术语

结点(Node)：使用树结构存储的每一个数据元素都被称为“结点”。

结点的度(DegreeofNode)：某个结点所拥有的子树的个数。

树的深度(DegreeofTree)：树中结点的最大层次数。

叶子结点(LeafNode)：度为0的结点，也叫终端结点。

分支结点(BranchNode)：度不为0的结点，也叫非终端结点或内部结点。

孩子(Child)：也可称之为子树或者子结点，表示当前结点下层的直接结点。

双亲(Parent)：也可称之为父结点，表示当前结点的直接上层结点。

根节点(RootNode)：没有双亲结点的结点。在一个树形结构中只有一个根节点。

祖先(Ancestor)：从当前结点上层的所有结点。

子孙(Descendant)：当前结点下层的所有结点。

兄弟(Brother)：同一双亲的孩子。

3.二叉树简介

二叉树（BinaryTree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

3.1二叉树分类：

满二叉树

满二叉树指除最后一层外，每一层上的所有节点都有两个子节点。

完全二叉树：

完全二叉树，除最后一层可能不满以外，其他各层都达到该层节点的最大数，最后一层如果不满，该层所有节点都全部靠左排。

3.2二叉树遍历：

二叉树遍历的方式：

1.前序遍历：根-左-右

2.中序遍历：左-根-右

3.后序遍历：左-右-根

4.层序遍历：从上至下逐层遍历

前序遍历：

中序遍历：

后续遍历：

层序遍历：

从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直到节点访问完毕。

3.3 二叉树排序

利用二叉树结构以及遍历方式可以实现基于二叉树的元素排序处理。

例如：12作为根节点，9比12小，放在12的左侧，5比12小，也放在左侧，但是12有左子节点9了，5再跟9比，放在9的左侧......

二叉树排序的实现：

package cn.pxy.test;
/**
 * 基于二叉树结构实现元素排序处理的排序器
 * @author 胖咸鱼
 *
 */
public class BinaryTreeSort<E extends Integer> {
	
	/**
	 * 定义节点类
	 */
	class Node<E extends Integer>{
		private E item;//存放元素
		private Node left;//存放左子树地址
		private Node rigtt;//存放右子树
		
		Node(E item){
			this.item=item;
		}
		
		/**
		 * 添加节点
		 */
		public void addNode(Node node) {
			//完成新节点中的元素与当前节点中的元素的判断
			//如果新节点中的元素小于当前节点中的元素，那么新节点放在当前节点的左子树中
			if(node.item.intValue()<this.item.intValue()) {
				if(this.left==null) {
					this.left=node;
				}else {
					this.left.addNode(node);
				}
			}else {
				//如果新节点中的元素大于当前节点中的元素，那么新节点放在当前节点的右子树中
				if(this.rigtt==null) {
					this.rigtt=node;
				}else {
					this.rigtt.addNode(node);
				}
			}
		}
		/**
		 * 使用中序遍历二叉树(左-根-右)
		 * 
		 * 递归的本质就是压栈与出栈的操作
		 * 当递归调用时每次调用自己时可以看做是压栈过程，当递归条件满足结束时，
		 * 递归一级一级的返回时可以看做是出栈的过程。
		 * 
		 */
		public void inorderTraversal() {
			//找到最左侧的那个节点
			if(this.left!=null) {
				this.left.inorderTraversal();
			}
			System.out.println(this.item);
			if(this.rigtt!=null) {
				this.rigtt.inorderTraversal();
			}
		}
	}
	
	private Node root;//存放根节点
	/**
	 * 将元素添加到排序器中
	 */
	public void add(E element) {
		//实例化节点对象
		Node<E> node=new Node<>(element);
		//判断当前二叉树中是否有根节点，如果没有那么新节点为根节点
		if(this.root==null) {
			this.root=node;
		}else {
			this.root.addNode(node);
		}
	}
	
	/**
	 * 对元素进行排序
	 */
	public void sort() {
		//判断根节点是否为空
		if(this.root==null) return;
		this.root.inorderTraversal();
	}
	
	public static void main(String[] args) {
		BinaryTreeSort<Integer> bts=new BinaryTreeSort<>();
		bts.add(1);
		bts.add(8);
		bts.add(6);
		bts.add(3);
		bts.add(5);
		bts.add(2);
		//排序
		bts.sort();
	}
}

运行结果：

4.自定义树形结构容器

4.1树形结构定义

能够找到当前结点的父结点

能够找到当前结点的子结点

能够找到当前结点的兄弟结点

能够找到当前结点的祖先结点

能够找到当前结点的子孙节点

4.2自定义树形结构分析

4.3实现自定义树形结构容器

package cn.pxy.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 基于树形结构实现元素存储的容器
 * @author 胖咸鱼
 *
 */
public class MyTree<E> {
	
	private Map<E,E> map=new HashMap<>();//String------String
	private Map<E,List<E>> map2=new HashMap<>();//String---List
	/**
	 * 向容器中添加元素
	 */
	public void add(E parent,E item) {
		//完成在单节点之间的映射
		this.map.put(item, parent);
		//完成多节点之间映射
		List<E> list=this.map2.get(parent);
		//判断当前节点下是否含有子节点，如果没有则创建一个新的list
		if(list==null) {
			list=new ArrayList<>();
			this.map2.put(parent, list);
		}
		list.add(item);
	}
	
	/**
	 * 获取当前节点的父节点
	 */
	public E getParent(E item) {
		return this.map.get(item);
	}
	
	/**
	 * 获取当前节点的子节点
	 */
	public List<E> getChild(E item){
		return this.map2.get(item);
	}
	
	/**
	 * 获取当前节点的兄弟节点
	 */
	public List<E> getBrother(E item){
		//获取当前节点的符节点
		E parent=this.getParent(item);
		//获取当前符节点的所有的子节点
		List<E> list=this.getChild(parent);
		List<E> brother=new ArrayList<>();
		if(list!=null) {
			brother.addAll(list);
			brother.remove(item);
		}
		return brother;
	}
	
	/**
	 * 获取当前节点的祖先节点
	 */
	public List<E> getForeFaqthers(E item){
		//获取当前节点的父节点
		E parent=this.getParent(item);
		//结束递归的边界条件
		if(parent==null) {
			return new ArrayList<>();
		}
		//递归调用，再次获取当前节点父节点的父节点
		List<E> list=this.getForeFaqthers(parent);
		//将递归到的所有节点元素添加到返回的list中
		list.add(parent);
		return list;
	}
	
	/**
	 * 获取当前节点的子孙节点
	 */
	public List<E> getGrandChildren(E item){
		//存放所有子孙节点中的元素
		List<E> list=new ArrayList<>();
		//获取当前节点的子节点
		List<E> child=this.getChild(item);
		//结束递归的边界条件
		if(child==null) {
			return list;
		}
		//遍历子节点
		for(int i=0;i<child.size();i++) {
			//获取节点中的元素
			E ele=child.get(i);
			List<E> temp=this.getGrandChildren(ele);
			list.add(ele);
			list.addAll(temp);
		}
		return list;
	}
	
	public static void main(String[] args) {
		//实例化容器
		MyTree<String> myTree=new MyTree<>();
		//添加元素
		myTree.add("root", "生物");
		myTree.add("生物","植物"); 
		myTree.add("生物","动物"); 
		myTree.add("生物","菌类"); 
		myTree.add("动物","脊椎动物"); 
		myTree.add("动物","脊索动物"); 
		myTree.add("动物","腔肠动物"); 
		myTree.add("脊椎动物","哺乳动物"); 
		myTree.add("脊椎动物","鱼类"); 
		myTree.add("哺乳动物","猫"); 
		myTree.add("哺乳动物","牛"); 
		myTree.add("哺乳动物","人"); 
		System.out.println("---------获取父结点---------"); 
		String parent = myTree.getParent("鱼类");
		System.out.println(parent); 
		System.out.println("---------获取子结点---------"); 
		List<String> child= myTree.getChild("动物"); 
		for(int i=0;i<child.size();i++){ 
			System.out.println(child.get(i)); 
		}
		System.out.println("---------获取兄弟结点---------"); 
		List<String> brother = myTree.getBrother("脊椎动物"); 
		for(int i=0;i<brother.size();i++){ 
			System.out.println(brother.get(i)); 
		}
		System.out.println("---------获取祖先结点---------"); 
		List<String> foreFathers = myTree.getForeFaqthers("人"); 
		for(int i=0;i<foreFathers.size();i++){ 
			System.out.println(foreFathers.get(i)); 
		}
		System.out.println("---------获取子孙结点---------"); 
		List<String> grandChildren = myTree.getGrandChildren("root"); 
		for(int i =0;i<grandChildren.size();i++){ 
			System.out.println(grandChildren.get(i)); 
		}
	}
}

运行结果：