数据结构C语言版第一章算法实现 [复制链接]

P10预定义常量和类型

文件名：c1.h

//c1.h文件名#includestring.h//字符串函数头文件#includectype.h//字符函数头文件#includemalloc.h//含有malloc()等#includelimits.h//INT_MAX等#includestdio.h//标准输入输出头文件#includestdlib.h//atoi(),exit()等#includeio.h//eof()#includemath.h//数学函数头文件，包括floor(),ceil(),abs()#includesys/timeb.h//ftime()#includestdarg.h//提供宏va_start,va_arg和va_end，用于存取变长参数表//函数结果状态代码。在严书P10#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;//Status是函数的类型，其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型，其值是TRUE或FALSE,第7/8/9章用到

P12

文件名：c1-1.h

//c1-1.h采用动态分配的顺序存储结构。在严书P12typedefElemType*Triplet;//由InitTriplet分配3个元素存储空间//Triplet类型是ElemType类型的指针，存放ElemType类型的地址

P12

文件名：bo1-1.h

//bo1-1.h抽象数据类型Triplet和ElemType（由c1-1.h定义）的基本操作8个StatusInitTriplet(TripletT,ElemTypev1,ElemTypev2,ElemTypev3){//操作结果：构造三元组T，依次置T的三个元素的初值为v1,v2,v3。在严书P12T=(ElemType*)malloc(3*sizeof(ElemType));//分配三个元素的存储空间if(!T)exit(OVERFLOW);//分配失败则退出T[0]=v1,T[1]=v2,T[2]=v3;returnOK;}StatusDestroyTriplet(TripletT){//操作结果：三元组T被销毁。在严书P12free(T);//释放T所指的三元组存储空间T=NULL;//T不再指向任何存储单元returnOK;}StatusGet(TripletT,inti,ElemTypee){//初始条件：三元组已存在，1=i=3//操作结果：用e返回T的第i元的值if(i1

i3)//i不在三元组的范围之内returnERROR;e=T[i-1];returnOK;}StatusPut(TripletT,inti,ElemTypee){//初始条件：三元组T已存在1=i=3//操作结果：改变T的第i元的值为eif(i1

i3)//i不在三元组的范围之内returnERROR;T[i-1]=e;returnOK;}StatusIsAscending(TripletT){//初始条件：三元组T已存在1=i=3//操作结果：如果三个元素按升序排列，则返回1，否则返回0return(T[0]=T[1]T[1]=T[2]);}StatusIsDescending(TripletT){//初始条件：三元组T已存在1=i=3//操作结果：如果三个元素按降序排列，则返回1，否则返回0return(T[0]=T[1]T[1]=T[2]);}StatusMax(TripletT,ElemTypee){//初始条件：三元组T已存在1=i=3//操作结果：返回三个元素中的最大值e=(T[0]=T[1])?(T[0]=T[2]?T[0][2])T[1]=T[2]?T[1][2]);returnOK;}StatusMin(TripletT,ElemTypee){//初始条件：三元组T已存在1=i=3//操作结果：返回三个元素中的最小值e=(T[0]=T[1])?(T[0]=T[2]?T[0][2])T[1]=T[2]?T[1][2]);returnOK;}

两个函数

文件名：func1-1.h

voidprintE(ElemTypee)//输出元素的值{printf("%d\n",e);//ElemType为整型选择此语句//printf("%f\n",e);//ElemType为双精度型选择此语句}voidprintT(TripletT)//依次输出三元组的值{printf("%d,%d,%d\n",T[0],T[1],T[2]);//ElemType为整型选择此语句//printf("%f,%f,%f\n",T[0],T[1],T[2]);//ElemType为双精度型选择此语句}

三元组数据结构的测试

#include"c1.h"typedefintElemType;#include"c1-1.h"#include"bo1-1.h"#include"func1-1.h"intmain(void){TripletT;ElemTypem;Statusi;//初始化i=InitTriplet(T,5,7,9);printf("调用初始化函数后，i=%d(1:成功)。T的三个值为：",i);//输出printT(T);i=Get(T,2,m);if(i==OK){printf("T的第二个值为");printE(m);}i=Put(T,2,6);if(i==OK){printf("将T的第二个值改为6后，T的第三个值为：");printT(T);}i=IsAscending(T);printf("调用测试升序后的函数后，i=%d(0否1是)\n",i);i=IsDescending(T);printf("调用测试降序后的函数后，i=%d(0否1是)\n",i);if((i=Max(T,m))==OK){printE(m);//输出最大值m}if((i=Min(T,m))==OK){printE(m);//输出最小值m}DestroyTriplet(T);//函数也可以不带返回值printf("销毁T后，T=%u\n",T);return0;}

C++引用类型的效果

#include"c1.h"voidfa(inta);//在函数中改变a，将不会带回主函数voidfb(inta);//a为引用类型，在函数中改变a，将会带回主函数voidfa(inta){a++;printf("在函数fa中：a=%d\n",a);}voidfb(inta){a++;printf("在函数fb中：a=%d\n",a);}intmain(void){intn=1;printf("在主程序中，调用函数fa之前：n=%d\n",n);fa(n);printf("在主程序中，调用函数fa之后，在调用函数fb之前：n=%d\n",n);fb(n);printf("在主程序中，调用函数fb之后：n=%d\n",n);return0;}

运行结果如下：

在主程序中，调用函数fa之前：n=1在函数fa中：a=2在主程序中，调用函数fa之后，在调用函数fb之前：n=1在函数fb中：a=2在主程序中，调用函数fb之后：n=2

不同算法的时间复杂度比较

1.

//计算1-1/x+1/(x*x)...#include"c1.h"intmain(void){timebt1,t2;longt;doublex,sum=1,sum1;inti,j,n;printf("请输入xn:");scanf("%lf%d",x,n);ftime(t1);//求得当前时间for(i=1;i=n;i++){sum1=1;for(j=1;j=i;j++)sum1=sum1*(-1.0/x);sum+=sum1;}ftime(t2);t=(t2.time-t1.time)*+(t2.millitm-t1.millitm);//计算时间差printf("sum=%lf，用时%ld毫秒\n",sum,t);return0;}

运行结果

2.

//计算1-1/x+1/(x*x)...#include"c1.h"intmain(void){timebt1,t2;longt;doublex,sum=1,sum1=1;inti,n;printf("请输入xn:");scanf("%lf%d",x,n);ftime(t1);//求得当前时间for(i=1;i=n;i++){sum1*=-1.0/x;sum+=sum1;}ftime(t2);t=(t2.time-t1.time)*+(t2.millitm-t1.millitm);//计算时间差printf("sum=%lf，用时%ld毫秒\n",sum,t);return0;}

运行结果

结果显而易见，一个好的算法十分重要