论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

C程序设计例解(01)

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:47:05

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

------------------------------------------------------------------------------------------

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

上一篇:{应用}程序设计竞赛试题选(02) 人气:6817
下一篇:{应用}C程序设计例解(02) 人气:5244
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058