课件数据结构1ch

1、数据结构教师介绍: 姓名: 姜存理 毕业学校: 同济大学 办公室:综合楼501 办公室电话: 50214252 第一章 绪言1.1 什么是数据结构 程序=数据结构+算法例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2 人机对奕问题树.多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科1.2 基本概念和术语数据（data)所有能输入到计算机中去的描述客观事物的符号数据元素（da

2、ta element）数据的基本单位，也称节点（node）或记录（record）数据项（data item）有独立含义的数据最小单位，也称域(field)数据结构（data structure)数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：顺序存储结

3、构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3 元素41345h存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 1346 链式存储 h 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链

4、式存储 线性表栈队树形结构图形结构数据结构的三个方面：数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例 C语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;4、数据类型和抽象数据类型抽象数据类型 (ADT)Abstract Data Type 简称ADT;是指一个数学模型以及定义在

5、此数学模型上的一组操作。4、数据类型和抽象数据类型抽象数据类型 (ADT)Abstract Data Type 简称ADT;是指一个数学模型以及定义在此数学模型上的一组操作。例如: “整数”是一个抽象数据类型。其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。4、数据类型和抽象数据类型抽象数据类型 (ADT)抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。在构造软件系统的各个相对独立的模块时，定义一组数据和施与这些数据之上的一组操作，并在模块内部给出它们的表示和实现细节，在模块外部使用的只是抽象的数据和抽象的操作。4、数据类型和抽象数据类型抽象数据类型的描

6、述方法抽象数据类型可用（D，S，P）三元组表示其中，D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。 4、数据类型和抽象数据类型ADT 有两个重要特征:数据抽象 ：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节4、数据类型和抽象数据类型抽象数据类型定义格式ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）初始

7、条件：初始条件描述操作结果：操作结果描述 4、数据类型和抽象数据类型抽象数据类型定义格式例如，定义抽象数据类型“复数”数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分, | e2 是复数的虚数部分 4、数据类型和抽象数据类型抽象数据类型定义格式基本操作：ADT Complex plex( &Z, v1, v2 )操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值 plex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。4、数据

8、类型和抽象数据类型抽象数据类型定义格式基本操作（续） ：GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 ADT Complex4、数据类型和抽象数据类型抽象数据类型的实现如果，一旦有定义好的ADT，那么根据选用的高级语言即可具体实现。 下面以C语言为例，实现上述的“复数”ADT4、数据类型和抽象数据类型抽象数据类型的实现/* 存储结构的定义 */ typedef struct float realpart；

9、 float imagpart； complex；4、数据类型和抽象数据类型抽象数据类型的实现/* 基本操作的函数原型说明 */void Assign(complex &Z, float realval,float imagval)；/ 构造复数 Z,其实部和虚部分别被赋以参数 / realval 和 imagval 的值float GetReal( cpmplex Z )；/ 返回复数 Z 的实部值float Getimag( cpmplex Z )；/ 返回复数 Z 的虚部值void add(complex plex z2, complex &sum )； / 以 sum 返回两个复数 z

10、1, z2 的和 4、数据类型和抽象数据类型抽象数据类型的实现/* 基本操作的细节实现 */void add(complexz1, complexz2, complex &sum ) / 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 抽象数据类型的实现对于某些高级语言已经有相应的概念，如C+中的类;而有些则没有，如C语言中，此时只能结构体来处理数据结构，而用函数来处理操作。4、数据类型和抽象数据类型4、数据类型和抽象数据类型AD

11、T角度的数据结构层次图1.4 算法的描述和算法分析简介算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性算法的描述采用C语言算法的评价衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本 身的优劣 2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语