數據結構開門篇
數據結構
1、什麼是數據結構
數據結構是數據組織、管理和存儲格式，其使用目的是為了高效地訪問和修改數據
2、時間複雜度和空間複雜度
什麼是時間複雜度
時間複雜度是對一個演算法運行時間長短的度量，用大O表示，記作
T(n)=O(f(n))
- 如果運行時間是常數量級，則用常數1表示
- 只保留時間函數中的最高階項
- 如果最高階項存在，則省區最高階項前面的係數
O(1)<O(logn)<O(n)<O(n2)
時間複雜度的場景：
線性、對數、常量、多項式
什麼是空間複雜度
空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，用大O表示，記作
S(n)=O(f(n))
空間複雜度的場景
常量空間、線性空間、二維空間、遞歸空間
O(1)、O(n)、O(n2)、O(n)
3、數組
public class ArrayDemo {
private int[] array;
private int size;
public ArrayDemo(int capacity){
this.array = new int[capacity];
size = 0;
}
/**
* 插入元素
* @param index
* @param element
*/
public void insert(int index,int element){
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("超過數組實際元素範圍！");
}
if(size >= array.length){
resize();
}
for (int i = size - 1; i >= size ; i--) {
array[i+1] = array[i];
}
array[index] = element;
size++;
}
/**
* 擴容
*/
public void resize(){
int[] arrayNew = new int[array.length*2];
System.arraycopy(array,0,arrayNew,0,array.length);
array = arrayNew;
}
public void output(){
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < size; i++) {
buffer.append(array[i]);
}
System.out.println(buffer);
}
public int delete(int index){
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("超出數組實際元素範圍");
}
int deletedElement = array[index];
for(int i = index;i < size - 1; i++){
array[i] = array[i - 1];
}
size--;
return deletedElement;
}
public static void main(String[] args) {
ArrayDemo arrayDemo = new ArrayDemo(2);
arrayDemo.insert(0,3);
arrayDemo.insert(1,7);
arrayDemo.insert(2,9);
arrayDemo.insert(3,5);
arrayDemo.delete(3);
arrayDemo.output();
}
}
利用下標查找數組元素的時間複雜度是O(1)，中間插入、刪除數組元素的時間複雜度是O(n)；
4、鏈表
public class LinkedListDemo {
/**
* 頭節點指針
*/
private Node head;
/**
* 尾節點指針
*/
private Node tail;
/**
* 鏈表實際長度
*/
private int size;
private static class Node{
int data;
Node next;
Node(int d){
this.data = d;
}
}
public void insert(int index,int data){
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("超出鏈表節點範圍！");
}
Node insetNode = new Node(data);
if(size == 0){
head = insetNode;
tail = insetNode;
}else if(index == 0){
insetNode.next = head;
head = insetNode;
}else if(index == size){
tail.next = insetNode;
tail = insetNode;
}else{
Node prevNode = getNode(index -1);
insetNode.next = prevNode.next;
prevNode.next = insetNode;
}
size++;
}
public Node remove(int index){
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("超出鏈表節點範圍！");
}
Node removeNode = null;
if(index == 0){
removeNode = head;
head = head.next;
}else if(index == size -1){
Node prevNode = getNode(index - 1);
//removeNode = prevNode.next;
prevNode.next = null;
tail = prevNode;
}else{
Node prevNode = getNode(index - 1);
removeNode = prevNode.next;
prevNode.next = removeNode.next;
}
size--;
return removeNode;
}
/**
* 獲取某個位置的鏈表
* @param index
* @return
*/
private Node getNode(int index) {
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("超出鏈表節點範圍！");
}
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
public void output(){
Node temp = head;
StringBuffer sb = new StringBuffer();
while(temp!= null){
sb.append(temp.data);
temp = temp.next;
}
System.out.println(sb);
}
public static void main(String[] args) {
LinkedListDemo linkedList = new LinkedListDemo();
linkedList.insert(0,3 );
linkedList.insert(1,4 );
linkedList.insert(2,5 );
linkedList.insert(3,6 );
linkedList.remove(1);
linkedList.output();
}
}
查找鏈表節點的時間複雜度是O(n),中間插入和刪除節點的時間複雜度是O(1)
5 棧和隊列
棧
棧是一種線性數據結構，可以用數組實現，也可以用鏈表實現。只能先進後出（FILO）
無論是以數組還是鏈表實現，入棧和出棧的時間複雜度都是
O（1）
隊列
隊列是一種線性數據結構，可以用數組實現，也可以用鏈表實現。先進先出（FIFO）.
當（隊尾下標+1）%數組長度 = 隊頭下標時，代表此隊列真的滿了
public class QueueDemo {
private int[] array;
private int front;
private int rear;
public QueueDemo(int capacity) {
this.array = new int[capacity];
}
/**
* 入隊
* @param element
* @throws Exception
*/
public void enQueue(int element) throws Exception {
if((rear + 1)% array.length == front){
throw new Exception("隊列已滿");
}
array[rear] = element;
rear =(rear + 1)% array.length;
}
/**
* 出隊
* @return
* @throws Exception
*/
public int dequeue() throws Exception {
if(rear == front){
throw new Exception("隊列已空！");
}
int dequeueElement = array[front];
front = (front + 1)% array.length;
return dequeueElement;
}
public void output(){
StringBuffer sb = new StringBuffer();
for (int i = front; i != rear ; i = (i + 1)% array.length) {
sb.append(array[i]);
}
}
public static void main(String[] args) throws Exception {
QueueDemo queue = new QueueDemo(3);
queue.enQueue(3);
queue.enQueue(4);
queue.enQueue(5);
queue.enQueue(6);
queue.dequeue();
queue.dequeue();
queue.output();
}
}
6 散列表
散列表也叫作哈希表，這種數據結構提供了鍵和值的映射關係。只要給出一個key，就可以高效查找到它匹配的value，時間複雜度接近O(1);
解決哈希衝突的方法主要有兩種，一種是開放定址法，一種是鏈表法。
在java中，ThreadLocal用的就是開放定址法；Java集合類HashMap中，使用的是鏈表法
樹
二叉樹有兩種特殊形式
一個叫做滿二叉樹，一個叫做完全二叉樹
滿二叉樹？
一個二叉樹的所有非葉子節點都存在左右孩子，並且所有葉子節點都在同一層級上，那麼這個樹就是滿二叉樹
完全二叉樹？
只需保證最後一個節點前的節點都是齊全的就可以。
物理存儲結構
二叉樹可以用那些物理存儲結構來表示：
1.鏈表
2.數組
下標計算
假如一個父節點的下標是parent，那麼它的左孩子節點的下標就2 * parent + 1；它的右孩子節點的下標就是2 * parent + 2；
反過來，假如一個左孩子的節點的下標是leftChild，那麼它的父親節點下標是（leftChild-1）/2
二叉堆，是一種完全二叉樹，用數組來存儲
二叉樹的應用
查找操作和維持相對順序
二叉查找樹要求左子樹小於父節點，右子樹大於父節點，保證了二叉樹的有序性
二叉樹的自平衡
紅黑樹、AVL樹、樹堆
深度優先遍歷
前序遍歷，中序遍歷，後續遍歷
public class TreeDemo {
private static class TreeNode{
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data){
this.data = data;
}
}
public static TreeNode crateBinaryTree(LinkedList<Integer> inputList){
TreeNode node = null;
if(inputList == null || inputList.isEmpty()){
return null;
}
Integer data = inputList.removeFirst();
if(data != null){
node = new TreeNode(data);
node.leftChild = crateBinaryTree(inputList);
node.rightChild = crateBinaryTree(inputList);
}
return node;
}
/**
* 前序遍歷
* @param node
*/
public static void preOrderTraversal(TreeNode node){
if (node == null) {
return;
}
System.out.println(node.data);
preOrderTraversal(node.leftChild);
preOrderTraversal(node.rightChild);
}
/**
* 中序遍歷
* @param node
*/
public static void inOrderTraversal(TreeNode node){
if (node == null) {
return;
}
preOrderTraversal(node.leftChild);
System.out.println(node.data);
preOrderTraversal(node.rightChild);
}
/**
* 後序遍歷
* @param node
*/
public static void postOrderTraversal(TreeNode node){
if (node == null) {
return;
}
preOrderTraversal(node.leftChild);
preOrderTraversal(node.rightChild);
System.out.println(node.data);
}
public static void main(String[] args) {
LinkedList<Integer> inputList = new LinkedList<Integer>(
Arrays.asList(3,4,8,null,null,12,null,null,7,null,4)
);
TreeNode treeNode = crateBinaryTree(inputList);
System.out.println("前序遍歷：");
preOrderTraversal(treeNode);
System.out.println("中序遍歷：");
inOrderTraversal(treeNode);
System.out.println("後序遍歷：");
postOrderTraversal(treeNode);
}
}
廣度優先
/**
* 二叉樹層序遍歷
* @param treeNode
*/
public static void levelOrderTraversal(TreeNode treeNode){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(treeNode);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.println(node.data);
if(node.leftChild != null){
queue.offer(node.leftChild);
}
if(node.rightChild!= null){
queue.offer(node.rightChild);
}
}
}
二叉樹
1.最大堆
最大堆的任意一個父節點的值，都大於或等於它左、右孩子節點的值
2.最小堆
最大堆的任意一個父節點的值，都小於或等於它左、右孩子節點的值
