C 程序设计例解(01)

文章作者 100test 发表时间 2007:03:10 16:54:45
来源 100Test.Com百考试题网

在程序设计过程中，类似于解决其它复杂的智力问题，我们使用推测、直觉、技巧、灵感和经验在内的各种技巧和技术，最经常使用的工具是抽象技术。一般地，在开始阶段，因还未了解问题的全部细节和求解的方法，主要问题集中于对问题的求解方案的全局作出决策，设计出大概的求解步聚，这是非常抽象的算法。其中有许多细节还不明确，只是用结构化的控制结构将若干抽象的计算步聚有机地联系起来。在抽象的计算步聚中，只是确定了计算的目标，而所指的操作对象和数据结构通常还是未确定的。以计算目标为线索，对抽象计算步聚作进一步的深入考虑，可能会引入数据结构和操作对象，并给也更详细的计算过程的描述。其中也许依旧包含有某些抽象计算步聚，但与原来的计算步聚相比，在规模及难度上已有所降低。对新产生的抽象计算步聚作进一步的深入考虑和分解，如此循序渐近，计算步聚、操作对象和数据结构会越来越明确，抽象的东西会越来越少，直至有关细节都已确定后设计过程才算结束，随后的工作是程序编码。
由此看来，程序设计的开始阶段最重要的就是确定算法和使用何种数据结构，只要这个过程完成得很好，随后的程序代码编写工作也就会很轻松了。所以学习时要从例子中得到启发，了解如何设计算法、设计数据结构、最终编出程序或函数的设计过程。

01. 试按以下给出的基数排序算法思想为整数链表编写一个排序 函数
解：
基数排序是按表元键值的各位值进行排序。
设有一个整数链表，其中表元的键值为不超过三位数的整数，不妨设键值形式ABC。其中A表示键值的百位数，B为十位数，C为个位数。首先按键值中的个位值C对链表作分拆和链接，先把链表分拆成多至10个队列链表，然后以C的值从0至9的顺序把分拆后的十个队列链表重新收集成一个链表。接着依次对键值中的B和A进行同样的分拆和链接操作，则最后收集起来的链表是按键值从小到大排序链接的。如有一个链表按它们的键值其表元的链接顺序依次为：
153 678 56 288 457 653 721 876 433 254
按它们的键值的个位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 721
2： 空链表
3： 153 653 433
4： 254
5： 空链表
6： 56 876
7： 457
8： 678 288
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
721 153 653 433 254 56 876 457 678 288