基础数据结构
2021-06-06 18:46:42 8 举报AI智能生成
基础数据结构分叉
作者其他创作
大纲/内容
栈
import java.Stack;
getSize()
isEmpty()
push()
作用是入栈
pop()
作用是出栈
peek()
作用是读取栈顶元素
成员
E e
Node next
链表
单链表
虚拟头结点（第一个节点的前置节点）
初始化e=null，next=null
基础方法
getSize()
isEmpty()
add()
原理：/*Node node = new Node(e);
*node.next=prev.next;
prev.next=node;*/
*node.next=prev.next;
prev.next=node;*/
remove()
原理：Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
prev.next = retNode.next;
retNode.next = null;
根据索引查元素：使用遍历prev=prev.next
根据元素查索引或者查找是否有该元素：使用遍历prev=prev.next
toString()
双链表
成员
E e
Node nextleft
Node nextright
虚拟头结点
初始化e=null，next=null
基础方法
基础方法
getSize()
isEmpty()
add()
原理：在单链表的基础上，要将添加节点的前驱指向最后一个节点，实现双向链接。
remove()
原理:在单链表的基础上，除了将一个方向的指针移动之外，还要操作反方向的指针，即将删除节点的下一个节点的前驱指向删除节点的上一个节点，即完成删除。
根据索引查元素：使用遍历prev=prev.next
根据元素查索引或者查找是否有该元素：使用遍历prev=prev.next
toString()
博客链接
CSDN
动态数组
结构
成员
E e
size
capacity
基础方法
getSize()
isEmpty()
add
原理：索引后面的元素都往后推一格，在index处添加该元素
remove
原理：将索引后的元素全部往前移一格，然后将索引处位置利用java的回收机制回收掉
toString
栈
栈的结构是先进先出，可以利用动态数组的方法实现
队列
队列的结构是先进后出，根排队一样，同样也可以利用动态数组方法实现
二分搜索树
成员
E e
Node left
Node right
基础方法
getSize()
isEmpty()
add()
remove()
原理：将所添元素与结点比较，若比结点小则继续与左结点比较，若比节点大则与右结点比较，直到找到合适位置进行添加
原理：与上述类似，需要比较，但是需要把无关子树进行保存
toString()
原理：分三个部分，具体见代码
查找最大值与最小值
原理：最大值在最右边且没有比它更右的节点，而最小值是最左边的节点，没有节点比它更左的节点
遍历
前序遍历
中序遍历
后续遍历
接口
Comparable
队列
import java.Queue
getSize()
isEmpty()
enqueue()
作用是添加队尾元素
denqueue()
作用是取出队首元素
getFront()
读取队首元素
0 条评论
下一页
