一丢烘、線性結(jié)構(gòu) {ignore}

數(shù)據(jù)結(jié)構(gòu)和算法概述

1. 什么是數(shù)據(jù)結(jié)構(gòu)陡厘？

存儲和運算是程序的兩大基礎(chǔ)功能，數(shù)據(jù)結(jié)構(gòu)是專門研究數(shù)據(jù)存儲的學(xué)科扶歪。

很多時候理肺，我們無法僅使用簡單的數(shù)字摄闸、字符串、布爾就能完整的描述數(shù)據(jù)妹萨，可能我們希望使用數(shù)組年枕、對象、或它們組合而成的復(fù)合結(jié)構(gòu)來對數(shù)據(jù)進行描述乎完。這種復(fù)合的結(jié)構(gòu)就是數(shù)據(jù)結(jié)構(gòu)熏兄。

而在實際開發(fā)中，我們會發(fā)現(xiàn)很多場景中使用的數(shù)據(jù)結(jié)構(gòu)有著相似的特征树姨，于是摩桶，數(shù)據(jù)結(jié)構(gòu)這門學(xué)科，就把這些相似的結(jié)構(gòu)單獨提取出來進行研究帽揪。

在這門學(xué)科中硝清，常見的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、鏈表转晰、樹芦拿、圖等

2. 什么是算法？

存儲和運算是程序的兩大基礎(chǔ)功能查邢，算法是專門研究運算過程的學(xué)科防嗡。

一個程序，很多時候都需要根據(jù)一種已知數(shù)據(jù)侠坎，通過計算蚁趁，得到另一個未知數(shù)據(jù)，這個運算過程使用的方法实胸，就是算法他嫡。

而在很多的場景中，它們使用的算法有一些共通的特點庐完，于是把這些共通的算法抽象出來钢属，就行了常見算法。

從一個更高的角度來對算法劃分门躯，常見的算法有：窮舉法淆党、分治法、貪心算法讶凉、動態(tài)規(guī)劃

3. 數(shù)據(jù)結(jié)構(gòu)和算法有什么關(guān)系染乌？

一個面向的是存儲，一個面向的是運算懂讯，它們共同構(gòu)成了計算機程序的兩個重要部分荷憋。

有了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，免不了對這種數(shù)據(jù)結(jié)構(gòu)的各種變化進行運算褐望，所以勒庄，很多時候串前，某種數(shù)據(jù)結(jié)構(gòu)都會自然而然的搭配不少算法。

4. 數(shù)據(jù)結(jié)構(gòu)和算法課程使用什么計算機語言实蔽？

數(shù)據(jù)結(jié)構(gòu)和算法屬于計算機基礎(chǔ)課程荡碾，它們和具體的語言無關(guān)，用任何語言都可以實現(xiàn)局装。

本課程采用JavaScript語言玩荠。

線性結(jié)構(gòu)

線性結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中的一種分類，用于表示一系列的元素形成的有序集合贼邓。

常見的線性結(jié)構(gòu)包括：數(shù)組阶冈、鏈表、棧塑径、隊列

數(shù)組

特別注意：這里所說的數(shù)組是數(shù)據(jù)結(jié)構(gòu)中的數(shù)組女坑，和JS中的數(shù)組不一樣

數(shù)組是一整塊連續(xù)的內(nèi)存空間，它由固定數(shù)量的元素組成统舀，數(shù)組具有以下基本特征：

1. 整個數(shù)組占用的內(nèi)存空間是連續(xù)的
2. 數(shù)組中元素的數(shù)量是固定的（不可增加也不可減少）匆骗，創(chuàng)建數(shù)組時就必須指定其長度
3. 每個元素占用的內(nèi)存大小是完全一樣的

2019-11-21-15-06-05.png

根據(jù)數(shù)組的基本特征，我們可以推導(dǎo)出數(shù)組具有以下特點：

1. 通過下標(biāo)尋找對應(yīng)的元素效率極高誉简，因此遍歷速度快
2. 無法添加和刪除數(shù)據(jù)碉就，雖然可以通過某種算法完成類似操作，但會增加額外的內(nèi)存開銷或時間開銷
3. 如果數(shù)組需要的空間很大闷串，可能一時無法找到足夠大的連續(xù)內(nèi)存

JS中的數(shù)組

在ES6之前瓮钥，JS沒有真正意義的數(shù)組，所謂的Array烹吵，實際上底層實現(xiàn)是鏈表碉熄。

ES6之后，出現(xiàn)真正的數(shù)組（類型化數(shù)組）肋拔，但是由于只能存儲數(shù)字锈津，因此功能有限

目前來講，JS語言只具備不完善的數(shù)組（類型化數(shù)組）

鏈表

為彌補數(shù)組的缺陷而出現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)凉蜂，它具有以下基本特征：

1. 每個元素除了存儲數(shù)據(jù)琼梆，需要有額外的內(nèi)存存儲一個引用（地址），來指向下一個元素
2. 每個元素占用的內(nèi)存空間并不要求是連續(xù)的
3. 往往使用鏈表的第一個節(jié)點（根節(jié)點）來代表整個鏈表

2019-11-21-15-19-23.png

根據(jù)鏈表的基本特征窿吩，我們可以推導(dǎo)出它具有以下特點：

1. 長度是可變的茎杂，隨時可以增加和刪除元素
2. 插入和刪除元素的效率極高
3. 由于要存儲下一個元素的地址，會增加額外的內(nèi)存開銷
4. 通過下標(biāo)查詢鏈表中的某個節(jié)點爆存，效率很低蛉顽，因此鏈表的下標(biāo)遍歷效率低

手動用代碼實現(xiàn)鏈表

實際上蝗砾，很多語言本身已經(jīng)實現(xiàn)了鏈表（如JS中的數(shù)組先较，底層就是用鏈表實現(xiàn)的）携冤，但鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，通過手寫代碼實現(xiàn)鏈表闲勺，不僅可以鍛煉程序思維和代碼轉(zhuǎn)換能力曾棕，對于后序的復(fù)雜數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)也是非常有幫助的。

因此菜循，手寫鏈表是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的一門基本功

手寫一個鏈表結(jié)構(gòu)翘地，并完成一些鏈表的相關(guān)函數(shù)，要實現(xiàn)以下功能：

1. 遍歷打印
2. 獲取鏈表的長度
3. 通過下標(biāo)獲取鏈表中的某個數(shù)據(jù)
4. 通過下標(biāo)設(shè)置鏈表中的某個數(shù)據(jù)
5. 在鏈表某一個節(jié)點之后加入一個新節(jié)點
6. 在鏈表末尾加入一個新節(jié)點
7. 刪除一個鏈表節(jié)點
8. 鏈表倒序

/**
 * 構(gòu)造函數(shù)癌幕，表示鏈表的一個節(jié)點
 */
function Node(value) {
    this.value = value; //節(jié)點的數(shù)據(jù)
    this.next = null; //下一個節(jié)點的地址
}

/**
 * 遍歷一個鏈表衙耕，打印每個節(jié)點的數(shù)據(jù)
 * @param root 鏈表的根節(jié)點
 */
function print(root) {
    // var node = root;
    // while (node) {
    //     //如果node有值，打印
    //     console.log(node.value);
    //     node = node.next;
    // }

    // 分治法
    if (root) {
        console.log(root.value); //打印自己
        print(root.next);
    }
}

/**
 * 計算鏈表的長度
 * @param {*} root 
 */
function count(root) {
    if (!root) return 0; //鏈表沒有節(jié)點
    return 1 + count(root.next); //1表示根節(jié)點占用一個數(shù)量
}

/**
 * 得到鏈表某個下標(biāo)的數(shù)據(jù)
 * @param {*} root 
 * @param {*} index 
 */
function getNode(root, index) {
    /**
     * 判斷某個節(jié)點是否是我要查找的節(jié)點
     * @param {*} node 表示某個節(jié)點
     * @param {*} i 該節(jié)點是第幾個節(jié)點
     */
    function _getValue(node, i) {
        if (!node) return null;
        if (i === index) return node;
        return _getValue(node.next, i + 1);
    }
    return _getValue(root, 0);
}

/**
 * 設(shè)置鏈表某個位置的數(shù)據(jù)
 */
function setValue(root, index, value) {
    function _setValue(node, i) {
        if (!node) return;
        if (i === index) {
            node.value = value
        }
        else {
            _setValue(node.next, i + 1);
        }
    }
    _setValue(root, 0);
}

/**
 * 在某個鏈表節(jié)點之后加入一個新節(jié)點
 * @param node 在哪個節(jié)點之后加入
 * @param newValue 新節(jié)點的數(shù)據(jù)
 */
function insertAfter(node, newValue) {
    var newNode = new Node(newValue); //構(gòu)建新節(jié)點

    node.next = newNode;
    newNode.next = node.next;
}

/**
 * 在鏈表的末尾加入新節(jié)點
 */
function push(root, newValue) {
    //判斷root是不是最后一個節(jié)點
    if (!root.next) {
        //最后一個節(jié)點
        var newNode = new Node(newValue);
        root.next = newNode;
    }
    else {
        push(root.next, newValue); //自己不是最后一個勺远，看下一個
    }
}

/**
 * 根據(jù)給定的鏈表橙喘，和 給定的要刪除的值，刪除對應(yīng)節(jié)點
 * @param {*} root 
 * @param {*} nodeValue 
 */
function removeNode(root, nodeValue) {
    if (!root || !root.next) return; //無法刪除的情況
    if (root.next.value === nodeValue) {
        //下一個節(jié)點就是要找的節(jié)點
        root.next = root.next.next;
    }
    else {
        //下一個節(jié)點還不是
        removeNode(root.next, nodeValue);
    }
}

/**
 * 給定一個鏈表胶逢，返回一個倒序后的根節(jié)點
 * @param {*} root 
 */
function reverse(root) {
    if (!root || !root.next) return root;
    if (!root.next.next) {
        var temp = root.next; //保存返回的節(jié)點
        //有兩個節(jié)點的鏈表
        root.next.next = root;
        root.next = null;
        return temp;
    }
    else {
        var temp = reverse(root.next); //后續(xù)節(jié)點倒序
        root.next.next = root;
        root.next = null;
        return temp;
    }
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");

a.next = b;
b.next = c;

// insertAfter(b, "d");

var temp = reverse(a);
print(temp);

二厅瞎、排序和查找 {ignore}

排序算法

排序算法沒有優(yōu)劣之分，在不同的場景中初坠，不同的排序算法執(zhí)行效率不同和簸。

1. 選擇排序 Selection Sort

一次選擇排序，可以將某個區(qū)間的最小值排列到該區(qū)域的第一位碟刺，具體的方式是：

1. 找出該區(qū)域的最小值
2. 將該值與該區(qū)域第一個值交換
3. 對下一個區(qū)域重復(fù)上述過程锁保，直到排序完成

2. 冒泡排序 Bubble Sort

一次冒泡排序，可以將某個區(qū)域序列的最大值排序到該區(qū)域的最后一位半沽，具體的方式是：

1. 將第1位和第2位比較身诺，如果前者比后者大則交換
2. 將第2位和第3位比較，如果前者比后者大則交換
3. 依次類推抄囚，直到比較到該區(qū)域的最后兩位
4. 重復(fù)上述過程霉赡，直到序列排序完成

3. 插入排序 Insertion Sort

將序列分為兩個部分，一部分是有序的幔托，一部分是無序的穴亏，現(xiàn)在要做的是，就是不斷的從無序的部分取出數(shù)據(jù)重挑，加入到有序的部分嗓化，直到整個排序完成

例如：序列[5, 7, 2, 3, 6]

1. 分為有序的序列和無序的序列 (5) (7 2 3 6)
2. 不斷的擴充有序序列 (5 7) (2 3 6)
3. 不斷的擴充有序序列 (2 5 7) (3 6)
4. 不斷的擴充有序序列 (2 3 5 7) (6)
5. 不斷的擴充有序序列 (2 3 5 6 7)
6. 排序完成

4. 快速排序 Quick Sort

選擇一個數(shù)（比如序列的最后一位）作為基準(zhǔn)數(shù)，將整個序列排序成兩部分谬哀，一部分比該數(shù)小刺覆，另一部分比該數(shù)大，基準(zhǔn)數(shù)在中間史煎，然后對剩余的序列做同樣的事情谦屑，直到排序完成

例如：序列[5, 7, 2, 3, 6, 4]

1. 選擇4作為基準(zhǔn)數(shù)驳糯，排序成為：(3, 2) 4 (7, 6, 5)
2. 對于3,2， 繼續(xù)使用該方式排序氢橙，得到： (2, 3) 4 (7,6,5)
3. 對于7,6,5酝枢，繼續(xù)使用該方式排序，得到： (2, 3) 4 (5,6,7)
4. 排序完成

查詢算法

1. 順序查找 Inorder Search

即普通的遍歷悍手，屬于算法的窮舉法帘睦，沒啥好解釋的

2. 二分查找 Binary Search

如果一個序列是一個排序好的序列，則使用二分查找可以極大的縮短查找時間

具體的做法是：

查找該序列中間未知的數(shù)據(jù)

1. 相等坦康，找到
2. 要找的數(shù)據(jù)較大竣付，則對后續(xù)部分的數(shù)據(jù)做同樣的步驟
3. 要找的數(shù)據(jù)較小，則對前面部分的數(shù)據(jù)做同樣的步驟

3. 插值查找 Interpolation Search

插值查找是對二分查找的進一步改進

如果序列不僅是一個排序好的序列滞欠，而且序列的步長大致相同卑笨，使用插值查找會更快的找到目標(biāo)。

插值查找基于如下假設(shè)：下標(biāo)之間的距離比和數(shù)據(jù)之間的距離比大致相同仑撞，即：

(目標(biāo)下標(biāo)-最小下標(biāo)) / (最大下標(biāo) - 最小下標(biāo)) ≈ (目標(biāo)值 - 最小值) / (最大值 - 最小值)

因此可以算出大致的下標(biāo)落點：

目標(biāo)下標(biāo) ≈ (目標(biāo)值 - 最小值) / (最大值 - 最小值) * (最大下標(biāo) - 最小下標(biāo)) + 最小下標(biāo)

這樣就可以計算出大致的下標(biāo)落點赤兴，后續(xù)的比較和二分查找一樣。

// sort.js
/**
 * 交換數(shù)組中指定的位置
 * @param {*} arr 
 * @param {*} i1 
 * @param {*} i2 
 */
function swap(arr, i1, i2) {
    var temp = arr[i1]
    arr[i1] = arr[i2];
    arr[i2] = temp;
}

/**
 * 選擇排序
 * @param {*} arr 
 */
function selectionSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        //搞定 i ~ arr.length-1 區(qū)間
        //從該區(qū)間中找出最小值隧哮，和 第 i 位交換
        var min = arr[i]; //定義一個變量桶良，為該區(qū)間的第一個數(shù)
        var index = i; //最小值所在的位置
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[j] < min) {
                min = arr[j];
                index = j; //重新記錄最小值的位置
            }
        }
        //最小值已經(jīng)找出
        //交換第i位和第index位
        swap(arr, i, index);
    }
}

/**
 * 冒泡排序
 * @param {*} arr 
 */
function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        //需要經(jīng)過arr.length-1次的冒泡
        //i:0   循環(huán)：0~arr.length-1-i
        //i:1   循環(huán)：0~arr.length-1-i
        //i:2   循環(huán): 0~arr.length-1-i
        for (var j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

/**
 * 插入排序
 * @param {*} arr 
 */
function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            //將第i位的值加入到前面有序隊列的正確位置
            var temp = arr[i];
            for (var j = i; j >= 0; j--) {
                if (j > 0 && arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                }
                else {
                    arr[j] = temp;
                    break;
                }
            }
        }
    }
}

/**
 * 快速排序
 * @param {*} arr 
 */
function quickSort(arr) {
    /**
     * 對數(shù)組的某個區(qū)域進行一次快速排序
     * @param {*} arr 
     * @param {*} start 區(qū)域的起始下標(biāo)
     * @param {*} end 區(qū)域的結(jié)束下標(biāo)
     */
    function _quickSort(arr, start, end) {
        if (start >= end || start > arr.length - 1) return;
        var low = start, high = end;
        var key = arr[end]; //基準(zhǔn)值
        while (low < high) {
            while (low < high && arr[low] <= key) low++;
            arr[high] = arr[low];
            while (low < high && arr[high] >= key) high--;
            arr[low] = arr[high];
        }
        //low === high
        arr[low] = key;
        _quickSort(arr, start, low - 1);
        _quickSort(arr, low + 1, end);
    }
    _quickSort(arr, 0, arr.length - 1);
}

var arr = [5, 3, 1, 6, 7, 4];
console.log(arr)
quickSort(arr)
console.log(arr);

//search.js
var num = 0;

/**
 * 查找一個數(shù)組中目標(biāo)值是否存在（順序查找）
 * @param {*} arr 
 * @param {*} target 
 */
function inOrderSearch(arr, target) {
    for (var i = 0; i < arr.length; i++) {
        num++;
        if (arr[i] === target) {
            return true;
        }
    }
    return false;
}

function binarySearch(arr, target) {
    if (arr.length === 0 || target < arr[0] || target > arr[arr.length - 1]) return false;

    var minIndex = 0; //最小下標(biāo)
    var maxIndex = arr.length - 1; //最大下標(biāo)
    while (minIndex <= maxIndex) {
        num++;
        var mid = Math.floor((minIndex + maxIndex) / 2);//中間下標(biāo)
        if (arr[mid] === target) {
            return true;
        }
        else if (arr[mid] > target) {
            maxIndex = mid - 1;
        }
        else {
            minIndex = mid + 1;
        }
    }
    return false;
}

function interpolationSearch(arr, target) {
    if (arr.length === 0 || target < arr[0] || target > arr[arr.length - 1]) return false;
    var minIndex = 0; //最小下標(biāo)
    var maxIndex = arr.length - 1; //最大下標(biāo)
    while (minIndex <= maxIndex) {
        num++;
        var mid = (target - arr[minIndex]) / (arr[maxIndex] - arr[minIndex]) * (maxIndex - minIndex) + minIndex;
        if (arr[mid] === target) {
            return true;
        }
        else if (arr[mid] > target) {
            maxIndex = mid - 1;
        }
        else {
            minIndex = mid + 1;
        }
    }
    return false;
}

var arr = new Array(100000);
for (var i = 0; i < arr.length; i++) {
    arr[i] = i + 1;
}

var result = interpolationSearch(arr, 100000)
console.log(result, num);

三、樹形結(jié)構(gòu) {ignore}

樹

樹是一個類似于鏈表的二維結(jié)構(gòu)沮翔，每個節(jié)點可以指向0個或多個其他節(jié)點

2019-11-22-16-21-49.png

樹具有以下特點：

1. 單根：如果一個節(jié)點A指向了另一個節(jié)點B陨帆，僅能通過A直接找到B節(jié)點，不可能通過其他節(jié)點直接找到B節(jié)點
2. 無環(huán)：節(jié)點的指向不能形成環(huán)

樹的術(shù)語：

1. 結(jié)點的度：某個節(jié)點的度 = 該節(jié)點子節(jié)點的數(shù)量
2. 樹的度：一棵樹中采蚀，最大的節(jié)點的度為該樹的度
3. 結(jié)點的層：從根開始定義起疲牵，根為第1層，根的子結(jié)點為第2層榆鼠，以此類推纲爸；
4. 樹的高度或深度：樹中結(jié)點的最大層次
5. 葉子節(jié)點：度為0的結(jié)點稱為葉結(jié)點；
6. 分支節(jié)點：非葉子節(jié)點
7. 子節(jié)點妆够、父節(jié)點：相對概念识啦，如果A節(jié)點有一個子節(jié)點B，則A是B的父節(jié)點神妹，B是A的子節(jié)點
8. 兄弟節(jié)點：如果兩個節(jié)點有同一個父節(jié)點颓哮，則它們互為兄弟節(jié)點
9. 祖先節(jié)點：某個節(jié)點的祖先節(jié)點，是從樹的根到該節(jié)點本身經(jīng)過的所有節(jié)點
10. 后代節(jié)點：如果A是B的祖先節(jié)點鸵荠，B則是A的后代節(jié)點

樹的代碼表示法：

function Node(value){
    this.value = value;
    this.children = [];
}

二叉樹

如果一顆樹的度為2冕茅，則該樹是二叉樹

二叉樹可以用下面的代碼表示

function Node(value){
    this.value = value;
    this.left = null;
    this.right = null;
}

二叉樹的相關(guān)算法

編寫各種函數(shù)，實現(xiàn)下面的功能

1. 對二叉樹遍歷打印
   1. 前(先)序遍歷 DLR
   2. 中序遍歷 LDR
   3. 后序遍歷 LRD
2. 根據(jù)前序遍歷和中序遍歷結(jié)果，得到一顆二叉樹
3. 計算樹的深度
4. 查詢二叉樹
   1. 深度優(yōu)先 Depth First Search
   2. 廣度優(yōu)先 Breadth First Search
5. 比較兩棵二叉樹姨伤，得到比較的結(jié)果

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

/**
 * 前序遍歷
 * @param {*} root 
 */
function DLR(root) {
    if (!root) return;// 沒有節(jié)點
    console.log(root.value);
    DLR(root.left);
    DLR(root.right);
}

/**
 * 中序遍歷
 * @param {*} root 
 */
function LDR(root) {
    if (!root) return;// 沒有節(jié)點
    LDR(root.left);
    console.log(root.value);
    LDR(root.right);
}

/**
 * 后序遍歷
 * @param {*} root 
 */
function LRD(root) {
    if (!root) return;// 沒有節(jié)點
    LRD(root.left);
    LRD(root.right);
    console.log(root.value);
}

/**
 * 根據(jù)前序遍歷哨坪，和 中序遍歷，得到一棵樹的根節(jié)點
 * @param {*} dlr 
 * @param {*} ldr 
 */
function getTree(dlr, ldr) {
    dlr = dlr.split("");
    ldr = ldr.split("");
    if (dlr.length !== ldr.length) throw new Error("無效的遍歷值");
    if (dlr.length === 0) return null;

    var rootValue = dlr[0]; //取出根節(jié)點的值 
    var root = new Node(rootValue);

    var index = ldr.indexOf(rootValue); //找到根節(jié)點的值在中序遍歷中的位置
    var leftLDR = ldr.slice(0, index).join(""); //左邊的中序遍歷結(jié)果
    var leftDLR = dlr.slice(1, leftLDR.length + 1).join(""); //左邊的前序遍歷結(jié)果
    root.left = getTree(leftDLR, leftLDR);

    var rightLDR = ldr.slice(index + 1).join(""); //右邊的中序遍歷結(jié)果
    var rightDLR = dlr.slice(leftLDR.length + 1).join(""); //右邊的前序遍歷結(jié)果
    root.right = getTree(rightDLR, rightLDR);

    return root;
}

/**
 * 得到一棵樹的深度
 * @param {*} root 
 */
function getDeep(root) {
    if (!root) return 0;
    var left = getDeep(root.left);
    var right = getDeep(root.right);
    return Math.max(left, right) + 1;
}

var root = getTree("abcde", "cbdae")
console.log(root)
console.log(getDeep(root));

// var a = new Node("a");
// var b = new Node("b");
// var c = new Node("c");
// var d = new Node("d");
// var e = new Node("e");
// var f = new Node("f");

// a.left = b;
// a.right = e;

// b.left = c;
// b.right = d;

// e.left = f;

// LRD(a);

四姜挺、圖結(jié)構(gòu) {ignore}

概念

2019-11-24-14-17-49.png

圖結(jié)構(gòu)中齿税，一個結(jié)點可以鏈接到任意結(jié)點彼硫，所有結(jié)點鏈接而成的結(jié)構(gòu)炊豪，即為圖結(jié)構(gòu)

圖結(jié)構(gòu)中的鏈接可以是有向的，也可以是無向的（雙向鏈接）拧篮，本文僅討論雙向鏈接

樹結(jié)構(gòu)是一種特殊的圖結(jié)構(gòu)

圖結(jié)構(gòu)沒有根词渤，可以有環(huán)奕锌，但是在一個圖結(jié)構(gòu)中腺阳，不能存在兩個或以上的孤立結(jié)點

可以使用圖中任何一個結(jié)點表示整個圖結(jié)構(gòu)

圖結(jié)構(gòu)是一種常見的數(shù)據(jù)結(jié)構(gòu)肉拓，例如網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁就是一種典型的圖結(jié)構(gòu)

圖結(jié)構(gòu)的代碼可表示為：

function Node(value){
    this.value = value;
    this.neighbors = [];
}

相關(guān)算法

1. 查詢算法

和樹結(jié)構(gòu)一樣坪郭，圖結(jié)構(gòu)的查詢也可以分為深度優(yōu)先（Depth First Search）和廣度優(yōu)先(Breadth First Search)查詢

2. 最小生成樹算法

如果一個圖中結(jié)點連接而成的邊具備某種數(shù)值峡懈，需要將這些邊進行精簡疏日，生成一個連接全節(jié)點同時總邊長最小的樹結(jié)構(gòu)彼哼，該樹稱之為最小生成樹

實現(xiàn)最小生成樹可以使用Prim算法坎穿，從任意一個點出發(fā)顷牌，連接到該點最短的點剪芍，組成一個部落，然后繼續(xù)連接到該部落最短的點窟蓝，直到把所有點連接完成

function Node(value) {
    this.value = value;
    this.neighbors = [];
}

/**
 * 深度優(yōu)先遍歷
 * @param {*} node 
 * @param {*} targetValue 
 * @param finded 已經(jīng)找過的結(jié)點
 */
function deepFirstSearch(node, targetValue, finded) {
    //如果finded數(shù)組中包含了node罪裹，說明，當(dāng)前結(jié)點已經(jīng)被看過了运挫，直接返回
    if (finded.includes(node)) return false;
    if (node.value === targetValue) return true;
    finded.push(node); //將當(dāng)前結(jié)點加入到已找過的結(jié)點
    //自己不是要找到状共，看相鄰結(jié)點
    for (var i = 0; i < node.neighbors.length; i++) {
        if (deepFirstSearch(node.neighbors[i], targetValue, finded)) {
            //在其中一個相鄰結(jié)點的深搜過程中找到了
            return true;
        }
    }
    return false; //所有相鄰的結(jié)點的深搜過程中都找不到
}

/**
 * 圖的廣搜
 * @param {*} nodes 要找的某一群結(jié)點，該數(shù)組中的結(jié)點都是沒有找過的
 * @param {*} targetValue 
 * @param finded 已經(jīng)找過的結(jié)點
 */
function breadthFirstSearch(nodes, targetValue, finded) {
    if (nodes.length === 0) return false;
    var nexts = [];
    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].value === targetValue) {
            return true;
        }
        //說明該結(jié)點已找過
        finded.push(nodes[i]);
        //直接將該結(jié)點的相鄰結(jié)點加入到數(shù)組nexts
        for (var j = 0; j < nodes[i].neighbors.length; j++) {
            var n = nodes[i].neighbors[j]; //第j個鄰居
            if (!nexts.includes(n)) {
                nexts.push(n);
            }
        }
    }
    //重新對nexts進行處理
    for (var i = 0; i < nexts.length; i++) {
        if (finded.includes(nexts[i])) {
            nexts.splice(i, 1);
            i--;
        }
    }
   
    console.log(nexts);
    return breadthFirstSearch(nexts, targetValue, finded);
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");

a.neighbors.push(b, c, e);
b.neighbors.push(a, c, d);
c.neighbors.push(a, b);
e.neighbors.push(a, e);
d.neighbors.push(b, e);

var result = breadthFirstSearch([c], "e", []);
console.log(result);

/**
 * 使用Prim算法根據(jù)點的集合谁帕，和邊的集合峡继，鏈接結(jié)點
 * @param {*} nodes 
 * @param {*} sides 
 */
function Prim(nodes, sides) {
    //先做一個驗證
    if (nodes.length !== sides.length || nodes.length <= 1) return;

    var horde = [nodes[0]]; //已連接的點形成的部落

    while (horde.length < nodes.length) {
        //添加一個點到部落horde
        //找到一個到這個部落最短的點
        var result = { //求的最短的點
            dis: Infinity, //距離默認(rèn)無窮大
            to: null, //連接到部落的哪個點，部落的點
            from: null //從哪個點連接到部落,新的點
        }
        for (var i = 0; i < nodes.length; i++) {
            var node = nodes[i]; //一個點一個點拿出來比較
            if (horde.includes(node)) {
                //部落中已經(jīng)有這個點了
                continue; //進行下一次循環(huán)
            }
            //這個點沒有在部落中
            var info = getMinDistance(node); //得到該點到部落的距離信息
            if (info.dis < result.dis) {
                result.dis = info.dis;
                result.to = info.connect;
                result.from = node;
            }
        }
        //將點和部落中對應(yīng)的點進行連接
        result.to.neighbors.push(result.from);
        result.from.neighbors.push(result.to);
        //將該點加入到部落中
        horde.push(result.from);
    }

    /**
     * 查找指定的結(jié)點到當(dāng)前部落最短的距離和要連接的點
     * @param {*} node 
     */
    function getMinDistance(node) {
        var result = { //求的結(jié)果
            dis: Infinity, //距離默認(rèn)無窮大
            connect: null //連接到部落的哪個點
        }
        for (var i = 0; i < horde.length; i++) {
            var target = horde[i]; //部落中的某個結(jié)點
            var dis = getDistance(node, target);
            if (dis < result.dis) {
                result.dis = dis;
                result.connect = target;
            }
        }
        return result;
    }

    /**
     * 得到兩個點的距離
     * @param {*} node1 
     * @param {*} node2 
     */
    function getDistance(node1, node2) {
        var i1 = nodes.indexOf(node1); //第一個點的下標(biāo)
        var i2 = nodes.indexOf(node2);//第二個點的下標(biāo)
        return sides[i1][i2];
    }
}


//點的集合
var nodes = [a, b, c, d, e];
//邊的集合
var sides = [
    [0, 8, 3, Infinity, 4],//a點到其他結(jié)點的距離
    [8, 0, 4, 10, Infinity], //b到其他點的距離
    [3, 4, 0, 3, Infinity], //c到其他點的距離
    [Infinity, 10, 3, 0, 6], //d到其他點的距離
    [4, Infinity, Infinity, 6, 0], //e到其他點的距離
];

Prim(nodes, sides);
console.log(a)

五匈挖、貪心算法和動態(tài)規(guī)劃 {ignore}

貪心算法

當(dāng)遇到一個求解全局最優(yōu)解問題時鬓椭，如果可以將全局問題切分為小的局部問題，并尋求局部最優(yōu)解关划，同時可以證明局部最優(yōu)解累計的結(jié)果就是全局最優(yōu)解小染，則可以使用貪心算法

面試題：找零問題

示例：假設(shè)你有一間小店，需要找給客戶46分錢的硬幣贮折，你的貨柜里只有面額為25分裤翩、10分、5分、1分的硬幣踊赠，如何找零才能保證數(shù)額正確并且硬幣數(shù)最小

動態(tài)規(guī)劃

分治法有一個問題呵扛，就是容易重復(fù)計算已經(jīng)計算過的值，使用動態(tài)規(guī)劃筐带，可以講每一次分治時算出的值記錄下來今穿，防止重復(fù)計算，從而提高效率伦籍。

面試題1：青蛙跳臺階問題

有N級臺階蓝晒，一只青蛙每次可以跳1級或兩級，一共有多少種跳法可以跳完臺階帖鸦？

面試題2：最長公共子序列問題（LCS）

有的時候芝薇，我們需要比較兩個字符串的相似程度，通常就是比較兩個字符串有多少相同的公共子序列

例如有兩個字符串

• 鄧哥特有的貴族氣質(zhì)吸引了很多女孩
• 鄧哥喜歡吃秋葵和香菜作儿，但是他的女朋友們不喜歡

以上兩個字符串的最長公共子序列為：鄧哥的女

/**
 * 貪心算法：找零問題
 * @param {*} total 找零總數(shù)
 * @param {*} deno 面額
 */
function exchange(total, deno) {
    var result = []; //找零結(jié)果
    while (total > 0) {
        //還要找
        var max = -1; //最大可用面額
        for (var i = 0; i < deno.length; i++) {
            var d = deno[i]; //當(dāng)前面額
            if (d > max && d <= total) {
                max = d;
            }
        }
        result.push(max); //找錢結(jié)果
        total -= max;
    }
    return result;
}

var result = exchange(41, [25, 20, 10, 5, 1]) 
console.log(result);

-------------------------------------------------------
function jumpTemp(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    return jumpTemp(n - 1) + jumpTemp(n - 2);
}

/**
 * 青蛙跳n級臺階一共有多少種跳法
 * @param {*} n 
 */
function jump(n) {
    var table = []; //用一個數(shù)組記錄已經(jīng)跳過的臺階結(jié)果

    function _jump(n) {
        if (table[n]) return table[n]; //已經(jīng)算過了洛二，不用再算了
        //沒有算過
        var newRecord; //用于記錄這一次運算的結(jié)果
        if (n === 1) newRecord = 1;
        else if (n === 2) newRecord = 2;
        else {
            newRecord = _jump(n - 1) + _jump(n - 2);
        }
        table[n] = newRecord;
        return newRecord;
    }

    var result = _jump(n);
    console.log(table);
    return result;
}

/**
 * 
 * @param {*} str1 
 * @param {*} str2 
 */
function LCS(str1, str2) {
    var table = [];

    function _LCS(str1, str2) {
        //判斷目前的輸入值是否有對應(yīng)的計算結(jié)果（是不是已經(jīng)存過了）
        for (var i = 0; i < table.length; i++) {
            if (table[i].str1 === str1 && table[i].str2 === str2) {
                return table[i].result;
            }
        }
        //沒有存儲結(jié)果
        var newResult; //用于計算最終計算的結(jié)果
        if (!str1 || !str2) newResult = "";// 其中有一個字符串沒東西
        else if (str1[0] === str2[0]) {
            //開頭相同
            newResult = str1[0] + _LCS(str1.substr(1), str2.substr(1));
        }
        else {
            var s1 = _LCS(str1, str2.substr(1));
            var s2 = _LCS(str1.substr(1), str2);
            if (s1.length < s2.length) {
                newResult = s2;
            }
            else {
                newResult = s1;
            }
        }
        table.push({
            str1: str1,
            str2: str2,
            result: newResult
        })
        return newResult;
    }

    var result = _LCS(str1, str2);
    console.log(table)
    return result;

}

var result = LCS("鄧哥特有的貴族氣質(zhì)吸引了很多女孩", "鄧哥喜歡吃秋葵和香菜，但是他的女朋友們不喜歡");
console.log(result);

----------------------------------思考題-------------------------------------
/**
 * 
 * @param {*} total 找零總數(shù) 41
 * @param {*} denos 數(shù)組攻锰，記錄面額 [25, 20, 5, 1]
 * @returns 數(shù)組晾嘶，得到最優(yōu)解 例如：[20, 20, 1]，如果無解娶吞，返回false
 */
function 找零問題(total, denos) {
    // 如果 denos數(shù)組長度為0垒迂，無解
    // 把denos第一個面額拿出來，看看該面額是否和total相等寝志，如果相等娇斑，直接放到最優(yōu)解中
    // 第一個面額比total大，這個面額不能找零材部，重新看剩下面額（分治）
    // 第一個面額比total小毫缆，兩種情況
    // 1. 如果我找了這個面額的最優(yōu)解
    // 2. 我沒有找這個面額的最優(yōu)解
    // 根據(jù)上面兩種情況看哪種情況最優(yōu)，取最優(yōu)的
}