当前位置:   article > 正文

java学习笔记第六周(一)_import java.util.arrays; import java.util.emptysta

import java.util.arrays; import java.util.emptystackexception; public class

目录

数据结构专项

一、数据结构简介

1、什么是数据结构

2、数据结构逻辑分类

二、线性结构

1 栈结构

1.1 栈的定义

1.2 实现自定义栈容器

2、链表结构

2.1 链表结构的定义

2.2  单向链表结构

 2.3 实现单向链表

2.4 双向链表结构

 2.5 实现双向链表

三、树形结构

1、树形结构简介

2、树的相关术语

3、二叉树简介

3.1二叉树分类

4、二叉树遍历

4.1 前序遍历

 4.2 中序遍历

​4.3 后序遍历

 4.4 层序遍历

5、二叉树排序

5.1 二叉树排序分析

5.2 二叉树排序实现

6、自定义树形结构容器

6.1 树形结构定义

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


数据结构专项

一、数据结构简介

1、什么是数据结构

简单地说,数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。所以我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。

数据结构=逻辑结构+物理结构(顺序、链式、索引、散列)

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

物理结构:(存储结构),在计算机存储器中的存储形式

 

2、数据结构逻辑分类

二、线性结构

1 栈结构

1.1 栈的定义

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

1.2 实现自定义栈容器

  1. package studyweek6数据结构;
  2. import java.util.Arrays;
  3. import java.util.EmptyStackException;
  4. /**
  5. * 自定义栈容器
  6. */
  7. public class MyStack<E> {
  8. private Object[] arr;//存放元素的物理结构
  9. private int stackLength=4;//数组的默认长度
  10. private int size; //记录栈容器的元素个数
  11. private int index=-1; //操作数组下标位置的指针
  12. /**判断栈容器是否为空
  13. *
  14. * @return
  15. */
  16. public boolean empty(){
  17. return this.size==0;
  18. }
  19. /**
  20. * 获取栈顶元素
  21. * @return
  22. */
  23. public E pop(){
  24. //如果栈容器中没有元素,则抛出异常
  25. if(this.index==-1){
  26. throw new EmptyStackException();
  27. }
  28. //拿出元素后要记录元素个数
  29. this.size--;
  30. //如果有元素,则返回栈顶元素
  31. return (E)this.arr[index--];
  32. }
  33. /**
  34. * 向栈容器中添加元素
  35. * @param item
  36. * @return
  37. */
  38. public E push(E item){
  39. //初始化数组
  40. this.capacity();
  41. //向数组中添加元素
  42. this.arr[++index]=item;//index先+1得到下标0,再添加
  43. //记录元素个数
  44. this.size++;
  45. return item;
  46. }
  47. /**
  48. * 数组初始化或者以1.5倍容量对数组扩容
  49. */
  50. private void capacity(){
  51. //数组初始化
  52. if(this.arr==null){
  53. this.arr=new Object[this.stackLength];
  54. }
  55. //以1.5倍对数组扩容
  56. if(this.size-(this.stackLength-1)>=0){
  57. this.stackLength=this.stackLength+(this.stackLength>>1);
  58. this.arr= Arrays.copyOf(this.arr,this.stackLength);//扩容操作是创建新的数组,并且把原数组拷贝到更大的数组里,copyOf()可以一次性实现,第一个参数是要扩容的原数组,第二哥参数是要扩容的长度
  59. }
  60. }
  61. //自定义栈容器的测试
  62. public static void main(String[] args) {
  63. //实例化容器哦
  64. MyStack<String> myStack=new MyStack<>();
  65. myStack.push("a");
  66. myStack.push("b");
  67. myStack.push("c");
  68. myStack.push("d");
  69. myStack.push("e");
  70. myStack.push("f");
  71. System.out.println(myStack.size);
  72. System.out.println(myStack.pop());
  73. System.out.println(myStack.pop());
  74. System.out.println(myStack.pop());
  75. }
  76. }

2、链表结构

2.1 链表结构的定义

 

2.2  单向链表结构

 2.3 实现单向链表

创建链表接口:

  1. package studyweek6数据结构;
  2. /**
  3. * 创建链表结构,让单向链表和双向链表实现该接口即可
  4. *基于链表结构存取元素的方法API定义
  5. * @param <E>
  6. */
  7. public interface MyList<E> {
  8. void add(E element);
  9. E get(int index);
  10. int size();
  11. E remove(int index);
  12. }

  1. package studyweek6数据结构;
  2. /**
  3. * 基于单向链表实现元素存取的容器
  4. * @param <E>
  5. */
  6. public class MySinglyLinkedList<E> implements MyList<E> {
  7. /**
  8. * 定于单向链表的节点对象(使用节点内部类来实现)
  9. */
  10. class Node<E>{
  11. private E item;//存储元素
  12. private Node next;//存储下一个节点对象的成员变量的的地址
  13. Node(E item,Node next){
  14. this.item=item;
  15. this.next=next;
  16. }
  17. }
  18. private Node head;//存放链表中的头节点(第一个节点)
  19. private int size;//记录元素的个数
  20. /**
  21. * 向链表中添加元素
  22. * @param element
  23. */
  24. @Override
  25. public void add(E element) {
  26. //创建节点
  27. Node<E> node=new Node<>(element,null);
  28. //找到尾节点
  29. Node tail=getTail();
  30. //节点的挂接
  31. if(tail==null){
  32. this.head=node;
  33. }else{
  34. tail.next=node;
  35. }
  36. //记录元素个数
  37. this.size++;
  38. }
  39. /**
  40. * 找尾节点
  41. */
  42. private Node getTail(){
  43. //判断头节点是否存在
  44. if(this.head==null){
  45. return null;
  46. }
  47. //查找尾节点
  48. Node node=this.head;
  49. while(true){
  50. if(node.next==null)break;
  51. node=node.next;
  52. }
  53. return node;
  54. }
  55. /**
  56. * 根据元素的位置获取元素
  57. * @param index
  58. * @return
  59. */
  60. @Override
  61. public E get(int index) {
  62. //校验Index的合法性
  63. this.checkIndex(index);
  64. //根据位置获取指定字节
  65. Node<E> node=this.getNode(index);
  66. //返回该节点中的元素
  67. return node.item;
  68. }
  69. /**
  70. * 对index合法性进行校验
  71. */
  72. private void checkIndex(int index){
  73. if(!(index>=0&&index<this.size)){
  74. throw new IndexOutOfBoundsException("Index:"+index+"Size"+this.size);
  75. }
  76. }
  77. /**
  78. * 根据位置获取节点
  79. */
  80. private Node getNode(int index){
  81. Node<E> node=this.head;
  82. for(int i=0;i<index;i++){
  83. node=node.next;
  84. }
  85. return node;
  86. }
  87. /**
  88. * 获取元素个数的方法
  89. * @return
  90. */
  91. @Override
  92. public int size() {
  93. return this.size;
  94. }
  95. /**
  96. * 根据元素的位置删除元素
  97. * @param index
  98. * @return
  99. */
  100. @Override
  101. public E remove(int index) {
  102. //校验Index的合法性
  103. this.checkIndex(index);
  104. //根据位置找到该节点对象
  105. Node<E> node=this.getNode(index);
  106. //获取该节点对象的元素
  107. E item=node.item;
  108. //删除该节点对象
  109. //判断当前删除的节点是否为头节点
  110. if(this.head==node){
  111. this.head=node.next;
  112. }else{
  113. Node<E> temp=this.head;
  114. for(int i=0;i<index-1;i++){
  115. temp=temp.next;//temp会循环到node前一个节点
  116. }
  117. temp.next=node.next;//node前一个节点的下一个节点指向node的下一个节点,这样就可以跳过node节点
  118. }
  119. node.next=null;
  120. //记录元素个数
  121. this.size--;
  122. //将被删除的元素返回
  123. return item;
  124. }
  125. public static void main(String[] args) {
  126. MySinglyLinkedList<String> mySinglyLinkedList=new MySinglyLinkedList<>();
  127. mySinglyLinkedList.add("a");
  128. mySinglyLinkedList.add("b");
  129. mySinglyLinkedList.add("c");
  130. mySinglyLinkedList.add("d");
  131. System.out.println(mySinglyLinkedList.size());
  132. System.out.println(mySinglyLinkedList.remove(0));
  133. for(int i=0;i< mySinglyLinkedList.size;i++){
  134. System.out.println(mySinglyLinkedList.get(i));
  135. }
  136. }
  137. }

2.4 双向链表结构

 

 2.5 实现双向链表

  1. package studyweek6数据结构;
  2. public class MyDoublyLinkedLIst<E> implements MyList<E>{
  3. /**
  4. * 定义双向链表的节点对象
  5. */
  6. class Node<E>{
  7. E item;//记录元素
  8. Node<E> prev;//记录前一个节点对象
  9. Node<E> next;//记录下一个节点对象
  10. Node(Node<E> prev,E item,Node<E> next){
  11. this.item=item;
  12. this.next=next;
  13. this.prev=prev;
  14. }
  15. }
  16. private Node head;//记录头节点
  17. private Node tail;//记录尾节点
  18. private int size;//记录元素个数
  19. /**
  20. * 向双向链表中添加元素
  21. * @param element
  22. */
  23. @Override
  24. public void add(E element) {
  25. this.linkLast(element);
  26. }
  27. /**
  28. * 将节点对象添加到双向链表的尾部
  29. */
  30. private void linkLast(E element){
  31. //获取尾节点
  32. Node t=this.tail;
  33. //创建节点对象
  34. Node<E> node=new Node<>(t,element,null);
  35. //将新节点定义为尾节点
  36. this.tail=node;
  37. if(t==null){
  38. this.head=node;
  39. }else{
  40. t.next=node;
  41. }
  42. this.size++;
  43. }
  44. /**
  45. * 根据指定位置获取元素
  46. * @param index
  47. * @return
  48. */
  49. @Override
  50. public E get(int index) {
  51. //Index合法性检验
  52. this.checkIndex(index);
  53. //根据位置获取指定节点对象
  54. Node<E> node=this.getNode(index);
  55. return node.item;
  56. }
  57. /**
  58. * 校验Index的合法性
  59. */
  60. private void checkIndex(int index){
  61. if(!(index>=0&&index<this.size)){
  62. throw new IndexOutOfBoundsException("Index"+index+"Size"+size);
  63. }
  64. }
  65. /**
  66. * 根据位置获取指定节点对象
  67. */
  68. private Node getNode(int index){
  69. //由于双向链表可以往任意一边开始查找,因此可以先判断当前位置距离头或者尾节点哪个更近
  70. if(index<(this.size>>1)){
  71. Node node=this.head;
  72. for(int i=0;i<index;i++){
  73. node=node.next;//移动node指针
  74. }
  75. return node;
  76. }else{
  77. Node node=this.tail;
  78. for(int i=this.size-1;i>index;i--){
  79. node=node.prev;
  80. }
  81. return node;
  82. }
  83. }
  84. /**
  85. * 返回元素个数
  86. * @return
  87. */
  88. @Override
  89. public int size() {
  90. return this.size;
  91. }
  92. /**
  93. * 根据指定位置删除元素
  94. * @param index
  95. * @return
  96. */
  97. @Override
  98. public E remove(int index) {
  99. //对index进行合法性校验
  100. this.checkIndex(index);
  101. //根据指定位置获取节点对象
  102. Node<E> node=this.getNode(index);
  103. //获取节点对象中的元素
  104. E item=node.item;
  105. //判断当前节点是否为头节点
  106. if(node.prev==null){//头节点的prev为空
  107. this.head=node.next;
  108. }else{
  109. //完成当前节点的直接前驱节点与当前节点的直接后继节点的挂接
  110. node.prev.next=node.next;
  111. }
  112. //判断当前节点是否为尾节点
  113. if(node.next==null){
  114. this.tail=node.prev;
  115. }else{
  116. //完成当前节点的直接后继节点与当前节点的直接前驱节点的挂接
  117. node.next.prev=node.prev;
  118. }
  119. //移除出链表
  120. node.prev=null;
  121. node.next=null;
  122. node.item=null;
  123. this.size--;
  124. return item;
  125. }
  126. /**
  127. * 在双向链表的头添加元素
  128. */
  129. public void addFirst(E element){
  130. this.linkFirst(element);
  131. }
  132. private void linkFirst(E element){
  133. Node head=this.head;
  134. Node node=new Node<>(null,element,head);
  135. //将新节点定义为头节点
  136. this.head=node;
  137. //判断当前链表中是否有节点,如果没有,那么该节点既是头也是尾节点
  138. if(head==null){
  139. this.tail=node;
  140. }else{
  141. head.prev=node;
  142. }
  143. this.size++;
  144. }
  145. /**
  146. * 在双向链表的尾添加元素
  147. */
  148. public void addLast(E element){
  149. this.linkLast(element);
  150. }
  151. //测试
  152. public static void main(String[] args) {
  153. /*MyList<String> myList=new MyDoublyLinkedLIst<>();
  154. myList.add("a");
  155. myList.add("b");
  156. myList.add("c");
  157. myList.add("d");
  158. System.out.println(myList.remove(2));
  159. System.out.println(myList.size());
  160. for(int i=0;i<myList.size();i++){
  161. System.out.println(myList.get(i));
  162. }*/
  163. //由于新建的addFirst和addLast方法没有在接口里定义,因此想要使用,引用必须是 MyDoublyLinkedLIst类型
  164. MyDoublyLinkedLIst<String> list=new MyDoublyLinkedLIst<>();
  165. list.add("a");
  166. list.addFirst("A");
  167. list.addLast("B");
  168. for(int i=0;i<list.size();i++){
  169. System.out.println(list.get(i));
  170. }
  171. }
  172. }

三、树形结构

1、树形结构简介

2、树的相关术语

 

 

3、二叉树简介

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

3.1二叉树分类

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

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

 

4、二叉树遍历

二叉树遍历的方式:

前序遍历:根-左-右

中序遍历:左-根-右

后序遍历:左-右-根

层序遍历:从上至下逐层遍历

4.1 前序遍历

 4.2 中序遍历

4.3 后序遍历

 4.4 层序遍历

 

5、二叉树排序

5.1 二叉树排序分析

 

5.2 二叉树排序实现

  1. package studyweek6数据结构;
  2. /**
  3. * 基于二叉树结构实现元素排序处理
  4. */
  5. public class BinaryTreeSort<E extends Integer>{//目前先实现整数的排序处理
  6. /**
  7. * 定义结点类
  8. */
  9. class Node<E extends Integer> {
  10. private E item;//存放元素
  11. private Node left;//存放左子树地址
  12. private Node right;//存放右子树地址
  13. Node(E item){
  14. this.item=item;
  15. }
  16. /**
  17. * 添加结点
  18. */
  19. public void addNode(Node node) {
  20. //完成新结点中的元素与当前结点中的元素的判断
  21. //如果新结点中的元素小于当前结点中的元素,那么新结点则放到当前结点的左子树中
  22. if (node.item.intValue() < this.item.intValue()) {
  23. if (this.left == null) {
  24. this.left = node;
  25. } else {
  26. this.left.addNode(node);//递归判断
  27. }
  28. }
  29. //如果新结点中的元素小于当前结点中的元素,那么新结点则放到当前结点的左子树中
  30. else {
  31. if(this.right==null){
  32. this.right=node;
  33. }
  34. else{
  35. this.right.addNode(node);
  36. }
  37. }
  38. }
  39. /**
  40. * 使用中序遍历二叉树
  41. */
  42. public void inorderTraversal(){
  43. //找到最左侧的那个结点
  44. if(this.left!=null){
  45. this.left.inorderTraversal();
  46. }
  47. System.out.println(this.item);
  48. if(this.right!=null){
  49. this.right.inorderTraversal();
  50. }
  51. }
  52. }
  53. /**
  54. * 将元素添加到排序器中
  55. */
  56. private Node root;//存放数的根结点的地址
  57. public void add(E element){
  58. //实例化结点对象
  59. Node<E> node=new Node<>(element);
  60. //判断当前二叉树中是否有根结点。如果没有那么新结点就是根结点
  61. if(this.root==null){
  62. this.root=node;
  63. }else{
  64. this.root.addNode(node);
  65. }
  66. }
  67. /**
  68. * 对元素进行排序
  69. */
  70. public void sort(){
  71. //判断根结点是否为空
  72. if(this.root==null)return;
  73. this.root.inorderTraversal();
  74. }
  75. //测试
  76. public static void main(String[] args) {
  77. BinaryTreeSort<Integer> sort=new BinaryTreeSort<>();
  78. //8,1,3,9,4,5
  79. sort.add(8);
  80. sort.add(1);
  81. sort.add(3);
  82. sort.add(9);
  83. sort.add(4);
  84. sort.add(5);
  85. sort.sort();
  86. }
  87. }

6、自定义树形结构容器

6.1 树形结构定义

 

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

  1. package studyweek6数据结构;
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.List;
  5. import java.util.Map;
  6. /**
  7. * 基于树形结构实现元素的储存器
  8. */
  9. public class MyTree <E>{
  10. private Map<E,E> map=new HashMap<>();//String->String
  11. private Map<E,List<E>> map2=new HashMap<>(); //String->List
  12. /**
  13. * 向容器中添加元素
  14. */
  15. public void add(E parent,E item){
  16. //完成单结点之间的映射
  17. this.map.put(item,parent);
  18. //完成多结点之间的映射
  19. List<E> list =this.map2.get(parent);
  20. if(list==null){
  21. list=new ArrayList<>();
  22. this.map2.put(parent,list);
  23. }
  24. list.add(item);
  25. }
  26. /**
  27. * 获取当前结点的父结点
  28. */
  29. public E getParent(E item){
  30. return this.map.get(item);
  31. }
  32. /**
  33. * 获取当前结点的子结点
  34. */
  35. public List<E> getChild(E item){
  36. return this.map2.get(item);
  37. }
  38. /**
  39. * 获取当前结点的兄弟结点
  40. */
  41. public List<E> getBrother(E item){
  42. //获取当前结点的父结点
  43. E parent=this.getParent(item);
  44. //获取当前父结点的所有子结点
  45. List<E> list=this.getChild(parent);
  46. List<E> brother=new ArrayList<>();//不能直接删除list里面的该结点,不然下面所有的子结点会丢失
  47. if(list!=null){
  48. brother.addAll(list);
  49. brother.remove(item);
  50. }
  51. return brother;
  52. }
  53. /**
  54. * 获取当前结点的祖先结点
  55. */
  56. public List<E> getForefathers(E item){
  57. //获取当前结点的父结点
  58. E parent=this.getParent(item);
  59. //结束递归的边界条件
  60. if(parent==null){
  61. return new ArrayList<>();
  62. }
  63. //递归调用,再次获取当前结点的父结点的父结点
  64. List <E> list=this.getForefathers(parent);//这里的list是当递归结束后会创建一个List去接受所得到的父节点的返回值
  65. //将递归到的所有结点元素添加到返回的List中
  66. list.add(parent);//弹栈时再执行
  67. return list;
  68. }
  69. /**
  70. * 获取当前结点的子孙结点
  71. */
  72. public List<E> getGrandChildren(E item){
  73. //存放所有子孙结点中的元素
  74. List<E> list=new ArrayList<>();
  75. //获取当前结点的子结点
  76. List<E> child=this.getChild(item);
  77. //结束递归的边界条件
  78. if(child==null){
  79. return list;
  80. }
  81. //遍历子结点
  82. for(int i=0;i<child.size();i++){
  83. //获取结点中的元素
  84. E ele=child.get(i);
  85. //递归调用
  86. List<E> temp=this.getGrandChildren(ele);
  87. list.add(ele);
  88. list.addAll(temp);
  89. }
  90. return list;
  91. }
  92. public static void main(String[] args) {
  93. //实例化容器
  94. MyTree<String> myTree=new MyTree<>();
  95. //添加元素
  96. myTree.add("root","生物");
  97. myTree.add("生物","植物");
  98. myTree.add("生物","动物");
  99. myTree.add("生物","菌类");
  100. myTree.add("动物","脊椎动物");
  101. myTree.add("动物","脊索动物");
  102. myTree.add("动物","腔肠动物");
  103. myTree.add("脊椎动物","哺乳动物");
  104. myTree.add("脊椎动物","鱼类");
  105. myTree.add("哺乳动物","猫");
  106. myTree.add("哺乳动物","牛");
  107. myTree.add("哺乳动物","人");
  108. System.out.println("-----------获取父结点-----------");
  109. String parent= myTree.getParent("鱼类");
  110. System.out.println(parent);
  111. System.out.println("-----------获取子结点-----------");
  112. List<String> child=myTree.getChild("动物");
  113. for (int i=0;i<child.size();i++){
  114. System.out.println(child.get(i));
  115. }
  116. System.out.println("-----------获取兄弟结点-----------");
  117. List<String> brother=myTree.getBrother("脊椎动物");
  118. for (int i=0;i<brother.size();i++){
  119. System.out.println(child.get(i));
  120. }
  121. System.out.println("-----------获取祖先结点-----------");
  122. List<String> foreFathers=myTree.getForefathers("人");
  123. for (int i=0;i<foreFathers.size();i++){
  124. System.out.println(foreFathers.get(i));
  125. }
  126. System.out.println("-----------h获取子孙结点-----------");
  127. List<String> grandChildren=myTree.getGrandChildren("root");
  128. for (int i=0;i<grandChildren.size();i++){
  129. System.out.println(grandChildren.get(i));
  130. }
  131. }
  132. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/201976
推荐阅读
相关标签
  

闽ICP备14008679号