1、1 抽象列表抽象列表 单链表单链表 双链表双链表 循环链表循环链表 向量列表向量列表2数据的存储结构数据的存储结构顺序存储顺序存储3用用一个数组变量一个数组变量可以表示可以表示一组相同性质的数据。一组相同性质的数据。数组声明的数组声明的格式格式为：为：类型标识符类型标识符 数组名数组名 或或 类型标识符类型标识符 数组名数组名如：如：int score;或者或者int score;数组的初始化数组的初始化是确定如下几项的过程：是确定如下几项的过程：元素的个数元素的个数整个数组所整个数组所占用的存储空间占用的存储空间数组中各个数组中各个元素的初始值元素的初始值（整型初值为（整型初值为0 0；浮点
2、型初值为；浮点型初值为0.00.0；布尔；布尔型初值为型初值为falsefalse；字符型初值为；字符型初值为u0000u0000；用户自定义的类型初值为；用户自定义的类型初值为nullnull）初始化数组的方法如下：初始化数组的方法如下：（1）使用）使用new操作符操作符（a a）先声明数组再初始化。如：）先声明数组再初始化。如：int score;score=new int150（b b）声明的同时进行初始化。如：）声明的同时进行初始化。如：int score=new int150;（2）给数组中所有的元素手动赋予初始值。如：）给数组中所有的元素手动赋予初始值。如：int score=65
3、,34,48,87,78,98;4 内存分配方式是静态分配还是动态分配？内存分配方式是静态分配还是动态分配？存储密度是存储密度是1吗？吗？存储密度（存储密度（Storage Density）是指元素数据本身是指元素数据本身所占的存储量和整个元素所占的存储量之比，即：所占的存储量和整个元素所占的存储量之比，即：存储密度存储密度=（元素数据本身所占的存储量）（元素数据本身所占的存储量）/（元素所占的存储总量）（元素所占的存储总量）如何访问数组的第如何访问数组的第i个元素？个元素？如何实现插入删除一个元素？如何实现插入删除一个元素？数组的容量不够的话怎么办？数组的容量不够的话怎么办？5 P35：向量
4、的底层是：向量的底层是数组数组protected Object elementData;向量的扩展虽是向量的扩展虽是自动自动进行进行的，但扩展仍需的，但扩展仍需要付出一定代价。要付出一定代价。扩展方法扩展方法复制的元素的次数复制的元素的次数增增1n(n-1)/2增增kn(n/k-1)/2扩展扩展2倍倍n-16 内存分配方式：静态分配内存分配方式：静态分配程序执行之前必须明确规定程序执行之前必须明确规定存储规模存储规模。若线性表长度。若线性表长度n变化变化较大，则存储规模难于预先确定：估计过大将造成空间浪较大，则存储规模难于预先确定：估计过大将造成空间浪费；估计太小又将使空间溢出机会增多。费；估
5、计太小又将使空间溢出机会增多。元素存取方式：随机存取元素存取方式：随机存取对表中任一元素都可在对表中任一元素都可在O（1）时间内直接获取。时间内直接获取。插入删除操作：需移动元素插入删除操作：需移动元素在顺序存储结构中进行插入和删除，平均要移动表中近一在顺序存储结构中进行插入和删除，平均要移动表中近一半的元素，尤其是当每个结点的信息量较大时，移动结点半的元素，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。的时间开销就相当可观。存储密度：为存储密度：为1 当线性表的长度变化不大，易于事先确定其大小时，为了当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序存
6、储结构。节约存储空间，宜采用顺序存储结构。7向量和数组在向量和数组在元素变动比较剧烈元素变动比较剧烈的情况不的情况不适应。适应。链表适合在元素频繁变动的情况下采用。链表适合在元素频繁变动的情况下采用。链表是一种链表是一种动态动态的数据结构，可以按需要的数据结构，可以按需要进行扩展和缩减。进行扩展和缩减。这种扩展和缩减可以在这种扩展和缩减可以在常量（常量（O（1）时）时间里间里完成。完成。8 头部插入头部插入 中间插入中间插入 尾部插入尾部插入 头部删除头部删除 删除删除 中间删除中间删除 尾部删除尾部删除链表操作：链表操作：插入插入Lifeon数据域数据域 引用域引用域每个元素都由两部分组成：
7、每个元素都由两部分组成：数据域数据域和和引用域引用域数据域数据域存放元素本身的数据；存放元素本身的数据；引用域引用域存放所指向元素的引用；存放所指向元素的引用；9链表的设计链表的设计 设计设计接口接口 设计设计抽象的链表类抽象的链表类 设计符合设计符合具体需求具体需求的链表类的链表类10public interface List extends Structure /*Determine size of list.*post returns number of elements in list *return The number of elements in list.*/public in
8、t size();/*Determine if list is empty.*post returns true iff list has no elements *return true if list has no elements.*/public boolean isEmpty();11 /*Remove all elements of list.*post empties list */public void clear();/*Add a value to the head of the list.*post value is added to beginning of list
9、*param value The value to be added to the head of the list.*/public void addFirst(Object value);/*Add a value to tail of list.*post value is added to end of list *param value The value to be added to tail of list.*/public void addLast(Object value);12/*Fetch first element of list.*pre list is not em
10、pty *post returns first value in list *return A reference to first element of list.*/public Object getFirst();/*Fetch last element of list.*pre list is not empty *post returns last value in list *return A reference to last element of list.*/public Object getLast();13/*Remove a value from first eleme
11、nt of list.*pre list is not empty *post removes first value from list *return The value actually removed.*/public Object removeFirst();/*Remove last value from list.*pre list is not empty *post removes last value from list *return The value actually removed.*/public Object removeLast();14/*Remove a
12、value from list.At most one of value *will be removed.*post removes and returns element equal to value *otherwise returns null *param value The value to be removed.*return The actual value removed.*/public Object remove(Object value);/*Add an object to tail of list.*post value is added to tail of li
13、st *param value The value to be added to tail of list.*see#addLast */public void add(Object value);15 /*Removes value from tail of list.*pre list has at least one element *post removes last value found in list *return object removed.*/public Object remove();/*Retrieves value from tail of list.*pre l
14、ist has at least one element *post returns last value found in list *return object found at end of list */public Object get();16 /*Check to see if a value is in list.*pre value is not null *post returns true iff list contains an object equal to value *param value value sought.*return True if value i
15、s within list.*/public boolean contains(Object value);/*Determine first location of a value in list.*pre value is not null *post returns(0-origin)index of value,*or-1 if value is not found *param value The value sought.*return index(0 is first element)of value,or-1 */public int indexOf(Object value)
16、;17 /*Set value stored at location i to object o,returning old value.*pre 0=i size()*post sets ith entry of list to value o;*returns old value *param i location of entry to be changed.*param o new value *return former value of ith entry of list.*/public Object set(int i,Object o);/*Insert value at l
17、ocation.*pre 0=i=size()*post adds ith entry of list to value o *param i index of this new value *param o value to be stored */public void add(int i,Object o);18 /*Determine last location of a value in list.*pre value is not null *post returns(0-origin)index of value,*or-1 if value is not found *para
18、m value value sought.*return index(0 is first element)of value,or-1 */public int lastIndexOf(Object value);/*Get value at location i.*pre 0=i size()*post returns object found at that location *param i position of value to be retrieved.*return value retrieved from location i(returns null if i invalid
19、)*/public Object get(int i);19 /*Remove and return value at location i.*pre 0=i size()*post removes and returns object found at that location *param i position of value to be retrieved.*return value retrieved from location i(returns null if i invalid)*/public Object remove(int i);/*Construct an iter
20、ator to traverse elements of list *from head to tail,in order.*post returns an iterator allowing *ordered traversal of elements in list *return Iterator that traverses list.*/public Iterator iterator();20示例：唯一程序（示例：唯一程序（Unique.java）该程序对输入的字符流进行检查，删除重复的行，打印剩余的行。字符流字符流s是否结束？是否结束？读入一行读入一行查找唯一列表查找唯一列表li
21、nes，有相同行否？有相同行否？打印，打印，把该行加入把该行加入linesNYNY程序结束程序结束21public static void main(String args)ReadStream s=new ReadStream(System.in);String current;List lines=new SinglyLinkedList();while(!s.eof()current=s.readLine();if(!lines.contains(current)System.out.println(current);lines.add(current);22思考思考 列表lines的类
22、型是SinglyLinkedList；单链单链表的存储结构是顺序的还是链式的？表的存储结构是顺序的还是链式的？程序中都用到了哪些列表的方法？想想他们程序中都用到了哪些列表的方法？想想他们应该如何实现？应该如何实现？23小型停车场的小型停车场的租用协议租用协议（类似于（类似于内存池内存池的动态分的动态分配）配）停车场共有停车场共有10个停车位，个停车位，3个小型，个小型，6个中型，个中型，1个大型：个大型：如果在如果在自由列表（自由列表（free）中能够找到一个合适的停中能够找到一个合适的停车位，那么用户就可以租用这个停车位，并在车位，那么用户就可以租用这个停车位，并在租租用列表（用列表（ren
23、ted）中保存租用人和停车位描述之中保存租用人和停车位描述之间的关联。间的关联。用户也可以退租，退租后的车位可以为别人使用。用户也可以退租，退租后的车位可以为别人使用。2400102031415161718192freenumber域，域，标示车位号标示车位号size域，标域，标示车位大小示车位大小Space对象，表示空闲对象，表示空闲的停车位号和车位大小的停车位号和车位大小25关联（关联（Assocoation.java）theKeytheValue键值对（键值对（key-value pair）的键：）的键：protected Object theKey;键值对（键值对（key-value
24、pair）的值：）的值：protected Object theValue;n两个参数的构造方法：两个参数的构造方法：Association(Object key,Object value)n一个参数的构造方法：一个参数的构造方法：Association(Object key)n看两个键值对是否相等：看两个键值对是否相等：boolean equals(Object other)n查询键值对的键：查询键值对的键：Object getValue()n查询键值对的值：查询键值对的值：Object getKey()2600张三张三61李四李四rented关联的关联的theKey域，域，标示租用人标示租
25、用人关联的关联的theValue域域，标示租用的，标示租用的车位信息，是一车位信息，是一个个Space对象对象关联类型（关联类型（Association）的对象，记录租用人和被的对象，记录租用人和被租用的车位之间的关联租用的车位之间的关联27import structure.*;class Spacepublic final static int COMPACT=0;public final static int MINIVAN=1;public final static int TRUCK =2;protected int number;protected int size;public S
26、pace(int n,int s)/post:construct parking space#n,size snumber=n;size=s;public boolean equals(Object Other)Space that=(Space)Other;return this.size=that.size;20number域，域，标示车位号标示车位号size域，标域，标示车位大小示车位大小Space对象，表示空闲对象，表示空闲的停车位号和车位大小的停车位号和车位大小28public static void main(String args)List free=new SinglyLink
27、edList();List rented=new SinglyLinkedList();for(int number=0;number 10;number+)if(number 3)free.add(new Space(number,Space.COMPACT);else if(number 9)free.add(new Space(number,Space.MINIVAN)else free.add(new Space(number,Space.TRUCK);/多次租用和退租多次租用和退租00102031415161718192freerented29ReadStream r=new Rea
28、dStream();for(r.skipWhite();!r.eof();r.skipWhite()String command=r.readString();Space location;/描述如何租用和退租描述如何租用和退租System.out.println(free.size()+slots remain available.);30if(command.equals(rent)String size=r.readString();Space request;if(size.equals(small)request=new Space(0,Space.COMPACT);else if(
29、size.equals(medium)request=new Space(0,Space.MINIVAN);else request=new Space(0,Space.TRUCK);if(free.contains(request)location=(Space)free.remove(request);String renter=r.readString();rented.add(new Association(renter,location);System.out.println();System.out.println(Space +location.number+rented.);e
30、lse System.out.println(No space available.sorry.);3100102031415161718192freerented初始状态初始状态102031415161718192free00ArentedA用用户租户租用小用小型位型位321020415161718192free00A31BrentedB用用户租户租用中用中型位型位00A31Brented92C10204151617181freeC用用户租户租用大用大型位型位3334if(command.equals(return)String renter=r.readString();Associati
31、on query=new Association(renter);if(rented.contains(query)Association contract=(Association)rented.remove(query);location=(Space)contract.getValue();free.add(location);System.out.println();System.out.println(Space +location.number+is free.);else System.out.println(No Space rented to +renter);3510204
32、15161718192free00A31BrentedB用用户户退退租租00A31Brented92C10204151617181freeC用用户户退退租租361020415161718192freerented最终状态最终状态102031415161718192free00ArentedA用用户户退退租租31003738设计好了设计好了接口接口List，我们开始设计，我们开始设计抽象列抽象列表表AbstractList。思考：思考：抽象列表抽象列表AbstractList前既然有前既然有Abstract修修饰符，为什么该类还需要饰符，为什么该类还需要构造方法构造方法？（参？（参考考P107的
33、的AbstractGenerator）39public abstract class AbstractList extends AbstractStructure implements List public AbstractList()public boolean isEmpty()return size()=0;public void addFirst(Object value)add(0,value);public void addLast(Object value)add(size(),value);40public Object getFirst()return get(0);pub
34、lic Object getLast()return get(size()-1);public Object removeFirst()return remove(0);public Object removeLast()return remove(size()-1);41public void add(Object value)addLast(value);public Object remove()return removeLast();public Object get()return getLast();public boolean contains(Object value)retu
35、rn indexOf(value)!=-1;421.引用引用2.垃圾收集器垃圾收集器431、引用、引用 一个类的实例（一个类的实例（对象对象）就像是一个）就像是一个风筝风筝；而而引用引用就像抓住风筝线的一个就像抓住风筝线的一个线拐线拐。AB44一个对象在内存中会一个对象在内存中会申请申请一块空间来保存对象的数据。一块空间来保存对象的数据。引用也是引用也是Java的一种的一种数据类型数据类型，它指示了对象在内存中的，它指示了对象在内存中的地址地址。访问对象的时候，我们访问对象的时候，我们不会直接不会直接访问对象在内存中存储的数据，而访问对象在内存中存储的数据，而是通过是通过引用引用去访问。去访问
36、。class Studentint studentNo;int classNo;long idNo;2566#s2566Student s=new Student();2570257445Student s1=new Student()String s2=s1;这里，这里，s1 和和 s2 是不同的引用，但它们的值是不同的引用，但它们的值（即他们（即他们存储的地址存储的地址）是一样的，都指向同）是一样的，都指向同一个对象。一个对象。2566#s12566257025742566#s29200#7800#46这里我描述了引用的这里我描述了引用的两个要点：两个要点：引用是一种数据类型，保存了对象在
37、内引用是一种数据类型，保存了对象在内存中的地址，这种类型即不是我们平时存中的地址，这种类型即不是我们平时所说的所说的简单数据类型简单数据类型也不是也不是类实例类实例(对象对象)；不同的引用可能指向同一个对象，换句不同的引用可能指向同一个对象，换句话说，一个对象可以有多个引用。话说，一个对象可以有多个引用。472、垃圾收集器、垃圾收集器许多程序设计语言都允许在程许多程序设计语言都允许在程序运行期间序运行期间动态动态地分配内存空地分配内存空间。不论是采用哪一种程序设间。不论是采用哪一种程序设计语言来内存分配，最后都要计语言来内存分配，最后都要返回所分配的返回所分配的内存块的起始地内存块的起始地址址
38、。当已经分配的内存空间不再需当已经分配的内存空间不再需要时，该程序或其运行环境就要时，该程序或其运行环境就应该应该回收回收该内存空间，以节省该内存空间，以节省宝贵的内存资源。宝贵的内存资源。48在在C，C+或其他程序设计语言中，无论是或其他程序设计语言中，无论是对象还是动态配置的资源或内存，都必须由对象还是动态配置的资源或内存，都必须由程序员程序员自行声明产生自行声明产生和和回收回收，否则将造成内，否则将造成内存资源的浪费甚至导致死机。存资源的浪费甚至导致死机。但手工回收内存往往是一项复杂而艰巨的工但手工回收内存往往是一项复杂而艰巨的工作。因为要预先确定占用的内存空间是否应作。因为要预先确定占
39、用的内存空间是否应该被回收是非常困难的！如果一段程序不能该被回收是非常困难的！如果一段程序不能回收内存空间，而且在程序运行时系统中又回收内存空间，而且在程序运行时系统中又没有了可以分配的内存空间时，这段程序就没有了可以分配的内存空间时，这段程序就只能崩溃。只能崩溃。通常，我们把分配出去后，却无法回收的内通常，我们把分配出去后，却无法回收的内存空间称为存空间称为“内存渗漏（内存渗漏（Memory Leaks）”。49这种潜在危险性在这种潜在危险性在Java这样以严谨、安全这样以严谨、安全著称的语言中是不允许的。但是著称的语言中是不允许的。但是Java语言语言既不能限制程序员编写程序的既不能限制程
40、序员编写程序的自由性自由性，又不，又不能把声明对象的部分能把声明对象的部分去除去除（否则就不是面向（否则就不是面向对象的程序语言了）；对象的程序语言了）；那么最好的解决办法就是从那么最好的解决办法就是从Java程序语言程序语言本身的特性入手。于是，本身的特性入手。于是，Java技术提供了技术提供了一个内存一个内存自动自动回收工具回收工具垃圾收集器垃圾收集器（GC）。该收集器该收集器跟踪跟踪每一块分配出去的内存空间，每一块分配出去的内存空间，当当Java虚拟机处于空闲时，垃圾收集器会虚拟机处于空闲时，垃圾收集器会自动检查每一块分配出去的内存空间，然后自动检查每一块分配出去的内存空间，然后自动回收
41、每一块可以回收的无用的内存块。自动回收每一块可以回收的无用的内存块。50Java中，动态内存的分配是用中，动态内存的分配是用new分配的，分配的，它返回一个指向新对象的它返回一个指向新对象的引用引用。引用引用就象一个就象一个线拐，线拐，利用利用线拐线拐我们可以抓住我们可以抓住风筝。如果一个风筝没有了风筝。如果一个风筝没有了线拐线拐，那么风筝，那么风筝就会随风飘荡，最终遗失到某个角落里成为就会随风飘荡，最终遗失到某个角落里成为“生活垃圾生活垃圾”。同理，如果一个对象没有引用指向它，那么同理，如果一个对象没有引用指向它，那么这个对象将被视为这个对象将被视为“内存垃圾内存垃圾”，也就意味，也就意味着
42、垃圾收集器可以检查到该对象占用的内存着垃圾收集器可以检查到该对象占用的内存空间并回收之。空间并回收之。问题是：垃圾收集器如何检查出哪些问题是：垃圾收集器如何检查出哪些内存是应该回收的呢？内存是应该回收的呢？518.4 实现：单链表实现：单链表（SinglyLinkedList.java)1.单链表元素单链表元素2.单链表单链表521、单链表元素、单链表元素(SinglyLinkedListElement.java)public class SinglyLinkedListElementprotected Object data;/value stored in this elementprot
43、ected SinglyLinkedListElement nextElement;/ref to nextonLife3870Data数据域数据域nextElement引用域引用域3200387053public SinglyLinkedListElement(Object v,SinglyLinkedListElement next)data=v;nextElement=next;public SinglyLinkedListElement(Object v)this(v,null);onLifeData数据域数据域nextElement引用域引用域54public SinglyLinke
44、dListElement next()return nextElement;public void setNext(SinglyLinkedListElement next)nextElement=next;public Object value()return data;public void setValue(Object value)data=value;public String toString()return;55我们访问一个类对象的成员变量时，通常的做法是设计一些我们访问一个类对象的成员变量时，通常的做法是设计一些由由public修饰的修饰的存取函数，然后用这些存取函数访问对象的
45、存取函数，然后用这些存取函数访问对象的各个成员变量；而不是用各个成员变量；而不是用“对象名对象名.成员变量名成员变量名”去访问。去访问。如单链表元素类中的：如单链表元素类中的：public SinglyLinkedListElement next()public void setNext(SinglyLinkedListElement next)public Object value()public void setValue(Object value)单链表元素是一个单链表元素是一个自引用自引用的数据结构，即对象中包含有指向的数据结构，即对象中包含有指向另一个单链表元素的引用：另一个单链表元
46、素的引用：protected SinglyLinkedListElement nextElement;onLifeData数据域数据域nextElement引用域引用域56 我们设计一个头结点，指向单链表的第一个我们设计一个头结点，指向单链表的第一个元素（元素（即第即第0索引位置元素索引位置元素）。）。LifeonMars null3单链表的计数单链表的计数域：域：count单链表的表头单链表的表头域：域：head0null57protected int count;protected SinglyLinkedListElement head;public SinglyLinkedList()
47、head=null;count=0;单链表的成员变量及构造方法单链表的成员变量及构造方法单链表的计数单链表的计数域：域：count单链表的表头单链表的表头域：域：head0null58获取单链表的长度获取单链表的长度 如何获取如何获取数组数组的长度？的长度？数组名数组名.length 如何获取如何获取向量向量的大小？的大小？protected int elementcount;public int size()return elementCount;那么如何获取那么如何获取单链表单链表的长度呢？的长度呢？protected int count;public int size()return c
48、ount;59获取单链表的长度另一种方法获取单链表的长度另一种方法l 扫描整个单链表，每扫描到一个元素，计数器扫描整个单链表，每扫描到一个元素，计数器elementCount加加1，直到单链表的尾结点。，直到单链表的尾结点。LifeonMars null3finger320038707230LifeonMars null3finger32003870723060LifeonMars null3finger320038707230LifeonMars null3finger32003870723061 public int size()int elementCount=0;SinglyLinke
49、dListElement finger=head;while(finger!=null)elementCount+;finger=finger.next();return elementCount;实现代码实现代码62单链表表头操作单链表表头操作1.表头表头插入插入一个元素一个元素2.表头表头删除删除一个元素一个元素3.获得获得表头元素的表头元素的值值631、表头插入元素、表头插入元素LifeonMars null4Yes！LifeonMars null3public void addFirst(Object value)SinglyLinkedListElement temp=new Sin
50、glyLinkedListElement(value,null);temp.setNext(head);head=temp;count+;插入元素前：插入元素前：插入元素后：插入元素后：temp64表头插入元素的另一种实现表头插入元素的另一种实现LifeonMars null4Yes！LifeonMars null3public void addFirst(Object value)head=new SinglyLinkedListElement(value,head);count+;插入元素前：插入元素前：插入元素后：插入元素后：652、删除表头元素、删除表头元素LifeonMars nul
