数据结构名师课件5

《数据结构名师课件5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATA1065865ABCDEFG数据结构与算法课程简介课程内容：计算机软件的基础知识—数据结构数据结构＋算法＝程序数据结构：问题的数学模型线性结构：线性表、栈、队列非线性结构：树、图算法：处理问题的策略查找、排序（算法基础）数据结构的教学要求：学会分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构以及相应的算法。简而言之——分析待处理的对象的特性以及各处理对象之间存在的关系。教材：数据结构（C语言版）严蔚敏清华大学出版社课时安排：76学时（60/16）4.5学分与其他课程的关系先修课：程序设计语言C程序

2、设计语言——算法描述的基础之一后续课：算法基础1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法的描述和算法分析第一章绪论对问题的解决方法是：寻找问题分析问题解决问题而对计算机来说：从具体问题数学模型设计算法编程测试调整解决问题1.1什么是数据结构例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2人机对奕问题树……..……..…...…...…...…...结论描述这类非数值计算问题的数学模型不是数学方程，而是树、表

3、和图之类的数据结构。数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。1.2基本概念和术语数据（Data)信息的载体所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。例如：数字、字母、汉字、图形、图像、声音都称为数据。数据元素（Dataelement）——构成数据的基本单位，具有独立意义，可以分割成若干个具有不同属性的项（字段），也称节点（node）或记录（record）。数据项（Dataitem）——数据不可分割的最小单元，也称域

4、(field)。数据元素可以是数据项的集合数据对象（DataObject）——性质相同的数据元素的集合。e.g.C={’A’，’B’，…，’Z’}字母字符数据对象数据结构（DataStructure）---带结构的数据元素的集合。研究数据结构，包括研究数据的逻辑结构和数据的存储结构。假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a

5、1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:col={,,}a1a3a5a2a4a6a1a2a3a4a5a6row={,,,}再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{

6、i=1,2,3,4,5}可见，不同的“关系”构成不同的“结构”

7、或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据的逻辑结构不考虑具体存储形式，只抽象反映数据元素的逻辑关系。可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据的存储（物理）结构——逻辑结构在计算机（存储器）中的表示（或称映象

8、），包括数据元素的表示和关系的表示，“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有

9、不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型。typedefintLong_int[3]定义长整数为:数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储