数据结构与算法
1.时间空间复杂度
注：(时间空间复杂度=时间和空间的增长趋势)
1.1时间复杂度（BigO）
【大O表示法】算法的渐进时间复杂度-> T(n)=O(f(n))
注：T(n)代表的是算法的渐进时间复杂度，f(n)是代码的执行次数
for(int i =1 ;i<n;i++){ /*此行代码执行1+2N次*/x++; /*此行代码执行N次*/} /*而在BigO中n是看成无穷的，所以此时有O(1+3N)=O(N)*/for(int i =1;i<n;i++){for(int j =1;i<n;j++){x++; /*同理，两个循环的代码的O(N)=O(N^2)*/}} /*此时，则有O(N)=O(N^2+N)*/
int x=0;int y=1;int temp =x;x=y;y=temp; /*该代码块的O(N)=O(1)*/
int i =1;while(i<n){ /*假设i在k次方时等于n，即2^k=n,所以k=logN*/i=i*2; /*所以该代码块的O(N)=O(logN)*/}
for(int i=1;i<n;i++){int x=1; /*由代码块1和代码块3得O(N)=O(NlogN)*/while(x<n){x=x*2;}}
1.2空间复杂度
内存空间增长的趋势
int x=0;int y=0;x++;y++; /*空间复杂度为O(1)*/
int[] newArray = new int[n];for(int i=0;i<n;i++){newArray[i]=i; /*空间复杂度O(n)*/}
2.排序算法
2.1插入排序（Insertion Sort）
在插入排序中，我们从前到后依次处理未排好序的元素，对于每个元素，我们将它与之前排好序的元素进行比较，找到对应的位置后并插入。
public void insertionSort(int[] array){for(int i=1;i<array.lenth;i++){ //从这个数组的第二个元素开始，从后向前扫描int cur=array[i]; //当前扫描的赋给curint insertionIndex=i-1;while(insertionIndex>=0&&array[insertionIndex]>cur){ //如果上一个数比当前的数大array[insertionIndex+1]=array[insertionIndex]; //则两个数调换位置insertionIndex--; //--向前面的数继续进行判断}array[insertionIndex+1]=cur; //若while的代码进行执行则两个数调换位置，没有执行的话，被扫描到的这个数位置不变}}
注：这段代码的时间复杂度为O(n^2),空间复杂度是O(1)。
2.2快速排序（Quick Sort）
快排是一种分治(Divide and Conquer)算法，在这个算法中，我们吧大问题变成小问题，然后将小问题逐个解决，当小问题解决玩时，大问题也迎刃而解了。
public void quickSort(int[] array,int left,int right){if(left>=right)return;int partitionIndex=partition(array,left,right);quickSort(array,partitionIndex+1,right);}public int partition(int[] array,int left,int right){int pivot=array[right];int leftIndex=left;int rightIndex=right-1;while(true){while(lefiIndex<right&array[leftIndex]<=pivot){leftIndex++;}while(rightIndex>=left&&array[rightIndex]>pivot){rightIndex--;}if(leftIndex>rightIndex)break;swap(array,leftIndex,rightIndex);}swap(array,leftIndex,right)return leftIndex;}public void swap(int[] array,int left,int right){int temp=array[left];array[left]=array[right];array[right]=temp;}
2.3归并排序（Merge Sort）
在此算法中，我们将一个数组氛围两个子数组，通过递归重复将数组切分到只剩下一个元素为止，然后把每个子数组中的元素排序后合并，通过不断合并子数组，最后就会拿到一个排序好的大数组。
public void mergeSort(int[] array){int[] helper=copy(array);mergeSort(array,helper,0,array.length-1);return array;}public void mergeSort(int[] array,int[] helper,int left,int right){if(right-left<1)return;int mid=left+(right-left)/2;mergeSort(array,helper,left,mid);mergeSort(array,helper,mid+1,right);merge(array,helper,left,mid,right);}public void merge(int[] array,int[] helper,int left,int mid,int right){for(int i =left;i<=right;i++){if(leftStart>mid){array[i]=helper[rightStart++];}else if(rightStart>right){array[i]=helper[leftStart++];}else if(helper[leftStart]<helper[rightStart]){array[i]=helper[leftStart++];}else{array[i]=helper[rightStart++];}}}
3.链表
3.1链表包括
单链表、双链表、循环链表
3.2链表的基本操作：
- 插入：将一个新元素插入链表的任意位置
- 删除：将一个元素从链表中删除
- 查找（遍历）：查找一个特定的元素
- 更新：更新一个特定节点上的元素
/*链表的定义*/
public class LinkedList{
static class ListNode( //节点的定义ListNode
int val; //节点上面的支
ListNode next;) //指针，指向下一个节点
public ListNode(int val){
this.val=val;
}
ListNode head; //头指针
ListNode tail; //尾指针
int size; //记录当前的节点数量
public LinkedList(){
head=null;
tail=null;
size=0;
}
}
/*插入 注：需要考虑是从这个链表的头部、中间还是尾部进行节点的插入*/
public void insert(int position,int number){
if(position>size){
return;
}
ListNode newNode=new ListNode(number);
if(position==0){
newNode.next=head;
head=newNode;
if(tail==null){
tail=newNode;
}
size++;
}else if(position==size){
this.append(number);
}else{
ListNode prev=head;
for(int i=0;i<position-1;i++){
prev=prev.next;
}
ListNode next=prev.next;
newNode.next=next;
prev.next=newNode;
size++
}
}
public void append(int number){
ListNode newNode=new ListNode(number);
if(tail==null){
tail=newNode;
}else{
tail.next=newNode;
tail=newNode
}
size++;
}
/*删除*/
public void delete(int number){
if(head!=null&&head.val==number){
head=head.next;
size--;
if(size==0){
tail=head;
}
}else{
ListNode prev=head;
ListNode cur=head;
while(prev!=null&&cur!=null){
if(cur.val==number){
if(cur==tail){
tail=prev;
}
prev.next=cur.next;
size--;
return;
}
prev=cur;
cur=cur.next;
}
}
}
/*查找*/
public int search(int number){
ListNode cur=head;
for(int index=0;cur!=null;index++){
if(cur.val==number){
return index;
}
cur=cur.next;
}
return -1;
}
/*更新*/
public int update(int oldValue,int newValue){
ListNode cur=head;
for(int index=0;cur!=null;index++){
if(cur.val==oldValue){
cur.val=newValue;
return index;
}
cur=cur.next;
}
retrun -1;
}
4.栈和队列
4.1堆栈(Stack)
堆栈是一种常用的数据结构，这种数据结构的存储方式和垃圾桶一样，后面放进去的元素可以先取出来，而最早放入的元素会被压在最下面，最后才能被拿出来。我们也可以把栈的储存方式简单理解为堆盘子，后面加入的盘子会被堆到最上面，最早堆入的盘子在最下面。
所以栈是一种后进先出（Last In First Out）的数据结构，后入的元素先出，先入的元素后出。
堆栈主要支持以下的两种操作：
- 入栈（Push）：将一个元素放入栈，用来加入数据。
- 出栈（Pop）：将一个元素弹出栈，用来删除数据。
还有以下两种辅助操作：
- Peek：查看最顶部的元素。
- isEmpty：查看栈是否为空。
/*数组栈的定义（即，用数组实现栈）*/
public class Stack {
static final int CAPACITY = 1000; //CAPACITY用来限制栈的容量
int top; //使用指针top来记录顶端元素的位置
int stack[];
public Stack() {
top = -1; //top初始化-1，代表数组栈没有任何元素
stack = new int[CAPACITY];
}
}
/*入栈（push）*/
public boolean push(int val) {
if (top >= (CAPACITY - 1)) { //在push中，需要判断顶部元素是否达到容量限制
System.out.println("Stack Overflow.");
return false; //如果达到容量限制，则输出“溢出栈”错误
}
stack[++top] = val; //否则，移动top指针，加入新的元素
return true;
}
/*出栈（pop）*/
public int pop() {
if (top < 0) { //在pop中，需要判断栈是否为空
System.out.println("Stack Underflow.");
return 0; //如果栈为空，则输出“栈下溢”错误
}
int element = stack[top--]; //否则将top指针减一，进行出栈操作
return element;
}
/*查看最顶部的元素（peek）*/
public int peek() {
if (top < 0) { //需要判断栈是否为空
System.out.println("Stack Underflow");
return 0;
}
int element = stack[top];
return element;
}
/*查看栈是否为空（isEmpty）*/
public boolean isEmpty() {
return top < 0;
}
4.2队列（Queue）
队列是很好理解的一种数据结构，顾名思义，队列数据结构就和我们平时排队一样，先进入的元素先出，后进入的元素后出。队列的两端都是开的，一段负责插入新元素，另一端负责删除元素。
队列主要支持以下两种操作：
- 入队（enqueue）：增加一个新的元素
- 出队（dequeue）：删除一个元素
还支持其他辅助操作：
- peek – 查看队列最前端的元素
- isFull – 查看队列是否满了
- isEmpty – 查看队列是否为空
/*循环队列，它和基础的顺序队列相比较，更能有效地利用数组空间*/
public class ArrayQueue {
int front, rear, size; //两个指针front、rear，front来指向队列的头部，rear指向队列尾部，size来记录元素的数量
int capacity; //capacity来限制队列的长度
int array[];
public ArrayQueue(int capacity) {
this.capacity = capacity;
front = rear = size = 0;
array = new int[capacity];
}
}
/*入队——增加一个新元素*/
public void enqueue(int item) {
if (isFull()) return;
array[rear] = item;
rear = (rear + 1) % capacity; //防止rear超过队列的内存
size++;
System.out.println(item + " is enqueued.");
}
/*出队——删除一个元素*/
public int dequeue() {
if (isEmpty()) return Integer.MIN_VALUE;
int item = array[front];
front = (front + 1) % capacity;
size --;
return item;
}
/*查看队列最前端的元素*/
public int peek() {
if (isEmpty()) return Integer.MIN_VALUE;
return array[front];
}
/*查看队列是否满了*/
public boolean isFull() {
return size == capacity;
}
/*查看队列是否为空*/
public boolean isEmpty() {
return size == 0;
}
5.优先队列和哈希表
5.1哈希表的介绍
- 数组：寻址容易，插入和删除元素困难
- 链表：寻址困难，插入和删除元素容易
而哈希表则是数组和链表的结合
5.2哈希表支持的操作：
- get(K key)：通过特定的关键字拿到其所对应的值
- add(Key key, Value value)：将一对新的键值对加入哈希表
- remove(Key key)：通过关键字，删除哈希表中的键值对
- getSize()：当前键值对的数量
- isEmpty()：查看哈希表是否为空
/*哈希表的实现*/
import java.util.ArrayList;
public class HashMap {
static class HashNode<String, Integer> { //HashNode是键值对节点的定义
String key; //关键字
Integer value; //数值
HashNode<String, Integer> next; //next指向下一个节点
public HashNode(String key, Integer value) {
this.key = key;
this.value = value;
}
}
private ArrayList<HashNode<String, Integer>> bucketArray;
private int numBuckets;
private int size;
public HashMap() { //HashMap是哈希表的定义
bucketArray = new ArrayList<>();//ArrayLis的bucketArray，可理解为哈希表图左侧的数组
numBuckets = 10; //numBuckets代表哈希表数组的长度
size = 0; //size代表当前bucket的数量
for(int i = 0; i < numBuckets; i++) { //在每个buckArray上加一个空的头节点
bucketArray.add(null);
}
}
}
/*输入一个关键字，输出是关键字对应的bucket位置*/
private int getBucketIndex(String key) {
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index;
}
/*将一对新的键值加入哈希表*/
public void add(String key, Integer value) {
int bucketIndex = getBucketIndex(key);//使用getBucketIndex拿到关键字对应的bucket指数
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
while (head != null) {
if (head.key.equals(key)) { //寻找与关键词对应的节点
head.value = value; //找到则更新节点数据
return;
}
head = head.next; //没找到则创建一个新的键值对节点，再把新节点更新为对应bucket的头节点
}
size++;
head = bucketArray.get(bucketIndex);
HashNode<String, Integer> newNode = new HashNode<String, Integer>(key, value);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
if ((1.0 * size) / numBuckets >= 0.7) {//如果当前键值对数量超过了bucket容量的70%
ArrayList<HashNode<String, Integer>> temp = bucketArray;
bucketArray = new ArrayList<>(); //则创建一个长度为当前数量两倍的bucketArray，并把当前的节点转移到新的bucketArray上
numBuckets = 2 * numBuckets;
size = 0;
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
for (HashNode<String, Integer> headNode : temp) {
while(headNode != null) {
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
/*get函数是通过关键字找到对应数组的函数*/
public Integer get(String key) {
int bucketIndex = getBucketIndex(key); //先通过getBucketIndex拿到关键字对应的bucket指数
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
while (head != null) { //并拿到head头指针，顺着对应的链表往下走
if (head.key.equals(key)) { //寻找是否有对应的关键字的节点
return head.value; //找到则返回对应的数值
}
head = head.next;
}
return null; //未找到则返回null
}
/*通过关键字，删除哈希表中的键值对*/
public Integer remove(String key) {
int bucketIndex = getBucketIndex(key);//先通过getBucketIndex拿到关键字对应的bucket指数
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
HashNode<String, Integer> prev = null; //拿到头指针，通过迭代next指针
while (head != null) { //使用删除链表节点的方式来删除对应的节点
if (head.key.equals(key))
break;
prev = head;
head = head.next;
}
if (head == null) {
return null;
}
size--;
if (prev != null) {
prev.next = head.next;
} else {
bucketArray.set(bucketIndex, head.next);
}
return head.value;
}
/*查看当前键值对的数量*/
public int size() {
return size;
}
/*查看哈希表是否为空*/
public boolean isEmpty() {
return size() == 0;
}
6.树
6.1树的种类
- 二叉树（Binary Tree）：每个节点最多含有两个子节点，上面图示中的树就是二叉树。
- 完全二叉树（Complete Binary Tree）：假设一个二叉树深度（depth）为d（d > 1），除了第d层外，其它各层的节点数量均已达到最大值，且第d层所有节点从左向右紧密排列，这样的二叉树就是完全二叉树。
- 满二叉树（Full Binary Tee）：在满二叉树中，每个不是尾节点的节点都有两个子节点。
- 排序二叉树（Binary Search Tree）：在此树中，每个节点的数值比左子树上的每个节点都大，比所有右子树上的节点都小。
- 平衡二叉树（AVL Tree）：任何节点的两颗子树的高度差不大于1的二叉树。
注：AVL Tree图中左支树的高度为二，右支树的高度为一
- B树（B-Tree）：B树和平衡二插树一样，只不过它是一种多叉树（一个节点的子节点数量可以超过二）。
- 红黑树（Red—Black Tree）：是一种自平衡二叉寻找树。
6.2二分查找树（Binary Search Tree）的实现
/*二分查找树的实现*/
public class BST {
static class TreeNode {
public int value; //记录数值
public TreeNode left; //left指向left child
public TreeNode right; //right指向right child
public TreeNode(int value) {
this.value = value;
}
}
private TreeNode root; //根节点root
}
/*在二分查找树中，查找某个数*/
public TreeNode get(int key){
TreeNode current=root; //从头节点开始搜索
whlie(current!=null&¤t.value!=key){ //判断条件，检测的值不为空，且未检测到目标值
if(key<current.value){
current=current.left;
}else if(key>current.right){
current=current.right;
}
}
return current==null?null:current;
}
public void insert(int key) {
if(root == null) {
root = new TreeNode(key);
return;
}
TreeNode current = root; //current代表要插入的位置
TreeNode parent = null; //parent代表所插入的位置的父亲
while(true) {
parent = current;
if(key < parent.value) {
current = parent.left;
if(current == null) {
parent.left = new TreeNode(key);
return;
}
} else if (key > parent.value){
current = parent.right;
if(current == null) {
parent.right = new TreeNode(key);
return;
}
} else {
return; // BST does not allow nodes with the same value
}
}
}
6.3树的遍历
- 前序遍历 A B D H E I C F J K G
- 中序遍历 D H B E I A J F K C G
- 后序遍历 H D I E B J F K G C A
7.图（Graph）
7.1图的种类
无向图（Undirected Graph）：在无向图中，每个顶点和其他顶点通过相连线连接。
有向图（Directed Graph）：有向图中的相连线是有方向的。
权重图（Weighted Graph）：在权重图中，每条相连线有各自的权重。
有向图
权重图
7.2图的实现
7.2.1有向图的实现（Directed Graph）
有向图的实现有两种，一种是用矩阵（Matrix）的形式来实现，另一种是用链表（List）的形式来实现。
- 使用矩阵实现有向图
每行代表相应的顶点，如果M[i][j]= 1，那么就代表顶点 i 连向 j，如果是0，则表达顶点间没有联系。用矩阵的方式来实现图的优势很明显，我们可以很快地判断两个顶点之间是否相连，可是用矩阵实现的空间复杂度很高，我们需要O(V^2)来记录所有的数据
- 使用链表实现有向图
图的左侧用数组来实现，代表我们的所有顶点，而每个顶点含有一个链表，链表上储存了该顶点指向的顶点。优点是没有浪费空间
7.3图的遍历（Graph Traversal）
1.深度优先搜索（Depth-first Search）
注：在图的深度优先搜索中，我们尽可能先遍历一个顶点可以达到的最深处，其中可能会出现的问题就是会有循环出现，所以我们需要一个数组来记录哪些节点已经被访问过。
- 访问A
- 访问B（在访问A之后，接下来应该访问的是A出发的另一个顶点，既顶点B）
- 访问C（在访问B之后，接下来访问的是从B出发的另一个顶点，既C，E，F。在此图中，我们按照字母排序顺序访问，因此先访问C。）
- 访问E（接下来访问与C连接的另一个顶点E。）
- 访问D（接下来访问从E出发的顶点B和D，因为B已被访问过，所以访问顶点D。）
- 访问F（接下来回溯“访问A的另一个连接顶点F”）
- 访问G
2.广度优先搜索（Breadth-first search）
广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。
- 访问A
- 访问B
- 依次访问C，E，F（在B被访问之后，接下来访问B的邻接点，既C，E，F。）
- 依次访问D，G（在访问完C，E，F之后，再依次访问他们出发的另一个顶点。还是按照C，E，F的顺序访问，C的已经全部访问过了，那么就只剩下E，E；先访问E的邻接点D，再访问F的邻接点G。
若有收获，就点个赞吧
0 人点赞
