数据结构(Java语言描述)：第1章 绪论java版

第一章绪论教学内容1.2基本概念与术语1.3算法与算法分析1.4Java提供的泛型方法1.1数据结构课程讨论的内容教学重点与难点重点：数据结构的基本概念及有关术语算法及算法的分析方法难点：时间复杂度的估算课前思考你知道数据结构是一门讨论什么内容的学科吗？著名的瑞士科学家沃思教授）

Algorithm

+DataStructures=Programs

(算法+数据结构=程序）数据结构:算法:程序:为计算机处理问题而编制的一组指令集处理问题的策略（是对数据运算的描述，是程序的逻辑抽象）问题的数学模型，它反映数据及其之间关系。（存储结构和逻辑结构）1.1数据结构课程讨论的内容1.1.1求解问题举例问题求解的主要步骤：1.确定求解问题的数学模型

(逻辑结构)；2.确定存储结构；3.设计算法；4.编程并测试结果。

程序设计的实质是在于解决两个主要问题：一是根据实际问题选择一种好的数据结构；二是设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。1.1.1求解问题举例【例1】N个数的选择问题

算法：?模型：?如何选择？N个数在计算机中的组织1.1.1求解问题举例【例2】生产订单的自动查询问题

算法：?模型：?如何查询？生产订单数据在计算机中的组织1.1.1求解问题举例【例3】城市网络的铺设问题

算法：?模型：?如何为城市的各小区之间铺设网络线路,使投资最小?(对n个小区只需铺设n-1条线路)图的最小生成树1.1.1求解问题举例1.1.2本课程的内容方面过程数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构的比较和算法性能分析数据结构课程的内容体系:简单地说,本课程研究的内容包括以下三方面：

1.数据的逻辑结构

2.数据的存储结构/物理结构

3.数据的运算数据与数据结构数据类型抽象数据类型1.2基本概念与术语1.2.1数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的总称。如：实数、整数、字符（串）、图形和声音等。数据(Data):是计算机操作对象的集合。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素（DataElement):是数据结构中讨论的基本单位不同场合也叫结点、顶点、记录1.2.1数据与数据结构

数据项（DataItem）：是数据结构中讨论的最小单位数据元素是由若干个数据项组成例如：描述一个运动员的数据元素称之为组合项,其它为简单项年月日姓名

俱乐部名称出生日期参加日期职务业绩1.2.1数据与数据结构

数据对象（DataObject）：是性质相同的数据元素的集合例如：学生成绩表是一个数据对象学号姓名数学分析普通物理高等代数2000120002200032000420005张三李四丁一马二王五908067985656876790878967876768

数据对象中的数据元素不会是孤立的，而是彼此相关的，这种彼此之间的关系称为“结构”,如书中表1.1、图1.2(a)、图1.3都形成了其特定的结构（线性表、图、树）。行：数据元素列：数据项

数据结构（DataStructure）：逻辑结构线性结构(1:1)树形结构(1:n)图状结构(m:n)集合结构(松散)非线性结构是相互之间存在一种或多种关系的数据元素的集合。按逻辑关系分为：CADBEADCBFEGABCDEBCADE逻辑结构可用二元组形式定义为:Data_Structures=(D,R)其中:D是数据元素的有限集合，

R是D上关系的有限集合。也可用数据的逻辑结构图来形象表示之。1.2.1数据与数据结构【例1】设有数据结构为：B=（D，R），其中：D={k1,k2,k3,….k9}R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}画出其逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些是终端结点？k2k1k4k5k3k8k6k9k7开始结点为k1,k2(无前驱的结点）终端结点为k6,k7(无后继的结点）【例2】矩阵

中9个元素之间存在两种关系，一种是行关系，一种是列关系，试给出其逻辑结构的二元组表示形式。

，，，其逻辑结构的二元组表示形式为：B=（D，R），其中：

D={a1,a2,……,a9}

R={ROW,COL}//ROW:行关系，COL:列关系

ROW={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>,<a7,a8>,<a8,a9>}

COL={<a1,a4>,<a4,a7>,<a2,a5>,<a5,a8>,<a3,a6>,<a6,a9>}存储结构

——是逻辑结构在计算机中的表示，（即是逻辑结构在存储器中的映象）“数据元素”的映象？“关系”的映象？1.2.1数据与数据结构“数据元素”的映象方法：用二进制位(bit)的位串表示数据元素(456)10

=(710)8

=(111001000)2B=(102)8=(001000010)2存储结构

1.2.1数据与数据结构——存储结构

1.2.1数据与数据结构——“数据关系”的映象方法：如：表示x,y的方法：1.顺序映象以相对的存储位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中整个存储结构中只含数据元素值本身的信息xy顺序存储结构（逻辑位置关系与存储位置关系是一致的）注意存储结构

1.2.1数据与数据结构——2.链式（非线性）映象以附加信息(指针)表示后继关系。需要用一个和x附加在一起的指针来指示y的存储位置。yx链式存储结构

(表示x,y的方法)所有元素存放在可以不连续的存贮单元中逻辑上相邻的元素其存储位置不一定相邻注意数据的存储结构顺序存储链式存储散列存储索引存储最常用的两种存储结构

1.2.1数据与数据结构——1.2.2数据类型

其实数据类型反映三个方面的内容：存储结构，取值范围和允许进行的操作。在用高级程序语言编写的程序中，每个数据都应有一个所属的、确定的数据类型。在Java语言中，简单数据可描述为Java内置的8种基本的数据类型之一；而对于复杂数据则可通过类的声明来引入新的数据类型。其中类的对象(object)是新的类型的实例，类的成员变量确定了新的数据类型的数据表示方法和存储结构，类的构造函数和成员函数确定了新的数据类型的操作。可用Java语言中的“数组”类型来实现顺序存储结构，用Java语言中提供的“对象引用”来实现链式存储结构。

例如：学生成绩表基于数组的顺序存储结构可描述如下：-学生成绩记录的类描述packagech01;publicclassResultsRecord{publicStringstudentNum;//学号publicStringstudentName;//学生姓名publicfloatmathScore;//数学分析publicfloatphysicalScore;//普通物理publicfloatalgebraScore;//高等代数publicStringgetStudentNum(){ returnstudentNum;}publicvoidsetStudentNum(StringstudentNum){ this.studentNum=studentNum;}……} -基于数组的顺序存储的类描述packagech01;publicclassSqResults{privateResultsRecord[]listElem；

//存放学生成绩的存储空间

privateintcluLen;//当前学生成绩表的长度

……}

1.2.2数据类型1.2.3抽象数据类型

抽象数据类型(AbstractDataType,简称ADT)是指一数据值的集合和定义在这个集合上的一组操作。AbstractDataType={Objects}{Operations}〖例如〗int={0,1,2,,INT_MAX,INT_MIN}{,,,,,}〖例如〗

复数的ADT：数据对象(Objects):

(real,imag)数据操作(Operation):

getReal():取当前复数的实部值；

getImag():取当前复数的虚部值；

setReal(real):修改当前复数的实部值；setImag(imag):修改当前复数的虚部值；

add(z):与另一个复数的加法运算；

minus(z):与另一个复数的减法运算

multiply

(z):与另一个复数的乘法运算；

以后将全部采用Java接口表示抽象数据类型。下面通过两个具体实例来说明抽象数据类型的描述和实现。1.2.2数据类型〖例1.3〗

用Java接口来描述复数的抽象数据类型。假设复数的操作只包含：构造一个实部和虚部为给定值的复数，读取和修改复数的实部和虚部，以及两个复数的求和。

//复数抽象数据类型的接口表示publicinterfaceIComplex{ publicdoublegetReal();//取实部

publicvoidsetReal(doublereal);//修改实部

publicdoublegetImag();//取虚部publicvoidsetImag(doubleimag);//修改虚部

publicvoidadd(IComplexZ);//两个实数的求和}publicclassCompleximplementsIComplex{

}

〖例1.4〗编写实现【例1.3】中复数抽象数据类型的Java类代码。

privatedoublereal;//实部privatedoubleimag;//虚部//构造一个实数publicComplex(doublereal,doubleimag){ this.real=real; this.imag=imag;}//取实部publicdoublegetReal(){ returnreal;}……publicclassCompleximplementsIComplex{

}

例1.4编写实现【例1.3】中复数抽象数据类型的Java类代码。

//修改实部publicvoidsetReal(doublereal){ this.real=real;}……//取虚部publicdoublegetImag(){

returnimag;}//修改虚部publicvoidsetImag(doubleimag){ this.imag=imag;}publicclassComplex

implementsIComplex{

}

例1.4编写实现【例1.3】中复数抽象数据类型的Java类代码。

……//两个实数的求和publicvoidadd(IComplexZ){ if(Z!=null){ real+=Z.getReal(); imag+=Z.getImag(); }}算法的基本概念算法的描述算法分析1.3算法与算法分析1.3.1算法的基本概念何谓算法？

算法是对特定问题求解步骤的一种描述。严格来讲，一个算法一般应具有以下5种性质：1．有穷性

2．确定性3．有效性4．输入5．输出算法与程序有区别吗？算法设计的目标:设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率（时间与空间）1.3.1算法的基本概念1.3.2算法的描述

本教程描述算法全部采用Java程序设计语言。

【例1】给出求整型数组a中最大值的算法。publicstaticint

maxEle(int[]a){intn=a.length;intmax=a[0];

for(inti=1;i<n;i++)

if(max<a[i])max=a[i];returnmax;}

【例2】给出将整型数组a中数据元素实现就地逆置的算法。1.3.2算法的描述publicstaticvoidreverse(int[]a){intn=a.length;inttemp;for(inti=0,j=n-1;

i<j;i++,j--){temp=a[i];a[i]=a[j];a[j]=temp;}}1.3.3算法分析

算法分析→算法复杂度的评判

算法复杂度时间复杂度空间复杂度时间复杂度通常有两种衡量算法时间(效率)的方法:事后统计法事前分析估算法缺点：1．必须执行程序

2．其它因素掩盖算法本质和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的硬件速度6．程序运行的软件环境时间复杂度

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，记为T(n),并将称T(n)为算法的时间复杂度。【定义】算法的时间复杂度T(n)=O(f(n))

当且仅当存在正常数c和N，对所有的

n(n≥N)满足0≤T(n)≤c×f(n)。例如：T(n)=4n3+3n2+2n+1=

O(n3)?其中c=10,N=1如何估算算法的时间复杂度？1.3.3算法分析算法=控制结构+原操作

（固有数据类型的操作）算法的执行时间

=原操作(i)的执行次数×原操作(i)的执行时间

算法的执行时间

与

原操作执行次数之和

成正比

1.3.3算法分析【例1】变量计量语句频度1n+1nn+1n(n+1)n2T(n)=2n2+4n+3=O(n2)1.3.3算法分析x=0;y=0;s=0;

for(k=1;k<=n;++k){

++x;s+=x;}

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

for(j=1;j<=n;++j){

++y;s+=y;}【例2】两个矩阵相乘语句频度n+1n(n+1)n2n2(n+1)n3T(n)=2n3+3n2+1=O(n3)1.3.3算法分析publicstaticvoidsquareMult

(int[][]a,int[][]b,int[][]c,intn){

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

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

c[i][j]=0;

for(intk=0;k<n;k++)

c[i][j]+=a[i][k]*b[k][j];

}

}

简单地：从算法中选取一种对于所研究的问题来说是关键操作

的原操作，以该关键操作在算法中重复执行的次数（语句频度）

作为算法运行时间的衡量准则。1.3.3算法分析【例3】求下列算法的关键操作语句的语句频度及算法的时间复杂度publicstaticmyOut(){

for(i=1;

i<=n;i=10*i)

printf("%4d",i);

}解：设关键操作语句的语句频度为f(n),则有10f(n)≤n,所以f(n)≤log10n

故:T(n)=O(log10n)1.3.3算法分析

有些算法在规模相同的情况之下，其语句频度会因输入的数据值或输入的数据顺序不同而不同，则时间复杂度也会不同，为此有最好、最坏和平均时间复杂度之分。1.3.3算法分析【例4】如下算法实现的功能是在数组a[0:n-1]中查找值为x的数据元素。若找到，则返回x在a中的位置；否则，返回-1。求其时间复杂度。publicstaticintrSearch(int[]a,intx){

intn=a.length;

for(inti=0;i<n&&!x.equals(a[i]);i++);

if(i==n)

return-1;

else

returni;

}最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)1.3.3算法分析【例5】如下算法是用冒泡排序法对数组a中的n个整型数据元素进行排序，求该算法的时间复杂度。1.3.3算法分析publicstaticvoidbubbleSort(int[]a,intn){

inttemp,flag=1;

for(inti=1;i<n&&flag;i++){

flag=0;

for(intj=0;j<n-i;j++){

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

flag=1;

temp=a[j];

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

a[j+1]=tmep;

}

}

}

}最好时间复杂度：O(n)

最坏时间复杂度：O(n2)按增长率由小至大的顺序排列有：注意多项式时间算法的时间复杂度：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间算法的时间复杂度：O(2n)<O(n!)<O(nn)总之，随着的增大，指数时间算法和多项式时间算法在所需时间上相差非常悬殊。1.3.3算法分析§2AsymptoticNotation2nn2nlognnLognfn1.3.3算法分析s=microsecond=10-6secondsms=millisecond=10-3secondssec=secondsmin=minutesyr=yearshr=hoursd=daysn1.3.4算法设计比较【问题描述】给定一整数序列A1，A2，...An

（可能有负数），求A1～An的一个子序列Ai～Aj，使得Ai到Aj的和最大。例如：整数序列-2,11,-4,13,-5,2,-5,-3,12,-9的最大子序列的和为21（从A2到A9）；整数序列4，-3，5，-2，1，2，6，-2的最大子序列的和为11（从A1到A7）。下面介绍四种实现方法方法一:穷举法(书中算法1.1)publicstaticintmaxSub_1(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;//第一重循环执行一次则计算出长度为i的所有子序列和的最大值

for(inti=1;i<=n;i++)

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

for(intk=j;k<j+i&&k<n;k++)sum+=sequence[k];if(sum>max)max=sum;}returnmax;时间复杂度:O(n3)详细分析见P10方法二:(书中算法1.2)publicstaticintmaxSub_2(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;for(inti=0;i<n;i++){sum=0;

for(intj=i;j<n;j++){sum+=sequence[j];//关键操作if(sum>max)max=sum;}returnmax;时间复杂度:O(n2)43521262结果分治45626811T(n/2)T(n/2)O(n)T(n)=2T(n/2)+n,T(1)=O(1)=2[2T(n/22)+n/2]+n=2kO(1)+kn当N/2k=1时=O(nlogn)AlsotrueforN

2k算法见P22/算法1.3方法三:分治法时间复杂度:O(nlogn)方法四:动态规划法(书中算法1.4)publicstaticintmaxSub_4(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;for(inti=0;i<n;i++){sum+=sequence[i];if(sum>max)max=sum;elseif(sum<0)sum=0;}returnmax;时间复杂度:O(n)1324616113