数据结构Java语言描述课件

数据结构数据结构即是描述数据的组织形式及操作的一门课程。数据的组织形式相关研究对相应组织形式的数据上的操作研究。什么是程序？程序（Program）就是供计算机执行后，能完成特定功能的指令序列（Instructionssequence）程序=计算机指令序列程序包含两方面的内容数据对象（Objects）及数据对象之间关系数据结构(Datastructure)对这些对象的处理过程算法(Algorithm)程序／数据结构／算法程序＝数据结构＋算法（Program＝DataStructure＋Algorithm）

这个公式由NiklausWirth首先提出。

NiklausWirth是PASCAL之父和结构化程序设计的首创者，1984图灵奖获得者。数据数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括：

整数、实数、字符串、图像和声音等。数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录等。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。数据结构数据的逻辑结构可描述为：Group=（D，R）有限个数据元素的集合这些数据元素间关系的集合数据的逻辑结构可描述为：Group=（D，R）数据的逻辑结构——线性结构

A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结数据的逻辑结构——树形结构全校学生档案管理的组织方式1423213数据的逻辑结构——图形结构节点间的连结是任意的数据的存储结构——顺序存储数据的存储结构——链式存储

数据的运算通过算法(Algorithm)描述，讨论算法是数据结构课程的重要内容之一。算法是对特定问题求解步骤的一种描述。数据结构中常见的算法有：检索、排序、插入、删除、修改等。算法和算法分析（1）有穷性——算法必须总是在执行有穷步之后结束。（2）确定性——算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性——即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入——一个算法有零个或多个输入。（5）输出——一个算法有一个或多个输出。算法具有以下五个特性：求解同一计算问题可能有许多不同的算法，如何去评价这些算法的优劣？选用的算法首先应该是“正确”的。此外，主要考虑如下三点：执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等等。评价算法好坏的标准

算法执行的时间等于所有语句执行时间的总和，是算法所处理的数据个数n的函数，表示为：O(f(n))，O(f(n))称为该算法的时间复杂度。O(1)表示算法的时间是一个常数，不依赖于n；

O(n)表示算法的时间与n成正比，是线性关系；O(n2)，O(n3)，O(2n)分别称为平方阶、立方阶和指数阶；O(log2n)为对数阶算法的时间性能分析定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳记作：f(n)=O(g(n))定理：若A(n)=amnm

+am-1nm-1+…+a1n+a0是一个m次多项式，则：A(n)=O(nm)算法的时间性能分析例1、{x++;s=0;}其时间复杂度仍为Ｏ(1)，即常量阶。例2、for(i=0;i<n;i++){x++;s+=x;}即时间复杂度为线性阶。语句频度为：其时间复杂度为：语句频度为：其时间复杂度为：例3、for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++) c[i][j]+=a[i][k]*b[k][j];}语句频度为：其时间复杂度为：以下六种计算算法时间的多项式是最常用的。其关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)参见P53图4-2，图4-3当n取得很大时，指数时间算法运算时间远远超过多项式时间算法。多项式时间复杂度和指数时间复杂度空间复杂度:算法所需存储空间的度量，记作:S(n)=O(g(n))

其中n为问题的规模(或大小)算法的存储空间需求数据类型类型是一组值的集合。数据类型是指一个类型和定义在该类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作。如：Java中整型类型int的值集是{-232,…,-2,-1,0,1,2,…,232-1},还包括对这个整数类型进行的加(+)、减(-)、乘(*)、除(/)和求模(%)操作。数据类型Java语言提供了一些基本数据类型。利用基本数据类型，软件设计人员还可以设计出各种复杂的数据类型。86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号抽象数据类型（AbstractType，简称ADT）ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。一个ADT可描述为：

ADTADT-Name{

Data: //数据说明

数据元素之间逻辑关系的描述

Operation1: //操作1，

Operation2: //操作2

……

}第一章：面向对象的方法基本概念数据抽象对象类接口1.3比率类（Ratio.java）publicclassRatio{protectedint

numerator;//numeratorofratioprotectedint

denominator;//denominatorofratiopublicRatio(inttop,intbottom)//prebottom!=0//postconstructsaratioequivalenttotop::bottom{numerator=top; denominator=bottom;reduce();}

publicint

getNumerator(){ returnnumerator;}

publicint

getDenominator(){ returndenominator;}

publicdoublegetValue(){return(double)numerator/(double)denominator;}1.3比率类（Ratio.java）

publicRatioadd(Ratioother){ returnnewRatio(this.numerator*other.denominator+ this.denominator*other.numerator, this.denominator*other.denominator);}

protectedvoidreduce(){ intdivisor=gcd(numerator,denominator); numerator/=divisor; denominator/=divisor;}1.3比率类（Ratio.java）

protectedstaticint

gcd(inta,intb){ if(a==0){ if(b==0)return1; elsereturnb; } if(b<a)returngcd(b,a); returngcd(b%a,a);}

publicStringtoString(){ returngetNumerator()+"/"+getDenominator();}1.3比率类（Ratio.java）1.3Ratio（比率）类的应用

publicstaticvoidmain(String[]args){ Ratior=newRatio(1,1);//r==1.0 r=newRatio(1,2); //r==0.5 r.add(newRatio(1,3));//sumcomputed,butrstill0.5 r=r.add(newRatio(2,8));//r==0.75 System.out.println(r.getValue());//0.75printed System.out.println(r.toString());//callstoString() System.out.println(r);//callstoString()}}1.4银行帐户类(BankAccount.java)publicclassBankAccount{protectedStringaccount;//theaccountnumberprotecteddoublebalance;//thebalanceassociatedwithaccountpublicBankAccount(Stringacc,doublebal){ account=acc; balance=bal;}publicbooleanequals(Objectother){ BankAccountthat=(BankAccount)other; returnthis.account.equals(that.account);}1.4银行帐户类(BankAccount.java)publicStringgetAccount(){ returnaccount;} publicdoublegetBalance(){ returnbalance;} publicvoiddeposit(doubleamount){ balance=balance+amount;}publicvoidwithdraw(doubleamount){ balance=balance-amount;}1.4银行帐户类的应用向一个10年期，利息%5的帐户存100$

向一个20年期，利息%2.5的帐户存100$

试比较采用哪一种投资最好?1.4银行帐户类的应用publicstaticvoidmain(String[]args){BankAccount

jd=newBankAccount("JainDough",100.00);BankAccount

js=newBankAccount("JonSmythe",100.00);for(intyears=0;years<10;years++)jd.deposit(jd.getBalance()*0.05);for(intyears=0;years<20;years++)js.deposit(js.getBalance()*0.025);1.4银行帐户类的应用System.out.println("Jaininvests$100over10yearsat5%.");System.out.println("After10years"+jd.getAccount()+"has$"+jd.getBalance());System.out.println("Joninvests$100over20yearsat2.5%.");System.out.println("After20years"+js.getAccount()+"has$"+js.getBalance());}1.5一般用途类：关联（Assocoation.java）packagestructure;importjava.util.Map;publicclassAssociationimplementsMap.Entry{protectedObjecttheKey;//thekeyofthekey-valuepairprotectedObjecttheValue;//thevalueofthekey-valuepairpublicAssociation(Objectkey,Objectvalue){ Assert.pre(key!=null,"Keymustnotbenull."); theKey=key; theValue=value;}publicAssociation(Objectkey){ this(key,null);}publicbooleanequals(Objectother){ AssociationotherAssoc=(Association)other; returngetKey().equals(otherAssoc.getKey());}

publicObjectgetValue(){ returntheValue;}publicObjectgetKey(){ returntheKey;}1.5一般用途类：关联（Assocoation.java）publicObjectsetValue(Objectvalue){ ObjectoldValue=theValue; theValue=value; returnoldValue;}publicStringtoString(){ StringBuffers=newStringBuffer(); s.append("<Association:"+getKey()+"="+getValue()+">"); returns.toString();}}1.5一般用途类：关联（Assocoation.java）1.5关联的应用（atinLay.java）importstructure.*;publicclassatinLay

{//apiglatintranslatorforninewordspublicstaticvoidmain(Stringargs[]){ Associationdict[]=newAssociation[9]; dict[0]=newAssociation("a","aay"); dict[1]=newAssociation("bad","adbay"); dict[2]=newAssociation("had","adhay"); dict[3]=newAssociation("dad","adday"); dict[4]=newAssociation("day","ayday"); dict[5]=newAssociation("hop","ophay"); dict[6]=newAssociation("on","onay"); dict[7]=newAssociation("pop","oppay"); dict[8]=newAssociation("sad","adsay"); for(intargn=0;argn<args.length;argn++) {//foreachargument for(intdictn=0;dictn<dict.length;dictn++) {//checkeachdictionaryentry if(dict[dictn].getKey().equals(args[argn])) System.out.println(dict[dictn].getValue()); } }}}1.5关联的应用（atinLay.java） for(intargn=0;argn<args.length;argn++) {//foreachargument for(intdictn=0;dictn<dict.length;dictn++) {//checkeachdictionaryentry if(dict[dictn].getKey().equals(args[argn])) System.out.println(dict[dictn].getValue()); } }}}1.6字列表（atinLay.java） for(intargn=0;argn<args.length;argn++) {//foreachargument for(intdictn=0;dictn<dict.length;dictn++) {//checkeachdictionaryentry if(dict[dictn].getKey().equals(args[argn])) System.out.println(dict[dictn].getValue()); } }}}1.5关联的应用（atinLay.java）1.8接口（Interface）描述接口而并不实现接口里面的方法类中实现接口增加灵活性Designbycontract1.8接口（Interface）publicinterface

Structure{publicintsize();publicbooleanisEmpty();publicvoidclear();publicbooleancontains(Objectvalue);publicvoidadd();publicvoidremove();}1.8接口的实现PublicclassWordlistimplementsStructure{}interfaceAlarm{ voidalarm();}abstractclassDoor{ abstractvoidopen(); abstractvoidclose()；}classAlarmDoorextendsDoorimplementsAlarm{ voidopen(){…