数据结构复习资料java数据结构期末考试Word文件下载.docx
- 文档编号:4515306
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:24
- 大小:33.57KB
数据结构复习资料java数据结构期末考试Word文件下载.docx
《数据结构复习资料java数据结构期末考试Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构复习资料java数据结构期末考试Word文件下载.docx(24页珍藏版)》请在冰点文库上搜索。
12.方法调用的复杂度分析:
如:
publicvoidprintsum(intcount){
intsum=0;
for(intI=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.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("
returnstack[top-1];
35.privatevoidexpandCapacity(){
T[]larger=(T[])(newObject[stack.length*2]);
for(intindex=0;
index<
stack.length;
index++)
larger[index]=stack[index];
stack=larger;
第4章链式结构——栈
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:
publicvoidpush(Telement){
LinearNode<
T>
temp=newLinearNode<
(element);
temp.setNext(top);
top=temp;
count++;
b)Pop:
publicTpop()throwsEmptyCollectionException{
if(isEmpty())
stack"
Tresult=top.getElement();
top=top.getNext();
count--;
returnresult;
第5章队列
1.队列是一种线性集合,其元素从一端加入,另一端删除。
因此,队列元素是按先进先出(FIFO)方式处理的。
从队列中删除元素的次序,与往队列中放置元素的次序是一样的。
元素都是从队列末端(rear)进入,从队列前端(front)退出。
2.用链表实现栈:
a)队列和栈的主要区别在于,队列中我们必须要操作链表的两端。
因此需要两个引用分别指向链表的首、末元素。
b)对于单向链表,可选择从末端入列,从前端出列。
c)双向链表可以解决需要遍历链表的问题,因此在双向链表实现中,无所谓在哪端入列和出列。
d)对于一个空队列,head和tail引用都为null,count为0。
队列中只有一个元素时,head和tail引用都会指向这个对象。
e)Enqueue:
将新元素放到链表末端
publicvoidenqueue(Telement){
LinearNode<
node=newLinearNode<
head=node;
else
tail.setNext(node);
tail=node;
count++;
}
f)Dequeue
publicTdequeue()throwsEmptyCollectionException{
if(isEmpty())
thrownewEmptyCollectionException("
queue"
Tresult=head.getElement();
head=head.getNext();
count--;
tail=null;
returnresult;
3.用数组实现队列:
a)由于队列操作会修改集合的两端,因此将一端固定于索引0出要求移动元素。
b)非环形数组实现的元素位移,将产生O(n)的复杂度。
c)把数组看作是环形的,可以除去在队列的数组实现中元素的移位需要。
d)环形数组:
如果数组的最后一个索引后面跟的是第一个索引,那么该数组就可用作环形数组。
e)用两个整数值表示队列的前端和末端。
front的值表示的是队列的首元素存储的位置,rear的值表示的是数组下一个可用单元(不是最后一个元素储存的位置),此时rear的值不在表示队列元素的数目了。
f)Enqueue:
if(size()==queue.length)
expendCapacity();
queue[rear]=element;
rear=(rear+1)%queue.length;
环形增加
rear=(rear+1)%queue.length;
e)Dequeue:
Tresult=queue[front];
queue[rear]=null;
front=(front+1)%queue.length;
count--;
4.队列是一种可存储重复编码密钥的便利集合。
5.
队列的链表实现中,head和tail引用相等的情况:
a)队列为空:
head和tail都为null
b)队列中只有一个元素
6.队列的环形数组实现中,front和rear引用相等的情况:
a)队列为空
b)队列为满
7.dequeue操作复杂度为O(n)的非环形数组实现的时间复杂度最差
8.环形数组和非环形数组都会因未填充元素而浪费空间。
链表实现中的每个存储元素都会占用更多的空间。
第6章列表
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;
scan<
rear;
scan++)
list[scan]=list[scan+1];
list[rear]=null;
程序中的for循环,当循环结束后,scan等于rear。
因为当scan==rear-1时,最后运行一次list[scan]=list[scan+1],然后scan++,不满足scan<
rear,退出循环。
复杂度为O(n)。
b)find方法:
privateintfind(Ttarget){
intscan=0;
intresult=NOT_FOUND;
if(!
isEmpty())
while(result==NOT_FOUND&
&
scan<
rear){
if(target.equals(list[scan]))
result=scan;
else
scan++;
}
find方法依靠equals方法来判断目标元素是否已找到。
c)contains操作
publicbooleancontains(Ttarget){
return(find(target)!
=NOT_FOUND);
如果没有找到目标元素,contains方法将返回false。
如果找到了,返回true。
由于该方法执行的是列表的线性查找,因此最坏的情况是所查找的元素不在列表中。
在这种情况下需要n个比较操作。
因此该方法平均需要n/2次比较操作,因而其复杂度为O(n)。
d)有序列表的add操作:
publicvoidadd(Telement){
if(size()==list.length)
Comparable<
temp=(Comparable<
)element;
intscan=0;
while(scan<
rear&
pareTo(list[scan])>
0)
scan++;
for(intscan2=rear;
scan2>
scan;
scan2--)
list[scan2]=list[scan2-1];
list[scan]=element;
rear++;
只有Comparable对象才能存储在有序列表中。
e)Comparable接口定义了comp
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习资料 java 期末考试