实用数据结构 复习资料

《实用数据结构 复习资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《实用数据结构》期末复习知识点梳理一、数据结构基本概念1.掌握数据结构、逻辑结构、物理结构等基本概念数据结构（DataStructure）是指数据及数据之间的相互关系，即数据的组织形式。它一般包括以下三个方面的内容：1)逻辑结构：数据元素之间的相互联系，也称为数据的逻辑结构（LogicalStructure）。有三种逻辑结构：线性结构（一对一）、树状结构（一对多）、图（多对多）。2)物理结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）。基本的存储方式有顺序存储、链式存储、索引存储、散列存储（哈希存储）四种。3)数据的运算（算法

2、），即对数据施加的操作。2.掌握算法评价标准、时间复杂度、空间复杂度的估算方法算法：对特定问题求解步骤的一种描述。算法设计要求：正确性、可读性、健壮性、高效率、低存贮算法评价三标准：执行算法所耗费的时间——时间复杂度执行算法所耗费的存储空间（主要是辅助空间）——空间复杂度算法应易于理解、易于编码、易于调试估算时间复杂度：例1：for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;例2：i=1;while(i

3、==0)break;i++;}if(i>x)return1;elsereturn0;}二、线性表1、线性表的顺序存储（1）掌握顺序存储的概念：线性表的顺序存储是指用一组连续的存储单元依次存放线性表的元素的存储方式。（2）顺序存储的类实现——ArrayList1)掌握System.Collections命名空间下系统类ArrayList的使用；（重点）重点掌握：插入、删除、查找（按值查找）算法publicvirtualintAddObjectobj)//添加操作publicvirtualvoidInsert(intindex,Objectobj)//将元素插入ArrayList的

4、指定索引处。publicvirtualvoidRemove(Objectobj)publicvirtualintIndexOf(Objectobj)//即Search,查找某元素在ArrayList中的位置。PublicvirtualintIndexOf(Objectobj,intpos)//搜索指定的Object，并返回ArrayList中从指定索引到//最后一个元素的元素范围内第一个匹配项的从零开始的索引。2）掌握ArrayList类的使用（Main()方法的编写），注意系统类ArrayList与自己定义的ArrayList在使用时是否用法相同。3）掌握自己创建的Array

5、List类；(提高要求)2、线性表的链式存储（1）掌握链式存储的概念链式存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元是任意散落在存储空间的，可以连续也可以不连续，不要求逻辑次序与物理次序上的一致。为了正确表示结点间的逻辑关系，存储每个结点值的同时，还在需要存储一个指示其直接后继的信息（即直接后继的存储地址）。这两部分信息组成一个数据元素的存储映象，称为结点。它包括两个域：存储结点值的域（data）称为数据域，存储结点直接后继的存储位置的域（next）称为指针域。链表就是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接起来的。链表的结点结构：datanext单

6、链表结点结构（2）单链表的类实现——LinkList重点掌握：插入、删除、查找（按值、按序号查找）算法publicvirtualNodeLocate(inti)//在链表中查找第i个结点，找到则返回该结点的引用，找不到则返回空引用publicvirtualNodeContains(intdata1)//在链表中查找值为data1的结点，找到返回该结点的引用，找不到，则返回空引用publicvirtualboolInsert(inti,intx)//在链表第i个位置插入值为x的结点publicvirtualvoidRemoveAfter(Nodep)//删除p对象后的结点publ

7、icvirtualboolRemoveAt(inti)//删除第i个元素publicvirtualboolRemove(intx)//删除值为x的结点3)掌握LinkList类的使用（Main()方法的编写）。3．掌握顺序表和链表的优缺点比较三、栈1.掌握栈的操作原则：后进先出2.掌握系统类Stack（栈类）的使用：能运用Stack类解决简单的应用问题（重点）3．掌握顺序存储的Stack类（顺序），重点掌握入栈出栈操作。4.掌握栈的链式存储的类类型定义以及在链式存储下的算法实现；Stack类