数据结构 C语言版 姓名 薛均晓办公室 302 63887286 Email xuejx 2 90 数据结构 C语言版 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内部排序 3 90 数据结构 C语言版 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内部排序 4 90 第一章绪论 知识点数据结构中常用的基本概念和术语算法描述和分析方法难点算法复杂性的分析方法要求了解数据的逻辑结构和物理结构 算法的基本概念 它们对于程序设计的重要性以及相互关系掌握算法复杂性的概念及分析方法 5 90 第一章绪论 内容 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 6 90 第一章绪论 内容 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 7 90 电子计算机的主要用途 早期 主要用于数值计算 后来 处理逐渐扩大到非数值计算领域 能处理多种复杂的具有一定结构关系的数据 1 1什么是数据结构 8 90 二十世纪四十年代 电子数字计算机问世就是解决复杂的计算问题 早期 电子计算机的应用范围 也只局限于科学和工程的计算 其处理的对象是纯数值性的信息 通常 人们把这类问题称为数值计算 随着计算机科学技术的迅猛发展 计算机的应用已从传统的数值计算领域发展到各种非数值计算领域 当前 计算机已广泛地应用于情报检索 企业管理 系统工程等各个领域 与此相应 计算机的处理对象也从简单的纯数值性数据发展到一般的符号和具有一定结构的数据 1 1什么是数据结构 9 90 1 1什么是数据结构 计算机解决问题的步骤 10 90 1 1什么是数据结构 计算机解决问题的第一步 如何抽象出数学模型 方程 实质是分析问题 从中提取操作的对象 数据元素 并找出这些操作对象之间含有的关系 然后用数学语言加以描述 数值计算问题 求几何元素的面积 体积等 预报人口增长非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述 11 90 例1书目自动检索系统 书目文件 12 90 例2人机对奕问题 13 90 例3多叉路口交通灯管理问题 交通灯问题等同于图顶点的染色问题 满足两个要求即可 每个顶点一种颜色 有线相连的不能同色 14 90 1 1什么是数据结构 综上可知 对于非数值计算问题 描述问题的模型不再是方程 而是诸如表 树 图等数据结构 求解非数值计算的问题 首先要考虑对相关的各种信息如何表示 组织和存储 即 设计出合适的数据结构及相应的算法 因此 简单说来 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 15 90 数据结构课程的形成和发展 形成阶段 60年代初期 数据结构 有关的内容散见于操作系统 编译原理和表处理语言等课程 1968年 数据结构 被列入美国一些大学计算机科学系的教学计划 1968年美国唐 欧 克努特教授开创了数据结构的最初体系 他所著的 计算机程序设计技巧 第一卷 基本算法 是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作 发展阶段 数据结构的概念不断扩充 包括了网络 集合代数论 关系等 离散数学结构 的内容 70年代后期 我国高校陆续开设该课程 1 1什么是数据结构 16 90 数据结构 课程所处的地位 1 1什么是数据结构 17 90 数据结构 在计算机科学中是一门综合性的专业基础课 数据结构是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 数据结构这一门课的内容不仅是一般程序设计 特别是非数值性程序设计 的基础 而且是设计和实现编译程序 操作系统 数据库系统及其他系统程序的重要基础 1 1什么是数据结构 18 90 第一章绪论 内容 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 19 90 1 2基本概念和术语 数据定义一 数据是客观事物的符号表示 例 张三的C语言考试成绩为92分 92就是该同学的成绩数据 20 90 1 2基本概念和术语 数据定义二 能输入到计算机中并被计算机程序处理的符号的总称 例 图像 声音等 21 90 1 2基本概念和术语 数据总结 现实世界信息的分析 复制 传播首先要符号化 这样才便于处理 尤其是便于计算机的处理 22 90 1 2基本概念和术语 数据元素 数据项 数据元素 表示一个事物的一组数据称为一个数据元素 dataelement 数据元素是数据的基本单位 即数据集合中的一个个体 也称元素 结点 顶点 记录 数据项 构成数据元素的数据称作该数据元素的数据项 dataitem 数据项是数据元素的不可分割的最小单位 数据元素由数据项 dataitem 组成 23 90 1 2基本概念和术语 数据元素 数据项 数据元素 数据项 数据 24 90 1 2基本概念和术语 数据对象 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 如上例 某图书馆的图书信息表可以看作一个数据对象 整数数据对象的集合可表示为N 0 1 2 字母字符数据对象的集合可表示为C A B Z 25 90 1 2基本概念和术语 数据结构表示 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 Data Structure D S 其中 D 数据对象 S D上的关系集 26 90 1 2基本概念和术语 数据结构 具体地说 数据结构包括三个方面 逻辑结构存储结构运算 27 90 1 2基本概念和术语 数据结构 这三个方面的关系为 1 数据的逻辑结构独立于计算机 是数据本身所固有的 2 存贮结构是逻辑结构在计算机存储器中的映像 必须依赖于计算机 3 运算是指所施加的一组操作总称 运算的定义直接依赖于逻辑结构 但运算的实现必须依赖于存储结构 28 90 1 2基本概念和术语 逻辑结构 数据的逻辑结构是对数据元素之间逻辑关系的描述 它可以用一个数据元素的集合和定义在此集合上的若干关系来表示 数据的逻辑结构常简称为数据结构 基本的逻辑结构有3种 线性结构 树结构和图结构 29 90 1 2基本概念和术语 逻辑结构 1 线性结构线性结构的特征 每个数据元素有且仅有一个直接前驱元素 第一个元素除外 有且仅有一个直接后继元素 最后一个元素除外 30 90 例 线性结构 表学生信息表 31 90 1 2基本概念和术语 逻辑结构 2 树结构树结构的特征 每个数据元素有且仅有一个直接前驱元素 树根元素除外 但可以有任意多个直接后继元素 32 90 例 树结构 33 90 1 2基本概念和术语 逻辑结构 3 图结构图结构的特征 每个数据元素可以有任意多个直接前驱元素 也可以有任意多个直接后继元素 34 90 例 图结构 图南京飞往昆明的航班路线图 35 90 1 2基本概念和术语 逻辑结构 4 集合结构数据元素间除 同属于一个集合 外 无其它关系 元素间为松散的关系 上节内容回顾 数据 数据元素 数据项 数据对象数据结构 数据结构的三要素数据的逻辑结构 36 90 37 90 练习 用图形表示下列数据结构 并指出它们属于什么类型数据结构 S D R D a b c d e f R a e b c c a e f f d S D R D di 1 i 5 R di dj i j 38 90 S D R D a b c d e f R a e b c c a e f f d 解1 上述表达式可用图形表示为 bcaefd 此结构为线性的 39 90 S D R D di 1 i 5 R di dj i j d1d5d2d4d3 该结构图 解2 上述表达式可用图形表示为 40 90 1 2基本概念和术语 存储结构 数据元素在计算机中的存储表示方式称为数据的存储结构 也称为物理结构 数据的存储结构要能够正确反映数据元素之间的逻辑关系 数据存储结构有2种基本形式 顺序存储结构 链式存储结构 41 90 1 2基本概念和术语 存储结构 1 顺序存储结构顺序存储结构是把数据元素存储在一块连续地址空间的内存中 其特点是逻辑上相邻的数据元素在物理上也相邻 数据间的逻辑关系表现在数据元素的存储位置关系上 借助元素在存储器中的相对位置表示它们间的逻辑关系 42 90 43 90 1 2基本概念和术语 存储结构 2 链式存储结构链式存储结构是使用指针把相互直接关联的结点 即直接前驱结点或直接后继结点 链接起来 其特点是逻辑上相邻的数据元素在物理上 即内存存储位置上 不一定相邻 数据间的逻辑关系表现在结点的链接关系上 借助指针表示数据元素间的逻辑关系 44 90 1536 元素2 1400 元素1 1346 元素3 元素4 1345 h 链式存储 h 45 90 1 2基本概念和术语 运算 每种逻辑结构都涉及到一些基本运算 这些基本运算实际上是定义在抽象的数据上的一系列操作 最常用的运算有 检索 插入 删除 修改 排序等 46 90 1 2基本概念和术语 总结 数据结构包括三个方面 数据的逻辑结构数据的存储结构运算 查找 插入 删除 修改 排序等 线性结构树结构图集合 顺序存储链式存储 47 90 总之 数据结构所要研究的主要内容简单归纳为以下三个方面 研究数据元素之间的客观联系 逻辑结构 研究数据在计算机内部的存储方法 存储结构 研究如何在数据的各种结构 逻辑的和物理的 上实施有效的操作或处理 算法 所以数据结构是一门抽象地研究数据之间的关系的学科 1 2基本概念和术语 48 90 1 2基本概念和术语 数据类型 数据类型 DataType 是一个值的集合和定义在该值集上的一组操作的总称 数据类型是和数据结构密切相关的一个概念 用以刻画 程序 操作对象的特征 49 90 1 2基本概念和术语 数据类型 在高级程序语言中 数据的取值范围及其上可以进行的操作的总称即数据类型 例如 C语言中提供 int char float double等基本数据类型 数组 结构体 共用体 枚举等构造数据类型 还有指针 空 void 类型等 用户也可用typedef自己定义数据类型 typedefstruct intnum charname 20 floatscore STUDENT STUDENTstu1 stu2 p 50 90 C的数据类型 数据类型 基本类型 整型 短整型 short 整型 int 长整型 long 实型 浮点型 单精度型 float 双精度型 double 数值类型 字符类型 char 枚举类型 enum 构造类型 组合类型 数组类型结构体类型 struct 共同体类型 union 文件类型 file 指针类型 空类型 void 不返回任何类型的数据 51 90 为什么要规定数据类型 C语言规定 在程序中用到的每一个变量都要指定它们属于哪一种类型 这是因为 1 不同类型的数据在内存中占不同长度的存储区 而且数据在计算机内的表示形式也不同 例如 一般微机2bytes存放一个整型4bytes存放一个实型 2 一种数据对应着一个值的范围 int 32768 32767 float10 38 1038之间 52 90 例如 整型数据可以进行求余 5 2 1 而实数不能进行求余运算 数值型数据可以进行四则运算 而结构型数据就不能进行四则运算 一个变量应有确定的类型 在一个程序中一个变量只能属于一个类型 不能先后被定义为二个或多个不同的类型 3 一种数据类型对应一组允许的操作 53 90 1 2基本概念和术语 数据类型 引入数据类型的目的 数据类型主要是告诉编译器的 怎么去产生二进制代码 提高程序编译速度与准确度例如 如果没有数据类型 怎么知道数字1到底是整数 浮点数 还是个指针 54 90 1 2基本概念和术语 数据类型 对用户而言 数据类型 定义后 不用关心数据的硬件存储形式 方便使用 55 90 1 2基本概念和术语 数据类型 数据类型根据是否允许分解分为原子类型和结构类型 其中原子类