数据结构复习资料-java数据结构期末考试.doc

第二章 算法分析
1. 算法分析是计算机科学的基础
2. 增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用
3. 渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n增加时表达式中增长最快的那一项。
4. 渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。
5. 渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。
6. 只有可运行的语句才会增加时间复杂度。
7. O() 或者 大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。
增长函数
阶次
t(n)=17
O(1)
t(n)=3log n
O(log n)
t(n)=20n-4
O(n)
t(n)=12n log n + 100n
O(n log n)
t(n)=3 + 5n - 2
O()
t(n)=8 + 3
O()
t(n)=+ 18 +3n
O()
8. 所有具有相同阶次的算法，从运行效率的角度来说都是等价的。
9. 如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。
10. 要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n表示的是问题的大小）
11. 分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。
12. 方法调用的复杂度分析：
如：public void printsum(int count){
int sum = 0 ;
for (int I = 1 ; I < count ; I++)
sum += I ;
System.out.println(sun);
}
printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复杂度为O（）。
13指数函数增长 > 幂函数增长 > 对数函数增长
第三章 集合概述——栈
1. 集合是一种聚集、组织了其他对象的对象。它定义了一种特定的方式，可以访问、管理所包含的对象（称为该集合的元素）。集合的使用者——通常是软件系统中的另一个类或对象——只能通过这些预定的方式与该集合进行交互。
2. 集合可分为线性集合和非线性集合。线性集合是一种元素按直线方式组织的集合。非线性集合是一种元素按某种非直线方式组织的集合，例如按层次组织或按网状组织。从这种意义上来说，非线性集合也许根本就没有任何组织形式。
3. 集合中的元素通常是按照它们添加到集合的顺序，或者是按元素之间的某种内在关系来组织的。
4. 抽象能隐藏某些细节。
5. 集合是一种隐藏了实现细节的抽象。
6. 对象是用于创建集合一种完美机制，因为只要设计正确，对象的内部工作对系统其他部分而言是被封装的。几乎在所有情况下，在类中定义的实例变量的可见性都应声明为私有的（private）。因此，只有该类的方法才可以访问和修改这些变量。用户与对象的唯一交互只能通过其公用方法。公用方法表示了对象所能提供的服务。
7. 数据类型是一组值及作用于这些数值上的各种操作。
8. 抽象数据类型（ADT）是一种在程序设计语言中尚未定义其值和操作的数据类型。ADT的抽象性体现在，ADT必须对其实现细节进行定义，且对这些用户是不可见的。因此，集合是一种抽象数据类型。
9. 数据结构是一种用于实现集合的基本编程结构。
10. Java集合API（应用程序编程接口）是一个类集，表示了一些特定类型的集合，这些类的实现方式各不相同。
11. 栈的元素是按照后进先出（LIFO）的方式进行处理的，最后进入栈中的元素最先被移出。栈是一种线性集合，元素的添加和删除都在同一端进行。在科学计算中，栈的基本使用就是用于颠倒顺序（如一个取消操作）。
12. 通常垂直的绘制栈，栈的末端称为栈的顶部，元素的添加和删除在顶部进行。
13. 如果pop或者peek可作用于空栈，那么栈的任何实现都要抛出一个异常。集合的作用不是去确定如何处理这个异常，而是把它报告给使用该栈的应用程序。在栈中没有满栈的概念，应由栈来管理它自己的存储空间。
14. 栈的toString（）操作可以在不修改栈的情况下遍历和现实栈的内容，对调试非常有用。
15. 类型兼容性是指把一个对象赋给引用的特定赋值是否合法。
16. 继承就是通过某个现有类派生出一个新类的过程。多态：使得一个引用可以多次指向相关但不同的对象类型，且其中调用的方法是在运行时与代码。多态引用是一个引用变量，它可以在不同地点引用不同类型的对象。继承可用于创建一个类层次，其中，一个引用变量可用于只想与之相关的任意对象。类层次：通过继承创建的类之间的关系，某个类的子类可以成为其他类的父类
17. 一个Object引用可用于引用任意对象，因为所有类最终都是从Object类派生而来的。
18. 泛型，用泛型定义类：使这个类能存储、操作和管理在实例化之前没有指定是何种类型的对象。
19. 泛型不能被实例化。它只是一个占位符，允许我们去定义管理特定类型的对象的类，且只有当该类被实例化时，才创建该类的对象。
20. 计算后缀表达式：从左到右扫描，把每个操作符应用到其之前的两个紧邻操作数，并用该计算结果代替该操作符。
21. 栈是用于计算后缀表达式的理想数据结构。
22. 用栈计算后缀表达式时，操作数是作为一个Integer对象而不是作为一个int基本数值被压入栈中的，这是因为栈被设计为存储对象的。注意：第一个弹出的操作数是表达式的第二个操作数，第二个弹出的操作数是表达式的第一个操作数。
23. Javadoc注释以 /** 开始，以 */ 结束。Javadoc标签用于标识特定类型的信息。@auther标签用于标识编写代码的程序员。@version标签用于制定代码的版本号。@return标签用于表明该方法的返回值。@param标签用于标识传递给该方法的每个参数。
24. 异常就是一个对象，它被定义了一种非正常或错误的情况。异常由程序或运行时环境抛出，可以按预期的被捕获或被正确处理。错误与一场异常类似，只不过错误往往表示一种无法恢复的情况，且不必去捕获它。
25. 接口的命名：用集合名+ADT来为集合接口命名。
26. 取消操作通常是使用一种名为drop-out的栈来实现。它与栈唯一的不同是，它对存储元素的数量有限制，一旦达到限制，如果有新元素要压入，那么栈底的元素将从栈中被丢弃。
27. 数组一旦创建好，其容量是不能改变的。
28. 处于运行效率的考虑，给予数组的栈实现总是使栈底位于数组的索引0处。
29. ArrayStack类有两个构造函数，一个使用的是默认容量，一个使用的是制定容量。
30. 构造函数与成员方法的区别：
a) 构造函数是初始化一个类的对象时调用，无返回值。名字与类名相同
b) 成员函数由类对象主动调用，使用点操作符（“.”），又返回值。
31. private T[] stack;
Stack = (T[]) ( new Object[DEFAULT_CAPACITY]);
由于不能实例化一个泛型对象，这里实例化了一个Object数组，然后将它转换为一个泛型数组。
32. push（）
public void push(T element) {
if(size()==stack.length)
expandCapacity();
stack[top]= element;
top++;
}
33. pop（）
public T pop() throws EmptyCollectionException
{
if (isEmpty())
throw new EmptyCollectionException("Stack");
top--;
T result=stack[top];
stack[top]=null;
return result;
}
34. peek（）
public T peek()throws EmptyCollectionException {
if(isEmpty())
throw new EmptyCollectionException("Stack");
return stack[top-1];}
35.private void expandCapacity(){
T[]larger = (T[])(new Object[stack.length*2]);
for (int index=0; index<stack.length;index++)
larger[index]=stack[index];
stack = larger;
}

第四章 链式结构——栈
1. 对象引用变量可以用来创建链式结构。链式结构是一种数据结构，它使用对象引用变量来创建对象之间链接。链式结构是基于数组的集合实现的主要替代方案。
2. 对象引用变量存放的是对象的地址，表示该对象在内存中的存储位置。我们通常并不是显示地址，而是把引用变量描绘成一种“指向”对象的名字，这种引用变量又称为指针。
3. 链表由一些对象构成，是一种链式结构，其中的一个对象可以指向另一个对象，从而在链表中创建一个对象的线性次序。链表中存储的对象通常泛称为该链表的结点。
4. 需要一个单独的引用变量来表示链表的首结点。链表终止于其next引用为空的结点。
5. 链表只是链式结构的一种。如果建立的类含有多个指向对象的引用，就可以创建更复杂的链式结构。链接的管理方式表明了这种链式结构的特定组织形式。
6. 链表会按需动态增长，因此在本质上，它没有容量限制（在不考虑计算机本身的内存限制下）。
7. 链表的大小可以按需伸缩以容纳要存储的元素数量，因此链表被认定为是一种动态结构。在java语言中，所有动态创建的对象都来自于一个名为系统堆或自由存储的内存区。
8. 对于链表来说，访问链表的元素的唯一方式是，从第一个元素开始，顺着该链表往下进行。
9. 结点可以被插入到链表的任意位置。在链表前端架结点时，需重新设置指向整个链表的引用：
a) 新添加结点的next引用被设置为指向链表的当前首结点；
b) 指向链表前端的引用重新设置为指向这个新结点。
如果颠倒顺序，即先重新设置front引用，那么就失去了那个唯一指向现有链表的引用，于是再也检索不到该链表了。
10. 改变引用顺序是维护链表的关键。
11. 链表的任一结点都可被删除。要删除链表的首结点，需要重置指向链表前端的引用，使其指向链表当前的次。如果其他地方需要这个被删除的结点，那么在重制front引用之前，必须创建一个指向被删除结点的单独引用。
12. 链表的一个关键特征：必须把链表结构的细节内容与链表所储存的元素区分开来
13. 存储在集合中的对象不应该含有基本数据结构的任何实现细节。
14. 节点类含有两个引用：一个引用指向链表的下一结点，另一个引用指向将存储到链表中的那个元素。这时，链表中所存储的实际元素是使用结点对象中单独引用来访问的。
15. 双向链表中，需维护两个引用：一个指向链表的首结点，一个指向链表的末结点。链表中的每个结点都存有两个引用：一个指向下一元素，一个指向上一元素。
16. 哨兵结点或哑结点：位于链表前端或末端的结点，起标记符作用，不表示链表中的某个元素。如果要在双向链表中使用哑结点，那么就得在链表的两端都放置哑结点。
17. 递归使用了程序栈的概念，程序栈又称运行时栈，用于跟踪被调用的方法。每调用一个方法时，就会创建一个表示该调用的调用记录，并压入到程序栈中。因此，栈中的元素表示的是在一个正在运行程序中，到达某个位置时所调用的方法系列。
18. 程序运行出现异常时，可检查调用跟踪栈，来发现问题出自于哪个方法。
19. 可以使用栈来模拟递归处理，以便跟踪恰当的数据。
20. 用链表实现栈：
a) Push：
public void push(T element){
LinearNode<T> temp = new LinearNode<T>(element);
temp.setNext(top);
top = temp;
count++;
}
b) Pop：
public T pop() throws EmptyCollectionException {
if(isEmpty())
throw new EmptyCollectionException("stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}

第五章 队列
1. 队列是一种线性集合，其元素从一端加入，另一端删除。因此，队列元素是按先进先出（FIFO）方式处理的。从队列中删除元素的次序，与往队列中放置元素的次序是一样的。元素都是从队列末端（rear）进入，从队列前端（front）退出。
2. 用链表实现栈：
a) 队列和栈的主要区别在于，队列中我们必须要操作链表的两端。因此需要两个引用分别指向链表的首、末元素。
b) 对于单向链表，可选择从末端入列，从前端出列。
c) 双向链表可以解决需要遍历链表的问题，因此在双向链表实现中，无所谓在哪端入列和出列。
d) 对于一个空队列，head和tail引用都为null，count为0。队列中只有一个元素时，head和tail引用都会指向这个对象。
e) Enqueue：将新元素放到链表末端
public void enqueue(T element) {
LinearNode<T> node = new LinearNode<T>(element);
if(isEmpty())
head = node;
else
tail.setNext(node);
tail = node;
count++;
}
f)Dequeue
public T dequeue() throws EmptyCollectionException {
if(isEmpty())
throw new EmptyCollectionException("queue");
T result = head.getElement();
head = head.getNext();
count--;
if(isEmpty())
tail = null;
return result;
}

3. 用数组实现队列：
a) 由于队列操作会修改集合的两端，因此将一端固定于索引0出要求移动元素。
b) 非环形数组实现的元素位移，将产生O（n）的复杂度。
c) 把数组看作是环形的，可以除去在队列的数组实现中元素的移位需要。
d) 环形数组：如果数组的最后一个索引后面跟的是第一个索引，那么该数组就可用作环形数组。
e) 用两个整数值表示队列的前端和末端。front的值表示的是队列的首元素存储的位置，rear的值表示的是数组下一个可用单元（不是最后一个元素储存的位置），此时rear的值不在表示队列元素的数目了。
f) Enqueue：
public void enqueue(T element) {
if(size() == queue.length)
expendCapacity();
queue[rear] = element;
rear = (rear + 1) % queue.length;
count++;
适当的时候，绕回到0
正常增加
}
注意：环形增加

rear = (rear + 1) % queue.length;
e) Dequeue:
public T dequeue() throws EmptyCollectionException {
if(isEmpty())
throw new EmptyCollectionException("queue");
T result = queue[front];
queue[rear] = null;
front = (front + 1)%queue.length;
count--;
return result;
}
4. 队列是一种可存储重复编码密钥的便利集合。
5. 队列的链表实现中，head和tail引用相等的情况：
a) 队列为空：head和tail都为null
b) 队列中只有一个元素
6. 队列的环形数组实现中，front和rear引用相等的情况：
a) 队列为空
b) 队列为满
7. dequeue操作复杂度为O(n)的非环形数组实现的时间复杂度最差
8. 环形数组和非环形数组都会因未填充元素而浪费空间。链表实现中的每个存储元素都会占用更多的空间。

第六章 列表
1. 链表和列表集合之间的差别：
a) 链表是一种实现策略，使用引用来在对象之间创建链接，如前面用链表来实现了栈和队列集合。
b) 列表集合是一种概念性表示法，其思想是使事物以线性列表的方式进行组织。就像栈和队列一样，列表也可以使用链表或数组来实现。
2. 列表集合没有内在的容量大小，它可以随着需要增大。
3. 栈和队列都是线性结构，可以像列表那样进行思考，但元素只能在末端添加和删除。列表集合更一般化，可以在列表的中间和末端添加和删除元素。In other words,栈和队列都属于列表，列表可任意操作。
4. 列表可分为：
a) 有序列表：其元素按照元素的某种内在特性进行排序；
b) 无序列表：其元素间不具有内在顺序，元素按照它们在列表中的位置进行排序。
c) 索引列表：其元素可以用数字索引来引用。
5. 有序列表是基于列表中元素的某种内在特征的。列表基于某个关键值排序。对于任何已添加到有序列表中的元素，只要给定了元素的关键值，同时已经定义了元素的所有关键值，那么它在列表中就会有一个固定的位置。
6. 无序列表中各元素的位置并不基于元素的任何内在特性。但列表中的元素是按照特殊顺序放置着，只不过这种顺序与元素本身无关。列表的使用者会决定元素的顺序。无序列表的新元素可以加到列表的前端、后端，或者插到某个特定元素之后。
7. 索引列表与无序列表类似，各元素间也不存在能够决定它们在列表中的顺序的内在关系。列表的使用者决定了元素的顺序。除此之外，索引列表的每个元素都能够从一个数字索引值得到引用，该索引值从列表头开始从0连续增加直到列表末端。索引列表的新元素可以加到列表的任一位置，包括列表的前端和后端。每当列表发生改变，索引值就相应调整以保持顺序和连续性。索引列表为它的元素维护一段连续的数字索引值。
8. 索引列表和数组的根本区别在于：索引列表的索引值总是连续的。如果删除了一个元素，其他元素的位置会像“坍塌”了一样消除产生的空隙。当插入一个元素时，其他元素的索引将进行位移以腾出位置。
9. 列表有可能既是有序列表，又是索引列表，但这种设计没有什么意义。
10. Java集合API中的列表：
a) Java集合API提供的列表类只要是支持索引列表。在一定程度上，这些类与无序列表是重叠的。
i. 注意：java API并没有任何类能直接实现以上描述的有序列表。
b) List接口：
add(E element)
往列表的 末端 添加一个元素
add（int index,E element）
在指定索引处插入一个元素
get（int index）
返回指定索引处的元素
remove(int index)
删除指定索引处的元素
remove（E Object）
删除制定对象的第一个出现
set（int index，E element）
替代指定索引处的元素
size（）
返回列表中的元素数目

11. 数组实现列表：使用环形数组方法，但当从列表中间插入或者删除元素时，仍需移动元素。
a) Remove操作：
public T remove(T element) throws ElementNotFoundException{
T result;
int index = find(element);
if(index == NOT_FOUND)
throw new ElementNotFoundException("ArrayList");
result = list[index];
rear--;
for(int scan=index;scan<rear; scan++)
list[scan]=list[scan+1];
list[rear]=null;
return result;
}
注意：
程序中的for循环，当循环结束后，scan等于rear。因为当scan==rear-1时，最后运行一次list[scan]=list[scan+1],然后scan++，不满足scan<rear,退出循环。
复杂度为O（n）。
b) find方法：
private int find(T target){
int scan = 0;
int result = NOT_FOUND;
if(!isEmpty())
while (result == NOT_FOUND && scan < rear) {
if(target.equals(list[scan]))
result = scan;
else
scan++;
}
return result;
}
注意：find方法依靠equals方法来判断目标元素是否已找到。
c) contains操作
public boolean contains(T target){
return (find(target)!=NOT_FOUND);
}
如果没有找到目标元素，contains方法将返回false。如果找到了，返回true。由于该方法执行的是列表的线性查找，因此最坏的情况是所查找的元素不在列表中。在这种情况下需要n个比较操作。因此该方法平均需要n/2次比较操作，因而其复杂度为O(n)。
d)有序列表的add操作：
public void add(T element) {
if(size()==list.length)
expandCapacity();
parable<T> temp =(parable<T>)element;
int scan =0;
while(scan<rear && temp.pareTo(list[scan])>0)
scan++;
for(int scan2=rear; scan2>scan;scan2--)
list[scan2]=list[scan2-1];
list[scan]=element;
rear++;

}
注意：
复杂度为O（n）。
只有parable对象才能存储在有序列表中。
e） parable接口定义了pareTo方法，当执行对象为小于、等于或者大于传入参数时，该方法将分别返回一个负整数、0或者一个正整数。
无序列表和索引列表不要求它们所存储的元素是parable的。
f）无序列表的操作
public void addAfter(T element,T target) {
if(size()==list.length)
expandCapacity();
int scan=0;
while(scan<rear&&!(target.equals(list[scan])))
scan++;
if(scan==rear)
throw new NoSuchElementException();
for(int i=rear;i>scan+1;i--)
list[i]=list[i-1];
list[scan+1]=element;
rear++;

}
public void addToFront(T element) {
if(size()==list.length)
expandCapacity();

for(int i=rear;i<0;i--)
list[i]=list[i-1];
list[0]=element;
rear++;
}
public void addToRear(T element) {
if(size()==list.length)
expandCapacity();

list[rear]=element;
rear++;

}
注意：addToFront操作的复杂度为O（n），addToRear的为O（1）
addAfter的为O（n）。
12. 用链表实现列表
a) Remove操作：
4种情况：
要删除的元素是唯一元素；
是首元素；
是末元素；
处于列表中间的元素。
最坏的情况下，仍需进行n次比较，以确定目标元素不在列表中。因此remove操作的复杂度是O（n）。
public T remove(T targetElement) throws ElementNotFoundException, EmptyCollectionException {
if (isEmpty())
throw new EmptyCollectionException("List");
boolean found = false;
LinearNode<T> previous = null;
LinearNode<T> current = head;
while(current !=null &&!found)
if(targetElement.equals(current.getElement()))
found = true;
else
{ previous = current;
current = current.getNext();
}
if(!found)
throw new ElementNotFoundException("List");
if(size()==1)
head=tail=null;
else if(current.equals(head))
head=current.getNext();
else if(current.equals(tail))
{ tail = previous;
tail.setNext(null);
}
else
previous.setNext(current.getNext());
count--;
return current.getElement();
}
b)有序列表的add操作（仅供参考）
public class LinkedOrderedList42<T extends parable<? super T>> extends LinkedList42<T> implements OrderedListADT<T>{

@Override
public void add(T element) {
LinearNode<T> node = new LinearNode<T>(element);
LinearNode<T> temp = head;
LinearNode<T> temp0 = temp;
if(isEmpty()){
head = tail = node;
count++;
}
else{
if(size()==1){
if(head.getElement().pareTo(element)>0){
node.setNext(head);
head = node;
count++;
}else{
head.setNext(node);
tail = node;
count ++;
}
}else if(head.getElement().pareTo(element)>=0){
node.setNext(head);
head = node;
count++;
}
else{
while(temp !=tail && temp.getElement().pareTo(element)<0){
temp0 = temp;
temp = temp.getNext();
}
if(temp == tail){
if(temp.getElement().pareTo(element)<0){
temp.setNext(node);
tail = node;
count++;
}else{
node.setNext(temp);
temp0.setNext(node);
count++;
}
}else{
node.setNext(temp);
temp0.setNext(node);
count++;
}
}
}
}
}
c)无序列表的操作
public class LinkedUnorderedList42<T> extends LinkedList42<T> implements UnorderedListADT<T>{

@Override
public void addToFront(T element) {
LinearNode<T> New = new LinearNode<T>(element);
if(count == 0){
tail = New;
head = New;
count ++;
}
else{
New.setNext(head);
head = New;
count ++;
}
}

@Override
public void addToRear(T element) {
LinearNode<T> New = new LinearNode<T>(element);
if(count == 0){
tail = New;
}else{
tail.setNext(New);
tail = New;
}
count ++;
}

@Override
public void addAfter(T element, T target) {
LinearNode<T> New = new LinearNode<T>(element);
LinearNode<T> current=head;
if(contains(target)){
while(!target.equals(current.getElement())){
current = current.getNext();
}
New.setNext(current.getNext());
current.setNext(New);
current = New;
if(New.getNext().equals(null))
tail = New;
count ++;
}else
return;
}

}
13. 许多共有的操作可以定义给所有的列表类型。列表之间的区别在于如何添加元素。
14. 迭代器是一个对象，它提供了在一个集合上进行迭代操作的手段。
15. 接口也可以用来派生其他接口。子接口包含父接口的所有抽象方法。
16. 接口名可以用来声明一个对象引用变量。一个接口引用可以用来引用实现了该接口的任意类的任意对象。
17. 接口允许我们创建多态引用，其中被调用的方法是基于被引用的特定对象的。
18. Josephus问题（当列表中的事件不是按顺序取出而是按每隔i个元素提取，直到一个不剩时，如何找到这些事件的顺序）是一个典型的适用于索引列表来求解的计算问题。
19. 访问索引列表的基本方法
a) 通过访问列表的特定索引位置
b) 通过访问列表的末端
c) 通过值来访问列表中的对象
第七章 迭代器
1. 迭代器是一个对象，允许用户每次获得和使用集合中的一个元素。它与某个集合一同使用，但它是一个单独的对象。迭代器是有助于实现某个集合的一种机制。
2. Iterator接口的方法
a) boolean hasNext（）：如果迭代器中还有更多元素，返回true
b) E next（）：返回迭代器的下一个元素
c) void remove（）:从基本集合中返回最后删除的元素。
3. toString的迭代器实现（仅供参考）：
String result = “”;
while(I.hasNext())
result += I.next() + “→”;
result += “null”;
4. 数组实现迭代器：
5. 链表实现迭代器：
第八章 递归
1. 概念
2. 两个基本前提

第九章 怕uxuyuchazhao