《数据结构》 (java版) 课件 3数据结构

主要内容数据结构数据结构的描述抽象数据类型及实现计算机的用途数值计算数据处理实时控制辅助设计人工智能......数值计算的特点早期的计算机多用于数值计算，例如：弹道计算数据比较少计算复杂应用需求催生了数据结构这门课数据处理的特点计算机用于数据处理，例如：银行业务、人口普查数据量很大计算比较简单数据种类丰富：数值、字符、音频、视频...数据之间的关系复杂：时间序列、社交网络...数据结构房屋结构钢结构分子结构……牛津字典nounthearrangementofandrelationsbetweenthepartsorelementsofsomethingcomplextheorganizationofasocietyorothergroupandtherelationsbetweenitsmembers,determineitsworkingabuildingorotherobjectconstructedfromseveralpartsverbstructureddatastructuringofdatastructure线性结构：层次结构：线性表、栈、队列二叉树、树经典的数据结构数据结构的描述在计算机的存储器中如何存储数据和数据之间的关系存储器计算机使用存储器存储数据内存储器外存储器内存储器外存储器内存储器模型0123n……存储单元地址：0、1、2、......指令：read、write、move数据占用若干个相邻的存储单元内存分配方式存储大量的数据，如何为它们分配存储单元连续分配链式分配连续分配方式连续分配方式将数据分配(存储)于连续的存储单元。已知第一个数据的地址a，按照以下的公式得到各数据的地址。location(i)=a+(i-1)×s链式分配方式链式分配方式将数据分配于离散的存储单元，通过附加的地址信息将数据连接(Link)在一起。存取任何数据，必须依次存取第1个、第2个、。。。高级程序设计语言(C、JAVA)提供了：变量：用于存储数据数组：用于存储大量的数据高级语言管理内存储器数据类型：数据占用的存储单元的数量和编码方式int:4个字节，二进制补码float:4个字节，IEEE754编码double：8个字节，IEEE754编码int[]a=new

int[3];length3componentTypeint高级语言管理内存储器变量、数组就是存储单元地址的助记符通过符号表完成转换变量名

地址a100b108c116......0123n……高级语言管理内存储器高级语言管理内存储器已使用的存储单元未使用的存储单元分配存储单元回存储单元外存储器模型0123n……文件：由字节(存储单元)组成；字节有地址(偏移位置)；可以在任何地址读写若干字节。操作系统的文件操作函数：open、closeread、writeseek通过文件使用外存储器原子数据：基本数据类型、引用数据类型复合数据数据classAddress{

String

road;

String

city;}复合数据地址：街道、城市学生的基本信息：姓名、年龄、身高和家庭住址复合数据public

classStudent{

char

name[];

int

age;

float

height; Addressaddress;}public

classStudent{

char

name[];

int

age;

float

height;}云飞扬17181Id:23浪淘沙18170Id:18万山红17165Id:25数据:对象学生的基本信息：姓名、年龄、身高和家庭住址nameageheight云飞扬17181浪淘沙18170万山红17165数据处理经常遇到表处理，数据一行一行的出现，即行与行之间有先后关系例如，有3位学生关系s2s3s1public

classStudent{

char

name[];

int

age;

float

height;

Student

next;}关系:增加变量云飞扬17181Id:18Id:23浪淘沙18170Id:25Id:18万山红17165nullId:25关系:增加变量云飞扬17181Id:18Id:23浪淘沙18170Id:25Id:18万山红17165nullId:25关系:增加变量箭头：表示引用关系:增加变量缺点：需要修改类的定义(修改数据)一个数据同时参与多个关系？动态的关系(随时间变化)？classNode<E>{ Edata; Node<E>next;}Node类的对象之间有先后关系Node类？Id:30？Id:40?Id:45云飞扬17181浪淘沙18170万山红17165借助Node类对象之间的引用关系，间接的表达学生对象之间的先后关系链式结构：通过引用关系表示数据之间的先后关系关系：借助Node类head云飞扬17181浪淘沙18170万山红17165如何找到万山红？顺序存取(sequentialaccess)链式结构的特点[0][1][2]elem数组元素的位置天然的表达了先后关系关系:数组云飞扬17181[0][1][2]浪淘沙18170万山红17165elem关系：数组数组元素的位置天然的表达了先后关系顺序结构：通数组的位置表示数据之间的先后关系云飞扬17181[0][1][2]浪淘沙18170万山红17165elem如何找到万山红？elem[2]随机存取(randomaccess)顺序结构的特点抽象数据类型抽象数据类型(AbstractDataType)是定义了若干运算(操作)的数学模型

例如，集合以及集合的并、交、差；图以及入度、出度等操作数据结构描述数学模型，因此，也可以说抽象数据类型由数据结构以及创建、维护、销毁等操作组成

算法使用抽象数据类型的各种操作描述求解问题的处理流程高级程序设计语言提供的数据类型叫做基本数据类型抽象数据类型public

interfaceIlist<T>{intsize();//返回数据个数voidclear();//清楚线性表中的所有数据booleanisEmpty();//是不是为空表intindexOf(Tx);//找到x的索引号Tget(int

index);//返回索引号为index的数据的值voidadd(int

index,Tx);//加入数据x,索引号为indexTremove(int

index);//删除索引号为index的的数据Iterator<T>iterator();//迭代器，枚举线性表中的数据}使用接口定义抽象数据类型抽象数据类型的实现就是综合运用数组描述和链式描述表示数据结构，在此基础上高效地实现数据结构的各种操作实现算法时，必须首先实现算法使用的抽象数据类型

抽象数据类型的实现public

classCLinkedList<T>implementsIlist<T>,Iterable<T>,Cloneable{private

static

classNode<T>{//嵌套类T