数据结构总结复习笔记Word格式.docx
《数据结构总结复习笔记Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构总结复习笔记Word格式.docx（43页珍藏版）》请在冰点文库上搜索。
1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。
2）链接存储，结点间的逻辑关系由附加指针字段表示。
3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。
4）散列存储，按结点的关键字直接计算出存储地址。
10.评价算法的好坏是：
算法是正确的；
执行算法所耗的时间；
执行算法的存储空间（辅助存储空间）；
易于理解、编码、调试。
11.算法的时间复杂度T（n）：
是该算法的时间耗费，是求解问题规模n的函数。
记为O（n）。
时间复杂度按数量级递增排列依次为：
常数阶O
（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
13.算法的空间复杂度S（n）：
是该算法的空间耗费，是求解问题规模n的函数。
12.算法衡量：
是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。
13.算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
第二章线性表
1.线性表：
是由n（n≥0）个数据元素组成的有限序列。
3.顺序表：
把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。
4.顺序表结点的存储地址计算公式：
Loc（ai）=Loc（a1）+（i-1）*C；
1≤i≤n
5.顺序表上的基本运算
publicinterfaceList{
//返回线性表的大小，即数据元素的个数。
publicintgetSize（）;
//如果线性表为空返回true，否则返回false。
publicbooleanisEmpty（）;
//判断线性表是否包含数据元素e
publicbooleancontains（Objecte）;
//将数据元素e插入到线性表中i号位置
publicvoidinsert（inti,Objecte）throwsOutOfBoundaryException;
//删除线性表中序号为i的元素,并返回之
publicObjectremove（inti）throwsOutOfBoundaryException;
//删除线性表中第一个与e相同的元素
publicbooleanremove（Objecte）;
//返回线性表中序号为i的数据元素
publicObjectget（inti）throwsOutOfBoundaryException;
}
在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O（n）。
在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O（n）。
publicclassListArrayimplementsList{
privatefinalintLEN=8;
//数组的默认大小
privateStrategystrategy;
//数据元素比较策略
privateintsize;
//线性表中数据元素的个数
privateObject[]elements;
//数据元素数组
//构造方法
publicListArray（Strategystrategy）{
size=0;
elements=newObject[LEN];
publicintgetSize（）{
returnsize;
publicbooleanisEmpty（）{
returnsize==0;
//判断线性表是否包含数据元素e
publicbooleancontains（Objecte）{
for（inti=0;
i<
size;
i++）
if（e==elements[i]）returntrue;
returnfalse;
publicvoidinsert（inti,Objecte）throwsOutOfBoundaryException{
if（i<
0||i>
size）
thrownewOutOfBoundaryException（"
错误，指定的插入序号越界。
"
）;
if（size>
=elements.length）
expandSpace（）;
for（intj=size;
j>
i;
j--）
elements[j]=elements[j-1];
elements[i]=e;
size++;
return;
privatevoidexpandSpace（）{
Object[]a=newObject[elements.length*2];
elements.length;
a[i]=elements[i];
elements=a;
publicObjectremove（inti）throwsOutOfBoundaryException{
=size）
错误，指定的删除序号越界。
Objectobj=elements[i];
for（intj=i;
j<
size-1;
j++）
elements[j]=elements[j+1];
elements[--size]=null;
returnobj;
//替换线性表中序号为i的数据元素为e，返回原数据元素
publicObjectreplace（inti,Objecte）throwsOutOfBoundaryException{
错误，指定的序号越界。
publicObjectget（inti）throwsOutOfBoundaryException{
returnelements[i];
publicbooleanremove（Objecte）{
inti=indexOf（e）;
0）returnfalse;
remove（i）;
returntrue;
6.单链表：
只有一个链域的链表称单链表。
在结点中存储结点值和结点的后继结点的地址，datanextdata是数据域，next是指针域。
（1）建立单链表。
时间复杂度为O（n）。
加头结点的优点：
1）链表第一个位置的操作无需特殊处理；
2）将空表和非空表的处理统一。
（2）查找运算。
publicclassSLNodeimplementsNode{
privateObjectelement;
privateSLNodenext;
publicSLNode（Objectele,SLNodenext）{
this.element=ele;
this.next=next;
publicSLNodegetNext（）{
returnnext;
publicvoidsetNext（SLNodenext）{
publicObjectgetData（）{
returnelement;
publicvoidsetData（Objectobj）{
element=obj;
publicclassListSLinkedimplementsList{
privateSLNodehead;
//单链表首结点引用
publicListSLinked（）{
head=newSLNode（）;
size=0;
//辅助方法：
获取数据元素e所在结点的前驱结点
privateSLNodegetPreNode（Objecte）{
SLNodep=head;
while（p.getNext（）!
=null）
if（p.getNext（）.getData（）==e）
returnp;
elsep=p.getNext（）;
returnnull;
获取序号为0<
=i<
size的元素所在结点的前驱结点
privateSLNodegetPreNode（inti）{
SLNodep=head;
for（;
i>
0;
i--）
p=p.getNext（）;
//获取序号为0<
size的元素所在结点
privateSLNodegetNode（inti）{
SLNodep=head.getNext（）;
returnsize;
returnsize==0;
while（p!
=null）{
if（p.getData（）==e））returntrue;
}returnfalse;
if（i<
thrownewOutOfBoundaryException（"
SLNodep=getPreNode（i）;
SLNodeq=newSLNode（e,p.getNext（））;
p.setNext（q）;
size++;
return;
//删除线性表中序号为i的元素,并返回之
Objectobj=p.getNext（）.getData（）;
p.setNext（p.getNext（）.getNext（））;
size--;
returnobj;
publicbooleanremove（Objecte）{
SLNodep=getPreNode（e）;
if（p!
=null）{
returntrue;
}
returnfalse;
SLNodep=getNode（i）;
Objectobj=p.getData（）;
p.setData（e）;
returnp.getData（）;
7.循环链表：
是一种首尾相连的链表。
特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。
8.空循环链表仅由一个自成循环的头结点表示。
9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。
用头指针表示的单循环链表查找开始结点的时间是O
（1）,查找尾结点的时间是O（n）；
用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O
（1）。
10.在结点中增加一个指针域，prior|data|next。
形成的链表中有两条不同方向的链称为双链表。
publicclassDLNodeimplementsNode{
privateDLNodepre;
privateDLNodenext;
publicDLNode（Objectele,DLNodepre,DLNodenext）{
this.pre=pre;
publicDLNodegetNext（）{
publicvoidsetNext（DLNodenext）{
publicDLNodegetPre（）{
returnpre;
publicvoidsetPre（DLNodepre）{
returnelement;
publicclassLinkedListDLNodeimplementsLinkedList{
privateintsize;
//规模
privateDLNodehead;
//头结点,哑元结点
privateDLNodetail;
//尾结点,哑元结点
publicLinkedListDLNode（）{
head=newDLNode（）;
//构建只有头尾结点的链表
tail=newDLNode（）;
head.setNext（tail）;
tail.setPre（head）;
//辅助方法，判断结点p是否合法，如合法转换为DLNode
protectedDLNodecheckPosition（Nodep）throwsInvalidNodeException{
if（p==null）
thrownewInvalidNodeException（"
错误：
p为空。
if（p==head）
p指向头节点，非法。
if（p==tail）
p指向尾结点，非法。
DLNodenode=（DLNode）p;
returnnode;
//查询链接表当前的规模
//判断链接表是否为空
//返回第一个结点
publicNodefirst（）throwsOutOfBoundaryException{
if（isEmpty（））
链接表为空。
returnhead.getNext（）;
//返回最后一结点
publicNodelast（）throwsOutOfBoundaryException{
returntail.getPre（）;
//返回p之后的结点
publicNodegetNext（Nodep）throwsInvalidNodeException,OutOfBoundaryException{
DLNodenode=checkPosition（p）;
node=node.getNext（）;
if（node==tail）
已经是链接表尾端。
//返回p之前的结点
publicNodegetPre（Nodep）throwsInvalidNodeException,OutOfBoundaryException{
node=node.getPre（）;
if（node==head）
已经是链接表前端。
//将e作为第一个元素插入链接表
publicNodeinsertFirst（Objecte）{
DLNodenode=newDLNode（e,head,head.getNext（））;
head.getNext（）.setPre（node）;
head.setNext（node）;
//将e作为最后一个元素插入列表,并返回e所在结点
publicNodeinsertLast（Objecte）{
DLNodenode=newDLNode（e,tail.getPre（）,tail）;
tail.getPre（）.setNext（node）;
tail.setPre（node）;
//删除给定位置处的元素，并返回之
publicObjectremove（Nodep）throwsInvalidNodeException{
Objectobj=node.getData（）;
node.getPre（）.setNext（node.getNext（））;
node.getNext（）.setPre（node.getPre（））;
//删除首元素，并返回之
publicObjectremoveFirst（）throwsOutOfBoundaryException{
returnremove（head.getNext（））;
//删除末元素，并返回之
publicObjectremoveLast（）throwsOutOfBoundaryException{
returnremove（tail.getPre（））;
//将处于给定位置的元素替换为新元素，并返回被替换的元素
publicObjectreplace（Nodep,Objecte）throwsInvalidNodeException{
node.setData（e）;
11.顺序表和链表的比较
1）?
基于空间的考虑：
顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。
顺序表的存储密度比链表大。
因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。
2）?
基于时间的考虑：
顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。
对频繁进行插入、删除操作的线性表宜采用链表。
若操作主要发生在表的首尾时采用尾指针表示的单循环链表。
12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）
存储密度：
顺序表=1，链表<
1。
升级会员 