代码意识流——花朵数问题(八)

来源:互联网 时间:1970-01-01

本文前一部分的链接http://www.cnblogs.com/KBTiller/archive/2011/06/07/2074344.html

21.记录结果
   由于无法保证输出的结果有序,所以只能把计算结果存储起来,待全部计算完毕再输出。
   事先也无法知道花朵数的个数,所以链表是比较适宜的存储方式。这种方案同时很容易保证保证有序存储。
   可以考虑用返回值的办法返回这个链表的head,也可以在main()中定义这个head,向qiongju()和xunhuan()传递&head。但是不难发现这两种方案参数总是要经历一系列无谓的传递,由于嵌套深度较深,求出结果的位置距离main()很远,所以不考虑这样的方案。代之以外部变量方案。
   首先在xunhuan()中写出函数调用语句及函数原型

   jilu( & he ); // void jilu( DASHU * );   //<=>记录结果

   把// void jilu( DASHU * ); 移动到"2_穷举.h"中,此后"2_穷举.c"变为

/*2_穷举.c*/#include "2_穷举.h"#include "0_问题.h"typedef unsigned int SHUZI_GESHU[JINZHI];//SHUZI_GESHU[d]存储数字d的个数 typedef DASHU SHUJUBIAO[JINZHI-1][WEISHU + 1];//0*(JINZHI-1)^N 1*(JINZHI-1)^N ……WEISHU*(JINZHI-1)^N//0*(JINZHI-2)^N 1*(JINZHI-2)^N ……WEISHU*(JINZHI-1)^N//……//0*(1)^N 1*(1)^N ……WEISHU*(1)^Nstatic void xunhuan(const int , const int , DASHU (*)[WEISHU + 1] ) ;static void jianli_sjb ( SHUJUBIAO * * ); //建立数据表static SF wenhe( SHUZI_GESHU * const , const DASHU * const);static SF wenhe( SHUZI_GESHU * const p_sz_gs , const DASHU * const p_he ){ int sz_gs_he[JINZHI] = { 0 }; //和中各数字的个数 if( chaoguo_W(p_he) == SHI // 超过W位 || 不足W位 || buzu_W (p_he) == SHI ){ return FOU ; } qiu_sz_gs( &sz_gs_he , p_he ); // 求和中各数字的个数 if ( memcmp ( sz_gs_he , *p_sz_gs , sizeof sz_gs_he )==0 ){ return SHI ; } return FOU ;}//建立数据表 static void jianli_sjb ( SHUJUBIAO * * p_p_sjb ){ if( (* p_p_sjb = malloc(sizeof(SHUJUBIAO)) ) == NULL ){ //#include <stdlib.h> exit(!EXIT_SUCCESS); } { int i , j ; for( i = 0 ; i < JINZHI - 1 ; i ++){ ds_fuzhi( *( * * p_p_sjb + i ) + 0 , 0 );//第一列为0 ds_fuzhi( *( * * p_p_sjb + i ) + 1 , 1 );//第二列先赋值为1 for( j = 0 ; j < N ; j ++ ){ //求N次幂 ds_chengyi( *( * * p_p_sjb + i ) + 1 , JINZHI - 1 - i ); } for( j = 2 ; j <= WEISHU ; j ++ ){ (*( * * p_p_sjb + i ))[j] = (*( * * p_p_sjb + i ))[j-1] ; ds_jiaru ( *( * * p_p_sjb + i ) + j , *( * * p_p_sjb + i ) + 1 ) ; } } } } extern void qiongju( void ){ SHUJUBIAO *p_sjb = NULL ; jianli_sjb ( & p_sjb ); //建立数据表 xunhuan( WEISHU , JINZHI-1 , *p_sjb ) ; free ( p_sjb );}static void xunhuan( const int gssx /*个数上限*/, const int sz /*关于哪个数字*/, DASHU (*p_hang)[WEISHU + 1] /*指向一行数据*/) { static DASHU he = { { 0 } } ;//static DASHU he ; // =0 待完成 DASHU he_ = he ; //记录累加前的值 static SHUZI_GESHU sz_gs ; if( sz > 0 ){ int i; for( i = 0 ; i <= gssx ; i++ ){ sz_gs[sz] = i ; //记录数字的个数 ds_jiaru ( &he , *p_hang + i ) ; xunhuan( gssx - i , sz - 1 , p_hang + 1 ); he = he_ ; //恢复原来的值 } } else{ sz_gs[sz] = gssx ; //记录数字的个数 if( wenhe ( & sz_gs , &he ) == SHI ){ //验算两者是否"吻合" jilu( & he ); //<=>记录结果 } }}

   考虑在另一个模块完成这个函数,为此在工程中添加"4_结果.h"。
   在"2_穷举.h" 中 // void jilu( DASHU * ); 之前加上 #include "4_结果.h",并把 // void  jilu( DASHU * ); 复制到 "4_结果.h" 中,此后"2_穷举.h"变为

/*2_穷举.h*/#ifndef QIONGJU_H#define QIONGJU_H /**************************类型定义**************************/ #include "3_大数.h" #include "常用.h"/**************************函数原型**************************/ extern void qiongju( void ); #include <stdlib.h> //malloc() #include <string.h> //memcmp() #include "4_结果.h" //void jilu(DASHU * ); #endif // QIONGJU_H

   在 "4_结果.h" 中将 void jilu(DASHU * ); 改写为
   extern void jilu(DASHU * );
   并在其前面添加 #include "3_大数.h" 预处理命令。此时"4_结果.h"的内容为

/*4_结果.h*/#ifndef JIEGUO_H#define JIEGUO_H /**************************类型定义**************************/ #include "3_大数.h" /**************************函数原型**************************/ extern void jilu( DASHU * ); #endif // JIEGUO_H

   在工程中添加"4_结果.c",在"4_结果.c"定义extern void jilu( DASHU * );

/*4_结果.c*/#include "4_结果.h"extern void jilu( DASHU *p_ds ){ }

由于链表很容易实现把数据依照顺序排列,所以采用链表存储已经求出的花朵数。首先定义节点的数据类型

/*4_结果.h*/#ifndef JIEGUO_H#define JIEGUO_H /**************************类型定义**************************/ #include "3_大数.h" typedef struct jd { DASHU hds; //花朵数 struct jd *xiayige; //下一个 } JIEDIAN;/**************************函数原型**************************/ extern void jilu( DASHU * ); #endif // JIEGUO_H

定义“头”的位置:由于main()中有函数需要使用,且用函数返回值的办法传回过于繁琐也很不自然,所以这里使用外部变量。但将其作用范围限制在仅仅模块内能使用(static)。下面是加入了一个节点的代码及测试代码

/*4_结果.c*/#include "4_结果.h"static JIEDIAN *tou = NULL ;//头 //在4_结果.h中加入 #include <stdlib.h> extern void jilu( DASHU *p_ds ){ JIEDIAN **p_t = &tou ; JIEDIAN *p_jd = NULL ; if((p_jd=malloc( sizeof (JIEDIAN ) ))==NULL ){ // 添加节点 printf("无法存储"); exit(1); } else{ p_jd->hds = *p_ds ; //写入节点 } while ( *p_t != NULL /* || (*p_t)->hds 小于 *p_ds */ ) { p_t = &(*p_t)->xyg ; } //加入到链表中 p_jd -> xyg = * p_t ; * p_t = p_jd ; #ifdef CESHI ds_shuchu( &tou->hds ); system("PAUSE"); exit(2); #endif }

测试输出153,测试通过。
其中还有一个判断一大数是否小于另一大数的函数尚未完成,依照下面次序完成:
在本地写函数调用—>在本地写函数原型—>将函数原型移动到"4_结果.h"
此时"4_结果.c"为

/*4_结果.c*/#include "4_结果.h"static JIEDIAN *tou = NULL ;//头 //在4_结果.h中加入 #include <stdlib.h> extern void jilu( DASHU *p_ds ){ JIEDIAN **p_t = &tou ; JIEDIAN *p_jd = NULL ; if((p_jd = malloc( sizeof (JIEDIAN ) ))==NULL ){ // 添加节点 printf("无法存储"); exit(1); } else{ p_jd->hds = *p_ds ; //写入节点 } while ( *p_t != NULL || ( xiaoyu(&(*p_t)->hds , p_ds ) == SHI ) // #include "常用.h" /* || (*p_t)->hds 小于 *p_ds */ ) { p_t = &(*p_t)->xyg ; } //加入到链表中 p_jd -> xyg = * p_t ; * p_t = p_jd ; #ifdef CESHI ds_shuchu( &tou->hds ); system("PAUSE"); //exit(2); #endif }


->在"4_结果.h"中加上

#include "3_大数.h"

之后将函数原型移动到"3_大数.h"

/*4_结果.h*/#ifndef JIEGUO_H#define JIEGUO_H /**************************类型定义**************************/ #include "3_大数.h" typedef struct jd { DASHU hds; //花朵数 struct jd *xyg; //下一个 } JIEDIAN; #include "常用.h" /**************************函数原型**************************/ extern void jilu( DASHU * ); #include "3_大数.h" //xiaoyu() #include <stdlib.h> //malloc(),NULL #endif // JIEGUO_H
/*3_大数.h*/#ifndef DASHU_H#define DASHU_H #include "0_问题.h" //DASHU用到了WEISHU /**************************类型定义**************************/ //gw_sz[0]为个位,gw_sz[WEISHU-1]为最高位//gw_sz[WEISHU-1]的值大于等于JINZHI表示溢出 typedef struct { int gw_sz[WEISHU] ; } DASHU ; #include "常用.h" /**************************函数原型**************************/ extern void ds_fuzhi ( DASHU * const , const int ) ; extern void ds_shuchu( const DASHU * const ) ; extern void ds_jiaru ( DASHU * const , const DASHU * const ) ; extern void ds_chengyi( DASHU * const , const int ); extern SF chaoguo_W(const DASHU * const); extern SF buzu_W(const DASHU * const); extern void qiu_sz_gs( int (*)[JINZHI] , const DASHU * const ) ; extern SF xiaoyu ( const DASHU * const, const DASHU * const) ; #endif // DASHU_H

->在"3_大数.c"中给出函数定义:

extern SF xiaoyu ( const DASHU * const p_ds1, const DASHU * const p_ds2) { int *t1 = p_ds1-> gw_sz , * w1 = t1 + WEISHU -1 ; int *t2 = p_ds2-> gw_sz , * w2 = t2 + WEISHU -1 ; while( w1 > t1 ){ if( *w1 < * w2){ return SHI ; } if( *w1-- > * w2-- ){ return FOU ; } } if(*w1<*w2){ return SHI ; } return FOU ;}

之后在main()中组织测试

#ifdef CESHI //测试 int main( void ) { #define TEST_xiaoyu #ifdef TEST_xiaoyu #include "3_大数.h" { DASHU t1,t2 ; ds_fuzhi(&t1,234); ds_fuzhi(&t2,567); printf("%d/n",xiaoyu(&t1,&t2)==SHI); } #endif //……前面进行的其他测试(略) system("PAUSE"); return 0; }#endif //CESHI

测试通过。至此,由qiongju()函数引出的全部函数完成。

22.输出结果

回到main()完成“//输出”部分
shuchu();//extern void shuchu(void);
依照下面次序
在本地写出函数调用—>在本地写函数原型—>将函数原型移动到"1_MAIN.h"

#ifdef QIUJIE //求解 int main( void ) { //求解:穷举<=>验算<=>记录结果 qiongju(); //输出 shuchu();//extern void shuchu(void); system("PAUSE"); return 0; } #endif //QIUJIE

->在"1_MAIN.h"中加上

#include "4_结果.h"

,之后将函数原型移动到"4_结果.h"

/*1_MAIN.h*/#ifndef MAIN_H#define MAIN_H /**************************类型定义**************************/ /**************************函数原型**************************/ #include <stdlib.h> //system() #include "2_穷举.h" //qiongju() #include "4_结果.h" #endif // MAIN_H

/*4_结果.h*/#ifndef JIEGUO_H#define JIEGUO_H /**************************类型定义**************************/ #include "3_大数.h" typedef struct jd { DASHU hds; //花朵数 struct jd *xyg; //下一个 } JIEDIAN; #include "常用.h" /**************************函数原型**************************/ extern void jilu( DASHU * ); #include "3_大数.h" #include <stdlib.h> //malloc(),NULL extern void shuchu(void); #endif // JIEGUO_H

->在"4_结果.c"中给出函数定义

extern void shuchu(void){ while(tou!=NULL){ JIEDIAN *p_xyg = tou-> xyg ; ds_shuchu(&tou->hds); free( tou ); tou = p_xyg ; } tou = NULL ;} 

本以为一切都写完了,直接把"0_问题.h"中的

#define CESHI 改成了 #define QIUJIE
兴高采烈地编译运行,结果……发生了可怕的错误。
后经过仔细检查,发现错误出在extern void jilu( DASHU *p_ds )中
 while ( *p_t != NULL 
        || ( xiaoyu(&(*p_t)->hds , p_ds ) == SHI )
实际上却应为
  while ( *p_t != NULL 
        && ( xiaoyu(&(*p_t)->hds , p_ds ) == SHI )

教训就是,前面对这个函数测试的不充分。在完成xiaoyu()函数前,测试了加入一个节点的情形,完成xiaoyu()函数之后,本应再测试一次 jilu()函数,但由于完成在即,心存侥幸地偷懒了。
修正这个BUG之后,编译运行,程序的运行结果为
128468643043731391252
449177399146038697307
运行时间约10秒。


  


相关阅读:
Top