(1.1.1)--1.1什么是数据结构.ppt

《(1.1.1)--1.1什么是数据结构.ppt》由会员分享，可在线阅读，更多相关《(1.1.1)--1.1什么是数据结构.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第 一 讲：什么是数据结构数据结构与算法数据结构与算法1.1 什么是什么是数据结构数据结构好的好的数据结构数据结构可以带来最优效率的可以带来最优效率的算法算法程序程序=算法算法+数据结构数据结构图灵奖获得者图灵奖获得者尼古拉斯尼古拉斯沃斯沃斯1.1 什么是什么是数据结构数据结构问题求解的过程框架：问题求解的过程框架：实际问题实际问题求解算法求解算法测试、调整测试、调整 程序设计程序设计 数据结构组织数据结构组织 数据结构课程中的内容数据结构课程中的内容数学模型数学模型抽象抽象 构造求解算法构造求解算法 数据结构设计数据结构设计 程序实现程序实现 4 例例1 1 如何在书架上摆放图书如何在书架

2、上摆放图书 非数值计算问题举例非数值计算问题举例1：ontents什么是数据结构什么是数据结构5 例例1 如何在书架上摆放图书如何在书架上摆放图书ontents什么是数据结构什么是数据结构例例1 如何在书架上摆放图书如何在书架上摆放图书图书的摆放至少是跟图书的摆放至少是跟两个操作两个操作直接相关的：直接相关的：插入：插入：新书怎么插入？新书怎么插入？查找：查找：如何查找指定的某本书？如何查找指定的某本书？6什么是数据结构什么是数据结构例例1 如何在书架上摆放图书如何在书架上摆放图书方法1：随便放插入：插入：新书怎么插入？新书怎么插入？哪里有空放哪里！哪里有空放哪里！查找：查找：如何查找指定的某

3、本书？如何查找指定的某本书？顺序查找顺序查找7什么是数据结构什么是数据结构例例1 如何在书架上摆放图书如何在书架上摆放图书方法2：按书名拼音字母顺序存放查找：查找：如何查找指定的某本书？如何查找指定的某本书？二分查找二分查找8什么是数据结构什么是数据结构A B CEDF GH I J K L MN OP QRXT U V WSY Z例例1 如何在书架上摆放图书如何在书架上摆放图书方法2：按书名拼音字母顺序存放插入：插入：新书怎么插入？新书怎么插入？确定插入位置确定插入位置,之后的书全部后移之后的书全部后移,空位插入空位插入9什么是数据结构什么是数据结构ZYA B CEDF GH I J K L

4、 MN OP QRXT U V WS例例1 如何在书架上摆放图书如何在书架上摆放图书方法3：按照书的类别划分区域，同类内按拼音字母顺序存放插入：插入：新书怎么插入？新书怎么插入？先定类别先定类别,再二分查找确定位置再二分查找确定位置,移出空位插入！移出空位插入！查找：查找：如何查找指定的某本书？如何查找指定的某本书？先确定类别，再二分查找先确定类别，再二分查找10什么是数据结构什么是数据结构例例1 如何在书架上摆放图书如何在书架上摆放图书方法3：按书按照书的类别划分区域，同类内按拼音字母顺序存放面临的新问题：面临的新问题：每类的空间应如何分配？每类的空间应如何分配？类别应该分多细？类别应该分多

5、细？11什么是数据结构什么是数据结构例例1 如何在书架上摆放图书如何在书架上摆放图书方法1、方法2、方法3：书架问题总结书架问题总结：解决问题方法的解决问题方法的效率效率，跟，跟数据的组织方式数据的组织方式是直是直接相关的。接相关的。12什么是数据结构什么是数据结构13例例2 2 田径赛的时间安排问题田径赛的时间安排问题（无向图的着色问题）（无向图的着色问题）例例2：田径赛的时间安排问题田径赛的时间安排问题ontents数据结构的概念数据结构的概念 设有六个比赛项目，规定每个选手至多可参加设有六个比赛项目，规定每个选手至多可参加三个项目三个项目,有人报名参加比赛（如下表所示）设计比有人报名参加

6、比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。赛日程表，使得在尽可能短的时间内完成比赛。14（1）设用如下六个不同的代号代表不同的项目：）设用如下六个不同的代号代表不同的项目：跳高跳高 跳远跳远 标枪标枪 铅球铅球 100米米 200米米 A B C D E F姓名项目1项目2项目3丁一 A B E马二 C D 张三 C E F李四 D F A王五 B F（2）用顶点代表比赛项目）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。ontents 例例2田径赛时间安排问题的解法田径赛时间安排问题的解法数据结构的概念数据结构的概念B

7、AEFDC（3）某选手比赛的项目必）某选手比赛的项目必定有边相连（不能同时比赛）定有边相连（不能同时比赛）15比赛时间 比赛项目1A，C2B，D3E4FBAEFDContents 例例2田径赛时间安排问题的解法田径赛时间安排问题的解法数据结构的概念数据结构的概念BAEFDC 日程安排结果是唯一的吗？日程安排结果是唯一的吗？只需安排四个单位时间进行比赛什么是数据结构？什么是数据结构？数据对象的数据对象的组织方式组织方式:逻辑结构：逻辑结构：表示数据元素之间的逻辑关系。表示数据元素之间的逻辑关系。物理结构：物理结构：数据结构在计算机内的存储方式。数据结构在计算机内的存储方式。数据对象必定与一系列加

8、在其上的数据对象必定与一系列加在其上的操作操作相关相关联。联。完成这些操作所用的方法就是完成这些操作所用的方法就是算法算法。1617逻辑结构逻辑结构(Logical Structure)(Logical Structure)l线性结构：线性结构：存在存在一对一一对一的关系。的关系。l树形结构：树形结构：存在存在一对多一对多的关系。的关系。l图：图：多对多多对多的关系。的关系。l集合：仅同属一个集合集合：仅同属一个集合。存储结构存储结构 (Storage Structure)(Storage Structure)运算（运算（OperationsOperations）ontents数据结构的三个数据结构的三个方面：方面：什么是数据结构什么是数据结构什么是数据结构数据结构的三要素：数据结构的三要素：给定数据，分析数据元素之间的给定数据，分析数据元素之间的逻辑结构逻辑结构，采取恰当的采取恰当的存储结构存储结构，实现数据的，实现数据的运算运算。数据结构课程的定义：数据结构课程的定义：数据结构是一门研究数据结构是一门研究非数值非数值计算的程序设计计算的程序设计问题中计算机的问题中计算机的操作对象操作对象以及它们之间的以及它们之间的关关系系和和操作操作的学科的学科。18