算法趣事·数组01

龚老师带你玩转编程世界！《算法趣事》。

一、背景

一、最简单的数据结构

通过某个已观察出的条件，利用特定规律得出中间推论，然后逐步递推直至得出结论。一步一步，123递推算法，你掌握原理了吗？再深入攻克递推算法之前，有必要学习种最基本最常见的数据结构——数组。【题外话，链表和数组相爱相杀多年，在此埋个彩蛋。】

编程世界中，如果算法是内功的话，数据结构便是招式了。合理运用数据结构将会起到四两拨千斤的妙处，今天来学习第一招式数组，一定要高度重视！

目前我们只需知道数据结构是计算机存储、组织数据的方式，好比你也能在不清楚大脑记忆结构的情况下完成数学题目。我们暂且不深究数据结构到底是什么，把好戏留在后头。先来看看，计算机“记忆”——内部存储的工作原理。

二、入秋，收拾夏装咯

秋分在仲秋，早晚凉悠悠。天气渐凉，小明把妈妈一起把夏装收拾起来，需要把衣服存在柜子里，柜子里有很多个抽屉。每个抽屉可以放一捆衣物，小明收拾出了一捆衣服，一捆裤子，因此问妈妈要两个抽屉。

好了，小明大致实现了计算机内存的工作原理。计算机里头就像很多抽屉的集合体，每个抽屉都有对应的地址。

小明把衣物塞进柜子前，需要先征求妈妈的意见，否则妈妈绝对不会允许随意塞满柜子这种乱糟糟的现象发生。我们在将数据存储到内存中时，也要请求计算机给我们提供存储空间，就像妈妈说：“放到柜子最上排第二个抽屉”一样，计算机给我们一个存储地址。

【那么你再想想，妈妈允许衣服、裤子挨着放。会允许衣服、零食、球鞋挨着放吗？妈妈整理衣物的做法就像数组！】

三、原理过渡——数组

数组是内存中开辟的一段连续的空间，并会在此空间存放元素。特点如下：1.存放的元素类型【数据类型】相同。2.数组长度固定。3.角标查询，速度快。4.增删慢。

之前例题中有定义变量的操作，int a=10；【把10赋值给整型变量a】，假如需要100个，999个整型变量改怎么办？难道还是耐着性子逐个单独定义吗？别逗了，用我们刚刚介绍的数组吧。

例如int a[10]； 定义一个整型数组a，此数组共能存放10个整型变量，分别是a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]，还有a[10]吗？注意了，c++中数组从0开始，当然学习pascal的同学a：array[1..10]of integer;思想是一样的，写法另当别论了。

四、小试牛刀

练练手，输入十个数字，逆序输出。

小提示：定义数组和定义其它数据类型的变量一样，必须先定义再使用。【为了不帮倒忙礼貌的问下妈妈能不能用这个抽屉更好！】然后把数据元素一个个的放入数组之中，【别熊孩子似的挪动整个柜子，老实的一个个抽屉放吧！】一个个放？这么熟悉的操作，计算机乐意效劳。当然，小心观察申请了多大空间的数组。【申请空间，别太小，否则放不下。当然也别太大，浪费整个柜子的空间放一件衣服明显不合理！】

示例图：【输入 0 1 2 3 4 5 6 7 8 9】

代码讲解：

首先，定义整型变量 i 用作循环中的循环变量。定义整型数组a[10]，可容纳10个整型变量的数组空间。第二步，挨个输入数据，挨个操作就交给循环来做吧，想一想，循环变量为什么从0开始，到9结束呢？数组从哪个元素开始呢？a[1]还是a[0]？

最后输出数据，需要逆序输出，从最后一个元素开始输出，最后一个元素便是a[9]，循环输出到a[0]。那么循环变量又该怎么设置呢？【输出后跟着的setw(2)设置宽度，为了看起来更美观点。】

今天的数组学习告一段落，学习数组顺带回顾数组，明天来看一看升级的斐波那契数列！强调一声别在大脑里单纯的记住数组这玩意，更重要的是记住计算机内部存储，以及数组这种数据结构的设计意图——开辟连续空间用来存放同类数据。

五、最后

通过某个已观察出的条件，利用特定规律得出中间推论，然后逐步递推直至得出结论。递推算法可是在数学世界中有着举足轻重的地位，你学会了吗？