数据结构 主讲：庄越

写在前面的话 本课程学习的是什么？ 学习在思考问题时， 不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考 学习在解决问题时， 不仅考虑人的处理方式，也要考虑计算机的处理方式 我是你亲密的朋友，你要理解和尊重我，也要能被我理解。 对你而言，是一场有趣的思维体操； 对我而言，是一座顺畅沟通的桥梁

写在前面的话 如何和我联系？ 本课程的网站： 办公室：2-204A 办公电话：37080178 Email：zyjiaoxue@163.com 本课程的网站： www.gdcp.cn/jpkc/sjjg

为什么要学数据结构？ 数据结构研究什么？ 重新理解算法。 如何分析算法的优劣？ 第一章 概论 为什么要学数据结构？ 数据结构研究什么？ 重新理解算法。 如何分析算法的优劣？

第一问题： 为什么要学数据结构 ？ Data Structure

用计算机处理的实际问题可分为两大类问题： 数值计算 非数值计算 数值计算问题： 在计算机发展初期，人们主要应用计算机来完成 科学计算，即处理数值计算问题，对于这类问题，可以 通过抽象出合适的数学模型，然后设计一个相应的算法 来解决。 在建筑设计时计算梁结构的应力要求解线性方程组 预报人口增长情况时要求解微分方程等。 非数值计算问题： 但是随着计算机应用领域的不断扩大，计算机更 多地应用于处理非数值计算问题，这类问题涉及到数据 元素间复杂的相互关系，一般无法用数学方程来描述。

现实中对象之间的关系 线性关系：如列车中各车箱之间的关系、排队买车 票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系：如学校的组织结构、人的辈分关系等。 网状关系：如城市铁路交通网、电话网、计算机网 络等。

实际问题中对象之间的关系—— 学生成绩管理 学生成绩表 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ： 关系：线性 特征：一个直接前趋， 一个直接后继 A07001 王萍 90 85 95 A07002 马玲 80 85 90 A07003 张兰 95 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78

实际问题中对象之间的关系 例2：“井字棋”的人机对弈 关系：树型 特征：一个直接前趋， 多个直接后继 × O × O × O × O × O … …

实际问题中对象之间的关系 例3：交通图的最短路径问题 关系：图型 特征：多个直接前趋， 多个直接后继 A6 7 4 A2 A4 5 9 A1 8 1 A3 A5 2 6

？ 第一问题： 为什么要学数据结构 计算机处理的大多属于非数值计算问题。 第一问题： 为什么要学数据结构 ？ 计算机处理的大多属于非数值计算问题。 解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。

第二问题 数据结构研究什么 ？

几个基本概念 数据(Data)是对客观事物的符号表示，能够被计算 机识别、存储和加工处理。它是计算机程序加工的 “原料”。 数据元素(Data Element)是数据的基本单位，在计算 机程序中通常作为一个整体进行考虑和处理，有时 数据元素也称为元素、结点、记录。 数据类型(Data Type)是具有相同性质的计算机数据 的集合及在这个数据集合上的一组操作。

数据结构的研究内容 数据结构 研究数据之间的相互关系，即数据的组织形式，包 括： 数据的运算，即基于某种存储结构对数据施加的操 作或运算。 数据元素之间的逻辑关系，也称为数据的逻辑结构 (Logical structure)。 数据元素及其关系在计算机存储器内的表示，称为数 据的存储结构(storage structure)。 数据的运算，即基于某种存储结构对数据施加的操 作或运算。 数据结构 结构 + 运算 ＝ 逻辑结构 存储结构

数据结构在计算机科学中的地位 数据结构 数据结构 程序 结构 运算 逻辑结构 存储结构 算法 + ＝ 瑞士计算机科学家沃思(N.Wirth)教授提出： 数据结构 算法 + ＝ 程序 程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 数据结构是计算机软件和计算机应用专业的核心课程之一，由于在计算机系统软件和应用软件中都要用到各种数据结构，要想更有效地使用计算机，就必须学习数据结构的有关知识。

数据结构在软件从业人员的知识与技能结构中的地位 系统分析员 需求分析 系统设计 高级程序员 详细设计 程序设计 程序员、初级程序员 程序设计 程序测试

数据结构在软件从业人员的知识与技能结构中的地位 编程语言 解决问题的思想

推荐阅读-- 《程序员》杂志 2006年4月特别策划《算法的力量》 特别策划《程序员的七种武器》 李开复.《算法的力量》 百度首席架构师揭密：算法是百度工程师的利器 影响算法世界的十位大师 特别策划《程序员的七种武器》 左轻候.《最基础的数据结构》

任何受过专业训练的程序员，对“数据 结构”这门课程中涉及到的各种数据结构都 不会陌生，但是在实际的编程工作中，大部 分的数据结构都不会用到，而且也永远都不 会用到。虽然如此，深入地理解基本数据结 构的概念和实现细节，仍然是每个程序员的 任务。这不仅仅是因为，掌握这些知识将有 利于更加正确和灵活地应用它们，而且也是 因为，对于语言背后的实现细节的求知欲是 一个优秀程序员的素质。 --摘自《最基础的数据结构》

关于数据结构中的结构 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储无关，是独立于计算机的，可以看作是从具体问题 抽象出来的数学模型。数据的逻辑结构有两大类： 线性结构：线性表 非线性结构：树和图 数据的存储结构是逻辑结构用计算机语言的实现，它是 依赖于计算机语言的。数据的存储结构有以下四种基本 的存储方法。 顺序存储方法 链接存储方法 索引存储方法 散列存储方法

关于数据结构中的算法 数据的运算是定义在数据的逻辑结构上的，每 种逻辑结构都有一个运算的集合。 最常用的运算有查找、插入、删除、更新、 排序等。 重点研究的两类基本算法： 查找 排序

本课程的结构 线性表 栈 队列 串 多维数组 树 图 查找 排序 线性结构 非线性结构 算法

第二问题 数据结构研究什么 ？ 逻辑结构 存储结构 运算

第三问题 重新理解算法Algorithm

算法的基本特征 通俗地讲，一个算法就是一种解题方法 更严格地说，算法是由若干条指令组成的有穷序列 算法必须满足下述准则： 算法的描述 输入：具有0个或多个输入的外界量。 输出：至少产生一个输出。 有穷性：每一条指令的执行次数必须是有限的。 确定性：每条指令的含义都必须明确，无二义性。 可行性：每条指令的执行时间都是有限的。 算法的描述 自然语言 伪高级语言

？ 算法 == 程序 算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。

算法存在的辨证关系 数据结构与算法的辨证关系 给定了数据的逻辑结构后，对同一逻辑结构而言， 由于存储结构的不同，定义的运算也是不同的。 如线性表是一种逻辑结构，若采用顺序存储方法表示，则 称为顺序表；若采用链式存储方法表示，则称为链表。 相同的运算在顺序表和链表上的实现方法是不同的。

第四问题 如何分析算法的优劣？ 两个指标： 时间复杂度 空间复杂度

评价算法的优劣 主要考虑如下三点： 执行算法所耗费的时间 执行算法所耗费的存储空间，其中主要 考虑辅助存储空间； 算法应易于理解，易于编码，易于调试 等等。

世界是平衡的 我们希望选用一个所占存储空间小、运行时间短、 其它性能也好的算法。然而，实际上很难做到十全 十美。原因是上述要求有时相互抵触，要节约算法 的执行时间往往要以牺牲更多的空间为代价，而为 了节省空间可能耗费更多的计算时间。因此我们只 能根据具体情况有所侧重。 若该程序使用次数较少，则力求算法简明易懂； 对于反复多次使用的程序，应尽可能选用快速的算法； 若待解决的问题数据量极大，机器的存储空间较小， 则相应算法主要考虑如何节省空间。

关于空间复杂度的分析 例: 数组的转置

关于时间复杂度的分析 一个算法所耗费的时间，应该是该算法中每条语句的 执行时间之和，而每条语句的执行时间是该语句的执 行次数(也称为频度(Frequency Count))与该语句执行一 次所需时间的乘积。 常数阶O(1) 对数阶O(1og2n) 线性阶O(n) 线性对数阶O(nlog2n) O(n2)、O(n3)、…、O(nk)、 指数阶O(2n)。