1.1 什么是数据结构
例1-如何在书架上摆放图书
图书的摆放要使得2个相关操作方便实现：
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
方法1：随便放
操作1–哪里有空放哪里，一步到位！
操作2–累死
方法2：按照书名的拼音字母顺序排放
操作1：
操作2：二分查找！
方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在某种类别内，按照书名的拼音字母顺序排放。
操作1：先定类别，二分查找确定位置，移出空位
操作2：先定类别，再二分查找
问题：空间如何分配？类别应该分多细？
解决问题方法的效率，跟数据的组织方式有关
例2-写程序实现一个函数PrintN，使得传入一个正整数N为参数后，能顺序打印从1到N的全部正整数
case 1：循环实现
复制代码
1
2
3
4
5
6
7
8
9
10void PrintN ( int N ) { int i; for ( i=1 ; i<=N ; i++ ) { printf("%dn",i); } return ; }
case 2：递归实现
复制代码
1
2
3
4
5
6
7
8
9
10void PrintN ( int N ) { if（ N ） { PrintN( N-1 ); printf( "%dn",N ); } return ; }
递归方法占用的空间大
例3：写程序计算给定多项式在给定点x处的值
f(x)=a0 + a1x + … +a(n-1)x^(n-1) + a(n)x^n
复制代码
1
2
3
4
5
6
7
8
9double f( int n,double a[],double x) { int i; double p = a[0]; for( i=1 ; i<=n ; i++ ) p += (a[i]*pow(x,i)); return p; }
f(x)=a0 + x(a1 + x(…(a(n-1) + x(a(n))…))–更快
复制代码
1
2
3
4
5
6
7
8
9double f( int n , double a[] , double x) { int i; double p = a[n]; for ( i=n ; i>0 ; i-- ) p = a[i-1] + x*p; return p; }
clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个世界单位是clock tick,即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟打点数
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20常用模板： #include<stdio.h> #include<time.h> clock_t start , stop ; //clock_t 是 clock() 函数返回的变量类型 double duration; //记录被测函数运行时间，以秒为单位 int main() {//不在测试范围内的准备 工作写在clock()调用之前 start = clock(); //开始计时 MyFunction(); //把被测函数加在这里 stop = clock(); //停止计时 duration = ((double)(stop - start))/CLK_TCK; //计算运行时间 //其他不在测试范围的处理写在后面，例如输出duration的值 return 0; }
例3：写程序计算给定多项式
f ( x ) = ∑ i = 0 9 i x i f(x)=sum_{i=0}^{9}{ix^i} f(x)=i=0∑9ixi
在给定点x=1.1处的值f(1.1)
复制代码
1
2
3
4
5
6
7
8
9double f1( int n, double a[], double x ) { int i ; double p = a[0]; for( i=1 ; i<=n ; i++ ) p+=(a[i] * pow(x,i) ); return p; }
复制代码
1
2
3
4
5
6
7
8
9double f2( int n, double a[] ,double x ) { int i; double p = a[n] ; for( i = n ; i > 0 ; i-- ) p = a[i-1] + x*p ; return p; }
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include<stdio.h> #include<time.h> #include<math.h> clock_t start , stop ; double duration; #define MAXK 1e7 //被测函数最大重复调用次数 #define MAXN 10 //多项式最大项数，即多项式阶数+1 double f1( int n, double a[], double x ); double f2( int n, double a[], double x ); int main() { int i; double a[MAXN]; //储存多项式的系数 for ( i=0 ; i<MAXN ; i++ ) a[i] = (double) i ; start = clock(); for ( i=0 ; i<=MAXK ; i++ ) f1( MAXN-1 , a , 1.1 ); stop = clock(); duration = ((double)(stop - start))/CLK_TCK/MAXK; printf("ticks1 = %fn" ,(double) ( stop - start )); printf("duration1 = %6.2en", duration); start = clock(); for ( i=0 ; i<=MAXK ; i++ ) f2( MAXN-1 , a , 1.1 ); stop = clock(); duration = ((double)(stop - start))/CLK_TCK/MAXK; printf("ticks2 = %fn" ,(double) ( stop - start )); printf("duration2 = %6.2en", duration); return 0; } double f1( int n, double a[], double x ) { int i ; double p = a[0]; for( i=1 ; i<=n ; i++ ) p+=(a[i] * pow(x,i) ); return p; } double f2( int n, double a[] ,double x ) { int i; double p = a[n] ; for( i = n ; i > 0 ; i-- ) p = a[i-1] + x*p ; return p; }
让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可！
什么是数据结构？？？
数据对象在计算机中的组织方式
逻辑结构
物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）
数据类型
数据对象集
数据集合相关联的操作
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
只描述数据对象集合相关操作集“是什么”，并不涉及“如何做到”的问题
例4 ：“矩阵”的抽象数据类型定义
类型名称：
矩阵（Matrix）
数据对象集：
一个MM的矩阵
A
m
∗
n
=
(
a
i
j
)
(
i
=
1
,
⋯
,
N
)
A_{m*n}=(a_{ij}) (i=1,cdots,N)
Am∗n=(aij) (i=1,⋯,N)
由MN个三元组< a , i , j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号
操作集：
对任意矩阵 A , B , C 属于Matrix，以及整数 i , j , M , N
复制代码
1
2
3
4
5
6
7
8· Matrix Create ( int M , int N ) : 返回一个M*N的空矩阵； · int GetMaxRow ( Maxtrix A ) :返回矩阵A的总行数； · int GetMaxCol ( Maxtrix A ) :返回矩阵A的总列数； · ElementType GetEntry ( Maxtrix A, int i, inr j ) :返回矩阵A的第i行，第j列的元素； · Maxtrix Add ( Matrix A, Matrix B ) : 如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志； · Maxtrix Multiply ( Matrix A, Matrix B ) : 如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志； · ……
最后
以上就是帅气钢笔最近收集整理的关于数据结构 1.1 什么是数据结构1.1 什么是数据结构什么是数据结构？？？的全部内容，更多相关数据结构内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复