实用数据结构复习资料

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

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

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

3、;while(i<=x){if(n%i==0)break;i++;iif(i>x)return1;elsereturn0;}二、线性表1、线性表的顺序存储(1)掌握顺序存储的概念：线性表的顺序存储足指用一组连续的存储羊元依次存放线性表的元素的存储方式。(2)顺序存储的类实现ArrayList1)常握System.Collections命名空间卜'系统类ArrayList的使用；(重点)重点挙握：插入、删除、查找(按值查找)算法publicvirtualintAddObjectobj)//添加操作publicvirtualvoidInsert(intindex

4、,Objectobj)//将元素插入ArrayList的指定索引处。publicvirtualvoidRemove(Objectobj)publicvirtualintlndexOf(Objectobj)//即Search，丧找某元素在ArrayList屮的位置。PublicvirtualintIndexOf(Objectobj,intpos)//搜索桁定的Object,并返回ArrayList屮从指定索引到//«活一个元素的元素范围内第一个匹配项的从零开始的索引。2)掌握ArrayList矣的使川(Main()方法的编写)，注意系统类ArrayList与&

5、己定义的ArrayList在使用吋是?T用法相同。3)掌捉自己创建的ArrayList炎；(提高要求)2、线性表的链式存储(1)掌握链式存储的概念链式存储是用一组任意的存储单元存储线性表的数拋元素,这组存储单元是任意散落在存储空间的，可以连续也可以不连续，不要求逻辑次序与物理次序上的一致。为了正确表示结点1川的逻辑关系，存储每个结点值的同时，还在需要存储一个指示接P继的信息(即直接后继的存储地址)。这两部分信息组成一个数裾元素的存储映象，称为结点。它包括两个域：存储结点伉的域(data)称为数据域，存储结点直接后继的存储位置的域(next)称为指针域。链表就

6、是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接起来的。链表的结点结构：datanext单链衣结点结构(2)单链表的类实现——LinkList重点掌握：插入、删除、杏找(按值、按序号杏找)算法publicvirtualNodeLocate(inti)//在链表中查找第i个结点，找到则返回该结点的引用，找不到则返回空引用publicvirtualNodeContains(intdatal)//在链表中査找值为datal的结点，找到返回该结点的引川，找不到，则返回空引川publicvirtualboolInsert(inti,intx)//在链表第i个位置

7、插入值为x的结点publicvirtualvoidRemoveAfter(Nodep)//删除p对象后的结点publicvirtualboolRemoveAt(inti)//删除第i个元素publicvirtualboolRemove(intx)//删除值为x的结点3)掌握LinkList类的使用(Main()方法的编写)。1.掌握顺序表和链表的优缺点比较三、栈1.掌握栈的操作原则：后进先出2.掌握系统类Stack(栈类)的使用：能运用Stack类解决简单的应用问题(秉点)3.掌握顺序存储的Stack类(顺序)，重点掌娓入栈出栈操作。4.掌握栈的链式存储的类

8、类型定义以及在链式存储下的算法实现；Stack类(链