资源描述：
《【大学数据结构课件】绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容提要1.1数据结构研究的内容对所加工的数据对象进行逻辑组织将数据对象存储在计算机中数据运算或处理1.2基本概念和术语数据、数据元素、数据结构、逻辑结构1.3抽象数据类型数据类型、抽象数据类型1.4算法和算法分析算法、算法设计、算法效率1.1数据结构研究的内容计算机中的非数值运算：字符、表格、声音、图象等(1)对所加工的数据对象进行逻辑组织数据元素及其数据项数据元素之间的逻辑关系：线性或是非线性(2)将数据对象存储在计算机中逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”物理结构要存储：数据元素本身和数据元素之间的关系物理结构的设计要满足：算法的实现、时间和内存
2、空间的节省(3)数据运算或处理基于某种特定程序语言的算法数据结构研究的内容(cont’d)用计算机解决一个具体问题的步骤：(1)从具体问题抽象出一个适当的数学模型寻求数学模型的实质是分析问题(2)设计一个解此数学模型的算法从中提取操作的对象，并找出这些操作对象之间含有的关系，用数学语言加以描述(3)编出程序、进行测试、调整直至得到最终解答数据结构研究的内容(cont’d)Example：1-1图书馆的书目检索系统自动化问题由四张表构成的文件为本系统的数学模型（见书P2）文档管理的数学模型—线性数据结构1-2计算机和人对奕问题格局（对奕过程中可能出现的棋盘状态）格局之间的关
3、系由比赛规则决定—非线性（树型）数据结构1-3多叉路口交通灯的管理问题非线性（图）数据结构数据结构研究的内容(cont’d)Example1-1：图书目录文件示例001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数栾汝书S02………………高等数学001,003,…理论力学002,…线性代数004,………樊映川001,…华罗庚003,…栾汝书004,………L002,…S001,003,………数据结构研究的内容(cont’d)Example1-2：井字棋对奕“树”oxxo(a)oxxooxxxoxoxxoxoxxooxxox(b)
4、(a)棋盘格局示例；(b)对奕树的局部oxxxo数据结构研究的内容(cont’d)Example1-3：五叉路口交通管理示意图(a)五叉路口CBADE在路口有13条可行的通路，如：AB和EC不能同时通行，如：EB和AD1.2基本概念和术语数据(Data)：对客观事物的符号表示数据元素(dataelement)：是作为整体考虑和处理的数据的基本单位数据项(DataItem)：组成数据元素，是数据不可分割的最小单位(主)关键字：能唯一标识数据元素的数据项次关键字：不能唯一标识数据元素的数据项数据对象(dataobject)：性质相同的数据元素的有限集数据结构(Data
5、Structure)：数据元素之间所具有的特定关系的有限集逻辑结构：数据元素之间的逻辑关系存储结构：数据结构在计算机中的表示基本概念和术语(cont’d)1、数据结构的形式化定义：Data-Structure=(D,R)二元组数据元素的有限集D上关系的有限集(逻辑结构)2、四种逻辑结构：(1)集合(2)线性结构：元素之间是一一对应的关系，首元素无前趋，尾元素无后继，其他元素都只有一个前驱和后继【例】Linear=(D,R)D={1,2,3,4,5}R={<1,2>,<2,3>,<3,4>,<4,5>}序偶12354基本概念和术语(cont’d)四种逻辑结构：(3)树型结构
6、：元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。【例】Tree=(D,R)D={a,b,c,d,e,f}R={,,,,}abcdef基本概念和术语(cont’d)四种逻辑结构：(4)图型结构：元素之间存在多对多的关系，任何元素之间都可以存在关系【例】Graph=(D,R)D={1,2,3,4}R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}3124基本概念和术语(cont’d)3、两种基本的存储结构：(1)顺序存储结构：利用元素在内存中相对位置来表示元
7、素之间的关系(2)链式存储结构：利用“指针”来单独存储数据元素之间的关系。这个“指针”不一定就是指针型数据，可能是个整型数据。1.3数据类型和抽象数据类型数据类型：是一个值的集合及定义于其上的一组操作的总称。也称为“抽象数据类型”。抽象数据类型的形式定义：ADT=(D,S,P)三元组数据对象D上的关系对D的基本操作软件系统的框架应该建立在数据之上，而不是操作（功能）之上抽象是强调数据类型的数学特性，而与它们在不同计算机中的实现方法和细节无关。使用抽象数据类型定义程序模块，将提高模块的复用率数据类型和抽象数据类型(cont’d)
