数据结构-计算机与软件学院-深圳大学.ppt

课程简介 《数据结构》课程简介 本课程教材为： 《数据结构》(C语言版) 　严蔚敏，吴伟民 　清华大学出版社 　2004年11月（第28次印刷） 《数据结构》课程简介 　所有课件、作业及实验，均上传至： 深圳大学首页－－ 课程中心－－ 输入学生姓名及密码，实现登录－－ 从《数据结构》课程下下载 第一章数据结构绪论 一、数据 是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合 数值性数据 非数值性数据 二、数据元素（Data Element） 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成（此时数据元素被称为记录） 数据元素又称为元素、结点、记录 三、数据项（Data Item） 具有独立含义的最小标识单位。 四、数据对象（Data Object） 具有相同性质的数据元素的集合。 整数数据对象 N = {0, ?1, ?2, … } 字母字符数据对象 C={ ‘A’, ‘B’, ‘C’, … ‘F’ }。 五、结构（Structure） 　结构是元素之间的： 空间位置关系 相互作用和依赖关系 五、结构 　四种基本结构 集合结构 线性结构 树形结构 图形结构 六、数据结构（Data Structure） 1. 形式定义： 某一数据对象的所有数据成员之间的关系。记为： Data_Structure = {D, S} 其中，D 是某一数据对象， S 是该对象中所有数据成员之间的关系的有限集合。 六、数据结构 2. 线性数据结构举例 L = {K, R} K = {1, 2, 3, 4, 5, 6} R = {1,2, 2,3, 3,4, 4,5, 5,6} 六、数据结构 3. 树形数据结构举例 T = {K, R} K = {1, 2, 3, 4, 5, 6} R = {1,2, 1,3, 2,4, 2,5, 3,6} 六、数据结构 4. 图形数据结构举例 G = {K, R} K = {1, 2, 3, 4, 5, 6} R = {(1,2), (1,5), (1,6), (2,3), (2,4), (2,6), (3,4), (4,5), (4,6), (5,6)} 七、应用举例 1. 线性数据结构举例 数据结构学生选课名单（部分） 七、应用举例 2. 树形数据结构举例 UNIX文件系统结构图（部分） 七、应用举例 3. 图形数据结构举例 深圳城市交通示意图（部分） 八、数据结构要解决的问题 如何为应用程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实现软件功能 从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现 一、逻辑结构 逻辑结构描述数据元素之间的关系 线性结构 线性表（表，栈，队列，串等） 非线性结构 树（二叉树，Huffman树，二叉排序树等） 图（有向图，无向图等） 二、物理结构（存储结构） 物理结构是数据结构在计算机中的表示（或映象） 顺序存储表示（可以用C语言中一维数组表示） 链接存储表示（可以用C语言中的指针表示） 索引存储表示 散列存储表示 二、物理结构（存储结构） 复数存储结构举例 一、数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+, -, x, /等 二、原子数据类型和结构数据类型 1. 原子数据类型 是不可分解的数据类型 如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void)等 二、原子数据类型和结构数据类型 2. 结构数据类型 由若干成分（原子类型或结构类型）按某种结构组成的数据类型 结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体 如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如int A[10]） 三、抽象数据类型（Abstract Data Type） 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离 三、抽象数据类型（ADT） 抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作 抽象数据类型 = 数据结构 + 定义在此数据结 构上的一组操作 三、抽象数据类型（ADT表示） 抽象数据类型可用（D，S，P）三元组表示 D是数据对象 S是D上的关系集 P是对D的基本操作集。 三、抽象数据类