数据结构(C语言版) 胡学钢01-概述.ppt

课程背景 计算机相关专业的一门重要的专业基础课 主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法 是学习计算机其他相关课程的必备条件，是提高编程能力的必要条件 需程序设计类课程的支撑（C/C++/Java） 教材 教材： 胡学钢，《数据结构（C语言版）》高等教育出版社，2008年1月 参考书目： 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.2002年9月. 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.2003年5月. 胡学钢.《数据结构算法设计指导》.清华大学出版社.1999年2月. Robert L. Kruse, Alexander J.Ryba, 《Data Structures and Program Design In C++》.高等教育出版社.2001年5月 本课程的教学方式 课堂教学（60学时） 课后作业 实验上机（30学时） 考试（笔试） 课程设计 其他 本课程的主要内容 数据结构的基本概念; 线性表、栈和队列、串和数组; 树形结构; 图结构; 查找； 排序; 其他 一个问题引发的 国际象棋发明人的报酬 一个问题引发的 … … 第一章 概 述 第一章 概 述 1.1 研究内容 1.2 术语 1.3 算法及其描述 1.4 算法分析 1.1 研究内容 软件设计中常用的基本技术 1.2 术语 数据（data）—— 能够输入到计算机中并能被计算机识别、存储 分解 和处理的符号的集合.（广义） 数据元素（data element）—— 构成数据的基本单元（具有完整的 描述 独立意义）。某些场合还被称为元素、记录、 结点、顶点等。 数据项（字段）—— 元素的具体信息 数据结构（data structure）——构成数据的元素之间的结构关系。 线性结构 树状结构（树型结构） 图结构（网状结构） 集合 1.2 术语 数据结构示例： 1.2 术语 1.2 术语 逻辑结构 —— 线性、树形（树型）、图（网状）、集合 存储结构 —— 数据结构在内存中的实现形式 同样的逻辑结构≠同样的存储结构 运算（判断存储结构的好坏） 有关数据结构几个方面的联系图 1.3 算法及其描述 算法 —— 特定问题的求解方法, 指令的有限序列， 满足： (1) 输入 0～n个 (2) 输出 1～n 个 与输入有特定联系 (3) 确定性（无二义性） 相同的输入只能有相同的输出 (4) 有限性 执行次数有限 (5) 可行性 算法可用计算机在有限时间内实现 1.3 算法及其描述 算法描述语言 易懂，灵活 自然语言 不准确 准确，严格 计算机语言 死板 伪语言（类语言）：类pascal、类C、类C++ 算法举例： 1.求最大公因子（辗转相除法） 2.韩信点兵问题 3.幻方问题（纵横图） P7 补充语法 1.4 算法分析 算法的衡量指标： 在正确性的前提下 时间性能——运行算法的时间开销 空间性能——运行算法的辅助空间规模 其它性能——如可读性/可移植性 1.4 算法分析 时间性能（时间复杂度）： 以算法运行时间开销来度量 改进 与具体机器相关 以算