Java基础——数据结构

Java基础——数据结构

一、数据结构简介

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)); } } }

运行结果:

...