数据结构与算法报告

合肥学院。

计算机科学与技术系。

课程设计报告。

2011 ～2012 学年第二学期。

20 12年 6 月。

一，题目。

1．名称：幸运数组。

2．内容：doraemon有一个幸运数字k, 并且对于一个数组，若其和能被k整除，则称该数组为幸运数组。现在他想知道，给定一个长度为n且由正整数构成的数组，它有多少个子数组为幸运数组呢？

其中，子数组的定义为a[i:j](即a[i] ,a[i + 1], a[j], 其中1 <=i <=j <=n)。

二，问题分析。

此程序需要完成如下要求：

1．输入：输入的第一行有2个整数n和k(1 <=n <=50,000, 1 <=k <=1,000,000,000),分别代表数组的长度和幸运数字，接下来的一行有n个正整数ai(1 <=i <=n, 1 <=ai <=1,000,000,000), 代表数组的元素。

2．输出：输出的一个数字，代表存在的幸运子数组的个数。

3．所设计的数据结构应尽可能节省存储空间。

4．程序的运行时间应尽可能少。

即在保证时间和空间复杂度的情况下，输入幸运数字以及某个数组，程序需要得出所有的幸运数组的个数。

实现本程序需要解决一下几个问题：

1．采用何种的数据存储结构来存储输入信息，因为本程序需要查找所有的子数组，数据存储结构需要能很方便的查到每个数组元素。首先想到的便是顺序表存储和链表存储。但因为链表不支持随机访问，在此顺序表存储最好。

2．采用什么方法将得到所有的子数组，幸运数组是子数组能被幸运数整除的数组，我们的目的是得到所有幸运数组的个数。

首先必须得到所有的子数组，来进行判断，是否为幸运数组。刚刚开始，想到方法是先查找只有一个元素的子数组，然后再到两个元素的子数组，乃至到n个元素的子数组。

但是采用这个方法需要3层for循环嵌套，时间复杂度过高，所以不采用。现在采用的方法是：首先找到所有以a1为第一个元素的子数组，然后查找所有以a2为第一个元素的子数组……到最后，查找所有以an为第一个元素的子数组，这种方法只需要2层for循环的嵌套，时间复杂度相对前一种，得到减少，在每次得到的子数组的时候，领用一个累加量进行累加，用于判断是否为幸运数字。

即如表一。

表一。三，数据结构的选择和概要设计。

由问题分析，我决定使用顺序表进行数据的存储。所以需要定义顺序表。

首先定义一个recordlist的顺序表，其中包括a[maxlen](储存数据)，n（记录数组的长度）。然后依次查找各个子数组，进行累加，并判断是否为幸运数组。详见各个函数流程图。

主函数流程图（图一）

数组元素输入函数流程图（图二）

子数组查找函数流程图（图三）

四，算法思想。

对于此程序，我们最主要的就是寻找各个子数组。此程序的所采用的方法为：固定子数组的第一个元素，然后查找以这个元素为首元素的所有子数组。

然后再换下一个元素作为首元素，再次查找，一直将所有的子数组全部查找出来。

首先以a1为子数组的第一个元素，则依次查找的子数组为a1，a1 a2，a1 a2 a3，……a1 a2……an。然后以a2为子数组的第一个元素，则依次查找的子数组就为a2，a2 a3，……a2 a3……an。一直到最后将an作为子数组的第一个元素进行查找。

五，详细设计和主要编码段。

1.顺序表的定义。

顺序表中定义一个数组，进行数据的存储，另外加上一个n，用于记录数组的长度。

typedef struct

int a[maxlen];

int n;

}recordlist;

2.数组的输入。

数组输入比较简单，首先需要申请空间。

l=(recordlist *)malloc (sizeof (recordlist));

然后利用for循环进行依次输入。

for (i=1;i<=l->n;i++)

scanf ("d",&l->a[i]);

3．幸运数组的查找。

根据之前所说的思路，可以用两个for循环得到所需子数组，在之前，定义一个累加量add，以及标志量flag记录幸运数组的个数。在每次得到子数组即开始累加。用于与幸运数k进行取余判断是否是幸运数组。

第一个for语句由于确定子数组的第一个元素，比如先当i为1时，就是确定a[1]为子数组的第一个元素，用于查找以a[1]为第一个元素的所有子数组。

第二个for语句有于确定该子数组的最后一个元素。因为在一轮查找中，前一个子数组与后一个子数组的区别就是多了一个元素，该元素也是前子数组的元素往后加了一个。比如，以a[2]为第一个元素，则查找的子数组就为a[2],a[2] a[3],a[2] a[3] a[4],…

在循环中，依次累加，用于记录各个子数组的元素总和。因为子数组的关系，后一个子数组的总和等于前一个子数组的总和加上一个a[i]。所以在add赋值可以为本身加上a[i](a[i]为子数组的增加的那个元素)。

同时，在得到总和之后，就需要判断是否为幸运数组。用add与幸运数k取余，判断余数是否是0。如果为0，该子数组就为幸运数组，标志量flag就加上1，记录幸运数组的个数。

如果不是0，则进行下组子数组的判断。

for (i=1;i<=l->n ;i++)

六，上机调试情况记录。

语法错误及修改：本算法较为简单利用了顺序表，然后就是for循环语句。在语法上面，主要就是遇到小问题，比如就是分号不是使用英文输入法输入，导致编译就出现问题。

还有就是for语句的范围确定，开始时对于第二个for语句的范围确定出现错误。

经验和体会：初拿到题目，似乎觉得很简单，但是经过考虑，本题目并没有考什么实际问题的模型化问题，主要的就是考虑算法的设计，来减少时间复杂度。但其实本程序还有待改进，因为现在的时间的复杂度还比较高。

这个也激励我，让我知道我要学的还很多，我还需要努力学习。

七，测试用例、结果及其算法性能分析。

1.测试用例。

测试数据一。

测试数据二。

2.算法性能分析。

本算法的空间算法度比较第，因为只需要一个n长度的数组，因此空间复杂度度就为o（n）。但是时间算法较高，因为需要寻找子数组，采用两个for语句，所以时间度就为o（n*n）。所以本程序在时间复杂度方面存在一定缺陷。

八，用户使用说明。

本程序运行过程时带有提示性语句。用户可以根据提示进行数据的输入。比如“输入数组的元素个数(1 <=n <=50,000)和幸运数(1 <=k <=1,000,000,000) ：

用户此时就可以提示进行输入数组的个数，即数组长度和幸运数。其他的情况依旧类似，程序会给予提示。

九，参考文献。

1] 王昆仑，李红。数据结构与算法。北京：中国铁道出版社。 2011

2] 王昆仑，李红。数据结构与算法实验指导。 2012

一十，附录（完整源程序）

#include <>

#define maxlen 5000

typedef struct

int a[maxlen]; 工作单元 */

int n; /n 为顺序表的长度 */

recordlist;

recordlist * enter (int n幸运数组的输入。

int i;

recordlist *l;

l=(recordlist *)malloc (sizeof (recordlist));

//申请空间。

l->n =n;

printf ("将数组输入(1 <=ai <=1,000,000,000)：");

for (i=1;i<=l->n;i++)将数据输入到顺序表中。

scanf ("d",&l->a[i]);

return (l);

void search (recordlist *l,int k)

int flag=0; /定义一个标志量记录幸运数组的个数。

int i,j,add;

printf ("幸运数组：");

for (i=1;i<=l->n ;i++)查找所有子数组。

if (flag ==0)

printf ("无");

printf ("幸运数组的个数：%d",flag); 输出幸运数组个数。

void main ()

int k,n;

recordlist * l;

printf ("输入数组的元素个数(1 <=n <=50,000)和幸运数(1 <=k <=1,000,000,000) ");

scanf ("d%d",&n,&k); 数组的个数n和输入幸运数。

while (n<1 ||n>5000 ||k<1 ||k>1000000000)

l=enter (n); 数组的输入。

printf ("n");

search (l,k);

数据结构与算法报告

数据结构与算法实习报告

数据结构与算法

算法与数据结构

其他用户还读了