第7讲 算法与数据结构

《第7讲 算法与数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础TechnologyFundamentalsofComputerSoftware算法与数据结构艾骏01082316413aijun@buaa.edu.cn十四系011教研室数据结构概述有些算法的操作对象很简单，几个变量就行了。有些算法，操作的对象是一组相互有关的数据，脱离了数据的关联性算法就无从施展。结构：许多元素和它们的联系在拓扑空间形成有界的整体。这些元素如果是数据，即为数据结构本讲讨论数据结构，即为数据元素及其相互关系数据的结构关系•数据及其关系构成数据结构•数据结构只由两种集合构成：DS=(DR)

2、DS=(D,R)•D:数据集合，可以是单个数据集合，也可以是不同类型子集组成的大集合，甚至可以是数据结构•R:关系集合，指数据间的结构关系•数据结构是研究数据的结构关系•举例说明例DS=(D,R)111D={a,b,c,d,e}1R={(a,b)(),(b,c)(),(c,d)(),(d,e)(),(e,a)(),(a,c)(),(a,d)(),(b,e)(),(c,e)}1DS是一个无向图1•R={,,,,2,,,,,,<

3、c,e>,}•DS是一个有向图2数据结构的研究方法数据结构的分类及图形表示•基础的数据结构分四类表：元素是线性关系（连接）树：元素间是非线性关系，连接不得有回路图：元素间非线性关系（连接），连接有回路文件：记录的序列第6页线性表示例学号姓名性别籍贯电话通讯地址01张三男长沙8639000麓山南路327号02李四男北京23456789学院路435号03王五女广州30472589天河路478号04赵六男上海41237568南京路1563号05钱七女南京5013472南京大学06刘八女武汉61543726武汉大

4、学07朱九男昆明4089651云南大学08孙十女杭州6154372西湖路635号学生数据表第7页树性结构示例一层Ttabc二层a1a2b1b2c1cd三层2d1d2d3四层图2-2树形结构示意图第8页图形结构示例123645图形结构示意图第9页研究方法及内容•数据结构作为一个学科分支主要是研究程序设计中计算机所操作的对象以及它们之间的关系和运算•首先研究数据结构的逻辑结构有什么运算性质（逻辑结构）•用什么表示法表示这种逻辑结构（物理结构）•再按表示法和性质写出求解问题的算法（运算）第10页2、研究方法(续)（1）数据的逻辑

5、结构独立于计算机，是数据本身所固有的。（2）物理结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于物理结构。逻辑结构是客观世界数据关系的真实反映。讨论问题感兴趣是逻辑结构程序的实现离不开物理结构逻辑结构和物理结构是相对的第11页①数据的逻辑结构•数据元素之间的逻辑关系。它只抽象地反映数据元素集合的结构，而不管其存储方式•从结构的观点，一般将数据结构分为2大类：–线性数据结构：线性表、栈、队列、串、数组、文件–非线性数据结构：树、图2

6、．逻辑结构的分类（1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。第12页②数据的存储结构•在计算机中，数据只能按顺序方式存储。逻辑结构映象（Mapping）物理结构–映象使结构有了改变，即数据元素的关系变了，数据元素一般是不变的，但仍应保证能实施原有数据结构的运算。第13页数据的物理结构数据结构在计算机中的表示（映像），也称存储结构。1．顺序存贮（向量存贮）

7、所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。2．链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。第14页③数据的运算•程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。–每种逻辑结构都有一个运算集合。–常用的运算：检索、插入、删除、更新、排序等•简单数据结构是复杂数据结构的基础•复杂数据结构能提高解决问题的能力第15页线性表线性表•最基本的一种数据结构•逻辑结构：N个数据元素的有

8、限序列：（a,a,a,…,a)123n表中元素的个数n定义为线性表的长度（n≥0）n=0——空表第17页线性表的逻辑结构特征：（1）数据元素呈线性关系（2）在线性表中必存在唯的唯一的“第个第一个”、“最后一个”数据元素（3）除第一个元素外，每个元素都有且只有一个前驱元素（4）除最后一个元素外，每个元素都