V2CE – 数据结构与算法(一)

​其实我们编程基本上就是在和数据打交道

int ,string ,GameObject等等数据类型…

数据结构是什么呢?

数据结构就是指数据的组织形式

string Str1 = "Hello";string Str2 = "Unity";Debug.Log (Str1+","+Str2);

Str1与Str2变量引用着不同的字符串.变量的顺序影响着输出结果.

但是,数据结构不仅仅用于组织数据,它极大的影响代码的速度,当我们采用合适的数据结构将会大大提高程序的运行速度,相反采用不合适的数据结构程序会被托到崩溃.一旦对于数据结构有了系统化的认知,那么你的代码将会十分优雅与高效.

• 数据结构的基础:数组

不管你学的是什么语言,第一个接触的数据结构大概率是数组,那么你真的懂数组吗?

数组,顾名思义,就是数据的组合,储存的都是同一类型的数据,在塔防游戏中,有的程序员会将敌人放入数组中.

假如,在塔防游戏中,A类防御塔只可以攻击地面的怪物,第N波敌人中有”地精”,”兽人”,”狼”这3种怪物,它们按照顺序走进了防御的攻击范围,那么,加入防御塔需要把在攻击范围内的怪物都用数组记录下来:

那么,防御塔有3种攻击模式:1.最近2.最远3.随机

如果玩家选择了最近,防御塔又如何知道离他最近的是”地精(Clone)”呢?

我们会用索引来表示每个怪物在数组中的位置

若想分析某个数据结构的性能,首先得分析程序是怎么操作这一数据的.

对于数据而言,操作的方法有:”读取”,”查找”,”插入”,”删除”.研究这4种操作的运行速度,即完成操作需要几步,这就有点像”把大象装冰箱”的问题了.

“完成这个操作需要几步”这是一个十分重要的判断方法,PS:后续会对这些做一个详细展开说明(大O计步发,算法等).

当你在unity中声明了一个长度为3数组,unity会在内存中开辟一个连续空间来存放你声明的数组,即使数组里面什么都没有,但是这3个空间是留给你的数组的.

每个数组的元素在内存中都有序号,假设下图中红色的部分是留给上面说的长度为3的数组的.

• 读取:因为在数组中每个数据有一个下标,且数组在内存中有地址,所以当我们需要找这个数组中下表为1的数据的时候,程序会直接跳到该索引并获取存在此处的值.不管你的数组长度是3还是300,查找就是一步到位.剧透一下,记下步骤数的就是大O记步法.这个后面再说.
• 查找:如果我们要查找”狼(Clone)”这条数据,我们一眼就可以看到,是在数组的最后方,但是程序没有眼,看不到,只能一个一个的去比对,那么像在最后的这种情况,我们称之为最坏的情况,也就是说你数组有多长就要比较多少次.
• 插入:当需要在数组中插入一个数据的时候,比如我们要在数组的开头插入一个数据

那么会看到所有的元素都向后移了一位,一个长度为N的数组,在数组开头插入一条数据,那么程序所执行的步骤是,向后移动了N个步骤,插入操作1个步骤,一共的步骤是N+1.
如果是在最后插入一条数据则不需要N步骤向后移动的步骤,直接可以在最后增加.

• 删除:删除和插入是差不多的操作,比如我要在最后删除一个数据,那么只需要删除这一个步骤就完成了,加入我删除的是第一个数据,那么需要的就是删除+N步骤的数据向前移动了.
• 数据结构的基础:集合

这里说的集合是List<T>.

集合,它是一种不能有重复数据的数据结构,它的这点特性决定了它与数组的区别,也就是说,这是它唯一与数组不一样的地方.所以在”读取”,”查找”,”插入”,”删除”就有一点不同

读取:这与数组一样 ,都是一步到位

查找:这与数组一样,都需要一个一个的比对

插入:由于集合的特性,在插入之前需要判断在已知的集合里面有没有这个数据,假如插入的数据在第一位,但是这个相同数据在末尾,那么首先就是N步的查找.如果末尾的和要插入的不一样,那么就是N+1步骤才能完成操作.

删除:和插入是一样的,都是首先要看是不是有相同的元素

总结

通过讲解了数组与集合的数据结构,分析程序的操作步骤(也就是性能),采用合适的数据结构,决定你的程序是承受压力还是崩溃.

不同的数据结构有不同的时间复杂度(上面所说的步骤数),那么就可以使用数据结构对比各种算法,找出性能最优的.这将是后续文章讲解的.