1.3 数据结构程序设计
1.3.1 数据结构程序设计步骤
一个数据结构程序用于求解一个数据结构问题，其设计的一般步骤如下。
第一步：分析求解问题的数据和求解功能，采用抽象数据类型来描述求解问题，主要包括数据逻辑结构和运算定义。
第二步：设计逻辑结构对应的存储结构。
第三步，在存储结构上设计实现运算定义的算法。
一种数据逻辑结构可以映射成多种存储结构，同一运算定义不仅在不同的存储结构上实现可以对应多种算法，而且在同一种存储结构上实现也可能有多种算法，那么哪一个算法更好呢？
从前面的介绍看出，算法的评价标准就是算法占用计算机资源的多少，占用计算机资源越多的算法就越坏，反之占用计算机资源越少的算法就越好。这是通过算法的时间复杂度和空间复杂度分析来完成的，所以设计好算法的过程如图1.22所示。
图1.22 设计好算法的过程
另外，数据结构程序设计的三个步骤是不是独立的呢？结论是这些步骤不是独立的，因为不可能设计出一大堆算法后再从中找出一个好的算法，而好的算法在很大程度上取决于描述实际问题的存储结构，也就是说必须以设计好算法为目标来设计存储结构，因为数据存储结构会影响算法的好坏，因此设计存储结构是很关键的一步，在选择存储结构时需要考虑其对算法设计的影响。
1.3.2 应用程序的结构
在设计好存储结构的基础上设计求解问题的应用程序时，应遵循结构化程序设计方法（若采用面向对象编程应遵循面向对象的程序设计方法），先提炼出基本运算功能的算法，设计出相应的函数，然后应用程序调用这些基本运算函数完成其求解问题的功能，应用程序的一般结构如图1.23所示。
图1.23 应用程序的一般结构
【例1.11】设计实现例1.4功能的完整程序。
解：设计求解本例应用程序SetApp的过程如下。
问题描述
见例1.4的抽象数据类型ASet和BSet。
设计存储结构
可以用一个整型数组存放ASet中的数据元素集合D，即单个集合的元素。由于C/C++语言中数组并没有一个标识数组中实际元素个数的值，为此用一个整型变量length表示数组中的实际元素个数，这样设计集合类型Set如下。
采用Set类型的变量存储一个集合。
设计运算算法
ASet抽象数据类型中的运算算法对应的函数如下。
BSet抽象数据类型中的运算算法对应的函数如下。
设计主函数
在所有基本运算设计好后，为了求两个集合{1，4，2，6，8}和{2，5，3，6}的并集、交集和差集，设计相关的主函数如下。
从中看到，求解本例应用程序SetApp的结构如图1.24所示，该结构清楚地反映了各种函数的调用关系。
图1.24 应用程序SetApp的结构
程序执行结果
上述程序的执行结果如下。
集合s1：1 4 2 6 8
集合s2：2 5 3 6
集合s1和s2的并集：1 4 2 6 8 5 3
集合s1和s2的差集：1 4 8
集合s1和s2的交集：2 6