C++程序设计例解(01)
在程序设计过程中，类似于解决其它复杂的智力问题，我们使用推测、直觉、技巧、灵感和经验在内的各种技巧和技术，最经常使用的工具是抽象技术。一般地，在开始阶段，因还未了解问题的全部细节和求解的方法，主要问题集中于对问题的求解方案的全局作出决策，设计出大概的求解步聚，这是非常抽象的算法。其中有许多细节还不明确，只是用结构化的控制结构将若干抽象的计算步聚有机地联系起来。在抽象的计算步聚中，只是确定了计算的目标，而所指的操作对象和数据结构通常还是未确定的。以计算目标为线索，对抽象计算步聚作进一步的深入考虑，可能会引入数据结构和操作对象，并给也更详细的计算过程的描述。其中也许依旧包含有某些抽象计算步聚，但与原来的计算步聚相比，在规模及难度上已有所降低。对新产生的抽象计算步聚作进一步的深入考虑和分解，如此循序渐近，计算步聚、操作对象和数据结构会越来越明确，抽象的东西会越来越少，直至有关细节都已确定后设计过程才算结束，随后的工作是程序编码。
由此看来，程序设计的开始阶段最重要的就是确定算法和使用何种数据结构，只要这个过程完成得很好，随后的程序代码编写工作也就会很轻松了。所以学习时要从例子中得到启发，了解如何设计算法、设计数据结构、最终编出程序或函数的设计过程。
------------------------------------------------------------------------------------------
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
再按它们键值的十位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 空链表
2： 721
3： 433
4： 空链表
5： 153 653 254 56 457
6： 空链表
7： 876 678
8： 288
9： 空链表
顺序将它们收集在一起后，链表的键值顺序有：
721 433 153 653 254 56 457 876 678 288
再按它们键值的百位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 56
1： 153
2： 254 288
3： 空链表
4： 433 457
5： 军分区边表
6： 653 678
7： 721
8： 876
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
56 153 254 288 433 457 653 678 721 876
这是一个按键值从小到大链接的链表。
基数排序主要包含以下控制过程，主循环控制对键值顺序从低位高位的重复操作，在主循环内包含两个计算步聚：按键值的当前位置分拆链表为十个队列链表，将对应0至9的十个队列链表收集成一个链表。用算法形式描述其计算过程如下：
算法--基数排序
{
依次对键值的个位到高位逐位循环
{
按键值的当前位将链表分拆成十个队列链表；
按对应0至9的顺序将十个链表收集成一个链表；
}
}
由于分拆时，当前表元接在对应值的队列链表的末尾，为了便于为每 个队列链表接入新表元，除每个队列链表有首指针外，还应为每个队列链表引入末表元指针。又为了能方便处理十个队列，十个队旬的头和尾指针又分别构成两个指针数组。按对应值0至9 的顺序将十个链表收集成一个链表的工作只要将空链表除外，顺序将这些链表的首尾链接即可。另外，编写函数需要知道链表的首指针，但排序后链表中各表元的链接顺序会改变，原来的首表元可能不再是首表元，即链表的首指针也会改变，所以函数的参数应为链表首指针的指针。
程序代码如下：
#include<stdio.h>
#include<stdlib.h>
#define KEYN 3
struct ele{
int key;
struct ele *link;
};
void basesort(struct ele **h)
{
int i,j,factor;
struct ele *head[10],*tail[10],*p,*u;
/*依次对键值的个位到高位逐位循环*/
for(i=0,factor=1,p=*h;i<KEYN;factor*=10,i++)
{
/*按键值的当前值将链表分拆成十个队列链表*/
for(j=0;j<10;j++) /*预置十个空链表*/
head[j]=NULL;
while(p)
{ /*将*p接到某队列链表*/
u=p->link; /*保护下一个表元的指针*/
j=(p->key/factor)%10; /*求表元键值的当前位*/
if(head[j]==NULL) /*按当前位值将*p接在对应队列的末尾*/
head[j]=p;
else
tail[j]->link=p;
tail[j]=p;
p->link=NULL;
p=u; /*准备访问下一表元*/
}
/*将十个队列链表链接成一个链表*/
p=NULL;
for(j=0;j<10;j++)
{
if(head[j]==NULL)continue; /*跳过空链表*/
if(p==NULL)p=head[j];
else u->link=head[j]; /*各链表首尾顺序链接*/
u=tail[j];
}
}
*h=p;
}
int a[]={35,298,832,932,38,635,22,15,48};
#define N sizeof a/sizeof a[0]
void main()
{
struct ele *h,*u;
int i;
h=NULL; /*先形成一个空链表*/
for(i=0;i<N;i++)
{ /*任意形成一个链表*/
u=(struct ele *)malloc(sizeof(struct ele));
u->key=a[i];
u->link=h;
h=u;
}
basesort(&h); /*排序*/
for(u=h;u;u=u->link) /*顺序输出链表各表元的链值*/
printf("%4d",u->key);
printf("n");
}
程序运行结果为：
15 22 35 38 48 298 635 832 932