第2章数据结构及其应用1概念和线性结构

《第2章数据结构及其应用1概念和线性结构》由会员分享，可在线阅读，更多相关《第2章数据结构及其应用1概念和线性结构（70页珍藏版）》请在文档大全上搜索。

1、普通高等教育“十一五”国家级规划教材“十二五”普通高等教育本科国家级规划教材赵英良等.软件开发技术基础(第2版). 机械工业出版社西安交通大学计算机教学实验中心http:/西安交通大学计算机教学实验中心本章内容2.1 数据集结构基本概念数据集结构基本概念2.2 线性数据结构线性数据结构2.3 非线性数据结构非线性数据结构2.4 查找和排序查找和排序2/27西安交通大学计算机教学实验中心2.1 2.1 数据结构基本概念数据结构基本概念1数据（数据（data） 数据是指能够输入到计算机中，并被计算机识别和数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。处理的符号的集合。 2数据元素（

2、数据元素（data element）数据元素是一个数据整体中相对独立的单位。数据元素是一个数据整体中相对独立的单位。 数据元素是组成数据的基本单位。数据元素是组成数据的基本单位。 它还可以分割成若干个具有不同属性的项（字段），它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。故不是组成数据的最小单位。3/27西安交通大学计算机教学实验中心数据与数据元素1罗振波罗振波135187528212刘刘 耘耘135141303303唐唐 颖颖135181307244刘玮琳刘玮琳135137722225蔡蔡 创创13519071909 4/27西安交通大学计算机教学实验中心3 数据结

3、构（数据结构（data structure）数据的逻辑结构数据的逻辑结构存贮结构存贮结构运算运算5/27西安交通大学计算机教学实验中心数据的逻辑结构基本类型数据的逻辑结构基本类型 集合集合线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路、通信网络交通线路、通信网络6/27西安交通大学计算机教学实验中心数据结构的形式定义数据结构的形式定义举例举例：复数：复数Complex=(C,R)Complex=(C,R)，其中：，其中：C C是两是两个实数的集合，个实数的集合，R R是是C C中两个实数的偶对。

4、中两个实数的偶对。西安交通大学计算机教学实验中心数据结构中数据结构中常用的存贮结构常用的存贮结构(1) 顺序存贮顺序存贮所有元素存放在一片连续的存贮单元中，逻所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。辑上相邻的元素存放到计算机内存仍然相邻。8/27西安交通大学计算机教学实验中心链式存贮链式存贮(2) 链式存贮链式存贮所有元素存放在可以不连续的存贮单元中，所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的元素存放到计算机内存后不一定是相邻的。邻的。9/27西安交

5、通大学计算机教学实验中心(3) 索引存贮索引存贮索引存贮索引存贮 索引表索引表10/27a1442b1005c12010d16o8存储单元的地址存储单元及内容100b120c144a160D西安交通大学计算机教学实验中心(4) 散列存贮散列存贮数据元素的关键字数据元素的关键字x地址地址=f(x)例如：数据元素的关键字是电话号码例如：数据元素的关键字是电话号码 f: 取电话号码的后四位取电话号码的后四位例如：数据元素的关键字是学号例如：数据元素的关键字是学号 f:班代号班代号+学号的后三位学号的后三位f为哈希函数，为哈希函数，建立的表为哈希表（又称为杂凑法或散列表）建立的表为哈希表（又称为杂凑法

6、或散列表）11/27西安交通大学计算机教学实验中心4 算法（算法（algorithm）（1）输入：）输入：具有具有0个或多个输入的外界量（算法开始前的初始个或多个输入的外界量（算法开始前的初始量）量）（2）输出：）输出：至少产生一个输出，它们是算法执行完后的结果。至少产生一个输出，它们是算法执行完后的结果。（3）有穷性：）有穷性：每条指令的每条指令的执行次数执行次数必须是有限的。必须是有限的。（4）确定性：）确定性：每条指令的含义都必须明确，无二义性。相同每条指令的含义都必须明确，无二义性。相同的输入，有相同的输出。的输入，有相同的输出。（5）可行性：）可行性：每条指令可以在每条指令可以在有限

7、时间有限时间内实现。内实现。12/27西安交通大学计算机教学实验中心算法分析算法分析（1） 时间复杂度时间复杂度算法编制的程序在计算机上执行所消耗的时间。算法编制的程序在计算机上执行所消耗的时间。与语句的执行次数有关。与语句的执行次数有关。与问题规模有关。与问题规模有关。（2） 空间复杂度空间复杂度指算法编制的程序在计算机内执行时所占用的内存单指算法编制的程序在计算机内执行时所占用的内存单元的多少。元的多少。存储数据必须的单元存储数据必须的单元辅助存储单元辅助存储单元与问题规模有关与问题规模有关13/27西安交通大学计算机教学实验中心2.22.2 线性数据结构线性数据结构线性数据结构也叫线性表

8、线性数据结构也叫线性表线性表是同类数据元素的有序（次序）集合线性表是同类数据元素的有序（次序）集合记作（记作（a1,a2,an）。）。线性结构的四个基本特征线性结构的四个基本特征存在唯一的一个被称作存在唯一的一个被称作“第一个第一个”的数据元素；的数据元素； 存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据元素；的数据元素； 除第一个之外，集合中的每个元素均只有一个前驱；除第一个之外，集合中的每个元素均只有一个前驱； 除最后一个之外，集合中的每个元素均只有一个后继除最后一个之外，集合中的每个元素均只有一个后继14/27西安交通大学计算机教学实验中心2.2.1顺序表顺序表 采用

9、顺序存储结构的线性表称为顺序表，采用顺序存储结构的线性表称为顺序表，数据元素按照逻辑顺序依次存放在一组连续的存储单数据元素按照逻辑顺序依次存放在一组连续的存储单元中。元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素假定元素a1的物理地址是的物理地址是Loc(aLoc(a1 1) )，每个元素占，每个元素占d个存储单元，则第个存储单元，则第i个元素的存储位置为：个元素的存储位置为：Loc(ai) = Loc(a1) + (i-1) * d 15/27 length=n maxsize0 1 i-2 i-1 i n-1 a2ai-1aiai+1

10、a1an西安交通大学计算机教学实验中心顺序表类描述顺序表类描述const int MAXSIZE=100; /顺序表最大允许长度顺序表最大允许长度class SeqListpublic: ElemType dataMAXSIZE; / 存储数据的数组存储数据的数组 int length; / 顺序表当前长度顺序表当前长度 SeqList() length=0; /构造函数构造函数 void ClearList() length=0; /将顺序表置为空表将顺序表置为空表 /判断顺序表是否为空表判断顺序表是否为空表 bool IsListEmpty() return length=0;( 下页下页

11、continue . )16/27西安交通大学计算机教学实验中心( 接上页接上页 ) /判断顺序表是否为满判断顺序表是否为满 bool IsListFull() return length=MAXSIZE; /在表中删除第在表中删除第i个元素个元素 void ListDelete( int i ); /在表中第在表中第 i 个位置插入新元素个位置插入新元素x void ListInsert( int i, ElemType x ); int Find( ElemType x ); /在表中查找元素在表中查找元素;（1）ElemType代表数组的代表数组的某种某种类型。类型。（2）length表