《数据结构JAVA语言版》课件 第1章绪论

数据结构DATASTRUCTURE——Java描述1.1数据结构的地位1.2基本概念和术语

1.2.1基本概念1.数据（data）：是对客观事物的符号表示，所有能输入到计算机中，被计算机程序识别和处理的符号的总称。2.数据元素（dataelement）：数据元素是表示现实世界中一个实体的一组数据，是数据结构的基本组成单位。一个数据元素可由一个或若干个数据项（dataItem）组成。3.数据对象(DataObject)：是性质相同的数据元素的集合。4.数据结构（Data_Structure）相互之间存在一种或多种特定关系的数据元素的集合。1.2.2数据结构的种类1、集合结构。在集合结构中，数据元素间的关系除了“属于同一个集合”外，别无任何关系。

1.2.2数据结构的种类2、线性结构。该结构的数据元素之间存在着一对一的关系。

1.2.2数据结构的种类3、树型结构。该结构的数据元素之间存在着一对多的关系。1.2.2数据结构的种类4、图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。1.2.3数据结构的数学定义数据结构的数学定义为：数据结构是一个二元组：

Data-Structure=(D，S)其中：D是数据元素的集合，S是数据元素之间关系的集合。例:复数a+bi的数据结构定义如下：

Complex=(C，R)其中，D部分用C表示，C是含两个实数的集合﹛a，b﹜；S部分用R表示，R={〈a，b〉}，〈a，b〉表示a和b存在一种有序关系，a表示复数的实部，b表示复数的虚部，二者不能互换。1.2.4数据的存储结构

本课程是在高级语言Java的层次上讨论数据结构在计算机中内存中的存储，主要研究的是数据元素以及它们之间的关系在Java虚拟处理器中的表示，可以称为虚拟存储结构。1、数据元素的表示单个数据项组成的数据元素可以利用java语言固有的基本数据类型（8种）来表示。

例如：复数数据结构Complex=(C，R)中的C=﹛a，b﹜，数据元素a和b是实数，可用Java语言中的固有的双精度浮点型double表示。多个数据项组成的数据元素可以利用Java语言中的自己定义的类表示。例如：学生实体的数据元素可由学号、姓名、所在系、性别、出生日期、入学成绩等数据项组成，在Java语言中用自己定义的类表示如下：classStudent{

StringNO;//String位于java.lang子类库中

StringName;

StringDepartment;

charSex;

DateBirthDate;//Date位于java.util子类库中

doubleScore;}1.2.4数据的存储结构2数据元素之间关系的表示数据元素之间的关系在计算机内存中有两种不同的表示方法：顺序存储和链式存储。顺序存储是把数据元素按一定的规则存放在一组编号连续的存储单元中，通过元素在内存中的存储位置来体现数据元素之间的逻辑关系，逻辑上相邻的数据元素在内存中的存储位置也相邻。abcd

例如：线性数据结构（‘a’，‘b’，‘c’，‘d’）的顺序存储就是把数据元素‘a’、‘b’、‘c’、‘d’放在一组编号连续的存储单元（1个存储单元即1个字节）中，通过元素的存储地址是否相邻来表示数据元素在逻辑上是否相邻。存储单元编号存储内容

…0030a0032b0034c0036d

…在高级语言Java的层次上讨论时，线性数据结构（‘a’，‘b’，‘c’，‘d’）的数据元素是char型，每个数据元素在占用2个字节的内存空间。。在Java语言中，存储单元的编号对用户透明，在Java虚拟处理器中线性数据结构的顺序存储就是线性数据结构中的数据元素依次存放到一维数组中，因为Java语言中一维数组占用的就是一组编号连续的内存单元。1.2.4数据的存储结构2数据元素之间关系的表示链式存储：链式存储时数据元素不必存放在一组编号连续的存储单元中，把数据元素后附加一个地址域，通过指示相邻元素的存储地址来体现数据元素的逻辑关系，逻辑上相邻的数据元素物理存储位置不一定相邻。线性数据结构（‘a’，‘b’，‘c’，‘d’）的链式存储是在把数据元素后面加一个地址域，通过指示相邻元素的存储地址来体现数据元素的逻辑关系，逻辑上相邻的数据元素物理存储位置上不一定相邻。abcd

存储单元编号存储内容

…0100b01020120……0120c01220160……0144a01460100……0160d0162NULL

…headd^cba前面已经提及，在Java语言中，存储单元的编号对用户透明，在Java虚拟处理器中，把相邻元素的存储地址抽象为引用，在存储结构图中用箭头表示，整个存储结构像一条链条，链式存储结构也是由此命名。1.2.5抽象数据类型抽象数据类型：数据的逻辑结构及定义在该逻辑结构上的一组操作。

ADT={D,S,P}为什麽还要研究操作呢？因为针对不同的数据元素集合，定义于其上的操作也不一样。以Java语言中的int,boolean数据类型为例：int数据类型，其数据元素集是-231～231-1区间的整数，定义在其上的操作是为加、减、乘、除和取模等算术运算和大于、不等于、等于、小于等关系运算。boolean数据类型，其数据元素集是{true，false}，定义在其上的操作是与、或、非等逻辑运算。在后面的章节中，每研究一种数据结构，都是从抽象数据类型开始，即先研究逻辑结构及定义于其上的操作，逻辑结构严格来说属于离散数学课程的学习内容。1.2.5抽象数据类型对于使用数据类型的用户而言，引入“数据类型”，实现了信息的隐蔽，即将一切用户不必了解的细节都封装在类型中。例如，Java编程用户使用int数据类型时，既不需要了解int型整数在计算机的内部是如何表示的，也不需要知道其操作是如何实现的，这些由Java语言的推出者关注实现。就int数据类型的“加”操作而言，Java编程用户只需关注“加”的功能及它的数学意义，不必去关注其硬件的“位”操作如何进行。

抽象数据类型和数据类型实质上是一个概念，抽象的意义在于数据类型的数学抽象特性。另外抽象数据类型的范畴更广，它不再局限于各高级语言处理器中已定义并实现的数据类型，还包括用户开发软件系统时自己定义的数据类型。

为了提高软件的复用率，在近代程序设计方法学中指出，一个软件系统的框架应建立在数据之上，而不是建立在操作之上。在构成软件系统的每个相对独立的模块上，定义一组数据和施于这组数据上的一组操作，并在模块内部给出这些数据的表示及操作的细节，而在模块外部使用的只是抽象的操作。显然，所定义的数据类型的抽象层次越高，含有该数据类型的软件模块的复用度也越高。1.3数学预备知识1.3.1集合1、集合的概念

集合是由一些确定的、彼此不同的成员或者元素构成的一个整体。成员的个数称为集合的基数。如果某集合的成员都属于该集合，那麽某集合叫做该集合的子集

没有元素的集合称为空集，记作Φ。3是R的成员，记为：3∈R，6不是R的成员，记为：6∉R。{3，4}是R的子集。2、集合的表示法

穷举法：S＝{2，4，6，8，10}；

描述法：S＝{x|x是偶数，且0≤x≤10}。3、集合的特性确定性：任何一个对象都能被确切地判断是集合中的元素或不是；互异性：集合中的元素不能重复；无序性：集合中元素与顺序无关。

1.3.2常用的数学术语计量单位(Unit)：字节缩写为“B”，位缩写为“b”，千字节缩写为“KB”，百万字节缩写为缩写为“MB”，十亿字节缩写为缩写为“GB”，万亿字节缩写为“TB”，。阶乘函数(FactorialFunction)：阶乘函数n!是指从1到n之间所有整数的连乘，其中n为大于0的整数。因此，5!=1∙2∙3∙4∙5=120。特别地，0!=1。取下整和取上整(FloorandCeiling)：实数x的取下整函数(Floor)，返回不超过x的最大整数，例如Floor（5.5)=5；实数x的取上整函数(Ceiling)，返回不小于x的最小整数，Ceiling（

5.5)=6

。取模操作符（Modulus）：取模函数返回整除后的余数,有时称为求余，记为%,例如:5%3=2。1.3.3对数一般地，如果a(a＞0，a≠1)的b次幂等于N，就是ab=N，那么数b叫做以a为底N的对数，记作logaN=b，其中a叫做对数的底数，N叫做真数。

负数和零没有对数。1.3.4递归如果一个算法直接调用自己或间接地调用自己，就称这个算法是递归的(Recursive)。根据调用方式的不同，它分为直接递归和间接递归。直接递归调用就是在函数a（或过程）中直接引用（调用）函数a本身。间接递归调用就是在函数a（或过程）中调用另外一个函数b，而该函数b又引用（调用）了函数a。

1.3.4递归一个递归算法必须有两个部分：初始部分(Basecase)和递归部分。初始情况只处理可以直接解决而不需要再次递归调用的简单输入。递归部分包含对算法的一次或多次递归调用，每一次的调用参数都在某种程度上比原始调用参数更接近初始情况。

函数的递归调用可以理解为：通过一系列的自身调用，达到某一终止条件后，在按照调用路线逐步返回。递归是程序设计中强有力的工具，有很多数学函数时递归定义的。阶乘函数，对n!作如下定义：

阶乘函数的java语言实现如下：

public

static

double

fun(intn){

if(n=0)

return1;

else

return

fun(n-1)*n;}1.4算法和算法分析1.4.1算法1、定义算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法的描述工具有自然语言、框图、PAD图、伪码、程序设计语言等等。在Java程序设计语言中，算法一般用类的一个方法进行描述，方法体内的一条条语句就是对问题求解步骤的一种描述。

1.4算法和算法分析1.4.1算法2、特性输入

有输入输出有输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算能有效的执行

（1）有输入。算法有一个或多个输入数据，输入数据是算法的加工对象，是数据原材料。

在Java程序设计语言中，算法表现为类的方法，算法的输入可以通过方法的形式参数接受，也可以在方法体内由变量赋值语句指定，还可以在方法体内通过输入语句从键盘、外存等外部设备接受，算法的输入数据亦可由方法所在类的成员变量的值提供。

例如求阶乘的算法有一个输入数据，通过方法的形式参数接受，如下所示：

staticdoublefact(intn){ doubles=1; for(inti=1;i<=n;i++){ s=s*i; } returns;

}算法也可以有两个或多个输入数据，例如求最大公约数的算法有两个输入数据，需要输入两个整数的值。

求两个非负整数数a和b（要求a>b）的最大公约数可以使用辗转相除法，算法用自然语言描述为：

①a除以b得到的余数为c（0<=c<b）；

②若c=0则算法结束，b为最大公约数。否则转③；

③a=b，b=c，转①；

static

int

gys1(int

a,int

b)//最大公约数

{

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

return

b;}

辗转相除法算法用Java语言描述如下，算法的两个输入数据均通过方法的形式参数接受：在Java语言中，辗转相除算法的两个输入数据也可以在方法体内通过输入语句从外设键盘接受，如下所示：static

int

gys2()//最大公约数

{Scannerreader=newScanner(System.in);System.out.print("请输入第一个数：");inta=reader.nextInt();System.out.print("请输入第二个数：");intb=reader.nextInt();

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

return

b;}

（2）有输出。

算法有一个或多个输出数据，输出数据是一组与输入有确定关系的值，是算法对输入数据进行加工后得到的结果数据，这种确定关系即为算法的功能。上面例子中，阶乘、最大公约数就是算法的输出。

在Java程序设计语言中，算法的输出一般通过方法体内的return语句返回，如上面两个例子；还可以把结果数据输出到屏幕、打印机、外存等外部设备，也可以传到网络，还可以表现为方法所在类中成员变量值的改变。例如辗转相除法求最大公约数可以把结果数据输出到屏幕，如下所示：staticvoidgys3()//最大公约数

{Scannerreader=newScanner(System.in);System.out.print("请输入第一个数：");inta=reader.nextInt();System.out.print("请输入第二个数：");intb=reader.nextInt();

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

System.out.print("最大公约数为："+b);}

（3）确定性。每步定义都是确切、无歧义的，而不是含糊的，模棱两可的。并且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得到相同的输出。

在Java程序设计语言中，算法的操作步骤通过语句描述，所写语句必须符合语法规定，不符合确定性要求的语句编译不会通过，算法的确定性检验主要由编译器协助完成。（4）有穷性。对于任意一组合法的输入值，算法在执行有穷步骤后一定能结束。即算法的操作步骤为有限个，且每步都能在有限时间内完成。

在Java程序设计语言中，死循环的算法是不符合设计要求的。事实上，“有穷性”是指合理的范围内，计算机执行100年才结束的算法，虽然是有穷的，但超过了合理的限度，也是不可行的。（5）有效性。算法每一步能有效的执行，并能得到确定的结果。例如，在除法中，除数不为0才能被有效执行，除数为0是不能被有效执行的。

在Java程序设计语言中，不能被有效执行的语句会中止执行，并产生异常对象。1.4.2算法设计的要求

对于一个特定的问题，采用的数据结构不同，其设计的算法一般也不同，即使在同一种数据结构下，也可以采用不同的算法。那么，解决实际问题时，选择哪一种算法比较合适，以及如何对现有的算法进行改进，从而设计出更优质的算法，这就是算法设计要求的问题。评价一个算法优劣的主要标准如下：

正确性可读性健壮性时间效率与空间效率

1、正确性（correctness）

算法的正确性指的是对合法正确的输入能够获取正确的输出。比如求阶乘的算法，对于合法正确的输入数据4，算法能够输出正确的结果24。

对于程序设计语言描述的算法，“正确”大体分为以下四个层次：

（1）不含语法错误，编译通过。

（2）几组输入数据能输出正确的结果数据。

（3）精心选择的几组典型、苛刻、刁难性数据能得出正确的结果数据。

（4）一切合法输入均能输出正确的结果数据。

显然，达到第四层次意义下的正确是极为困难的，一切合法输入数据量大得惊人，逐一测试的方法是不现实的。对大型软件需要进行专业测试，一般情况下，通常以第三层次意义的正确性作为软件验收标准1.4.2算法设计的要求

2、可读性（readbility）算法的可读性指的是算法的表达思路清晰，简洁明了，易于理解。对于程序设计语言描述的算法，为了提高可读性，通常做法加注释。1.4.2算法设计的要求3、健壮性（robustness）又称鲁棒性，是robust音译,也称容错性。当用户输入不合法时，例如用户输入错误时，能够反馈给用户相应的提示信息，而不是终止程序的执行，或显示调试时出现的一些错误信息。1.4.2算法设计的要求4、时间效率与空间效率要求算法执行时间越短，算法的时间效率越高，算法执行时占用的内存空间越少，算法的空间效率越高。下面两小节就要来讲述怎样度量算法的效率。1.4.2算法设计的要求1.4.3算法时间效率的度量1、算法的执行时间算法时间效率可以利用算法执行时间进行度量，算法执行时间就是依据该算法编制的程序在计算机上运行所消耗的时间。两个缺陷：

1）必须首先运行依据算法编制的程序

2）所得时间的统计量依赖于计算机硬件、软件的因素，容易掩盖算法本身的优劣。分析算法时间效率时，必须撇开这些与算法无关的软硬件因素。通常的做法是：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。称之为：2、渐进时间复杂度

被称作问题的基本操作的原操作多数情况下是最深层循环内语句的原操作，它的执行次数和包含它的语句频度相同，语句的频度指的是该语句重复执行的次数。

例题1求阶乘的算法把乘法操作看作基本操作，乘法操作包含在下面画横线的语句中，基本操作重复执行了多少次？staticdoublefact(intn){ doubles=1; for(inti=1;i<=n;i++){

s=s*i; } returns;}

乘法操作执行了n次。该算法的时间复杂度记为O(n)基本操作执行次数与n成正比的即an+b均记为O(n)基本操作执行次数与n2成正比的即cn2+an+b均记为O(n2)（重点关注增长最快的项）在一些常用的项中到底哪个项增长快呢？有下面的不等式成立：c<log2n<n<nlog2n<n2<n3<2n<3n<n!例题2：求n行n列矩阵所有元素之和的算法可以把加法操作看作基本操作，加法操作包含在下面划横线的语句中，请分析该算法的时间复杂度。

基本操作执行n2+n次，该算法的时间复杂度记为O(n2)

staticfloatexample(float[][]x,intn){ float[]sum=newfloat[n]; floattotalsum=0.0f; for(inti=0;i<n;i++){//x[][]中各行数据累加和

for(intj=0;j<n;j++)

sum[i]=sum[i]+x[i][j]; } for(inti=0;i<n;i++)//各行数据汇总相加

totalsum=totalsum+sum[i]; returntotalsum;

}有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。比如冒泡排序法，此算法的功能是对输入数据序列进行排序，算法执行完毕后，序列中数据元素依次递增。排序过程如下所示：冒泡排序的过程：假设输入数据序列中元素个数是n，首先比较第一个和第二个数据，将其中较小的数据放到第一个位置，较大的放到第二个位置；然后比较第二个和第三个数据，仍将较大的放到后一个位置。依此类推，直到比较第n-1和第n个数据。这样，就将待排序序列中的最大的一个放到了第n个位置（一趟排序冒出一个泡来），这个过程称为第一趟排序。对前n-1个数据重复这个过程（不用考虑第n个位置数据，因为它已经是最大的了），又将次大的数据放到了第n-1个位置。第三趟排序选出第三大的数据，放到倒数第三个位置。重复这个过程，直到数据依次递增为止（共n-1趟）。[初态]：4682405267312173对此输入数据序列进行冒泡排序：冒泡排序法示例：[初态]：4682405267312173第1趟：4640526731217382第2趟：4046523121677382第3趟：4046312152677382第4趟：4031214652677382第5趟：3121404652677382第6趟：2131404652677382第7趟：2131404652677382java语言源码

static

voidbubble_sort(int[]a,int

n) {

for(int

i=n-1;i>0;i--)

for(int

j=0;j<i;++j)

if(a[j]>a[j+1])

{int

temp=a[j];a[j]=a[j+1];a[j+1]=temp;} }冒泡排序法中把数据交换操作看作基本操作，数据交换操作包含在上面画横线的语句中，设输入数据序列中数据元素个数是n，则冒泡排序法中基本操作重复执行的次数随输入数据状态的不同而不同。最坏的情况：当初始状态完全逆序，即数据元素递减有序，需要进行多少次数据交换？（此例中数据元素个数n=8）

[初态]：82736752464031

21第1趟：736752464031

21

82

n-1第2趟：6752464031

2173

82n-2第3趟：5246403121677382n-3第4趟：4640312152677382.第5趟：4031214652677382.第6趟：31214046526773822第7趟：21314046526773821第1趟需要进行n-1次数据交换，第2趟需要进行n-2次数据交换，依此类推...，第n-1要进行需要进行1次数据交换，数据交换操作重复进行的总次数=(n-1)+(n-2)+…+2+1=n(n-1)/2。

[初态]：2131404652677382次数第1趟：21314046526773820第2趟：21314046526773820第3趟：21314046526773820第4趟：21314046526773820第5趟：21314046526773820第6趟：21314046526773820第7趟：21314046526773820最好的情况：当初始状态已经递增有序时，第1趟不需要进行数据交换，第2趟不需要进行数据交换，依此类推...，第n-1趟也不需要进行次数据交换，如下所示：（此例中数据元素个数n=8）

计算时间复杂度以最坏情况为准，为O(n2)。当某一趟排序没有数据交换时，表明数据元素已经按递增有序，接下来的排序过程可以不必进行，但此算法依就会进行完n-1排序过程才终止。怎样解决此问题？具体做法是：设置一个变量change=true，用它来记录一趟排序过程中是否有数据交换。在每趟排序之前置change的值为false，每当产生交换数据，change的值就改为true。每趟排序之后，判断change的值，若为true，则继续下一趟排序；若为false，表明这一趟没有交换任何数据，排序已经完成。

改进算法中，如果输入数据集的初始状态已经呈现递增有序，形如21、31、40、46、52、67、73、82，则if分支下的语句无执行的机会，chang