1、数据结构数据结构v数据结构数据结构即是描述数据的即是描述数据的组织形式组织形式及及操操作作的一门课程。的一门课程。数据的组织形式相关研究数据的组织形式相关研究对相应组织形式的数据上的操作研究。对相应组织形式的数据上的操作研究。什么是程序？什么是程序？v程序（程序（Program）就是）就是供计算机执行后，能完成特供计算机执行后，能完成特定功能的指令序列（定功能的指令序列（Instructions sequence）程序程序=计算机指令序列计算机指令序列v程序包含两方面的内容程序包含两方面的内容数据对象数据对象（Objects）及）及数据对象数据对象之间关系之间关系v数据结构数据结构(Data
2、structure)对这些对象的处理过程对这些对象的处理过程v算法算法(Algorithm)程序数据结构算法程序数据结构算法v程序程序 数据结构数据结构 算法算法（Program Data Structure Algorithm）这个公式由Niklaus Wirth首先提出。Niklaus Wirth 是PASCAL之父和结构化程序 设计的首创者，1984图灵奖获得者。数据数据v数据是信息的载体数据是信息的载体。它能够被计算机识。它能够被计算机识别、存储和加工处理，是计算机程序加别、存储和加工处理，是计算机程序加工的工的“原料原料”。v随着计算机应用领域的扩大，数据的范随着计算机应用领域的扩大
3、，数据的范畴包括：畴包括：整数、实数、字符串、图像和声音整数、实数、字符串、图像和声音等。等。数据元素（数据元素（Data Element）v数据元素是数据的基本单位数据元素是数据的基本单位。数据元素也称元。数据元素也称元素、结点、顶点、记录等。素、结点、顶点、记录等。v一个数据元素可以由若干个一个数据元素可以由若干个数据项数据项（也可称为（也可称为字段、域、属性）组成。字段、域、属性）组成。v数据项数据项是具有独立含义的是具有独立含义的最小标识单位最小标识单位。数据结构数据结构数据的逻辑结构可描述为：数据的逻辑结构可描述为：Group=（D，R）有限个有限个数据元素数据元素的集合的集合这些数
4、据元素间这些数据元素间关系关系的集合的集合数据的逻辑结构可描述为：数据的逻辑结构可描述为：Group=（D，R）数据的逻辑结构数据的逻辑结构线性结构线性结构 A,B,C,，X,Y,Z学 生 成 绩 表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表线性表结点间是以线性关系联结结点间是以线性关系联结数据的逻辑结构数据的逻辑结构树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式1423213数据的逻辑结构数据的逻辑结构图形结构图形结构节点间的连结是任意的节点间的连结是任意的数据的存储结构数据的存储结构顺序存储顺序存储数据的存储结构数据的存
5、储结构链式存储链式存储 v数据的运算通过数据的运算通过算法算法(Algorithm)描述，描述，讨论算法是数据结构课程的重要内容之讨论算法是数据结构课程的重要内容之一。一。v算法算法是对特定问题求解步骤的一种描述。是对特定问题求解步骤的一种描述。v数据结构中常见的算法有：检索、排序、数据结构中常见的算法有：检索、排序、插入、删除、修改等。插入、删除、修改等。算法和算法分析算法和算法分析v（1）有穷性有穷性算法必须总是在执行有穷步之算法必须总是在执行有穷步之后结束。后结束。v（2）确定性确定性算法中每一条指令必须有确切算法中每一条指令必须有确切的含义。不存在二义性。的含义。不存在二义性。v（3）
6、可行性可行性即算法描述的操作都是可以通即算法描述的操作都是可以通过已经实现的过已经实现的基本运算基本运算执行有限次来实现的。执行有限次来实现的。v（4）输入输入一个算法有零个或多个输入。一个算法有零个或多个输入。v（5）输出输出一个算法有一个或多个输出。一个算法有一个或多个输出。算法具有以下五个特性：算法具有以下五个特性：v求解同一计算问题可能有求解同一计算问题可能有许多不同许多不同的算法，如的算法，如何去评价这些算法的优劣？何去评价这些算法的优劣？v选用的算法首先应该是选用的算法首先应该是“正确正确”的。此外，主的。此外，主要考虑如下三点：要考虑如下三点：执行算法所耗费的执行算法所耗费的时间
7、时间；执行算法所耗费的执行算法所耗费的存储空间存储空间，其中主要考虑，其中主要考虑辅辅助存储空间助存储空间；算法应易于理解，易于编码，易于调试等等。算法应易于理解，易于编码，易于调试等等。评价算法好坏的标准评价算法好坏的标准 v算法执行的时间等于所有语句执行时间的总和，算法执行的时间等于所有语句执行时间的总和，是算法所处理的数据个数是算法所处理的数据个数n的函数，表示为：的函数，表示为：O(f(n)，vO(f(n)称为该算法的称为该算法的时间复杂度时间复杂度。vO(1)表示算法的时间是一个常数，不依赖于表示算法的时间是一个常数，不依赖于n；v O(n)表示算法的时间与表示算法的时间与n成正比，
8、是线性关系；成正比，是线性关系；vO(n2)，O(n3)，O(2n)分别称为平方阶、立方分别称为平方阶、立方阶和指数阶；阶和指数阶；O(log2n)为对数阶为对数阶算法的时间性能分析算法的时间性能分析 v定义：定义：如果存在两个如果存在两个正常数正常数c和和n0，对于，对于所有的所有的nn0，有，有f(n)cg(n)记作：记作：f(n)=O(g(n)v定理：定理：若若A(n)=amnm+am-1nm-1+a1n+a0是一个是一个m次多项式次多项式，则：，则：A(n)=O(nm)算法的时间性能分析算法的时间性能分析 v例例1、x+;s=0;其时间复杂度仍为其时间复杂度仍为(1)，即，即常量阶常量
9、阶。v例例2、for(i=0;in;i+)x+;s+=x;即时间复杂度为即时间复杂度为线性阶线性阶。nn2)11()(n11语句频度为：语句频度为：其时间复杂度为：其时间复杂度为：)1(语句频度为：语句频度为：其时间复杂度为：其时间复杂度为：例例3、for(i=0;in;i+)for(j=0;jn;j+)cij=0;for(k=0;kn;k+)cij+=aik*bkj;23nn 语句频度为：语句频度为：其时间复杂度为：其时间复杂度为：)(3nv以下六种计算算法时间的以下六种计算算法时间的多项式多项式是最常用的。其关是最常用的。其关系为：系为：O(1)O(logn)O(n)O(nlogn)O(n
10、2)O(n3)v指数时间指数时间的关系为：的关系为：O(2n)O(n!)O(nn)v参见参见P53图图4-2，图，图4-3v当当n取得很大时，取得很大时，指数时间算法指数时间算法运算时间运算时间远远超过远远超过多项式时间算法多项式时间算法。多项式时间复杂度多项式时间复杂度和和指数时间复杂度指数时间复杂度v空间复杂度空间复杂度:算法所需存储空间的度量，算法所需存储空间的度量，记作记作:S(n)=O(g(n)其中其中n为问题的规模为问题的规模(或大小或大小)算法的存储空间需求算法的存储空间需求数据类型数据类型v类型类型是一组是一组值值的的集合集合。v数据类型数据类型是指一个是指一个类型类型和定义在
11、该类型和定义在该类型上的上的操作集合操作集合。v数据类型定义了数据的数据类型定义了数据的性质性质、取值范围取值范围以及对数据所能进行的以及对数据所能进行的各种操作各种操作。v如：如：Java中整型类型中整型类型int的值集是的值集是-232,-2,-1,0,1,2,232-1,还包括对这个还包括对这个整数类型进行的加整数类型进行的加(+)、减、减(-)、乘、乘(*)、除、除(/)和求模和求模(%)操作操作。数据类型数据类型vJava语言提供了一些语言提供了一些基本数据类型基本数据类型。v利用基本数据类型，软件设计人员还可利用基本数据类型，软件设计人员还可以设计出各种以设计出各种复杂的数据类型复
12、杂的数据类型。86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号抽象数据类型（抽象数据类型（Abstract Type，简称，简称ADT）vADT是指是指抽象数据的组织抽象数据的组织和与之相关的和与之相关的操作操作。可。可以看作是以看作是数据的逻辑结构数据的逻辑结构及其在逻辑结构上定义及其在逻辑结构上定义的的操作操作。v一个一个ADT可描述为：可描述为：ADT ADT-Name Data:/数据说明数据说明 数据元素之间逻辑关系的描述数据元素之间逻辑关系的描述 Operation1:/操作操作1，Operation2:/操作操作2 第一章：面向对象的方法v基本
13、概念数据抽象对象类接口1.3 比率类（比率类（Ratio.java）v public class Ratiov v protected int numerator;/numerator of ratiov protected int denominator;/denominator of ratiov public Ratio(int top,int bottom)v/pre bottom!=0v/post constructs a ratio equivalent to top:bottomv v numerator=top;vdenominator=bottom;v reduce();v
14、v public int getNumerator()v vreturn numerator;v v public int getDenominator()v vreturn denominator;v v public double getValue()v v return(double)numerator/(double)denominator;v 1.3 比率类（比率类（Ratio.java）v public Ratio add(Ratio other)v vreturn new Ratio(this.numerator*other.denominator+v this.denomina
15、tor*other.numerator,v this.denominator*other.denominator);v v vprotected void reduce()v vint divisor=gcd(numerator,denominator);vnumerator/=divisor;vdenominator/=divisor;v 1.3 比率类（比率类（Ratio.java）v protected static int gcd(int a,int b)v vif(a=0)v if(b=0)return 1;v else return b;vvif(b a)return gcd(b,
16、a);vreturn gcd(b%a,a);v v vpublic String toString()v vreturn getNumerator()+/+getDenominator();v 1.3 比率类（比率类（Ratio.java）1.3 Ratio（比率）类的应用（比率）类的应用v public static void main(String args)v vRatio r=new Ratio(1,1);/r=1.0vr=new Ratio(1,2);/r=0.5vr.add(new Ratio(1,3);/sum computed,but r still 0.5vr=r.add(n
17、ew Ratio(2,8);/r=0.75vSystem.out.println(r.getValue();/0.75 printedvSystem.out.println(r.toString();/calls toString()System.out.println(r);/calls toString()vv1.4 银行帐户类银行帐户类(BankAccount.java)vpublic class BankAccountvv protected String account;/the account numberv protected double balance;/the balanc
18、e associated with accountvpublic BankAccount(String acc,double bal)v vaccount=acc;vbalance=bal;v vpublic boolean equals(Object other)v vBankAccount that=(BankAccount)other;vreturn this.account.equals(that.account);v 1.4 银行帐户类银行帐户类(BankAccount.java)vpublic String getAccount()v vreturn account;v vpubl
19、ic double getBalance()v vreturn balance;v vpublic void deposit(double amount)v vbalance=balance+amount;v vpublic void withdraw(double amount)v vbalance=balance-amount;v 1.4 银行帐户类的应用银行帐户类的应用v向一个向一个10年期，利息年期，利息%5的帐户存的帐户存100$向一个向一个20年期，利息年期，利息%2.5的帐户存的帐户存100$试比较采用哪一种投资最好试比较采用哪一种投资最好?1.4 银行帐户类的应用银行帐户类的应
20、用public static void main(String args)BankAccount jd=new BankAccount(Jain Dough,100.00);BankAccount js=new BankAccount(Jon Smythe,100.00);for(int years=0;years 10;years+)jd.deposit(jd.getBalance()*0.05);for(int years=0;years 20;years+)js.deposit(js.getBalance()*0.025);1.4 银行帐户类的应用银行帐户类的应用System.out.p
21、rintln(Jain invests$100 over 10 years at 5%.);System.out.println(After 10 years +jd.getAccount()+has$+jd.getBalance();System.out.println(Jon invests$100 over 20 years at 2.5%.);System.out.println(After 20 years +js.getAccount()+has$+js.getBalance();1.5 一般用途类：关联（一般用途类：关联（Assocoation.java）vpackage str
22、ucture;vimport java.util.Map;vpublic class Association implements Map.Entryvvprotected Object theKey;/the key of the key-value pairvprotected Object theValue;/the value of the key-value pairvpublic Association(Object key,Object value)v vAssert.pre(key!=null,Key must not be null.);vtheKey=key;vtheVal
23、ue=value;v vpublic Association(Object key)v vthis(key,null);v vpublic boolean equals(Object other)v vAssociation otherAssoc=(Association)other;vreturn getKey().equals(otherAssoc.getKey();v v vpublic Object getValue()v vreturn theValue;v vpublic Object getKey()v vreturn theKey;v 1.5 一般用途类：关联（一般用途类：关联
24、（Assocoation.java）vpublic Object setValue(Object value)v vObject oldValue=theValue;vtheValue=value;vreturn oldValue;v vpublic String toString()v vStringBuffer s=new StringBuffer();vs.append();vreturn s.toString();v v1.5 一般用途类：关联（一般用途类：关联（Assocoation.java）1.5 关联的应用（关联的应用（atinLay.java）import structure
25、.*;vpublic class atinLay v /a pig latin translator for nine wordsvpublic static void main(String args)v vAssociation dict=new Association9;vdict0=new Association(a,aay);vdict1=new Association(bad,adbay);vdict2=new Association(had,adhay);vdict3=new Association(dad,adday);vdict4=new Association(day,ay
26、day);vdict5=new Association(hop,ophay);vdict6=new Association(on,onay);vdict7=new Association(pop,oppay);vdict8=new Association(sad,adsay);vfor(int argn=0;argn args.length;argn+)v /for each argumentv for(int dictn=0;dictn dict.length;dictn+)v /check each dictionary entryvif(dictdictn.getKey().equals
27、(argsargn)v System.out.println(dictdictn.getValue();v vv v1.5 关联的应用（关联的应用（atinLay.java）vfor(int argn=0;argn args.length;argn+)v /for each argumentv for(int dictn=0;dictn dict.length;dictn+)v /check each dictionary entryvif(dictdictn.getKey().equals(argsargn)v System.out.println(dictdictn.getValue();
28、v vv v1.6 字列表（字列表（atinLay.java）vfor(int argn=0;argn args.length;argn+)v /for each argumentv for(int dictn=0;dictn dict.length;dictn+)v /check each dictionary entryvif(dictdictn.getKey().equals(argsargn)v System.out.println(dictdictn.getValue();v vv v1.5 关联的应用（关联的应用（atinLay.java）1.8 接口（接口（Interface）v
29、描述接口而并不实现接口里面的方法v类中实现接口v增加灵活性vDesign by contract1.8 接口（接口（Interface）public interface Structure public int size();public boolean isEmpty();public void clear();public boolean contains(Object value);public void add();public void remove();1.8 接口的实现接口的实现Public class Wordlist implements Structureinterface
30、 Alarm void alarm();abstract class Door abstract void open();abstract void close()；class AlarmDoor extends Door implements Alarm void open()void close()void alarm()1.9 用户用户v程序员在将类导入到程序中时使用了类。v对于一些自己实现的类，自己可能是唯一的用户。v站在用户的角度设计并遵守你的接口。v程序的注释，文档v类的数据成员应受保护，不可从外部直接访问，需遵守接口访问规则第二章 注释、条件、断言v基本概念前提条件后置条件断言版
31、权代码注释v精心设计的文字，用来描述程序中：变量的使用，机器的状态，设计者的意图和技巧等。v何时写注释？应和程序代码同时编写。v注释出现在何处？对代码感觉不放心的地方。v注释的作用有利于理解程序代码。以便让别人或者今后自己查看原有代码。前置条件n描述方法在何种情况下可以被调用，并且能够得到正确的结果。例如：一个除法方法要求分母非0 平方根函数要求非负/x is nonnegative/denominator can not be zero前置条件v调用方法时不满足前置条件时会怎样？v答：Java中，前置条件不满足的情况下调用一个方法是合法的，但不会得到预想的结果。v如果一个方法没有前置条件，意
32、味着什么？v答：说明该程序在任何情况下调用都不会出错。后置条件v在调用满足前提条件下，方法运行完毕后的状态。v每一个例程都应有后置条件。（如果没有后置条件意味着什么？）Public void withdraw(double amount)/pre:there are sufficient funds in the account/post:withdraw money from the bank account balance=balance amount;前提、后置条件的作用v不足以保证你正确地编写代码，也没有明确程序执行的过程。v提供统一的方法对对所编写的程序进行文档化（documenting）v程序员应该花一定的时间来斟酌前提、后置条件，以便理清思路。断言（Assert)v断言是你对自己的程序状态进行假定。（类似于报警器）v断言正确，程序继续执行v断言失败，程序挂起，显示出错信息v例子：P25 Examplesv程序员如果肯定代码正确，可以删除断言v去除断言可以提高程序的运行性能
