《数据结构上机实验（C语言实现）》笔记（1/12）：绪论

验证性实验

求1~n的连续整数和

说明

对于给定的正整数n&＃xff0c;求$1\&＃43;2\&＃43;\dots \&＃43;n$&＃xff0c;采用逐个累加和n(n&＃xff0b;1)2\frac {n(n&＃xff0b;1)} 22n(n&＃xff0b;1)​&＃xff08;高斯法&＃xff09;两种解法。

对于相同的n&＃xff0c;给出这两种解法的求和结果和求解时间&＃xff0c;并用相关数据进行测试。

• clock_t类型、clock()函数和CLOCKS_PER_SEC常量均在time.h头文件中声明。
• clock_t是时钟数据类型&＃xff08;长整型数&＃xff09;
• clock()函数返回CPU时钟计时单元数&＃xff08;以毫秒为单位&＃xff09;
• CLOCKSPER_SEC是一个常量&＃xff0c;表示1秒包含的毫秒数。
• 表达式((float) t)/CLOCKS_PER_SEC返回t转换成的秒数;

放码

//文件名&＃xff1a;exp1-1.cpp//求1&＃43;2&＃43;...&＃43;n
#include
#include // clock_t, clock, CLOCKS_PER_SEC
#include //方法1&＃xff1a;老实累加
long add1(long n)
{long i, sum &＃61; 0;for (i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)sum &＃43;&＃61; i;return(sum);
}void AddTime1(long n) /* 采用方法1的耗时统计 */
{clock_t t &＃61; clock();long sum &＃61; add1(n);t &＃61; clock() - t;printf("方法1:\n");printf(" 结果:1&＃xff5e;%d之和:%ld\n", n, sum);printf(" 用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//方法2&＃xff1a;用公式
long add2(long n) /* 方法2&＃xff1a;求1&＃43;2&＃43;...&＃43;n */
{return(n * (n &＃43; 1) / 2);
}void AddTime2(long n) /* 采用方法2的耗时统计 */
{clock_t t &＃61; clock();long sum &＃61; add2(n);t &＃61; clock() - t;printf("方法2:\n");printf(" 结果:1&＃xff5e;%d之和:%ld\n", n, sum);printf(" 用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}int main()
{int n;printf("n(大于1000000):");scanf("%d", &n);if (n < 1000000)return(0);AddTime1(n);AddTime2(n);return(1);
}


结果

n(大于1000000):99999999
方法1:结果:1&＃xff5e;99999999之和:887459712用时:0.222000秒
方法2:结果:1&＃xff5e;99999999之和:887459712用时:0.000000秒
请按任意键继续. . .


常见算法时间函数的增长趋势分析

说明

理解常见算法时间函数的增长情况。

对于1~n的每个整数n&＃xff0c;输log⁡2n\log_2nlog2​n 、n\sqrt nn

​、$n$、nlog⁡2nn \log_2nnlog2​n、n2n^2n2、n3n^3n3、2n2^n2n 和$n!$。

放码

//文件名&＃xff1a;exp1-2.cpp
#include
#include double log2(double x) //求log2(x)
{return log10(x)/log10((double)2);
}long exponent(int n) //求2^n
{long s&＃61;1;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)s*&＃61;2;return s;
}long factorial(int n) //求n!
{long s&＃61;1;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)s*&＃61;i;return s;
}void fun(int n)
{printf("log2(n) sqrt(n) n nlog2(n) n^2 n^3 2^n n!\n");printf("&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;\n");for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){printf("%5.2f\t",log2(double(i)));printf("%5.2f\t",sqrt((double)i));printf("%2d\t",i);printf("%7.2f\t",i*log2(double(i)));printf("%5d\t",i*i);printf("%7d\t",i*i*i);printf("%8d\t",exponent(i));printf("%10d\n",factorial(i));}
}int main()
{int n&＃61;10;fun(n);return 1;
}


结果

log2(n) sqrt(n) n nlog2(n) n^2 n^3 2^n n!
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;0.00 1.00 1 0.00 1 1 2 11.00 1.41 2 2.00 4 8 4 21.58 1.73 3 4.75 9 27 8 62.00 2.00 4 8.00 16 64 16 242.32 2.24 5 11.61 25 125 32 1202.58 2.45 6 15.51 36 216 64 7202.81 2.65 7 19.65 49 343 128 50403.00 2.83 8 24.00 64 512 256 403203.17 3.00 9 28.53 81 729 512 3628803.32 3.16 10 33.22 100 1000 1024 3628800
请按任意键继续. . .


设计性实验

求素数个数

说明

通过对比同一问题不同解法的绝对执行时间 &＃xff0c;体会如何设计“好”的算法。

求1~n的素数个数。对于相同的n&＃xff0c;给出这两种解法的结果和求解时间&＃xff0c;并用相关数据进行测试。

放码

//文件名&＃xff1a;exp1-3.cpp
#include
#include
#include //clock_t, clock, CLOCKS_PER_SEC
#include //------方法1-----------------------------------------------
bool prime1(long n) //方法1&＃xff1a;判断正整数n是否为素数
{long i;for (i &＃61; 2; i < n; i&＃43;&＃43;)if (n % i &＃61;&＃61; 0)return false; //若n不是素数,则退出并返回falsereturn true;
}void PrimeTime1(long n) //采用方法1的耗时统计
{long sum &＃61; 0, i;clock_t t &＃61; clock();for (i &＃61; 2; i <&＃61; n; i&＃43;&＃43;)if (prime1(i))sum&＃43;&＃43;;t &＃61; clock() - t;printf("方法1:\n");printf(" 结果:2&＃xff5e;%d的素数个数:%d\n", n, sum);printf(" 用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------方法2-----------------------------------------------
bool prime2(long n) //方法2&＃xff1a;判断正整数n是否为素数
{long i;for (i &＃61; 2; i <&＃61; (int)sqrt((double)n); i&＃43;&＃43;)//对n开方进行优化if (n % i &＃61;&＃61; 0)return false; //若n不是素数,则退出并返回falsereturn true;
}
void PrimeTime2(long n) //采用方法2的耗时统计
{long sum &＃61; 0, i;clock_t t &＃61; clock();for (i &＃61; 2; i <&＃61; n; i&＃43;&＃43;)if (prime2(i))sum&＃43;&＃43;;t &＃61; clock() - t;printf("方法2:\n");printf(" 结果:2&＃xff5e;%d的素数个数:%d\n", n, sum);printf(" 用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------方法3-----------------------------------------------
int countPrimes(long n) //方法3&＃xff1a;埃拉托色尼筛选法&＃xff0c;空间换时间&＃xff0c;n不能过大&＃xff0c;否则程序报错
{bool *flag &＃61; (bool *)malloc(n * sizeof(bool));for (long i &＃61; 0; i < n; i&＃43;&＃43;)//这步不能省略&＃xff0c;否则得不到正确值flag[i] &＃61; 0;int count &＃61; 0;for (long i &＃61; 2; i < n; i&＃43;&＃43;){if (flag[i] &＃61;&＃61; 0){count&＃43;&＃43;;for (long j &＃61; i; i * j < n; j&＃43;&＃43;) {flag[i * j] &＃61; 1;}}}free(flag);return count;
}
void PrimeTime3(long n) //采用方法3的耗时统计
{long sum &＃61; 0;clock_t t &＃61; clock();sum &＃61; countPrimes(n);t &＃61; clock() - t;printf("方法3:\n");printf(" 结果:2&＃xff5e;%d的素数个数:%d\n", n, sum);printf(" 用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------------------------------------------------------------
int main() {long n;printf("n&＃xff08;取值范围[10000, 40000]&＃xff09;:");scanf("%d", &n);if (!(10000 <&＃61; n && n <&＃61; 40000)) return 0;PrimeTime1(n);PrimeTime2(n);PrimeTime3(n);return 1;
}


结果

n&＃xff08;取值范围[10000, 40000]&＃xff09;:40000
方法1:结果:2&＃xff5e;40000的素数个数:4203用时:0.236000秒
方法2:结果:2&＃xff5e;40000的素数个数:4203用时:0.009000秒
方法3:结果:2&＃xff5e;40000的素数个数:4203用时:0.001000秒
请按任意键继续. . .


求连续整数阶乘的和

说明

对于给定的正整数n&＃xff0c;求1!&＃43;2!&＃43;3!&＃43;…&＃43;n !。给出一种时间复杂度为O(n)的解法。

放码

//文件名&＃xff1a;exp1-4.cpp
#include //循环版
long Sum(int n) {long sum &＃61; 0, fact &＃61; 1;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {fact *&＃61; i;sum &＃43;&＃61; fact;}return sum;
}//TODO:递归版//------------------------------------------------------------
int main() {int n;printf("n(3-20):");scanf("%d", &n);if (n < 3 || n > 20) return 0;printf("1!&＃43;2!&＃43;…&＃43;%d!&＃61;%ld\n", n, Sum(n));return 1;
}


结果

n(3-20):15
1!&＃43;2!&＃43;…&＃43;15!&＃61;1443297817
请按任意键继续. . .