共计 742 个字符,预计需要花费 2 分钟才能阅读完成。
数据结构的存储形式: 数组 (顺序存储) 和链表(链式存储)
数组和链表是根底构造,其余数据结构都是基于这个根底构建的
散列表
通过散列函数将键映射到一个大数组中。
栈
先进先出
队列
先进后出
堆
用数组实现就是[堆]
树
二叉搜寻树、AVL 树、红黑树、区间树和 B 树等等。
图
数据结构的基本操作
数据结构品种很多,但他们存在的目标就是在不同场景,尽可能高效地增删改查
如何遍历 + 拜访
线性和非线性
线性就是 for/while 迭代为代表, 非线性就是递归为代表
数组遍历框架
void traverse(int[] arr){for(int i=0;i<arr.length;i++){// 迭代拜访 arr}
常见框架
非线性,兼具迭代和递归结构
// 根本的单链表节点
class ListNode{
int val;
ListNode next;
}
void traverse(ListNode head){for(ListNode p=head;p!=null;p=p.next){// 迭代拜访 p.val}
}
void traverse(ListNode head){
// 递归拜访 head.val
traverse(head.next);
}
二叉树遍历框架
// 根本的二叉树节点
class TreeNode{
int val;
TreeNode left,right;
}
void traverse(TreeNode root){traverse(root.left);
traverse(roo.right);
}
衍生出的 N 多叉树
// 根本的 N 叉树节点
class TreeNode{
int val;
TreeNode[] children;}
void traverse(TreeNode root){for(TreeNode child:root.children){traverse(child);
}
}
正文完