数据结构 [data structure] (01)

《数据结构 [data structure] (01)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(1)——绪论主讲：骆昊E-mail：help.my.student@gmail.com什么是数据结构学习数据结构的背景计算机技术的飞速发展，使得计算机的应用领域不再仅仅局限于科学计算，而是更多的应用于控制、管理、自动化、仿真、娱乐等非数值计算领域。计算机加工处理的对象由纯粹的数值发展到字符、表格、图象、声音等各种具有一定结构的数据。那么，如何在计算机上存储并操作不同类型的数据一般来说，用计算机解决问题需要经过下列步骤：首先从具体问题抽象出适当的数学模型，然后设计一个求解该数学模型的算法，最后编写程序并进行测试、调整直到求得问题的解。寻求数学模型的实质是

2、分析问题，从中提取操作的对象并找出这些对象之间的关系，然后用数学语言加以描述。某些问题的数学模型可以用数学方程的形式加以描述，然而更多的非数值计算问题的模型是无法用数学方程来描述的。对于这类问题如何通过计算机求解呢什么是数据结构Wirth公式程序=算法+数据结构程序：为计算机处理问题所编写的一组指令集算法：解决问题的方法数据结构：问题的数学模型三个例子例子1：信息检索(线性结构)例子2：人机对弈(层次结构)例子3：网络路由(网状结构)研究内容数据结构的研究内容是非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作基本概念和术语数据

3、(data)对客观事物的符号表示，在计算机科学中是指输入到计算机中并被计算机程序识别、存储和处理的符号的总称数据元素(dataelement)数据的基本单位，在计算机程序中通常作为一个整体来进行考虑和处理。一个数据元素可以由若干个数据项(DataItem)组成数据对象(dataobject)性质相同的数据元素的集合，是数据的一个子集学号姓名语文数学英语数据元素100001芙蓉姐姐472212数据对象100002犀利哥9899100100003凤姐522544数据基本概念和术语数据结构(datastructure)相互之间存在一种或多种特定关系的数据元素的

4、集合通过前面的三个例子可以看出，数据元素都不是孤立存在的，将它们之间的相互关系称之为结构(structure)根据数据元素之间关系的不同，通常有以下四类基本结构：集合：结构中的数据元素满足确定性、互异性、无序性线性结构：结构中的数据元素之间存在一个对一个的关系树形结构：结构中的数据元素之间存在一个对多个的关系网状结构：结构中的数据元素之间存在多个对多个的关系集合线性结构树形结构网状结构基本概念和术语数据结构的形式定义数据结构=(D,S)，其中：D是数据元素的有限集，S是D上关系的有限集两个例子复数的数据结构：Complex=(C,R)，其中：C是两

5、个实数的集合{c,c}；R={r}，而r是定义在集合C上的一种关系，用有序偶12表示，其中c是复数的实部，c是复数的虚部1212Linux文件系统的数据结构：Linux-File-System=(F,R)，其中：F={ROOT,BIN,ETC,USR,VAR,DEV,HOME,LOCAL,LOG,SHARE,SPOOL,Jack,Bob,001.c,02.c,cat,mount,kernel,…}；R={,,,…,,,,

6、,,,,,,…}说明：ROOT是Linux文件系统的根，下面有BIN、ETC、USR、VAR等目录，其中USR是用户目录，Jack和Bob分别是两个不同用户各自的目录，而001.c和02.c则是其中的文件基本概念和术语逻辑结构结构定义中的关系描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构物理结构数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。本课程要探讨的一个重要问题就是如何将数据的逻辑结构映射成物理结构，通常有两种映射方式：顺

7、序映射和非顺序映射，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构的特点是借助指示元素存储地址指针(pointer)表示数据元素之间的逻辑关系说明：在C和C++中，通常使用指针来实现链式存储结构，Java中则使用引用(reference)来实现，Java中的引用实际上就是一种不计数的指针基本概念和术语数据类型(datatype)一个值的集合和定义在这个值集上的一组操作的总称，是对数据元素取值范围和运算的限定按照“值”的不同，高级程序语言中的数