数据结构复习笔记

1第一章概论1.数据：信息的载体,能被计算机识别、存储和加工处理。2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7.抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。211.算法的时间复杂度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≤n5.顺序表上的基本运算publicinterfaceList{//返回线性表的大小，即数据元素的个数。publicintgetSize();//如果线性表为空返回true，否则返回false。publicbooleanisEmpty();//判断线性表是否包含数据元素epublicbooleancontains(Objecte);//将数据元素e插入到线性表中i号位置publicvoidinsert(inti,Objecte)throwsOutOfBoundaryException;//删除线性表中序号为i的元素,并返回之publicObjectremove(inti)throwsOutOfBoundaryException;//删除线性表中第一个与e相同的元素publicbooleanremove(Objecte);//返回线性表中序号为i的数据元素3publicObjectget(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;}//判断线性表是否包含数据元素epublicbooleancontains(Objecte){for(inti=0;isize;i++)if(e==elements[i])returntrue;returnfalse;}4//将数据元素e插入到线性表中i号位置publicvoidinsert(inti,Objecte)throwsOutOfBoundaryException{if(i0||isize)thrownewOutOfBoundaryException(错误，指定的插入序号越界。);if(size=elements.length)expandSpace();for(intj=size;ji;j--)elements[j]=elements[j-1];elements[i]=e;size++;return;}privatevoidexpandSpace(){Object[]a=newObject[elements.length*2];for(inti=0;ielements.length;i++)a[i]=elements[i];elements=a;}//删除线性表中序号为i的元素,并返回之publicObjectremove(inti)throwsOutOfBoundaryException{if(i0||i=size)thrownewOutOfBoundaryException(错误，指定的删除序号越界。);Objectobj=elements[i];for(intj=i;jsize-1;j++)elements[j]=elements[j+1];elements[--size]=null;returnobj;}//替换线性表中序号为i的数据元素为e，返回原数据元素publicObjectreplace(inti,Objecte)throwsOutOfBoundaryException{5if(i0||i=size)thrownewOutOfBoundaryException(错误，指定的序号越界。);Objectobj=elements[i];elements[i]=e;returnobj;}//返回线性表中序号为i的数据元素publicObjectget(inti)throwsOutOfBoundaryException{if(i0||i=size)thrownewOutOfBoundaryException(错误，指定的序号越界。);returnelements[i];}//删除线性表中第一个与e相同的元素publicbooleanremove(Objecte){inti=indexOf(e);if(i0)returnfalse;remove(i);returntrue;}}6.单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，datanextdata是数据域，next是指针域。（1）建立单链表。时间复杂度为O(n)。加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为O(n)。publicclassSLNodeimplementsNode{privateObjectelement;privateSLNodenext;publicSLNode(Objectele,SLNodenext){6this.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();7returnnull;}//辅助方法：获取序号为0=isize的元素所在结点的前驱结点privateSLNodegetPreNode(inti){SLNodep=head;for(;i0;i--)p=p.getNext();returnp;}//获取序号为0=isize的元素所在结点privateSLNodegetNode(inti){SLNodep=head.getNext();for(;i0;i--)p=p.getNext();returnp;}//返回线性表的大小，即数据元素的个数。publicintgetSize(){returnsize;}//如果线性表为空返回true，否则返回false。publicbooleanisEmpty(){returnsize==0;}//判断线性表是否包含数据元素epublicbooleancontains(Objecte){SLNodep=head.getNext();while(p!=null){if(p.getData()==e))returntrue;elsep=p.getNext();8}returnfalse;}//将数据元素e插入到线性表中i号位置publicvoidinsert(inti,Objecte)throwsOutOfBoundaryException{if(i0||isize)thrownewOutOfBoundaryException(错误，指定的插入序号越界。);SLNodep=getPreNode(i);SLNodeq=newSLNode(e,p.getNext());p.setNext(q);size++;return;}//删除线性表中序号为i的元素,并返回之publicObjectremove(inti)throwsOutOfBoundaryException{if(i0||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;}9returnfalse;}//替换线性表中序号为i的数据元素为e，返回原数据元素publicObjectreplace(inti,