数据结构复习资料,java数据结构期末考试

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构复习资料,java数据结构期末考试其次章算法分析

1.算法分析是计算机科学的基础

2.增长函数表示问题（n）大小与我们希翼最优化的值之间的关系。该函数表示了该算法的时光复杂度或空间复杂度。增长函数表示与该问题大小相对应的时光或空间的使用

3.渐进复杂度：随着n的增强时增长函数的普通性质，这一特性基于该表达式的主项，即n增强时表达式中增长最快的那一项。

4.渐进复杂度称为算法的阶次，算法的阶次是忽视该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。

5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。

6.惟独可运行的语句才会增强时光复杂度。

7.O()或者大O记法：与问题大小无关、执行时光恒定的增长函数称为具有O（1）的复杂度。

增长函数阶次

t(n)=17O(1)

t(n)=3lognO(logn)

t(n)=20n-4O(n)

t(n)=12nlogn+100nO(nlogn)

t(n)=3n2+5n-2O(n2)

t(n)=8n3+3n2O(n3)

t(n)=2n+18n2+3nO(2n)

8.全部具有相同阶次的算法，从运行效率的角度来说都是等价的。

9.假如算法的运行效率低，从长远来说，使用更快的处理器也无济于事。

10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n表示的是问题的大小）

11.分析嵌套循环的复杂度时，必需将内层和外层循环都考虑进来。

12.办法调用的复杂度分析：

如：publicvoidprintsum(intcount){

intsum=0;

for(intI=1;I幂函数增长>对数函数增长

第三章集合概述——栈

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.privateT[]stack;

Stack=(T[])(newObject[DEFAULT_CAPACITY]);

因为不能实例化一个泛型对象，这里实例化了一个Object数组，然后将它转换为一个泛型数组。

32.push（）

publicvoidpush(Telement){

if(size()==stack.length)

expandCapacity();

stack[top]=element;

top++;

}

33.pop（）

publicTpop()throwsEmptyCollectionException

{

if(isEmpty())

thrownewEmptyCollectionException("Stack");

top--;

Tresult=stack[top];

stack[top]=null;

returnresult;

}

34.peek（）

publicTpeek()throwsEmptyCollectionException{

if(isEmpty())

thrownewEmptyCollectionException("Stack");

returnstack[top-1];}

35.privatevoidexpandCapacity(){

T[]larger=(T[])(newObject[stack.length*2]);

for(intindex=0;indextemp=newLinearNode(element);

temp.setNext(top);

top=temp;

count++;

}

b)Pop：

publicTpop()throwsEmptyCollectionException{

if(isEmpty())

thrownewEmptyCollectionException("stack");

Tresult=top.getElement();

top=top.getNext();

count--;

returnresult;

}

第五章队列

1.队列是一种线性集合，其元素从一端加入，另一端删除。因此，队列元素是按先进先出（FIFO）方式处理的。从队列中删除元素的次序，与往队列中放置元素的次序是一样的。元素都是从队列末端（rear）进入，从队列前端（front）退出。

2.用链表实现栈：

a)队列和栈的主要区分在于，队列中我们必需要操作链表的两端。因此需要两个引用

分离指向链表的首、末元素。

b)对于单向链表，可挑选从末端入列，先前端出列。

c)双向链表可以解决需要遍历链表的问题，因此在双向链表实现中，无所谓在哪端入

列和出列。

d)对于一个空队列，head和tail引用都为null，count为0。队列中惟独一个元素时，

head和tail引用都会指向这个对象。

e)Enqueue：将新元素放到链表末端

publicvoidenqueue(Telement){

LinearNodenode=newLinearNode(element);

if(isEmpty())

head=node;

else

tail.setNext(node);

tail=node;

count++;

}

f)Dequeue

publicTdequeue()throwsEmptyCollectionException{if(isEmpty())

thrownewEmptyCollectionException("queue");Tresult=head.getElement();head=head.getNext();count--;

if(isEmpty())tail=null;

returnresult;}

3.用数组实现队列：

a)因为队列操作会修改集合的两端，因此将一端固定于索引0出要求移动元素。b)非环形数组实现的元素位移，将产生O（n）的复杂度。

c)把数组看作是环形的，可以除去在队列的数组实现中元素的移位需要。d)环形数组：假如数组的最后一个索引后面跟的是第一个索引，那么该数组就可用作

环形数组。

e)用两个整数值表示队列的前端和末端。front的值表示的是队列的首元素存储的位

置，rear的值表示的是数组下一个可用单元（不是最后一个元素储存的位置），此时rear的值不在表示队列元素的数目了。f)Enqueue：

publicvoidenqueue(Telement){if(size()==queue.length)expendCapacity();queue[rear]=element;

rear=(rear+1)%queue.length;count++;}

注重：环形增强

rear=(rear+1)%queue.length;

e)Dequeue:

publicTdequeue()throwsEmptyCollectionException{if(isEmpty())

thrownewEmptyCollectionException("queue");Tresult=queue[front];queue[rear]=null;

front=(front+1)%queue.length;count--;

returnresult;}

4.队列是一种可存储重复编码密钥的方便集合。

正常增强

适当的时候，绕回到0

5.队列的链表实现中，head和tail引用相等的状况：

a)队列为空：head和tail都为null

b)队列中惟独一个元素

6.队列的环形数组实现中，front和rear引用相等的状况：

a)队列为空

b)队列为满

7.dequeue操作复杂度为O(n)的非环形数组实现的时光复杂度最差

8.环形数组和非环形数组都会因未填充元素而铺张空间。链表实现中的每个存储元素都会占用更多的空间。

第六章列表

1.链表和列表集合之间的差别：

a)链表是一种实现策略，使用引用来在对象之间创建链接，如前面用链表来实现了栈

和队列集合。

b)列表集合是一种概念性表示法，其思想是使事物以线性列表的方式举行组织。就像

栈和队列一样，列表也可以使用链表或数组来实现。

2.列表集合没有内在的容量大小，它可以随着需要增大。

3.栈和队列都是线性结构，可以像列表那样举行思量，但元素只能在末端添加和删除。列表集合更普通化，可以在列表的中间和末端添加和删除元素。Inotherwords,栈和队列都属于列表，列表可随意操作。

4.列表可分为：

a)有序列表：其元素根据元素的某种内在特性举行排序；

b)无序列表：其元素间不具有内在挨次，元素根据它们在列表中的位置举行排序。

c)索引列表：其元素可以用数字索引来引用。

5.有序列表是基于列表中元素的某种内在特征的。列表基于某个关键值排序。对于任何已添加到有序列表中的元素，只要给定了元素的关键值，同时已经定义了元素的全部关键值，那么它在列表中就会有一个固定的位置。

6.无序列表中各元素的位置并不基于元素的任何内在特性。但列表中的元素是根据特别挨次放置着，只不过这种挨次与元素本身无关。列表的使用者会打算元素的挨次。无序列表的新元素可以加到列表的前端、后端，或者插到某个特定元素之后。

7.索引列表与无序列表类似，各元素间也不存在能够打算它们在列表中的挨次的内在关系。列表的使用者打算了元素的挨次。除此之外，索引列表的每个元素都能够从一个数字索引值得到引用，该索引值从列表头开头从0延续增强直到列表末端。索引列表的新元素可以加到列表的任一位置，包括列表的前端和后端。每当列表发生转变，索引值就相应调节以保持挨次和延续性。索引列表为它的元素维护一段延续的数字索引值。

8.索引列表和数组的根本区分在于：索引列表的索引值总是延续的。假如删除了一个元素，其他元素的位置会像“坍塌”了一样消退产生的空隙。当插入一个元素时，其他元素的索引将举行位移以腾出位置。

9.列表有可能既是有序列表，又是索引列表，但这种设计没有什么意义。

10.Java集合API中的列表：

a)Java集合API提供的列表类只要是支持索引列表。在一定程度上，这些类与无序

列表是重叠的。

i.注重：javaAPI并没有任何类能直接实现以上描述的有序列表。

b)List接口：

add(Eelement)往列表的末端添加一个元素

add（intindex,Eelement）在指定索引处插入一个元素

get（intindex）返回指定索引处的元素

remove(intindex)删除指定索引处的元素

remove（EObject）删除制定对象的第一个浮现

set（intindex，Eelement）替代指定索引处的元素

size（）返回列表中的元素数目

11.数组实现列表：使用环形数组办法，但当从列表中间插入或者删除元素时，仍需移动元素。

a)Remove操作：

publicTremove(Telement)throwsElementNotFoundException{Tresult;

intindex=find(element);

if(index==NOT_FOUND)

thrownewElementNotFoundException("ArrayList");

result=list[index];

rear--;

for(intscan=index;scantemp=(Comparable)element;

intscan=0;

while(scanscan;scan2--)

list[scan2]=list[scan2-1];

list[scan]=element;

rear++;

}

注重：

复杂度为O（n）。

惟独Comparable对象才干存储在有序列表中。

e）Comparable接口定义了compareTo办法，当执行对象为小于、等于或者大于传入参数时，该办法将分离返回一个负整数、0或者一个正整数。

无序列表和索引列表不要求它们所存储的元素是Comparable的。

f）无序列表的操作

publicvoidaddAfter(Telement,Ttarget){

if(size()==list.length)

expandCapacity();

intscan=0;

while(scanscan+1;i--)

list[i]=list[i-1];

list[scan+1]=element;

rear++;

}

publicvoidaddToFront(Telement){

if(size()==list.length)

expandCapacity();

for(inti=rear;iprevious=null;

LinearNodecurrent=head;

while(current!=null

else

{previous=current;

current=current.getNext();

}

if(!found)

thrownewElementNotFoundException("List");

if(size()==1)

head=tail=null;

elseif(current.equals(head))

head=current.getNext();

elseif(current.equals(tail))

{tail=previous;

tail.setNext(null);

}

else

previous.setNext(current.getNext());

count--;

returncurrent.getElement();

}

b)有序列表的add操作（仅供参考）

publicclassLinkedOrderedList42>extendsLinkedList42implements

OrderedListADT{

@Override

publicvoidadd(Telement){

LinearNodenode=newLinearNode(element);

LinearNodetemp=head;

LinearNodetemp0=temp;

if(isEmpty()){

head=tail=node;

count++;

}

else{

if(size()==1){

if(head.getElement().compareTo(element)>0){

node.setNext(head);

head=node;

count++;

}else{

head.setNext(node);

tail=node;

count++;

}

}elseif(head.getElement().compareTo(element)>=0){node.setNext(head);

head=node;

count++;

}

else{

while(temp!=tail&&

temp.getElement().compareTo(element)extendsLinkedList42implementsUnorderedListADT{

@Override

publicvoidaddToFront(Telement){

LinearNodeNew=newLinearNode(element);

if(count==0){

tail=New;

head=New;

count++;

}

else{

New.setNext(head);

head=New;

count++;

}

}

@Override

publicvoidaddToRear(Telement){

LinearNodeNew=newLinearNode(element);

if(count==0){

tail=New;

}else{

tail.setNext(New);

tail=New;

}

count++;

}

@Override

publicvoidaddAfter(Telement,Ttarget){

LinearNodeNew=newLinearNode(element);

LinearNodecurrent=head;

if(contains(targ