教学课件：《数据结构》浙江大学陈越（300页）.ppt

第1章概论§1引子

【定义】“数据结构是计算机中存储、组织数据的方式。精心选择的数据结

构可以带来最优效率的算法。”

[例1.1]该如何摆放书，才能让读者很方便地找到你手里这本

《数据结构》？

1/25

第1章概论§1引子

【分析】

[方法1]随便放——任何时候有新书进来，哪里有空就把书插到哪里。

查找效率极低！

[方法2]按照书名的拼音字母顺序排放。

有时插入新书很困难！

[方法3]把书架划分成几块区域，每块区域指定摆放某种类别的图书；

在每种类别内，按照书名的拼音字母顺序排放。

可能造成空间的浪费！

2/25

第1章概论§1引子

[例1.2]写程序实现一个函数PrintN，使得传入一个正整

数为N的参数后，能顺序打印从1到N的全部正整数。

voidPrintN(intN)voidPrintN(intN)

{inti;{if(!N)return;

for(i=1;i=N;i++)PrintN(N–1);

printf(“%d\n”,i);printf(“%d\n”,N);

return;return;

}}

3/25

第1章概论§1引子

[例1.3]多项式的标准表达式可以写为：

2n

f(x)=a0+a1x+a2x+…+anx

现给定一个多项式的阶数n，并将全体系数存放在数组a[]里。请写程序计算

这个多项式在给定点x处的值。

方法秦九韶法

[[方法21]]计算多项式函数值的直接法

f(x)=a0+x(a1+x(a2+…+x(an)…)

doduobulebfl(eifn(tint,dno,duobulebale[]a,[d]o,duobulebxle)x)

计算阶数为，系数为的多项式在点的值

{{/*/*计算阶数为nn，系数为a[a0[]0.]..a..[an[]n]的多项式在xx点的值*/*/

inintti;i;

ddoouubblelepp==aa[n[0];];

foforr(i(=in=;1i;i0;=in--;)i++)

pp=+a=[ia-1[i]]*+pxo*wp;(x,i);

reretuturnrnpp;;

}}

4/25

第1章概论