《历史沿革》PPT课件

《《历史沿革》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1、历史沿革2、计算机科技的两大支柱3、数据类型和数据结构4、算法5、时间复杂性的度量6、有效算法的重要性1968年D·E·Knuth：“Artofcomputerprogramming”IEEE68教程1983IEEE83教程1991IEEE91教程2000IEEE2000教程国内在78年开设历史沿革·1、数据结构2、算法·程序＝数据结构＋算法输入未处理的数据算法输出加工过的数据计算机科技的两大支柱·数据值：atomicdatavalue:不可再分解。如3、2、5等。non-atomicdatavalue:可以再分解，其成分称

2、为dataelement或element。如set:{32.99,-1.03,0,23}。·类型：同一类别可供识别的一组个体。·数据类型：datatype=datavalue+operation或者定义为1、Asetofvalue2、Asetofoperationsonthethesevalue。数据类型和数据结构1、原子数据类型：数据值是原子数据值。如：int2、结构数据类型：数据值是可以再分解。如：anarray[1..3]ofrealvalue1value2value3[1]0[1]1.9[1]1.9[2]1.9[2]0[2]1.9

3、[3]3.4[3]3.4[3]6.8value1value2数据值的进一步分解为数据元素，它们之间有一个关系。数据类型的类别1、原子数据类型：数据值是原子数据值。如：int2、结构数据类型：数据值是可以再分解。如：anarray[1..3]ofrealvalue1value2value3[1]0[1]1.9[1]1.9[2]1.9[2]0[2]1.9[3]3.4[3]3.4[3]6.8operation:1、在datavalue上：varvalue1,value2,value3;value3=value1+value2;2、在元素上：va

4、rvalue1;value1[1]=1.2;数据类型的类别数据结构是一种数据类型，其数据值：1、可以进一步分解为数据元素的集合，该数据元素可以是原子数据值，也可以是另外一种数据结构。2、数据元素之间有一个关系的集合。注意：在许多数据结构的书籍（课本）之中，通常将数据元素称之为结点·数据结构的分类：1、线性结构：如：线性表：空或一个元素或：除第一个结点外，都有直接前驱结点，除最后一个结点外，都有直接后继结点。其它如：栈、队列等。2、非线性结构：树、二叉树、图等。数据结构的实现1.ADT(AbstractDataType):认为DT仅存在于想

5、象之中。注意力集中在感兴趣的性质上，不关心数据的表示形式、操作的具体代码等等。给出规范或说明。2.VDT(VirtualDataType)：DT存在于Virtualprocessor上。如：c++=O.S.+hardware+c++compiler的Virtualprocessor。其他如SQLVirtualprocessor等。给出表示和实现。如：用类、类属数据类型、模板等。3.PDT(PhysicalDataType)：DT存在于物理机器上。例：线性表在C++中数据结构的构造：以一个线形表为例说明。322545238线形表实例：抽象数

6、据类型表1.1:表seqlist的抽象数据类型（ADT）ADTseqlistisData一个数据元素的表seqlist，其数据元素或结点可由序号进行标识。OperationsConstructor构造一个空表。ListSize前提：无。结果：给出表seqlist的规模。ListEmpty前提：无。结果：若表seqlist为空返回True，否则False。ClearList前提：无。结果：若表seqlist非空，则清空表seqlist。Find前提：给定数据元素或结点。结果：若查找成功则返回True,否则返回False。Insert前提:给

7、定要插入的数据元素。结果：将该数据元素插入到表seqlist的末尾，表的规模增加1。Delete前提:给定要删除的数据元素之值。结果：查找该数据值的结点，查找成功则删除之，表seqlist的规模减少1，否则删除失败。DeleteFront前提:表seqlist非空。结果：删除队首结点并返回结点的数据值，表seqlist的规模减少1。GetData前提:数据元素或结点的位置或序号，其序号在0和表的大小减1之间。结果：给出相应表seqlist位置序号的结点的数据值。虚拟数据类型表1.2:用C++表示的表seqlist的规范(VDT)class

8、seqlist{private:intsize;//sizeoftheseqlist.Itis0whentheseqlistisempty.DataType*list;//DataTypeis