数据结构复习笔记.docx
- 文档编号:13664674
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:48
- 大小:359.54KB
数据结构复习笔记.docx
《数据结构复习笔记.docx》由会员分享,可在线阅读,更多相关《数据结构复习笔记.docx(48页珍藏版)》请在冰点文库上搜索。
数据结构复习笔记
数据结构复习笔记
第一章概论
1.数据:
信息的载体,能被计算机识别、存储和加工处理。
2.数据元素:
数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位。
3.数据结构:
数据之间的相互关系,即数据的组织形式。
它包括:
1)数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机;
2)数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言。
3)数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合。
常用的运算:
检索/插入/删除/更新/排序。
4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
数据的存储结构是逻辑结构用计算机语言的实现。
5.数据类型:
一个值的集合及在值上定义的一组操作的总称。
分为:
原子类型和结构类型。
6.抽象数据类型:
抽象数据的组织和与之相关的操作。
优点:
将数据和操作封装在一起实现了信息隐藏。
7.抽象数据类型ADT:
是在概念层上描述问题;类:
是在实现层上描述问题;在应用层上操作对象(类的实例)解决问题。
8.数据的逻辑结构,简称为数据结构,有:
(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。
9.数据的存储结构有:
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;
}
//如果线性表为空返回true,否则返回false。
publicbooleanisEmpty(){
returnsize==0;
}
//判断线性表是否包含数据元素e
publicbooleancontains(Objecte){
for(inti=0;i if(e==elements[i])returntrue; returnfalse; } //将数据元素e插入到线性表中i号位置 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]; for(inti=0;i a[i]=elements[i]; elements=a; } //删除线性表中序号为i的元素,并返回之 publicObjectremove(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的删除序号越界。 "); Objectobj=elements[i]; for(intj=i;j elements[j]=elements[j+1]; elements[--size]=null; returnobj; } //替换线性表中序号为i的数据元素为e,返回原数据元素 publicObjectreplace(inti,Objecte)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。 "); Objectobj=elements[i]; elements[i]=e; returnobj; } //返回线性表中序号为i的数据元素 publicObjectget(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。 "); returnelements[i]; } //删除线性表中第一个与e相同的元素 publicbooleanremove(Objecte){ inti=indexOf(e); if(i<0)returnfalse; remove(i); returntrue; } } 6.单链表: 只有一个链域的链表称单链表。 在结点中存储结点值和结点的后继结点的地址,datanextdata是数据域,next是指针域。 (1)建立单链表。 时间复杂度为O(n)。 加头结点的优点: 1)链表第一个位置的操作无需特殊处理;2)将空表和非空表的处理统一。 (2)查找运算。 时间复杂度为O(n)。 publicclassSLNodeimplementsNode{ privateObjectelement; privateSLNodenext; publicSLNode(Objectele,SLNodenext){ this.element=ele; this.next=next; } publicSLNodegetNext(){ returnnext; } publicvoidsetNext(SLNodenext){ this.next=next; } publicObjectgetData(){ returnelement; } publicvoidsetData(Objectobj){ element=obj; } } publicclassListSLinkedimplementsList{ privateSLNodehead;//单链表首结点引用 privateintsize;//线性表中数据元素的个数 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 privateSLNodegetPreNode(inti){ SLNodep=head; for(;i>0;i--) p=p.getNext(); returnp; } //获取序号为0<=i privateSLNodegetNode(inti){ SLNodep=head.getNext(); for(;i>0;i--) p=p.getNext(); returnp; } //返回线性表的大小,即数据元素的个数。 publicintgetSize(){ returnsize; } //如果线性表为空返回true,否则返回false。 publicbooleanisEmpty(){ returnsize==0; } //判断线性表是否包含数据元素e publicbooleancontains(Objecte){ SLNodep=head.getNext(); while(p! =null){ if(p.getData()==e))returntrue; elsep=p.getNext(); }returnfalse; } //将数据元素e插入到线性表中i号位置 publicvoidinsert(inti,Objecte)throwsOutOfBoundaryException{ if(i<0||i>size) thrownewOutOfBoundaryException("错误,指定的插入序号越界。 "); SLNodep=getPreNode(i); SLNodeq=newSLNode(e,p.getNext()); p.setNext(q); size++; return; } //删除线性表中序号为i的元素,并返回之 publicObjectremove(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的删除序号越界。 "); SLNodep=getPreNode(i); Objectobj=p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; returnobj; } //删除线性表中第一个与e相同的元素 publicbooleanremove(Objecte){ SLNodep=getPreNode(e); if(p! =null){ p.setNext(p.getNext().getNext()); size--; returntrue; } returnfalse; } //替换线性表中序号为i的数据元素为e,返回原数据元素 publicObjectreplace(inti,Objecte)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。 "); SLNodep=getNode(i); Objectobj=p.getData(); p.setData(e); returnobj; } //返回线性表中序号为i的数据元素 publicObjectget(inti)throwsOutOfBoundaryException{ if(i<0||i>=size) thrownewOutOfBoundaryException("错误,指定的序号越界。 "); SLNodep=getNode(i); returnp.getData(); } } 7.循环链表: 是一种首尾相连的链表。 特点是无需增加存储量,仅对表的链接方式修改使表的处理灵活方便。 8.空循环链表仅由一个自成循环的头结点表示。 9.很多时候表的操作是在表的首尾位置上进行,此时头指针表示的单循环链表就显的不够方便,改用尾指针rear来表示单循环链表。 用头指针表示的单循环链表查找开始结点的时间是O (1),查找尾结点的时间是O(n);用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O (1)。 10.在结点中增加一个指针域,prior|data|next。 形成的链表中有两条不同方向的链称为双链表。 publicclassDLNodeimplementsNode{ privateObjectelement; privateDLNodepre; privateDLNodenext; publicDLNode(Objectele,DLNodepre,DLNodenext){ this.element=ele; this.pre=pre; this.next=next; } publicDLNodegetNext(){ returnnext; } publicvoidsetNext(DLNodenext){ this.next=next; } publicDLNodegetPre(){ returnpre; } publicvoidsetPre(DLNodepre){ this.pre=pre; } publicObjectgetData(){ returnelement; } publicvoidsetData(Objectobj){ element=obj; } } publicclassLinkedListDLNodeimplementsLinkedList{ privateintsize;//规模 privateDLNodehead;//头结点,哑元结点 privateDLNodetail;//尾结点,哑元结点 publicLinkedListDLNode(){ size=0; head=newDLNode();//构建只有头尾结点的链表 tail=newDLNode(); head.setNext(tail); tail.setPre(head); } //辅助方法,判断结点p是否合法,如合法转换为DLNode protectedDLNodecheckPosition(Nodep)throwsInvalidNodeException{ if(p==null) thrownewInvalidNodeException("错误: p为空。 "); if(p==head) thrownewInvalidNodeException("错误: p指向头节点,非法。 "); if(p==tail) thrownewInvalidNodeException("错误: p指向尾结点,非法。 "); DLNodenode=(DLNode)p; returnnode; } //查询链接表当前的规模 publicintgetSize(){ returnsize; } //判断链接表是否为空 publicbooleanisEmpty(){ returnsize==0; } //返回第一个结点 publicNodefirst()throwsOutOfBoundaryException{ if(isEmpty()) thrownewOutOfBoundaryException("错误: 链接表为空。 "); returnhead.getNext(); } //返回最后一结点 publicNodelast()throwsOutOfBoundaryException{ if(isEmpty()) thrownewOutOfBoundaryException("错误: 链接表为空。 "); returntail.getPre(); } //返回p之后的结点 publicNodegetNext(Nodep)throwsInvalidNodeException,OutOfBoundaryException{ DLNodenode=checkPosition(p); node=node.getNext(); if(node==tail) thrownewOutOfBoundaryException("错误: 已经是链接表尾端。 "); returnnode; } //返回p之前的结点 publicNodegetPre(Nodep)throwsInvalidNodeException,OutOfBoundaryException{ DLNodenode=checkPosition(p); node=node.getPre(); if(node==head) thrownewOutOfBoundaryException("错误: 已经是链接表前端。 "); returnnode; } //将e作为第一个元素插入链接表 publicNodeinsertFirst(Objecte){ DLNodenode=newDLNode(e,head,head.getNext()); head.getNext().setPre(node); head.setNext(node); size++; returnnode; } //将e作为最后一个元素插入列表,并返回e所在结点 publicNodeinsertLast(Objecte){ DLNodenode=newDLNode(e,tail.getPre(),tail); tail.getPre().setNext(node); tail.setPre(node); size++; returnnode; } //删除给定位置处的元素,并返回之 publicObjectremove(Nodep)throwsInvalidNodeException{ DLNodenode=checkPosition(p); Objectobj=node.getData(); node.getPre().setNext(node.getNext()); node.getNext().setPre(node.getPre()); size--; returnobj; } //删除首元素,并返回之 publicObjectremoveFirst()throwsOutOfBoundaryException{ returnremove(head.getNext()); } //删除末元素,并返回之 publicObjectremoveLast()throwsOutOfBoundaryException{ returnremove(tail.getPre()); } //将处于给定位置的元素替换为新元素,并返回被替换的元素 publicObjectreplace(Nodep,Objecte)throwsInvalidNodeException{ DLNodenode=checkPosition(p); Objectobj=node.getData(); node.setData(e); returnobj; } } 11.顺序表和链表的比较 1) 基于空间的考虑: 顺序表的存储空间是静态分配的,链表的存储空间是动态分配的。 顺序表的存储密度比链表大。 因此,在线性表长度变化不大,易于事先确定时,宜采用顺序表作为存储结构。 2) 基于时间的考虑: 顺序表是随机存取结构,若线性表的操作主要是查找,很少有插入、删除操作时,宜用顺序表结构。 对频繁进行插入、删除操作的线性表宜采用链表。 若操作主要发生在表的首尾时采用尾指针表示的单循环链表。 12.存储密度=(结点数据本身所占的存储量)/(整个结点结构所占的存储总量) 存储
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 笔记