数据结构基本概念

数据结构基本概念第1页，课件共50页，创作于2023年2月主要内容概念和术语数据、数据元素、数据项、数据对象、关键码数据结构及其描述方式抽象数据类型算法与算法分析泛型第2页，课件共50页，创作于2023年2月1、概念和术语

数据（Data）：是计算机加工处理的对象和信息的载体。可以是数值数据，如整数、实数或复数；也可以是非数值数据，如字符、文字、图形、图像、语音等。数据元素（DataElement）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，如元素、结点、顶点、记录等。数据项（DataItem）：数据元素的某一属性，数据项又称域、字段。数据元素可以由若干数据项组成，数据项可以分为两种:原子项（不能再分割的最小单位）和组合项。数据对象（DataObject）或数据元素类（DataElementClass）：是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。关键字（KeyCode）：能起唯一标识（数据元素）作用的数据项3第3页，课件共50页，创作于2023年2月数据对象：

Digit={0,1,2,3,4,5,6,7,8,9}

Letter={A,B,C,.,Z,a,b,.,z}

NaturalNumber={0,1,2,.}

String={a,b,.,aa,ab,ac,.}数据对象与数据元素数据对象数据元素数据项关键码4第4页，课件共50页，创作于2023年2月数据元素之间的关系数据对象的元素通常都有某种相关性；

如：NaturalNumber元素之间存在大小关系；在String

中构成字符串的字符有排列顺序。除了相关性之外，对于任一个数据对象通常都有一组相关的函数（操作），这些函数可以把对象的某个元素（或称实例）转换成该对象的另外一个元素、创建一个新的元素，或转换成另一个数据对象的元素。

如：对自然数进行相加操作将创建一个新的自然数。5第5页，课件共50页，创作于2023年2月数据结构（DataStructure）数据结构是指互相之间存在着一种或多种关系的数据元素的集合。一个数据结构有两个要素：一个是数据元素的集合，另一个是关系的集合。数据结构的形式定义为： 数据结构是一个二元组

Data_Structure＝（D，R） 其中：D是数据元素的有限集，R是D上关系的有限集。当我们研究数据结构时，关心的是数据对象（实际上是数据元素）的描述以及数据对象关系函数（操作）的具体实现。数据对象的良好描述可以有效地促进函数的高效实现。6第6页，课件共50页，创作于2023年2月数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，可以看作是从具体问题抽象出来的数学模型，可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系：数据的物理结构：是指数据结构在计算机中的具体表示和实现，又称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。2、数据结构的描述方式EiEj数据元素数据元素关系7第7页，课件共50页，创作于2023年2月具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）。这三个方面的关系为：（1）数据的逻辑结构独立于计算机，是数据本身所固有的。与数据元素本身的形式、内容和存储方式无关。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。8第8页，课件共50页，创作于2023年2月数据结构的分类－逻辑结构分类根据数据元素间逻辑关系的不同特性，通常有下列四类基本的结构：集合结构：数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。线性结构：数据元素之间存在着一对一的关系。树型结构：数据元素之间存在着一对多的关系。图形结构：数据元素之间存在着多对多的关系， 也称作网状结构。前驱和后继9第9页，课件共50页，创作于2023年2月E1E2E3E4E5E1E2E3E4E5E1E2E3E4E5集合结构：D={E1,E2,E3,E4,E5}R={}E1E2E3E4E5线性结构：D={E1,E2,E3,E4,E5}R={<E1,E2>,<E2,E3>,<E3,E4>,<E4,E5>}树型结构：D={E1,E2,E3,E4,E5}R={<E1,E2>,<E1,E3>,<E2,E4>,<E2,E5>}图形结构：D={E1,E2,E3,E4,E5}R={<E1,E2>,<E1,E4>,<E2,E3>,<E2,E4><E3,E4>,<E3,E5>,<E4,E5>}数据结构的表示10第10页，课件共50页，创作于2023年2月练习

（1）（2）给出该数据结构的二元组表示给出该数据结构的图形表示E1E2E3E4E5D={E1,E2,E3,E4,E5}R={<E1,E2>,<E1,E4>,<E2,E3>,<E3,E5>}11第11页，课件共50页，创作于2023年2月数据的存储结构

根据存储结构分类：顺序存储:把逻辑上相邻的元素存储在物理位 置相邻的存储单元中，是一种最基本 的存储表示方法，通常用数组来实现。链式存储:对逻辑上相邻的元素不要求其物理 位置相邻，元素间的逻辑关系通过附 加的指针字段（域）来表示，通常用

引用（或指针）来实现。索引存储:为数据元素的存储建立附加的索引表散列存储:通过构造散列函数，用函数的值来确 定元素存放的地址。主要用于内存存储表示主要用于外存(文件)的存储表示是逻辑结构用计算机语言的实现，依赖于计算机语言。方便查找12第12页，课件共50页，创作于2023年2月（a）顺序存储结构（b）链式存储结构13第13页，课件共50页，创作于2023年2月课堂练习设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a1,a2,…,an}，R={<ai,ai+1>|i=1,2,…，n-1}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。14第14页，课件共50页，创作于2023年2月常见的操作（运算、函数）创建、初始化；判断是否为空；求长度：统计元素个数；包含（查找、搜索）：判断是否包含指定元素；遍历：按某种次序访问所有元素，每个元素只被访问一次；访问取值：获取指定元素值；修改置值：设置和修改指定元素值；插入：增加指定元素；删除：移去指定元素。15第15页，课件共50页，创作于2023年2月抽象数据类型(ADT:AbstractDataType)数据类型：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。抽象数据类型：一个数据模型以及定义在该模型上的一组操作。由用户定义，用以表示应用问题的数据模型。包括一组相关的操作(抽象操作，不涉及具体实现细节)。封装和隐藏了数据的存储结构，使得数据类型的使用与实现相分离。16第16页，课件共50页，创作于2023年2月抽象数据类型通过操作的性质刻画所定义的数据对象的性质，与对象在计算机里的表示方法无关。这样就隐藏了运算实现的细节和内部数据结构。需要为用户提供使用该数据类型所需的完整信息，通常包括创建对象的手段和各种操作使用形式的说明（函数原型）——数据类型的使用界面抽象数据类型实现1（如修改）实现2（如查询）实现3（如添加）实现4（如删除）17第17页，课件共50页，创作于2023年2月抽象数据类型的表示

ADT抽象数据类型名{ Data（或Object）:<数据描述> Operation（或Function）:<操作声明> }抽象数据类型名

如：ADTLinearList{ Data: L=(a1,a2,...,an); //线性表L的数据成员

Operation:voidInitList(L); //初始化线性表L intListSize(L); //返回线性表L的长度（元素个数）

intInsertItem(L,item); //向线性表L中插入元素

intDeleteItem(L,item); //删除线性表L中某个元素

...... }LinearList18第18页，课件共50页，创作于2023年2月例：一个简单的圆柱体抽象数据类型：ADTCYLinder{ Data：

floatr,h; //底面半径r和圆柱高h Operation：

Initcyld(r,h); //初始化圆柱 Basearea(r); //计算底面积

Sidearea(r,h);//计算侧面积 Volume(r,h); //计算体积}CYLinder19第19页，课件共50页，创作于2023年2月用Java语言描述数据结构可以采用Java接口表示抽象数据类型接口是一种与类相似的结构，只包含常量和抽象方法。接口在许多方面与抽象类很相似，但它的目的是指明多个对象的共同行为。publicinterfaceSset//集合接口{booleanisEmpty();//判断集合是否为空

intsize();//返回集合的元素个数

StringtoString();//返回集合元素的描述字符串

Objectsearch(Objectkey);//查找，返回关键字为key元素

booleancontain(Objectx);//判断集合是否包含元素x

voidadd(Objectx);//增加元素xvoidremove(Objectx);//删除首次出现的元素xvoidremoveAll();//删除集合所有元素}20第20页，课件共50页，创作于2023年2月3、算法（algorithm）

算法是为了解决给定的问题而规定的一个有限长的操作步 骤（指令）序列，着重于解决问题的方法和步骤。当算 法由计算机语言表示时称为程序（代码）算法是由若干条指令组成的有穷序列，是一种解题的方法。算法的五大特性（必须满足的条件）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3）有穷性：每条指令的执行次数必须是有限的。 （4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条指令的执行时间都是有限的。21第21页，课件共50页，创作于2023年2月算法描述元素search(关键字key){e=数据序列的第一个元素;while(数据序列未结束&&e的关键字不是key)e=数据序列的下一个元素;

返回查找到的元素或查找不成功标记;}22第22页，课件共50页，创作于2023年2月算法与数据结构23第23页，课件共50页，创作于2023年2月算法性能分析与度量

算法的性能标准（设计目标）：

正确性： 可使用性： 可读性： 效率：执行时间、占用内存空间 健壮性：稳定可靠算法分析：可以用一个算法的时间复杂度与空间复杂 度来分析和评价算法的优劣

事后统计法和事前分析估算法24第24页，课件共50页，创作于2023年2月空间复杂度的度量一个程序的空间复杂度（Spacecomplexity）是指程序运行从开始到结束所需的存储量。存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间。存储空间的可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间等。25第25页，课件共50页，创作于2023年2月时间复杂度一个程序的时间复杂度（Timecomplexity）是指程序运行从开始到结束所需要的时间。

T＝执行步数x单步执行时间对于大规模计算，算法的执行时间绝大部分是花在循环和递归上的。要估算程序的运行时间（即时间复杂性），可以把执行步数仅看成是要处理的数据个数n（问题规模）的函数。

即：T＝ƒ(执行步数)=T(n)26第26页，课件共50页，创作于2023年2月程序步（programstep）程序步（programstep）：定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。语法上或语义上有意义的一段指令序列。执行时间与实例特性（问题规模）无关。由一个程序步所表示的计算量可能与其他形式表示的计算量不同。通常：声明语句的程序步数为0;表达式为1个程序步。例如：语句：x=y; 可以视为一个程序步；语句：returna+b+b*c+(a+b-c)/(a+b)+4;

也可以被视为一个程序步，只要它的执行时间独立于所选用的 实例特征；27第27页，课件共50页，创作于2023年2月课堂练习一个循环的程序步=循环次数x每次执行的程序步数；多个并列循环的程序步=每个循环的程序步之和；多层嵌套循环的程序步=每层循环的程序步之积；i=1;k=0;while(i<=n-1){

k+=10*i;

i++;

}

（1）k=0;for(i=1;i<=n;i++){

for(j=1;j<=i;j++)

k++;}

（2）intn=8,count=0;for(inti=1;i<=n;i*=2)

count++;

（3）intn=8,count=0;for(inti=1;i<=n;i*=2)for(intj=1;j<=i;j++)

count++;

（4）28第28页，课件共50页，创作于2023年2月程序语句（计算数组a的前n个元素的和）一次执行所需程序步数(s/e)执行频度程序步数floatSum(floata[])000{010floats=0.0;

111for(inti=0;i<n;i++)1n+1n+1s+=a[i];1nnreturns;111}010总程序步数2n+3计算程序步的意义： 可以比较两个完成同一功能的程序的时间复杂性；

可以预测随着实例特征的变化，程序运行时间的变化量。29第29页，课件共50页，创作于2023年2月程序步数程序语句(求两个n阶方阵的乘积C=A×B)程序步数程序步数voidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n])00{00for(inti=0;i<n;i++)n+1n+1for(intj=0;j<n;j++){n(n+1)n(n+1)C[i][j]=0;n2n2for(intk=0;k<n;k++)n2(n+1)n2(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];n3n3}00}00程序步数总计2n3+3n2+2n+130第30页，课件共50页，创作于2023年2月StaticfloatRsum(floata[],intn)//计算a[]中前n个元素之和{ if(n>0) //count++; returnRsum(a,n-1)+a[n-1]; //count++; return0; //count++;}程序步：TRsum(n)=2+TRsum(n-1)=2+2+TRsum(n-2) =4+TRsum(n-2)...=2n+TRsum(0) =2(n+1)递归函数的程序步31第31页，课件共50页，创作于2023年2月程序语句最好情况(最大)最坏情况（最小）s/e执行频率程序步数s/e执行频率程序步数voidinsert(floata[],floatx)000000{000000inti=0；111111for(i=a.length-1;i>=0&&x<a[i];i--)1111n+1n+1a[i+1]=a[i];0001nna[i+1]=x;111111}000000程序步数总计32n+3例：将元素x插入递增数组a的程序步数最佳、最差和平均执行步数32第32页，课件共50页，创作于2023年2月平均执行步数为了计算平均执行步数，假定x被插入到任何位置上的概率是一样的（共有n+1个可能的位置）。如果x最终被插入到位置j处，j≥0，则执行步数为(n+1-j)+(n-j)+1+1=2n-2j+3。 所以平均执行步数为：33第33页，课件共50页，创作于2023年2月时间复杂度的渐进表示法在前面的例子中，算法中所有语句的频度之和是数组元素个数n或矩阵阶数n的函数称n为问题的规模，则时间复杂度T(n)是问题规模n的函数。

如：T（n）＝2n3+3n2+2n+1；程序步数不能够非常精确地描述时间复杂性（因为“程序步”的概念本身就不精确，指令x=y和x=y+z+(x/y)都可以被称为一步）。34第34页，课件共50页，创作于2023年2月时间复杂度的渐进表示法设T(n)的一个辅助函数为g(n)，定义为当n大于等于某一足够大的正整数n0时，存在两个正的常数A和B（其中A≤B），使得A≤T(n)/g(n)≤B成立，则称g(n)是T(n)的同数量级函数。把T(n)表示成数量级(Order)的形式为：T(n)=O(g(n))；称为算法的渐进时间复杂度（大O表示法） 如：T(n)＝2n3+3n2+2n+1＝O(n3)

许多时候要精确地计算T(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间，同样能够达到分析算法的目的。渐进时间复杂度可以很好地反映时间复杂性的变化规律。35第35页，课件共50页，创作于2023年2月【例1.1】算法时间复杂度分析一个简单语句的时间复杂度为O(1)。

intcount=0;一个循环的时间复杂度为O(n)。

intn=8,count=0; for(inti=1;i<=n;i++) count++;时间复杂度为O(log2n)的循环语句。

intn=8,count=0; for(inti=1;i<=n;i*=2) count++;时间复杂度为O(n2)的二重循环。 intn=8,count=0; for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) count++;36第36页，课件共50页，创作于2023年2月时间复杂度为O(nlog2n)的二重循环。 intn=8,count=0; for(inti=1;i<=n;i*=2) for(intj=1;j<=n;j++) count++;循环次数为。时间复杂度为O(nlog2n)。时间复杂度为O(n)的二重循环。

intn=8,count=0; for(inti=1;i<=n;i*=2) for(intj=1;j<=i;j++) count++;总的循环次数为。时间复杂度为O(n)。37第37页，课件共50页，创作于2023年2月常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)k次方阶O(nk)指数阶O(2n)阶乘阶(n!)常见的时间复杂度按数量级递增38第38页，课件共50页，创作于2023年2月时间复杂度的运算规则O(c)=O(1)；c为常数O(f(n))+O(g(n))=O(max(f(n),g(n)))；O(f(n))+O(g(n))=O(f(n)+g(n))；(加法规则)O(f(n))*O(g(n))=O(f(n)*g(n))；(乘法规则)O(c*f(n))=O(f(n))；c为常数如：

O(2n3+3n2+2n+1) =O(2n3)+O(3n2)+O(2n)+O(1) =O(n3)+O(n2)+O(n)+O(1) =O(n3)39第39页，课件共50页，创作于2023年2月若除去数据对象的基本类型外，实现方法相同的，则可用泛型方法来描述这种基本功能。1、使用Object表示泛型2、使用Comparable接口类型表示泛型3、Java5.0提供泛型支持4、关于泛型第40页，课件共50页，创作于2023年2月使用Object表示泛型【例1】

两个数的置换算法（要求方法与与被置换的数据对象的类型无关）publicstaticvoidswap(Objecta,Objectb){Objecttemp=a;a=b;b=tmep;}第41页，课件共50页，创作于2023年2月使用Object表示泛型【注意】1.为了访问这种对象的一个特定方法，必须首先要强制转换成正确的类型。2.基本类型不能作为Object类进行传递。因为只有引用类型能够与Object类相容，而Java中的8种基本类型都不能。

解决方法：利用Java为这8种基本类型的所提供的包装类。3.只有当使用Object类中已有的方法能够表示所执行的操作时，才能使用Object类作为泛型类来工作。第42页，课件共50页，创作于2023年2月使用Comparable接口类型表示泛型//Thisinterfaceisdefinedinjava.langpackagepackagejava.lang;publicinterfaceComparable{publicintcompareTo(Objecto);}许多类(e.g.,String、Date、包装类)实现Comparable接口，定义了对象的自然顺序。如果查看这些类的源代码，会发现这些类中使用了关键字implements：第43页，课件共50页，创作于2023年2月使用Comparable接口类型表示泛型【例2】

找出数组a中的最大数publiccalssFindMaxExamp{publicstaticComparable

findMax(Comparable[]a){intk=0;for(inti=1;i<a.length;i++)if(a[i].compareTo(a[k])>0)k=i;returna[k];}publicstaticvoidmain(String[]args){Integer[]sh1={2,3,4};String[]st1={"Joe","Bob","Bill","Zeke"};System.out.println(findMax(sh1));System.out.println(findMax(st1));}}第44页，课件共50页，创作于2023年2月Java5.0提供泛型支持泛型是JavaSE1.5的新特性，其本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。在之前没有泛型的情况的下，通过对类型Object的引用来实现参数的“任意化”，缺点是要做显式的强制类型转换，而这种转换是要求开发者对实际参数类型可以预知的情况下进行的。对于强制类型转换错误的情况，编译器可能不提示错误，在运行的时候才出现异常，这是一个安全隐患。泛型的好处是在编译的时候检查类型安全，并且所有的强制转换都是自动和隐式的，提高代码的重用率。第45页，课件共50页，创作于2023年2月泛型的使用规则和限制

1、泛型的类型参数只能是类类型（包括自定义类），不能是简单类型。

2、泛型的类型参数可以有多个。3、同一种泛型可以对应多个版本（因为参数类型是不确定的），不同版本的泛型类实例是不兼容的。

4、泛型的参数类型可以使用extends语句，例如<Textendssuperclass>。习惯上称为“有界类型”。

5、泛型的参数类型还可以是通配符类型。例如Class<?>classType=Class.forName(java.lang.String);第46页，课件共50页，创作于2023年2月publicclassGen<T>{

privateTob;//定义泛型成员变量

publicGen(Tob){

this.ob=ob;

}

publicTgetOb(){

returnob;

}

publicvoidsetOb(Tob){

this.ob=ob;

}

publicvoidshow