以数据结构为核心的编程方法

这是一种与过程化编程非常不同的编程思想,它不需要一个非常清晰的流程图做为程序的蓝本,也不需要做非常庞大的全局规划,只需要明确业务规则和结果的表示法。

这是一种更接近于数学方法的编程思想,先明确表示法和规则,然后按规则推演公式和定理,再应用到实际数据中。

这种方法中的数据结构,并不只是数组、链表、树和图这些具体的数据结构,也包括整数,枚举,复合结构(对象)和完全抽象表示。

这种方法中的核心实体数据结构对应的处理结构,一般来说是函数结构,在一些语言中也对象,块,lambda函数等,甚至具体代码片断。我们可以称为段。段这个名字隐含这些处理结构并不完全,它可以组合成更大的段。

让我们用一些简单的例子来说明这个方法如何解决问题。

一个小型需要一个计算找零的程序,当一个顾客使用大面额的纸币购买商品,程序需要按商品的价格计算出需要的零钱的总数,以及
每种零钱需要几张。我们假定,顾客不会使用超过100元的纸币,找零只会使用到50,20,10,5,2,1这5种纸币,且纸币的数量无限。

从最顶层来看,有这些数据需要处理:顾客提供的纸币,商品价格,各种找零的纸币和数量。它们需要满足顾客提供的纸币面额=商品价格+ 各种(找零 * 数量)的和。

这里可以发现我们还需要补充一个找零的总数,规则变化为
纸币面额 = 商品价格 + 找零的总数
找零的总数 = 各种(找零 * 数量)的和

容易看到我们似乎不能进一步分解,这里的技巧在于,需要有一些代码段的经验,能知道把一个整体分解为多个可选部分时,可以使用的几个段,其中最简单的一种是分步,它是这样

list<...> divide (... whole) {
whole -= part;
result = divide(whole);
result.append(part);
return result;
}

... 部分是段的重要特征,即它是可以组合的。

从表示法来看,它们是这样的:

int currency;
int price;
map<change_type,int> changes;  
//用这种表示法暗示了我的C++背景,但不并不影响你换用其它熟悉的等价表示法。

基于这个容易得到一个函数代码段:

map<change_type,int> calcChanges(int currency, int price); 

从另一个角度看来,涉及本方法的另一个重要方法,抽象和具体相互转换。以currency为例,它做为整数是一个抽象实体。

如果把整数看成1 + Rest,它变成了一个列表,通过一个映射函数,就可以从一个整数得到另一个列表。

当列表中有重复值时,可以通过对值的统计,得到一个值和计数的map。

对一个复杂系统,进行数据结构设计时,需要把复杂的子系统看成一个抽象的数据,使当前层次上的数据结构简化为

常见的数据结构,规避图的图,表的表,树的树等嵌套数据结构。

对数据结构的处理代码,所谓段,不必与编程语言的语句结构对应,它更像一个个patch。每个patch为程序增加一些数据结构的处理。理想的情况下,每个处理不同数据结构部份的段,可以以任意顺序组合到代码中。

原文地址:https://www.cnblogs.com/ahuangliang/p/7242950.html