algorithm - 文件、月份、模块和伪代码

Question

我正在做试卷的最后一题，但我已经迷失在算法的创建过程中。我的定义图看起来不错，但我就是无法确定计算月份方面的顺序。

题目如下:

A file of transaction records includes details such as:
- The number of customer who made a purchase in one day
- The total value of purchases made in one day
- The date of the day

Write a modularised algorithm that uses the information in this file to calculate the total number of customers for each month and the total value of purchases for each month. This information should be recorded a file.

Provide a defining diagram, an algorithm written in pseudocode, and two desk checks for this problem statement.

我不知道从哪里开始。

Answer 1

这都是关于数据结构的。

您需要读取输入流，读取日期，找到那个月的旧总数，然后将新的美元数和天数加回总数中。 (无论我在哪里说“月”，为了清楚起见，我的意思是月+年)。

一个简单的按月排列的数组可以工作，但由于月数是可变的，这将需要程序读取输入两次以查看数组范围，或者将它们全部保存在内存中，这两者都可能是不可能的。由于其他原因，它的结构很差。

下一步是链接列表，其中包含一个数据结构，其中包括月份和总计值。但这需要您查找该月份是否已出现在列表中，对于每一行输入都是 O(n)。

再上一层楼。将月份/金额保存在按月份排序(索引)的二叉树中 - 一个“排序列表”。要找到合适的月份是订单日志(输入流中的月份)，不能太大，因为即使 10 年也只有 120 个月。这样做的好处是您不必为输出报告再次对数据进行排序，这可能是他们希望您使用的。

可能最有效的结构有时被称为“字典”。矫枉过正除非你有几千个月。 http://www.dotnetperls.com/dictionary解释这个数据结构。其他环境也有类似的东西；它是标准哈希表的变体。不同的 Dictionary 类有辅助函数来告诉你值的数量、列出键、告诉你键是否已经存在等等——这些都是你需要的。您可以使用月/年作为键，使用美元数和客户数作为存储值。字典是常数时间的，所以它们是高效的(但我怀疑是矫枉过正)。