[理学]数据结构第一讲.ppt

桂林电子科技大学信息科技学院 赵莹莹 桂林电子科技大学信息科技学院 赵莹莹 教材书 《数据结构——C语言版》 赵坚等编著 中国水利水电出版社 简介 什么是数据结构(Data Structure)？为什么要学习数据结构？ 介绍本书 C描述 学习方法 对大家的要求 记笔记，按时完成作业，完成思考题，确定辅导时间 大家对我的要求 欢迎大家随时跟我联系，提意见给我，或给这门课 数据结构 第一章 绪论 本章要点 一、什么是数据结构（重点） 二、算法描述 三、算法分析与评价（重点） 四、小结 1.1 什么是数据结构 数据结构包含两个方面： 数据的逻辑结构 数据的物理结构 著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出： 算法+数据结构=程序 ??数据结构：是指数据的逻辑结构和存储结构 ? 算法：是对数据运算的描述 1.1.1 数据结构举例（1） 【例1.1】电话号码查询问题 。 编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。 1.1.1 数据结构举例（2） 【例1.2】 判定树问题。 有八枚硬币分别用a，b，c，d，e，f，g，h表示，其中有一枚且仅有一枚硬币是伪造的，假硬币的重量和真硬币的重量不同，可能轻，也可能重。现要求设计算法，用最少的比较次数挑选出假硬币，并同时确定这枚假硬币的重量比其他硬币的重量是重还是轻。 1.1.1 数据结构举例（3） 【例1.3】 最小代价问题。 假设几个村庄之间要架设输电线路，根据电能的可传递性，并不需要在每对村庄之间架设线路。如何用最小代价架设线路让每个村庄都能用上电。 1.1.2 基本概念和术语 数据（Data）：是对客观事物的符号表示，它能被计算机识别、存储和加工处理。 数据元素（Data Element）：是数据的基本单位，有时也称为元素、结点、顶点、记录。一个数据元素可能由若干数据项(Data Item)组成。 数据结构：是指数据元素之间的相互关系，即数据的组织形式。 1.1.3 数据结构 二，数据的存储结构： 顺序存储：将数据元素依次存储于一组地址连续的存储单元中，元素间的逻辑关系由存储单元的位置直接体现。 链接存储：将数据元素存储在一组任意的存储单元当中，用附加的指针域表示元素之间的逻辑关系。 索引存储：该方法的特点是在存储数据元素的同时，还可以建立附加的索引表。索引表中每一项称为索引项。索引项的一般形式是：(关键字，地址)。 关键字是指能唯一标识数据元素的数据项 散列存储：该方法是依据数据元素的关键字，用一个事先设计好的函数计算出该数据元素的存储地址，然后把它存入该地址中。这种函数称为散列函数，由散列函数计算出的地址称为散列地址。 本章要点 一、什么是数据结构（重点） 二、算法描述 三、算法分析与评价（重点） 四、小结 1.2.1 算法定义及特性 一、定义： 算法(Algorithm)：为了解决一个或者一类问题给出的一个确定的、有限长的操作序列。 二，特性 有穷性 确定性 可行性 输入 输出 1.2.2 算法的描述 (1)、自然语言：用自然语言来描述算法的优点是简单且便于人们对算法的阅读，缺点是不够严谨，容易产生二义性。 (2)、流程图、N-S图等：其特点是描述过程简洁明了。 (3)、程序语言：难度较大且不太直观，需要借助注释才能使人看明白。 (4)、伪码：伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。 本章要点 一、什么是数据结构（重点） 二、算法描述 三、算法分析与评价（重点） 四、小结 1.3.1 算法设计的要求 通常对算法的评价按照下面五个指标来衡量： 正确性(Correctness)：满足说要求解问题的需求。 可读性(Readability)：指算法要便于人们阅读、交流与调试。可读 性好有助于人们对算法的理解；晦涩难懂的算法易于隐藏错误且难以 调试和修改。 健壮性(Robustness)：当输入数据非法或运行环境改变时，算法能 恰当地做出反应或进行处理，不会产生莫名其妙的输出结果。 时空效率(Efficiency)：要求算法的执行时间尽可能地短，占用的存 储空间尽可能地少。但这两者往往相互矛盾。 可用性：应能方便地被使用。 1.3.2 算法效率的度量 通常情况下用算法的时间复杂度与空间复杂度来评价算 法的优劣 。 一，时间复杂度(Time Complexity)：是指算法运行从开始到结束所需