数据结构复习资料.doc

数据结构复习资料.doc

ID:51908256

大小:832.00 KB

页数:11页

时间:2020-03-18

数据结构复习资料.doc_第1页
数据结构复习资料.doc_第2页
数据结构复习资料.doc_第3页
数据结构复习资料.doc_第4页
数据结构复习资料.doc_第5页
资源描述:

《数据结构复习资料.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、数据(Data):信息的载体,它能够被计算机识别、存储和加工处理。数据元素是数据基本单位。数据一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。数据元素之间的逻辑关系简称为数据结构,存储结构是数据元素及其关系在计算机存储器内的表示,称为数据的存储结构它分为线性结构和非线性结构。栈、队列、串等都是线性结构,非线性结构:数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 ,数据存储方法有:1.顺序存储方法2.链接存储方法3.索引存储方法4.散列存储方法算法的时间复杂度不仅与问题的

2、规模相关,还与输入实例中的初始状态有关。但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定。把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里用这种方法存储的线性表这顺序表。把与树对应的广义表称为纯表.它限制了表中成分的共享和递归;把允许结点共享的表称为再入表把允许递归的表称为递归表数据项(DataItem):具有独立意义的最小数据单位,是对数据元素属性的描述。数据项也称域或字段。10.数据结构(DataStruct

3、ure):指的是数据之间的相互关系,即数据的组织形式。11.数据元素之间的逻辑关系,也称为数据的逻辑结构(LogicalStructrue);12.数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(StorageStructure);13.算法的空间复杂度(SpaceComplexity):当问题的规模以某种单位由1增至n时,解决该问题的算法实现所占用的空间也以某种单位由1增至f(n),则称该算法的空间复杂度是f(n)。14.语句频度(FrequencyCount):指的是该语句重复执行的次数。15.线性表(LinearList):是由n(n>0)个

4、性质相同的数据元素组成的有限序列16.顺序表:即用一组连续的存储单元依次存放线性表的数据元素17.链表(LinkedList):用链接存储方式存储的线性表28.若链表中每个结点只包含一个指针域,则称此链表为单链表(SingleLinked)。19.存储数据元素信息的域称为数据域20.存储直接后继存储位置的域称为指针域21.循环链表(CircularLinkedList):就是将单向链表中的最后一个结点的指针指向链表中第一个结点,使整个链表构成一个环形。22.双(向)链表(DoubleLinkedList):有两种不同方向链的链表称为双向循环链表。23.栈(St

5、ack):是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。24.串是零个或多个字符组成的有限序列。25.长度为零的串称为空串。26.数据结构由数据的逻辑结构、存储结构和数据的运算三部分组成27.串中任意个连续字符组成的子序列称为串的子串(模式),包含子串的串相应地称为主串(目标).28.空串是任意串的子串,任意串是其自身的子串。29.串的顺序存储结构简称为顺序串30.用单链表方式来存储串值,串的这种链式存储结构简称为链串。31.森林是m(m>=0)棵互不相交的树的集合32.高度(深度)是树

6、中结点的最大层数33.二叉树是n(n>=0)个结点的有限集合。34.文件是性质相同的记录集合,文件上的操作方要有两类:检索和维护。35.文件基本的组织方式有四种:顺序组织,索引组识,散列组织和链组织。36.在有向图中,把顶点v为终点的边的数目,称为v的入度37.在有向图中,把顶点v为始点的边的数目,称为v的出度38.对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列称为深度优先遍历(DFS序列)39.对图进行用树的按层次遍历时,按访问顶点的先后次序得到的顶点序列称为广度优先遍历(BFS序列)40.经过排序后这些具相同关键字的记录之间的相对次序保持不变,

7、称这种排序方法是稳定41.经过排序后这些具相同关键字的记录之间的相对次序发生变化,称这种排序方法是不稳定42.稳定的排序方法有直接插入排序,冒泡排序,归并排序,基数排序43.不稳定的排序方法有希尔排序,快速排序,直接选择排序,堆排序44.插入排序方法:直接插入排序和希尔排序45.交换排序方法:冒泡排序和快速排序46.选择排序方法:直接选择排序和堆排序47.平方阶0(n2)排序,一般称为间单,例如直接插入,直接排序和冒泡排序48.线性对数阶(0(nlgn))排序,如快速,堆,归并排序。49.线性阶(0(n))排序,如桶,箱和基数排序50.0(n1+@)阶排序,@

8、是介于0和1之间的常数,0<@<1,如

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。