菜鸟智慧系统（必做）（线性表）

[问题描述]

使用双向链表模拟快递驿站的系统运作：

+ 假设快递驿站的货架分小、中、大3种类型，容量分别为500、100、50个包裹；该快递站关联的社区人员为MAX_PERSON人（例如，限定为30人，每人唯一手机号）。非社区人员不能取件？臭外地的跑这来要包裹的是吧？

+ 驿站每天都会来一批新的包裹。包裹根据大小类型分别上对应的货架，加入对应链表表尾，并使用该货架当前可用的最小编号。用N[1]、N[2]、N[3]分别表示每天随机来的大、中、小包裹数量，保证N[i]在货架的承受能力之内。超出承受能力的包裹直接扔喽~知道题目想简单化，但也不用这么敷衍吧，还不如搞无限容量。因为这样做，每天收包裹的数量就必须取决于货架剩余容量（或者人人化身取快递超人，所有包裹当天到当天取完），反而更蠢了。

+ 包裹信息包括：包裹编号（生成的取件码，分别为1-x(小)，2-x（中）, 3-x（大））、取件人姓名、取件人手机号、包裹大小（小1、中2、大3）、到达日期。取件码难道就是个编号？我知道所有包裹的编号，岂不是能全部取了？

+ 包裹上架时，按照包裹编号从小到大的顺序排列。这点给搞忘了，直接插末尾了。算了，不管了。难道数据里的顺序和货架上真实的顺序是一一对应的？这太蠢了。

+ 包裹取出后就从对应链表中删除。用M表示每天随机来取包裹的人数，且M≤MAX_PERSON。数据里一共就30人，还能有31人来取包裹不成？就算你告诉我这样做我也不知道该怎么实现啊。

+ 包裹最多在驿站存放两天，逾期则退还寄件人（从货架上清除）。纯纯的逆天。且不说存放几天的问题，菜鸟驿站本身在未经用户允许的情况下代为存放包裹就是违法的（菜鸟驿站的盈利来自于寄件方，每件5毛左右。未经允许代存放其实是可以举报的），还擅自给人退回去了，怎么敢的啊。

+ 当一人来取包裹时，可通过提供其任一取件码或手机号查询包裹并取出该人员所有关联的包裹。这里有歧义。是可以取出所有包裹，还是需要一次全取完？我是按前者做的，因为现实中也不会规定谁必须一次全取完。

+ 设计相应的分析、统计功能（自定义），例如当天收包裹数量最多的人，当天有包裹人的平均包裹数量，一周内与其被退回的包裹数量等。统计这个干啥？准备做个成就榜，搞个快递达人徽章是吧。还是说要弄个”年度报告“感动一下客户，让客户直呼“卧槽，我一年取了这么多快递”？

+ 可根据需要做功能拓展，使得模拟系统更接近实用或在现有商用快递系统的基础上有针对性的创新（*）都按要求写出这个东西了，我觉得就没必要再拓展了。屎山再堆屎也还是屎山。从一开始严格按照这个要求就不可能写出什么正经能用的东西，再加功能也是白费。指望拿这个鬼东西碰瓷商用项目，还是离得太远了。

+ 该问题需有较好的展示性，能够演示快递收发过程。怎么展示？要不要搞个3d建模，一堆纸片小人在快递站和屏幕外边来回平移啊？莫名其妙，不知道出题人在想什么，估计自己也不清楚，觉得这样出题很有B格，很有拓展性和启发性吧。

[基本要求]

• 所有事件均随机生成 随机生成=固定事件+随机抽取，除了麻烦有什么必要吗？
• 用文件存储货架状态，所有变更均应反应在文件中。存储形式自行设计，但务必清晰、直观 文件想要清晰直观，那就excel喽~不过不管是文本文件，还是什么文件，怎样才能做到清晰直观？想象不出来，难道有一目650行的超人吗。

主要数据结构：LinkedList<>双向链表

辅助数据结构：List<>动态数组

C#提供的这些东西确实好用。不会真的有人去造轮子吧？

将包裹、社区人员、货架分别设类。模拟快递站一天的日程，在营业前收包裹，营业时间提供取包裹服务，营业后清理逾期包裹。要模拟快递收发，也就只能分阶段，手动点击推进了。总不能像p社一样，精确到以小时为单位自动推进日程吧？有那个功夫还来写这个？

对于货架上可用的包裹编号，使用List<>存储。货架上存放的包裹使用LinkedList<>存储。

当包裹上架时，从List中取出首位可用编号，将包裹添加至货架LinkedList中。

当包裹被取走或者逾期时，将其编号放回可用编号List中，将其从LinkedList中移除。

每日清理逾期包裹时，从LinkedList首位开始，循环至其末尾，对于存放超过两天的包裹，将其编号放回可用编号List中，将其从LinkedList中移除。

见附件 scripts-1 源码过长，文件过多，不予展示

不便展示，请自行测试。

当货架上有n个包裹时：

包裹上架：O(1)

包裹下架（包括取走和逾期清理）：O(n)

每日清理逾期包裹：O(n)

综合复杂度：O(n)

实际上还要考虑更多，比如可用的编号，因为是分阶段的，当天包裹取出后不会再有新包裹，所以可用的编号每天排一次序就可以了。

算术表达式求值 (必做)（栈）

[问题描述]

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#6+15*（21-8/4）#。引入表达式起始、结束符是为了方便。编程利用“运算符优先法”求算术表达式的值。

[基本要求]

（1）从键盘或文件读入一个合法的算术表达式，输出正确的结果。键盘和文件，你都给我选了，你猜我会选哪个？

（2）显示输入序列和栈的变化过程。

（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。然而大多数情况下，都是弹出一个“输入有误”了事。和那些“用户名或密码错误“一样，说了个寂寞。

（4）实现非整数的处理（*）。简单到这个星号都没必要加。

    //算法表达式
    public struct CalExpression
    {
        public const char ERROR = 'E';
        //操作数栈
        public Stack<float> nums;
        //操作符栈
        public Stack<char> opers;
        //中缀表达式
        public string expression;
    }

依次读取字符。如果是操作数，循环直到不是操作数为止，并将此区间字符串转为数字。如果是操作符，分情况讨论：如果优先级相等，说明是左右括号，消去；如果栈顶元素优先级低，符号入栈；如果栈顶元素优先级高，计算并将计算结果入栈。网上抄来的。

对于非整数的处理：这里将”.“小数点号，也视作操作数，即可实现。

    public class Calculate : MonoBehaviour
    {
        public static Calculate Ins;
        public List<Transform> contents;
        public InputField input;
        public GameObject mes;
        private void Awake()
        {
            Ins = this;
        }
        public void Cal()
        {
            ClearMessages();
            string expr;
            //默认表达式
            if (input.text.Length == 0)
                expr = "#(4.4+2*(5-4.8/2))/2+10.4/2#";
            else expr = '#'+input.text.Trim('#')+'#';
            var cal = new CalExpression(expr);
            cal.Execute();
        }

        //Mini Object Pool
        List<GameObject> ObjectPool = new List<GameObject>(64);
        private void Release(GameObject obj)
        {
            obj.SetActive(false);
            obj.transform.SetParent(null);
            ObjectPool.Add(obj);
        }
        private GameObject Get(Transform parent)
        {
            GameObject obj;
            if (ObjectPool.Count > 0)
            {
                obj = ObjectPool[0];
                obj.transform.SetParent(parent, true);
                ObjectPool.RemoveAt(0);
            }
            else
            {
                obj = Instantiate(mes, parent);
            }
            obj.SetActive(true);
            return obj;
        }
        public void AddMessage(MesType type,string str)
        {
            var obj = Get(contents[(int)type]);
            obj.GetComponent<Text>().text = str;
        }

        public void ClearMessages()
        {
            contents.ForEach(obj =>
            {
                while (obj.transform.childCount > 0)
                    Release(obj.GetChild(0).gameObject);
            });
        }
    }
    public enum MesType
    {
        Num = 0,
        Oper = 1,
        Expr = 2,
    }

    //算法表达式
    public struct CalExpression
    {
        public const char ERROR = 'E';
        //操作数栈
        public Stack<float> nums;
        //操作符栈
        public Stack<char> opers;
        //中缀表达式
        public string expression;

        public CalExpression(string _expression)
        {
            nums = new Stack<float>();
            opers = new Stack<char>();
            expression = _expression;
        }
        public float Execute()
        {
            //用来读取下一位的位置指针
            int i = 1;
            //操作次数，仅用于输出
            int count = 0;
            //1.将 # 入栈
            opers.Push('#');
            while (expression[i]!='#'||opers.Peek()!='#')
            {
                //2.如果是操作数
                if (IsNum(expression[i]))
                {
                    int index = i;
                    //index一直读到不是操作数为止
                    while(IsNum(expression[index]))
                    {
                        index++;
                    }
                    string number = expression[i..index];

                    //是操作数，却不能转换，是小数点有误
                    if(!float.TryParse(number,out float result))
                    {
                        Calculate.Ins.AddMessage(MesType.Expr, "重复的小数点");
                        return ERROR;
                    }
                    nums.Push(result);
                    i = index;
                }
                //3.如果是操作符，则与栈顶符号比较优先级，来决定是否计算
                else if (IsOper(expression[i]))
                {
                    switch (Compare(opers.Peek(), expression[i]))
                    {
                        case '<':                                                   
                        //栈顶元素优先级低：符号入栈
                            opers.Push(expression[i]);
                            i++;
                            break;
                        case '=':                                                   
                        //优先级相等：说明是栈顶的 ( 和 expression里的 ),则消去
                            opers.Pop();
                            i++;
                            break;
                        case '>':                                                   
                        //栈顶元素优先级高：计算并将计算结果入栈
                            if (!nums.TryPeek(out float opval2))
                            {
                                char warn = opers.Peek();
                                Calculate.Ins.AddMessage(MesType.Expr,$"{warn}缺少运算数");
                                return ERROR;
                            }
                            nums.Pop();

                            if(!nums.TryPeek(out float opval1))
                            {
                                char warn = opers.Peek();
                                Calculate.Ins.AddMessage(MesType.Expr, $"{warn}缺少运算数");
                                return ERROR;
                            }
                            nums.Pop();
                            //将计算结果入栈
                            float result = Caculate(opval1, opers.Peek(), opval2);
                            nums.Push(result);
                            //弹出运算符
                            opers.Pop();
                            break;
                    }
                }
                //非法字符
                else
                {
                    Calculate.Ins.AddMessage(MesType.Expr, $"含有非法字符{expression[i]}");
                    return ERROR;
                }

                //弹出消息
                count++;
                StringBuilder builder = new StringBuilder();
                builder.Append($"第{count}步 ");
                foreach (var num in nums.ToArray())
                {
                    builder.Append(num.ToString());
                    builder.Append(' ');
                }
                Calculate.Ins.AddMessage(MesType.Num, builder.ToString());
                builder.Clear();
                builder.Append($"第{count}步 ");
                foreach (var oper in opers.ToArray())
                {
                    builder.Append(oper.ToString());
                    builder.Append(' ');
                }
                Calculate.Ins.AddMessage(MesType.Oper, builder.ToString());
                builder.Clear();
                builder.Append($"第{count}步 ");
                builder.Append(expression[i..]);
                Calculate.Ins.AddMessage(MesType.Expr, builder.ToString());
            }
            //4.计算完后返回栈顶元素
            return nums.Peek();
        }

        //计算两个数的结果
        public float Caculate(float a, char oper, float b)
            => oper switch
            {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                '/' => a / b,
                _ => ERROR,
            };
        //判断是否是操作数
        public bool IsNum(char num) => ".0123456789".Contains(num);
        //判断是否是操作符
        public bool IsOper(char oper) => oper is '+' or'-' or '*' or '/' or '(' or ')' or '#';

        //比较操作符的优先级
        public char Compare(char op1, char op2)
            => op1 switch
            {
                '+' or '-' => op2 switch
                {
                    '+' or '-' or ')' or '#' => '>',
                    _ => '<'
                },
                '*' or '/' => op2 == '(' ? '<' : '>',
                '(' => op2 switch
                {
                    '+' or '-' or '*' or '/' or '(' => '<',
                    ')' => '=',
                    _ => ERROR,
                },
                ')' => op2 switch
                {
                    '+' or '-' or '*' or '/' or ')' or '#' => '>',
                    '(' => ERROR,
                    _ => ERROR,
                },
                '#' => op2 switch
                {
                    ')' => ERROR,
                    '#' => '=',
                    _ => '<',
                },
                _ => ERROR,
            };
    };

输入：(4.4+2*(5-4.8/2))/2+10.4/2

输出：10

输入：2*(1+2*(1+2*(1+2*(1+2))))

输出：62

对于长度为n的表达式：O(n)

特殊路径统计（必做)（树和图）

[问题描述]

给定一颗有N个节点（编号为1-N）的树。

两个节点a，b（a<b）之间的简单路径上若所有节点编号i均在a，b之间（a≤i≤b），则该路径可标记为特殊路径。

试统计树上一共有多少条特殊路径。统计这个有啥用？总不能又是瞎编一个概念让我求吧。

[输入格式]

+ 第一行包含一个整数N，代表节点数

+ 第二行包含N个整数p1，p2，…，pn，代表每个节点的父节点编号。若pi=0，则该节点为树的根节点

[输出数据]

输出树上一共有多少条特殊路径

[补充说明]

+ 0≤pi≤N

+ 有且仅有一个pi=0

+ 输入的图是一棵树

[样例1]

输入：

7

0 5 5 1 4 1 4

输出：

10

[样例2]

输入：

5

2 3 0 2 2

输出：

7

其中样例1的图形示例：

public class TreeNode
{
    //编号
    public int index;

    //父节点编号
    public int parentIndex;

    //父节点引用
    public TreeNode parent;

    //层级，也就是从上往下第几行
    public int Level => parentIndex==0 ? 1 : parent.Level + 1;

    public bool IsIndexIn(int n1, int n2) => index >= Mathf.Min(n1, n2) && index <= Mathf.Max(n1, n2);
}
    
public class Tree  
{    
    List<TreeNode> nodes = new List<TreeNode>();
}

建立一个树，树上每个节点都含有对其父节点的引用。检测a，b间路径是否为特殊路径的方法如下：首先找到两个节点中层较高的节点，即在树的图像中更靠近底部的节点。然后从此节点开始，不断向其父节点移动，直到与到另一个节点的层相等为止。然后两个节点轮流向各自的父节点移动，直到两者最终移动到同一个父节点为止。在每一次移动后，检测节点编号是否符合特殊路径的要求。若所有的节点都符合要求，则a，b间路径为特殊路径，否则不为特殊路径。

    public class TreeCal : MonoBehaviour
    {
        public UnityEngine.UI.InputField input;
        public UnityEngine.UI.Text text;
        public void Cal()
        {
            string str = input.text;
            Tree tree = new Tree(str);
            text.text = "特殊路径数："+tree.GetSpecialPathNum().ToString();
        }
    }

    public class Tree
    {
        List<TreeNode> nodes = new List<TreeNode>();
        public Tree(string str)
        {
            CreateTree(str.Split(' '));
        }
        private void CreateTree(params string[] nums)
        {
            for(int index=1;index<=nums.Length;index++)
            {
                var node = new TreeNode(index, int.Parse(nums[index - 1]));
                nodes.Add(node);
            }
            //直接遍历设置父节点 复杂度n^2
            nodes.ForEach(node => { if (node.parentIndex > 0) node.parent = nodes[node.parentIndex - 1]; });
        }
        public int GetSpecialPathNum()
        {
            int num = 0;
            //遍历寻找特殊路径 复杂度n^2
            for (int i = 1; i <= nodes.Count; i++)
            {
                for(int j=1;j<=nodes.Count;j++)
                {
                    if (i >= j) continue;
                    if (IsSpecialPath(nodes[i - 1], nodes[j - 1])) num++;
                }
            }
                return num;
        }
        private bool IsSpecialPath(TreeNode a,TreeNode b)
        {
            //找到层次比较深（图中更靠下边）的节点
            TreeNode highLevel = a;
            TreeNode lowLevel = b;
            if(a.Level<b.Level)
            {
                highLevel = b;
                lowLevel = a;
            }

            //靠下边的节点往上一步步走，直到与另一个节点到一个层次，如果有不符合条件的节点就返回
            while(highLevel.Level>lowLevel.Level)
            {
                highLevel = highLevel.parent;
                if (!highLevel.IsIndexIn(a.index, b.index)) return false;
            }

            //两个节点同时往上走，直到最终走到一块，如果有不符合条件的节点就返回
            while (highLevel.index!=lowLevel.index)
            {
                highLevel = highLevel.parent;
                lowLevel = lowLevel.parent;
                if (!highLevel.IsIndexIn(a.index, b.index)) return false;
                if (!lowLevel.IsIndexIn(a.index, b.index)) return false;
            }

            //能运行到这里，就说明两个节点间路径上的所有节点都符合条件，是特殊路径
            return true;
        }
    }
    public class TreeNode
    {
        //编号
        public int index;

        //父节点编号
        public int parentIndex;

        //父节点引用
        public TreeNode parent;

        //层级，也就是从上往下第几行
        public int Level => parentIndex==0 ? 1 : parent.Level + 1;
        public TreeNode(int _index,int _parentIndex)
        {
            index = _index;
            parentIndex = _parentIndex;
        }
        public bool IsIndexIn(int n1, int n2) => index >= Mathf.Min(n1, n2) && index <= Mathf.Max(n1, n2);
    }

输入：2 3 0 2 2

输出：7

遍历寻找特殊路径：O(n^2)

判断特殊路径：O(n)

公交线路提示 (必做)（图）

[问题描述]

根据真实南京公交线路图，建立南京主要公交线路图的存储结构。

[基本要求]

（1）输入任意两站点，给出转车次数最少的乘车路线。

（2）输入任意两站点，给出经过站点最少的乘车路线。

槽点比较少。唯一的槽点就是输出说明太少，只能自由发挥。

public abstract class Node
{
    public string id;
    public List<string> nexts;

    public Node(string id)
    {
        this.id = id;
        nexts = new List<string>(4);
    }
    public void AddNext(string next)
    {
        if (!nexts.Contains(next))
            nexts.Add(next);
    }
    public void AddNextRange(List<string> nextRange)
    {
        nexts.AddRange(nextRange);
    }
}
public class Stop : Node
{
    public List<string> lines;
    public Stop(string id) : base(id) { lines = new List<string>(); }
    public void AddLine(string line)
    {
        lines.Add(line);
    }
}
public class Line : Node
{
    public List<string> stops;
    public Line(string id) : base(id) { stops = new List<string>(); }
    public void AddStop(string stop)
    {
        stops.Add(stop);
    }
    public bool HasStop(string stop)
    {
        return stops.Contains(stop);
    }
}

最少站点：对站点建立邻接表（为了方便，本程序中以List<Node>形式储存），用广度优先算法从起始点开始搜索，直到发现目标站点为止。

最少转乘：对每条公交路线建立邻接表，同样用广度优先算法搜索，直到发现目标所处的路线之一为止。若起始点处在多条路线中，则选出各条路线中转乘次数最少的一条。

在搜索中，使用一个字典（本质是Hash表）。将每个搜索到的节点作为键，上一个节点作为值进行储存。于是当发现目标时，以目标作为键找到上一个节点，如此循环即可得到完整路径。将此路径压入栈中，按照一定的 输出格式依次取出内容即可。

public class NJBus : MonoBehaviour
{
    Dictionary<string, Node> stops;
    Dictionary<string, Node> lines;
    public TextAsset txt;
    public GameObject content;
    public GameObject mes;
    public InputField from;
    public InputField to;
    private void Awake()
    {
        CreateGraph();
    }
    private void Execute(System.Action<Stop, Stop> action)
    {
        ClearMessage();
        if (GetInput(out Node nodeFrom, out Node nodeTo))
            action.Invoke((Stop)nodeFrom, (Stop)nodeTo);
    }
    public void Execute_Stop()
    {
        Execute(PrintNearestByStop);
    }
    public void Execute_Line()
    {
        Execute(PrintNearestByLine);
    }
    private bool GetInput(out Node nodeFrom, out Node nodeTo)
    {
        if (from.text.Length == 0) from.text = "鼓楼医院站";
        if (!stops.TryGetValue(from.text, out nodeFrom))
        {
            AddMessage("未找到出发站点");
            nodeTo = null;
            return false;
        }
        if (to.text.Length == 0) to.text = "陆郎站";
        if (!stops.TryGetValue(to.text, out nodeTo))
        {
            AddMessage("未找到目标站点");
            return false;
        }
        return true;
    }

    private void CreateGraph()
    {
        //2022.10.27数据 507公交路线，8684个公交站点
        stops = new Dictionary<string, Node>(10000);
        lines = new Dictionary<string, Node>(1000);

        //建立站点之间的表
        string[] strings = txt.text.Split('\n');
        foreach (var stringline in strings)
        {
            CreateGraph_LoadLine(stringline);
        }

        //建立路线之间的表
        foreach (Line line in lines.Values)
        {
            line.stops.ForEach(stop => line.AddNextRange(TryGetStop(stop).lines));
            line.nexts.Distinct();
        }
    }

    private void CreateGraph_LoadLine(string stringline)
    {
        //利用正则表达式将多个空格改为逗号
        stringline = System.Text.RegularExpressions.Regex.Replace(stringline, @"\s+", ",").Trim(',');
        string[] stringnode = stringline.Split(',');

        //加入路线
        Line line = new Line(stringnode[0]);
        lines.Add(line.id, line);

        int length = stringnode.Length;
        for (int index = 1; index < length; index++)
        {
            Stop now = TryGetStop(stringnode[index]);

            line.AddStop(now.id);

            now.AddLine(line.id);

            //添加前后节点作为自己的相邻节点
            if (index - 1 > 0)
            {
                now.AddNext(stringnode[index - 1]);
            }
            if (index + 1 < length)
            {
                now.AddNext(stringnode[index + 1]);
            }
        }
    }

    private Stop TryGetStop(string id)
    {
        //尝试从字典中找到目标，没有就创建一个
        if (!stops.TryGetValue(id, out Node result))
        {
            result = new Stop(id);
            stops.Add(id, result);
        }
        return (Stop)result;
    }

    private void PrintNearestByStop(Stop start, Stop end)
    {
        //获取最少站点路径
        var target = FindNearestBFS(stops, start, stop => stop.id == end.id);

        //以下开始处理输出
        var builder = new System.Text.StringBuilder();

        var old = target.Pop();
        builder.Append(start.id);
        builder.Append("乘坐");
        AppendNowLine(start);
        builder.Append("->");

        while (target.Count > 1)
        {
            var temp = target.Pop();
            builder.Append(temp);
            bool isTrans = true;

            foreach (var (now, next) in from i in ((Stop)stops[old]).lines from j in ((Stop)stops[target.Peek()]).lines select (i, j))
            {
                if (now == next)
                {
                    isTrans = false;
                }
            }
            if (isTrans)
            {
                builder.Append("换乘");
                AppendNowLine((Stop)stops[temp]);
            }

            builder.Append("->");
            old = temp;
        }

        void AppendNowLine(Stop stop)
        {
            foreach (Line line in from linestr in stop.lines select lines[linestr])
            {
                if (line.HasStop(target.Peek()))
                {
                    builder.Append(line.id);
                    break;
                }
            }
        }
        builder.Append("到达目的地");
        builder.Append(end.id);

        AddMessage(builder.ToString());
    }

    private void PrintNearestByLine(Stop start, Stop end)
    {
        //从不同站出发，获取最少转乘路径
        List<Stack<string>> traces = new List<Stack<string>>();
        foreach (var path in start.lines)
        {
            traces.Add(FindNearestBFS(lines, (Line)lines[path], line => end.lines.Contains(line.id)));
        }
        //traces.ForEach(t => Debug.Log(t.Count));
        traces.Sort((x, y) => x.Count.CompareTo(y.Count));

        var target = traces[0];

        //以下开始输出

        var builder = new System.Text.StringBuilder();
        builder.Append("从");
        builder.Append(start.id);
        while (target.Count > 1)
        {
            var temp = target.Pop();
            builder.Append("乘坐");
            builder.Append(temp);
            foreach (var (now, next) in from i in ((Line)lines[temp]).stops from j in ((Line)lines[target.Peek()]).stops select (i, j))
            {
                if (now == next)
                {
                    builder.Append("从");
                    builder.Append(now);
                    builder.Append("换乘");
                    break;
                }

            }
            builder.Append("->");
        }
        builder.Append("乘坐");
        builder.Append(target.Pop());
        builder.Append("到达目的地");
        builder.Append(end.id);
        AddMessage(builder.ToString());
    }

    private Stack<string> FindNearestBFS(Dictionary<string, Node> dic, Node start, System.Predicate<Node> compare)
    {
        //是否已经经过
        Dictionary<string, bool> hasChecked = new Dictionary<string, bool>(dic.Count);
        //轨迹 从A搜索到相邻的B、C时，分别以B、C为键，A为值
        Dictionary<string, string> trace = new Dictionary<string, string>(dic.Count);
        foreach (var node in dic.Keys)
        {
            hasChecked.Add(node, false);
        }

        List<Node> temp = new List<Node>(dic.Count);
        List<Node> temp2 = new List<Node>(32);

        temp.Add(start);

        int num = 0;

        while (temp.Count > 0)
        {
            //找到的情况
            var find = temp.Find(compare);
            if (find is not null)
            {
                return ToPath(trace, find.id, start.id);
            }

            //搜索
            temp.ForEach(node =>node.nexts.ForEach(next =>
            {
                if (!hasChecked[next])
                {
                    hasChecked[next] = true;
                    trace.Add(next, node.id);
                    temp2.Add(dic[next]);
                }
            }));

            temp.Clear();
            temp.AddRange(temp2);
            temp2.Clear();

            num++;
            //如果经过100个站点或者100条路线还没到，那么一定是程序出了问题
            if (num > 100)
            {
                Debug.Log("循环过多");
                break;
            }
        }

        return null;
    }

    private Stack<string> ToPath(Dictionary<string, string> trace, string end, string start)
    {
        Stack<string> path = new Stack<string>();
        for (string traceStop = end; traceStop != start; traceStop = trace[traceStop])
        {
            path.Push(traceStop);
        }
        path.Push(start);
        return path;
    }

    public void AddMessage(string message)
    {
        Get(content.transform).GetComponent<Text>().text = message;
    }

    public void ClearMessage()
    {
        while (content.transform.childCount > 0)
        {
            Release(content.transform.GetChild(0).gameObject);
        }
    }

    //Mini Object Pool
    List<GameObject> ObjectPool = new List<GameObject>(64);
    private void Release(GameObject obj)
    {
        obj.SetActive(false);
        obj.transform.SetParent(null);
        ObjectPool.Add(obj);
    }
    private GameObject Get(Transform parent)
    {
        GameObject obj;
        if (ObjectPool.Count > 0)
        {
            obj = ObjectPool[0];
            obj.transform.SetParent(parent, true);
            ObjectPool.RemoveAt(0);
        }
        else
        {
            obj = Instantiate(mes, parent);
        }
        obj.SetActive(true);
        return obj;
    }
}

public abstract class Node
{
    public string id;
    public List<string> nexts;

    public Node(string id)
    {
        this.id = id;
        nexts = new List<string>(4);
    }
    public void AddNext(string next)
    {
        if (!nexts.Contains(next))
            nexts.Add(next);
    }
    public void AddNextRange(List<string> nextRange)
    {
        nexts.AddRange(nextRange);
    }
}
public class Stop : Node
{
    public List<string> lines;
    public Stop(string id) : base(id) { lines = new List<string>(); }
    public void AddLine(string line)
    {
        lines.Add(line);
    }
}
public class Line : Node
{
    public List<string> stops;
    public Line(string id) : base(id) { stops = new List<string>(); }
    public void AddStop(string stop)
    {
        stops.Add(stop);
    }
    public bool HasStop(string stop)
    {
        return stops.Contains(stop);
    }
}

输入：鼓楼医院站 陆郎站

输出：

最少站点：鼓楼医院站乘坐16路->中山北路鼓楼站换乘52路->北京东路鼓楼站换乘26路->进香河站->红庙站换乘988路->新铜花苑站->服务中心站换乘981路->闻家站->捻家站->李庄站->周村站->柏埂站->人评水库站->陆郎加油站站->陆郎派出所站->到达目的地陆郎站

最少换乘：从鼓楼医院站乘坐16路从新街口南站换乘->乘坐27路从宏运大道金源路站换乘->乘坐866路到达目的地陆郎站

输入：幕府东路站 天柱门站

输出：

最少站点：幕府东路站乘坐53路->晓庄村站->晓庄站->南砖新村站->红山路迈皋桥站->红山森林动物园站->江南公交一公司站->曹后村站->新庄广场南站换乘2路->长途东站站换乘70路->岔路口站换乘812路->金盛路站->学院路站->天地新城站->天地新城东门站->到达目的地天柱门站

最少换乘：从幕府东路站乘坐53路从迈皋桥广场站换乘->乘坐146路从岔路口站换乘->乘坐812路到达目的地天柱门站

对于n个站点/路线

O(n)

Huffman编码与解码（必做）（Huffman编码、二叉树）

[问题描述]

对一篇不少于5000字符的英文文章（source.txt），统计各字符出现的次数，实现Huffman编码(code.dat)，以及对编码结果的解码(recode.txt)。

[基本要求]

（1） 输出每个字符出现的次数和编码,并存储文件(Huffman.txt)。

（2） 在Huffman编码后，英文文章编码结果保存到文件中(code.dat)，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符‘0’和‘1’表示（*）。这个*号到底是什么意思？做了加分？

（3） 实现解码功能。我直接利用编码时的霍夫曼树去解码了。

public class HuffmanNode
{
    public char symbol;
    public int num;

    public HuffmanNode parent;
    public HuffmanNode leftChild;
    public HuffmanNode rightChild;

    //获取原编码
    public string OriginalCode
    {
        get
        {
            if (parent is null) return "";
            if (parent.leftChild is not null && this == parent.leftChild) return parent.OriginalCode + "1";
            if (parent.rightChild is not null && this == parent.rightChild) return parent.OriginalCode + "0";
            else return "";
        }
    }
    //创建父节点
    public HuffmanNode(HuffmanNode _leftChild, HuffmanNode _rightChild)
    {
        leftChild = _leftChild;
        leftChild.parent = this;
        rightChild = _rightChild;
        rightChild.parent = this;
        num = leftChild.num + rightChild.num;
    }
    //创建数字节点
    public HuffmanNode(char _sym, int _num)
    {
        symbol = _sym;
        num = _num;
    }
}

建立霍夫曼树：统计文章中各字符出现的次数，储存到各自对应字符的HuffmanNode中，然后根据次数将List中的HuffmanNode进行排序。拷贝此List。从拷贝中移出两个HuffmanNode，产生一个新的HuffmanNode作为二者父节点，此节点不对应任何字符，将新的节点放入拷贝中，排序，重复此步骤直到最终拷贝中只剩根节点为止。

编码：对于HuffmanNode，若它是父节点的左孩子，则它的霍夫曼编码为父节点的编码加上“1”，若为右孩子则加上“0”，根节点编码为空字符串。如此可迭代得到所有字符对应HuffmanNode的霍夫曼编码。逐个读取文章中的字符，将其转换成霍夫曼编码。每8位储存为一个字节，最后若不足8位则依次补上”00111……“，因为无论取此字符串的前几位，编码对应的节点都不存在对应字符。

解码：利用霍夫曼树进行解码。从根节点开始，读取字节中的每一位，若为“1”则移动到左孩子，为”0“移动到右孩子，直到左右孩子都为空，则其为叶子节点，将其对应字符输出到文本文档中，即成功解码一个字符。解码一个字符后，重新从根节点开始读取下一位Bit，直到读完为止。

public class HuffmanCode : MonoBehaviour
{
    public List<TextAsset> sources;

    public TextAsset source;

    List<HuffmanNode> charsList = new List<HuffmanNode>(64);
    Dictionary<char, string> codeDic = new Dictionary<char, string>(64);

    HuffmanNode root;

    //换文章
    public void Change(int num)
    {
        source = sources[Mathf.Clamp(num,0,sources.Count)];
        charsList.Clear();
        codeDic.Clear();
    }

    public void Execute()
    {
        Statistics();
        CreateHuffmanTree();
        WriteHuffman();
        Code();
        ReCode();
    }

    //统计各字符出现次数
    public void Statistics()
    {
        string txt = source.text;
        //字符出现的次数
        Dictionary<char, int> charsDic = new Dictionary<char, int>(64);
        foreach (var c in txt)
        {
            if (!charsDic.TryAdd(c, 1))
                charsDic[c]++;
        }
        //转换成List
        foreach (var pair in charsDic)
        {
            charsList.Add(new HuffmanNode(pair.Key, pair.Value));
        }
        //排序 升序
        charsList.Sort((a, b) => a.num.CompareTo(b.num));
    }

    //创建霍夫曼树
    public void CreateHuffmanTree()
    {
        List<HuffmanNode> tempList = new List<HuffmanNode>(charsList);
        while (tempList.Count > 1)
        {
            var min1 = tempList[0];
            var min2 = tempList[1];
            tempList.RemoveRange(0, 2);
            var parent = new HuffmanNode(min1, min2);
            tempList.Add(parent);
            tempList.Sort((a, b) => a.num.CompareTo(b.num));
        }
        root = tempList[0];
    }

    //记录字符出现次数和对应编码
    public void WriteHuffman()
    {
        if (!Directory.Exists(Application.streamingAssetsPath + "/scene5"))
        {
            Directory.CreateDirectory(Application.streamingAssetsPath + "/scene5");
        }
        var file = File.CreateText(Application.streamingAssetsPath + $"/scene5/{source.name} Huffman.txt");
        foreach (var charNode in charsList)
        {
            //利用属性递归直接得到原编码
            string code = charNode.OriginalCode;
            codeDic.TryAdd(charNode.symbol, code);
            file.WriteLine($"{charNode.symbol}:{charNode.num} {code}");
        }
        file.Dispose();
    }

    //编码
    public void Code()
    {
        List<byte> bytes = new List<byte>(1024);
        StringBuilder unit = new StringBuilder();
        string txt = source.text;
        foreach (var c in txt)
        {
            unit.Append(codeDic[c]);
        }
        //这是0和1的字符串
        string byteString = unit.ToString();
        int index = 0;
        while (index < byteString.Length / 8)
        {
            string sub = byteString.Substring(index * 8, 8);
            bytes.Add(System.Convert.ToByte(System.Convert.ToInt32(sub, 2)));
            index++;
        }
        //如果最后有空缺
        if (byteString.Length % 8 != 0)
        {
            StringBuilder sub = new StringBuilder();
            sub.Append(byteString[(index * 8)..]);
            if (sub.Length < 8) sub.Append('0');
            if (sub.Length < 8) sub.Append('0');
            while (sub.Length < 8) sub.Append('1');
            bytes.Add(System.Convert.ToByte(System.Convert.ToInt32(sub.ToString(), 2)));
        }
        var file = File.Create(Application.streamingAssetsPath + $"/scene5/{source.name} code.dat");
        bytes.ForEach(Byte => file.WriteByte(Byte));
        file.Dispose();
    }

    //解码
    public void ReCode()
    {
        var read = File.OpenRead(Application.streamingAssetsPath + $"/scene5/{source.name} code.dat");
        var binary = new BinaryReader(read);
        byte[] bytesArray = binary.ReadBytes((int)read.Length);

        int byteIndex = 0;
        int bitIndex = 0;
        HuffmanNode nowNode = root;

        var write = File.CreateText(Application.streamingAssetsPath + $"/scene5/{source.name} recode.txt");

        while (byteIndex < bytesArray.Length)
        {
            if (nowNode.leftChild is null && nowNode.rightChild is null)
            {
                write.Write(nowNode.symbol);
                nowNode = root;
            }

            int value = GetBitValue(bytesArray[byteIndex], 7 - bitIndex);
            if (value == 1) nowNode = nowNode.leftChild;
            else nowNode = nowNode.rightChild;

            bitIndex += 1;
            if (bitIndex > 7)
            {
                bitIndex -= 8;
                byteIndex += 1;
            }
        }

        read.Dispose();
        write.Dispose();
    }

    //获取字节中某一位的值（从右往左0~7）
    public int GetBitValue(byte value, int index)
    {
        byte val = (byte)(1 << index);
        return (value & val) == val ? 1 : 0;
    }
}
public class HuffmanNode
{
    public char symbol;
    public int num;

    public HuffmanNode parent;
    public HuffmanNode leftChild;
    public HuffmanNode rightChild;

    //获取原编码
    public string OriginalCode
    {
        get
        {
            if (parent is null) return "";
            if (parent.leftChild is not null && this == parent.leftChild) return parent.OriginalCode + "1";
            if (parent.rightChild is not null && this == parent.rightChild) return parent.OriginalCode + "0";
            else return "";
        }
    }
    //创建父节点
    public HuffmanNode(HuffmanNode _leftChild, HuffmanNode _rightChild)
    {
        leftChild = _leftChild;
        leftChild.parent = this;
        rightChild = _rightChild;
        rightChild.parent = this;
        num = leftChild.num + rightChild.num;
    }
    //创建数字节点
    public HuffmanNode(char _sym, int _num)
    {
        symbol = _sym;
        num = _num;
    }
}

数据和结果以文档形式储存，不便展示。

这里给出另一篇文章原文

对于有n种不同字符，的文章：

O(n^2)

排序算法比较（必做）（排序）

[问题描述]

利用随机函数产生10个样本，每个样本有50000个随机整数（并使第一个样本是正序，第二个样本是逆序），利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序、基数排序8种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序算法对不同样本所耗费的时间。

 [基本要求]

（1）原始数据存在文件中，用相同样本对不同算法进行测试；原始数据到底指啥？生成的样本么？

（2）屏幕显示每种排序算法对不同样本所花的时间；

无

以下所有算法均为升序排序。

直接插入排序：从第一个数据开始，往后挑一个数据向前插入。此时前两个数据是有序的，往后挑选一个数据向前插入，则前三个数据是有序的。以此类推，直到所有数据都是有序的。

希尔排序：对直接插入排序的改进。设定初始步长，每隔步长挑出一个数据，作为一个序列，对这个序列进行直接插入排序。缩小步长，重复此步骤，直到步长为1，对所有数据进行直接插入排序。

冒泡排序：从第一个数据开始，和后一位比较。若前者小于后者，则交换。如此最大的数被移至最后。重复此步骤，直到所有数据有序。

快速排序：从序列中挑选一个数据，将所有比它小的移动到其左边，比它大的移动到右边。于是左右产生了两个新序列，再对新序列进行此步骤，直到所有数据有序。

选择排序：挑选第一个数据，视为最小值，遍历序列，若有比它更小的值，则将更小的值视为最小值，向后比较。最后将第一个数据和最小值交换，从第二个数据开始重复进行。直到所有数据有序。

堆排序：首先建立大根堆，于是堆首是最大值，将其和堆尾互换。不考虑堆尾，重新排序此大根堆，将次大值放到堆尾。重复，直到所有数据有序。

归并排序：将序列分为两个序列，再重复划分直到每个数据都是一个序列。两两合并，合并时每次挑选最小值放入，进行排序，直到最终所有数据有序。

基数排序：首先找出最大的数，得到它的位数t。从最小位数（个位数）开始，根据每个数据的最小位数上的数字放入对应列表中。然后从最小数字的列表开始依次取出。然后进一位数，重复此步骤。循环t此，直到所有数据有序。

这个代码是有问题的。八个算法同时测试，会互相干扰。单独计算才会准确。

public class Sort8 : MonoBehaviour
{
    //消息和消息框的物件
    public GameObject mes;
    public GameObject content;

    //单个样例的尺寸与样例个数
    const int SampleSize = 50000;
    const int SampleCount = 10;

    //样例
    int[][] sample;

    //生成样本并进行测试，点击按钮时触发这个方法
    public void Execute()
    {
        GetRandomSample();
        Statistic();
    }

    //获取随机数作为样例
    private void GetRandomSample()
    {
        sample = new int[SampleCount][];
        for (int sampleIndex = 0; sampleIndex < SampleCount; sampleIndex++)
        {
            sample[sampleIndex] = new int[SampleSize];
            for (int index = 0; index < SampleSize; index++)
            {
                //从-99999到100000的随机数
                sample[sampleIndex][index] = UnityEngine.Random.Range(-100000, 100000);
            }
        }

        //使样本1为正序，样本2为逆序
        List<int> positive = new List<int>(sample[0]);
        positive.Sort((a, b) => a.CompareTo(b));
        List<int> reverse = new List<int>(sample[1]);
        reverse.Sort((a, b) => -a.CompareTo(b));
        sample[0] = positive.ToArray();
        sample[1] = reverse.ToArray();

        //保存生成的样例数据到指定文件夹
        for(int index = 0;index<SampleCount;index++)
        {
            Utility.SL.Saver.SaveSingle(sample[index], "Sample" + index, Application.streamingAssetsPath + "/scene6");
        }
    }

    //测试各个算法并弹出消息
    private void Statistic()
    {
        List<Action<int[]>> sortActs = new List<Action<int[]>>()
        {
            StraightInsertionSort,
            ShellSort,
            BubbleSort,
            QuickSort,
            SelectSort,
            HeapSort,
            MergeSort,
            RadixSort
        };
        int SortKinds = sortActs.Count;

        //测得每个算法，对应的每个样例所需时间
        List<double[]> sortTimeForEachSample = new List<double[]>(8);
        for (int sortIndex = 0; sortIndex < SortKinds; sortIndex++)
        {
            sortTimeForEachSample.Add(new double[SampleCount]);
            for (int sampleIndex = 0; sampleIndex < SampleCount; sampleIndex++)
            {
                sortTimeForEachSample[sortIndex][sampleIndex] =
                    DoSortWithSingleSample(sortActs[sortIndex], sample[sampleIndex]);
            }
        }

        //根据测试十个样例总时间，升序排序各个算法所用时间
        sortTimeForEachSample.Sort((a, b) => a.Sum().CompareTo(b.Sum()));

        //逐个输出
        foreach (var index in Enumerable.Range(0, SortKinds))
        {
            foreach(var sampleIndex in Enumerable.Range(0,SampleCount))
            {
                var m = Instantiate(mes, content.transform);
                m.GetComponent<UnityEngine.UI.Text>().text = 
                    sortActs[index].Method.Name + " SampleCount" + sampleIndex + ":" +sortTimeForEachSample[index][sampleIndex] + "ms";
            }

            //Debug.Log(sortActs[index].Method.Name + " SumTime:" + sortTimeForEachSample[index].Sum() + "ms");
            Debug.Log(sortActs[index].Method.Name + " AverageTime:" + sortTimeForEachSample[index].Sum()/SampleCount + "ms");
        }
    }

    //测量指定算法排序指定样例所用时间
    private double DoSortWithSingleSample(Action<int[]> sortAct, int[] sample)
    {
        //之前使用DateTime记录时间，也许它的精度不够
        //现在使用专用于测量时间的StopWatch库

        Stopwatch watch = new Stopwatch();
        watch.Start();

        sortAct.Invoke(sample);

        watch.Stop();

        return watch.ElapsedTicks * 1000.0 / Stopwatch.Frequency;
    }

    private void StraightInsertionSort(int[] sample)
    {
        int n = SampleSize;
        for (int i = 1; i < n; i++)
        {
            if (sample[i] < sample[i - 1])
            {
                int value = sample[i];
                int j;
                //从后往前，如果不是sample[i]应在的位置，就往后挪
                for (j = i - 1; j >= 0 && value < sample[j]; j--)
                {
                    sample[j + 1] = sample[j];
                }
                //到达sample[i]应在的位置，替换
                sample[j + 1] = value;
            }
        }
    }

    private void ShellSort(int[] sample)
    {
        int n = SampleSize;
        //步长，每次循环减半。
        int gap;
        for (gap = n / 2; gap > 0; gap /= 2)
        {
            // 共gap个组，每组直接插入排序
            for (int i = 0; i < gap; i++)
            {
                for (int j = i + gap; j < n; j += gap)
                {
                    // 如果sample[j] < sample[j-gap]，寻找sample[j]位置，后面数据都后移。
                    if (sample[j] < sample[j - gap])
                    {
                        int temp = sample[j];
                        int k;
                        for (k = j - gap; k >= 0 && sample[k] > temp; k -= gap)
                        {
                            sample[k + gap] = sample[k];
                        }
                        sample[k + gap] = temp;
                    }
                }
            }
        }
    }

    private void BubbleSort(int[] sample)
    {
        int temp;
        int n = SampleSize;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - 1; j++)
            {
                if (sample[j] > sample[j + 1])
                {
                    //交换
                    temp = sample[j];
                    sample[j] = sample[j + 1];
                    sample[j + 1] = temp;
                }
            }
        }
    }

    private void QuickSort(int[] sample)
    {

        int Sort(int[] arr, int left, int right)
        {
            // 哨兵划分操作（以 arr[left] 作为基准数）
            int i = left, j = right;

            int temp;

            while (i < j)
            {//注意：以下两个while循环的顺序不能反，一旦选用左边界作为基准值，那么就必须先从右边开始遍历
                while (i < j && arr[j] >= arr[left]) j--;
                while (i < j && arr[i] <= arr[left]) i++;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            //循环结束
            temp = arr[i];
            arr[i] = arr[left];
            arr[left] = temp;

            return i;
        }

        //使用栈记录每次划分后的左右位置，以代替迭代
        Stack<Vector2Int> stack = new Stack<Vector2Int>();

        int left = 0;
        int right = sample.Length - 1;
        if (left < right)
        {
            int pivot = Sort(sample, left, right);
            if (pivot - 1 >= left)
            {
                stack.Push(new Vector2Int(left, pivot - 1));
            }
            if (pivot + 1 <= right)
            {
                stack.Push(new Vector2Int(pivot + 1, right));
            }
            while (stack.Count > 0)
            {
                Vector2Int record = stack.Pop();
                pivot = Sort(sample, record[0], record[1]);
                if (pivot - 1 >= record[0])
                {
                    stack.Push(new Vector2Int(record[0], pivot - 1));
                }
                if (pivot + 1 <= record[1])
                {
                    stack.Push(new Vector2Int(pivot + 1, record[1]));
                }
            }
        }

    }

    private void SelectSort(int[] sample)
    {
        int n = sample.Length;
        for (int i = 0; i < n; i++)
        {
            int min = sample[i];
            for (int j = i + 1; j < n; j++)
            {
                if (min < sample[j]) continue;
                int temp = min;
                min = sample[j];
                sample[j] = temp;
            }
        }
    }

    private void HeapSort(int[] sample)
    {

        HeapInsert(sample);
        int n = sample.Length;
        while (n > 1)
        {
            //固定最大值
            int temp = sample[0];
            sample[0] = sample[n - 1];
            sample[n - 1] = temp;
            n -= 1;
            //构造大根堆
            Heapify(sample, 0, n);
        }

        //构造大根堆（通过新插入的数上升）
        void HeapInsert(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
                //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
                while (array[currentIndex] > array[fatherIndex])
                {
                    //交换当前结点与父结点的值
                    int temp = array[currentIndex];
                    array[currentIndex] = array[fatherIndex];
                    array[fatherIndex] = temp;
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        //将剩余的数构造成大根堆（通过顶端的数下降）
        void Heapify(int[] array, int index, int size)
        {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size)
            {
                int largestIndex;
                //判断孩子中较大的值的索引（要确保右孩子在size范围之内）
                if (array[left] < array[right] && right < size)
                {
                    largestIndex = right;
                }
                else
                {
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值，并确定最大值的索引
                if (array[index] > array[largestIndex])
                {
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
                if (index == largestIndex)
                {
                    break;
                }
                //父结点不是最大值，与孩子中较大的值交换
                int temp = array[largestIndex];
                array[largestIndex] = array[index];
                array[index] = temp;
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
        }
    }

    private void MergeSort(int[] sample)
    {
        int n = sample.Length;
        int[] p = new int[n];
        mergesort(sample, 0, n - 1, p);

        void mergesort(int[] a, int first, int last, int[] temp)
        {
            if (first < last)
            {
                int mid = (first + last) / 2;
                mergesort(a, first, mid, temp);    //左边有序
                mergesort(a, mid + 1, last, temp); //右边有序
                mergearray(a, first, mid, last, temp); //再将二个有序数列合并
            }
        }

        //将有二个有序数列a[first...mid]和a[mid...last]合并。
        void mergearray(int[] a, int first, int mid, int last, int[] temp)
        {
            int i = first, j = mid + 1;
            int m = mid, n = last;
            int k = 0;

            while (i <= m && j <= n)
            {
                if (a[i] <= a[j])
                    temp[k++] = a[i++];
                else
                    temp[k++] = a[j++];
            }

            while (i <= m)
                temp[k++] = a[i++];

            while (j <= n)
                temp[k++] = a[j++];

            for (i = 0; i < k; i++)
                a[first + i] = temp[i];
        }
    }

    private void RadixSort(int[] sample)
    {
        List<int> list = new List<int>(sample);
        int maxValue = list.Max();
        int minAbsValue = Mathf.Abs(list.Min());

        //需要循环几次9-1 99-2 999-3
        int it = 0;

        List<List<int>> buckets = new List<List<int>>(10);//分10个列表对应0-9
                                                          //列表初始化大小
        for (int i = 0; i < 10; i++)
        {
            buckets.Add(new List<int>());
        }

        while (Math.Pow(10, it) <= maxValue)
        {
            //入桶
            for (int i = 0; i < list.Count; i++)
            {
                //989 it=0 989/10^it=989 989%10=9;
                int digit = (int)(((list[i] + minAbsValue) / Math.Pow(10, it)) % 10);
                //得到对应列表
                buckets[digit].Add(list[i]);
            }
            //清除list
            list.Clear();
            //依次取出来
            for (int i = 0; i < buckets.Count; i++)
            {
                list.AddRange(buckets[i]);
            }
            it += 1;

            //清除列表，继续下一次循环
            buckets.ForEach(bucket => bucket.Clear());
        }
    }
}

数据过多，不变展示。这里仅展示测试时间。

平均时间
插入排序 547.70204ms
希尔排序 4.33829ms
气泡排序 4217.20727ms
快速排序 137.94294ms
选择排序 2576.35584ms
堆排序 4.86773ms
归并排序 3.94078ms
基数排序 17.34571ms

插入排序 O(n^2)
希尔排序 O(n^1.3)～O(n^2)
气泡排序 O(n^2)
快速排序 平均O(nlogn)
选择排序 O(n^2)
堆排序 O(nlog n)
归并排序 O(nlog n)
基数排序 O(d(n+k)) 于此位数d = 6而种类数k = 10

火车购票 (选做)（线性表）

[问题描述]

请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。

假设一节车厢有20排、每一排5个座位。为方便起见，我们用1到100来给所有的座位编号，第一排是1到5号，第二排是6到10号，依次类推，第20排是96到100号。

购票时，一个人可能购一张或多张票，最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中（不考虑是否相邻）。

假设初始时车票全部未被购买，现在给了一些购票指令，请你处理这些指令。

[输入格式]

对于所有评测用例，1 ≤ n ≤ 100，所有购票数量之和不超过100。

输入的第一行包含一个整数n，表示购票指令的数量。

第二行包含n个整数，每个整数p在1到5之间，表示要购入的票数，相邻的两个数之间使用一个空格分隔。

[输出格式]

输出n行，每行对应一条指令的处理结果。

对于购票指令p，输出p张车票的编号，按从小到大排序。

[样例]

输入：

4

2 5 4 2

输出：

1 2

6 7 8 9 10

11 12 13 14

3 4

其实只用数组就能完成。但如果这样我写这题干什么呢？我总得给自己留下点代码资产，否则写这个就是纯浪费时间。

    private class LinkedStack<T>
    {
        Stack<T> stack;
        int maxSize;

        public LinkedStack<T> last;
        public LinkedStack<T> next;
        public int Count => stack.Count;
        public LinkedStack(int capacity)
        {
            maxSize = capacity;
            stack = new Stack<T>(maxSize);
        }
        public void Push(T obj)
        {
            if(stack.Count==maxSize)
            {
                next.Push(obj);
            }
            else
            {
                stack.Push(obj);
            }
        }
        public T Pop()
        {
            if (stack.Count == 0)
            {
                return last.Pop();
            }
            else
            {
                return stack.Pop();
            }
        }
    }

    private class LinkedStackList<T>
    {
        LinkedStack<T> start;
        LinkedStack<T> end;
        int length;
        public LinkedStackList(int length, int eachSize)
        {
            this.length = length;
            start = new LinkedStack<T>(eachSize);
            LinkedStack<T> past = start;
            LinkedStack<T> now = start;
            foreach (var i in Enumerable.Range(0, length-1))
            {
                now = new LinkedStack<T>(eachSize);
                now.last = past;
                past.next = now;
                past = past.next;
            }
            end = now;
        }

        public void Push(T obj)
        {
            start.Push(obj);
        }
        public T Pop()
        {
            return end.Pop();
        }
        public T[] PopNear(int count)
        {
            T[] result = new T[count];

            var temp = end;

            int index = length;

            while(index>0)
            {
                if (temp.Count >= count)
                {
                    return Pop(temp);
                }
                else
                {
                    temp = temp.last;
                    index--;
                }
            }

            return Pop(end);

            T[] Pop(LinkedStack<T> linked)
            {
                foreach (var i in Enumerable.Range(0, count))
                    result[i] = linked.Pop();
                return result;
            }
        }
    }

建立一种数据结构，每个栈都连接到其上一个和下一个栈。当栈的数量不足以Pop时，从上一个栈Pop。当栈的容量不足以Push时，Push到下一个栈中。

首先将100个数倒序压入栈中，然后从栈尾开始取出。当取出n张票时，若栈尾数量>=n则取出，不足则对上一个栈进行相同操作。当达到栈首，若仍无法取出，则从栈尾取出。

public class TrainCal : MonoBehaviour
{

    public Transform content;
    public GameObject mes;
    public InputField input;

    public void Cal()
    {
        ClearMessages();

        string[] txt = input.text.Split(' ');

        var nums = GetIntArray(txt);

        if (nums is null) return;

        Execute(nums);

    }

    public int[] GetIntArray(string[] txt)
    {
        int[] nums = new int[txt.Length];
        int index = 0;
        foreach (var num in from str in txt select int.Parse(str))
        {
            if(num >=1 && num<=5)
            {
                nums[index++] = num;
            }
            else
            {
                AddMessage("每次输入的数应在1~5，已超出范围");
                return null;
            }
        }

        if(nums.Sum()>100)
        {
            AddMessage("总数超过100，错误");
            return null;
        }

        return nums;
    }

    public void Execute(int[] nums)
    {
        LinkedStackList<int> list = new LinkedStackList<int>(20, 5);
        foreach (var num in Enumerable.Range(1,100).Reverse())
        {
            list.Push(num);
        }
        foreach (var num in nums)
        {
            AddMessage(string.Join(' ',list.PopNear(num)));
        }
    }

    public void AddMessage(string str)
    {
        var obj = Get(content);
        obj.GetComponent<Text>().text = str;
    }

    public void ClearMessages()
    {
        while(content.transform.childCount>0)
        {
            Release(content.transform.GetChild(0).gameObject);
        }

    }

    //Mini Object Pool
    List<GameObject> ObjectPool = new List<GameObject>(64);
    private void Release(GameObject obj)
    {
        obj.SetActive(false);
        obj.transform.SetParent(null);
        ObjectPool.Add(obj);
    }
    private GameObject Get(Transform parent)
    {
        GameObject obj;
        if (ObjectPool.Count > 0)
        {
            obj = ObjectPool[0];
            obj.transform.SetParent(parent, true);
            ObjectPool.RemoveAt(0);
        }
        else
        {
            obj = Instantiate(mes, parent);
        }
        obj.SetActive(true);
        return obj;
    }

    private class LinkedStack<T>
    {
        Stack<T> stack;
        int maxSize;

        public LinkedStack<T> last;
        public LinkedStack<T> next;
        public int Count => stack.Count;
        public LinkedStack(int capacity)
        {
            maxSize = capacity;
            stack = new Stack<T>(maxSize);
        }
        public void Push(T obj)
        {
            if(stack.Count==maxSize)
            {
                next.Push(obj);
            }
            else
            {
                stack.Push(obj);
            }
        }
        public T Pop()
        {
            if (stack.Count == 0)
            {
                return last.Pop();
            }
            else
            {
                return stack.Pop();
            }
        }
    }

    private class LinkedStackList<T>
    {
        LinkedStack<T> start;
        LinkedStack<T> end;
        int length;
        public LinkedStackList(int length, int eachSize)
        {
            this.length = length;
            start = new LinkedStack<T>(eachSize);
            LinkedStack<T> past = start;
            LinkedStack<T> now = start;
            foreach (var i in Enumerable.Range(0, length-1))
            {
                now = new LinkedStack<T>(eachSize);
                now.last = past;
                past.next = now;
                past = past.next;
            }
            end = now;
        }

        public void Push(T obj)
        {
            start.Push(obj);
        }
        public T Pop()
        {
            return end.Pop();
        }
        public T[] PopNear(int count)
        {
            T[] result = new T[count];

            var temp = end;

            int index = length;

            while(index>0)
            {
                if (temp.Count >= count)
                {
                    return Pop(temp);
                }
                else
                {
                    temp = temp.last;
                    index--;
                }
            }

            return Pop(end);

            T[] Pop(LinkedStack<T> linked)
            {
                foreach (var i in Enumerable.Range(0, count))
                    result[i] = linked.Pop();
                return result;
            }
        }
    }

}

输入：3 4 1 2 1 5 3 5 2 1

输出：

1 2 3

6 7 8 9

4

11 12

5

16 17 18 19 20

13 14 15

21 22 23 24 25

26 27

10

可以使用LinkedList<Stack>代替。

通信管理系统（选做）（图）

[问题描述]

你负责管理一个计算机通信系统。

有n台计算机接入了该系统，编号为1~n，它们之间可以互相发送数据。

由于设备条件限制，机器之间不能任意多地发送数据。每两台机器之间均有一个“每日可用额度”的限制，单位为MB/day，表示这两台机器每日可以互相发送的数据量（双方各自向对方发送的数据量之和）的最大值。

最初，任意两台机器的每日可用额度均为0。为了能发送数据，机器管理者需要向你申请额度。每个申请形如u v x y的格式，表示机器u和v的每日可用额度增大x MB/day，持续y天（即从申请当天开始至申请后第y-1天内有效，从第y天开始失效）。不同申请的效果是可以叠加的。

定义每台机器的“通信主要对象”为当前时刻与该机器的每日可用额度最大的机器（如果有并列，则取其中编号最小的机器）；如果一台机器与任何机器的每日可用额度均为0，则称其为“通信孤岛”，并认为其没有“通信主要对象”；如果两台机器x和y互为“通信主要对象”，则称它们是一个“通信对”。

每天开始时，你都会先接受若干个额度申请，你需要依次处理这些申请；而后，你将接收到若干个查询某台机器的“通信主要对象”的请求；最后，你可能还希望求出此时的“通信孤岛”和“通信对”各有多少。

请你编写一段程序来实现上述任务。

[输入格式]

第一行：2个正整数n，m，表示机器数和天数。

接下来3m行，每两行描述一天中的事件，格式如下：

+ 第1行：首先是一个非负整数ki，表示当天额度申请的数量。接下来有4ki个非负整数，依次描述每一个额度申请，格式如题面中所述。

+ 第2行：首先是一个非负整数li，表示当天查询“通信主要对象”的数量。接下来有li个正整数，依次表示查询的机器编号，保证编号在[1，n]范围内。

+ 第3行：2个整数pi，qi，取值均为0或1，分别表示当天是否要查询“通信孤岛”和“通信对”的数量。其中pi=1表示需要查询“通信孤岛”的数量，pi=0表示不需要查询；qi的含义同理。

[输出格式]

对于每个查询分别输出一行，一个非负整数表示该查询的答案。

查询按照天数顺序输出，对于同一天内的查询，先按照输入顺序输出所有查询“通信主要对象”的答案，再依次输出查询“通信孤岛”和“通信对”的答案（如果当天需要查询的话）。

如果某台被查询“通信主要对象”的机器是“通信孤岛”，认为查询结果为0。

[样例]

输入：

3 3

2 1 2 2 3 1 3 3 2

1 1

0 0

1 2 3 3 1

2 1 2

0 1

0

2 1 3

1 1

输出：

3

3

3

1

2

0

1

1

public class Computer
{
    public readonly int id;
    public List<Link> links;
    public int MainTarget()
    {
        if (links.Count == 0) return 0;
        var max = links.Aggregate((i, j) => i.mb > j.mb ? i : j);
        return max.source.id == id ? max.target.id : max.source.id;
    }
    public Computer(int _id)
    {
        id = _id;
        links = new List<Link>();
    }
    public void AddLink(Link link) => links.Add(link);
}
public class Link
{
    public Computer source;
    public Computer target;
    public int mb;
    public int duration;
    public Link(Computer _source, Computer _target, int _mb, int _duration)
    {
        (source, target, mb, duration) = (_source, _target, _mb, _duration);
    }
    public bool ToNextDay() => --duration <= 0;
    public bool IsPair => source.MainTarget() == target.id && target.MainTarget() == source.id;
}

将计算机视为节点，计算机之间的通信申请视为节点间带权值的连接。查找主要通信对象，即遍历该节点上的连接，找出权值最大的一个。查找信息孤岛，即查找不存在连接的节点。查找通信对，即遍历连接，找到两端节点的主要通信对象互为对方的连接。

输入：

3 3

2 1 2 2 3 1 3 3 2

1 1

0 0

1 2 3 3 1

2 1 2

0 1

0

2 1 3

1 1

输出：

3

3

3

1

2

0

1

1

查找主要通信对象：遍历n个节点，所以是O(n) （主要通信对象在建表时已确认）

查找信息孤岛：O(n)

查找通信对：最多存在n*(n-1)/2个连接，所以是O(n^2)

连连看（选做）（图）

[问题描述]

建立一个10*20的矩形方格图，其中有10种不同的图案，每种图案个数为偶数，填满矩形方格图。

[基本要求]

（1）随机产生原始数据；

（2）输入两个位置，如果两者图案相同，并且可以用小于等于3条直线相连，即可消除该两个图案。

public class SignLayout
{
    public Sign[][] layout;
    public readonly int width;
    public readonly int height;

    public Sign Get(int row, int col) => layout[row][col];
    public Sign Get(Vector2Int location) => layout[location.x][location.y];
    public SignLayout(int width, int height)
    {
        layout = new Sign[height][];
        for (int index = 0; index < height; index++)
        {
            layout[index] = new Sign[width];
        }
        this.width = width;
        this.height = height;
    }

    public void Clear()
    {
        for (int index = 0; index < height; index++)
        {
            layout[index] = new Sign[width];
        }
    }

    public bool IsSameSign(int row1, int col1, int row2, int col2)
        => Get(row1, col1) == Get(row2, col2);

    private List<Vector2Int> GetLinkable(int row, int col)
    {
        //可以连接到的点
        List<Vector2Int> canLink = new List<Vector2Int>();
        canLink.Add(new Vector2Int(row, col));
        List<Vector2Int> finds = new List<Vector2Int>();
        //第一根线
        finds.AddRange(FindReachablePoints(row, col));
        canLink.AddRange(finds);
        finds.Clear();
        //第二根线
        canLink.FindAll(point=>Get(point)==Sign.None).ForEach(point => finds.AddRange(FindReachablePoints(point.x, point.y)));
        canLink.AddRange(finds);
        canLink = canLink.Distinct().ToList();
        finds.Clear();

        //第三根线
        canLink.FindAll(point => Get(point) == Sign.None).ForEach(point => finds.AddRange(FindReachablePoints(point.x, point.y)));
        canLink.AddRange(finds);
        finds.Clear();
        finds = null;
        canLink = canLink.Distinct().ToList();

        return canLink;
    }
    /// <summary>
    /// 某两格图案是否可以连起来
    /// </summary>
    /// <param name="row"></param>
    /// <param name="col"></param>
    /// <returns></returns>
    public bool IsCanMatch(int row1, int col1, int row2, int col2)
    {
        if (!IsSameSign(row1, col1, row2, col2)) return false;

        var linkList = GetLinkable(row1, col1);

        return linkList.Contains(new Vector2Int(row2, col2));
    }

    //寻找横竖方向上可以到达的点
    private List<Vector2Int> FindReachablePoints(int row, int col)
    {
        List<Vector2Int> result = new List<Vector2Int>();

        void Finds(int start, int end, int fix, bool isFixRow)
        {
            if (start == end) return;
            int step = start < end ? 1 : -1;
            Vector2Int location;
            for (int temp = start + step; temp != end + step; temp += step)
            {
                location = isFixRow ? new Vector2Int(fix, temp) : new Vector2Int(temp, fix);
                result.Add(location);
                if (Get(location) != Sign.None)
                {
                    break;
                }
            }
        }
        //向左
        Finds(col, 0, row, true);
        //向右
        Finds(col, width - 1, row, true);
        //向上
        Finds(row, 0, col, false);
        //向下
        Finds(row, height - 1, col, false);

        return result;
    }

    public void SetSign(int row, int col, Sign sign) => layout[row][col] = sign;

    /// <summary>
    /// 将某两格消除
    /// </summary>
    /// <param name="row"></param>
    /// <param name="col"></param>
    public void Match(int row1, int col1, int row2, int col2)
    {
        layout[row1][col1] = Sign.None;
        layout[row2][col2] = Sign.None;
    }

}

生成一对图案，检测能否消除，不能则重新生成。如此循环直到空白少于一定值为止。之后填充图案不再检测能否消除。检测能否消除：对于起始点，使用广度优先算法，重复三次。每次得到该点在横竖方向上所有可以达到的点。于是三次后得到的点即为通过三条直线可以到达的点。检测其中是否包含目标点，即能否消除。

不便展示，请自行测试。

O(n)

若要显示消除时的轨迹，可新增字典：每次搜索时，将每个搜索到的节点作为键，上一个节点作为值进行储存。则将目标点作为键可查询到轨迹上上一个点，迭代可得到完整轨迹。

电子小字典（选做）（查找）

[问题描述]

利用键树结构，建立一个微型电子字典。

[基本要求]

实现生词的加入，单词的查找、删除，修改等操作。

public class KeywordNode
{
    public readonly char key;
    public string meaning;

    public List<KeywordNode> childs;
    public KeywordNode this[char _key] => FindChildFirst(_key);
    public KeywordNode() {}
    public KeywordNode(char _key, string _meaning = default)
    {
        key = _key;
        meaning = _meaning;
        childs = new List<KeywordNode>();
    }
    public KeywordNode AddChild(KeywordNode add)
    {
        var insertIndex = childs.SkipWhile(child => child.key < add.key).FirstOrDefault();

        if (insertIndex is null)
            childs.Add(add);
        else
            childs.Insert(childs.IndexOf(insertIndex), add);

        return add;
    }
    public KeywordNode FindChildFirst(char _key) 
        => childs.Where(child => child.key.Equals(_key)).FirstOrDefault();

    public KeywordNode GetChild(char _key)
        => FindChildFirst(_key) ?? AddChild(new KeywordNode(_key, default));
}

建立节点，每个节点储存其所有子节点，节点对应的字符，以及对应单词的意思。当用户添加单词时，创建对应的节点并设置意思。查找时，从根节点开始，遍历每个所查找单词的字符，移动至对应的子节点，最终达到目标单词所处节点并输出其意思。

public class KeywordTree : MonoBehaviour
{
    public InputField inputWord;
    public InputField inputMeaning;

    KeywordNode root;
    private void Awake()
    {
        root = new KeywordNode(' ', null);
    }
    private KeywordNode FindKeywordNode(string word)
    {
        KeywordNode result = root;
        word.ToList().ForEach(symbol => result = result.GetChild(symbol));
        return result;
    }
    private void ChangeMeaning(string word,string newMeaning)
    {
        FindKeywordNode(word).meaning = newMeaning;
    }
    //以下是程序内部接口
    public void ReloadWord(string word)
    {
        Debug.Log(FindKeywordNode(word).meaning);
    }
    public void CreateWord(string word,string meaning)
    {
        ChangeMeaning(word, meaning);
    }
    public void DeleteWord(string word)
    {
        ChangeMeaning(word, default);
    }
    public void UpdateWord(string word, string newMeaning)
    {
        ChangeMeaning(word, newMeaning);
    }
    //以下是按钮接口
    public void ReloadWord()
    {
        inputMeaning.placeholder.GetComponent<Text>().text = FindKeywordNode(inputWord.text).meaning;
    }
    public void CreateWord()
    {
        ChangeMeaning(inputWord.text, inputMeaning.text);
        inputWord.text = "";
        inputMeaning.text = "";
    }
    public void DeleteWord()
    {
        ChangeMeaning(inputWord.text, default);
        inputWord.text = "";
        inputMeaning.text = "";
    }
    public void UpdateWord()
    {
        ChangeMeaning(inputWord.text, inputMeaning.text);
        inputWord.text = "";
        inputMeaning.text = "";
    }
}
public class KeywordNode
{
    public readonly char key;
    public string meaning;

    public List<KeywordNode> childs;
    public KeywordNode this[char _key] => FindChildFirst(_key);
    public KeywordNode() {}
    public KeywordNode(char _key, string _meaning = default)
    {
        key = _key;
        meaning = _meaning;
        childs = new List<KeywordNode>();
    }
    public KeywordNode AddChild(KeywordNode add)
    {
        var insertIndex = childs.SkipWhile(child => child.key < add.key).FirstOrDefault();

        if (insertIndex is null)
            childs.Add(add);
        else
            childs.Insert(childs.IndexOf(insertIndex), add);

        return add;
    }
    public KeywordNode FindChildFirst(char _key) 
        => childs.Where(child => child.key.Equals(_key)).FirstOrDefault();

    public KeywordNode GetChild(char _key)
        => FindChildFirst(_key) ?? AddChild(new KeywordNode(_key, default));
}

增加：

Apple 苹果

App 应用程序

UFO 不明飞行物

Nut 坚果

修改：

Apple 苹果，苹果树

删除：

Nut

查询：

UFO 不明飞行物

Apple 苹果，苹果树

Nut （无）

O(n)

目前使用动态数组储存子节点，每次查找子节点需要遍历此动态数组。使用字典（哈希表）储存可以减少所用时间。