DS01_概论_陈越主编_数据结构.ppt

《DS01_概论_陈越主编_数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章概论【定义】“数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。”1/25§1引子[例1.1]该如何摆放书，才能让读者很方便地找到你手里这本《数据结构》？第1章概论【分析】2/25§1引子[方法1]随便放——任何时候有新书进来，哪里有空就把书插到哪里。[方法2]按照书名的拼音字母顺序排放。[方法3]把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放。放书方便，但查找效率极低！查找方便，但插入新书很困难！查找、插入方便，但每种类型的书不知道有多少本，有可能造成空间的浪费！第1章概论§1引子[例1.2]写程序

2、实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。voidPrintN(intN){inti;for(i=1;i<=N;i++)printf(“%d”,i);return;}voidPrintN(intN){if(!N)return;PrintN(N–1);printf(“%d”,N);return;}3/25考虑当N足够大时，会出现什么问题！第1章概论§1引子[例1.3]多项式的标准表达式可以写为：f(x)=a0+a1x+a2x2+…+anxn现给定一个多项式的阶数n，并将全体系数存放在数组a[]里。请写程序计算这个多项式在给定点x处的

3、值。[方法1]计算多项式函数值的直接法doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/inti;doublep=a[0];for(i=1;i<=n;i++)p+=a[i]*pow(x,i);returnp;}[方法2]秦九韶法f(x)=a0+x(a1+x(a2+…+x(an)…)doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/inti;doublep=a[n];for(i=n;i>0;i--)p=a[i-1]+x*p;r

4、eturnp;}4/25#include#includeclock_tstart,stop;/*clock_t是clock()函数返回的变量类型*/doubleduration;/*记录被测函数运行时间，以秒为单位*/intmain(){/*不在测试范围内的准备工作写在clock()调用之前*/start=clock();/*开始计时*/function();/*把被测函数加在这里*/stop=clock();/*停止计时*/duration=((double)(stop-start))/CLK_TCK;/*计算运行时间*//*其他不在测试范围的处理写

5、在后面，例如输出duration的值*/return0;}秦九韶算法的计算速度明显比直接法快了一个数量级！为什么会这样？第1章概论§1引子5/25代码1.6测试函数function()的运行时间即使解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远解决问题方法的效率跟数据的组织方式有关（如例1.1）跟空间的利用效率有关（如例1.2）跟算法的巧妙程度有关（如例1.3）第1章概论§1引子6/25第1章概论数据对象：计算机要处理的事物，如例1.1中“图书”。§2.1术语定义操作：处理事物的动作集合，如例1.1中的“查找”和“插入”，例1.2的函数“求值”等。算法

6、：操作的实现方法，如例1.1的按字母序排放的“查找”和“插入”、例1.2的“直接法”和例1.3的“秦九韶法”等。通常一个算法用一个函数来实现。逻辑结构：数据对象的逻辑组织关系。分为“线性”、“树”和“图”。例1.1中按方法1来处理，就是把图书集看成是线性的结构；按方法3来处理，就是把图书集看成是树形的结构。物理结构：数据对象信息在计算机内存中的存储组织关系。一般分为“顺序存储”和“链式存储”。7/25第1章概论数据类型：数据对象的类型确定了其“操作集”和“数据定义域”。§2.2抽象数据类型抽象数据类型：“抽象”的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集

7、和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。8/25第1章概论[例1.4]“矩阵”的抽象数据类型定义§2.2抽象数据类型类型名称：Matrix数据对象集：一个MN的矩阵A。操作集：对于任意矩阵A、B、CMatrix，以及正整数i、j、M、N，以下仅列出几项有代表性的操作。1）MatrixCreate(