数据结构（牛小飞）数据结构复习指南

《数据结构（牛小飞）数据结构复习指南》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构复习指南第一章引论1、理解数据元素是数据的基本单位、数据项是最小单位。2、理解数据结构的概念：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。掌握数据结构的逻辑结构有四种：集合结构（无关系）、线性结构（一对一）、树形结构（一对多）、图状或网状结构（多对多）掌握数据结构的物理（存储）结构有两种：顺序存储结构和链式存储结构（1）顺序存储结构：用一段地址连续的存储单元依次存储数据元素，逻辑上相邻的数据元素物理位置上一定（必须）相邻，即物理上相邻表示逻辑上相邻。（2）链式存储结构：逻辑上相邻的数据元素物理位置上不一定相邻，为了表示元素之间的关系，在存储数据元素的同时要存储其后继

2、的地址，所以链式存储结构借助指针（地址）表示元素之间的逻辑关系。3、理解递归的含义：递归体现为一个函数调用自身。掌握递归必须有两部分,（1）基准情形：无须递归就能求解，即递归结束条件；（2）不断推进：需耍递归求解的情形，每一次递归调用都必须使状况朝向一种基准情形推进，即规模耍不断变小。4、理解泛型的概念和实现方法第二章算法和算法分析1、理解算法的定义；掌握算法的特点（输入、输岀、有穷性、确定性和可行性）和设计原则（正确性、可读性、健壮性、高效率和低存储）2、掌握算法分析包括时间复杂性分析和空间复杂性分析。3、掌握渐进时间复杂性分析方法，掌握常用阶：常数阶0⑴＜对数阶O（logn）＜对数平

3、方阶O（log2n）＜线性阶0（n）＜线性对数阶O（nlogn）＜平方阶0（『）＜立方阶0（n3）＜……＜K次方阶0（nk）＜指数阶0（2n）第三章表、栈和队列1、理解线性表的特点：（1）存在唯一的第一个元素；（2）存在唯一的最后一个元素；（3）除第一个元素外，每一个元素均只有一个前驱；（4）除最后一个元素外，每一个元素均只有一个后继。2、掌握线性表顺序存储（顺序表）的定义与实现（课本P53-54）,课件上也有。3、掌握线性表链式存储（带头结点的单链表）的定义与实现classNode＜AnyType＞{publicAnyTypedata;publicNode＜AnyType＞next;p

4、ublicNode（AnyTypedzNode＜AnyType＞n）{this.data=d;this.next=n;}publicNode(AnyTyped){this.data=d;this.next=null;}publicNode(){this・data=null;this.next=null;}}publicclassSheadLinkedListheadNode;〃头节点publicSheadLinkedLis

5、t(){〃构造带头节点的单链表Nodep=newNode();headNode=p;theSize=0;}publicintSize(){returntheSize;}publicAnyTypeget(intidx){returngetNode(idx).data;}privateNode=Size())thrownewIndexOutOfBoundsException(宠etNodeindex:H+idx+size:"+size());Nodep;p=hea

6、dNode;〃指向头节点for(inti=0;ip=getNode(idx);AnyTypeoldVahp.data;p.data=newVal;returnoldVal;}publicbooleanadd(AnyTypex){add(size(),x);returntrue;}publicvoidadd(intidx,AnyTypex){if(idx<011idx>Size())thrownewIndexOutOfBoundsE

7、xception("addNodeindex:"+idx+size:"+size());NodenewNode=newNode(x);Node