文档介绍：数据结构与算法Data Structures and Algorithm
第1章概论
【定义】“数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。”
1/25
§1 引子
[] 该如何摆放书,才能让读者很方便地找到你手里这本《数据结构》?
第1章概论
【分析】
2/25
§1 引子
[方法1] 随便放——任何时候有新书进来,哪里有空就把书插到哪里。
[方法2] 按照书名的拼音字母顺序排放。
[方法3] 把书架划分成几块区域,每块区域指定摆放某种类别的图书;在每种类别内,按照书名的拼音字母顺序排放。
查找效率极低!
有时插入新书很困难!
可能造成空间的浪费!
第1章概论
§1 引子
[] 写程序实现一个函数PrintN,使得传入一个正整数为N的参数后,能顺序打印从1到N的全部正整数。
void PrintN ( int N )
{ int i;
for ( i=1; i<=N; i++ )
printf(“%d\n”, i );
return;
}
void PrintN ( int N )
{ if ( !N ) return;
PrintN( N – 1 );
printf(“%d\n”, N );
return;
}
3/25
第1章概论
§1 引子
[] 多项式的标准表达式可以写为:
f(x) = a0 + a1x + a2x2 +…+ anxn
现给定一个多项式的阶数 n,并将全体系数存放在数组 a[ ]里。请写程序计算这个多项式在给定点 x 处的值。
[方法1] 计算多项式函数值的直接法
double f( int n, double a[], double x )
{ /* 计算阶数为n,系数为a[0]...a[n]的多项式在x点的值*/
int i;
double p = a[0];
for ( i=1; i<=n; i++ )
p += a[i]*pow(x, i);
return p;
}
[方法2] 秦九韶法
f(x) = a0 + x (a1+ x (a2 +…+ x (an) …)
double f( int n, double a[], double x )
{ /* 计算阶数为n,系数为a[0]...a[n]的多项式在x点的值*/
int i;
double p = a[n];
for (i=n; i>0; i--)
p = a[i-1] + x*p;
return p;
}
4/25
#include <>
#include <>
clock_t start, stop; /* clock_t是clock()函数返回的变量类型*/
double duration; /* 记录被测函数运行时间,以秒为单位*/
int main ()
{ /* 不在测试范围内的准备工作写在clock()调用之前*/
start = clock(); /* 开始计时*/
function(); /* 把被测函数加在这里*/
stop = clock(); /* 停止计时*/
duration = ((double)(stop - start))/CLK_TCK;/* 计算运行时间*/
/* 其他不在测试范围的处理写在后面,例如输出duration的值*/
return 0;
}
秦九韶算法的计算速度明显比
直接法快了一个数量级!
为什么会这样?
第1章概论
§1 引子
5/25
测试函数function()的运行时间
即使解决一个非常简单的问题,往往也有多种方法,且不同方法之间的效率可能相差甚远
解决问题方法的效率
跟数据的组织方式有关()
跟空间的利用效率有关()
跟算法的巧妙程度有关()
第1章概论
§1 引子
6/25
数据结构基本概念
数据结构的起源
早期人们把计算机理解为数值计算的工具
现实中,更多的不是解决数值计算的问题
数据结构的起源
1968年Prof. Donald E. Knuth
数据的逻辑结构和存储结构及操作