《数据结构JAVA语言版》课件 孙爱香 第1-3章 绪论、线性表、栈和队列

数据结构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分支下的语句无执行的机会，change的值无法改变为true，始终保持false，内层循环语句执行结束后，i>0&&change逻辑表达式的运算结果为false，不能再次进入外层循环，排序过程终止。

static

voidimprove_bubble_sort(int[]a,int

n){

int

i,jtemp;boolean

change=true;

for(i=n-1;i>0&&change;--i)

{

change=false;

for(

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

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

temp=a[j];a[j]=a[j+1];a[j+1]=temp;

change=true;}}}1.4.4算法的空间效率分析算法的空间效率指的是包含算法的程序从运行开始到结束所需的存储空间。执行一个算法所需的存储空间包括三部分：（1）程序指令占用的存储空间；（2）输入数据占用的存储空间；（3）实现数据处理任务所必须的辅助存储空间。指令占用存储空间一般与问题规模n无关;输入数据占用的存储空间多数情况下与算法无关;重点分析辅助存储空间与问题规模n的函数关系，该函数记为f（n）。

请分析下面算法的空间复杂度。

static

voidimprove_bubble_sort(int[]a,int

n){

int

i,jtemp;boolean

change=true;

for(i=n-1;i>0&&change;--i)

{

change=false;

for(

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

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

temp=a[j];a[j]=a[j+1];a[j+1]=temp;

change=true;}}}该冒泡排序算法除了程序指令和输入数据占用的存储空间，还必须用到i、j、change、temp四个辅助变量，i、j、temp是int型变量，分别占用4个字节的存储空间，change是boolean型变量，占用2个字节的存储空间，所以该冒泡排序算法辅助变量占用的总存储空间14个字节，即f（n）=14，算法的空间复杂度记为O(1)，是常量阶的。第2章线性表本章主要介绍下列内容线性表的类型定义线性表的顺序存储结构线性表的链式存储结构线性表的应用举例2.1线性表的类型定义2.1.1线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列，通常表示成如下形式：

L=(a1,a2,...,ai-1,ai,ai+1,...,an)

其中，L为线性表名称，习惯用大写字母书写；ai为组成该线性表的数据元素，习惯用小写字母书写。

线性表中数据元素的个数被称为线性表的长度，当线性表的长度为0时，线性表被称为空线性表。

表中相邻元素之间存在着前后次序关系，将ai-1称为ai的直接前驱，将ai＋1称为ai的直接后继。

线性表举例：

例如，

线性表LA=(34,89,765,12,90,-34,22)中，

线性表的长度为7，数据元素类型均为整型，765是12的直接前驱，90是12的直接后继。

线性表LB=(“Hello”,“World”,“China”,“Welcome”)中，

线性表的长度为4，数据元素类型均为字符串型，“World”是“China”的直接前驱，“Welcome”是“China”的直接后继。L=(a1,a2,...,ai-1,ai,ai+1,...,an)

2.1.2线性表的四个特点：（1）存在唯一的一个被称作“第一个”的数据元素。（2）存在唯一的一个被称作“最后一个”的数据元素。（3）除第一个之外，集合中的每个数据元素均只有一个直接前驱。（4）除最后一个外，集合中的每个数据元素均只有一个直接后继。2.1.3线性表的抽象数据类型定义

ADT

LIST{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}

基本操作：}

栈D是n个数据元素的集合，D是ElemSet的子集。ElemSet表示某个集合，集合中的数据元素类型相同，例如整数集、自然数集等。栈R是数据元素之间关系的集合，<ai-1,ai>表示ai-1和ai之间互为前驱和后继的逻辑关系。

基本操作的定义如下。返回值类型

基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>“初始条件”描述了基本操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，并返回相应信息。若初始条件为空，即基本操作执行之前数据结构和参数不必满足任何条件，则省略该部分-初始条件：<初始条件描述>。“操作结果”说明了基本操作正常完成之后，数据结构的变化状况和应返回的结果。关于ADT

LIST中基本操作的几点附加说明：（1）线性表中的数据元素类型用T表示。（2）线性表基本操作是定义于逻辑结构上的基本操作，是向使用者提供的使用说明。基本操作只有在存储结构确定之后才能实现。如果线性表采用的存储结构不同，线性表基本操作的实现算法也不相同。（3）线性表基本操作的种类和数量可以根据实际需要决定。（4）线性表基本操作名称，形式参数数量、名称、类型，返回值类型由设计者决定，使用者根据设计者的设计规则使用基本操作。

基本操作P：（1）intCount()//求长度操作

操作结果：返回线性表中所有数据元素的个数，如果线性表为空，返回0。（2）Clear()//清空

操作结果：从线性表中清除所有数据元素。（3）booleanIsEmpty()//判断线性表是否为空

操作结果：判断线性表当前的状态，如果线性表为空返回true，否则返回false。

（4）Append(Titem)//附加操作初始条件：线性表未满。操作结果：将值为item的新元素添加到表的末尾。（5）Insert(Titem,inti)//插入操作初始条件：线性表未满且插入位置正确(1≤i≤n+1,n为插入前的表长)。操作结果：在线性表的第i个位置上插入一个值为item的新元素，这样使得原序号为i,i+1,…,n的数据元素的序号变为i+1,i+2,…,n+1，插入后表长=原表长+1。

（6）TDelete(inti)//删除操作初始条件：线性表不为空且删除位置正确(1≤i≤n,n为删除前的表长)。操作结果：在线性表中删除序号为i的数据元素，返回删除后的数据元素。删除后使原序号为i+1,i+2,…,n的数据元素的序号变为i,i+1,…,n-1，删除后表长=原表长-1。（7）TGetElem(inti)//取表元操作初始条件：线性表不为空且所取数据元素位置正确（1≤i≤n，n为线性表的表长）。操作结果：返回线性表中的第i个数据元素。。（8）intLocate(Tvalue)//按值查找操作

操作结果：在线性表中查找值为value的数据元素，其结果返回在线性表中首次出现的值为value的数据元素的序号，称为查找成功；否则，在线性表中未找到值为value的数据元素，返回一个特殊值-1表示查找失败。。interface

IListDS<T>{

int

Count();//求长度

void

Clear();//清空操作

boolean

IsEmpty();//判断线性表是否为空

void

Append(Titem);//附加操作

void

Insert(Titem,int

i);//插入操作

TDelete(int

i);//删除操作

TGetElem(int

i);//取表元

int

Locate(Tvalue);//按值查找}在Java程序设计语言中，用接口表示线性表的抽象数据类型如下。

2.2线性表的顺序存储及操作实现2.2.1顺序存储线性表的顺序存储是把线性表的数据元素放在一组地址连续的存储单元中。（在这种存储方式中，以元素在计算机内存储器内的物理位置来体现互为前驱和后继的逻辑关系，线性表中相邻的元素在内存储器内也相邻）

假设每个元素占用l(小写L)个存储单元，线性表中第一个元素的存储地址LOC(a1)=b，那麽线性表中第i个元素的存储地址是多少？我们利用Java语言讨论线性表的顺序存储，在Java虚拟处理器中，存储单元的编号即存储地址对用户来说是透明的，不可见的。在java虚拟处理器中我们认为线性表的顺序存储是把线性表的数据元素放在一维数组中，(数组占用的就是一组地址连续的存储单元)数据元素在数组中相邻就表示它们在线性表中互为前驱和后继。在线性表抽象数据类型的定义中讲过，定义于逻辑结构上的基本操作只是向外界使用者提供的一个使用接口，存储结构确定了之后基本操才能实现。所以接下来讨论在顺序存储结构下基本操作的实现，重点分析一下插入和删除两种基本操作的实现算法。ia1a2…an…ai+1

ai

a1a2…ani…ai+1ai

a1a2…ani…ai+1aiitemn+1n+1n+12.2.2顺序存储结构下基本操作分析

1、

在线性表的第i个位置上插入数据元素item？分析插入数据元素到线性表（即数组）的第i个位置上所需移动元素次数：答：从第i个数据元素到第n个都需移动，共需移动n-i+1次？每一个位置上都有可能插入数据元素，平均移动次数是多少？答：第一个位置上n次，第二个位置上n-1次，第三个位置上n-2次，依次类推，第n+1个位置上0次，平均移动次数为：[n+（n-1）+…+1]/n+1=n/2,即：

插入到每个位置的概率相等的情况下，平均移动次数是n/2，有些情况下插入到每个位置的概率不一定相等，怎麽算？假设插入到第一个位置的概率是1/2，其余位置是1/2n，所需移动元素次数的期望值（平均值）（用到概率中的数学期望概念）：ia1a2…an…ai+2ai+1

iia1a2…

…ai+2ai+1

an

a1

a2

……ai+2ai+1ai

an2、

删除线性表的第i个数据元素分析删除线性表的第i个数据元素所需移动元素次数答：从第i+1个数据元素到第n个都需向上移动，共需移动n-i次每一个位置上的数据元素都有可能被删除，平均移动次数是多少？答：删除第一个数据元素需要n-1次，第二个数据元素需要n-2次，第三个位置上n-3次，依次类推，第n个位置上0次，平均移动次数为：[（n-1）+（n-2）+…+1]/n=（n-1）/2,即：删除每个数据元素的概率相等的情况下即pi=1/n，平均移动次数是（n-1）/2，有些情况下删除每个数据元素概率不一定相等，怎麽算？假设删除第一个数据元素概率是1/2，其余位置是所需移动元素次数的期望值（平均值）（用到概率中的数学期望概念）：2.2.3源码实现1、几点说明：

（1）前面定义的线性表接口IListDS<T>interface

IListDS<T>{

intCount();//求长度

voidClear();//清空操作

boolean

IsEmpty();//判断线性表是否为空

void

Append(T

item);//附加操作

void

Insert(T

item,int

i);//插入操作

TDelete(int

i);//删除操作

TGetElem(int

i);//取表元

int

Locate(T

value);//按值查找}（2）顺序表类SeqList<T>，实现接口IListDS<T>。顺序表类SeqList<T>的实现说明如下所示：

public

class

SeqList<T>implements

IListDS<T>

{T[]data;

//数组，用于存储顺序表中的数据元素

int

maxsize;//顺序表的容量

int

last;

//指示顺序表最后一个元素的位置

//接口成员方法的实现；

}关于属性成员的几点说明：①Java语言中的数组在内存中占用的存储空间就是一组地址连续的存储单元，所以，在Java虚拟处理器中考虑问题时，认为线性表的顺序存储就是把线性表的数据元素存放到数组data中。②maxsize表示容量；容量可以用数组的length属性即data.length来表示，但为了说明线性表的最大长度（容量），增强可读性，在SeqList<T>类中用属性成员maxsize来表示。③线性表中的元素由data[0]开始依次顺序存放，由于线性表中的实际元素个数一般达不到maxsize，因此，在SeqList<T>类中需要一个属性成员last表示线性表中最后一个数据元素在数组中的位置。last的值等于线性表中最后一个数据元素在数组中的下标，0≤last≤maxsize-1，last值为-1时表示线性表为空。

public

SeqList(int

size){

if

(size

>0){

data

=(T[])new

Object[size];

//建立一个长度为size，类型为T的数组

this.maxsize

=size;

//顺序表的容量maxsize

=size

last

=-1;

//最后一个元素位置last=-1；表示顺序表为空。

}else

throw

new

IllegalArgumentException("初始化容量必须大于0");

}（3）顺序表类SeqList<T>的构造方法在Java语言中，一个基本操作表现为类中的一个方法。SeqList<T>类除了实现接口IListDS<T>中的方法外，还可实现一些另外的成员方法，实现更复杂的操作。2基本操作实现（1）求长度

由于数组是0基数组，即数组的最小下标为0，所以，长度就是最后一个元素在数组中的下标last加1。

求长度的算法实现如下：

public

intCount(){

return

last+1;}2、清空操作

清除顺序表中的数据元素是使顺序表为空，此时，last等于-1。

public

voidClear(){

last=-1;}

3、判断线性表是否为空如果顺序表的last为-1，则顺序表为空，返回true，否则返回false。

public

boolean

IsEmpty(){

if(last==-1){

return

true;}

else{

return

false;}}4、判断顺序表是否为满如果顺序表为满，即last等于maxsize-1，则返回true，否则返回false。

public

boolean

IsFull(){

if(last==maxsize-1)//顺序表已满

{

return

true;}

else{

return

false;}}

5、附加操作

附加操作是在顺序表未满的情况下，在表的末端添加一个新元素，然后使顺序表的last加1。

public

void

Append(T

item){

if(last==maxsize-1)//顺序表已满

{System.out.println("Listisfull");

//输出顺序表已满信息提示

return;//返回

}

data[++last]=item;//在表的末端添加一个新元素，使顺序表的last加1}

6、插入操作Insert(Titem,inti)

顺序表的插入是指在顺序表的第i个位置插入一个值为item的新元素。

插入后使原表长为n的表

(a1,a2,…,ai-1,ai,ai+1,…,an)成为表长为n+1的表

(a1,a2,…,ai-1,item,ai,ai+1,…,an)。i的取值范围为1≤i≤n+1（n为顺序表的表长=last+1）。i为n+1(即last+2)时，表示在顺序表的末尾插入数据元素。

顺序表上插入数据元素的步骤如下：判断顺序表是否已满和插入的位置是否正确，表满或插入的位置不正确不能插入；如果表未满和插入的位置正确，则将an～ai依次向后移动，为新的数据元素空出位置。在算法中用循环来实现；将新的数据元素插入到空出的第i个位置上；修改last（相当于修改表长），使它仍指向顺序表的最后一个数据元素。

插入操作的算法实现如下：

public

void

Insert(T

item,int

i){

//判断顺序表是否已满

if(IsFull()){

System.out.println("Listisfull");

return;}//判断插入的位置是否正确，//i小于1表示在第1个位置之前插入，//i大于last+2表示在最后一个元素后面的第2个位置插入。

if(i<1||i>last+2){

System.out.println("Positioniserror!");

return;}

//元素移动

for(int

j=last;j>=i-1;--j){

data[j+1]=data[j];}

//将新的数据元素插入到第i个位置上

data[i-1]=item;

//修改表长

++last;}算法的时间复杂度分析：顺序表上的插入操作，时间主要消耗在数据的移动上；在第i个位置插入一个元素，从ai到an都要向后移动一个位置，共需要移动n-i+1个元素；i的取值范围为1≤i≤n+1，当i等于1时，需要移动的元素个数最多，为n个；当i为n+1时，不需要移动元素。插入操作的时间复杂度为O（n）。7、删除操作顺序表的删除操作是指将表中第i个数据元素从顺序表中去掉。删除后使原表长为n的表(a1,a2,…,ai-1,ai,ai+1,…,an)变为表长为n-1的表(a1,a2,…,ai-1,ai+1,…,an)。i的取值范围为1≤i≤n。i为n时，表示删除末尾的数据元素。

顺序表上删除一个数据元素的步骤如下：（1）判断顺序表是否为空和删除的位置是否正确，表空或删除的位置不正确不能删除；

（2）如果表未空和删除的位置正确，则将ai+1～an依次向前移动。在算法中用循环来实现；

（3）修改last（相当于修改表长），使它仍指向顺序表的最后一个元素。

publicTDelete(inti)删除操作的算法实现如下：

publicTDelete(int

i){Ttmp;

//判断表是否为空

if(IsEmpty()){

throw

new

RuntimeException("线性表为空，无法删除");}

//判断删除的位置是否正确

//i小于1表示删除第1个位置之前的元素，

//i大于last+1表示删除最后一个元素后面的第1个位置的元素。

if(i<1||i>last+1){

throw

new

RuntimeException(“无效的下标：”+i);

//抛出异常}

tmp=data[i-1];

//tmp值等于顺序表的第i个数据元素data[i-1]

for(int

j=i;j<=last;++j){

data[j-1]=data[j];}//元素移动

--last;//修改表长

return

tmp;//返回tmp值}

算法的时间复杂度分析在第i个位置删除一个元素，从ai+1到an都要向前移动一个位置，共需要移动n-i个元素；而i的取值范围为1≤i≤n；当i等于1时，需要移动的元素个数最多，为n-1个；当i为n时，不需要移动元素；删除操作的时间复杂度为O(n)。8、取表元TGetElem(inti)取表元运算是返回顺序表中第i个数据元素。i的取值范围是1≤i≤last+1步骤如下：判断表是否为空和位置是否正确返回顺序表的第i个数据元素

取表元运算的算法实现如下：顺序表取表元运算的时间复杂度为O（1）。

publicTGetElem(int

i){//判断表是否为空和位置是否正确

if(IsEmpty()){

throw

new

RuntimeException("线性表为空，无法删除"); }

//判断位置是否正确

//i小于1表示获取第1个位置之前的元素，

//i大于last+1表示获取最后一个元素后面的第1个位置的元素。

if(i<1||i>last+1) {

throw

new

RuntimeException("无效的下标："+i);

//返回tmp }

return

data[i-1];//返回顺序表的第i个数据元素

}

9、按值查找int

Locate(Tvalue)

顺序表中的按值查找是指在表中查找满足给定值的数据元素。从第一个元素起依次与给定值比较，如果找到，则返回在顺序表中首次出现与给定值相等的数据元素的序号，称为查找成功；否则，在顺序表中没有与给定值匹配的数据元素，返回一个特殊值-1表示查找失败。

按值查找运算的算法实现如下：

public

int

Locate(T

value){

//顺序表为空

if(IsEmpty()){

System.out.println("listisEmpty");

return-1;}

int

i=0;

//循环处理顺序表

for(i=0;i<=last;++i){

//顺序表中存在与给定值相等的元素

if(data[i]==value){

break;}}

//顺序表中不存在与给定值相等的元素

if(i>last){

return-1;}

return

i;}算法的时间复杂度分析顺序表中的按值查找的主要运算是比较，比较的次数与给定值在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为1；而当给定值与最后一个元素相等时，比较次数为n。平均比较次数为(n+1)/2，时间复杂度为O（n）。10、输出线性表

2.2.4顺序表中的复杂操作【例2-1】已知顺序表L，写一算法将其倒置。(a)

(b)

112336458060406640608045362311

算法思路把第一个元素与最后一个元素交换，把第二个元素与倒数第二个元素交换。也就是，把第i个元素与第n-i+1个元素交换。（n为线性表中元素的个数）i的取值范围是1到n/2。（包括n/2）public

static

void

ReversSeqList(SeqList<Integer>L)存储整数的顺序表的倒置的算法实现如下：

public

static

void

ReversSeqList(SeqList<Integer>L){//顺序表数据类型是int

int

tmp=0;

int

n=L.Count();//n等于线性表的长度

//以下循环实现顺序表的倒置

for(int

i=1;i<=n/2;++i){

//数组下标从0开始，所以是下标i-1的元素与n-i的元素交换

tmp=L.data[i-1];

L.data[i-1]=L.data[n-i];

L.data[n-i]=tmp;}}该算法只是对顺序表中的数据元素顺序扫描一遍即完成了倒置，所以时间复杂度为O(n)。【例2】有数据类型为整型的顺序表La和Lb，其数据元素均按从小到大的升序排列，编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。

算法实现思路是依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。线性表采用顺序存储方式时,缺点：

1）占用一组编号连续的存储单元。

2）删除、插入操作需大量移动数据元素。

为什麽说占用一组编号连续的存储单元是缺点？某一时刻计算机内存状态因为计算机的内存中存在很多零碎的小空间;采用顺序存储方式时,占用一组编号连续的存储单元,这些零碎的小空间得不到充分利用.2.3.1基本概念1、线性表的链式存储线性表的链式存储是指用一组任意的存储单元（可以不连续）存储线性表中的数据元素。

Le=(‘A’,‘B’,‘C’)数据类型是字符型，字符型数据占用二个存储单元，即二个字节。

Le的顺序存储结构：线性表的顺序存储是指用一组连续的存储单元存储线性表中的数据元素。采用顺序存储方式时，数据的存储是有规律的，计算机可以通过数据元素自身的地址计算出它的后继元素地址，从而找到它的后继元素。假设数据元素A的存储地址是L,它的后继元素的存储地址是：L+2,L+2地址里面存放着B，表明A的后继元素就是B数据元素B的存储地址是L+2，它的后继元素的存储地址是L+4L+4地址里面存放着C，表明B的后继元素就是C……B……A……C……864128Le=(‘A’,‘B’,‘C’)的链式存储结构：线性表采用链式存储时是用一组任意的存储单元存放它的数据元素，数据的存储毫无规律可言，计算机通过数据元素自身的地址无法计算出它的后继元素地址，从而无法找到它的后继元素是谁。……8B……128A……NULLC……864128我们需要在它的后面附加一个指针(引用)，指向它的后继元素。查找元素后继时，利用指针(引用)提供的后继元素地址，从而找到它的后继元素。例如：数据元素A，利用指针提供的后继元素地址128，可以确认它的后继是B。数据元素B，利用指针提供的后继元素地址8，可以确认它的后继是C。讲到这儿，同学们能不能看出链式存储的一个优点？

线性表的数据元素不必放在地址连续的存储单元中，零碎空间能得到充分的利用。

ABCNULL在Java语言中，内存单元的编号8，64，128对用户屏蔽（也就是8，64，128不需要我们知道）,线性表的链式存储结构可以用如下形式表示：箭头代表指针(引用)，指向下一个元素的存储位置一个蓝色的方块称为一个结点,它包含数据和指针（引用）两部分。2、结点：数据和引用（指针）的组合。上图中一个蓝色的方块就代表一个结点。ABCnull3、链表：线性表的链式存储结构。上图三个方块加两个箭头就是一个链表。

数据部分命名为data：用来存放线性表中数据元素。引用（指针）部分命名为next：存放下一个结点的地址。L=的链表（同学们自画）a1a2an∧heada1a2an∧head

a1a2an