通信数据结构课件陈雄峰第一章绪论.pptVIP

数据结构 ?? 2013～ 2014学年 第一学期 ? （总72学时：授课56学时，实验16学时） 任课班级 ： 12通信工程 主讲教师 ： 陈雄峰 课程性质 计算机专业的专业基础课 先修课：程序设计语言、离散数学 后续课：数据库、操作系统、编译原理等 考研的必考科目 学习目标 掌握基本的数据结构及其实现方法 掌握初步的算法分析技术 培养算法设计能力、程序设计能力 学习要求 真正理解基础知识和理论而不是背诵 保证足够的课外学习时间，课外学习时间至少是课堂教学时间的两倍 上课认真听讲，课后及时复习 独立完成作业，编程实现经典算法 教材 ?数据结构 ?(C语言版）严蔚敏等编著,清华大学出版社 参考书 《数据结构题集》，严蔚敏等编，清华大学出版社 ?数据结构 ?（用面向对象方法与C++描述） 殷人昆等编著，清华大学出版社 考核方式 1 ?数据结构 ?课程成绩组成 平时成绩20% 出勤+作业+期中成绩 实验成绩20% 程序+报告 期末考试成绩 60% 第一章 绪论 重点：数据结构、算法分析。 难点：算法分析、抽象数据类型。 知识点： 什么是数据结构 基本概念和术语 抽象数据类型 算法分析、性能分析与度量 学生成绩表格 选课单 UNIX文件系统结构图 非数值计算问题的数学模型是树、表和图之类的数据结构。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 基本概念和术语 数据(Data) 是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据元素（Data Element） 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录 数据对象 (data object) 具有相同性质的数据元素的集合。 整数数据对象 N = { 0, ?1, ?2, … } 字母字符数据对象 C={ ‘A’, ‘B’, ‘C’, … ‘Z’ } 数据结构（Data Structure） 形式定义： 某一数据对象的所有数据成员之间的关系。记为： Data_Structure = {D, S} 其中，D 是某一数据对象， S 是该对象中所有数据成员之间的关系的有限集合。 四个基本逻辑结构 集合 线性结构 树形结构 网状结构 数据的逻辑结构 从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。 逻辑结构指的是数据在人脑中的反映或认识。 数据的存储结构（物理结构） 数据结构在计算机中的表示。 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示 数据的逻辑结构和存储结构的关系 数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示 一种数据的逻辑结构可以用多种存储结构来存储 数据结构的基本操作是定义于逻辑结构，实现于存储结构 采用不同的存储结构，其数据处理的效率往往是不同的 抽象数据类型 是指一个数学模型以及定义在此数学模型上的一组操作 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型 例如：矩阵 +（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型 抽象数据类型的描述 抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中,数据对象、数据关系用伪码描述；基本操作定义格式为 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以打头， 除可提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。