Unity第三方插件

本章节主要讲解学习Unity第三方工具插件(比如NGUI，Dotween，2DToolkit……)。

NGUI

NGUI是C#写的第三方插件，堪称Unity 4.6之前最完美的GUI解决方案(NGUI 2.7及之前貌似是免费)，复杂的UI都能在一个Draw Call完成渲染。
出于学习目的下载NGUI 2.7试试：
NGUI 2.7 Download
一下学习都是基于NGUI 2.7版本学习的，新的版本特性这里没有涉及到。

Tutorials

以下学习参考

Creating Your UI

这里就不再一一讲述步骤了，主要记录一些重要的概念。
先来看看我们创建出UI之后的UI层次结构：

看看各组成部分的作用：

1. UI Root
   上面挂载UIRoot Script，这个脚本的主要目的是把所有挂载在UI Root下的object 所在屏幕比例根据屏幕大小变化而变化
   When attached to the root object of the UI, it will scale that object by the inverse of the screen’s height, thus maintaining a 1 pixel = 1 unit ratio, ensuring pixel-perfect UIs.
   UIStretch – This script is capable of stretching the widget relative to the size of the screen (or, if specified — panel or widget size).
   UIStretch是自适应的关键，根据屏幕或特定panel长宽变化去做适应。但后来的NGUI版本好像对自适应这一块做了很大修改，UIStretch貌似不再支持。
2. Camera
   上面挂载了UICamera Script，这个脚本的主要目的是”contains NGUI’s event system”，至于消息是如何传递的这里先暂时不管，以后会深入学习。
3. Anchor
   上面挂载了UIAnchor Script，这个脚本的主要目的是”apply a half-pixel offset on Windows machines, for pixel-perfect results.”(把UI限定在窗口特定位置，当窗口变化的时候会依然处于相对窗口的位置)
4. Panel
   上面挂载了UIPanel，这个脚本的主要目的是”container that will collect all UI widgets under it and will combine them into as few draw calls as possible.”(这里相当于UI的管理容器，负责以最少的draw call去管理UI)

Sprite

创建了UI，那么接下来就是增加我们的UI组件。
通过Widget Tool可以创建一系列不同类型的组件，这里有两个概念比较重要。
Atlas(图集) – Atlas好比我们的图片库，因为组件会需要选择图案，而Atlas定义了切割好的图集可供选择
Font(字体库) – 正如其名，字体库，至于字体库是怎么制作的这里暂时不得而知(待学习)
让我们简单看一下创建一个Sprite后的显示面板：

这里Sprite有深度的概念，通过调节Depth我们可以实现层次排序。
还值得注意的一点是Sprite有个属性Sprite Type，这里的Sprite Type不仅可以决定Sprite如何显示，还会影响Sprite如何去适应显示区域。

9-Sliced Sprite

Sliced技术会决定如何去拉伸图案去适应显示区域而不至于看起来变形。
9-Sliced详解

Tiled Sprite

Tiled Sprite是用原始sprite大小去铺满显示区域

Note:
这里有一个官网说是显示Debug Info的东西，通过把Panel的Debug Info设置成Geometry，场景里会增加一个叫_UIDrawCall的对象。

(这里还不太明白是什么，但看起来是把UI更新整合到一个Draw Call里了)

Label

Lable里的字来源于我们之前选的字库。
在Label里填写文本有个比较方便的设定，可以通过[hex color]改变后续文本的颜色e.g. [FF0000]代表红色。

1
2

[FF0000]NGUI's [FFFFFF]lables can have [00FF00]embedded 
[0000FF]colors.

Button

当我们添加了Button后，如何响应事件了？
“anything with a collider on it will receive all of the events.”

还记得之前说UICamera负责发送所有事件吗？所有在Camera(绑定了UICamera)下的UI都会接受到Event(前提是设置了event发送到UI层)。
让我们来看下UICamera的一些public可控变量：

让我们关注一些比较重要的点：
Event Receive Mask – 控制了接受events的layer层
Debug – debug模式下可以让我们看到哪一个game objec
t接收到了event
Range Distance – 控制raycast的有效范围
Scroll Axis Name – 设定横向控制来源
Vertical Axis Name – 设定纵向控制来源
……

接下来让我们看看UICamera都负责发送哪些事件？(具体可以参见UICamera源码)
OnHover (isOver) is sent when the mouse hovers over a collider or moves away.
OnPress (isDown) is sent when a mouse button gets pressed on the collider.
OnSelect (selected) is sent when a mouse button is first pressed on a game object. Repeated presses on the same object won’t result in a new OnSelect.
OnClick () is sent with the same conditions as OnSelect, with the added check to see if the mouse has not moved much. UICamera.currentTouchID tells you which button was clicked.
OnDoubleClick () is sent when the click happens twice within a fourth of a second. UICamera.currentTouchID tells you which button was clicked.
OnDragStart () is sent to a game object under the touch just before the OnDrag() notifications begin.
OnDrag (delta) is sent to an object that’s being dragged.
OnDragOver (draggedObject) is sent to a game object when another object is dragged over its area.
OnDragOut (draggedObject) is sent to a game object when another object is dragged out of its area.
OnDragEnd () is sent to a dragged object when the drag event finishes.
OnInput (text) is sent when typing (after selecting a collider by clicking on it).
OnTooltip (show) is sent when the mouse hovers over a collider for some time without moving.
OnScroll (float delta) is sent out when the mouse scroll wheel is moved.
OnKey (KeyCode key) is sent when keyboard or controller input is used.

那么知道了发送哪些事件，那么我们如何通过添加的控件去响应事件了？

1. 控件要处于Camera(含UICamera脚本)之下
2. Layer处于UICamera的Event Receiver Mask
3. 接受事件的控件必须包含Collider
4. 自定义响应方法
   1. 定义对应事件响应的方法并挂载到需要响应的Game Object上

1
2
3
4
5
6
7
8
9
10
11

void OnPress(bool isPressed)
{
    if(isPressed)
    {
        Debug.Log("Exit button is pressed!");
    }
    else
    {
        Debug.Log("Exit button is unpressed!");
    }
}

2. 通过UIListener，直接添加delegate去监听事件

首先现在需要实现delegate监听事件的控件上添加一个UIListener脚本(Component -> NGUI -> Internal -> Event Listener)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// UIListener Soure Code
//----------------------------------------------
//            NGUI: Next-Gen UI kit
// Copyright © 2011-2013 Tasharen Entertainment
//----------------------------------------------

using UnityEngine;

/// <summary>
/// Event Hook class lets you easily add remote event listener functions to an object.
/// Example usage: UIEventListener.Get(gameObject).onClick += MyClickFunction;
/// </summary>

[AddComponentMenu("NGUI/Internal/Event Listener")]
public class UIEventListener : MonoBehaviour
{
    public delegate void VoidDelegate (GameObject go);
    public delegate void BoolDelegate (GameObject go, bool state);
    public delegate void FloatDelegate (GameObject go, float delta);
    public delegate void VectorDelegate (GameObject go, Vector2 delta);
    public delegate void StringDelegate (GameObject go, string text);
    public delegate void ObjectDelegate (GameObject go, GameObject draggedObject);
    public delegate void KeyCodeDelegate (GameObject go, KeyCode key);

    public object parameter;

    public VoidDelegate onSubmit;
    public VoidDelegate onClick;
    public VoidDelegate onDoubleClick;
    public BoolDelegate onHover;
    public BoolDelegate onPress;
    public BoolDelegate onSelect;
    public FloatDelegate onScroll;
    public VectorDelegate onDrag;
    public ObjectDelegate onDrop;
    public StringDelegate onInput;
    public KeyCodeDelegate onKey;

    void OnSubmit ()                { if (onSubmit != null) onSubmit(gameObject); }
    void OnClick ()                 { if (onClick != null) onClick(gameObject); }
    void OnDoubleClick ()           { if (onDoubleClick != null) onDoubleClick(gameObject); }
    void OnHover (bool isOver)      { if (onHover != null) onHover(gameObject, isOver); }
    void OnPress (bool isPressed)   { if (onPress != null) onPress(gameObject, isPressed); }
    void OnSelect (bool selected)   { if (onSelect != null) onSelect(gameObject, selected); }
    void OnScroll (float delta)     { if (onScroll != null) onScroll(gameObject, delta); }
    void OnDrag (Vector2 delta)     { if (onDrag != null) onDrag(gameObject, delta); }
    void OnDrop (GameObject go)     { if (onDrop != null) onDrop(gameObject, go); }
    void OnInput (string text)      { if (onInput != null) onInput(gameObject, text); }
    void OnKey (KeyCode key)        { if (onKey != null) onKey(gameObject, key); }

    /// <summary>
    /// Get or add an event listener to the specified game object.
    /// </summary>

    static public UIEventListener Get (GameObject go)
    {
        UIEventListener listener = go.GetComponent<UIEventListener>();
        if (listener == null) listener = go.AddComponent<UIEventListener>();
        return listener;
    }
}

可以看出通过UIListener，该控件已经具备了响应UI Event的能力，而且每一个UI Event都定义了对应的delegate，这样一来我们就可以通过动态的添加修改每一个UI event的delegate实现控制UI Event响应了。
那么接下来我们只需在任何一个Game Object挂载下列代码就能响应特定控件的特定UI事件了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

using UnityEngine;
using System.Collections;

public class RemoveExitButtonListener : MonoBehaviour {

    // Use this for initialization
    void Start () {
        GameObject exitbutton = GameObject.Find("UI Root (2D)/Camera/Anchor/Panel/Exit");
        // 这里的回调方法要和delegate签名一致
        UIEventListener.Get(exitbutton).onPress = RemoteExitButtonClick;
    }
    
    // Update is called once per frame
    void Update () {
    
    }

    void RemoteExitButtonClick(GameObject go, bool state)
    {
        if (state)
        {
            Debug.Log("RemoteExitButtonClick button is pressed!");
        }
        else
        {
            Debug.Log("RemoteExitButtonClick button is unpressed!");
        }
    }
}

同时NGUI还为Button控制添加了很多可自定义的脚本：

1. UIButton – 自定义控件被点击或处于控件之上等颜色信息
2. UIButtonScale – 自定义焦点处于控件之上时的scale变换
3. UIButtonOffset – 自定义控件被点击后的位移
4. UIButtonSound – 自定义控件被点击时播放的声音
5. UIButtonMessage – 自定义控件触发事件
6. UIButtonTween – 自定义控件触发tween
7. UIButtonPlayAnimation – 自定义控件触发动画

Slider

通过传递接受Slider Event的Game Object，我们可以去对应物体上定义OnSliderChange(float stepvalue)去响应slider事件，这样一来响应了Slider Event的物体就可以根据Slider的拖拽去做对应的事情了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

using UnityEngine;
using System.Collections;

public class DisplayTextListener : MonoBehaviour {

    private Vector3 m_OriginalPosition;

    // Use this for initialization
    void Start () {
        // 这里获取的postion不是世界坐标系的，不知道为什么
        m_OriginalPosition = transform.position;
    }

    // Update is called once per frame
    void Update () {
    
    }

    void OnSliderChange(float stepvalue)
    {
        Vector3 temp = m_OriginalPosition;
        temp.y *= stepvalue;
        transform.position = temp;
    }
}

Checkbox

通过把一组Checkbox放到同一个Game Object，然后设定所有UICheckbox的Radio Button Root到同一个Game Object可以实现一组单选按钮。
然后通过添加UICheckboxControlledComponent到Checkbox上，我们可以指定当该Checkbox激活或未激活时去enable的Game Object(做到根据Checkbox状态响应)。

Input

Label要具有而输入的特性需要确保以下几点：

1. 父节点或自身包含Box Collider
2. 父节点或自身包含UIInput Script(所有的Input相关的东西都抽象到这里了e.g. IME，键盘弹出，平台相关输入等)
3. 指定需要增加Input功能的Laybel到UIInput的Laybel属性
   Note：
   两者必须都在同一个Game Object上才能起作用，因为UIInput要通过Box Collider去接收OnSelect等事件。

NGUI为我们提供了方便的控件类，Input – 直接用于创建可接收输入的Laybel模板

3D

将2D UI变换到3D UI很容易。
步骤如下：

1. 去掉Anchor，直接把panel挂载在UIRoot(2D)上
   还记得最初创建NGUI UI的时候Anchor上面挂载的UIAnchor Script的作用吗？因为变换到3D后我们不需要在控制相对窗口的位置，所以不需要UIAnchor了。
2. 设置Camera的投影方式到Perspective(为了3D显示)
   就这么简单，通过这样设置后，UI就完全当做3D Game Object显示在scene里了。
   

Atlas Maker

声明：后续用到的UI素材来源于COC，仅用于学习目的。
首先要知道为什么要使用图集？
减少纹理的使用，比如当多个材质只是纹理不同的时候，我们可以合并纹理到一个大的纹理，给材质指定对应的UV坐标即可。另外合并多个小的纹理到大的纹理图集也可以减少Memory使用。详情见Texture atlas。
这一节讲一下图集的制作。

1. 准备好所有图片素材(可以通过PS等工具制作)
2. 打开NGUI Atlas Maker
   NGUI -> Open the Altas Maker
3. 设置一个Atlas名字，点击Create，选中要放到一张图集里的所有纹理图片，然后等Altas Maker切割完成后点击Add/Update All
   
   
   Note:
   NGUI也支持导入Texture Packer导出的文件
   NGUI Atlas Maker支持多种图片格式(e.g. PNG, psd……)
   一旦Sprite导入并生成UI Atlas后，我们可以直接在Atlas Maker里添加并更新该Atlas即可。

Font Maker

Font Maker里的字体是由什么制作而来的了？
“All fonts are created using the free BMFont program, or the more advanced Glyph Designer.”(NGUI使用的Font是由BMFont program或Glyph Designer制作的)

那么BMFont program又是什么了？
This program will allow you to generate bitmap fonts from TrueType fonts. The application generates both image files and character descriptions that can be read by a game for easy rendering of fonts.BMFont program通过TrueType fonts生成bitmap fonts(一个是Font的image file文件，一个是描述了每一个字符渲染所需的信息文件))

那么这里提到了两个概念：

1. TrueType Font
   TrueType is an outline font
   Outline fonts (also called vector fonts) use Bézier curves, drawing instructions and mathematical formulae to describe each glyph, which make the character outlines scalable to any size.
   可以看出TrueType是outline font，outline font是一种vector font(可以理解成矢量字体，放大缩小不会出现锯齿和模糊。之所以称作vector font是因为TrueType记录每一个字符的轮廓信息，通过这些信息可以计算出如何绘制字符)
   以下引用至What are TrueType fonts?
   TrueType technology actually involves two parts:
   The TrueType Rasterizer
   TrueType fonts – “The fonts themselves contain data that describes the outline of each character in the typeface. “

2. Bitmap Font
   Bitmap fonts consist of a matrix of dots or pixels representing the image of each glyph in each face and size.
   可以看出Bitmap Font是记录的每一个字符的像素和位置等信息。
   以下引用至What is a Bitmap Font?
   A bitmap font is essentially an image file containing a bunch of characters and a control file detailing the size and location of each character within the image. Each character is represented by a number of dots or pixels, rendered in a particular font and size.
   可以看出Bitmap Font包含两部分：

3. Image file – 包含了所有文字的纹理图片

4. Control file – 包含了字体大小，每一个字符所在位置等信息
   Bitmap Font因为不是outline font(vector font)，所以在字体拉伸变换的时候会出现失真的情况。
   既然这样我们为什么还要使用Bitmap Font了？
   OpenGL itself doesn’t even understand fonts(e.g. vector font), so in order to display text in your game you would need to use whats known as a bitmap font.
   当计算去利用vector font渲染字体的时候，不会失真。但是在游戏里，如果我们还想对vector font做进一步的处理就显得心有余而力不足了。
   The major benefit of using bitmap fonts is that each character can be pre-rendered using multiple effects, loaded into OpenGL as a texture, and rendered to the screen using very little resources.
   但Bitmap Font不一样，Bitmap Font存储的就是字体的纹理图片，纹理图片在OpenGL里做额外的效果处理就容易的多了。

说了这么多让我们看看BMFon program是如何制作Bitmap Font的？

1. 下载BitMap Font Program
   Bitmap Font Program Download Link
2. 通过Font Settings我可以选择我们要导入的ttf字库，是否采用unicode编码等。
3. 然后选中我们要导出的字符集(这里主要选择了英文和中文字符集)
   
4. 设置export option，为导出的文件设置相关配置
   
   Note：
   If you’re importing colored icons, or planning on using post processing to add colors to the characters, then you’ll want to choose the 32bit format, otherwise the 8bit format may be sufficient.
   官网提到如果要后期再对字符做颜色等处理，需要选择32bit的存储模式(应该是为了能存储颜色信息)
   同时File Format会决定我们导出的字符集纹理图片和Font descriptor的格式。
   为了将字符都导出到一张纹理图片我们需要定义合适的Texture Size。
5. 最后点击存储为Bitmap导出字符集(Option -> Save Bitmap Font As)
   这里就会生成对应的字符集纹理图片和Font Descriptor文件。
   
   Note:
   但我发现由于包含了大量中文字符，字符纹理比较大，包括中文和英文就有10M了，如果文字比较多比如做本地化，静态字体(我们这里提前生成字符集纹理就是静态字体)不适合。

NGUI支持动态字体的生成：
让我们先看看什么是动态字体？
“When you set the Characters drop-down in the Import Settings to Dynamic, Unity will not pre-generate a texture with all font characters. Instead, it will use the FreeType font rendering engine to create the texture on the fly.”(https://docs.unity3d.com/Manual/class-Font.html)
可以看出动态字体不需提前生成字符集纹理，而是通过导入的ttf动态的在游戏里生成对应字体纹理。这样做的好处就是减少了像静态字体这样的纹理内存开销，我们只需指定使用哪些ttf并确保用户包含了该ttf就能正确显示所有语言。
个人认为动态字体是本地化的一个解决方案。
动态字体直接从ttf文件生成。

Note:
值得注意的是动态字体下写的那个警告”Please note that dynamic fonts can’t be made a part of an atlas, and they will always be draw in a speparate draw call. You will need to adjust transform position’s Z rather than depth.”
使用动态字体后会增加一个draw call，而且动态字体的深度不再是有depth来控制而是z值。

Bitmap Font制作好了，那么接下来我就应该用制作好的Bitmap Font去通过Font Maker制作我们的字符集(Atlas)了。

1. 打开Font Maker
2. 选定我们刚才制作的Font Texture和Font Descriptor作为输入，指定生成的字符集名字
3. 点击创建
   

这里看一下用自己制作的字体集和UI图片集做的登陆界面：

NGUI 2.7屏幕自适应

下文主要参考：
NGUI所见即所得之UIRoot
Unity3d + NGUI 的多分辨率适配
Unity3D开发（一）：NGUI之UIRoot屏幕分辨率自适应
NGUI研究院之自适应屏幕（十）
Unity3d + NGUI 的多分辨率适配
屏幕自适应是UI在所难免会遇到的问题。
那么为什么需要做屏幕自适应了？
美术在做UI的时候，程序需要确定我们资源的最基本的分辨率，比如我们是基于1024 * 768（1.3333比例）。
在屏幕分辨率为1024 * 768(1.333比例)的时候完美显示如下：

当我们把屏幕分辨率设置成800 * 800(1.0比例)的时候显示如下：

当我们把屏幕分辨率设置成960 * 640(1.5比例)的时候显示如下：

Note:
UIRoot的Manual Height设置为768，Scaling Stype为FixedSize(后续会讲到UIRoot的缩放自适应原理)
从上面可以看出当分辨率比例降低的时候，会出现图像显示不全，这是因为NGUI是基于高度去缩放的。(后续会详细讲解)
所以当比例从1.33变到1.0的时候，768/800=0.96的缩放比例，宽度应该是1024/0.96=1066.66大于800这也就是为什么会出现图像显示不全的原因了。
再来看看从1.33变到1.5的时候，同理768/640=1.2缩放比例，宽度应该是1024/1.2=853.33小于960这也就是为什么会出现宽度铺不满的情况。
所以在这个时候为了不去做多套不同分辨率的资源去适应各种分辨率的机型，我们需要使用NGUII里的自适应。
当下移动设备的主流分辨率，数据来源腾讯分析移动设备屏幕分辨率分析报告：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

iOS设备的分辨率主要有：
宽　  高   宽高比
960     640     1.5
1136    640     1.775
1024    768     1.3333
2048    1536    1.3333
 
Android设备的分辨率则相对纷杂，主流的分辨率有：
宽   高   宽高比
800     480     1.6667
854     480     1.7792
1280    720     1.7778
960     540     1.7778
1280    800     1.6
960     640     1.5
1184    720     1.6444
1920    1080    1.7778

那么让我们进入正题，NGUI是如何实现屏幕自适应的了？
这里有三个最重要的脚本需要学习：

1. UIRoot
2. UIStretch
3. Anchor
   让我们先来看看UIRoot的界面：
   
   还记得之前提到UIRoot的功能吗？
   This script rescales the object it’s on to be 2/ScreenHeight in size, letting you specify widget coordinates in pixels and still have them be relatively small when compared to the rest of your game world.
   可以看出UIRoot通过scale UIRoot到2/ScreenHeight比例后，使得所有控件的坐标与像素一一对应。那么为什么这样能实现控件坐标与像素一一对应了？这个问题后面会讲到。
   让我们先分别看看具体参数的含义:
   Scaling Style

1
2
3
4
5
6

public enum Scaling
{
    PixelPerfect,
    FixedSize,
    FixedSizeOnMobiles,
}

而已看出NGUI 2.7给我们提供了3种scale方式。
那么三种方式是如何起作用的了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public int activeHeight
{
    get
    {
        int height = Mathf.Max(2, Screen.height);
        if (scalingStyle == Scaling.FixedSize) return manualHeight;

#if UNITY_IPHONE || UNITY_ANDROID
        if (scalingStyle == Scaling.FixedSizeOnMobiles)
            return manualHeight;
#endif
        if (height < minimumHeight) return minimumHeight;
        if (height > maximumHeight) return maximumHeight;
        return height;
    }
}

void Update ()
{
    if (mTrans != null)
    {
        float calcActiveHeight = activeHeight;

        if (calcActiveHeight > 0f )
        {
            float size = 2f / calcActiveHeight;
            
            Vector3 ls = mTrans.localScale;

            if (!(Mathf.Abs(ls.x - size) <= float.Epsilon) ||
                !(Mathf.Abs(ls.y - size) <= float.Epsilon) ||
                !(Mathf.Abs(ls.z - size) <= float.Epsilon))
            {
                mTrans.localScale = new Vector3(size, size, size);
            }
        }
    }
}

从上面可以看出PixelPerfect，FixedSize(FixedSizeOnMobile是移动平台的FixedSize设置)主要是缩放标准的选取。
当设置为PixelPerfect的时候会根据ScreenHeight与minmumHeight和maxmumHeight的比较来决定是以ScreenHeight为基准按2/ScreenHeight比例缩放还是2/minmumHeight or 2/maxmumHeight为比例缩放。
当设置FixedSize的时候只根据我们设定的manualHeight作为参考标准去缩放UIRoot，缩放比例为2/manualHeight。
根据缩放标准的选取去设定UIRoot localScale的值以实现UI缩放。
那么这里就有个疑问，为什么是2/manualHeight而不是1/manualHeight了？
要明白2这个常数的含义，我们先要看看Camera设定为Orthographic类型中的Orthographic Size的含义。
Camera’s half-size when in orthographic mode. This is half of the vertical size of the viewing volume. Horizontal viewing size varies depending on viewport’s aspect ratio. Orthographic size is ignored when camera is not orthographic (see orthographic). See Also: camera component.
可以看出Orthographic Size是指摄像机所观察垂直区域的一半。(前提是设置了orthographic camera)。如果Size设置为1，那么Camera所看到的高度为2 Unit。摄像机所看到的垂直区域一半也就是屏幕高度的一半,Orthographic Size所指示的1个Unit的高度为Screen.Height/2。(结合Orthographic Size和Pixel Per Unit设置，我们可以实现Sprite的Pixels Perfect显示)
如果屏幕高度为1000个像素，Size设置的值为1表示1000/2=500个像素。所以，我们通过整个关系计算UIRoot下的GameObject的实际对应屏幕的高度：从GameObject向上一直到UIRoot，将它们的loaclScal相乘得到的乘积除以Size乘以屏幕高度的一半，即（localScale*….localScale)/Size*Screen.height/2。
如果屏幕分辨率为1024 * 768，那么如果我们把Size设置为1，那么1 Unit就对应屏幕分辩率高度的一半即384，也就是说UIRoot下Gameobject实际对应屏幕的高度应该按照384来计算即Screen.height/2来计算，因为Size的大小会使物体所占比例成倍缩小，所以我们还需要除以Size。
最终得出UIRoot下GameObject的实际对应屏幕的高度计算如下：
(localScale *…….*localScale)Screen.height/2/Size
(这也就是为什么UIRoot缩放比例是2/manuaHeight里常数为2的原因，这样一来localScale的值就和屏幕所占比例一一对应了(前提是Size为1))
这可以解释UIRoot的localStyle为啥都是很小的小数，因为这样可以保证UIRoot的子节点都可以以原来的大小作为localScale，比如一张图片是20*20的，我们可以直接设置localScale为（20,20,1）不用进行换算，直观方便。（NGUI3.0（or 2.7)以后的版本已经不再使用localScale来表示UISprite ，UILable（UIWidget的子类）的大小了，而是在UIWidget的width和height来设置，这样做的好处就是一个gameObject节点可以挂多个UISprite或UILabel了，而不会受localScale的冲突影响 2013/11/16增补）。
这样一来控件坐标与像素一一对应了。这也就是为什么在缩放UIRoot的时候采用2f / calcActiveHeight的原因。
那么如何让我们的制作的Sprite的像素完美一一对应显示在屏幕上了？
我们知道了屏幕分辨率为1024768且Orthographic Size设置为1时，1个Unit对应的高度是384，那么也就是说要想让Sprite像素完美一一对应屏幕显示，我们要确保Sprite的Pixel Per Unit设定为Screen.height/2/Size。
之前提到当我们的常数是2来除以Screen.height的时候需要把Camera的Orthographic Size设置成1才能实现控件坐标与像素的一一对应，让我们看看UIRoot的源码：

1
2
3
4
5
6
7
8
9
10
11
12

protected virtual void Start ()  
{  
    UIOrthoCamera oc = GetComponentInChildren<UIOrthoCamera>();  
    if (oc != null)  
    {  
        Debug.LogWarning("UIRoot should not be active at the same time as UIOrthoCamera. Disabling UIOrthoCamera.", oc);  
        Camera cam = oc.gameObject.GetComponent<Camera>();  
        oc.enabled = false;  
        if (cam != null) cam.orthographicSize = 1f;  
    }  
    else Update();  
}  

看得出NGUI并没有为我们强制设置为1，只是警告我们不能把UIRoot和UIOrthoCamera一起使用，如果使用了会自动剔除UIOrthoCamera，并设置orthographicSize为1。我们可以去设置orthographicSize实现不同的效果。
了解了UIRoot的实现，那么回到我们原始的话题，如何通过UIRoot实现屏幕自适应了？
当屏幕分辨率变化的时候UIRoot下的UI会出现显示不全或者两边有黑边的问题，因为FixedSize结合Manual Height而已控制UIRoot的按比例缩放，所以我们只需把两边未能显示全的UI以宽为基准按比例缩放即可(通过动态计算Manual Height的值)。
UIRoot分辨率自适应代码
ManualWidth和ManualHeight是我们最初美术设计所针对的分辨率，修改到对应的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

using UnityEngine;
using System.Collections;
  
public class UIRootExtend : MonoBehaviour {
      
    public int ManualWidth = 640;
    public int ManualHeight = 960;
  
    private UIRoot _UIRoot;
  
    void Awake()
    {
        _UIRoot = this.GetComponent<UIRoot>();
    }
  
    void FixedUpdate()
    {
        if (System.Convert.ToSingle(Screen.height) / Screen.width > System.Convert.ToSingle(ManualHeight) / ManualWidth)
            _UIRoot.manualHeight = Mathf.RoundToInt(System.Convert.ToSingle(ManualWidth) / Screen.width * Screen.height);
        else
            _UIRoot.manualHeight = ManualHeight;
    }
}

自适应后在屏幕分辨率为1024768(1.333比例)的时候完美显示如下：

自适应后在屏幕分辨率为800800(1.0比例)的时候显示如下：

自适应后在屏幕分辨率设置为960*640(1.5比例)的时候显示如下：

这样一来就实现了保持比例自适应。因为UIRoot是基于高度来缩放的，所以在低分辨率变到高分辨率的时候会出现左右黑边，这在横版游戏里是肯定不行的，所以我们需要做到以宽为基准的自适应。
那么基于宽度缩放的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public int activeHeight
{
    get
    {
        int height = Mathf.Max(2, Screen.height);

        // Base on width instead of height
        manualHeight = Screen.height * UIRootExtend.ManualWidth / Screen.width;
        
        if (scalingStyle == Scaling.FixedSize) return manualHeight;

        #if UNITY_IPHONE || UNITY_ANDROID
        if (scalingStyle == Scaling.FixedSizeOnMobiles)
            return manualHeight;
        #endif
        if (height < minimumHeight) return minimumHeight;
        if (height > maximumHeight) return maximumHeight;
        return height;
    }
}

但上述在低分辨率变到高分辨率的时候会因为以宽为基准导致高度的自适应超出范围，见下图：

这种情况只能通过拉伸背景来铺满屏幕，但会失去原始比例(UIStretch可以实现基于屏幕或容器的自适应，不建议使用，后续NGUI都放弃了)。
我们肯定不希望我们的主要的UI都被拉伸变形，所以这里需要提到的是UIAnchor，
让我们在回忆下UIAnchor的作用：
“apply a half-pixel offset on Windows machines, for pixel-perfect results.”(把UI限定在窗口特定位置，当窗口变化的时候会依然处于相对窗口的位置)
待续……

关于UI制作尺寸的选择以及UI自适应相关设置：
前面的学习结合Unity Unit Pixel Per Unit的学习，可以看出，UI自适应和Pixel显示我們需要考虑的点有以下几个:
UI需要考虑的点：

1. Canvas Render Mode(Canvas) – Screen Space Camera(一般来说不是作为3D UI摄像机的话，都会选择Screen Space Camera去自己指定一個UI Camera)
2. UI Scale Mode(Canvas Scaler) – Scale With Screen Size(一般来说为了根据不同设备分辨率进行自适应，我們都会选择这种模式(跟物理size无关))
3. Project(Camera) – 不是用于3D UI的话，一般来说UI Camera都是设置成Orthographic(正交投影)
4. Screen Match Mode(Canvas Scaler) – 一般都选择Match Width Or Height指定是以宽为主还是以高为主(影响最终黑边情况 – 是上下黑边还是左右黑边)
5. Reference Size(Canvas Scaler) – 影响不同机器上的自适应情况(分辨率降低或者升高会影响自适应结果 – 比如居中满屏显示的UI，以高分辨Reference Size在低分辨率Screen Size上以高度自适应会导致左右两侧的UI超出显示范围)(主流手机分辨率比例都在1.333 - 1.778，大部分是1.778)
6. UI Anchors – 主要影響UI的自適應佈局方式(是自适应缩放还是相对位置)

Note:
横版2D和竖版2D游戏选择时，主要要考虑Screen Match Mode和Reference Size的选择，因为前者是不允许左右黑边，后者是不允许上下黑边的，两者同时也不允许超出的情况，所以个人认为横版2D应该选择Match Width Or Height值为0(以宽为主不让左右有黑边)，同时Reference Size选择高分辨率，在低分辨率机器上显示时不至于超出高度(只是上下有黑边，这个问题可以通过用背景结合UI Anchors自适应的方式避免)。普通的2D UI，我们最主要要考虑的是Refrence Size的选择(选择高分辨率Reference Size和以宽度为基准自适应，然后结合UI Anchor
s布局和拉升背景即可)，这样居中的物体不会被切割显示不全，在低分辨率Screen Size上只是显示高度缩小而已，UI Anchor靠边布局的UI依然正常显示。

Pixel Perfect显示考虑的点：

1. Reference Size(Canvas Scaler) – 我们作为基准计算PPU的分辨率
2. Orthographic Size(Camera) – 参与Pixel Perfect显示计算，同时把屏幕划分成Orthographci Size * 2个高Unit
3. Reference Pixels Per Unit(Canvas Scaler) – 参与SpriteRectSize显示计算的参数(SpriteRectSize = SpriteSize * SpritePPU / CanvaReferencePPU)，一般设置跟Sprite PPU一样保证Sprite按原始大小显示即可
4. Pixels Per Unit(Asset) – Asset相对一个屏幕Unit显示的Pixels，用于确保Asset Pixel Perfect显示

Pixel Perfect显示公式：
Orthographic Size = Screen.height / 2 / PPU;
从前面的学习我们知道了，要想Pixel Perfect显示，除了动态修正Orthographic Size以外就是针对不同分辨率机器做多套PPU的资源去使用。
如果想Pixel Perfect显示，那么UI尺寸的选择就要参考计算出的PPU来设计。

DOTween

DOTween Instroduction

DOTween is a fast, efficient, fully type-safe object-oriented animation engine for Unity, optimized for C# users, free and open-source, with tons of advanced features

简单看一下官网提到的Features(这里只Copy一部分)：
Speed and efficiency:
Not only very fast, but also very efficient: everything is cached and reused to avoid useless GC allocations.
Shortcuts:
Shortcut extensions that directly extend common objects
Extremely accurate:
Time is calculated in a very precise way. This means that 1000 loops of 1 second each will play exactly as long as a single loop of 1000 seconds.
Animate everything (almost)
DOTween can animate every numeric value and also some non-numeric ones. It can even animate strings, with support for rich-text.
Full control
Play, Pause, Rewind, Restart, Complete, Goto and tons of other useful methods to control your tweens.
Grouping
Combine tweens into Sequences to create complex animations (which don’t need to be in a, uh, sequence: they can also overlap each other).
Blendable tweens
Some tweens can blend between each other in realtime, thanks to powerful DOBlendable shortcuts.
Paths
Animate stuff along both linear and curved paths, with additional options for the orientation of your traveling agents.
Change values and duration while playing
Change a tween’s start/end values or duration at any moment, even while playing.
Yield for coroutines
Various “WaitFor…” methods to use inside coroutines, that allow you to wait for a tween to be completed, killed, started, or for it to reach a given position or loops.
Plugins
DOTween is built with an extensible architecture in mind, which allows you to create your own tween plugins as separate files.
Extras
Extra virtual methods to do stuff like calling a function after a given delay.
…….
总的来说DOTween可以满足我们做动画的任何要求且高效快速方便使用。

DOTween Install

看得出DOTween的定位是一个动画引擎。
首先是DOTween下载
其次是DOTween加入到我们的工程项目里(Assets下)，然后DOTween被自动加载。
DOTween加载进来后会弹出设置界面：

点击Setup DOTween进行设置，设置DOTween好使DOTween根据我们的Unity版本去导入一些特定库。
接下来我们就可以使用DOTween里的库函数做动画了。

DOTween Nomenclature and Prefixes

深入学习DOTween之前，让我们先了解下DOTween里的命名方式和一些关键术语：
以下学习源于DOTween官网
Nomenclature:
Tweener – A tween that takes control of a value and animates it.(Tweener是控制动画细节参数和播放的)
Sequence – A special tween that, instead of taking control of a value, takes control of other tweens and animates them as a group.(Sequence可以理解成负责对tweens进行动画而非对属性比如position做动画)
Tween – A generic word that indicates both a Tweener and a Sequence.
Nested tween – A tween contained inside a Sequence.

Prefixes:
DO – Prefix for all tween shortcuts (operations that can be started directly from a known object, like a transform or a material). Also the prefix of the main DOTween class.

1
2
3

transform.DOMoveX(100, 1);
transform.DORestart();
DOTween.Play();

Set – Prefix for all settings that can be chained to a tween (except for From, since it’s applied as a setting but is not really a setting).(tween的setting函数)

1

myTween.SetLoops(4, LoopType.Yoyo).SetSpeedBased();

On – Prefix for all callbacks that can be chained to a tween.(tween的一些回调设定函数)

1

myTween.OnStart(myStartFunction).OnComplete(myCompleteFunction);

DOTween使用学习

在使用DOTween之前，我们需要在项目添加命名空间并对DOTween的初始化(初始化这一步不是必须的，不手动初始化也会自动初始化，官网推荐手动初始化设定)：

1
2
3

using DG.Tweening;

DOTween.Init();

让我们来看看DOTween里的函数定义：

1
2
3
4

public static Tweener DOMove(this Transform target, Vector3 endValue, float duration, bool snapping = false);
public static Sequence DOJump(this Transform target, Vector3 endValue, float jumpPower, int numJumps, float duration, bool snapping = false);
public static int DOKill(this Component target, bool complete = false);
......

可以看出DOTween里面的大量方法都是通过C#里extend method的方式添加进去的。
所以我们要使用特定DOTween方法，我只需要在对应类的实例调用扩展方法即可。
接下来看看我们如何创建自定义的Tween。
有三中方式可供选择：

1. The generic way
   DOTween.TO(getter, setter, to float duration)
   Changes the given property from its current value to the given one.
   getter A delegate that returns the value of the property to tween. Can be written as a lambda like this: ()=> myValue
   where myValue is the name of the property to tween.
   setter A delegate that sets the value of the property to tween. Can be written as a lambda like this: x=> myValue = x
   where myValue is the name of the property to tween.
   to The end value to reach.
   duration The duration of the tween.

1
2
3
4

// Tween a Vector3 called myVector to 3,4,8 in 1 second
DOTween.To(()=> myVector, x=> myVector = x, new Vector3(3,4,8), 1);
// Tween a float called myFloat to 52 in 1 second
DOTween.To(()=> myFloat, x=> myFloat = x, 52, 1);

2. The shortcuts way(Extension method)

1

transform.DOMove(new Vector3(2,3,4), 1);

在shortcuts方法后面调用From()的话，就会初始位置当做dest，把dest当做初始绘制来做动画。

1

transform.DOMove(new Vector3(2,3,4), 1).From();

3. Additional generic ways
   这种没太看明白

1
2
3
4
5

static DOTween.Punch(getter, setter, Vector3 direction, float duration, int vibrato, float elasticity)
static DOTween.Shake(getter, setter, float duration, float/Vector3 strength, int vibrato, float randomness, bool ignoreZAxis)
static DOTween.ToAlpha(getter, setter, float to, float duration)
static DOTween.ToArray(getter, setter, float to, float duration)
static DOTween.ToAxis(getter, setter, float to, float duration, AxisConstraint axis)

貌似是会对Tween做特殊的限制，比如DOTween.Shake延axis轴变化vector3。

接下来让我们看看如何使用Sequence：
The sequenced tweens don’t have to be one after each other. You can overlap tweens with the Insert method.(sequence可包含其他sequence，可以通过Insert把tween插入到特定时间执行)
A tween (Sequence or Tweener) can be nested only inside a single other Sequence, meaning you can’t reuse the same tween in multiple Sequences. (同一个tween不能被多个sequence使用)
创建一个Sequence:

1

DOTween.Sequence();

我们可以通过添加tweens，callback到sequence里去做一些特别的动画。
Note:
“ all these methods need to be applied before the Sequence starts (usually the next frame after you create it, unless it’s paused), or they won’t have any effect.”(添加tweens，callback这些都必须在Sequence开始之前，可以理解为同一帧里)

接下来我们看看Tween的一些设置：
这些设置分为针对全局，tweens，sequence，tweener设置。
举个简单的例子，比如我们在初始化DOTween的时候设置了tween在同一时刻激活的最大数量。我超过这个数量后想要修改，我们可以通过:

1

DOTween.SetTweensCapacity(***);

上述这个方法就是针对全局设置的

接下来我们看看如何动态的控制tween动画的：
有三种方式：

1. Via Static methods and filters
   DOTween class给我们提供了大量的静态方法去控制tween动画。
   比如我们想暂停某个tween动画或暂停所有tween：

1
2

DOTween.Pause(tweenname);
DOTween.PauseAll();

2. Directly from the tween
   我们也可以通过保存的tween动画引用去调用控制相关的动画

1

myTween.Pause();

3. From a shortcut-enhanced reference
   直接通过扩展方法去停止对应的物体上的tween(这里要注意的是，所有控制tween的扩展方法都带DO前缀)

1

transfrom.DOPause();

Note:
“IMPORTANT: remember that to use these methods on a tween after it has ended, you have to disable its autoKill behaviour, otherwise a tween is automatically killed at completion.”(对tween设置的时候一定要disable automatically kill，否则在tween完成的时候tween会被销毁)
同时DOTween还给我们提供了很多静态方法去获取tween的信息(比如Delay(),Duration()等)

Tween结合Coroutines的使用：
Tween提供了一些YieldInstructions的方法，可以让我们结合Coroutines去方便快速的实现一些对调用时机有讲究的动画:

1
2
3
4
5
6
7
8

// 需要等到tween结束
IEnumerator SomeCoroutine()
{
    Tween myTween = transform.DOMoveX(45, 1);
    yield return myTween.WaitForCompletion();
    // This log will happen after the tween has completed
    Debug.Log("Tween completed!");
}

总结：
给我的感觉，DOTween是一个基于Unity扩展的强大的数学动画库。
通过DOTween我们可以快速的去针对Unity里的一些属性比如位置，材质，UI等做动画，可以说是属于程序员的动画制作工具。

TexturePacker官网

待续……

Reference

TexturePacker官网

前言

写这一篇文章的目的是出于自己一直以来基础都比较弱，特别是数据结构和算法，但数据结构和算法确实程序里很核心的部分，只有了解各种数据结构和算法的基本思想，才能针对实际问题做出最好的选择，写出最优的程序。工作两年多了，但感觉自己再这方面还是依然原地踏步，了解的一知半解。为了避免多年以后还来学习这些本应该在学校学好的知识，从而有了这一次学习计划。

在看了这位博主的我的算法学习之路之后，深深的感受到了数据结构和算法的魅力和重要性。虽然不知道自己还能为游戏梦想坚持多久，但当下，制定一个完整的数据结构和算法的学习计划是当务之急。

现在有点理解别人说过的”编程语言只是工具，编程思想，数据结构和算法才是核心。”

以下学习主要是对于数据结构和算法的回顾和进阶学习计划。准备用C++来写。

参考书籍：
编程语言：
《C++ Primer》Fifth Edition – Stanley B.Lippman Josee Lajoie Barbara E.Moo
《Effective C++》Third Edition – Scott Meyers
最初学习C++是看的《Thinking in C++》和《Professional C++》，但后来看了部分《C++ Primer》之后觉得，这本书在细节方面讲解的更细致到位。而《Effective C++》是从我们平时容易忽略或错误理解的点，以一条条规则的形式，讲述背后的道理，可以作为C++编程指南。

数据结构和算法：
《数据结构与算法 - C语言描述》 – Mark Allen Weiss
数据结构与算法 - C语言描述课后习题在线答案参考
《算法设计与分析》 Third Edition – 王晓东
《Introduction To Algorithm》(算法导论) Third Edition– Thomas H.Cormen & ……
Introduction To Algorithm MIT课程视频

前两者是我在大学时候学习的关于数据结构和算法的书籍，作为基础知识回顾来学习。
第三个在网络上的评价褒贬不一，但作为国外的优秀教材来使用，可以看出是很有分量的，作为进阶学习书籍。最后一个是麻省理工对于算法导论教材的上课视频可以作为学习《Introduction To Algorithm》的学习资料。

编程艺术和思考：
《The Progmatic Programmer》(程序员修炼之道) – Andrew Hunt & David Thomas
此书并非将编程技巧而是讲程序员应该如何去思考，如何高效的开发。

STL深入学习：
《C++标准程序库》
此书虽然比较老，但貌似是C++标准库学习的经典书籍，里面对STL进行基本的讲解学习。
《STL源码剖析》
此书乃侯捷所著，对于STL进行了深入的讲解学习，属于对STL的深入学习的一本参考书籍。

欲善其事必先利其器

单纯学习数据结构和算法是比较枯燥的，算法可视化的神奇网站，这个网站可以让我们在学习数据结构和算法的时候可视化的看到每一步的变化，更加形象生动。

数学知识

指数

Power(X,A) X Power(X,B) = Power(X,A+B)
Power(X,A) / Power(X,B) = Power(X,A-B)

对数

LogA(B) = LogC(B) / LogC(A); C > 0
Log(AB) = Log(A) + Log(B)
Log(A/B) = Log(A) - Log(B)
Log(Power(A,B)) = B X Log(A)
Log(X) < X(X > 0)

级数

1
2
3
4
5
6

 N
 ∑  (Power(2, i)) =  Power(2, N+1) - 1;
i=0
 N
 ∑ (Power(A, i)) = (Power(2, N+1) - 1) / (A - 1)
i=0

模运算

如果N整除A-B,那么A与B模N同余，记为A≡B(mod N)

证明方法

1. 归纳法
   第一步证明基准情形(对于某些小的值的正确性，比如1)
   第二步，假设直到k也成立
   最后，证明k+1的时候也成立即可
2. 反证法
   首先假设定力不成立
   然后证明该假设导致的某个已知的性质不成立，从而证明原假设是错误的。

递归简论

基本法则：

1. 基准情形
   必须要有某些基准的情形，它们不用递归就能求解
2. 不断推进
   对于那些递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进
3. 设计法则
   假设所有的递归调用都能运行
4. 合成效益法则
   在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作

数据结构

抽象数据类型(Abstract data type, ADT)是一些操作的集合。

链表

链表是由一系列不必在内存中相邻的结构组成。每一个结构均含有表元素和指向包含该元素后下一个元素的结构的指针。最后一个单元的后继元指向NULL。

链表分类：

1. 单向链表
   只能从前往后访问节点
   以下实现了简单的单向链表，允许头插入Node，删除第一个满足条件的Node，打印所有成员，判断是否为空，得到Node节点数等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

#include "stdafx.h"

template<typename T>
struct SingleLinkNode
{
	T mElement;
	SingleLinkNode* Next;
};

template<typename T>
class SingleLinkList
{
public:
	SingleLinkList()
	{
		mHeadNode = NULL;

		mLength = 0;
	}

	~SingleLinkList()
	{
		SingleLinkNode<T> *tempnode;
		while (mHeadNode != NULL)
		{
			tempnode = mHeadNode->Next;
			delete mHeadNode;
			mLength--;
			mHeadNode = tempnode;
		}
	}

	//ADT
	void FrontInsert(T v)
	{
		SingleLinkNode<T> *tempnode = new SingleLinkNode<T>();

		tempnode->mElement = v;

		tempnode->Next = mHeadNode;

		mHeadNode = tempnode;

		mLength++;
	}

	bool IsEmpty()
	{
		return mLength;
	}

	
	void Delete(T v)
	{
		if (mHeadNode == NULL)
		{
			return;
		}

		SingleLinkNode<T> *tempnode = mHeadNode;

		SingleLinkNode<T> *prenode = NULL;

		bool find = false;

		while (tempnode != NULL)
		{
			//remove first v element
			if (tempnode->mElement == v)
			{
				//when remove first node, move forward mHeadNode
				if (tempnode == mHeadNode)
				{
					mHeadNode = tempnode->Next;
				}
				else
				{
					prenode->Next = tempnode->Next;
				}
				delete tempnode;
				mLength--;
				find = true;
				break;
			}
			//Record pre node for later operation
			prenode = tempnode;
			tempnode = tempnode->Next;
		}

		if (find)
		{
			cout << "Delete " << v << " successfully!" << endl;
		}
		else
		{
			cout << "Delete " << v << " failed! Not find it in list!" << endl;
		}
	}

	int Find(T v)
	{
		int position = 0;
		SingleLinkNode<T> *tempnode = mHeadNode;
		while (tempnode != NULL)
		{
			position++;
			if (tempnode->mElement == v)
			{
				return position;
			}
			else
			{
				tempnode = tempnode->Next;
			}
		}
		return -1;
	}

	SingleLinkNode<T>* GetNodeAt(int position)
	{
		if (position < 1 || position > mLength)
		{
			cout << position << " Out of range of link list!" << endl;
			cout << "Current length of link list = " << mLength << endl;
			cout << "Insert failed!" << endl;
			return NULL;
		}
		else
		{
			//链表是非连续的存储方式，所以需要通过循环访问到特定位置
			SingleLinkNode<T> *tempnode = mHeadNode;

			if (position == 1)
			{
				return mHeadNode;
			}
			else
			{
				for (int i = 1; i < position; i++)
				{
					tempnode = tempnode->Next;
				}
				return tempnode;
			}
		}
	}

	void TraversAll()
	{
		SingleLinkNode<T> *tempnode = mHeadNode;
		while (tempnode != NULL)
		{
			cout << tempnode->mElement << endl;
			tempnode = tempnode->Next;
		}
	}

	int Length()
	{
		return mLength;
	}
private:
	SingleLinkNode<T> *mHeadNode;

	int mLength;
};

测试程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include "stdafx.h"
#include <vld.h>

#include "SingleLinkList.h"

int _tmain(int argc, _TCHAR* argv[])
{
	//Single Link List part
	SingleLinkList<int> *singlelinklist = new SingleLinkList<int>();

	singlelinklist->FrontInsert(3);
	singlelinklist->FrontInsert(1);
	singlelinklist->FrontInsert(4);
	singlelinklist->FrontInsert(2);

	singlelinklist->TraversAll();

	singlelinklist->Delete(1);
	singlelinklist->Delete(5);

	singlelinklist->TraversAll();

	delete singlelinklist;

	system("pause");
	return 0;
}

可以看到链表的节点是通过SingleLinkNode抽象出来。

2. 双向链表
   可以从前往后也可以从后往前访问节点
   为了从后往前访问，我们需要改写SingleLinkNode支持从当前Node访问前一Node

1
2
3
4
5
6
7
8
9

template<typename T>
struct DoubleLinkNode
{
	T mElement;
	
	DoubleLinkNode *Pre;

	DoubleLinkNode *Next;
};

同时为了快速从尾部访问，SingleLinkList需要增加mTailNode去指向链表尾部Node，同时支持从尾部插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

#include "stdafx.h"

//DoubleLinkNode definition
//.....

template<typename T>
class DoubleLinkList
{
public:
	DoubleLinkList()
	{
		mHeadNode = NULL;

		mTailNode = NULL;

		mLength = 0;
	}

	~DoubleLinkList()
	{
		DoubleLinkNode<T> *tempnode;
		while (mHeadNode != NULL)
		{
			tempnode = mHeadNode->Next;
			delete mHeadNode;
			mLength--;
			mHeadNode = tempnode;
		}
	}

	//ADT
	void FrontInsert(T v)
	{
		DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

		tempnode->mElement = v;

		//when insert first element, tail node equals to head node
		if (mLength == 0)
		{
			tempnode->Pre = NULL;
			tempnode->Next = NULL;
			mHeadNode = tempnode;
			mTailNode = mHeadNode;
		}
		else
		{
			mHeadNode->Pre = tempnode;
			tempnode->Next = mHeadNode;
			mHeadNode = tempnode;
		}

		mLength++;
	}

	void InsertAtPosition(int position, T v)
	{
		if (position < 1 || position > mLength + 1)
		{
			cout << position << " Out of range of link list!" << endl;
			cout << "Current length of link list = " << mLength << endl;
			cout << "Insert failed!" << endl;
		}
		//when insert element as first element.
		else if (position == 1)
		{
			FrontInsert(v);
		}
		//when insert at final position
		//when position is larger than length of link list,
		//we insert it at the end of the link list
		else if (position == mLength + 1)
		{
			TailInsert(v);
		}
		//insert element between head and last element
		else
		{
			DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

			tempnode->mElement = v;

			DoubleLinkNode<T> *prenode = GetNodeAt(position - 1);

			if (prenode != NULL)
			{
				tempnode->Pre = prenode;

				tempnode->Next = prenode->Next;

				prenode->Next->Pre = tempnode;

				prenode->Next = tempnode;

				mLength++;
			}
		}
	}

	void TailInsert(T v)
	{
		DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

		tempnode->mElement = v;

		//when insert first element, tail node equals to head node
		if (mLength == 0)
		{
			tempnode->Pre = NULL;

			tempnode->Next = NULL;

			mHeadNode = tempnode;

			mTailNode = mHeadNode;
		}
		else
		{
			tempnode->Pre = mTailNode;

			tempnode->Next = NULL;

			mTailNode->Next = tempnode;

			mTailNode = tempnode;
		}

		mLength++;
	}

	DoubleLinkNode<T>* GetNodeAt(int position)
	{
		if (position < 1 || position > mLength)
		{
			cout << position << " Out of range of link list!" << endl;
			cout << "Current length of link list = " << mLength << endl;
			cout << "Insert failed!" << endl;
			return NULL;
		}
		else
		{
			//链表是非连续的存储方式，所以需要通过循环访问到特定位置
			DoubleLinkNode<T> *tempnode = mHeadNode;

			if (position == 1)
			{
				return mHeadNode;
			}
			else if (position == mLength)
			{
				return mTailNode;
			}
			else
			{
				for (int i = 1; i < position; i++)
				{
					tempnode = tempnode->Next;
				}
				return tempnode;
			}
		}
	}

	bool IsEmpty()
	{
		return mLength;
	}

	void Delete(T v)
	{
		if (mHeadNode == NULL)
		{
			return;
		}

		DoubleLinkNode<T> *tempnode = mHeadNode;

		DoubleLinkNode<T> *prenode = NULL;

		bool find = false;

		while (tempnode != NULL)
		{
			//remove first v element
			if (tempnode->mElement == v)
			{
				//when remove first node, move forward mHeadNode
				if (tempnode == mHeadNode)
				{
					if (mLength <= 1)
					{
						mHeadNode = NULL;
						mTailNode = NULL;
					}
					else
					{
						mHeadNode = tempnode->Next;
						mHeadNode->Pre = NULL;
					}
				}
				else if (tempnode == mTailNode)
				{
					if (mLength <= 1)
					{
						mHeadNode = NULL;
						mTailNode = NULL;
					}
					else
					{
						mTailNode = prenode;
						mTailNode->Next = NULL;
					}
				}
				else
				{
					prenode->Next = tempnode->Next;
					tempnode->Next->Pre = prenode;
				}
				delete tempnode;
				mLength--;
				find = true;
				break;
			}
			//Record pre node for later operation
			prenode = tempnode;
			tempnode = tempnode->Next;
		}

		if (find)
		{
			cout << "Delete " << v << " successfully!" << endl;
		}
		else
		{
			cout << "Delete " << v << " failed! Not find it in list!" << endl;
		}
	}

	int Find(T v)
	{
		int position = 0;
		DoubleLinkNode<T> *tempnode = mHeadNode;
		while (tempnode != NULL)
		{
			position++;
			if (tempnode->mElement == v)
			{
				return position;
			}
			else
			{
				tempnode = tempnode->Next;
			}
		}
		return -1;
	}

	void TraversAll()
	{
		DoubleLinkNode<T> *tempnode = mHeadNode;
		while (tempnode != NULL)
		{
			cout << tempnode->mElement << endl;
			tempnode = tempnode->Next;
		}
	}

	int Length()
	{
		return mLength;
	}
private:
	DoubleLinkNode<T> *mHeadNode;

	DoubleLinkNode<T> *mTailNode;

	int mLength;
};

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include "stdafx.h"
#include <vld.h>

#include "SingleLinkList.h"

int _tmain(int argc, _TCHAR* argv[])
{
	//Double link list part
	DoubleLinkList<int> *doublelinklist = new DoubleLinkList<int>();

	doublelinklist->TailInsert(2);
	doublelinklist->FrontInsert(3);
	doublelinklist->TailInsert(4);
	doublelinklist->TailInsert(1);

	doublelinklist->TraversAll();

	doublelinklist->Delete(4);

	cout << "Complete doublelinklist->Delete(4);" << endl;

	doublelinklist->TraversAll();

	doublelinklist->InsertAtPosition(3, 6);

	cout << "Complete doublelinklist->InsertAtPosition(3, 6);" << endl;

	doublelinklist->TraversAll();

	doublelinklist->InsertAtPosition(5, 7);

	cout << "Complete doublelinklist->InsertAtPosition(5, 7);" << endl;

	doublelinklist->TraversAll();

	doublelinklist->InsertAtPosition(9, 10);

	cout << "Complete doublelinklist->InsertAtPosition(9, 10);" << endl;

	doublelinklist->TraversAll();

	delete doublelinklist;

	system("pause");
	return 0;
}

测试结果：

3. 循环链表
   双向链表的基础上，可以从头直接访问尾也可以从尾直接访问头
   出于测试目的，为了验证是否至此从尾访问到头部，在TraversAll的方法里，我从第二个节点开始访问进行打印数据直到回到头节点

1
2
3
4
5
6
7
8
9
10
11

void TraversAll()
{
	CircleLinkNode<T> *tempnode = mHeadNode;
	tempnode = tempnode->Next;
	cout << mHeadNode->mElement << endl;
	while (tempnode != mHeadNode)
	{
		cout << tempnode->mElement << endl;
		tempnode = tempnode->Next;
	}
}

因为Head节点的Pre指向Tail节点，Tail节点的Next指向Head，所以这里在析构释放内存的时候需要注意判断条件：

1
2
3
4
5
6
7
8
9
10
11

~CircleLinkList()
{
	CircleLinkNode<T> *	tempnode = mHeadNode;
	while (mLength != 0)
	{
		mHeadNode = mHeadNode->Next;
		delete tempnode;
		tempnode = mHeadNode;
		mLength--;
	}
}

其他情况主要注意在Head和Tail的极端顶点时的判断处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//ADT
void FrontInsert(T v)
{
	CircleLinkNode<T> *tempnode = new CircleLinkNode<T>();

	tempnode->mElement = v;

	//when insert first element, tail node equals to head node
	if (mLength == 0)
	{
		tempnode->Pre = tempnode;
		tempnode->Next = tempnode;
		mHeadNode = tempnode;
		mTailNode = mHeadNode;
	}
	else
	{
		mHeadNode->Pre = tempnode;
		tempnode->Pre = mTailNode;
		tempnode->Next = mHeadNode->Next;
		mHeadNode = tempnode;
		mTailNode->Next = mHeadNode;
	}

	mLength++;
}

//......

测试结果：

栈

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。
栈的ADT：
Push(进栈)
Pop(出栈)

栈是LIFO(后进先出)

栈的实现：
栈是一个表，因此任何实现表的方法都能实现栈(比如数组，链表)。
下面以前面实现的链表为例来实现栈：
因为栈只允许顶端Push，Pop以及Top查看顶端元素并返回值，所以这里采用单向链表即可。

待续……

算法

算法与程序

算法是由若干条指令组成的又有穷序列，且满足下述4条性质：

1. 输入：有零个或多个由外部提供的量作为算法的输入。
2. 输出：算法产生至少一个量作为输出。
3. 确定性：组成算法的每条指令是清晰的，无歧义的。
4. 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

区分程序和算法：
程序与算法不同。程序是算法用某种程序设计语言的具体实现。

算法复杂性

算法复杂性体现在运行该算法所需的计算机资源(时间和空间)的多少上。

所以算法复杂性主要是体现的时间复杂度和空间复杂度上。
C表示复杂度，N表示问题的规模，I表示算法的输入，A表示算法本身。
C = F(N,I,A)
T表示时间复杂度，S表示空间复杂度。
T = F(N,I,A)
S = F(N,I,A)

时间复杂度

时间复杂度 — 指执行算法所需要的计算工作量
时间复杂度分为下列三种：

1. 平均时间复杂度 — 理论上一般情况的时间复杂度
2. 最坏时间复杂度 — 特殊情况下（导致时间耗费最多的数据输入）
3. 最优时间复杂度 — 特殊情况下（导致时间耗费最少的数据输入）

空间复杂度

空间复杂度 — 指执行算法所需要的内存空间

程序算法思想

递归

定义：
直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。

基本思想：
每个递归函数都必须有非递归定义的初始值，否则，递归函数就无法计算。
递归式的第二式用较小自变量的函数值来表示较大自变量的函数值的方式来定义。

事例：
无穷数列1,1,2,3,5,8,13，,2,34,55……，称为Fibonacci数列。

1
2
3

       {  1                         n = 0
F(n) = {  1                         n = 1
       {  F(n - 1) + F(n - 2)       n > 1

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// AlgorithmStudy.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int Fibonacci(int n)
{
	if( n <= 2)
	{
		return 1;
	}
	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	cout<<"Please Enter the Fibonacci's n:"<<endl;
	cin>>n;
	cout<<"Fibonacci("<<n<<") = "<<Fibonacci(n)<<endl;

	system("pause");
	return 0;
}

还有一个典型的问题，汉诺塔问题。
问题描述：
a，b，c三个塔座。塔座a上共n个圆盘，圆盘至下而上从大到小的叠放在一起，圆盘编号从小到大为1,2,3……n。要求将塔座a上的这一叠圆盘移动到塔座b上，并按同样顺序叠放。移动规则如下：

1. 每次只能移动一个圆盘
2. 任何时时刻都不允许将较大的圆盘压在较小的圆盘会上
3. 在满足移动规则1和2的前提下，将圆盘至a，b，c中任意塔座上。

解题思想：
若是奇数次移动，则将最小的圆盘移到顺时针方向的下一座塔上。若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移动到另一个塔座上。

那么如何用递归来实现这个解题思想了。
当n = 1时，将编号1的圆盘从塔座a移动到塔座b即可。
当n > 1时，需要利用塔座c作为辅助塔座。此时要设法将n - 1个较小的圆盘依照移动规则从塔座a移至塔座c上，然后，将剩下的最大圆盘从塔座a移至塔座b上，最后，再设法将n - 1个较小的圆盘你依照移动规则从塔座c移至塔座b上。(由此可见，n个圆盘的移动问题分解成为了两次n - 1个圆盘的移动问题，这就可以通过递归的方式解决)

1
2
3
4
5
6
7
8
9

void Hanoi(int n, int a, int b, int c)
{
	if(n > 0)
	{
        Hanoi(n - 1, a, c, b); // 将n - 1个圆盘按移动规则从a移动到c
        move(a,b);             // 将圆盘n从a移动到b
        Hanoi(n -1, c,  b, a); // 将n - 1个圆盘按移动规则从c移动到b
    }
}

递归算法好处：
结构清晰，可读性强，且容易用数学归纳法证明算法的正确性，方便调试。

递归算法坏处：
运行效率低，时间复杂度和空间复杂度都很大。

针对Fabonacci方法，我们可以写一个非递归的方法，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int FibonacciNoRecursion(int n)
{
	int temp[2];
	temp[0] = 1;
	temp[1] = 1;
	if(n <= 2)
	{
		return 1;
	}
	else
	{
		for(int i = 2; i < n; i++)
		{
			int tp = temp[0] + temp[1];
			temp[1]= temp[0];
			temp[0] = tp;
		}
	}
	return temp[0];
}

这样一来，递归调用导致的调用栈深度问题就没有了，而是通过临时变量把数据存储了起来。

分治

基本思想：
将一个规模为n的问题分解为k个(一般划分成n/2 – 二分细分)规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解。

在排序算法学习中，快速排序(Quick Sort)和归并排序(Merge Sort)就用到了分治的思想。

动态规划

基本思想：
动态规划与分治思想类似，但动态规划里经分解得到的子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，会这样就可以避免大量的重复计算，从而得到多项式时间算法。

动态规划适用于解最优化问题。一般有4个步骤设计：

1. 找出最优解的性质，并刻画其结构特征。
2. 递归地定义最优值。
3. 以自底向上的方式计算出最优值。
4. 根据计算最优值时得到的信息，构造最优解。

动态规划的基本要素：

1. 最优子结构
   当问题的最优解包含其子问题的最优解时，称该问题具有最优子结构性质
2. 重叠子问题
   在递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复运算。
3. 备忘录方法
   备忘录方法是动态规划的变形，唯一不同的是递归方式是至顶向下。

接下来以求解最长公共子序列来分析动态规划算法。
问题描述：
X = {x1, x2, x3,…..xn}
Z = {z1, z2, z3,…..zn}
存在一个递增序列，即Z是X的子序列。

X = {x1, x2, x3,….. xm}
Y = {y1, y2, y3,….. yn}
求解X和Y的最长公共子序列Z：
Z = {z1, z2, z3,…zk}

分析最优子结构性质：
若X(m) = Y(n)，则Z(k) = X(m) = Y(n)，且Z(k-1)是X(m-1)和Y(n-1)的最长公共子序列
若X(m) != Y(n)且Z(k) != X(m)，则Z是X(m-1)和Y的最长公共子序列
若X(m) != Y(n)且Z(k) != Y(n)，则Z是X和Y(n-1)的最长公共子序列

c[i][j]记录序列X(i)和Y(j)的最长公共子序列的长度
从上面的最优子结构性质我们可以得出下列结论：

1
2
3

          {         0                       i = 0, j = 0
c[i][j] = {    c[i-1][j-1] + 1              i,j > 0; X(i) = Y(j)
          { Max(c[i][j-1], c[i-1][j])       i,j > 0; X(i) != Y(j)

从上面而已看出，在递归求的时候，很多子问题是重叠的。

b[i][j]用于记录c[i][j]的值是由哪一个子问题的解得到的。b最后会用于构建最优解。
我们把上面的情况分别分为1,2,3。在递归求解的时候存储的b[i][j]里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include "stdafx.h"
#include <iostream>
using namespace std;

template<typename T>
int GetArrayLength(T &array)
{
	return sizeof(array) / sizeof(array[0]);
}

void LCSLength(int m, int n, char *x, char *y, int **c, int **b)
{
	int i,j;
	// i = 0, j = 0的情况
	c[0][0] = 0;

	for(i = 1; i <= m; i++)
	{
		c[i][0] = 0;
	}
	
	for(i = 1; i <= n; i++)
	{
		c[0][i] = 0;
	}
	//自底向上的填充最优解
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
		{
			// X(i) == Y(j)的情况
			if(x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = 1;
			}
			// X(i) != Y(j) 且 Max{}取c[i][j-1]
			else if(c[i-1][j] >= c[i][j - 1])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 2;
			}
			// X(i) != Y(j) 且 Max{}取c[i-1][j]
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = 3;
			}
		}
	}
}

void LCS(int i, int j, char *x, int **b)
{
	if(i == 0 || j == 0)
	{
		return ;
	}
	//根据前面LCSLength的分解情况，自底向上的递归构建最长公共子序列
	if(b[i][j] == 1)
	{
		LCS(i-1, j-1, x, b);
		cout<<x[i]<<endl;
	}
	else if(b[i][j] == 2)
	{
		LCS(i-1, j, x, b);
	}
	else
	{
		LCS(i, j-1, x, b);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	//LCS,因为LCSLength里面都是以1作为索引来访问x和y的第一个字母，
	//所以这里增加一个额外的" "便于1作为第一个字母的索引
	char x[] = {' ', 'A', 'B', 'D', 'B', 'C', 'A', 'E', 'F'};
	char y[] = {' ', 'A', 'C', 'B', 'A', 'F'};
	int **c = new int*[GetArrayLength(x)];
	int **b = new int*[GetArrayLength(x)];
	for(int i = 0; i < GetArrayLength(x); i++)
	{
		c[i] = new int[GetArrayLength(y)];
		b[i] = new int[GetArrayLength(y)];
	}
	//因为前面我们额外增加了一个" "，所以这里要减少一个长度计算
	LCSLength(GetArrayLength(x) - 1, GetArrayLength(y) - 1, x, y, c, b);
	LCS(GetArrayLength(x) - 1, GetArrayLength(y) - 1, x, b);
	
	system("pause");
	return 0;
}

算法时间复杂度分析：
计算最长公共序列的LCSLength耗时O(m x n);
构建最长公共序列的LCS递归调用自身使i和j - 1,时间复杂度为O(m + n)

算法改进：
c[i][j]可以由c[i-1][j-1],c[i-1][j]和c[i][j-1]推断出来，所以可以节省数组b的空间，但数组c仍需要m x n的空间，所以空间复杂度仍然是O(m x n)

另一个很典型的动态规划事例是0-1背包问题：
问题描述：
给定n种物品和一背包。物品i的重量是w(i)，其价值为v(i)，背包容量为c。应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

形式化描述：
给定c > 0,w(i) > 0, v(i) > 0, i <= i <=n,要求找出一个n元0-1向量(x1,x2,x3…..,xn), x(i) ∈ {0, 1}, 1 <= i <= n,使得∑(i= 1 - n)(w(i) x x(i)) <= c，而且∑(i= 1 - n)(v(i) x x(i))达到最大。
转换成式子如下：
max(∑( 1 <= i <= n)(v(i) x x(i)))
{ ∑(i= 1 - n)(w(i) x x(i)) <= c
{ x(i) ∈ {0, 1}, 1 <= i <= n

分析：
最优子结构性质：
设(y1,y2……yn)是所给0-1背包问题的一个最优解，则(y2,y3…..yn)是下面相应子问题的一个最优解：
max(∑(2 <= i <= n)(v(i) x x(i)))
{ ∑(2 <= i <= n)(w(i) x x(i)) <= c - w(1) x y(1)
{ x(i) ∈ {0, 1}, 2 <= i <= n

递归关系：
0-1背包问题的子问题：
max(∑(i <= k <= n)(v(k) x x(k)))
{ ∑(i <= k <= n)(w(k) x x(k)) <= j
{ x(k) ∈ {0, 1}, i <= k <= n
m(i,j)是背包容量为j，可选物品为i,i+1…..n时0-1背包问题的最优解。
x(i)表示背包i的选择∈ {0, 1}
根据最优子结构性质，可以建立就按m(i,j)的递归式如下：
{ max{m((i+1,j), m(i+1, j - w(i)) + v(i))} j >= w(i)
m(i,j) = {
{ m(i+1,j) 0 <= j <= w(i)

     {  v(n)   j >= w(n)

m(n,j) = {
{ 0 0 <= j < w(n)

计算出所有m[i][j]后，我们可以通过判断m[i][c]和m[i+1]c是否相同来判断x(i)的值。

算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include "stdafx.h"
#include <vld.h>
#include <iostream>
#include <math.h>
using namespace std;

template<typename T>
int GetArrayLength(T &array)
{
	int length = sizeof(array) / sizeof(array[0]);
	return length;
}

void Knapsack(float *v, int *w, int c, int n, float **m)
{
	int jmax = fmin(w[n] - 1,c);
	//根据最优子结构性质，m[n - 1][j]的最优解是m[n][j]最优解的子集，
	//我们先构建出m[n][j]时的数据,然后利用m[n][j]的数据去构建m[i][c]  1 <= i < n
	for (int j = 0; j <= jmax; j++)
	{
		m[n][j] = 0;
	}

	for (int j = w[n]; j <= c; j++)
	{
		m[n][j] = v[n];
	}

	//利用m[n][j]去构建m[i][j]   1 <= i < n
	for (int i = n - 1; i > 1; i--)
	{
		jmax = fmin(w[i] - 1, c);
		for (int j = 0; j <= jmax; j++)
		{
			m[i][j] = m[i + 1][j];
		}

		for (int j = w[i]; j <= c; j++)
		{
			m[i][j] = fmax(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
		}
	}

	//Finally, we can get m[1][c] from c[2][c]
	m[1][c] = m[2][c];
	if (c >= w[1])
	{
		m[1][c] = fmax(m[2][c], m[2][c - w[1]] + v[1]);
	}
}

void Traceback(float **m, int *w, int c, int n, int *x)
{
	for (int i = 1; i < n; i++)
	{
		if (m[i][c] == m[i + 1][c])
		{
			x[i] = 0;
		}
		else
		{
			x[i] = 1;
			c -= w[i];
			cout << "Put " << i << " into the bag!" << endl;
		}
	}
	//check for last one
	x[n] = m[n][c] ? 1 : 0;
	if (x[n] == 1)
	{
		cout << "Put " << n << " into the bag!" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	//0-1背包问题
	//因为我们从v[1]开始访问当做第一个背包的价值，
	//所以这里加一个0在最前面方便从1开始索引
	float v[] = { 0, 1, 5, 2, 3, 6, 8, 3 };
	int w[] = { 0, 4, 3, 6, 7, 2, 3, 1 };
	int c = 20;
	//减掉我们额外增加的第一个
	int n = GetArrayLength(v) - 1;
	float **m = new float*[GetArrayLength(v)];
	//为了从1开始索引
	int *x = new int[n + 1];
	for (int i = 0; i < GetArrayLength(v); i++)
	{
		//m[i][j]    1 <= j <= n用于表示背包容量为j，可选物品为i,i+1....n是0-1背包问题的最优解
		//为了m[i][c]来访问背包重量为c的时候的最优解，这里需要额外增加数组长度1
		m[i] = new float[c + 1];
	}
	Knapsack(v, w, c, n, m);
	Traceback(m, w, c, n, x);
	
	for (int i = 0; i < GetArrayLength(v); i++)
	{
		delete m[i];
	}

	delete x;

	system("pause");
	return 0;
}

算法复杂度分析：
计算m[i][j]的递归式可以看出，算法Knapsack需要O(nc)计算时间，Traceback需要O(n)计算时间

算法缺点：

1. w[i]要求是整数
2. 当c很大的时候，算法Knapsack时间复杂度很大

算法改进：
详情参考计算机算法设计与分析(第3版)

贪心算法

基本思想：
贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。

基本要素：

1. 贪心选择性质
   贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。(贪心算法以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题)
2. 最优子结构性质
   最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

下面结合背包问题来区分动态规划和贪心算法在实际应用中的区别：
问题描述：
背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。

最优子结构性质分析：
若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量w，剩余的将是n-1个原重量物品1,2,…,j-1,j+1,…,n及重为w(j)-w的物品j中可装入容量为c-w的背包且具有最大价值的物品。

贪心选择性质分析：
按单位价值为依据(局部最优)进行选择(贪心选择)，可使最终装满背包时，价值最大。

贪心算法解背包问题的基本步骤：

1. 计算每种物品单位重量的价值v(i)/w(i)
2. 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
3. 若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多的装入背包。
4. 依次策略，直到背包装满为止。

贪心选择对于0-1背包问题就不能得到最优解，因为它无法保证最终背包能装满，部分闲置的背包空间使每千克背包空间的价值降低了。所以在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后做出最好选择，而不是按最优单位价值(局部最优)来选。

回溯法算法

回溯法的算法框架：

1. 问题的解空间
   解空间包含所有可能的答案
2. 回溯法的基本思想
   在问题的解空间树种，按深度优先策略，从根节点触发搜索解空间树。算法搜索到任一节点时，先判断该节点是否包含问题的解，如果不包含，则以该节点为根节点以深度优先搜索。直到搜索到叶节点也没找到问题解时，回溯到最近一个非叶节点继续搜索，知道所有节点都搜索完成为止。

接下来以0-1背包问题为例来学习理解回溯法：
假设0-1背包n = 3，w = [16, 15, 15] v = [45, 25, 25] c= 30
解空间为：
{(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1)}

因为是以深度优先搜索，所以是延A -> B -> D -> H -> D -> I -> D -> B -> E -> J -> K的顺序来搜索，直到回溯完所有的解空间节点或找到答案为止。

问题:
上述回溯法把所有的解空间都搜索了一遍，时间和空间复杂度大。

优化：
回溯法通常采用两种策略避免无效搜索，提高回溯法的搜索效率：

1. 用约束函数在扩展结点处剪去不满足约束条件的子树。
2. 用限界函数剪去得不到最优解的子树。(两个函数统称为剪枝函数)

在0-1背包里左子树表示装载当前背包，右子树表示不装载当前背包。
所以在针对剪枝函数的优化上，我们可以在判断只有在右子树中有可能包含最优解时才进入。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp + r <= bestp时，可剪去右子树。

正确的选取r是优化的关键之一：
我们可以通过按背包问题里贪心算法的方式计算出当前剩余物品的最优值(算出当前剩余物品最多还能增加的价值)作为上界剪枝。

代码实现:
Utilites.h

1
2
3
4
5
6
7
8

#include "stdafx.h"

template<typename T>
static int GetArrayLength(T &array)
{
	int length = sizeof(array) / sizeof(array[0]);
	return length;
}

Knap.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include "stdafx.h"

class Knap
{
public:
	Knap(float *v, int *w, int c, int n);

	~Knap();

	void Backtrack(int i);

	float GetBestp();

private:
	float Bound(int i);

	//把物品按单位价值降序排列
	void Sort();

	int mC; //背包容量

	int mN; //物品数量

	int *mW; //物品重量

	float *mV; //物品价值

	int mCW; //当前重量

	float mCV; //当前价值

	float mBestp; //当前最优价值
};

Knap.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

#include "stdafx.h"
#include "Knap.h"
#include "Utilties.h"

Knap::Knap(float *v, int *w, int c, int n)
{
	assert(c > 0);
	assert(n > 0);
	mC = c;
	mN = n;
	mW = w;
	mV = v;
	mCW = 0;
	mCV = 0; 
	mBestp = 0;
	Sort();
}

void Knap::Backtrack(int i)
{
	//到达叶节点
	if (i > mN)
	{
		//到了叶节点后记录最优值
		mBestp = mCV;
		return;
	}

	//进入左子树
	if (mCW + mW[i] <= mC)
	{
		mCW += mW[i];
		mCV += mV[i];
		//深度优先扩张
		Backtrack(i + 1);
		//回溯到i时，我们需要在判断是否进入右子树之前把mCW和mCV的值回复到正确的值。
		mCW -= mW[i];
		mCV -= mV[i];
	}

	//进入右子树
	if (Bound(i + 1) > mBestp)
	{
		//继续深度优先扩张
		Backtrack(i + 1);
	}
}

float Knap::GetBestp()
{
	return mBestp;
}

//计算cp + r <= bestp中r的值
//通过把剩余物品按贪心算法的背包问题来计算出最优值上界
float Knap::Bound(int i)
{
	int cleft = mC - mCW; //剩余容量

	float b = mCV; //当前价值

	//以物品单位重量价值递减序装入物品
	while (i <= mN && mW[i] <= cleft)
	{
		cleft -= mW[i];
		b += mV[i];
		i++;
	}

	//装满背包
	if (i <= mN)
	{
		b += mV[i] * cleft / mW[i];
	}

	return b;
}

void Knap::Sort()
{
	assert(mN > 0);
	float *pervalue = new float[mN];
	pervalue[0] = 0;
	for (int i = 1; i <= mN; i++)
	{
		pervalue[i] = mV[i] / mW[i];
	}

	//双重循环都跟数据大小有关
	//所以冒泡排序平均时间复杂度是O(square(n))
	for (int i = 1; i <= mN; i++)
	{
		for (int j = i + 1; j <= mN; j++)
		{
			if (pervalue[i] < pervalue[j])
			{
				swap(mV[i], mV[j]);
				swap(mW[i], mW[j]);
				swap(pervalue[i], pervalue[j]);
			}
		}
	}
}

Knap::~Knap()
{

}

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int _tmain(int argc, _TCHAR* argv[])
{	
	//0-1背包回溯算法
	//因为我们从v[1]开始访问当做第一个背包的价值，
	//所以这里加一个0在最前面方便从1开始索引
	float v[] = { 0, 1, 5, 2, 3, 6, 8, 3 };
	int w[] = { 0, 4, 3, 6, 7, 2, 3, 1 };
	int c = 20;
	//减掉我们额外增加的第一个
	int n = GetArrayLength(v) - 1;
	Knap *knap = new Knap(v, w, c, n);

	knap->Backtrack(1);

	cout << "knap->GetBestp() = " << knap->GetBestp() << endl;

	delete knap;

	system("pause");
	return 0;
}

时间复杂度分析：
Knap::Sort()排序采用冒泡排序，时间复杂度为：
平均时间复杂度：O(square(n))
最坏时间复杂度：O(square(n)) （每一次比较都需要交换）
最优时间复杂度：O(n) （第一次循环就完成所有排序而无需进行后面的，需要判断结束条件）

Knap::Bound()计算上界剪枝需要O(n)
最坏情况下有O(Pow(2,n))个右节点，所以回溯算法的最坏时间复杂度为O(n x Pow(2,n))
跟动态规划解0-1背包的O(nc)时间复杂度相比，回溯算法的时间复杂度大得多。

Note:
剪枝函数(约束函数和上界函数)的选取是回溯法性能的关键。

分支限界法

待续…..

STL

C++里将数据结构和算法运用的比较好的就不得不提STL了。

STL

STL(标准模板库)是C++标准程序库的核心，是一个泛型程序库，利用先进，高效的算法来管理数据。

STL组件

1. 容器(Containers)
   用来管理某类对象的集合。
2. 迭代器(Iterators)
   用来在一个对象群集(Collection of objects)的元素上进行遍历动作
3. 算法(Algorithoms)
   用来处理群集内的元素。(比如搜寻，排序，修改，使用等)

“STL的基本观念就是将数据和操作分离。数据由容器类加以管理，操作则由可定制的算法定义。迭代器在两者之间充当粘合剂是的任何算法都可以和任何容器运作。”

STL将数据和算法分开对待，这和面向对象设计(OOP)的思想是矛盾的。
但这么做的好处是：
可以将各容器与各算法结合起来。

STL的特性一：
泛型，可以针对任意类型运作

Note:
“STL甚至提供更泛型化的组件。通过特定的适配器(adapters)和仿函数(functors)，你可以补充，约束或定制算法，以满足特别需求。”

容器(Containers)

容器可分为两类：

1. Sequence Containers
   “可序(ordered)群集，每个元素均有固定位置–取决于插入时机和地点，和元素值无关。”
   vector，deque，list
   Vectors特点(Vector将其元素置于一个dynamic array)：
   1. 允许随机存储。
   2. 非尾部插入会比较费时(要保持原本的相对次序，导致元素移动)
   3. 动态扩容
      Deques特点(double-ended queue是一个dynamic array，可以向两端发展)：
   4. 允许随机存储
   5. 头部和尾部插入迅速
   6. 中间部分插入费时(导致元素移动)
   7. 动态扩容
      Lists特点(doubly linked list，分散存储内存):
   8. 不提供随机存取(因为是分散存储的)
   9. 访问元素费时(沿着链表节点访问)
   10. 插入和删除快速(因为只需要改变链接点即可)
   11. 动态扩容
2. Associative Containers
   “已序(sorted)群集，元素位置取决于特定的排序准则。”
   set，multiset，map，multimap
   Sets特点:
   1. 依据值自动排序
   2. 每个元素值只允许出现一次
   3. 动态扩容
      Multisets特点：
   4. 依据值自动排序
   5. 允许重复元素
   6. 动态扩容
      Maps特点：
   7. 采用键值对存储，根据键值排序
   8. 键值不允许重复
   9. 动态扩容
      Multimaps特点：
   10. 采用键值对存储，根据键值排序
   11. 允许键值重复
   12. 动态扩容

除了上述容器，C++标准成宿还提供了一些特别的Container Adapters。
Container Adapaters：

1. Stacks
   LIFO(后进先出)
2. Queues
   FIFO(先进先出)
3. Priority Queues
   元素按优先级排序

Note:
“通常关联式容器由二叉树(binary tree)实现。”