第一讲 基本概念 - 1 2019-11-14
写在前面：
**课程来源：中国大学MOOC课程 -- 浙江大学 -- 数据结构 -- 陈越、何钦铭
**链接：https://www.icourse163.org/course/ZJU-93001
**此为该课程第十次开课的笔记**
**预计一周学习 1-2讲的内容；并更新博客**
Part-1
数据结构：类似与图书馆中摆放书籍、检索、插入的问题。
解决问题的效率，跟数据的组织方法有关。
Part-2
循环与递归
例1：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数
1 // loop 2 void printN(int N){ 3 int i; 4 for(i=1;i<=N;i++){ 5 printf("%d ", i); 6 } 7 } 8 9 // recursion 10 void printN(int N){ 11 if(N){ 12 printN(N-1); 13 printf("%d\n", N); 14 } 15 }
// 当 N=100,000 时，循环能得到正确的结果，递归return非0
*递归对空间的占用是可怕的
*电脑做递归的能力 << 远远弱于 做循环；类似情况应该使用循环 而非递归
Part-3
例3：写程序计算给定多项式在给定点x处的值
方法1：依照数学公式计算
方法2：降低运算量版本 -- 更优
1 // a0 + a1*x + a2*x^2 + ... + an*x^n 2 double f1(int n, double a[], double x){ 3 int i; 4 double p=a[0]; 5 for(i=1; i<=n; i++){ 6 p += ( a[i] * pow(x,i) ); 7 } 8 return p; 9 } 10 11 // a0 + x(a1 + x(...(an-1 + x*an)...)) 12 double f2(int n, double a[], double x){ 13 int i; 14 double p=a[n]; 15 for(i=n; i>0; i--){ 16 p += a[i-1] + x*p; 17 } 18 return p; 19 }
* 计算程序运行时间 C语言 - clock() *
# include <time.h>
*注：start & stop 获得的值不是 sec，而是时钟打点，获得时间（s）则需要除以 CLK_TCK
*注：当被测程序运行过快的时候，可以使用循环，重复运行多次该程序；再用时间除以循环次数。
完整测试代码：wk1_loop_recursion.c (见本文最后)
完整测试代码 -- 包括 discuss-1.3：wk1_pow.c (见本文最后)
Part-4 数据结构(定义)
数据对象在计算机中的组织方式 [对象：object]
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
描述数据结构一个很好的方法：抽象数据类型 Abstract Data type
数据类型 【c中独立处理，c++等使用类进行封装】
? 数据对象集 [描述对象，是什么东西]
? 数据集合相关联的操作集 [图书的摆放和操作]
抽象：描述数据类型的方法不依赖于具体实现
? 与存放数据的机器无关
? 与数据存储的物理结构无关
? 与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
例4：“矩阵”的抽象数据类型定义
* 矩阵元素a 的类型不确定，可以说int，float，...
* ElementType: 对应返回矩阵元素 的类型。
* 抽象不关心矩阵的 存储方式：二维数组？十字链表？
* 抽象也不关心具体的实现方式：编程语言，加法顺序等
* 抽象的好处：
1）抽象可以在宏观程度上把握程序的整体架构，定义抽象时只关心业务逻辑就够了，不关心具体实现。【框架】
2）需要使用时才考虑程序实现的具体细节，慢慢地去完善 【具体实现】
1 /* WK1_loop_recursion */ 2 #include <stdio.h> 3 4 void printN(int N); 5 6 int main(){ 7 8 int N; 9 scanf("%d", &N); 10 printN(N); 11 12 return 0; 13 } 14 // 使用时请注释其中一个 15 // loop 16 void printN(int N){ 17 int i; 18 for(i=1;i<=N;i++){ 19 printf("%d ", i); 20 } 21 } 22 23 // recursion 24 void printN(int N){ 25 if(N){ 26 printN(N-1); 27 printf("%d\n", N); 28 } 29 }
[以下代码有大量重复片段没有优化]
1 /* WK1_pow */ 2 3 #include<stdio.h> 4 #include <time.h> // obtain func run time 5 #include <math.h> 6 7 clock_t start, stop; 8 double duration; 9 #define MAXK 1e6 //被测函数最大重复调用次数 10 #define MAXN 10 //多项式最大项数 11 #define LEN 101 12 double f1(int n, double a[], double x); 13 double f2(int n, double a[], double x); 14 15 int main(){ 16 int i; 17 double a[MAXN]; 18 for(i=0;i<MAXN;i++){ 19 a[i]= (double)i; 20 } 21 22 /* execution time: func f1 */ 23 start = clock(); //start time 24 // test func 25 for(i=0; i<MAXK; i++){ 26 f1(MAXN, a, 1.1); 27 } 28 29 stop = clock(); //stop time 30 duration =((double)(stop-start))/CLK_TCK/MAXK; //*func duration 31 printf("ticks1 = %f\n", (double)(stop-start)); 32 printf("duration1 = %6.2e\n", duration); 33 34 printf("\n"); 35 36 /* execution time: func f2 */ 37 start = clock(); //start time 38 // test func 39 for(i=0; i<MAXK; i++){ 40 f2(MAXN, a, 1.1); 41 } 42 43 stop = clock(); //stop time 44 duration =((double)(stop-start))/CLK_TCK/MAXK; //*func duration 45 printf("ticks2 = %f\n", (double)(stop-start)); 46 printf("duration2 = %6.2e\n", duration); 47 48 //------------------------------------------------------------ 49 /* discuss 1.3 */ 50 double b[LEN]; 51 b[0] = 1.0; 52 for(i=1; i<=LEN; i++){ 53 b[i]=1.0/(double)i; 54 } 55 56 // method 1 57 start = clock(); 58 for(i=0; i<MAXK; i++){ 59 f1(LEN, b, 1.1); 60 } 61 stop=clock(); 62 duration = ((double)(stop-start))/CLK_TCK/MAXK; 63 printf("ticks1 = %f\n", (double)(stop-start)); 64 printf("duration1 = %6.2e\n", duration); 65 66 // method 2 67 start = clock(); 68 for(i=0; i<MAXK; i++){ 69 f2(LEN, b, 1.1); 70 } 71 stop = clock(); 72 duration = ((double)(stop-start))/CLK_TCK/MAXK; 73 printf("ticks2 = %f\n", (double)(stop-start)); 74 printf("duration2 = %6.2e\n", duration); 75 76 return 0; 77 } 78 79 double f1(int n, double a[], double x){ // a0 + a1*x + a2*x^2 + ... + an*x^n 80 int i; 81 double p=a[0]; 82 for(i=1; i<=n; i++){ 83 p += ( a[i] * pow(x,i) ); 84 } 85 return p; 86 } 87 88 double f2(int n, double a[], double x){ // a0 + x(a1 + x(...(an-1 + x*an)...)) 89 int i; 90 double p=a[n]; 91 for(i=n; i>0; i--){ 92 p += a[i-1] + x*p; 93 } 94 return p; 95 }
原文：https://www.cnblogs.com/SAzSkjEydrD2B9yu/p/11846054.html